diff options
| -rw-r--r-- | library/alloc/src/collections/btree/append.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map.rs | 44 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map/entry.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/node.rs | 186 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/node/tests.rs | 21 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/split.rs | 12 | ||||
| -rw-r--r-- | src/etc/gdb_providers.py | 67 | ||||
| -rw-r--r-- | src/test/debuginfo/pretty-std-collections.rs | 4 |
9 files changed, 168 insertions, 176 deletions
diff --git a/library/alloc/src/collections/btree/append.rs b/library/alloc/src/collections/btree/append.rs index a4253a732c3..d3edcd0b87e 100644 --- a/library/alloc/src/collections/btree/append.rs +++ b/library/alloc/src/collections/btree/append.rs @@ -34,7 +34,7 @@ impl<K, V> Root<K, V> { where I: Iterator<Item = (K, V)>, { - let mut cur_node = self.node_as_mut().last_leaf_edge().into_node(); + let mut cur_node = self.borrow_mut().last_leaf_edge().into_node(); // Iterate through all key-value pairs, pushing them into nodes at the right level. for (key, value) in iter { // Try to push key-value pair into the current leaf node. @@ -86,7 +86,7 @@ impl<K, V> Root<K, V> { fn fix_right_edge(&mut self) { // Handle underfull nodes, start from the top. - let mut cur_node = self.node_as_mut(); + let mut cur_node = self.borrow_mut(); while let Internal(internal) = cur_node.force() { // Check if right-most child is underfull. let mut last_kv = internal.last_kv().consider_for_balancing(); diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 7151d3763f0..6641ad33f92 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -157,7 +157,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { { let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped - let mut out_node = match root.node_as_mut().force() { + let mut out_node = match root.borrow_mut().force() { Leaf(leaf) => leaf, Internal(_) => unreachable!(), }; @@ -213,7 +213,7 @@ impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> { // Ord` constraint, which this method lacks. BTreeMap { root: None, length: 0 } } else { - clone_subtree(self.root.as_ref().unwrap().node_as_ref()) // unwrap succeeds because not empty + clone_subtree(self.root.as_ref().unwrap().reborrow()) // unwrap succeeds because not empty } } } @@ -226,7 +226,7 @@ where type Key = K; fn get(&self, key: &Q) -> Option<&K> { - let root_node = self.root.as_ref()?.node_as_ref(); + let root_node = self.root.as_ref()?.reborrow(); match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv().0), GoDown(_) => None, @@ -235,7 +235,7 @@ where fn take(&mut self, key: &Q) -> Option<K> { let (map, dormant_map) = DormantMutRef::new(self); - let root_node = map.root.as_mut()?.node_as_mut(); + let root_node = map.root.as_mut()?.borrow_mut(); match search::search_tree(root_node, key) { Found(handle) => { Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_kv().0) @@ -246,7 +246,7 @@ where fn replace(&mut self, key: K) -> Option<K> { let (map, dormant_map) = DormantMutRef::new(self); - let root_node = Self::ensure_is_owned(&mut map.root).node_as_mut(); + let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut(); match search::search_tree::<marker::Mut<'_>, K, (), K>(root_node, &key) { Found(handle) => Some(mem::replace(handle.into_key_mut(), key)), GoDown(handle) => { @@ -522,7 +522,7 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - let root_node = self.root.as_ref()?.node_as_ref(); + let root_node = self.root.as_ref()?.reborrow(); match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_kv().1), GoDown(_) => None, @@ -550,7 +550,7 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - let root_node = self.root.as_ref()?.node_as_ref(); + let root_node = self.root.as_ref()?.reborrow(); match search::search_tree(root_node, k) { Found(handle) => Some(handle.into_kv()), GoDown(_) => None, @@ -576,7 +576,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn first_key_value(&self) -> Option<(&K, &V)> { - let root_node = self.root.as_ref()?.node_as_ref(); + let root_node = self.root.as_ref()?.reborrow(); root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv) } @@ -603,7 +603,7 @@ impl<K: Ord, V> BTreeMap<K, V> { #[unstable(feature = "map_first_last", issue = "62924")] pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> { let (map, dormant_map) = DormantMutRef::new(self); - let root_node = map.root.as_mut()?.node_as_mut(); + let root_node = map.root.as_mut()?.borrow_mut(); let kv = root_node.first_leaf_edge().right_kv().ok()?; Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData }) } @@ -650,7 +650,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` #[unstable(feature = "map_first_last", issue = "62924")] pub fn last_key_value(&self) -> Option<(&K, &V)> { - let root_node = self.root.as_ref()?.node_as_ref(); + let root_node = self.root.as_ref()?.reborrow(); root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv) } @@ -677,7 +677,7 @@ impl<K: Ord, V> BTreeMap<K, V> { #[unstable(feature = "map_first_last", issue = "62924")] pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> { let (map, dormant_map) = DormantMutRef::new(self); - let root_node = map.root.as_mut()?.node_as_mut(); + let root_node = map.root.as_mut()?.borrow_mut(); let kv = root_node.last_leaf_edge().left_kv().ok()?; Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData }) } @@ -758,7 +758,7 @@ impl<K: Ord, V> BTreeMap<K, V> { K: Borrow<Q>, Q: Ord, { - let root_node = self.root.as_mut()?.node_as_mut(); + let root_node = self.root.as_mut()?.borrow_mut(); match search::search_tree(root_node, key) { Found(handle) => Some(handle.into_val_mut()), GoDown(_) => None, @@ -854,7 +854,7 @@ impl<K: Ord, V> BTreeMap<K, V> { Q: Ord, { let (map, dormant_map) = DormantMutRef::new(self); - let root_node = map.root.as_mut()?.node_as_mut(); + let root_node = map.root.as_mut()?.borrow_mut(); match search::search_tree(root_node, key) { Found(handle) => { Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_entry()) @@ -971,7 +971,7 @@ impl<K: Ord, V> BTreeMap<K, V> { R: RangeBounds<T>, { if let Some(root) = &self.root { - let (f, b) = root.node_as_ref().range_search(range); + let (f, b) = root.reborrow().range_search(range); Range { front: Some(f), back: Some(b) } } else { @@ -1017,7 +1017,7 @@ impl<K: Ord, V> BTreeMap<K, V> { R: RangeBounds<T>, { if let Some(root) = &mut self.root { - let (f, b) = root.node_as_valmut().range_search(range); + let (f, b) = root.borrow_valmut().range_search(range); RangeMut { front: Some(f), back: Some(b), _marker: PhantomData } } else { @@ -1047,7 +1047,7 @@ impl<K: Ord, V> BTreeMap<K, V> { pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { // FIXME(@porglezomp) Avoid allocating if we don't insert let (map, dormant_map) = DormantMutRef::new(self); - let root_node = Self::ensure_is_owned(&mut map.root).node_as_mut(); + let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut(); match search::search_tree(root_node, &key) { Found(handle) => Occupied(OccupiedEntry { handle, dormant_map, _marker: PhantomData }), GoDown(handle) => { @@ -1103,10 +1103,10 @@ impl<K: Ord, V> BTreeMap<K, V> { left_root.split_off(right_root, key); if left_root.height() < right_root.height() { - self.length = left_root.node_as_ref().calc_length(); + self.length = left_root.reborrow().calc_length(); right.length = total_num - self.len(); } else { - right.length = right_root.node_as_ref().calc_length(); + right.length = right_root.reborrow().calc_length(); self.length = total_num - right.len(); } @@ -1154,7 +1154,7 @@ impl<K: Ord, V> BTreeMap<K, V> { pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> { if let Some(root) = self.root.as_mut() { let (root, dormant_root) = DormantMutRef::new(root); - let front = root.node_as_mut().first_leaf_edge(); + let front = root.borrow_mut().first_leaf_edge(); DrainFilterInner { length: &mut self.length, dormant_root: Some(dormant_root), @@ -1361,7 +1361,7 @@ impl<K, V> IntoIterator for BTreeMap<K, V> { fn into_iter(self) -> IntoIter<K, V> { let mut me = ManuallyDrop::new(self); if let Some(root) = me.root.take() { - let (f, b) = root.into_ref().full_range(); + let (f, b) = root.full_range(); IntoIter { front: Some(f), back: Some(b), length: me.length } } else { @@ -2007,7 +2007,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter(&self) -> Iter<'_, K, V> { if let Some(root) = &self.root { - let (f, b) = root.node_as_ref().full_range(); + let (f, b) = root.reborrow().full_range(); Iter { range: Range { front: Some(f), back: Some(b) }, length: self.length } } else { @@ -2039,7 +2039,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { if let Some(root) = &mut self.root { - let (f, b) = root.node_as_valmut().full_range(); + let (f, b) = root.borrow_valmut().full_range(); IterMut { range: RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }, diff --git a/library/alloc/src/collections/btree/map/entry.rs b/library/alloc/src/collections/btree/map/entry.rs index 73a0ca21f67..69926ac2aff 100644 --- a/library/alloc/src/collections/btree/map/entry.rs +++ b/library/alloc/src/collections/btree/map/entry.rs @@ -286,7 +286,7 @@ impl<'a, K: Ord, V> VacantEntry<'a, K, V> { // Safety: We have consumed self.handle and the reference returned. let map = unsafe { self.dormant_map.awaken() }; let root = map.root.as_mut().unwrap(); - root.push_internal_level().push(ins.k, ins.v, ins.right); + root.push_internal_level().push(ins.kv.0, ins.kv.1, ins.right); map.length += 1; val_ptr } diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 6e45d38dd9f..f15959a1665 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -49,7 +49,7 @@ impl<K, V> BTreeMap<K, V> { // Panics if the map (or the code navigating it) is corrupted. fn check_invariants(&self) { if let Some(root) = &self.root { - let root_node = root.node_as_ref(); + let root_node = root.reborrow(); // Check the back pointers top-down, before we attempt to rely on // more serious navigation code. @@ -92,7 +92,7 @@ impl<K, V> BTreeMap<K, V> { K: Debug, { if let Some(root) = self.root.as_ref() { - root.node_as_ref().dump_keys() + root.reborrow().dump_keys() } else { String::from("not yet allocated") } diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index 5feab920138..4658629753d 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -31,7 +31,7 @@ use core::cmp::Ordering; use core::marker::PhantomData; use core::mem::{self, MaybeUninit}; -use core::ptr::{self, NonNull, Unique}; +use core::ptr::{self, NonNull}; use crate::alloc::{AllocRef, Global, Layout}; use crate::boxed::Box; @@ -114,100 +114,80 @@ impl<K, V> InternalNode<K, V> { /// of nodes it actually contains, and, partially due to this lack of information, /// has no destructor. struct BoxedNode<K, V> { - ptr: Unique<LeafNode<K, V>>, + ptr: NonNull<LeafNode<K, V>>, } impl<K, V> BoxedNode<K, V> { - fn from_leaf(node: Box<LeafNode<K, V>>) -> Self { - BoxedNode { ptr: Unique::from(Box::leak(node)) } - } - - fn from_internal(node: Box<InternalNode<K, V>>) -> Self { - BoxedNode { ptr: Unique::from(Box::leak(node)).cast() } + fn from_owned(ptr: NonNull<LeafNode<K, V>>) -> Self { + BoxedNode { ptr } } fn as_ptr(&self) -> NonNull<LeafNode<K, V>> { - NonNull::from(self.ptr) + self.ptr } } /// An owned tree. /// /// Note that this does not have a destructor, and must be cleaned up manually. -pub struct Root<K, V> { - node: BoxedNode<K, V>, - /// The number of levels below the root node. - height: usize, -} - -unsafe impl<K: Sync, V: Sync> Sync for Root<K, V> {} -unsafe impl<K: Send, V: Send> Send for Root<K, V> {} +pub type Root<K, V> = NodeRef<marker::Owned, K, V, marker::LeafOrInternal>; impl<K, V> Root<K, V> { - /// Returns the number of levels below the root. - pub fn height(&self) -> usize { - self.height - } - /// Returns a new owned tree, with its own root node that is initially empty. pub fn new_leaf() -> Self { - Root { node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), height: 0 } - } - - /// Borrows and returns an immutable reference to the node owned by the root. - pub fn node_as_ref(&self) -> NodeRef<marker::Immut<'_>, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } + NodeRef::new().forget_type() } +} - /// Borrows and returns a mutable reference to the node owned by the root. - pub fn node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } +impl<K, V> NodeRef<marker::Owned, K, V, marker::Leaf> { + fn new() -> Self { + Self::from_new_leaf(Box::new(unsafe { LeafNode::new() })) } - /// Borrows and returns a mutable reference to the leaf node owned by the root. - /// # Safety - /// The root node is a leaf. - unsafe fn leaf_node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Leaf> { - debug_assert!(self.height == 0); - NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } + fn from_new_leaf(leaf: Box<LeafNode<K, V>>) -> Self { + NodeRef { height: 0, node: NonNull::from(Box::leak(leaf)), _marker: PhantomData } } +} - /// Borrows and returns a mutable reference to the internal node owned by the root. - /// # Safety - /// The root node is not a leaf. - unsafe fn internal_node_as_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { - debug_assert!(self.height > 0); - NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } +impl<K, V> NodeRef<marker::Owned, K, V, marker::Internal> { + fn from_new_internal(internal: Box<InternalNode<K, V>>, height: usize) -> Self { + NodeRef { height, node: NonNull::from(Box::leak(internal)).cast(), _marker: PhantomData } } +} - pub fn node_as_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } +impl<K, V, Type> NodeRef<marker::Owned, K, V, Type> { + /// Mutably borrows the owned node. Unlike `reborrow_mut`, this is safe, + /// because the return value cannot be used to destroy the node itself, + /// and there cannot be other references to the tree (except during the + /// process of `into_iter` or `drop`, but that is a horrific already). + pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, K, V, Type> { + NodeRef { height: self.height, node: self.node, _marker: PhantomData } } - pub fn into_ref(self) -> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { - NodeRef { height: self.height, node: self.node.as_ptr(), _marker: PhantomData } + /// Slightly mutably borrows the owned node. + pub fn borrow_valmut(&mut self) -> NodeRef<marker::ValMut<'_>, 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<K, V> { - self.node + BoxedNode::from_owned(self.node) } +} +impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> { /// Adds a new internal node with a single edge pointing to the previous root node, /// make that new node the root node, and return it. This increases the height by 1 /// and is the opposite of `pop_internal_level`. pub fn push_internal_level(&mut self) -> NodeRef<marker::Mut<'_>, K, V, marker::Internal> { let mut new_node = Box::new(unsafe { InternalNode::new() }); - new_node.edges[0].write(unsafe { ptr::read(&mut self.node) }); + new_node.edges[0].write(BoxedNode::from_owned(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(); - self.node = BoxedNode::from_internal(new_node); - self.height += 1; - - unsafe { - let mut ret = self.internal_node_as_mut(); - ret.reborrow_mut().first_edge().correct_parent_link(); - ret - } + // `self.borrow_mut()`, except that we just forgot we're internal now: + NodeRef { height: self.height, node: self.node, _marker: PhantomData } } /// Removes the internal root node, using its first child as the new root node. @@ -216,19 +196,17 @@ impl<K, V> Root<K, V> { /// This decreases the height by 1 and is the opposite of `push_internal_level`. /// /// Requires exclusive access to the `Root` object but not to the root node; - /// it will not invalidate existing handles or references to the root node. + /// it will not invalidate other handles or references to the root node. /// /// Panics if there is no internal level, i.e., if the root node is a leaf. pub fn pop_internal_level(&mut self) { assert!(self.height > 0); - let top = BoxedNode::as_ptr(&self.node); + let top = self.node; - let mut internal_node = unsafe { self.internal_node_as_mut() }; - let internal_node = NodeRef::as_internal_mut(&mut internal_node); - self.node = unsafe { internal_node.edges[0].assume_init_read() }; - self.height -= 1; - self.node_as_mut().clear_parent_link(); + let internal_node = NodeRef { height: self.height, node: top, _marker: PhantomData }; + *self = internal_node.first_edge().descend(); + self.borrow_mut().clear_parent_link(); unsafe { Global.dealloc(top.cast(), Layout::new::<InternalNode<K, V>>()); @@ -755,10 +733,10 @@ impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { ForceResult::Leaf(_) => None, ForceResult::Internal(internal) => { let boxed_node = ptr::read(internal.reborrow().edge_at(idx + 1)); - let mut edge = Root { node: boxed_node, height: internal.height - 1 }; + let mut edge = Root::from_boxed_node(boxed_node, internal.height - 1); // In practice, clearing the parent is a waste of time, because we will // insert the node elsewhere and set its parent link again. - edge.node_as_mut().clear_parent_link(); + edge.borrow_mut().clear_parent_link(); Some(edge) } }; @@ -784,10 +762,10 @@ impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { ForceResult::Internal(mut internal) => { let boxed_node = slice_remove(internal.reborrow_mut().into_edge_area_slice(), 0); - let mut edge = Root { node: boxed_node, height: internal.height - 1 }; + let mut edge = Root::from_boxed_node(boxed_node, internal.height - 1); // In practice, clearing the parent is a waste of time, because we will // insert the node elsewhere and set its parent link again. - edge.node_as_mut().clear_parent_link(); + edge.borrow_mut().clear_parent_link(); internal.correct_childrens_parent_links(0..old_len); @@ -1028,17 +1006,17 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark } else { let (middle_kv_idx, insertion) = splitpoint(self.idx); let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; - let (mut left, k, v, mut right) = middle.split(); + let mut result = middle.split(); let mut insertion_edge = match insertion { LeftOrRight::Left(insert_idx) => unsafe { - Handle::new_edge(left.reborrow_mut(), insert_idx) + Handle::new_edge(result.left.reborrow_mut(), insert_idx) }, LeftOrRight::Right(insert_idx) => unsafe { - Handle::new_edge(right.leaf_node_as_mut(), insert_idx) + Handle::new_edge(result.right.borrow_mut(), insert_idx) }, }; let val_ptr = insertion_edge.insert_fit(key, val); - (InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }), val_ptr) + (InsertResult::Split(result), val_ptr) } } } @@ -1092,17 +1070,17 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, } else { let (middle_kv_idx, insertion) = splitpoint(self.idx); let middle = unsafe { Handle::new_kv(self.node, middle_kv_idx) }; - let (mut left, k, v, mut right) = middle.split(); + let mut result = middle.split(); let mut insertion_edge = match insertion { LeftOrRight::Left(insert_idx) => unsafe { - Handle::new_edge(left.reborrow_mut(), insert_idx) + Handle::new_edge(result.left.reborrow_mut(), insert_idx) }, LeftOrRight::Right(insert_idx) => unsafe { - Handle::new_edge(right.internal_node_as_mut(), insert_idx) + Handle::new_edge(result.right.borrow_mut(), insert_idx) }, }; insertion_edge.insert_fit(key, val, edge); - InsertResult::Split(SplitResult { left: left.forget_type(), k, v, right }) + InsertResult::Split(result) } } } @@ -1124,16 +1102,16 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark (InsertResult::Fit(handle), ptr) => { return (InsertResult::Fit(handle.forget_node_type()), ptr); } - (InsertResult::Split(split), val_ptr) => (split, val_ptr), + (InsertResult::Split(split), val_ptr) => (split.forget_node_type(), val_ptr), }; loop { split = match split.left.ascend() { - Ok(parent) => match parent.insert(split.k, split.v, split.right) { + Ok(parent) => match parent.insert(split.kv.0, split.kv.1, split.right) { InsertResult::Fit(handle) => { return (InsertResult::Fit(handle.forget_node_type()), val_ptr); } - InsertResult::Split(split) => split, + InsertResult::Split(split) => split.forget_node_type(), }, Err(root) => { return (InsertResult::Split(SplitResult { left: root, ..split }), val_ptr); @@ -1239,14 +1217,14 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, mark /// - The key and value pointed to by this handle are extracted. /// - All the key/value pairs to the right of this handle are put into a newly /// allocated node. - pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, K, V, Root<K, V>) { + pub fn split(mut self) -> SplitResult<'a, K, V, marker::Leaf> { unsafe { let mut new_node = Box::new(LeafNode::new()); - let (k, v) = self.split_leaf_data(&mut new_node); + let kv = self.split_leaf_data(&mut new_node); - let right = Root { node: BoxedNode::from_leaf(new_node), height: 0 }; - (self.node, k, v, right) + let right = NodeRef::from_new_leaf(new_node); + SplitResult { left: self.node, kv, right } } } @@ -1272,7 +1250,7 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, /// - The key and value pointed to by this handle are extracted. /// - All the edges and key/value pairs to the right of this handle are put into /// a newly allocated node. - pub fn split(mut self) -> (NodeRef<marker::Mut<'a>, K, V, marker::Internal>, K, V, Root<K, V>) { + pub fn split(mut self) -> SplitResult<'a, K, V, marker::Internal> { unsafe { let mut new_node = Box::new(InternalNode::new()); let new_len = self.split_new_node_len(); @@ -1282,14 +1260,14 @@ impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Internal>, new_node.edges.as_mut_ptr(), new_len + 1, ); - let (k, v) = self.split_leaf_data(&mut new_node.data); + let kv = self.split_leaf_data(&mut new_node.data); let height = self.node.height; - let mut right = Root { node: BoxedNode::from_internal(new_node), height }; + let mut right = NodeRef::from_new_internal(new_node, height); - right.internal_node_as_mut().correct_childrens_parent_links(0..=new_len); + right.borrow_mut().correct_childrens_parent_links(0..=new_len); - (self.node, k, v, right) + SplitResult { left: self.node, kv, right } } } } @@ -1756,20 +1734,30 @@ pub enum ForceResult<Leaf, Internal> { } /// Result of insertion, when a node needed to expand beyond its capacity. -/// Does not distinguish between `Leaf` and `Internal` because `Root` doesn't. -pub struct SplitResult<'a, K, V> { - // Altered node in existing tree with elements and edges that belong to the left of `k`. - pub left: NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, +pub struct SplitResult<'a, K, V, NodeType> { + // Altered node in existing tree with elements and edges that belong to the left of `kv`. + pub left: NodeRef<marker::Mut<'a>, K, V, NodeType>, // Some key and value split off, to be inserted elsewhere. - pub k: K, - pub v: V, - // Owned, unattached, new node with elements and edges that belong to the right of `k`. - pub right: Root<K, V>, + pub kv: (K, V), + // Owned, unattached, new node with elements and edges that belong to the right of `kv`. + pub right: NodeRef<marker::Owned, K, V, NodeType>, +} + +impl<'a, K, V> SplitResult<'a, K, V, marker::Leaf> { + pub fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> { + SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() } + } +} + +impl<'a, K, V> SplitResult<'a, K, V, marker::Internal> { + pub fn forget_node_type(self) -> SplitResult<'a, K, V, marker::LeafOrInternal> { + SplitResult { left: self.left.forget_type(), kv: self.kv, right: self.right.forget_type() } + } } -pub enum InsertResult<'a, K, V, Type> { - Fit(Handle<NodeRef<marker::Mut<'a>, K, V, Type>, marker::KV>), - Split(SplitResult<'a, K, V>), +pub enum InsertResult<'a, K, V, NodeType> { + Fit(Handle<NodeRef<marker::Mut<'a>, K, V, NodeType>, marker::KV>), + Split(SplitResult<'a, K, V, NodeType>), } pub mod marker { diff --git a/library/alloc/src/collections/btree/node/tests.rs b/library/alloc/src/collections/btree/node/tests.rs index b04b29320ac..bbf35891b56 100644 --- a/library/alloc/src/collections/btree/node/tests.rs +++ b/library/alloc/src/collections/btree/node/tests.rs @@ -74,16 +74,19 @@ fn test_splitpoint() { #[test] fn test_partial_cmp_eq() { - let mut root1: Root<i32, ()> = Root::new_leaf(); - let mut leaf1 = unsafe { root1.leaf_node_as_mut() }; + let mut root1 = NodeRef::new(); + let mut leaf1 = root1.borrow_mut(); leaf1.push(1, ()); + let mut root1 = root1.forget_type(); root1.push_internal_level(); - let root2: Root<i32, ()> = Root::new_leaf(); + let root2 = Root::new_leaf(); + root1.reborrow().assert_back_pointers(); + root2.reborrow().assert_back_pointers(); - let leaf_edge_1a = root1.node_as_ref().first_leaf_edge().forget_node_type(); - let leaf_edge_1b = root1.node_as_ref().last_leaf_edge().forget_node_type(); - let top_edge_1 = root1.node_as_ref().first_edge(); - let top_edge_2 = root2.node_as_ref().first_edge(); + let leaf_edge_1a = root1.reborrow().first_leaf_edge().forget_node_type(); + let leaf_edge_1b = root1.reborrow().last_leaf_edge().forget_node_type(); + let top_edge_1 = root1.reborrow().first_edge(); + let top_edge_2 = root2.reborrow().first_edge(); assert!(leaf_edge_1a == leaf_edge_1a); assert!(leaf_edge_1a != leaf_edge_1b); @@ -100,8 +103,8 @@ fn test_partial_cmp_eq() { assert_eq!(top_edge_1.partial_cmp(&top_edge_2), None); root1.pop_internal_level(); - unsafe { root1.into_ref().deallocate_and_ascend() }; - unsafe { root2.into_ref().deallocate_and_ascend() }; + unsafe { root1.deallocate_and_ascend() }; + unsafe { root2.deallocate_and_ascend() }; } #[test] diff --git a/library/alloc/src/collections/btree/split.rs b/library/alloc/src/collections/btree/split.rs index cd9615a330d..701f36c37ee 100644 --- a/library/alloc/src/collections/btree/split.rs +++ b/library/alloc/src/collections/btree/split.rs @@ -9,7 +9,7 @@ impl<K, V> Root<K, V> { K: Borrow<Q>, { debug_assert!(right_root.height() == 0); - debug_assert!(right_root.node_as_ref().len() == 0); + debug_assert!(right_root.len() == 0); let left_root = self; for _ in 0..left_root.height() { @@ -17,8 +17,8 @@ impl<K, V> Root<K, V> { } { - let mut left_node = left_root.node_as_mut(); - let mut right_node = right_root.node_as_mut(); + let mut left_node = left_root.borrow_mut(); + let mut right_node = right_root.borrow_mut(); loop { let mut split_edge = match search_node(left_node, key) { @@ -48,7 +48,7 @@ impl<K, V> Root<K, V> { /// Removes empty levels on the top, but keeps an empty leaf if the entire tree is empty. fn fix_top(&mut self) { - while self.height() > 0 && self.node_as_ref().len() == 0 { + while self.height() > 0 && self.len() == 0 { self.pop_internal_level(); } } @@ -57,7 +57,7 @@ impl<K, V> Root<K, V> { self.fix_top(); { - let mut cur_node = self.node_as_mut(); + let mut cur_node = self.borrow_mut(); while let Internal(node) = cur_node.force() { let mut last_kv = node.last_kv().consider_for_balancing(); @@ -83,7 +83,7 @@ impl<K, V> Root<K, V> { self.fix_top(); { - let mut cur_node = self.node_as_mut(); + let mut cur_node = self.borrow_mut(); while let Internal(node) = cur_node.force() { let mut first_kv = node.first_kv().consider_for_balancing(); diff --git a/src/etc/gdb_providers.py b/src/etc/gdb_providers.py index eec3027085c..b5ade324bba 100644 --- a/src/etc/gdb_providers.py +++ b/src/etc/gdb_providers.py @@ -207,42 +207,43 @@ class StdRefCellProvider: yield "borrow", self.borrow -# Yields children (in a provider's sense of the word) for a tree headed by a BoxedNode. -# In particular, yields each key/value pair in the node and in any child nodes. -def children_of_node(boxed_node, height): - def cast_to_internal(node): - internal_type_name = node.type.target().name.replace("LeafNode", "InternalNode", 1) - internal_type = lookup_type(internal_type_name) - return node.cast(internal_type.pointer()) - - node_ptr = unwrap_unique_or_non_null(boxed_node["ptr"]) - leaf = node_ptr.dereference() - keys = leaf["keys"] - vals = leaf["vals"] - edges = cast_to_internal(node_ptr)["edges"] if height > 0 else None - length = int(leaf["len"]) - - for i in xrange(0, length + 1): - if height > 0: - boxed_child_node = edges[i]["value"]["value"] - for child in children_of_node(boxed_child_node, height - 1): - yield child - if i < length: - # Avoid "Cannot perform pointer math on incomplete type" on zero-sized arrays. - key = keys[i]["value"]["value"] if keys.type.sizeof > 0 else "()" - val = vals[i]["value"]["value"] if vals.type.sizeof > 0 else "()" - yield key, val - - -# Yields children for a BTreeMap. -def children_of_map(map): +# Yields children (in a provider's sense of the word) for a BTreeMap. +def children_of_btree_map(map): + # Yields each key/value pair in the node and in any child nodes. + def children_of_node(node_ptr, height): + def cast_to_internal(node): + internal_type_name = node.type.target().name.replace("LeafNode", "InternalNode", 1) + internal_type = lookup_type(internal_type_name) + return node.cast(internal_type.pointer()) + + leaf = node_ptr.dereference() + keys = leaf["keys"] + vals = leaf["vals"] + edges = cast_to_internal(node_ptr)["edges"] if height > 0 else None + length = leaf["len"] + + for i in xrange(0, length + 1): + if height > 0: + boxed_child_node = edges[i]["value"]["value"] + child_node = unwrap_unique_or_non_null(boxed_child_node["ptr"]) + for child in children_of_node(child_node, height - 1): + yield child + if i < length: + # Avoid "Cannot perform pointer math on incomplete type" on zero-sized arrays. + key = keys[i]["value"]["value"] if keys.type.sizeof > 0 else "()" + val = vals[i]["value"]["value"] if vals.type.sizeof > 0 else "()" + yield key, val + if map["length"] > 0: root = map["root"] if root.type.name.startswith("core::option::Option<"): root = root.cast(gdb.lookup_type(root.type.name[21:-1])) - boxed_root_node = root["node"] + node_ptr = root["node"] + if node_ptr.type.name.startswith("alloc::collections::btree::node::BoxedNode<"): + node_ptr = node_ptr["ptr"] + node_ptr = unwrap_unique_or_non_null(node_ptr) height = root["height"] - for child in children_of_node(boxed_root_node, height): + for child in children_of_node(node_ptr, height): yield child @@ -255,7 +256,7 @@ class StdBTreeSetProvider: def children(self): inner_map = self.valobj["map"] - for i, (child, _) in enumerate(children_of_map(inner_map)): + for i, (child, _) in enumerate(children_of_btree_map(inner_map)): yield "[{}]".format(i), child @staticmethod @@ -271,7 +272,7 @@ class StdBTreeMapProvider: return "BTreeMap(size={})".format(self.valobj["length"]) def children(self): - for i, (key, val) in enumerate(children_of_map(self.valobj)): + for i, (key, val) in enumerate(children_of_btree_map(self.valobj)): yield "key{}".format(i), key yield "val{}".format(i), val diff --git a/src/test/debuginfo/pretty-std-collections.rs b/src/test/debuginfo/pretty-std-collections.rs index cc2a3a34510..b79f00a9d04 100644 --- a/src/test/debuginfo/pretty-std-collections.rs +++ b/src/test/debuginfo/pretty-std-collections.rs @@ -101,7 +101,7 @@ fn main() { btree_set.insert(i); } - let mut empty_btree_set: BTreeSet<i32> = BTreeSet::new(); + let empty_btree_set: BTreeSet<i32> = BTreeSet::new(); // BTreeMap let mut btree_map = BTreeMap::new(); @@ -109,7 +109,7 @@ fn main() { btree_map.insert(i, i); } - let mut empty_btree_map: BTreeMap<i32, u32> = BTreeMap::new(); + let empty_btree_map: BTreeMap<i32, u32> = BTreeMap::new(); let mut option_btree_map: BTreeMap<bool, Option<bool>> = BTreeMap::new(); option_btree_map.insert(false, None); |