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
auto	begin () const noexcept -> typed_iterator< Owner, member >
static auto	copy (rb_node , rb_node ) noexcept -> void
auto	empty () const noexcept -> bool
auto	empty () const noexcept -> bool
auto	end () const noexcept -> typed_iterator< Owner, member >
template<typename Owner, rb_node Owner::* member>
auto	iter () const noexcept -> typed_range< Owner, member >
	Get a typed iterable range over the tree.
auto	operator!= (const typed_iterator &o) const noexcept -> bool
auto	operator* () const noexcept -> const Owner &
auto	operator* () noexcept -> Owner &
auto	operator++ () noexcept -> typed_iterator &
auto	operator++ (int) noexcept -> typed_iterator
auto	operator-> () noexcept -> Owner *
auto	operator== (const typed_iterator &o) const noexcept -> bool
static auto	propagate (rb_node *) 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
static auto	rotate (rb_node , rb_node ) noexcept -> void
constexpr	typed_iterator (rb_node *cur) noexcept

Variables
uptr	__parent_color {}
	Parent pointer \| color bit.
rb_node *	current
rb_node *	first
rb_node *	left {}
	Left child (nullptr = leaf).
rb_node *	leftmost {nullptr}
rb_node *	node {nullptr}
constexpr uptr	lib::RB_BLACK = 1
constexpr uptr	lib::RB_RED = 0
rb_node *	right {}
	Right child (nullptr = leaf).
rb_root	root {}

Files
file	lib/rbtree.cxxm
	Intrusive augmented red-black tree.

ZXFoundation™ 26h2

Data Structures

Functions

Variables

Files