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
/// 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
elem: NoElem(bucket),
};
}
- Full(bucket) => bucket
+ Full(bucket) => bucket,
};
let robin_ib = full.index() as isize - full.displacement() as isize;
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 };
}
}
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,
};
}
///
/// `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*.
// 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();
}
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)
}
/// 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()))
#[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()))
empty.put(hash, k, v);
return;
}
- Full(b) => b.into_bucket()
+ Full(b) => b.into_bucket(),
};
buckets.next();
}
}
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.
/// ```
#[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 {
}
b.into_bucket()
}
- Empty(b) => b.into_bucket()
+ Empty(b) => b.into_bucket(),
};
bucket.next();
}
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!(),
}
}
/// 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.
///
/// ```
#[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.
#[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
/// ```
#[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)
}
/// ```
#[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()
}
/// ```
#[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)
}
/// ```
#[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)
#[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()
#[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> {
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;
/// 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>,
InternalEntry::Occupied { elem } => {
Some(Occupied(OccupiedEntry {
key: Some(key),
- elem: elem
+ elem: elem,
}))
}
InternalEntry::Vacant { hash, elem } => {
elem: elem,
}))
}
- InternalEntry::TableIsEmpty => None
+ InternalEntry::TableIsEmpty => None,
}
}
}
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()
+ }
}
}
}
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()
}
}
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()
}
}
#[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>;
#[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>;
#[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>;
/// 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() }
}
}
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")]
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> {}
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> {}
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> {}
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> {}
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> {}
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> {}
#[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());
#[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);
}
#[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)));
}
}
/// 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
(r.gen(), r.gen())
});
- KEYS.with(|&(k0, k1)| {
- RandomState { k0: k0, k1: k1 }
- })
+ KEYS.with(|&(k0, k1)| RandomState { k0: k0, k1: k1 })
}
}
}
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;
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)
#[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)]
#[derive(Hash, PartialEq, Eq)]
struct Dropable {
- k: usize
+ k: usize,
}
impl Dropable {
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);
}
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);
}
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);
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);
}
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));
}
}
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));
}
m.insert(1, 2);
match m.get(&1) {
None => panic!(),
- Some(v) => assert_eq!(*v, 2)
+ Some(v) => assert_eq!(*v, 2),
}
}
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();
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();
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();
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();
}
#[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();
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);
Vacant(e) => {
assert_eq!(key, *e.key());
e.insert(value.clone());
- },
+ }
}
assert_eq!(a.len(), 1);
assert_eq!(a[key], value);
projects / rust.git / blobdiff