Dynamic vector of void* in C

Question

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_H
typedef 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 16ul
void_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_err
vv_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]);
}
void
delete_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"
int
main (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 by gcc -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 of void_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).

• Lundin: "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.

Answer 1

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 a void *, changing the return type to const 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 of NULL

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

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

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

"default size"

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

Create a VV_DEFAULT_SIZE 16u if desired for the user to call with new_void_vector(VV_DEFAULT_SIZE).

Overflow

I'd detect overflow in size computations.

Tolerate freeing NULL

free(NULL) is well defined. I'd expect the same with delete_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.h
vv.h
// VOID_VECTOR_H
VV_H
// void_vector* new_void_vector(size_t size);
void_vector* vv_new(size_t size);

Or use void_vector instead of vv 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

An L, l, LL, ll is needed a lot less than one thinks. In the following case, L certainty not needed. The u is 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

Use const

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 as vv_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

Replace 10 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)) {

• eternal newbie: 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 function const void* vv_read_index(vv, i) returns a const void* and you are recommending it should return void*.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?
• chux: @eternalnewbie vv stores a pointer. Returning const void * or void * does not allow the use to change the pointer stored in vv. Returning const void * does not allow the use to change what the pointer points to. That is not vv concern so vv_read_index() should return what it was given, a void *. 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]); }
• eternal newbie: I was trying to avoid a situation where the user would call p = vv_read_index(vv, i); then free(p); finally followed by delete_vv(vv);. This would cause double a free() which would be UB. I tried this out and it works and it works fine.
• eternal newbie: 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.
• chux: I now see why you coded a return of const. Yet the memory management of the void* pointers is not really the concern of vv.

Answer 2

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

The vv_read_index function can read past the end of the vector if index is equal to vv->length. If vv->length == vv->size, this will read past the end of allocated memory.

While the cast in while(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)