Typesafe generic array in C

array.h

// This file introduces a simple but powerful generic dynamic array concept.
// It works by defining struct for each type and then using type generic macros to work
// with these structs. 
//
// This approach was chosen because: 
// 1) Type safety: Array of int should be distinct type from Array of char.
//    Not only does it require more state management it is also a mjor pain to work with because we always
//    need to cast to our desired type (or pass the type to some acessor macro).
//    This discvalified the one Array struct for all types holding the size of the type currently used.
// 
// 2) We need to be able to work with empty arrays easily and safely. 
//    Empty arrays are the most common arrays there are so having them as a special and error prone case
//    is less than ideal. This discvalifies the typed pointer to allocated array prefixed with header holding
//    the meta data. (See how stb library implements "stretchy buffers" and images).
//    This approach introduces a lot of ifs, makes the emta data adress unstable and requires more memory lookups.
//
// 3) Array types need to be distinct from non array types. ie char* cannot be an array handle. We need
//    to be able to tell if array should be deallocated based on the type alone. This is because in more complex systems
//    we often return a pointer to internally managed data and these pointers should NOT be deallocated. Thus we would 
//    need to document every function if the data should be freed or not!
// 
// Additionally these arrays CAN implemnt the following:
// 1) Hold the info abouyt allocators. This would probably mean having an init function as well.
// 
// 2) Have some indicator of if the array was allocated or not. 
//    The highest or lowest bit of capacity, lowest or highest bit of allocator can serve for this purpose.
//    This of course enables quick "borrowing" which can be used to pass data into an interface that accepts
//    a dynamic array without actually needing the full functionality. It can also (and probably more importantly) be used for stack backing
//    arrays - we allocate lets say 128B array on the stack and initialize the array with this data with the allocated flag to false. 
//    We only reallocate if we need more than the ammount of static data given and this time allocate dynamically setting the flag to true.
//    This can potentially give us a lot of speed!
//    The downside is that unless we name the allocator something like allocator_and_flag_bit we cannot really comunicate to whoever is using the
//    the structure not to use the field directly and ask for it through some function. This is not a problem in practice. 
//
// 3) We can null terminate all array types (or just with size 1) to be able to use these arrays for strings that are 
//    always C string compatible. This can be very very handy.
// 
// 4) Because the functions are implemented as macros we make them all __LINE__, __FILE__, __FUNCTION__ transparent. 
//    This can be used for debugging memory leaks.

//Define to include implementation!
#define JOT_ARRAY_IMPL
//Define to run the example!
#define RUN_EXAMPLE

#ifndef JOT_ARRAY
#define JOT_ARRAY

#include <stdint.h> 
#include <stdlib.h> //malloc, free
#include <assert.h> //assert
#include <string.h> //memcpy, memset

#ifndef __cplusplus
#include <stdbool.h>
#endif

//Feel free to change to size_t
typedef int64_t isize;

#define DEFINE_ARRAY_TYPE(Type, Struct_Name) \
    typedef struct Struct_Name {             \
        Type* data;                          \
        isize size;                          \
        isize capacity;                      \
    } Struct_Name                            \
    
//Some common types. 
//You can define array types like this for 
//any type (can be struct, union or anything else)
DEFINE_ARRAY_TYPE(uint8_t,  u8_Array);
DEFINE_ARRAY_TYPE(uint16_t, u16_Array);
DEFINE_ARRAY_TYPE(uint32_t, u32_Array);
DEFINE_ARRAY_TYPE(uint64_t, u64_Array);

DEFINE_ARRAY_TYPE(int8_t,   i8_Array);
DEFINE_ARRAY_TYPE(int16_t,  i16_Array);
DEFINE_ARRAY_TYPE(int32_t,  i32_Array);
DEFINE_ARRAY_TYPE(int64_t,  i64_Array);

DEFINE_ARRAY_TYPE(float,    f32_Array);
DEFINE_ARRAY_TYPE(double,   f64_Array);
DEFINE_ARRAY_TYPE(void*,    ptr_Array);

//Low level array operation that sets capacity to exactly the value specified.
//If new capacity is larger then size reallocates and sets capacity
//If new capacity is smaller then size reallocates and sets both size and capacity thus perserving invarinats
//If new capacity is 0 deallocates
#define array_set_capacity(array_ptr, capacity) \
    _array_set_capacity(array_ptr, sizeof *(array_ptr)->data, capacity)
    
//Deallocates and resets the array
#define array_deinit(array_ptr) \
    array_set_capacity(array_ptr, 0)

//If the array capacity is lower than to_capacity sets the capacity to to_capacity. 
//If setting of capacity is required and the new capcity is less then one geometric growth 
// step away from current capacity grows instead.
#define array_reserve(array_ptr, to_capacity) \
    _array_reserve(array_ptr, sizeof *(array_ptr)->data, to_capacity) 

//Sets the array size to the specied to_size. 
//If the to_size is smaller than current size simply dicards further items
//If the to_size is greater than current size zero initializes the newly added items
#define array_resize(array_ptr, to_size)              \
    _array_resize(array_ptr, sizeof *(array_ptr)->data, to_size, true) 
   
//Just like array_resize except doesnt zero initialized newly added region
#define array_resize_for_overwrite(array_ptr, to_size)              \
    _array_resize(array_ptr, sizeof *(array_ptr)->data, to_size, false) 

//Sets the array size to 0. Does not deallocate the array
#define array_clear(array_ptr) \
    array_resize(array_ptr, 0)

//Appends item_count items to the end of the array growing it
#define array_append(array_ptr, items, item_count) \
    /* Here is a little hack to typecheck the items array.*/ \
    /* We try to assign the first item to the first data but never actaully run it */ \
    /* This forces the compiler to evaluate typecheck the compaibility of the types. */ \
    (void) (0 ? *(array_ptr)->data = *(items), 0 : 0), \
    _array_append(array_ptr, sizeof *(array_ptr)->data, items, item_count)
    
//Discards current items in the array and replaces them with the provided items
#define array_assign(array_ptr, items, item_count) \
    array_clear(array_ptr), \
    array_append(array_ptr, items, item_count)
    
//Copies from copy_from_array into copy_into_array_ptr overriding its elements. 
#define array_copy(copy_into_array_ptr, copy_from_array) \
    array_assign(copy_into_array_ptr, (copy_from_array).data, (copy_from_array).size)

//Appends a single item to the end of the array
#define array_push(array_ptr, item_value)            \
    _array_reserve(array_ptr, sizeof *(array_ptr)->data, (array_ptr)->size + 1), \
    (array_ptr)->data[(array_ptr)->size++] = item_value \

//Removes a single item from the end of the array. The array needs to not be empty!
#define array_pop(array_ptr) \
    (array_ptr)->data[--(array_ptr)->size]

//Implementation functions
void _array_set_capacity(void* array, isize item_size, isize capacity); 
isize _array_resize(void* array, isize item_size, isize to_size, bool zero_new);
void _array_reserve(void* array, isize item_size, isize to_capacity);
void _array_append(void* array, isize item_size, const void* data, isize data_count);
#endif

#if defined(JOT_ARRAY_IMPL) && !defined(JOT_ARRAY_HAS_IMPL)
#define JOT_ARRAY_HAS_IMPL

static void _array_check_invariants(const void* array, isize item_size)
{
    //This function checks if the array is in valid state. 
    // This provides a surprising ammount of test coverage while being very cheap.
    u8_Array* base = (u8_Array*) array; 
    (void) base;
    (void) item_size;

    assert(base != NULL && 0 < item_size);
    assert(0 <= base->capacity);
    assert(0 <= base->size && base->size <= base->capacity);
    assert((base->data == NULL) == (base->capacity == 0) && "data is NULL iff (if and only if) capacity is 0");
}

void _array_set_capacity(void* array, isize item_size, isize capacity)
{
    assert(capacity >= 0);
    u8_Array* base = (u8_Array*) array;
    _array_check_invariants(array, item_size);

    if(capacity == 0)
    {
        free(base->data);
        memset(base, 0, sizeof *base);
    }
    else
    {
        isize new_byte_size = item_size * capacity;
        uint8_t* new_data = (uint8_t*) realloc(base->data, new_byte_size);
        
        //If success set the new data and potentially size
        if(new_data != NULL)
        {
            base->data = new_data;
            base->capacity = capacity;
            if(base->size > capacity)
                base->size = capacity;
        }
    }

    _array_check_invariants(array, item_size);
}

isize _array_resize(void* array, isize item_size, isize to_size, bool zero_new)
{
    u8_Array* base = (u8_Array*) array;
    _array_reserve(base, item_size, to_size);
    isize size_before = base->size;
    if(zero_new && to_size > base->size)
        memset(base->data + base->size*item_size, 0, (size_t) ((to_size - base->size)*item_size));
        
    base->size = to_size;
    _array_check_invariants(array, item_size);
    return size_before;
}

void _array_reserve(void* array, isize item_size, isize to_fit)
{
    _array_check_invariants(array, item_size);
    assert(to_fit >= 0);
    u8_Array* base = (u8_Array*) array;
    if(base->capacity > to_fit)
        return;
        
    //Reasonable defaults. 
    //Does one growth step and selects max between
    //the size give and the grown size. 
    //This prevents quadratic reallocation time when calling
    // array_reserve(array, array->size + 3) repeatedly.
    isize new_capacity = to_fit;
    isize growth_step = base->capacity * 3/2 + 8;
    if(new_capacity < growth_step)
        new_capacity = growth_step;

    _array_set_capacity(array, item_size, new_capacity);
}

void _array_append(void* array, isize item_size, const void* data, isize data_count)
{
    assert(data_count >= 0 && item_size > 0);
    u8_Array* base = (u8_Array*) array;
    _array_reserve(base, item_size, base->size+data_count);

    //using memcpy since if we would be copying from the array it could crash anyway
    // (new array needs more size thus gets reallocated thus old ptr points to invalid memory)
    // thus memmove is not needed
    memcpy(base->data + item_size * base->size, data, (size_t) (item_size * data_count));
    base->size += data_count;
    _array_check_invariants(array, item_size);
}

#endif

#define RUN_EXAMPLE
#ifdef RUN_EXAMPLE

#include <stdio.h>
int main(void)
{
    typedef struct {
        int a;
        int b;
    } My_Struct;
    DEFINE_ARRAY_TYPE(My_Struct, My_Struct_Array);

    My_Struct_Array my_array = {0};
    My_Struct_Array my_array_copy = {0};
    array_reserve(&my_array, 5);

    for(int i = 0; i < 20; i++)
    {
        My_Struct s = {i, i+1};
        array_push(&my_array, s);
    }

    //for testing purposes (is not needed)
    array_copy(&my_array_copy, my_array);
    array_set_capacity(&my_array, 10); 

    printf("should print numbers 9 -> 0:\n");
    while(my_array.size > 0)
    {
        My_Struct s = array_pop(&my_array);
        printf("{%i, %i}\n", s.a, s.b);
    }
    
    printf("should print 5 times 0:\n");
    array_resize(&my_array, 5);
    for(int i = 0; i < my_array.size; i++)
    {
        printf("%i\n", my_array.data[i].a);
    }

    //for testing purposes (is not needed)
    array_set_capacity(&my_array, 20);

    array_deinit(&my_array);
    array_deinit(&my_array_copy);
}

#endif