From cd639d8927674cda3303c4d4af33565dab12b17b Mon Sep 17 00:00:00 2001 From: Jonathan S Date: Wed, 16 Dec 2015 18:48:11 -0600 Subject: [PATCH] Rewrite BTreeMap to use parent pointers. --- src/libcollections/btree/map.rs | 2156 ++++++++++++-------------- src/libcollections/btree/mod.rs | 1 + src/libcollections/btree/node.rs | 2242 +++++++++++----------------- src/libcollections/btree/search.rs | 76 + src/libcollections/lib.rs | 4 +- 5 files changed, 1884 insertions(+), 2595 deletions(-) create mode 100644 src/libcollections/btree/search.rs diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index 74895f16596..2375a63fbd7 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -1,4 +1,4 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT // file at the top-level directory of this distribution and at // http://rust-lang.org/COPYRIGHT. // @@ -8,32 +8,24 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -// This implementation is largely based on the high-level description and analysis of B-Trees -// found in *Open Data Structures* (ODS). Although our implementation does not use any of -// the source found in ODS, if one wishes to review the high-level design of this structure, it -// can be freely downloaded at http://opendatastructures.org/. Its contents are as of this -// writing (August 2014) freely licensed under the following Creative Commons Attribution -// License: [CC BY 2.5 CA](http://creativecommons.org/licenses/by/2.5/ca/). - -use self::Entry::*; - use core::cmp::Ordering; use core::fmt::Debug; use core::hash::{Hash, Hasher}; -use core::iter::{Map, FromIterator}; +use core::iter::FromIterator; use core::ops::Index; -use core::{fmt, mem, usize}; -use Bound::{self, Included, Excluded, Unbounded}; +use core::{fmt, intrinsics, mem, ptr}; use borrow::Borrow; -use vec_deque::VecDeque; +use Bound::{self, Included, Excluded, Unbounded}; + +use super::node::{self, NodeRef, Handle, marker}; +use super::search; -use self::Continuation::{Continue, Finished}; -use self::StackOp::*; -use super::node::ForceResult::{Leaf, Internal}; -use super::node::TraversalItem::{self, Elem, Edge}; -use super::node::{Traversal, MutTraversal, MoveTraversal}; -use super::node::{self, Node, Found, GoDown}; +use super::node::InsertResult::*; +use super::node::ForceResult::*; +use super::search::SearchResult::*; +use self::UnderflowResult::*; +use self::Entry::*; /// A map based on a B-Tree. /// @@ -65,60 +57,173 @@ /// It is a logic error for a key to be modified in such a way that the key's ordering relative to /// any other key, as determined by the `Ord` trait, changes while it is in the map. This is /// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code. -#[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct BTreeMap { - root: Node, - length: usize, - depth: usize, - b: usize, + root: node::Root, + length: usize +} + +impl Drop for BTreeMap { + #[unsafe_destructor_blind_to_params] + fn drop(&mut self) { + unsafe { + for _ in ptr::read(self).into_iter() { } + } + } +} + +impl Clone for BTreeMap { + fn clone(&self) -> BTreeMap { + fn clone_subtree( + node: node::NodeRef) + -> BTreeMap { + + match node.force() { + Leaf(leaf) => { + let mut out_tree = BTreeMap { + root: node::Root::new_leaf(), + length: 0 + }; + + { + let mut out_node = match out_tree.root.as_mut().force() { + Leaf(leaf) => leaf, + Internal(_) => unreachable!() + }; + + let mut in_edge = leaf.first_edge(); + while let Ok(kv) = in_edge.right_kv() { + let (k, v) = kv.into_kv(); + in_edge = kv.right_edge(); + + out_node.push(k.clone(), v.clone()); + out_tree.length += 1; + } + } + + out_tree + }, + Internal(internal) => { + let mut out_tree = clone_subtree(internal.first_edge().descend()); + + { + let mut out_node = out_tree.root.push_level(); + let mut in_edge = internal.first_edge(); + while let Ok(kv) = in_edge.right_kv() { + let (k, v) = kv.into_kv(); + in_edge = kv.right_edge(); + + let k = (*k).clone(); + let v = (*v).clone(); + let subtree = clone_subtree(in_edge.descend()); + + // We can't destructure subtree directly + // because BTreeMap implements Drop + let (subroot, sublength) = unsafe { + let root = ptr::read(&subtree.root); + let length = subtree.length; + mem::forget(subtree); + (root, length) + }; + + out_node.push(k, v, subroot); + out_tree.length += 1 + sublength; + } + } + + out_tree + } + } + } + + clone_subtree(self.root.as_ref()) + } } -/// An abstract base over-which all other BTree iterators are built. -#[derive(Clone)] -struct AbsIter { - traversals: VecDeque, - size: usize, +impl super::Recover for BTreeMap + where K: Borrow + Ord, + Q: Ord +{ + type Key = K; + + fn get(&self, key: &Q) -> Option<&K> { + match search::search_tree(self.root.as_ref(), key) { + Found(handle) => Some(handle.into_kv().0), + GoDown(_) => None + } + } + + fn take(&mut self, key: &Q) -> Option { + match search::search_tree(self.root.as_mut(), key) { + Found(handle) => { + Some(OccupiedEntry { + handle: handle, + length: &mut self.length + }.remove_kv().0) + }, + GoDown(_) => None + } + } + + fn replace(&mut self, key: K) -> Option { + match search::search_tree::(self.root.as_mut(), &key) { + Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)), + GoDown(handle) => { + VacantEntry { + key: key, + handle: handle, + length: &mut self.length + }.insert(()); + None + } + } + } } /// An iterator over a BTreeMap's entries. #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, K: 'a, V: 'a> { - inner: AbsIter>, + range: Range<'a, K, V>, + length: usize } /// A mutable iterator over a BTreeMap's entries. #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, K: 'a, V: 'a> { - inner: AbsIter>, + range: RangeMut<'a, K, V>, + length: usize } /// An owning iterator over a BTreeMap's entries. #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter { - inner: AbsIter>, + front: Handle, marker::Edge>, + back: Handle, marker::Edge>, + length: usize } /// An iterator over a BTreeMap's keys. #[stable(feature = "rust1", since = "1.0.0")] pub struct Keys<'a, K: 'a, V: 'a> { - inner: Map, fn((&'a K, &'a V)) -> &'a K>, + inner: Iter<'a, K, V>, } /// An iterator over a BTreeMap's values. #[stable(feature = "rust1", since = "1.0.0")] pub struct Values<'a, K: 'a, V: 'a> { - inner: Map, fn((&'a K, &'a V)) -> &'a V>, + inner: Iter<'a, K, V>, } /// An iterator over a sub-range of BTreeMap's entries. pub struct Range<'a, K: 'a, V: 'a> { - inner: AbsIter>, + front: Handle, K, V, marker::Leaf>, marker::Edge>, + back: Handle, K, V, marker::Leaf>, marker::Edge> } /// A mutable iterator over a sub-range of BTreeMap's entries. pub struct RangeMut<'a, K: 'a, V: 'a> { - inner: AbsIter>, + front: Handle, K, V, marker::Leaf>, marker::Edge>, + back: Handle, K, V, marker::Leaf>, marker::Edge> } /// A view into a single entry in a map, which may either be vacant or occupied. @@ -141,28 +246,30 @@ pub enum Entry<'a, K: 'a, V: 'a> { #[stable(feature = "rust1", since = "1.0.0")] pub struct VacantEntry<'a, K: 'a, V: 'a> { key: K, - stack: stack::SearchStack<'a, K, V, node::handle::Edge, node::handle::Leaf>, + handle: Handle, K, V, marker::Leaf>, marker::Edge>, + length: &'a mut usize } /// An occupied Entry. #[stable(feature = "rust1", since = "1.0.0")] pub struct OccupiedEntry<'a, K: 'a, V: 'a> { - stack: stack::SearchStack<'a, K, V, node::handle::KV, node::handle::LeafOrInternal>, + handle: Handle, + K, V, + marker::LeafOrInternal + >, marker::KV>, + + length: &'a mut usize } impl BTreeMap { /// Makes a new empty BTreeMap with a reasonable choice for B. #[stable(feature = "rust1", since = "1.0.0")] - #[allow(deprecated)] pub fn new() -> BTreeMap { BTreeMap { - length: 0, - depth: 1, - root: Node::make_leaf_root(6), - // FIXME(Gankro): Tune this as a function of size_of? - b: 6, + root: node::Root::new_leaf(), + length: 0 } - } /// Clears the map, removing all values. @@ -179,18 +286,10 @@ pub fn new() -> BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { - // avoid recursive destructors by manually traversing the tree - for _ in mem::replace(self, BTreeMap::new()) {} + // FIXME(gereeter) .clear() allocates + *self = BTreeMap::new(); } - // Searching in a B-Tree is pretty straightforward. - // - // Start at the root. Try to find the key in the current node. If we find it, return it. - // If it's not in there, follow the edge *before* the smallest key larger than - // the search key. If no such key exists (they're *all* smaller), then just take the last - // edge in the node. If we're in a leaf and we don't find our key, then it's not - // in the tree. - /// Returns a reference to the value corresponding to the key. /// /// The key may be any borrowed form of the map's key type, but the ordering @@ -207,24 +306,10 @@ pub fn clear(&mut self) { /// assert_eq!(map.get(&2), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn get(&self, key: &Q) -> Option<&V> - where K: Borrow, - Q: Ord - { - let mut cur_node = &self.root; - loop { - match Node::search(cur_node, key) { - Found(handle) => return Some(handle.into_kv().1), - GoDown(handle) => { - match handle.force() { - Leaf(_) => return None, - Internal(internal_handle) => { - cur_node = internal_handle.into_edge(); - continue; - } - } - } - } + pub fn get(&self, key: &Q) -> Option<&V> where K: Borrow, Q: Ord { + match search::search_tree(self.root.as_ref(), key) { + Found(handle) => Some(handle.into_kv().1), + GoDown(_) => None } } @@ -244,10 +329,7 @@ pub fn get(&self, key: &Q) -> Option<&V> /// assert_eq!(map.contains_key(&2), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains_key(&self, key: &Q) -> bool - where K: Borrow, - Q: Ord - { + pub fn contains_key(&self, key: &Q) -> bool where K: Borrow, Q: Ord { self.get(key).is_some() } @@ -270,55 +352,13 @@ pub fn contains_key(&self, key: &Q) -> bool /// ``` // See `get` for implementation notes, this is basically a copy-paste with mut's added #[stable(feature = "rust1", since = "1.0.0")] - pub fn get_mut(&mut self, key: &Q) -> Option<&mut V> - where K: Borrow, - Q: Ord - { - // temp_node is a Borrowck hack for having a mutable value outlive a loop iteration - let mut temp_node = &mut self.root; - loop { - let cur_node = temp_node; - match Node::search(cur_node, key) { - Found(handle) => return Some(handle.into_kv_mut().1), - GoDown(handle) => { - match handle.force() { - Leaf(_) => return None, - Internal(internal_handle) => { - temp_node = internal_handle.into_edge_mut(); - continue; - } - } - } - } + pub fn get_mut(&mut self, key: &Q) -> Option<&mut V> where K: Borrow, Q: Ord { + match search::search_tree(self.root.as_mut(), key) { + Found(handle) => Some(handle.into_kv_mut().1), + GoDown(_) => None } } - // Insertion in a B-Tree is a bit complicated. - // - // First we do the same kind of search described in `find`. But we need to maintain a stack of - // all the nodes/edges in our search path. If we find a match for the key we're trying to - // insert, just swap the vals and return the old ones. However, when we bottom out in a leaf, - // we attempt to insert our key-value pair at the same location we would want to follow another - // edge. - // - // If the node has room, then this is done in the obvious way by shifting elements. However, - // if the node itself is full, we split node into two, and give its median key-value - // pair to its parent to insert the new node with. Of course, the parent may also be - // full, and insertion can propagate until we reach the root. If we reach the root, and - // it is *also* full, then we split the root and place the two nodes under a newly made root. - // - // Note that we subtly deviate from Open Data Structures in our implementation of split. - // ODS describes inserting into the node *regardless* of its capacity, and then - // splitting *afterwards* if it happens to be overfull. However, this is inefficient. - // Instead, we split beforehand, and then insert the key-value pair into the appropriate - // result node. This has two consequences: - // - // 1) While ODS produces a left node of size B-1, and a right node of size B, - // we may potentially reverse this. However, this shouldn't effect the analysis. - // - // 2) While ODS may potentially return the pair we *just* inserted after - // the split, we will never do this. Again, this shouldn't effect the analysis. - /// Inserts a key-value pair into the map. /// /// If the map did not have this key present, `None` is returned. @@ -343,98 +383,16 @@ pub fn get_mut(&mut self, key: &Q) -> Option<&mut V> /// assert_eq!(map[&37], "c"); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(&mut self, mut key: K, mut value: V) -> Option { - // This is a stack of rawptrs to nodes paired with indices, respectively - // representing the nodes and edges of our search path. We have to store rawptrs - // because as far as Rust is concerned, we can mutate aliased data with such a - // stack. It is of course correct, but what it doesn't know is that we will only - // be popping and using these ptrs one at a time in child-to-parent order. The alternative - // to doing this is to take the Nodes from their parents. This actually makes - // borrowck *really* happy and everything is pretty smooth. However, this creates - // *tons* of pointless writes, and requires us to always walk all the way back to - // the root after an insertion, even if we only needed to change a leaf. Therefore, - // we accept this potential unsafety and complexity in the name of performance. - // - // Regardless, the actual dangerous logic is completely abstracted away from BTreeMap - // by the stack module. All it can do is immutably read nodes, and ask the search stack - // to proceed down some edge by index. This makes the search logic we'll be reusing in a - // few different methods much neater, and of course drastically improves safety. - let mut stack = stack::PartialSearchStack::new(self); - - loop { - let result = stack.with(move |pusher, node| { - // Same basic logic as found in `find`, but with PartialSearchStack mediating the - // actual nodes for us - match Node::search(node, &key) { - Found(mut handle) => { - // Perfect match, swap the values and return the old one - mem::swap(handle.val_mut(), &mut value); - Finished(Some(value)) - } - GoDown(handle) => { - // We need to keep searching, try to get the search stack - // to go down further - match handle.force() { - Leaf(leaf_handle) => { - // We've reached a leaf, perform the insertion here - pusher.seal(leaf_handle).insert(key, value); - Finished(None) - } - Internal(internal_handle) => { - // We've found the subtree to insert this key/value pair in, - // keep searching - Continue((pusher.push(internal_handle), key, value)) - } - } - } - } - }); - match result { - Finished(ret) => return ret, - Continue((new_stack, renewed_key, renewed_val)) => { - stack = new_stack; - key = renewed_key; - value = renewed_val; - } + pub fn insert(&mut self, key: K, value: V) -> Option { + match self.entry(key) { + Occupied(mut entry) => Some(entry.insert(value)), + Vacant(entry) => { + entry.insert(value); + None } } } - // Deletion is the most complicated operation for a B-Tree. - // - // First we do the same kind of search described in - // `find`. But we need to maintain a stack of all the nodes/edges in our search path. - // If we don't find the key, then we just return `None` and do nothing. If we do find the - // key, we perform two operations: remove the item, and then possibly handle underflow. - // - // # removing the item - // If the node is a leaf, we just remove the item, and shift - // any items after it back to fill the hole. - // - // If the node is an internal node, we *swap* the item with the smallest item in - // in its right subtree (which must reside in a leaf), and then revert to the leaf - // case - // - // # handling underflow - // After removing an item, there may be too few items in the node. We want nodes - // to be mostly full for efficiency, although we make an exception for the root, which - // may have as few as one item. If this is the case, we may first try to steal - // an item from our left or right neighbour. - // - // To steal from the left (right) neighbour, - // we take the largest (smallest) item and child from it. We then swap the taken item - // with the item in their mutual parent that separates them, and then insert the - // parent's item and the taken child into the first (last) index of the underflowed node. - // - // However, stealing has the possibility of underflowing our neighbour. If this is the - // case, we instead *merge* with our neighbour. This of course reduces the number of - // children in the parent. Therefore, we also steal the item that separates the now - // merged nodes, and insert it into the merged node. - // - // Merging may cause the parent to underflow. If this is the case, then we must repeat - // the underflow handling process on the parent. If merging merges the last two children - // of the root, then we replace the root with the merged node. - /// Removes a key from the map, returning the value at the key if the key /// was previously in the map. /// @@ -452,73 +410,201 @@ pub fn insert(&mut self, mut key: K, mut value: V) -> Option { /// assert_eq!(map.remove(&1), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove(&mut self, key: &Q) -> Option - where K: Borrow, - Q: Ord - { - // See `swap` for a more thorough description of the stuff going on in here - let mut stack = stack::PartialSearchStack::new(self); - loop { - let result = stack.with(move |pusher, node| { - match Node::search(node, key) { - Found(handle) => { - // Perfect match. Terminate the stack here, and remove the entry - Finished(Some(pusher.seal(handle).remove())) - } - GoDown(handle) => { - // We need to keep searching, try to go down the next edge - match handle.force() { - // We're at a leaf; the key isn't in here - Leaf(_) => Finished(None), - Internal(internal_handle) => Continue(pusher.push(internal_handle)), - } - } - } - }); - match result { - Finished(ret) => return ret.map(|(_, v)| v), - Continue(new_stack) => stack = new_stack, - } + pub fn remove(&mut self, key: &Q) -> Option where K: Borrow, Q: Ord { + match search::search_tree(self.root.as_mut(), key) { + Found(handle) => { + Some(OccupiedEntry { + handle: handle, + length: &mut self.length + }.remove()) + }, + GoDown(_) => None } } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl IntoIterator for BTreeMap { - type Item = (K, V); - type IntoIter = IntoIter; - /// Gets an owning iterator over the entries of the map. + /// Constructs a double-ended iterator over a sub-range of elements in the map, starting + /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative + /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity". + /// Thus range(Unbounded, Unbounded) will yield the whole collection. /// /// # Examples /// /// ``` + /// #![feature(btree_range, collections_bound)] + /// /// use std::collections::BTreeMap; + /// use std::collections::Bound::{Included, Unbounded}; /// /// let mut map = BTreeMap::new(); - /// map.insert(1, "a"); - /// map.insert(2, "b"); - /// map.insert(3, "c"); - /// - /// for (key, value) in map.into_iter() { + /// map.insert(3, "a"); + /// map.insert(5, "b"); + /// map.insert(8, "c"); + /// for (&key, &value) in map.range(Included(&4), Included(&8)) { /// println!("{}: {}", key, value); /// } + /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next()); /// ``` - fn into_iter(self) -> IntoIter { - let len = self.len(); - let mut lca = VecDeque::new(); - lca.push_back(Traverse::traverse(self.root)); - IntoIter { - inner: AbsIter { - traversals: lca, - size: len, + #[unstable(feature = "btree_range", + reason = "matches collection reform specification, waiting for dust to settle", + issue = "27787")] + pub fn range(&self, + min: Bound<&Min>, + max: Bound<&Max>) + -> Range + where K: Borrow + Borrow, + { + let front = match min { + Included(key) => match search::search_tree(self.root.as_ref(), key) { + Found(kv_handle) => match kv_handle.left_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => last_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Excluded(key) => match search::search_tree(self.root.as_ref(), key) { + Found(kv_handle) => match kv_handle.right_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => first_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Unbounded => first_leaf_edge(self.root.as_ref()) + }; + + let back = match max { + Included(key) => match search::search_tree(self.root.as_ref(), key) { + Found(kv_handle) => match kv_handle.right_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => first_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Excluded(key) => match search::search_tree(self.root.as_ref(), key) { + Found(kv_handle) => match kv_handle.left_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => last_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Unbounded => last_leaf_edge(self.root.as_ref()) + }; + + Range { + front: front, + back: back + } + } + + /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting + /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative + /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity". + /// Thus range(Unbounded, Unbounded) will yield the whole collection. + /// + /// # Examples + /// + /// ``` + /// #![feature(btree_range, collections_bound)] + /// + /// use std::collections::BTreeMap; + /// use std::collections::Bound::{Included, Excluded}; + /// + /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter() + /// .map(|&s| (s, 0)) + /// .collect(); + /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) { + /// *balance += 100; + /// } + /// for (name, balance) in &map { + /// println!("{} => {}", name, balance); + /// } + /// ``` + #[unstable(feature = "btree_range", + reason = "matches collection reform specification, waiting for dust to settle", + issue = "27787")] + pub fn range_mut(&mut self, + min: Bound<&Min>, + max: Bound<&Max>) + -> RangeMut + where K: Borrow + Borrow, + { + let root1 = self.root.as_mut(); + let root2 = unsafe { ptr::read(&root1) }; + + let front = match min { + Included(key) => match search::search_tree(root1, key) { + Found(kv_handle) => match kv_handle.left_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => last_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Excluded(key) => match search::search_tree(root1, key) { + Found(kv_handle) => match kv_handle.right_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => first_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Unbounded => first_leaf_edge(root1) + }; + + let back = match max { + Included(key) => match search::search_tree(root2, key) { + Found(kv_handle) => match kv_handle.right_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => first_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom + }, + Excluded(key) => match search::search_tree(root2, key) { + Found(kv_handle) => match kv_handle.left_edge().force() { + Leaf(bottom) => bottom, + Internal(internal) => last_leaf_edge(internal.descend()) + }, + GoDown(bottom) => bottom }, + Unbounded => last_leaf_edge(root2) + }; + + RangeMut { + front: front, + back: back + } + } + + /// Gets the given key's corresponding entry in the map for in-place manipulation. + /// + /// # Examples + /// + /// ``` + /// use std::collections::BTreeMap; + /// + /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); + /// + /// // count the number of occurrences of letters in the vec + /// for x in vec!["a","b","a","c","a","b"] { + /// *count.entry(x).or_insert(0) += 1; + /// } + /// + /// assert_eq!(count["a"], 3); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn entry(&mut self, key: K) -> Entry { + match search::search_tree(self.root.as_mut(), &key) { + Found(handle) => Occupied(OccupiedEntry { + handle: handle, + length: &mut self.length + }), + GoDown(handle) => Vacant(VacantEntry { + key: key, + handle: handle, + length: &mut self.length + }) } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> IntoIterator for &'a BTreeMap { +impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap { type Item = (&'a K, &'a V); type IntoIter = Iter<'a, K, V>; @@ -527,769 +613,570 @@ fn into_iter(self) -> Iter<'a, K, V> { } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> IntoIterator for &'a mut BTreeMap { - type Item = (&'a K, &'a mut V); - type IntoIter = IterMut<'a, K, V>; +impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); - fn into_iter(mut self) -> IterMut<'a, K, V> { - self.iter_mut() + fn next(&mut self) -> Option<(&'a K, &'a V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_unchecked()) } + } } -} -/// A helper enum useful for deciding whether to continue a loop since we can't -/// return from a closure -enum Continuation { - Continue(A), - Finished(B), + fn size_hint(&self) -> (usize, Option) { + (self.length, Some(self.length)) + } } -/// The stack module provides a safe interface for constructing and manipulating a stack of ptrs -/// to nodes. By using this module much better safety guarantees can be made, and more search -/// boilerplate gets cut out. -mod stack { - use core::marker; - use core::mem; - use core::ops::{Deref, DerefMut}; - use super::BTreeMap; - use super::super::node::{self, Node, Fit, Split, Internal, Leaf}; - use super::super::node::handle; - use vec::Vec; - - struct InvariantLifetime<'id>(marker::PhantomData<::core::cell::Cell<&'id ()>>); - - impl<'id> InvariantLifetime<'id> { - fn new() -> InvariantLifetime<'id> { - InvariantLifetime(marker::PhantomData) +impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_back_unchecked()) } } } +} - /// A generic mutable reference, identical to `&mut` except for the fact that its lifetime - /// parameter is invariant. This means that wherever an `IdRef` is expected, only an `IdRef` - /// with the exact requested lifetime can be used. This is in contrast to normal references, - /// where `&'static` can be used in any function expecting any lifetime reference. - pub struct IdRef<'id, T: 'id> { - inner: &'id mut T, - _marker: InvariantLifetime<'id>, - } - - impl<'id, T> Deref for IdRef<'id, T> { - type Target = T; +impl<'a, K: 'a, V: 'a> ExactSizeIterator for Iter<'a, K, V> { + fn len(&self) -> usize { self.length } +} - fn deref(&self) -> &T { - &*self.inner +impl<'a, K, V> Clone for Iter<'a, K, V> { + fn clone(&self) -> Iter<'a, K, V> { + Iter { + range: self.range.clone(), + length: self.length } } +} - impl<'id, T> DerefMut for IdRef<'id, T> { - fn deref_mut(&mut self) -> &mut T { - &mut *self.inner - } +impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut BTreeMap { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + + fn into_iter(self) -> IterMut<'a, K, V> { + self.iter_mut() } +} - type StackItem = node::Handle<*mut Node, handle::Edge, handle::Internal>; - type Stack = Vec>; +impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); - /// A `PartialSearchStack` handles the construction of a search stack. - pub struct PartialSearchStack<'a, K: 'a, V: 'a> { - map: &'a mut BTreeMap, - stack: Stack, - next: *mut Node, + fn next(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_unchecked()) } + } } - /// A `SearchStack` represents a full path to an element or an edge of interest. It provides - /// methods depending on the type of what the path points to for removing an element, inserting - /// a new element, and manipulating to element at the top of the stack. - pub struct SearchStack<'a, K: 'a, V: 'a, Type, NodeType> { - map: &'a mut BTreeMap, - stack: Stack, - top: node::Handle<*mut Node, Type, NodeType>, + fn size_hint(&self) -> (usize, Option) { + (self.length, Some(self.length)) } +} - /// A `PartialSearchStack` that doesn't hold a reference to the next node, and is just - /// just waiting for a `Handle` to that next node to be pushed. See `PartialSearchStack::with` - /// for more details. - pub struct Pusher<'id, 'a, K: 'a, V: 'a> { - map: &'a mut BTreeMap, - stack: Stack, - _marker: InvariantLifetime<'id>, +impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.length == 0 { + None + } else { + self.length -= 1; + unsafe { Some(self.range.next_back_unchecked()) } + } } +} - impl<'a, K, V> PartialSearchStack<'a, K, V> { - /// Creates a new PartialSearchStack from a BTreeMap by initializing the stack with the - /// root of the tree. - pub fn new(map: &'a mut BTreeMap) -> PartialSearchStack<'a, K, V> { - let depth = map.depth; +impl<'a, K: 'a, V: 'a> ExactSizeIterator for IterMut<'a, K, V> { + fn len(&self) -> usize { self.length } +} - PartialSearchStack { - next: &mut map.root as *mut _, - map: map, - stack: Vec::with_capacity(depth), - } - } +impl IntoIterator for BTreeMap { + type Item = (K, V); + type IntoIter = IntoIter; - /// Breaks up the stack into a `Pusher` and the next `Node`, allowing the given closure - /// to interact with, search, and finally push the `Node` onto the stack. The passed in - /// closure must be polymorphic on the `'id` lifetime parameter, as this statically - /// ensures that only `Handle`s from the correct `Node` can be pushed. - /// - /// The reason this works is that the `Pusher` has an `'id` parameter, and will only accept - /// handles with the same `'id`. The closure could only get references with that lifetime - /// through its arguments or through some other `IdRef` that it has lying around. However, - /// no other `IdRef` could possibly work - because the `'id` is held in an invariant - /// parameter, it would need to have precisely the correct lifetime, which would mean that - /// at least one of the calls to `with` wouldn't be properly polymorphic, wanting a - /// specific lifetime instead of the one that `with` chooses to give it. - /// - /// See also Haskell's `ST` monad, which uses a similar trick. - pub fn with FnOnce(Pusher<'id, 'a, K, V>, - IdRef<'id, Node>) -> T>(self, closure: F) -> T { - let pusher = Pusher { - map: self.map, - stack: self.stack, - _marker: InvariantLifetime::new(), - }; - let node = IdRef { - inner: unsafe { &mut *self.next }, - _marker: InvariantLifetime::new(), - }; + fn into_iter(self) -> IntoIter { + let root1 = unsafe { ptr::read(&self.root).into_ref() }; + let root2 = unsafe { ptr::read(&self.root).into_ref() }; + let len = self.length; + mem::forget(self); - closure(pusher, node) + IntoIter { + front: first_leaf_edge(root1), + back: last_leaf_edge(root2), + length: len } } +} - impl<'id, 'a, K, V> Pusher<'id, 'a, K, V> { - /// Pushes the requested child of the stack's current top on top of the stack. If the child - /// exists, then a new PartialSearchStack is yielded. Otherwise, a VacantSearchStack is - /// yielded. - pub fn push(mut self, - mut edge: node::Handle>, handle::Edge, handle::Internal>) - -> PartialSearchStack<'a, K, V> { - self.stack.push(edge.as_raw()); - PartialSearchStack { - map: self.map, - stack: self.stack, - next: edge.edge_mut() as *mut _, - } - } - - /// Converts the PartialSearchStack into a SearchStack. - pub fn seal(self, - mut handle: node::Handle>, - Type, - NodeType>) - -> SearchStack<'a, K, V, Type, NodeType> { - SearchStack { - map: self.map, - stack: self.stack, - top: handle.as_raw(), +impl Drop for IntoIter { + fn drop(&mut self) { + for _ in &mut *self { } + unsafe { + let leaf_node = ptr::read(&self.front).into_node(); + 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() { + cur_node = parent.into_node() + } } } } +} - impl<'a, K, V, NodeType> SearchStack<'a, K, V, handle::KV, NodeType> { - /// Gets a reference to the value the stack points to. - pub fn peek(&self) -> &V { - unsafe { self.top.from_raw().into_kv().1 } - } - - /// Gets a mutable reference to the value the stack points to. - pub fn peek_mut(&mut self) -> &mut V { - unsafe { self.top.from_raw_mut().into_kv_mut().1 } - } +impl Iterator for IntoIter { + type Item = (K, V); - /// Converts the stack into a mutable reference to the value it points to, with a lifetime - /// tied to the original tree. - pub fn into_top(mut self) -> &'a mut V { - unsafe { &mut *(self.top.from_raw_mut().val_mut() as *mut V) } + fn next(&mut self) -> Option<(K, V)> { + if self.length == 0 { + return None; + } else { + self.length -= 1; } - } - impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::Leaf> { - /// Removes the key and value in the top element of the stack, then handles underflows as - /// described in BTree's pop function. - fn remove_leaf(mut self) -> (K, V) { - self.map.length -= 1; + let handle = unsafe { ptr::read(&self.front) }; - // Remove the key-value pair from the leaf that this search stack points to. - // Then, note if the leaf is underfull, and promptly forget the leaf and its ptr - // to avoid ownership issues. - let (key_val, mut underflow) = unsafe { - let key_val = self.top.from_raw_mut().remove_as_leaf(); - let underflow = self.top.from_raw().node().is_underfull(); - (key_val, underflow) - }; + let mut cur_handle = match handle.right_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.front = kv.right_edge(); + return Some((k, v)); + }, + Err(last_edge) => unsafe { + unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()) + } + }; - loop { - match self.stack.pop() { - None => { - // We've reached the root, so no matter what, we're done. We manually - // access the root via the tree itself to avoid creating any dangling - // pointers. - if self.map.root.is_empty() && !self.map.root.is_leaf() { - // We've emptied out the root, so make its only child the new root. - // If it's a leaf, we just let it become empty. - self.map.depth -= 1; - self.map.root.hoist_lone_child(); - } - return key_val; - } - Some(mut handle) => { - if underflow { - // Underflow! Handle it! - unsafe { - handle.from_raw_mut().handle_underflow(); - underflow = handle.from_raw().node().is_underfull(); - } - } else { - // All done! - return key_val; - } - } + loop { + match cur_handle.right_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.front = first_leaf_edge(kv.right_edge().descend()); + return Some((k, v)); + }, + Err(last_edge) => unsafe { + cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()); } } } } - impl<'a, K, V> SearchStack<'a, K, V, handle::KV, handle::LeafOrInternal> { - /// Removes the key and value in the top element of the stack, then handles underflows as - /// described in BTree's pop function. - pub fn remove(self) -> (K, V) { - // Ensure that the search stack goes to a leaf. This is necessary to perform deletion - // in a BTree. Note that this may put the tree in an inconsistent state (further - // described in into_leaf's comments), but this is immediately fixed by the - // removing the value we want to remove - self.into_leaf().remove_leaf() + fn size_hint(&self) -> (usize, Option) { + (self.length, Some(self.length)) + } +} + +impl DoubleEndedIterator for IntoIter { + fn next_back(&mut self) -> Option<(K, V)> { + if self.length == 0 { + return None; + } else { + self.length -= 1; } - /// Subroutine for removal. Takes a search stack for a key that might terminate at an - /// internal node, and mutates the tree and search stack to *make* it a search stack - /// for that same key that *does* terminates at a leaf. If the mutation occurs, then this - /// leaves the tree in an inconsistent state that must be repaired by the caller by - /// removing the entry in question. Specifically the key-value pair and its successor will - /// become swapped. - fn into_leaf(mut self) -> SearchStack<'a, K, V, handle::KV, handle::Leaf> { - unsafe { - let mut top_raw = self.top; - let mut top = top_raw.from_raw_mut(); - - let key_ptr = top.key_mut() as *mut _; - let val_ptr = top.val_mut() as *mut _; - - // Try to go into the right subtree of the found key to find its successor - match top.force() { - Leaf(mut leaf_handle) => { - // We're a proper leaf stack, nothing to do - return SearchStack { - map: self.map, - stack: self.stack, - top: leaf_handle.as_raw(), - }; - } - Internal(mut internal_handle) => { - let mut right_handle = internal_handle.right_edge(); - - // We're not a proper leaf stack, let's get to work. - self.stack.push(right_handle.as_raw()); - - let mut temp_node = right_handle.edge_mut(); - loop { - // Walk into the smallest subtree of this node - let node = temp_node; - - match node.kv_handle(0).force() { - Leaf(mut handle) => { - // This node is a leaf, do the swap and return - mem::swap(handle.key_mut(), &mut *key_ptr); - mem::swap(handle.val_mut(), &mut *val_ptr); - return SearchStack { - map: self.map, - stack: self.stack, - top: handle.as_raw(), - }; - } - Internal(kv_handle) => { - // This node is internal, go deeper - let mut handle = kv_handle.into_left_edge(); - self.stack.push(handle.as_raw()); - temp_node = handle.into_edge_mut(); - } - } - } - } + let handle = unsafe { ptr::read(&self.back) }; + + let mut cur_handle = match handle.left_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.back = kv.left_edge(); + return Some((k, v)); + }, + Err(last_edge) => unsafe { + unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()) + } + }; + + loop { + match cur_handle.left_kv() { + Ok(kv) => { + let k = unsafe { ptr::read(kv.reborrow().into_kv().0) }; + let v = unsafe { ptr::read(kv.reborrow().into_kv().1) }; + self.back = last_leaf_edge(kv.left_edge().descend()); + return Some((k, v)); + }, + Err(last_edge) => unsafe { + cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend()); } } } } +} - impl<'a, K, V> SearchStack<'a, K, V, handle::Edge, handle::Leaf> { - /// Inserts the key and value into the top element in the stack, and if that node has to - /// split recursively inserts the split contents into the next element stack until - /// splits stop. - /// - /// Assumes that the stack represents a search path from the root to a leaf. - /// - /// An &mut V is returned to the inserted value, for callers that want a reference to this. - pub fn insert(mut self, key: K, val: V) -> &'a mut V { - unsafe { - self.map.length += 1; - - // Insert the key and value into the leaf at the top of the stack - let (mut insertion, inserted_ptr) = self.top - .from_raw_mut() - .insert_as_leaf(key, val); - - loop { - match insertion { - Fit => { - // The last insertion went off without a hitch, no splits! We can stop - // inserting now. - return &mut *inserted_ptr; - } - Split(key, val, right) => { - match self.stack.pop() { - // The last insertion triggered a split, so get the next element on - // the stack to recursively insert the split node into. - None => { - // The stack was empty; we've split the root, and need to make a - // a new one. This is done in-place because we can't move the - // root out of a reference to the tree. - Node::make_internal_root(&mut self.map.root, - self.map.b, - key, - val, - right); - - self.map.depth += 1; - return &mut *inserted_ptr; - } - Some(mut handle) => { - // The stack wasn't empty, do the insertion and recurse - insertion = handle.from_raw_mut() - .insert_as_internal(key, val, right); - continue; - } - } - } - } - } - } - } - } +impl ExactSizeIterator for IntoIter { + fn len(&self) -> usize { self.length } } -#[stable(feature = "rust1", since = "1.0.0")] -impl FromIterator<(K, V)> for BTreeMap { - fn from_iter>(iter: T) -> BTreeMap { - let mut map = BTreeMap::new(); - map.extend(iter); - map - } -} +impl<'a, K, V> Iterator for Keys<'a, K, V> { + type Item = &'a K; -#[stable(feature = "rust1", since = "1.0.0")] -impl Extend<(K, V)> for BTreeMap { - #[inline] - fn extend>(&mut self, iter: T) { - for (k, v) in iter { - self.insert(k, v); - } + fn next(&mut self) -> Option<&'a K> { + self.inner.next().map(|(k, _)| k) } -} -#[stable(feature = "extend_ref", since = "1.2.0")] -impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap { - fn extend>(&mut self, iter: I) { - self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); + fn size_hint(&self) -> (usize, Option) { + self.inner.size_hint() } } -#[stable(feature = "rust1", since = "1.0.0")] -impl Hash for BTreeMap { - fn hash(&self, state: &mut H) { - for elt in self { - elt.hash(state); - } +impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { + fn next_back(&mut self) -> Option<&'a K> { + self.inner.next_back().map(|(k, _)| k) } } -#[stable(feature = "rust1", since = "1.0.0")] -impl Default for BTreeMap { - fn default() -> BTreeMap { - BTreeMap::new() +impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> { + fn len(&self) -> usize { + self.inner.len() } } -#[stable(feature = "rust1", since = "1.0.0")] -impl PartialEq for BTreeMap { - fn eq(&self, other: &BTreeMap) -> bool { - self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b) +impl<'a, K, V> Clone for Keys<'a, K, V> { + fn clone(&self) -> Keys<'a, K, V> { + Keys { + inner: self.inner.clone() + } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl Eq for BTreeMap {} +impl<'a, K, V> Iterator for Values<'a, K, V> { + type Item = &'a V; -#[stable(feature = "rust1", since = "1.0.0")] -impl PartialOrd for BTreeMap { - #[inline] - fn partial_cmp(&self, other: &BTreeMap) -> Option { - self.iter().partial_cmp(other.iter()) + fn next(&mut self) -> Option<&'a V> { + self.inner.next().map(|(_, v)| v) } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl Ord for BTreeMap { - #[inline] - fn cmp(&self, other: &BTreeMap) -> Ordering { - self.iter().cmp(other.iter()) + fn size_hint(&self) -> (usize, Option) { + self.inner.size_hint() } } -#[stable(feature = "rust1", since = "1.0.0")] -impl Debug for BTreeMap { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_map().entries(self.iter()).finish() +impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { + fn next_back(&mut self) -> Option<&'a V> { + self.inner.next_back().map(|(_, v)| v) } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap - where K: Borrow, - Q: Ord -{ - type Output = V; - - #[inline] - fn index(&self, key: &Q) -> &V { - self.get(key).expect("no entry found for key") +impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> { + fn len(&self) -> usize { + self.inner.len() } } -/// Genericizes over how to get the correct type of iterator from the correct type -/// of Node ownership. -trait Traverse { - fn traverse(node: N) -> Self; -} - -impl<'a, K, V> Traverse<&'a Node> for Traversal<'a, K, V> { - fn traverse(node: &'a Node) -> Traversal<'a, K, V> { - node.iter() +impl<'a, K, V> Clone for Values<'a, K, V> { + fn clone(&self) -> Values<'a, K, V> { + Values { + inner: self.inner.clone() + } } } -impl<'a, K, V> Traverse<&'a mut Node> for MutTraversal<'a, K, V> { - fn traverse(node: &'a mut Node) -> MutTraversal<'a, K, V> { - node.iter_mut() - } -} +impl<'a, K, V> Iterator for Range<'a, K, V> { + type Item = (&'a K, &'a V); -impl Traverse> for MoveTraversal { - fn traverse(node: Node) -> MoveTraversal { - node.into_iter() + fn next(&mut self) -> Option<(&'a K, &'a V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_unchecked()) } + } } } -/// Represents an operation to perform inside the following iterator methods. -/// This is necessary to use in `next` because we want to modify `self.traversals` inside -/// a match that borrows it. Similarly in `next_back`. Instead, we use this enum to note -/// what we want to do, and do it after the match. -enum StackOp { - Push(T), - Pop, -} -impl Iterator for AbsIter - where T: DoubleEndedIterator> + Traverse -{ - type Item = (K, V); +impl<'a, K, V> Range<'a, K, V> { + unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) { + let handle = self.front; - // Our iterator represents a queue of all ancestors of elements we have - // yet to yield, from smallest to largest. Note that the design of these - // iterators permits an *arbitrary* initial pair of min and max, making - // these arbitrary sub-range iterators. - fn next(&mut self) -> Option<(K, V)> { - loop { - // We want the smallest element, so try to get the back of the queue - let op = match self.traversals.back_mut() { - None => return None, - // The queue wasn't empty, so continue along the node in its head - Some(iter) => { - match iter.next() { - // The head is empty, so Pop it off and continue the process - None => Pop, - // The head yielded an edge, so make that the new head - Some(Edge(next)) => Push(Traverse::traverse(next)), - // The head yielded an entry, so yield that - Some(Elem(kv)) => { - self.size -= 1; - return Some(kv); - } - } - } - }; + let mut cur_handle = match handle.right_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.front = kv.right_edge(); + return ret; + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; - // Handle any operation as necessary, without a conflicting borrow of the queue - match op { - Push(item) => { - self.traversals.push_back(item); - } - Pop => { - self.traversals.pop_back(); + loop { + match cur_handle.right_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.front = first_leaf_edge(kv.right_edge().descend()); + return ret; + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); } } } } +} - fn size_hint(&self) -> (usize, Option) { - (self.size, Some(self.size)) +impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_back_unchecked()) } + } } } -impl DoubleEndedIterator for AbsIter - where T: DoubleEndedIterator> + Traverse -{ - // next_back is totally symmetric to next - #[inline] - fn next_back(&mut self) -> Option<(K, V)> { - loop { - let op = match self.traversals.front_mut() { - None => return None, - Some(iter) => { - match iter.next_back() { - None => Pop, - Some(Edge(next)) => Push(Traverse::traverse(next)), - Some(Elem(kv)) => { - self.size -= 1; - return Some(kv); - } - } - } - }; +impl<'a, K, V> Range<'a, K, V> { + unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) { + let handle = self.back; - match op { - Push(item) => { - self.traversals.push_front(item); - } - Pop => { - self.traversals.pop_front(); + let mut cur_handle = match handle.left_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.back = kv.left_edge(); + return ret; + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; + + loop { + match cur_handle.left_kv() { + Ok(kv) => { + let ret = kv.into_kv(); + self.back = last_leaf_edge(kv.left_edge().descend()); + return ret; + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); } } } } } -impl<'a, K, V> Clone for Iter<'a, K, V> { - fn clone(&self) -> Iter<'a, K, V> { - Iter { inner: self.inner.clone() } - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Iter<'a, K, V> { - type Item = (&'a K, &'a V); - - fn next(&mut self) -> Option<(&'a K, &'a V)> { - self.inner.next() - } - fn size_hint(&self) -> (usize, Option) { - self.inner.size_hint() - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> { - fn next_back(&mut self) -> Option<(&'a K, &'a V)> { - self.inner.next_back() +impl<'a, K, V> Clone for Range<'a, K, V> { + fn clone(&self) -> Range<'a, K, V> { + Range { + front: self.front, + back: self.back + } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for IterMut<'a, K, V> { +impl<'a, K, V> Iterator for RangeMut<'a, K, V> { type Item = (&'a K, &'a mut V); fn next(&mut self) -> Option<(&'a K, &'a mut V)> { - self.inner.next() - } - fn size_hint(&self) -> (usize, Option) { - self.inner.size_hint() - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> { - fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { - self.inner.next_back() + if self.front == self.back { + None + } else { + unsafe { Some (self.next_unchecked()) } + } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {} -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for IntoIter { - type Item = (K, V); +impl<'a, K, V> RangeMut<'a, K, V> { + unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) { + let handle = ptr::read(&self.front); - fn next(&mut self) -> Option<(K, V)> { - self.inner.next() - } - fn size_hint(&self) -> (usize, Option) { - self.inner.size_hint() - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for IntoIter { - fn next_back(&mut self) -> Option<(K, V)> { - self.inner.next_back() - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for IntoIter {} + let mut cur_handle = match handle.right_kv() { + Ok(kv) => { + let (k, v) = ptr::read(&kv).into_kv_mut(); + self.front = kv.right_edge(); + return (k, v); + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; -impl<'a, K, V> Clone for Keys<'a, K, V> { - fn clone(&self) -> Keys<'a, K, V> { - Keys { inner: self.inner.clone() } + loop { + match cur_handle.right_kv() { + Ok(kv) => { + let (k, v) = ptr::read(&kv).into_kv_mut(); + self.front = first_leaf_edge(kv.right_edge().descend()); + return (k, v); + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); + } + } + } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Keys<'a, K, V> { - type Item = &'a K; - fn next(&mut self) -> Option<(&'a K)> { - self.inner.next() - } - fn size_hint(&self) -> (usize, Option) { - self.inner.size_hint() - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> { - fn next_back(&mut self) -> Option<(&'a K)> { - self.inner.next_back() +impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { + if self.front == self.back { + None + } else { + unsafe { Some(self.next_back_unchecked()) } + } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {} +impl<'a, K, V> RangeMut<'a, K, V> { + unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) { + let handle = ptr::read(&self.back); -impl<'a, K, V> Clone for Values<'a, K, V> { - fn clone(&self) -> Values<'a, K, V> { - Values { inner: self.inner.clone() } - } -} -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> Iterator for Values<'a, K, V> { - type Item = &'a V; + let mut cur_handle = match handle.left_kv() { + Ok(kv) => { + let (k, v) = ptr::read(&kv).into_kv_mut(); + self.back = kv.left_edge(); + return (k, v); + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + unwrap_unchecked(next_level) + } + }; - fn next(&mut self) -> Option<(&'a V)> { - self.inner.next() - } - fn size_hint(&self) -> (usize, Option) { - self.inner.size_hint() + loop { + match cur_handle.left_kv() { + Ok(kv) => { + let (k, v) = ptr::read(&kv).into_kv_mut(); + self.back = last_leaf_edge(kv.left_edge().descend()); + return (k, v); + }, + Err(last_edge) => { + let next_level = last_edge.into_node().ascend().ok(); + cur_handle = unwrap_unchecked(next_level); + } + } + } } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> { - fn next_back(&mut self) -> Option<(&'a V)> { - self.inner.next_back() + +impl FromIterator<(K, V)> for BTreeMap { + fn from_iter>(iter: T) -> BTreeMap { + let mut map = BTreeMap::new(); + map.extend(iter); + map } } -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {} -impl<'a, K, V> Clone for Range<'a, K, V> { - fn clone(&self) -> Range<'a, K, V> { - Range { inner: self.inner.clone() } +impl Extend<(K, V)> for BTreeMap { + #[inline] + fn extend>(&mut self, iter: T) { + for (k, v) in iter { + self.insert(k, v); + } } } -impl<'a, K, V> Iterator for Range<'a, K, V> { - type Item = (&'a K, &'a V); - fn next(&mut self) -> Option<(&'a K, &'a V)> { - self.inner.next() +impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap { + fn extend>(&mut self, iter: I) { + self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); } } -impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { - fn next_back(&mut self) -> Option<(&'a K, &'a V)> { - self.inner.next_back() + +impl Hash for BTreeMap { + fn hash(&self, state: &mut H) { + for elt in self { + elt.hash(state); + } } } -impl<'a, K, V> Iterator for RangeMut<'a, K, V> { - type Item = (&'a K, &'a mut V); - - fn next(&mut self) -> Option<(&'a K, &'a mut V)> { - self.inner.next() +impl Default for BTreeMap { + fn default() -> BTreeMap { + BTreeMap::new() } } -impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> { - fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { - self.inner.next_back() + +impl PartialEq for BTreeMap { + fn eq(&self, other: &BTreeMap) -> bool { + self.len() == other.len() && + self.iter().zip(other).all(|(a, b)| a == b) } } -impl<'a, K: Ord, V> Entry<'a, K, V> { - #[stable(feature = "rust1", since = "1.0.0")] - /// Ensures a value is in the entry by inserting the default if empty, and returns - /// a mutable reference to the value in the entry. - pub fn or_insert(self, default: V) -> &'a mut V { - match self { - Occupied(entry) => entry.into_mut(), - Vacant(entry) => entry.insert(default), - } - } +impl Eq for BTreeMap {} - #[stable(feature = "rust1", since = "1.0.0")] - /// Ensures a value is in the entry by inserting the result of the default function if empty, - /// and returns a mutable reference to the value in the entry. - pub fn or_insert_with V>(self, default: F) -> &'a mut V { - match self { - Occupied(entry) => entry.into_mut(), - Vacant(entry) => entry.insert(default()), - } +impl PartialOrd for BTreeMap { + #[inline] + fn partial_cmp(&self, other: &BTreeMap) -> Option { + self.iter().partial_cmp(other.iter()) } } -impl<'a, K: Ord, V> VacantEntry<'a, K, V> { - /// Sets the value of the entry with the VacantEntry's key, - /// and returns a mutable reference to it. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(self, value: V) -> &'a mut V { - self.stack.insert(self.key, value) +impl Ord for BTreeMap { + #[inline] + fn cmp(&self, other: &BTreeMap) -> Ordering { + self.iter().cmp(other.iter()) } } -impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { - /// Gets a reference to the value in the entry. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn get(&self) -> &V { - self.stack.peek() +impl Debug for BTreeMap { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_map().entries(self.iter()).finish() } +} - /// Gets a mutable reference to the value in the entry. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn get_mut(&mut self) -> &mut V { - self.stack.peek_mut() - } +impl<'a, K: Ord, Q: ?Sized, V> Index<&'a Q> for BTreeMap + where K: Borrow, Q: Ord +{ + type Output = V; - /// Converts the entry into a mutable reference to its value. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn into_mut(self) -> &'a mut V { - self.stack.into_top() + #[inline] + fn index(&self, key: &Q) -> &V { + self.get(key).expect("no entry found for key") } +} - /// Sets the value of the entry with the OccupiedEntry's key, - /// and returns the entry's old value. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(&mut self, mut value: V) -> V { - mem::swap(self.stack.peek_mut(), &mut value); - value +fn first_leaf_edge( + mut node: NodeRef + ) -> Handle, marker::Edge> { + loop { + match node.force() { + Leaf(leaf) => return leaf.first_edge(), + Internal(internal) => { + node = internal.first_edge().descend(); + } + } } +} - /// Takes the value of the entry out of the map, and returns it. - #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove(self) -> V { - self.stack.remove().1 +fn last_leaf_edge( + mut node: NodeRef + ) -> Handle, marker::Edge> { + loop { + match node.force() { + Leaf(leaf) => return leaf.last_edge(), + Internal(internal) => { + node = internal.last_edge().descend(); + } + } } } +#[inline(always)] +unsafe fn unwrap_unchecked(val: Option) -> T { + val.unwrap_or_else(|| { + if cfg!(debug_assertions) { + panic!("'unchecked' unwrap on None in BTreeMap"); + } else { + intrinsics::unreachable(); + } + }) +} + impl BTreeMap { /// Gets an iterator over the entries of the map. /// @@ -1312,15 +1199,12 @@ impl BTreeMap { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn iter(&self) -> Iter { - let len = self.len(); - // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases. - let mut lca = VecDeque::new(); - lca.push_back(Traverse::traverse(&self.root)); Iter { - inner: AbsIter { - traversals: lca, - size: len, + range: Range { + front: first_leaf_edge(self.root.as_ref()), + back: last_leaf_edge(self.root.as_ref()) }, + length: self.length } } @@ -1345,14 +1229,14 @@ pub fn iter(&self) -> Iter { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut { - let len = self.len(); - let mut lca = VecDeque::new(); - lca.push_back(Traverse::traverse(&mut self.root)); + let root1 = self.root.as_mut(); + let root2 = unsafe { ptr::read(&root1) }; IterMut { - inner: AbsIter { - traversals: lca, - size: len, + range: RangeMut { + front: first_leaf_edge(root1), + back: last_leaf_edge(root2), }, + length: self.length } } @@ -1372,12 +1256,7 @@ pub fn iter_mut(&mut self) -> IterMut { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn keys<'a>(&'a self) -> Keys<'a, K, V> { - fn first((a, _): (A, B)) -> A { - a - } - let first: fn((&'a K, &'a V)) -> &'a K = first; // coerce to fn pointer - - Keys { inner: self.iter().map(first) } + Keys { inner: self.iter() } } /// Gets an iterator over the values of the map. @@ -1396,12 +1275,7 @@ fn first((a, _): (A, B)) -> A { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn values<'a>(&'a self) -> Values<'a, K, V> { - fn second((_, b): (A, B)) -> B { - b - } - let second: fn((&'a K, &'a V)) -> &'a V = second; // coerce to fn pointer - - Values { inner: self.iter().map(second) } + Values { inner: self.iter() } } /// Returns the number of elements in the map. @@ -1439,357 +1313,207 @@ pub fn is_empty(&self) -> bool { } } -macro_rules! range_impl { - ($root:expr, $min:expr, $max:expr, $as_slices_internal:ident, $iter:ident, $Range:ident, - $edges:ident, [$($mutability:ident)*]) => ( - { - // A deque that encodes two search paths containing (left-to-right): - // a series of truncated-from-the-left iterators, the LCA's doubly-truncated iterator, - // and a series of truncated-from-the-right iterators. - let mut traversals = VecDeque::new(); - let (root, min, max) = ($root, $min, $max); - - let mut leftmost = None; - let mut rightmost = None; +impl<'a, K: Ord, V> Entry<'a, K, V> { + /// Ensures a value is in the entry by inserting the default if empty, and returns + /// a mutable reference to the value in the entry. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn or_insert(self, default: V) -> &'a mut V { + match self { + Occupied(entry) => entry.into_mut(), + Vacant(entry) => entry.insert(default), + } + } - match (&min, &max) { - (&Unbounded, &Unbounded) => { - traversals.push_back(Traverse::traverse(root)) - } - (&Unbounded, &Included(_)) | (&Unbounded, &Excluded(_)) => { - rightmost = Some(root); - } - (&Included(_), &Unbounded) | (&Excluded(_), &Unbounded) => { - leftmost = Some(root); - } - (&Included(min_key), &Included(max_key)) - | (&Included(min_key), &Excluded(max_key)) - | (&Excluded(min_key), &Included(max_key)) - | (&Excluded(min_key), &Excluded(max_key)) => { - // lca represents the Lowest Common Ancestor, above which we never - // walk, since everything else is outside the range to iterate. - // ___________________ - // |__0_|_80_|_85_|_90_| (root) - // | | | | | - // | - // v - // ___________________ - // |__5_|_15_|_30_|_73_| - // | | | | | - // | - // v - // ___________________ - // |_33_|_58_|_63_|_68_| lca for the range [41, 65] - // | |\___|___/| | iterator at traversals[2] - // | | - // | v - // v rightmost - // leftmost - let mut is_leaf = root.is_leaf(); - let mut lca = root.$as_slices_internal(); - loop { - let slice = lca.slice_from(min_key).slice_to(max_key); - if let [ref $($mutability)* edge] = slice.edges { - // Follow the only edge that leads the node that covers the range. - is_leaf = edge.is_leaf(); - lca = edge.$as_slices_internal(); - } else { - let mut iter = slice.$iter(); - if is_leaf { - leftmost = None; - rightmost = None; - } else { - // Only change the state of nodes with edges. - leftmost = iter.next_edge_item(); - rightmost = iter.next_edge_item_back(); - } - traversals.push_back(iter); - break; - } - } - } - } - // Keep narrowing the range by going down. - // ___________________ - // |_38_|_43_|_48_|_53_| - // | |____|____|____/ iterator at traversals[1] - // | - // v - // ___________________ - // |_39_|_40_|_41_|_42_| (leaf, the last leftmost) - // \_________| iterator at traversals[0] - match min { - Included(key) | Excluded(key) => - while let Some(left) = leftmost { - let is_leaf = left.is_leaf(); - let mut iter = left.$as_slices_internal().slice_from(key).$iter(); - leftmost = if is_leaf { - None - } else { - // Only change the state of nodes with edges. - iter.next_edge_item() - }; - traversals.push_back(iter); - }, - _ => {} - } - // If the leftmost iterator starts with an element, then it was an exact match. - if let (Excluded(_), Some(leftmost_iter)) = (min, traversals.back_mut()) { - // Drop this excluded element. `next_kv_item` has no effect when - // the next item is an edge. - leftmost_iter.next_kv_item(); - } + /// Ensures a value is in the entry by inserting the result of the default function if empty, + /// and returns a mutable reference to the value in the entry. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn or_insert_with V>(self, default: F) -> &'a mut V { + match self { + Occupied(entry) => entry.into_mut(), + Vacant(entry) => entry.insert(default()), + } + } +} - // The code for the right side is similar. - match max { - Included(key) | Excluded(key) => - while let Some(right) = rightmost { - let is_leaf = right.is_leaf(); - let mut iter = right.$as_slices_internal().slice_to(key).$iter(); - rightmost = if is_leaf { - None - } else { - iter.next_edge_item_back() - }; - traversals.push_front(iter); - }, - _ => {} - } - if let (Excluded(_), Some(rightmost_iter)) = (max, traversals.front_mut()) { - rightmost_iter.next_kv_item_back(); +impl<'a, K: Ord, V> VacantEntry<'a, K, V> { + /// Sets the value of the entry with the VacantEntry's key, + /// and returns a mutable reference to it. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn insert(self, value: V) -> &'a mut V { + *self.length += 1; + + let out_ptr; + + let mut ins_k; + let mut ins_v; + let mut ins_edge; + + let mut cur_parent = match self.handle.insert(self.key, value) { + (Fit(handle), _) => return handle.into_kv_mut().1, + (Split(left, k, v, right), ptr) => { + ins_k = k; + ins_v = v; + ins_edge = right; + out_ptr = ptr; + left.ascend().map_err(|n| n.into_root_mut()) } + }; - $Range { - inner: AbsIter { - traversals: traversals, - size: usize::MAX, // unused + loop { + match cur_parent { + Ok(parent) => match parent.insert(ins_k, ins_v, ins_edge) { + Fit(_) => return unsafe { &mut *out_ptr }, + Split(left, k, v, right) => { + ins_k = k; + ins_v = v; + ins_edge = right; + cur_parent = left.ascend().map_err(|n| n.into_root_mut()); + } + }, + Err(root) => { + root.push_level().push(ins_k, ins_v, ins_edge); + return unsafe { &mut *out_ptr }; } } } - ) + } } -impl BTreeMap { - /// Constructs a double-ended iterator over a sub-range of elements in the map, starting - /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative - /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity". - /// Thus range(Unbounded, Unbounded) will yield the whole collection. - /// - /// # Examples - /// - /// ``` - /// #![feature(btree_range, collections_bound)] - /// - /// use std::collections::BTreeMap; - /// use std::collections::Bound::{Included, Unbounded}; - /// - /// let mut map = BTreeMap::new(); - /// map.insert(3, "a"); - /// map.insert(5, "b"); - /// map.insert(8, "c"); - /// for (&key, &value) in map.range(Included(&4), Included(&8)) { - /// println!("{}: {}", key, value); - /// } - /// assert_eq!(Some((&5, &"b")), map.range(Included(&4), Unbounded).next()); - /// ``` - #[unstable(feature = "btree_range", - reason = "matches collection reform specification, waiting for dust to settle", - issue = "27787")] - pub fn range(&self, - min: Bound<&Min>, - max: Bound<&Max>) - -> Range - where K: Borrow + Borrow - { - range_impl!(&self.root, - min, - max, - as_slices_internal, - iter, - Range, - edges, - []) +impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> { + /// Gets a reference to the value in the entry. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn get(&self) -> &V { + self.handle.reborrow().into_kv().1 } - /// Constructs a mutable double-ended iterator over a sub-range of elements in the map, starting - /// at min, and ending at max. If min is `Unbounded`, then it will be treated as "negative - /// infinity", and if max is `Unbounded`, then it will be treated as "positive infinity". - /// Thus range(Unbounded, Unbounded) will yield the whole collection. - /// - /// # Examples - /// - /// ``` - /// #![feature(btree_range, collections_bound)] - /// - /// use std::collections::BTreeMap; - /// use std::collections::Bound::{Included, Excluded}; - /// - /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"].iter() - /// .map(|&s| (s, 0)) - /// .collect(); - /// for (_, balance) in map.range_mut(Included("B"), Excluded("Cheryl")) { - /// *balance += 100; - /// } - /// for (name, balance) in &map { - /// println!("{} => {}", name, balance); - /// } - /// ``` - #[unstable(feature = "btree_range", - reason = "matches collection reform specification, waiting for dust to settle", - issue = "27787")] - pub fn range_mut(&mut self, - min: Bound<&Min>, - max: Bound<&Max>) - -> RangeMut - where K: Borrow + Borrow - { - range_impl!(&mut self.root, - min, - max, - as_slices_internal_mut, - iter_mut, - RangeMut, - edges_mut, - [mut]) + /// Gets a mutable reference to the value in the entry. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn get_mut(&mut self) -> &mut V { + self.handle.kv_mut().1 } - /// Gets the given key's corresponding entry in the map for in-place manipulation. - /// - /// # Examples - /// - /// ``` - /// use std::collections::BTreeMap; - /// - /// let mut count: BTreeMap<&str, usize> = BTreeMap::new(); - /// - /// // count the number of occurrences of letters in the vec - /// for x in vec!["a","b","a","c","a","b"] { - /// *count.entry(x).or_insert(0) += 1; - /// } - /// - /// assert_eq!(count["a"], 3); - /// ``` + /// Converts the entry into a mutable reference to its value. #[stable(feature = "rust1", since = "1.0.0")] - pub fn entry(&mut self, mut key: K) -> Entry { - // same basic logic of `swap` and `pop`, blended together - let mut stack = stack::PartialSearchStack::new(self); - loop { - let result = stack.with(move |pusher, node| { - match Node::search(node, &key) { - Found(handle) => { - // Perfect match - Finished(Occupied(OccupiedEntry { stack: pusher.seal(handle) })) - } - GoDown(handle) => { - match handle.force() { - Leaf(leaf_handle) => { - Finished(Vacant(VacantEntry { - stack: pusher.seal(leaf_handle), - key: key, - })) - } - Internal(internal_handle) => { - Continue((pusher.push(internal_handle), key)) - } - } - } - } - }); - match result { - Finished(finished) => return finished, - Continue((new_stack, renewed_key)) => { - stack = new_stack; - key = renewed_key; - } - } - } + pub fn into_mut(self) -> &'a mut V { + self.handle.into_kv_mut().1 } -} -impl super::Recover for BTreeMap - where K: Borrow + Ord, - Q: Ord -{ - type Key = K; + /// Sets the value of the entry with the OccupiedEntry's key, + /// and returns the entry's old value. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn insert(&mut self, value: V) -> V { + mem::replace(self.get_mut(), value) + } - fn get(&self, key: &Q) -> Option<&K> { - let mut cur_node = &self.root; - loop { - match Node::search(cur_node, key) { - Found(handle) => return Some(handle.into_kv().0), - GoDown(handle) => { - match handle.force() { - Leaf(_) => return None, - Internal(internal_handle) => { - cur_node = internal_handle.into_edge(); - continue; - } - } - } - } - } + /// Takes the value of the entry out of the map, and returns it. + #[stable(feature = "rust1", since = "1.0.0")] + pub fn remove(self) -> V { + self.remove_kv().1 } - fn take(&mut self, key: &Q) -> Option { - // See `remove` for an explanation of this. + fn remove_kv(self) -> (K, V) { + *self.length -= 1; - let mut stack = stack::PartialSearchStack::new(self); - loop { - let result = stack.with(move |pusher, node| { - match Node::search(node, key) { - Found(handle) => { - // Perfect match. Terminate the stack here, and remove the entry - Finished(Some(pusher.seal(handle).remove())) - } - GoDown(handle) => { - // We need to keep searching, try to go down the next edge - match handle.force() { - // We're at a leaf; the key isn't in here - Leaf(_) => Finished(None), - Internal(internal_handle) => Continue(pusher.push(internal_handle)), - } - } - } - }); - match result { - Finished(ret) => return ret.map(|(k, _)| k), - Continue(new_stack) => stack = new_stack, + let (small_leaf, old_key, old_val) = match self.handle.force() { + Leaf(leaf) => { + let (hole, old_key, old_val) = leaf.remove(); + (hole.into_node(), old_key, old_val) + }, + Internal(mut internal) => { + let key_loc = internal.kv_mut().0 as *mut K; + let val_loc = internal.kv_mut().1 as *mut V; + + let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok(); + let to_remove = unsafe { unwrap_unchecked(to_remove) }; + + let (hole, key, val) = to_remove.remove(); + + let old_key = unsafe { + mem::replace(&mut *key_loc, key) + }; + let old_val = unsafe { + mem::replace(&mut *val_loc, val) + }; + + (hole.into_node(), old_key, old_val) + } + }; + + // Handle underflow + let mut cur_node = small_leaf.forget_type(); + while cur_node.len() < node::CAPACITY / 2 { + match handle_underfull_node(cur_node) { + AtRoot => break, + EmptyParent(_) => unreachable!(), + Merged(parent) => if parent.len() == 0 { + // We must be at the root + parent.into_root_mut().pop_level(); + break; + } else { + cur_node = parent.forget_type(); + }, + Stole(_) => break } } + + (old_key, old_val) } +} - fn replace(&mut self, mut key: K) -> Option { - // See `insert` for an explanation of this. +enum UnderflowResult<'a, K, V> { + AtRoot, + EmptyParent(NodeRef, K, V, marker::Internal>), + Merged(NodeRef, K, V, marker::Internal>), + Stole(NodeRef, K, V, marker::Internal>) +} - let mut stack = stack::PartialSearchStack::new(self); +fn handle_underfull_node<'a, K, V>(node: NodeRef, + K, V, + marker::LeafOrInternal>) + -> UnderflowResult<'a, K, V> { + let parent = if let Ok(parent) = node.ascend() { + parent + } else { + return AtRoot; + }; + + let (is_left, mut handle) = match parent.left_kv() { + Ok(left) => (true, left), + Err(parent) => match parent.right_kv() { + Ok(right) => (false, right), + Err(parent) => { + return EmptyParent(parent.into_node()); + } + } + }; + + if handle.can_merge() { + return Merged(handle.merge().into_node()); + } else { + unsafe { + let (k, v, edge) = if is_left { + handle.reborrow_mut().left_edge().descend().pop() + } else { + handle.reborrow_mut().right_edge().descend().pop_front() + }; - loop { - let result = stack.with(move |pusher, node| { - match Node::search::(node, &key) { - Found(mut handle) => { - mem::swap(handle.key_mut(), &mut key); - Finished(Some(key)) - } - GoDown(handle) => { - match handle.force() { - Leaf(leaf_handle) => { - pusher.seal(leaf_handle).insert(key, ()); - Finished(None) - } - Internal(internal_handle) => { - Continue((pusher.push(internal_handle), key, ())) - } - } - } + let k = mem::replace(handle.reborrow_mut().into_kv_mut().0, k); + let v = mem::replace(handle.reborrow_mut().into_kv_mut().1, v); + + // FIXME: reuse cur_node? + if is_left { + match handle.reborrow_mut().right_edge().descend().force() { + Leaf(mut leaf) => leaf.push_front(k, v), + Internal(mut internal) => internal.push_front(k, v, edge.unwrap()) } - }); - match result { - Finished(ret) => return ret, - Continue((new_stack, renewed_key, _)) => { - stack = new_stack; - key = renewed_key; + } else { + match handle.reborrow_mut().left_edge().descend().force() { + Leaf(mut leaf) => leaf.push(k, v), + Internal(mut internal) => internal.push(k, v, edge.unwrap()) } } } + + return Stole(handle.into_node()); } } diff --git a/src/libcollections/btree/mod.rs b/src/libcollections/btree/mod.rs index d424cb7e29d..087c9f228d4 100644 --- a/src/libcollections/btree/mod.rs +++ b/src/libcollections/btree/mod.rs @@ -9,6 +9,7 @@ // except according to those terms. mod node; +mod search; pub mod map; pub mod set; diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs index e55b1597a21..2e2a39df347 100644 --- a/src/libcollections/btree/node.rs +++ b/src/libcollections/btree/node.rs @@ -8,1632 +8,1120 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -// This module represents all the internal representation and logic for a B-Tree's node -// with a safe interface, so that BTreeMap itself does not depend on any of these details. - -pub use self::InsertionResult::*; -pub use self::SearchResult::*; -pub use self::ForceResult::*; -pub use self::TraversalItem::*; +// This is an attempt at an implementation following the ideal +// +// ``` +// struct BTreeMap { +// height: usize, +// root: Option>> +// } +// +// struct Node { +// keys: [K; 2 * B - 1], +// vals: [V; 2 * B - 1], +// edges: if height > 0 { +// [Box>; 2 * B] +// } else { () }, +// parent: *const Node, +// parent_idx: u16, +// len: u16, +// } +// ``` +// +// Since Rust doesn't acutally have dependent types and polymorphic recursion, +// we make do with lots of unsafety. -use core::cmp::Ordering::{Greater, Less, Equal}; -use core::intrinsics::arith_offset; -use core::iter::Zip; -use core::marker::PhantomData; -use core::ops::{Deref, DerefMut, Index, IndexMut}; -use core::ptr::Unique; -use core::{slice, mem, ptr, cmp}; use alloc::heap; - -use borrow::Borrow; - -/// Represents the result of an Insertion: either the item fit, or the node had to split -pub enum InsertionResult { - /// The inserted element fit - Fit, - /// The inserted element did not fit, so the node was split - Split(K, V, Node), -} - -/// Represents the result of a search for a key in a single node -pub enum SearchResult { - /// The element was found at the given index - Found(Handle), - /// The element wasn't found, but if it's anywhere, it must be beyond this edge - GoDown(Handle), -} - -/// A B-Tree Node. We keep keys/edges/values separate to optimize searching for keys. -#[unsafe_no_drop_flag] -pub struct Node { - // To avoid the need for multiple allocations, we allocate a single buffer with enough space - // for `capacity` keys, `capacity` values, and (in internal nodes) `capacity + 1` edges. - // Despite this, we store three separate pointers to the three "chunks" of the buffer because - // the performance drops significantly if the locations of the vals and edges need to be - // recalculated upon access. - // - // These will never be null during normal usage of a `Node`. However, to avoid the need for a - // drop flag, `Node::drop` zeroes `keys`, signaling that the `Node` has already been cleaned - // up. - keys: Unique, - vals: Unique, - - // In leaf nodes, this will be None, and no space will be allocated for edges. - edges: Option>>, - - // At any given time, there will be `_len` keys, `_len` values, and (in an internal node) - // `_len + 1` edges. In a leaf node, there will never be any edges. - // - // Note: instead of accessing this field directly, please call the `len()` method, which should - // be more stable in the face of representation changes. - _len: usize, - - // FIXME(gereeter) It shouldn't be necessary to store the capacity in every node, as it should - // be constant throughout the tree. Once a solution to this is found, it might be possible to - // also pass down the offsets into the buffer that vals and edges are stored at, removing the - // need for those two pointers. - // - // Note: instead of accessing this field directly, please call the `capacity()` method, which - // should be more stable in the face of representation changes. - _capacity: usize, -} - -pub struct NodeSlice<'a, K: 'a, V: 'a> { - keys: &'a [K], - vals: &'a [V], - pub edges: &'a [Node], - head_is_edge: bool, - tail_is_edge: bool, - has_edges: bool, -} - -pub struct MutNodeSlice<'a, K: 'a, V: 'a> { - keys: &'a [K], - vals: &'a mut [V], - pub edges: &'a mut [Node], - head_is_edge: bool, - tail_is_edge: bool, - has_edges: bool, -} - -/// Rounds up to a multiple of a power of two. Returns the closest multiple -/// of `target_alignment` that is higher or equal to `unrounded`. -/// -/// # Panics -/// -/// Fails if `target_alignment` is not a power of two. -#[inline] -fn round_up_to_next(unrounded: usize, target_alignment: usize) -> usize { - assert!(target_alignment.is_power_of_two()); - (unrounded + target_alignment - 1) & !(target_alignment - 1) -} - -#[test] -fn test_rounding() { - assert_eq!(round_up_to_next(0, 4), 0); - assert_eq!(round_up_to_next(1, 4), 4); - assert_eq!(round_up_to_next(2, 4), 4); - assert_eq!(round_up_to_next(3, 4), 4); - assert_eq!(round_up_to_next(4, 4), 4); - assert_eq!(round_up_to_next(5, 4), 8); -} - -// Returns a tuple of (val_offset, edge_offset), -// from the start of a mallocated array. -#[inline] -fn calculate_offsets(keys_size: usize, - vals_size: usize, - vals_align: usize, - edges_align: usize) - -> (usize, usize) { - let vals_offset = round_up_to_next(keys_size, vals_align); - let end_of_vals = vals_offset + vals_size; - - let edges_offset = round_up_to_next(end_of_vals, edges_align); - - (vals_offset, edges_offset) -} - -// Returns a tuple of (minimum required alignment, array_size), -// from the start of a mallocated array. -#[inline] -fn calculate_allocation(keys_size: usize, - keys_align: usize, - vals_size: usize, - vals_align: usize, - edges_size: usize, - edges_align: usize) - -> (usize, usize) { - let (_, edges_offset) = calculate_offsets(keys_size, vals_size, vals_align, edges_align); - let end_of_edges = edges_offset + edges_size; - - let min_align = cmp::max(keys_align, cmp::max(vals_align, edges_align)); - - (min_align, end_of_edges) -} - -#[test] -fn test_offset_calculation() { - assert_eq!(calculate_allocation(128, 8, 15, 1, 4, 4), (8, 148)); - assert_eq!(calculate_allocation(3, 1, 2, 1, 1, 1), (1, 6)); - assert_eq!(calculate_allocation(6, 2, 12, 4, 24, 8), (8, 48)); - assert_eq!(calculate_offsets(128, 15, 1, 4), (128, 144)); - assert_eq!(calculate_offsets(3, 2, 1, 1), (3, 5)); - assert_eq!(calculate_offsets(6, 12, 4, 8), (8, 24)); +use core::marker::PhantomData; +use core::mem; +use core::nonzero::NonZero; +use core::ptr::{self, Unique}; +use core::slice; + +use boxed::Box; + +const B: usize = 6; +pub const CAPACITY: usize = 2 * B - 1; + +struct LeafNode { + keys: [K; CAPACITY], + vals: [V; CAPACITY], + parent: *const InternalNode, + parent_idx: u16, + len: u16, } -fn calculate_allocation_generic(capacity: usize, is_leaf: bool) -> (usize, usize) { - let (keys_size, keys_align) = (capacity * mem::size_of::(), mem::align_of::()); - let (vals_size, vals_align) = (capacity * mem::size_of::(), mem::align_of::()); - let (edges_size, edges_align) = if is_leaf { - // allocate one edge to ensure that we don't pass size 0 to `heap::allocate` - if mem::size_of::() == 0 && mem::size_of::() == 0 { - (1, mem::align_of::>()) - } else { - (0, 1) +impl LeafNode { + unsafe fn new() -> Self { + LeafNode { + keys: mem::uninitialized(), + vals: mem::uninitialized(), + parent: ptr::null(), + parent_idx: mem::uninitialized(), + len: 0 } - } else { - ((capacity + 1) * mem::size_of::>(), - mem::align_of::>()) - }; - - calculate_allocation(keys_size, - keys_align, - vals_size, - vals_align, - edges_size, - edges_align) -} - -fn calculate_offsets_generic(capacity: usize, is_leaf: bool) -> (usize, usize) { - let keys_size = capacity * mem::size_of::(); - let vals_size = capacity * mem::size_of::(); - let vals_align = mem::align_of::(); - let edges_align = if is_leaf { - 1 - } else { - mem::align_of::>() - }; - - calculate_offsets(keys_size, vals_size, vals_align, edges_align) + } } -/// An iterator over a slice that owns the elements of the slice but not the allocation. -struct RawItems { - head: *const T, - tail: *const T, +// We use repr(C) so that a pointer to an internal node can be +// directly used as a pointer to a leaf node +#[repr(C)] +struct InternalNode { + data: LeafNode, + edges: [BoxedNode; 2 * B], } -impl RawItems { - unsafe fn from_slice(slice: &[T]) -> RawItems { - RawItems::from_parts(slice.as_ptr(), slice.len()) - } - - unsafe fn from_parts(ptr: *const T, len: usize) -> RawItems { - if mem::size_of::() == 0 { - RawItems { - head: ptr, - tail: arith_offset(ptr as *const i8, len as isize) as *const T, - } - } else { - RawItems { - head: ptr, - tail: ptr.offset(len as isize), - } - } - } - - unsafe fn push(&mut self, val: T) { - ptr::write(self.tail as *mut T, val); - - if mem::size_of::() == 0 { - self.tail = arith_offset(self.tail as *const i8, 1) as *const T; - } else { - self.tail = self.tail.offset(1); +impl InternalNode { + unsafe fn new() -> Self { + InternalNode { + data: LeafNode::new(), + edges: mem::uninitialized() } } } -impl Iterator for RawItems { - type Item = T; - - fn next(&mut self) -> Option { - if self.head == self.tail { - None - } else { - unsafe { - let ret = Some(ptr::read(self.head)); - - if mem::size_of::() == 0 { - self.head = arith_offset(self.head as *const i8, 1) as *const T; - } else { - self.head = self.head.offset(1); - } +struct BoxedNode { + ptr: Unique> // we don't know if this points to a leaf node or an internal node +} - ret - } +impl BoxedNode { + fn from_leaf(node: Box>) -> Self { + unsafe { + BoxedNode { ptr: Unique::new(Box::into_raw(node)) } } } -} - -impl DoubleEndedIterator for RawItems { - fn next_back(&mut self) -> Option { - if self.head == self.tail { - None - } else { - unsafe { - if mem::size_of::() == 0 { - self.tail = arith_offset(self.tail as *const i8, -1) as *const T; - } else { - self.tail = self.tail.offset(-1); - } - Some(ptr::read(self.tail)) - } + fn from_internal(node: Box>) -> Self { + unsafe { + BoxedNode { ptr: Unique::new(Box::into_raw(node) as *mut LeafNode) } } } -} -impl Drop for RawItems { - #[unsafe_destructor_blind_to_params] - fn drop(&mut self) { - for _ in self {} + unsafe fn from_ptr(ptr: NonZero<*mut LeafNode>) -> Self { + BoxedNode { ptr: Unique::new(*ptr) } } -} -impl Drop for Node { - #[unsafe_destructor_blind_to_params] - fn drop(&mut self) { - if self.keys.is_null() || - (unsafe { self.keys.get() as *const K as usize == mem::POST_DROP_USIZE }) { - // Since we have #[unsafe_no_drop_flag], we have to watch - // out for the sentinel value being stored in self.keys. (Using - // null is technically a violation of the `Unique` - // requirements, though.) - return; - } - - // Do the actual cleanup. + fn as_ptr(&self) -> NonZero<*mut LeafNode> { unsafe { - drop(RawItems::from_slice(self.keys())); - drop(RawItems::from_slice(self.vals())); - drop(RawItems::from_slice(self.edges())); - - self.destroy(); + NonZero::new(*self.ptr) } - - self.keys = unsafe { Unique::new(ptr::null_mut()) }; } } -impl Node { - /// Make a new internal node. The caller must initialize the result to fix the invariant that - /// there are `len() + 1` edges. - unsafe fn new_internal(capacity: usize) -> Node { - let (alignment, size) = calculate_allocation_generic::(capacity, false); - - let buffer = heap::allocate(size, alignment); - if buffer.is_null() { - ::alloc::oom(); - } +/// An owned tree. Note that despite being owned, this does not have a destructor, +/// and must be cleaned up manually. +pub struct Root { + node: BoxedNode, + height: usize +} - let (vals_offset, edges_offset) = calculate_offsets_generic::(capacity, false); +unsafe impl Sync for Root { } +unsafe impl Send for Root { } - Node { - keys: Unique::new(buffer as *mut K), - vals: Unique::new(buffer.offset(vals_offset as isize) as *mut V), - edges: Some(Unique::new(buffer.offset(edges_offset as isize) as *mut Node)), - _len: 0, - _capacity: capacity, +impl Root { + pub fn new_leaf() -> Self { + Root { + node: BoxedNode::from_leaf(Box::new(unsafe { LeafNode::new() })), + height: 0 } } - /// Make a new leaf node - fn new_leaf(capacity: usize) -> Node { - let (alignment, size) = calculate_allocation_generic::(capacity, true); - - let buffer = unsafe { heap::allocate(size, alignment) }; - if buffer.is_null() { - ::alloc::oom(); - } - - let (vals_offset, _) = calculate_offsets_generic::(capacity, true); - - Node { - keys: unsafe { Unique::new(buffer as *mut K) }, - vals: unsafe { Unique::new(buffer.offset(vals_offset as isize) as *mut V) }, - edges: None, - _len: 0, - _capacity: capacity, + pub fn as_ref(&self) + -> NodeRef { + NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: self as *const _ as *mut _, + _marker: PhantomData, } } - unsafe fn destroy(&mut self) { - let (alignment, size) = calculate_allocation_generic::(self.capacity(), - self.is_leaf()); - heap::deallocate(*self.keys as *mut u8, size, alignment); - } - - #[inline] - pub fn as_slices<'a>(&'a self) -> (&'a [K], &'a [V]) { - unsafe { - (slice::from_raw_parts(*self.keys, self.len()), - slice::from_raw_parts(*self.vals, self.len())) + pub fn as_mut(&mut self) + -> NodeRef { + NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: self as *mut _, + _marker: PhantomData, } } - #[inline] - pub fn as_slices_mut<'a>(&'a mut self) -> (&'a mut [K], &'a mut [V]) { - unsafe { - (slice::from_raw_parts_mut(*self.keys, self.len()), - slice::from_raw_parts_mut(*self.vals, self.len())) + pub fn into_ref(self) + -> NodeRef { + NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: ptr::null_mut(), // FIXME: Is there anything better to do here? + _marker: PhantomData, } } - #[inline] - pub fn as_slices_internal<'b>(&'b self) -> NodeSlice<'b, K, V> { - let is_leaf = self.is_leaf(); - let (keys, vals) = self.as_slices(); - let edges: &[_] = if self.is_leaf() { - &[] - } else { - unsafe { - let data = match self.edges { - None => heap::EMPTY as *const Node, - Some(ref p) => **p as *const Node, - }; - slice::from_raw_parts(data, self.len() + 1) - } - }; - NodeSlice { - keys: keys, - vals: vals, - edges: edges, - head_is_edge: true, - tail_is_edge: true, - has_edges: !is_leaf, - } - } + /// Add a new internal node with a single edge, pointing to the previous root, and make that + /// new node the root. This increases the height by 1 and is the opposite of `pop_level`. + pub fn push_level(&mut self) + -> NodeRef { + let mut new_node = Box::new(unsafe { InternalNode::new() }); + new_node.edges[0] = unsafe { BoxedNode::from_ptr(self.node.as_ptr()) }; - #[inline] - pub fn as_slices_internal_mut<'b>(&'b mut self) -> MutNodeSlice<'b, K, V> { - let len = self.len(); - let is_leaf = self.is_leaf(); - let keys = unsafe { slice::from_raw_parts_mut(*self.keys, len) }; - let vals = unsafe { slice::from_raw_parts_mut(*self.vals, len) }; - let edges: &mut [_] = if is_leaf { - &mut [] - } else { - unsafe { - let data = match self.edges { - None => heap::EMPTY as *mut Node, - Some(ref mut p) => **p as *mut Node, - }; - slice::from_raw_parts_mut(data, len + 1) - } - }; - MutNodeSlice { - keys: keys, - vals: vals, - edges: edges, - head_is_edge: true, - tail_is_edge: true, - has_edges: !is_leaf, - } - } + self.node = BoxedNode::from_internal(new_node); + self.height += 1; - #[inline] - pub fn keys<'a>(&'a self) -> &'a [K] { - self.as_slices().0 - } + let mut ret = NodeRef { + height: self.height, + node: self.node.as_ptr(), + root: self as *mut _, + _marker: PhantomData + }; - #[inline] - pub fn keys_mut<'a>(&'a mut self) -> &'a mut [K] { - self.as_slices_mut().0 - } + unsafe { + ret.reborrow_mut().first_edge().correct_parent_link(); + } - #[inline] - pub fn vals<'a>(&'a self) -> &'a [V] { - self.as_slices().1 + ret } - #[inline] - pub fn vals_mut<'a>(&'a mut self) -> &'a mut [V] { - self.as_slices_mut().1 - } + /// Remove the root node, using its first child as the new root. This cannot be called when + /// the tree consists only of a leaf node. As it is intended only to be called when the root + /// has only one edge, no cleanup is done on any of the other children are elements of the root. + /// This decreases the height by 1 and is the opposite of `push_level`. + pub fn pop_level(&mut self) { + debug_assert!(self.height > 0); - #[inline] - pub fn edges<'a>(&'a self) -> &'a [Node] { - self.as_slices_internal().edges - } + let top = *self.node.ptr as *mut u8; - #[inline] - pub fn edges_mut<'a>(&'a mut self) -> &'a mut [Node] { - self.as_slices_internal_mut().edges - } -} - -// FIXME(gereeter) Write an efficient clone_from -impl Clone for Node { - fn clone(&self) -> Node { - let mut ret = if self.is_leaf() { - Node::new_leaf(self.capacity()) - } else { - unsafe { Node::new_internal(self.capacity()) } + self.node = unsafe { + BoxedNode::from_ptr(self.as_mut() + .cast_unchecked::() + .first_edge() + .descend() + .node) }; + self.height -= 1; + self.as_mut().as_leaf_mut().parent = ptr::null(); unsafe { - // For failure safety - let mut keys = RawItems::from_parts(ret.keys().as_ptr(), 0); - let mut vals = RawItems::from_parts(ret.vals().as_ptr(), 0); - let mut edges = RawItems::from_parts(ret.edges().as_ptr(), 0); - - for key in self.keys() { - keys.push(key.clone()) - } - for val in self.vals() { - vals.push(val.clone()) - } - for edge in self.edges() { - edges.push(edge.clone()) - } - - mem::forget(keys); - mem::forget(vals); - mem::forget(edges); - - ret._len = self.len(); + heap::deallocate( + top, + mem::size_of::>(), + mem::align_of::>() + ); } - - ret } } -/// A reference to something in the middle of a `Node`. There are two `Type`s of `Handle`s, -/// namely `KV` handles, which point to key/value pairs, and `Edge` handles, which point to edges -/// before or after key/value pairs. Methods are provided for removing pairs, inserting into edges, -/// accessing the stored values, and moving around the `Node`. -/// -/// This handle is generic, and can take any sort of reference to a `Node`. The reason for this is -/// two-fold. First of all, it reduces the amount of repetitive code, implementing functions that -/// don't need mutability on both mutable and immutable references. Secondly and more importantly, -/// this allows users of the `Handle` API to associate metadata with the reference. This is used in -/// `BTreeMap` to give `Node`s temporary "IDs" that persist to when the `Node` is used in a -/// `Handle`. +/// A reference to a node. /// -/// # A note on safety -/// -/// Unfortunately, the extra power afforded by being generic also means that safety can technically -/// be broken. For sensible implementations of `Deref` and `DerefMut`, these handles are perfectly -/// safe. As long as repeatedly calling `.deref()` results in the same Node being returned each -/// time, everything should work fine. However, if the `Deref` implementation swaps in multiple -/// different nodes, then the indices that are assumed to be in bounds suddenly stop being so. For -/// example: -/// -/// ```rust,ignore -/// struct Nasty<'a> { -/// first: &'a Node, -/// second: &'a Node, -/// flag: &'a Cell, -/// } -/// -/// impl<'a> Deref for Nasty<'a> { -/// type Target = Node; -/// -/// fn deref(&self) -> &Node { -/// if self.flag.get() { -/// &*self.second -/// } else { -/// &*self.first -/// } -/// } -/// } -/// -/// fn main() { -/// let flag = Cell::new(false); -/// let mut small_node = Node::make_leaf_root(3); -/// let mut large_node = Node::make_leaf_root(100); -/// -/// for i in 0..100 { -/// // Insert to the end -/// large_node.edge_handle(i).insert_as_leaf(i, i); -/// } -/// -/// let nasty = Nasty { -/// first: &large_node, -/// second: &small_node, -/// flag: &flag -/// } -/// -/// // The handle points at index 75. -/// let handle = Node::search(nasty, 75); -/// -/// // Now the handle still points at index 75, but on the small node, which has no index 75. -/// flag.set(true); -/// -/// println!("Uninitialized memory: {:?}", handle.into_kv()); -/// } -/// ``` -#[derive(Copy, Clone)] -pub struct Handle { - node: NodeRef, - index: usize, - marker: PhantomData<(Type, NodeType)>, +/// This type has a number of paramaters that controls how it acts: +/// - `BorrowType`: This can be `Immut<'a>` or `Mut<'a>` for some `'a` or `Owned`. +/// When this is `Immut<'a>`, the `NodeRef` acts roughly like `&'a Node`, +/// when this is `Mut<'a>`, the `NodeRef` acts roughly like `&'a mut Node`, +/// and when this is `Owned`, the `NodeRef` acts roughly like `Box`. +/// - `K` and `V`: These control what types of things are stored in the nodes. +/// - `Type`: This can be `Leaf`, `Internal`, or `LeafOrInternal`. When this is +/// `Leaf`, the `NodeRef` points to a leaf node, when this is `Internal` the +/// `NodeRef` points to an internal node, and when this is `LeafOrInternal` the +/// `NodeRef` could be pointing to either type of node. +pub struct NodeRef { + height: usize, + node: NonZero<*mut LeafNode>, + root: *mut Root, + _marker: PhantomData<(BorrowType, Type)> } -pub mod handle { - // Handle types. - pub enum KV {} - pub enum Edge {} - - // Handle node types. - pub enum LeafOrInternal {} - pub enum Leaf {} - pub enum Internal {} +impl<'a, K: 'a, V: 'a, Type> Copy for NodeRef, K, V, Type> { } +impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef, K, V, Type> { + fn clone(&self) -> Self { + *self + } } -impl Node { - /// Searches for the given key in the node. If it finds an exact match, - /// `Found` will be yielded with the matching index. If it doesn't find an exact match, - /// `GoDown` will be yielded with the index of the subtree the key must lie in. - pub fn search>>(node: NodeRef, - key: &Q) - -> SearchResult - where K: Borrow, - Q: Ord - { - // FIXME(Gankro): Tune when to search linear or binary based on B (and maybe K/V). - // For the B configured as of this writing (B = 6), binary search was *significantly* - // worse for usizes. - match node.as_slices_internal().search_linear(key) { - (index, true) => { - Found(Handle { - node: node, - index: index, - marker: PhantomData, - }) - } - (index, false) => { - GoDown(Handle { - node: node, - index: index, - marker: PhantomData, - }) - } +unsafe impl Sync + for NodeRef { } + +unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send + for NodeRef, K, V, Type> { } +unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send + for NodeRef, K, V, Type> { } +unsafe impl Send + for NodeRef { } + +impl NodeRef { + fn as_internal(&self) -> &InternalNode { + unsafe { + &*(*self.node as *const InternalNode) } } } -// Public interface -impl Node { - /// Make a leaf root from scratch - pub fn make_leaf_root(b: usize) -> Node { - Node::new_leaf(capacity_from_b(b)) - } - - /// Make an internal root and swap it with an old root - pub fn make_internal_root(left_and_out: &mut Node, - b: usize, - key: K, - value: V, - right: Node) { - let node = mem::replace(left_and_out, - unsafe { Node::new_internal(capacity_from_b(b)) }); - left_and_out._len = 1; +impl<'a, K, V> NodeRef, K, V, marker::Internal> { + fn as_internal_mut(&mut self) -> &mut InternalNode { unsafe { - ptr::write(left_and_out.keys_mut().get_unchecked_mut(0), key); - ptr::write(left_and_out.vals_mut().get_unchecked_mut(0), value); - ptr::write(left_and_out.edges_mut().get_unchecked_mut(0), node); - ptr::write(left_and_out.edges_mut().get_unchecked_mut(1), right); + &mut *(*self.node as *mut InternalNode) } } +} - /// How many key-value pairs the node contains - pub fn len(&self) -> usize { - self._len - } - /// Does the node not contain any key-value pairs - pub fn is_empty(&self) -> bool { - self.len() == 0 +impl NodeRef { + pub fn len(&self) -> usize { + self.as_leaf().len as usize } - /// How many key-value pairs the node can fit - pub fn capacity(&self) -> usize { - self._capacity + pub fn forget_type(self) -> NodeRef { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData + } } - /// If the node has any children - pub fn is_leaf(&self) -> bool { - self.edges.is_none() + fn reborrow<'a>(&'a self) -> NodeRef, K, V, Type> { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData + } } - /// if the node has too few elements - pub fn is_underfull(&self) -> bool { - self.len() < min_load_from_capacity(self.capacity()) + fn as_leaf(&self) -> &LeafNode { + unsafe { + &**self.node + } } - /// if the node cannot fit any more elements - pub fn is_full(&self) -> bool { - self.len() == self.capacity() + pub fn keys(&self) -> &[K] { + self.reborrow().into_slices().0 } -} -impl>, Type, NodeType> Handle { - /// Returns a reference to the node that contains the pointed-to edge or key/value pair. This - /// is very different from `edge` and `edge_mut` because those return children of the node - /// returned by `node`. - pub fn node(&self) -> &Node { - &*self.node + pub fn vals(&self) -> &[V] { + self.reborrow().into_slices().1 } -} -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Converts a handle into one that stores the same information using a raw pointer. This can - /// be useful in conjunction with `from_raw` when the type system is insufficient for - /// determining the lifetimes of the nodes. - pub fn as_raw(&mut self) -> Handle<*mut Node, Type, NodeType> { - Handle { - node: &mut *self.node as *mut _, - index: self.index, - marker: PhantomData, + pub fn ascend(self) -> Result< + Handle< + NodeRef< + BorrowType, + K, V, + marker::Internal + >, + marker::Edge + >, + Self + > { + if self.as_leaf().parent.is_null() { + Err(self) + } else { + Ok(Handle { + node: NodeRef { + height: self.height + 1, + node: unsafe { + NonZero::new(self.as_leaf().parent as *mut LeafNode) + }, + root: self.root, + _marker: PhantomData + }, + idx: self.as_leaf().parent_idx as usize, + _marker: PhantomData + }) } } -} -impl Handle<*mut Node, Type, NodeType> { - /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle - /// stored with a reference. This is an unsafe inverse of `as_raw`, and together they allow - /// unsafely extending the lifetime of the reference to the `Node`. - pub unsafe fn from_raw<'a>(&'a self) -> Handle<&'a Node, Type, NodeType> { - Handle { - node: &*self.node, - index: self.index, - marker: PhantomData, - } + pub fn first_edge(self) -> Handle { + Handle::new_edge(self, 0) } - /// Converts from a handle stored with a raw pointer, which isn't directly usable, to a handle - /// stored with a mutable reference. This is an unsafe inverse of `as_raw`, and together they - /// allow unsafely extending the lifetime of the reference to the `Node`. - pub unsafe fn from_raw_mut<'a>(&'a mut self) -> Handle<&'a mut Node, Type, NodeType> { - Handle { - node: &mut *self.node, - index: self.index, - marker: PhantomData, - } + pub fn last_edge(self) -> Handle { + let len = self.len(); + Handle::new_edge(self, len) } } -impl<'a, K: 'a, V: 'a> Handle<&'a Node, handle::Edge, handle::Internal> { - /// Turns the handle into a reference to the edge it points at. This is necessary because the - /// returned pointer has a larger lifetime than what would be returned by `edge` or `edge_mut`, - /// making it more suitable for moving down a chain of nodes. - pub fn into_edge(self) -> &'a Node { - unsafe { self.node.edges().get_unchecked(self.index) } +impl NodeRef { + pub unsafe fn deallocate_and_ascend(self) -> Option< + Handle< + NodeRef< + marker::Owned, + K, V, + marker::Internal + >, + marker::Edge + > + > { + let ptr = self.as_leaf() as *const LeafNode as *const u8 as *mut u8; + let ret = self.ascend().ok(); + heap::deallocate(ptr, mem::size_of::>(), mem::align_of::>()); + ret } } -impl<'a, K: 'a, V: 'a> Handle<&'a mut Node, handle::Edge, handle::Internal> { - /// Turns the handle into a mutable reference to the edge it points at. This is necessary - /// because the returned pointer has a larger lifetime than what would be returned by - /// `edge_mut`, making it more suitable for moving down a chain of nodes. - pub fn into_edge_mut(self) -> &'a mut Node { - unsafe { self.node.edges_mut().get_unchecked_mut(self.index) } +impl NodeRef { + pub unsafe fn deallocate_and_ascend(self) -> Option< + Handle< + NodeRef< + marker::Owned, + K, V, + marker::Internal + >, + marker::Edge + > + > { + let ptr = self.as_internal() as *const InternalNode as *const u8 as *mut u8; + let ret = self.ascend().ok(); + heap::deallocate( + ptr, + mem::size_of::>(), + mem::align_of::>() + ); + ret } } -impl>> Handle { - // This doesn't exist because there are no uses for it, - // but is fine to add, analogous to edge_mut. - // - // /// Returns a reference to the edge pointed-to by this handle. This should not be - // /// confused with `node`, which references the parent node of what is returned here. - // pub fn edge(&self) -> &Node -} - -pub enum ForceResult { - Leaf(Handle), - Internal(Handle), -} +impl<'a, K, V, Type> NodeRef, K, V, Type> { + unsafe fn cast_unchecked(&mut self) + -> NodeRef { -impl>, Type> - Handle -{ - /// Figure out whether this handle is pointing to something in a leaf node or to something in - /// an internal node, clarifying the type according to the result. - pub fn force(self) -> ForceResult { - if self.node.is_leaf() { - Leaf(Handle { - node: self.node, - index: self.index, - marker: PhantomData, - }) - } else { - Internal(Handle { - node: self.node, - index: self.index, - marker: PhantomData, - }) + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData } } -} -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Tries to insert this key-value pair at the given index in this leaf node - /// If the node is full, we have to split it. - /// - /// Returns a *mut V to the inserted value, because the caller may want this when - /// they're done mutating the tree, but we don't want to borrow anything for now. - pub fn insert_as_leaf(mut self, key: K, value: V) -> (InsertionResult, *mut V) { - if !self.node.is_full() { - // The element can fit, just insert it - (Fit, unsafe { self.node.insert_kv(self.index, key, value) as *mut _ }) - } else { - // The element can't fit, this node is full. Split it into two nodes. - let (new_key, new_val, mut new_right) = self.node.split(); - let left_len = self.node.len(); - - let ptr = unsafe { - if self.index <= left_len { - self.node.insert_kv(self.index, key, value) - } else { - // We need to subtract 1 because in splitting we took out new_key and new_val. - // Just being in the right node means we are past left_len k/v pairs in the - // left node and 1 k/v pair in the parent node. - new_right.insert_kv(self.index - left_len - 1, key, value) - } - } as *mut _; - - (Split(new_key, new_val, new_right), ptr) - } - } -} - -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Returns a mutable reference to the edge pointed-to by this handle. This should not be - /// confused with `node`, which references the parent node of what is returned here. - pub fn edge_mut(&mut self) -> &mut Node { - unsafe { self.node.edges_mut().get_unchecked_mut(self.index) } - } - - /// Tries to insert this key-value pair at the given index in this internal node - /// If the node is full, we have to split it. - pub fn insert_as_internal(mut self, - key: K, - value: V, - right: Node) - -> InsertionResult { - if !self.node.is_full() { - // The element can fit, just insert it - unsafe { - self.node.insert_kv(self.index, key, value); - self.node.insert_edge(self.index + 1, right); // +1 to insert to the right - } - Fit - } else { - // The element can't fit, this node is full. Split it into two nodes. - let (new_key, new_val, mut new_right) = self.node.split(); - let left_len = self.node.len(); - if self.index <= left_len { - unsafe { - self.node.insert_kv(self.index, key, value); - self.node.insert_edge(self.index + 1, right); // +1 to insert to the right - } - } else { - unsafe { - // The -1 here is for the same reason as in insert_as_internal - because we - // split, there are actually left_len + 1 k/v pairs before the right node, with - // the extra 1 being put in the parent. - new_right.insert_kv(self.index - left_len - 1, key, value); - new_right.insert_edge(self.index - left_len, right); - } - } - - Split(new_key, new_val, new_right) + unsafe fn reborrow_mut(&mut self) -> NodeRef { + NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData } } - /// Handle an underflow in this node's child. We favor handling "to the left" because we know - /// we're empty, but our neighbour can be full. Handling to the left means when we choose to - /// steal, we pop off the end of our neighbour (always fast) and "unshift" ourselves - /// (always slow, but at least faster since we know we're half-empty). - /// Handling "to the right" reverses these roles. Of course, we merge whenever possible - /// because we want dense nodes, and merging is about equal work regardless of direction. - pub fn handle_underflow(mut self) { + fn as_leaf_mut(&mut self) -> &mut LeafNode { unsafe { - if self.index > 0 { - self.handle_underflow_to_left(); - } else { - self.handle_underflow_to_right(); - } + &mut **self.node } } - /// Right is underflowed. Tries to steal from left, - /// but merges left and right if left is low too. - unsafe fn handle_underflow_to_left(&mut self) { - let left_len = self.node.edges()[self.index - 1].len(); - if left_len > min_load_from_capacity(self.node.capacity()) { - self.left_kv().steal_rightward(); - } else { - self.left_kv().merge_children(); - } + pub fn keys_mut(&mut self) -> &mut [K] { + unsafe { self.reborrow_mut().into_slices_mut().0 } } - /// Left is underflowed. Tries to steal from the right, - /// but merges left and right if right is low too. - unsafe fn handle_underflow_to_right(&mut self) { - let right_len = self.node.edges()[self.index + 1].len(); - if right_len > min_load_from_capacity(self.node.capacity()) { - self.right_kv().steal_leftward(); - } else { - self.right_kv().merge_children(); - } + pub fn vals_mut(&mut self) -> &mut [V] { + unsafe { self.reborrow_mut().into_slices_mut().1 } } } -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Gets the handle pointing to the key/value pair just to the left of the pointed-to edge. - /// This is unsafe because the handle might point to the first edge in the node, which has no - /// pair to its left. - unsafe fn left_kv<'a>(&'a mut self) -> Handle<&'a mut Node, handle::KV, NodeType> { - Handle { - node: &mut *self.node, - index: self.index - 1, - marker: PhantomData, +impl<'a, K: 'a, V: 'a, Type> NodeRef, K, V, Type> { + pub fn into_slices(self) -> (&'a [K], &'a [V]) { + unsafe { + ( + slice::from_raw_parts( + self.as_leaf().keys.as_ptr(), + self.len() + ), + slice::from_raw_parts( + self.as_leaf().vals.as_ptr(), + self.len() + ) + ) } } +} - /// Gets the handle pointing to the key/value pair just to the right of the pointed-to edge. - /// This is unsafe because the handle might point to the last edge in the node, which has no - /// pair to its right. - unsafe fn right_kv<'a>(&'a mut self) -> Handle<&'a mut Node, handle::KV, NodeType> { - Handle { - node: &mut *self.node, - index: self.index, - marker: PhantomData, +impl<'a, K: 'a, V: 'a, Type> NodeRef, K, V, Type> { + pub fn into_root_mut(self) -> &'a mut Root { + unsafe { + &mut *self.root } } -} -impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a Node, handle::KV, NodeType> { - /// Turns the handle into references to the key and value it points at. This is necessary - /// because the returned pointers have larger lifetimes than what would be returned by `key` - /// or `val`. - pub fn into_kv(self) -> (&'a K, &'a V) { - let (keys, vals) = self.node.as_slices(); + pub fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) { unsafe { - (keys.get_unchecked(self.index), - vals.get_unchecked(self.index)) + ( + slice::from_raw_parts_mut( + &mut self.as_leaf_mut().keys as *mut [K] as *mut K, + self.len() + ), + slice::from_raw_parts_mut( + &mut self.as_leaf_mut().vals as *mut [V] as *mut V, + self.len() + ) + ) } } } -impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a mut Node, handle::KV, NodeType> { - /// Turns the handle into mutable references to the key and value it points at. This is - /// necessary because the returned pointers have larger lifetimes than what would be returned - /// by `key_mut` or `val_mut`. - pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) { - let (keys, vals) = self.node.as_slices_mut(); +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); + + let idx = self.len(); + unsafe { - (keys.get_unchecked_mut(self.index), - vals.get_unchecked_mut(self.index)) + ptr::write(self.keys_mut().get_unchecked_mut(idx), key); + ptr::write(self.vals_mut().get_unchecked_mut(idx), val); } + + self.as_leaf_mut().len += 1; } - /// Convert this handle into one pointing at the edge immediately to the left of the key/value - /// pair pointed-to by this handle. This is useful because it returns a reference with larger - /// lifetime than `left_edge`. - pub fn into_left_edge(self) -> Handle<&'a mut Node, handle::Edge, NodeType> { - Handle { - node: &mut *self.node, - index: self.index, - marker: PhantomData, + pub fn push_front(&mut self, key: K, val: V) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() < CAPACITY); + + unsafe { + slice_insert(self.keys_mut(), 0, key); + slice_insert(self.vals_mut(), 0, val); } + + self.as_leaf_mut().len += 1; } } +impl<'a, K, V> NodeRef, K, V, marker::Internal> { + pub fn push(&mut self, key: K, val: V, edge: Root) { + // Necessary for correctness, but this is an internal module + debug_assert!(edge.height == self.height - 1); + debug_assert!(self.len() < CAPACITY); -impl<'a, K: 'a, V: 'a, NodeRef: Deref> + 'a, NodeType> Handle { - // These are fine to include, but are currently unneeded. - // - // /// Returns a reference to the key pointed-to by this handle. This doesn't return a - // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the - // /// handle. - // pub fn key(&'a self) -> &'a K { - // unsafe { self.node.keys().get_unchecked(self.index) } - // } - // - // /// Returns a reference to the value pointed-to by this handle. This doesn't return a - // /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the - // /// handle. - // pub fn val(&'a self) -> &'a V { - // unsafe { self.node.vals().get_unchecked(self.index) } - // } -} + let idx = self.len(); -impl<'a, K: 'a, V: 'a, NodeRef, NodeType> Handle - where NodeRef: 'a + Deref> + DerefMut -{ - /// Returns a mutable reference to the key pointed-to by this handle. This doesn't return a - /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the - /// handle. - pub fn key_mut(&'a mut self) -> &'a mut K { - unsafe { self.node.keys_mut().get_unchecked_mut(self.index) } - } + unsafe { + ptr::write(self.keys_mut().get_unchecked_mut(idx), key); + ptr::write(self.vals_mut().get_unchecked_mut(idx), val); + ptr::write(self.as_internal_mut().edges.get_unchecked_mut(idx + 1), edge.node); - /// Returns a mutable reference to the value pointed-to by this handle. This doesn't return a - /// reference with a lifetime as large as `into_kv_mut`, but it also does not consume the - /// handle. - pub fn val_mut(&'a mut self) -> &'a mut V { - unsafe { self.node.vals_mut().get_unchecked_mut(self.index) } - } -} + self.as_leaf_mut().len += 1; -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Gets the handle pointing to the edge immediately to the left of the key/value pair pointed - /// to by this handle. - pub fn left_edge<'a>(&'a mut self) -> Handle<&'a mut Node, handle::Edge, NodeType> { - Handle { - node: &mut *self.node, - index: self.index, - marker: PhantomData, + Handle::new_edge(self.reborrow_mut(), idx + 1).correct_parent_link(); } } - /// Gets the handle pointing to the edge immediately to the right of the key/value pair pointed - /// to by this handle. - pub fn right_edge<'a>(&'a mut self) -> Handle<&'a mut Node, handle::Edge, NodeType> { - Handle { - node: &mut *self.node, - index: self.index + 1, - marker: PhantomData, + pub fn push_front(&mut self, key: K, val: V, edge: Root) { + // Necessary for correctness, but this is an internal module + debug_assert!(edge.height == self.height - 1); + debug_assert!(self.len() < CAPACITY); + + unsafe { + slice_insert(self.keys_mut(), 0, key); + slice_insert(self.vals_mut(), 0, val); + slice_insert( + slice::from_raw_parts_mut( + self.as_internal_mut().edges.as_mut_ptr(), + self.len()+1 + ), + 0, + edge.node + ); + + self.as_leaf_mut().len += 1; + + for i in 0..self.len()+1 { + Handle::new_edge(self.reborrow_mut(), i).correct_parent_link(); + } } - } -} -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Removes the key/value pair at the handle's location. - /// - /// # Panics (in debug build) - /// - /// Panics if the node containing the pair is not a leaf node. - pub fn remove_as_leaf(mut self) -> (K, V) { - unsafe { self.node.remove_kv(self.index) } } } -impl Handle - where NodeRef: Deref> + DerefMut -{ - /// Steal! Stealing is roughly analogous to a binary tree rotation. - /// In this case, we're "rotating" right. - unsafe fn steal_rightward(&mut self) { - // Take the biggest stuff off left - let (mut key, mut val, edge) = { - let mut left_handle = self.left_edge(); - let left = left_handle.edge_mut(); - let (key, val) = left.pop_kv(); - let edge = if left.is_leaf() { - None - } else { - Some(left.pop_edge()) +impl<'a, K, V> NodeRef, K, V, marker::LeafOrInternal> { + pub fn pop(&mut self) -> (K, V, Option>) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() > 0); + + let idx = self.len() - 1; + + unsafe { + let key = ptr::read(self.keys().get_unchecked(idx)); + let val = ptr::read(self.vals().get_unchecked(idx)); + let edge = match self.reborrow_mut().force() { + ForceResult::Leaf(_) => None, + ForceResult::Internal(internal) => { + let edge = ptr::read(internal.as_internal().edges.get_unchecked(idx + 1)); + let mut new_root = Root { node: edge, height: internal.height - 1 }; + new_root.as_mut().as_leaf_mut().parent = ptr::null(); + Some(new_root) + } }; + self.as_leaf_mut().len -= 1; (key, val, edge) - }; - - // Swap the parent's separating key-value pair with left's - mem::swap(&mut key, self.key_mut()); - mem::swap(&mut val, self.val_mut()); - - // Put them at the start of right - let mut right_handle = self.right_edge(); - let right = right_handle.edge_mut(); - right.insert_kv(0, key, val); - match edge { - Some(edge) => right.insert_edge(0, edge), - None => {} } } - /// Steal! Stealing is roughly analogous to a binary tree rotation. - /// In this case, we're "rotating" left. - unsafe fn steal_leftward(&mut self) { - // Take the smallest stuff off right - let (mut key, mut val, edge) = { - let mut right_handle = self.right_edge(); - let right = right_handle.edge_mut(); - let (key, val) = right.remove_kv(0); - let edge = if right.is_leaf() { - None - } else { - Some(right.remove_edge(0)) - }; + pub fn pop_front(&mut self) -> (K, V, Option>) { + // Necessary for correctness, but this is an internal module + debug_assert!(self.len() > 0); - (key, val, edge) - }; + let old_len = self.len(); - // Swap the parent's separating key-value pair with right's - mem::swap(&mut key, self.key_mut()); - mem::swap(&mut val, self.val_mut()); - - // Put them at the end of left - let mut left_handle = self.left_edge(); - let left = left_handle.edge_mut(); - left.push_kv(key, val); - match edge { - Some(edge) => left.push_edge(edge), - None => {} - } - } + unsafe { + let key = slice_remove(self.keys_mut(), 0); + let val = slice_remove(self.vals_mut(), 0); + let edge = match self.reborrow_mut().force() { + ForceResult::Leaf(_) => None, + ForceResult::Internal(mut internal) => { + let edge = slice_remove( + slice::from_raw_parts_mut( + internal.as_internal_mut().edges.as_mut_ptr(), + old_len+1 + ), + 0 + ); + + let mut new_root = Root { node: edge, height: internal.height - 1 }; + new_root.as_mut().as_leaf_mut().parent = ptr::null(); + + for i in 0..old_len { + Handle::new_edge(internal.reborrow_mut(), i).correct_parent_link(); + } + + Some(new_root) + } + }; - /// Merge! Smooshes left and right into one node, along with the key-value - /// pair that separated them in their parent. - unsafe fn merge_children(mut self) { - // Permanently remove right's index, and the key-value pair that separates - // left and right - let (key, val) = self.node.remove_kv(self.index); - let right = self.node.remove_edge(self.index + 1); + self.as_leaf_mut().len -= 1; - // Give left right's stuff. - self.left_edge() - .edge_mut() - .absorb(key, val, right); + (key, val, edge) + } } } -impl Node { - /// Returns the mutable handle pointing to the key/value pair at a given index. - /// - /// # Panics (in debug build) - /// - /// Panics if the given index is out of bounds. - pub fn kv_handle(&mut self, - index: usize) - -> Handle<&mut Node, handle::KV, handle::LeafOrInternal> { - // Necessary for correctness, but in a private module - debug_assert!(index < self.len(), "kv_handle index out of bounds"); - Handle { - node: self, - index: index, - marker: PhantomData, +impl NodeRef { + pub fn force(self) -> ForceResult< + NodeRef, + NodeRef + > { + if self.height == 0 { + ForceResult::Leaf(NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData + }) + } else { + ForceResult::Internal(NodeRef { + height: self.height, + node: self.node, + root: self.root, + _marker: PhantomData + }) } } +} - pub fn iter<'a>(&'a self) -> Traversal<'a, K, V> { - self.as_slices_internal().iter() - } +pub struct Handle { + node: Node, + idx: usize, + _marker: PhantomData +} - pub fn iter_mut<'a>(&'a mut self) -> MutTraversal<'a, K, V> { - self.as_slices_internal_mut().iter_mut() +impl Copy for Handle { } +impl Clone for Handle { + fn clone(&self) -> Self { + *self } +} - pub fn into_iter(self) -> MoveTraversal { - unsafe { - let ret = MoveTraversal { - inner: MoveTraversalImpl { - keys: RawItems::from_slice(self.keys()), - vals: RawItems::from_slice(self.vals()), - edges: RawItems::from_slice(self.edges()), - - ptr: Unique::new(*self.keys as *mut u8), - capacity: self.capacity(), - is_leaf: self.is_leaf(), - }, - head_is_edge: true, - tail_is_edge: true, - has_edges: !self.is_leaf(), - }; - mem::forget(self); - ret - } +impl Handle { + pub fn into_node(self) -> Node { + self.node } +} - /// When a node has no keys or values and only a single edge, extract that edge. - pub fn hoist_lone_child(&mut self) { +impl Handle, marker::KV> { + pub fn new_kv(node: NodeRef, idx: usize) -> Self { // Necessary for correctness, but in a private module - debug_assert!(self.is_empty()); - debug_assert!(!self.is_leaf()); + debug_assert!(idx < node.len()); - unsafe { - let ret = ptr::read(self.edges().get_unchecked(0)); - self.destroy(); - ptr::write(self, ret); + Handle { + node: node, + idx: idx, + _marker: PhantomData } } -} - -// Vector functions (all unchecked) -impl Node { - // This must be followed by push_edge on an internal node. - #[inline] - unsafe fn push_kv(&mut self, key: K, val: V) { - let len = self.len(); - - ptr::write(self.keys_mut().get_unchecked_mut(len), key); - ptr::write(self.vals_mut().get_unchecked_mut(len), val); - self._len += 1; + pub fn left_edge(self) -> Handle, marker::Edge> { + Handle::new_edge(self.node, self.idx) } - // This can only be called immediately after a call to push_kv. - #[inline] - unsafe fn push_edge(&mut self, edge: Node) { - let len = self.len(); - - ptr::write(self.edges_mut().get_unchecked_mut(len), edge); + pub fn right_edge(self) -> Handle, marker::Edge> { + Handle::new_edge(self.node, self.idx + 1) } +} - // This must be followed by insert_edge on an internal node. - #[inline] - unsafe fn insert_kv(&mut self, index: usize, key: K, val: V) -> &mut V { - ptr::copy(self.keys().as_ptr().offset(index as isize), - self.keys_mut().as_mut_ptr().offset(index as isize + 1), - self.len() - index); - ptr::copy(self.vals().as_ptr().offset(index as isize), - self.vals_mut().as_mut_ptr().offset(index as isize + 1), - self.len() - index); +impl PartialEq + for Handle, HandleType> { - ptr::write(self.keys_mut().get_unchecked_mut(index), key); - ptr::write(self.vals_mut().get_unchecked_mut(index), val); + fn eq(&self, other: &Self) -> bool { + self.node.node == other.node.node && self.idx == other.idx + } +} - self._len += 1; +impl + Handle, HandleType> { - self.vals_mut().get_unchecked_mut(index) - } + pub fn reborrow(&self) + -> Handle, HandleType> { - // This can only be called immediately after a call to insert_kv. - #[inline] - unsafe fn insert_edge(&mut self, index: usize, edge: Node) { - ptr::copy(self.edges().as_ptr().offset(index as isize), - self.edges_mut().as_mut_ptr().offset(index as isize + 1), - self.len() - index); - ptr::write(self.edges_mut().get_unchecked_mut(index), edge); + // We can't use Handle::new_kv or Handle::new_edge because we don't know our type + Handle { + node: self.node.reborrow(), + idx: self.idx, + _marker: PhantomData + } } +} - // This must be followed by pop_edge on an internal node. - #[inline] - unsafe fn pop_kv(&mut self) -> (K, V) { - let key = ptr::read(self.keys().get_unchecked(self.len() - 1)); - let val = ptr::read(self.vals().get_unchecked(self.len() - 1)); +impl<'a, K, V, NodeType, HandleType> + Handle, K, V, NodeType>, HandleType> { - self._len -= 1; + pub unsafe fn reborrow_mut(&mut self) + -> Handle, HandleType> { - (key, val) + // We can't use Handle::new_kv or Handle::new_edge because we don't know our type + Handle { + node: self.node.reborrow_mut(), + idx: self.idx, + _marker: PhantomData + } } +} - // This can only be called immediately after a call to pop_kv. - #[inline] - unsafe fn pop_edge(&mut self) -> Node { - let edge = ptr::read(self.edges().get_unchecked(self.len() + 1)); - - edge - } +impl + Handle, marker::Edge> { - // This must be followed by remove_edge on an internal node. - #[inline] - unsafe fn remove_kv(&mut self, index: usize) -> (K, V) { - let key = ptr::read(self.keys().get_unchecked(index)); - let val = ptr::read(self.vals().get_unchecked(index)); + pub fn new_edge(node: NodeRef, idx: usize) -> Self { + // Necessary for correctness, but in a private module + debug_assert!(idx <= node.len()); - ptr::copy(self.keys().as_ptr().offset(index as isize + 1), - self.keys_mut().as_mut_ptr().offset(index as isize), - self.len() - index - 1); - ptr::copy(self.vals().as_ptr().offset(index as isize + 1), - self.vals_mut().as_mut_ptr().offset(index as isize), - self.len() - index - 1); + Handle { + node: node, + idx: idx, + _marker: PhantomData + } + } - self._len -= 1; + pub fn left_kv(self) + -> Result, marker::KV>, Self> { - (key, val) + if self.idx > 0 { + Ok(Handle::new_kv(self.node, self.idx - 1)) + } else { + Err(self) + } } - // This can only be called immediately after a call to remove_kv. - #[inline] - unsafe fn remove_edge(&mut self, index: usize) -> Node { - let edge = ptr::read(self.edges().get_unchecked(index)); + pub fn right_kv(self) + -> Result, marker::KV>, Self> { - ptr::copy(self.edges().as_ptr().offset(index as isize + 1), - self.edges_mut().as_mut_ptr().offset(index as isize), - // index can be == len+1, so do the +1 first to avoid underflow. - (self.len() + 1) - index); - - edge + if self.idx < self.node.len() { + Ok(Handle::new_kv(self.node, self.idx)) + } else { + Err(self) + } } } -// Private implementation details -impl Node { - /// Node is full, so split it into two nodes, and yield the middle-most key-value pair - /// because we have one too many, and our parent now has one too few - fn split(&mut self) -> (K, V, Node) { - // Necessary for correctness, but in a private function - debug_assert!(!self.is_empty()); - - let mut right = if self.is_leaf() { - Node::new_leaf(self.capacity()) - } else { - unsafe { Node::new_internal(self.capacity()) } - }; +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); unsafe { - right._len = self.len() / 2; - let right_offset = self.len() - right.len(); - ptr::copy_nonoverlapping(self.keys().as_ptr().offset(right_offset as isize), - right.keys_mut().as_mut_ptr(), - right.len()); - ptr::copy_nonoverlapping(self.vals().as_ptr().offset(right_offset as isize), - right.vals_mut().as_mut_ptr(), - right.len()); - if !self.is_leaf() { - ptr::copy_nonoverlapping(self.edges().as_ptr().offset(right_offset as isize), - right.edges_mut().as_mut_ptr(), - right.len() + 1); - } - - let key = ptr::read(self.keys().get_unchecked(right_offset - 1)); - let val = ptr::read(self.vals().get_unchecked(right_offset - 1)); + slice_insert(self.node.keys_mut(), self.idx, key); + slice_insert(self.node.vals_mut(), self.idx, val); - self._len = right_offset - 1; + self.node.as_leaf_mut().len += 1; - (key, val, right) + self.node.vals_mut().get_unchecked_mut(self.idx) } } - /// Take all the values from right, separated by the given key and value - fn absorb(&mut self, key: K, val: V, mut right: Node) { - // Necessary for correctness, but in a private function - // Just as a sanity check, make sure we can fit this guy in - debug_assert!(self.len() + right.len() <= self.capacity()); - debug_assert!(self.is_leaf() == right.is_leaf()); + pub fn insert(mut self, key: K, val: V) + -> (InsertResult<'a, K, V, marker::Leaf>, *mut V) { - unsafe { - let old_len = self.len(); - self._len += right.len() + 1; - - ptr::write(self.keys_mut().get_unchecked_mut(old_len), key); - ptr::write(self.vals_mut().get_unchecked_mut(old_len), val); - - ptr::copy_nonoverlapping(right.keys().as_ptr(), - self.keys_mut().as_mut_ptr().offset(old_len as isize + 1), - right.len()); - ptr::copy_nonoverlapping(right.vals().as_ptr(), - self.vals_mut().as_mut_ptr().offset(old_len as isize + 1), - right.len()); - if !self.is_leaf() { - ptr::copy_nonoverlapping(right.edges().as_ptr(), - self.edges_mut() - .as_mut_ptr() - .offset(old_len as isize + 1), - right.len() + 1); - } - - right.destroy(); - mem::forget(right); + if self.node.len() < CAPACITY { + let ptr = self.insert_fit(key, val); + (InsertResult::Fit(Handle::new_kv(self.node, self.idx)), ptr) + } else { + let middle = Handle::new_kv(self.node, B); + let (mut left, k, v, mut right) = middle.split(); + let ptr = if self.idx <= B { + unsafe { + Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val) + } + } else { + unsafe { + Handle::new_edge( + right.as_mut().cast_unchecked::(), + self.idx - (B + 1) + ).insert_fit(key, val) + } + }; + (InsertResult::Split(left, k, v, right), ptr) } } } -/// Get the capacity of a node from the order of the parent B-Tree -fn capacity_from_b(b: usize) -> usize { - 2 * b - 1 -} - -/// Get the minimum load of a node from its capacity -fn min_load_from_capacity(cap: usize) -> usize { - // B - 1 - cap / 2 -} +impl<'a, K, V> Handle, K, V, marker::Internal>, marker::Edge> { + fn correct_parent_link(mut self) { + let idx = self.idx as u16; + let ptr = self.node.as_internal_mut() as *mut _; + let mut child = self.descend(); + child.as_leaf_mut().parent = ptr; + child.as_leaf_mut().parent_idx = idx; + } -/// A trait for pairs of `Iterator`s, one over edges and the other over key/value pairs. This is -/// necessary, as the `MoveTraversalImpl` needs to have a destructor that deallocates the `Node`, -/// and a pair of `Iterator`s would require two independent destructors. -pub trait TraversalImpl { - type Item; - type Edge; + unsafe fn cast_unchecked(&mut self) + -> Handle, marker::Edge> { - fn next_kv(&mut self) -> Option; - fn next_kv_back(&mut self) -> Option; + Handle::new_edge(self.node.cast_unchecked(), self.idx) + } - fn next_edge(&mut self) -> Option; - fn next_edge_back(&mut self) -> Option; -} + fn insert_fit(&mut self, key: K, val: V, edge: Root) { + // Necessary for correctness, but in an internal module + debug_assert!(self.node.len() < CAPACITY); + debug_assert!(edge.height == self.node.height - 1); -/// A `TraversalImpl` that actually is backed by two iterators. This works in the non-moving case, -/// as no deallocation needs to be done. -#[derive(Clone)] -pub struct ElemsAndEdges(Elems, Edges); + unsafe { + self.cast_unchecked::().insert_fit(key, val); + + slice_insert( + slice::from_raw_parts_mut( + self.node.as_internal_mut().edges.as_mut_ptr(), + self.node.len() + ), + self.idx + 1, + edge.node + ); + + for i in (self.idx+1)..(self.node.len()+1) { + Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link(); + } + } + } -impl - TraversalImpl for ElemsAndEdges - where Elems : Iterator, Edges : Iterator -{ - type Item = (K, V); - type Edge = E; + pub fn insert(mut self, key: K, val: V, edge: Root) + -> InsertResult<'a, K, V, marker::Internal> { - fn next_kv(&mut self) -> Option<(K, V)> { self.0.next() } - fn next_kv_back(&mut self) -> Option<(K, V)> { self.0.next_back() } + // Necessary for correctness, but this is an internal module + debug_assert!(edge.height == self.node.height - 1); - fn next_edge(&mut self) -> Option { self.1.next() } - fn next_edge_back(&mut self) -> Option { self.1.next_back() } + if self.node.len() < CAPACITY { + self.insert_fit(key, val, edge); + InsertResult::Fit(Handle::new_kv(self.node, self.idx)) + } else { + let middle = Handle::new_kv(self.node, B); + let (mut left, k, v, mut right) = middle.split(); + if self.idx <= B { + unsafe { + Handle::new_edge(left.reborrow_mut(), self.idx).insert_fit(key, val, edge); + } + } else { + unsafe { + Handle::new_edge( + right.as_mut().cast_unchecked::(), + self.idx - (B + 1) + ).insert_fit(key, val, edge); + } + } + InsertResult::Split(left, k, v, right) + } + } } -/// A `TraversalImpl` taking a `Node` by value. -pub struct MoveTraversalImpl { - keys: RawItems, - vals: RawItems, - edges: RawItems>, +impl + Handle, marker::Edge> { - // For deallocation when we are done iterating. - ptr: Unique, - capacity: usize, - is_leaf: bool, + pub fn descend(self) -> NodeRef { + NodeRef { + height: self.node.height - 1, + node: unsafe { self.node.as_internal().edges.get_unchecked(self.idx).as_ptr() }, + root: self.node.root, + _marker: PhantomData + } + } } -unsafe impl Sync for MoveTraversalImpl {} -unsafe impl Send for MoveTraversalImpl {} - -impl TraversalImpl for MoveTraversalImpl { - type Item = (K, V); - type Edge = Node; +impl<'a, K: 'a, V: 'a, NodeType> + Handle, K, V, NodeType>, marker::KV> { - fn next_kv(&mut self) -> Option<(K, V)> { - match (self.keys.next(), self.vals.next()) { - (Some(k), Some(v)) => Some((k, v)), - _ => None, + pub fn into_kv(self) -> (&'a K, &'a V) { + let (keys, vals) = self.node.into_slices(); + unsafe { + (keys.get_unchecked(self.idx), vals.get_unchecked(self.idx)) } } +} - fn next_kv_back(&mut self) -> Option<(K, V)> { - match (self.keys.next_back(), self.vals.next_back()) { - (Some(k), Some(v)) => Some((k, v)), - _ => None, - } - } +impl<'a, K: 'a, V: 'a, NodeType> + Handle, K, V, NodeType>, marker::KV> { - fn next_edge(&mut self) -> Option> { - // Necessary for correctness, but in a private module - debug_assert!(!self.is_leaf); - self.edges.next() + pub fn into_kv_mut(self) -> (&'a mut K, &'a mut V) { + let (mut keys, mut vals) = self.node.into_slices_mut(); + unsafe { + (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx)) + } } +} - fn next_edge_back(&mut self) -> Option> { - // Necessary for correctness, but in a private module - debug_assert!(!self.is_leaf); - self.edges.next_back() +impl<'a, K, V, NodeType> Handle, K, V, NodeType>, marker::KV> { + pub fn kv_mut(&mut self) -> (&mut K, &mut V) { + unsafe { + let (mut keys, mut vals) = self.node.reborrow_mut().into_slices_mut(); + (keys.get_unchecked_mut(self.idx), vals.get_unchecked_mut(self.idx)) + } } } -impl Drop for MoveTraversalImpl { - #[unsafe_destructor_blind_to_params] - fn drop(&mut self) { - // We need to cleanup the stored values manually, as the RawItems destructor would run - // after our deallocation. - for _ in self.keys.by_ref() {} - for _ in self.vals.by_ref() {} - for _ in self.edges.by_ref() {} +impl<'a, K, V> Handle, K, V, marker::Leaf>, marker::KV> { + pub fn split(mut self) + -> (NodeRef, K, V, marker::Leaf>, K, V, Root) { + unsafe { + let mut new_node = Box::new(LeafNode::new()); + + let k = ptr::read(self.node.keys().get_unchecked(self.idx)); + let v = ptr::read(self.node.vals().get_unchecked(self.idx)); + + let new_len = self.node.len() - self.idx - 1; + + ptr::copy_nonoverlapping( + self.node.keys().as_ptr().offset(self.idx as isize + 1), + new_node.keys.as_mut_ptr(), + new_len + ); + ptr::copy_nonoverlapping( + self.node.vals().as_ptr().offset(self.idx as isize + 1), + new_node.vals.as_mut_ptr(), + new_len + ); + + self.node.as_leaf_mut().len = self.idx as u16; + new_node.len = new_len as u16; + + ( + self.node, + k, v, + Root { + node: BoxedNode::from_leaf(new_node), + height: 0 + } + ) + } + } - let (alignment, size) = calculate_allocation_generic::(self.capacity, self.is_leaf); - unsafe { heap::deallocate(*self.ptr, size, alignment) }; + pub fn remove(mut self) + -> (Handle, K, V, marker::Leaf>, marker::Edge>, K, V) { + unsafe { + let k = slice_remove(self.node.keys_mut(), self.idx); + let v = slice_remove(self.node.vals_mut(), self.idx); + self.node.as_leaf_mut().len -= 1; + (self.left_edge(), k, v) + } } } -/// An abstraction over all the different kinds of traversals a node supports -#[derive(Clone)] -pub struct AbsTraversal { - inner: Impl, - head_is_edge: bool, - tail_is_edge: bool, - has_edges: bool, -} +impl<'a, K, V> Handle, K, V, marker::Internal>, marker::KV> { + pub fn split(mut self) + -> (NodeRef, K, V, marker::Internal>, K, V, Root) { + unsafe { + let mut new_node = Box::new(InternalNode::new()); + + let k = ptr::read(self.node.keys().get_unchecked(self.idx)); + let v = ptr::read(self.node.vals().get_unchecked(self.idx)); + + let height = self.node.height; + let new_len = self.node.len() - self.idx - 1; + + ptr::copy_nonoverlapping( + self.node.keys().as_ptr().offset(self.idx as isize + 1), + new_node.data.keys.as_mut_ptr(), + new_len + ); + ptr::copy_nonoverlapping( + self.node.vals().as_ptr().offset(self.idx as isize + 1), + new_node.data.vals.as_mut_ptr(), + new_len + ); + ptr::copy_nonoverlapping( + self.node.as_internal().edges.as_ptr().offset(self.idx as isize + 1), + new_node.edges.as_mut_ptr(), + new_len + 1 + ); + + self.node.as_leaf_mut().len = self.idx as u16; + new_node.data.len = new_len as u16; + + let mut new_root = Root { + node: BoxedNode::from_internal(new_node), + height: height + }; -/// A single atomic step in a traversal. -pub enum TraversalItem { - /// An element is visited. This isn't written as `Elem(K, V)` just because `opt.map(Elem)` - /// requires the function to take a single argument. (Enum constructors are functions.) - Elem((K, V)), - /// An edge is followed. - Edge(E), -} + for i in 0..(new_len+1) { + Handle::new_edge(new_root.as_mut().cast_unchecked(), i).correct_parent_link(); + } -/// A traversal over a node's entries and edges -pub type Traversal<'a, K, V> = AbsTraversal, - slice::Iter<'a, V>>, - slice::Iter<'a, Node>>>; + ( + self.node, + k, v, + new_root + ) + } + } -/// A mutable traversal over a node's entries and edges -pub type MutTraversal<'a, K, V> = AbsTraversal, - slice::IterMut<'a, V>>, - slice::IterMut<'a, Node>>>; + pub fn can_merge(&self) -> bool { + ( + self.reborrow() + .left_edge() + .descend() + .len() + + self.reborrow() + .right_edge() + .descend() + .len() + + 1 + ) <= CAPACITY + } + + pub fn merge(mut self) + -> Handle, K, V, marker::Internal>, marker::Edge> { + let self1 = unsafe { ptr::read(&self) }; + let self2 = unsafe { ptr::read(&self) }; + let mut left_node = self1.left_edge().descend(); + let left_len = left_node.len(); + let mut right_node = self2.right_edge().descend(); + let right_len = right_node.len(); + + // necessary for correctness, but in a private module + debug_assert!(left_len + right_len + 1 <= CAPACITY); -/// An owning traversal over a node's entries and edges -pub type MoveTraversal = AbsTraversal>; + unsafe { + ptr::write(left_node.keys_mut().get_unchecked_mut(left_len), + slice_remove(self.node.keys_mut(), self.idx)); + ptr::copy_nonoverlapping( + right_node.keys().as_ptr(), + left_node.keys_mut().as_mut_ptr().offset(left_len as isize + 1), + right_len + ); + ptr::write(left_node.vals_mut().get_unchecked_mut(left_len), + slice_remove(self.node.vals_mut(), self.idx)); + ptr::copy_nonoverlapping( + right_node.vals().as_ptr(), + left_node.vals_mut().as_mut_ptr().offset(left_len as isize + 1), + right_len + ); + + slice_remove(&mut self.node.as_internal_mut().edges, self.idx + 1); + for i in self.idx+1..self.node.len() { + Handle::new_edge(self.node.reborrow_mut(), i).correct_parent_link(); + } + self.node.as_leaf_mut().len -= 1; + + if self.node.height > 1 { + ptr::copy_nonoverlapping( + right_node.cast_unchecked().as_internal().edges.as_ptr(), + left_node.cast_unchecked() + .as_internal_mut() + .edges + .as_mut_ptr() + .offset(left_len as isize + 1), + right_len + 1 + ); + + for i in left_len+1..left_len+right_len+2 { + Handle::new_edge( + left_node.cast_unchecked().reborrow_mut(), + i + ).correct_parent_link(); + } + heap::deallocate( + *right_node.node as *mut u8, + mem::size_of::>(), + mem::align_of::>() + ); + } else { + heap::deallocate( + *right_node.node as *mut u8, + mem::size_of::>(), + mem::align_of::>() + ); + } -impl Iterator for AbsTraversal - where Impl: TraversalImpl -{ - type Item = TraversalItem; + left_node.as_leaf_mut().len += right_len as u16 + 1; - fn next(&mut self) -> Option> { - self.next_edge_item().map(Edge).or_else(|| self.next_kv_item().map(Elem)) + Handle::new_edge(self.node, self.idx) + } } } -impl DoubleEndedIterator for AbsTraversal - where Impl: TraversalImpl -{ - fn next_back(&mut self) -> Option> { - self.next_edge_item_back().map(Edge).or_else(|| self.next_kv_item_back().map(Elem)) +impl + Handle, HandleType> { + + pub fn force(self) -> ForceResult< + Handle, HandleType>, + Handle, HandleType> + > { + match self.node.force() { + ForceResult::Leaf(node) => ForceResult::Leaf(Handle { + node: node, + idx: self.idx, + _marker: PhantomData + }), + ForceResult::Internal(node) => ForceResult::Internal(Handle { + node: node, + idx: self.idx, + _marker: PhantomData + }) + } } } -impl AbsTraversal where Impl: TraversalImpl { - /// Advances the iterator and returns the item if it's an edge. Returns None - /// and does nothing if the first item is not an edge. - pub fn next_edge_item(&mut self) -> Option { - // NB. `&& self.has_edges` might be redundant in this condition. - let edge = if self.head_is_edge && self.has_edges { - self.inner.next_edge() - } else { - None - }; - self.head_is_edge = false; - edge - } - - /// Advances the iterator and returns the item if it's an edge. Returns None - /// and does nothing if the last item is not an edge. - pub fn next_edge_item_back(&mut self) -> Option { - let edge = if self.tail_is_edge && self.has_edges { - self.inner.next_edge_back() - } else { - None - }; - self.tail_is_edge = false; - edge - } - - /// Advances the iterator and returns the item if it's a key-value pair. Returns None - /// and does nothing if the first item is not a key-value pair. - pub fn next_kv_item(&mut self) -> Option<(K, V)> { - if !self.head_is_edge { - self.head_is_edge = true; - self.inner.next_kv() - } else { - None - } - } +pub enum ForceResult { + Leaf(Leaf), + Internal(Internal) +} - /// Advances the iterator and returns the item if it's a key-value pair. Returns None - /// and does nothing if the last item is not a key-value pair. - pub fn next_kv_item_back(&mut self) -> Option<(K, V)> { - if !self.tail_is_edge { - self.tail_is_edge = true; - self.inner.next_kv_back() - } else { - None - } - } +pub enum InsertResult<'a, K, V, Type> { + Fit(Handle, K, V, Type>, marker::KV>), + Split(NodeRef, K, V, Type>, K, V, Root) } -macro_rules! node_slice_impl { - ($NodeSlice:ident, $Traversal:ident, - $as_slices_internal:ident, $index:ident, $iter:ident) => { - impl<'a, K: Ord + 'a, V: 'a> $NodeSlice<'a, K, V> { - /// Performs linear search in a slice. Returns a tuple of (index, is_exact_match). - fn search_linear(&self, key: &Q) -> (usize, bool) - where K: Borrow, Q: Ord { - for (i, k) in self.keys.iter().enumerate() { - match key.cmp(k.borrow()) { - Greater => {}, - Equal => return (i, true), - Less => return (i, false), - } - } - (self.keys.len(), false) - } +pub mod marker { + use core::marker::PhantomData; - /// Returns a sub-slice with elements starting with `min_key`. - pub fn slice_from(self, min_key: &Q) -> $NodeSlice<'a, K, V> where - K: Borrow, - { - // _______________ - // |_1_|_3_|_5_|_7_| - // | | | | | - // 0 0 1 1 2 2 3 3 4 index - // | | | | | - // \___|___|___|___/ slice_from(&0); pos = 0 - // \___|___|___/ slice_from(&2); pos = 1 - // |___|___|___/ slice_from(&3); pos = 1; result.head_is_edge = false - // \___|___/ slice_from(&4); pos = 2 - // \___/ slice_from(&6); pos = 3 - // \|/ slice_from(&999); pos = 4 - let (pos, pos_is_kv) = self.search_linear(min_key); - $NodeSlice { - has_edges: self.has_edges, - edges: if !self.has_edges { - self.edges - } else { - self.edges.$index(pos ..) - }, - keys: &self.keys[pos ..], - vals: self.vals.$index(pos ..), - head_is_edge: !pos_is_kv, - tail_is_edge: self.tail_is_edge, - } - } + pub enum Leaf { } + pub enum Internal { } + pub enum LeafOrInternal { } - /// Returns a sub-slice with elements up to and including `max_key`. - pub fn slice_to(self, max_key: &Q) -> $NodeSlice<'a, K, V> where - K: Borrow, - { - // _______________ - // |_1_|_3_|_5_|_7_| - // | | | | | - // 0 0 1 1 2 2 3 3 4 index - // | | | | | - //\|/ | | | | slice_to(&0); pos = 0 - // \___/ | | | slice_to(&2); pos = 1 - // \___|___| | | slice_to(&3); pos = 1; result.tail_is_edge = false - // \___|___/ | | slice_to(&4); pos = 2 - // \___|___|___/ | slice_to(&6); pos = 3 - // \___|___|___|___/ slice_to(&999); pos = 4 - let (pos, pos_is_kv) = self.search_linear(max_key); - let pos = pos + if pos_is_kv { 1 } else { 0 }; - $NodeSlice { - has_edges: self.has_edges, - edges: if !self.has_edges { - self.edges - } else { - self.edges.$index(.. (pos + 1)) - }, - keys: &self.keys[..pos], - vals: self.vals.$index(.. pos), - head_is_edge: self.head_is_edge, - tail_is_edge: !pos_is_kv, - } - } - } + pub enum Owned { } + pub struct Immut<'a>(PhantomData<&'a ()>); + pub struct Mut<'a>(PhantomData<&'a mut ()>); - impl<'a, K: 'a, V: 'a> $NodeSlice<'a, K, V> { - /// Returns an iterator over key/value pairs and edges in a slice. - #[inline] - pub fn $iter(self) -> $Traversal<'a, K, V> { - let mut edges = self.edges.$iter(); - // Skip edges at both ends, if excluded. - if !self.head_is_edge { edges.next(); } - if !self.tail_is_edge { edges.next_back(); } - // The key iterator is always immutable. - $Traversal { - inner: ElemsAndEdges( - self.keys.iter().zip(self.vals.$iter()), - edges - ), - head_is_edge: self.head_is_edge, - tail_is_edge: self.tail_is_edge, - has_edges: self.has_edges, - } - } - } - } + pub enum KV { } + pub enum Edge { } } -node_slice_impl!(NodeSlice, Traversal, as_slices_internal, index, iter); -node_slice_impl!(MutNodeSlice, MutTraversal, as_slices_internal_mut, index_mut, iter_mut); +unsafe fn slice_insert(slice: &mut [T], idx: usize, val: T) { + ptr::copy( + slice.as_ptr().offset(idx as isize), + slice.as_mut_ptr().offset(idx as isize + 1), + slice.len() - idx + ); + ptr::write(slice.get_unchecked_mut(idx), val); +} + +unsafe fn slice_remove(slice: &mut [T], idx: usize) -> T { + let ret = ptr::read(slice.get_unchecked(idx)); + ptr::copy( + slice.as_ptr().offset(idx as isize + 1), + slice.as_mut_ptr().offset(idx as isize), + slice.len() - idx - 1 + ); + ret +} diff --git a/src/libcollections/btree/search.rs b/src/libcollections/btree/search.rs new file mode 100644 index 00000000000..c94b570bfed --- /dev/null +++ b/src/libcollections/btree/search.rs @@ -0,0 +1,76 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use core::cmp::Ordering; + +use borrow::Borrow; + +use super::node::{Handle, NodeRef, marker}; + +use super::node::ForceResult::*; +use self::SearchResult::*; + +pub enum SearchResult { + Found(Handle, marker::KV>), + GoDown(Handle, marker::Edge>) +} + +pub fn search_tree( + mut node: NodeRef, + key: &Q +) -> SearchResult + where Q: Ord, K: Borrow { + + loop { + match search_node(node, key) { + Found(handle) => return Found(handle), + GoDown(handle) => match handle.force() { + Leaf(leaf) => return GoDown(leaf), + Internal(internal) => { + node = internal.descend(); + continue; + } + } + } + } +} + +pub fn search_node( + node: NodeRef, + key: &Q +) -> SearchResult + where Q: Ord, K: Borrow { + + match search_linear(&node, key) { + (idx, true) => Found( + Handle::new_kv(node, idx) + ), + (idx, false) => SearchResult::GoDown( + Handle::new_edge(node, idx) + ) + } +} + +fn search_linear( + node: &NodeRef, + key: &Q +) -> (usize, bool) + where Q: Ord, K: Borrow { + + for (i, k) in node.keys().iter().enumerate() { + match key.cmp(k.borrow()) { + Ordering::Greater => {}, + Ordering::Equal => return (i, true), + Ordering::Less => return (i, false) + } + } + (node.keys().len(), false) +} + diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs index 8b876df32af..41f52b67079 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -43,8 +43,8 @@ #![feature(iter_arith)] #![feature(iter_arith)] #![feature(lang_items)] +#![feature(nonzero)] #![feature(num_bits_bytes)] -#![feature(oom)] #![feature(pattern)] #![feature(shared)] #![feature(slice_bytes)] @@ -55,7 +55,7 @@ #![feature(unboxed_closures)] #![feature(unicode)] #![feature(unique)] -#![feature(unsafe_no_drop_flag, filling_drop)] +#![feature(unsafe_no_drop_flag)] #![cfg_attr(test, feature(clone_from_slice, rand, test))] #![no_std] -- 2.44.0