Expand description
§Intrusive Red-Black Tree (no_std)
A high-performance, zero-allocation, intrusive Red-Black Tree implementation
engineered specifically for #![no_std] systems, operating system kernels, bare-metal
runtimes, and low-level memory allocators.
Unlike standard container structures (such as std::collections::BTreeMap), this crate uses an intrusive layout.
Nodes are allocated and owned by the caller (e.g., embedded directly inside page descriptors, Virtual Memory Area
structs, or slab headers), and linked into the tree via pointer references (NonNull<T>).
§Key Architectural Features
- Intrusive Trait Abstraction (
RBNode): decouples memory layout from tree logic. ImplementRBNodeon any custom struct to store metadata directly within your allocation. - Zero Heap Allocation: operations (
insert,delete,search,iter) perform zero internal allocations or dynamic memory management. - Sentinel Node Pattern (
nil): uses a dedicated sentinel node representing leaves and tree boundaries. This eliminates null-pointer branch checks in critical balance/rotation loops. - O(1) Cached Minimum: tracks the leftmost node dynamically during insertions and deletions for instant O(1) minimum key access and O(1) start for in-order iteration.
- Flexible Querying (
Borrow<Q>): enables zero-allocation searches on complex keys (e.g., querying a node with aStringkey using a borrowed&str). - Bitwise Optimized Rotations: standardizes directional logic (
0for left,1for right) using bitwise operations (dir ^ 1), reducing code duplicate paths for symmetric rebalancing logic.
§Red-Black Tree Invariants
Every tree managed by RBTree strictly maintains the 5 fundamental Red-Black invariants across all operations:
- Node Color: Every node is either
Color::REDorColor::BLACK. - Root Property: The root node is always
Color::BLACK. - Leaf Property: Every leaf (represented by the sentinel
nilnode) isColor::BLACK. - Red Violation Absence: If a node is
Color::RED, both of its children must beColor::BLACK(no two adjacent red nodes). - Black Height Uniformity: Every path from a given node to any of its descendant
nilleaves contains the exact same number of black nodes.
§Algorithmic Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
Search / Query (search, exist) | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ |
Insertion (insert) | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ |
Deletion (delete) | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ |
Pop Minimum (delete_min) | $\mathcal{O}(\log N)$ worst, $\mathcal{O}(1)$ expected | $\mathcal{O}(1)$ |
Access Minimum Node (min_node) | $\mathcal{O}(1)$ | $\mathcal{O}(1)$ |
In-order Iteration (iter, next_node) | $\mathcal{O}(1)$ amortized per step | $\mathcal{O}(1)$ |
§Safety & Ownership Obligations
Because this crate works directly with raw NonNull<T> pointers:
- Pinning & Address Stability: Nodes inserted into an
RBTreemust remain at stable memory locations until unlinked or deleted. Moving a node in memory invalidates tree pointers. - Lifetime Management: Deallocating a node while it is still linked inside an active
RBTreecauses Undefined Behavior (UB). Always callRBTree::deleteorRBTree::delete_minbefore dropping a node. - Sentinel Validity: The sentinel node (
nil) passed toRBTree::newmust remain valid and initialized for the entire lifespan of the tree.
§Complete & Testable Example
The following testable example demonstrates defining a custom memory node, implementing RBNode,
setting up the tree with a sentinel node, performing insertions, searching, iterating in-order, and clean deletion.
use core::ptr::NonNull;
use intrusive_red_black_tree::{Color, RBNode, RBTree};
// 1. Define your domain struct containing tree linkage pointers.
#[derive(Debug)]
pub struct VmaNode {
pub start_addr: usize,
pub end_addr: usize,
pub color: Color,
pub parent: NonNull<Self>,
pub children: [NonNull<Self>; 2],
}
impl VmaNode {
/// Helper to create a heap/leak-allocated node for testing.
pub fn new(start_addr: usize, end_addr: usize, sentinel: NonNull<Self>) -> NonNull<Self> {
let boxed = Box::new(Self {
start_addr,
end_addr,
color: Color::RED,
parent: sentinel,
children: [sentinel, sentinel],
});
NonNull::from(Box::leak(boxed))
}
/// Helper to construct a valid sentinel node.
pub fn create_sentinel() -> NonNull<Self> {
let sentinel_raw = Box::leak(Box::new(Self {
start_addr: 0,
end_addr: 0,
color: Color::BLACK,
parent: NonNull::dangling(),
children: [NonNull::dangling(), NonNull::dangling()],
}));
let mut ptr = NonNull::from(sentinel_raw);
unsafe {
ptr.as_mut().parent = ptr;
ptr.as_mut().children = [ptr, ptr];
}
ptr
}
/// Safely clean up leaked heap nodes in test/drop routines.
pub unsafe fn free(ptr: NonNull<Self>) {
unsafe { drop(Box::from_raw(ptr.as_ptr())) };
}
}
// 2. Implement the `RBNode` trait for your structure.
impl RBNode for VmaNode {
type NodePtr = NonNull<VmaNode>;
type Key = usize;
fn set_color(mut node_ptr: Self::NodePtr, color: Color) {
unsafe { node_ptr.as_mut() }.color = color;
}
fn get_color(node_ptr: Self::NodePtr) -> Color {
unsafe { node_ptr.as_ref() }.color
}
fn set_parent(mut node_ptr: Self::NodePtr, parent: Self::NodePtr) {
unsafe { node_ptr.as_mut() }.parent = parent;
}
fn get_parent(node_ptr: Self::NodePtr) -> Self::NodePtr {
unsafe { node_ptr.as_ref() }.parent
}
fn set_child(mut node_ptr: Self::NodePtr, dir: usize, child: Self::NodePtr) {
unsafe { node_ptr.as_mut() }.children[dir] = child;
}
fn get_child(node_ptr: Self::NodePtr, dir: usize) -> Self::NodePtr {
unsafe { node_ptr.as_ref() }.children[dir]
}
fn get_key<'a>(node_ptr: Self::NodePtr) -> &'a Self::Key {
unsafe { &node_ptr.as_ref().start_addr }
}
fn dangling() -> Self::NodePtr {
NonNull::dangling()
}
}
// 3. Drive tree operations.
fn main() {
let sentinel = VmaNode::create_sentinel();
let mut tree : RBTree<VmaNode> = RBTree::new(sentinel);
// Allocate nodes
let node1 = VmaNode::new(0x1000, 0x2000, sentinel);
let node2 = VmaNode::new(0x0500, 0x0FFF, sentinel);
let node3 = VmaNode::new(0x3000, 0x5000, sentinel);
// Insert nodes
assert!(tree.insert(node1));
assert!(tree.insert(node2));
assert!(tree.insert(node3));
// Duplicate insertion should fail
assert!(!tree.insert(node1));
// Query minimum
assert_eq!(tree.min_node(), node2);
// Zero-allocation search
let found = tree.search(&0x1000);
assert_eq!(found, Some(node1));
assert!(tree.exist(&0x3000));
assert!(!tree.exist(&0x9000));
// In-order iteration (returns nodes sorted by key: 0x0500 -> 0x1000 -> 0x3000)
let keys: Vec<usize> = tree.iter().map(|n| *VmaNode::get_key(n)).collect();
assert_eq!(keys, vec![0x0500, 0x1000, 0x3000]);
// Deletion
let deleted = tree.delete(&0x1000);
assert_eq!(deleted, Some(node1));
assert!(!tree.exist(&0x1000));
// Free allocations
unsafe {
VmaNode::free(node1);
VmaNode::free(node2);
VmaNode::free(node3);
VmaNode::free(sentinel);
}
}Structs§
- RBTree
- An intrusive Red-Black Tree backed by raw pointers (
NonNull<T>).
Enums§
Traits§
- RBNode
- Abstraction trait for intrusive Red-Black Tree nodes.