AVL Tree

c_tree.h provides a generic, type-erased AVL (self-balancing binary search tree) built on top of the csalt allocator and dtype systems. It is designed for predictable performance, allocator control, and efficient ordered data access 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 AVL tree 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.

The tree maintains the AVL invariant:

  • For every node, the height difference between left and right subtrees is at most 1

  • Insertions and removals automatically rebalance the tree using rotations

This guarantees:

  • O(log n) insertion

  • O(log n) removal

  • O(log n) search

  • Ordered traversal in O(n)

A hybrid allocation model is used:

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

  • Nodes are recycled through an internal free list

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

All memory management is performed through a caller-supplied allocator_vtable_t.

#include "c_tree.h"

static int cmp_int32(const void* a, const void* b) {
    int32_t x = *(const int32_t*)a;
    int32_t y = *(const int32_t*)b;
    return (x > y) - (x < y);
}

allocator_vtable_t alloc = heap_allocator();

avl_expect_t r = init_avl(64, INT32_TYPE, true, false, alloc, cmp_int32);
if (!r.has_value) { /* handle r.u.error */ }

avl_t* tree = r.u.value;

int32_t v = 42;
avl_insert(tree, &v);

int32_t out = 0;
avl_find(tree, &v, &out);

return_avl(tree);

Note

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

Memory Model

Each node stores its value inline:

struct avl_node_t {
    struct avl_node_t* left;
    struct avl_node_t* right;
    int                height;
    uint8_t            data[];
};

This layout provides:

  • Single allocation per node

  • Improved spatial locality for slab-allocated nodes

  • No double indirection for value access

The tree uses three allocation strategies:

  1. Free list reuse (primary) - Removed nodes are recycled - Avoids unnecessary allocations

  2. Slab allocation - Nodes are carved from a contiguous block - Improves cache performance

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

Ownership Rules

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

  • All memory is released via return_avl()

  • Individual nodes must never be freed by the caller

Allocator Integration

All allocations are performed through allocator_vtable_t.

This allows the tree to be backed by:

  • heap allocators

  • arena allocators

  • pool allocators

  • buddy allocators

  • custom user-defined allocators

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

See C Allocator Overview for details.

Error Handling

The tree follows the csalt expected value pattern:

  • Constructors return avl_expect_t

  • Mutating operations return error_code_t

Callers must always check return values.

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

Type System and User-Defined Types

The tree relies on dtype_id_t to describe stored data.

Built-in types are defined in c_dtypes.h:

  • INT32_TYPE

  • FLOAT_TYPE

  • DOUBLE_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 VEC3_TYPE (USER_BASE_TYPE + 1u)

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

ensure_dtype_registered(&vec3_desc);

avl_expect_t r = init_avl(32, VEC3_TYPE, false, false, alloc, cmp_vec3);

Note

User-defined dtype IDs must be >= USER_BASE_TYPE and must be unique.

Core API

Structs

struct avl_t

A generic, type-safe AVL binary search tree.

avl_t stores elements as fixed-size inline byte buffers inside avl_node_t nodes. All node memory comes from a pre-allocated contiguous slab carved at initialisation. When the slab is exhausted and overflow is enabled, additional nodes are allocated individually through the allocator vtable. Removed nodes are returned to an internal free list (reusing the left pointer field) so that slab slots are recycled rather than abandoned.

Tree ordering and duplicate policy are both fixed at initialisation:

  • The comparator defines the sort order and follows the qsort(3) convention.

  • allow_duplicates controls whether equal elements are accepted (inserted into the right subtree of their match) or rejected with INVALID_ARG.

In-order traversal via avl_foreach always visits elements in sorted order, which is the primary advantage of an AVL tree over a heap.

Do not modify any field directly — use the provided API functions.

Public Members

avl_node_t *root

Root of the tree; NULL when empty.

avl_node_t *slab

Flat pre-allocated node block.

avl_node_t *free_list

Head of the recycled-node free list.

size_t slab_cap

Total nodes in the slab.

size_t slab_used

Next uncarved slab index (bump pointer).

size_t len

Cached number of elements in the tree.

size_t data_size

Size of one element in bytes.

size_t node_size

sizeof(avl_node_t) + data_size, cached.

dtype_id_t dtype

Runtime type identity.

Fixed at init time.

bool overflow

If true, allocate beyond slab when full.

bool allow_duplicates

If true, equal elements go to right child.

allocator_vtable_t alloc_v

Allocator vtable for all memory operations.

int (*cmp)(const void*, const void*)

Element comparator.

struct avl_expect_t

Expected return type for AVL tree initialisation and copy operations.

On success, has_value is true and u.value points to a valid avl_t. On failure, has_value is false and u.error contains the error code.

Initialisation and Teardown

avl_expect_t init_avl(size_t capacity, dtype_id_t dtype, bool overflow, bool allow_duplicates, allocator_vtable_t alloc_v, int (*cmp)(const void*, const void*))

Initialise a new AVL tree.

Allocates the avl_t struct and a contiguous slab of capacity nodes through the provided allocator vtable. The dtype must be registered in the dtype registry before calling this function. The comparator and duplicate policy are fixed for the lifetime of the tree.

The comparator follows the qsort(3) convention:

  • Returns < 0 if *a should sort before *b.

  • Returns 0 if *a and *b are equal.

  • Returns > 0 if *a should sort after *b.

When allow_duplicates is true, elements that compare equal to an existing node are inserted into that node’s right subtree. When false, avl_insert returns INVALID_ARG without modifying the tree.

When overflow is true and the slab is exhausted, additional nodes are allocated individually through alloc_v. When false, avl_insert returns CAPACITY_OVERFLOW once the slab is full and no free-list slots remain.

static int cmp_int32(const void* a, const void* b) {
    int32_t va = *(const int32_t*)a, vb = *(const int32_t*)b;
    return (va > vb) - (va < vb);
}
allocator_vtable_t alloc = heap_allocator();
avl_expect_t r = init_avl(64, INT32_TYPE, true, false, alloc, cmp_int32);
if (!r.has_value) { handle_error(r.u.error); }
avl_t* tree = r.u.value;

Parameters:

  • capacity – Number of nodes to pre-allocate in the slab. Must be > 0.

  • dtype – Type identifier. Must be registered in the dtype registry.

  • overflow – If true, allocate beyond the slab when it is exhausted.

  • allow_duplicates – If true, equal elements are accepted; if false, they are rejected with INVALID_ARG.

  • alloc_v – Allocator vtable for all memory operations.

  • cmp – Comparator defining sort order. Must not be NULL.

Returns:

avl_expect_t with has_value true and a valid avl_t* on success. On failure, has_value is false and u.error is one of:

  • NULL_POINTER if alloc_v.allocate or cmp is NULL

  • INVALID_ARG if capacity is 0 or dtype is UNKNOWN_TYPE

  • ILLEGAL_STATE if the dtype registry could not be initialised

  • TYPE_MISMATCH if dtype is not registered in the dtype registry

  • LENGTH_OVERFLOW if capacity * node_size would overflow size_t

  • BAD_ALLOC if the allocator fails to allocate the avl_t struct

  • OUT_OF_MEMORY if the allocator fails to allocate the node slab

void return_avl(avl_t *tree)

Return an AVL tree’s memory back to its allocator.

Frees every overflow node individually through the allocator vtable, then releases the node slab and the avl_t struct. Slab nodes do not require individual deallocation since the entire slab is freed as one block. After this call the pointer must not be used.

Parameters:

  • tree – Pointer to the tree to return. Silently ignored if NULL.

Insertion and Removal

error_code_t avl_insert(avl_t *tree, const void *data)

Insert one element into the tree and restore AVL balance.

Descends the tree using cmp to find the insertion point. If an equal element is found and allow_duplicates is false, returns INVALID_ARG without modifying the tree. If allow_duplicates is true, the new element is placed in the right subtree of the matching node. After insertion, the path from the new node back to the root is rebalanced via single and double rotations as needed. The element is copied by value; the caller retains ownership of the buffer pointed to by data.

Node allocation prefers the free list, then the slab bump pointer, then overflow allocation if enabled.

int32_t v = 42;
error_code_t err = avl_insert(tree, &v);

Parameters:

  • tree – Pointer to the target tree. Must not be NULL.

  • data – Pointer to the element to insert. Must not be NULL. Must point to exactly tree->data_size bytes.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree or data is NULL

  • INVALID_ARG if the element compares equal to an existing node and allow_duplicates is false

  • CAPACITY_OVERFLOW if the slab is full, free list is empty, and overflow is false

  • OUT_OF_MEMORY if overflow is true but allocation fails

error_code_t avl_remove(avl_t *tree, const void *key, void *out)

Remove one element from the tree and restore AVL balance.

Searches for an element equal to key under the tree’s comparator. If found, optionally copies it into out, unlinks the node using the standard BST deletion algorithm (replacing with in-order successor when the node has two children), rebalances the path back to the root, and returns the node to the internal free list for reuse. If allow_duplicates is true and multiple equal elements exist, the first one encountered in the descent is removed.

int32_t key = 42, removed;
error_code_t err = avl_remove(tree, &key, &removed);

Parameters:

  • tree – Pointer to the target tree. Must not be NULL.

  • key – Pointer to a value to match against. Must not be NULL. Must point to exactly tree->data_size bytes.

  • out – Caller-provided buffer to receive the removed element, or NULL to discard. If non-NULL must be at least tree->data_size bytes.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree or key is NULL

  • EMPTY if the tree contains no elements

  • NOT_FOUND if no element equal to key exists in the tree

Search and Access

bool avl_contains(const avl_t *tree, const void *key)

Test whether an element equal to key exists in the tree.

Descends the tree in O(log n) comparisons. Does not modify the tree.

int32_t key = 42;
if (avl_contains(tree, &key)) { ... }

Parameters:

  • tree – Pointer to the tree to search. Must not be NULL.

  • key – Pointer to the value to search for. Must not be NULL.

Returns:

true if a matching element is found, false otherwise. Also returns false if tree or key is NULL.

error_code_t avl_find(const avl_t *tree, const void *key, void *out)

Copy the element equal to key into a caller-supplied buffer.

Descends the tree in O(log n) comparisons and copies exactly tree->data_size bytes into out if a match is found. The tree is not modified.

int32_t key = 42, result;
error_code_t err = avl_find(tree, &key, &result);

Parameters:

  • tree – Pointer to the tree to search. Must not be NULL.

  • key – Pointer to the value to search for. Must not be NULL.

  • out – Caller-provided buffer to receive the found element. Must not be NULL. Must be at least tree->data_size bytes.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree, key, or out is NULL

  • EMPTY if the tree contains no elements

  • NOT_FOUND if no element equal to key exists in the tree

error_code_t avl_min(const avl_t *tree, void *out)

Copy the minimum element (leftmost node) into a caller-supplied buffer.

Traverses left pointers from the root to the leftmost node in O(log n). The tree is not modified.

int32_t min_val;
error_code_t err = avl_min(tree, &min_val);

Parameters:

  • tree – Pointer to the tree to query. Must not be NULL.

  • out – Caller-provided buffer to receive the minimum element. Must not be NULL. Must be at least tree->data_size bytes.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree or out is NULL

  • EMPTY if the tree contains no elements

error_code_t avl_max(const avl_t *tree, void *out)

Copy the maximum element (rightmost node) into a caller-supplied buffer.

Traverses right pointers from the root to the rightmost node in O(log n). The tree is not modified.

int32_t max_val;
error_code_t err = avl_max(tree, &max_val);

Parameters:

  • tree – Pointer to the tree to query. Must not be NULL.

  • out – Caller-provided buffer to receive the maximum element. Must not be NULL. Must be at least tree->data_size bytes.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree or out is NULL

  • EMPTY if the tree contains no elements

Traversal

error_code_t avl_foreach(const avl_t *tree, void (*fn)(const void *element, void *ctx), void *ctx)

Visit every element in sorted order via an in-order traversal.

Performs a recursive in-order traversal (left subtree, node, right subtree), calling fn once per element in ascending order as defined by the tree’s comparator. When allow_duplicates is true, equal elements appear contiguously in the output in an unspecified relative order.

The callback signature is: void fn(const void* element, void* ctx) where element points into the node’s inline data buffer (valid only for the duration of the callback) and ctx is the opaque pointer supplied by the caller. The tree must not be mutated during traversal.

static void print_int(const void* elem, void* ctx) {
    (void)ctx;
    printf("%d\n", *(const int32_t*)elem);
}
avl_foreach(tree, print_int, NULL);

Parameters:

  • tree – Pointer to the tree to traverse. Must not be NULL.

  • fn – Callback invoked once per element in sorted order. Must not be NULL.

  • ctx – Opaque pointer forwarded to every fn call. May be NULL.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree or fn is NULL

  • EMPTY if the tree contains no elements

error_code_t avl_foreach_range(const avl_t *tree, const void *low, const void *high, void (*fn)(const void *element, void *ctx), void *ctx)

Visit every element within [low, high] in sorted order.

Performs a selective in-order traversal, calling fn only for elements e where cmp(low, e) <= 0 and cmp(e, high) <= 0. The subtree descent is pruned: left subtrees are skipped when the current node is already below low, and right subtrees are skipped when the current node is already above high, making this significantly faster than a full traversal followed by filtering when the range is narrow relative to the tree size.

Both low and high are inclusive bounds. Passing the same pointer for both is valid and visits exactly the elements equal to that value (useful for duplicate-enabled trees).

int32_t lo = 10, hi = 50;
avl_foreach_range(tree, &lo, &hi, print_int, NULL);

Parameters:

  • tree – Pointer to the tree to traverse. Must not be NULL.

  • low – Pointer to the lower bound (inclusive). Must not be NULL.

  • high – Pointer to the upper bound (inclusive). Must not be NULL.

  • fn – Callback invoked once per in-range element. Must not be NULL.

  • ctx – Opaque pointer forwarded to every fn call. May be NULL.

Returns:

NO_ERROR on success, or one of:

  • NULL_POINTER if tree, low, high, or fn is NULL

  • EMPTY if the tree contains no elements

  • INVALID_ARG if cmp(low, high) > 0 (inverted range)

Introspection

All introspection functions are O(1) read-only operations.

size_t avl_size(const avl_t *tree)

Return the number of elements currently stored in the tree.

Returns the cached len field. O(1). Returns 0 if tree is NULL.

Parameters:

  • tree – Pointer to the tree to query.

Returns:

Number of elements in the tree, or 0 if tree is NULL.

int avl_height(const avl_t *tree)

Return the height of the tree.

Returns the cached height of the root node, which equals the height of the entire tree. An empty tree has height 0; a single-node tree has height 1. O(1). Returns 0 if tree is NULL or the tree is empty.

For a perfectly balanced tree of n nodes, height is approximately log2(n). The AVL invariant guarantees height never exceeds 1.44 * log2(n + 2).

Parameters:

  • tree – Pointer to the tree to query.

Returns:

Height of the tree, or 0 if tree is NULL or empty.

bool avl_is_empty(const avl_t *tree)

Return true if the tree contains no elements.

Equivalent to avl_size(tree) == 0. Returns true if tree is NULL.

Parameters:

  • tree – Pointer to the tree to query.

Returns:

true if empty or NULL, false otherwise.

Copy

avl_expect_t copy_avl(const avl_t *src, allocator_vtable_t alloc_v)

Create a deep copy of an AVL tree using a (possibly different) allocator.

Allocates a new avl_t struct and a new node slab through alloc_v, then copies all elements from src into the new tree via a pre-order traversal. The copy shares the same dtype, data_size, comparator, overflow flag, and allow_duplicates policy as src. The comparator function pointer is shallow-copied — function pointers carry no ownership.

The returned tree is fully independent of src: mutations to either tree do not affect the other, and each must be individually returned via return_avl.

The copy’s slab is sized to src->len rather than src->slab_cap, so the copy is compact. If the caller expects to insert more elements, they should pre-size their own tree or enable overflow.

allocator_vtable_t alloc = heap_allocator();
avl_expect_t r = copy_avl(tree, alloc);
if (!r.has_value) { handle_error(r.u.error); }
avl_t* copy = r.u.value;
// ... use copy ...
return_avl(copy);

Parameters:

  • src – Pointer to the source tree. Must not be NULL.

  • alloc_v – Allocator vtable for all memory operations on the new tree. May differ from src’s allocator. alloc_v.allocate must not be NULL.

Returns:

avl_expect_t with has_value true and a valid avl_t* on success. On failure, has_value is false and u.error is one of:

  • NULL_POINTER if src is NULL or alloc_v.allocate is NULL

  • BAD_ALLOC if the allocator fails to allocate the new avl_t

  • OUT_OF_MEMORY if the allocator fails to allocate the new node slab