From 8526c313c115bb997a10d6c012864f6c4a5c6853 Mon Sep 17 00:00:00 2001 From: Stein Somers Date: Mon, 23 Nov 2020 16:40:48 +0100 Subject: BTreeMap: cut out the ceremony around BoxedNode --- library/alloc/src/collections/btree/node.rs | 50 +++++++---------------------- 1 file changed, 12 insertions(+), 38 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index e3e555a72de..6a8be441513 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -112,20 +112,8 @@ impl InternalNode { /// /// However, `BoxedNode` contains no information as to which of the two types /// of nodes it actually contains, and, partially due to this lack of information, -/// has no destructor. -struct BoxedNode { - ptr: NonNull>, -} - -impl BoxedNode { - fn from_owned(ptr: NonNull>) -> Self { - BoxedNode { ptr } - } - - fn as_ptr(&self) -> NonNull> { - self.ptr - } -} +/// is not a separate type and has no destructor. +type BoxedNode = NonNull>; /// An owned tree. /// @@ -168,11 +156,6 @@ impl NodeRef { pub fn borrow_valmut(&mut self) -> NodeRef, K, V, Type> { NodeRef { height: self.height, node: self.node, _marker: PhantomData } } - - /// Packs the reference, aware of type and height, into a type-agnostic pointer. - fn into_boxed_node(self) -> BoxedNode { - BoxedNode::from_owned(self.node) - } } impl NodeRef { @@ -181,7 +164,7 @@ impl NodeRef { /// and is the opposite of `pop_internal_level`. pub fn push_internal_level(&mut self) -> NodeRef, K, V, marker::Internal> { let mut new_node = Box::new(unsafe { InternalNode::new() }); - new_node.edges[0].write(BoxedNode::from_owned(self.node)); + new_node.edges[0].write(self.node); let mut new_root = NodeRef::from_new_internal(new_node, self.height + 1); new_root.borrow_mut().first_edge().correct_parent_link(); *self = new_root.forget_type(); @@ -288,13 +271,6 @@ unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef Send for NodeRef, K, V, Type> {} unsafe impl Send for NodeRef {} -impl NodeRef { - /// Unpack a node reference that was packed by `Root::into_boxed_node`. - fn from_boxed_node(boxed_node: BoxedNode, height: usize) -> Self { - NodeRef { height, node: boxed_node.as_ptr(), _marker: PhantomData } - } -} - impl NodeRef { /// Unpack a node reference that was packed as `NodeRef::parent`. fn from_internal(node: NonNull>, height: usize) -> Self { @@ -695,7 +671,7 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::Internal> { unsafe { self.reborrow_mut().into_key_area_mut_at(idx).write(key); self.reborrow_mut().into_val_area_mut_at(idx).write(val); - self.reborrow_mut().into_edge_area_mut_at(idx + 1).write(edge.into_boxed_node()); + self.reborrow_mut().into_edge_area_mut_at(idx + 1).write(edge.node); Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link(); } } @@ -710,7 +686,7 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::Internal> { *self.reborrow_mut().into_len_mut() += 1; slice_insert(self.reborrow_mut().into_key_area_slice(), 0, key); slice_insert(self.reborrow_mut().into_val_area_slice(), 0, val); - slice_insert(self.reborrow_mut().into_edge_area_slice(), 0, edge.into_boxed_node()); + slice_insert(self.reborrow_mut().into_edge_area_slice(), 0, edge.node); } self.correct_all_childrens_parent_links(); @@ -732,8 +708,8 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::LeafOrInternal> { let edge = match self.reborrow_mut().force() { ForceResult::Leaf(_) => None, ForceResult::Internal(internal) => { - let boxed_node = ptr::read(internal.reborrow().edge_at(idx + 1)); - let mut edge = Root::from_boxed_node(boxed_node, internal.height - 1); + let node = ptr::read(internal.reborrow().edge_at(idx + 1)); + let mut edge = Root { node, height: internal.height - 1, _marker: PhantomData }; // In practice, clearing the parent is a waste of time, because we will // insert the node elsewhere and set its parent link again. edge.borrow_mut().clear_parent_link(); @@ -760,9 +736,8 @@ impl<'a, K: 'a, V: 'a> NodeRef, K, V, marker::LeafOrInternal> { let edge = match self.reborrow_mut().force() { ForceResult::Leaf(_) => None, ForceResult::Internal(mut internal) => { - let boxed_node = - slice_remove(internal.reborrow_mut().into_edge_area_slice(), 0); - let mut edge = Root::from_boxed_node(boxed_node, internal.height - 1); + let node = slice_remove(internal.reborrow_mut().into_edge_area_slice(), 0); + let mut edge = Root { node, height: internal.height - 1, _marker: PhantomData }; // In practice, clearing the parent is a waste of time, because we will // insert the node elsewhere and set its parent link again. edge.borrow_mut().clear_parent_link(); @@ -1041,12 +1016,11 @@ impl<'a, K: 'a, V: 'a> Handle, K, V, marker::Internal>, debug_assert!(self.node.len() < CAPACITY); debug_assert!(edge.height == self.node.height - 1); - let boxed_node = edge.into_boxed_node(); unsafe { *self.node.reborrow_mut().into_len_mut() += 1; slice_insert(self.node.reborrow_mut().into_key_area_slice(), self.idx, key); slice_insert(self.node.reborrow_mut().into_val_area_slice(), self.idx, val); - slice_insert(self.node.reborrow_mut().into_edge_area_slice(), self.idx + 1, boxed_node); + slice_insert(self.node.reborrow_mut().into_edge_area_slice(), self.idx + 1, edge.node); self.node.correct_childrens_parent_links((self.idx + 1)..=self.node.len()); } @@ -1135,8 +1109,8 @@ impl Handle, marke // reference (Rust issue #73987) and invalidate any other references // to or inside the array, should any be around. let parent_ptr = NodeRef::as_internal_ptr(&self.node); - let boxed_node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() }; - NodeRef::from_boxed_node(boxed_node, self.node.height - 1) + let node = unsafe { (*parent_ptr).edges.get_unchecked(self.idx).assume_init_read() }; + NodeRef { node, height: self.node.height - 1, _marker: PhantomData } } } -- cgit 1.4.1-3-g733a5