From ef6060c863c86e1422baa2cc85ae75af22feaf51 Mon Sep 17 00:00:00 2001 From: C Jones Date: Mon, 30 Apr 2018 17:34:14 -0400 Subject: Add a statically allocated empty node for empty maps This gives a pointer to that static empty node instead of allocating a new node, and then whenever inserting makes sure that the root isn't that empty node. --- src/liballoc/btree/map.rs | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'src/liballoc/btree/map.rs') diff --git a/src/liballoc/btree/map.rs b/src/liballoc/btree/map.rs index 3984379ea86..985a41722d7 100644 --- a/src/liballoc/btree/map.rs +++ b/src/liballoc/btree/map.rs @@ -523,7 +523,7 @@ impl BTreeMap { #[stable(feature = "rust1", since = "1.0.0")] pub fn new() -> BTreeMap { BTreeMap { - root: node::Root::new_leaf(), + root: node::Root::shared_empty_root(), length: 0, } } @@ -544,7 +544,6 @@ impl BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { - // FIXME(gereeter) .clear() allocates *self = BTreeMap::new(); } @@ -687,6 +686,10 @@ impl BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn insert(&mut self, key: K, value: V) -> Option { + if self.root.is_shared_root() { + self.root = node::Root::new_leaf(); + } + match self.entry(key) { Occupied(mut entry) => Some(entry.insert(value)), Vacant(entry) => { @@ -890,6 +893,10 @@ impl BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn entry(&mut self, key: K) -> Entry { + if self.root.is_shared_root() { + self.root = node::Root::new_leaf(); + } + match search::search_tree(self.root.as_mut(), &key) { Found(handle) => { Occupied(OccupiedEntry { @@ -910,6 +917,10 @@ impl BTreeMap { } fn from_sorted_iter>(&mut self, iter: I) { + if self.root.is_shared_root() { + self.root = node::Root::new_leaf(); + } + let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node(); // Iterate through all key-value pairs, pushing them into nodes at the right level. for (key, value) in iter { -- cgit 1.4.1-3-g733a5 From fa62eba92ad9a3d25b200835a5cd3ca48b700d75 Mon Sep 17 00:00:00 2001 From: C Jones Date: Tue, 1 May 2018 00:21:30 -0400 Subject: Don't drop the shared static node We modify the drop implementation in IntoIter to not drop the shared root --- src/liballoc/btree/map.rs | 8 ++++---- src/liballoc/btree/node.rs | 13 +++++++++---- 2 files changed, 13 insertions(+), 8 deletions(-) (limited to 'src/liballoc/btree/map.rs') diff --git a/src/liballoc/btree/map.rs b/src/liballoc/btree/map.rs index 985a41722d7..a88631b1e67 100644 --- a/src/liballoc/btree/map.rs +++ b/src/liballoc/btree/map.rs @@ -686,10 +686,6 @@ impl BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn insert(&mut self, key: K, value: V) -> Option { - if self.root.is_shared_root() { - self.root = node::Root::new_leaf(); - } - match self.entry(key) { Occupied(mut entry) => Some(entry.insert(value)), Vacant(entry) => { @@ -1301,6 +1297,10 @@ impl Drop for IntoIter { self.for_each(drop); unsafe { let leaf_node = ptr::read(&self.front).into_node(); + if leaf_node.is_shared_root() { + return; + } + if let Some(first_parent) = leaf_node.deallocate_and_ascend() { let mut cur_node = first_parent.into_node(); while let Some(parent) = cur_node.deallocate_and_ascend() { diff --git a/src/liballoc/btree/node.rs b/src/liballoc/btree/node.rs index 6381006e7fc..79615e11c67 100644 --- a/src/liballoc/btree/node.rs +++ b/src/liballoc/btree/node.rs @@ -101,6 +101,10 @@ impl LeafNode { len: 0 } } + + fn is_shared_root(&self) -> bool { + self as *const _ == &EMPTY_ROOT_NODE as *const _ as *const LeafNode + } } // We need to implement Sync here in order to make a static instance @@ -185,10 +189,7 @@ unsafe impl Send for Root { } impl Root { pub fn is_shared_root(&self) -> bool { - ptr::eq( - self.node.as_ptr().as_ptr(), - &EMPTY_ROOT_NODE as *const _ as *const LeafNode, - ) + self.as_ref().is_shared_root() } pub fn shared_empty_root() -> Self { @@ -387,6 +388,10 @@ impl NodeRef { } } + pub fn is_shared_root(&self) -> bool { + self.as_leaf().is_shared_root() + } + pub fn keys(&self) -> &[K] { self.reborrow().into_slices().0 } -- cgit 1.4.1-3-g733a5 From f3a3599e090cb6aa63a327351738d7633c934728 Mon Sep 17 00:00:00 2001 From: C Jones Date: Mon, 7 May 2018 19:42:28 -0400 Subject: Add debug asserts and fix some violations --- src/liballoc/btree/map.rs | 5 +++++ src/liballoc/btree/node.rs | 11 +++++++++++ 2 files changed, 16 insertions(+) (limited to 'src/liballoc/btree/map.rs') diff --git a/src/liballoc/btree/map.rs b/src/liballoc/btree/map.rs index a88631b1e67..7ed7fd204fd 100644 --- a/src/liballoc/btree/map.rs +++ b/src/liballoc/btree/map.rs @@ -246,6 +246,9 @@ impl super::Recover for BTreeMap } fn replace(&mut self, key: K) -> Option { + if self.root.is_shared_root() { + self.root = node::Root::new_leaf(); + } match search::search_tree::(self.root.as_mut(), &key) { Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)), GoDown(handle) => { @@ -889,6 +892,7 @@ impl BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn entry(&mut self, key: K) -> Entry { + // FIXME(@porglezomp) Avoid allocating if we don't insert if self.root.is_shared_root() { self.root = node::Root::new_leaf(); } @@ -1026,6 +1030,7 @@ impl BTreeMap { let total_num = self.len(); let mut right = Self::new(); + right.root = node::Root::new_leaf(); for _ in 0..(self.root.as_ref().height()) { right.root.push_level(); } diff --git a/src/liballoc/btree/node.rs b/src/liballoc/btree/node.rs index ce770d384f8..17eee65178e 100644 --- a/src/liballoc/btree/node.rs +++ b/src/liballoc/btree/node.rs @@ -195,6 +195,10 @@ impl Root { } pub fn shared_empty_root() -> Self { + // Ensuring that the shared node hasn't been corrupted by any mutations + debug_assert!(EMPTY_ROOT_NODE.parent == ptr::null()); + debug_assert!(EMPTY_ROOT_NODE.parent_idx == 0); + debug_assert!(EMPTY_ROOT_NODE.len == 0); Root { node: unsafe { BoxedNode::from_ptr(NonNull::new_unchecked( @@ -246,6 +250,7 @@ impl Root { /// new node the root. This increases the height by 1 and is the opposite of `pop_level`. pub fn push_level(&mut self) -> NodeRef { + debug_assert!(!self.is_shared_root()); let mut new_node = Box::new(unsafe { InternalNode::new() }); new_node.edges[0] = unsafe { BoxedNode::from_ptr(self.node.as_ptr()) }; @@ -474,6 +479,7 @@ impl NodeRef { marker::Edge > > { + debug_assert!(!self.is_shared_root()); let node = self.node; let ret = self.ascend().ok(); Global.dealloc(node.as_opaque(), Layout::new::>()); @@ -631,6 +637,7 @@ impl<'a, K, V> NodeRef, K, V, marker::Leaf> { pub fn push(&mut self, key: K, val: V) { // Necessary for correctness, but this is an internal module debug_assert!(self.len() < CAPACITY); + debug_assert!(!self.is_shared_root()); let idx = self.len(); @@ -646,6 +653,7 @@ impl<'a, K, V> NodeRef, K, V, marker::Leaf> { pub fn push_front(&mut self, key: K, val: V) { // Necessary for correctness, but this is an internal module debug_assert!(self.len() < CAPACITY); + debug_assert!(!self.is_shared_root()); unsafe { slice_insert(self.keys_mut(), 0, key); @@ -959,6 +967,7 @@ impl<'a, K, V> Handle, K, V, marker::Leaf>, marker::Edge fn insert_fit(&mut self, key: K, val: V) -> *mut V { // Necessary for correctness, but in a private module debug_assert!(self.node.len() < CAPACITY); + debug_assert!(!self.node.is_shared_root()); unsafe { slice_insert(self.node.keys_mut(), self.idx, key); @@ -1136,6 +1145,7 @@ impl<'a, K, V> Handle, K, V, marker::Leaf>, marker::KV> /// allocated node. pub fn split(mut self) -> (NodeRef, K, V, marker::Leaf>, K, V, Root) { + debug_assert!(!self.node.is_shared_root()); unsafe { let mut new_node = Box::new(LeafNode::new()); @@ -1173,6 +1183,7 @@ impl<'a, K, V> Handle, K, V, marker::Leaf>, marker::KV> /// now adjacent key/value pairs to the left and right of this handle. pub fn remove(mut self) -> (Handle, K, V, marker::Leaf>, marker::Edge>, K, V) { + debug_assert!(!self.node.is_shared_root()); unsafe { let k = slice_remove(self.node.keys_mut(), self.idx); let v = slice_remove(self.node.vals_mut(), self.idx); -- cgit 1.4.1-3-g733a5 From e83c18f91d373592ecf7a0fbbc24d7597925af13 Mon Sep 17 00:00:00 2001 From: C Jones Date: Tue, 8 May 2018 13:28:49 -0400 Subject: Make an ensure_root_is_owned method to reduce duplication Also remove some unnecessary debug_assert! when creating the shared root, since the root should be stored in the rodata and thus be impossible to accidentally modify. --- src/liballoc/btree/map.rs | 21 ++++++++++----------- src/liballoc/btree/node.rs | 4 ---- 2 files changed, 10 insertions(+), 15 deletions(-) (limited to 'src/liballoc/btree/map.rs') diff --git a/src/liballoc/btree/map.rs b/src/liballoc/btree/map.rs index 7ed7fd204fd..bb2c68a27ba 100644 --- a/src/liballoc/btree/map.rs +++ b/src/liballoc/btree/map.rs @@ -246,9 +246,7 @@ impl super::Recover for BTreeMap } fn replace(&mut self, key: K) -> Option { - if self.root.is_shared_root() { - self.root = node::Root::new_leaf(); - } + self.ensure_root_is_owned(); match search::search_tree::(self.root.as_mut(), &key) { Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)), GoDown(handle) => { @@ -893,10 +891,7 @@ impl BTreeMap { #[stable(feature = "rust1", since = "1.0.0")] pub fn entry(&mut self, key: K) -> Entry { // FIXME(@porglezomp) Avoid allocating if we don't insert - if self.root.is_shared_root() { - self.root = node::Root::new_leaf(); - } - + self.ensure_root_is_owned(); match search::search_tree(self.root.as_mut(), &key) { Found(handle) => { Occupied(OccupiedEntry { @@ -917,10 +912,7 @@ impl BTreeMap { } fn from_sorted_iter>(&mut self, iter: I) { - if self.root.is_shared_root() { - self.root = node::Root::new_leaf(); - } - + self.ensure_root_is_owned(); let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node(); // Iterate through all key-value pairs, pushing them into nodes at the right level. for (key, value) in iter { @@ -1165,6 +1157,13 @@ impl BTreeMap { self.fix_top(); } + + /// If the root node is the shared root node, allocate our own node. + fn ensure_root_is_owned(&mut self) { + if self.root.is_shared_root() { + self.root = node::Root::new_leaf(); + } + } } #[stable(feature = "rust1", since = "1.0.0")] diff --git a/src/liballoc/btree/node.rs b/src/liballoc/btree/node.rs index 17eee65178e..431695c32ab 100644 --- a/src/liballoc/btree/node.rs +++ b/src/liballoc/btree/node.rs @@ -195,10 +195,6 @@ impl Root { } pub fn shared_empty_root() -> Self { - // Ensuring that the shared node hasn't been corrupted by any mutations - debug_assert!(EMPTY_ROOT_NODE.parent == ptr::null()); - debug_assert!(EMPTY_ROOT_NODE.parent_idx == 0); - debug_assert!(EMPTY_ROOT_NODE.len == 0); Root { node: unsafe { BoxedNode::from_ptr(NonNull::new_unchecked( -- cgit 1.4.1-3-g733a5