Generic data structures in C

Question

I'm new to C, and I thought a great way to learn would be to implement some generic data structures and algorithms. So far I've implemented a linked list and a dynamic array. Both are generic, the linked list with void*s and the dynamic array with macros. Both have some straightforward tests in Unity. Both compile with no warnings with the flags:

-std=c89 -ansi -pedantic

Let me know what you think!

dynamic_array.h

/*
 * A generic dynamic array implemented from scratch in C89.
 *
 * Define a dynamic array through the macro 'DEFINE_DYNAMIC_ARRAY(T)'. Put this
 * in your code to define a dynamic array called 'DynamicArray_T' that holds
 * type 'T'. For example: 'DEFINE_DYNAMIC_ARRAY(float)' will define a dynamic
 * array called 'DynamicArray_float' that holds floats. This macro will also
 * define all the dynamic array operations as well. These include:
 *   - dynamic_array_T_construct(~)
 *   - dynamic_array_T_destruct(~)
 *   - dynamic_array_T_add(~)
 *   - dynamic_array_T_add_at(~)
 *   - dynamic_array_T_remove(~)
 *   - dynamic_array_T_remove_at(~)
 *   - dynamic_array_T_contains(~)
 * Different types of Dynamic arrays can be defined in the same file. Their
 * types and operations are differentiated by the 'T' in their names.
 * See the macros that define these operations below for their docs.
 * The initial capacity of the array and when it expands/contracts, and by how
 * much, are defined in the constants below.
 *
 * Written by Max Hanson, June 2019.
 */

#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H

#include <stdlib.h>

static const int INIT_CAPACITY = 10; /* Initial capacity. */
static const float EXPANSION_POINT = 1.0; /* load > this -> array expands */
static const float CONTRACTION_POINT = 0.3; /* load < this -> array contracts */
/* Expanded capacity = this * old capacity */
static const float EXPANSION_FACTOR = 2.0;
/* Contracted capacity = this * old capacity */
static const float CONTRACTION_FACTOR = 0.5;

/*
 * Macro to define a dynamic array of type T and its operations.
 *
 * A type parameter 'T' is valid if, and only if:
 *   - It contains no spaces. Note this means pointers must be typecast.
 */
#define DEFINE_DYNAMIC_ARRAY(T)                                                \
    DEFINE_DYNAMIC_ARRAY_STRUCT(T)                                             \
    DECLARE_DYNAMIC_ARRAY_HELPERS(T)                                           \
    DEFINE_DYNAMIC_ARRAY_CTOR(T)                                               \
    DEFINE_DYNAMIC_ARRAY_DTOR(T)                                               \
    DEFINE_DYNAMIC_ARRAY_ADD(T)                                                \
    DEFINE_DYNAMIC_ARRAY_ADD_AT(T)                                             \
    DEFINE_DYNAMIC_ARRAY_REMOVE(T)                                             \
    DEFINE_DYNAMIC_ARRAY_REMOVE_AT(T)                                          \
    DEFINE_DYNAMIC_ARRAY_CONTAINS(T)                                           \
    DEFINE_DYNAMIC_ARRAY_EXPAND(T)                                             \
    DEFINE_DYNAMIC_ARRAY_CONTRACT(T)                                           \
    DEFINE_DYNAMIC_ARRAY_INSERT_ELEM(T)                                        \
    DEFINE_DYNAMIC_ARRAY_DELETE_ELEM(T)                                        \
    DEFINE_DYNAMIC_ARRAY_RECALC_LOAD(T)

/*
 * A generic dynamic array.
 *
 * A dynamic array is valid if, and only if:
 *   - Its size is how many elements it contains.
 *   - Its capacity is how large the internal array is.
 *   - Its load is its size divided by its capacity.
 *   - All of its elements are consecutive and start at index 0.
 * The constructor is guaranteed to return a valid dynamic array and each
 * operation will keep a valid dynamic array valid.
 */
#define DEFINE_DYNAMIC_ARRAY_STRUCT(T)                                         \
    typedef struct DynamicArrayTag_##T                                          \
    {                                                                           \
        float load;                                                             \
        int size;                                                               \
        int capacity;                                                           \
        T *array;                                                               \
    } DynamicArray_##T;

/*
 * Create an empty dynamic array on the heap.
 *
 * The initial array capacity is defined in a constant at the top of the file.
 *
 * Every case complexity: BIG-THETA( malloc() ).
 * If:
 *   - The type 'T' supplied to the definition macro is valid.
 * Then:
 *   - A pointer to a valid dynamic array is returned.
 *   - The size and load of the array will be 0.
 *   - The capacity will be initialized according to the constants above.
 *   - The elements of the internal array will be random.
 * Edge cases:
 *   - If there is an error allocating either the internal array or the dynamic
 *     array instance, then null will be returned.
 */
#define DEFINE_DYNAMIC_ARRAY_CTOR(T)                                           \
    DynamicArray_##T *dynamic_array_##T##_construct()                           \
    {                                                                           \
        T *array;                                                               \
                                                                                \
        DynamicArray_##T *self = malloc(sizeof(DynamicArray_##T));           \
        array = malloc(INIT_CAPACITY * sizeof(T));                              \
        if (self == NULL || array == NULL)                                   \
        {                                                                       \
            return NULL;                                                        \
        }                                                                       \
        self->array = array;                                                 \
                                                                                \
        self->capacity = INIT_CAPACITY;                                      \
        self->size = 0;                                                      \
        self->load = 0;                                                      \
    }

/*
 * Free all memory associated with a dynamic array.
 *
 * Every case complexity: BIG-THETA( free() ).
 * If:
 *   - The dynamic array is valid.
 * Then:
 *   - All memory associated with the dynamic array will be deallocated.
 */
#define DEFINE_DYNAMIC_ARRAY_DTOR(T)                                           \
    void dynamic_array_##T##_destruct(DynamicArray_##T *self)                \
    {                                                                           \
        free(self->array);                                                   \
        free(self);                                                          \
    }

/*
 * Add an element to the end of a dynamic array.
 *
 * Every case complexity: O( n + malloc() + free() ). N: size of the array.
 * Amortized complexity: O(1).
 * If:
 *   - The dynamic array is valid.
 * Then:
 *   - The new element is added onto the end of the array and 0 is returned.
 *   - The arrays size will be incremented.
 *   - The arrays load factor will be recalculated.
 *   - If the array is full, then it will be expanded to hold the new element.
 * Edge cases:
 *   - If the array is full and reallocation fails (no more memory), then 1
 *     is returned and the array is not altered.
 */
#define DEFINE_DYNAMIC_ARRAY_ADD(T)                                            \
    int dynamic_array_##T##_add(DynamicArray_##T *self, T elem)              \
    {                                                                           \
        return dynamic_array_##T##_insert_elem(self, elem, self->size);   \
    }

/*
 * Add an element at the i-th index of a dynamic array.
 *
 * Every case complexity: O( n + malloc() + free() ) to expand the array.
 *   N: size of the array.
 * Amortized complexity: O(1).
 * If:
 *   - The dynamic array is valid.
 * Then:
 *   - The element will be the new i-th element of the array.
 *   - The arrays size will be incremented.
 *   - The arrays load factor will be recalculated.
 *   - If the array is full, then it will be expanded to hold the new element.
 * Edge cases:
 *   - If the array is full and reallocation fails (no more memory), then 1
 *     is returned and the array is not altered.
 */
#define DEFINE_DYNAMIC_ARRAY_ADD_AT(T)                                         \
    int dynamic_array_##T##_add_at(DynamicArray_##T *self, T elem, int i)    \
    {                                                                           \
        return dynamic_array_##T##_insert_elem(self, elem, i);               \
    }

/*
 * Remove the first occurrence of an element in the array.
 *
 * Worst case complexity: O( n + malloc() + free() ) to contract the array.
 *   N: number of elements in the array.
 * Best case complexity: O(1) to remove the last element.
 * Average case complexity: O(n) to remvoe an intermediate element.
 * If:
 *   - The dynamic array is valid.
 * Then:
 *   - The first occurence of the element is removed from the array and all
 *     elements after it are moved one index down.
 *   - The size of the array is decremented.
 *   - The load factor of the array is recalculated.
 *   - If the load is small enough (see constants), then the array is contracted.
 * Edge cases:
 *   - If the array is contracted and there is an error allocating the new array,
 *     then 1 is returned and the original array is not modified.
 */
#define DEFINE_DYNAMIC_ARRAY_REMOVE(T)                                         \
    int dynamic_array_##T##_remove(DynamicArray_##T *self, T elem)           \
    {                                                                           \
        int idx;                                                                \
                                                                                \
        for (idx = 0; idx < self->size; idx++)                               \
        {                                                                       \
            if ((self->array)[idx] == elem)                                  \
            {                                                                   \
                return dynamic_array_##T##_delete_elem(self, idx);           \
            }                                                                   \
        }                                                                       \
        return 0;                                                               \
    }

/*
 * Remove the i-th element in the array.
 *
 * Worst case complexity: O( n + malloc() + free() ) to contract the array.
 *   N: number of elements in the array.
 * Best case complexity: O(1) to remove the last element.
 * Average case complexity: O(n) to remvoe an intermediate element.
 * If:
 *   - The dynamic array is valid.
 * Then:
 *   - The i-th element is removed from the array and all elements after it
 *     are moved one index down.
 *   - The size of the array is decremented.
 *   - The load factor of the array is recalculated.
 *   - If the load is small enough (see constants), then the array is contracted.
 * Edge cases:
 *   - If the array is contracted and there is an error allocating the new array,
 *     then 1 is returned and the original array is not modified.
 */
#define DEFINE_DYNAMIC_ARRAY_REMOVE_AT(T)                                      \
    int dynamic_array_##T##_remove_at(DynamicArray_##T *self, int i)         \
    {                                                                           \
        return dynamic_array_##T##_delete_elem(self, i);                     \
    }

/*
 * Determine if the array contains an element.
 *
 * Every case complexity: O(n).
 * If:
 *   - The dynamic array is valid
 * Then:
 *   - If the array contains the element, then 1 is returned. If it does not,
 *     then 0 is returned.
 */
#define DEFINE_DYNAMIC_ARRAY_CONTAINS(T)                                       \
    int dynamic_array_##T##_contains(DynamicArray_##T *self, T elem)         \
    {                                                                           \
        int idx;                                                                \
        T *array;                                                               \
                                                                                \
        array = self->array;                                                 \
        for (idx = 0; idx < self->size; idx++)                               \
        {                                                                       \
            if (array[idx] == elem)                                             \
            {                                                                   \
                return 1;                                                       \
            }                                                                   \
        }                                                                       \
        return 0;                                                               \
    }

/*
 * Declare signatures of helper methods.
 */
#define DECLARE_DYNAMIC_ARRAY_HELPERS(T)                                       \
    static int dynamic_array_##T##_expand(DynamicArray_##T *self);           \
    static int dynamic_array_##T##_contract(DynamicArray_##T *self);         \
    static int dynamic_array_##T##_insert_elem(DynamicArray_##T *self,       \
                                               T elem, int i);                  \
    static int dynamic_array_##T##_delete_elem(DynamicArray_##T *self,       \
                                               int rem_idx);                    \
    static void dynamic_array_##T##_recalc_load(DynamicArray_##T *self);     \

/*
 * Expand the array.
 *
 * The capacity of the new array is defined in the EXPANSION_FACTOR constant
 * at the top if this file.
 *
 * Every case complexity: O( n + malloc() + free() ). N: size of array.
 * If:
 *   - The array is valid.
 * Then:
 *   - A new, expanded array is allocated.
 *   - All elements in the dynamic array are copied to this new array.
 *   - The dynamic arrays internal array is swapped with this new array.
 *   - 0 is returned.
 * Edge cases:
 *   - If there is an error allocating the new array, then 1 is returned. and
 *     the old array is not modified.
 */
#define DEFINE_DYNAMIC_ARRAY_EXPAND(T)                                         \
    static int dynamic_array_##T##_expand(DynamicArray_##T *self)            \
    {                                                                           \
        T *new_array;                                                           \
        int new_capacity;                                                       \
        int idx;                                                                \
                                                                                \
        /* Allocate new array. */                                               \
        new_capacity = EXPANSION_FACTOR * (self->capacity);                  \
        new_array = malloc(new_capacity * sizeof(T));                           \
        if (new_array == NULL)                                                  \
        {                                                                       \
            /* Return and do not alter original array. */                       \
            return 1;                                                           \
        }                                                                       \
                                                                                \
        /* Copy elements over and swap arrays. */                               \
        for (idx = 0; idx <= self->size; idx++)                              \
        {                                                                       \
            new_array[idx] = self->array[idx];                               \
        }                                                                       \
        free(self->array);                                                   \
        self->array = new_array;                                             \
                                                                                \
        self->capacity = new_capacity;                                       \
        dynamic_array_##T##_recalc_load(self);                               \
                                                                                \
        return 0;                                                               \
    }

/*
 * Contract the array.
 *
 * The capacity of the new array is defined in the CONTRACTION_FACTOR constant
 * at the top if this file.
 *
 * Every case complexity: O( n + malloc() + free() ). N: size of array.
 * If:
 *   - The array is valid.
 * Then:
 *   - A new, contracted array is allocated.
 *   - All elements in the dynamic array are copied to this new array.
 *   - The dynamic arrays internal array is swapped with this new array.
 *   - 0 is returned.
 * Edge cases:
 *   - If there is an error allocating the new array, then 1 is returned and the
 *     old array is not modified.
 */
#define DEFINE_DYNAMIC_ARRAY_CONTRACT(T)                                       \
    static int dynamic_array_##T##_contract(DynamicArray_##T *self)          \
    {                                                                           \
        T *new_array;                                                           \
        int new_capacity;                                                       \
        int idx;                                                                \
                                                                                \
        /* Allocate new array. */                                               \
        new_capacity = CONTRACTION_FACTOR * self->capacity;                  \
        new_array = malloc(new_capacity * sizeof(T));                           \
        if (new_array == NULL)                                                  \
        {                                                                       \
            /* Return error and leave old array unmodified. */                  \
            return 1;                                                           \
        }                                                                       \
                                                                                \
        /* Copy elements over and swap arrays. */                               \
        for (idx = 0; idx <= self->size; idx++)                              \
        {                                                                       \
            new_array[idx] = self->array[idx];                               \
        }                                                                       \
        free(new_array);                                                        \
        self->array = new_array;                                             \
                                                                                \
        self->capacity = new_capacity;                                       \
        dynamic_array_##T##_recalc_load(self);                               \
                                                                                \
        return 0;                                                               \
    }

/*
 * Insert an element at the i-th index of a dynamic array.
 * Helper methods for add, add_at operations.
 * 
 * Worst case complexity: O(n + malloc() + free() ) to expand the array.
 *   N: size of array.
 * Best case complexity: O(1) to add to the end of the array.
 * If:
 *   - The dynamic array is valid.
 *   - 0 <= i <= self->size.
 * Then:
 *   - The element will be the new i-th element in the dynamic array.
 *   - The dynamic arrays size will be incremented.
 *   - The dynamic arrays load factor will be recalculated.
 *   - If the dynamic array is full, then it will be expanded.
 * Edge cases:
 *   - If the dynamic array is full and there is an error expanding it, then 1
 *     is returned.
 */
#define DEFINE_DYNAMIC_ARRAY_INSERT_ELEM(T)                                    \
static int dynamic_array_##T##_insert_elem(DynamicArray_##T *self, T elem,   \
                                           int i)                               \
{                                                                               \
    int idx;                                                                    \
    int status;                                                                 \
    T *array;                                                                   \
                                                                                \
    /* Expand if needed. */                                                     \
    if (self->load == EXPANSION_POINT)                                       \
    {                                                                           \
        status = dynamic_array_##T##_expand(self);                           \
        if (status > 1)                                                         \
        {                                                                       \
            return status; /* pass allocation error code up */                  \
        }                                                                       \
    }                                                                           \
                                                                                \
    /* Move all elements in [i+1..self->size) forward one index. */          \
    array = self->array;                                                     \
    for (idx = self->size; idx > i; idx--)                                   \
    {                                                                           \
        array[idx] = array[idx - 1];                                            \
    }                                                                           \
                                                                                \
    array[idx] = elem;                                                          \
    self->size += 1;                                                         \
    dynamic_array_##T##_recalc_load(self);                                   \
                                                                                \
    return 0;                                                                   \
}

/*
 * Delete the element at the ith index of a dynamic array.
 * Helper method for the remove, remove_at operations.
 *
 * If:
 *   - The dynamic array is valid.
 *   - 0 <= i < self->size.
 * Then:
 *   - The element at the i-th index of the array will be removed.
 *   - All elements higher than the i-th index will be moved an index down.
 *   - The array size will be decremented.
 *   - The array load will be recalculated.
 *   - If the array is sufficiently small after removal (see constants), then
 *     the array will be contracted. The capacity and load will be recalculated.
 *   - 0 is returned.
 * Edge cases:
 *   - If the array is contracted and there is an error allocating a new array,
 *     then 1 is returned.
 */
#define DEFINE_DYNAMIC_ARRAY_DELETE_ELEM(T)                                    \
static int dynamic_array_##T##_delete_elem(DynamicArray_##T *self,           \
                                           int i)                               \
{                                                                               \
    int idx;                                                                    \
    T *array;                                                                   \
                                                                                \
    /* Copy every element in [i+1..) back one index. Overwrites array[i] */     \
    array = self->array;                                                     \
    for (idx = i + 1; idx < self->size; idx++)                               \
    {                                                                           \
        array[idx - 1] = array[idx];                                            \
    }                                                                           \
                                                                                \
    /* Contract if necessary. Only contract if array has expanded before */     \
    if (self->load <= CONTRACTION_POINT && self->capacity > INIT_CAPACITY)\
    {                                                                           \
        return dynamic_array_##T##_contract(self);                           \
    }                                                                           \
                                                                                \
    self->size -= 1;                                                         \
    dynamic_array_##T##_recalc_load(self);                                   \
                                                                                \
    return 0;                                                                   \
}

/*
 * Set load equal to size divided by capacity.
 *
 * If:
 *   - The dynamic array is valid.
 * Then:
 *   - load will equal size divided by capacity.
 */
#define DEFINE_DYNAMIC_ARRAY_RECALC_LOAD(T)                                    \
    static void dynamic_array_##T##_recalc_load(DynamicArray_##T *self)      \
    {                                                                           \
        self->load = ((float)self->size) / ((float)self->capacity);    \
    }

#endif

linked_list.h:

/*
 * A basic, generic forward-linked-list data structure and relevant operations
 * implemented from scratch in pure, old fashioned C.
 *
 * All functions in this header are prepended with 'linked_list_' to create a
 * psuedo-namespace. The linked list supports operations to: create a new linked
 * list, add an element (at the end or at an index), remove an element (from the
 * end or by key), test if a key is in the list, and determine the size of the
 * list.
 *
 * Written by Max Hanson, June 2019.
 */


#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <stdlib.h> /* For malloc/NULL */


/*
 * A generic forward-linked-list data structure.
 *
 * Note that by 'generic' I mean the key is a void pointer that can point to any
 * data type. It is the client's responsibility to track what data type the
 * linked list's keys are and safely cast them to/from void pointers.
 * Also note that it is necessary that each key in the list points to an object
 * on the heap that was allocated with 'malloc/calloc/realloc'. This is because
 * each key is freed in the linked_list_destruct operation. Undefined behavior
 * will occur if this requirement is not met.
 *
 * A LinkedList is valid if, and only if:
 *   - The key of all nodes is non-null pointer.
 *   - The next node of all nodes points to another node, except the tail node
 *     whose next is null.
 *   - There are no loops in the list.
 *   - The head node leads to the tail node.
 * Note that these operations do not verify linked list validity, but it is
 * guaranteed that the constructor will create a valid linked list and that
 * each operation will leave a valid linked list valid.
 */
typedef struct linked_list_node_tag LinkedListNode;
struct linked_list_node_tag
{
    void *key;
    LinkedListNode *next;
};
typedef struct linked_list_tag
{
    int size;
    LinkedListNode *head;
    LinkedListNode *tail;
} LinkedList;

/*
 * Create a new linked list from a key.
 *
 * Every case complexity: BIG-THETA(1).
 * If:
 *   - The head_key is not NULL.
 * Then:
 *   - A valid LinkedList is returned such that:
 *     - Its head nodes key is the head_key.
 *     - Its head node is its tail node.
 *     - Its size is 1.
 * Edge cases:
 *   - If there is not enough space on the heap for a new LinkedList and
 *     LinkedListNode, then NULL is returned.
 */
LinkedList *linked_list_construct(void *head_key);

/*
 * Deallocate a linked list.
 *
 * 
 * Every case runtime: BIG-THETA(n) where n is the size of the list.
 * If:
 *   - The list is a valid linked list.
 * Then:
 *   - All keys in the list will be freed.
 *   - All nodes in the list will be freed.
 *   - The linked list itself will be freed.
 *   - The list pointer will be NULL.
 */
void linked_list_destruct(LinkedList *list);

/*
 * Append a key to a linked list.
 *
 * Every case complexity: BIG-THETA(1).
 * If:
 *   - The list is a valid LinkedList.
 *   - The key points to the same data type as all nodes of the list.
 * Then:
 *   - A new node is created whose key is The key.
 *   - The lists previous tail will point to this new node.
 *   - The lists tail will point to this new node.
 *   - The lists size will be incremented.
 *   - A positive value is returned.
 * Edge cases:
 *   - If there is not enough space on the heap for a new LinkedListNode, then
 *     zero is returned.
 */
int linked_list_add(LinkedList *list, void *key);

/*
 * Add an element to the i-th index of a linked list.
 *
 * Every case complexity: O(n) where n is the number of nodes in the list.
 * Worst case complexity: BIG-THETA(n).
 * Best case complexity: BIG-THETA(1).
 * If:
 *   - The list is a valid LinkedList.
 *   - The key points to the same data type as all nodes of the list.
 *   - 0 <= 'i' <= list.size.
 * Then:
 *   - A new node is created whose key is The key.
 *   - This new node will be the i-th node of the list.
 *   - If a new head is added, then the lists head will be updated.
 *   - The lists size will be incremented.
 *   - A positive value is returned.
 * Edge cases:
 *   - If there is not enough space on the heap for a new LinkedListNode, then
 *     zero is returned.
 */
int linked_list_add_at(LinkedList *list, void *key, int i);

/*
 * Remove the i-th node of a linked list.
 *
 * Every case complexity: O(n) where n is the number of elements in the list.
 * Worst case complexity: BIG-THETA(n).
 * Best case complexity: BIG-THETA(1).
 * If:
 *   - The list is a valid LinkedList.
 *   - 0 <= i < 'list.size'.
 * Then:
 *   - The node previously at the lists i-th index will be removed.
 *   - If the head/tail is removed, then the new head/tail will be updated.
 *   - The lists size will be decremented.
 */
void linked_list_remove_at(LinkedList *list, int i);

/*
 * Remove the first node containing a certain key from a linked list.
 *
 * Every case complexity: O(n) where n is the number of elements in the list.
 * Worst case complexity: BIG-THETA(n).
 * Best case complexity: BIG-THETA(1).
 * If:
 *   - The list is a valid LinkedList.
 *   - The key is not NULL.
 * Then:
 *   - If the list contains the key, the first node with the matching key
 *     (comparing addresses) is removed and a positive value is returned.
 *   - If the list doesnt contain the key, then the list is unchanged and zero
 *     is returned.
 */
int linked_list_remove_key(LinkedList *list, void *key);

/*
 * Determine if a linked list contains a key.
 *
 * Every case complexity: O(n) where n is the nubmer of elements in the list.
 * Worst case complexity: BIG-THETA(n).
 * Best case complexity: BIG-THETA(1).
 * If:
 *   - The list is a valid LinkedList.
 *   - The key is not NULL.
 * Then:
 *   - If the list contains the key, then a positive value is returned.
 *   - If the list doesnt contain the key then zero is returned.
 */
int linked_list_contains_key(LinkedList *list, void *key);

/*
 * Get the key of the i-th node of a linked list.
 *
 * Every case complexity: O(n) where n is the number of elements in the list.
 * Worst case complexity: BIG-THETA(n).
 * Best case complexity: BIG-THETA(1).
 * If:
 *   - The list is a valid LinkedList.
 *   - 0 <= i < list.size
 * Then:
 *   - The key of the i-th node of the list is returned.
 */
void *linked_list_get_key(LinkedList *list, int i);


#endif

linked_list.c:

/**
 * An implementation of the linked list operations from scratch.
 *
 * See the function definitions in the linked list header for documentation.
 *
 * Written by Max Hanson, June 2019.
 */

#include "linked_list.h"

static LinkedListNode *create_node(void *key);
static void point_to_index(LinkedList *list, LinkedListNode **prev_ptr,
                           LinkedListNode **cursor_ptr, int index);
static void point_to_key(LinkedList *list, LinkedListNode **prev_ptr,
                         LinkedListNode **cursor_ptr, void *key);
static void remove_node(LinkedList *list, LinkedListNode *prev,
                        LinkedListNode *cursor);


LinkedList *linked_list_construct(void *head_key)
{
    LinkedListNode *new_node;
    LinkedList *new_llist;

    new_node = create_node(head_key); 
    new_llist = malloc(sizeof(LinkedList));
    if (new_node == NULL || new_llist == NULL)
    {
        /* Allocation failed. */
        return NULL;
    }
    new_llist->size = 1;
    new_llist->head = new_node;
    new_llist->tail = new_node;

    return new_llist;
}

void linked_list_destruct(LinkedList *list)
{
    LinkedListNode *cursor;
    LinkedListNode *prev;

    /* Step through, freeing each previous. Frees tail too. */
    cursor = list->head;
    prev = NULL;
    while (cursor != NULL)
    {
        prev = cursor;
        cursor = cursor->next;

        free(prev->key);
        free(prev);
    }
    free(list);
}

int linked_list_add(LinkedList *list, void *key)
{
    LinkedListNode *new_node;

    new_node = create_node(key);
    if (new_node == NULL)
    {
        return 0;
    }

    list->tail->next = new_node;
    list->tail = new_node;
    list->size += 1;

    return 1;
}

int linked_list_add_at(LinkedList *list, void *key, int i)
{
    LinkedListNode *new_node;
    LinkedListNode *cursor;
    LinkedListNode *prev;
    int idx;

    new_node = create_node(key);
    if (new_node == NULL)
    {
        return 0;
    }

    point_to_index(list, &prev, &cursor, i);
    /* Add new_node as new i-th node. */
    if (cursor == list->head)
    {
        /* Adding new head. Prev is null. */
        new_node->next = cursor;
        list->head = new_node;
    }
    if (prev == list->tail)
    {
        /* Adding a new tail. Cursor is null. */
        prev->next = new_node;
        list->tail = new_node;
    }
    else
    {
        /* Adding intermediate node. */
        prev->next = new_node;
        new_node->next = cursor;
    }
    list->size += 1;

    return 1;
}

void linked_list_remove_at(LinkedList *list, int i)
{
    LinkedListNode *cursor;
    LinkedListNode *prev;
    int idx;

    /* NOTE assumed that i is within range, no checking. */
    point_to_index(list, &prev, &cursor, i);
    remove_node(list, prev, cursor);
}

int linked_list_remove_key(LinkedList *list, void *key)
{
    LinkedListNode *cursor;
    LinkedListNode *prev;
    int idx;

    point_to_key(list, &prev, &cursor, key);
    if (cursor == NULL)
    {
        /* NOTE null if no matching key. */
        return 0;
    }
    remove_node(list, prev, cursor);
    return 1;
}

int linked_list_contains_key(LinkedList *list, void *key)
{
    LinkedListNode *cursor;
    LinkedListNode *prev;
    int idx;

    point_to_key(list, &prev, &cursor, key);
    return (cursor != NULL); /* NOTE null if no matching key. */
}

void *linked_list_get_key(LinkedList *list, int i)
{
    LinkedListNode *cursor;
    LinkedListNode *prev;
    int idx;

    point_to_index(list, &prev, &cursor, i);

    return cursor->key;
}

/* === HELPER METHODS === */

/*
 * Create a new node on the heap.
 *
 * Every case complexity: O(1).
 * If:
 *   - The key is not NULL.
 * Then:
 *   - A pointer to a node whose key is 'key' and next is NULL is returned.
 * Edge cases:
 *   - If there is not room for a new node on the heap, the NULL is returned.
 */
static LinkedListNode *create_node(void *key)
{
    LinkedListNode *new_node;

    new_node = malloc(sizeof(LinkedListNode));
    if (new_node == NULL)
    {
        return NULL;
    }
    new_node->key = key;
    new_node->next = NULL;

    return new_node;
}

/*
 * Point a cursor to a lists i-th node.
 *
 * Note the double pointers used in the arguments. This is so the function can
 * modify the first-level pointer.
 *
 * Every case runtime: O(n) where n is the number of nodes in the list.
 * Worst case runtime: BIG-THETA(n).
 * Best case runtime: BIG-THETA(1).
 * If:
 *   - The list is a valid linked list.
 *   - 0 <= index <= list.size
 * Then:
 *   - The cursor will point to the i-th node.
 *   - The prev will point to the (i-1)-th node, or null if cursor is the head.
 *   - If i = list.size: then cursor will be null and prev will be the tail.
 */
static void point_to_index(LinkedList *list, LinkedListNode **prev_ptr,
                           LinkedListNode **cursor_ptr, int index)
{
    int idx;
    LinkedListNode *cursor;
    LinkedListNode *prev;

    /* Point cursor, prev to the correct nodes. */
    idx = 0;
    cursor = list->head;
    prev = NULL;
    while(idx != index)
    {
        prev = cursor;
        cursor = cursor->next;
        idx++;
    }

    /* Point what the args point to to the correct nodes. */
    (*prev_ptr) = prev;
    (*cursor_ptr) = cursor;
}

/*
 * Point a cursor to the first node in a list containing a key.
 *
 * A node contains a key if they both point to the same location in memory.
 * Note the double pointers used in the arguments. This is so the function can
 * modify the first-level pointer.
 *
 * Every case runtime: O(n) where n is the size of the list.
 * Worst case runtime: BIG-THETA(n).
 * Best case runtime: BIG-THETA(1).
 * If:
 *   - The list is a valid linked list.
 *   - The key points to the same type of data as the list.
 * Then:
 *   - If the key is in the list, then the cursor will point to the first node
 *     that contains that key and the prev will point to its previous.
 *   - If the key is not in the list, then the cursor and prev will be NULL.
 */
static void point_to_key(LinkedList *list, LinkedListNode **prev_ptr,
                           LinkedListNode **cursor_ptr, void *key)
{
    LinkedListNode *cursor;
    LinkedListNode *prev;

    /* Point cursor, prev to the correct nodes */
    cursor = list->head;
    prev = NULL;
    while(cursor != NULL && cursor->key != key)
    {
        prev = cursor;
        cursor = cursor->next;
    }

    /* Point what the args point to to the correct nodes */
    (*cursor_ptr) = cursor;
    (*prev_ptr) = prev;
}

/*
 * Remove a node from a linked list.
 *
 * Every case runtime: O(1).
 * If:
 *   - The list is a valid list.
 *   - The cursor points to a node in the list.
 *   - The prev points to the node that points to the cursor.
 * Then:
 *   - The list will no longer contain the cursor.
 *   - The lists size will be decremented.
 *   - If the cursor was the lists head/tail, then the head/tail will be updated.
 *   - The cursor will be deallocated.
 */
static void remove_node(LinkedList *list, LinkedListNode *prev,
                        LinkedListNode *cursor)
{
    if (cursor == list->head)
    {
        /* Removing head. Prev is NULL. */
        list->head = cursor->next;
    }
    else if (cursor == list->tail)
    {
        /* Removing tail. */
        prev->next = NULL;
        list->tail = prev;
    }
    else
    {
        /* Removing intermediate node. */
        prev->next = cursor->next;
    }
    free(cursor);
    list->size -= 1;
}
```

Answer 1

- float

float constants need the suffix f:

static const float  EXPANSION_POINT = 1.0f;

if not, you're assigning a double constant implicitly converted to float.

---

- functions that accept 0 parameters

Functions that accept 0 parameters should always be defined as type foo(void)

type foo() means different things depending on the context. It is different in prototypes (accept any parameters) and definitions (accept 0 parameters), so it's better to avoid that and explicitly use (void).

---

- sizeof(type) vs sizeof(*pointer)

It's better to use sizeof(*pointer) so that if the type of pointer ever changes, the code is still valid.

---

- Be careful with error handling

It's better to use sizeof(*pointer) so that if the type of pointer ever changes, the code is still valid.

In this code of yours:

    DynamicArray_##T *self = malloc(sizeof(DynamicArray_##T));      \
    array = malloc(INIT_CAPACITY * sizeof(T));                      \
    if (self == NULL || array == NULL)                              \
    {                                                               \
        return NULL;                                                \
    }                                                           

Imagine that one of the allocations fails but the other doesn't.

Solution:

    self    = malloc(sizeof(*self));                                \
    if (!self)                                                      \
        return  NULL;                                               \
    array   = malloc(sizeof(*array) * INIT_CAPACITY);               \
    if (!array)                                                     \
        goto err_array;                                             \
...
err_array:                                                          \
    free(self);                                                     \
    return  NULL;                                                   \

---

- Reached end of non-void function

In the function DynamicArray_##T *dynamic_array_##T##_construct(void) you forgot the final return statement.

Fixed:

#define DEFINE_DYNAMIC_ARRAY_CTOR(T)                    
DynamicArray_##T    *dynamic_array_##T##_construct(void)            \
{                                                                   \
    DynamicArray_##T    *self;                                      \
                                                                    \
    self    = malloc(sizeof(*self));                                \
    if (!self)                                                      \
        return  NULL;                                               \
    self->array = malloc(sizeof(*self->array) * INIT_CAPACITY);     \
    if (!self->array)                                               \
        goto err_array;                                             \
                                                                    \
    self->capacity = INIT_CAPACITY;                                 \
    self->size = 0;                                                 \
    self->load = 0.0;                                               \
                                                                    \
    return  self;                                                   \
                                                                    \
err_array:                                                          \
    free(self);                                                     \
    return  NULL;                                                   \
}

---

- ptrdiff_t

The appropriate type for pointer arithmetics (and a dynamic array is full of that) is ptrdiff_t. Of course int will work in almost any case (unless you plan to have an array with more than ~2 thousand million elements), but ptrdiff_t helps self-documenting the code.

#include <stddef.h>

static const ptrdiff_t  INIT_CAPACITY = 10;

#define DEFINE_DYNAMIC_ARRAY_STRUCT(T)                              \
struct DynamicArrayTag_##T {                                        \
    float       load;                                               \
    ptrdiff_t   size;                                               \
    ptrdiff_t   capacity;                                           \
    T           *array;                                             \
};                                                                  \
typedef struct DynamicArrayTag_##T DynamicArray_##T;

---

- comparing floating-point variables

There are infinite different real numbers between any two given numbers. In C, that is not true, because of obvious reasons. But there are still too many different float possible values between any two given values.

Comparisons like if (self->load == EXPANSION_POINT) are unlikely to work.

Depending on the desired behavior, the solution is easy or not. In this case it is easy:

if (self->load >= EXPANSION_POINT)

---

- nmemb vs size (This is somewhat personal; feel free to disagree)

There is a slight difference between the terms size and nmemb.

size is a name normally used to mean absolute size in Bytes. Its natural type is size_t.

nmemb is a name normally used to mean number of members of an array. Its natural type is ptrdiff_t, although size_t is not uncommon to see (sadly).

So, I would change the struct this way:

#define DEFINE_DYNAMIC_ARRAY_STRUCT(T)                              \
struct DynamicArrayTag_##T {                                        \
    float       load;                                               \
    ptrdiff_t   nmemb;                                              \
    ptrdiff_t   capacity;                                           \
    T           *array;                                             \
};                                                                  \
typedef struct DynamicArrayTag_##T DynamicArray_##T;

---

- double vs float

Unless you have a very good reason, always use double.

It's usually faster, and has a lot more precission. Only some embedded systems should use float. Or one can also use float for huge arrays of floating-point numbers, where precission is not important, and cache/RAM speed is a problem.

#define EXPANSION_POINT     (1.0) /* load > this -> array expands */
#define CONTRACTION_POINT   (0.3) /* load < this -> array contracts */
/* Expanded capacity = this * old capacity */
#define EXPANSION_FACTOR    (2.0)
/* Contracted capacity = this * old capacity */
#define CONTRACTION_FACTOR  (0.5)

#define DEFINE_DYNAMIC_ARRAY_STRUCT(T)                              \
struct DynamicArrayTag_##T {                                        \
    double      load;                                               \
    ptrdiff_t   nmemb;                                              \
    ptrdiff_t   capacity;                                           \
    T           *array;                                             \
};                                                                  \
typedef struct DynamicArrayTag_##T DynamicArray_##T;

---

- EXPANSION_POINT

Given the instability of floating-point arithmetics, I would set the expansion point a bit lower than 1.0 (maybe 0.85).

An even better option, if you want it to be 1 is to use the integer values directly (and delete EXPANSION_POINT):

if (self->size == self->capacity)
        // Expand

---

Fixed code sample:

#define DEFINE_DYNAMIC_ARRAY_INSERT_ELEM(T)             
static int dynamic_array_##T##_insert_elem(DynamicArray_##T *self,  \
                                            T elem, ptrdiff_t i)    \
{                                                                   \
    ptrdiff_t   j;                                                  \
    int         status;                                             \
                                                                    \
    /* Expand if needed. */                                         \
    if (self->size == self->capacity) {                             \
        status = dynamic_array_##T##_expand(self);                  \
        if (status)                                                 \
            return  status;                                         \
    }                                                               \
                                                                    \
    for (j = self->nmemb; j > i; j--)                               \
        self->array[j] = self->array[j - 1];                        \
    self->array[j] = elem;                                          \
    self->nmemb++;                                                  \
    dynamic_array_##T##_recalc_load(self);                          \
                                                                    \
    return  0;                                                      \
}

---

Answer 2

First impressions: I like the comments that clearly specify preconditions and postconditions - very valuable in C! One thing that wasn't clear was the meaning of the return value from the insert/add/remove methods - is that the number of elements added/removed?

It would be nice to have a list of all the functions at the top of the file (I was surprised to find no accessor to return the size of a dynamic array).

It's a shame there's no simple main() included.

---

A limitation of pasting type names to create identifiers is that it requires typedefs for types such as long long or struct foo or char*. We can probably live with that.

---

Here's a memory leak:

LinkedListNode *new_node;
LinkedList *new_llist;

new_node = create_node(head_key); 
new_llist = malloc(sizeof(LinkedList));
if (new_node == NULL || new_llist == NULL)
{
    /* Allocation failed. */
    return NULL;
}

If one of the allocations succeeds and the other fails, we never free the successful one, and lose our reference to it.

Thankfully, free() will do the right thing when given a null pointer, so we can unconditionally free both pointers:

LinkedListNode *const new_node = create_node(head_key); 
LinkedList *const new_llist = malloc(sizeof *new_llist);

if (new_node == NULL || new_llist == NULL) {
    /* Allocation failed. */
    free(new_node);
    free(new_llist);
    return NULL;
}

---

A nicety: it may simplify calling code if it can accept a null pointer instead of a list:

#define DEFINE_DYNAMIC_ARRAY_DTOR(T)                            \
    void dynamic_array_##T##_destruct(DynamicArray_##T *self)   \
    {                                                           \
        if (self) {                                             \
            free(self->array);                                  \
            free(self);                                         \
        }                                                       \
    }

This makes it behave more like free() causing less surprise to users.

---

I don't think there's much to be gained by having load as a member, given that it can always be obtained from size and capacity.

---

We can make the expand/contract functions much more efficient, by using realloc() instead of malloc() and copy every time:

#define DEFINE_DYNAMIC_ARRAY_EXPAND(T)                                  \
    static int dynamic_array_##T##_expand(DynamicArray_##T *self)       \
    {                                                                   \
        size_t new_capacity = EXPANSION_FACTOR * (self->capacity);      \
        T *new_array = realloc(self->array, new_capacity * sizeof (T)); \
        if (!new_array) {                                               \
            /* Return and do not alter original array. */               \
            return 1;                                                   \
        }                                                               \
                                                                        \
        self->array = new_array;                                        \
        self->capacity = new_capacity;                                  \
        dynamic_array_##T##_recalc_load(self);                          \
        return 0;                                                       \
    }

realloc() only needs to copy data if it couldn't extend the existing allocation.

The contract() function has almost exactly the same code, with only a different new_capacity calculation (and perhaps should be merged).

On a related note, instead of loops like this:

/* Move all elements in [i+1..self->size) forward one index. */          \
array = self->array;                                                     \
for (idx = self->size; idx > i; idx--)                                   \
{                                                                           \
    array[idx] = array[idx - 1];                                            \
}                                                                           \

we could save both code and CPU time by using memmove() (untested):

    /* Move all elements in [i+1..self->size) forward one index. */ \
    memmove(self->array + i + 1, self->array + i,                   \
            (self->size - i) * sizeof *self->array);                \

And in the delete_elem():

    /* Copy every element in [i+1..) back one index. Overwrites array[i] */ \
    memmove(self->array + i, self->array + i + 1,                   \
            (self->size - i) * sizeof *self->array);                \

---

We have unused local variables called idx in several functions: linked_list_add_at(), linked_list_remove_at(), linked_list_remove_key(), linked_list_contains_key(), linked_list_get_key().

The dynamic array construct declaration ought to be a prototype (explicitly declare (void) = no arguments, rather than () = unspecified arguments).

Make INIT_CAPACITY an unsigned type to prevent unexpected promotion when multiplying by size_t. Using double rather than float for the other constants reduces compiler warnings, too.