Skip to main content

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;