diff options
Diffstat (limited to 'ctr-std/src/collections/hash/map.rs')
| -rw-r--r-- | ctr-std/src/collections/hash/map.rs | 367 |
1 files changed, 177 insertions, 190 deletions
diff --git a/ctr-std/src/collections/hash/map.rs b/ctr-std/src/collections/hash/map.rs index a82ff91..20a4f9b 100644 --- a/ctr-std/src/collections/hash/map.rs +++ b/ctr-std/src/collections/hash/map.rs @@ -11,6 +11,7 @@ use self::Entry::*; use self::VacantEntryState::*; +use alloc::{Global, Alloc, CollectionAllocErr}; use cell::Cell; use borrow::Borrow; use cmp::max; @@ -19,8 +20,7 @@ use fmt::{self, Debug}; use hash::{Hash, Hasher, BuildHasher, SipHasher13}; use iter::{FromIterator, FusedIterator}; use mem::{self, replace}; -use ops::{Deref, Index, InPlace, Place, Placer}; -use ptr; +use ops::{Deref, Index}; use sys; use super::table::{self, Bucket, EmptyBucket, FullBucket, FullBucketMut, RawTable, SafeHash}; @@ -42,21 +42,28 @@ impl DefaultResizePolicy { /// provide that capacity, accounting for maximum loading. The raw capacity /// is always zero or a power of two. #[inline] - fn raw_capacity(&self, len: usize) -> usize { + fn try_raw_capacity(&self, len: usize) -> Result<usize, CollectionAllocErr> { if len == 0 { - 0 + Ok(0) } else { // 1. Account for loading: `raw_capacity >= len * 1.1`. // 2. Ensure it is a power of two. // 3. Ensure it is at least the minimum size. - let mut raw_cap = len * 11 / 10; - assert!(raw_cap >= len, "raw_cap overflow"); - raw_cap = raw_cap.checked_next_power_of_two().expect("raw_capacity overflow"); + let mut raw_cap = len.checked_mul(11) + .map(|l| l / 10) + .and_then(|l| l.checked_next_power_of_two()) + .ok_or(CollectionAllocErr::CapacityOverflow)?; + raw_cap = max(MIN_NONZERO_RAW_CAPACITY, raw_cap); - raw_cap + Ok(raw_cap) } } + #[inline] + fn raw_capacity(&self, len: usize) -> usize { + self.try_raw_capacity(len).expect("raw_capacity overflow") + } + /// The capacity of the given raw capacity. #[inline] fn capacity(&self, raw_cap: usize) -> usize { @@ -620,7 +627,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomState> { /// /// ``` /// use std::collections::HashMap; - /// let mut map: HashMap<&str, isize> = HashMap::new(); + /// let mut map: HashMap<&str, i32> = HashMap::new(); /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] @@ -637,7 +644,7 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomState> { /// /// ``` /// use std::collections::HashMap; - /// let mut map: HashMap<&str, isize> = HashMap::with_capacity(10); + /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10); /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] @@ -724,7 +731,7 @@ impl<K, V, S> HashMap<K, V, S> /// use std::collections::hash_map::RandomState; /// /// let hasher = RandomState::new(); - /// let map: HashMap<isize, isize> = HashMap::with_hasher(hasher); + /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher); /// let hasher: &RandomState = map.hasher(); /// ``` #[stable(feature = "hashmap_public_hasher", since = "1.9.0")] @@ -741,7 +748,7 @@ impl<K, V, S> HashMap<K, V, S> /// /// ``` /// use std::collections::HashMap; - /// let map: HashMap<isize, isize> = HashMap::with_capacity(100); + /// let map: HashMap<i32, i32> = HashMap::with_capacity(100); /// assert!(map.capacity() >= 100); /// ``` #[inline] @@ -770,22 +777,50 @@ impl<K, V, S> HashMap<K, V, S> /// /// ``` /// use std::collections::HashMap; - /// let mut map: HashMap<&str, isize> = HashMap::new(); + /// let mut map: HashMap<&str, i32> = HashMap::new(); /// map.reserve(10); /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn reserve(&mut self, additional: usize) { + match self.try_reserve(additional) { + Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"), + Err(CollectionAllocErr::AllocErr) => Global.oom(), + Ok(()) => { /* yay */ } + } + } + + /// Tries to reserve capacity for at least `additional` more elements to be inserted + /// in the given `HashMap<K,V>`. The collection may reserve more space to avoid + /// frequent reallocations. + /// + /// # Errors + /// + /// If the capacity overflows, or the allocator reports a failure, then an error + /// is returned. + /// + /// # Examples + /// + /// ``` + /// #![feature(try_reserve)] + /// use std::collections::HashMap; + /// let mut map: HashMap<&str, isize> = HashMap::new(); + /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?"); + /// ``` + #[unstable(feature = "try_reserve", reason = "new API", issue="48043")] + pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> { let remaining = self.capacity() - self.len(); // this can't overflow if remaining < additional { - let min_cap = self.len().checked_add(additional).expect("reserve overflow"); - let raw_cap = self.resize_policy.raw_capacity(min_cap); - self.resize(raw_cap); + let min_cap = self.len().checked_add(additional) + .ok_or(CollectionAllocErr::CapacityOverflow)?; + let raw_cap = self.resize_policy.try_raw_capacity(min_cap)?; + self.try_resize(raw_cap)?; } else if self.table.tag() && remaining <= self.len() { // Probe sequence is too long and table is half full, // resize early to reduce probing length. let new_capacity = self.table.capacity() * 2; - self.resize(new_capacity); + self.try_resize(new_capacity)?; } + Ok(()) } /// Resizes the internal vectors to a new capacity. It's your @@ -795,15 +830,15 @@ impl<K, V, S> HashMap<K, V, S> /// 2) Ensure `new_raw_cap` is a power of two or zero. #[inline(never)] #[cold] - fn resize(&mut self, new_raw_cap: usize) { + fn try_resize(&mut self, new_raw_cap: usize) -> Result<(), CollectionAllocErr> { assert!(self.table.size() <= new_raw_cap); assert!(new_raw_cap.is_power_of_two() || new_raw_cap == 0); - let mut old_table = replace(&mut self.table, RawTable::new(new_raw_cap)); + let mut old_table = replace(&mut self.table, RawTable::try_new(new_raw_cap)?); let old_size = old_table.size(); if old_table.size() == 0 { - return; + return Ok(()); } let mut bucket = Bucket::head_bucket(&mut old_table); @@ -838,6 +873,7 @@ impl<K, V, S> HashMap<K, V, S> } assert_eq!(self.table.size(), old_size); + Ok(()) } /// Shrinks the capacity of the map as much as possible. It will drop @@ -849,7 +885,7 @@ impl<K, V, S> HashMap<K, V, S> /// ``` /// use std::collections::HashMap; /// - /// let mut map: HashMap<isize, isize> = HashMap::with_capacity(100); + /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100); /// map.insert(1, 2); /// map.insert(3, 4); /// assert!(map.capacity() >= 100); @@ -872,6 +908,46 @@ impl<K, V, S> HashMap<K, V, S> } } + /// Shrinks the capacity of the map with a lower limit. It will drop + /// down no lower than the supplied limit while maintaining the internal rules + /// and possibly leaving some space in accordance with the resize policy. + /// + /// Panics if the current capacity is smaller than the supplied + /// minimum capacity. + /// + /// # Examples + /// + /// ``` + /// #![feature(shrink_to)] + /// use std::collections::HashMap; + /// + /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100); + /// map.insert(1, 2); + /// map.insert(3, 4); + /// assert!(map.capacity() >= 100); + /// map.shrink_to(10); + /// assert!(map.capacity() >= 10); + /// map.shrink_to(0); + /// assert!(map.capacity() >= 2); + /// ``` + #[unstable(feature = "shrink_to", reason = "new API", issue="0")] + pub fn shrink_to(&mut self, min_capacity: usize) { + assert!(self.capacity() >= min_capacity, "Tried to shrink to a larger capacity"); + + let new_raw_cap = self.resize_policy.raw_capacity(max(self.len(), min_capacity)); + if self.raw_capacity() != new_raw_cap { + let old_table = replace(&mut self.table, RawTable::new(new_raw_cap)); + let old_size = old_table.size(); + + // Shrink the table. Naive algorithm for resizing: + for (h, k, v) in old_table.into_iter() { + self.insert_hashed_nocheck(h, k, v); + } + + debug_assert_eq!(self.table.size(), old_size); + } + } + /// Insert a pre-hashed key-value pair, without first checking /// that there's enough room in the buckets. Returns a reference to the /// newly insert value. @@ -1146,6 +1222,34 @@ impl<K, V, S> HashMap<K, V, S> self.search(k).map(|bucket| bucket.into_refs().1) } + /// Returns the key-value pair corresponding to the supplied key. + /// + /// The supplied key may be any borrowed form of the map's key type, but + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for + /// the key type. + /// + /// [`Eq`]: ../../std/cmp/trait.Eq.html + /// [`Hash`]: ../../std/hash/trait.Hash.html + /// + /// # Examples + /// + /// ``` + /// #![feature(map_get_key_value)] + /// use std::collections::HashMap; + /// + /// let mut map = HashMap::new(); + /// map.insert(1, "a"); + /// assert_eq!(map.get_key_value(&1), Some((&1, &"a"))); + /// assert_eq!(map.get_key_value(&2), None); + /// ``` + #[unstable(feature = "map_get_key_value", issue = "49347")] + pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> + where K: Borrow<Q>, + Q: Hash + Eq + { + self.search(k).map(|bucket| bucket.into_refs()) + } + /// Returns true if the map contains a value for the specified key. /// /// The key may be any borrowed form of the map's key type, but @@ -1306,7 +1410,7 @@ impl<K, V, S> HashMap<K, V, S> /// ``` /// use std::collections::HashMap; /// - /// let mut map: HashMap<isize, isize> = (0..8).map(|x|(x, x*10)).collect(); + /// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect(); /// map.retain(|&k, _| k % 2 == 0); /// assert_eq!(map.len(), 4); /// ``` @@ -1722,7 +1826,7 @@ impl<K, V, S> IntoIterator for HashMap<K, V, S> /// map.insert("c", 3); /// /// // Not possible with .iter() - /// let vec: Vec<(&str, isize)> = map.into_iter().collect(); + /// let vec: Vec<(&str, i32)> = map.into_iter().collect(); /// ``` fn into_iter(self) -> IntoIter<K, V> { IntoIter { inner: self.table.into_iter() } @@ -1750,7 +1854,7 @@ impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<'a, K, V> FusedIterator for Iter<'a, K, V> {} #[stable(feature = "rust1", since = "1.0.0")] @@ -1773,7 +1877,7 @@ impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { self.inner.len() } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {} #[stable(feature = "std_debug", since = "1.16.0")] @@ -1808,7 +1912,7 @@ impl<K, V> ExactSizeIterator for IntoIter<K, V> { self.inner.len() } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<K, V> FusedIterator for IntoIter<K, V> {} #[stable(feature = "std_debug", since = "1.16.0")] @@ -1840,7 +1944,7 @@ impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> { self.inner.len() } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<'a, K, V> FusedIterator for Keys<'a, K, V> {} #[stable(feature = "rust1", since = "1.0.0")] @@ -1863,7 +1967,7 @@ impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> { self.inner.len() } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<'a, K, V> FusedIterator for Values<'a, K, V> {} #[stable(feature = "map_values_mut", since = "1.10.0")] @@ -1886,7 +1990,7 @@ impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> { self.inner.len() } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {} #[stable(feature = "std_debug", since = "1.16.0")] @@ -1921,7 +2025,7 @@ impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> { self.inner.len() } } -#[unstable(feature = "fused", issue = "35602")] +#[stable(feature = "fused", since = "1.26.0")] impl<'a, K, V> FusedIterator for Drain<'a, K, V> {} #[stable(feature = "std_debug", since = "1.16.0")] @@ -1936,80 +2040,6 @@ impl<'a, K, V> fmt::Debug for Drain<'a, K, V> } } -/// A place for insertion to a `Entry`. -/// -/// See [`HashMap::entry`](struct.HashMap.html#method.entry) for details. -#[must_use = "places do nothing unless written to with `<-` syntax"] -#[unstable(feature = "collection_placement", - reason = "struct name and placement protocol is subject to change", - issue = "30172")] -pub struct EntryPlace<'a, K: 'a, V: 'a> { - bucket: FullBucketMut<'a, K, V>, -} - -#[unstable(feature = "collection_placement", - reason = "struct name and placement protocol is subject to change", - issue = "30172")] -impl<'a, K: 'a + Debug, V: 'a + Debug> Debug for EntryPlace<'a, K, V> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - f.debug_struct("EntryPlace") - .field("key", self.bucket.read().0) - .field("value", self.bucket.read().1) - .finish() - } -} - -#[unstable(feature = "collection_placement", - reason = "struct name and placement protocol is subject to change", - issue = "30172")] -impl<'a, K, V> Drop for EntryPlace<'a, K, V> { - fn drop(&mut self) { - // Inplacement insertion failed. Only key need to drop. - // The value is failed to insert into map. - unsafe { self.bucket.remove_key() }; - } -} - -#[unstable(feature = "collection_placement", - reason = "placement protocol is subject to change", - issue = "30172")] -impl<'a, K, V> Placer<V> for Entry<'a, K, V> { - type Place = EntryPlace<'a, K, V>; - - fn make_place(self) -> EntryPlace<'a, K, V> { - let b = match self { - Occupied(mut o) => { - unsafe { ptr::drop_in_place(o.elem.read_mut().1); } - o.elem - } - Vacant(v) => { - unsafe { v.insert_key() } - } - }; - EntryPlace { bucket: b } - } -} - -#[unstable(feature = "collection_placement", - reason = "placement protocol is subject to change", - issue = "30172")] -unsafe impl<'a, K, V> Place<V> for EntryPlace<'a, K, V> { - fn pointer(&mut self) -> *mut V { - self.bucket.read_mut().1 - } -} - -#[unstable(feature = "collection_placement", - reason = "placement protocol is subject to change", - issue = "30172")] -impl<'a, K, V> InPlace<V> for EntryPlace<'a, K, V> { - type Owner = (); - - unsafe fn finalize(self) { - mem::forget(self); - } -} - impl<'a, K, 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 @@ -2082,7 +2112,6 @@ impl<'a, K, V> Entry<'a, K, V> { /// # Examples /// /// ``` - /// #![feature(entry_and_modify)] /// use std::collections::HashMap; /// /// let mut map: HashMap<&str, u32> = HashMap::new(); @@ -2097,7 +2126,7 @@ impl<'a, K, V> Entry<'a, K, V> { /// .or_insert(42); /// assert_eq!(map["poneyland"], 43); /// ``` - #[unstable(feature = "entry_and_modify", issue = "44733")] + #[stable(feature = "entry_and_modify", since = "1.26.0")] pub fn and_modify<F>(self, mut f: F) -> Self where F: FnMut(&mut V) { @@ -2433,26 +2462,6 @@ impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> { }; b.into_mut_refs().1 } - - // Only used for InPlacement insert. Avoid unnecessary value copy. - // The value remains uninitialized. - unsafe fn insert_key(self) -> FullBucketMut<'a, K, V> { - match self.elem { - NeqElem(mut bucket, disp) => { - if disp >= DISPLACEMENT_THRESHOLD { - bucket.table_mut().set_tag(true); - } - let uninit = mem::uninitialized(); - robin_hood(bucket, disp, self.hash, self.key, uninit) - }, - NoElem(mut bucket, disp) => { - if disp >= DISPLACEMENT_THRESHOLD { - bucket.table_mut().set_tag(true); - } - bucket.put_key(self.hash, self.key) - }, - } - } } #[stable(feature = "rust1", since = "1.0.0")] @@ -2717,7 +2726,9 @@ mod test_map { use super::RandomState; use cell::RefCell; use rand::{thread_rng, Rng}; - use panic; + use realstd::collections::CollectionAllocErr::*; + use realstd::mem::size_of; + use realstd::usize; #[test] fn test_zero_capacities() { @@ -2787,24 +2798,24 @@ mod test_map { assert_eq!(m2.len(), 2); } - thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) } + thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) } #[derive(Hash, PartialEq, Eq)] - struct Dropable { + struct Droppable { k: usize, } - impl Dropable { - fn new(k: usize) -> Dropable { + impl Droppable { + fn new(k: usize) -> Droppable { DROP_VECTOR.with(|slot| { slot.borrow_mut()[k] += 1; }); - Dropable { k: k } + Droppable { k: k } } } - impl Drop for Dropable { + impl Drop for Droppable { fn drop(&mut self) { DROP_VECTOR.with(|slot| { slot.borrow_mut()[self.k] -= 1; @@ -2812,9 +2823,9 @@ mod test_map { } } - impl Clone for Dropable { - fn clone(&self) -> Dropable { - Dropable::new(self.k) + impl Clone for Droppable { + fn clone(&self) -> Droppable { + Droppable::new(self.k) } } @@ -2834,8 +2845,8 @@ mod test_map { }); for i in 0..100 { - let d1 = Dropable::new(i); - let d2 = Dropable::new(i + 100); + let d1 = Droppable::new(i); + let d2 = Droppable::new(i + 100); m.insert(d1, d2); } @@ -2846,7 +2857,7 @@ mod test_map { }); for i in 0..50 { - let k = Dropable::new(i); + let k = Droppable::new(i); let v = m.remove(&k); assert!(v.is_some()); @@ -2893,8 +2904,8 @@ mod test_map { }); for i in 0..100 { - let d1 = Dropable::new(i); - let d2 = Dropable::new(i + 100); + let d1 = Droppable::new(i); + let d2 = Droppable::new(i + 100); hm.insert(d1, d2); } @@ -2944,13 +2955,13 @@ mod test_map { #[test] fn test_empty_remove() { - let mut m: HashMap<isize, bool> = HashMap::new(); + let mut m: HashMap<i32, bool> = HashMap::new(); assert_eq!(m.remove(&0), None); } #[test] fn test_empty_entry() { - let mut m: HashMap<isize, bool> = HashMap::new(); + let mut m: HashMap<i32, bool> = HashMap::new(); match m.entry(0) { Occupied(_) => panic!(), Vacant(_) => {} @@ -2961,7 +2972,7 @@ mod test_map { #[test] fn test_empty_iter() { - let mut m: HashMap<isize, bool> = HashMap::new(); + let mut m: HashMap<i32, bool> = HashMap::new(); assert_eq!(m.drain().next(), None); assert_eq!(m.keys().next(), None); assert_eq!(m.values().next(), None); @@ -3462,7 +3473,7 @@ mod test_map { fn test_entry_take_doesnt_corrupt() { #![allow(deprecated)] //rand // Test for #19292 - fn check(m: &HashMap<isize, ()>) { + fn check(m: &HashMap<i32, ()>) { for k in m.keys() { assert!(m.contains_key(k), "{} is in keys() but not in the map?", k); @@ -3571,7 +3582,7 @@ mod test_map { #[test] fn test_retain() { - let mut map: HashMap<isize, isize> = (0..100).map(|x|(x, x*10)).collect(); + let mut map: HashMap<i32, i32> = (0..100).map(|x|(x, x*10)).collect(); map.retain(|&k, _| k % 2 == 0); assert_eq!(map.len(), 50); @@ -3601,55 +3612,31 @@ mod test_map { } #[test] - fn test_placement_in() { - let mut map = HashMap::new(); - map.extend((0..10).map(|i| (i, i))); - - map.entry(100) <- 100; - assert_eq!(map[&100], 100); + fn test_try_reserve() { - map.entry(0) <- 10; - assert_eq!(map[&0], 10); - - assert_eq!(map.len(), 11); - } - - #[test] - fn test_placement_panic() { - let mut map = HashMap::new(); - map.extend((0..10).map(|i| (i, i))); + let mut empty_bytes: HashMap<u8,u8> = HashMap::new(); - fn mkpanic() -> usize { panic!() } + const MAX_USIZE: usize = usize::MAX; - // modify existing key - // when panic happens, previous key is removed. - let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { map.entry(0) <- mkpanic(); })); - assert_eq!(map.len(), 9); - assert!(!map.contains_key(&0)); + // HashMap and RawTables use complicated size calculations + // hashes_size is sizeof(HashUint) * capacity; + // pairs_size is sizeof((K. V)) * capacity; + // alignment_hashes_size is 8 + // alignment_pairs size is 4 + let size_of_multiplier = (size_of::<usize>() + size_of::<(u8, u8)>()).next_power_of_two(); + // The following formula is used to calculate the new capacity + let max_no_ovf = ((MAX_USIZE / 11) * 10) / size_of_multiplier - 1; - // add new key - let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { map.entry(100) <- mkpanic(); })); - assert_eq!(map.len(), 9); - assert!(!map.contains_key(&100)); - } + if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) { + } else { panic!("usize::MAX should trigger an overflow!"); } - #[test] - fn test_placement_drop() { - // correctly drop - struct TestV<'a>(&'a mut bool); - impl<'a> Drop for TestV<'a> { - fn drop(&mut self) { - if !*self.0 { panic!("value double drop!"); } // no double drop - *self.0 = false; - } + if size_of::<usize>() < 8 { + if let Err(CapacityOverflow) = empty_bytes.try_reserve(max_no_ovf) { + } else { panic!("isize::MAX + 1 should trigger a CapacityOverflow!") } + } else { + if let Err(AllocErr) = empty_bytes.try_reserve(max_no_ovf) { + } else { panic!("isize::MAX + 1 should trigger an OOM!") } } - - fn makepanic<'a>() -> TestV<'a> { panic!() } - - let mut can_drop = true; - let mut hm = HashMap::new(); - hm.insert(0, TestV(&mut can_drop)); - let _ = panic::catch_unwind(panic::AssertUnwindSafe(|| { hm.entry(0) <- makepanic(); })); - assert_eq!(hm.len(), 0); } + } |