Crate embed_avl 

An intrusive AVL tree implementation.

The algorithm origin from open-zfs

benchmarks: https://github.com/NaturalIO/embed-collections-rs/wiki

The ordering of avl tree is defined by AvlItem trait. There’re two usage:

• borrow field as key from the node struct
• impl Ord for struct itself

We provide Entry API to achieve CursorMut like ability, you can use the following combination:

• AvlTree::entry, AvlTree::first_entry, AvlTree::last_entry
• OccupiedEntry::peek_prev, OccupiedEntry::peek_next
• OccupiedEntry::move_prev, OccupiedEntry::move_next
• OccupiedEntry::insert_prev_unchecked, OccupiedEntry::insert_next_unchecked ( does not change current OccupiedEntry)
• OccupiedEntry::insert_move_prev_unchecked, OccupiedEntry::insert_move_next_unchecked] (return the newlly inserted OccupiedEntry, reduce additional seek cost)
• OccupiedEntry::remove_prev , OccupiedEntry::remove_next (does not change current OccupiedEntry)

Refer to the example of AvlItem document.

Examples

Using Box to search and remove by key

use embed_avl::{AvlTree, AvlItem, AvlNode, Entry, impl_ord_with_borrow};
use core::cell::UnsafeCell;
use core::borrow::Borrow;
extern crate format_attr;

#[derive(format_attr::DebugAttr)]
#[fmt("MyNode {value}")]
struct MyNode {
    value: i32,
    avl_node: UnsafeCell<AvlNode<MyNode, ()>>,
}

impl Borrow<i32> for MyNode {
    fn borrow(&self) -> &i32 {
        &self.value
    }
}

unsafe impl AvlItem<()> for MyNode {
    fn get_node(&self) -> &mut AvlNode<MyNode, ()> {
        unsafe { &mut *self.avl_node.get() }
    }
}

impl_ord_with_borrow!(MyNode, i32);

let mut tree = AvlTree::<Box<MyNode>, ()>::new();
tree.add(Box::new(MyNode { value: 10, avl_node: UnsafeCell::new(Default::default()) })).expect("add ok");

// Search and remove
if let Some(node) = tree.remove_by_key::<i32>(&10i32) {
    assert_eq!(node.value, 10);
}
assert!(tree.is_empty());

Using Arc to search and remove by node

use embed_avl::{AvlTree, AvlItem, AvlNode, Entry, impl_ord_with_borrow};
use core::cell::UnsafeCell;
use core::borrow::Borrow;
extern crate format_attr;
extern crate alloc;
use alloc::sync::Arc;

#[derive(format_attr::DebugAttr)]
#[fmt("MyNode {value}")]
struct MyNode {
    value: i32,
    avl_node: UnsafeCell<AvlNode<MyNode, ()>>,
}

impl Borrow<i32> for MyNode {
    fn borrow(&self) -> &i32 {
        &self.value
    }
}

unsafe impl AvlItem<()> for MyNode {
    fn get_node(&self) -> &mut AvlNode<MyNode, ()> {
        unsafe { &mut *self.avl_node.get() }
    }
}

impl_ord_with_borrow!(MyNode, i32);

// Using `Arc` for multiple ownership
// remove_ref only available to `Arc` and `Rc`

let mut tree = AvlTree::<Arc<MyNode>, ()>::new();
let node = Arc::new(MyNode { value: 42, avl_node: UnsafeCell::new(Default::default()) });

// Alternative way of insert
if let Entry::Vacant(ent) = tree.entry(node.value) {
    ent.insert_node(node.clone());
} else {
    unreachable!();
}
assert_eq!(tree.len(), 1);

// Remove by reference (detach from avl tree)
tree.remove(&node);
assert_eq!(tree.len(), 0);

Efficient bulk insertion

use embed_avl::{AvlTree, AvlItem, AvlNode, Entry, impl_ord_with_borrow};
use core::cell::UnsafeCell;
use core::borrow::Borrow;
extern crate format_attr;

#[derive(format_attr::DebugAttr)]
#[fmt("MyNode {value}")]
struct MyNode {
    value: i32,
    avl_node: UnsafeCell<AvlNode<MyNode, ()>>,
}

impl Borrow<i32> for MyNode {
    fn borrow(&self) -> &i32 {
        &self.value
    }
}

unsafe impl AvlItem<()> for MyNode {
    fn get_node(&self) -> &mut AvlNode<MyNode, ()> {
        unsafe { &mut *self.avl_node.get() }
    }
}

impl_ord_with_borrow!(MyNode, i32);

let mut tree = AvlTree::<Box<MyNode>, ()>::new();
let mut ent = tree.last_entry();
for i in 0..100 {
    ent = unsafe{ent.append_unchecked(
        Box::new(MyNode { value: i, avl_node: UnsafeCell::new(Default::default()) })
    )};
}

// Search
if let Some(node) = tree.get::<i32>(&10) {
    assert_eq!(node.value, 10);
}
assert_eq!(tree.len(), 100);

Macros

impl_ord_with_borrow

Implement Ord with Borrow<K>

trace_log

logging macro for development

Structs

AvlIntoIter

AvlIter

Return a reference of P (you can P.clone() of P has Clone)

AvlNode

AvlNodeRef

A Reference to P

AvlTree

An intrusive AVL tree (balanced binary search tree).

First

Use to mark first entry

Last

Use to mark last entry

OccupiedEntry

VacantEntry

Examples

Enums

Entry

Result of a search operation in an AvlTree.

Traits

AvlItem

A trait to return internal mutable AvlNode for specified list.