intrusive_red_black_tree/lib.rs
1#![no_std]
2
3//! # Intrusive Red-Black Tree (`no_std`)
4//!
5//! A high-performance, zero-allocation, intrusive Red-Black Tree implementation
6//! engineered specifically for `#![no_std]` systems, operating system kernels, bare-metal
7//! runtimes, and low-level memory allocators.
8//!
9//! Unlike standard container structures (such as `std::collections::BTreeMap`), this crate uses an **intrusive layout**.
10//! Nodes are allocated and owned by the caller (e.g., embedded directly inside page descriptors, Virtual Memory Area
11//! structs, or slab headers), and linked into the tree via pointer references (`NonNull<T>`).
12//!
13//! ---
14//!
15//! ## Key Architectural Features
16//!
17//! * **Intrusive Trait Abstraction ([`RBNode`]):** decouples memory layout from tree logic. Implement [`RBNode`] on any custom struct to store metadata directly within your allocation.
18//! * **Zero Heap Allocation:** operations (`insert`, `delete`, `search`, `iter`) perform zero internal allocations or dynamic memory management.
19//! * **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.
20//! * **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.
21//! * **Flexible Querying (`Borrow<Q>`):** enables zero-allocation searches on complex keys (e.g., querying a node with a `String` key using a borrowed `&str`).
22//! * **Bitwise Optimized Rotations:** standardizes directional logic (`0` for left, `1` for right) using bitwise operations (`dir ^ 1`), reducing code duplicate paths for symmetric rebalancing logic.
23//!
24//! ---
25//!
26//! ## Red-Black Tree Invariants
27//!
28//! Every tree managed by [`RBTree`] strictly maintains the 5 fundamental Red-Black invariants across all operations:
29//!
30//! 1. **Node Color:** Every node is either [`Color::RED`] or [`Color::BLACK`].
31//! 2. **Root Property:** The root node is always [`Color::BLACK`].
32//! 3. **Leaf Property:** Every leaf (represented by the sentinel `nil` node) is [`Color::BLACK`].
33//! 4. **Red Violation Absence:** If a node is [`Color::RED`], both of its children must be [`Color::BLACK`] (no two adjacent red nodes).
34//! 5. **Black Height Uniformity:** Every path from a given node to any of its descendant `nil` leaves contains the exact same number of black nodes.
35//!
36//! ---
37//!
38//! ## Algorithmic Complexity
39//!
40//! | Operation | Time Complexity | Space Complexity |
41//! | :--- | :--- | :--- |
42//! | Search / Query (`search`, `exist`) | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ |
43//! | Insertion (`insert`) | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ |
44//! | Deletion (`delete`) | $\mathcal{O}(\log N)$ | $\mathcal{O}(1)$ |
45//! | Pop Minimum (`delete_min`) | $\mathcal{O}(\log N)$ worst, $\mathcal{O}(1)$ expected | $\mathcal{O}(1)$ |
46//! | Access Minimum Node (`min_node`) | $\mathcal{O}(1)$ | $\mathcal{O}(1)$ |
47//! | In-order Iteration (`iter`, `next_node`) | $\mathcal{O}(1)$ amortized per step | $\mathcal{O}(1)$ |
48//!
49//! ---
50//!
51//! ## Safety & Ownership Obligations
52//!
53//! Because this crate works directly with raw `NonNull<T>` pointers:
54//!
55//! 1. **Pinning & Address Stability:** Nodes inserted into an [`RBTree`] must remain at stable memory locations until unlinked or deleted. Moving a node in memory invalidates tree pointers.
56//! 2. **Lifetime Management:** Deallocating a node while it is still linked inside an active [`RBTree`] causes Undefined Behavior (UB). Always call [`RBTree::delete`] or [`RBTree::delete_min`] before dropping a node.
57//! 3. **Sentinel Validity:** The sentinel node (`nil`) passed to [`RBTree::new`] must remain valid and initialized for the entire lifespan of the tree.
58//!
59//! ---
60//!
61//! ## Complete & Testable Example
62//!
63//! The following testable example demonstrates defining a custom memory node, implementing [`RBNode`],
64//! setting up the tree with a sentinel node, performing insertions, searching, iterating in-order, and clean deletion.
65//!
66//! ```rust
67//! use core::ptr::NonNull;
68//! use intrusive_red_black_tree::{Color, RBNode, RBTree};
69//!
70//! // 1. Define your domain struct containing tree linkage pointers.
71//! #[derive(Debug)]
72//! pub struct VmaNode {
73//! pub start_addr: usize,
74//! pub end_addr: usize,
75//! pub color: Color,
76//! pub parent: NonNull<Self>,
77//! pub children: [NonNull<Self>; 2],
78//! }
79
80//! impl VmaNode {
81//! /// Helper to create a heap/leak-allocated node for testing.
82//! pub fn new(start_addr: usize, end_addr: usize, sentinel: NonNull<Self>) -> NonNull<Self> {
83//! let boxed = Box::new(Self {
84//! start_addr,
85//! end_addr,
86//! color: Color::RED,
87//! parent: sentinel,
88//! children: [sentinel, sentinel],
89//! });
90//! NonNull::from(Box::leak(boxed))
91//! }
92//!
93//! /// Helper to construct a valid sentinel node.
94//! pub fn create_sentinel() -> NonNull<Self> {
95//! let sentinel_raw = Box::leak(Box::new(Self {
96//! start_addr: 0,
97//! end_addr: 0,
98//! color: Color::BLACK,
99//! parent: NonNull::dangling(),
100//! children: [NonNull::dangling(), NonNull::dangling()],
101//! }));
102//! let mut ptr = NonNull::from(sentinel_raw);
103//! unsafe {
104//! ptr.as_mut().parent = ptr;
105//! ptr.as_mut().children = [ptr, ptr];
106//! }
107//! ptr
108//! }
109//!
110//! /// Safely clean up leaked heap nodes in test/drop routines.
111//! pub unsafe fn free(ptr: NonNull<Self>) {
112//! unsafe { drop(Box::from_raw(ptr.as_ptr())) };
113//! }
114//! }
115//!
116//! // 2. Implement the `RBNode` trait for your structure.
117//! impl RBNode for VmaNode {
118//! type NodePtr = NonNull<VmaNode>;
119//! type Key = usize;
120//!
121//! fn set_color(mut node_ptr: Self::NodePtr, color: Color) {
122//! unsafe { node_ptr.as_mut() }.color = color;
123//! }
124//!
125//! fn get_color(node_ptr: Self::NodePtr) -> Color {
126//! unsafe { node_ptr.as_ref() }.color
127//! }
128//!
129//! fn set_parent(mut node_ptr: Self::NodePtr, parent: Self::NodePtr) {
130//! unsafe { node_ptr.as_mut() }.parent = parent;
131//! }
132//!
133//! fn get_parent(node_ptr: Self::NodePtr) -> Self::NodePtr {
134//! unsafe { node_ptr.as_ref() }.parent
135//! }
136//!
137//! fn set_child(mut node_ptr: Self::NodePtr, dir: usize, child: Self::NodePtr) {
138//! unsafe { node_ptr.as_mut() }.children[dir] = child;
139//! }
140//!
141//! fn get_child(node_ptr: Self::NodePtr, dir: usize) -> Self::NodePtr {
142//! unsafe { node_ptr.as_ref() }.children[dir]
143//! }
144//!
145//! fn get_key<'a>(node_ptr: Self::NodePtr) -> &'a Self::Key {
146//! unsafe { &node_ptr.as_ref().start_addr }
147//! }
148//!
149//! fn dangling() -> Self::NodePtr {
150//! NonNull::dangling()
151//! }
152//! }
153//!
154//! // 3. Drive tree operations.
155//! fn main() {
156//! let sentinel = VmaNode::create_sentinel();
157//! let mut tree : RBTree<VmaNode> = RBTree::new(sentinel);
158//!
159//! // Allocate nodes
160//! let node1 = VmaNode::new(0x1000, 0x2000, sentinel);
161//! let node2 = VmaNode::new(0x0500, 0x0FFF, sentinel);
162//! let node3 = VmaNode::new(0x3000, 0x5000, sentinel);
163//!
164//! // Insert nodes
165//! assert!(tree.insert(node1));
166//! assert!(tree.insert(node2));
167//! assert!(tree.insert(node3));
168//!
169//! // Duplicate insertion should fail
170//! assert!(!tree.insert(node1));
171//!
172//! // Query minimum
173//! assert_eq!(tree.min_node(), node2);
174//!
175//! // Zero-allocation search
176//! let found = tree.search(&0x1000);
177//! assert_eq!(found, Some(node1));
178//! assert!(tree.exist(&0x3000));
179//! assert!(!tree.exist(&0x9000));
180//!
181//! // In-order iteration (returns nodes sorted by key: 0x0500 -> 0x1000 -> 0x3000)
182//! let keys: Vec<usize> = tree.iter().map(|n| *VmaNode::get_key(n)).collect();
183//! assert_eq!(keys, vec![0x0500, 0x1000, 0x3000]);
184//!
185//! // Deletion
186//! let deleted = tree.delete(&0x1000);
187//! assert_eq!(deleted, Some(node1));
188//! assert!(!tree.exist(&0x1000));
189
190//! // Free allocations
191//! unsafe {
192//! VmaNode::free(node1);
193//! VmaNode::free(node2);
194//! VmaNode::free(node3);
195//! VmaNode::free(sentinel);
196//! }
197//! }
198//! ```
199
200mod color;
201mod rb_iter;
202mod rb_node;
203mod rb_tree;
204
205pub use color::Color;
206pub use rb_node::RBNode;
207pub use rb_tree::RBTree;