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

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

Creates a new and empty tree.

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.

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

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

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.

Returns a reference to the value corresponding to the key.

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

Removes the node with the given key from the tree.

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

Removes the node with the given key from the tree.

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

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

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

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

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

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

Trait Implementations

Returns the “default value” for a type. Read more

Executes the destructor for this type. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.

This documentation is an old archive. Please see https://rust.docs.kernel.org instead.