dynarr - yet another simple C dynamic array library

Question

I wrote my own dynamic array library for C as I was not happy with the others I found. It is very crude but the basic logic should be correct, it mainly revolves making realloc easier to use and avoiding repetitive code.

Please offer your suggestions and criticisms!

#include <stdlib.h>
#include <string.h>

#define DYNARRAY_H_INCREMENT 50

typedef struct dynarr dynarr;

struct dynarr {
    void *actual;
    size_t size;
    size_t e_size;
    size_t occupied;
    size_t increment;
    void (*mem_callback)(dynarr *);
};

void *dynarr_nomen(dynarr *array) {
    if (array->mem_callback) array->mem_callback(array);
    array->actual = NULL;
    array->occupied = 0;
    return NULL;
}

dynarr dynarr_init_full(size_t e_size, size_t increment, void (*mem_callback)(dynarr *)) {
    return (dynarr){
        .actual = NULL,
        .size = 0,
        .e_size = e_size,
        .occupied = 0,
        .increment = increment,
        .mem_callback = mem_callback,
    };
}

dynarr dynarr_init(size_t element_size) {
    return dynarr_init_full(element_size, DYNARRAY_H_INCREMENT, NULL);
}

void *dynarr_push(dynarr *array, void *data) {
    if (array->occupied == array->size) {
        // Array is full
        // Increase size
        size_t new_real_size = (array->size + array->increment) * array->e_size;
        array->actual = realloc(array->actual, new_real_size);
        if (!array->actual) return dynarr_nomen(array);
        array->size += array->increment;
    }
    
    // Copy data
    char *charr = (char *) array->actual;
    memcpy(charr + array->occupied++ * array->e_size, data, array->e_size);
    
    return array->actual;
}

void *dynarr_get(dynarr *array, size_t *size) {
    if (size) *size = array->occupied;
    return array->actual;
}

void *dynarr_compact(dynarr *array) {
    if (array->occupied == array->size) goto end;
    array->actual = realloc(array->actual, array->occupied * array->e_size);
    if (!array->actual) return dynarr_nomen(array);
    array->size = array->occupied;
    end: return array->actual;
}

void dynarr_free(dynarr *array) {
    free(array->actual);
    array->actual = NULL;
    array->occupied = 0;
}

I intend to split declarations into a separate header in the future, I have kept it as a simple single source file for now.

I also made a very crude example program which could definitely use some major improvements... or maybe it can even be replaced by something else.

#include <signal.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "dynarr.c"

volatile sig_atomic_t signaled = false;

void trap_interrupt(int sig) {
    signaled = true;
}

int main(void) {
    signal(SIGINT, trap_interrupt); 
    
    int c;
    char data;
    dynarr input = dynarr_init(sizeof data);
    
    for (;;) {
        if (signaled) break;
        c = getc(stdin);
        if (c == EOF) break;
        data = c;
        if (!dynarr_push(&input, &data)) {
            puts("Ran out of memory!!!");
            break;
        };
    }
    
    size_t count;
    dynarr_get(&input, &count);
    printf("Stored %zu bytes in dynamic array\n", count);
    
    return EXIT_SUCCESS;
}

Answer 1

Regarding incrementing by a fixed amount

The problem with resizing the storage by a fixed amount each time you reach capacity is that it effectively makes pushing a new element to the array an \$\mathcal{O}(N)\$ operation. If you instead double the amount of storage each time, pushing will be amortized \$\mathcal{O}(1)\$.

The drawback of doubling the capacity each time is that you might waste more memory than if you only increase it by fixed amounts. However, unless you are constrained by the amount of memory you have, I would recommend the doubling approach.

Memory leaks

Your code leaks memory when running out of memory. If you call realloc(), but it returns NULL, the original memory is not freed and still valid. So instead of unconditionally overwriting array->actual, you should write something like:

void *new_actual = realloc(array->actual, new_real_size);

if (!new_actual) {
    free(array->actual);
    return dynarray_nomem(array->actual);
}

array->actual = new_actual;
array->size = new_real_size;

Alternatively, and perhaps even better, is to just keep the original data and return NULL, and let the caller worry about whether they want to destroy the array or want to keep using it:

void *new_actual = realloc(array->actual, new_real_size);

if (!new_actual) {
    return NULL;
}
...

(Re)move the callback

I don't see the point of having a callback function that is called when memory allocation failed, if the caller already has to check the return value of dynarray_push() and dynarray_compact(). I would just remove this unnecessary complexity.

This is an useful feature which can be used to avoid error checking for each push, instead of the caller can specify a callback function which would use something like longjmp to initiate a no memory exit sequence.

If you want this, I recommend you move the mem_callback pointer out of struct dynarr, and make it a global variable named dynarr_mem_callback.

Consider returning a pointer to the pushed element

It would be much more useful if dynarray_push() would return a pointer to the element that was just pushed, instead of a pointer to the start of the array. There is already dynarray_get() to get a pointer to the start, but see below.

Add a function to get a pointer to a specific element

Since it is likely that a user might want to access a specific element in the dynamic array, it would be helpful to add a function that does that in one go. In fact, I would name that function dynarray_get():

void *dynarray_get(dynarray *array, size_t offset) {
    // Bounds checking, has a performance impact though:
    if (offset >= array->occupied)
        return NULL;

    return (char *)array->actual + offset * array->e_size;
}

And add separate functions dynarray_data() and dynarray_size() to get a pointer to the underlying storage and the number of elements respectively.

Avoid using goto

It is quite easy to avoid the goto statement in dynarray_compact(), just replace it with return array->actual. Even better would be to just unconditionally call realloc(), since it is unlikely that size and occupied will be the same, and this is not a function that would be called very often anyway, so it is not performance critical:

void *dynarr_compact(dynarr *array) {
    void *new_actual = realloc(array->actual, array->occupied * array->e_size);

    if (new_actual) {
        array->actual = new_actual;
        array->size = array->occupied;
    }

    return array->actual;
}