Module avl 

Available on crate feature avl only.

An intrusive AVL tree implementation.

The algorithm origin from open-zfs

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

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

Refer to the example of AvlItem document.

Examples

Using Box to search and remove by key

use embed_collections::avl::{AvlTree, AvlItem, AvlNode};
use core::cell::UnsafeCell;
use core::cmp::Ordering;
extern crate alloc;
use alloc::sync::Arc;

struct MyNode {
    value: i32,
    avl_node: UnsafeCell<AvlNode<MyNode, ()>>,
}

unsafe impl AvlItem<()> for MyNode {

    type Key = i32;

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

    fn borrow_key(&self) -> &Self::Key {
        &self.value
    }
}

// A boxed example

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

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

// 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()) });

tree.add(node.clone());
assert_eq!(tree.len(), 1);

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

Structs

AvlDrain

AvlIter

AvlNode

AvlSearchResult

Result of a search operation in an AvlTree.

AvlTree

An intrusive AVL tree (balanced binary search tree).

Enums

AvlDirection

Traits

AvlItem

A trait to return internal mutable AvlNode for specified list.

Type Aliases

AvlCmpFunc