Generic variable-size array

Question

As stated in the tags, I'm a beginner to C. This code implements a dynamic array (List in .NET, vector in C++, etc) for any pointer type. I would like that it be reviewed on memory usage and code structure/style.

list.h

#ifndef _game_structures_list_h
#define _game_structures_list_h

#include <stdbool.h>

typedef enum {
    LIST_ERR_NONE = 0x00,

    LIST_ERR_POP_EMPTY = 0x01,
    LIST_ERR_OUT_OF_BOUNDS = 0x02,
    LIST_ERR_MEMORY = 0x03,

    LIST_ERR_UNITIALIZED = 0xff
} ListError;

typedef struct {
    int capacity;
    int length;
    ListError error;
    void **data;
} List;

/**
 * Creates a new List with the given starting capacity.
 * @param capacity The initial allocation size for this list, not its length!
 * @return A new empty List
 */
List list_new(int capacity);

/**
 * Frees memory used by the list and makes it unusable
 */
void list_destroy(List *list);

/**
 * Gets the error of the last operation on this list
 * @return The last error, or LIST_ERR_NONE if successful
 */
ListError list_error(List *list);

/**
 * Gets the amount of items in the list
 * @return Length of list
 */
int list_length(List *list);

/**
 * Removes all elements from the list
 * @param list The list to be cleared
 */
void list_clear(List *list);

/**
 * Access the item at the given index.
 * @return Pointer to the item at the given index
 */
void *list_get(List *list, int index);

/**
 * Sets the value at the given index to the item given
 */
void list_set(List *list, void *item, int index);

/**
 * Adds an item to the end of the list
 * @param list Where to add the item to
 * @param item The value to be added
 */
void list_push(List *list, void *item);
/**
 * Removes the last item from the list and returns it
 * @param list The list to be popped
 * @return The value removed
 */
void *list_pop(List *list);

/**
 * Adds a new item to a list at the given position, moving all remaining items to the right
 * @param list The list to which the item will be added
 * @param item The value to be added
 * @param index The position in the list where the item will be placed
 */
void list_insert(List *list, void *item, int index);
/**
 * Removes the item at the given index from the list, returning it and shifting all remaining items to fill the gap
 * @param list The list to remove
 * @param index Index of the item to be removed
 * @return The removed value
 */
void *list_remove(List *list, int index);

#endif

list.c

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

#define L_ERR(list, err) list->error = err; return
#define L_OK(list) L_ERR(list, LIST_ERR_NONE)
#define L_BOUNDS(list, index, ...) if (index < 0 || index >= list->length) {L_ERR(list, LIST_ERR_OUT_OF_BOUNDS) __VA_ARGS__;}

#define CAPACITY_FACTOR 2

static inline bool change_capacity(List *list, int new_capacity) {
    void **new_data = realloc(list->data, new_capacity * sizeof(*list->data));
    if (new_data) {
        list->data = new_data;
        list->capacity = new_capacity;
        L_OK(list) true;
    }
    L_ERR(list, LIST_ERR_MEMORY) false;
}

static inline bool adjust_capacity(List *list) {
    int length = list->length;
    int capacity = list->capacity;
    int half_cap = capacity / CAPACITY_FACTOR;
    if (length < half_cap) {
        return change_capacity(list, half_cap);
    } else if (length == capacity) {
        return change_capacity(list, capacity * CAPACITY_FACTOR);
    }
    L_OK(list) true;
}

List list_new(int capacity) {
    List list = {
        .capacity = 0,
        .length = 0,
        .data = NULL
    };
    if (capacity) {
        change_capacity(&list, capacity);
    }
    return list;
}

void list_destroy(List *list) {
    list_clear(list);
    free(list->data);
    list->data = NULL;
    list->capacity = 0;
}

ListError list_error(List *list) {
    if (!list->capacity) {
        list->error = LIST_ERR_UNITIALIZED;
    }
    return list->error;
}

int list_length(List *list) {
    return list->length;
}

void list_clear(List *list) {
    list->length = 0;
    L_OK(list);
}

void *list_get(List *list, int index) {
    L_BOUNDS(list, index, NULL);

    L_OK(list) list->data[index];
}

void list_set(List *list, void *item, int index) {
    L_BOUNDS(list, index, );

    list->data[index] = item;
    L_OK(list);
}

void list_push(List *list, void *item) {
    if (!adjust_capacity(list)) return;

    list->data[list->length] = item;
    list->length++;
    L_OK(list);
}

void *list_pop(List *list) {
    if (!list->length) {
        L_ERR(list, LIST_ERR_OUT_OF_BOUNDS) NULL;
    }
    void *item = list->data[list->length - 1];
    if (!adjust_capacity(list)) return NULL;
    list->length--;
    L_OK(list) item;
}

void list_insert(List *list, void *item, int index) {
    L_BOUNDS(list, index, );
    if (!adjust_capacity(list)) return;

    void **base = list->data + index;
    int size = (list->length - index) * sizeof(*list->data);

    if (!memmove(base + 1, base, size)) {
        L_ERR(list, LIST_ERR_MEMORY);
    }
    list->data[index] = item;
    list->length++;
    L_OK(list);
}

void *list_remove(List *list, int index) {
    L_BOUNDS(list, index, NULL);
    if (!adjust_capacity(list)) return NULL;

    void **base = list->data + index;
    void *item = *base;
    int size = (list->length - index) * sizeof(*list->data);

    if (!memmove(base, base + 1, size)) {
        L_ERR(list, LIST_ERR_MEMORY) NULL;
    }
    list->length--;
    return item;
}

Answer 1

Better Naming Conventions

One of the things that immediately jumps out at me is the name you used for the data structure. As you mentioned, a dynamic array is called a List in C# and in Java. However, in the C/C++ world, we generally like to refer to dynamic arrays as either (ahem) dynamic arrays or vectors. When I saw List, my brain automatically started thinking I was going to be looking at code for a singly/doubly linked list of some sort (since I come from a C/C++ world). I'm sure others would find the use of the name List to describe a vector a little misleading as well. Obviously, you'd need to rename all your functions and your error enumeration to reflect this name change and keep the API consistent. For the code I'll be presenting, I'll be calling the structure a cvector.

Use Opaque Types

One issue with the way you have your structure defined in the header file is that it exposes it's internal representation to the user. That is, if the user includes your header file, they are free to change the contents of the members without ever using your functions. As you can probably imagine, without proper documentation on how to properly manipulate the fields (or even with proper documentation), this is very error-prone. Ideally, you'd like your users to only be able to manipulate your structure using your API. To do this, we need to forward declare the structure in the header file and supply its definition in the implementation file. One disadvantage with this approach though is that you'll be forced to use heap allocation to initialize opaque structures.

cvector.h

// forward declare here
typedef struct cvector_ cvector;

// no need to assign values to enumerations past the first one since
// the compiler automatically provides incremented values for them.
typedef enum {
    CVECTOR_ERR_NONE = 0x00,
    CVECTOR_ERR_POP_EMPTY,
    CVECTOR_ERR_OUT_OF_BOUNDS,
    CVECTOR_ERR_MEMORY,
    CVECTOR_INVALID_OPERATION,
    CVECTOR_ERR_UNITIALIZED
} CVectorError;

cvector.c

// define structure in here
struct cvector_ {
    // these values can never be negative so use unsigned numbers to reflect that
    size_t capacity, size;
    void **data;
};

CVector API

Having is_empty() convenience function, a function to return the current capacity of the vector, a reserve() function to reserve memory storage, and maybe a shrink_to_fit() function would be great to have. You will also want to have init() and free() functions to both initialize and destroy the vector you created. Also, notice that I removed the error code member from the vector structure. It isn't needed because if you design your API to return error codes where appropriate, the user could just query the return result of whatever API function they're calling. Moreover, it serves to just bloat the data structure unnecessarily. You should look to have your set(), get(), push(), pop(), insert(), and remove() functions return error codes that the user could query if they so choose. Below is a simplified implementation of some of the functions I talked about to give you an idea of what I mean.

cvector *cvector_init(size_t capacity)
{
    cvector *cv = calloc(1, sizeof(*cv));
    if (cv && internal_cvector_reserve(cv, capacity) != CVECTOR_ERR_NONE) {
        free(cv);
        cv = NULL;
    }
    return cv;
}

void cvector_free(cvector *cv)
{
    free(cv->data);
    free(cv);
}

static CVectorError internal_cvector_reserve(cvector *cv, size_t new_capacity)
{
    void **new_data = realloc(cv->data, new_capacity * sizeof(*(cv->data)));
    if (!new_data) {
        return CVECTOR_ERR_MEMORY;
    }
    cv->data = new_data;
    cv->capacity = new_capacity;
    return CVECTOR_ERR_NONE;
}

CVectorError cvector_reserve(cvector *cv, size_t new_capacity)
{
     return new_capacity > cv->capacity ? 
            internal_cvector_reserve(cv, new_capacity) :
            CVECTOR_INVALID_OPERATION;
}

bool cvector_empty(const cvector *cv)
{
    return cvector->size == 0;
}

CVectorError cvector_shrink_to_fit(cvector *cv)
{
    return internal_cvector_reserve(cv, cv->size);
}

Avoid Macros When They Are Unnecessary

In your case, all the macros are completely unnecessary and could just be implemented as either small static functions or as typed constants. This one is especially egregious: L_ERR . That's because it hides a return statement and makes reading the code using it very very awkward. Instead of the CAPACITY_FACTOR macro, you could just as easily use:

static const size_t CAPACITY_FACTOR = 2;

You gain the benefits of type safety and self-documenting code with this.

EDIT:

Revise allocation strategy

Currently, your allocation strategy is forcing you to reallocate every single time a modifying operation is done on a vector. As an example, assume I create a vector with 10 as the initial capacity:

Capacity: 10
Size: 0

Then I push an element into the vector. Your code would check and see that my size is less than the capacity and halve the capacity; this incurs a reallocation which is very expensive relative to the actual push operation:

Capacity: 5
Size: 1

Another push:

Capacity: 2 (this is truncated down from 2.5)
Size: 2

Another push... Now the size is equal to the capacity so I reallocate to double the length and push:

Capacity: 4
Size: 3

Another push... Now the size is less than the capacity and we reallocate to half the storage:

Capacity: 2
Size: 4

Now we have an interesting situation where the size is greater than the capacity... and your adjust_capacity doesn't take that into account and will happily return true. Now when I do another push, I have invoked undefined behavior. Not to mention that I've managed to reallocate on every single push operation!! Notice too that this behavior will exist for any initial capacity you provide. In fact, given an initial capacity of N, your allocation strategy will invoke undefined behavior in exactly \$\mathcal{ceil}(\log N)\$ modifying operations!

The fix for this would be to just ditch halving the capacity and focus on making the vector grow by some certain factor. Read this article here for an interesting vector allocation scheme.