1
\$\begingroup\$

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

1 Answer 1

1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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