Made a dynamic array in C

Question

I have often wondered how one would deal with dynamically sized arrays in C, since the only thing close is using malloc and realloc with pointers. To find out how they work I decided that I should create a dynamic array in C.

xvec.h

#ifndef XVEC_C_XVEC_H
#define XVEC_C_XVEC_H
#include <stdlib.h>
#include <string.h>
/*needed for increasing capacity*/
static inline size_t upper_power_of_two(size_t v) {
 v--;
 v |= v >> 1;
 v |= v >> 2;
 v |= v >> 4;
 v |= v >> 8;
 v |= v >> 16;
 //only needed for 64 bit mode
 if (sizeof (size_t) == 8) v |= v >> 32;
 v++;
 return v;
}
typedef struct xvec_base { size_t cap, len; } xvec_base;
#define XVEC_ALEN(a) (sizeof(a) / sizeof(*a))
static inline size_t *xvec_len_ptr(void *v) {
 return &((xvec_base *) v - 1)->len;
}
static inline size_t *xvec_cap_ptr(void *v) {
 return &((xvec_base *) v - 1)->cap;
}
static inline size_t xvec_len(void* v) {
 return ((xvec_base *) v - 1)->len;
}
static inline size_t xvec_cap(void* v) {
 return ((xvec_base *) v - 1)->cap;
}
/* how to use
 * T = type
 * ... = items to initialize the array with
*/
#define xvec_new(T, ...) \
({ \
 const T __args[] = {__VA_ARGS__}; \
 const size_t initial_size = 16+XVEC_ALEN(__args); \
 xvec_base *_v = (xvec_base*)malloc(sizeof(xvec_base) + sizeof(T) * initial_size); \
 _v->cap = initial_size; \
 _v->len = XVEC_ALEN(__args); \
 T* v = (T*)(_v+1); \
 memcpy(v,__args,sizeof(__args)); \
 v; \
}) \
/* how to use
 * v = container
 * size = the size to resize to
*/
#define xvec_resize(v, size) \
({ \
 const size_t _size = size; \
 size_t* _len = xvec_len_ptr(v); \
 size_t* _cap = xvec_cap_ptr(v); \
 if(_size > *_len) { \
 xvec_reserve(v,_size); \
 _len = xvec_len_ptr(v); \
 /*clear memory after resizing*/ \
 memset(v+*_len,0, (*_cap-*_len)*sizeof(*v)); \
 } \
 *_len = _size; \
 v; \
})
#define xvec_reserve(v, size) \
({ \
 const size_t s = size; \
 size_t* _cap = xvec_cap_ptr(v); \
 if(s > *_cap) { \
 *_cap = s; \
 v = (__typeof__(v))((char*)realloc((xvec_base*)v-1,sizeof(xvec_base) + sizeof(*v)*(*_cap))+sizeof(xvec_base)); \
 } \
 v; \
})
#define xvec_free(v) free((xvec_base*)v-1)
#define xvec_pop(v) ({v[(*xvec_len_ptr(v))--];})
/*how to use
 * v = container
 * ... = items to insert
*/
#define xvec_push(v, ...) \
({ \
 const __typeof__(*v) __args[] = {__VA_ARGS__}; \
 size_t* _len = xvec_len_ptr(v); \
 size_t* _cap = xvec_cap_ptr(v); \
 if(*_len + XVEC_ALEN(__args) >= *_cap) { \
 xvec_reserve(v,upper_power_of_two(*_len+XVEC_ALEN(__args))); \
 _len = xvec_len_ptr(v); \
 } \
 for(size_t i = 0; i < XVEC_ALEN(__args); ++i) { \
 v[(*_len)++] = __args[i]; \
 } \
 v; \
})
/*how to use
 * v = container
 * index = where to insert
 * ... = items to insert
*/
#define xvec_insert(v, index, ...) \
({ \
 const size_t _n = index; \
 const __typeof__(*v) __args[] = {__VA_ARGS__}; \
 size_t* _len = xvec_len_ptr(v); \
 size_t* _cap = xvec_cap_ptr(v); \
 if(*_len + XVEC_ALEN(__args) >= *_cap) { \
 xvec_reserve(v,upper_power_of_two(*_len+XVEC_ALEN(__args))); \
 _len = xvec_len_ptr(v); \
 } \
 memcpy(v+_n+XVEC_ALEN(__args),v+_n, \
 sizeof(*v)*(*_len-_n)); \
 memcpy(v+_n,&__args[0], \
 XVEC_ALEN(__args)*sizeof(*v)); \
 *_len += XVEC_ALEN(__args); \
 v; \
})
/* how to use
 * v = container
 * index = where to remove
*/
#define xvec_remove(v, index) \
({ \
 const size_t _index = index; \
 size_t *_len = xvec_len_ptr(v); \
 memcpy(v+_index,v+_index+1,sizeof(*v)*(*_len-_index)); \
 (*_len)--; \
 v; \
})
/* how to use
 * v = container
 * first = the first item to be removed
 * last = the last item to be removed
*/
#define xvec_remove_range(v, first, last) \
({ \
 const size_t _first = first; \
 const size_t _last = last; \
 const size_t _n = _last-_first+1; \
 size_t *_len = xvec_len_ptr(v); \
 memcpy(v+_first,v+_last+1,sizeof(*v)*(*_len-_last)); \
 *_len-=_n; \
 v; \
})
/* how to use
 * v = container
*/
#define xvec_copy(v) \
({ \
 __typeof__(v) new_xvec = xvec_new(typeof(v)); \
 xvec_resize(new_xvec,xvec_len(v)); \
 memcpy(new_xvec,v,xvec_len(v)*sizeof(*v)); \
 new_xvec; \
})
#endif //XVEC_C_XVEC_H

Here is a test case:

test.c

#include "xvec.h"
#include <stdio.h>
int main() {
 int *v = xvec_new(int,987654321);
 xvec_push(v, 1);
 xvec_push(v, 1);
 xvec_push(v, 1, 7, 8, 9, 10, 11);
 v[2] = 2;
 xvec_insert(v, 0, 12, 3, 5, 6, 7, 8, 9, 10);
 xvec_insert(v, 0, 1, 2, 3, 4);
 xvec_insert(v, 0, 1, 2, 3, 4);
 xvec_insert(v, 0, 1, 2, 3, 4);
 xvec_insert(v, 0, 1, 2, 3, 4);
 xvec_pop(v);
 xvec_insert(v, xvec_len(v), 1, 2, 3, 4);
 xvec_remove_range(v,xvec_len(v)-2,xvec_len(v)-1);
 xvec_remove(v,xvec_len(v)-2);
 xvec_reserve(v,70);
 xvec_resize(v,3453);
 xvec_resize(v,32);
 int* t= xvec_copy(v);
 t[31] = -1;
 printf("%zu\n", xvec_cap(v));
 for (int i = 0; i < xvec_len(v); ++i) {
 printf("%d\n", v[i]);
 }
 printf("%d\n",t[31]);
 xvec_free(v);
 xvec_free(t);
}

• chux: Why does the dynamic array not shrink (reduce allocations) with xvec_resize()?

Answer 1

IMO this kind of error prone, hard to maintain macros should be avoided at any price.

If I was doing it I would do something like this (assuming gcc):

typedef struct
{
 size_t nelem;
 size_t elemsize;
 char arr[];
}DARR_t;
#define INLINE inline __attribute__((always_inline))
#define arr_init(nelem,type) _arr_init(nelem, sizeof(type))
static INLINE void *_arr_init(size_t numelements, size_t elemsize)
{
 DARR_t *p = malloc(numelements * elemsize + sizeof(*p));
 if(p)
 {
 p -> nelem = numelements;
 p -> elemsize = elemsize;
 }
 return p ? p -> arr : (void *)p;
}
#define arr_append(ptr, type, ...) _arr_append(ptr, &(type []){__VA_ARGS__}, sizeof((type []){__VA_ARGS__})/sizeof(type))
static INLINE void *_arr_append(void *arr, void *val, size_t size)
{
 DARR_t *p = arr - offsetof(DARR_t, arr), *tmp;
 tmp = realloc(p, (p -> nelem + size) * p -> elemsize + sizeof(*tmp));
 if(tmp) 
 {
 memcpy(&tmp -> arr[tmp -> nelem * tmp -> elemsize], val, tmp -> elemsize * size);
 tmp -> nelem++;
 }
 return tmp ? tmp -> arr : (void *)tmp;
}

etc, etc

But if I want to use dynamic arrays I would rather use C++.

• 0___________: @chux-ReinstateMonica good spot - I almost never sizeof types. Why did I do it here? Even I do not know
• 0___________: return p ? p -> arr : (void *)p this time you are not right. If the pointer types in conditional expression are different (except void*) - gcc emits the warning. To suppress it it cast is needed (or NULL) godbolt.org/z/oKgvDe