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 overwrite da->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!).