Two red-black trees:
- Allocating nodes from a slab
- Unsafe mut pointers
The trees take keys representing satellite data of type T: PartialOrd
. It should be trivial to add values to use as a K/V store.
The pointer implementation is completely unsafe - a real one should use Box or Rc. It was just shoved in for comparisons' sake. The real showcase is the slab implementation which is a neat pattern inspired by https://gist.github.com/stjepang/07fbf88afa824e11796e51ea2f68bd5a and https://www.reddit.com/r/rust/comments/7zsy72/writing_a_doubly_linked_list_in_rust_is_easy/
The feature MaybeUninit has been especially useful in the red-black tree, given its black-colored Nil Sentinel. Every single node in the tree has a valid key, parent, and children pointing to either other real nodes or the Nil Sentinel. This is how most of the code (which I copied from CLRS) works.
It's in fact only the nil sentinel itself that has unsoundness in its contents.
Slab:
const NULL: usize = !0; // an impossible index = usize max
unsafe {
// slab entry 0 is the nil sentinel
let nil_sentinel = rb.slab.insert(Node::new(
mem::MaybeUninit::<T>::uninit().assume_init(),
NULL,
));
}
Pointer:
unsafe fn nil_sentinel() -> *mut Node<T> {
new_node_ptr(
mem::MaybeUninit::<T>::uninit().assume_init(),
ptr::null_mut(),
)
}
The alternative is T: Default
trait, to use a key T::default()
for the nil sentinel, but I preferred to minimize the traits required for T.
Also, I don't need Option<>
pointers since every node (except the nil sentinel) always has pointers to valid children and parent (the nil sentinel).