C generic typesafe dynamic array (vector) try 2

Question

The previous generic dynamic array I asked a review for here was written using only the preprocessor and so while the array itself was type-safe, all the manipulating macros where not.

In this try I wrote a dynamic array that stores the element size, and then a macro interface that hides it as an implementation detail. I also took advice from the previous review and removed the arrayMap(array,callback) macro and replaced it with VEC_FOREACH(index_variable_name, vec) which is simply a wrapper around a for loop.

A note on memory allocation: as I'm still testing this array, I didn't add any code to gracefully handle memory allocation errors yet.

The code is currently in a single file, and isn't ready yet to be included by other files yet.

#include <stdint.h> #include <stdlib.h> #include <stddef.h> // offsetof #include <assert.h> typedef struct vec_header { uint32_t used; uint32_t capacity; uint32_t element_size; char data[]; } VecHeader; union align { int i; long l; long *lp; void *p; void (*fp)(void); float f; double d; long double ld; }; union header { VecHeader h; union align a; }; VecHeader *_vec_make_header(uint32_t element_size, uint32_t capacity) { VecHeader *h = calloc(1, element_size * capacity + sizeof(union header)); assert(h); h->capacity = capacity; h->element_size = element_size; return h; } static inline VecHeader *_vec_to_header(void *vec) { assert(vec); return vec - offsetof(VecHeader, data); } void _vec_free_header(VecHeader *h) { free(h); } void _vec_ensure_capacity(void **vec, uint32_t capacity) { assert(vec && *vec); VecHeader *h = _vec_to_header(*vec); if(h->used >= capacity) { return; } h->capacity = capacity; h = realloc(h, h->element_size * h->capacity +sizeof(union header)); assert(h); *vec = (void *)h->data; } void *_vec_prepare_push(void **vec) { assert(vec && *vec); VecHeader *h = _vec_to_header(*vec); if(h->used + 1 > h->capacity) { h->capacity *= 2; h = realloc(h, h->element_size * h->capacity + sizeof(union header)); assert(h); } h->used++; *vec = (void *)h->data; return h->data + (h->used - 1) * h->element_size; } void *_vec_pop(VecHeader *h) { assert(h && h->used > 0); h->used--; return h->data + h->used * h->element_size; } void *_vec_get(VecHeader *h, uint32_t index) { assert(h && index < h->used); return h->data + index * h->element_size; } void _vec_copy(void **dest_vec, VecHeader *src) { assert(dest_vec && *dest_vec && src); VecHeader *dest = _vec_to_header(*dest_vec); assert(dest->element_size == src->element_size); dest->used = 0; // clear the destination vec. _vec_ensure_capacity(dest_vec, src->capacity); dest = _vec_to_header(*dest_vec); // needed in case of reallocation in above call. // both loops can be replaced with 'memcpy(dest->data, src->data, i * src->element_size); for(uint32_t i = 0; i < src->used; ++i) { for(uint32_t j = 0; j < src->element_size; ++j) { dest->data[i * dest->element_size + j] = src->data[i * src->element_size + j]; } } _vec_to_header(*dest_vec)->used = src->used; } void _vec_reverse(void *vec) { assert(vec); VecHeader *h = _vec_to_header(vec); // The division below might result in a float in which // case it will be rounded down which is what we want. for(uint32_t i = 0; i < h->used / 2; ++i) { for(uint32_t j = 0; j < h->element_size; ++j) { char tmp = h->data[i * h->element_size + j]; h->data[i * h->element_size + j] = h->data[(h->used - i - 1) * h->element_size + j]; h->data[(h->used - i - 1) * h->element_size + j] = tmp; } } } #define VEC_INITIAL_SIZE 8 #define VEC_NEW(type) ((type *)(_vec_make_header(sizeof(type), VEC_INITIAL_SIZE)->data)) #define VEC_FREE(vec) (_vec_free_header(_vec_to_header((void *)vec))) #define VEC_CAPACITY(vec) (_vec_to_header((void *)vec)->capacity) #define VEC_LENGTH(vec) (_vec_to_header((void *)vec)->used) #define VEC_PUSH(vec, value) (*(typeof(vec))(_vec_prepare_push((void **)&(vec))) = (value)) #define VEC_POP(vec) (*(typeof(vec))_vec_pop(_vec_to_header((void *)vec))) #define VEC_GET(vec, index) (*(typeof(vec))_vec_get(_vec_to_header((void *)vec), index)) #define VEC_COPY(dest, src) (_vec_copy((void **)&(dest), _vec_to_header((void *)src))) #define VEC_CLEAR(vec) ((void)(_vec_to_header((void *)vec)->used = 0)) #define VEC_REVERSE(vec) (_vec_reverse((void *)(vec))) #define VEC_FOREACH(index_var_name, vec) for(uint32_t index_var_name = 0; index_var_name < VEC_LENGTH(vec); ++index_var_name) // Note: [vec] is referenced multiple times. #define VEC_ITERATE(iter_var_name, vec) for(typeof(*vec) *iter_var_name = (vec); iter_var_name - (vec) < VEC_LENGTH(vec); ++iter_var_name) 

An example usage:

#include <stdio.h> int main(void) { int *nums = VEC_NEW(int); VEC_PUSH(nums, 42); VEC_PUSH(nums, 123); VEC_FOREACH(i, nums) { printf("nums[%u] = %d\n", i, nums[i]); // VEC_GET(nums, i) checks bounds. } int *nums2 = VEC_NEW(int); VEC_COPY(nums2, nums); printf("len: %u, cap: %u, nums2[len] = %d\n", VEC_LENGTH(nums2), VEC_CAPACITY(nums2), VEC_POP(nums2)); VEC_CLEAR(nums2); VEC_FREE(nums2); VEC_FREE(nums); return 0; } 

Answer 1

Should vec_header.data be a uint8_t instead of a char?

VEC_NEW asserts and fails on an allocation error. It could return NULL and let the caller decide how to handle out-of-memory errors.

Why does _vec_ensure_capacity test that h->used is greater than the desired capacity, rather than h->capacity? This means you may reallocate when the destination is large enough, but not full. And when used is bigger than the new capacity, you don't reallocate - leaving around the old values with no way to access them.

_vec_prepare_push could call _vec_ensure_capacity to avoid having two very similar blocks of code that call realloc.

The last line of _vec_copy shouldn't need another call to _vec_to_header: dest already has that value.

Technically, the division in _vec_reverse won't result in a float, but it will be rounded toward zero as you state.

In _vec_reverse, I might use two local variables for the repeated index calculations: uint32_t front = i * h->element_size + j; rear = (h->used - i - 1) * h->element_size + j;