diff options
Diffstat (limited to 'rust/kernel/rbtree.rs')
| -rw-r--r-- | rust/kernel/rbtree.rs | 49 |
1 files changed, 27 insertions, 22 deletions
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index d03e4aa1f481..cb4415a12258 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -7,7 +7,6 @@ //! Reference: <https://docs.kernel.org/core-api/rbtree.html> use crate::{alloc::Flags, bindings, container_of, error::Result, prelude::*}; -use alloc::boxed::Box; use core::{ cmp::{Ord, Ordering}, marker::PhantomData, @@ -497,7 +496,7 @@ impl<K, V> Drop for RBTree<K, V> { // but it is not observable. The loop invariant is still maintained. // SAFETY: `this` is valid per the loop invariant. - unsafe { drop(Box::from_raw(this.cast_mut())) }; + unsafe { drop(KBox::from_raw(this.cast_mut())) }; } } } @@ -764,7 +763,7 @@ impl<'a, K, V> Cursor<'a, K, V> { // point to the links field of `Node<K, V>` objects. let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) }.cast_mut(); // SAFETY: `this` is valid by the type invariants as described above. - let node = unsafe { Box::from_raw(this) }; + let node = unsafe { KBox::from_raw(this) }; let node = RBTreeNode { node }; // 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 are valid. @@ -809,7 +808,7 @@ impl<'a, K, V> Cursor<'a, K, V> { // point to the links field of `Node<K, V>` objects. let this = unsafe { container_of!(neighbor, Node<K, V>, links) }.cast_mut(); // SAFETY: `this` is valid by the type invariants as described above. - let node = unsafe { Box::from_raw(this) }; + let node = unsafe { KBox::from_raw(this) }; return Some(RBTreeNode { node }); } None @@ -1038,7 +1037,7 @@ impl<K, V> Iterator for IterRaw<K, V> { /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One /// can be obtained by directly allocating it ([`RBTreeNodeReservation::new`]). pub struct RBTreeNodeReservation<K, V> { - node: Box<MaybeUninit<Node<K, V>>>, + node: KBox<MaybeUninit<Node<K, V>>>, } impl<K, V> RBTreeNodeReservation<K, V> { @@ -1046,7 +1045,7 @@ impl<K, V> RBTreeNodeReservation<K, V> { /// call to [`RBTree::insert`]. pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> { Ok(RBTreeNodeReservation { - node: <Box<_> as BoxExt<_>>::new_uninit(flags)?, + node: KBox::new_uninit(flags)?, }) } } @@ -1062,14 +1061,15 @@ impl<K, V> RBTreeNodeReservation<K, V> { /// Initialises a node reservation. /// /// It then becomes an [`RBTreeNode`] that can be inserted into a tree. - pub fn into_node(mut self, key: K, value: V) -> RBTreeNode<K, V> { - self.node.write(Node { - key, - value, - links: bindings::rb_node::default(), - }); - // SAFETY: We just wrote to it. - let node = unsafe { self.node.assume_init() }; + pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> { + let node = KBox::write( + self.node, + Node { + key, + value, + links: bindings::rb_node::default(), + }, + ); RBTreeNode { node } } } @@ -1079,7 +1079,7 @@ impl<K, V> RBTreeNodeReservation<K, V> { /// The node is fully initialised (with key and value) and can be inserted into a tree without any /// extra allocations or failure paths. pub struct RBTreeNode<K, V> { - node: Box<Node<K, V>>, + node: KBox<Node<K, V>>, } impl<K, V> RBTreeNode<K, V> { @@ -1091,7 +1091,9 @@ impl<K, V> RBTreeNode<K, V> { /// Get the key and value from inside the node. pub fn to_key_value(self) -> (K, V) { - (self.node.key, self.node.value) + let node = KBox::into_inner(self.node); + + (node.key, node.value) } } @@ -1113,7 +1115,7 @@ impl<K, V> RBTreeNode<K, V> { /// may be freed (but only for the key/value; memory for the node itself is kept for reuse). pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> { RBTreeNodeReservation { - node: Box::drop_contents(self.node), + node: KBox::drop_contents(self.node), } } } @@ -1164,7 +1166,7 @@ impl<'a, K, V> RawVacantEntry<'a, K, V> { /// The `node` must have a key such that inserting it here does not break the ordering of this /// [`RBTree`]. fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V { - let node = Box::into_raw(node.node); + let node = KBox::into_raw(node.node); // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when // the node is removed or replaced. @@ -1238,21 +1240,24 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { // SAFETY: The node was a node in the tree, but we removed it, so we can convert it // back into a box. node: unsafe { - Box::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) + KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }, } } /// Takes the value of the entry out of the map, and returns it. pub fn remove(self) -> V { - self.remove_node().node.value + let rb_node = self.remove_node(); + let node = KBox::into_inner(rb_node.node); + + node.value } /// Swap the current node for the provided node. /// /// The key of both nodes must be equal. fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> { - let node = Box::into_raw(node.node); + let node = KBox::into_raw(node.node); // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when // the node is removed or replaced. @@ -1268,7 +1273,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { // - `self.node_ptr` produces a valid pointer to a node in the tree. // - Now that we removed this entry from the tree, we can convert the node to a box. let old_node = - unsafe { Box::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }; + unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }; RBTreeNode { node: old_node } } |