Singly Linked List

c_list.h provides a generic, type-erased singly linked list built on top of the csalt allocator and dtype systems. It is designed for flexibility, allocator control, and predictable performance, while remaining fully agnostic to the stored data type.

This module does not provide primitive typed wrappers. Instead, it is intended to serve as a foundation for user-defined data structures, where the caller defines the stored type via dtype_id_t and builds thin wrappers around the generic API.

Overview

The list stores values as raw byte buffers of fixed size determined at initialisation. Each node embeds its value inline, avoiding additional pointer indirection and improving cache locality during traversal.

A hybrid allocation model is used:

• A contiguous slab of nodes is pre-allocated at initialisation

• Additional nodes may optionally be allocated individually if overflow is enabled

All memory management is performed through a caller-supplied allocator_vtable_t. No assumptions are made about the backing allocator (arena, pool, heap, etc.).

#include "c_list.h"

allocator_vtable_t alloc = heap_allocator();

slist_expect_t r = init_slist(64, sizeof(int32_t),
                             INT32_TYPE, true, alloc);
if (!r.has_value) { /* handle r.u.error */ }

slist_t* list = r.u.value;

int32_t v = 10;
push_back_slist(list, &v);

int32_t out = 0;
get_slist(list, 0, &out);   /* out == 10 */

return_slist(list);

Note

The generic API performs no implicit type conversions. The caller is responsible for ensuring that all inserted values match the declared data_size and dtype.

Memory Model

Each node stores its value inline:

struct sNode {
    struct sNode* next;
    uint8_t       data[];
};

This layout provides:

• Single allocation per node

• Improved spatial locality for slab-allocated nodes

• No double indirection for value access

The list uses two allocation strategies:

1. Slab allocation (primary) - Nodes are carved from a contiguous block - Improves cache performance

2. Overflow allocation (optional) - Enabled via allow_overflow = true - Falls back to allocator when slab is exhausted

Ownership Rules

• The list owns: - its header - its slab allocation - any overflow nodes

• All memory is released via return_slist()

• Individual nodes must never be freed by the caller

Allocator Integration

All allocations are performed through allocator_vtable_t.

This allows the list to be backed by:

• heap allocators

• arena allocators

• pool allocators

• custom user-defined allocators

The list does not assume ownership semantics beyond what is defined by the allocator implementation.

See C Allocator Overview for details.

Recommended Allocators

Different allocators are appropriate depending on how the list is used:

• HeapAllocator

  Best for:

  • general-purpose use

  • unit testing

  • host-side applications

  • debugging container logic independent of allocator complexity

  This is usually the best allocator to use first because failure modes are simple and easy to reason about.

• ArenaAllocator

  Best for:

  • build-then-discard workflows

  • temporary lists used during parsing or transformation passes

  • scenarios where the full list lifetime matches a larger arena lifetime

  This works especially well when overflow is disabled or rare. If overflow is frequent, the arena must still have enough capacity to satisfy those extra node allocations.

• BuddyAllocator

  Best for:

  • deterministic dynamic allocation

  • environments where memory should be returnable and coalesced

  • systems requiring more structure than a heap allocator

  This is a reasonable choice when the list may grow dynamically and later release memory through normal destruction.

• PoolAllocator / SlabAllocator

  Best for:

  • overflow-heavy workloads with uniform node sizes

  • fixed-type deployments where the node footprint is stable

  • performance-sensitive paths with many push/pop operations

  These allocators can be particularly effective because list nodes are fixed-size objects for a given T. They are less useful when only the primary slab is used and overflow is disabled.

Error Handling

The list follows the csalt expected value pattern:

• Constructors return slist_expect_t

• Mutating operations return error_code_t

Callers must always check return values before use.

slist_expect_t r = init_slist(...);
if (!r.has_value) {
    error_code_t err = r.u.error;
    /* handle error */
}

Type System and User-Defined Types

The list relies on dtype_id_t to describe stored data.

Built-in types are defined in c_dtypes.h:

• INT32_TYPE

• FLOAT_TYPE

• STRING_TYPE

• etc.

For user-defined types, define a unique type ID and register it with the dtype registry.

typedef struct {
    float x, y, z;
} vec3_t;

/* Define a unique dtype ID */
#define VEC3_TYPE (USER_BASE_TYPE + 1u)

static const dtype_t vec3_desc = {
    VEC3_TYPE,
    sizeof(vec3_t),
    "vec3"
};

ensure_dtype_registered(&vec3_desc);

slist_expect_t r = init_slist(32, sizeof(vec3_t),
                             VEC3_TYPE, false, alloc);

Note

User-defined dtype IDs must be >= USER_BASE_TYPE and must be unique within the application. It is recommended to define them as named macros rather than using raw numeric values.

Typed Wrapper Pattern (Recommended)

Because the generic API operates on void* buffers, it is recommended to define thin wrappers for your specific data types.

Example wrapper for vec3_t:

static inline error_code_t push_back_vec3(slist_t* list,
                                          const vec3_t* v) {
    return push_back_slist(list, v);
}

static inline error_code_t get_vec3(const slist_t* list,
                                    size_t index,
                                    vec3_t* out) {
    return get_slist(list, index, out);
}

This provides:

• Type safety at the call site

• Cleaner API usage

• No runtime overhead

Core API

Structs

struct slist_t

A singly-linked list backed by a pre-allocated contiguous node slab.

This is a pure linked list. All operations traverse the ->next chain and the list makes no assumptions about physical node order or adjacency. The slab is an allocation optimisation only: pre-allocating slab_cap nodes in a single contiguous block reduces allocator pressure and improves cache behaviour during sequential traversal, because nodes handed out from the slab in push order tend to be physically adjacent in memory.

Once the slab is exhausted, behaviour is controlled by allow_overflow:

• true — fall back to individual allocator calls. Cache locality is no longer guaranteed beyond the slab boundary. The caller may migrate to a new, larger list to restore locality.

• false — any push beyond slab_cap returns CAPACITY_OVERFLOW and leaves the list unchanged.

Do not manipulate any fields directly; use the provided API.

Public Members

sNode *head

First node, or NULL if empty.

sNode *tail

Last node, or NULL if empty.

uint8_t *slab

Contiguous slab storage for primary nodes.

sNode *slab_free

Recycled slab nodes available for reuse.

size_t len

Number of live nodes currently in the list.

size_t slab_cap

Total number of nodes the slab can hold.

size_t slab_used

Fresh slab slots ever consumed.

size_t slab_free_count

Number of nodes on slab_free.

size_t overflow_live

Number of currently live overflow nodes.

size_t data_size

Bytes per element stored in each node.

dtype_id_t dtype

Type identifier (UINT8_TYPE, FLOAT_TYPE, etc.).

bool allow_overflow

true = allocator fallback, false = hard cap.

allocator_vtable_t alloc_v

Allocator used for slab and overflow nodes.

struct slist_expect_t

Expected return type for init_slist and copy_slist.

Check has_value before using u.value. On failure u.error contains the relevant error_code_t.

struct slist_index_expect_t

Expected return type for contains_slist.

On success u.value is the zero-based index of the first matching node. On failure u.error is NOT_FOUND or another error code.

Initialisation and Teardown

slist_expect_t init_slist(size_t num_nodes, size_t data_size, dtype_id_t dtype, bool allow_overflow, allocator_vtable_t alloc_v)

Allocate and initialise a singly-linked list with a pre-allocated node slab.

All num_nodes nodes are allocated as a single contiguous block of num_nodes * _node_stride(data_size) bytes. This reduces allocator pressure and improves cache behaviour for sequential traversal when nodes are pushed in order. All traversal is performed via ->next pointers.

allocator_vtable_t a = heap_allocator();
slist_expect_t r = init_slist(64, sizeof(float), FLOAT_TYPE, false, a);
if (!r.has_value) { // handle r.u.error }
slist_t* l = r.u.value;
float v = 3.14f;
push_back_slist(l, &v);
return_slist(l);

Parameters:

• num_nodes – Number of nodes to pre-allocate. Must be > 0.

• data_size – Size in bytes of each stored value. Must be > 0.

• dtype – Type tag identifying the stored type.

• allow_overflow – If true, pushes beyond num_nodes fall back to individual allocator calls. If false, returns CAPACITY_OVERFLOW.

• alloc_v – Allocator. alloc_v.allocate must not be NULL.

Returns:

slist_expect_t with has_value true on success.

void return_slist(slist_t *list)

Release all memory owned by the list.

Overflow nodes are returned individually via alloc_v.return_element. The slab and list header are returned in single calls. Passing NULL is safe and performs no action.

Parameters:

• list – List to release.

Push Operations

error_code_t push_back_slist(slist_t *list, const void *value)

Append a copy of value to the tail.

O(1).

Parameters:

• list – Must not be NULL.

• value – Pointer to exactly data_size bytes. Must not be NULL.

Returns:

NO_ERROR, NULL_POINTER, CAPACITY_OVERFLOW, or OUT_OF_MEMORY.

error_code_t push_front_slist(slist_t *list, const void *value)

Prepend a copy of value to the head.

O(1).

Parameters:

• list – Must not be NULL.

• value – Pointer to exactly data_size bytes. Must not be NULL.

Returns:

NO_ERROR, NULL_POINTER, CAPACITY_OVERFLOW, or OUT_OF_MEMORY.

error_code_t push_at_slist(slist_t *list, size_t index, const void *value)

Insert a copy of value before the node at zero-based index.

O(n). index == 0 delegates to push_front_slist. index == list->len delegates to push_back_slist.

Parameters:

• list – Must not be NULL.

• index – Zero-based insertion position (0 … list->len inclusive).

• value – Pointer to exactly data_size bytes. Must not be NULL.

Returns:

NO_ERROR, NULL_POINTER, INVALID_ARG, CAPACITY_OVERFLOW, or OUT_OF_MEMORY.

Access Operations

error_code_t get_slist(const slist_t *list, size_t index, void *out_value)

Copy the value at zero-based index into out_value.

O(n) — traverses the ->next chain from head.

Parameters:

• list – Must not be NULL.

• index – Zero-based position (0 … list->len - 1).

• out_value – Destination buffer of at least data_size bytes.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND (index out of range).

error_code_t peek_front_slist(const slist_t *list, void *out_value)

Copy the value at the head without removing the node.

O(1).

Parameters:

• list – Must not be NULL.

• out_value – Destination buffer of at least data_size bytes.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND (list is empty).

error_code_t peek_back_slist(const slist_t *list, void *out_value)

Copy the value at the tail without removing the node.

O(1).

Parameters:

• list – Must not be NULL.

• out_value – Destination buffer of at least data_size bytes.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND (list is empty).

Pop Operations

error_code_t pop_front_slist(slist_t *list, void *out_value)

Remove the head node and optionally copy its value.

O(1). Pass NULL for out_value to discard.

Parameters:

• list – Must not be NULL.

• out_value – Destination buffer of at least data_size bytes, or NULL.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND (list is empty).

error_code_t pop_back_slist(slist_t *list, void *out_value)

Remove the tail node and optionally copy its value.

O(n) — must walk to find the predecessor of the tail.

Parameters:

• list – Must not be NULL.

• out_value – Destination buffer of at least data_size bytes, or NULL.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND (list is empty).

error_code_t pop_at_slist(slist_t *list, size_t index, void *out_value)

Remove the node at zero-based index and optionally copy its value.

O(n). Boundary cases delegate to pop_front_slist and pop_back_slist.

Parameters:

• list – Must not be NULL.

• index – Zero-based position (0 … list->len - 1).

• out_value – Destination buffer of at least data_size bytes, or NULL.

Returns:

NO_ERROR, NULL_POINTER, INVALID_ARG, or NOT_FOUND.

Iteration

error_code_t foreach_slist(const slist_t *list, slist_iter_fn fn, void *user_data)

Call fn once for every node in the list, in head-to-tail order.

The callback receives a read-only pointer to the node’s inline value buffer, the zero-based node index, and the caller-supplied user_data pointer. The callback must not insert or remove nodes during traversal.

O(n).

static void print_float(const void* v, size_t i, void* ud) {
    (void)ud;
    printf("[%zu] = %f\n", i, *(const float*)v);
}
foreach_slist(l, print_float, NULL);

Parameters:

• list – Must not be NULL.

• fn – Callback. Must not be NULL.

• user_data – Passed unchanged to fn; may be NULL.

Returns:

NO_ERROR or NULL_POINTER.

Search

slist_index_expect_t contains_slist(const slist_t *list, const void *needle)

Search for the first node whose value matches needle.

Comparison is performed by memcmp over data_size bytes. O(n).

float target = 2.0f;
slist_index_expect_t r = contains_slist(l, &target);
if (r.has_value)
    printf("found at index %zu\n", r.u.value);

Parameters:

• list – Must not be NULL.

• needle – Pointer to exactly data_size bytes to search for. Must not be NULL.

Returns:

slist_index_expect_t with has_value true and u.value set to the zero-based index of the first match. On failure u.error is NULL_POINTER or NOT_FOUND.

Introspection

All introspection functions are O(1) read-only operations. Functions return safe default values when passed a NULL pointer.

static inline size_t slist_size(const slist_t *list)

Total number of nodes.

Returns 0 if list is NULL.

static inline bool is_slist_empty(const slist_t *list)

True if list is NULL or contains no nodes.

static inline size_t slist_slab_alloc(const slist_t *list)

Maximum nodes the slab can hold.

Returns 0 if list is NULL.

static inline size_t slist_data_size(const slist_t *list)

Size in bytes of each stored value.

Returns 0 if list is NULL.