Announcing `intrusive_splay_tree`: an intrusive, zero-allocation, zero-move, top-down, #![no_std]-compatible splay tree implementation

announcements
1

From the README:

Splay trees are self-adjusting, meaning that operating on an element (for
example, doing a find or an insert) rebalances the tree in such a way
that the element becomes the root. This means that subsequent operations on
that element are O(1) as long as no other element is operated on in the
meantime.

Implementation and Goals

  • Intrusive: The space for the subtree pointers is stored inside the
    element type. In non-intrusive trees, we would have a node type that
    contains the subtree pointers and either a pointer to the element or we
    would move the element into the node. The intrusive design inverts the
    relationship, so that the elements hold the subtree pointers within
    themselves.

  • Freedom from allocations and moves: The intrusive design enables this
    implementation to fully avoid both allocations and moving elements in
    memory. Since the space for subtree pointers already exists in the element,
    no allocation is necessary, just a handful of pointer writes. Therefore,
    this implementation can be used in constrained environments that don't have
    access to an allocator (e.g. some embedded devices or within a signal
    handler) and with types that can't move in memory (e.g. pthread_mutex_t).

  • Small code size: This implementation is geared towards small code
    size, and uses trait objects internally to avoid the code bloat induced by
    monomorphization. This implementation is suitable for targeting WebAssembly,
    where code is downloaded over the network, and code bloat delays Web page
    loading.

  • Nodes do not have parent pointers: An intrusive node is only two words
    in size: left and right sub tree pointers. There are no parent pointers,
    which would require another word of overhead. To meet this goal, the
    implementation uses the "top-down" variant of splay trees.

Click through to the full README for more and example usage!

9 Likes