rust: rbtree: add cursor
authorMatt Gilbride <mattgilbride@google.com>
Thu, 22 Aug 2024 16:37:56 +0000 (16:37 +0000)
committerMiguel Ojeda <ojeda@kernel.org>
Sat, 31 Aug 2024 15:36:20 +0000 (17:36 +0200)
commit98c14e40e07a077827f6842e8f31d191cb82576c
tree7365cce6d6adf82d18093135b8f2f5a17a6607fb
parentcf5397d1776489e1c66b7db01f6a58c431ab08f1
rust: rbtree: add cursor

Add a cursor interface to `RBTree`, supporting the following use cases:
- Inspect the current node pointed to by the cursor, inspect/move to
  it's neighbors in sort order (bidirectionally).
- Mutate the tree itself by removing the current node pointed to by the
  cursor, or one of its neighbors.

Add functions to obtain a cursor to the tree by key:
- The node with the smallest key
- The node with the largest key
- The node matching the given key, or the one with the next larger key

The cursor abstraction is needed by the binder driver to efficiently
search for nodes and (conditionally) modify them, as well as their
neighbors [1].

Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-6-08ba9197f637@google.com/
Co-developed-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-4-014561758a57@google.com
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
rust/kernel/rbtree.rs