dict_t Overview

The dict_t family provides a generic, allocator-agnostic hash dictionary that maps arbitrary byte-span keys to fixed-size values. Keys and values are both stored as raw bytes, making the engine suitable for any value type: a scalar such as float or uint8_t, a struct copied by value, or a pointer to a heap object. Type-specific wrappers cast in and out of the void* interface without the engine needing to know anything about the concrete type.

Keys are represented as a dict_key_t — a (const void* data, size_t len) byte-span pair. This handles both null-terminated C-strings and arbitrary binary keys uniformly. The convenience macro DICT_KEY builds a dict_key_t from a C-string literal in a single expression. The dict always deep-copies key bytes into its own allocator-managed storage on insert, so the caller may free or reuse the key immediately after the call returns.

All memory is managed through an allocator_vtable_t supplied by the caller. init_dict() and insert_dict() each accept an allocator argument; all other operations use the allocator stored in the dict_t at initialisation time. This split allows nodes to be allocated from a different arena than the dict struct itself if needed. See C Allocator Overview for the full allocator API and available implementations.

Error handling follows the expected value pattern: operations that produce a new object return a dict_expect_t whose has_value field distinguishes success from failure, while in-place mutations return an error_code_t directly. Callers must always check the result before using the value.

#include "c_dict.h"

allocator_vtable_t a = heap_allocator();

/* Create a dict mapping C-string keys to float values. */
dict_expect_t r = init_dict(16, sizeof(float), FLOAT_TYPE, true, a);
if (!r.has_value) { /* handle r.u.error */ }
dict_t* d = r.u.value;

float pi = 3.14159f;
insert_dict(d, DICT_KEY("pi"), &pi, a);

float v;
if (get_dict_value(d, DICT_KEY("pi"), &v) == NO_ERROR)
    printf("pi = %f\n", v);

return_dict(d);

Recommended Allocators

Different allocators are appropriate depending on how dictionaries are used and how frequently elements are inserted and removed:

HeapAllocator

Best for:
- general-purpose hash maps
- development and testing
- workloads with unpredictable insertion and removal patterns
The heap allocator is flexible and easy to debug, making it the default choice for most use cases.
ArenaAllocator

Best for:
- build-once dictionaries
- read-only lookup tables
- configuration or initialization data
This is highly efficient when the dictionary is constructed once and not modified or individually freed.
BuddyAllocator

Best for:
- dynamic dictionaries with frequent insertions and deletions
- systems requiring controlled fragmentation
- long-running applications
Buddy allocation helps manage fragmentation when many nodes are allocated and returned over time.
PoolAllocator / SlabAllocator

Best for:
- high-frequency insert/remove workloads
- uniform key/value sizes
- performance-critical systems
Dictionary nodes are typically uniform in size, making them an excellent match for pool or slab allocators. This can significantly reduce allocation overhead and improve cache locality.

Writing a Type-Specific Wrapper

The recommended way to use dict_t is through a thin type-specific wrapper that hides the void* casts. The wrapper fixes data_size and dtype at initialisation and exposes a typed API to callers. No type registration is required — the dict engine uses only memcpy and memcmp internally and never inspects the value bytes.

/* Example: a dict mapping C-string keys to int32_t values. */

typedef dict_t         int32_dict_t;
typedef dict_expect_t  int32_dict_expect_t;

static inline int32_dict_expect_t
init_int32_dict(size_t cap, bool growth, allocator_vtable_t a) {
    return init_dict(cap, sizeof(int32_t), INT32_TYPE, growth, a);
}

static inline error_code_t
insert_int32_dict(int32_dict_t* d, const char* key,
                  int32_t value, allocator_vtable_t a) {
    return insert_dict(d, DICT_KEY(key), &value, a);
}

static inline error_code_t
get_int32_dict_value(const int32_dict_t* d, const char* key,
                     int32_t* out) {
    return get_dict_value(d, DICT_KEY(key), out);
}

Hash Function

Keys are hashed with a MurmurHash3-inspired function operating on the raw key bytes. The hash is seeded with a compile-time constant. The table size is always rounded up to the next power of two and collisions are resolved by chaining. The table resizes automatically when the load factor exceeds 0.75, doubling capacity for small tables and growing by a fixed step for large ones, provided growth was set to true at initialisation.

Internal Structure

Each entry in the hash table is a dict_node_t allocated as a single block whose layout is:

[ dict_node_t header ][ value buffer (data_size bytes) ]

The value buffer is accessed through dict_node_value() and dict_node_value_c(). Nodes are singly-linked within each bucket via the next pointer. Each bucket slot in the backing array is a dict_bucket_t sentinel whose next pointer is the head of the chain for that bucket.

Structs

struct dict_key_t

A non-owning view of a key as a byte span.

Both string keys and arbitrary binary keys are represented the same way. For null-terminated C-strings, set data to the string and len to strlen(string). For binary keys, set len to the byte count.

The dict does not retain the data pointer — it copies the bytes into its own allocation during insert. The caller may free or reuse the key memory immediately after any dict call.

Public Members

const void *data

Pointer to the key bytes.

Must not be NULL.

size_t len

Number of bytes in the key.

Must be > 0.

struct dict_node_t

A single chained node in the hash table.

Each node owns:

An allocator-managed copy of the key bytes (key_data, key_len bytes).
An inline value buffer of data_size bytes immediately following the struct in the same allocation (accessed via dict_node_value()).

Nodes are singly-linked within a bucket.

Public Members

struct dict_node_t *next: Next node in the same bucket, or NULL.

size_t key_len: Length of the key in bytes.

uint8_t *key_data: Allocator-managed copy of the key bytes.

struct dict_bucket_t

A bucket sentinel — each bucket[i] is one of these; its next pointer is the head of the chain for that bucket.

The sentinel itself never holds a key or value; only the linked nodes do.

Public Members

dict_node_t *next: Head of the linked list for this bucket.

struct dict_t

A generic hash dictionary mapping byte-span keys to fixed-size values.

All fields are public so that advanced users can inspect internals, but they should be treated as read-only outside of the dict API.

The value for each key is stored as data_size raw bytes. Type-specific wrappers cast a typed pointer to void* on insert and cast back on retrieval. For pointer-valued dicts (e.g. mapping strings to str_array_t*), store the pointer itself — data_size == sizeof(void*).

// Float-valued dict
allocator_vtable_t a = heap_allocator();
dict_expect_t r = init_dict(8, sizeof(float), FLOAT_TYPE, true, a);
float x = 3.14f;
insert_dict(r.u.value, DICT_KEY("pi"), &x, a);

// Pointer-valued dict (string_t* values)
dict_expect_t r2 = init_dict(8, sizeof(string_t*), STRING_TYPE, true, a);

Public Members

dict_bucket_t *buckets: Array of bucket sentinels, length alloc.

size_t len: Number of occupied buckets (non-empty chains).

size_t hash_size: Total number of key-value pairs stored.

size_t alloc: Number of buckets allocated.

size_t data_size: Value size in bytes, fixed at init.

dtype_id_t dtype: Type tag for the value, fixed at init.

bool growth: If true, resize automatically on high load.

allocator_vtable_t alloc_v: Allocator used for all internal allocations.

struct dict_expect_t: Expected return type for dict_t init and copy operations.

struct dict_entry_t

Read-only view of a single key-value entry, passed to the iterator callback.

Public Members

const void *key: Pointer to the key bytes.

size_t key_len: Length of the key in bytes.

const void *value: Pointer to the value bytes.

size_t value_len: Value size in bytes (== data_size).

Key Construction Macro

DICT_KEY(s)

Construct a dict_key_t from a null-terminated C-string at compile time using sizeof.

The length is set to strlen equivalent via pointer arithmetic so that the key does not include the terminating \0.

insert_dict(d, DICT_KEY("hello"), &value, alloc_v);

Value Access Helpers

These static inline helpers return a pointer to the inline value buffer of a node. They are intended for use inside type-specific wrappers and are not typically called directly by application code.

static inline uint8_t *dict_node_value(dict_node_t *node)

Return a pointer to the inline value buffer of a node.

The value buffer is allocated as part of the same block as node, at offset sizeof(dict_node_t).

Parameters:

node – Must not be NULL.

Returns:

Pointer to the first byte of the value.

static inline const uint8_t *dict_node_value_c(const dict_node_t *node): Const-qualified variant of dict_node_value().

Iterator Type

typedef void (*dict_iter_fn)(dict_entry_t entry, void *user_data)

Iterator callback type for foreach_dict().

Param entry:: Read-only view of the current key-value pair.
Param user_data:: Caller-supplied context pointer, may be NULL.

Initialisation and Teardown

dict_expect_t init_dict(size_t capacity, size_t data_size, dtype_id_t dtype, bool growth, allocator_vtable_t alloc_v)

Allocate and initialise a new dict_t.

allocator_vtable_t a = heap_allocator();
dict_expect_t r = init_dict(16, sizeof(float), FLOAT_TYPE, true, a);
if (!r.has_value) { handle r.u.error }
dict_t* d = r.u.value;

Parameters:

capacity – Initial bucket count. Must be > 0. Rounded up to the next power of two internally.
data_size – Size of each value in bytes. Must be > 0.
dtype – Type tag stored in dict_t::dtype. Use one of the *_TYPE constants from c_dtypes.h, or a user-defined id >= USER_BASE_TYPE.
growth – If true, the table resizes automatically when the load factor exceeds 0.75.
alloc_v – Allocator for all internal memory. alloc_v.allocate must not be NULL.

Returns:

dict_expect_t with has_value true and u.value pointing to the new dict on success; has_value false with u.error set to NULL_POINTER, INVALID_ARG, or OUT_OF_MEMORY on failure.

void return_dict(dict_t *dict)

Free all memory owned by a dict_t.

Releases every node (key copy + value buffer), the bucket array, and the dict_t struct itself. Passing NULL is safe and performs no action.

Parameters:

dict – Dictionary to free.

Insert / Remove / Update

error_code_t insert_dict(dict_t *dict, dict_key_t key, const void *value, allocator_vtable_t alloc_v)

Insert a new key-value pair.

The key bytes are deep-copied via the allocator. The value is copied bytewise (data_size bytes) from value into the node.

If the key already exists the insertion is rejected and INVALID_ARG is returned. To update an existing key use update_dict().

If growth is true and the load factor exceeds 0.75, the table is resized before insertion.

Parameters:

dict – Must not be NULL.
key – Key to insert. key.data must not be NULL; key.len must be > 0.
value – Pointer to dict->data_size bytes to copy as the value. Must not be NULL.
alloc_v – Allocator used to allocate the new node.

Returns:

NO_ERROR, NULL_POINTER, INVALID_ARG (duplicate key), CAPACITY_OVERFLOW (table full and growth == false), or OUT_OF_MEMORY.

error_code_t pop_dict(dict_t *dict, dict_key_t key, void *out_value)

Remove the entry with the given key and copy its value out.

If out_value is non-NULL and the key is found, dict->data_size bytes are copied from the node’s value buffer into out_value before the node is freed. If the key is not found, out_value is not written.

Parameters:

dict – Must not be NULL.
key – Key to remove.
out_value – Destination buffer of at least dict->data_size bytes, or NULL to discard the value.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND.

error_code_t update_dict(dict_t *dict, dict_key_t key, const void *value)

Overwrite the value of an existing key.

Copies dict->data_size bytes from value into the node’s inline buffer. The key is not re-hashed and no allocation is performed.

Parameters:

dict – Must not be NULL.
key – Key to update. Must already exist.
value – Pointer to dict->data_size bytes. Must not be NULL.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND.

Lookup

error_code_t get_dict_value(const dict_t *dict, dict_key_t key, void *out_value)

Copy the value associated with a key into a caller-supplied buffer.

Parameters:

dict – Must not be NULL.
key – Key to look up.
out_value – Destination buffer of at least dict->data_size bytes. Must not be NULL.

Returns:

NO_ERROR, NULL_POINTER, or NOT_FOUND.

const void *get_dict_value_ptr(const dict_t *dict, dict_key_t key)

Return a read-only pointer directly into the node’s value buffer.

The pointer is valid until the next mutation of the dict. The caller must not free or write through it.

Parameters:

dict – Must not be NULL.
key – Key to look up.

Returns:

Pointer to the value bytes on success, NULL if not found or on error.

bool has_dict_key(const dict_t *dict, dict_key_t key)

Test whether a key exists in the dict without retrieving its value.

Parameters:

dict – Must not be NULL.
key – Key to test.

Returns:

true if the key exists, false if not found or on error.

Utility Operations

error_code_t clear_dict(dict_t *dict)

Remove all entries without freeing the dict or its bucket array.

Frees every node (key copy + value buffer). The bucket array is retained and zeroed, ready for reuse. len and hash_size are reset to 0.

Parameters:

dict – Must not be NULL.

Returns:

NO_ERROR or NULL_POINTER.

dict_expect_t copy_dict(const dict_t *src, allocator_vtable_t alloc_v)

Allocate a deep copy of src.

All nodes are rehashed into a fresh bucket array of the same capacity. The copy uses alloc_v for all allocations; src->alloc_v is not forwarded automatically.

Parameters:

src – Must not be NULL.
alloc_v – Allocator for the new dict and its nodes.

Returns:

dict_expect_t with has_value true on success.

dict_expect_t merge_dict(const dict_t *a, const dict_t *b, bool overwrite, allocator_vtable_t alloc_v)

Merge two dicts into a new dict.

All entries from a are inserted first. Entries from b are then processed:

If the key does not exist in the result, it is inserted.
If the key already exists and overwrite is true, the value is updated.
If the key already exists and overwrite is false, the original value is kept.

Both source dicts must have the same data_size; if they differ INVALID_ARG is returned.

Parameters:

a – First source dict. Must not be NULL.
b – Second source dict. Must not be NULL.
overwrite – If true, b's values win on key conflicts.
alloc_v – Allocator for the new dict.

Returns:

dict_expect_t with has_value true on success.

Iteration

foreach_dict() visits every entry in bucket order, which is not guaranteed to match insertion order. The callback receives a read-only dict_entry_t view of the current key and value. The callback must not insert or remove entries during traversal.

static void print_entry(dict_entry_t e, void* ud) {
    (void)ud;
    float v;
    memcpy(&v, e.value, sizeof(float));
    printf("%.*s = %f\n", (int)e.key_len, (const char*)e.key, v);
}

foreach_dict(d, print_entry, NULL);

error_code_t foreach_dict(const dict_t *dict, dict_iter_fn fn, void *user_data)

Call fn once for every entry in the dict.

Traversal order is bucket order (not insertion order). The callback receives a dict_entry_t view; it must not insert or remove entries during traversal.

static void print_entry(dict_entry_t e, void* ud) {
    (void)ud;
    float v;
    memcpy(&v, e.value, sizeof(float));
    printf("%.*s = %f\n", (int)e.key_len, (const char*)e.key, v);
}
foreach_dict(d, print_entry, NULL);

Parameters:

dict – Must not be NULL.
fn – Callback invoked for each entry. Must not be NULL.
user_data – Passed unchanged to fn; may be NULL.

Returns:

NO_ERROR or NULL_POINTER.

Introspection

size_t dict_size(const dict_t *dict)

Number of occupied buckets (chains with at least one entry).

Returns 0 if dict is NULL.

size_t dict_hash_size(const dict_t *dict)

Total number of key-value pairs stored.

Returns 0 if dict is NULL.

size_t dict_alloc(const dict_t *dict)

Number of buckets allocated.

Returns 0 if dict is NULL.

size_t dict_data_size(const dict_t *dict)

Value size in bytes as fixed at initialisation.

Returns 0 if dict is NULL.

bool is_dict_empty(const dict_t *dict): true if dict is NULL or contains no entries.