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
sourceimpl<K, V> RBTree<K, V>
impl<K, V> RBTree<K, V>
sourcepub fn try_insert(&mut self, key: K, value: V) -> Result<Option<RBTreeNode<K, V>>>where
K: Ord,
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.
sourcepub fn try_reserve_node() -> Result<RBTreeNodeReservation<K, V>>
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
.
sourcepub fn try_allocate_node(key: K, value: V) -> Result<RBTreeNode<K, V>>
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
.
sourcepub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>>where
K: Ord,
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.
sourcepub fn get(&self, key: &K) -> Option<&V>where
K: Ord,
pub fn get(&self, key: &K) -> Option<&V>where
K: Ord,
Returns a reference to the value corresponding to the key.
sourcepub fn get_mut(&mut self, key: &K) -> Option<&mut V>where
K: Ord,
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.
sourcepub fn remove_node(&mut self, key: &K) -> Option<RBTreeNode<K, V>>where
K: Ord,
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.
sourcepub fn remove(&mut self, key: &K) -> Option<V>where
K: Ord,
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.
sourcepub fn iter(&self) -> RBTreeIterator<'_, K, V>ⓘNotable traits for RBTreeIterator<'a, K, V>impl<'a, K, V> Iterator for RBTreeIterator<'a, K, V> type Item = (&'a K, &'a V);
pub fn iter(&self) -> RBTreeIterator<'_, K, V>ⓘNotable traits for RBTreeIterator<'a, K, V>impl<'a, K, V> Iterator for RBTreeIterator<'a, K, V> type Item = (&'a K, &'a V);
Returns an iterator over the tree nodes, sorted by key.
sourcepub fn iter_mut(&mut self) -> RBTreeIteratorMut<'_, K, V>ⓘNotable traits for RBTreeIteratorMut<'a, K, V>impl<'a, K, V> Iterator for RBTreeIteratorMut<'a, K, V> type Item = (&'a K, &'a mut V);
pub fn iter_mut(&mut self) -> RBTreeIteratorMut<'_, K, V>ⓘNotable traits for RBTreeIteratorMut<'a, K, V>impl<'a, K, V> Iterator for RBTreeIteratorMut<'a, K, V> type Item = (&'a K, &'a mut V);
Returns a mutable iterator over the tree nodes, sorted by key.
sourcepub fn keys(&self) -> impl Iterator<Item = &K>
pub fn keys(&self) -> impl Iterator<Item = &K>
Returns an iterator over the keys of the nodes in the tree, in sorted order.
sourcepub fn values(&self) -> impl Iterator<Item = &V>
pub fn values(&self) -> impl Iterator<Item = &V>
Returns an iterator over the values of the nodes in the tree, sorted by key.
sourcepub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>
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.