1
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
10
  • \$\begingroup\$ Thank you for the review, I would like to clarify some points: \$\endgroup\$ – TheDcoder Apr 2 at 6:35
  • \$\begingroup\$ Don't increment by a fixed amount: The problem with doubling the memory is that the growth is exponential and for a sufficiently large array, the system might not have enough memory, while the operation does not require such huge amounts. The option to customize the increments is therefore given so that the end-user can choose their ideal size increments. \$\endgroup\$ – TheDcoder Apr 2 at 6:36
  • \$\begingroup\$ Remove the callback: 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. \$\endgroup\$ – TheDcoder Apr 2 at 6:39
  • 1
    \$\begingroup\$ If you have improved the code and would like a review of the improved code, then please do ask a new question (include a link to this first review, to give more context). See I improved my code based on the reviews. What next?. \$\endgroup\$ – Toby Speight Apr 2 at 7:48
  • 1
    \$\begingroup\$ @TheDcoder As for the exponential growth, it can indeed be an issue. However, it is quite unlikely you run into it on modern systems. Also, with the major operating systems using virtual memory and overcommitting it, the unused part of a large dynarray will typically not even cost any memory. If you are working on a small embedded system, it is different of course. \$\endgroup\$ – G. Sliepen Apr 2 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.