Another generic dynamic arrays in C

Question

Wrote this (and others not here) as an exercise to explore how generics could be implemented in C.

Question -- if I were to support out-of-band error setting, how would that look like for dynarray_len()? There is no wrong value to return and requiring the user to check the error after every call seems cumbersome; I don't see any other way around though.

// generic_dynarray.h #ifndef GENERIC_DYNARRAY_H #define GENERIC_DYNARRAY_H #include <stdbool.h> typedef struct dynarray_T dynarray_T; // dynarray_new returns a new, initialised dynarray_T. dynarray_T *dynarray_new(size_t data_size); // dynarray_destroy frees da. void dynarray_destroy(dynarray_T *da); // dynarray_init initialises or clears da. void dynarray_init(dynarray_T *da, size_t data_size); // dynarray_get returns the data at index i of da, otherwise NULL incase // of out-of-bounds i. void *dynarray_get(dynarray_T *da, size_t i); // dynarray_set sets the value of index i of da to data. Returns true if // operation succeeded, false otherwise. bool dynarray_set(dynarray_T *da, size_t i, void *data); // dynarray_append appends data to da. void dynarray_append(dynarray_T *da, void *data); // dynarray_pop pops and returns the value of da at it's last index. void *dynarray_pop(dynarray_T *da); // dynarray_len returns the length of da. size_t dynarray_len(dynarray_T *da); #endif 

// generic_dynarray.c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> #include "generic_dynarray.h" #define DYNARRAY_MIN_CAP 10 #define DYNARRAY_CAP_GROWTH_RATE 2 #define DYNARRAY_CAP_SHRINK_RATE 0.25 // 1/4 struct dynarray_T { void *buf; // The buffer array holding the data size_t cap, len; // The capacity and length of the dynarray size_t data_size; // The size of the value stored in buf }; static void valid_dynarray(dynarray_T *da, const char *func) { if (!da) { fprintf(stderr, "%s: dynarray_T should not be NULL", func); exit(1); } } dynarray_T *dynarray_new(size_t data_size) { dynarray_T *da = malloc(sizeof(*da)); if (!da) { fprintf(stderr, "%s: memory allocation for da failed\n", __func__); exit(1); } // For realloc in dynarray_init() to work like malloc da->buf = NULL; dynarray_init(da, data_size); return da; } void dynarray_destroy(dynarray_T *da) { valid_dynarray(da, __func__); free(da->buf); free(da); } // dynarray_resize resizes da->buf to capacity da->cap by reallocing. static void dynarray_resize(dynarray_T *da, const char *func) { da->buf = realloc(da->buf, da->data_size * da->cap); if (!da->buf) { fprintf(stderr, "%s: memory allocation for da->buf failed\n", func); exit(1); } } void dynarray_init(dynarray_T *da, size_t data_size) { valid_dynarray(da, __func__); da->cap = DYNARRAY_MIN_CAP; da->len = 0; da->data_size = data_size; dynarray_resize(da, __func__); } void *dynarray_get(dynarray_T *da, size_t i) { valid_dynarray(da, __func__); if (i >= da->len) { fprintf(stderr, "%s: i %lu must be less than %lu\n", __func__, i, da->len); return NULL; } return da->buf + i*da->data_size; } bool dynarray_set(dynarray_T *da, size_t i, void *data) { valid_dynarray(da, __func__); if (i >= da->len) { fprintf(stderr, "%s: i %lu must be less than %lu\n", __func__, i, da->len); return false; } memcpy(da->buf + i*da->data_size, data, da->data_size); return true; } void dynarray_append(dynarray_T *da, void *data) { valid_dynarray(da, __func__); if (da->cap == da->len+1) { da->cap = DYNARRAY_CAP_GROWTH_RATE * da->cap; dynarray_resize(da, __func__); } dynarray_set(da, da->len++, data); } void *dynarray_pop(dynarray_T *da) { valid_dynarray(da, __func__); if (da->len == DYNARRAY_CAP_SHRINK_RATE * da->cap) { da->cap = DYNARRAY_CAP_SHRINK_RATE * da->cap; dynarray_resize(da, __func__); } void *ret = dynarray_get(da, da->len-1); da->len--; return ret; } size_t dynarray_len(dynarray_T *da) { valid_dynarray(da, __func__); return da->len; } 

And a simple test driver,

#include <stdio.h> #include <stdlib.h> #include <string.h> #include "generic_dynarray.h" int main(int argc, char *argv[]) { if (argc < 2) { fprintf(stderr, "expect at least one argument\n"); exit(1); } dynarray_T *da_strs = dynarray_new(sizeof(char *)); for (size_t i = 0; i < argc; i++) { dynarray_append(da_strs, argv[i]); } printf("da.len = %lu\n", dynarray_len(da_strs)); for (size_t i = 0; i < dynarray_len(da_strs); i++) { printf("da_strs[%lu] = %s; ", i, (char *)dynarray_get(da_strs, i)); } puts(""); size_t len = dynarray_len(da_strs); for (size_t i = 0; i < len; i++) { printf("da_strs[%lu] = %s; ", len-i-1, (char *)dynarray_pop(da_strs)); printf("da.len = %lu\n", dynarray_len(da_strs)); } dynarray_destroy(da_strs); return 0; } 

Answer 1

You have a bug here:

 da->buf = realloc(da->buf, da->data_size * da->cap); 

When realloc() returns a null pointer, we overwriteda->buf with that, losing our pointer to the memory block (i.e. a leak). We should use a temporary pointer:

void *newmem = realloc(da->buf, da->data_size * da->cap); if (!newmem) { /* handle error */ } else { da->buf = newmem; } 

In this particular case, the harm is small, because we call exit() in the failure case, so the only evidence is when we run under Valgrind or similar.

But a real library should not unilaterally exit the program - we should return an error indication to the caller, which is in a better position to decide what to do (perhaps try a different operation, or squeeze a cache and try again, or report the error in a GUI rather than on stderr).

---

You'll find that DYNARRAY_CAP_GROWTH_RATE==2 is a bit high for good performance. Try a value near to 1.5 instead (but make sure you round upwards!).