Dynamic vector of void* in C

Question 1

I have implemented a simple dynamic vector library in C. It is a header-only library.

Full library listing -void_vector.h:

#ifndef VOID_VECTOR_H#define VOID_VECTOR_Htypedef enum {    VV_SUCCESS,    VV_MALLOC_FAILURE} vv_err;typedef struct vv {    size_t length;    size_t size;    void *data[];} void_vector;void_vector* new_void_vector(size_t size);vv_err vv_push(void_vector **vv, void *el);void *vv_pop(void_vector *vv);const void* vv_read_index(void_vector *vv, size_t index);void delete_void_vector(void_vector *vv, void (del_el)(void*));#ifdef VOID_VECTOR_IMPL#undef VOID_VECTOR_IMPL#include <stdlib.h>#define defualt_size 16ulvoid_vector*new_void_vector(size_t size){    if (!size) size = defualt_size;    void_vector* vv = malloc(sizeof(void_vector) + sizeof(void*) * size);    if (vv) {        vv->size = size;        vv->length = 0;    }    return vv;}vv_errvv_push(void_vector **vv, void *el){    if ((*vv)->length >= (*vv)->size) {        void_vector *new_vv = realloc((*vv), sizeof(void_vector)                                            + sizeof(void*) * (*vv)->size * 2);        if (!new_vv) return VV_MALLOC_FAILURE;        (*vv) = new_vv;        (*vv)->size *= 2;    }    (*vv)->data[(*vv)->length] = el;    (*vv)->length++;    return VV_SUCCESS;}void*vv_pop(void_vector *vv){    if(vv->length == 0) return NULL;    vv->length--;    return vv->data[vv->length];}const void*vv_read_index(void_vector *vv, size_t index){    if (index > vv->length) return NULL;    return (vv->data[index]);}voiddelete_void_vector(void_vector *vv, void (del_el)(void*)){    if (!del_el) del_el = &free;    for (int i = vv->length; i; i--) {        del_el(vv->data[i-1]);    }    free(vv);}#endif /* VOID_VECTOR_IMPL */#endif /* VOID_VECTOR_H */

I am using this as test bench -void_vector_tb.c

#include <stdio.h>#define VOID_VECTOR_IMPL#include "void_vector.h"intmain (int argc, char **argv){    void_vector* vv = new_void_vector(4);    char *strings[10];    for (int i = 0; i < 10; i++) {        strings[i] = malloc(32);        snprintf(strings[i], 32, "This is String: %d", i);     }    for (int i = 0; i < 10; i++) {        vv_push(&vv, strings[i]);    }    for (int i = 0; i < vv->length; i++) {        printf("%d:\t%s\n", i+1, vv_read_index(vv, i));    }    char *s;    while(s = (char*) vv_pop(vv)) {        printf("%s\n", s);    }    for (int i = 0; i < 10; i++) {        vv_push(&vv, strings[i]);    }    delete_void_vector(vv, NULL);}

I am not using a make file. Compilation is performed bygcc -ggdb void_vector_tb.c -o void_vector_tb

I would greatly appreciate your time and any comments but I'm particularly interested in the following points:

Am I doing anything dangerous in this?
Is the code clear, what can I do to make it easier to follow?
Is there an obvious way to greatly improve the efficiency?
General style comments
I'm not overly concerned about the contents ofvoid_vector_tb.c.

I ran this through valgrind and got the following output:

==7009== HEAP SUMMARY:==7009==     in use at exit: 0 bytes in 0 blocks==7009==   total heap usage: 14 allocs, 14 frees, 1,616 bytes allocated==7009== ==7009== All heap blocks were freed -- no leaks are possible==7009== ==7009== For counts of detected and suppressed errors, rerun with: -v==7009== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

I am trying to minimize use of external libraries (although I don't think it would be possible to avoid stdlib.h).

Question 2

"Am I doing anything dangerous in this?" Yeah you are using void pointers :) They tend to kill type safety and there are many better ways of generic programming.

Question 3

Overall, fairly good.

Am I doing anything dangerous in this?

Lack of comments

I'd expect at least some commentary about the roll of the functions and how to use them near the function declaration section.

Assume a user will read the header and not delve into implementation.

Unexpected type change

The stored ellement is avoid *, changing the return type toconst is not good.

// const void* vv_read_index(void_vector *vv, size_t index)void* vv_read_index(void_vector *vv, size_t index)

Overuse ofNULL

vv_pop(), vv_read_index() returnNULL as an error indicator and can returnNULL as a valid return. IfNULL is not to be allowed (which I think is a bad idea) as a storablevoid *,vv_push(&vv, NULL) should error.

I'd re-work calls to return an error code onvv_pop(), likevv_err vv_pop(void_vector **vv, void **el).

It seems odd to have 2 forms of error signaling: error codes andNULL.

"default size"

I see no real value in a default size of 16. Suggest setting asidesize == 0 as something special and allow an initial vector size of 0. Add code to handle doubling array size when size is 0.

Create aVV_DEFAULT_SIZE 16u if desired for the user to call withnew_void_vector(VV_DEFAULT_SIZE).

Overflow

I'd detect overflow in size computations.

Tolerate freeingNULL

free(NULL) is well defined. I'd expect the same withdelete_void_vector(NULL, foo). Currently code dies on this.

Is the code clear, what can I do to make it easier to follow?

Naming convention

Recommend to use the same one prefix with all external types, names and functions.

// void_vector.hvv.h// VOID_VECTOR_HVV_H// void_vector* new_void_vector(size_t size);void_vector* vv_new(size_t size);

Or usevoid_vector instead ofvv throughout, not both.

Allocate to the size of the object, not type

Allocating to the size of the referenced object is 1) less error prone, 2) easier to review 3) easier to maintain than allocating to the type.

// void_vector* vv = malloc(sizeof(void_vector) + sizeof(void*) * size);void_vector* vv = malloc(sizeof *vv + sizeof *vv->data * size);

Avoid unnecessary suffixes

AnL,l,LL,ll is needed a lot less than one thinks. In the following case,L certainty not needed. Theuis useful though. I am curios as to why OP thought is was needed - what issue was of concern?

/// #define defualt_size 16ul#define defualt_size 16u

Useconst

const would help convey that the function is not altering*vv

// vv_read_index(void_vector *vv ...vv_read_index(const void_vector *vv ...

Is there an obvious way to greatly improve the efficiency?

Allocations only increase asvv_pop() does not reduce things. This can make for an inefficiency of memory usage.

IMO, a more advanced scheme could decrease by 1/2 when size needed falls below 25% or 33%.

General style comments

Spell check

// #define defualt_size 16ul#define default_size 16ul

! vs.>

Minor: With arithmetic concerns,> is more readily understood that! negation.

// if (!size)if (size > 0)

I'm not overly concerned about the contents of void_vector_tb.c.

Avoid naked magic numbers

Replace10 with#define VV_STR_N 10,32 with#define VV_STR_SZ 32,

Cast not needed

// while(s = (char*) vv_pop(vv)) {while(s = vv_pop(vv)) {

Question 4

First off thank you for the detailed and extended review. I will make your recommended changes this evening. I have a single follow up question. Currently the functionconst void* vv_read_index(vv, i) returns aconst void* and you are recommending it should returnvoid*.Originally I did this as I considered the returned value to "belong" to the the vector and did not want the user changing it. Is there a better way to achieve this without confusing types or do I just trust the user not to corrupt the data store?

Question 5

@eternalnewbievv stores apointer. Returningconst void * orvoid * does not allow the use to change thepointer stored invv. Returningconst void * does not allow the use to change what the pointer points to. That is notvv concern sovv_read_index() should return what it was given, avoid *. It sounds like to are thinking about returning the address of the pointer:

const void** vv_index_address(void_vector *vv, size_t index) {     if (index > vv->length) return NULL;     return (&vv->data[index]); }

Question 6

I was trying to avoid a situation where the user would callp = vv_read_index(vv, i); thenfree(p); finally followed bydelete_vv(vv);. This would cause double a free() which would be UB. I tried this out and it works and it works fine.

Question 7

I think my best option is to take your advice and return void*. But also note in the usage comments and readme about the potential UB.

Question 8

I now seewhy you coded a return ofconst. Yet the memory management of thevoid* pointers is not really the concern ofvv.

Question 9

I have two things to add to @chux's comments.

Thevv_read_index function can read past the end of the vector ifindex is equal tovv->length. Ifvv->length == vv->size, this will read past the end of allocated memory.

While the cast inwhile(s = (void *) vv_pop(vv)) is not needed, the use of an assignment within a conditional test can be misread as a typo. (Some compilers will issue a warning when you do this.) To clarify the intent, you can use

while((s = vv_pop(vv)) != NULL)

chux 36.5k2 gold badges43 silver badges97 bronze badges · Accepted Answer · 2019-03-04 09:33:33Z