From nobody Thu Sep 19 01:09:30 2024 Received: from mail-qk1-f201.google.com (mail-qk1-f201.google.com [209.85.222.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0F60761FCF for ; Fri, 26 Jul 2024 19:57:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722023880; cv=none; b=HrM/H3TNp4i95Ng1JZQ/1Pf9nuH9sz5nx2vPo5xbpFfUP4Gtzdswc+tACiD5aGQvhMg8jZTckQ2tJa/41GwGVdBnpwuTLjHoY4wseynWthCt6Dx5inJhvTH44+h0t1nrPfmH2qpS9JAEdlGSEBwHSQuYu6nPqLDz857i/QCmlrg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722023880; c=relaxed/simple; bh=q4QRA80ZniVAEhnFSRFNLIyXwhFvaAjS9p/cLfM7FLM=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=KfzCQQcW8lgMy0N4FApG1dnFUr1Bd3xMADOrVTrtqlG5mWjBfrqYSu6004LwCL5UZ5LwD9TPiotD8lbhkOKtFNuoptAQBsskUSCnMybZ+pAk26doTGH8ptzKUc+N3hskrgC0DssKxTLVrbp3Pp1YErmMGnwLRN7vZLLJdooyu/U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=HA9qb4zU; arc=none smtp.client-ip=209.85.222.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="HA9qb4zU" Received: by mail-qk1-f201.google.com with SMTP id af79cd13be357-7a1df9ced6fso116319185a.2 for ; Fri, 26 Jul 2024 12:57:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722023877; x=1722628677; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=d8GaitvJd3HTC0qdEAqCrtZyprc/3NqgvgsE5rl1gFA=; b=HA9qb4zUBs3O3PteRMaSzfZ3J828P4C3QyI6nNZ+CV3TP0ZCGguXSVWPzevWWPZkqM sxLXFpJsxEC+Qmk161rqcMUne9YitbvuedX4jhqB6dsSg6eAZjzn1QMleOyVhBolUZvo KroJiULPqNQu+E46sP9XRvsx70Vizwvs8pyo9utvdkLbGPUnkp6d/nQ9b0ZPehYdWLz6 CrvJUXRYdPdoHEsYDxO7o/R8OHDxhqMi8v6jwHlNdqlcMUzZs5XtFppI3bWOGxLSbM1n GssgmzGOVBgWEF2uv6mtfwjD3fTDmuqPRkOGkV3yBnASWwkFWtxXtPE/nWyZEkSzft/A DD9Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722023877; x=1722628677; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=d8GaitvJd3HTC0qdEAqCrtZyprc/3NqgvgsE5rl1gFA=; b=rvscCf2wRGhpgMwsNysPTubEQpLnhsU9+USTivxyuytResZKYFP9Qly0kOANx5m/yn A86hlbbeaKcUNWwhyFHovV64s47BnlR40tS9Sq3B2eOMgBqZMzdaLXkSusm7/07NP3Xt /qvogMoaKUWORsIdWDMqDXU93JRwEezvJ9X6mQm39IzAirICo1iWiya5/Sbi/PCJvGQT kG2ngt0T+dNaN+/MenMyJkVPvk43zDOh/Eb/juBRxfGGXtNTHBMEw0TCnwYCdJKbhlIf 2zV7L0pjGQEevk3XD7WMqzBIapkRqbV1C2HdnLxM5ScGGOot1z+Z2YF4bl/dKLSsmrNG tcSQ== X-Forwarded-Encrypted: i=1; AJvYcCVWjKoAAzTsrUxlB0KJZ7e0Y74tl/ufvUrpIqWEYn/VYbLCBlu1tjsLxO5dtxTp6ODiCuNOADzi/fKXDEFm8bWyPP9BvNe+5w41HDc8 X-Gm-Message-State: AOJu0Yx4EMlV84pAZMInABEs/mA3Yo6IOs0EQwcVrAQjiexPgcEtKFRV m8Pc9sf72KZWVVvgg2Cyal6pqYPsd4wOkeFfP4cH7QMI+ODQIMtO6w5iKF1u5mzD/bluYpqEjMV /TuAvruqPz8WYh3LwYgVr2BBnvQ== X-Google-Smtp-Source: AGHT+IHyb/LbXvb2BO9cvjYJaxebXRB3fBNSA3hIC7buLJSepRBdh2ixF8JT864LcG7pN2CstdyP1OkL03MZDfdItRs= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:a05:620a:25d4:b0:79f:955:56df with SMTP id af79cd13be357-7a1e52a2a31mr171785a.11.1722023877073; Fri, 26 Jul 2024 12:57:57 -0700 (PDT) Date: Fri, 26 Jul 2024 19:57:44 +0000 In-Reply-To: <20240726-b4-rbtree-v7-0-aee88caaf97c@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240726-b4-rbtree-v7-0-aee88caaf97c@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240726-b4-rbtree-v7-5-aee88caaf97c@google.com> Subject: [PATCH v7 5/6] rust: rbtree: add `RBTreeCursor` From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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-08ba= 9197f637@google.com/ [1] Co-developed-by: Alice Ryhl Signed-off-by: Alice Ryhl Reviewed-by: Alice Ryhl Tested-by: Alice Ryhl Signed-off-by: Matt Gilbride --- rust/kernel/rbtree.rs | 538 ++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 538 insertions(+) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index 64e0f2328879..5611ae903779 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -234,6 +234,40 @@ pub fn values(&self) -> impl Iterator { pub fn values_mut(&mut self) -> impl Iterator { self.iter_mut().map(|(_, v)| v) } + + /// Returns a cursor over the tree nodes, starting with the smallest k= ey. + pub fn cursor_front(&mut self) -> Option> { + let root =3D addr_of_mut!(self.root); + // SAFETY: `self.root` is always a valid root node + let current =3D unsafe { bindings::rb_first(root) }; + NonNull::new(current).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + // - Due to the type signature of this function, the returned = [`RBTreeCursor`] + // borrows mutably from `self`. + RBTreeCursor { + current, + tree: self, + } + }) + } + + /// Returns a cursor over the tree nodes, starting with the largest ke= y. + pub fn cursor_back(&mut self) -> Option> { + let root =3D addr_of_mut!(self.root); + // SAFETY: `self.root` is always a valid root node + let current =3D unsafe { bindings::rb_last(root) }; + NonNull::new(current).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + // - Due to the type signature of this function, the returned = [`RBTreeCursor`] + // borrows mutably from `self`. + RBTreeCursor { + current, + tree: self, + } + }) + } } =20 impl RBTree @@ -394,6 +428,77 @@ fn remove_node(&mut self, key: &K) -> Option> { pub fn remove(&mut self, key: &K) -> Option { self.remove_node(key).map(|node| node.node.value) } + + /// Returns a cursor over the tree nodes based on the given key. + /// + /// If the given key exists, the cursor starts there. + /// Otherwise it starts with the first larger key in sort order. + /// If there is no larger key, it returns [`None`]. + pub fn cursor_lower_bound(&mut self, key: &K) -> Option> + where + K: Ord, + { + let mut node =3D self.root.rb_node; + let mut best_match: Option>> =3D None; + while !node.is_null() { + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node, Node, links) }= .cast_mut(); + // SAFETY: `this` is a non-null node so it is valid by the typ= e invariants. + let this_key =3D unsafe { &(*this).key }; + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + let left_child =3D unsafe { (*node).rb_left }; + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + let right_child =3D unsafe { (*node).rb_right }; + if key =3D=3D this_key { + return NonNull::new(node).map(|current| { + // INVARIANT: + // - `node` is a valid node in the [`RBTree`] pointed = to by `self`. + // - Due to the type signature of this function, the r= eturned [`RBTreeCursor`] + // borrows mutably from `self`. + RBTreeCursor { + current, + tree: self, + } + }); + } else { + node =3D if key > this_key { + right_child + } else { + let is_better_match =3D match best_match { + None =3D> true, + Some(best) =3D> { + // SAFETY: `best` is a non-null node so it is = valid by the type invariants. + let best_key =3D unsafe { &(*best.as_ptr()).ke= y }; + best_key > this_key + } + }; + if is_better_match { + best_match =3D NonNull::new(this); + } + left_child + }; + } + } + + let Some(best) =3D best_match else { + return None; + }; + + // SAFETY: `best` is a non-null node so it is valid by the type in= variants. + let links =3D unsafe { addr_of_mut!((*best.as_ptr()).links) }; + + NonNull::new(links).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + // - Due to the type signature of this function, the returned = [`RBTreeCursor`] + // borrows mutably from `self`. + RBTreeCursor { + current, + tree: self, + } + }) + } } =20 impl Default for RBTree { @@ -425,6 +530,434 @@ fn drop(&mut self) { } } =20 +/// A bidirectional cursor over the tree nodes, sorted by key. +/// +/// # Examples +/// +/// In the following example, we obtain a cursor to the first element in t= he tree. +/// The cursor allows us to iterate bidirectionally over key/value pairs i= n the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D 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 =3D tree.cursor_front().unwrap(); +/// let mut current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// +/// // Move the cursor, updating it to the 2nd element. +/// cursor =3D cursor.move_next().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Peek at the next element without impacting the cursor. +/// let next =3D cursor.peek_next().unwrap(); +/// assert_eq!(next, (&30, &300)); +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Moving past the last element causes the cursor to return [`None`]. +/// cursor =3D cursor.move_next().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// let cursor =3D 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 =3D 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 =3D tree.cursor_back().unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// Obtaining a cursor returns [`None`] if the tree is empty. +/// +/// ``` +/// use kernel::rbtree::RBTree; +/// +/// let mut tree: RBTree =3D RBTree::new(); +/// assert!(tree.cursor_front().is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary no= de in the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D 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 =3D tree.cursor_lower_bound(&20).unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // If the provided key doesn't exist, a cursor to the first larger ele= ment in sort order is returned. +/// let cursor =3D tree.cursor_lower_bound(&25).unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// // If there is no larger key, [`None`] is returned. +/// let cursor =3D tree.cursor_lower_bound(&55); +/// assert!(cursor.is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// The cursor allows mutation of values in the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D 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 =3D tree.cursor_front().unwrap(); +/// +/// // Get a mutable reference to the current value. +/// let (k, v) =3D cursor.current_mut(); +/// *v =3D 1000; +/// +/// // The updated value is reflected in the tree. +/// let updated =3D tree.get(&10).unwrap(); +/// assert_eq!(updated, &1000); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// It also allows node removal. The following examples demonstrate the be= havior of removing the current node. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D 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 =3D tree.cursor_front().unwrap(); +/// let mut current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// cursor =3D cursor.remove_current().0.unwrap(); +/// +/// // If a node exists after the current element, it is returned. +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Get a cursor to the last element, and remove it. +/// cursor =3D tree.cursor_back().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// // Since there is no next node, the previous node is returned. +/// cursor =3D cursor.remove_current().0.unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Removing the last element in the tree returns [`None`]. +/// assert!(cursor.remove_current().0.is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// Nodes adjacent to the current node can also be removed. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D 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 =3D tree.cursor_front().unwrap(); +/// let mut current =3D 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 =3D tree.cursor_back().unwrap(); +/// current =3D 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 =3D cursor.move_prev().unwrap(); +/// current =3D 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)); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// # Invariants +/// - `current` points to a node that is in the same [`RBTree`] as `tree`. +pub struct RBTreeCursor<'a, K, V> { + tree: &'a mut RBTree, + current: NonNull, +} + +// SAFETY: The [`RBTreeCursor`] gives out immutable references to K and mu= table references to V, +// so it has the same thread safety requirements as mutable references. +unsafe impl<'a, K: Send, V: Send> Send for RBTreeCursor<'a, K, V> {} + +// SAFETY: The [`RBTreeCursor`] gives out immutable references to K and mu= table references to V, +// so it has the same thread safety requirements as mutable references. +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeCursor<'a, K, V> {} + +impl<'a, K, V> RBTreeCursor<'a, K, V> { + /// The current node + pub fn current(&self) -> (&K, &V) { + // SAFETY: + // - `self.current` is a valid node by the type invariants. + // - We have an immutable reference by the function signature. + unsafe { Self::to_key_value(self.current) } + } + + /// The current node, with a mutable value + pub fn current_mut(&mut self) -> (&K, &mut V) { + // SAFETY: + // - `self.current` is a valid node by the type invariants. + // - We have an mutable reference by the function signature. + unsafe { Self::to_key_value_mut(self.current) } + } + + /// Remove the current node from the tree. + /// + /// Returns a tuple where the first element is a cursor to the next no= de, if it exists, + /// else the previous node, else [`None`] (if the tree becomes empty).= The second element + /// is the removed node. + pub fn remove_current(self) -> (Option, RBTreeNode) { + let prev =3D self.get_neighbor_raw(Direction::Prev); + let next =3D self.get_neighbor_raw(Direction::Next); + // SAFETY: By the type invariant of `Self`, all non-null `rb_node`= pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(self.current.as_ptr(), Node, links) }.cast_mut(); + // SAFETY: `this` is valid by the type invariants as described abo= ve. + let node =3D unsafe { Box::from_raw(this) }; + let node =3D RBTreeNode { node }; + // SAFETY: The reference to the tree used to create the cursor out= lives the cursor, so + // the tree cannot change. By the tree invariant, all nodes are va= lid. + unsafe { bindings::rb_erase(&mut (*this).links, addr_of_mut!(self.= tree.root)) }; + + let current =3D match (prev, next) { + (_, Some(next)) =3D> next, + (Some(prev), None) =3D> prev, + (None, None) =3D> { + return (None, node); + } + }; + + ( + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self.tree`. + // - Due to the function signature, `self` is an owned [`RBTre= eCursor`], + // and [`RBTreeCursor`]s are only created via functions with= a mutable reference + // to an [`RBTree`]. + Some(Self { + current, + tree: self.tree, + }), + node, + ) + } + + /// Remove the previous node, returning it if it exists. + pub fn remove_prev(&mut self) -> Option> { + self.remove_neighbor(Direction::Prev) + } + + /// Remove the next node, returning it if it exists. + pub fn remove_next(&mut self) -> Option> { + self.remove_neighbor(Direction::Next) + } + + fn remove_neighbor(&mut self, direction: Direction) -> Option> { + if let Some(neighbor) =3D self.get_neighbor_raw(direction) { + let neighbor =3D neighbor.as_ptr(); + // SAFETY: The reference to the tree used to create the cursor= outlives the cursor, so + // the tree cannot change. By the tree invariant, all nodes ar= e valid. + unsafe { bindings::rb_erase(neighbor, addr_of_mut!(self.tree.r= oot)) }; + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(neighbor, Node, link= s) }.cast_mut(); + // SAFETY: `this` is valid by the type invariants as described= above. + let node =3D unsafe { Box::from_raw(this) }; + return Some(RBTreeNode { node }); + } + None + } + + /// Move the cursor to the previous node, returning [`None`] if it doe= sn't exist. + pub fn move_prev(self) -> Option { + self.mv(Direction::Prev) + } + + /// Move the cursor to the next node, returning [`None`] if it doesn't= exist. + pub fn move_next(self) -> Option { + self.mv(Direction::Next) + } + + fn mv(self, direction: Direction) -> Option { + // INVARIANT: + // - `neighbor` is a valid node in the [`RBTree`] pointed to by `s= elf.tree`. + // - Due to the function signature, `self` is an owned [`RBTreeCur= sor`], + // and [`RBTreeCursor`]s are only created via functions with a m= utable reference + // to an [`RBTree`]. + self.get_neighbor_raw(direction).map(|neighbor| Self { + tree: self.tree, + current: neighbor, + }) + } + + /// Access the previous node without moving the cursor. + pub fn peek_prev(&self) -> Option<(&K, &V)> { + self.peek(Direction::Prev) + } + + /// Access the previous node without moving the cursor. + pub fn peek_next(&self) -> Option<(&K, &V)> { + self.peek(Direction::Next) + } + + fn peek(&self, direction: Direction) -> Option<(&K, &V)> { + self.get_neighbor_raw(direction) + // SAFETY: + // - `neighbor` is a valid tree node. + // - By the function signature, we have an immutable reference= to `self`. + .map(|neighbor| unsafe { Self::to_key_value(neighbor) }) + } + + /// Access the previous node mutably without moving the cursor. + pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> { + self.peek_mut(Direction::Prev) + } + + /// Access the next node mutably without moving the cursor. + pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> { + self.peek_mut(Direction::Next) + } + + fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> { + self.get_neighbor_raw(direction) + // SAFETY: + // - `neighbor` is a valid tree node. + // - By the function signature, we have a mutable reference to= `self`. + .map(|neighbor| unsafe { Self::to_key_value_mut(neighbor) }) + } + + fn get_neighbor_raw(&self, direction: Direction) -> Option> { + // SAFETY: `self.current` is valid by the type invariants. + let neighbor =3D unsafe { + match direction { + Direction::Prev =3D> bindings::rb_prev(self.current.as_ptr= ()), + Direction::Next =3D> bindings::rb_next(self.current.as_ptr= ()), + } + }; + + NonNull::new(neighbor) + } + + /// SAFETY: + /// - `node` must be a valid pointer to a node in an [`RBTree`]. + /// - The caller has immutable access to `node` for the duration of 'b. + unsafe fn to_key_value<'b>(node: NonNull) -> (&'b K= , &'b V) { + // SAFETY: the caller guarantees that `node` is a valid pointer in= an `RBTree`. + let (k, v) =3D unsafe { Self::to_key_value_raw(node) }; + // SAFETY: the caller guarantees immutable access to `node`. + (k, unsafe { &*v }) + } + + /// SAFETY: + /// - `node` must be a valid pointer to a node in an [`RBTree`]. + /// - The caller has mutable access to `node` for the duration of 'b. + unsafe fn to_key_value_mut<'b>(node: NonNull) -> (&= 'b K, &'b mut V) { + // SAFETY: the caller guarantees that `node` is a valid pointer in= an `RBTree`. + let (k, v) =3D unsafe { Self::to_key_value_raw(node) }; + // SAFETY: the caller guarantees mutable access to `node`. + (k, unsafe { &mut *v }) + } + + /// SAFETY: + /// - `node` must be a valid pointer to a node in an [`RBTree`]. + /// - The caller has immutable access to the key for the duration of '= b. + unsafe fn to_key_value_raw<'b>(node: NonNull) -> (&= 'b K, *mut V) { + // SAFETY: By the type invariant of `Self`, all non-null `rb_node`= pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node.as_ptr(), Node, lin= ks) }.cast_mut(); + // SAFETY: The passed `node` is the current node or a non-null nei= ghbor, + // thus `this` is valid by the type invariants. + let k =3D unsafe { &(*this).key }; + // SAFETY: The passed `node` is the current node or a non-null nei= ghbor, + // thus `this` is valid by the type invariants. + let v =3D unsafe { addr_of_mut!((*this).value) }; + (k, v) + } +} + +/// Direction for [`RBTreeCursor`] operations. +enum Direction { + /// the node immediately before, in sort order + Prev, + /// the node immediately after, in sort order + Next, +} + impl<'a, K, V> IntoIterator for &'a RBTree { type Item =3D (&'a K, &'a V); type IntoIter =3D Iter<'a, K, V>; @@ -583,6 +1116,11 @@ impl RBTreeNode { pub fn new(key: K, value: V, flags: Flags) -> Result>= { Ok(RBTreeNodeReservation::new(flags)?.into_node(key, value)) } + + /// Get the key and value from inside the node. + pub fn to_key_value(self) -> (K, V) { + (self.node.key, self.node.value) + } } =20 // SAFETY: If K and V can be sent across threads, then it's also okay to s= end [`RBTreeNode`] across --=20 2.46.0.rc1.232.g9752f9e123-goog