rbtree.cxxm File Reference

Intrusive augmented red-black tree. More...

import std;
import lib.container_of;
import zxfoundation.base.types;

Include dependency graph for rbtree.cxxm:

Data Structures
struct	lib::rb_augment_none
	Default augmentation — no-op. Zero overhead when not needed. More...
struct	lib::rb_node
	Intrusive red-black tree node. More...
struct	lib::rb_root
	RB-tree root. nullptr = empty tree. More...
struct	lib::rb_root_cached
	RB-tree root with cached leftmost node for O(1) begin(). More...
struct	lib::rb_root_cached::typed_iterator< Owner, member >
	Typed in-order iterator (yields Owner&). More...
struct	lib::rb_root_cached::typed_range< Owner, member >
	Typed range adaptor for range-for. More...

Functions
auto	lib::_detail::__rb_count (const rb_node *n) noexcept -> u32
template<typename Augment>
auto	lib::_detail::__rb_erase_fixup (rb_node *node, rb_node *parent, rb_root &root) noexcept -> void
	Erase rebalance fixup (called when we removed a black node).
auto	lib::_detail::__rb_rotate_set_parents (rb_node *old_n, rb_node *new_n, rb_root &root, uptr color) noexcept -> void
template<typename T>
auto	lib::rb_cmp (T a, T b) noexcept -> i32
	Trichotomy helper for the common case where Key comparison reduces to a numeric difference.
auto	lib::rb_color (const rb_node *n) noexcept -> uptr
auto	lib::rb_count (const rb_root &root) noexcept -> u32
	Count all nodes in the tree. O(n) — for diagnostics only.
template<typename Augment = rb_augment_none>
auto	lib::rb_erase (rb_node *node, rb_root &root) noexcept -> void
	Remove a node from the tree and rebalance.
template<typename Augment = rb_augment_none>
auto	lib::rb_erase_cached (rb_node *node, rb_root_cached &tree) noexcept -> void
	Erase from a cached root.
template<typename Pred>
auto	lib::rb_erase_if (rb_root &root, Pred &&pred) noexcept -> void
	Erase all nodes matching a predicate. Erase-safe internally via rb_for_each_safe.
template<typename Pred>
auto	lib::rb_erase_if_cached (rb_root_cached &tree, Pred &&pred) noexcept -> void
template<typename Key, typename Cmp>
auto	lib::rb_find (const rb_root &root, const Key &key, Cmp &&cmp) noexcept -> rb_node *
	Exact find: first node equal to key.
auto	lib::rb_first (const rb_root &root) noexcept -> rb_node *
	Return the leftmost (minimum) node, or nullptr if empty.
auto	lib::rb_first_cached (const rb_root_cached &tree) noexcept -> rb_node *
	O(1) begin for cached roots — returns the cached leftmost.
template<typename Fn>
auto	lib::rb_for_each (const rb_root &root, Fn &&fn) noexcept -> void
	In-order walk invoking fn for each node.
template<typename Fn>
auto	lib::rb_for_each_safe (rb_root &root, Fn &&fn) noexcept -> void
	Erase-safe iteration: snapshot successor before invoking fn so fn may safely call rb_erase on the yielded node.
template<typename Fn>
auto	lib::rb_for_each_safe_cached (rb_root_cached &tree, Fn &&fn) noexcept -> void
	Erase-safe iteration over a cached tree (maintains leftmost).
template<typename Key, typename Cmp>
auto	lib::rb_insert (rb_root &root, rb_node *node, const Key &key, Cmp &&cmp) noexcept -> void
	Insert a pre-allocated node via BST walk + link + rebalance.
template<typename Key, typename Cmp>
auto	lib::rb_insert_cached (rb_root_cached &tree, rb_node *node, const Key &key, Cmp &&cmp) noexcept -> void
	Insert + cached leftmost update in one call.
template<typename Augment = rb_augment_none>
auto	lib::rb_insert_color (rb_node *node, rb_root &root) noexcept -> void
	Rebalance the tree after inserting a new (red) node.
template<typename Augment = rb_augment_none>
auto	lib::rb_insert_color_cached (rb_node *node, rb_root_cached &tree, bool leftmost) noexcept -> void
	Insert + rebalance for a cached root.
auto	lib::rb_is_black (const rb_node *n) noexcept -> bool
auto	lib::rb_is_red (const rb_node *n) noexcept -> bool
auto	lib::rb_last (const rb_root &root) noexcept -> rb_node *
	Return the rightmost (maximum) node, or nullptr if empty.
auto	lib::rb_link_node (rb_node *node, rb_node *parent, rb_node **link) noexcept -> void
	Link a new node into the tree at the caller-determined position.
template<typename Key, typename Cmp>
auto	lib::rb_lower_bound (const rb_root &root, const Key &key, Cmp &&cmp) noexcept -> rb_node *
	Lower-bound search: first node for which cmp(node, key) >= 0.
auto	lib::rb_next (const rb_node *node) noexcept -> rb_node *
	Return the in-order successor, or nullptr if node is the last.
auto	lib::rb_parent (const rb_node *n) noexcept -> rb_node *
auto	lib::rb_prev (const rb_node *node) noexcept -> rb_node *
	Return the in-order predecessor, or nullptr if node is the first.
auto	lib::rb_replace_node (rb_node *old_node, rb_node *new_node, rb_root &root) noexcept -> void
	Replace a node in the tree with another node.
auto	lib::rb_replace_node_cached (rb_node *old_node, rb_node *new_node, rb_root_cached &tree) noexcept -> void
	Replace for cached root.
auto	lib::rb_set_color (rb_node *n, uptr color) noexcept -> void
auto	lib::rb_set_parent (rb_node *n, rb_node *p) noexcept -> void
auto	lib::rb_set_parent_color (rb_node *n, rb_node *p, uptr color) noexcept -> void

Variables
constexpr uptr	lib::RB_BLACK = 1
constexpr uptr	lib::RB_RED = 0

Detailed Description

Intrusive augmented red-black tree.

SPDX-License-Identifier: Apache-2.0

Function Documentation

rb_cmp()

template<typename T>

auto lib::rb_cmp ( T a, T b )->i32

inlinenodiscardexportnoexcept

Trichotomy helper for the common case where Key comparison reduces to a numeric difference.

Returns

-1 / 0 / +1 for less / equal / greater.

rb_erase()

template<typename Augment = rb_augment_none>

auto lib::rb_erase ( rb_node * node, rb_root & root )->void

exportnoexcept

Remove a node from the tree and rebalance.

Template Parameters

Augment

Augmentation policy (default = no-op).

Parameters

[in,out]	node	The node to remove.
[in,out]	root	The tree root.

rb_find()

template<typename Key, typename Cmp>

auto lib::rb_find ( const rb_root & root, const Key & key, Cmp && cmp )->rb_node *

nodiscardexportnoexcept

Exact find: first node equal to key.

Returns

Pointer to the node, or nullptr when no exact match.

rb_for_each()

template<typename Fn>

auto lib::rb_for_each ( const rb_root & root, Fn && fn )->void

exportnoexcept

In-order walk invoking fn for each node.

Template Parameters

Fn	Invocable as auto(rb_node&) -> void

rb_insert()

template<typename Key, typename Cmp>

auto lib::rb_insert ( rb_root & root, rb_node * node, const Key & key, Cmp && cmp )->void

exportnoexcept

Insert a pre-allocated node via BST walk + link + rebalance.

Walks the tree using cmp(node, key) to find the parent and link slot, then calls rb_link_node and rb_insert_color.

rb_insert_color()

template<typename Augment = rb_augment_none>

auto lib::rb_insert_color ( rb_node * node, rb_root & root )->void

exportnoexcept

Rebalance the tree after inserting a new (red) node.

Template Parameters

Augment

Augmentation policy (default = no-op).

Parameters

[in,out]	node	The newly inserted node (must be red, linked via rb_link_node).
[in,out]	root	The tree root.

rb_insert_color_cached()

template<typename Augment = rb_augment_none>

auto lib::rb_insert_color_cached ( rb_node * node, rb_root_cached & tree, bool leftmost )->void

exportnoexcept

Insert + rebalance for a cached root.

Parameters

[in,out]	node	The newly linked node (via rb_link_node).
[in,out]	tree	The cached root.
[in]	leftmost	true if this node is the new leftmost.

rb_link_node()

auto lib::rb_link_node ( rb_node * node, rb_node * parent, rb_node ** link )->void

inlineexportnoexcept

Link a new node into the tree at the caller-determined position.

Parameters

[in]	node	The new node to insert.
[in]	parent	Parent of the new node (nullptr if tree is empty).
[in]	link	Address of the parent's child pointer to set.

rb_lower_bound()

template<typename Key, typename Cmp>

auto lib::rb_lower_bound ( const rb_root & root, const Key & key, Cmp && cmp )->rb_node *

nodiscardexportnoexcept

Lower-bound search: first node for which cmp(node, key) >= 0.

Template Parameters

Cmp	Functor: auto(const rb_node*, const Key&) -> i32 returning <0 when node < key, 0 on equal, >0 > key.

rb_replace_node()

auto lib::rb_replace_node ( rb_node * old_node, rb_node * new_node, rb_root & root )->void

inlineexportnoexcept

Replace a node in the tree with another node.

new_node takes old_node's position. The caller must ensure new_node has the same key as old_node.