dynamic_array.h

Go to the documentation of this file.

 
#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H
 
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
#ifndef DA_MALLOC
#define DA_MALLOC malloc
#endif
 
#ifndef DA_REALLOC
#define DA_REALLOC realloc
#endif
 
#ifndef DA_FREE
#define DA_FREE free
#endif
 
#ifndef DA_ASSERT
#define DA_ASSERT assert
#endif
 
#ifndef DA_DEF
    #ifdef DA_STATIC
        #define DA_DEF static
    #else
        #define DA_DEF extern
    #endif
#endif
 
#ifndef DA_ATOMIC_REFCOUNT
#define DA_ATOMIC_REFCOUNT 0
#endif
 
 
/* Check C11 support for atomic operations */
#if DA_ATOMIC_REFCOUNT && __STDC_VERSION__ < 201112L
    #error "DA_ATOMIC_REFCOUNT requires C11 or later for atomic support (compile with -std=c11 or later)"
#endif
 
/* atomic operations */
#if DA_ATOMIC_REFCOUNT
    #include <stdatomic.h>
    #define DA_ATOMIC_INT _Atomic int
    #define DA_ATOMIC_FETCH_ADD(ptr, val) atomic_fetch_add(ptr, val)
    #define DA_ATOMIC_FETCH_SUB(ptr, val) atomic_fetch_sub(ptr, val)
    #define DA_ATOMIC_LOAD(ptr) atomic_load(ptr)
    #define DA_ATOMIC_STORE(ptr, val) atomic_store(ptr, val)
#else
    #define DA_ATOMIC_INT int
    #define DA_ATOMIC_FETCH_ADD(ptr, val) (*(ptr) += (val), *(ptr) - (val))
    #define DA_ATOMIC_FETCH_SUB(ptr, val) (*(ptr) -= (val), *(ptr) + (val))
    #define DA_ATOMIC_LOAD(ptr) (*(ptr))
    #define DA_ATOMIC_STORE(ptr, val) (*(ptr) = (val))
#endif
 
/* Detect C23/C++11 auto support (preferred) or typeof fallback */
#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 202311L && !defined(__STDC_NO_TYPEOF__)
    #define DA_TYPEOF(x) typeof(x)     /* the C23 typeof keyword */
    #define DA_HAS_TYPEOF 1
#elif defined(__cplusplus) && __cplusplus >= 201103L
    #define DA_TYPEOF(x) decltype(x)   /* the C++ decltype keyword */
    #define DA_HAS_TYPEOF 1
#elif (defined(__GNUC__) && __GNUC__ >= 4) || defined(__clang__)
    #define DA_TYPEOF(x) typeof(x)
    #define DA_HAS_TYPEOF 1
#else
    #define DA_HAS_TYPEOF 0
#endif
 
#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 202311L
    #define DA_AUTO auto   /* the C23 auto keyword */
    #define DA_HAS_AUTO 1
#elif defined(__cplusplus) && __cplusplus >= 201103L
    #define DA_AUTO auto   /* the C++ auto keyword */
    #define DA_HAS_AUTO 1
#elif (defined(__GNUC__) && __GNUC__ >= 4) || defined(__clang__)
    #define DA_AUTO __auto_type
    #define DA_HAS_AUTO 1
#else
    #define DA_HAS_AUTO 0
#endif
 
#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
    #define DA_GENERIC(x, ...) _Generic((x), __VA_ARGS__)
    #define DA_HAS_GENERIC 1
#else
    #define DA_HAS_GENERIC 0
#endif
 
#if DA_HAS_AUTO
    #define DA_SUPPORT_TYPE_INFERENCE 1
    #define DA_MAKE_VAR_WITH_INFERRED_TYPE(name, initializer) DA_AUTO (name) = (initializer);
#elif DA_HAS_TYPEOF
    #define DA_SUPPORT_TYPE_INFERENCE 1
    #define DA_MAKE_VAR_WITH_INFERRED_TYPE(name, initializer) DA_TYPEOF(initializer) (name) = (initializer);
#else
    #define DA_SUPPORT_TYPE_INFERENCE 0
#endif
 
typedef struct {
    DA_ATOMIC_INT ref_count;  
    int length;               
    int capacity;             
    int element_size;         
    void *data;               
    void (*retain_fn)(void*); 
    void (*release_fn)(void*); 
} da_array_t, *da_array;
 
typedef struct {
    int length;               
    int capacity;             
    int element_size;         
    void *data;               
} da_builder_t, *da_builder;
 
 
DA_DEF da_array da_new(int element_size);
 
DA_DEF da_array da_create(int element_size, int initial_capacity, void (*retain_fn)(void*), void (*release_fn)(void*));
 
DA_DEF void da_release(da_array* arr);
 
DA_DEF da_array da_retain(da_array arr);
 
 
DA_DEF void* da_get(da_array arr, int index);
 
DA_DEF void* da_data(da_array arr);
 
DA_DEF void da_set(da_array arr, int index, const void* element);
 
 
DA_DEF void da_push(da_array arr, const void* element);
 
DA_DEF void da_insert(da_array arr, int index, const void* element);
 
DA_DEF void da_remove(da_array arr, int index, void* out);
 
DA_DEF void da_pop(da_array arr, void* out);
 
DA_DEF void da_clear(da_array arr);
 
DA_DEF void* da_peek(da_array arr);
 
DA_DEF void* da_peek_first(da_array arr);
 
 
DA_DEF int da_length(da_array arr);
 
DA_DEF int da_capacity(da_array arr);
 
DA_DEF void da_reserve(da_array arr, int new_capacity);
 
DA_DEF void da_resize(da_array arr, int new_length);
 
DA_DEF void da_trim(da_array arr, int new_capacity);
 
DA_DEF void da_append_array(da_array dest, da_array src);
 
DA_DEF da_array da_concat(da_array arr1, da_array arr2);
 
DA_DEF void da_append_raw(da_array arr, const void* data, int count);
 
DA_DEF void da_fill(da_array arr, const void* element, int count);
 
DA_DEF da_array da_slice(da_array arr, int start, int end);
 
DA_DEF da_array da_copy(da_array arr);
 
DA_DEF da_array da_filter(da_array arr, int (*predicate)(const void* element, void* context), void* context);
 
DA_DEF da_array da_map(da_array arr, void (*mapper)(const void* src, void* dst, void* context), void* context);
 
DA_DEF void da_reduce(da_array arr, const void* initial, void* result,
                      void (*reducer)(void* accumulator, const void* element, void* context), void* context);
 
DA_DEF void da_remove_range(da_array arr, int start, int count);
 
DA_DEF void da_reverse(da_array arr);
 
DA_DEF void da_swap(da_array arr, int i, int j);
 
DA_DEF int da_is_empty(da_array arr);
 
DA_DEF int da_find_index(da_array arr, int (*predicate)(const void* element, void* context), void* context);
 
DA_DEF int da_contains(da_array arr, int (*predicate)(const void* element, void* context), void* context);
 
DA_DEF void da_sort(da_array arr, int (*compare)(const void* a, const void* b, void* context), void* context);
 
 
DA_DEF da_builder da_builder_create(int element_size);
 
DA_DEF da_array da_builder_to_array(da_builder* builder, void (*retain_fn)(void*), void (*release_fn)(void*));
 
DA_DEF void da_builder_clear(da_builder builder);
 
DA_DEF void da_builder_destroy(da_builder* builder);
 
 
DA_DEF void da_builder_append(da_builder builder, const void* element);
 
DA_DEF void da_builder_reserve(da_builder builder, int new_capacity);
 
DA_DEF void da_builder_append_array(da_builder builder, da_array arr);
 
 
DA_DEF int da_builder_length(da_builder builder);
 
DA_DEF int da_builder_capacity(da_builder builder);
 
DA_DEF void* da_builder_get(da_builder builder, int index);
 
DA_DEF void da_builder_set(da_builder builder, int index, const void* element);
 
 
 
#define DA_NEW(T) da_new(sizeof(T))
#define DA_CREATE(T, cap, retain_fn, release_fn) da_create(sizeof(T), cap, retain_fn, release_fn)
 
#define DA_PUSH_TYPED(arr, val, T) do { T _temp = (val); da_push(arr, (void*)&_temp); } while(0)
#define DA_PUT_TYPED(arr, i, val, T) do { T _temp = (val); da_set(arr, i, (void*)&_temp); } while(0)
#define DA_INSERT_TYPED(arr, i, val, T) do { T _temp = (val); da_insert(arr, i, (void*)&_temp); } while(0)
 
#if DA_SUPPORT_TYPE_INFERENCE
    #define DA_PUSH_INFERRED(arr, val) do { DA_MAKE_VAR_WITH_INFERRED_TYPE(_temp, val); da_push(arr, (void*)&_temp); } while(0)
    #define DA_PUT_INFERRED(arr, i, val) do { DA_MAKE_VAR_WITH_INFERRED_TYPE(_temp, val); da_set(arr, i, (void*)&_temp); } while(0)
    #define DA_INSERT_INFERRED(arr, i, val) do { DA_MAKE_VAR_WITH_INFERRED_TYPE(_temp, val); da_insert(arr, i, (void*)&_temp); } while(0)
#endif
 
#if DA_SUPPORT_TYPE_INFERENCE && !defined(DA_NOT_USE_TYPE_GENERIC)
    #define DA_PUSH(arr, val) DA_PUSH_INFERRED(arr, val)
    #define DA_PUT(arr, i, val) DA_PUT_INFERRED(arr, i, val)
    #define DA_INSERT(arr, i, val) DA_INSERT_INFERRED(arr, i, val)
#else
    #define DA_PUSH(arr, val, T) DA_PUSH_TYPED(arr, val, T)
    #define DA_PUT(arr, i, val, T) DA_PUT_TYPED(arr, i, val, T)
    #define DA_INSERT(arr, i, val, T) DA_INSERT_TYPED(arr, i, val, T)
#endif
 
#define DA_LENGTH(arr) da_length(arr)
#define DA_CAPACITY(arr) da_capacity(arr)
#define DA_AT(arr, i, T) (*(T*)da_get(arr, i))
#define DA_POP(arr, out_ptr) da_pop(arr, out_ptr)
#define DA_REMOVE(arr, i, out_ptr) da_remove(arr, i, out_ptr)
#define DA_CLEAR(arr) da_clear(arr)
#define DA_RESERVE(arr, cap) da_reserve(arr, cap)
#define DA_RESIZE(arr, len) da_resize(arr, len)
#define DA_TRIM(arr, cap) da_trim(arr, cap)
#define DA_SHRINK_TO_FIT(arr) da_trim(arr, da_length(arr))
#define DA_PEEK(arr, T) (*(T*)da_peek(arr))
#define DA_PEEK_FIRST(arr, T) (*(T*)da_peek_first(arr))
 
#define DA_BUILDER_CREATE(T) da_builder_create(sizeof(T))
 
#define DA_BUILDER_APPEND_TYPED(builder, val, T) do { T _temp = (val); da_builder_append(builder, (void*)&_temp); } while(0)
#define DA_BUILDER_PUT_TYPED(builder, i, val, T) do { T _temp = (val); da_builder_set(builder, i, (void*)&_temp); } while(0)
 
#if DA_SUPPORT_TYPE_INFERENCE
    #define DA_BUILDER_APPEND_INFERRED(builder, val) \
        do { DA_MAKE_VAR_WITH_INFERRED_TYPE(_temp, val); da_builder_append(builder, (void*)&_temp); } while(0)
    #define DA_BUILDER_PUT_INFERRED(builder, i, val) \
        do { DA_MAKE_VAR_WITH_INFERRED_TYPE(_temp, val); da_builder_set(builder, i, (void*)&_temp); } while(0)
#endif
 
#if DA_SUPPORT_TYPE_INFERENCE && !defined(DA_NOT_USE_TYPE_GENERIC)
    #define DA_BUILDER_APPEND(builder, val) DA_BUILDER_APPEND_INFERRED(builder, val)
    #define DA_BUILDER_PUT(builder, i, val) DA_BUILDER_PUT_INFERRED(builder, i, val)
#else
    #define DA_BUILDER_APPEND(builder, val, T) DA_BUILDER_APPEND_TYPED(builder, val, T)
    #define DA_BUILDER_PUT(builder, i, val, T) DA_BUILDER_PUT_TYPED(builder, i, val, T)
#endif
 
 
#define DA_BUILDER_LEN(builder) da_builder_length(builder)
#define DA_BUILDER_CAP(builder) da_builder_capacity(builder)
#define DA_BUILDER_AT(builder, i, T) (*(T*)da_builder_get(builder, i))
#define DA_BUILDER_CLEAR(builder) da_builder_clear(builder)
#define DA_BUILDER_TO_ARRAY(builder) da_builder_to_array(builder, NULL, NULL)
#define DA_BUILDER_TO_ARRAY_MANAGED(builder, retain_fn, release_fn) da_builder_to_array(builder, retain_fn, release_fn)
 
/* Implementation */
#ifdef DA_IMPLEMENTATION
 
static int da_grow_capacity(int current_capacity, int min_needed) {
    int new_capacity = current_capacity;
 
#ifdef DA_GROWTH
    /* Fixed growth strategy */
    while (new_capacity < min_needed) {
        new_capacity += DA_GROWTH;
    }
#else
    /* Doubling strategy */
    if (new_capacity == 0) new_capacity = 1;
    while (new_capacity < min_needed) {
        new_capacity *= 2;
    }
#endif
 
    return new_capacity;
}
 
static int da_builder_grow_capacity(int current_capacity, int min_needed) {
    /* Builders always use doubling strategy for fast construction */
    int new_capacity = current_capacity;
    if (new_capacity == 0) new_capacity = 1;
    while (new_capacity < min_needed) {
        new_capacity *= 2;
    }
    return new_capacity;
}
 
/* Array Implementation */
 
DA_DEF da_array da_new(int element_size) {
    DA_ASSERT(element_size > 0);
 
    da_array arr = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(arr != NULL);
 
    DA_ATOMIC_STORE(&arr->ref_count, 1);
    arr->length = 0;
    arr->capacity = 0;  /* Deferred allocation */
    arr->element_size = element_size;
    arr->retain_fn = NULL;
    arr->release_fn = NULL;
    arr->data = NULL;
 
    return arr;
}
 
DA_DEF da_array da_create(int element_size, int initial_capacity, void (*retain_fn)(void*), void (*release_fn)(void*)) {
    DA_ASSERT(element_size > 0);
    DA_ASSERT(initial_capacity >= 0);
 
    da_array arr = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(arr != NULL);
 
    DA_ATOMIC_STORE(&arr->ref_count, 1);
    arr->length = 0;
    arr->capacity = initial_capacity;
    arr->element_size = element_size;
    arr->retain_fn = retain_fn;
    arr->release_fn = release_fn;
 
    if (initial_capacity > 0) {
        arr->data = DA_MALLOC(initial_capacity * element_size);
        DA_ASSERT(arr->data != NULL);
    } else {
        arr->data = NULL;
    }
 
    return arr;
}
 
DA_DEF void da_release(da_array* arr) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(*arr != NULL);
 
    int old_count = DA_ATOMIC_FETCH_SUB(&(*arr)->ref_count, 1);
 
    if (old_count == 1) {  /* We were the last reference */
        if ((*arr)->data && (*arr)->release_fn) {
            /* Call release function on each element before freeing */
            for (int i = 0; i < (*arr)->length; i++) {
                void* element_ptr = (char*)(*arr)->data + (i * (*arr)->element_size);
                (*arr)->release_fn(element_ptr);
            }
        }
        if ((*arr)->data) {
            DA_FREE((*arr)->data);
        }
        DA_FREE(*arr);
    }
 
    *arr = NULL;  /* Always NULL the pointer for safety */
}
 
DA_DEF da_array da_retain(da_array arr) {
    DA_ASSERT(arr != NULL);
    DA_ATOMIC_FETCH_ADD(&arr->ref_count, 1);
    return arr;
}
 
DA_DEF void* da_get(da_array arr, int index) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(index >= 0 && index < arr->length);
    return (char*)arr->data + (index * arr->element_size);
}
 
DA_DEF void* da_data(da_array arr) {
    DA_ASSERT(arr != NULL);
    return arr->data;
}
 
DA_DEF void da_set(da_array arr, int index, const void* element) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(element != NULL);
    DA_ASSERT(index >= 0 && index < arr->length);
 
    void* dest = (char*)arr->data + (index * arr->element_size);
    
    /* Call release function on the old element before overwriting */
    if (arr->release_fn) {
        arr->release_fn(dest);
    }
    
    memcpy(dest, element, arr->element_size);
    
    /* Call retain function on the newly set element */
    if (arr->retain_fn) {
        arr->retain_fn(dest);
    }
}
 
DA_DEF void da_push(da_array arr, const void* element) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(element != NULL);
 
    if (arr->length >= arr->capacity) {
        int new_capacity = da_grow_capacity(arr->capacity, arr->length + 1);
        arr->data = DA_REALLOC(arr->data, new_capacity * arr->element_size);
        DA_ASSERT(arr->data != NULL);
        arr->capacity = new_capacity;
    }
 
    void* dest = (char*)arr->data + (arr->length * arr->element_size);
    memcpy(dest, element, arr->element_size);
    
    /* Call retain function on the newly added element */
    if (arr->retain_fn) {
        arr->retain_fn(dest);
    }
    
    arr->length++;
}
 
DA_DEF void da_insert(da_array arr, int index, const void* element) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(element != NULL);
    DA_ASSERT(index >= 0 && index <= arr->length);
 
    /* Grow array if needed */
    if (arr->length >= arr->capacity) {
        int new_capacity = da_grow_capacity(arr->capacity, arr->length + 1);
        arr->data = DA_REALLOC(arr->data, new_capacity * arr->element_size);
        DA_ASSERT(arr->data != NULL);
        arr->capacity = new_capacity;
    }
 
    /* Shift elements to the right if not inserting at the end */
    if (index < arr->length) {
        void* src = (char*)arr->data + (index * arr->element_size);
        void* dest = (char*)arr->data + ((index + 1) * arr->element_size);
        int bytes_to_move = (arr->length - index) * arr->element_size;
        memmove(dest, src, bytes_to_move);
    }
 
    /* Insert the new element */
    void* insert_pos = (char*)arr->data + (index * arr->element_size);
    memcpy(insert_pos, element, arr->element_size);
    
    /* Call retain function on the newly inserted element */
    if (arr->retain_fn) {
        arr->retain_fn(insert_pos);
    }
    
    arr->length++;
}
 
DA_DEF void da_remove(da_array arr, int index, void* out) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(index >= 0 && index < arr->length);
 
    void* element_ptr = (char*)arr->data + (index * arr->element_size);
    
    /* Copy element to output if requested */
    if (out != NULL) {
        memcpy(out, element_ptr, arr->element_size);
    }
    
    /* Call destructor on the removed element */
    if (arr->release_fn) {
        arr->release_fn(element_ptr);
    }
 
    /* Shift elements to the left if not removing the last element */
    if (index < arr->length - 1) {
        void* dest = (char*)arr->data + (index * arr->element_size);
        void* src = (char*)arr->data + ((index + 1) * arr->element_size);
        int bytes_to_move = (arr->length - index - 1) * arr->element_size;
        memmove(dest, src, bytes_to_move);
    }
 
    arr->length--;
}
 
DA_DEF void da_pop(da_array arr, void* out) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(arr->length > 0);
 
    arr->length--;
 
    void* src = (char*)arr->data + (arr->length * arr->element_size);
    if (out != NULL) {
        memcpy(out, src, arr->element_size);
    }
    
    /* Call release function on the popped element */
    if (arr->release_fn) {
        arr->release_fn(src);
    }
}
 
DA_DEF void da_clear(da_array arr) {
    DA_ASSERT(arr != NULL);
    
    /* Call release function on all elements before clearing */
    if (arr->release_fn && arr->data) {
        for (int i = 0; i < arr->length; i++) {
            void* element_ptr = (char*)arr->data + (i * arr->element_size);
            arr->release_fn(element_ptr);
        }
    }
    
    arr->length = 0;
}
 
DA_DEF int da_length(da_array arr) {
    DA_ASSERT(arr != NULL);
    return arr->length;
}
 
DA_DEF int da_capacity(da_array arr) {
    DA_ASSERT(arr != NULL);
    return arr->capacity;
}
 
DA_DEF void da_reserve(da_array arr, int new_capacity) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(new_capacity >= 0);
 
    if (new_capacity > arr->capacity) {
        arr->data = DA_REALLOC(arr->data, new_capacity * arr->element_size);
        DA_ASSERT(arr->data != NULL);
        arr->capacity = new_capacity;
    }
}
 
DA_DEF void da_resize(da_array arr, int new_length) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(new_length >= 0);
 
    if (new_length > arr->capacity) {
        da_reserve(arr, new_length);
    }
 
    if (new_length < arr->length) {
        /* Call destructor on elements being removed */
        if (arr->release_fn && arr->data) {
            for (int i = new_length; i < arr->length; i++) {
                void* element_ptr = (char*)arr->data + (i * arr->element_size);
                arr->release_fn(element_ptr);
            }
        }
    } else if (new_length > arr->length) {
        /* Zero-fill new elements */
        void* start = (char*)arr->data + (arr->length * arr->element_size);
        int bytes_to_zero = (new_length - arr->length) * arr->element_size;
        memset(start, 0, bytes_to_zero);
    }
 
    arr->length = new_length;
}
 
DA_DEF void da_trim(da_array arr, int new_capacity) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(new_capacity >= arr->length);
 
    if (new_capacity < arr->capacity) {
        if (new_capacity == 0) {
            if (arr->data) {
                DA_FREE(arr->data);
                arr->data = NULL;
            }
        } else {
            arr->data = DA_REALLOC(arr->data, new_capacity * arr->element_size);
            DA_ASSERT(arr->data != NULL);
        }
        arr->capacity = new_capacity;
    }
}
 
DA_DEF void da_append_array(da_array dest, da_array src) {
    DA_ASSERT(dest != NULL);
    DA_ASSERT(src != NULL);
    DA_ASSERT(dest->element_size == src->element_size);
 
    if (src->length == 0) return;  /* Nothing to append */
 
    /* Ensure dest has enough capacity */
    int new_length = dest->length + src->length;
    if (new_length > dest->capacity) {
        int new_capacity = da_grow_capacity(dest->capacity, new_length);
        dest->data = DA_REALLOC(dest->data, new_capacity * dest->element_size);
        DA_ASSERT(dest->data != NULL);
        dest->capacity = new_capacity;
    }
 
    /* Copy all elements from src to end of dest */
    void* dest_ptr = (char*)dest->data + (dest->length * dest->element_size);
    memcpy(dest_ptr, src->data, src->length * src->element_size);
    
    /* Call retain function on all copied elements */
    if (dest->retain_fn) {
        for (int i = dest->length; i < new_length; i++) {
            void* element_ptr = (char*)dest->data + (i * dest->element_size);
            dest->retain_fn(element_ptr);
        }
    }
    
    dest->length = new_length;
}
 
DA_DEF da_array da_concat(da_array arr1, da_array arr2) {
    DA_ASSERT(arr1 != NULL);
    DA_ASSERT(arr2 != NULL);
    DA_ASSERT(arr1->element_size == arr2->element_size);
 
    int total_length = arr1->length + arr2->length;
 
    /* Create new array with exact capacity */
    da_array result = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(result != NULL);
 
    DA_ATOMIC_STORE(&result->ref_count, 1);
    result->length = total_length;
    result->capacity = total_length;  /* Exact capacity */
    result->element_size = arr1->element_size;
    result->retain_fn = arr1->retain_fn;   /* Inherit retain function from first array */
    result->release_fn = arr1->release_fn;  /* Inherit release function from first array */
 
    if (total_length > 0) {
        result->data = DA_MALLOC(total_length * result->element_size);
        DA_ASSERT(result->data != NULL);
 
        /* Copy arr1 elements first */
        if (arr1->length > 0) {
            memcpy(result->data, arr1->data, arr1->length * result->element_size);
        }
 
        /* Copy arr2 elements after arr1 */
        if (arr2->length > 0) {
            void* dest_ptr = (char*)result->data + (arr1->length * result->element_size);
            memcpy(dest_ptr, arr2->data, arr2->length * result->element_size);
        }
        
        /* Call retain function on all copied elements */
        if (result->retain_fn) {
            for (int i = 0; i < result->length; i++) {
                void* element_ptr = (char*)result->data + (i * result->element_size);
                result->retain_fn(element_ptr);
            }
        }
    } else {
        result->data = NULL;
    }
 
    return result;
}
 
/* Builder Implementation */
 
DA_DEF da_builder da_builder_create(int element_size) {
    DA_ASSERT(element_size > 0);
 
    da_builder builder = (da_builder)DA_MALLOC(sizeof(da_builder_t));
    DA_ASSERT(builder != NULL);
 
    builder->length = 0;
    builder->capacity = 0;
    builder->element_size = element_size;
    builder->data = NULL;
 
    return builder;
}
 
DA_DEF void da_builder_append(da_builder builder, const void* element) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(element != NULL);
 
    if (builder->length >= builder->capacity) {
        int new_capacity = da_builder_grow_capacity(builder->capacity, builder->length + 1);
        builder->data = DA_REALLOC(builder->data, new_capacity * builder->element_size);
        DA_ASSERT(builder->data != NULL);
        builder->capacity = new_capacity;
    }
 
    void* dest = (char*)builder->data + (builder->length * builder->element_size);
    memcpy(dest, element, builder->element_size);
    builder->length++;
}
 
DA_DEF void da_builder_reserve(da_builder builder, int new_capacity) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(new_capacity >= 0);
 
    if (new_capacity > builder->capacity) {
        builder->data = DA_REALLOC(builder->data, new_capacity * builder->element_size);
        DA_ASSERT(builder->data != NULL);
        builder->capacity = new_capacity;
    }
}
 
DA_DEF void da_builder_append_array(da_builder builder, da_array arr) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(arr != NULL);
    DA_ASSERT(builder->element_size == arr->element_size);
 
    if (arr->length == 0) return;  /* Nothing to append */
 
    /* Ensure enough capacity */
    int new_length = builder->length + arr->length;
    if (new_length > builder->capacity) {
        int new_capacity = da_builder_grow_capacity(builder->capacity, new_length);
        builder->data = DA_REALLOC(builder->data, new_capacity * builder->element_size);
        DA_ASSERT(builder->data != NULL);
        builder->capacity = new_capacity;
    }
 
    /* Copy all elements from array at once */
    void* dest_ptr = (char*)builder->data + (builder->length * builder->element_size);
    memcpy(dest_ptr, arr->data, arr->length * arr->element_size);
    builder->length = new_length;
}
 
DA_DEF da_array da_builder_to_array(da_builder* builder, void (*retain_fn)(void*), void (*release_fn)(void*)) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(*builder != NULL);
 
    da_builder b = *builder;
 
    /* Create new da_array */
    da_array arr = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(arr != NULL);
 
    DA_ATOMIC_STORE(&arr->ref_count, 1);
    arr->length = b->length;
    arr->capacity = b->length;  /* Exact capacity = length */
    arr->element_size = b->element_size;
    arr->retain_fn = retain_fn;
    arr->release_fn = release_fn;
 
    if (b->length > 0) {
        /* Shrink to exact size */
        arr->data = DA_REALLOC(b->data, b->length * b->element_size);
        DA_ASSERT(arr->data != NULL);
        
        /* Call retain function on all elements in the new array */
        if (arr->retain_fn) {
            for (int i = 0; i < arr->length; i++) {
                void* element_ptr = (char*)arr->data + (i * arr->element_size);
                arr->retain_fn(element_ptr);
            }
        }
    } else {
        arr->data = NULL;
        if (b->data) {
            DA_FREE(b->data);
        }
    }
 
    /* Free builder */
    DA_FREE(b);
    *builder = NULL;
 
    return arr;
}
 
DA_DEF void da_builder_clear(da_builder builder) {
    DA_ASSERT(builder != NULL);
    builder->length = 0;
}
 
DA_DEF void da_builder_destroy(da_builder* builder) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(*builder != NULL);
 
    if ((*builder)->data) {
        DA_FREE((*builder)->data);
    }
    DA_FREE(*builder);
    *builder = NULL;
}
 
DA_DEF int da_builder_length(da_builder builder) {
    DA_ASSERT(builder != NULL);
    return builder->length;
}
 
DA_DEF int da_builder_capacity(da_builder builder) {
    DA_ASSERT(builder != NULL);
    return builder->capacity;
}
 
DA_DEF void* da_builder_get(da_builder builder, int index) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(index >= 0 && index < builder->length);
    return (char*)builder->data + (index * builder->element_size);
}
 
DA_DEF void da_builder_set(da_builder builder, int index, const void* element) {
    DA_ASSERT(builder != NULL);
    DA_ASSERT(element != NULL);
    DA_ASSERT(index >= 0 && index < builder->length);
 
    void* dest = (char*)builder->data + (index * builder->element_size);
    memcpy(dest, element, builder->element_size);
}
 
/* Additional Array Functions Implementation */
 
DA_DEF void* da_peek(da_array arr) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(arr->length > 0);
    return (char*)arr->data + ((arr->length - 1) * arr->element_size);
}
 
DA_DEF void* da_peek_first(da_array arr) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(arr->length > 0);
    return arr->data;
}
 
DA_DEF void da_append_raw(da_array arr, const void* data, int count) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(data != NULL);
    DA_ASSERT(count >= 0);
 
    if (count == 0) return;  /* Nothing to append */
 
    /* Ensure enough capacity */
    int new_length = arr->length + count;
    if (new_length > arr->capacity) {
        int new_capacity = da_grow_capacity(arr->capacity, new_length);
        arr->data = DA_REALLOC(arr->data, new_capacity * arr->element_size);
        DA_ASSERT(arr->data != NULL);
        arr->capacity = new_capacity;
    }
 
    /* Copy all elements at once */
    void* dest_ptr = (char*)arr->data + (arr->length * arr->element_size);
    memcpy(dest_ptr, data, count * arr->element_size);
    
    /* Call retain function on all copied elements */
    if (arr->retain_fn) {
        for (int i = arr->length; i < new_length; i++) {
            void* element_ptr = (char*)arr->data + (i * arr->element_size);
            arr->retain_fn(element_ptr);
        }
    }
    
    arr->length = new_length;
}
 
DA_DEF void da_fill(da_array arr, const void* element, int count) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(element != NULL);
    DA_ASSERT(count >= 0);
 
    if (count == 0) return;  /* Nothing to fill */
 
    /* Ensure enough capacity */
    int new_length = arr->length + count;
    if (new_length > arr->capacity) {
        int new_capacity = da_grow_capacity(arr->capacity, new_length);
        arr->data = DA_REALLOC(arr->data, new_capacity * arr->element_size);
        DA_ASSERT(arr->data != NULL);
        arr->capacity = new_capacity;
    }
 
    /* Fill elements one by one */
    for (int i = 0; i < count; i++) {
        void* dest_ptr = (char*)arr->data + ((arr->length + i) * arr->element_size);
        memcpy(dest_ptr, element, arr->element_size);
    }
    arr->length = new_length;
}
 
DA_DEF da_array da_slice(da_array arr, int start, int end) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(start >= 0 && start <= arr->length);
    DA_ASSERT(end >= start && end <= arr->length);
 
    int slice_length = end - start;
 
    /* Create new array with exact capacity */
    da_array result = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(result != NULL);
 
    DA_ATOMIC_STORE(&result->ref_count, 1);
    result->length = slice_length;
    result->capacity = slice_length;  /* Exact capacity */
    result->element_size = arr->element_size;
    result->retain_fn = arr->retain_fn;   /* Inherit retain function */
    result->release_fn = arr->release_fn;  /* Inherit release function */
 
    if (slice_length > 0) {
        result->data = DA_MALLOC(slice_length * result->element_size);
        DA_ASSERT(result->data != NULL);
 
        /* Copy slice elements */
        void* src_ptr = (char*)arr->data + (start * arr->element_size);
        memcpy(result->data, src_ptr, slice_length * arr->element_size);
        
        /* Call retain function on all copied elements */
        if (result->retain_fn) {
            for (int i = 0; i < result->length; i++) {
                void* element_ptr = (char*)result->data + (i * result->element_size);
                result->retain_fn(element_ptr);
            }
        }
    } else {
        result->data = NULL;
    }
 
    return result;
}
 
DA_DEF void da_remove_range(da_array arr, int start, int count) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(start >= 0 && start < arr->length);
    DA_ASSERT(count >= 0);
    DA_ASSERT(start + count <= arr->length);
 
    if (count == 0) return;  /* Nothing to remove */
 
    int end = start + count;
 
    /* Call destructor on elements being removed */
    if (arr->release_fn) {
        for (int i = start; i < end; i++) {
            void* element_ptr = (char*)arr->data + (i * arr->element_size);
            arr->release_fn(element_ptr);
        }
    }
 
    /* Shift elements after the range to the left */
    if (end < arr->length) {
        void* dest = (char*)arr->data + (start * arr->element_size);
        void* src = (char*)arr->data + (end * arr->element_size);
        int bytes_to_move = (arr->length - end) * arr->element_size;
        memmove(dest, src, bytes_to_move);
    }
 
    arr->length -= count;
}
 
DA_DEF void da_reverse(da_array arr) {
    DA_ASSERT(arr != NULL);
 
    if (arr->length <= 1) return;  /* Nothing to reverse */
 
    char* temp = (char*)DA_MALLOC(arr->element_size);
    DA_ASSERT(temp != NULL);
 
    /* Swap elements from both ends moving toward center */
    for (int i = 0; i < arr->length / 2; i++) {
        int j = arr->length - 1 - i;
 
        char* left = (char*)arr->data + (i * arr->element_size);
        char* right = (char*)arr->data + (j * arr->element_size);
 
        /* Three-way swap using temp buffer */
        memcpy(temp, left, arr->element_size);
        memcpy(left, right, arr->element_size);
        memcpy(right, temp, arr->element_size);
    }
 
    DA_FREE(temp);
}
 
DA_DEF void da_swap(da_array arr, int i, int j) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(i >= 0 && i < arr->length);
    DA_ASSERT(j >= 0 && j < arr->length);
 
    if (i == j) return;  /* No-op if same index */
 
    char* temp = (char*)DA_MALLOC(arr->element_size);
    DA_ASSERT(temp != NULL);
 
    char* elem_i = (char*)arr->data + (i * arr->element_size);
    char* elem_j = (char*)arr->data + (j * arr->element_size);
 
    /* Three-way swap */
    memcpy(temp, elem_i, arr->element_size);
    memcpy(elem_i, elem_j, arr->element_size);
    memcpy(elem_j, temp, arr->element_size);
 
    DA_FREE(temp);
}
 
DA_DEF da_array da_copy(da_array arr) {
    DA_ASSERT(arr != NULL);
 
    /* Create new array with exact capacity = length */
    da_array result = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(result != NULL);
 
    DA_ATOMIC_STORE(&result->ref_count, 1);
    result->length = arr->length;
    result->capacity = arr->length;  /* Exact capacity for efficiency */
    result->element_size = arr->element_size;
    result->retain_fn = arr->retain_fn;   /* Inherit retain function */
    result->release_fn = arr->release_fn;  /* Inherit release function */
 
    if (arr->length > 0) {
        result->data = DA_MALLOC(arr->length * arr->element_size);
        DA_ASSERT(result->data != NULL);
 
        /* Copy all elements */
        memcpy(result->data, arr->data, arr->length * arr->element_size);
        
        /* Call retain function on all copied elements */
        if (result->retain_fn) {
            for (int i = 0; i < result->length; i++) {
                void* element_ptr = (char*)result->data + (i * result->element_size);
                result->retain_fn(element_ptr);
            }
        }
    } else {
        result->data = NULL;
    }
 
    return result;
}
 
DA_DEF da_array da_filter(da_array arr, int (*predicate)(const void* element, void* context), void* context) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(predicate != NULL);
 
    /* Use builder for single-pass filtering */
    da_builder builder = da_builder_create(arr->element_size);
 
    /* Single pass: test and append matching elements */
    for (int i = 0; i < arr->length; i++) {
        void* element_ptr = (char*)arr->data + (i * arr->element_size);
        if (predicate(element_ptr, context)) {
            da_builder_append(builder, element_ptr);
        }
    }
 
    /* Convert builder to array with exact capacity, inherit destructor */
    da_array result = da_builder_to_array(&builder, arr->retain_fn, arr->release_fn);
    return result;
}
 
DA_DEF da_array da_map(da_array arr, void (*mapper)(const void* src, void* dst, void* context), void* context) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(mapper != NULL);
 
    /* Create new array with same length and exact capacity */
    da_array result = (da_array)DA_MALLOC(sizeof(da_array_t));
    DA_ASSERT(result != NULL);
 
    DA_ATOMIC_STORE(&result->ref_count, 1);
    result->length = arr->length;
    result->capacity = arr->length;  /* Exact capacity for efficiency */
    result->element_size = arr->element_size;
    result->retain_fn = arr->retain_fn;   /* Inherit retain function */
    result->release_fn = arr->release_fn;  /* Inherit release function */
 
    if (arr->length > 0) {
        result->data = DA_MALLOC(arr->length * arr->element_size);
        DA_ASSERT(result->data != NULL);
 
        /* Transform each element */
        for (int i = 0; i < arr->length; i++) {
            void* src_ptr = (char*)arr->data + (i * arr->element_size);
            void* dst_ptr = (char*)result->data + (i * arr->element_size);
            mapper(src_ptr, dst_ptr, context);
        }
    } else {
        result->data = NULL;
    }
 
    return result;
}
 
DA_DEF void da_reduce(da_array arr, const void* initial, void* result,
                      void (*reducer)(void* accumulator, const void* element, void* context), void* context) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(initial != NULL);
    DA_ASSERT(result != NULL);
    DA_ASSERT(reducer != NULL);
 
    /* Initialize result with initial value */
    memcpy(result, initial, arr->element_size);
 
    /* Apply reducer to each element */
    for (int i = 0; i < arr->length; i++) {
        void* element_ptr = (char*)arr->data + (i * arr->element_size);
        reducer(result, element_ptr, context);
    }
}
 
DA_DEF int da_is_empty(da_array arr) {
    DA_ASSERT(arr != NULL);
    return arr->length == 0;
}
 
DA_DEF int da_find_index(da_array arr, int (*predicate)(const void* element, void* context), void* context) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(predicate != NULL);
    
    for (int i = 0; i < arr->length; i++) {
        void* element_ptr = (char*)arr->data + (i * arr->element_size);
        if (predicate(element_ptr, context)) {
            return i;
        }
    }
    
    return -1;  // Not found
}
 
DA_DEF int da_contains(da_array arr, int (*predicate)(const void* element, void* context), void* context) {
    return da_find_index(arr, predicate, context) != -1;
}
 
// Helper structure for qsort context
struct da_sort_context {
    int (*compare)(const void* a, const void* b, void* context);
    void* user_context;
};
 
// Global context for qsort (not thread-safe, but qsort isn't either)
static struct da_sort_context* da_sort_global_context = NULL;
 
// qsort comparison wrapper
static int da_sort_compare_wrapper(const void* a, const void* b) {
    struct da_sort_context* ctx = (struct da_sort_context*)da_sort_global_context;
    return ctx->compare(a, b, ctx->user_context);
}
 
DA_DEF void da_sort(da_array arr, int (*compare)(const void* a, const void* b, void* context), void* context) {
    DA_ASSERT(arr != NULL);
    DA_ASSERT(compare != NULL);
    
    if (arr->length <= 1) {
        return;  // Already sorted or empty
    }
    
    // Set up global context for qsort wrapper
    struct da_sort_context sort_ctx = { compare, context };
    da_sort_global_context = &sort_ctx;
    
    // Use standard library qsort
    qsort(arr->data, arr->length, arr->element_size, da_sort_compare_wrapper);
    
    // Clean up global context
    da_sort_global_context = NULL;
}
 
#endif /* DA_IMPLEMENTATION */
 
#endif /* DYNAMIC_ARRAY_H */