Dynamically sized C array

Question

I've been working in C for a while and have decided to implement my own dynamically sized array as an exercise and to actually be used in a project.

I have also written Doxygen documentation for the library, which I have removed from the code here for readability. You can find the full code with documentation here.

I know I should comment inside the actual methods of the library but I haven't gotten around to it yet.

example.c - Example dynarray usage

#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <math.h>

#include "dynarray.h"

int main(int argc, char **argv) {

    // The array
    dynarray_t array;

    // The current index in the array
    int index;

    // Seed the random number generator with the current time
    srand(time(NULL));

    // Initialize the array with 8 elements
    if (!dynarray_init(&array, 8)) {
        printf("Failed to initialize array\n");
        return EXIT_FAILURE;
    }

    // Allocate memory for the value to be stored in the array
    int *value = malloc(sizeof(int));

    // Add 10 elements to the array
    for (index = 0; index < 10; index++) {

        // Assign the value to be stored in the array
        *value = rand() % 100;

        // Add the element to the array
        if (!dynarray_add(&array, value)) {
            printf("Failed to add element %d to array\n", index);

            // Free all elements in the array
            dynarray_deep_free(&array);

            // Free the value
            free(value);

            return EXIT_FAILURE;
        }

        // Allocate memory for the next value
        value = malloc(sizeof(int));
    }

    // Assign the value to be stored in the array
    *value = 9999;

    // Set the first element
    if (!dynarray_set(&array, 0, value)) {
        printf("Failed to set element 0 in array\n");

        // Free all elements in the array
        dynarray_deep_free(&array);

        // Free the value
        free(value);

        return EXIT_FAILURE;
    }

    // The size of the array
    int size = array.size;

    // Iterate the elements in the array
    for (index = 0; index < size; index++) {

        // Retrieve the current element of the array
        if (!dynarray_get(&array, index, (void **) &value)) {
            printf("Failed to retrieve element %d from the array\n", index);

            // Free all elements in the array
            dynarray_deep_free(&array);

            return EXIT_FAILURE;
        }

        // Output the current element
        printf("[%2d] = %2d\n", index, *value);
    }

    // Output information about the array
    printf("Current size: %d elements\n", array.size);
    printf("Current capacity: %d elements\n", array.capacity);
    printf("Initial capacity: %d elements\n", array.initial_capacity);
    printf("Resized %d times\n", (int) floor(log(array.capacity / array.initial_capacity) / log(2)));

    // Free all elements in the array
    dynarray_deep_free(&array);

    return EXIT_SUCCESS;
}

dynarray.h

#ifndef _DYNARRAY_H_
#define _DYNARRAY_H_

#define DYNARRAY_SUCCESS 1
#define DYNARRAY_ERROR (!DYNARRAY_SUCCESS)

struct dynarray {
    void **data;
    int initial_capacity;
    int capacity;
    int size;
};

typedef struct dynarray dynarray_t;

unsigned int dynarray_init(dynarray_t *array, int initial_capacity);
unsigned int dynarray_size(dynarray_t *array, int *size);
unsigned int dynarray_add(dynarray_t *array, void *item);
unsigned int dynarray_set(dynarray_t *array, int index, void *item);
unsigned int dynarray_get(dynarray_t *array, int index, void **item);
unsigned int dynarray_remove(dynarray_t *array, int index);
unsigned int dynarray_free(dynarray_t *array);
unsigned int dynarray_deep_free(dynarray_t *array);

#endif

dynarray.c

#include <stdlib.h>

#include "dynarray.h"

unsigned int dynarray_init(dynarray_t *array, int initial_capacity) {
    if (array == NULL || initial_capacity < 1 || (initial_capacity % 2) != 0) {
        return DYNARRAY_ERROR;
    }

    void **data = malloc(sizeof(void *) * initial_capacity);

    if (data == NULL) {
        return DYNARRAY_ERROR;
    }

    array->data = data;
    array->initial_capacity = initial_capacity;
    array->capacity = initial_capacity;
    array->size = 0;

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_size(dynarray_t *array, int *size) {
    if (array == NULL) {
        return DYNARRAY_ERROR;
    }

    *size = array->size;

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_resize(dynarray_t *array, int capacity) {
    if (array == NULL || array->data == NULL) {
        return DYNARRAY_ERROR;
    }

    void **data = realloc(array->data, sizeof(void *) * capacity);

    if (data == NULL) {
        return DYNARRAY_ERROR;
    }

    array->data = data;
    array->capacity = capacity;

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_add(dynarray_t *array, void *item) {
    if (array == NULL || array->data == NULL || item == NULL) {
        return DYNARRAY_ERROR;
    }

    int capacity = array->capacity;
    int size = array->size;

    if (size >= capacity) {
        if (dynarray_resize(array, capacity * 2) != DYNARRAY_SUCCESS) {
            return DYNARRAY_ERROR;
        }
    }

    array->data[array->size] = item;
    array->size++;

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_set(dynarray_t *array, int index, void *item) {
    if (array == NULL || array->data == NULL ||
        index < 0 || index >= array->capacity ||
        item == NULL) {

        return DYNARRAY_ERROR;
    }

    array->data[index] = item;

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_get(dynarray_t *array, int index, void **item) {
    if (array == NULL || array->data == NULL ||
        index < 0 || index >= array->size ||
        item == NULL) {

        return DYNARRAY_ERROR;
    }

    *item = array->data[index];

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_remove(dynarray_t *array, int index) {
    if (array == NULL || array->data == NULL ||
        index < 0 || index >= array->size) {

        return DYNARRAY_ERROR;
    }

    void **data = array->data;
    int initial_capacity = array->initial_capacity;
    int capacity = array->capacity;
    int size = array->size;

    data[index] = NULL;

    if (index < (size - 1)) {
        int current;

        for (current = index; current < (size - 1); current++) {
            data[current] = data[current + 1];
            data[current + 1] = NULL;
        }
    }

    array->size = --size;

    int new_capacity = capacity / 2;

    if (size > 0 && size <= new_capacity && new_capacity >= initial_capacity) {
        if (dynarray_resize(array, new_capacity) != DYNARRAY_SUCCESS) {
            return DYNARRAY_ERROR;
        }
    }

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_free(dynarray_t *array) {
    if (array == NULL || array->data == NULL) {
        return DYNARRAY_ERROR;
    }

    free(array->data);
    array->data = NULL;

    array->capacity = 0;
    array->size = 0;

    return DYNARRAY_SUCCESS;
}

unsigned int dynarray_deep_free(dynarray_t *array) {
    if (array == NULL || array->data == NULL) {
        return DYNARRAY_ERROR;
    }

    void **data = array->data;
    int size = array->size;
    int index;

    for (index = 0; index < size; index++) {
        free(data[index]);
    }

    dynarray_free(array);

    return DYNARRAY_SUCCESS;
}

Answer 1

Should the dynarray type be opaque? Personally I have my doubts, but I have found it useful to make library types opaque in development and testing, as an aid to identifying missing library functionality.

It's common practice in C to have indices and sizes be size_t, you might want to do that (and eliminate all the index<0 checks).

A piece of pedantry, perhaps, but I think 'empty' would be better than free as dynarray_free doesn't free the container, just the contents.

Why rule out adding NULL data in dynarray_add and dynarray_set? It could be reasonable to want to first create places for items to live, and then in another pass create the items themselves.

A user can only find out the index of data added with dynarry_add by using the size field before the call or the size field-1 after the call; this seems a bit ugly.

Further to Ratchet Freak's point about free, even if the intention is that only the one heap well ever be used, the items themselves could contain allocated data. You should consider passing a itemfree function to dynarray_deep_free and dynarray_remove.

If I was using the library I'd want a function that would call a function for every element of the array, rather than having to code such loops myself.

Strictly speaking, identifiers ending in _t are reserved for the OS/standard libraries. It's good practice to not define identifiers like that.

It can be irritating to have to remember a different name for 0 and 1 for error returns for all the libraries a program uses. Since you only have two values, I think it would be better to be explicit in the documentation, and code, that these are 0 and 1, and dispense with the names.

Why require that initial_capacity be even in dynarray_init?

Answer 2

Comments on every line is just noise, those who can't figure out what each simple line of code does shouldn't be reading it.

Instead you can just comment the big blocks: fill array, indexed set and indexed get.

In dynarray_remove there is no need to set data[current + 1] to NULL. As you won't be accessing data[size] except to set it again.

That for can also be replaced with a memmove (it's a memcpy that allows overlapped copies).

dynarray_deep_free assumes the pointers were allocated with malloc and the heap of the dynarray.c and the program are the same. This may not always be the case.