diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/collections/hash/map.rs | 123 | ||||
| -rw-r--r-- | src/libstd/collections/hash/set.rs | 2 | ||||
| -rw-r--r-- | src/libstd/collections/hash/table.rs | 4 |
3 files changed, 41 insertions, 88 deletions
diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs index 2a8d97eed05..7d9c9b92460 100644 --- a/src/libstd/collections/hash/map.rs +++ b/src/libstd/collections/hash/map.rs @@ -297,7 +297,7 @@ pub struct HashMap<K, V, H = RandomSipHasher> { /// Search for a pre-hashed key. fn search_hashed<K, V, M, F>(table: M, - hash: &SafeHash, + hash: SafeHash, mut is_match: F) -> SearchResult<K, V, M> where M: Deref<RawTable<K, V>>, @@ -320,14 +320,9 @@ fn search_hashed<K, V, M, F>(table: M, } // If the hash doesn't match, it can't be this one.. - if *hash == full.hash() { - let matched = { - let (k, _) = full.read(); - is_match(k) - }; - + if hash == full.hash() { // If the key doesn't match, it can't be this one.. - if matched { + if is_match(full.read().0) { return FoundExisting(full); } } @@ -353,7 +348,7 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) { } // Now we've done all our shifting. Return the value we grabbed earlier. - return (retkey, retval); + (retkey, retval) } /// Perform robin hood bucket stealing at the given `bucket`. You must @@ -389,10 +384,11 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>, let b = bucket.put(old_hash, old_key, old_val); // Now that it's stolen, just read the value's pointer // right out of the table! - let (_, v) = Bucket::at_index(b.into_table(), starting_index).peek() - .expect_full() - .into_mut_refs(); - return v; + return Bucket::at_index(b.into_table(), starting_index) + .peek() + .expect_full() + .into_mut_refs() + .1; }, table::Full(bucket) => bucket }; @@ -441,14 +437,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { fn search_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>> { let hash = self.make_hash(q); - search_hashed(&self.table, &hash, |k| q.equiv(k)).into_option() + search_hashed(&self.table, hash, |k| q.equiv(k)).into_option() } #[allow(deprecated)] fn search_equiv_mut<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>> { let hash = self.make_hash(q); - search_hashed(&mut self.table, &hash, |k| q.equiv(k)).into_option() + search_hashed(&mut self.table, hash, |k| q.equiv(k)).into_option() } /// Search for a key, yielding the index if it's found in the hashtable. @@ -458,7 +454,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { where Q: BorrowFrom<K> + Eq + Hash<S> { let hash = self.make_hash(q); - search_hashed(&self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k))) + search_hashed(&self.table, hash, |k| q.eq(BorrowFrom::borrow_from(k))) .into_option() } @@ -466,14 +462,14 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { where Q: BorrowFrom<K> + Eq + Hash<S> { let hash = self.make_hash(q); - search_hashed(&mut self.table, &hash, |k| q.eq(BorrowFrom::borrow_from(k))) + search_hashed(&mut self.table, hash, |k| q.eq(BorrowFrom::borrow_from(k))) .into_option() } // The caller should ensure that invariants by Robin Hood Hashing hold. fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) { let cap = self.table.capacity(); - let mut buckets = Bucket::new(&mut self.table, &hash); + let mut buckets = Bucket::new(&mut self.table, hash); let ib = buckets.index(); while buckets.index() != ib + cap { @@ -762,26 +758,22 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { { // Worst case, we'll find one empty bucket among `size + 1` buckets. let size = self.table.size(); - let mut probe = Bucket::new(&mut self.table, &hash); + let mut probe = Bucket::new(&mut self.table, hash); let ib = probe.index(); loop { let mut bucket = match probe.peek() { Empty(bucket) => { // Found a hole! - let bucket = bucket.put(hash, k, v); - let (_, val) = bucket.into_mut_refs(); - return val; - }, + return bucket.put(hash, k, v).into_mut_refs().1; + } Full(bucket) => bucket }; + // hash matches? if bucket.hash() == hash { - let found_match = { - let (bucket_k, _) = bucket.read_mut(); - k == *bucket_k - }; - if found_match { + // key matches? + if k == *bucket.read_mut().0 { let (bucket_k, bucket_v) = bucket.into_mut_refs(); debug_assert!(k == *bucket_k); // Key already exists. Get its reference. @@ -811,13 +803,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { /// Deprecated: use `get` and `BorrowFrom` instead. #[deprecated = "use get and BorrowFrom instead"] pub fn find_equiv<'a, Sized? Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V> { - match self.search_equiv(k) { - None => None, - Some(bucket) => { - let (_, v_ref) = bucket.into_refs(); - Some(v_ref) - } - } + self.search_equiv(k).map(|bucket| bucket.into_refs().1) } /// Deprecated: use `remove` and `BorrowFrom` instead. @@ -829,13 +815,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { self.reserve(1); - match self.search_equiv_mut(k) { - Some(bucket) => { - let (_k, val) = pop_internal(bucket); - Some(val) - } - _ => None - } + self.search_equiv_mut(k).map(|bucket| pop_internal(bucket).1) } /// An iterator visiting all keys in arbitrary order. @@ -1022,11 +1002,8 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { while buckets.index() != cap { buckets = match buckets.peek() { - Empty(b) => b.next(), - Full(full) => { - let (b, _, _) = full.take(); - b.next() - } + Empty(b) => b.next(), + Full(full) => full.take().0.next(), }; } } @@ -1057,10 +1034,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { pub fn get<Sized? Q>(&self, k: &Q) -> Option<&V> where Q: Hash<S> + Eq + BorrowFrom<K> { - self.search(k).map(|bucket| { - let (_, v) = bucket.into_refs(); - v - }) + self.search(k).map(|bucket| bucket.into_refs().1) } /// Returns true if the map contains a value for the specified key. @@ -1115,13 +1089,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { pub fn get_mut<Sized? Q>(&mut self, k: &Q) -> Option<&mut V> where Q: Hash<S> + Eq + BorrowFrom<K> { - match self.search_mut(k) { - Some(bucket) => { - let (_, v) = bucket.into_mut_refs(); - Some(v) - } - _ => None - } + self.search_mut(k).map(|bucket| bucket.into_mut_refs().1) } /// Deprecated: Renamed to `insert`. @@ -1189,10 +1157,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> { return None } - self.search_mut(k).map(|bucket| { - let (_k, val) = pop_internal(bucket); - val - }) + self.search_mut(k).map(|bucket| pop_internal(bucket).1) } } @@ -1200,7 +1165,7 @@ fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHas -> Entry<'a, K, V> { // Worst case, we'll find one empty bucket among `size + 1` buckets. let size = table.size(); - let mut probe = Bucket::new(table, &hash); + let mut probe = Bucket::new(table, hash); let ib = probe.index(); loop { @@ -1216,13 +1181,10 @@ fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHas Full(bucket) => bucket }; + // hash matches? if bucket.hash() == hash { - let is_eq = { - let (bucket_k, _) = bucket.read(); - k == *bucket_k - }; - - if is_eq { + // key matches? + if k == *bucket.read().0 { return Occupied(OccupiedEntry{ elem: bucket, }); @@ -1308,10 +1270,7 @@ impl<K: Hash<S> + Eq, Sized? Q, V, S, H: Hasher<S>> IndexMut<Q, V> for HashMap<K { #[inline] fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V { - match self.get_mut(index) { - Some(v) => v, - None => panic!("no entry found for key") - } + self.get_mut(index).expect("no entry found for key") } } @@ -1400,21 +1359,18 @@ impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> { impl<'a, K, V> OccupiedEntry<'a, K, V> { /// Gets a reference to the value in the entry pub fn get(&self) -> &V { - let (_, v) = self.elem.read(); - v + self.elem.read().1 } /// Gets a mutable reference to the value in the entry pub fn get_mut(&mut self) -> &mut V { - let (_, v) = self.elem.read_mut(); - v + self.elem.read_mut().1 } /// Converts the OccupiedEntry into a mutable reference to the value in the entry /// with a lifetime bound to the map itself pub fn into_mut(self) -> &'a mut V { - let (_, v) = self.elem.into_mut_refs(); - v + self.elem.into_mut_refs().1 } /// Sets the value of the entry, and returns the entry's old value @@ -1426,8 +1382,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { /// Takes the value out of the entry, and returns it pub fn take(self) -> V { - let (_, v) = pop_internal(self.elem); - v + pop_internal(self.elem).1 } } @@ -1440,9 +1395,7 @@ impl<'a, K, V> VacantEntry<'a, K, V> { robin_hood(bucket, ib, self.hash, self.key, value) } NoElem(bucket) => { - let full = bucket.put(self.hash, self.key, value); - let (_, v) = full.into_mut_refs(); - v + bucket.put(self.hash, self.key, value).into_mut_refs().1 } } } @@ -1458,7 +1411,7 @@ pub type Values<'a, K, V> = impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> { fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> { - let (lower, _) = iter.size_hint(); + let lower = iter.size_hint().0; let mut map = HashMap::with_capacity_and_hasher(lower, Default::default()); map.extend(iter); map diff --git a/src/libstd/collections/hash/set.rs b/src/libstd/collections/hash/set.rs index c71f0d5b935..262bbf094ec 100644 --- a/src/libstd/collections/hash/set.rs +++ b/src/libstd/collections/hash/set.rs @@ -595,7 +595,7 @@ impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> { impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> { fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> { - let (lower, _) = iter.size_hint(); + let lower = iter.size_hint().0; let mut set = HashSet::with_capacity_and_hasher(lower, Default::default()); set.extend(iter); set diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs index ef4cabedc47..da06387e9a5 100644 --- a/src/libstd/collections/hash/table.rs +++ b/src/libstd/collections/hash/table.rs @@ -124,7 +124,7 @@ struct GapThenFull<K, V, M> { /// A hash that is not zero, since we use a hash of zero to represent empty /// buckets. -#[deriving(PartialEq)] +#[deriving(PartialEq, Copy)] pub struct SafeHash { hash: u64, } @@ -211,7 +211,7 @@ impl<K, V, M> Bucket<K, V, M> { } impl<K, V, M: Deref<RawTable<K, V>>> Bucket<K, V, M> { - pub fn new(table: M, hash: &SafeHash) -> Bucket<K, V, M> { + pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> { Bucket::at_index(table, hash.inspect() as uint) } |