diff options
Diffstat (limited to 'src/libcollections/btree')
| -rw-r--r-- | src/libcollections/btree/map.rs | 57 | ||||
| -rw-r--r-- | src/libcollections/btree/node.rs | 93 | ||||
| -rw-r--r-- | src/libcollections/btree/set.rs | 10 |
3 files changed, 100 insertions, 60 deletions
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index 747211e9238..7823f536c7a 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -19,7 +19,6 @@ use self::Entry::*; use core::prelude::*; -use core::borrow::BorrowFrom; use core::cmp::Ordering; use core::default::Default; use core::fmt::Debug; @@ -29,7 +28,8 @@ use core::ops::{Index, IndexMut}; use core::{iter, fmt, mem}; use Bound::{self, Included, Excluded, Unbounded}; -use ring_buf::RingBuf; +use borrow::Borrow; +use vec_deque::VecDeque; use self::Continuation::{Continue, Finished}; use self::StackOp::*; @@ -75,7 +75,7 @@ pub struct BTreeMap<K, V> { /// An abstract base over-which all other BTree iterators are built. struct AbsIter<T> { - traversals: RingBuf<T>, + traversals: VecDeque<T>, size: usize, } @@ -208,7 +208,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.get(&2), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where Q: BorrowFrom<K> + Ord { + pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord { let mut cur_node = &self.root; loop { match Node::search(cur_node, key) { @@ -240,7 +240,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.contains_key(&2), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where Q: BorrowFrom<K> + Ord { + pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord { self.get(key).is_some() } @@ -264,7 +264,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// ``` // 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<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where Q: BorrowFrom<K> + Ord { + pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, 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 { @@ -434,7 +434,7 @@ impl<K: Ord, V> BTreeMap<K, V> { /// assert_eq!(map.remove(&1), None); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where Q: BorrowFrom<K> + Ord { + pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord { // See `swap` for a more thorough description of the stuff going on in here let mut stack = stack::PartialSearchStack::new(self); loop { @@ -512,13 +512,22 @@ mod stack { 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) + } + } + /// 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: marker::InvariantLifetime<'id> + _marker: InvariantLifetime<'id>, } impl<'id, T> Deref for IdRef<'id, T> { @@ -560,7 +569,7 @@ mod stack { pub struct Pusher<'id, 'a, K:'a, V:'a> { map: &'a mut BTreeMap<K, V>, stack: Stack<K, V>, - marker: marker::InvariantLifetime<'id> + _marker: InvariantLifetime<'id>, } impl<'a, K, V> PartialSearchStack<'a, K, V> { @@ -595,11 +604,11 @@ mod stack { let pusher = Pusher { map: self.map, stack: self.stack, - marker: marker::InvariantLifetime + _marker: InvariantLifetime::new(), }; let node = IdRef { inner: unsafe { &mut *self.next }, - marker: marker::InvariantLifetime + _marker: InvariantLifetime::new(), }; closure(pusher, node) @@ -826,7 +835,7 @@ mod stack { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { - fn from_iter<T: Iterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> { + fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> BTreeMap<K, V> { let mut map = BTreeMap::new(); map.extend(iter); map @@ -836,13 +845,14 @@ impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> { #[inline] - fn extend<T: Iterator<Item=(K, V)>>(&mut self, iter: T) { + fn extend<T: IntoIterator<Item=(K, V)>>(&mut self, iter: T) { for (k, v) in iter { self.insert(k, v); } } } +#[cfg(stage0)] #[stable(feature = "rust1", since = "1.0.0")] impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> { fn hash(&self, state: &mut S) { @@ -851,6 +861,15 @@ impl<S: Hasher, K: Hash<S>, V: Hash<S>> Hash<S> for BTreeMap<K, V> { } } } +#[cfg(not(stage0))] +#[stable(feature = "rust1", since = "1.0.0")] +impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> { + fn hash<H: Hasher>(&self, state: &mut H) { + for elt in self { + elt.hash(state); + } + } +} #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, V> Default for BTreeMap<K, V> { @@ -903,7 +922,7 @@ impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V> - where Q: BorrowFrom<K> + Ord + where K: Borrow<Q>, Q: Ord { type Output = V; @@ -914,7 +933,7 @@ impl<K: Ord, Q: ?Sized, V> Index<Q> for BTreeMap<K, V> #[stable(feature = "rust1", since = "1.0.0")] impl<K: Ord, Q: ?Sized, V> IndexMut<Q> for BTreeMap<K, V> - where Q: BorrowFrom<K> + Ord + where K: Borrow<Q>, Q: Ord { fn index_mut(&mut self, key: &Q) -> &mut V { self.get_mut(key).expect("no entry found for key") @@ -1189,7 +1208,7 @@ impl<K, V> BTreeMap<K, V> { pub fn iter(&self) -> Iter<K, V> { let len = self.len(); // NB. The initial capacity for ringbuf is large enough to avoid reallocs in many cases. - let mut lca = RingBuf::new(); + let mut lca = VecDeque::new(); lca.push_back(Traverse::traverse(&self.root)); Iter { inner: AbsIter { @@ -1221,7 +1240,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn iter_mut(&mut self) -> IterMut<K, V> { let len = self.len(); - let mut lca = RingBuf::new(); + let mut lca = VecDeque::new(); lca.push_back(Traverse::traverse(&mut self.root)); IterMut { inner: AbsIter { @@ -1250,7 +1269,7 @@ impl<K, V> BTreeMap<K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn into_iter(self) -> IntoIter<K, V> { let len = self.len(); - let mut lca = RingBuf::new(); + let mut lca = VecDeque::new(); lca.push_back(Traverse::traverse(self.root)); IntoIter { inner: AbsIter { @@ -1342,7 +1361,7 @@ macro_rules! range_impl { // 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 = RingBuf::new(); + let mut traversals = VecDeque::new(); let (root, min, max) = ($root, $min, $max); let mut leftmost = None; diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs index 24523d4dcc9..f0fc12da727 100644 --- a/src/libcollections/btree/node.rs +++ b/src/libcollections/btree/node.rs @@ -18,13 +18,15 @@ pub use self::TraversalItem::*; use core::prelude::*; -use core::borrow::BorrowFrom; use core::cmp::Ordering::{Greater, Less, Equal}; 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, num, raw}; -use alloc::heap; +use alloc::heap::{self, EMPTY}; + +use borrow::Borrow; /// Represents the result of an Insertion: either the item fit, or the node had to split pub enum InsertionResult<K, V> { @@ -57,8 +59,8 @@ pub struct Node<K, V> { keys: Unique<K>, vals: Unique<V>, - // In leaf nodes, this will be null, and no space will be allocated for edges. - edges: Unique<Node<K, V>>, + // In leaf nodes, this will be None, and no space will be allocated for edges. + edges: Option<Unique<Node<K, V>>>, // 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. @@ -278,8 +280,11 @@ impl<T> Drop for RawItems<T> { #[unsafe_destructor] impl<K, V> Drop for Node<K, V> { fn drop(&mut self) { - if self.keys.ptr.is_null() { - // We have already cleaned up this node. + if self.keys.is_null() { + // Since we have #[unsafe_no_drop_flag], we have to watch + // out for a null value being stored in self.keys. (Using + // null is technically a violation of the `Unique` + // requirements, though.) return; } @@ -292,7 +297,7 @@ impl<K, V> Drop for Node<K, V> { self.destroy(); } - self.keys.ptr = ptr::null_mut(); + self.keys = unsafe { Unique::new(0 as *mut K) }; } } @@ -308,9 +313,9 @@ impl<K, V> Node<K, V> { let (vals_offset, edges_offset) = calculate_offsets_generic::<K, V>(capacity, false); Node { - keys: Unique(buffer as *mut K), - vals: Unique(buffer.offset(vals_offset as isize) as *mut V), - edges: Unique(buffer.offset(edges_offset as isize) as *mut Node<K, V>), + 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<K, V>)), _len: 0, _capacity: capacity, } @@ -326,9 +331,9 @@ impl<K, V> Node<K, V> { let (vals_offset, _) = calculate_offsets_generic::<K, V>(capacity, true); Node { - keys: Unique(buffer as *mut K), - vals: Unique(unsafe { buffer.offset(vals_offset as isize) as *mut V }), - edges: Unique(ptr::null_mut()), + 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, } @@ -337,18 +342,18 @@ impl<K, V> Node<K, V> { unsafe fn destroy(&mut self) { let (alignment, size) = calculate_allocation_generic::<K, V>(self.capacity(), self.is_leaf()); - heap::deallocate(self.keys.ptr as *mut u8, size, alignment); + heap::deallocate(*self.keys as *mut u8, size, alignment); } #[inline] pub fn as_slices<'a>(&'a self) -> (&'a [K], &'a [V]) { unsafe {( mem::transmute(raw::Slice { - data: self.keys.ptr, + data: *self.keys as *const K, len: self.len() }), mem::transmute(raw::Slice { - data: self.vals.ptr, + data: *self.vals as *const V, len: self.len() }) )} @@ -367,8 +372,12 @@ impl<K, V> Node<K, V> { &[] } else { unsafe { + let data = match self.edges { + None => heap::EMPTY as *const Node<K,V>, + Some(ref p) => **p as *const Node<K,V>, + }; mem::transmute(raw::Slice { - data: self.edges.ptr, + data: data, len: self.len() + 1 }) } @@ -524,7 +533,8 @@ impl<K: Clone, V: Clone> Clone for Node<K, V> { #[derive(Copy)] pub struct Handle<NodeRef, Type, NodeType> { node: NodeRef, - index: usize + index: usize, + marker: PhantomData<(Type, NodeType)>, } pub mod handle { @@ -543,13 +553,13 @@ impl<K: Ord, V> Node<K, V> { /// `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<Q: ?Sized, NodeRef: Deref<Target=Node<K, V>>>(node: NodeRef, key: &Q) - -> SearchResult<NodeRef> where Q: BorrowFrom<K> + Ord { + -> SearchResult<NodeRef> where K: Borrow<Q>, 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 }), - (index, false) => GoDown(Handle { node: node, index: index }), + (index, true) => Found(Handle { node: node, index: index, marker: PhantomData }), + (index, false) => GoDown(Handle { node: node, index: index, marker: PhantomData }), } } } @@ -586,7 +596,7 @@ impl <K, V> Node<K, V> { /// If the node has any children pub fn is_leaf(&self) -> bool { - self.edges.ptr.is_null() + self.edges.is_none() } /// if the node has too few elements @@ -618,7 +628,8 @@ impl<K, V, NodeRef, Type, NodeType> Handle<NodeRef, Type, NodeType> where pub fn as_raw(&mut self) -> Handle<*mut Node<K, V>, Type, NodeType> { Handle { node: &mut *self.node as *mut _, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -630,7 +641,8 @@ impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> { pub unsafe fn from_raw<'a>(&'a self) -> Handle<&'a Node<K, V>, Type, NodeType> { Handle { node: &*self.node, - index: self.index + index: self.index, + marker: PhantomData, } } @@ -640,7 +652,8 @@ impl<K, V, Type, NodeType> Handle<*mut Node<K, V>, Type, NodeType> { pub unsafe fn from_raw_mut<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, Type, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -688,12 +701,14 @@ impl<K, V, NodeRef: Deref<Target=Node<K, V>>, Type> Handle<NodeRef, Type, handle if self.node.is_leaf() { Leaf(Handle { node: self.node, - index: self.index + index: self.index, + marker: PhantomData, }) } else { Internal(Handle { node: self.node, - index: self.index + index: self.index, + marker: PhantomData, }) } } @@ -826,7 +841,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType> where unsafe fn left_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> { Handle { node: &mut *self.node, - index: self.index - 1 + index: self.index - 1, + marker: PhantomData, } } @@ -836,7 +852,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::Edge, NodeType> where unsafe fn right_kv<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::KV, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -876,7 +893,8 @@ impl<'a, K: 'a, V: 'a, NodeType> Handle<&'a mut Node<K, V>, handle::KV, NodeType pub fn into_left_edge(self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } } @@ -926,7 +944,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType> where pub fn left_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> { Handle { node: &mut *self.node, - index: self.index + index: self.index, + marker: PhantomData, } } @@ -935,7 +954,8 @@ impl<K, V, NodeRef, NodeType> Handle<NodeRef, handle::KV, NodeType> where pub fn right_edge<'a>(&'a mut self) -> Handle<&'a mut Node<K, V>, handle::Edge, NodeType> { Handle { node: &mut *self.node, - index: self.index + 1 + index: self.index + 1, + marker: PhantomData, } } } @@ -1044,7 +1064,8 @@ impl<K, V> Node<K, V> { debug_assert!(index < self.len(), "kv_handle index out of bounds"); Handle { node: self, - index: index + index: index, + marker: PhantomData, } } @@ -1064,7 +1085,7 @@ impl<K, V> Node<K, V> { vals: RawItems::from_slice(self.vals()), edges: RawItems::from_slice(self.edges()), - ptr: self.keys.ptr as *mut u8, + ptr: *self.keys as *mut u8, capacity: self.capacity(), is_leaf: self.is_leaf() }, @@ -1491,9 +1512,9 @@ macro_rules! node_slice_impl { 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<Q: ?Sized>(&self, key: &Q) -> (usize, bool) - where Q: BorrowFrom<K> + Ord { + where K: Borrow<Q>, Q: Ord { for (i, k) in self.keys.iter().enumerate() { - match key.cmp(BorrowFrom::borrow_from(k)) { + match key.cmp(k.borrow()) { Greater => {}, Equal => return (i, true), Less => return (i, false), diff --git a/src/libcollections/btree/set.rs b/src/libcollections/btree/set.rs index 7ef887b70cc..929b2f58043 100644 --- a/src/libcollections/btree/set.rs +++ b/src/libcollections/btree/set.rs @@ -13,7 +13,6 @@ use core::prelude::*; -use core::borrow::BorrowFrom; use core::cmp::Ordering::{self, Less, Greater, Equal}; use core::default::Default; use core::fmt::Debug; @@ -21,6 +20,7 @@ use core::fmt; use core::iter::{Peekable, Map, FromIterator, IntoIterator}; use core::ops::{BitOr, BitAnd, BitXor, Sub}; +use borrow::Borrow; use btree_map::{BTreeMap, Keys}; use Bound; @@ -336,7 +336,7 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.contains(&4), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where Q: BorrowFrom<T> + Ord { + pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: Ord { self.map.contains_key(value) } @@ -466,14 +466,14 @@ impl<T: Ord> BTreeSet<T> { /// assert_eq!(set.remove(&2), false); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where Q: BorrowFrom<T> + Ord { + pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where T: Borrow<Q>, Q: Ord { self.map.remove(value).is_some() } } #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> FromIterator<T> for BTreeSet<T> { - fn from_iter<Iter: Iterator<Item=T>>(iter: Iter) -> BTreeSet<T> { + fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> BTreeSet<T> { let mut set = BTreeSet::new(); set.extend(iter); set @@ -503,7 +503,7 @@ impl<'a, T> IntoIterator for &'a BTreeSet<T> { #[stable(feature = "rust1", since = "1.0.0")] impl<T: Ord> Extend<T> for BTreeSet<T> { #[inline] - fn extend<Iter: Iterator<Item=T>>(&mut self, iter: Iter) { + fn extend<Iter: IntoIterator<Item=T>>(&mut self, iter: Iter) { for elem in iter { self.insert(elem); } |