Struct Cursor

Help

pub struct Cursor<'a, K, V> { /* private fields */ }

Expand description

A bidirectional cursor over the tree nodes, sorted by key.

§Examples

In the following example, we obtain a cursor to the first element in the tree. The cursor allows us to iterate bidirectionally over key/value pairs in the tree.

use kernel::{alloc::flags, rbtree::RBTree};

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

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

// Get a cursor to the first element.
let mut cursor = tree.cursor_front().unwrap();
let mut current = cursor.current();
assert_eq!(current, (&10, &100));

// Move the cursor, updating it to the 2nd element.
cursor = cursor.move_next().unwrap();
current = cursor.current();
assert_eq!(current, (&20, &200));

// Peek at the next element without impacting the cursor.
let next = cursor.peek_next().unwrap();
assert_eq!(next, (&30, &300));
current = cursor.current();
assert_eq!(current, (&20, &200));

// Moving past the last element causes the cursor to return [`None`].
cursor = cursor.move_next().unwrap();
current = cursor.current();
assert_eq!(current, (&30, &300));
let cursor = cursor.move_next();
assert!(cursor.is_none());

A cursor can also be obtained at the last element in the tree.

use kernel::{alloc::flags, rbtree::RBTree};

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

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

let mut cursor = tree.cursor_back().unwrap();
let current = cursor.current();
assert_eq!(current, (&30, &300));

Obtaining a cursor returns None if the tree is empty.

use kernel::rbtree::RBTree;

let mut tree: RBTree<u16, u16> = RBTree::new();
assert!(tree.cursor_front().is_none());

RBTree::cursor_lower_bound can be used to start at an arbitrary node in the tree.

use kernel::{alloc::flags, rbtree::RBTree};

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

// Insert five elements.
tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
tree.try_create_and_insert(40, 400, flags::GFP_KERNEL)?;
tree.try_create_and_insert(50, 500, flags::GFP_KERNEL)?;

// If the provided key exists, a cursor to that key is returned.
let cursor = tree.cursor_lower_bound(&20).unwrap();
let current = cursor.current();
assert_eq!(current, (&20, &200));

// If the provided key doesn't exist, a cursor to the first larger element in sort order is returned.
let cursor = tree.cursor_lower_bound(&25).unwrap();
let current = cursor.current();
assert_eq!(current, (&30, &300));

// If there is no larger key, [`None`] is returned.
let cursor = tree.cursor_lower_bound(&55);
assert!(cursor.is_none());

The cursor allows mutation of values in the tree.

use kernel::{alloc::flags, rbtree::RBTree};

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

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

// Retrieve a cursor.
let mut cursor = tree.cursor_front().unwrap();

// Get a mutable reference to the current value.
let (k, v) = cursor.current_mut();
*v = 1000;

// The updated value is reflected in the tree.
let updated = tree.get(&10).unwrap();
assert_eq!(updated, &1000);

It also allows node removal. The following examples demonstrate the behavior of removing the current node.

use kernel::{alloc::flags, rbtree::RBTree};

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

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

// Remove the first element.
let mut cursor = tree.cursor_front().unwrap();
let mut current = cursor.current();
assert_eq!(current, (&10, &100));
cursor = cursor.remove_current().0.unwrap();

// If a node exists after the current element, it is returned.
current = cursor.current();
assert_eq!(current, (&20, &200));

// Get a cursor to the last element, and remove it.
cursor = tree.cursor_back().unwrap();
current = cursor.current();
assert_eq!(current, (&30, &300));

// Since there is no next node, the previous node is returned.
cursor = cursor.remove_current().0.unwrap();
current = cursor.current();
assert_eq!(current, (&20, &200));

// Removing the last element in the tree returns [`None`].
assert!(cursor.remove_current().0.is_none());

Nodes adjacent to the current node can also be removed.

use kernel::{alloc::flags, rbtree::RBTree};

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

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

// Get a cursor to the first element.
let mut cursor = tree.cursor_front().unwrap();
let mut current = cursor.current();
assert_eq!(current, (&10, &100));

// Calling `remove_prev` from the first element returns [`None`].
assert!(cursor.remove_prev().is_none());

// Get a cursor to the last element.
cursor = tree.cursor_back().unwrap();
current = cursor.current();
assert_eq!(current, (&30, &300));

// Calling `remove_prev` removes and returns the middle element.
assert_eq!(cursor.remove_prev().unwrap().to_key_value(), (20, 200));

// Calling `remove_next` from the last element returns [`None`].
assert!(cursor.remove_next().is_none());

// Move to the first element
cursor = cursor.move_prev().unwrap();
current = cursor.current();
assert_eq!(current, (&10, &100));

// Calling `remove_next` removes and returns the last element.
assert_eq!(cursor.remove_next().unwrap().to_key_value(), (30, 300));

§Invariants

current points to a node that is in the same RBTree as tree.

Implementations§

Source §

impl<'a, K, V> Cursor<'a, K, V>

Source

pub fn current(&self) -> (&K, &V)

The current node

Source

pub fn current_mut(&mut self) -> (&K, &mut V)

The current node, with a mutable value

Source

pub fn remove_current(self) -> (Option<Self>, RBTreeNode<K, V>)

Remove the current node from the tree.

Returns a tuple where the first element is a cursor to the next node, if it exists, else the previous node, else None (if the tree becomes empty). The second element is the removed node.

Source