ztree.h

ztree.h provides Type-safe Red-Black Trees (Ordered Maps/Sets) for C projects. Unlike typical C tree implementations that rely on void* casting and lose type safety, ztree.h uses C11 _Generic selection and X-Macros to generate fully typed, type-safe implementations for your specific Key/Value pairs.

It also includes a robust C++11 wrapper, allowing you to use it as a lightweight, drop-in map class (z_tree::map) in mixed codebases while sharing the same underlying C implementation.

It is part of the Zen Development Kit.

Features

• Type Safety: Compiler errors if you try to insert a float key into an int tree.
• Sorted Data: Keys are always maintained in sorted order (Red-Black Tree invariant).
• Native Performance: Node-based structure with optimized rotation and rebalancing logic.
• C++ Support: Includes a full C++ class wrapper with RAII, iterators, and std::map-like API.
• Range Queries: Supports lower_bound for finding elements >= key.
• Header Only: No linking required.
• Memory Agnostic: Supports custom allocators.
• Zero Dependencies: Only standard C headers used.

Installation

Manual

ztree.h uses X-Macros to register types.

1. Copy ztree.h (and zcommon.h if separated) to your project's include folder.
2. Add the z-core tools (optional but recommended):

    git submodule add https://github.com/z-libs/z-core.git z-core

Clib

If you use the clib package manager, run:

    clib install z-libs/zdk

ZDK (Recommended)

If you use the Zen Development Kit, it is included automatically by including <zdk/ztree.h> (or <zdk/zworld.h>).

Usage: C

For C projects, you define the tree types you need using X-Macros. You must also provide a comparison function.

#include <stdio.h>
#include <string.h>

// Define comparison function: int (*)(const Key*, const Key*)
// Returns <0 if a < b, 0 if equal, >0 if a > b.
static int str_cmp(const char** a, const char** b) {
    return strcmp(*a, *b);
}

// Register types: X(KeyType, ValueType, Name, CompareFunc)
#define REGISTER_ZTREE_TYPES(X) \
    X(const char*, int, SymbolTable, str_cmp)

#include "ztree.h"

int main(void)
{
    // Initialize.
    ztree_SymbolTable symbols = ztree_init(SymbolTable);

    // Insert.
    ztree_insert(&symbols, "velocity", 100);
    ztree_insert(&symbols, "gravity", 9);

    // Find.
    ztree_node_SymbolTable* node = ztree_find(&symbols, "velocity");
    if (node) 
    {
        printf("Velocity is: %d\n", node->value);
    }
        
    // Iteration (sorted).
    ztree_foreach(&symbols, it) 
    {
        printf("%s: %d\n", it->key, it->value);
    }

    // Cleanup.
    ztree_free(&symbols); // (mapped via ztree_clear)
    return 0;
}

Usage: C++

The library detects C++ compilers automatically. The C++ wrapper lives in the z_tree namespace.

Note: C++ objects (like std::string) are supported. The library uses new and delete internally when compiled in C++ mode to ensure constructors/destructors are called.

#include <iostream>
#include <string>

// Comparator for int keys (descending order).
static int int_cmp(const int* a, const int* b) { return *b - *a; }

// Register C backend.
#define REGISTER_ZTREE_TYPES(X) \
    X(int, std::string, Leaderboard, int_cmp)

#include "ztree.h"

int main()
{
    // RAII handles memory automatically.
    z_tree::map<int, std::string> board;

    // Operator[] support.
    board[100] = "Alice";
    board[50]  = "Bob";

    // Range-based for loops (via proxy object).
    for(auto entry : board) 
    {
        std::cout << entry.value() << ": " << entry.key() << "\n";
    }

    // Lower bound.
    auto it = board.lower_bound(80);
    if (it != board.end()) 
    {
        std::cout << "Top score <= 80 is: " << it.value() << "\n";
    }

    return 0;
}

Manual Setup

You register your types using X-Macros.

• Create a file named my_trees.h (or similar).
• Register your types.

#ifndef MY_TREES_H
#define MY_TREES_H

// Comparator must match: int (*)(const Key*, const Key*).
int my_int_cmp(const int* a, const int* b);

#define REGISTER_ZTREE_TYPES(X) \
    X(int, float, MyMap, my_int_cmp)

// **IT HAS TO BE INCLUDED AFTER, NOT BEFORE**.
#include "ztree.h"

#endif

API Reference (C)

ztree.h uses C11 _Generic to automatically select the correct function implementation based on the tree pointer you pass.

Initialization & Management

Macro	Description
ztree_init(Name)	Returns an empty tree structure initialized to zero.
ztree_clear(t)	Frees all nodes in the tree and resets size to 0.
ztree_autofree(Name)	Declares a tree that automatically calls clear when the variable leaves scope (RAII style, GCC/Clang only).

Data Access

Macro	Description
ztree_find(t, key)	Returns a pointer to the node matching key, or NULL.
ztree_lower_bound(t, key)	Returns a pointer to the first node that is not less than key (>=).
ztree_min(t)	Returns the node with the minimum key.
ztree_max(t)	Returns the node with the maximum key.

Modification

Macro	Description
ztree_insert(t, key, val)	Inserts a key-value pair. Updates value if key exists. Returns Z_OK or Z_ENOMEM.
ztree_remove(t, key)	Removes the node with key. Rebalances the tree automatically.

Iteration

Macro	Description
ztree_next(node)	Returns the successor node (in sorted order).
ztree_prev(node)	Returns the predecessor node.
ztree_foreach(t, it)	Standard traversal. it is a node pointer.
ztree_foreach_safe(t, it, safe)	Traversal that allows ztree_remove on the current iterator.
ztree_foreach_reverse(t, it)	Standard reverse traversal.

API Reference (C++)

The C++ wrapper lives in the z_tree namespace. It strictly adheres to RAII principles and delegates logic to the underlying C implementation.

class z_tree::map<K, V>

Constructors & Management

Method	Description
map()	Default constructor (empty).
~map()	Destructor. Automatically frees nodes.
operator=	Copy (delete) and Move (transfer) assignment.
clear()	Removes all elements.

Access & Iterators

Method	Description
size()	Returns current number of elements.
empty()	Returns true if size is 0.
operator[](key)	Returns reference to value. Inserts default if missing.
find(key)	Returns pointer to value or nullptr.
lower_bound(key)	Returns iterator to first element >= key.
begin(), end()	Standard bidirectional iterators.

Modification

Method	Description
insert(k, v)	Inserts or updates key-value pair.
erase(key)	Removes element by key.
erase(iterator)	Removes element at iterator. Returns next valid iterator.

Memory Management

By default, ztree.h uses the standard C library functions (malloc, free) in C mode.

Important for C++:

In C++ mode, ztree.h automatically switches to using new and delete. This ensures that complex types (like std::string or classes with destructors) are correctly constructed and destructed inside the tree nodes.

Global Override

To use a custom allocator (for example, for C arenas), define the Z_ macros inside your registry header.

#ifndef MY_TREES_H
#define MY_TREES_H

#include "my_memory.h"

// Override global allocators
#define Z_MALLOC(sz)      my_alloc(sz)
#define Z_FREE(p)         my_free(p)
// (ztree doesn't use realloc/calloc, but defining them keeps consistency)

#include "ztree.h"
#endif

Short Names (Opt-In)

If you prefer a cleaner API and don't have naming conflicts, define ZTREE_SHORT_NAMES before including the header.

#define ZTREE_SHORT_NAMES
#include "ztree.h"

// Now you can use:
ztree_SymbolTable t = tree_init(SymbolTable);
tree_insert(&t, k, v);
tree_foreach(&t, it) { ... }