rust/kernel/rbtree.rs

Source file repositories/reference/linux-study-clean/rust/kernel/rbtree.rs

File Facts

System
Linux kernel
Corpus path
rust/kernel/rbtree.rs
Extension
.rs
Size
54373 bytes
Lines
1434
Domain
Rust Kernel Layer
Bucket
Rust API Membrane
Inferred role
Rust Kernel Layer: implementation source
Status
source implementation candidate

Why This File Exists

Rust-side wrappers and abstractions around kernel C APIs, ownership contracts, allocation, synchronization, and module integration.

Dependency Surface

Detected Declarations

Annotated Snippet

fn drop(&mut self) {
        // SAFETY: `root` is valid as it's embedded in `self` and we have a valid `self`.
        let mut next = unsafe { bindings::rb_first_postorder(&self.root) };

        // INVARIANT: The loop invariant is that all tree nodes from `next` in postorder are valid.
        while !next.is_null() {
            // SAFETY: All links fields we create are in a `Node<K, V>`.
            let this = unsafe { container_of!(next, Node<K, V>, links) };

            // Find out what the next node is before disposing of the current one.
            // SAFETY: `next` and all nodes in postorder are still valid.
            next = unsafe { bindings::rb_next_postorder(next) };

            // INVARIANT: This is the destructor, so we break the type invariant during clean-up,
            // but it is not observable. The loop invariant is still maintained.

            // SAFETY: `this` is valid per the loop invariant.
            unsafe { drop(KBox::from_raw(this)) };
        }
    }
}

/// A bidirectional mutable 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_mut().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());
///
/// # Ok::<(), Error>(())
/// ```
///
/// 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_mut().unwrap();
/// let current = cursor.current();
/// assert_eq!(current, (&30, &300));
///
/// # Ok::<(), Error>(())
/// ```
///
/// Obtaining a cursor returns [`None`] if the tree is empty.
///
/// ```
/// use kernel::rbtree::RBTree;

Annotation

Implementation Notes