dynamic_array.h

 

A high-performance, (optionally atomic) reference-counted dynamic array library for C with support for element retain/release functions. Designed for maximum portability across PC and microcontroller targets, with special support for language interpreters and reference-counted object systems.

Features

High Performance

• Lock-free atomic reference counting
• Configurable growth strategies (fixed increment or doubling)
• Zero-copy data access with direct pointer operations

Memory Safe

• Reference counting prevents memory leaks and use-after-free
• Element retain/release functions for complex object lifecycle management
• Perfect for language interpreters with garbage-collected objects
• Automatic cleanup when last reference is released
• Pointers always NULLed after release for safety

Developer Friendly

• Type-safe macros with typeof support
• JavaScript-like array semantics
• Comprehensive assert-based error checking
• Single header-only library

Cross-Platform

• Works on Linux, Windows, macOS
• Microcontroller support: Raspberry Pi Pico, ESP32-C3, ARM Cortex-M
• Both GCC and Clang compatible
• Graceful fallback for compilers without typeof

Atomic reference counting

• Optional atomic reference counting (C11 required)
• Lock-free performance on multi-core systems
• Safe sharing between threads without mutexes

Functional Programming

• Filter, map, and reduce operations with exact capacity allocation
• Single-pass optimizations for memory efficiency
• Perfect for data processing pipelines

Builder Pattern

• Efficient construction with pre-allocation
• Bulk append operations for performance
• Zero-waste capacity management

What's New

v0.3.0 (Latest) - Element Retain/Release System

BREAKING CHANGES - Major API update for language interpreter support

New Element Memory Management

• Added retain/release function pointers to array structure for complex object lifecycle management
• da_create() now takes retain_fn and release_fn parameters: da_create(element_size, capacity, retain_fn, release_fn)
• New da_new() function for simple arrays without retain/release: da_new(element_size)
• All element copying operations (copy, concat, slice, append) now call retain_fn on copied elements
• Perfect for language interpreters with reference-counted objects (like Metal interpreter's cell_t)

Updated API

• DA_NEW(T) macro for simple array creation without retain/release functions
• DA_CREATE(T, cap, retain_fn, release_fn) macro for full-featured arrays
• da_builder_to_array() now takes retain_fn and release_fn parameters
• Enhanced documentation with interpreter integration examples

Comprehensive Testing

• All 129+ tests updated and passing
• Added extensive destructor tests for complex object scenarios
• Fixed double-free issues and memory leak scenarios
• Validated retain/release functionality across all operations

v0.1.1

Type Inference Support (Thanks to @Maqi-x via PR #1)

• Added automatic type inference for C23, C++11, and GCC/Clang
• Macros like DA_PUSH now work without explicit type parameter when compiler supports it
• Backward compatible - older compilers still work with explicit types
• Improved developer ergonomics with modern C/C++ standards

API Improvements

• Renamed DA_LEN/DA_CAP to DA_LENGTH/DA_CAPACITY for clarity
• Similarly renamed builder macros for consistency
• Enhanced documentation with comprehensive examples

v0.1.0

Functional Programming Complete

• Added da_reduce() function with accumulator pattern for array reduction
• Completes the functional programming trinity: filter → map → reduce
• User-controlled memory management with result buffers

Builder Pattern Enhancements

• New da_builder_reserve() for efficient pre-allocation
• New da_builder_append_array() for bulk array operations
• Optimized construction patterns for high-performance scenarios

Performance Optimizations

• Optimized da_filter() to use builder pattern internally (single-pass filtering)
• Improved memory efficiency across all operations
• Exact capacity allocation throughout the API

Comprehensive Testing

• Expanded test suite to 110+ tests (from 20+)
• Complete coverage of all new functions and edge cases
• Enhanced reliability and stability validation

v0.0.1 (Initial Release)

• Core dynamic array functionality with reference counting
• Atomic ref counting
• Type-safe macros and cross-platform compatibility
• Basic builder pattern implementation
• Initial filter and map operations

Quick Start

#define DA_IMPLEMENTATION
#include "dynamic_array.h"
 
int main() {
    // Simple arrays (no retain/release functions needed)
    da_array arr = DA_NEW(int);
    
    // Add elements
    DA_PUSH(arr, 42);
    DA_PUSH(arr, 99);
    
    // Access elements
    int value = DA_AT(arr, 0, int);  // 42
    
    // Direct pointer access (like stb_ds.h)
    int* data = (int*)da_data(arr);
    data[1] = 100;
    
    // Reference counting
    da_array shared = da_retain(arr);
    
    // Functional programming - filter, map, reduce
    da_array evens = da_filter(arr, is_even_predicate, NULL);
    da_array doubled = da_map(evens, double_mapper, NULL);
    
    int sum = 0, total;
    da_reduce(doubled, &sum, &total, sum_reducer, NULL);
    
    // Builder pattern for efficient construction
    da_builder builder = DA_BUILDER_CREATE(int);
    da_builder_reserve(builder, 1000);  // Pre-allocate
    da_builder_append_array(builder, existing_data);
    da_array result = DA_BUILDER_TO_ARRAY(builder);  // Simple version
    
    // Cleanup (decrements ref count, frees when count reaches 0)
    da_release(&arr);
    da_release(&shared);
    da_release(&evens);
    da_release(&doubled);
    da_release(&result);
    
    return 0;
}

Advanced: Arrays with Element Retain/Release Functions

For complex objects that need custom memory management (like reference-counted interpreter values):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct {
    int id;
    char* name;  // Dynamically allocated
} Person;
 
// Retain function - called when elements are copied
void person_retain(void* p) {
    Person* person = (Person*)p;
    if (person->name) {
        // Duplicate the string
        size_t len = strlen(person->name);
        char* new_name = malloc(len + 1);
        strcpy(new_name, person->name);
        person->name = new_name;
    }
}
 
// Release function - called when elements are removed
void person_release(void* p) {
    Person* person = (Person*)p;
    if (person->name) {
        free(person->name);
        person->name = NULL;
    }
}
 
int main() {
    // Create array with retain/release functions
    da_array people = DA_CREATE(Person, 10, person_retain, person_release);
    
    // Add a person with dynamic memory
    Person alice = {1, malloc(16)};
    strcpy(alice.name, "Alice");
    DA_PUSH(people, alice);
    
    // When copying, retain_fn duplicates the name string
    da_array people_copy = da_copy(people);
    
    // Each array now owns its own copy of the name string
    // No double-free issues when both arrays are released
    
    da_release(&people);      // Calls person_release on elements
    da_release(&people_copy); // Calls person_release on copy elements
    
    return 0;
}

Language Interpreter Integration

Perfect for language interpreters with reference-counted objects:

// Example: Metal interpreter cell_t integration
extern void cell_retain(void* cell_ptr);   // From metal/src/cell.c
extern void cell_release(void* cell_ptr);  // From metal/src/cell.c
 
typedef struct cell cell_t;  // Forward declaration
 
// Create array for interpreter values
da_array code_array = DA_CREATE(cell_t, 100, cell_retain, cell_release);
 
// Push interpreter values - they're automatically retained
cell_t value = new_int32(42);
DA_PUSH(code_array, value);
 
// Copy operations work correctly with reference counting
da_array code_copy = da_copy(code_array);  // All cells properly retained
 
// Cleanup releases all cell references
da_release(&code_array);  // All cells properly released
da_release(&code_copy);   // Copy cells properly released

Configuration

Configure the library before including:

// Custom allocators
#define DA_MALLOC my_malloc
#define DA_REALLOC my_realloc  
#define DA_FREE my_free
 
// Custom assert
#define DA_ASSERT my_assert
 
// Growth strategy
#define DA_GROWTH 16        // Fixed growth of 16 elements
// #define DA_GROWTH undefined  // Use doubling strategy (default)
 
// Atomic reference counting (requires C11)
#define DA_ATOMIC_REFCOUNT 1
 
#define DA_IMPLEMENTATION
#include "dynamic_array.h"

API Reference

Creation and Reference Counting

// Simple arrays (no retain/release functions)
da_array da_new(int element_size);
#define DA_NEW(T)  da_new(sizeof(T))
 
// Arrays with element retain/release functions  
da_array da_create(int element_size, int initial_capacity, 
                   void (*retain_fn)(void*), void (*release_fn)(void*));
#define DA_CREATE(T, cap, retain_fn, release_fn)  \
    da_create(sizeof(T), cap, retain_fn, release_fn)
 
// Reference counting
da_array da_retain(da_array arr);      // Increment reference count
void da_release(da_array* arr);        // Decrement ref count, NULL pointer

Type-Safe Macros

// With typeof support (GCC/Clang)
#define DA_CREATE(T, cap)           // Create typed array
#define DA_PUSH(arr, val)           // Push value
#define DA_PUT(arr, i, val)         // Set element at index
 
// Without typeof support (strict ISO C)
#define DA_PUSH(arr, val, T)        // Push value with type
#define DA_PUT(arr, i, val, T)      // Set element with type
 
// Universal macros
#define DA_AT(arr, i, T)            // Get element at index
#define DA_LENGTH(arr)                 // Get length
#define DA_CAPACITY(arr)                 // Get capacity
#define DA_POP(arr, out_ptr)        // Pop last element
#define DA_CLEAR(arr)               // Clear all elements
#define DA_RESERVE(arr, cap)        // Reserve capacity
#define DA_RESIZE(arr, len)         // Resize array

Raw Functions

void* da_get(da_array arr, int index);           // Get element pointer
void* da_data(da_array arr);                     // Get raw data pointer
void da_set(da_array arr, int index, const void* element);
void da_push(da_array arr, const void* element);
void da_pop(da_array arr, void* out);            // out can be NULL
int da_length(da_array arr);
int da_capacity(da_array arr);
void da_clear(da_array arr);
void da_reserve(da_array arr, int new_capacity);
void da_resize(da_array arr, int new_length);

Lock-free Reference Counting

Enable atomic reference counting:

#define DA_ATOMIC_REFCOUNT 1
#define DA_IMPLEMENTATION
#include "dynamic_array.h"

• da_retain() - Atomic reference increment
• da_release() - Atomic reference decrement
• Memory cleanup - Only one thread frees when ref count hits 0

Requires External Synchronization:

• Array modifications (DA_PUSH, DA_POP, da_set)
• Concurrent access to array contents

Perfect for sharing immutable or read-mostly data between threads!

Growth Strategies

Fixed Growth (recommended for microcontrollers):

#define DA_GROWTH 16  // Grow by 16 elements each time

Doubling Growth (default, good for desktop):

// Don't define DA_GROWTH - uses doubling strategy

Error Handling

The library uses assertions for error detection. All errors fail fast:

• Out-of-bounds access → Assert failure
• Memory allocation failure → Assert failure
• Invalid parameters → Assert failure

This is perfect for embedded systems where you want to catch bugs early rather than handle them gracefully.

Platform Support

Tested Platforms:

• Linux (GCC, Clang)
• Windows (MinGW, MSVC)
• Raspberry Pi Pico (arm-none-eabi-gcc)
• Raspberry Pi Zero/4 (GCC)
• ESP32-C3 (Espressif toolchain)

Requirements:

• C11 for atomic reference count operations
• <stdlib.h>, <string.h>, <assert.h>
• <stdatomic.h> (only if DA_ATOMIC_REFCOUNT=1)

Building and Testing

The library includes a comprehensive Unity-based test suite:

# Clone with Unity framework
git clone <your-repo>
cd dynamic_array.h
 
# Add Unity framework to unity/ directory
# Then build and test:
mkdir build && cd build
cmake ..
make
./test_runner

Builder Pattern

// Create builder
da_builder da_builder_create(int element_size);
#define DA_BUILDER_CREATE(T)  da_builder_create(sizeof(T))
 
// Add elements to builder
void da_builder_append(da_builder builder, const void* element);
#define DA_BUILDER_APPEND(builder, val)  da_builder_append(builder, &(val))
 
// Convert to array
da_array da_builder_to_array(da_builder* builder, 
                              void (*retain_fn)(void*), void (*release_fn)(void*));
 
// Convenience macros
#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)

All 129+ tests should pass, covering:

• Creation and destruction (both simple and retain/release arrays)
• Reference counting behavior
  
• Element retain/release function integration
• Double-free prevention and memory leak detection
• Growth strategies and builder patterns
• Type-safe macros
• Functional programming operations
• Edge cases and stress tests
• Atomic reference count validation

Use Cases

Perfect for:

• Interpreters and virtual machines
• Game engines (entity lists, render queues)
• Embedded systems with dynamic data
• Multi-threaded applications sharing read-only data
• Data processing pipelines (ETL operations)
• Scientific computing with functional patterns
• Any C project needing JavaScript-like arrays

Example - Shared Bytecode in Interpreter:

// Main thread creates bytecode
da_array bytecode = DA_CREATE(instruction_t, 1000);
compile_to_bytecode(source, bytecode);
 
// Share with worker threads (lock-free!)
spawn_worker(da_retain(bytecode));
spawn_worker(da_retain(bytecode));
 
// Main thread releases its reference
da_release(&bytecode);
// Memory freed when last worker finishes

Example - Data Processing Pipeline:

// Functional data processing with exact memory allocation
da_array sensor_data = load_sensor_readings();
da_array valid = da_filter(sensor_data, is_valid_reading, &threshold);
da_array scaled = da_map(valid, normalize_value, &scale_params);
 
// Reduce to statistical summary
float stats = {0};
da_reduce(scaled, &stats, &summary, calculate_stats, NULL);
 
// Efficient bulk construction
da_builder results = DA_BUILDER_CREATE(result_t);
da_builder_reserve(results, expected_count);
da_builder_append_array(results, processed_batch_1);
da_builder_append_array(results, processed_batch_2);
da_array final = da_builder_to_array(&results);  // Exact capacity

Version History

v0.3.0 (Current) - Element Retain/Release System

BREAKING CHANGES - Major API update for language interpreter support

• API: da_create() now takes 4 parameters: da_create(element_size, capacity, retain_fn, release_fn)
• NEW: da_new() function for simple arrays without retain/release functions
• NEW: DA_NEW(T) macro for convenient simple array creation
• Enhanced: All element copying operations call retain_fn on copied elements
• Enhanced: da_builder_to_array() now accepts retain_fn and release_fn parameters
• Fixed: Double-free issues and memory leaks in complex object scenarios
• Testing: All 129+ tests updated and passing with comprehensive retain/release coverage

v0.2.0

• Added: da_find_index() - find first element matching predicate function
• Added: da_contains() - boolean check for element existence using predicates
• Added: da_sort() - sort array with custom comparison function and context
• Improved: All array construction operations use da_builder internally for efficiency
• Documentation: Enhanced Doxygen comments with detailed usage examples for new functions

v0.1.0

• Foundation: Complete single-header dynamic array library
• Features: Reference counting, atomic operations, type-safe macros, builder pattern
• Features: Functional operations (filter, map, reduce)
• Features: Advanced manipulation (slice, concat, reverse, swap)
• Platform Support: C99+, optional C11 atomic operations, microcontroller support
• Documentation: Comprehensive Doxygen documentation with examples

License

This project is dual-licensed under your choice of:

• [MIT License](LICENSE-MIT)
• [The Unlicense](LICENSE-UNLICENSE)

Choose whichever license works best for your project!

Contributing

Contributions welcome! Please ensure:

• All tests pass (make test)
• Code follows existing style
• New features include tests
• Maintain compatibility across target platforms

---

Built for performance, designed for portability, crafted for developers. 🚀