Struct kernel::rbtree::RBTree

pub struct RBTree<K, V> { /* private fields */ }

A red-black tree with owned nodes.

It is backed by the kernel C red-black trees.

Invariants

Non-null parent/children pointers stored in instances of the rb_node C struct are always valid, and pointing to a field of our internal representation of a node.

Examples

In the example below we do several operations on a tree. We note that insertions may fail if the system is out of memory.

use kernel::rbtree::RBTree;

// Create a new tree.
let mut tree = RBTree::new();

// Insert three elements.
tree.try_insert(20, 200)?;
tree.try_insert(10, 100)?;
tree.try_insert(30, 300)?;

// Check the nodes we just inserted.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&10, &100));
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert_eq!(iter.next().unwrap(), (&30, &300));
    assert!(iter.next().is_none());
}

// Print all elements.
for (key, value) in &tree {
    pr_info!("{} = {}\n", key, value);
}

// Replace one of the elements.
tree.try_insert(10, 1000)?;

// Check that the tree reflects the replacement.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&10, &1000));
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert_eq!(iter.next().unwrap(), (&30, &300));
    assert!(iter.next().is_none());
}

// Change the value of one of the elements.
*tree.get_mut(&30).unwrap() = 3000;

// Check that the tree reflects the update.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&10, &1000));
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert_eq!(iter.next().unwrap(), (&30, &3000));
    assert!(iter.next().is_none());
}

// Remove an element.
tree.remove(&10);

// Check that the tree reflects the removal.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert_eq!(iter.next().unwrap(), (&30, &3000));
    assert!(iter.next().is_none());
}

// Update all values.
for value in tree.values_mut() {
    *value *= 10;
}

// Check that the tree reflects the changes to values.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&20, &2000));
    assert_eq!(iter.next().unwrap(), (&30, &30000));
    assert!(iter.next().is_none());
}

In the example below, we first allocate a node, acquire a spinlock, then insert the node into the tree. This is useful when the insertion context does not allow sleeping, for example, when holding a spinlock.

use kernel::{rbtree::RBTree, sync::SpinLock};

fn insert_test(tree: &SpinLock<RBTree<u32, u32>>) -> Result {
    // Pre-allocate node. This may fail (as it allocates memory).
    let node = RBTree::try_allocate_node(10, 100)?;

    // Insert node while holding the lock. It is guaranteed to succeed with no allocation
    // attempts.
    let mut guard = tree.lock();
    guard.insert(node);
    Ok(())
}

In the example below, we reuse an existing node allocation from an element we removed.

use kernel::rbtree::RBTree;

// Create a new tree.
let mut tree = RBTree::new();

// Insert three elements.
tree.try_insert(20, 200)?;
tree.try_insert(10, 100)?;
tree.try_insert(30, 300)?;

// Check the nodes we just inserted.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&10, &100));
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert_eq!(iter.next().unwrap(), (&30, &300));
    assert!(iter.next().is_none());
}

// Remove a node, getting back ownership of it.
let existing = tree.remove_node(&30).unwrap();

// Check that the tree reflects the removal.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&10, &100));
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert!(iter.next().is_none());
}

// Turn the node into a reservation so that we can reuse it with a different key/value.
let reservation = existing.into_reservation();

// Insert a new node into the tree, reusing the previous allocation. This is guaranteed to
// succeed (no memory allocations).
tree.insert(reservation.into_node(15, 150));

// Check that the tree reflect the new insertion.
{
    let mut iter = tree.iter();
    assert_eq!(iter.next().unwrap(), (&10, &100));
    assert_eq!(iter.next().unwrap(), (&15, &150));
    assert_eq!(iter.next().unwrap(), (&20, &200));
    assert!(iter.next().is_none());
}

Implementations

impl<K, V> RBTree<K, V>

pub fn new() -> Self

Creates a new and empty tree.

pub fn try_insert(
    &mut self,
    key: K,
    value: V
) -> Result<Option<RBTreeNode<K, V>>> where
    K: Ord, 

Tries to insert a new value into the tree.

It overwrites a node if one already exists with the same key and returns it (containing the key/value pair). Returns None if a node with the same key didn’t already exist.

Returns an error if it cannot allocate memory for the new node.

pub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>>

Allocates memory for a node to be eventually initialised and inserted into the tree via a call to RBTree::insert.

pub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>>

Allocates and initialiases a node that can be inserted into the tree via RBTree::insert.

pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> where
    K: Ord, 

Inserts a new node into the tree.

It overwrites a node if one already exists with the same key and returns it (containing the key/value pair). Returns None if a node with the same key didn’t already exist.

This function always succeeds.

pub fn get(&self, key: &K) -> Option<&V> where
    K: Ord, 

Returns a reference to the value corresponding to the key.

pub fn get_mut(&mut self, key: &K) -> Option<&mut V> where
    K: Ord, 

Returns a mutable reference to the value corresponding to the key.

pub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>> where
    K: Ord, 

Removes the node with the given key from the tree.

It returns the node that was removed if one exists, or None otherwise.

pub fn remove(&mut self, key: &K) -> Option<V> where
    K: Ord, 

Removes the node with the given key from the tree.

It returns the value that was removed if one exists, or None otherwise.

pub fn iter(&self) -> RBTreeIterator<'_, K, V>

Returns an iterator over the tree nodes, sorted by key.

pub fn iter_mut(&mut self) -> RBTreeIteratorMut<'_, K, V>

Returns a mutable iterator over the tree nodes, sorted by key.

pub fn keys(&self) -> impl Iterator<Item = &K>

Returns an iterator over the keys of the nodes in the tree, in sorted order.

pub fn values(&self) -> impl Iterator<Item = &V>

Returns an iterator over the values of the nodes in the tree, sorted by key.

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>

Returns a mutable iterator over the values of the nodes in the tree, sorted by key.

Trait Implementations

impl<K, V> Default for RBTree<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Drop for RBTree<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V> IntoIterator for &'a RBTree<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = RBTreeIterator<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut RBTree<K, V>

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = RBTreeIteratorMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.