A Rust implementation of Weak AVL Trees, primarily for use in the k23 operating system.

Weak AVL trees are self-balancing binary search trees introduced by Haeupler, Sen & Tarjan (2015) that are similar to red-black trees but better in several ways. In particular, their worst-case height is that of AVL trees (~1.44log2(n) as opposed to 2log2(n) for red-black trees), while tree restructuring operations after deletions are even more efficient than red-black trees. Additionally, this implementation is intrusive meaning node data (pointers to other nodes etc.) are stored within participating values, rather than being allocated and owned by the tree itself.

This crate is self-contained, (somewhat) fuzzed, and fully no_std.

Example

The following example shows an implementation of a simple intrusive WAVL tree node (MyNode) and how it can be used with WAVLTree, notice how - due to the intrusive nature of the data structure - there is quite a lot more setup required, compared to e.g. a BTreeMap or HashMap.

use alloc::boxed::Box;
use core::mem::offset_of;
use core::pin::Pin;
use core::ptr::NonNull;

#[derive(Default)]
struct MyNode {
    links: wavltree::Links<Self>,
    value: usize,
}

impl MyNode {
    pub fn new(value: usize) -> Self {
        let mut this = Self::default();
        this.value = value;
        this
    }
}

// Participation in an intrusive collection requires a bit more effort
// on the values's part.
unsafe impl wavltree::Linked for MyNode {
    /// The owning handle type, must ensure participating values are pinned in memory.
    type Handle = Pin<Box<Self>>;
    /// The key type by which entries are identified.
    type Key = usize;

    /// Convert a `Handle` into a raw pointer to `Self`,
    /// taking ownership of it in the process.
    fn into_ptr(handle: Self::Handle) -> NonNull<Self> {
        unsafe { NonNull::from(Box::leak(Pin::into_inner_unchecked(handle))) }
    }

    /// Convert a raw pointer back into an owned `Handle`.
    unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle {
        Pin::new_unchecked(Box::from_raw(ptr.as_ptr()))
    }

    /// Return the links of the node pointed to by ptr.
    unsafe fn links(ptr: NonNull<Self>) -> NonNull<wavltree::Links<Self>> {
        ptr.map_addr(|addr| {
            let offset = offset_of!(Self, links);
            addr.checked_add(offset).unwrap()
        })
        .cast()
    }

    /// Retrieve the key identifying this node within the collection.
    fn get_key(&self) -> &Self::Key {
        &self.value
   }
}

fn main() {
    let mut tree = wavltree::WAVLTree::new();
    tree.insert(Box::pin(MyNode::new(42)));
    tree.insert(Box::pin(MyNode::new(17)));
    tree.insert(Box::pin(MyNode::new(9)));

    tree.remove(&9);

    let _entry = tree.entry(&42);
}

When To Use This

• want binary search - WAVL trees are sorted collections that are efficient to search.
• search more than you edit - WAVL trees offer better search complexity than red-black trees at the cost of being slightly more complex.
• want to avoid hidden allocations - Because node data is stored inside participating values, an element can be added without requiring additional heap allocations.
• have to allocator at all - When elements have fixed memory locations (such as pages in a page allocator, static s), they can be added without any allocations at all.
• want flexibility - Intrusive data structures allow elements to participate in many different collections at the same time, e.g. a node might both be linked to a WAVLTree and an intrusive doubly-linked list at the same time.

In short, WAVLTrees are a good choice for no_std binary search trees such as inside page allocators.

When Not To Use This

• need to store primitives - Intrusive collections require elements to store the node data, which excludes primitives such as strings or numbers, since they can't hold this metadata.
• can't use unsafe - Both this implementation and code consuming it require unsafe, the Linked trait is unsafe to implement since it requires implementors uphold special invariants.
• you are unsure if you need this - Search trees and especially intrusive ones like this are niche data structures, only use them if you are sure you need them. Very likely doing binary search on a sorted Vec or using a HashMap works better for your use case.

Cargo Features

The following features are available:

References

This paper implements the Weak AVL tree algorithm in Rust as described in Haeupler, Sen & Tarjan (2015), with additional references taken from Phil Vachons WAVL tree C implementation as well as the implementation in the Fuchsia base library.

Inspiration for the design of intrusive APIs in Rust has been taken from cordyceps and intrusive-collections