AxlRBTree — Intrusive Augmented Red-Black Tree

See AxlData — Data Structures for an overview of all data modules.

A generic, intrusive, augmentable red-black tree. The caller embeds an AxlRBNode in its own struct (the tree never allocates nodes) and descends to the insertion point itself, so the same tree serves ordered maps, order-statistic trees, and the byte/newline-weighted AxlPieceTree — Out-of-Core Editable Buffer. An optional recompute callback keeps a cached subtree aggregate (size, byte/newline sums, …) exact across every structural change in O(log n).

Distinct from AxlTree’s sibling AVL map — that is a non-intrusive key→value container; this is intrusive and augmentable. Reimplemented under Apache-2.0 from the textbook red-black algorithm; no GPL source is used. See docs/AXL-RBTree-Design.md.

Header: <axl/axl-rb-tree.h>

API Reference

Defines

AXL_RB_ENTRY(ptr, type, member)

Recover the embedding struct from a node pointer.

Parameters:

  • ptr – AxlRBNode pointer

  • type – embedding struct type

  • member – name of the AxlRBNode field in type

Typedefs

typedef void (*AxlRBRecompute)(AxlRBNode *node, void *user)

AxlRBRecompute:

Recompute node's cached aggregate(s) from its own payload and its children’s aggregates (read the children via AXL_RB_ENTRY on node->left / node->right; a NULL child contributes the identity). Invoked bottom-up after structural changes — when called, both children already hold correct aggregates. May be NULL (a plain balanced tree with no augmentation).

Enums

enum AxlRBColor

axl-rb-tree.h:

A generic, intrusive, augmentable red-black tree.

Intrusive: the caller embeds an AxlRBNode in its own struct and recovers the struct with AXL_RB_ENTRY; the tree never allocates or frees nodes. Generic: no key type or comparator is baked in — the caller descends to the insertion point itself (by key, by position, by weighted sum), so the same tree serves ordered maps, order-statistic trees, and the byte/newline-weighted piece tree.

Augmentation: an optional recompute callback recomputes a node’s cached aggregate(s) (subtree size, subtree byte/newline sums, …) from its own payload plus its children’s aggregates. The tree invokes it bottom-up after every structural change, so the aggregates stay exact with O(log n) work per edit.

This is the substrate behind AxlPieceTree. It is distinct from AxlTree, which is a non-intrusive, opaque, key->value AVL map.

Reimplemented under Apache-2.0 from the textbook red-black algorithm (CLRS) and the well-known intrusive/augment API pattern. No GPL (e.g. Linux kernel rbtree) source is used.

Single-threaded (UEFI).

Values:

enumerator AXL_RB_RED
enumerator AXL_RB_BLACK

Functions

void axl_rb_tree_init(AxlRBTree *t, AxlRBRecompute recompute, void *user)

Initialize an empty tree.

Parameters:

  • t – tree

  • recompute – augmentation hook, or NULL

  • user – cookie for recompute

bool axl_rb_tree_empty(const AxlRBTree *t)

Whether the tree has no nodes.

Parameters:

  • t – tree

Link a new node into a found slot as a red leaf.

Step 1 of insertion: the caller descends to the insertion point, tracking the parent and the address of the child slot link (&parent->left or &parent->right, or &tree->root for the first node). This links node there; call axl_rb_insert() next to rebalance.

Parameters:

  • node – node to link (payload already set)

  • parent – parent node (NULL for the root)

  • link – child slot to write node into

void axl_rb_insert(AxlRBTree *t, AxlRBNode *node)

Rebalance after axl_rb_link_node and propagate augmentation.

Step 2 of insertion. Restores the red-black invariants (rotations as needed) and brings every affected node’s aggregate up to date.

Parameters:

  • t – tree

  • node – the just-linked node

void axl_rb_erase(AxlRBTree *t, AxlRBNode *node)

Remove a node and rebalance.

Restores the red-black invariants and updates augmentation. The node’s memory is the caller’s to reuse or free afterward.

Parameters:

  • t – tree

  • node – node to remove (must be in t)

void axl_rb_update_augment(AxlRBTree *t, AxlRBNode *node)

Re-propagate augmentation after an in-place payload change.

Call when a node’s payload changed in a way that affects its aggregate but its tree position did not (e.g. trimming a piece’s length). Recomputes from node to the root.

Parameters:

  • t – tree

  • node – node whose payload changed

AxlRBNode *axl_rb_first(const AxlRBTree *t)

First (in-order minimum) node, or NULL if empty.

Parameters:

  • t – tree

AxlRBNode *axl_rb_last(const AxlRBTree *t)

Last (in-order maximum) node, or NULL if empty.

Parameters:

  • t – tree

AxlRBNode *axl_rb_next(const AxlRBNode *node)

In-order successor of node, or NULL.

Parameters:

  • node – node

AxlRBNode *axl_rb_prev(const AxlRBNode *node)

In-order predecessor of node, or NULL.

Parameters:

  • node – node

struct AxlRBNode

AxlRBNode:

Intrusive tree link. Embed one in your struct and recover the struct with AXL_RB_ENTRY. Fields are managed by the tree — treat as opaque.

Public Members

AxlRBNode *parent
AxlRBNode *left
AxlRBNode *right
AxlRBColor color
struct AxlRBTree
#include <axl-rb-tree.h>

AxlRBTree:

Tree handle — a caller-embedded value (no allocation; the tree owns nothing). Initialize with axl_rb_tree_init.

Public Members

AxlRBNode *root
AxlRBRecompute recompute

augmentation hook (NULL = none)

void *user

cookie passed to recompute