Struct 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.

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::{alloc::flags, rbtree::{RBTree, RBTreeNode, RBTreeNodeReservation}};

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

// Insert three elements.
tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;

// Check the nodes we just inserted.
{
    assert_eq!(tree.get(&10).unwrap(), &100);
    assert_eq!(tree.get(&20).unwrap(), &200);
    assert_eq!(tree.get(&30).unwrap(), &300);
}

// Iterate over 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_create_and_insert(10, 1000, flags::GFP_KERNEL)?;

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

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::{alloc::flags, rbtree::{RBTree, RBTreeNode}, sync::SpinLock};

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

    // 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::{alloc::flags, rbtree::{RBTree, RBTreeNodeReservation}};

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

// Insert three elements.
tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;

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

// Create a preallocated reservation that we can re-use later.
let reservation = RBTreeNodeReservation::new(flags::GFP_KERNEL)?;

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

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.

Implementations

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

pub fn new() -> Self

Creates a new and empty tree.

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

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

pub fn iter_mut(&mut self) -> IterMut<'_, 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.

pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>>

Returns a cursor over the tree nodes, starting with the smallest key.

pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>>

Returns a cursor over the tree nodes, starting with the largest key.

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

where K: Ord,

pub fn try_create_and_insert( &mut self, key: K, value: V, flags: Flags, ) -> Result<Option<RBTreeNode<K, V>>>

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 insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>>

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 entry(&mut self, key: K) -> Entry<'_, K, V>

Gets the given key’s corresponding entry in the map for in-place manipulation.

pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>>

Used for accessing the given node, if it exists.

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

Returns a reference to the value corresponding to the key.

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

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

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

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>

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 cursor_lower_bound(&mut self, key: &K) -> Option<Cursor<'_, K, V>>

where K: Ord,

Returns a cursor over the tree nodes based on the given key.

If the given key exists, the cursor starts there. Otherwise it starts with the first larger key in sort order. If there is no larger key, it returns None.

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 = Iter<'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 = IterMut<'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<K: Send, V: Send> Send for RBTree<K, V>

impl<K: Sync, V: Sync> Sync for RBTree<K, V>