1 use crate::raw
::{Bucket, RawDrain, RawIntoIter, RawIter, RawTable}
;
2 use crate::TryReserveError
;
3 use core
::borrow
::Borrow
;
4 use core
::fmt
::{self, Debug}
;
5 use core
::hash
::{BuildHasher, Hash, Hasher}
;
6 use core
::iter
::{FromIterator, FusedIterator}
;
7 use core
::marker
::PhantomData
;
11 /// Default hasher for `HashMap`.
12 #[cfg(feature = "ahash")]
13 pub type DefaultHashBuilder
= ahash
::RandomState
;
15 /// Dummy default hasher for `HashMap`.
16 #[cfg(not(feature = "ahash"))]
17 pub enum DefaultHashBuilder {}
19 /// A hash map implemented with quadratic probing and SIMD lookup.
21 /// The default hashing algorithm is currently [`AHash`], though this is
22 /// subject to change at any point in the future. This hash function is very
23 /// fast for all types of keys, but this algorithm will typically *not* protect
24 /// against attacks such as HashDoS.
26 /// The hashing algorithm can be replaced on a per-`HashMap` basis using the
27 /// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods. Many
28 /// alternative algorithms are available on crates.io, such as the [`fnv`] crate.
30 /// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
31 /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
32 /// If you implement these yourself, it is important that the following
36 /// k1 == k2 -> hash(k1) == hash(k2)
39 /// In other words, if two keys are equal, their hashes must be equal.
41 /// It is a logic error for a key to be modified in such a way that the key's
42 /// hash, as determined by the [`Hash`] trait, or its equality, as determined by
43 /// the [`Eq`] trait, changes while it is in the map. This is normally only
44 /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
46 /// It is also a logic error for the [`Hash`] implementation of a key to panic.
47 /// This is generally only possible if the trait is implemented manually. If a
48 /// panic does occur then the contents of the `HashMap` may become corrupted and
49 /// some items may be dropped from the table.
54 /// use hashbrown::HashMap;
56 /// // Type inference lets us omit an explicit type signature (which
57 /// // would be `HashMap<String, String>` in this example).
58 /// let mut book_reviews = HashMap::new();
60 /// // Review some books.
61 /// book_reviews.insert(
62 /// "Adventures of Huckleberry Finn".to_string(),
63 /// "My favorite book.".to_string(),
65 /// book_reviews.insert(
66 /// "Grimms' Fairy Tales".to_string(),
67 /// "Masterpiece.".to_string(),
69 /// book_reviews.insert(
70 /// "Pride and Prejudice".to_string(),
71 /// "Very enjoyable.".to_string(),
73 /// book_reviews.insert(
74 /// "The Adventures of Sherlock Holmes".to_string(),
75 /// "Eye lyked it alot.".to_string(),
78 /// // Check for a specific one.
79 /// // When collections store owned values (String), they can still be
80 /// // queried using references (&str).
81 /// if !book_reviews.contains_key("Les Misérables") {
82 /// println!("We've got {} reviews, but Les Misérables ain't one.",
83 /// book_reviews.len());
86 /// // oops, this review has a lot of spelling mistakes, let's delete it.
87 /// book_reviews.remove("The Adventures of Sherlock Holmes");
89 /// // Look up the values associated with some keys.
90 /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
91 /// for &book in &to_find {
92 /// match book_reviews.get(book) {
93 /// Some(review) => println!("{}: {}", book, review),
94 /// None => println!("{} is unreviewed.", book)
98 /// // Look up the value for a key (will panic if the key is not found).
99 /// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]);
101 /// // Iterate over everything.
102 /// for (book, review) in &book_reviews {
103 /// println!("{}: \"{}\"", book, review);
107 /// `HashMap` also implements an [`Entry API`](#method.entry), which allows
108 /// for more complex methods of getting, setting, updating and removing keys and
112 /// use hashbrown::HashMap;
114 /// // type inference lets us omit an explicit type signature (which
115 /// // would be `HashMap<&str, u8>` in this example).
116 /// let mut player_stats = HashMap::new();
118 /// fn random_stat_buff() -> u8 {
119 /// // could actually return some random value here - let's just return
120 /// // some fixed value for now
124 /// // insert a key only if it doesn't already exist
125 /// player_stats.entry("health").or_insert(100);
127 /// // insert a key using a function that provides a new value only if it
128 /// // doesn't already exist
129 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
131 /// // update a key, guarding against the key possibly not being set
132 /// let stat = player_stats.entry("attack").or_insert(100);
133 /// *stat += random_stat_buff();
136 /// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`].
137 /// We must also derive [`PartialEq`].
139 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
140 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
141 /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
142 /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
143 /// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html
144 /// [`default`]: #method.default
145 /// [`with_hasher`]: #method.with_hasher
146 /// [`with_capacity_and_hasher`]: #method.with_capacity_and_hasher
147 /// [`fnv`]: https://crates.io/crates/fnv
148 /// [`AHash`]: https://crates.io/crates/ahash
151 /// use hashbrown::HashMap;
153 /// #[derive(Hash, Eq, PartialEq, Debug)]
160 /// /// Creates a new Viking.
161 /// fn new(name: &str, country: &str) -> Viking {
162 /// Viking { name: name.to_string(), country: country.to_string() }
166 /// // Use a HashMap to store the vikings' health points.
167 /// let mut vikings = HashMap::new();
169 /// vikings.insert(Viking::new("Einar", "Norway"), 25);
170 /// vikings.insert(Viking::new("Olaf", "Denmark"), 24);
171 /// vikings.insert(Viking::new("Harald", "Iceland"), 12);
173 /// // Use derived implementation to print the status of the vikings.
174 /// for (viking, health) in &vikings {
175 /// println!("{:?} has {} hp", viking, health);
179 /// A `HashMap` with fixed list of elements can be initialized from an array:
182 /// use hashbrown::HashMap;
184 /// let timber_resources: HashMap<&str, i32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)]
185 /// .iter().cloned().collect();
186 /// // use the values stored in map
188 pub struct HashMap
<K
, V
, S
= DefaultHashBuilder
> {
189 pub(crate) hash_builder
: S
,
190 pub(crate) table
: RawTable
<(K
, V
)>,
193 impl<K
: Clone
, V
: Clone
, S
: Clone
> Clone
for HashMap
<K
, V
, S
> {
194 fn clone(&self) -> Self {
196 hash_builder
: self.hash_builder
.clone(),
197 table
: self.table
.clone(),
201 fn clone_from(&mut self, source
: &Self) {
202 self.table
.clone_from(&source
.table
);
204 // Update hash_builder only if we successfully cloned all elements.
205 self.hash_builder
.clone_from(&source
.hash_builder
);
209 #[cfg_attr(feature = "inline-more", inline)]
210 pub(crate) fn make_hash
<K
: Hash
+ ?Sized
>(hash_builder
: &impl BuildHasher
, val
: &K
) -> u64 {
211 let mut state
= hash_builder
.build_hasher();
212 val
.hash(&mut state
);
216 #[cfg(feature = "ahash")]
217 impl<K
, V
> HashMap
<K
, V
, DefaultHashBuilder
> {
218 /// Creates an empty `HashMap`.
220 /// The hash map is initially created with a capacity of 0, so it will not allocate until it
221 /// is first inserted into.
226 /// use hashbrown::HashMap;
227 /// let mut map: HashMap<&str, i32> = HashMap::new();
229 #[cfg_attr(feature = "inline-more", inline)]
230 pub fn new() -> Self {
234 /// Creates an empty `HashMap` with the specified capacity.
236 /// The hash map will be able to hold at least `capacity` elements without
237 /// reallocating. If `capacity` is 0, the hash map will not allocate.
242 /// use hashbrown::HashMap;
243 /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
245 #[cfg_attr(feature = "inline-more", inline)]
246 pub fn with_capacity(capacity
: usize) -> Self {
247 Self::with_capacity_and_hasher(capacity
, DefaultHashBuilder
::default())
251 impl<K
, V
, S
> HashMap
<K
, V
, S
> {
252 /// Creates an empty `HashMap` which will use the given hash builder to hash
255 /// The created map has the default initial capacity.
257 /// Warning: `hash_builder` is normally randomly generated, and
258 /// is designed to allow HashMaps to be resistant to attacks that
259 /// cause many collisions and very poor performance. Setting it
260 /// manually using this function can expose a DoS attack vector.
262 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
263 /// the HashMap to be useful, see its documentation for details.
268 /// use hashbrown::HashMap;
269 /// use hashbrown::hash_map::DefaultHashBuilder;
271 /// let s = DefaultHashBuilder::default();
272 /// let mut map = HashMap::with_hasher(s);
273 /// map.insert(1, 2);
276 /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
277 #[cfg_attr(feature = "inline-more", inline)]
278 pub const fn with_hasher(hash_builder
: S
) -> Self {
281 table
: RawTable
::new(),
285 /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
286 /// to hash the keys.
288 /// The hash map will be able to hold at least `capacity` elements without
289 /// reallocating. If `capacity` is 0, the hash map will not allocate.
291 /// Warning: `hash_builder` is normally randomly generated, and
292 /// is designed to allow HashMaps to be resistant to attacks that
293 /// cause many collisions and very poor performance. Setting it
294 /// manually using this function can expose a DoS attack vector.
296 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
297 /// the HashMap to be useful, see its documentation for details.
302 /// use hashbrown::HashMap;
303 /// use hashbrown::hash_map::DefaultHashBuilder;
305 /// let s = DefaultHashBuilder::default();
306 /// let mut map = HashMap::with_capacity_and_hasher(10, s);
307 /// map.insert(1, 2);
310 /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
311 #[cfg_attr(feature = "inline-more", inline)]
312 pub fn with_capacity_and_hasher(capacity
: usize, hash_builder
: S
) -> Self {
315 table
: RawTable
::with_capacity(capacity
),
319 /// Returns a reference to the map's [`BuildHasher`].
321 /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
326 /// use hashbrown::HashMap;
327 /// use hashbrown::hash_map::DefaultHashBuilder;
329 /// let hasher = DefaultHashBuilder::default();
330 /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher);
331 /// let hasher: &DefaultHashBuilder = map.hasher();
333 #[cfg_attr(feature = "inline-more", inline)]
334 pub fn hasher(&self) -> &S
{
338 /// Returns the number of elements the map can hold without reallocating.
340 /// This number is a lower bound; the `HashMap<K, V>` might be able to hold
341 /// more, but is guaranteed to be able to hold at least this many.
346 /// use hashbrown::HashMap;
347 /// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
348 /// assert!(map.capacity() >= 100);
350 #[cfg_attr(feature = "inline-more", inline)]
351 pub fn capacity(&self) -> usize {
352 self.table
.capacity()
355 /// An iterator visiting all keys in arbitrary order.
356 /// The iterator element type is `&'a K`.
361 /// use hashbrown::HashMap;
363 /// let mut map = HashMap::new();
364 /// map.insert("a", 1);
365 /// map.insert("b", 2);
366 /// map.insert("c", 3);
368 /// for key in map.keys() {
369 /// println!("{}", key);
372 #[cfg_attr(feature = "inline-more", inline)]
373 pub fn keys(&self) -> Keys
<'_
, K
, V
> {
374 Keys { inner: self.iter() }
377 /// An iterator visiting all values in arbitrary order.
378 /// The iterator element type is `&'a V`.
383 /// use hashbrown::HashMap;
385 /// let mut map = HashMap::new();
386 /// map.insert("a", 1);
387 /// map.insert("b", 2);
388 /// map.insert("c", 3);
390 /// for val in map.values() {
391 /// println!("{}", val);
394 #[cfg_attr(feature = "inline-more", inline)]
395 pub fn values(&self) -> Values
<'_
, K
, V
> {
396 Values { inner: self.iter() }
399 /// An iterator visiting all values mutably in arbitrary order.
400 /// The iterator element type is `&'a mut V`.
405 /// use hashbrown::HashMap;
407 /// let mut map = HashMap::new();
409 /// map.insert("a", 1);
410 /// map.insert("b", 2);
411 /// map.insert("c", 3);
413 /// for val in map.values_mut() {
414 /// *val = *val + 10;
417 /// for val in map.values() {
418 /// println!("{}", val);
421 #[cfg_attr(feature = "inline-more", inline)]
422 pub fn values_mut(&mut self) -> ValuesMut
<'_
, K
, V
> {
424 inner
: self.iter_mut(),
428 /// An iterator visiting all key-value pairs in arbitrary order.
429 /// The iterator element type is `(&'a K, &'a V)`.
434 /// use hashbrown::HashMap;
436 /// let mut map = HashMap::new();
437 /// map.insert("a", 1);
438 /// map.insert("b", 2);
439 /// map.insert("c", 3);
441 /// for (key, val) in map.iter() {
442 /// println!("key: {} val: {}", key, val);
445 #[cfg_attr(feature = "inline-more", inline)]
446 pub fn iter(&self) -> Iter
<'_
, K
, V
> {
447 // Here we tie the lifetime of self to the iter.
450 inner
: self.table
.iter(),
456 /// An iterator visiting all key-value pairs in arbitrary order,
457 /// with mutable references to the values.
458 /// The iterator element type is `(&'a K, &'a mut V)`.
463 /// use hashbrown::HashMap;
465 /// let mut map = HashMap::new();
466 /// map.insert("a", 1);
467 /// map.insert("b", 2);
468 /// map.insert("c", 3);
470 /// // Update all values
471 /// for (_, val) in map.iter_mut() {
475 /// for (key, val) in &map {
476 /// println!("key: {} val: {}", key, val);
479 #[cfg_attr(feature = "inline-more", inline)]
480 pub fn iter_mut(&mut self) -> IterMut
<'_
, K
, V
> {
481 // Here we tie the lifetime of self to the iter.
484 inner
: self.table
.iter(),
491 #[cfg_attr(feature = "inline-more", inline)]
492 fn raw_capacity(&self) -> usize {
496 /// Returns the number of elements in the map.
501 /// use hashbrown::HashMap;
503 /// let mut a = HashMap::new();
504 /// assert_eq!(a.len(), 0);
505 /// a.insert(1, "a");
506 /// assert_eq!(a.len(), 1);
508 #[cfg_attr(feature = "inline-more", inline)]
509 pub fn len(&self) -> usize {
513 /// Returns `true` if the map contains no elements.
518 /// use hashbrown::HashMap;
520 /// let mut a = HashMap::new();
521 /// assert!(a.is_empty());
522 /// a.insert(1, "a");
523 /// assert!(!a.is_empty());
525 #[cfg_attr(feature = "inline-more", inline)]
526 pub fn is_empty(&self) -> bool
{
530 /// Clears the map, returning all key-value pairs as an iterator. Keeps the
531 /// allocated memory for reuse.
536 /// use hashbrown::HashMap;
538 /// let mut a = HashMap::new();
539 /// a.insert(1, "a");
540 /// a.insert(2, "b");
542 /// for (k, v) in a.drain().take(1) {
543 /// assert!(k == 1 || k == 2);
544 /// assert!(v == "a" || v == "b");
547 /// assert!(a.is_empty());
549 #[cfg_attr(feature = "inline-more", inline)]
550 pub fn drain(&mut self) -> Drain
<'_
, K
, V
> {
552 inner
: self.table
.drain(),
556 /// Retains only the elements specified by the predicate.
558 /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`.
563 /// use hashbrown::HashMap;
565 /// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect();
566 /// map.retain(|&k, _| k % 2 == 0);
567 /// assert_eq!(map.len(), 4);
569 pub fn retain
<F
>(&mut self, mut f
: F
)
571 F
: FnMut(&K
, &mut V
) -> bool
,
573 // Here we only use `iter` as a temporary, preventing use-after-free
575 for item
in self.table
.iter() {
576 let &mut (ref key
, ref mut value
) = item
.as_mut();
578 self.table
.erase(item
);
584 /// Drains elements which are true under the given predicate,
585 /// and returns an iterator over the removed items.
587 /// In other words, move all pairs `(k, v)` such that `f(&k,&mut v)` returns `true` out
588 /// into another iterator.
590 /// When the returned DrainedFilter is dropped, any remaining elements that satisfy
591 /// the predicate are dropped from the table.
596 /// use hashbrown::HashMap;
598 /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
599 /// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect();
601 /// let mut evens = drained.keys().cloned().collect::<Vec<_>>();
602 /// let mut odds = map.keys().cloned().collect::<Vec<_>>();
606 /// assert_eq!(evens, vec![0, 2, 4, 6]);
607 /// assert_eq!(odds, vec![1, 3, 5, 7]);
609 #[cfg_attr(feature = "inline-more", inline)]
610 pub fn drain_filter
<F
>(&mut self, f
: F
) -> DrainFilter
<'_
, K
, V
, F
>
612 F
: FnMut(&K
, &mut V
) -> bool
,
616 inner
: DrainFilterInner
{
617 iter
: unsafe { self.table.iter() }
,
618 table
: &mut self.table
,
623 /// Clears the map, removing all key-value pairs. Keeps the allocated memory
629 /// use hashbrown::HashMap;
631 /// let mut a = HashMap::new();
632 /// a.insert(1, "a");
634 /// assert!(a.is_empty());
636 #[cfg_attr(feature = "inline-more", inline)]
637 pub fn clear(&mut self) {
642 impl<K
, V
, S
> HashMap
<K
, V
, S
>
647 /// Reserves capacity for at least `additional` more elements to be inserted
648 /// in the `HashMap`. The collection may reserve more space to avoid
649 /// frequent reallocations.
653 /// Panics if the new allocation size overflows [`usize`].
655 /// [`usize`]: https://doc.rust-lang.org/std/primitive.usize.html
660 /// use hashbrown::HashMap;
661 /// let mut map: HashMap<&str, i32> = HashMap::new();
664 #[cfg_attr(feature = "inline-more", inline)]
665 pub fn reserve(&mut self, additional
: usize) {
666 let hash_builder
= &self.hash_builder
;
668 .reserve(additional
, |x
| make_hash(hash_builder
, &x
.0));
671 /// Tries to reserve capacity for at least `additional` more elements to be inserted
672 /// in the given `HashMap<K,V>`. The collection may reserve more space to avoid
673 /// frequent reallocations.
677 /// If the capacity overflows, or the allocator reports a failure, then an error
683 /// use hashbrown::HashMap;
684 /// let mut map: HashMap<&str, isize> = HashMap::new();
685 /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
687 #[cfg_attr(feature = "inline-more", inline)]
688 pub fn try_reserve(&mut self, additional
: usize) -> Result
<(), TryReserveError
> {
689 let hash_builder
= &self.hash_builder
;
691 .try_reserve(additional
, |x
| make_hash(hash_builder
, &x
.0))
694 /// Shrinks the capacity of the map as much as possible. It will drop
695 /// down as much as possible while maintaining the internal rules
696 /// and possibly leaving some space in accordance with the resize policy.
701 /// use hashbrown::HashMap;
703 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
704 /// map.insert(1, 2);
705 /// map.insert(3, 4);
706 /// assert!(map.capacity() >= 100);
707 /// map.shrink_to_fit();
708 /// assert!(map.capacity() >= 2);
710 #[cfg_attr(feature = "inline-more", inline)]
711 pub fn shrink_to_fit(&mut self) {
712 let hash_builder
= &self.hash_builder
;
713 self.table
.shrink_to(0, |x
| make_hash(hash_builder
, &x
.0));
716 /// Shrinks the capacity of the map with a lower limit. It will drop
717 /// down no lower than the supplied limit while maintaining the internal rules
718 /// and possibly leaving some space in accordance with the resize policy.
720 /// This function does nothing if the current capacity is smaller than the
721 /// supplied minimum capacity.
726 /// use hashbrown::HashMap;
728 /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100);
729 /// map.insert(1, 2);
730 /// map.insert(3, 4);
731 /// assert!(map.capacity() >= 100);
732 /// map.shrink_to(10);
733 /// assert!(map.capacity() >= 10);
734 /// map.shrink_to(0);
735 /// assert!(map.capacity() >= 2);
736 /// map.shrink_to(10);
737 /// assert!(map.capacity() >= 2);
739 #[cfg_attr(feature = "inline-more", inline)]
740 pub fn shrink_to(&mut self, min_capacity
: usize) {
741 let hash_builder
= &self.hash_builder
;
743 .shrink_to(min_capacity
, |x
| make_hash(hash_builder
, &x
.0));
746 /// Gets the given key's corresponding entry in the map for in-place manipulation.
751 /// use hashbrown::HashMap;
753 /// let mut letters = HashMap::new();
755 /// for ch in "a short treatise on fungi".chars() {
756 /// let counter = letters.entry(ch).or_insert(0);
760 /// assert_eq!(letters[&'s'], 2);
761 /// assert_eq!(letters[&'t'], 3);
762 /// assert_eq!(letters[&'u'], 1);
763 /// assert_eq!(letters.get(&'y'), None);
765 #[cfg_attr(feature = "inline-more", inline)]
766 pub fn entry(&mut self, key
: K
) -> Entry
<'_
, K
, V
, S
> {
767 let hash
= make_hash(&self.hash_builder
, &key
);
768 if let Some(elem
) = self.table
.find(hash
, |q
| q
.0.eq(&key
)) {
769 Entry
::Occupied(OccupiedEntry
{
776 Entry
::Vacant(VacantEntry
{
784 /// Returns a reference to the value corresponding to the key.
786 /// The key may be any borrowed form of the map's key type, but
787 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
790 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
791 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
796 /// use hashbrown::HashMap;
798 /// let mut map = HashMap::new();
799 /// map.insert(1, "a");
800 /// assert_eq!(map.get(&1), Some(&"a"));
801 /// assert_eq!(map.get(&2), None);
804 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
809 // Avoid `Option::map` because it bloats LLVM IR.
810 match self.get_inner(k
) {
811 Some(&(_
, ref v
)) => Some(v
),
816 /// Returns the key-value pair corresponding to the supplied key.
818 /// The supplied key may be any borrowed form of the map's key type, but
819 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
822 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
823 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
828 /// use hashbrown::HashMap;
830 /// let mut map = HashMap::new();
831 /// map.insert(1, "a");
832 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
833 /// assert_eq!(map.get_key_value(&2), None);
836 pub fn get_key_value
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<(&K
, &V
)>
841 // Avoid `Option::map` because it bloats LLVM IR.
842 match self.get_inner(k
) {
843 Some(&(ref key
, ref value
)) => Some((key
, value
)),
849 fn get_inner
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&(K
, V
)>
854 let hash
= make_hash(&self.hash_builder
, k
);
855 self.table
.get(hash
, |x
| k
.eq(x
.0.borrow()))
858 /// Returns the key-value pair corresponding to the supplied key, with a mutable reference to value.
860 /// The supplied key may be any borrowed form of the map's key type, but
861 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
864 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
865 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
870 /// use hashbrown::HashMap;
872 /// let mut map = HashMap::new();
873 /// map.insert(1, "a");
874 /// let (k, v) = map.get_key_value_mut(&1).unwrap();
875 /// assert_eq!(k, &1);
876 /// assert_eq!(v, &mut "a");
878 /// assert_eq!(map.get_key_value_mut(&1), Some((&1, &mut "b")));
879 /// assert_eq!(map.get_key_value_mut(&2), None);
882 pub fn get_key_value_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<(&K
, &mut V
)>
887 // Avoid `Option::map` because it bloats LLVM IR.
888 match self.get_inner_mut(k
) {
889 Some(&mut (ref key
, ref mut value
)) => Some((key
, value
)),
894 /// Returns `true` if the map contains a value for the specified key.
896 /// The key may be any borrowed form of the map's key type, but
897 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
900 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
901 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
906 /// use hashbrown::HashMap;
908 /// let mut map = HashMap::new();
909 /// map.insert(1, "a");
910 /// assert_eq!(map.contains_key(&1), true);
911 /// assert_eq!(map.contains_key(&2), false);
913 #[cfg_attr(feature = "inline-more", inline)]
914 pub fn contains_key
<Q
: ?Sized
>(&self, k
: &Q
) -> bool
919 self.get_inner(k
).is_some()
922 /// Returns a mutable reference to the value corresponding to the key.
924 /// The key may be any borrowed form of the map's key type, but
925 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
928 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
929 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
934 /// use hashbrown::HashMap;
936 /// let mut map = HashMap::new();
937 /// map.insert(1, "a");
938 /// if let Some(x) = map.get_mut(&1) {
941 /// assert_eq!(map[&1], "b");
943 #[cfg_attr(feature = "inline-more", inline)]
944 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
949 // Avoid `Option::map` because it bloats LLVM IR.
950 match self.get_inner_mut(k
) {
951 Some(&mut (_
, ref mut v
)) => Some(v
),
957 fn get_inner_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut (K
, V
)>
962 let hash
= make_hash(&self.hash_builder
, k
);
963 self.table
.get_mut(hash
, |x
| k
.eq(x
.0.borrow()))
966 /// Inserts a key-value pair into the map.
968 /// If the map did not have this key present, [`None`] is returned.
970 /// If the map did have this key present, the value is updated, and the old
971 /// value is returned. The key is not updated, though; this matters for
972 /// types that can be `==` without being identical. See the [module-level
973 /// documentation] for more.
975 /// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
976 /// [module-level documentation]: index.html#insert-and-complex-keys
981 /// use hashbrown::HashMap;
983 /// let mut map = HashMap::new();
984 /// assert_eq!(map.insert(37, "a"), None);
985 /// assert_eq!(map.is_empty(), false);
987 /// map.insert(37, "b");
988 /// assert_eq!(map.insert(37, "c"), Some("b"));
989 /// assert_eq!(map[&37], "c");
991 #[cfg_attr(feature = "inline-more", inline)]
992 pub fn insert(&mut self, k
: K
, v
: V
) -> Option
<V
> {
993 let hash
= make_hash(&self.hash_builder
, &k
);
994 if let Some((_
, item
)) = self.table
.get_mut(hash
, |x
| k
.eq(&x
.0)) {
995 Some(mem
::replace(item
, v
))
997 let hash_builder
= &self.hash_builder
;
999 .insert(hash
, (k
, v
), |x
| make_hash(hash_builder
, &x
.0));
1004 /// Removes a key from the map, returning the value at the key if the key
1005 /// was previously in the map.
1007 /// The key may be any borrowed form of the map's key type, but
1008 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1011 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1012 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1017 /// use hashbrown::HashMap;
1019 /// let mut map = HashMap::new();
1020 /// map.insert(1, "a");
1021 /// assert_eq!(map.remove(&1), Some("a"));
1022 /// assert_eq!(map.remove(&1), None);
1024 #[cfg_attr(feature = "inline-more", inline)]
1025 pub fn remove
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<V
>
1030 // Avoid `Option::map` because it bloats LLVM IR.
1031 match self.remove_entry(k
) {
1032 Some((_
, v
)) => Some(v
),
1037 /// Removes a key from the map, returning the stored key and value if the
1038 /// key was previously in the map.
1040 /// The key may be any borrowed form of the map's key type, but
1041 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
1044 /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1045 /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1050 /// use hashbrown::HashMap;
1052 /// let mut map = HashMap::new();
1053 /// map.insert(1, "a");
1054 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1055 /// assert_eq!(map.remove(&1), None);
1057 #[cfg_attr(feature = "inline-more", inline)]
1058 pub fn remove_entry
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<(K
, V
)>
1063 let hash
= make_hash(&self.hash_builder
, &k
);
1064 self.table
.remove_entry(hash
, |x
| k
.eq(x
.0.borrow()))
1068 impl<K
, V
, S
> HashMap
<K
, V
, S
> {
1069 /// Creates a raw entry builder for the HashMap.
1071 /// Raw entries provide the lowest level of control for searching and
1072 /// manipulating a map. They must be manually initialized with a hash and
1073 /// then manually searched. After this, insertions into a vacant entry
1074 /// still require an owned key to be provided.
1076 /// Raw entries are useful for such exotic situations as:
1078 /// * Hash memoization
1079 /// * Deferring the creation of an owned key until it is known to be required
1080 /// * Using a search key that doesn't work with the Borrow trait
1081 /// * Using custom comparison logic without newtype wrappers
1083 /// Because raw entries provide much more low-level control, it's much easier
1084 /// to put the HashMap into an inconsistent state which, while memory-safe,
1085 /// will cause the map to produce seemingly random results. Higher-level and
1086 /// more foolproof APIs like `entry` should be preferred when possible.
1088 /// In particular, the hash used to initialized the raw entry must still be
1089 /// consistent with the hash of the key that is ultimately stored in the entry.
1090 /// This is because implementations of HashMap may need to recompute hashes
1091 /// when resizing, at which point only the keys are available.
1093 /// Raw entries give mutable access to the keys. This must not be used
1094 /// to modify how the key would compare or hash, as the map will not re-evaluate
1095 /// where the key should go, meaning the keys may become "lost" if their
1096 /// location does not reflect their state. For instance, if you change a key
1097 /// so that the map now contains keys which compare equal, search may start
1098 /// acting erratically, with two keys randomly masking each other. Implementations
1099 /// are free to assume this doesn't happen (within the limits of memory-safety).
1100 #[cfg_attr(feature = "inline-more", inline)]
1101 pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut
<'_
, K
, V
, S
> {
1102 RawEntryBuilderMut { map: self }
1105 /// Creates a raw immutable entry builder for the HashMap.
1107 /// Raw entries provide the lowest level of control for searching and
1108 /// manipulating a map. They must be manually initialized with a hash and
1109 /// then manually searched.
1111 /// This is useful for
1112 /// * Hash memoization
1113 /// * Using a search key that doesn't work with the Borrow trait
1114 /// * Using custom comparison logic without newtype wrappers
1116 /// Unless you are in such a situation, higher-level and more foolproof APIs like
1117 /// `get` should be preferred.
1119 /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
1120 #[cfg_attr(feature = "inline-more", inline)]
1121 pub fn raw_entry(&self) -> RawEntryBuilder
<'_
, K
, V
, S
> {
1122 RawEntryBuilder { map: self }
1126 impl<K
, V
, S
> PartialEq
for HashMap
<K
, V
, S
>
1132 fn eq(&self, other
: &Self) -> bool
{
1133 if self.len() != other
.len() {
1138 .all(|(key
, value
)| other
.get(key
).map_or(false, |v
| *value
== *v
))
1142 impl<K
, V
, S
> Eq
for HashMap
<K
, V
, S
>
1150 impl<K
, V
, S
> Debug
for HashMap
<K
, V
, S
>
1155 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1156 f
.debug_map().entries(self.iter()).finish()
1160 impl<K
, V
, S
> Default
for HashMap
<K
, V
, S
>
1164 /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
1165 #[cfg_attr(feature = "inline-more", inline)]
1166 fn default() -> Self {
1167 Self::with_hasher(Default
::default())
1171 impl<K
, Q
: ?Sized
, V
, S
> Index
<&Q
> for HashMap
<K
, V
, S
>
1173 K
: Eq
+ Hash
+ Borrow
<Q
>,
1179 /// Returns a reference to the value corresponding to the supplied key.
1183 /// Panics if the key is not present in the `HashMap`.
1184 #[cfg_attr(feature = "inline-more", inline)]
1185 fn index(&self, key
: &Q
) -> &V
{
1186 self.get(key
).expect("no entry found for key")
1190 /// An iterator over the entries of a `HashMap`.
1192 /// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
1193 /// documentation for more.
1195 /// [`iter`]: struct.HashMap.html#method.iter
1196 /// [`HashMap`]: struct.HashMap.html
1197 pub struct Iter
<'a
, K
, V
> {
1198 inner
: RawIter
<(K
, V
)>,
1199 marker
: PhantomData
<(&'a K
, &'a V
)>,
1202 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1203 impl<K
, V
> Clone
for Iter
<'_
, K
, V
> {
1204 #[cfg_attr(feature = "inline-more", inline)]
1205 fn clone(&self) -> Self {
1207 inner
: self.inner
.clone(),
1208 marker
: PhantomData
,
1213 impl<K
: Debug
, V
: Debug
> fmt
::Debug
for Iter
<'_
, K
, V
> {
1214 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1215 f
.debug_list().entries(self.clone()).finish()
1219 /// A mutable iterator over the entries of a `HashMap`.
1221 /// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
1222 /// documentation for more.
1224 /// [`iter_mut`]: struct.HashMap.html#method.iter_mut
1225 /// [`HashMap`]: struct.HashMap.html
1226 pub struct IterMut
<'a
, K
, V
> {
1227 inner
: RawIter
<(K
, V
)>,
1228 // To ensure invariance with respect to V
1229 marker
: PhantomData
<(&'a K
, &'a
mut V
)>,
1232 // We override the default Send impl which has K: Sync instead of K: Send. Both
1233 // are correct, but this one is more general since it allows keys which
1234 // implement Send but not Sync.
1235 unsafe impl<K
: Send
, V
: Send
> Send
for IterMut
<'_
, K
, V
> {}
1237 impl<K
, V
> IterMut
<'_
, K
, V
> {
1238 /// Returns a iterator of references over the remaining items.
1239 #[cfg_attr(feature = "inline-more", inline)]
1240 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1242 inner
: self.inner
.clone(),
1243 marker
: PhantomData
,
1248 /// An owning iterator over the entries of a `HashMap`.
1250 /// This `struct` is created by the [`into_iter`] method on [`HashMap`]
1251 /// (provided by the `IntoIterator` trait). See its documentation for more.
1253 /// [`into_iter`]: struct.HashMap.html#method.into_iter
1254 /// [`HashMap`]: struct.HashMap.html
1255 pub struct IntoIter
<K
, V
> {
1256 inner
: RawIntoIter
<(K
, V
)>,
1259 impl<K
, V
> IntoIter
<K
, V
> {
1260 /// Returns a iterator of references over the remaining items.
1261 #[cfg_attr(feature = "inline-more", inline)]
1262 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1264 inner
: self.inner
.iter(),
1265 marker
: PhantomData
,
1270 /// An iterator over the keys of a `HashMap`.
1272 /// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
1273 /// documentation for more.
1275 /// [`keys`]: struct.HashMap.html#method.keys
1276 /// [`HashMap`]: struct.HashMap.html
1277 pub struct Keys
<'a
, K
, V
> {
1278 inner
: Iter
<'a
, K
, V
>,
1281 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1282 impl<K
, V
> Clone
for Keys
<'_
, K
, V
> {
1283 #[cfg_attr(feature = "inline-more", inline)]
1284 fn clone(&self) -> Self {
1286 inner
: self.inner
.clone(),
1291 impl<K
: Debug
, V
> fmt
::Debug
for Keys
<'_
, K
, V
> {
1292 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1293 f
.debug_list().entries(self.clone()).finish()
1297 /// An iterator over the values of a `HashMap`.
1299 /// This `struct` is created by the [`values`] method on [`HashMap`]. See its
1300 /// documentation for more.
1302 /// [`values`]: struct.HashMap.html#method.values
1303 /// [`HashMap`]: struct.HashMap.html
1304 pub struct Values
<'a
, K
, V
> {
1305 inner
: Iter
<'a
, K
, V
>,
1308 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1309 impl<K
, V
> Clone
for Values
<'_
, K
, V
> {
1310 #[cfg_attr(feature = "inline-more", inline)]
1311 fn clone(&self) -> Self {
1313 inner
: self.inner
.clone(),
1318 impl<K
, V
: Debug
> fmt
::Debug
for Values
<'_
, K
, V
> {
1319 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1320 f
.debug_list().entries(self.clone()).finish()
1324 /// A draining iterator over the entries of a `HashMap`.
1326 /// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
1327 /// documentation for more.
1329 /// [`drain`]: struct.HashMap.html#method.drain
1330 /// [`HashMap`]: struct.HashMap.html
1331 pub struct Drain
<'a
, K
, V
> {
1332 inner
: RawDrain
<'a
, (K
, V
)>,
1335 impl<K
, V
> Drain
<'_
, K
, V
> {
1336 /// Returns a iterator of references over the remaining items.
1337 #[cfg_attr(feature = "inline-more", inline)]
1338 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1340 inner
: self.inner
.iter(),
1341 marker
: PhantomData
,
1346 /// A draining iterator over entries of a `HashMap` which don't satisfy the predicate `f`.
1348 /// This `struct` is created by the [`drain_filter`] method on [`HashMap`]. See its
1349 /// documentation for more.
1351 /// [`drain_filter`]: struct.HashMap.html#method.drain_filter
1352 /// [`HashMap`]: struct.HashMap.html
1353 pub struct DrainFilter
<'a
, K
, V
, F
>
1355 F
: FnMut(&K
, &mut V
) -> bool
,
1358 inner
: DrainFilterInner
<'a
, K
, V
>,
1361 impl<'a
, K
, V
, F
> Drop
for DrainFilter
<'a
, K
, V
, F
>
1363 F
: FnMut(&K
, &mut V
) -> bool
,
1365 #[cfg_attr(feature = "inline-more", inline)]
1366 fn drop(&mut self) {
1367 while let Some(item
) = self.next() {
1368 let guard
= ConsumeAllOnDrop(self);
1375 pub(super) struct ConsumeAllOnDrop
<'a
, T
: Iterator
>(pub &'a
mut T
);
1377 impl<T
: Iterator
> Drop
for ConsumeAllOnDrop
<'_
, T
> {
1378 #[cfg_attr(feature = "inline-more", inline)]
1379 fn drop(&mut self) {
1380 self.0.for_each
(drop
)
1384 impl<K
, V
, F
> Iterator
for DrainFilter
<'_
, K
, V
, F
>
1386 F
: FnMut(&K
, &mut V
) -> bool
,
1390 #[cfg_attr(feature = "inline-more", inline)]
1391 fn next(&mut self) -> Option
<Self::Item
> {
1392 self.inner
.next(&mut self.f
)
1396 fn size_hint(&self) -> (usize, Option
<usize>) {
1397 (0, self.inner
.iter
.size_hint().1)
1401 impl<K
, V
, F
> FusedIterator
for DrainFilter
<'_
, K
, V
, F
> where F
: FnMut(&K
, &mut V
) -> bool {}
1403 /// Portions of `DrainFilter` shared with `set::DrainFilter`
1404 pub(super) struct DrainFilterInner
<'a
, K
, V
> {
1405 pub iter
: RawIter
<(K
, V
)>,
1406 pub table
: &'a
mut RawTable
<(K
, V
)>,
1409 impl<K
, V
> DrainFilterInner
<'_
, K
, V
> {
1410 #[cfg_attr(feature = "inline-more", inline)]
1411 pub(super) fn next
<F
>(&mut self, f
: &mut F
) -> Option
<(K
, V
)>
1413 F
: FnMut(&K
, &mut V
) -> bool
,
1416 while let Some(item
) = self.iter
.next() {
1417 let &mut (ref key
, ref mut value
) = item
.as_mut();
1419 return Some(self.table
.remove(item
));
1427 /// A mutable iterator over the values of a `HashMap`.
1429 /// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
1430 /// documentation for more.
1432 /// [`values_mut`]: struct.HashMap.html#method.values_mut
1433 /// [`HashMap`]: struct.HashMap.html
1434 pub struct ValuesMut
<'a
, K
, V
> {
1435 inner
: IterMut
<'a
, K
, V
>,
1438 /// A builder for computing where in a [`HashMap`] a key-value pair would be stored.
1440 /// See the [`HashMap::raw_entry_mut`] docs for usage examples.
1442 /// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
1443 pub struct RawEntryBuilderMut
<'a
, K
, V
, S
> {
1444 map
: &'a
mut HashMap
<K
, V
, S
>,
1447 /// A view into a single entry in a map, which may either be vacant or occupied.
1449 /// This is a lower-level version of [`Entry`].
1451 /// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`],
1452 /// then calling one of the methods of that [`RawEntryBuilderMut`].
1454 /// [`HashMap`]: struct.HashMap.html
1455 /// [`Entry`]: enum.Entry.html
1456 /// [`raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
1457 /// [`RawEntryBuilderMut`]: struct.RawEntryBuilderMut.html
1458 pub enum RawEntryMut
<'a
, K
, V
, S
> {
1459 /// An occupied entry.
1460 Occupied(RawOccupiedEntryMut
<'a
, K
, V
, S
>),
1462 Vacant(RawVacantEntryMut
<'a
, K
, V
, S
>),
1465 /// A view into an occupied entry in a `HashMap`.
1466 /// It is part of the [`RawEntryMut`] enum.
1468 /// [`RawEntryMut`]: enum.RawEntryMut.html
1469 pub struct RawOccupiedEntryMut
<'a
, K
, V
, S
> {
1470 elem
: Bucket
<(K
, V
)>,
1471 table
: &'a
mut RawTable
<(K
, V
)>,
1472 hash_builder
: &'a S
,
1475 unsafe impl<K
, V
, S
> Send
for RawOccupiedEntryMut
<'_
, K
, V
, S
>
1482 unsafe impl<K
, V
, S
> Sync
for RawOccupiedEntryMut
<'_
, K
, V
, S
>
1490 /// A view into a vacant entry in a `HashMap`.
1491 /// It is part of the [`RawEntryMut`] enum.
1493 /// [`RawEntryMut`]: enum.RawEntryMut.html
1494 pub struct RawVacantEntryMut
<'a
, K
, V
, S
> {
1495 table
: &'a
mut RawTable
<(K
, V
)>,
1496 hash_builder
: &'a S
,
1499 /// A builder for computing where in a [`HashMap`] a key-value pair would be stored.
1501 /// See the [`HashMap::raw_entry`] docs for usage examples.
1503 /// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry
1504 pub struct RawEntryBuilder
<'a
, K
, V
, S
> {
1505 map
: &'a HashMap
<K
, V
, S
>,
1508 impl<'a
, K
, V
, S
> RawEntryBuilderMut
<'a
, K
, V
, S
> {
1509 /// Creates a `RawEntryMut` from the given key.
1510 #[cfg_attr(feature = "inline-more", inline)]
1511 #[allow(clippy::wrong_self_convention)]
1512 pub fn from_key
<Q
: ?Sized
>(self, k
: &Q
) -> RawEntryMut
<'a
, K
, V
, S
>
1518 let mut hasher
= self.map
.hash_builder
.build_hasher();
1519 k
.hash(&mut hasher
);
1520 self.from_key_hashed_nocheck(hasher
.finish(), k
)
1523 /// Creates a `RawEntryMut` from the given key and its hash.
1525 #[allow(clippy::wrong_self_convention)]
1526 pub fn from_key_hashed_nocheck
<Q
: ?Sized
>(self, hash
: u64, k
: &Q
) -> RawEntryMut
<'a
, K
, V
, S
>
1531 self.from_hash(hash
, |q
| q
.borrow().eq(k
))
1535 impl<'a
, K
, V
, S
> RawEntryBuilderMut
<'a
, K
, V
, S
> {
1536 /// Creates a `RawEntryMut` from the given hash.
1537 #[cfg_attr(feature = "inline-more", inline)]
1538 #[allow(clippy::wrong_self_convention)]
1539 pub fn from_hash
<F
>(self, hash
: u64, is_match
: F
) -> RawEntryMut
<'a
, K
, V
, S
>
1541 for<'b
> F
: FnMut(&'b K
) -> bool
,
1543 self.search(hash
, is_match
)
1546 #[cfg_attr(feature = "inline-more", inline)]
1547 fn search
<F
>(self, hash
: u64, mut is_match
: F
) -> RawEntryMut
<'a
, K
, V
, S
>
1549 for<'b
> F
: FnMut(&'b K
) -> bool
,
1551 match self.map
.table
.find(hash
, |(k
, _
)| is_match(k
)) {
1552 Some(elem
) => RawEntryMut
::Occupied(RawOccupiedEntryMut
{
1554 table
: &mut self.map
.table
,
1555 hash_builder
: &self.map
.hash_builder
,
1557 None
=> RawEntryMut
::Vacant(RawVacantEntryMut
{
1558 table
: &mut self.map
.table
,
1559 hash_builder
: &self.map
.hash_builder
,
1565 impl<'a
, K
, V
, S
> RawEntryBuilder
<'a
, K
, V
, S
> {
1566 /// Access an entry by key.
1567 #[cfg_attr(feature = "inline-more", inline)]
1568 #[allow(clippy::wrong_self_convention)]
1569 pub fn from_key
<Q
: ?Sized
>(self, k
: &Q
) -> Option
<(&'a K
, &'a V
)>
1575 let mut hasher
= self.map
.hash_builder
.build_hasher();
1576 k
.hash(&mut hasher
);
1577 self.from_key_hashed_nocheck(hasher
.finish(), k
)
1580 /// Access an entry by a key and its hash.
1581 #[cfg_attr(feature = "inline-more", inline)]
1582 #[allow(clippy::wrong_self_convention)]
1583 pub fn from_key_hashed_nocheck
<Q
: ?Sized
>(self, hash
: u64, k
: &Q
) -> Option
<(&'a K
, &'a V
)>
1588 self.from_hash(hash
, |q
| q
.borrow().eq(k
))
1591 #[cfg_attr(feature = "inline-more", inline)]
1592 fn search
<F
>(self, hash
: u64, mut is_match
: F
) -> Option
<(&'a K
, &'a V
)>
1594 F
: FnMut(&K
) -> bool
,
1596 match self.map
.table
.get(hash
, |(k
, _
)| is_match(k
)) {
1597 Some(&(ref key
, ref value
)) => Some((key
, value
)),
1602 /// Access an entry by hash.
1603 #[cfg_attr(feature = "inline-more", inline)]
1604 #[allow(clippy::wrong_self_convention)]
1605 pub fn from_hash
<F
>(self, hash
: u64, is_match
: F
) -> Option
<(&'a K
, &'a V
)>
1607 F
: FnMut(&K
) -> bool
,
1609 self.search(hash
, is_match
)
1613 impl<'a
, K
, V
, S
> RawEntryMut
<'a
, K
, V
, S
> {
1614 /// Sets the value of the entry, and returns a RawOccupiedEntryMut.
1619 /// use hashbrown::HashMap;
1621 /// let mut map: HashMap<&str, u32> = HashMap::new();
1622 /// let entry = map.raw_entry_mut().from_key("horseyland").insert("horseyland", 37);
1624 /// assert_eq!(entry.remove_entry(), ("horseyland", 37));
1626 #[cfg_attr(feature = "inline-more", inline)]
1627 pub fn insert(self, key
: K
, value
: V
) -> RawOccupiedEntryMut
<'a
, K
, V
, S
>
1633 RawEntryMut
::Occupied(mut entry
) => {
1634 entry
.insert(value
);
1637 RawEntryMut
::Vacant(entry
) => entry
.insert_entry(key
, value
),
1641 /// Ensures a value is in the entry by inserting the default if empty, and returns
1642 /// mutable references to the key and value in the entry.
1647 /// use hashbrown::HashMap;
1649 /// let mut map: HashMap<&str, u32> = HashMap::new();
1651 /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
1652 /// assert_eq!(map["poneyland"], 3);
1654 /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
1655 /// assert_eq!(map["poneyland"], 6);
1657 #[cfg_attr(feature = "inline-more", inline)]
1658 pub fn or_insert(self, default_key
: K
, default_val
: V
) -> (&'a
mut K
, &'a
mut V
)
1664 RawEntryMut
::Occupied(entry
) => entry
.into_key_value(),
1665 RawEntryMut
::Vacant(entry
) => entry
.insert(default_key
, default_val
),
1669 /// Ensures a value is in the entry by inserting the result of the default function if empty,
1670 /// and returns mutable references to the key and value in the entry.
1675 /// use hashbrown::HashMap;
1677 /// let mut map: HashMap<&str, String> = HashMap::new();
1679 /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
1680 /// ("poneyland", "hoho".to_string())
1683 /// assert_eq!(map["poneyland"], "hoho".to_string());
1685 #[cfg_attr(feature = "inline-more", inline)]
1686 pub fn or_insert_with
<F
>(self, default: F
) -> (&'a
mut K
, &'a
mut V
)
1688 F
: FnOnce() -> (K
, V
),
1693 RawEntryMut
::Occupied(entry
) => entry
.into_key_value(),
1694 RawEntryMut
::Vacant(entry
) => {
1695 let (k
, v
) = default();
1701 /// Provides in-place mutable access to an occupied entry before any
1702 /// potential inserts into the map.
1707 /// use hashbrown::HashMap;
1709 /// let mut map: HashMap<&str, u32> = HashMap::new();
1711 /// map.raw_entry_mut()
1712 /// .from_key("poneyland")
1713 /// .and_modify(|_k, v| { *v += 1 })
1714 /// .or_insert("poneyland", 42);
1715 /// assert_eq!(map["poneyland"], 42);
1717 /// map.raw_entry_mut()
1718 /// .from_key("poneyland")
1719 /// .and_modify(|_k, v| { *v += 1 })
1720 /// .or_insert("poneyland", 0);
1721 /// assert_eq!(map["poneyland"], 43);
1723 #[cfg_attr(feature = "inline-more", inline)]
1724 pub fn and_modify
<F
>(self, f
: F
) -> Self
1726 F
: FnOnce(&mut K
, &mut V
),
1729 RawEntryMut
::Occupied(mut entry
) => {
1731 let (k
, v
) = entry
.get_key_value_mut();
1734 RawEntryMut
::Occupied(entry
)
1736 RawEntryMut
::Vacant(entry
) => RawEntryMut
::Vacant(entry
),
1740 /// Provides shared access to the key and owned access to the value of
1741 /// an occupied entry and allows to replace or remove it based on the
1742 /// value of the returned option.
1747 /// use hashbrown::HashMap;
1748 /// use hashbrown::hash_map::RawEntryMut;
1750 /// let mut map: HashMap<&str, u32> = HashMap::new();
1753 /// .raw_entry_mut()
1754 /// .from_key("poneyland")
1755 /// .and_replace_entry_with(|_k, _v| panic!());
1758 /// RawEntryMut::Vacant(_) => {},
1759 /// RawEntryMut::Occupied(_) => panic!(),
1762 /// map.insert("poneyland", 42);
1765 /// .raw_entry_mut()
1766 /// .from_key("poneyland")
1767 /// .and_replace_entry_with(|k, v| {
1768 /// assert_eq!(k, &"poneyland");
1769 /// assert_eq!(v, 42);
1774 /// RawEntryMut::Occupied(e) => {
1775 /// assert_eq!(e.key(), &"poneyland");
1776 /// assert_eq!(e.get(), &43);
1778 /// RawEntryMut::Vacant(_) => panic!(),
1781 /// assert_eq!(map["poneyland"], 43);
1784 /// .raw_entry_mut()
1785 /// .from_key("poneyland")
1786 /// .and_replace_entry_with(|_k, _v| None);
1789 /// RawEntryMut::Vacant(_) => {},
1790 /// RawEntryMut::Occupied(_) => panic!(),
1793 /// assert!(!map.contains_key("poneyland"));
1795 #[cfg_attr(feature = "inline-more", inline)]
1796 pub fn and_replace_entry_with
<F
>(self, f
: F
) -> Self
1798 F
: FnOnce(&K
, V
) -> Option
<V
>,
1801 RawEntryMut
::Occupied(entry
) => entry
.replace_entry_with(f
),
1802 RawEntryMut
::Vacant(_
) => self,
1807 impl<'a
, K
, V
, S
> RawOccupiedEntryMut
<'a
, K
, V
, S
> {
1808 /// Gets a reference to the key in the entry.
1809 #[cfg_attr(feature = "inline-more", inline)]
1810 pub fn key(&self) -> &K
{
1811 unsafe { &self.elem.as_ref().0 }
1814 /// Gets a mutable reference to the key in the entry.
1815 #[cfg_attr(feature = "inline-more", inline)]
1816 pub fn key_mut(&mut self) -> &mut K
{
1817 unsafe { &mut self.elem.as_mut().0 }
1820 /// Converts the entry into a mutable reference to the key in the entry
1821 /// with a lifetime bound to the map itself.
1822 #[cfg_attr(feature = "inline-more", inline)]
1823 pub fn into_key(self) -> &'a
mut K
{
1824 unsafe { &mut self.elem.as_mut().0 }
1827 /// Gets a reference to the value in the entry.
1828 #[cfg_attr(feature = "inline-more", inline)]
1829 pub fn get(&self) -> &V
{
1830 unsafe { &self.elem.as_ref().1 }
1833 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1834 /// with a lifetime bound to the map itself.
1835 #[cfg_attr(feature = "inline-more", inline)]
1836 pub fn into_mut(self) -> &'a
mut V
{
1837 unsafe { &mut self.elem.as_mut().1 }
1840 /// Gets a mutable reference to the value in the entry.
1841 #[cfg_attr(feature = "inline-more", inline)]
1842 pub fn get_mut(&mut self) -> &mut V
{
1843 unsafe { &mut self.elem.as_mut().1 }
1846 /// Gets a reference to the key and value in the entry.
1847 #[cfg_attr(feature = "inline-more", inline)]
1848 pub fn get_key_value(&mut self) -> (&K
, &V
) {
1850 let &(ref key
, ref value
) = self.elem
.as_ref();
1855 /// Gets a mutable reference to the key and value in the entry.
1856 #[cfg_attr(feature = "inline-more", inline)]
1857 pub fn get_key_value_mut(&mut self) -> (&mut K
, &mut V
) {
1859 let &mut (ref mut key
, ref mut value
) = self.elem
.as_mut();
1864 /// Converts the OccupiedEntry into a mutable reference to the key and value in the entry
1865 /// with a lifetime bound to the map itself.
1866 #[cfg_attr(feature = "inline-more", inline)]
1867 pub fn into_key_value(self) -> (&'a
mut K
, &'a
mut V
) {
1869 let &mut (ref mut key
, ref mut value
) = self.elem
.as_mut();
1874 /// Sets the value of the entry, and returns the entry's old value.
1875 #[cfg_attr(feature = "inline-more", inline)]
1876 pub fn insert(&mut self, value
: V
) -> V
{
1877 mem
::replace(self.get_mut(), value
)
1880 /// Sets the value of the entry, and returns the entry's old value.
1881 #[cfg_attr(feature = "inline-more", inline)]
1882 pub fn insert_key(&mut self, key
: K
) -> K
{
1883 mem
::replace(self.key_mut(), key
)
1886 /// Takes the value out of the entry, and returns it.
1887 #[cfg_attr(feature = "inline-more", inline)]
1888 pub fn remove(self) -> V
{
1889 self.remove_entry().1
1892 /// Take the ownership of the key and value from the map.
1893 #[cfg_attr(feature = "inline-more", inline)]
1894 pub fn remove_entry(self) -> (K
, V
) {
1895 unsafe { self.table.remove(self.elem) }
1898 /// Provides shared access to the key and owned access to the value of
1899 /// the entry and allows to replace or remove it based on the
1900 /// value of the returned option.
1901 #[cfg_attr(feature = "inline-more", inline)]
1902 pub fn replace_entry_with
<F
>(self, f
: F
) -> RawEntryMut
<'a
, K
, V
, S
>
1904 F
: FnOnce(&K
, V
) -> Option
<V
>,
1907 let still_occupied
= self
1909 .replace_bucket_with(self.elem
.clone(), |(key
, value
)| {
1910 f(&key
, value
).map(|new_value
| (key
, new_value
))
1914 RawEntryMut
::Occupied(self)
1916 RawEntryMut
::Vacant(RawVacantEntryMut
{
1918 hash_builder
: self.hash_builder
,
1925 impl<'a
, K
, V
, S
> RawVacantEntryMut
<'a
, K
, V
, S
> {
1926 /// Sets the value of the entry with the VacantEntry's key,
1927 /// and returns a mutable reference to it.
1928 #[cfg_attr(feature = "inline-more", inline)]
1929 pub fn insert(self, key
: K
, value
: V
) -> (&'a
mut K
, &'a
mut V
)
1934 let mut hasher
= self.hash_builder
.build_hasher();
1935 key
.hash(&mut hasher
);
1936 self.insert_hashed_nocheck(hasher
.finish(), key
, value
)
1939 /// Sets the value of the entry with the VacantEntry's key,
1940 /// and returns a mutable reference to it.
1941 #[cfg_attr(feature = "inline-more", inline)]
1942 #[allow(clippy::shadow_unrelated)]
1943 pub fn insert_hashed_nocheck(self, hash
: u64, key
: K
, value
: V
) -> (&'a
mut K
, &'a
mut V
)
1948 let hash_builder
= self.hash_builder
;
1949 self.insert_with_hasher(hash
, key
, value
, |k
| make_hash(hash_builder
, k
))
1952 /// Set the value of an entry with a custom hasher function.
1953 #[cfg_attr(feature = "inline-more", inline)]
1954 pub fn insert_with_hasher
<H
>(
1960 ) -> (&'a
mut K
, &'a
mut V
)
1964 let &mut (ref mut k
, ref mut v
) = self
1966 .insert_entry(hash
, (key
, value
), |x
| hasher(&x
.0));
1970 #[cfg_attr(feature = "inline-more", inline)]
1971 fn insert_entry(self, key
: K
, value
: V
) -> RawOccupiedEntryMut
<'a
, K
, V
, S
>
1976 let hash_builder
= self.hash_builder
;
1977 let mut hasher
= self.hash_builder
.build_hasher();
1978 key
.hash(&mut hasher
);
1980 let elem
= self.table
.insert(hasher
.finish(), (key
, value
), |k
| {
1981 make_hash(hash_builder
, &k
.0)
1983 RawOccupiedEntryMut
{
1986 hash_builder
: self.hash_builder
,
1991 impl<K
, V
, S
> Debug
for RawEntryBuilderMut
<'_
, K
, V
, S
> {
1992 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1993 f
.debug_struct("RawEntryBuilder").finish()
1997 impl<K
: Debug
, V
: Debug
, S
> Debug
for RawEntryMut
<'_
, K
, V
, S
> {
1998 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2000 RawEntryMut
::Vacant(ref v
) => f
.debug_tuple("RawEntry").field(v
).finish(),
2001 RawEntryMut
::Occupied(ref o
) => f
.debug_tuple("RawEntry").field(o
).finish(),
2006 impl<K
: Debug
, V
: Debug
, S
> Debug
for RawOccupiedEntryMut
<'_
, K
, V
, S
> {
2007 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2008 f
.debug_struct("RawOccupiedEntryMut")
2009 .field("key", self.key())
2010 .field("value", self.get())
2015 impl<K
, V
, S
> Debug
for RawVacantEntryMut
<'_
, K
, V
, S
> {
2016 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2017 f
.debug_struct("RawVacantEntryMut").finish()
2021 impl<K
, V
, S
> Debug
for RawEntryBuilder
<'_
, K
, V
, S
> {
2022 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2023 f
.debug_struct("RawEntryBuilder").finish()
2027 /// A view into a single entry in a map, which may either be vacant or occupied.
2029 /// This `enum` is constructed from the [`entry`] method on [`HashMap`].
2031 /// [`HashMap`]: struct.HashMap.html
2032 /// [`entry`]: struct.HashMap.html#method.entry
2033 pub enum Entry
<'a
, K
, V
, S
> {
2034 /// An occupied entry.
2035 Occupied(OccupiedEntry
<'a
, K
, V
, S
>),
2038 Vacant(VacantEntry
<'a
, K
, V
, S
>),
2041 impl<K
: Debug
, V
: Debug
, S
> Debug
for Entry
<'_
, K
, V
, S
> {
2042 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2044 Entry
::Vacant(ref v
) => f
.debug_tuple("Entry").field(v
).finish(),
2045 Entry
::Occupied(ref o
) => f
.debug_tuple("Entry").field(o
).finish(),
2050 /// A view into an occupied entry in a `HashMap`.
2051 /// It is part of the [`Entry`] enum.
2053 /// [`Entry`]: enum.Entry.html
2054 pub struct OccupiedEntry
<'a
, K
, V
, S
> {
2057 elem
: Bucket
<(K
, V
)>,
2058 table
: &'a
mut HashMap
<K
, V
, S
>,
2061 unsafe impl<K
, V
, S
> Send
for OccupiedEntry
<'_
, K
, V
, S
>
2068 unsafe impl<K
, V
, S
> Sync
for OccupiedEntry
<'_
, K
, V
, S
>
2076 impl<K
: Debug
, V
: Debug
, S
> Debug
for OccupiedEntry
<'_
, K
, V
, S
> {
2077 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2078 f
.debug_struct("OccupiedEntry")
2079 .field("key", self.key())
2080 .field("value", self.get())
2085 /// A view into a vacant entry in a `HashMap`.
2086 /// It is part of the [`Entry`] enum.
2088 /// [`Entry`]: enum.Entry.html
2089 pub struct VacantEntry
<'a
, K
, V
, S
> {
2092 table
: &'a
mut HashMap
<K
, V
, S
>,
2095 impl<K
: Debug
, V
, S
> Debug
for VacantEntry
<'_
, K
, V
, S
> {
2096 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2097 f
.debug_tuple("VacantEntry").field(self.key()).finish()
2101 impl<'a
, K
, V
, S
> IntoIterator
for &'a HashMap
<K
, V
, S
> {
2102 type Item
= (&'a K
, &'a V
);
2103 type IntoIter
= Iter
<'a
, K
, V
>;
2105 #[cfg_attr(feature = "inline-more", inline)]
2106 fn into_iter(self) -> Iter
<'a
, K
, V
> {
2111 impl<'a
, K
, V
, S
> IntoIterator
for &'a
mut HashMap
<K
, V
, S
> {
2112 type Item
= (&'a K
, &'a
mut V
);
2113 type IntoIter
= IterMut
<'a
, K
, V
>;
2115 #[cfg_attr(feature = "inline-more", inline)]
2116 fn into_iter(self) -> IterMut
<'a
, K
, V
> {
2121 impl<K
, V
, S
> IntoIterator
for HashMap
<K
, V
, S
> {
2123 type IntoIter
= IntoIter
<K
, V
>;
2125 /// Creates a consuming iterator, that is, one that moves each key-value
2126 /// pair out of the map in arbitrary order. The map cannot be used after
2132 /// use hashbrown::HashMap;
2134 /// let mut map = HashMap::new();
2135 /// map.insert("a", 1);
2136 /// map.insert("b", 2);
2137 /// map.insert("c", 3);
2139 /// // Not possible with .iter()
2140 /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
2142 #[cfg_attr(feature = "inline-more", inline)]
2143 fn into_iter(self) -> IntoIter
<K
, V
> {
2145 inner
: self.table
.into_iter(),
2150 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
2151 type Item
= (&'a K
, &'a V
);
2153 #[cfg_attr(feature = "inline-more", inline)]
2154 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
2155 // Avoid `Option::map` because it bloats LLVM IR.
2156 match self.inner
.next() {
2164 #[cfg_attr(feature = "inline-more", inline)]
2165 fn size_hint(&self) -> (usize, Option
<usize>) {
2166 self.inner
.size_hint()
2169 impl<K
, V
> ExactSizeIterator
for Iter
<'_
, K
, V
> {
2170 #[cfg_attr(feature = "inline-more", inline)]
2171 fn len(&self) -> usize {
2176 impl<K
, V
> FusedIterator
for Iter
<'_
, K
, V
> {}
2178 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
2179 type Item
= (&'a K
, &'a
mut V
);
2181 #[cfg_attr(feature = "inline-more", inline)]
2182 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
2183 // Avoid `Option::map` because it bloats LLVM IR.
2184 match self.inner
.next() {
2187 Some((&r
.0, &mut r
.1))
2192 #[cfg_attr(feature = "inline-more", inline)]
2193 fn size_hint(&self) -> (usize, Option
<usize>) {
2194 self.inner
.size_hint()
2197 impl<K
, V
> ExactSizeIterator
for IterMut
<'_
, K
, V
> {
2198 #[cfg_attr(feature = "inline-more", inline)]
2199 fn len(&self) -> usize {
2203 impl<K
, V
> FusedIterator
for IterMut
<'_
, K
, V
> {}
2205 impl<K
, V
> fmt
::Debug
for IterMut
<'_
, K
, V
>
2210 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2211 f
.debug_list().entries(self.iter()).finish()
2215 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
2218 #[cfg_attr(feature = "inline-more", inline)]
2219 fn next(&mut self) -> Option
<(K
, V
)> {
2222 #[cfg_attr(feature = "inline-more", inline)]
2223 fn size_hint(&self) -> (usize, Option
<usize>) {
2224 self.inner
.size_hint()
2227 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
2228 #[cfg_attr(feature = "inline-more", inline)]
2229 fn len(&self) -> usize {
2233 impl<K
, V
> FusedIterator
for IntoIter
<K
, V
> {}
2235 impl<K
: Debug
, V
: Debug
> fmt
::Debug
for IntoIter
<K
, V
> {
2236 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2237 f
.debug_list().entries(self.iter()).finish()
2241 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
2244 #[cfg_attr(feature = "inline-more", inline)]
2245 fn next(&mut self) -> Option
<&'a K
> {
2246 // Avoid `Option::map` because it bloats LLVM IR.
2247 match self.inner
.next() {
2248 Some((k
, _
)) => Some(k
),
2252 #[cfg_attr(feature = "inline-more", inline)]
2253 fn size_hint(&self) -> (usize, Option
<usize>) {
2254 self.inner
.size_hint()
2257 impl<K
, V
> ExactSizeIterator
for Keys
<'_
, K
, V
> {
2258 #[cfg_attr(feature = "inline-more", inline)]
2259 fn len(&self) -> usize {
2263 impl<K
, V
> FusedIterator
for Keys
<'_
, K
, V
> {}
2265 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
2268 #[cfg_attr(feature = "inline-more", inline)]
2269 fn next(&mut self) -> Option
<&'a V
> {
2270 // Avoid `Option::map` because it bloats LLVM IR.
2271 match self.inner
.next() {
2272 Some((_
, v
)) => Some(v
),
2276 #[cfg_attr(feature = "inline-more", inline)]
2277 fn size_hint(&self) -> (usize, Option
<usize>) {
2278 self.inner
.size_hint()
2281 impl<K
, V
> ExactSizeIterator
for Values
<'_
, K
, V
> {
2282 #[cfg_attr(feature = "inline-more", inline)]
2283 fn len(&self) -> usize {
2287 impl<K
, V
> FusedIterator
for Values
<'_
, K
, V
> {}
2289 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
2290 type Item
= &'a
mut V
;
2292 #[cfg_attr(feature = "inline-more", inline)]
2293 fn next(&mut self) -> Option
<&'a
mut V
> {
2294 // Avoid `Option::map` because it bloats LLVM IR.
2295 match self.inner
.next() {
2296 Some((_
, v
)) => Some(v
),
2300 #[cfg_attr(feature = "inline-more", inline)]
2301 fn size_hint(&self) -> (usize, Option
<usize>) {
2302 self.inner
.size_hint()
2305 impl<K
, V
> ExactSizeIterator
for ValuesMut
<'_
, K
, V
> {
2306 #[cfg_attr(feature = "inline-more", inline)]
2307 fn len(&self) -> usize {
2311 impl<K
, V
> FusedIterator
for ValuesMut
<'_
, K
, V
> {}
2313 impl<K
, V
> fmt
::Debug
for ValuesMut
<'_
, K
, V
>
2318 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2319 f
.debug_list().entries(self.inner
.iter()).finish()
2323 impl<'a
, K
, V
> Iterator
for Drain
<'a
, K
, V
> {
2326 #[cfg_attr(feature = "inline-more", inline)]
2327 fn next(&mut self) -> Option
<(K
, V
)> {
2330 #[cfg_attr(feature = "inline-more", inline)]
2331 fn size_hint(&self) -> (usize, Option
<usize>) {
2332 self.inner
.size_hint()
2335 impl<K
, V
> ExactSizeIterator
for Drain
<'_
, K
, V
> {
2336 #[cfg_attr(feature = "inline-more", inline)]
2337 fn len(&self) -> usize {
2341 impl<K
, V
> FusedIterator
for Drain
<'_
, K
, V
> {}
2343 impl<K
, V
> fmt
::Debug
for Drain
<'_
, K
, V
>
2348 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2349 f
.debug_list().entries(self.iter()).finish()
2353 impl<'a
, K
, V
, S
> Entry
<'a
, K
, V
, S
> {
2354 /// Sets the value of the entry, and returns an OccupiedEntry.
2359 /// use hashbrown::HashMap;
2361 /// let mut map: HashMap<&str, u32> = HashMap::new();
2362 /// let entry = map.entry("horseyland").insert(37);
2364 /// assert_eq!(entry.key(), &"horseyland");
2366 #[cfg_attr(feature = "inline-more", inline)]
2367 pub fn insert(self, value
: V
) -> OccupiedEntry
<'a
, K
, V
, S
>
2373 Entry
::Occupied(mut entry
) => {
2374 entry
.insert(value
);
2377 Entry
::Vacant(entry
) => entry
.insert_entry(value
),
2381 /// Ensures a value is in the entry by inserting the default if empty, and returns
2382 /// a mutable reference to the value in the entry.
2387 /// use hashbrown::HashMap;
2389 /// let mut map: HashMap<&str, u32> = HashMap::new();
2391 /// map.entry("poneyland").or_insert(3);
2392 /// assert_eq!(map["poneyland"], 3);
2394 /// *map.entry("poneyland").or_insert(10) *= 2;
2395 /// assert_eq!(map["poneyland"], 6);
2397 #[cfg_attr(feature = "inline-more", inline)]
2398 pub fn or_insert(self, default: V
) -> &'a
mut V
2404 Entry
::Occupied(entry
) => entry
.into_mut(),
2405 Entry
::Vacant(entry
) => entry
.insert(default),
2409 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2410 /// and returns a mutable reference to the value in the entry.
2415 /// use hashbrown::HashMap;
2417 /// let mut map: HashMap<&str, String> = HashMap::new();
2418 /// let s = "hoho".to_string();
2420 /// map.entry("poneyland").or_insert_with(|| s);
2422 /// assert_eq!(map["poneyland"], "hoho".to_string());
2424 #[cfg_attr(feature = "inline-more", inline)]
2425 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
2431 Entry
::Occupied(entry
) => entry
.into_mut(),
2432 Entry
::Vacant(entry
) => entry
.insert(default()),
2436 /// Ensures a value is in the entry by inserting, if empty, the result of the default function,
2437 /// which takes the key as its argument, and returns a mutable reference to the value in the
2443 /// use hashbrown::HashMap;
2445 /// let mut map: HashMap<&str, usize> = HashMap::new();
2447 /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
2449 /// assert_eq!(map["poneyland"], 9);
2451 #[cfg_attr(feature = "inline-more", inline)]
2452 pub fn or_insert_with_key
<F
: FnOnce(&K
) -> V
>(self, default: F
) -> &'a
mut V
2458 Entry
::Occupied(entry
) => entry
.into_mut(),
2459 Entry
::Vacant(entry
) => {
2460 let value
= default(entry
.key());
2466 /// Returns a reference to this entry's key.
2471 /// use hashbrown::HashMap;
2473 /// let mut map: HashMap<&str, u32> = HashMap::new();
2474 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2476 #[cfg_attr(feature = "inline-more", inline)]
2477 pub fn key(&self) -> &K
{
2479 Entry
::Occupied(ref entry
) => entry
.key(),
2480 Entry
::Vacant(ref entry
) => entry
.key(),
2484 /// Provides in-place mutable access to an occupied entry before any
2485 /// potential inserts into the map.
2490 /// use hashbrown::HashMap;
2492 /// let mut map: HashMap<&str, u32> = HashMap::new();
2494 /// map.entry("poneyland")
2495 /// .and_modify(|e| { *e += 1 })
2497 /// assert_eq!(map["poneyland"], 42);
2499 /// map.entry("poneyland")
2500 /// .and_modify(|e| { *e += 1 })
2502 /// assert_eq!(map["poneyland"], 43);
2504 #[cfg_attr(feature = "inline-more", inline)]
2505 pub fn and_modify
<F
>(self, f
: F
) -> Self
2510 Entry
::Occupied(mut entry
) => {
2512 Entry
::Occupied(entry
)
2514 Entry
::Vacant(entry
) => Entry
::Vacant(entry
),
2518 /// Provides shared access to the key and owned access to the value of
2519 /// an occupied entry and allows to replace or remove it based on the
2520 /// value of the returned option.
2525 /// use hashbrown::HashMap;
2526 /// use hashbrown::hash_map::Entry;
2528 /// let mut map: HashMap<&str, u32> = HashMap::new();
2531 /// .entry("poneyland")
2532 /// .and_replace_entry_with(|_k, _v| panic!());
2535 /// Entry::Vacant(e) => {
2536 /// assert_eq!(e.key(), &"poneyland");
2538 /// Entry::Occupied(_) => panic!(),
2541 /// map.insert("poneyland", 42);
2544 /// .entry("poneyland")
2545 /// .and_replace_entry_with(|k, v| {
2546 /// assert_eq!(k, &"poneyland");
2547 /// assert_eq!(v, 42);
2552 /// Entry::Occupied(e) => {
2553 /// assert_eq!(e.key(), &"poneyland");
2554 /// assert_eq!(e.get(), &43);
2556 /// Entry::Vacant(_) => panic!(),
2559 /// assert_eq!(map["poneyland"], 43);
2562 /// .entry("poneyland")
2563 /// .and_replace_entry_with(|_k, _v| None);
2566 /// Entry::Vacant(e) => assert_eq!(e.key(), &"poneyland"),
2567 /// Entry::Occupied(_) => panic!(),
2570 /// assert!(!map.contains_key("poneyland"));
2572 #[cfg_attr(feature = "inline-more", inline)]
2573 pub fn and_replace_entry_with
<F
>(self, f
: F
) -> Self
2575 F
: FnOnce(&K
, V
) -> Option
<V
>,
2578 Entry
::Occupied(entry
) => entry
.replace_entry_with(f
),
2579 Entry
::Vacant(_
) => self,
2584 impl<'a
, K
, V
: Default
, S
> Entry
<'a
, K
, V
, S
> {
2585 /// Ensures a value is in the entry by inserting the default value if empty,
2586 /// and returns a mutable reference to the value in the entry.
2591 /// use hashbrown::HashMap;
2593 /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
2594 /// map.entry("poneyland").or_default();
2596 /// assert_eq!(map["poneyland"], None);
2598 #[cfg_attr(feature = "inline-more", inline)]
2599 pub fn or_default(self) -> &'a
mut V
2605 Entry
::Occupied(entry
) => entry
.into_mut(),
2606 Entry
::Vacant(entry
) => entry
.insert(Default
::default()),
2611 impl<'a
, K
, V
, S
> OccupiedEntry
<'a
, K
, V
, S
> {
2612 /// Gets a reference to the key in the entry.
2617 /// use hashbrown::HashMap;
2619 /// let mut map: HashMap<&str, u32> = HashMap::new();
2620 /// map.entry("poneyland").or_insert(12);
2621 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2623 #[cfg_attr(feature = "inline-more", inline)]
2624 pub fn key(&self) -> &K
{
2625 unsafe { &self.elem.as_ref().0 }
2628 /// Take the ownership of the key and value from the map.
2633 /// use hashbrown::HashMap;
2634 /// use hashbrown::hash_map::Entry;
2636 /// let mut map: HashMap<&str, u32> = HashMap::new();
2637 /// map.entry("poneyland").or_insert(12);
2639 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2640 /// // We delete the entry from the map.
2641 /// o.remove_entry();
2644 /// assert_eq!(map.contains_key("poneyland"), false);
2646 #[cfg_attr(feature = "inline-more", inline)]
2647 pub fn remove_entry(self) -> (K
, V
) {
2648 unsafe { self.table.table.remove(self.elem) }
2651 /// Gets a reference to the value in the entry.
2656 /// use hashbrown::HashMap;
2657 /// use hashbrown::hash_map::Entry;
2659 /// let mut map: HashMap<&str, u32> = HashMap::new();
2660 /// map.entry("poneyland").or_insert(12);
2662 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2663 /// assert_eq!(o.get(), &12);
2666 #[cfg_attr(feature = "inline-more", inline)]
2667 pub fn get(&self) -> &V
{
2668 unsafe { &self.elem.as_ref().1 }
2671 /// Gets a mutable reference to the value in the entry.
2673 /// If you need a reference to the `OccupiedEntry` which may outlive the
2674 /// destruction of the `Entry` value, see [`into_mut`].
2676 /// [`into_mut`]: #method.into_mut
2681 /// use hashbrown::HashMap;
2682 /// use hashbrown::hash_map::Entry;
2684 /// let mut map: HashMap<&str, u32> = HashMap::new();
2685 /// map.entry("poneyland").or_insert(12);
2687 /// assert_eq!(map["poneyland"], 12);
2688 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2689 /// *o.get_mut() += 10;
2690 /// assert_eq!(*o.get(), 22);
2692 /// // We can use the same Entry multiple times.
2693 /// *o.get_mut() += 2;
2696 /// assert_eq!(map["poneyland"], 24);
2698 #[cfg_attr(feature = "inline-more", inline)]
2699 pub fn get_mut(&mut self) -> &mut V
{
2700 unsafe { &mut self.elem.as_mut().1 }
2703 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
2704 /// with a lifetime bound to the map itself.
2706 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2708 /// [`get_mut`]: #method.get_mut
2713 /// use hashbrown::HashMap;
2714 /// use hashbrown::hash_map::Entry;
2716 /// let mut map: HashMap<&str, u32> = HashMap::new();
2717 /// map.entry("poneyland").or_insert(12);
2719 /// assert_eq!(map["poneyland"], 12);
2720 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2721 /// *o.into_mut() += 10;
2724 /// assert_eq!(map["poneyland"], 22);
2726 #[cfg_attr(feature = "inline-more", inline)]
2727 pub fn into_mut(self) -> &'a
mut V
{
2728 unsafe { &mut self.elem.as_mut().1 }
2731 /// Sets the value of the entry, and returns the entry's old value.
2736 /// use hashbrown::HashMap;
2737 /// use hashbrown::hash_map::Entry;
2739 /// let mut map: HashMap<&str, u32> = HashMap::new();
2740 /// map.entry("poneyland").or_insert(12);
2742 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2743 /// assert_eq!(o.insert(15), 12);
2746 /// assert_eq!(map["poneyland"], 15);
2748 #[cfg_attr(feature = "inline-more", inline)]
2749 pub fn insert(&mut self, mut value
: V
) -> V
{
2750 let old_value
= self.get_mut();
2751 mem
::swap(&mut value
, old_value
);
2755 /// Takes the value out of the entry, and returns it.
2760 /// use hashbrown::HashMap;
2761 /// use hashbrown::hash_map::Entry;
2763 /// let mut map: HashMap<&str, u32> = HashMap::new();
2764 /// map.entry("poneyland").or_insert(12);
2766 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2767 /// assert_eq!(o.remove(), 12);
2770 /// assert_eq!(map.contains_key("poneyland"), false);
2772 #[cfg_attr(feature = "inline-more", inline)]
2773 pub fn remove(self) -> V
{
2774 self.remove_entry().1
2777 /// Replaces the entry, returning the old key and value. The new key in the hash map will be
2778 /// the key used to create this entry.
2783 /// use hashbrown::hash_map::{Entry, HashMap};
2784 /// use std::rc::Rc;
2786 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2787 /// map.insert(Rc::new("Stringthing".to_string()), 15);
2789 /// let my_key = Rc::new("Stringthing".to_string());
2791 /// if let Entry::Occupied(entry) = map.entry(my_key) {
2792 /// // Also replace the key with a handle to our other key.
2793 /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
2797 #[cfg_attr(feature = "inline-more", inline)]
2798 pub fn replace_entry(self, value
: V
) -> (K
, V
) {
2799 let entry
= unsafe { self.elem.as_mut() }
;
2801 let old_key
= mem
::replace(&mut entry
.0, self.key
.unwrap());
2802 let old_value
= mem
::replace(&mut entry
.1, value
);
2804 (old_key
, old_value
)
2807 /// Replaces the key in the hash map with the key used to create this entry.
2812 /// use hashbrown::hash_map::{Entry, HashMap};
2813 /// use std::rc::Rc;
2815 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
2816 /// let mut known_strings: Vec<Rc<String>> = Vec::new();
2818 /// // Initialise known strings, run program, etc.
2820 /// reclaim_memory(&mut map, &known_strings);
2822 /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) {
2823 /// for s in known_strings {
2824 /// if let Entry::Occupied(entry) = map.entry(s.clone()) {
2825 /// // Replaces the entry's key with our version of it in `known_strings`.
2826 /// entry.replace_key();
2831 #[cfg_attr(feature = "inline-more", inline)]
2832 pub fn replace_key(self) -> K
{
2833 let entry
= unsafe { self.elem.as_mut() }
;
2834 mem
::replace(&mut entry
.0, self.key
.unwrap())
2837 /// Provides shared access to the key and owned access to the value of
2838 /// the entry and allows to replace or remove it based on the
2839 /// value of the returned option.
2844 /// use hashbrown::HashMap;
2845 /// use hashbrown::hash_map::Entry;
2847 /// let mut map: HashMap<&str, u32> = HashMap::new();
2848 /// map.insert("poneyland", 42);
2850 /// let entry = match map.entry("poneyland") {
2851 /// Entry::Occupied(e) => {
2852 /// e.replace_entry_with(|k, v| {
2853 /// assert_eq!(k, &"poneyland");
2854 /// assert_eq!(v, 42);
2858 /// Entry::Vacant(_) => panic!(),
2862 /// Entry::Occupied(e) => {
2863 /// assert_eq!(e.key(), &"poneyland");
2864 /// assert_eq!(e.get(), &43);
2866 /// Entry::Vacant(_) => panic!(),
2869 /// assert_eq!(map["poneyland"], 43);
2871 /// let entry = match map.entry("poneyland") {
2872 /// Entry::Occupied(e) => e.replace_entry_with(|_k, _v| None),
2873 /// Entry::Vacant(_) => panic!(),
2877 /// Entry::Vacant(e) => {
2878 /// assert_eq!(e.key(), &"poneyland");
2880 /// Entry::Occupied(_) => panic!(),
2883 /// assert!(!map.contains_key("poneyland"));
2885 #[cfg_attr(feature = "inline-more", inline)]
2886 pub fn replace_entry_with
<F
>(self, f
: F
) -> Entry
<'a
, K
, V
, S
>
2888 F
: FnOnce(&K
, V
) -> Option
<V
>,
2891 let mut spare_key
= None
;
2895 .replace_bucket_with(self.elem
.clone(), |(key
, value
)| {
2896 if let Some(new_value
) = f(&key
, value
) {
2897 Some((key
, new_value
))
2899 spare_key
= Some(key
);
2904 if let Some(key
) = spare_key
{
2905 Entry
::Vacant(VacantEntry
{
2911 Entry
::Occupied(self)
2917 impl<'a
, K
, V
, S
> VacantEntry
<'a
, K
, V
, S
> {
2918 /// Gets a reference to the key that would be used when inserting a value
2919 /// through the `VacantEntry`.
2924 /// use hashbrown::HashMap;
2926 /// let mut map: HashMap<&str, u32> = HashMap::new();
2927 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2929 #[cfg_attr(feature = "inline-more", inline)]
2930 pub fn key(&self) -> &K
{
2934 /// Take ownership of the key.
2939 /// use hashbrown::HashMap;
2940 /// use hashbrown::hash_map::Entry;
2942 /// let mut map: HashMap<&str, u32> = HashMap::new();
2944 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2948 #[cfg_attr(feature = "inline-more", inline)]
2949 pub fn into_key(self) -> K
{
2953 /// Sets the value of the entry with the VacantEntry's key,
2954 /// and returns a mutable reference to it.
2959 /// use hashbrown::HashMap;
2960 /// use hashbrown::hash_map::Entry;
2962 /// let mut map: HashMap<&str, u32> = HashMap::new();
2964 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2967 /// assert_eq!(map["poneyland"], 37);
2969 #[cfg_attr(feature = "inline-more", inline)]
2970 pub fn insert(self, value
: V
) -> &'a
mut V
2975 let hash_builder
= &self.table
.hash_builder
;
2976 let table
= &mut self.table
.table
;
2977 let entry
= table
.insert_entry(self.hash
, (self.key
, value
), |x
| {
2978 make_hash(hash_builder
, &x
.0)
2983 #[cfg_attr(feature = "inline-more", inline)]
2984 fn insert_entry(self, value
: V
) -> OccupiedEntry
<'a
, K
, V
, S
>
2989 let hash_builder
= &self.table
.hash_builder
;
2990 let elem
= self.table
.table
.insert(self.hash
, (self.key
, value
), |x
| {
2991 make_hash(hash_builder
, &x
.0)
3002 impl<K
, V
, S
> FromIterator
<(K
, V
)> for HashMap
<K
, V
, S
>
3005 S
: BuildHasher
+ Default
,
3007 #[cfg_attr(feature = "inline-more", inline)]
3008 fn from_iter
<T
: IntoIterator
<Item
= (K
, V
)>>(iter
: T
) -> Self {
3009 let iter
= iter
.into_iter();
3010 let mut map
= Self::with_capacity_and_hasher(iter
.size_hint().0, S
::default());
3011 iter
.for_each(|(k
, v
)| {
3018 /// Inserts all new key-values from the iterator and replaces values with existing
3019 /// keys with new values returned from the iterator.
3020 impl<K
, V
, S
> Extend
<(K
, V
)> for HashMap
<K
, V
, S
>
3025 #[cfg_attr(feature = "inline-more", inline)]
3026 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
3027 // Keys may be already present or show multiple times in the iterator.
3028 // Reserve the entire hint lower bound if the map is empty.
3029 // Otherwise reserve half the hint (rounded up), so the map
3030 // will only resize twice in the worst case.
3031 let iter
= iter
.into_iter();
3032 let reserve
= if self.is_empty() {
3035 (iter
.size_hint().0 + 1) / 2
3037 self.reserve(reserve
);
3038 iter
.for_each(move |(k
, v
)| {
3044 #[cfg(feature = "nightly")]
3045 fn extend_one(&mut self, (k
, v
): (K
, V
)) {
3050 #[cfg(feature = "nightly")]
3051 fn extend_reserve(&mut self, additional
: usize) {
3052 // Keys may be already present or show multiple times in the iterator.
3053 // Reserve the entire hint lower bound if the map is empty.
3054 // Otherwise reserve half the hint (rounded up), so the map
3055 // will only resize twice in the worst case.
3056 let reserve
= if self.is_empty() {
3059 (additional
+ 1) / 2
3061 self.reserve(reserve
);
3065 impl<'a
, K
, V
, S
> Extend
<(&'a K
, &'a V
)> for HashMap
<K
, V
, S
>
3067 K
: Eq
+ Hash
+ Copy
,
3071 #[cfg_attr(feature = "inline-more", inline)]
3072 fn extend
<T
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: T
) {
3073 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
3077 #[cfg(feature = "nightly")]
3078 fn extend_one(&mut self, (k
, v
): (&'a K
, &'a V
)) {
3079 self.insert(*k
, *v
);
3083 #[cfg(feature = "nightly")]
3084 fn extend_reserve(&mut self, additional
: usize) {
3085 Extend
::<(K
, V
)>::extend_reserve(self, additional
);
3090 fn assert_covariance() {
3091 fn map_key
<'new
>(v
: HashMap
<&'
static str, u8>) -> HashMap
<&'new
str, u8> {
3094 fn map_val
<'new
>(v
: HashMap
<u8, &'
static str>) -> HashMap
<u8, &'new
str> {
3097 fn iter_key
<'a
, 'new
>(v
: Iter
<'a
, &'
static str, u8>) -> Iter
<'a
, &'new
str, u8> {
3100 fn iter_val
<'a
, 'new
>(v
: Iter
<'a
, u8, &'
static str>) -> Iter
<'a
, u8, &'new
str> {
3103 fn into_iter_key
<'new
>(v
: IntoIter
<&'
static str, u8>) -> IntoIter
<&'new
str, u8> {
3106 fn into_iter_val
<'new
>(v
: IntoIter
<u8, &'
static str>) -> IntoIter
<u8, &'new
str> {
3109 fn keys_key
<'a
, 'new
>(v
: Keys
<'a
, &'
static str, u8>) -> Keys
<'a
, &'new
str, u8> {
3112 fn keys_val
<'a
, 'new
>(v
: Keys
<'a
, u8, &'
static str>) -> Keys
<'a
, u8, &'new
str> {
3115 fn values_key
<'a
, 'new
>(v
: Values
<'a
, &'
static str, u8>) -> Values
<'a
, &'new
str, u8> {
3118 fn values_val
<'a
, 'new
>(v
: Values
<'a
, u8, &'
static str>) -> Values
<'a
, u8, &'new
str> {
3122 d
: Drain
<'
static, &'
static str, &'
static str>,
3123 ) -> Drain
<'new
, &'new
str, &'new
str> {
3130 use super::DefaultHashBuilder
;
3131 use super::Entry
::{Occupied, Vacant}
;
3132 use super::{HashMap, RawEntryMut}
;
3133 use crate::TryReserveError
::*;
3134 use rand
::{rngs::SmallRng, Rng, SeedableRng}
;
3135 use std
::cell
::RefCell
;
3140 fn test_zero_capacities() {
3141 type HM
= HashMap
<i32, i32>;
3144 assert_eq
!(m
.capacity(), 0);
3146 let m
= HM
::default();
3147 assert_eq
!(m
.capacity(), 0);
3149 let m
= HM
::with_hasher(DefaultHashBuilder
::default());
3150 assert_eq
!(m
.capacity(), 0);
3152 let m
= HM
::with_capacity(0);
3153 assert_eq
!(m
.capacity(), 0);
3155 let m
= HM
::with_capacity_and_hasher(0, DefaultHashBuilder
::default());
3156 assert_eq
!(m
.capacity(), 0);
3158 let mut m
= HM
::new();
3164 assert_eq
!(m
.capacity(), 0);
3166 let mut m
= HM
::new();
3168 assert_eq
!(m
.capacity(), 0);
3172 fn test_create_capacity_zero() {
3173 let mut m
= HashMap
::with_capacity(0);
3175 assert
!(m
.insert(1, 1).is_none());
3177 assert
!(m
.contains_key(&1));
3178 assert
!(!m
.contains_key(&0));
3183 let mut m
= HashMap
::new();
3184 assert_eq
!(m
.len(), 0);
3185 assert
!(m
.insert(1, 2).is_none());
3186 assert_eq
!(m
.len(), 1);
3187 assert
!(m
.insert(2, 4).is_none());
3188 assert_eq
!(m
.len(), 2);
3189 assert_eq
!(*m
.get(&1).unwrap(), 2);
3190 assert_eq
!(*m
.get(&2).unwrap(), 4);
3195 let mut m
= HashMap
::new();
3196 assert_eq
!(m
.len(), 0);
3197 assert
!(m
.insert(1, 2).is_none());
3198 assert_eq
!(m
.len(), 1);
3199 assert
!(m
.insert(2, 4).is_none());
3200 assert_eq
!(m
.len(), 2);
3202 assert_eq
!(*m2
.get(&1).unwrap(), 2);
3203 assert_eq
!(*m2
.get(&2).unwrap(), 4);
3204 assert_eq
!(m2
.len(), 2);
3208 fn test_clone_from() {
3209 let mut m
= HashMap
::new();
3210 let mut m2
= HashMap
::new();
3211 assert_eq
!(m
.len(), 0);
3212 assert
!(m
.insert(1, 2).is_none());
3213 assert_eq
!(m
.len(), 1);
3214 assert
!(m
.insert(2, 4).is_none());
3215 assert_eq
!(m
.len(), 2);
3217 assert_eq
!(*m2
.get(&1).unwrap(), 2);
3218 assert_eq
!(*m2
.get(&2).unwrap(), 4);
3219 assert_eq
!(m2
.len(), 2);
3222 thread_local
! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) }
3224 #[derive(Hash, PartialEq, Eq)]
3230 fn new(k
: usize) -> Droppable
{
3231 DROP_VECTOR
.with(|slot
| {
3232 slot
.borrow_mut()[k
] += 1;
3239 impl Drop
for Droppable
{
3240 fn drop(&mut self) {
3241 DROP_VECTOR
.with(|slot
| {
3242 slot
.borrow_mut()[self.k
] -= 1;
3247 impl Clone
for Droppable
{
3248 fn clone(&self) -> Self {
3249 Droppable
::new(self.k
)
3255 DROP_VECTOR
.with(|slot
| {
3256 *slot
.borrow_mut() = vec
![0; 200];
3260 let mut m
= HashMap
::new();
3262 DROP_VECTOR
.with(|v
| {
3264 assert_eq
!(v
.borrow()[i
], 0);
3269 let d1
= Droppable
::new(i
);
3270 let d2
= Droppable
::new(i
+ 100);
3274 DROP_VECTOR
.with(|v
| {
3276 assert_eq
!(v
.borrow()[i
], 1);
3281 let k
= Droppable
::new(i
);
3282 let v
= m
.remove(&k
);
3284 assert
!(v
.is_some());
3286 DROP_VECTOR
.with(|v
| {
3287 assert_eq
!(v
.borrow()[i
], 1);
3288 assert_eq
!(v
.borrow()[i
+ 100], 1);
3292 DROP_VECTOR
.with(|v
| {
3294 assert_eq
!(v
.borrow()[i
], 0);
3295 assert_eq
!(v
.borrow()[i
+ 100], 0);
3299 assert_eq
!(v
.borrow()[i
], 1);
3300 assert_eq
!(v
.borrow()[i
+ 100], 1);
3305 DROP_VECTOR
.with(|v
| {
3307 assert_eq
!(v
.borrow()[i
], 0);
3313 fn test_into_iter_drops() {
3314 DROP_VECTOR
.with(|v
| {
3315 *v
.borrow_mut() = vec
![0; 200];
3319 let mut hm
= HashMap
::new();
3321 DROP_VECTOR
.with(|v
| {
3323 assert_eq
!(v
.borrow()[i
], 0);
3328 let d1
= Droppable
::new(i
);
3329 let d2
= Droppable
::new(i
+ 100);
3333 DROP_VECTOR
.with(|v
| {
3335 assert_eq
!(v
.borrow()[i
], 1);
3342 // By the way, ensure that cloning doesn't screw up the dropping.
3346 let mut half
= hm
.into_iter().take(50);
3348 DROP_VECTOR
.with(|v
| {
3350 assert_eq
!(v
.borrow()[i
], 1);
3354 for _
in half
.by_ref() {}
3356 DROP_VECTOR
.with(|v
| {
3357 let nk
= (0..100).filter(|&i
| v
.borrow()[i
] == 1).count();
3359 let nv
= (0..100).filter(|&i
| v
.borrow()[i
+ 100] == 1).count();
3366 DROP_VECTOR
.with(|v
| {
3368 assert_eq
!(v
.borrow()[i
], 0);
3374 fn test_empty_remove() {
3375 let mut m
: HashMap
<i32, bool
> = HashMap
::new();
3376 assert_eq
!(m
.remove(&0), None
);
3380 fn test_empty_entry() {
3381 let mut m
: HashMap
<i32, bool
> = HashMap
::new();
3383 Occupied(_
) => panic
!(),
3386 assert
!(*m
.entry(0).or_insert(true));
3387 assert_eq
!(m
.len(), 1);
3391 fn test_empty_iter() {
3392 let mut m
: HashMap
<i32, bool
> = HashMap
::new();
3393 assert_eq
!(m
.drain().next(), None
);
3394 assert_eq
!(m
.keys().next(), None
);
3395 assert_eq
!(m
.values().next(), None
);
3396 assert_eq
!(m
.values_mut().next(), None
);
3397 assert_eq
!(m
.iter().next(), None
);
3398 assert_eq
!(m
.iter_mut().next(), None
);
3399 assert_eq
!(m
.len(), 0);
3400 assert
!(m
.is_empty());
3401 assert_eq
!(m
.into_iter().next(), None
);
3405 #[cfg_attr(miri, ignore)] // FIXME: takes too long
3406 fn test_lots_of_insertions() {
3407 let mut m
= HashMap
::new();
3409 // Try this a few times to make sure we never screw up the hashmap's
3412 assert
!(m
.is_empty());
3415 assert
!(m
.insert(i
, i
).is_none());
3419 assert_eq
!(r
, Some(&j
));
3422 for j
in i
+ 1..1001 {
3424 assert_eq
!(r
, None
);
3428 for i
in 1001..2001 {
3429 assert
!(!m
.contains_key(&i
));
3434 assert
!(m
.remove(&i
).is_some());
3437 assert
!(!m
.contains_key(&j
));
3440 for j
in i
+ 1..1001 {
3441 assert
!(m
.contains_key(&j
));
3446 assert
!(!m
.contains_key(&i
));
3450 assert
!(m
.insert(i
, i
).is_none());
3454 for i
in (1..1001).rev() {
3455 assert
!(m
.remove(&i
).is_some());
3458 assert
!(!m
.contains_key(&j
));
3462 assert
!(m
.contains_key(&j
));
3469 fn test_find_mut() {
3470 let mut m
= HashMap
::new();
3471 assert
!(m
.insert(1, 12).is_none());
3472 assert
!(m
.insert(2, 8).is_none());
3473 assert
!(m
.insert(5, 14).is_none());
3475 match m
.get_mut(&5) {
3477 Some(x
) => *x
= new
,
3479 assert_eq
!(m
.get(&5), Some(&new
));
3483 fn test_insert_overwrite() {
3484 let mut m
= HashMap
::new();
3485 assert
!(m
.insert(1, 2).is_none());
3486 assert_eq
!(*m
.get(&1).unwrap(), 2);
3487 assert
!(!m
.insert(1, 3).is_none());
3488 assert_eq
!(*m
.get(&1).unwrap(), 3);
3492 fn test_insert_conflicts() {
3493 let mut m
= HashMap
::with_capacity(4);
3494 assert
!(m
.insert(1, 2).is_none());
3495 assert
!(m
.insert(5, 3).is_none());
3496 assert
!(m
.insert(9, 4).is_none());
3497 assert_eq
!(*m
.get(&9).unwrap(), 4);
3498 assert_eq
!(*m
.get(&5).unwrap(), 3);
3499 assert_eq
!(*m
.get(&1).unwrap(), 2);
3503 fn test_conflict_remove() {
3504 let mut m
= HashMap
::with_capacity(4);
3505 assert
!(m
.insert(1, 2).is_none());
3506 assert_eq
!(*m
.get(&1).unwrap(), 2);
3507 assert
!(m
.insert(5, 3).is_none());
3508 assert_eq
!(*m
.get(&1).unwrap(), 2);
3509 assert_eq
!(*m
.get(&5).unwrap(), 3);
3510 assert
!(m
.insert(9, 4).is_none());
3511 assert_eq
!(*m
.get(&1).unwrap(), 2);
3512 assert_eq
!(*m
.get(&5).unwrap(), 3);
3513 assert_eq
!(*m
.get(&9).unwrap(), 4);
3514 assert
!(m
.remove(&1).is_some());
3515 assert_eq
!(*m
.get(&9).unwrap(), 4);
3516 assert_eq
!(*m
.get(&5).unwrap(), 3);
3520 fn test_is_empty() {
3521 let mut m
= HashMap
::with_capacity(4);
3522 assert
!(m
.insert(1, 2).is_none());
3523 assert
!(!m
.is_empty());
3524 assert
!(m
.remove(&1).is_some());
3525 assert
!(m
.is_empty());
3530 let mut m
= HashMap
::new();
3532 assert_eq
!(m
.remove(&1), Some(2));
3533 assert_eq
!(m
.remove(&1), None
);
3537 fn test_remove_entry() {
3538 let mut m
= HashMap
::new();
3540 assert_eq
!(m
.remove_entry(&1), Some((1, 2)));
3541 assert_eq
!(m
.remove(&1), None
);
3546 let mut m
= HashMap
::with_capacity(4);
3548 assert
!(m
.insert(i
, i
* 2).is_none());
3550 assert_eq
!(m
.len(), 32);
3552 let mut observed
: u32 = 0;
3555 assert_eq
!(*v
, *k
* 2);
3556 observed
|= 1 << *k
;
3558 assert_eq
!(observed
, 0xFFFF_FFFF);
3563 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
3564 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
3565 let keys
: Vec
<_
> = map
.keys().cloned().collect();
3566 assert_eq
!(keys
.len(), 3);
3567 assert
!(keys
.contains(&1));
3568 assert
!(keys
.contains(&2));
3569 assert
!(keys
.contains(&3));
3574 let vec
= vec
![(1, 'a'
), (2, 'b'
), (3, 'c'
)];
3575 let map
: HashMap
<_
, _
> = vec
.into_iter().collect();
3576 let values
: Vec
<_
> = map
.values().cloned().collect();
3577 assert_eq
!(values
.len(), 3);
3578 assert
!(values
.contains(&'a'
));
3579 assert
!(values
.contains(&'b'
));
3580 assert
!(values
.contains(&'c'
));
3584 fn test_values_mut() {
3585 let vec
= vec
![(1, 1), (2, 2), (3, 3)];
3586 let mut map
: HashMap
<_
, _
> = vec
.into_iter().collect();
3587 for value
in map
.values_mut() {
3588 *value
= (*value
) * 2
3590 let values
: Vec
<_
> = map
.values().cloned().collect();
3591 assert_eq
!(values
.len(), 3);
3592 assert
!(values
.contains(&2));
3593 assert
!(values
.contains(&4));
3594 assert
!(values
.contains(&6));
3599 let mut m
= HashMap
::new();
3600 assert
!(m
.get(&1).is_none());
3604 Some(v
) => assert_eq
!(*v
, 2),
3610 let mut m1
= HashMap
::new();
3615 let mut m2
= HashMap
::new();
3628 let mut map
= HashMap
::new();
3629 let empty
: HashMap
<i32, i32> = HashMap
::new();
3634 let map_str
= format
!("{:?}", map
);
3636 assert
!(map_str
== "{1: 2, 3: 4}" || map_str
== "{3: 4, 1: 2}");
3637 assert_eq
!(format
!("{:?}", empty
), "{}");
3642 let mut m
= HashMap
::new();
3644 assert_eq
!(m
.len(), 0);
3645 assert
!(m
.is_empty());
3648 let old_raw_cap
= m
.raw_capacity();
3649 while old_raw_cap
== m
.raw_capacity() {
3654 assert_eq
!(m
.len(), i
);
3655 assert
!(!m
.is_empty());
3659 fn test_behavior_resize_policy() {
3660 let mut m
= HashMap
::new();
3662 assert_eq
!(m
.len(), 0);
3663 assert_eq
!(m
.raw_capacity(), 1);
3664 assert
!(m
.is_empty());
3668 assert
!(m
.is_empty());
3669 let initial_raw_cap
= m
.raw_capacity();
3670 m
.reserve(initial_raw_cap
);
3671 let raw_cap
= m
.raw_capacity();
3673 assert_eq
!(raw_cap
, initial_raw_cap
* 2);
3676 for _
in 0..raw_cap
* 3 / 4 {
3680 // three quarters full
3682 assert_eq
!(m
.len(), i
);
3683 assert_eq
!(m
.raw_capacity(), raw_cap
);
3685 for _
in 0..raw_cap
/ 4 {
3691 let new_raw_cap
= m
.raw_capacity();
3692 assert_eq
!(new_raw_cap
, raw_cap
* 2);
3694 for _
in 0..raw_cap
/ 2 - 1 {
3697 assert_eq
!(m
.raw_capacity(), new_raw_cap
);
3699 // A little more than one quarter full.
3701 assert_eq
!(m
.raw_capacity(), raw_cap
);
3702 // again, a little more than half full
3703 for _
in 0..raw_cap
/ 2 {
3709 assert_eq
!(m
.len(), i
);
3710 assert
!(!m
.is_empty());
3711 assert_eq
!(m
.raw_capacity(), initial_raw_cap
);
3715 fn test_reserve_shrink_to_fit() {
3716 let mut m
= HashMap
::new();
3719 assert
!(m
.capacity() >= m
.len());
3725 let usable_cap
= m
.capacity();
3726 for i
in 128..(128 + 256) {
3728 assert_eq
!(m
.capacity(), usable_cap
);
3731 for i
in 100..(128 + 256) {
3732 assert_eq
!(m
.remove(&i
), Some(i
));
3736 assert_eq
!(m
.len(), 100);
3737 assert
!(!m
.is_empty());
3738 assert
!(m
.capacity() >= m
.len());
3741 assert_eq
!(m
.remove(&i
), Some(i
));
3746 assert_eq
!(m
.len(), 1);
3747 assert
!(m
.capacity() >= m
.len());
3748 assert_eq
!(m
.remove(&0), Some(0));
3752 fn test_from_iter() {
3753 let xs
= [(1, 1), (2, 2), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3755 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3757 for &(k
, v
) in &xs
{
3758 assert_eq
!(map
.get(&k
), Some(&v
));
3761 assert_eq
!(map
.iter().len(), xs
.len() - 1);
3765 fn test_size_hint() {
3766 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3768 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3770 let mut iter
= map
.iter();
3772 for _
in iter
.by_ref().take(3) {}
3774 assert_eq
!(iter
.size_hint(), (3, Some(3)));
3778 fn test_iter_len() {
3779 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3781 let map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3783 let mut iter
= map
.iter();
3785 for _
in iter
.by_ref().take(3) {}
3787 assert_eq
!(iter
.len(), 3);
3791 fn test_mut_size_hint() {
3792 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3794 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3796 let mut iter
= map
.iter_mut();
3798 for _
in iter
.by_ref().take(3) {}
3800 assert_eq
!(iter
.size_hint(), (3, Some(3)));
3804 fn test_iter_mut_len() {
3805 let xs
= [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
3807 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3809 let mut iter
= map
.iter_mut();
3811 for _
in iter
.by_ref().take(3) {}
3813 assert_eq
!(iter
.len(), 3);
3818 let mut map
= HashMap
::new();
3824 assert_eq
!(map
[&2], 1);
3829 fn test_index_nonexistent() {
3830 let mut map
= HashMap
::new();
3841 let xs
= [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
3843 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
3845 // Existing key (insert)
3846 match map
.entry(1) {
3847 Vacant(_
) => unreachable
!(),
3848 Occupied(mut view
) => {
3849 assert_eq
!(view
.get(), &10);
3850 assert_eq
!(view
.insert(100), 10);
3853 assert_eq
!(map
.get(&1).unwrap(), &100);
3854 assert_eq
!(map
.len(), 6);
3856 // Existing key (update)
3857 match map
.entry(2) {
3858 Vacant(_
) => unreachable
!(),
3859 Occupied(mut view
) => {
3860 let v
= view
.get_mut();
3861 let new_v
= (*v
) * 10;
3865 assert_eq
!(map
.get(&2).unwrap(), &200);
3866 assert_eq
!(map
.len(), 6);
3868 // Existing key (take)
3869 match map
.entry(3) {
3870 Vacant(_
) => unreachable
!(),
3872 assert_eq
!(view
.remove(), 30);
3875 assert_eq
!(map
.get(&3), None
);
3876 assert_eq
!(map
.len(), 5);
3878 // Inexistent key (insert)
3879 match map
.entry(10) {
3880 Occupied(_
) => unreachable
!(),
3882 assert_eq
!(*view
.insert(1000), 1000);
3885 assert_eq
!(map
.get(&10).unwrap(), &1000);
3886 assert_eq
!(map
.len(), 6);
3890 fn test_entry_take_doesnt_corrupt() {
3891 #![allow(deprecated)] //rand
3893 fn check(m
: &HashMap
<i32, ()>) {
3895 assert
!(m
.contains_key(k
), "{} is in keys() but not in the map?", k
);
3899 let mut m
= HashMap
::new();
3902 let seed
= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
3903 SmallRng
::from_seed(seed
)
3906 // Populate the map with some items.
3908 let x
= rng
.gen_range(-10, 10);
3913 let x
= rng
.gen_range(-10, 10);
3926 fn test_extend_ref() {
3927 let mut a
= HashMap
::new();
3929 let mut b
= HashMap
::new();
3931 b
.insert(3, "three");
3935 assert_eq
!(a
.len(), 3);
3936 assert_eq
!(a
[&1], "one");
3937 assert_eq
!(a
[&2], "two");
3938 assert_eq
!(a
[&3], "three");
3942 fn test_capacity_not_less_than_len() {
3943 let mut a
= HashMap
::new();
3951 assert
!(a
.capacity() > a
.len());
3953 let free
= a
.capacity() - a
.len();
3959 assert_eq
!(a
.len(), a
.capacity());
3961 // Insert at capacity should cause allocation.
3963 assert
!(a
.capacity() > a
.len());
3967 fn test_occupied_entry_key() {
3968 let mut a
= HashMap
::new();
3969 let key
= "hello there";
3970 let value
= "value goes here";
3971 assert
!(a
.is_empty());
3972 a
.insert(key
.clone(), value
.clone());
3973 assert_eq
!(a
.len(), 1);
3974 assert_eq
!(a
[key
], value
);
3976 match a
.entry(key
.clone()) {
3977 Vacant(_
) => panic
!(),
3978 Occupied(e
) => assert_eq
!(key
, *e
.key()),
3980 assert_eq
!(a
.len(), 1);
3981 assert_eq
!(a
[key
], value
);
3985 fn test_vacant_entry_key() {
3986 let mut a
= HashMap
::new();
3987 let key
= "hello there";
3988 let value
= "value goes here";
3990 assert
!(a
.is_empty());
3991 match a
.entry(key
.clone()) {
3992 Occupied(_
) => panic
!(),
3994 assert_eq
!(key
, *e
.key());
3995 e
.insert(value
.clone());
3998 assert_eq
!(a
.len(), 1);
3999 assert_eq
!(a
[key
], value
);
4003 fn test_occupied_entry_replace_entry_with() {
4004 let mut a
= HashMap
::new();
4007 let value
= "an initial value";
4008 let new_value
= "a new value";
4010 let entry
= a
.entry(key
).insert(value
).replace_entry_with(|k
, v
| {
4011 assert_eq
!(k
, &key
);
4012 assert_eq
!(v
, value
);
4018 assert_eq
!(e
.key(), &key
);
4019 assert_eq
!(e
.get(), &new_value
);
4021 Vacant(_
) => panic
!(),
4024 assert_eq
!(a
[key
], new_value
);
4025 assert_eq
!(a
.len(), 1);
4027 let entry
= match a
.entry(key
) {
4028 Occupied(e
) => e
.replace_entry_with(|k
, v
| {
4029 assert_eq
!(k
, &key
);
4030 assert_eq
!(v
, new_value
);
4033 Vacant(_
) => panic
!(),
4037 Vacant(e
) => assert_eq
!(e
.key(), &key
),
4038 Occupied(_
) => panic
!(),
4041 assert
!(!a
.contains_key(key
));
4042 assert_eq
!(a
.len(), 0);
4046 fn test_entry_and_replace_entry_with() {
4047 let mut a
= HashMap
::new();
4050 let value
= "an initial value";
4051 let new_value
= "a new value";
4053 let entry
= a
.entry(key
).and_replace_entry_with(|_
, _
| panic
!());
4056 Vacant(e
) => assert_eq
!(e
.key(), &key
),
4057 Occupied(_
) => panic
!(),
4060 a
.insert(key
, value
);
4062 let entry
= a
.entry(key
).and_replace_entry_with(|k
, v
| {
4063 assert_eq
!(k
, &key
);
4064 assert_eq
!(v
, value
);
4070 assert_eq
!(e
.key(), &key
);
4071 assert_eq
!(e
.get(), &new_value
);
4073 Vacant(_
) => panic
!(),
4076 assert_eq
!(a
[key
], new_value
);
4077 assert_eq
!(a
.len(), 1);
4079 let entry
= a
.entry(key
).and_replace_entry_with(|k
, v
| {
4080 assert_eq
!(k
, &key
);
4081 assert_eq
!(v
, new_value
);
4086 Vacant(e
) => assert_eq
!(e
.key(), &key
),
4087 Occupied(_
) => panic
!(),
4090 assert
!(!a
.contains_key(key
));
4091 assert_eq
!(a
.len(), 0);
4095 fn test_raw_occupied_entry_replace_entry_with() {
4096 let mut a
= HashMap
::new();
4099 let value
= "an initial value";
4100 let new_value
= "a new value";
4106 .replace_entry_with(|k
, v
| {
4107 assert_eq
!(k
, &key
);
4108 assert_eq
!(v
, value
);
4113 RawEntryMut
::Occupied(e
) => {
4114 assert_eq
!(e
.key(), &key
);
4115 assert_eq
!(e
.get(), &new_value
);
4117 RawEntryMut
::Vacant(_
) => panic
!(),
4120 assert_eq
!(a
[key
], new_value
);
4121 assert_eq
!(a
.len(), 1);
4123 let entry
= match a
.raw_entry_mut().from_key(&key
) {
4124 RawEntryMut
::Occupied(e
) => e
.replace_entry_with(|k
, v
| {
4125 assert_eq
!(k
, &key
);
4126 assert_eq
!(v
, new_value
);
4129 RawEntryMut
::Vacant(_
) => panic
!(),
4133 RawEntryMut
::Vacant(_
) => {}
4134 RawEntryMut
::Occupied(_
) => panic
!(),
4137 assert
!(!a
.contains_key(key
));
4138 assert_eq
!(a
.len(), 0);
4142 fn test_raw_entry_and_replace_entry_with() {
4143 let mut a
= HashMap
::new();
4146 let value
= "an initial value";
4147 let new_value
= "a new value";
4152 .and_replace_entry_with(|_
, _
| panic
!());
4155 RawEntryMut
::Vacant(_
) => {}
4156 RawEntryMut
::Occupied(_
) => panic
!(),
4159 a
.insert(key
, value
);
4164 .and_replace_entry_with(|k
, v
| {
4165 assert_eq
!(k
, &key
);
4166 assert_eq
!(v
, value
);
4171 RawEntryMut
::Occupied(e
) => {
4172 assert_eq
!(e
.key(), &key
);
4173 assert_eq
!(e
.get(), &new_value
);
4175 RawEntryMut
::Vacant(_
) => panic
!(),
4178 assert_eq
!(a
[key
], new_value
);
4179 assert_eq
!(a
.len(), 1);
4184 .and_replace_entry_with(|k
, v
| {
4185 assert_eq
!(k
, &key
);
4186 assert_eq
!(v
, new_value
);
4191 RawEntryMut
::Vacant(_
) => {}
4192 RawEntryMut
::Occupied(_
) => panic
!(),
4195 assert
!(!a
.contains_key(key
));
4196 assert_eq
!(a
.len(), 0);
4200 fn test_replace_entry_with_doesnt_corrupt() {
4201 #![allow(deprecated)] //rand
4203 fn check(m
: &HashMap
<i32, ()>) {
4205 assert
!(m
.contains_key(k
), "{} is in keys() but not in the map?", k
);
4209 let mut m
= HashMap
::new();
4212 let seed
= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
4213 SmallRng
::from_seed(seed
)
4216 // Populate the map with some items.
4218 let x
= rng
.gen_range(-10, 10);
4223 let x
= rng
.gen_range(-10, 10);
4224 m
.entry(x
).and_replace_entry_with(|_
, _
| None
);
4231 let mut map
: HashMap
<i32, i32> = (0..100).map(|x
| (x
, x
* 10)).collect();
4233 map
.retain(|&k
, _
| k
% 2 == 0);
4234 assert_eq
!(map
.len(), 50);
4235 assert_eq
!(map
[&2], 20);
4236 assert_eq
!(map
[&4], 40);
4237 assert_eq
!(map
[&6], 60);
4241 fn test_drain_filter() {
4243 let mut map
: HashMap
<i32, i32> = (0..8).map(|x
| (x
, x
* 10)).collect();
4244 let drained
= map
.drain_filter(|&k
, _
| k
% 2 == 0);
4245 let mut out
= drained
.collect
::<Vec
<_
>>();
4246 out
.sort_unstable();
4247 assert_eq
!(vec
![(0, 0), (2, 20), (4, 40), (6, 60)], out
);
4248 assert_eq
!(map
.len(), 4);
4251 let mut map
: HashMap
<i32, i32> = (0..8).map(|x
| (x
, x
* 10)).collect();
4252 drop(map
.drain_filter(|&k
, _
| k
% 2 == 0));
4253 assert_eq
!(map
.len(), 4);
4258 #[cfg_attr(miri, ignore)] // FIXME: no OOM signalling (https://github.com/rust-lang/miri/issues/613)
4259 fn test_try_reserve() {
4260 let mut empty_bytes
: HashMap
<u8, u8> = HashMap
::new();
4262 const MAX_USIZE
: usize = usize::MAX
;
4264 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve(MAX_USIZE
) {
4266 panic
!("usize::MAX should trigger an overflow!");
4269 if let Err(AllocError { .. }
) = empty_bytes
.try_reserve(MAX_USIZE
/ 8) {
4271 // This may succeed if there is enough free memory. Attempt to
4272 // allocate a second hashmap to ensure the allocation will fail.
4273 let mut empty_bytes2
: HashMap
<u8, u8> = HashMap
::new();
4274 if let Err(AllocError { .. }
) = empty_bytes2
.try_reserve(MAX_USIZE
/ 8) {
4276 panic
!("usize::MAX / 8 should trigger an OOM!");
4282 fn test_raw_entry() {
4283 use super::RawEntryMut
::{Occupied, Vacant}
;
4285 let xs
= [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
4287 let mut map
: HashMap
<_
, _
> = xs
.iter().cloned().collect();
4289 let compute_hash
= |map
: &HashMap
<i32, i32>, k
: i32| -> u64 {
4290 use core
::hash
::{BuildHasher, Hash, Hasher}
;
4292 let mut hasher
= map
.hasher().build_hasher();
4293 k
.hash(&mut hasher
);
4297 // Existing key (insert)
4298 match map
.raw_entry_mut().from_key(&1) {
4299 Vacant(_
) => unreachable
!(),
4300 Occupied(mut view
) => {
4301 assert_eq
!(view
.get(), &10);
4302 assert_eq
!(view
.insert(100), 10);
4305 let hash1
= compute_hash(&map
, 1);
4306 assert_eq
!(map
.raw_entry().from_key(&1).unwrap(), (&1, &100));
4308 map
.raw_entry().from_hash(hash1
, |k
| *k
== 1).unwrap(),
4312 map
.raw_entry().from_key_hashed_nocheck(hash1
, &1).unwrap(),
4315 assert_eq
!(map
.len(), 6);
4317 // Existing key (update)
4318 match map
.raw_entry_mut().from_key(&2) {
4319 Vacant(_
) => unreachable
!(),
4320 Occupied(mut view
) => {
4321 let v
= view
.get_mut();
4322 let new_v
= (*v
) * 10;
4326 let hash2
= compute_hash(&map
, 2);
4327 assert_eq
!(map
.raw_entry().from_key(&2).unwrap(), (&2, &200));
4329 map
.raw_entry().from_hash(hash2
, |k
| *k
== 2).unwrap(),
4333 map
.raw_entry().from_key_hashed_nocheck(hash2
, &2).unwrap(),
4336 assert_eq
!(map
.len(), 6);
4338 // Existing key (take)
4339 let hash3
= compute_hash(&map
, 3);
4340 match map
.raw_entry_mut().from_key_hashed_nocheck(hash3
, &3) {
4341 Vacant(_
) => unreachable
!(),
4343 assert_eq
!(view
.remove_entry(), (3, 30));
4346 assert_eq
!(map
.raw_entry().from_key(&3), None
);
4347 assert_eq
!(map
.raw_entry().from_hash(hash3
, |k
| *k
== 3), None
);
4348 assert_eq
!(map
.raw_entry().from_key_hashed_nocheck(hash3
, &3), None
);
4349 assert_eq
!(map
.len(), 5);
4351 // Nonexistent key (insert)
4352 match map
.raw_entry_mut().from_key(&10) {
4353 Occupied(_
) => unreachable
!(),
4355 assert_eq
!(view
.insert(10, 1000), (&mut 10, &mut 1000));
4358 assert_eq
!(map
.raw_entry().from_key(&10).unwrap(), (&10, &1000));
4359 assert_eq
!(map
.len(), 6);
4361 // Ensure all lookup methods produce equivalent results.
4363 let hash
= compute_hash(&map
, k
);
4364 let v
= map
.get(&k
).cloned();
4365 let kv
= v
.as_ref().map(|v
| (&k
, v
));
4367 assert_eq
!(map
.raw_entry().from_key(&k
), kv
);
4368 assert_eq
!(map
.raw_entry().from_hash(hash
, |q
| *q
== k
), kv
);
4369 assert_eq
!(map
.raw_entry().from_key_hashed_nocheck(hash
, &k
), kv
);
4371 match map
.raw_entry_mut().from_key(&k
) {
4372 Occupied(mut o
) => assert_eq
!(Some(o
.get_key_value()), kv
),
4373 Vacant(_
) => assert_eq
!(v
, None
),
4375 match map
.raw_entry_mut().from_key_hashed_nocheck(hash
, &k
) {
4376 Occupied(mut o
) => assert_eq
!(Some(o
.get_key_value()), kv
),
4377 Vacant(_
) => assert_eq
!(v
, None
),
4379 match map
.raw_entry_mut().from_hash(hash
, |q
| *q
== k
) {
4380 Occupied(mut o
) => assert_eq
!(Some(o
.get_key_value()), kv
),
4381 Vacant(_
) => assert_eq
!(v
, None
),
4387 fn test_key_without_hash_impl() {
4389 struct IntWrapper(u64);
4391 let mut m
: HashMap
<IntWrapper
, (), ()> = HashMap
::default();
4393 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_none());
4396 let vacant_entry
= match m
.raw_entry_mut().from_hash(0, |k
| k
.0 == 0) {
4397 RawEntryMut
::Occupied(..) => panic
!("Found entry for key 0"),
4398 RawEntryMut
::Vacant(e
) => e
,
4400 vacant_entry
.insert_with_hasher(0, IntWrapper(0), (), |k
| k
.0);
4403 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_some());
4404 assert
!(m
.raw_entry().from_hash(1, |k
| k
.0 == 1).is_none());
4405 assert
!(m
.raw_entry().from_hash(2, |k
| k
.0 == 2).is_none());
4408 let vacant_entry
= match m
.raw_entry_mut().from_hash(1, |k
| k
.0 == 1) {
4409 RawEntryMut
::Occupied(..) => panic
!("Found entry for key 1"),
4410 RawEntryMut
::Vacant(e
) => e
,
4412 vacant_entry
.insert_with_hasher(1, IntWrapper(1), (), |k
| k
.0);
4415 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_some());
4416 assert
!(m
.raw_entry().from_hash(1, |k
| k
.0 == 1).is_some());
4417 assert
!(m
.raw_entry().from_hash(2, |k
| k
.0 == 2).is_none());
4420 let occupied_entry
= match m
.raw_entry_mut().from_hash(0, |k
| k
.0 == 0) {
4421 RawEntryMut
::Occupied(e
) => e
,
4422 RawEntryMut
::Vacant(..) => panic
!("Couldn't find entry for key 0"),
4424 occupied_entry
.remove();
4426 assert
!(m
.raw_entry().from_hash(0, |k
| k
.0 == 0).is_none());
4427 assert
!(m
.raw_entry().from_hash(1, |k
| k
.0 == 1).is_some());
4428 assert
!(m
.raw_entry().from_hash(2, |k
| k
.0 == 2).is_none());
4432 #[cfg(feature = "raw")]
4433 fn test_into_iter_refresh() {
4434 use core
::hash
::{BuildHasher, Hash, Hasher}
;
4437 const N
: usize = 32;
4439 const N
: usize = 128;
4441 let mut rng
= rand
::thread_rng();
4443 let mut m
= HashMap
::new();
4445 assert
!(m
.insert(i
, 2 * i
).is_none());
4447 let hasher
= m
.hasher().clone();
4449 let mut it
= unsafe { m.table.iter() }
;
4450 assert_eq
!(it
.len(), n
);
4454 let mut removed
= Vec
::new();
4456 // occasionally remove some elements
4457 if i
< n
&& rng
.gen_bool(0.1) {
4458 let mut hsh
= hasher
.build_hasher();
4460 let hash
= hsh
.finish();
4463 let e
= m
.table
.find(hash
, |q
| q
.0.eq(&i
));
4464 if let Some(e
) = e
{
4465 it
.reflect_remove(&e
);
4466 let t
= m
.table
.remove(e
);
4470 assert
!(removed
.contains(&(i
, 2 * i
)), "{} not in {:?}", i
, removed
);
4473 .insert(hash
, (i
, 2 * i
), |x
| super::make_hash(&hasher
, &x
.0));
4474 it
.reflect_insert(&e
);
4475 if let Some(p
) = removed
.iter().position(|e
| e
== &(i
, 2 * i
)) {
4476 removed
.swap_remove(p
);
4488 let t
= unsafe { e.unwrap().as_ref() }
;
4489 assert
!(!removed
.contains(t
));
4491 assert_eq
!(*v
, 2 * k
);
4497 assert_eq
!(m
.table
.len(), left
);
4502 fn test_const_with_hasher() {
4503 use core
::hash
::BuildHasher
;
4504 use std
::borrow
::ToOwned
;
4505 use std
::collections
::hash_map
::DefaultHasher
;
4509 impl BuildHasher
for MyHasher
{
4510 type Hasher
= DefaultHasher
;
4512 fn build_hasher(&self) -> DefaultHasher
{
4513 DefaultHasher
::new()
4517 const EMPTY_MAP
: HashMap
<u32, std
::string
::String
, MyHasher
> =
4518 HashMap
::with_hasher(MyHasher
);
4520 let mut map
= EMPTY_MAP
.clone();
4521 map
.insert(17, "seventeen".to_owned());
4522 assert_eq
!("seventeen", map
[&17]);