diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/collections/hash/bench.rs | 6 | ||||
| -rw-r--r-- | src/libstd/collections/hash/map.rs | 448 | ||||
| -rw-r--r-- | src/libstd/collections/hash/set.rs | 235 | ||||
| -rw-r--r-- | src/libstd/collections/hash/table.rs | 28 |
4 files changed, 438 insertions, 279 deletions
diff --git a/src/libstd/collections/hash/bench.rs b/src/libstd/collections/hash/bench.rs index a1275d23d57..ff6cb7985a4 100644 --- a/src/libstd/collections/hash/bench.rs +++ b/src/libstd/collections/hash/bench.rs @@ -15,17 +15,17 @@ extern crate test; use self::test::Bencher; #[bench] -fn new_drop(b : &mut Bencher) { +fn new_drop(b: &mut Bencher) { use super::map::HashMap; b.iter(|| { - let m : HashMap<i32, i32> = HashMap::new(); + let m: HashMap<i32, i32> = HashMap::new(); assert_eq!(m.len(), 0); }) } #[bench] -fn new_insert_drop(b : &mut Bencher) { +fn new_insert_drop(b: &mut Bencher) { use super::map::HashMap; b.iter(|| { diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index 3dfae976bfa..fb8a0c3c265 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -21,19 +21,8 @@ use mem::{self, replace}; use ops::{Deref, Index}; use rand::{self, Rng}; -use super::table::{ - self, - Bucket, - EmptyBucket, - FullBucket, - FullBucketMut, - RawTable, - SafeHash -}; -use super::table::BucketState::{ - Empty, - Full, -}; +use super::table::{self, Bucket, EmptyBucket, FullBucket, FullBucketMut, RawTable, SafeHash}; +use super::table::BucketState::{Empty, Full}; const MIN_NONZERO_RAW_CAPACITY: usize = 32; // must be a power of two @@ -370,12 +359,9 @@ pub struct HashMap<K, V, S = RandomState> { /// Search for a pre-hashed key. #[inline] -fn search_hashed<K, V, M, F>(table: M, - hash: SafeHash, - mut is_match: F) - -> InternalEntry<K, V, M> where - M: Deref<Target=RawTable<K, V>>, - F: FnMut(&K) -> bool, +fn search_hashed<K, V, M, F>(table: M, hash: SafeHash, mut is_match: F) -> InternalEntry<K, V, M> + where M: Deref<Target = RawTable<K, V>>, + F: FnMut(&K) -> bool { // This is the only function where capacity can be zero. To avoid // undefined behavior when Bucket::new gets the raw bucket in this @@ -397,7 +383,7 @@ fn search_hashed<K, V, M, F>(table: M, elem: NoElem(bucket), }; } - Full(bucket) => bucket + Full(bucket) => bucket, }; let robin_ib = full.index() as isize - full.displacement() as isize; @@ -416,9 +402,7 @@ fn search_hashed<K, V, M, F>(table: M, if hash == full.hash() { // If the key doesn't match, it can't be this one.. if is_match(full.read().0) { - return InternalEntry::Occupied { - elem: full - }; + return InternalEntry::Occupied { elem: full }; } } @@ -431,13 +415,13 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) { let (empty, retkey, retval) = starting_bucket.take(); let mut gap = match empty.gap_peek() { Some(b) => b, - None => return (retkey, retval) + None => return (retkey, retval), }; while gap.full().displacement() != 0 { gap = match gap.shift() { Some(b) => b, - None => break + None => break, }; } @@ -451,11 +435,11 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) { /// /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable. fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>, - mut ib: usize, - mut hash: SafeHash, - mut key: K, - mut val: V) - -> &'a mut V { + mut ib: usize, + mut hash: SafeHash, + mut key: K, + mut val: V) + -> &'a mut V { let starting_index = bucket.index(); let size = bucket.table().size(); // Save the *starting point*. @@ -487,8 +471,8 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>, // FullBucketMut, into just one FullBucketMut. The "table" // refers to the inner FullBucketMut in this context. return bucket.into_table().into_mut_refs().1; - }, - Full(bucket) => bucket + } + Full(bucket) => bucket, }; let probe_ib = full_bucket.index() - full_bucket.displacement(); @@ -505,9 +489,12 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>, } impl<K, V, S> HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + where K: Eq + Hash, + S: BuildHasher { - fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash where X: Hash { + fn make_hash<X: ?Sized>(&self, x: &X) -> SafeHash + where X: Hash + { table::make_hash(&self.hash_builder, x) } @@ -516,7 +503,8 @@ impl<K, V, S> HashMap<K, V, S> /// search_hashed. #[inline] fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> InternalEntry<K, V, &'a RawTable<K, V>> - where K: Borrow<Q>, Q: Eq + Hash + where K: Borrow<Q>, + Q: Eq + Hash { let hash = self.make_hash(q); search_hashed(&self.table, hash, |k| q.eq(k.borrow())) @@ -524,7 +512,8 @@ impl<K, V, S> HashMap<K, V, S> #[inline] fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> InternalEntry<K, V, &'a mut RawTable<K, V>> - where K: Borrow<Q>, Q: Eq + Hash + where K: Borrow<Q>, + Q: Eq + Hash { let hash = self.make_hash(q); search_hashed(&mut self.table, hash, |k| q.eq(k.borrow())) @@ -544,7 +533,7 @@ impl<K, V, S> HashMap<K, V, S> empty.put(hash, k, v); return; } - Full(b) => b.into_bucket() + Full(b) => b.into_bucket(), }; buckets.next(); } @@ -586,7 +575,8 @@ impl<K: Hash + Eq, V> HashMap<K, V, RandomState> { } impl<K, V, S> HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + where K: Eq + Hash, + S: BuildHasher { /// Creates an empty `HashMap` which will use the given hash builder to hash /// keys. @@ -640,8 +630,7 @@ impl<K, V, S> HashMap<K, V, S> /// ``` #[inline] #[stable(feature = "hashmap_build_hasher", since = "1.7.0")] - pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) - -> HashMap<K, V, S> { + pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashMap<K, V, S> { let resize_policy = DefaultResizePolicy::new(); let raw_cap = resize_policy.raw_capacity(capacity); HashMap { @@ -779,7 +768,7 @@ impl<K, V, S> HashMap<K, V, S> } b.into_bucket() } - Empty(b) => b.into_bucket() + Empty(b) => b.into_bucket(), }; bucket.next(); } @@ -828,16 +817,12 @@ impl<K, V, S> HashMap<K, V, S> fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> Option<V> { let entry = search_hashed(&mut self.table, hash, |key| *key == k).into_entry(k); match entry { - Some(Occupied(mut elem)) => { - Some(elem.insert(v)) - } + Some(Occupied(mut elem)) => Some(elem.insert(v)), Some(Vacant(elem)) => { elem.insert(v); None } - None => { - unreachable!() - } + None => unreachable!(), } } @@ -1001,7 +986,9 @@ impl<K, V, S> HashMap<K, V, S> /// assert_eq!(a.len(), 1); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { self.table.size() } + pub fn len(&self) -> usize { + self.table.size() + } /// Returns true if the map contains no elements. /// @@ -1017,7 +1004,9 @@ impl<K, V, S> HashMap<K, V, S> /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { self.len() == 0 } + pub fn is_empty(&self) -> bool { + self.len() == 0 + } /// Clears the map, returning all key-value pairs as an iterator. Keeps the /// allocated memory for reuse. @@ -1041,9 +1030,7 @@ impl<K, V, S> HashMap<K, V, S> #[inline] #[stable(feature = "drain", since = "1.6.0")] pub fn drain(&mut self) -> Drain<K, V> { - Drain { - inner: self.table.drain(), - } + Drain { inner: self.table.drain() } } /// Clears the map, removing all key-value pairs. Keeps the allocated memory @@ -1086,7 +1073,8 @@ impl<K, V, S> HashMap<K, V, S> /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> - where K: Borrow<Q>, Q: Hash + Eq + where K: Borrow<Q>, + Q: Hash + Eq { self.search(k).into_occupied_bucket().map(|bucket| bucket.into_refs().1) } @@ -1112,7 +1100,8 @@ impl<K, V, S> HashMap<K, V, S> /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool - where K: Borrow<Q>, Q: Hash + Eq + where K: Borrow<Q>, + Q: Hash + Eq { self.search(k).into_occupied_bucket().is_some() } @@ -1140,7 +1129,8 @@ impl<K, V, S> HashMap<K, V, S> /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> - where K: Borrow<Q>, Q: Hash + Eq + where K: Borrow<Q>, + Q: Hash + Eq { self.search_mut(k).into_occupied_bucket().map(|bucket| bucket.into_mut_refs().1) } @@ -1198,10 +1188,11 @@ impl<K, V, S> HashMap<K, V, S> /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> - where K: Borrow<Q>, Q: Hash + Eq + where K: Borrow<Q>, + Q: Hash + Eq { if self.table.size() == 0 { - return None + return None; } self.search_mut(k).into_occupied_bucket().map(|bucket| pop_internal(bucket).1) @@ -1210,25 +1201,32 @@ impl<K, V, S> HashMap<K, V, S> #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> PartialEq for HashMap<K, V, S> - where K: Eq + Hash, V: PartialEq, S: BuildHasher + where K: Eq + Hash, + V: PartialEq, + S: BuildHasher { fn eq(&self, other: &HashMap<K, V, S>) -> bool { - if self.len() != other.len() { return false; } + if self.len() != other.len() { + return false; + } - self.iter().all(|(key, value)| - other.get(key).map_or(false, |v| *value == *v) - ) + self.iter().all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) } } #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> Eq for HashMap<K, V, S> - where K: Eq + Hash, V: Eq, S: BuildHasher -{} + where K: Eq + Hash, + V: Eq, + S: BuildHasher +{ +} #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> Debug for HashMap<K, V, S> - where K: Eq + Hash + Debug, V: Debug, S: BuildHasher + where K: Eq + Hash + Debug, + V: Debug, + S: BuildHasher { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { f.debug_map().entries(self.iter()).finish() @@ -1238,7 +1236,7 @@ impl<K, V, S> Debug for HashMap<K, V, S> #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> Default for HashMap<K, V, S> where K: Eq + Hash, - S: BuildHasher + Default, + S: BuildHasher + Default { /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher. fn default() -> HashMap<K, V, S> { @@ -1250,7 +1248,7 @@ impl<K, V, S> Default for HashMap<K, V, S> impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S> where K: Eq + Hash + Borrow<Q>, Q: Eq + Hash, - S: BuildHasher, + S: BuildHasher { type Output = V; @@ -1263,79 +1261,71 @@ impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S> /// HashMap iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, K: 'a, V: 'a> { - inner: table::Iter<'a, K, V> + inner: table::Iter<'a, K, V>, } // FIXME(#19839) Remove in favor of `#[derive(Clone)]` #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> Clone for Iter<'a, K, V> { fn clone(&self) -> Iter<'a, K, V> { - Iter { - inner: self.inner.clone() - } + Iter { inner: self.inner.clone() } } } /// HashMap mutable values iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct IterMut<'a, K: 'a, V: 'a> { - inner: table::IterMut<'a, K, V> + inner: table::IterMut<'a, K, V>, } /// HashMap move iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<K, V> { - inner: table::IntoIter<K, V> + inner: table::IntoIter<K, V>, } /// HashMap keys iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct Keys<'a, K: 'a, V: 'a> { - inner: Iter<'a, K, V> + inner: Iter<'a, K, V>, } // FIXME(#19839) Remove in favor of `#[derive(Clone)]` #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> Clone for Keys<'a, K, V> { fn clone(&self) -> Keys<'a, K, V> { - Keys { - inner: self.inner.clone() - } + Keys { inner: self.inner.clone() } } } /// HashMap values iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct Values<'a, K: 'a, V: 'a> { - inner: Iter<'a, K, V> + inner: Iter<'a, K, V>, } // FIXME(#19839) Remove in favor of `#[derive(Clone)]` #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> Clone for Values<'a, K, V> { fn clone(&self) -> Values<'a, K, V> { - Values { - inner: self.inner.clone() - } + Values { inner: self.inner.clone() } } } /// HashMap drain iterator. #[stable(feature = "drain", since = "1.6.0")] pub struct Drain<'a, K: 'a, V: 'a> { - inner: table::Drain<'a, K, V> + inner: table::Drain<'a, K, V>, } /// Mutable HashMap values iterator. #[stable(feature = "map_values_mut", since = "1.10.0")] pub struct ValuesMut<'a, K: 'a, V: 'a> { - inner: IterMut<'a, K, V> + inner: IterMut<'a, K, V>, } enum InternalEntry<K, V, M> { - Occupied { - elem: FullBucket<K, V, M>, - }, + Occupied { elem: FullBucket<K, V, M> }, Vacant { hash: SafeHash, elem: VacantEntryState<K, V, M>, @@ -1360,7 +1350,7 @@ impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> { InternalEntry::Occupied { elem } => { Some(Occupied(OccupiedEntry { key: Some(key), - elem: elem + elem: elem, })) } InternalEntry::Vacant { hash, elem } => { @@ -1370,7 +1360,7 @@ impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> { elem: elem, })) } - InternalEntry::TableIsEmpty => None + InternalEntry::TableIsEmpty => None, } } } @@ -1384,27 +1374,29 @@ impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> { pub enum Entry<'a, K: 'a, V: 'a> { /// An occupied Entry. #[stable(feature = "rust1", since = "1.0.0")] - Occupied( - #[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V> - ), + Occupied(#[stable(feature = "rust1", since = "1.0.0")] + OccupiedEntry<'a, K, V>), /// A vacant Entry. #[stable(feature = "rust1", since = "1.0.0")] - Vacant( - #[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V> - ), + Vacant(#[stable(feature = "rust1", since = "1.0.0")] + VacantEntry<'a, K, V>), } #[stable(feature= "debug_hash_map", since = "1.12.0")] impl<'a, K: 'a + Debug, V: 'a + Debug> Debug for Entry<'a, K, V> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match *self { - Vacant(ref v) => f.debug_tuple("Entry") - .field(v) - .finish(), - Occupied(ref o) => f.debug_tuple("Entry") - .field(o) - .finish(), + Vacant(ref v) => { + f.debug_tuple("Entry") + .field(v) + .finish() + } + Occupied(ref o) => { + f.debug_tuple("Entry") + .field(o) + .finish() + } } } } @@ -1423,9 +1415,9 @@ pub struct OccupiedEntry<'a, K: 'a, V: 'a> { impl<'a, K: 'a + Debug, V: 'a + Debug> Debug for OccupiedEntry<'a, K, V> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { f.debug_struct("OccupiedEntry") - .field("key", self.key()) - .field("value", self.get()) - .finish() + .field("key", self.key()) + .field("value", self.get()) + .finish() } } @@ -1444,8 +1436,8 @@ pub struct VacantEntry<'a, K: 'a, V: 'a> { impl<'a, K: 'a + Debug, V: 'a> Debug for VacantEntry<'a, K, V> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { f.debug_tuple("VacantEntry") - .field(self.key()) - .finish() + .field(self.key()) + .finish() } } @@ -1460,7 +1452,8 @@ enum VacantEntryState<K, V, M> { #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + where K: Eq + Hash, + S: BuildHasher { type Item = (&'a K, &'a V); type IntoIter = Iter<'a, K, V>; @@ -1472,7 +1465,8 @@ impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + where K: Eq + Hash, + S: BuildHasher { type Item = (&'a K, &'a mut V); type IntoIter = IterMut<'a, K, V>; @@ -1484,7 +1478,8 @@ impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> IntoIterator for HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + where K: Eq + Hash, + S: BuildHasher { type Item = (K, V); type IntoIter = IntoIter<K, V>; @@ -1507,9 +1502,7 @@ impl<K, V, S> IntoIterator for HashMap<K, V, S> /// let vec: Vec<(&str, isize)> = map.into_iter().collect(); /// ``` fn into_iter(self) -> IntoIter<K, V> { - IntoIter { - inner: self.table.into_iter() - } + IntoIter { inner: self.table.into_iter() } } } @@ -1517,12 +1510,21 @@ impl<K, V, S> IntoIterator for HashMap<K, V, S> impl<'a, K, V> Iterator for Iter<'a, K, V> { type Item = (&'a K, &'a V); - #[inline] fn next(&mut self) -> Option<(&'a K, &'a V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(&'a K, &'a V)> { + self.inner.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] @@ -1532,12 +1534,21 @@ impl<'a, K, V> FusedIterator for Iter<'a, K, V> {} impl<'a, K, V> Iterator for IterMut<'a, K, V> { type Item = (&'a K, &'a mut V); - #[inline] fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.inner.next() } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(&'a K, &'a mut V)> { + self.inner.next() + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {} @@ -1546,12 +1557,21 @@ impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {} impl<K, V> Iterator for IntoIter<K, V> { type Item = (K, V); - #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(K, V)> { + self.inner.next().map(|(_, k, v)| (k, v)) + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<K, V> ExactSizeIterator for IntoIter<K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<K, V> FusedIterator for IntoIter<K, V> {} @@ -1560,12 +1580,21 @@ impl<K, V> FusedIterator for IntoIter<K, V> {} impl<'a, K, V> Iterator for Keys<'a, K, V> { type Item = &'a K; - #[inline] fn next(&mut self) -> Option<(&'a K)> { self.inner.next().map(|(k, _)| k) } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(&'a K)> { + self.inner.next().map(|(k, _)| k) + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K, V> FusedIterator for Keys<'a, K, V> {} @@ -1574,12 +1603,21 @@ impl<'a, K, V> FusedIterator for Keys<'a, K, V> {} impl<'a, K, V> Iterator for Values<'a, K, V> { type Item = &'a V; - #[inline] fn next(&mut self) -> Option<(&'a V)> { self.inner.next().map(|(_, v)| v) } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(&'a V)> { + self.inner.next().map(|(_, v)| v) + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K, V> FusedIterator for Values<'a, K, V> {} @@ -1588,12 +1626,21 @@ impl<'a, K, V> FusedIterator for Values<'a, K, V> {} impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { type Item = &'a mut V; - #[inline] fn next(&mut self) -> Option<(&'a mut V)> { self.inner.next().map(|(_, v)| v) } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(&'a mut V)> { + self.inner.next().map(|(_, v)| v) + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {} @@ -1602,12 +1649,21 @@ impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {} impl<'a, K, V> Iterator for Drain<'a, K, V> { type Item = (K, V); - #[inline] fn next(&mut self) -> Option<(K, V)> { self.inner.next().map(|(_, k, v)| (k, v)) } - #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() } + #[inline] + fn next(&mut self) -> Option<(K, V)> { + self.inner.next().map(|(_, k, v)| (k, v)) + } + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + self.inner.size_hint() + } } #[stable(feature = "drain", since = "1.6.0")] impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> { - #[inline] fn len(&self) -> usize { self.inner.len() } + #[inline] + fn len(&self) -> usize { + self.inner.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K, V> FusedIterator for Drain<'a, K, V> {} @@ -1902,21 +1958,18 @@ impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> { #[stable(feature = "rust1", since = "1.0.0")] pub fn insert(self, value: V) -> &'a mut V { match self.elem { - NeqElem(bucket, ib) => { - robin_hood(bucket, ib, self.hash, self.key, value) - } - NoElem(bucket) => { - bucket.put(self.hash, self.key, value).into_mut_refs().1 - } + NeqElem(bucket, ib) => robin_hood(bucket, ib, self.hash, self.key, value), + NoElem(bucket) => bucket.put(self.hash, self.key, value).into_mut_refs().1, } } } #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + Default + where K: Eq + Hash, + S: BuildHasher + Default { - fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> HashMap<K, V, S> { + fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S> { let iterator = iter.into_iter(); let lower = iterator.size_hint().0; let mut map = HashMap::with_capacity_and_hasher(lower, Default::default()); @@ -1927,9 +1980,10 @@ impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> #[stable(feature = "rust1", since = "1.0.0")] impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S> - where K: Eq + Hash, S: BuildHasher + where K: Eq + Hash, + S: BuildHasher { - fn extend<T: IntoIterator<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); } @@ -1938,9 +1992,11 @@ impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S> #[stable(feature = "hash_extend_copy", since = "1.4.0")] impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S> - where K: Eq + Hash + Copy, V: Copy, S: BuildHasher + where K: Eq + Hash + Copy, + V: Copy, + S: BuildHasher { - fn extend<T: IntoIterator<Item=(&'a K, &'a V)>>(&mut self, iter: T) { + fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) { self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); } } @@ -1982,7 +2038,8 @@ impl RandomState { /// let s = RandomState::new(); /// ``` #[inline] - #[allow(deprecated)] // rand + #[allow(deprecated)] + // rand #[stable(feature = "hashmap_build_hasher", since = "1.7.0")] pub fn new() -> RandomState { // Historically this function did not cache keys from the OS and instead @@ -2009,9 +2066,7 @@ impl RandomState { (r.gen(), r.gen()) }); - KEYS.with(|&(k0, k1)| { - RandomState { k0: k0, k1: k1 } - }) + KEYS.with(|&(k0, k1)| RandomState { k0: k0, k1: k1 }) } } @@ -2080,7 +2135,9 @@ impl Default for RandomState { } impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S> - where K: Eq + Hash + Borrow<Q>, S: BuildHasher, Q: Eq + Hash + where K: Eq + Hash + Borrow<Q>, + S: BuildHasher, + Q: Eq + Hash { type Key = K; @@ -2090,7 +2147,7 @@ impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S> fn take(&mut self, key: &Q) -> Option<K> { if self.table.size() == 0 { - return None + return None; } self.search_mut(key).into_occupied_bucket().map(|bucket| pop_internal(bucket).0) @@ -2114,18 +2171,40 @@ impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S> #[allow(dead_code)] fn assert_covariance() { - fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> { v } - fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> { v } - fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> { v } - fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> { v } - fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> { v } - fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> { v } - fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> { v } - fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> { v } - fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> { v } - fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> { v } + fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> { + v + } + fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> { + v + } + fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> { + v + } + fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> { + v + } + fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> { + v + } + fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> { + v + } + fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> { + v + } + fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> { + v + } + fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> { + v + } + fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> { + v + } fn drain<'new>(d: Drain<'static, &'static str, &'static str>) - -> Drain<'new, &'new str, &'new str> { d } + -> Drain<'new, &'new str, &'new str> { + d + } } #[cfg(test)] @@ -2208,7 +2287,7 @@ mod test_map { #[derive(Hash, PartialEq, Eq)] struct Dropable { - k: usize + k: usize, } impl Dropable { @@ -2252,7 +2331,7 @@ mod test_map { for i in 0..100 { let d1 = Dropable::new(i); - let d2 = Dropable::new(i+100); + let d2 = Dropable::new(i + 100); m.insert(d1, d2); } @@ -2311,7 +2390,7 @@ mod test_map { for i in 0..100 { let d1 = Dropable::new(i); - let d2 = Dropable::new(i+100); + let d2 = Dropable::new(i + 100); hm.insert(d1, d2); } @@ -2339,13 +2418,13 @@ mod test_map { for _ in half.by_ref() {} DROP_VECTOR.with(|v| { - let nk = (0..100).filter(|&i| { - v.borrow()[i] == 1 - }).count(); + let nk = (0..100) + .filter(|&i| v.borrow()[i] == 1) + .count(); - let nv = (0..100).filter(|&i| { - v.borrow()[i+100] == 1 - }).count(); + let nv = (0..100) + .filter(|&i| v.borrow()[i + 100] == 1) + .count(); assert_eq!(nk, 50); assert_eq!(nv, 50); @@ -2402,12 +2481,12 @@ mod test_map { for i in 1..1001 { assert!(m.insert(i, i).is_none()); - for j in 1..i+1 { + for j in 1..i + 1 { let r = m.get(&j); assert_eq!(r, Some(&j)); } - for j in i+1..1001 { + for j in i + 1..1001 { let r = m.get(&j); assert_eq!(r, None); } @@ -2421,11 +2500,11 @@ mod test_map { for i in 1..1001 { assert!(m.remove(&i).is_some()); - for j in 1..i+1 { + for j in 1..i + 1 { assert!(!m.contains_key(&j)); } - for j in i+1..1001 { + for j in i + 1..1001 { assert!(m.contains_key(&j)); } } @@ -2461,7 +2540,8 @@ mod test_map { assert!(m.insert(5, 14).is_none()); let new = 100; match m.get_mut(&5) { - None => panic!(), Some(x) => *x = new + None => panic!(), + Some(x) => *x = new, } assert_eq!(m.get(&5), Some(&new)); } @@ -2580,7 +2660,7 @@ mod test_map { m.insert(1, 2); match m.get(&1) { None => panic!(), - Some(v) => assert_eq!(*v, 2) + Some(v) => assert_eq!(*v, 2), } } @@ -2743,7 +2823,7 @@ mod test_map { fn test_size_hint() { let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - let map: HashMap<_, _> = xs.iter().cloned().collect(); + let map: HashMap<_, _> = xs.iter().cloned().collect(); let mut iter = map.iter(); @@ -2756,7 +2836,7 @@ mod test_map { fn test_iter_len() { let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - let map: HashMap<_, _> = xs.iter().cloned().collect(); + let map: HashMap<_, _> = xs.iter().cloned().collect(); let mut iter = map.iter(); @@ -2769,7 +2849,7 @@ mod test_map { fn test_mut_size_hint() { let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - let mut map: HashMap<_, _> = xs.iter().cloned().collect(); + let mut map: HashMap<_, _> = xs.iter().cloned().collect(); let mut iter = map.iter_mut(); @@ -2782,7 +2862,7 @@ mod test_map { fn test_iter_mut_len() { let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; - let mut map: HashMap<_, _> = xs.iter().cloned().collect(); + let mut map: HashMap<_, _> = xs.iter().cloned().collect(); let mut iter = map.iter_mut(); @@ -2815,7 +2895,7 @@ mod test_map { } #[test] - fn test_entry(){ + fn test_entry() { let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; let mut map: HashMap<_, _> = xs.iter().cloned().collect(); @@ -2889,11 +2969,11 @@ mod test_map { for i in 0..1000 { let x = rng.gen_range(-10, 10); match m.entry(x) { - Vacant(_) => {}, + Vacant(_) => {} Occupied(e) => { println!("{}: remove {}", i, x); e.remove(); - }, + } } check(&m); @@ -2971,7 +3051,7 @@ mod test_map { Vacant(e) => { assert_eq!(key, *e.key()); e.insert(value.clone()); - }, + } } assert_eq!(a.len(), 1); assert_eq!(a[key], value); diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs index e5fe3c2f7c6..1ec7a4a7b63 100644 --- a/src/libstd/collections/hash/set.rs +++ b/src/libstd/collections/hash/set.rs @@ -115,7 +115,7 @@ use super::map::{self, HashMap, Keys, RandomState}; #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct HashSet<T, S = RandomState> { - map: HashMap<T, (), S> + map: HashMap<T, (), S>, } impl<T: Hash + Eq> HashSet<T, RandomState> { @@ -152,7 +152,8 @@ impl<T: Hash + Eq> HashSet<T, RandomState> { } impl<T, S> HashSet<T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { /// Creates a new empty hash set which will use the given hasher to hash /// keys. @@ -203,8 +204,7 @@ impl<T, S> HashSet<T, S> /// ``` #[inline] #[stable(feature = "hashmap_build_hasher", since = "1.7.0")] - pub fn with_capacity_and_hasher(capacity: usize, hasher: S) - -> HashSet<T, S> { + pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashSet<T, S> { HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) } } @@ -342,8 +342,9 @@ impl<T, S> HashSet<T, S> /// assert_eq!(diff1, [1, 4].iter().cloned().collect()); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>) - -> SymmetricDifference<'a, T, S> { + pub fn symmetric_difference<'a>(&'a self, + other: &'a HashSet<T, S>) + -> SymmetricDifference<'a, T, S> { SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) } } @@ -407,7 +408,9 @@ impl<T, S> HashSet<T, S> /// assert_eq!(v.len(), 1); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn len(&self) -> usize { self.map.len() } + pub fn len(&self) -> usize { + self.map.len() + } /// Returns true if the set contains no elements. /// @@ -422,7 +425,9 @@ impl<T, S> HashSet<T, S> /// assert!(!v.is_empty()); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn is_empty(&self) -> bool { self.map.is_empty() } + pub fn is_empty(&self) -> bool { + self.map.is_empty() + } /// Clears the set, returning all elements in an iterator. #[inline] @@ -444,7 +449,9 @@ impl<T, S> HashSet<T, S> /// assert!(v.is_empty()); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn clear(&mut self) { self.map.clear() } + pub fn clear(&mut self) { + self.map.clear() + } /// Returns `true` if the set contains a value. /// @@ -463,7 +470,8 @@ impl<T, S> HashSet<T, S> /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool - where T: Borrow<Q>, Q: Hash + Eq + where T: Borrow<Q>, + Q: Hash + Eq { self.map.contains_key(value) } @@ -475,7 +483,8 @@ impl<T, S> HashSet<T, S> /// the value type. #[stable(feature = "set_recovery", since = "1.9.0")] pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> - where T: Borrow<Q>, Q: Hash + Eq + where T: Borrow<Q>, + Q: Hash + Eq { Recover::get(&self.map, value) } @@ -566,7 +575,9 @@ impl<T, S> HashSet<T, S> /// assert_eq!(set.len(), 1); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() } + pub fn insert(&mut self, value: T) -> bool { + self.map.insert(value, ()).is_none() + } /// Adds a value to the set, replacing the existing value, if any, that is equal to the given /// one. Returns the replaced value. @@ -595,7 +606,8 @@ impl<T, S> HashSet<T, S> /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool - where T: Borrow<Q>, Q: Hash + Eq + where T: Borrow<Q>, + Q: Hash + Eq { self.map.remove(value).is_some() } @@ -607,7 +619,8 @@ impl<T, S> HashSet<T, S> /// the value type. #[stable(feature = "set_recovery", since = "1.9.0")] pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> - where T: Borrow<Q>, Q: Hash + Eq + where T: Borrow<Q>, + Q: Hash + Eq { Recover::take(&mut self.map, value) } @@ -615,10 +628,13 @@ impl<T, S> HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<T, S> PartialEq for HashSet<T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { fn eq(&self, other: &HashSet<T, S>) -> bool { - if self.len() != other.len() { return false; } + if self.len() != other.len() { + return false; + } self.iter().all(|key| other.contains(key)) } @@ -626,8 +642,10 @@ impl<T, S> PartialEq for HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<T, S> Eq for HashSet<T, S> - where T: Eq + Hash, S: BuildHasher -{} + where T: Eq + Hash, + S: BuildHasher +{ +} #[stable(feature = "rust1", since = "1.0.0")] impl<T, S> fmt::Debug for HashSet<T, S> @@ -642,9 +660,9 @@ impl<T, S> fmt::Debug for HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<T, S> FromIterator<T> for HashSet<T, S> where T: Eq + Hash, - S: BuildHasher + Default, + S: BuildHasher + Default { - fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> HashSet<T, S> { + fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> HashSet<T, S> { let iterator = iter.into_iter(); let lower = iterator.size_hint().0; let mut set = HashSet::with_capacity_and_hasher(lower, Default::default()); @@ -656,9 +674,9 @@ impl<T, S> FromIterator<T> for HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<T, S> Extend<T> for HashSet<T, S> where T: Eq + Hash, - S: BuildHasher, + S: BuildHasher { - fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { + fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { for k in iter { self.insert(k); } @@ -668,9 +686,9 @@ impl<T, S> Extend<T> for HashSet<T, S> #[stable(feature = "hash_extend_copy", since = "1.4.0")] impl<'a, T, S> Extend<&'a T> for HashSet<T, S> where T: 'a + Eq + Hash + Copy, - S: BuildHasher, + S: BuildHasher { - fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) { + fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { self.extend(iter.into_iter().cloned()); } } @@ -678,7 +696,7 @@ impl<'a, T, S> Extend<&'a T> for HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<T, S> Default for HashSet<T, S> where T: Eq + Hash, - S: BuildHasher + Default, + S: BuildHasher + Default { /// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher. fn default() -> HashSet<T, S> { @@ -689,7 +707,7 @@ impl<T, S> Default for HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S> where T: Eq + Hash + Clone, - S: BuildHasher + Default, + S: BuildHasher + Default { type Output = HashSet<T, S>; @@ -721,7 +739,7 @@ impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S> where T: Eq + Hash + Clone, - S: BuildHasher + Default, + S: BuildHasher + Default { type Output = HashSet<T, S>; @@ -753,7 +771,7 @@ impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S> where T: Eq + Hash + Clone, - S: BuildHasher + Default, + S: BuildHasher + Default { type Output = HashSet<T, S>; @@ -785,7 +803,7 @@ impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S> where T: Eq + Hash + Clone, - S: BuildHasher + Default, + S: BuildHasher + Default { type Output = HashSet<T, S>; @@ -817,13 +835,13 @@ impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S> /// HashSet iterator #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, K: 'a> { - iter: Keys<'a, K, ()> + iter: Keys<'a, K, ()>, } /// HashSet move iterator #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<K> { - iter: map::IntoIter<K, ()> + iter: map::IntoIter<K, ()>, } /// HashSet drain iterator @@ -853,18 +871,19 @@ pub struct Difference<'a, T: 'a, S: 'a> { /// Symmetric difference iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct SymmetricDifference<'a, T: 'a, S: 'a> { - iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>> + iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>, } /// Set union iterator. #[stable(feature = "rust1", since = "1.0.0")] pub struct Union<'a, T: 'a, S: 'a> { - iter: Chain<Iter<'a, T>, Difference<'a, T, S>> + iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> IntoIterator for &'a HashSet<T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { type Item = &'a T; type IntoIter = Iter<'a, T>; @@ -909,18 +928,26 @@ impl<T, S> IntoIterator for HashSet<T, S> #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K> Clone for Iter<'a, K> { - fn clone(&self) -> Iter<'a, K> { Iter { iter: self.iter.clone() } } + fn clone(&self) -> Iter<'a, K> { + Iter { iter: self.iter.clone() } + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K> Iterator for Iter<'a, K> { type Item = &'a K; - fn next(&mut self) -> Option<&'a K> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + fn next(&mut self) -> Option<&'a K> { + self.iter.next() + } + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K> ExactSizeIterator for Iter<'a, K> { - fn len(&self) -> usize { self.iter.len() } + fn len(&self) -> usize { + self.iter.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K> FusedIterator for Iter<'a, K> {} @@ -929,12 +956,18 @@ impl<'a, K> FusedIterator for Iter<'a, K> {} impl<K> Iterator for IntoIter<K> { type Item = K; - fn next(&mut self) -> Option<K> { self.iter.next().map(|(k, _)| k) } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + fn next(&mut self) -> Option<K> { + self.iter.next().map(|(k, _)| k) + } + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<K> ExactSizeIterator for IntoIter<K> { - fn len(&self) -> usize { self.iter.len() } + fn len(&self) -> usize { + self.iter.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<K> FusedIterator for IntoIter<K> {} @@ -943,12 +976,18 @@ impl<K> FusedIterator for IntoIter<K> {} impl<'a, K> Iterator for Drain<'a, K> { type Item = K; - fn next(&mut self) -> Option<K> { self.iter.next().map(|(k, _)| k) } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + fn next(&mut self) -> Option<K> { + self.iter.next().map(|(k, _)| k) + } + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } } #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K> ExactSizeIterator for Drain<'a, K> { - fn len(&self) -> usize { self.iter.len() } + fn len(&self) -> usize { + self.iter.len() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, K> FusedIterator for Drain<'a, K> {} @@ -962,7 +1001,8 @@ impl<'a, T, S> Clone for Intersection<'a, T, S> { #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Iterator for Intersection<'a, T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { type Item = &'a T; @@ -970,9 +1010,11 @@ impl<'a, T, S> Iterator for Intersection<'a, T, S> loop { match self.iter.next() { None => return None, - Some(elt) => if self.other.contains(elt) { - return Some(elt) - }, + Some(elt) => { + if self.other.contains(elt) { + return Some(elt); + } + } } } } @@ -985,8 +1027,10 @@ impl<'a, T, S> Iterator for Intersection<'a, T, S> #[unstable(feature = "fused", issue = "35602")] impl<'a, T, S> FusedIterator for Intersection<'a, T, S> - where T: Eq + Hash, S: BuildHasher -{} + where T: Eq + Hash, + S: BuildHasher +{ +} #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Clone for Difference<'a, T, S> { @@ -997,7 +1041,8 @@ impl<'a, T, S> Clone for Difference<'a, T, S> { #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Iterator for Difference<'a, T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { type Item = &'a T; @@ -1005,9 +1050,11 @@ impl<'a, T, S> Iterator for Difference<'a, T, S> loop { match self.iter.next() { None => return None, - Some(elt) => if !self.other.contains(elt) { - return Some(elt) - }, + Some(elt) => { + if !self.other.contains(elt) { + return Some(elt); + } + } } } } @@ -1020,8 +1067,10 @@ impl<'a, T, S> Iterator for Difference<'a, T, S> #[unstable(feature = "fused", issue = "35602")] impl<'a, T, S> FusedIterator for Difference<'a, T, S> - where T: Eq + Hash, S: BuildHasher -{} + where T: Eq + Hash, + S: BuildHasher +{ +} #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> { @@ -1032,53 +1081,85 @@ impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> { #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { type Item = &'a T; - fn next(&mut self) -> Option<&'a T> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + fn next(&mut self) -> Option<&'a T> { + self.iter.next() + } + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, T, S> FusedIterator for SymmetricDifference<'a, T, S> - where T: Eq + Hash, S: BuildHasher -{} + where T: Eq + Hash, + S: BuildHasher +{ +} #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Clone for Union<'a, T, S> { - fn clone(&self) -> Union<'a, T, S> { Union { iter: self.iter.clone() } } + fn clone(&self) -> Union<'a, T, S> { + Union { iter: self.iter.clone() } + } } #[unstable(feature = "fused", issue = "35602")] impl<'a, T, S> FusedIterator for Union<'a, T, S> - where T: Eq + Hash, S: BuildHasher -{} + where T: Eq + Hash, + S: BuildHasher +{ +} #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Iterator for Union<'a, T, S> - where T: Eq + Hash, S: BuildHasher + where T: Eq + Hash, + S: BuildHasher { type Item = &'a T; - fn next(&mut self) -> Option<&'a T> { self.iter.next() } - fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } + fn next(&mut self) -> Option<&'a T> { + self.iter.next() + } + fn size_hint(&self) -> (usize, Option<usize>) { + self.iter.size_hint() + } } #[allow(dead_code)] fn assert_covariance() { - fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> { v } - fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { v } - fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { v } + fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> { + v + } + fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> { + v + } + fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> { + v + } fn difference<'a, 'new>(v: Difference<'a, &'static str, RandomState>) - -> Difference<'a, &'new str, RandomState> { v } + -> Difference<'a, &'new str, RandomState> { + v + } fn symmetric_difference<'a, 'new>(v: SymmetricDifference<'a, &'static str, RandomState>) - -> SymmetricDifference<'a, &'new str, RandomState> { v } + -> SymmetricDifference<'a, &'new str, RandomState> { + v + } fn intersection<'a, 'new>(v: Intersection<'a, &'static str, RandomState>) - -> Intersection<'a, &'new str, RandomState> { v } + -> Intersection<'a, &'new str, RandomState> { + v + } fn union<'a, 'new>(v: Union<'a, &'static str, RandomState>) - -> Union<'a, &'new str, RandomState> { v } - fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { d } + -> Union<'a, &'new str, RandomState> { + v + } + fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> { + d + } } #[cfg(test)] @@ -1383,7 +1464,9 @@ mod test_set { assert_eq!(last_i, 49); } - for _ in &s { panic!("s should be empty!"); } + for _ in &s { + panic!("s should be empty!"); + } // reset to try again. s.extend(1..100); diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs index afd833d8bdd..b12f132a3a9 100644 --- a/src/libstd/collections/hash/table.rs +++ b/src/libstd/collections/hash/table.rs @@ -448,10 +448,10 @@ impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> { unsafe { *self.raw.hash = EMPTY_BUCKET; (EmptyBucket { - raw: self.raw, - idx: self.idx, - table: self.table, - }, + raw: self.raw, + idx: self.idx, + table: self.table, + }, ptr::read(self.raw.key), ptr::read(self.raw.val)) } @@ -643,13 +643,13 @@ impl<K, V> RawTable<K, V> { // One check for overflow that covers calculation and rounding of size. let size_of_bucket = size_of::<u64>() - .checked_add(size_of::<K>()) - .unwrap() - .checked_add(size_of::<V>()) - .unwrap(); + .checked_add(size_of::<K>()) + .unwrap() + .checked_add(size_of::<V>()) + .unwrap(); assert!(size >= capacity.checked_mul(size_of_bucket) - .expect("capacity overflow"), + .expect("capacity overflow"), "capacity overflow"); let buffer = allocate(size, malloc_alignment); @@ -672,10 +672,8 @@ impl<K, V> RawTable<K, V> { let keys_size = self.capacity * size_of::<K>(); let buffer = *self.hashes as *const u8; - let (keys_offset, vals_offset, oflo) = calculate_offsets(hashes_size, - keys_size, - align_of::<K>(), - align_of::<V>()); + let (keys_offset, vals_offset, oflo) = + calculate_offsets(hashes_size, keys_size, align_of::<K>(), align_of::<V>()); debug_assert!(!oflo, "capacity overflow"); unsafe { RawBucket { @@ -990,9 +988,7 @@ impl<'a, K, V> Iterator for Drain<'a, K, V> { } impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> { fn len(&self) -> usize { - unsafe { - (**self.table).size() - } + unsafe { (**self.table).size() } } } |