]>
Commit | Line | Data |
---|---|---|
6a06907d XL |
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; | |
8 | use core::mem; | |
9 | use core::ops::Index; | |
10 | ||
11 | /// Default hasher for `HashMap`. | |
12 | #[cfg(feature = "ahash")] | |
13 | pub type DefaultHashBuilder = ahash::RandomState; | |
14 | ||
15 | /// Dummy default hasher for `HashMap`. | |
16 | #[cfg(not(feature = "ahash"))] | |
17 | pub enum DefaultHashBuilder {} | |
18 | ||
19 | /// A hash map implemented with quadratic probing and SIMD lookup. | |
20 | /// | |
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. | |
25 | /// | |
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. | |
29 | /// | |
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 | |
33 | /// property holds: | |
34 | /// | |
35 | /// ```text | |
36 | /// k1 == k2 -> hash(k1) == hash(k2) | |
37 | /// ``` | |
38 | /// | |
39 | /// In other words, if two keys are equal, their hashes must be equal. | |
40 | /// | |
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. | |
45 | /// | |
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. | |
50 | /// | |
51 | /// # Examples | |
52 | /// | |
53 | /// ``` | |
54 | /// use hashbrown::HashMap; | |
55 | /// | |
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(); | |
59 | /// | |
60 | /// // Review some books. | |
61 | /// book_reviews.insert( | |
62 | /// "Adventures of Huckleberry Finn".to_string(), | |
63 | /// "My favorite book.".to_string(), | |
64 | /// ); | |
65 | /// book_reviews.insert( | |
66 | /// "Grimms' Fairy Tales".to_string(), | |
67 | /// "Masterpiece.".to_string(), | |
68 | /// ); | |
69 | /// book_reviews.insert( | |
70 | /// "Pride and Prejudice".to_string(), | |
71 | /// "Very enjoyable.".to_string(), | |
72 | /// ); | |
73 | /// book_reviews.insert( | |
74 | /// "The Adventures of Sherlock Holmes".to_string(), | |
75 | /// "Eye lyked it alot.".to_string(), | |
76 | /// ); | |
77 | /// | |
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()); | |
84 | /// } | |
85 | /// | |
86 | /// // oops, this review has a lot of spelling mistakes, let's delete it. | |
87 | /// book_reviews.remove("The Adventures of Sherlock Holmes"); | |
88 | /// | |
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) | |
95 | /// } | |
96 | /// } | |
97 | /// | |
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"]); | |
100 | /// | |
101 | /// // Iterate over everything. | |
102 | /// for (book, review) in &book_reviews { | |
103 | /// println!("{}: \"{}\"", book, review); | |
104 | /// } | |
105 | /// ``` | |
106 | /// | |
107 | /// `HashMap` also implements an [`Entry API`](#method.entry), which allows | |
108 | /// for more complex methods of getting, setting, updating and removing keys and | |
109 | /// their values: | |
110 | /// | |
111 | /// ``` | |
112 | /// use hashbrown::HashMap; | |
113 | /// | |
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(); | |
117 | /// | |
118 | /// fn random_stat_buff() -> u8 { | |
119 | /// // could actually return some random value here - let's just return | |
120 | /// // some fixed value for now | |
121 | /// 42 | |
122 | /// } | |
123 | /// | |
124 | /// // insert a key only if it doesn't already exist | |
125 | /// player_stats.entry("health").or_insert(100); | |
126 | /// | |
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); | |
130 | /// | |
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(); | |
134 | /// ``` | |
135 | /// | |
136 | /// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`]. | |
137 | /// We must also derive [`PartialEq`]. | |
138 | /// | |
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 | |
149 | /// | |
150 | /// ``` | |
151 | /// use hashbrown::HashMap; | |
152 | /// | |
153 | /// #[derive(Hash, Eq, PartialEq, Debug)] | |
154 | /// struct Viking { | |
155 | /// name: String, | |
156 | /// country: String, | |
157 | /// } | |
158 | /// | |
159 | /// impl Viking { | |
160 | /// /// Creates a new Viking. | |
161 | /// fn new(name: &str, country: &str) -> Viking { | |
162 | /// Viking { name: name.to_string(), country: country.to_string() } | |
163 | /// } | |
164 | /// } | |
165 | /// | |
166 | /// // Use a HashMap to store the vikings' health points. | |
167 | /// let mut vikings = HashMap::new(); | |
168 | /// | |
169 | /// vikings.insert(Viking::new("Einar", "Norway"), 25); | |
170 | /// vikings.insert(Viking::new("Olaf", "Denmark"), 24); | |
171 | /// vikings.insert(Viking::new("Harald", "Iceland"), 12); | |
172 | /// | |
173 | /// // Use derived implementation to print the status of the vikings. | |
174 | /// for (viking, health) in &vikings { | |
175 | /// println!("{:?} has {} hp", viking, health); | |
176 | /// } | |
177 | /// ``` | |
178 | /// | |
179 | /// A `HashMap` with fixed list of elements can be initialized from an array: | |
180 | /// | |
181 | /// ``` | |
182 | /// use hashbrown::HashMap; | |
183 | /// | |
184 | /// let timber_resources: HashMap<&str, i32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)] | |
185 | /// .iter().cloned().collect(); | |
186 | /// // use the values stored in map | |
187 | /// ``` | |
188 | pub struct HashMap<K, V, S = DefaultHashBuilder> { | |
189 | pub(crate) hash_builder: S, | |
190 | pub(crate) table: RawTable<(K, V)>, | |
191 | } | |
192 | ||
193 | impl<K: Clone, V: Clone, S: Clone> Clone for HashMap<K, V, S> { | |
194 | fn clone(&self) -> Self { | |
195 | HashMap { | |
196 | hash_builder: self.hash_builder.clone(), | |
197 | table: self.table.clone(), | |
198 | } | |
199 | } | |
200 | ||
201 | fn clone_from(&mut self, source: &Self) { | |
202 | self.table.clone_from(&source.table); | |
203 | ||
204 | // Update hash_builder only if we successfully cloned all elements. | |
205 | self.hash_builder.clone_from(&source.hash_builder); | |
206 | } | |
207 | } | |
208 | ||
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); | |
213 | state.finish() | |
214 | } | |
215 | ||
216 | #[cfg(feature = "ahash")] | |
217 | impl<K, V> HashMap<K, V, DefaultHashBuilder> { | |
218 | /// Creates an empty `HashMap`. | |
219 | /// | |
220 | /// The hash map is initially created with a capacity of 0, so it will not allocate until it | |
221 | /// is first inserted into. | |
222 | /// | |
223 | /// # Examples | |
224 | /// | |
225 | /// ``` | |
226 | /// use hashbrown::HashMap; | |
227 | /// let mut map: HashMap<&str, i32> = HashMap::new(); | |
228 | /// ``` | |
229 | #[cfg_attr(feature = "inline-more", inline)] | |
230 | pub fn new() -> Self { | |
231 | Self::default() | |
232 | } | |
233 | ||
234 | /// Creates an empty `HashMap` with the specified capacity. | |
235 | /// | |
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. | |
238 | /// | |
239 | /// # Examples | |
240 | /// | |
241 | /// ``` | |
242 | /// use hashbrown::HashMap; | |
243 | /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10); | |
244 | /// ``` | |
245 | #[cfg_attr(feature = "inline-more", inline)] | |
246 | pub fn with_capacity(capacity: usize) -> Self { | |
247 | Self::with_capacity_and_hasher(capacity, DefaultHashBuilder::default()) | |
248 | } | |
249 | } | |
250 | ||
251 | impl<K, V, S> HashMap<K, V, S> { | |
252 | /// Creates an empty `HashMap` which will use the given hash builder to hash | |
253 | /// keys. | |
254 | /// | |
255 | /// The created map has the default initial capacity. | |
256 | /// | |
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. | |
261 | /// | |
262 | /// The `hash_builder` passed should implement the [`BuildHasher`] trait for | |
263 | /// the HashMap to be useful, see its documentation for details. | |
264 | /// | |
265 | /// # Examples | |
266 | /// | |
267 | /// ``` | |
268 | /// use hashbrown::HashMap; | |
269 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
270 | /// | |
271 | /// let s = DefaultHashBuilder::default(); | |
272 | /// let mut map = HashMap::with_hasher(s); | |
273 | /// map.insert(1, 2); | |
274 | /// ``` | |
275 | /// | |
276 | /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html | |
277 | #[cfg_attr(feature = "inline-more", inline)] | |
278 | pub const fn with_hasher(hash_builder: S) -> Self { | |
279 | Self { | |
280 | hash_builder, | |
281 | table: RawTable::new(), | |
282 | } | |
283 | } | |
284 | ||
285 | /// Creates an empty `HashMap` with the specified capacity, using `hash_builder` | |
286 | /// to hash the keys. | |
287 | /// | |
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. | |
290 | /// | |
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. | |
295 | /// | |
296 | /// The `hash_builder` passed should implement the [`BuildHasher`] trait for | |
297 | /// the HashMap to be useful, see its documentation for details. | |
298 | /// | |
299 | /// # Examples | |
300 | /// | |
301 | /// ``` | |
302 | /// use hashbrown::HashMap; | |
303 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
304 | /// | |
305 | /// let s = DefaultHashBuilder::default(); | |
306 | /// let mut map = HashMap::with_capacity_and_hasher(10, s); | |
307 | /// map.insert(1, 2); | |
308 | /// ``` | |
309 | /// | |
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 { | |
313 | Self { | |
314 | hash_builder, | |
315 | table: RawTable::with_capacity(capacity), | |
316 | } | |
317 | } | |
318 | ||
319 | /// Returns a reference to the map's [`BuildHasher`]. | |
320 | /// | |
321 | /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html | |
322 | /// | |
323 | /// # Examples | |
324 | /// | |
325 | /// ``` | |
326 | /// use hashbrown::HashMap; | |
327 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
328 | /// | |
329 | /// let hasher = DefaultHashBuilder::default(); | |
330 | /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher); | |
331 | /// let hasher: &DefaultHashBuilder = map.hasher(); | |
332 | /// ``` | |
333 | #[cfg_attr(feature = "inline-more", inline)] | |
334 | pub fn hasher(&self) -> &S { | |
335 | &self.hash_builder | |
336 | } | |
337 | ||
338 | /// Returns the number of elements the map can hold without reallocating. | |
339 | /// | |
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. | |
342 | /// | |
343 | /// # Examples | |
344 | /// | |
345 | /// ``` | |
346 | /// use hashbrown::HashMap; | |
347 | /// let map: HashMap<i32, i32> = HashMap::with_capacity(100); | |
348 | /// assert!(map.capacity() >= 100); | |
349 | /// ``` | |
350 | #[cfg_attr(feature = "inline-more", inline)] | |
351 | pub fn capacity(&self) -> usize { | |
352 | self.table.capacity() | |
353 | } | |
354 | ||
355 | /// An iterator visiting all keys in arbitrary order. | |
356 | /// The iterator element type is `&'a K`. | |
357 | /// | |
358 | /// # Examples | |
359 | /// | |
360 | /// ``` | |
361 | /// use hashbrown::HashMap; | |
362 | /// | |
363 | /// let mut map = HashMap::new(); | |
364 | /// map.insert("a", 1); | |
365 | /// map.insert("b", 2); | |
366 | /// map.insert("c", 3); | |
367 | /// | |
368 | /// for key in map.keys() { | |
369 | /// println!("{}", key); | |
370 | /// } | |
371 | /// ``` | |
372 | #[cfg_attr(feature = "inline-more", inline)] | |
373 | pub fn keys(&self) -> Keys<'_, K, V> { | |
374 | Keys { inner: self.iter() } | |
375 | } | |
376 | ||
377 | /// An iterator visiting all values in arbitrary order. | |
378 | /// The iterator element type is `&'a V`. | |
379 | /// | |
380 | /// # Examples | |
381 | /// | |
382 | /// ``` | |
383 | /// use hashbrown::HashMap; | |
384 | /// | |
385 | /// let mut map = HashMap::new(); | |
386 | /// map.insert("a", 1); | |
387 | /// map.insert("b", 2); | |
388 | /// map.insert("c", 3); | |
389 | /// | |
390 | /// for val in map.values() { | |
391 | /// println!("{}", val); | |
392 | /// } | |
393 | /// ``` | |
394 | #[cfg_attr(feature = "inline-more", inline)] | |
395 | pub fn values(&self) -> Values<'_, K, V> { | |
396 | Values { inner: self.iter() } | |
397 | } | |
398 | ||
399 | /// An iterator visiting all values mutably in arbitrary order. | |
400 | /// The iterator element type is `&'a mut V`. | |
401 | /// | |
402 | /// # Examples | |
403 | /// | |
404 | /// ``` | |
405 | /// use hashbrown::HashMap; | |
406 | /// | |
407 | /// let mut map = HashMap::new(); | |
408 | /// | |
409 | /// map.insert("a", 1); | |
410 | /// map.insert("b", 2); | |
411 | /// map.insert("c", 3); | |
412 | /// | |
413 | /// for val in map.values_mut() { | |
414 | /// *val = *val + 10; | |
415 | /// } | |
416 | /// | |
417 | /// for val in map.values() { | |
418 | /// println!("{}", val); | |
419 | /// } | |
420 | /// ``` | |
421 | #[cfg_attr(feature = "inline-more", inline)] | |
422 | pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { | |
423 | ValuesMut { | |
424 | inner: self.iter_mut(), | |
425 | } | |
426 | } | |
427 | ||
428 | /// An iterator visiting all key-value pairs in arbitrary order. | |
429 | /// The iterator element type is `(&'a K, &'a V)`. | |
430 | /// | |
431 | /// # Examples | |
432 | /// | |
433 | /// ``` | |
434 | /// use hashbrown::HashMap; | |
435 | /// | |
436 | /// let mut map = HashMap::new(); | |
437 | /// map.insert("a", 1); | |
438 | /// map.insert("b", 2); | |
439 | /// map.insert("c", 3); | |
440 | /// | |
441 | /// for (key, val) in map.iter() { | |
442 | /// println!("key: {} val: {}", key, val); | |
443 | /// } | |
444 | /// ``` | |
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. | |
448 | unsafe { | |
449 | Iter { | |
450 | inner: self.table.iter(), | |
451 | marker: PhantomData, | |
452 | } | |
453 | } | |
454 | } | |
455 | ||
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)`. | |
459 | /// | |
460 | /// # Examples | |
461 | /// | |
462 | /// ``` | |
463 | /// use hashbrown::HashMap; | |
464 | /// | |
465 | /// let mut map = HashMap::new(); | |
466 | /// map.insert("a", 1); | |
467 | /// map.insert("b", 2); | |
468 | /// map.insert("c", 3); | |
469 | /// | |
470 | /// // Update all values | |
471 | /// for (_, val) in map.iter_mut() { | |
472 | /// *val *= 2; | |
473 | /// } | |
474 | /// | |
475 | /// for (key, val) in &map { | |
476 | /// println!("key: {} val: {}", key, val); | |
477 | /// } | |
478 | /// ``` | |
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. | |
482 | unsafe { | |
483 | IterMut { | |
484 | inner: self.table.iter(), | |
485 | marker: PhantomData, | |
486 | } | |
487 | } | |
488 | } | |
489 | ||
490 | #[cfg(test)] | |
491 | #[cfg_attr(feature = "inline-more", inline)] | |
492 | fn raw_capacity(&self) -> usize { | |
493 | self.table.buckets() | |
494 | } | |
495 | ||
496 | /// Returns the number of elements in the map. | |
497 | /// | |
498 | /// # Examples | |
499 | /// | |
500 | /// ``` | |
501 | /// use hashbrown::HashMap; | |
502 | /// | |
503 | /// let mut a = HashMap::new(); | |
504 | /// assert_eq!(a.len(), 0); | |
505 | /// a.insert(1, "a"); | |
506 | /// assert_eq!(a.len(), 1); | |
507 | /// ``` | |
508 | #[cfg_attr(feature = "inline-more", inline)] | |
509 | pub fn len(&self) -> usize { | |
510 | self.table.len() | |
511 | } | |
512 | ||
513 | /// Returns `true` if the map contains no elements. | |
514 | /// | |
515 | /// # Examples | |
516 | /// | |
517 | /// ``` | |
518 | /// use hashbrown::HashMap; | |
519 | /// | |
520 | /// let mut a = HashMap::new(); | |
521 | /// assert!(a.is_empty()); | |
522 | /// a.insert(1, "a"); | |
523 | /// assert!(!a.is_empty()); | |
524 | /// ``` | |
525 | #[cfg_attr(feature = "inline-more", inline)] | |
526 | pub fn is_empty(&self) -> bool { | |
527 | self.len() == 0 | |
528 | } | |
529 | ||
530 | /// Clears the map, returning all key-value pairs as an iterator. Keeps the | |
531 | /// allocated memory for reuse. | |
532 | /// | |
533 | /// # Examples | |
534 | /// | |
535 | /// ``` | |
536 | /// use hashbrown::HashMap; | |
537 | /// | |
538 | /// let mut a = HashMap::new(); | |
539 | /// a.insert(1, "a"); | |
540 | /// a.insert(2, "b"); | |
541 | /// | |
542 | /// for (k, v) in a.drain().take(1) { | |
543 | /// assert!(k == 1 || k == 2); | |
544 | /// assert!(v == "a" || v == "b"); | |
545 | /// } | |
546 | /// | |
547 | /// assert!(a.is_empty()); | |
548 | /// ``` | |
549 | #[cfg_attr(feature = "inline-more", inline)] | |
550 | pub fn drain(&mut self) -> Drain<'_, K, V> { | |
551 | Drain { | |
552 | inner: self.table.drain(), | |
553 | } | |
554 | } | |
555 | ||
556 | /// Retains only the elements specified by the predicate. | |
557 | /// | |
558 | /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`. | |
559 | /// | |
560 | /// # Examples | |
561 | /// | |
562 | /// ``` | |
563 | /// use hashbrown::HashMap; | |
564 | /// | |
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); | |
568 | /// ``` | |
569 | pub fn retain<F>(&mut self, mut f: F) | |
570 | where | |
571 | F: FnMut(&K, &mut V) -> bool, | |
572 | { | |
573 | // Here we only use `iter` as a temporary, preventing use-after-free | |
574 | unsafe { | |
575 | for item in self.table.iter() { | |
576 | let &mut (ref key, ref mut value) = item.as_mut(); | |
577 | if !f(key, value) { | |
578 | self.table.erase(item); | |
579 | } | |
580 | } | |
581 | } | |
582 | } | |
583 | ||
584 | /// Drains elements which are true under the given predicate, | |
585 | /// and returns an iterator over the removed items. | |
586 | /// | |
587 | /// In other words, move all pairs `(k, v)` such that `f(&k,&mut v)` returns `true` out | |
588 | /// into another iterator. | |
589 | /// | |
590 | /// When the returned DrainedFilter is dropped, any remaining elements that satisfy | |
591 | /// the predicate are dropped from the table. | |
592 | /// | |
593 | /// # Examples | |
594 | /// | |
595 | /// ``` | |
596 | /// use hashbrown::HashMap; | |
597 | /// | |
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(); | |
600 | /// | |
601 | /// let mut evens = drained.keys().cloned().collect::<Vec<_>>(); | |
602 | /// let mut odds = map.keys().cloned().collect::<Vec<_>>(); | |
603 | /// evens.sort(); | |
604 | /// odds.sort(); | |
605 | /// | |
606 | /// assert_eq!(evens, vec![0, 2, 4, 6]); | |
607 | /// assert_eq!(odds, vec![1, 3, 5, 7]); | |
608 | /// ``` | |
609 | #[cfg_attr(feature = "inline-more", inline)] | |
610 | pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, K, V, F> | |
611 | where | |
612 | F: FnMut(&K, &mut V) -> bool, | |
613 | { | |
614 | DrainFilter { | |
615 | f, | |
616 | inner: DrainFilterInner { | |
617 | iter: unsafe { self.table.iter() }, | |
618 | table: &mut self.table, | |
619 | }, | |
620 | } | |
621 | } | |
622 | ||
623 | /// Clears the map, removing all key-value pairs. Keeps the allocated memory | |
624 | /// for reuse. | |
625 | /// | |
626 | /// # Examples | |
627 | /// | |
628 | /// ``` | |
629 | /// use hashbrown::HashMap; | |
630 | /// | |
631 | /// let mut a = HashMap::new(); | |
632 | /// a.insert(1, "a"); | |
633 | /// a.clear(); | |
634 | /// assert!(a.is_empty()); | |
635 | /// ``` | |
636 | #[cfg_attr(feature = "inline-more", inline)] | |
637 | pub fn clear(&mut self) { | |
638 | self.table.clear(); | |
639 | } | |
640 | } | |
641 | ||
642 | impl<K, V, S> HashMap<K, V, S> | |
643 | where | |
644 | K: Eq + Hash, | |
645 | S: BuildHasher, | |
646 | { | |
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. | |
650 | /// | |
651 | /// # Panics | |
652 | /// | |
653 | /// Panics if the new allocation size overflows [`usize`]. | |
654 | /// | |
655 | /// [`usize`]: https://doc.rust-lang.org/std/primitive.usize.html | |
656 | /// | |
657 | /// # Examples | |
658 | /// | |
659 | /// ``` | |
660 | /// use hashbrown::HashMap; | |
661 | /// let mut map: HashMap<&str, i32> = HashMap::new(); | |
662 | /// map.reserve(10); | |
663 | /// ``` | |
664 | #[cfg_attr(feature = "inline-more", inline)] | |
665 | pub fn reserve(&mut self, additional: usize) { | |
666 | let hash_builder = &self.hash_builder; | |
667 | self.table | |
668 | .reserve(additional, |x| make_hash(hash_builder, &x.0)); | |
669 | } | |
670 | ||
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. | |
674 | /// | |
675 | /// # Errors | |
676 | /// | |
677 | /// If the capacity overflows, or the allocator reports a failure, then an error | |
678 | /// is returned. | |
679 | /// | |
680 | /// # Examples | |
681 | /// | |
682 | /// ``` | |
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?"); | |
686 | /// ``` | |
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; | |
690 | self.table | |
691 | .try_reserve(additional, |x| make_hash(hash_builder, &x.0)) | |
692 | } | |
693 | ||
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. | |
697 | /// | |
698 | /// # Examples | |
699 | /// | |
700 | /// ``` | |
701 | /// use hashbrown::HashMap; | |
702 | /// | |
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); | |
709 | /// ``` | |
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)); | |
714 | } | |
715 | ||
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. | |
719 | /// | |
720 | /// This function does nothing if the current capacity is smaller than the | |
721 | /// supplied minimum capacity. | |
722 | /// | |
723 | /// # Examples | |
724 | /// | |
725 | /// ``` | |
726 | /// use hashbrown::HashMap; | |
727 | /// | |
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); | |
738 | /// ``` | |
739 | #[cfg_attr(feature = "inline-more", inline)] | |
740 | pub fn shrink_to(&mut self, min_capacity: usize) { | |
741 | let hash_builder = &self.hash_builder; | |
742 | self.table | |
743 | .shrink_to(min_capacity, |x| make_hash(hash_builder, &x.0)); | |
744 | } | |
745 | ||
746 | /// Gets the given key's corresponding entry in the map for in-place manipulation. | |
747 | /// | |
748 | /// # Examples | |
749 | /// | |
750 | /// ``` | |
751 | /// use hashbrown::HashMap; | |
752 | /// | |
753 | /// let mut letters = HashMap::new(); | |
754 | /// | |
755 | /// for ch in "a short treatise on fungi".chars() { | |
756 | /// let counter = letters.entry(ch).or_insert(0); | |
757 | /// *counter += 1; | |
758 | /// } | |
759 | /// | |
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); | |
764 | /// ``` | |
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 { | |
770 | hash, | |
771 | key: Some(key), | |
772 | elem, | |
773 | table: self, | |
774 | }) | |
775 | } else { | |
776 | Entry::Vacant(VacantEntry { | |
777 | hash, | |
778 | key, | |
779 | table: self, | |
780 | }) | |
781 | } | |
782 | } | |
783 | ||
784 | /// Returns a reference to the value corresponding to the key. | |
785 | /// | |
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 | |
788 | /// the key type. | |
789 | /// | |
790 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
791 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
792 | /// | |
793 | /// # Examples | |
794 | /// | |
795 | /// ``` | |
796 | /// use hashbrown::HashMap; | |
797 | /// | |
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); | |
802 | /// ``` | |
803 | #[inline] | |
804 | pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> | |
805 | where | |
806 | K: Borrow<Q>, | |
807 | Q: Hash + Eq, | |
808 | { | |
809 | // Avoid `Option::map` because it bloats LLVM IR. | |
810 | match self.get_inner(k) { | |
811 | Some(&(_, ref v)) => Some(v), | |
812 | None => None, | |
813 | } | |
814 | } | |
815 | ||
816 | /// Returns the key-value pair corresponding to the supplied key. | |
817 | /// | |
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 | |
820 | /// the key type. | |
821 | /// | |
822 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
823 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
824 | /// | |
825 | /// # Examples | |
826 | /// | |
827 | /// ``` | |
828 | /// use hashbrown::HashMap; | |
829 | /// | |
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); | |
834 | /// ``` | |
835 | #[inline] | |
836 | pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> | |
837 | where | |
838 | K: Borrow<Q>, | |
839 | Q: Hash + Eq, | |
840 | { | |
841 | // Avoid `Option::map` because it bloats LLVM IR. | |
842 | match self.get_inner(k) { | |
843 | Some(&(ref key, ref value)) => Some((key, value)), | |
844 | None => None, | |
845 | } | |
846 | } | |
847 | ||
848 | #[inline] | |
849 | fn get_inner<Q: ?Sized>(&self, k: &Q) -> Option<&(K, V)> | |
850 | where | |
851 | K: Borrow<Q>, | |
852 | Q: Hash + Eq, | |
853 | { | |
854 | let hash = make_hash(&self.hash_builder, k); | |
855 | self.table.get(hash, |x| k.eq(x.0.borrow())) | |
856 | } | |
857 | ||
858 | /// Returns the key-value pair corresponding to the supplied key, with a mutable reference to value. | |
859 | /// | |
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 | |
862 | /// the key type. | |
863 | /// | |
864 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
865 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
866 | /// | |
867 | /// # Examples | |
868 | /// | |
869 | /// ``` | |
870 | /// use hashbrown::HashMap; | |
871 | /// | |
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"); | |
877 | /// *v = "b"; | |
878 | /// assert_eq!(map.get_key_value_mut(&1), Some((&1, &mut "b"))); | |
879 | /// assert_eq!(map.get_key_value_mut(&2), None); | |
880 | /// ``` | |
881 | #[inline] | |
882 | pub fn get_key_value_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<(&K, &mut V)> | |
883 | where | |
884 | K: Borrow<Q>, | |
885 | Q: Hash + Eq, | |
886 | { | |
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)), | |
890 | None => None, | |
891 | } | |
892 | } | |
893 | ||
894 | /// Returns `true` if the map contains a value for the specified key. | |
895 | /// | |
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 | |
898 | /// the key type. | |
899 | /// | |
900 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
901 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
902 | /// | |
903 | /// # Examples | |
904 | /// | |
905 | /// ``` | |
906 | /// use hashbrown::HashMap; | |
907 | /// | |
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); | |
912 | /// ``` | |
913 | #[cfg_attr(feature = "inline-more", inline)] | |
914 | pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool | |
915 | where | |
916 | K: Borrow<Q>, | |
917 | Q: Hash + Eq, | |
918 | { | |
919 | self.get_inner(k).is_some() | |
920 | } | |
921 | ||
922 | /// Returns a mutable reference to the value corresponding to the key. | |
923 | /// | |
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 | |
926 | /// the key type. | |
927 | /// | |
928 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
929 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
930 | /// | |
931 | /// # Examples | |
932 | /// | |
933 | /// ``` | |
934 | /// use hashbrown::HashMap; | |
935 | /// | |
936 | /// let mut map = HashMap::new(); | |
937 | /// map.insert(1, "a"); | |
938 | /// if let Some(x) = map.get_mut(&1) { | |
939 | /// *x = "b"; | |
940 | /// } | |
941 | /// assert_eq!(map[&1], "b"); | |
942 | /// ``` | |
943 | #[cfg_attr(feature = "inline-more", inline)] | |
944 | pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> | |
945 | where | |
946 | K: Borrow<Q>, | |
947 | Q: Hash + Eq, | |
948 | { | |
949 | // Avoid `Option::map` because it bloats LLVM IR. | |
950 | match self.get_inner_mut(k) { | |
951 | Some(&mut (_, ref mut v)) => Some(v), | |
952 | None => None, | |
953 | } | |
954 | } | |
955 | ||
956 | #[inline] | |
957 | fn get_inner_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut (K, V)> | |
958 | where | |
959 | K: Borrow<Q>, | |
960 | Q: Hash + Eq, | |
961 | { | |
962 | let hash = make_hash(&self.hash_builder, k); | |
963 | self.table.get_mut(hash, |x| k.eq(x.0.borrow())) | |
964 | } | |
965 | ||
966 | /// Inserts a key-value pair into the map. | |
967 | /// | |
968 | /// If the map did not have this key present, [`None`] is returned. | |
969 | /// | |
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. | |
974 | /// | |
975 | /// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None | |
976 | /// [module-level documentation]: index.html#insert-and-complex-keys | |
977 | /// | |
978 | /// # Examples | |
979 | /// | |
980 | /// ``` | |
981 | /// use hashbrown::HashMap; | |
982 | /// | |
983 | /// let mut map = HashMap::new(); | |
984 | /// assert_eq!(map.insert(37, "a"), None); | |
985 | /// assert_eq!(map.is_empty(), false); | |
986 | /// | |
987 | /// map.insert(37, "b"); | |
988 | /// assert_eq!(map.insert(37, "c"), Some("b")); | |
989 | /// assert_eq!(map[&37], "c"); | |
990 | /// ``` | |
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)) | |
996 | } else { | |
997 | let hash_builder = &self.hash_builder; | |
998 | self.table | |
999 | .insert(hash, (k, v), |x| make_hash(hash_builder, &x.0)); | |
1000 | None | |
1001 | } | |
1002 | } | |
1003 | ||
1004 | /// Removes a key from the map, returning the value at the key if the key | |
1005 | /// was previously in the map. | |
1006 | /// | |
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 | |
1009 | /// the key type. | |
1010 | /// | |
1011 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
1012 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1013 | /// | |
1014 | /// # Examples | |
1015 | /// | |
1016 | /// ``` | |
1017 | /// use hashbrown::HashMap; | |
1018 | /// | |
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); | |
1023 | /// ``` | |
1024 | #[cfg_attr(feature = "inline-more", inline)] | |
1025 | pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> | |
1026 | where | |
1027 | K: Borrow<Q>, | |
1028 | Q: Hash + Eq, | |
1029 | { | |
1030 | // Avoid `Option::map` because it bloats LLVM IR. | |
1031 | match self.remove_entry(k) { | |
1032 | Some((_, v)) => Some(v), | |
1033 | None => None, | |
1034 | } | |
1035 | } | |
1036 | ||
1037 | /// Removes a key from the map, returning the stored key and value if the | |
1038 | /// key was previously in the map. | |
1039 | /// | |
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 | |
1042 | /// the key type. | |
1043 | /// | |
1044 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
1045 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1046 | /// | |
1047 | /// # Examples | |
1048 | /// | |
1049 | /// ``` | |
1050 | /// use hashbrown::HashMap; | |
1051 | /// | |
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); | |
1056 | /// ``` | |
1057 | #[cfg_attr(feature = "inline-more", inline)] | |
1058 | pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)> | |
1059 | where | |
1060 | K: Borrow<Q>, | |
1061 | Q: Hash + Eq, | |
1062 | { | |
1063 | let hash = make_hash(&self.hash_builder, &k); | |
1064 | self.table.remove_entry(hash, |x| k.eq(x.0.borrow())) | |
1065 | } | |
1066 | } | |
1067 | ||
1068 | impl<K, V, S> HashMap<K, V, S> { | |
1069 | /// Creates a raw entry builder for the HashMap. | |
1070 | /// | |
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. | |
1075 | /// | |
1076 | /// Raw entries are useful for such exotic situations as: | |
1077 | /// | |
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 | |
1082 | /// | |
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. | |
1087 | /// | |
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. | |
1092 | /// | |
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 } | |
1103 | } | |
1104 | ||
1105 | /// Creates a raw immutable entry builder for the HashMap. | |
1106 | /// | |
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. | |
1110 | /// | |
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 | |
1115 | /// | |
1116 | /// Unless you are in such a situation, higher-level and more foolproof APIs like | |
1117 | /// `get` should be preferred. | |
1118 | /// | |
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 } | |
1123 | } | |
1124 | } | |
1125 | ||
1126 | impl<K, V, S> PartialEq for HashMap<K, V, S> | |
1127 | where | |
1128 | K: Eq + Hash, | |
1129 | V: PartialEq, | |
1130 | S: BuildHasher, | |
1131 | { | |
1132 | fn eq(&self, other: &Self) -> bool { | |
1133 | if self.len() != other.len() { | |
1134 | return false; | |
1135 | } | |
1136 | ||
1137 | self.iter() | |
1138 | .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) | |
1139 | } | |
1140 | } | |
1141 | ||
1142 | impl<K, V, S> Eq for HashMap<K, V, S> | |
1143 | where | |
1144 | K: Eq + Hash, | |
1145 | V: Eq, | |
1146 | S: BuildHasher, | |
1147 | { | |
1148 | } | |
1149 | ||
1150 | impl<K, V, S> Debug for HashMap<K, V, S> | |
1151 | where | |
1152 | K: Debug, | |
1153 | V: Debug, | |
1154 | { | |
1155 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1156 | f.debug_map().entries(self.iter()).finish() | |
1157 | } | |
1158 | } | |
1159 | ||
1160 | impl<K, V, S> Default for HashMap<K, V, S> | |
1161 | where | |
1162 | S: Default, | |
1163 | { | |
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()) | |
1168 | } | |
1169 | } | |
1170 | ||
1171 | impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S> | |
1172 | where | |
1173 | K: Eq + Hash + Borrow<Q>, | |
1174 | Q: Eq + Hash, | |
1175 | S: BuildHasher, | |
1176 | { | |
1177 | type Output = V; | |
1178 | ||
1179 | /// Returns a reference to the value corresponding to the supplied key. | |
1180 | /// | |
1181 | /// # Panics | |
1182 | /// | |
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") | |
1187 | } | |
1188 | } | |
1189 | ||
1190 | /// An iterator over the entries of a `HashMap`. | |
1191 | /// | |
1192 | /// This `struct` is created by the [`iter`] method on [`HashMap`]. See its | |
1193 | /// documentation for more. | |
1194 | /// | |
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)>, | |
1200 | } | |
1201 | ||
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 { | |
1206 | Iter { | |
1207 | inner: self.inner.clone(), | |
1208 | marker: PhantomData, | |
1209 | } | |
1210 | } | |
1211 | } | |
1212 | ||
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() | |
1216 | } | |
1217 | } | |
1218 | ||
1219 | /// A mutable iterator over the entries of a `HashMap`. | |
1220 | /// | |
1221 | /// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its | |
1222 | /// documentation for more. | |
1223 | /// | |
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)>, | |
1230 | } | |
1231 | ||
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> {} | |
1236 | ||
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> { | |
1241 | Iter { | |
1242 | inner: self.inner.clone(), | |
1243 | marker: PhantomData, | |
1244 | } | |
1245 | } | |
1246 | } | |
1247 | ||
1248 | /// An owning iterator over the entries of a `HashMap`. | |
1249 | /// | |
1250 | /// This `struct` is created by the [`into_iter`] method on [`HashMap`] | |
1251 | /// (provided by the `IntoIterator` trait). See its documentation for more. | |
1252 | /// | |
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)>, | |
1257 | } | |
1258 | ||
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> { | |
1263 | Iter { | |
1264 | inner: self.inner.iter(), | |
1265 | marker: PhantomData, | |
1266 | } | |
1267 | } | |
1268 | } | |
1269 | ||
1270 | /// An iterator over the keys of a `HashMap`. | |
1271 | /// | |
1272 | /// This `struct` is created by the [`keys`] method on [`HashMap`]. See its | |
1273 | /// documentation for more. | |
1274 | /// | |
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>, | |
1279 | } | |
1280 | ||
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 { | |
1285 | Keys { | |
1286 | inner: self.inner.clone(), | |
1287 | } | |
1288 | } | |
1289 | } | |
1290 | ||
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() | |
1294 | } | |
1295 | } | |
1296 | ||
1297 | /// An iterator over the values of a `HashMap`. | |
1298 | /// | |
1299 | /// This `struct` is created by the [`values`] method on [`HashMap`]. See its | |
1300 | /// documentation for more. | |
1301 | /// | |
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>, | |
1306 | } | |
1307 | ||
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 { | |
1312 | Values { | |
1313 | inner: self.inner.clone(), | |
1314 | } | |
1315 | } | |
1316 | } | |
1317 | ||
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() | |
1321 | } | |
1322 | } | |
1323 | ||
1324 | /// A draining iterator over the entries of a `HashMap`. | |
1325 | /// | |
1326 | /// This `struct` is created by the [`drain`] method on [`HashMap`]. See its | |
1327 | /// documentation for more. | |
1328 | /// | |
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)>, | |
1333 | } | |
1334 | ||
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> { | |
1339 | Iter { | |
1340 | inner: self.inner.iter(), | |
1341 | marker: PhantomData, | |
1342 | } | |
1343 | } | |
1344 | } | |
1345 | ||
1346 | /// A draining iterator over entries of a `HashMap` which don't satisfy the predicate `f`. | |
1347 | /// | |
1348 | /// This `struct` is created by the [`drain_filter`] method on [`HashMap`]. See its | |
1349 | /// documentation for more. | |
1350 | /// | |
1351 | /// [`drain_filter`]: struct.HashMap.html#method.drain_filter | |
1352 | /// [`HashMap`]: struct.HashMap.html | |
1353 | pub struct DrainFilter<'a, K, V, F> | |
1354 | where | |
1355 | F: FnMut(&K, &mut V) -> bool, | |
1356 | { | |
1357 | f: F, | |
1358 | inner: DrainFilterInner<'a, K, V>, | |
1359 | } | |
1360 | ||
1361 | impl<'a, K, V, F> Drop for DrainFilter<'a, K, V, F> | |
1362 | where | |
1363 | F: FnMut(&K, &mut V) -> bool, | |
1364 | { | |
1365 | #[cfg_attr(feature = "inline-more", inline)] | |
1366 | fn drop(&mut self) { | |
1367 | while let Some(item) = self.next() { | |
1368 | let guard = ConsumeAllOnDrop(self); | |
1369 | drop(item); | |
1370 | mem::forget(guard); | |
1371 | } | |
1372 | } | |
1373 | } | |
1374 | ||
1375 | pub(super) struct ConsumeAllOnDrop<'a, T: Iterator>(pub &'a mut T); | |
1376 | ||
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) | |
1381 | } | |
1382 | } | |
1383 | ||
1384 | impl<K, V, F> Iterator for DrainFilter<'_, K, V, F> | |
1385 | where | |
1386 | F: FnMut(&K, &mut V) -> bool, | |
1387 | { | |
1388 | type Item = (K, V); | |
1389 | ||
1390 | #[cfg_attr(feature = "inline-more", inline)] | |
1391 | fn next(&mut self) -> Option<Self::Item> { | |
1392 | self.inner.next(&mut self.f) | |
1393 | } | |
1394 | ||
1395 | #[inline] | |
1396 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1397 | (0, self.inner.iter.size_hint().1) | |
1398 | } | |
1399 | } | |
1400 | ||
1401 | impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {} | |
1402 | ||
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)>, | |
1407 | } | |
1408 | ||
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)> | |
1412 | where | |
1413 | F: FnMut(&K, &mut V) -> bool, | |
1414 | { | |
1415 | unsafe { | |
1416 | while let Some(item) = self.iter.next() { | |
1417 | let &mut (ref key, ref mut value) = item.as_mut(); | |
1418 | if f(key, value) { | |
1419 | return Some(self.table.remove(item)); | |
1420 | } | |
1421 | } | |
1422 | } | |
1423 | None | |
1424 | } | |
1425 | } | |
1426 | ||
1427 | /// A mutable iterator over the values of a `HashMap`. | |
1428 | /// | |
1429 | /// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its | |
1430 | /// documentation for more. | |
1431 | /// | |
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>, | |
1436 | } | |
1437 | ||
1438 | /// A builder for computing where in a [`HashMap`] a key-value pair would be stored. | |
1439 | /// | |
1440 | /// See the [`HashMap::raw_entry_mut`] docs for usage examples. | |
1441 | /// | |
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>, | |
1445 | } | |
1446 | ||
1447 | /// A view into a single entry in a map, which may either be vacant or occupied. | |
1448 | /// | |
1449 | /// This is a lower-level version of [`Entry`]. | |
1450 | /// | |
1451 | /// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`], | |
1452 | /// then calling one of the methods of that [`RawEntryBuilderMut`]. | |
1453 | /// | |
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>), | |
1461 | /// A vacant entry. | |
1462 | Vacant(RawVacantEntryMut<'a, K, V, S>), | |
1463 | } | |
1464 | ||
1465 | /// A view into an occupied entry in a `HashMap`. | |
1466 | /// It is part of the [`RawEntryMut`] enum. | |
1467 | /// | |
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, | |
1473 | } | |
1474 | ||
1475 | unsafe impl<K, V, S> Send for RawOccupiedEntryMut<'_, K, V, S> | |
1476 | where | |
1477 | K: Send, | |
1478 | V: Send, | |
1479 | S: Sync, | |
1480 | { | |
1481 | } | |
1482 | unsafe impl<K, V, S> Sync for RawOccupiedEntryMut<'_, K, V, S> | |
1483 | where | |
1484 | K: Sync, | |
1485 | V: Sync, | |
1486 | S: Sync, | |
1487 | { | |
1488 | } | |
1489 | ||
1490 | /// A view into a vacant entry in a `HashMap`. | |
1491 | /// It is part of the [`RawEntryMut`] enum. | |
1492 | /// | |
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, | |
1497 | } | |
1498 | ||
1499 | /// A builder for computing where in a [`HashMap`] a key-value pair would be stored. | |
1500 | /// | |
1501 | /// See the [`HashMap::raw_entry`] docs for usage examples. | |
1502 | /// | |
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>, | |
1506 | } | |
1507 | ||
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> | |
1513 | where | |
1514 | S: BuildHasher, | |
1515 | K: Borrow<Q>, | |
1516 | Q: Hash + Eq, | |
1517 | { | |
1518 | let mut hasher = self.map.hash_builder.build_hasher(); | |
1519 | k.hash(&mut hasher); | |
1520 | self.from_key_hashed_nocheck(hasher.finish(), k) | |
1521 | } | |
1522 | ||
1523 | /// Creates a `RawEntryMut` from the given key and its hash. | |
1524 | #[inline] | |
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> | |
1527 | where | |
1528 | K: Borrow<Q>, | |
1529 | Q: Eq, | |
1530 | { | |
1531 | self.from_hash(hash, |q| q.borrow().eq(k)) | |
1532 | } | |
1533 | } | |
1534 | ||
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> | |
1540 | where | |
1541 | for<'b> F: FnMut(&'b K) -> bool, | |
1542 | { | |
1543 | self.search(hash, is_match) | |
1544 | } | |
1545 | ||
1546 | #[cfg_attr(feature = "inline-more", inline)] | |
1547 | fn search<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S> | |
1548 | where | |
1549 | for<'b> F: FnMut(&'b K) -> bool, | |
1550 | { | |
1551 | match self.map.table.find(hash, |(k, _)| is_match(k)) { | |
1552 | Some(elem) => RawEntryMut::Occupied(RawOccupiedEntryMut { | |
1553 | elem, | |
1554 | table: &mut self.map.table, | |
1555 | hash_builder: &self.map.hash_builder, | |
1556 | }), | |
1557 | None => RawEntryMut::Vacant(RawVacantEntryMut { | |
1558 | table: &mut self.map.table, | |
1559 | hash_builder: &self.map.hash_builder, | |
1560 | }), | |
1561 | } | |
1562 | } | |
1563 | } | |
1564 | ||
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)> | |
1570 | where | |
1571 | S: BuildHasher, | |
1572 | K: Borrow<Q>, | |
1573 | Q: Hash + Eq, | |
1574 | { | |
1575 | let mut hasher = self.map.hash_builder.build_hasher(); | |
1576 | k.hash(&mut hasher); | |
1577 | self.from_key_hashed_nocheck(hasher.finish(), k) | |
1578 | } | |
1579 | ||
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)> | |
1584 | where | |
1585 | K: Borrow<Q>, | |
1586 | Q: Eq, | |
1587 | { | |
1588 | self.from_hash(hash, |q| q.borrow().eq(k)) | |
1589 | } | |
1590 | ||
1591 | #[cfg_attr(feature = "inline-more", inline)] | |
1592 | fn search<F>(self, hash: u64, mut is_match: F) -> Option<(&'a K, &'a V)> | |
1593 | where | |
1594 | F: FnMut(&K) -> bool, | |
1595 | { | |
1596 | match self.map.table.get(hash, |(k, _)| is_match(k)) { | |
1597 | Some(&(ref key, ref value)) => Some((key, value)), | |
1598 | None => None, | |
1599 | } | |
1600 | } | |
1601 | ||
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)> | |
1606 | where | |
1607 | F: FnMut(&K) -> bool, | |
1608 | { | |
1609 | self.search(hash, is_match) | |
1610 | } | |
1611 | } | |
1612 | ||
1613 | impl<'a, K, V, S> RawEntryMut<'a, K, V, S> { | |
1614 | /// Sets the value of the entry, and returns a RawOccupiedEntryMut. | |
1615 | /// | |
1616 | /// # Examples | |
1617 | /// | |
1618 | /// ``` | |
1619 | /// use hashbrown::HashMap; | |
1620 | /// | |
1621 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
1622 | /// let entry = map.raw_entry_mut().from_key("horseyland").insert("horseyland", 37); | |
1623 | /// | |
1624 | /// assert_eq!(entry.remove_entry(), ("horseyland", 37)); | |
1625 | /// ``` | |
1626 | #[cfg_attr(feature = "inline-more", inline)] | |
1627 | pub fn insert(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S> | |
1628 | where | |
1629 | K: Hash, | |
1630 | S: BuildHasher, | |
1631 | { | |
1632 | match self { | |
1633 | RawEntryMut::Occupied(mut entry) => { | |
1634 | entry.insert(value); | |
1635 | entry | |
1636 | } | |
1637 | RawEntryMut::Vacant(entry) => entry.insert_entry(key, value), | |
1638 | } | |
1639 | } | |
1640 | ||
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. | |
1643 | /// | |
1644 | /// # Examples | |
1645 | /// | |
1646 | /// ``` | |
1647 | /// use hashbrown::HashMap; | |
1648 | /// | |
1649 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
1650 | /// | |
1651 | /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3); | |
1652 | /// assert_eq!(map["poneyland"], 3); | |
1653 | /// | |
1654 | /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2; | |
1655 | /// assert_eq!(map["poneyland"], 6); | |
1656 | /// ``` | |
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) | |
1659 | where | |
1660 | K: Hash, | |
1661 | S: BuildHasher, | |
1662 | { | |
1663 | match self { | |
1664 | RawEntryMut::Occupied(entry) => entry.into_key_value(), | |
1665 | RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val), | |
1666 | } | |
1667 | } | |
1668 | ||
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. | |
1671 | /// | |
1672 | /// # Examples | |
1673 | /// | |
1674 | /// ``` | |
1675 | /// use hashbrown::HashMap; | |
1676 | /// | |
1677 | /// let mut map: HashMap<&str, String> = HashMap::new(); | |
1678 | /// | |
1679 | /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| { | |
1680 | /// ("poneyland", "hoho".to_string()) | |
1681 | /// }); | |
1682 | /// | |
1683 | /// assert_eq!(map["poneyland"], "hoho".to_string()); | |
1684 | /// ``` | |
1685 | #[cfg_attr(feature = "inline-more", inline)] | |
1686 | pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V) | |
1687 | where | |
1688 | F: FnOnce() -> (K, V), | |
1689 | K: Hash, | |
1690 | S: BuildHasher, | |
1691 | { | |
1692 | match self { | |
1693 | RawEntryMut::Occupied(entry) => entry.into_key_value(), | |
1694 | RawEntryMut::Vacant(entry) => { | |
1695 | let (k, v) = default(); | |
1696 | entry.insert(k, v) | |
1697 | } | |
1698 | } | |
1699 | } | |
1700 | ||
1701 | /// Provides in-place mutable access to an occupied entry before any | |
1702 | /// potential inserts into the map. | |
1703 | /// | |
1704 | /// # Examples | |
1705 | /// | |
1706 | /// ``` | |
1707 | /// use hashbrown::HashMap; | |
1708 | /// | |
1709 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
1710 | /// | |
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); | |
1716 | /// | |
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); | |
1722 | /// ``` | |
1723 | #[cfg_attr(feature = "inline-more", inline)] | |
1724 | pub fn and_modify<F>(self, f: F) -> Self | |
1725 | where | |
1726 | F: FnOnce(&mut K, &mut V), | |
1727 | { | |
1728 | match self { | |
1729 | RawEntryMut::Occupied(mut entry) => { | |
1730 | { | |
1731 | let (k, v) = entry.get_key_value_mut(); | |
1732 | f(k, v); | |
1733 | } | |
1734 | RawEntryMut::Occupied(entry) | |
1735 | } | |
1736 | RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry), | |
1737 | } | |
1738 | } | |
1739 | ||
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. | |
1743 | /// | |
1744 | /// # Examples | |
1745 | /// | |
1746 | /// ``` | |
1747 | /// use hashbrown::HashMap; | |
1748 | /// use hashbrown::hash_map::RawEntryMut; | |
1749 | /// | |
1750 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
1751 | /// | |
1752 | /// let entry = map | |
1753 | /// .raw_entry_mut() | |
1754 | /// .from_key("poneyland") | |
1755 | /// .and_replace_entry_with(|_k, _v| panic!()); | |
1756 | /// | |
1757 | /// match entry { | |
1758 | /// RawEntryMut::Vacant(_) => {}, | |
1759 | /// RawEntryMut::Occupied(_) => panic!(), | |
1760 | /// } | |
1761 | /// | |
1762 | /// map.insert("poneyland", 42); | |
1763 | /// | |
1764 | /// let entry = map | |
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); | |
1770 | /// Some(v + 1) | |
1771 | /// }); | |
1772 | /// | |
1773 | /// match entry { | |
1774 | /// RawEntryMut::Occupied(e) => { | |
1775 | /// assert_eq!(e.key(), &"poneyland"); | |
1776 | /// assert_eq!(e.get(), &43); | |
1777 | /// }, | |
1778 | /// RawEntryMut::Vacant(_) => panic!(), | |
1779 | /// } | |
1780 | /// | |
1781 | /// assert_eq!(map["poneyland"], 43); | |
1782 | /// | |
1783 | /// let entry = map | |
1784 | /// .raw_entry_mut() | |
1785 | /// .from_key("poneyland") | |
1786 | /// .and_replace_entry_with(|_k, _v| None); | |
1787 | /// | |
1788 | /// match entry { | |
1789 | /// RawEntryMut::Vacant(_) => {}, | |
1790 | /// RawEntryMut::Occupied(_) => panic!(), | |
1791 | /// } | |
1792 | /// | |
1793 | /// assert!(!map.contains_key("poneyland")); | |
1794 | /// ``` | |
1795 | #[cfg_attr(feature = "inline-more", inline)] | |
1796 | pub fn and_replace_entry_with<F>(self, f: F) -> Self | |
1797 | where | |
1798 | F: FnOnce(&K, V) -> Option<V>, | |
1799 | { | |
1800 | match self { | |
1801 | RawEntryMut::Occupied(entry) => entry.replace_entry_with(f), | |
1802 | RawEntryMut::Vacant(_) => self, | |
1803 | } | |
1804 | } | |
1805 | } | |
1806 | ||
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 } | |
1812 | } | |
1813 | ||
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 } | |
1818 | } | |
1819 | ||
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 } | |
1825 | } | |
1826 | ||
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 } | |
1831 | } | |
1832 | ||
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 } | |
1838 | } | |
1839 | ||
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 } | |
1844 | } | |
1845 | ||
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) { | |
1849 | unsafe { | |
1850 | let &(ref key, ref value) = self.elem.as_ref(); | |
1851 | (key, value) | |
1852 | } | |
1853 | } | |
1854 | ||
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) { | |
1858 | unsafe { | |
1859 | let &mut (ref mut key, ref mut value) = self.elem.as_mut(); | |
1860 | (key, value) | |
1861 | } | |
1862 | } | |
1863 | ||
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) { | |
1868 | unsafe { | |
1869 | let &mut (ref mut key, ref mut value) = self.elem.as_mut(); | |
1870 | (key, value) | |
1871 | } | |
1872 | } | |
1873 | ||
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) | |
1878 | } | |
1879 | ||
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) | |
1884 | } | |
1885 | ||
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 | |
1890 | } | |
1891 | ||
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) } | |
1896 | } | |
1897 | ||
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> | |
1903 | where | |
1904 | F: FnOnce(&K, V) -> Option<V>, | |
1905 | { | |
1906 | unsafe { | |
1907 | let still_occupied = self | |
1908 | .table | |
1909 | .replace_bucket_with(self.elem.clone(), |(key, value)| { | |
1910 | f(&key, value).map(|new_value| (key, new_value)) | |
1911 | }); | |
1912 | ||
1913 | if still_occupied { | |
1914 | RawEntryMut::Occupied(self) | |
1915 | } else { | |
1916 | RawEntryMut::Vacant(RawVacantEntryMut { | |
1917 | table: self.table, | |
1918 | hash_builder: self.hash_builder, | |
1919 | }) | |
1920 | } | |
1921 | } | |
1922 | } | |
1923 | } | |
1924 | ||
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) | |
1930 | where | |
1931 | K: Hash, | |
1932 | S: BuildHasher, | |
1933 | { | |
1934 | let mut hasher = self.hash_builder.build_hasher(); | |
1935 | key.hash(&mut hasher); | |
1936 | self.insert_hashed_nocheck(hasher.finish(), key, value) | |
1937 | } | |
1938 | ||
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) | |
1944 | where | |
1945 | K: Hash, | |
1946 | S: BuildHasher, | |
1947 | { | |
1948 | let hash_builder = self.hash_builder; | |
1949 | self.insert_with_hasher(hash, key, value, |k| make_hash(hash_builder, k)) | |
1950 | } | |
1951 | ||
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>( | |
1955 | self, | |
1956 | hash: u64, | |
1957 | key: K, | |
1958 | value: V, | |
1959 | hasher: H, | |
1960 | ) -> (&'a mut K, &'a mut V) | |
1961 | where | |
1962 | H: Fn(&K) -> u64, | |
1963 | { | |
1964 | let &mut (ref mut k, ref mut v) = self | |
1965 | .table | |
1966 | .insert_entry(hash, (key, value), |x| hasher(&x.0)); | |
1967 | (k, v) | |
1968 | } | |
1969 | ||
1970 | #[cfg_attr(feature = "inline-more", inline)] | |
1971 | fn insert_entry(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S> | |
1972 | where | |
1973 | K: Hash, | |
1974 | S: BuildHasher, | |
1975 | { | |
1976 | let hash_builder = self.hash_builder; | |
1977 | let mut hasher = self.hash_builder.build_hasher(); | |
1978 | key.hash(&mut hasher); | |
1979 | ||
1980 | let elem = self.table.insert(hasher.finish(), (key, value), |k| { | |
1981 | make_hash(hash_builder, &k.0) | |
1982 | }); | |
1983 | RawOccupiedEntryMut { | |
1984 | elem, | |
1985 | table: self.table, | |
1986 | hash_builder: self.hash_builder, | |
1987 | } | |
1988 | } | |
1989 | } | |
1990 | ||
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() | |
1994 | } | |
1995 | } | |
1996 | ||
1997 | impl<K: Debug, V: Debug, S> Debug for RawEntryMut<'_, K, V, S> { | |
1998 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1999 | match *self { | |
2000 | RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(), | |
2001 | RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(), | |
2002 | } | |
2003 | } | |
2004 | } | |
2005 | ||
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()) | |
2011 | .finish() | |
2012 | } | |
2013 | } | |
2014 | ||
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() | |
2018 | } | |
2019 | } | |
2020 | ||
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() | |
2024 | } | |
2025 | } | |
2026 | ||
2027 | /// A view into a single entry in a map, which may either be vacant or occupied. | |
2028 | /// | |
2029 | /// This `enum` is constructed from the [`entry`] method on [`HashMap`]. | |
2030 | /// | |
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>), | |
2036 | ||
2037 | /// A vacant entry. | |
2038 | Vacant(VacantEntry<'a, K, V, S>), | |
2039 | } | |
2040 | ||
2041 | impl<K: Debug, V: Debug, S> Debug for Entry<'_, K, V, S> { | |
2042 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2043 | match *self { | |
2044 | Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), | |
2045 | Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(), | |
2046 | } | |
2047 | } | |
2048 | } | |
2049 | ||
2050 | /// A view into an occupied entry in a `HashMap`. | |
2051 | /// It is part of the [`Entry`] enum. | |
2052 | /// | |
2053 | /// [`Entry`]: enum.Entry.html | |
2054 | pub struct OccupiedEntry<'a, K, V, S> { | |
2055 | hash: u64, | |
2056 | key: Option<K>, | |
2057 | elem: Bucket<(K, V)>, | |
2058 | table: &'a mut HashMap<K, V, S>, | |
2059 | } | |
2060 | ||
2061 | unsafe impl<K, V, S> Send for OccupiedEntry<'_, K, V, S> | |
2062 | where | |
2063 | K: Send, | |
2064 | V: Send, | |
2065 | S: Send, | |
2066 | { | |
2067 | } | |
2068 | unsafe impl<K, V, S> Sync for OccupiedEntry<'_, K, V, S> | |
2069 | where | |
2070 | K: Sync, | |
2071 | V: Sync, | |
2072 | S: Sync, | |
2073 | { | |
2074 | } | |
2075 | ||
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()) | |
2081 | .finish() | |
2082 | } | |
2083 | } | |
2084 | ||
2085 | /// A view into a vacant entry in a `HashMap`. | |
2086 | /// It is part of the [`Entry`] enum. | |
2087 | /// | |
2088 | /// [`Entry`]: enum.Entry.html | |
2089 | pub struct VacantEntry<'a, K, V, S> { | |
2090 | hash: u64, | |
2091 | key: K, | |
2092 | table: &'a mut HashMap<K, V, S>, | |
2093 | } | |
2094 | ||
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() | |
2098 | } | |
2099 | } | |
2100 | ||
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>; | |
2104 | ||
2105 | #[cfg_attr(feature = "inline-more", inline)] | |
2106 | fn into_iter(self) -> Iter<'a, K, V> { | |
2107 | self.iter() | |
2108 | } | |
2109 | } | |
2110 | ||
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>; | |
2114 | ||
2115 | #[cfg_attr(feature = "inline-more", inline)] | |
2116 | fn into_iter(self) -> IterMut<'a, K, V> { | |
2117 | self.iter_mut() | |
2118 | } | |
2119 | } | |
2120 | ||
2121 | impl<K, V, S> IntoIterator for HashMap<K, V, S> { | |
2122 | type Item = (K, V); | |
2123 | type IntoIter = IntoIter<K, V>; | |
2124 | ||
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 | |
2127 | /// calling this. | |
2128 | /// | |
2129 | /// # Examples | |
2130 | /// | |
2131 | /// ``` | |
2132 | /// use hashbrown::HashMap; | |
2133 | /// | |
2134 | /// let mut map = HashMap::new(); | |
2135 | /// map.insert("a", 1); | |
2136 | /// map.insert("b", 2); | |
2137 | /// map.insert("c", 3); | |
2138 | /// | |
2139 | /// // Not possible with .iter() | |
2140 | /// let vec: Vec<(&str, i32)> = map.into_iter().collect(); | |
2141 | /// ``` | |
2142 | #[cfg_attr(feature = "inline-more", inline)] | |
2143 | fn into_iter(self) -> IntoIter<K, V> { | |
2144 | IntoIter { | |
2145 | inner: self.table.into_iter(), | |
2146 | } | |
2147 | } | |
2148 | } | |
2149 | ||
2150 | impl<'a, K, V> Iterator for Iter<'a, K, V> { | |
2151 | type Item = (&'a K, &'a V); | |
2152 | ||
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() { | |
2157 | Some(x) => unsafe { | |
2158 | let r = x.as_ref(); | |
2159 | Some((&r.0, &r.1)) | |
2160 | }, | |
2161 | None => None, | |
2162 | } | |
2163 | } | |
2164 | #[cfg_attr(feature = "inline-more", inline)] | |
2165 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2166 | self.inner.size_hint() | |
2167 | } | |
2168 | } | |
2169 | impl<K, V> ExactSizeIterator for Iter<'_, K, V> { | |
2170 | #[cfg_attr(feature = "inline-more", inline)] | |
2171 | fn len(&self) -> usize { | |
2172 | self.inner.len() | |
2173 | } | |
2174 | } | |
2175 | ||
2176 | impl<K, V> FusedIterator for Iter<'_, K, V> {} | |
2177 | ||
2178 | impl<'a, K, V> Iterator for IterMut<'a, K, V> { | |
2179 | type Item = (&'a K, &'a mut V); | |
2180 | ||
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() { | |
2185 | Some(x) => unsafe { | |
2186 | let r = x.as_mut(); | |
2187 | Some((&r.0, &mut r.1)) | |
2188 | }, | |
2189 | None => None, | |
2190 | } | |
2191 | } | |
2192 | #[cfg_attr(feature = "inline-more", inline)] | |
2193 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2194 | self.inner.size_hint() | |
2195 | } | |
2196 | } | |
2197 | impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { | |
2198 | #[cfg_attr(feature = "inline-more", inline)] | |
2199 | fn len(&self) -> usize { | |
2200 | self.inner.len() | |
2201 | } | |
2202 | } | |
2203 | impl<K, V> FusedIterator for IterMut<'_, K, V> {} | |
2204 | ||
2205 | impl<K, V> fmt::Debug for IterMut<'_, K, V> | |
2206 | where | |
2207 | K: fmt::Debug, | |
2208 | V: fmt::Debug, | |
2209 | { | |
2210 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2211 | f.debug_list().entries(self.iter()).finish() | |
2212 | } | |
2213 | } | |
2214 | ||
2215 | impl<K, V> Iterator for IntoIter<K, V> { | |
2216 | type Item = (K, V); | |
2217 | ||
2218 | #[cfg_attr(feature = "inline-more", inline)] | |
2219 | fn next(&mut self) -> Option<(K, V)> { | |
2220 | self.inner.next() | |
2221 | } | |
2222 | #[cfg_attr(feature = "inline-more", inline)] | |
2223 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2224 | self.inner.size_hint() | |
2225 | } | |
2226 | } | |
2227 | impl<K, V> ExactSizeIterator for IntoIter<K, V> { | |
2228 | #[cfg_attr(feature = "inline-more", inline)] | |
2229 | fn len(&self) -> usize { | |
2230 | self.inner.len() | |
2231 | } | |
2232 | } | |
2233 | impl<K, V> FusedIterator for IntoIter<K, V> {} | |
2234 | ||
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() | |
2238 | } | |
2239 | } | |
2240 | ||
2241 | impl<'a, K, V> Iterator for Keys<'a, K, V> { | |
2242 | type Item = &'a K; | |
2243 | ||
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), | |
2249 | None => None, | |
2250 | } | |
2251 | } | |
2252 | #[cfg_attr(feature = "inline-more", inline)] | |
2253 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2254 | self.inner.size_hint() | |
2255 | } | |
2256 | } | |
2257 | impl<K, V> ExactSizeIterator for Keys<'_, K, V> { | |
2258 | #[cfg_attr(feature = "inline-more", inline)] | |
2259 | fn len(&self) -> usize { | |
2260 | self.inner.len() | |
2261 | } | |
2262 | } | |
2263 | impl<K, V> FusedIterator for Keys<'_, K, V> {} | |
2264 | ||
2265 | impl<'a, K, V> Iterator for Values<'a, K, V> { | |
2266 | type Item = &'a V; | |
2267 | ||
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), | |
2273 | None => None, | |
2274 | } | |
2275 | } | |
2276 | #[cfg_attr(feature = "inline-more", inline)] | |
2277 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2278 | self.inner.size_hint() | |
2279 | } | |
2280 | } | |
2281 | impl<K, V> ExactSizeIterator for Values<'_, K, V> { | |
2282 | #[cfg_attr(feature = "inline-more", inline)] | |
2283 | fn len(&self) -> usize { | |
2284 | self.inner.len() | |
2285 | } | |
2286 | } | |
2287 | impl<K, V> FusedIterator for Values<'_, K, V> {} | |
2288 | ||
2289 | impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { | |
2290 | type Item = &'a mut V; | |
2291 | ||
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), | |
2297 | None => None, | |
2298 | } | |
2299 | } | |
2300 | #[cfg_attr(feature = "inline-more", inline)] | |
2301 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2302 | self.inner.size_hint() | |
2303 | } | |
2304 | } | |
2305 | impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { | |
2306 | #[cfg_attr(feature = "inline-more", inline)] | |
2307 | fn len(&self) -> usize { | |
2308 | self.inner.len() | |
2309 | } | |
2310 | } | |
2311 | impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} | |
2312 | ||
2313 | impl<K, V> fmt::Debug for ValuesMut<'_, K, V> | |
2314 | where | |
2315 | K: fmt::Debug, | |
2316 | V: fmt::Debug, | |
2317 | { | |
2318 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2319 | f.debug_list().entries(self.inner.iter()).finish() | |
2320 | } | |
2321 | } | |
2322 | ||
2323 | impl<'a, K, V> Iterator for Drain<'a, K, V> { | |
2324 | type Item = (K, V); | |
2325 | ||
2326 | #[cfg_attr(feature = "inline-more", inline)] | |
2327 | fn next(&mut self) -> Option<(K, V)> { | |
2328 | self.inner.next() | |
2329 | } | |
2330 | #[cfg_attr(feature = "inline-more", inline)] | |
2331 | fn size_hint(&self) -> (usize, Option<usize>) { | |
2332 | self.inner.size_hint() | |
2333 | } | |
2334 | } | |
2335 | impl<K, V> ExactSizeIterator for Drain<'_, K, V> { | |
2336 | #[cfg_attr(feature = "inline-more", inline)] | |
2337 | fn len(&self) -> usize { | |
2338 | self.inner.len() | |
2339 | } | |
2340 | } | |
2341 | impl<K, V> FusedIterator for Drain<'_, K, V> {} | |
2342 | ||
2343 | impl<K, V> fmt::Debug for Drain<'_, K, V> | |
2344 | where | |
2345 | K: fmt::Debug, | |
2346 | V: fmt::Debug, | |
2347 | { | |
2348 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2349 | f.debug_list().entries(self.iter()).finish() | |
2350 | } | |
2351 | } | |
2352 | ||
2353 | impl<'a, K, V, S> Entry<'a, K, V, S> { | |
2354 | /// Sets the value of the entry, and returns an OccupiedEntry. | |
2355 | /// | |
2356 | /// # Examples | |
2357 | /// | |
2358 | /// ``` | |
2359 | /// use hashbrown::HashMap; | |
2360 | /// | |
2361 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2362 | /// let entry = map.entry("horseyland").insert(37); | |
2363 | /// | |
2364 | /// assert_eq!(entry.key(), &"horseyland"); | |
2365 | /// ``` | |
2366 | #[cfg_attr(feature = "inline-more", inline)] | |
2367 | pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S> | |
2368 | where | |
2369 | K: Hash, | |
2370 | S: BuildHasher, | |
2371 | { | |
2372 | match self { | |
2373 | Entry::Occupied(mut entry) => { | |
2374 | entry.insert(value); | |
2375 | entry | |
2376 | } | |
2377 | Entry::Vacant(entry) => entry.insert_entry(value), | |
2378 | } | |
2379 | } | |
2380 | ||
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. | |
2383 | /// | |
2384 | /// # Examples | |
2385 | /// | |
2386 | /// ``` | |
2387 | /// use hashbrown::HashMap; | |
2388 | /// | |
2389 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2390 | /// | |
2391 | /// map.entry("poneyland").or_insert(3); | |
2392 | /// assert_eq!(map["poneyland"], 3); | |
2393 | /// | |
2394 | /// *map.entry("poneyland").or_insert(10) *= 2; | |
2395 | /// assert_eq!(map["poneyland"], 6); | |
2396 | /// ``` | |
2397 | #[cfg_attr(feature = "inline-more", inline)] | |
2398 | pub fn or_insert(self, default: V) -> &'a mut V | |
2399 | where | |
2400 | K: Hash, | |
2401 | S: BuildHasher, | |
2402 | { | |
2403 | match self { | |
2404 | Entry::Occupied(entry) => entry.into_mut(), | |
2405 | Entry::Vacant(entry) => entry.insert(default), | |
2406 | } | |
2407 | } | |
2408 | ||
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. | |
2411 | /// | |
2412 | /// # Examples | |
2413 | /// | |
2414 | /// ``` | |
2415 | /// use hashbrown::HashMap; | |
2416 | /// | |
2417 | /// let mut map: HashMap<&str, String> = HashMap::new(); | |
2418 | /// let s = "hoho".to_string(); | |
2419 | /// | |
2420 | /// map.entry("poneyland").or_insert_with(|| s); | |
2421 | /// | |
2422 | /// assert_eq!(map["poneyland"], "hoho".to_string()); | |
2423 | /// ``` | |
2424 | #[cfg_attr(feature = "inline-more", inline)] | |
2425 | pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V | |
2426 | where | |
2427 | K: Hash, | |
2428 | S: BuildHasher, | |
2429 | { | |
2430 | match self { | |
2431 | Entry::Occupied(entry) => entry.into_mut(), | |
2432 | Entry::Vacant(entry) => entry.insert(default()), | |
2433 | } | |
2434 | } | |
2435 | ||
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 | |
2438 | /// entry. | |
2439 | /// | |
2440 | /// # Examples | |
2441 | /// | |
2442 | /// ``` | |
2443 | /// use hashbrown::HashMap; | |
2444 | /// | |
2445 | /// let mut map: HashMap<&str, usize> = HashMap::new(); | |
2446 | /// | |
2447 | /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count()); | |
2448 | /// | |
2449 | /// assert_eq!(map["poneyland"], 9); | |
2450 | /// ``` | |
2451 | #[cfg_attr(feature = "inline-more", inline)] | |
2452 | pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V | |
2453 | where | |
2454 | K: Hash, | |
2455 | S: BuildHasher, | |
2456 | { | |
2457 | match self { | |
2458 | Entry::Occupied(entry) => entry.into_mut(), | |
2459 | Entry::Vacant(entry) => { | |
2460 | let value = default(entry.key()); | |
2461 | entry.insert(value) | |
2462 | } | |
2463 | } | |
2464 | } | |
2465 | ||
2466 | /// Returns a reference to this entry's key. | |
2467 | /// | |
2468 | /// # Examples | |
2469 | /// | |
2470 | /// ``` | |
2471 | /// use hashbrown::HashMap; | |
2472 | /// | |
2473 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2474 | /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); | |
2475 | /// ``` | |
2476 | #[cfg_attr(feature = "inline-more", inline)] | |
2477 | pub fn key(&self) -> &K { | |
2478 | match *self { | |
2479 | Entry::Occupied(ref entry) => entry.key(), | |
2480 | Entry::Vacant(ref entry) => entry.key(), | |
2481 | } | |
2482 | } | |
2483 | ||
2484 | /// Provides in-place mutable access to an occupied entry before any | |
2485 | /// potential inserts into the map. | |
2486 | /// | |
2487 | /// # Examples | |
2488 | /// | |
2489 | /// ``` | |
2490 | /// use hashbrown::HashMap; | |
2491 | /// | |
2492 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2493 | /// | |
2494 | /// map.entry("poneyland") | |
2495 | /// .and_modify(|e| { *e += 1 }) | |
2496 | /// .or_insert(42); | |
2497 | /// assert_eq!(map["poneyland"], 42); | |
2498 | /// | |
2499 | /// map.entry("poneyland") | |
2500 | /// .and_modify(|e| { *e += 1 }) | |
2501 | /// .or_insert(42); | |
2502 | /// assert_eq!(map["poneyland"], 43); | |
2503 | /// ``` | |
2504 | #[cfg_attr(feature = "inline-more", inline)] | |
2505 | pub fn and_modify<F>(self, f: F) -> Self | |
2506 | where | |
2507 | F: FnOnce(&mut V), | |
2508 | { | |
2509 | match self { | |
2510 | Entry::Occupied(mut entry) => { | |
2511 | f(entry.get_mut()); | |
2512 | Entry::Occupied(entry) | |
2513 | } | |
2514 | Entry::Vacant(entry) => Entry::Vacant(entry), | |
2515 | } | |
2516 | } | |
2517 | ||
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. | |
2521 | /// | |
2522 | /// # Examples | |
2523 | /// | |
2524 | /// ``` | |
2525 | /// use hashbrown::HashMap; | |
2526 | /// use hashbrown::hash_map::Entry; | |
2527 | /// | |
2528 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2529 | /// | |
2530 | /// let entry = map | |
2531 | /// .entry("poneyland") | |
2532 | /// .and_replace_entry_with(|_k, _v| panic!()); | |
2533 | /// | |
2534 | /// match entry { | |
2535 | /// Entry::Vacant(e) => { | |
2536 | /// assert_eq!(e.key(), &"poneyland"); | |
2537 | /// } | |
2538 | /// Entry::Occupied(_) => panic!(), | |
2539 | /// } | |
2540 | /// | |
2541 | /// map.insert("poneyland", 42); | |
2542 | /// | |
2543 | /// let entry = map | |
2544 | /// .entry("poneyland") | |
2545 | /// .and_replace_entry_with(|k, v| { | |
2546 | /// assert_eq!(k, &"poneyland"); | |
2547 | /// assert_eq!(v, 42); | |
2548 | /// Some(v + 1) | |
2549 | /// }); | |
2550 | /// | |
2551 | /// match entry { | |
2552 | /// Entry::Occupied(e) => { | |
2553 | /// assert_eq!(e.key(), &"poneyland"); | |
2554 | /// assert_eq!(e.get(), &43); | |
2555 | /// } | |
2556 | /// Entry::Vacant(_) => panic!(), | |
2557 | /// } | |
2558 | /// | |
2559 | /// assert_eq!(map["poneyland"], 43); | |
2560 | /// | |
2561 | /// let entry = map | |
2562 | /// .entry("poneyland") | |
2563 | /// .and_replace_entry_with(|_k, _v| None); | |
2564 | /// | |
2565 | /// match entry { | |
2566 | /// Entry::Vacant(e) => assert_eq!(e.key(), &"poneyland"), | |
2567 | /// Entry::Occupied(_) => panic!(), | |
2568 | /// } | |
2569 | /// | |
2570 | /// assert!(!map.contains_key("poneyland")); | |
2571 | /// ``` | |
2572 | #[cfg_attr(feature = "inline-more", inline)] | |
2573 | pub fn and_replace_entry_with<F>(self, f: F) -> Self | |
2574 | where | |
2575 | F: FnOnce(&K, V) -> Option<V>, | |
2576 | { | |
2577 | match self { | |
2578 | Entry::Occupied(entry) => entry.replace_entry_with(f), | |
2579 | Entry::Vacant(_) => self, | |
2580 | } | |
2581 | } | |
2582 | } | |
2583 | ||
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. | |
2587 | /// | |
2588 | /// # Examples | |
2589 | /// | |
2590 | /// ``` | |
2591 | /// use hashbrown::HashMap; | |
2592 | /// | |
2593 | /// let mut map: HashMap<&str, Option<u32>> = HashMap::new(); | |
2594 | /// map.entry("poneyland").or_default(); | |
2595 | /// | |
2596 | /// assert_eq!(map["poneyland"], None); | |
2597 | /// ``` | |
2598 | #[cfg_attr(feature = "inline-more", inline)] | |
2599 | pub fn or_default(self) -> &'a mut V | |
2600 | where | |
2601 | K: Hash, | |
2602 | S: BuildHasher, | |
2603 | { | |
2604 | match self { | |
2605 | Entry::Occupied(entry) => entry.into_mut(), | |
2606 | Entry::Vacant(entry) => entry.insert(Default::default()), | |
2607 | } | |
2608 | } | |
2609 | } | |
2610 | ||
2611 | impl<'a, K, V, S> OccupiedEntry<'a, K, V, S> { | |
2612 | /// Gets a reference to the key in the entry. | |
2613 | /// | |
2614 | /// # Examples | |
2615 | /// | |
2616 | /// ``` | |
2617 | /// use hashbrown::HashMap; | |
2618 | /// | |
2619 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2620 | /// map.entry("poneyland").or_insert(12); | |
2621 | /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); | |
2622 | /// ``` | |
2623 | #[cfg_attr(feature = "inline-more", inline)] | |
2624 | pub fn key(&self) -> &K { | |
2625 | unsafe { &self.elem.as_ref().0 } | |
2626 | } | |
2627 | ||
2628 | /// Take the ownership of the key and value from the map. | |
2629 | /// | |
2630 | /// # Examples | |
2631 | /// | |
2632 | /// ``` | |
2633 | /// use hashbrown::HashMap; | |
2634 | /// use hashbrown::hash_map::Entry; | |
2635 | /// | |
2636 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2637 | /// map.entry("poneyland").or_insert(12); | |
2638 | /// | |
2639 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
2640 | /// // We delete the entry from the map. | |
2641 | /// o.remove_entry(); | |
2642 | /// } | |
2643 | /// | |
2644 | /// assert_eq!(map.contains_key("poneyland"), false); | |
2645 | /// ``` | |
2646 | #[cfg_attr(feature = "inline-more", inline)] | |
2647 | pub fn remove_entry(self) -> (K, V) { | |
2648 | unsafe { self.table.table.remove(self.elem) } | |
2649 | } | |
2650 | ||
2651 | /// Gets a reference to the value in the entry. | |
2652 | /// | |
2653 | /// # Examples | |
2654 | /// | |
2655 | /// ``` | |
2656 | /// use hashbrown::HashMap; | |
2657 | /// use hashbrown::hash_map::Entry; | |
2658 | /// | |
2659 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2660 | /// map.entry("poneyland").or_insert(12); | |
2661 | /// | |
2662 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
2663 | /// assert_eq!(o.get(), &12); | |
2664 | /// } | |
2665 | /// ``` | |
2666 | #[cfg_attr(feature = "inline-more", inline)] | |
2667 | pub fn get(&self) -> &V { | |
2668 | unsafe { &self.elem.as_ref().1 } | |
2669 | } | |
2670 | ||
2671 | /// Gets a mutable reference to the value in the entry. | |
2672 | /// | |
2673 | /// If you need a reference to the `OccupiedEntry` which may outlive the | |
2674 | /// destruction of the `Entry` value, see [`into_mut`]. | |
2675 | /// | |
2676 | /// [`into_mut`]: #method.into_mut | |
2677 | /// | |
2678 | /// # Examples | |
2679 | /// | |
2680 | /// ``` | |
2681 | /// use hashbrown::HashMap; | |
2682 | /// use hashbrown::hash_map::Entry; | |
2683 | /// | |
2684 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2685 | /// map.entry("poneyland").or_insert(12); | |
2686 | /// | |
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); | |
2691 | /// | |
2692 | /// // We can use the same Entry multiple times. | |
2693 | /// *o.get_mut() += 2; | |
2694 | /// } | |
2695 | /// | |
2696 | /// assert_eq!(map["poneyland"], 24); | |
2697 | /// ``` | |
2698 | #[cfg_attr(feature = "inline-more", inline)] | |
2699 | pub fn get_mut(&mut self) -> &mut V { | |
2700 | unsafe { &mut self.elem.as_mut().1 } | |
2701 | } | |
2702 | ||
2703 | /// Converts the OccupiedEntry into a mutable reference to the value in the entry | |
2704 | /// with a lifetime bound to the map itself. | |
2705 | /// | |
2706 | /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`]. | |
2707 | /// | |
2708 | /// [`get_mut`]: #method.get_mut | |
2709 | /// | |
2710 | /// # Examples | |
2711 | /// | |
2712 | /// ``` | |
2713 | /// use hashbrown::HashMap; | |
2714 | /// use hashbrown::hash_map::Entry; | |
2715 | /// | |
2716 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2717 | /// map.entry("poneyland").or_insert(12); | |
2718 | /// | |
2719 | /// assert_eq!(map["poneyland"], 12); | |
2720 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
2721 | /// *o.into_mut() += 10; | |
2722 | /// } | |
2723 | /// | |
2724 | /// assert_eq!(map["poneyland"], 22); | |
2725 | /// ``` | |
2726 | #[cfg_attr(feature = "inline-more", inline)] | |
2727 | pub fn into_mut(self) -> &'a mut V { | |
2728 | unsafe { &mut self.elem.as_mut().1 } | |
2729 | } | |
2730 | ||
2731 | /// Sets the value of the entry, and returns the entry's old value. | |
2732 | /// | |
2733 | /// # Examples | |
2734 | /// | |
2735 | /// ``` | |
2736 | /// use hashbrown::HashMap; | |
2737 | /// use hashbrown::hash_map::Entry; | |
2738 | /// | |
2739 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2740 | /// map.entry("poneyland").or_insert(12); | |
2741 | /// | |
2742 | /// if let Entry::Occupied(mut o) = map.entry("poneyland") { | |
2743 | /// assert_eq!(o.insert(15), 12); | |
2744 | /// } | |
2745 | /// | |
2746 | /// assert_eq!(map["poneyland"], 15); | |
2747 | /// ``` | |
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); | |
2752 | value | |
2753 | } | |
2754 | ||
2755 | /// Takes the value out of the entry, and returns it. | |
2756 | /// | |
2757 | /// # Examples | |
2758 | /// | |
2759 | /// ``` | |
2760 | /// use hashbrown::HashMap; | |
2761 | /// use hashbrown::hash_map::Entry; | |
2762 | /// | |
2763 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2764 | /// map.entry("poneyland").or_insert(12); | |
2765 | /// | |
2766 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
2767 | /// assert_eq!(o.remove(), 12); | |
2768 | /// } | |
2769 | /// | |
2770 | /// assert_eq!(map.contains_key("poneyland"), false); | |
2771 | /// ``` | |
2772 | #[cfg_attr(feature = "inline-more", inline)] | |
2773 | pub fn remove(self) -> V { | |
2774 | self.remove_entry().1 | |
2775 | } | |
2776 | ||
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. | |
2779 | /// | |
2780 | /// # Examples | |
2781 | /// | |
2782 | /// ``` | |
2783 | /// use hashbrown::hash_map::{Entry, HashMap}; | |
2784 | /// use std::rc::Rc; | |
2785 | /// | |
2786 | /// let mut map: HashMap<Rc<String>, u32> = HashMap::new(); | |
2787 | /// map.insert(Rc::new("Stringthing".to_string()), 15); | |
2788 | /// | |
2789 | /// let my_key = Rc::new("Stringthing".to_string()); | |
2790 | /// | |
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); | |
2794 | /// } | |
2795 | /// | |
2796 | /// ``` | |
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() }; | |
2800 | ||
2801 | let old_key = mem::replace(&mut entry.0, self.key.unwrap()); | |
2802 | let old_value = mem::replace(&mut entry.1, value); | |
2803 | ||
2804 | (old_key, old_value) | |
2805 | } | |
2806 | ||
2807 | /// Replaces the key in the hash map with the key used to create this entry. | |
2808 | /// | |
2809 | /// # Examples | |
2810 | /// | |
2811 | /// ``` | |
2812 | /// use hashbrown::hash_map::{Entry, HashMap}; | |
2813 | /// use std::rc::Rc; | |
2814 | /// | |
2815 | /// let mut map: HashMap<Rc<String>, u32> = HashMap::new(); | |
2816 | /// let mut known_strings: Vec<Rc<String>> = Vec::new(); | |
2817 | /// | |
2818 | /// // Initialise known strings, run program, etc. | |
2819 | /// | |
2820 | /// reclaim_memory(&mut map, &known_strings); | |
2821 | /// | |
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(); | |
2827 | /// } | |
2828 | /// } | |
2829 | /// } | |
2830 | /// ``` | |
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()) | |
2835 | } | |
2836 | ||
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. | |
2840 | /// | |
2841 | /// # Examples | |
2842 | /// | |
2843 | /// ``` | |
2844 | /// use hashbrown::HashMap; | |
2845 | /// use hashbrown::hash_map::Entry; | |
2846 | /// | |
2847 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2848 | /// map.insert("poneyland", 42); | |
2849 | /// | |
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); | |
2855 | /// Some(v + 1) | |
2856 | /// }) | |
2857 | /// } | |
2858 | /// Entry::Vacant(_) => panic!(), | |
2859 | /// }; | |
2860 | /// | |
2861 | /// match entry { | |
2862 | /// Entry::Occupied(e) => { | |
2863 | /// assert_eq!(e.key(), &"poneyland"); | |
2864 | /// assert_eq!(e.get(), &43); | |
2865 | /// } | |
2866 | /// Entry::Vacant(_) => panic!(), | |
2867 | /// } | |
2868 | /// | |
2869 | /// assert_eq!(map["poneyland"], 43); | |
2870 | /// | |
2871 | /// let entry = match map.entry("poneyland") { | |
2872 | /// Entry::Occupied(e) => e.replace_entry_with(|_k, _v| None), | |
2873 | /// Entry::Vacant(_) => panic!(), | |
2874 | /// }; | |
2875 | /// | |
2876 | /// match entry { | |
2877 | /// Entry::Vacant(e) => { | |
2878 | /// assert_eq!(e.key(), &"poneyland"); | |
2879 | /// } | |
2880 | /// Entry::Occupied(_) => panic!(), | |
2881 | /// } | |
2882 | /// | |
2883 | /// assert!(!map.contains_key("poneyland")); | |
2884 | /// ``` | |
2885 | #[cfg_attr(feature = "inline-more", inline)] | |
2886 | pub fn replace_entry_with<F>(self, f: F) -> Entry<'a, K, V, S> | |
2887 | where | |
2888 | F: FnOnce(&K, V) -> Option<V>, | |
2889 | { | |
2890 | unsafe { | |
2891 | let mut spare_key = None; | |
2892 | ||
2893 | self.table | |
2894 | .table | |
2895 | .replace_bucket_with(self.elem.clone(), |(key, value)| { | |
2896 | if let Some(new_value) = f(&key, value) { | |
2897 | Some((key, new_value)) | |
2898 | } else { | |
2899 | spare_key = Some(key); | |
2900 | None | |
2901 | } | |
2902 | }); | |
2903 | ||
2904 | if let Some(key) = spare_key { | |
2905 | Entry::Vacant(VacantEntry { | |
2906 | hash: self.hash, | |
2907 | key, | |
2908 | table: self.table, | |
2909 | }) | |
2910 | } else { | |
2911 | Entry::Occupied(self) | |
2912 | } | |
2913 | } | |
2914 | } | |
2915 | } | |
2916 | ||
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`. | |
2920 | /// | |
2921 | /// # Examples | |
2922 | /// | |
2923 | /// ``` | |
2924 | /// use hashbrown::HashMap; | |
2925 | /// | |
2926 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2927 | /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); | |
2928 | /// ``` | |
2929 | #[cfg_attr(feature = "inline-more", inline)] | |
2930 | pub fn key(&self) -> &K { | |
2931 | &self.key | |
2932 | } | |
2933 | ||
2934 | /// Take ownership of the key. | |
2935 | /// | |
2936 | /// # Examples | |
2937 | /// | |
2938 | /// ``` | |
2939 | /// use hashbrown::HashMap; | |
2940 | /// use hashbrown::hash_map::Entry; | |
2941 | /// | |
2942 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2943 | /// | |
2944 | /// if let Entry::Vacant(v) = map.entry("poneyland") { | |
2945 | /// v.into_key(); | |
2946 | /// } | |
2947 | /// ``` | |
2948 | #[cfg_attr(feature = "inline-more", inline)] | |
2949 | pub fn into_key(self) -> K { | |
2950 | self.key | |
2951 | } | |
2952 | ||
2953 | /// Sets the value of the entry with the VacantEntry's key, | |
2954 | /// and returns a mutable reference to it. | |
2955 | /// | |
2956 | /// # Examples | |
2957 | /// | |
2958 | /// ``` | |
2959 | /// use hashbrown::HashMap; | |
2960 | /// use hashbrown::hash_map::Entry; | |
2961 | /// | |
2962 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2963 | /// | |
2964 | /// if let Entry::Vacant(o) = map.entry("poneyland") { | |
2965 | /// o.insert(37); | |
2966 | /// } | |
2967 | /// assert_eq!(map["poneyland"], 37); | |
2968 | /// ``` | |
2969 | #[cfg_attr(feature = "inline-more", inline)] | |
2970 | pub fn insert(self, value: V) -> &'a mut V | |
2971 | where | |
2972 | K: Hash, | |
2973 | S: BuildHasher, | |
2974 | { | |
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) | |
2979 | }); | |
2980 | &mut entry.1 | |
2981 | } | |
2982 | ||
2983 | #[cfg_attr(feature = "inline-more", inline)] | |
2984 | fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S> | |
2985 | where | |
2986 | K: Hash, | |
2987 | S: BuildHasher, | |
2988 | { | |
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) | |
2992 | }); | |
2993 | OccupiedEntry { | |
2994 | hash: self.hash, | |
2995 | key: None, | |
2996 | elem, | |
2997 | table: self.table, | |
2998 | } | |
2999 | } | |
3000 | } | |
3001 | ||
3002 | impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> | |
3003 | where | |
3004 | K: Eq + Hash, | |
3005 | S: BuildHasher + Default, | |
3006 | { | |
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)| { | |
3012 | map.insert(k, v); | |
3013 | }); | |
3014 | map | |
3015 | } | |
3016 | } | |
3017 | ||
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> | |
3021 | where | |
3022 | K: Eq + Hash, | |
3023 | S: BuildHasher, | |
3024 | { | |
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() { | |
3033 | iter.size_hint().0 | |
3034 | } else { | |
3035 | (iter.size_hint().0 + 1) / 2 | |
3036 | }; | |
3037 | self.reserve(reserve); | |
3038 | iter.for_each(move |(k, v)| { | |
3039 | self.insert(k, v); | |
3040 | }); | |
3041 | } | |
3042 | ||
3043 | #[inline] | |
3044 | #[cfg(feature = "nightly")] | |
3045 | fn extend_one(&mut self, (k, v): (K, V)) { | |
3046 | self.insert(k, v); | |
3047 | } | |
3048 | ||
3049 | #[inline] | |
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() { | |
3057 | additional | |
3058 | } else { | |
3059 | (additional + 1) / 2 | |
3060 | }; | |
3061 | self.reserve(reserve); | |
3062 | } | |
3063 | } | |
3064 | ||
3065 | impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S> | |
3066 | where | |
3067 | K: Eq + Hash + Copy, | |
3068 | V: Copy, | |
3069 | S: BuildHasher, | |
3070 | { | |
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))); | |
3074 | } | |
3075 | ||
3076 | #[inline] | |
3077 | #[cfg(feature = "nightly")] | |
3078 | fn extend_one(&mut self, (k, v): (&'a K, &'a V)) { | |
3079 | self.insert(*k, *v); | |
3080 | } | |
3081 | ||
3082 | #[inline] | |
3083 | #[cfg(feature = "nightly")] | |
3084 | fn extend_reserve(&mut self, additional: usize) { | |
3085 | Extend::<(K, V)>::extend_reserve(self, additional); | |
3086 | } | |
3087 | } | |
3088 | ||
3089 | #[allow(dead_code)] | |
3090 | fn assert_covariance() { | |
3091 | fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> { | |
3092 | v | |
3093 | } | |
3094 | fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> { | |
3095 | v | |
3096 | } | |
3097 | fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> { | |
3098 | v | |
3099 | } | |
3100 | fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> { | |
3101 | v | |
3102 | } | |
3103 | fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> { | |
3104 | v | |
3105 | } | |
3106 | fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> { | |
3107 | v | |
3108 | } | |
3109 | fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> { | |
3110 | v | |
3111 | } | |
3112 | fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> { | |
3113 | v | |
3114 | } | |
3115 | fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> { | |
3116 | v | |
3117 | } | |
3118 | fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> { | |
3119 | v | |
3120 | } | |
3121 | fn drain<'new>( | |
3122 | d: Drain<'static, &'static str, &'static str>, | |
3123 | ) -> Drain<'new, &'new str, &'new str> { | |
3124 | d | |
3125 | } | |
3126 | } | |
3127 | ||
3128 | #[cfg(test)] | |
3129 | mod test_map { | |
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; | |
3136 | use std::usize; | |
3137 | use std::vec::Vec; | |
3138 | ||
3139 | #[test] | |
3140 | fn test_zero_capacities() { | |
3141 | type HM = HashMap<i32, i32>; | |
3142 | ||
3143 | let m = HM::new(); | |
3144 | assert_eq!(m.capacity(), 0); | |
3145 | ||
3146 | let m = HM::default(); | |
3147 | assert_eq!(m.capacity(), 0); | |
3148 | ||
3149 | let m = HM::with_hasher(DefaultHashBuilder::default()); | |
3150 | assert_eq!(m.capacity(), 0); | |
3151 | ||
3152 | let m = HM::with_capacity(0); | |
3153 | assert_eq!(m.capacity(), 0); | |
3154 | ||
3155 | let m = HM::with_capacity_and_hasher(0, DefaultHashBuilder::default()); | |
3156 | assert_eq!(m.capacity(), 0); | |
3157 | ||
3158 | let mut m = HM::new(); | |
3159 | m.insert(1, 1); | |
3160 | m.insert(2, 2); | |
3161 | m.remove(&1); | |
3162 | m.remove(&2); | |
3163 | m.shrink_to_fit(); | |
3164 | assert_eq!(m.capacity(), 0); | |
3165 | ||
3166 | let mut m = HM::new(); | |
3167 | m.reserve(0); | |
3168 | assert_eq!(m.capacity(), 0); | |
3169 | } | |
3170 | ||
3171 | #[test] | |
3172 | fn test_create_capacity_zero() { | |
3173 | let mut m = HashMap::with_capacity(0); | |
3174 | ||
3175 | assert!(m.insert(1, 1).is_none()); | |
3176 | ||
3177 | assert!(m.contains_key(&1)); | |
3178 | assert!(!m.contains_key(&0)); | |
3179 | } | |
3180 | ||
3181 | #[test] | |
3182 | fn test_insert() { | |
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); | |
3191 | } | |
3192 | ||
3193 | #[test] | |
3194 | fn test_clone() { | |
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); | |
3201 | let m2 = m.clone(); | |
3202 | assert_eq!(*m2.get(&1).unwrap(), 2); | |
3203 | assert_eq!(*m2.get(&2).unwrap(), 4); | |
3204 | assert_eq!(m2.len(), 2); | |
3205 | } | |
3206 | ||
3207 | #[test] | |
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); | |
3216 | m2.clone_from(&m); | |
3217 | assert_eq!(*m2.get(&1).unwrap(), 2); | |
3218 | assert_eq!(*m2.get(&2).unwrap(), 4); | |
3219 | assert_eq!(m2.len(), 2); | |
3220 | } | |
3221 | ||
3222 | thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) } | |
3223 | ||
3224 | #[derive(Hash, PartialEq, Eq)] | |
3225 | struct Droppable { | |
3226 | k: usize, | |
3227 | } | |
3228 | ||
3229 | impl Droppable { | |
3230 | fn new(k: usize) -> Droppable { | |
3231 | DROP_VECTOR.with(|slot| { | |
3232 | slot.borrow_mut()[k] += 1; | |
3233 | }); | |
3234 | ||
3235 | Droppable { k } | |
3236 | } | |
3237 | } | |
3238 | ||
3239 | impl Drop for Droppable { | |
3240 | fn drop(&mut self) { | |
3241 | DROP_VECTOR.with(|slot| { | |
3242 | slot.borrow_mut()[self.k] -= 1; | |
3243 | }); | |
3244 | } | |
3245 | } | |
3246 | ||
3247 | impl Clone for Droppable { | |
3248 | fn clone(&self) -> Self { | |
3249 | Droppable::new(self.k) | |
3250 | } | |
3251 | } | |
3252 | ||
3253 | #[test] | |
3254 | fn test_drops() { | |
3255 | DROP_VECTOR.with(|slot| { | |
3256 | *slot.borrow_mut() = vec![0; 200]; | |
3257 | }); | |
3258 | ||
3259 | { | |
3260 | let mut m = HashMap::new(); | |
3261 | ||
3262 | DROP_VECTOR.with(|v| { | |
3263 | for i in 0..200 { | |
3264 | assert_eq!(v.borrow()[i], 0); | |
3265 | } | |
3266 | }); | |
3267 | ||
3268 | for i in 0..100 { | |
3269 | let d1 = Droppable::new(i); | |
3270 | let d2 = Droppable::new(i + 100); | |
3271 | m.insert(d1, d2); | |
3272 | } | |
3273 | ||
3274 | DROP_VECTOR.with(|v| { | |
3275 | for i in 0..200 { | |
3276 | assert_eq!(v.borrow()[i], 1); | |
3277 | } | |
3278 | }); | |
3279 | ||
3280 | for i in 0..50 { | |
3281 | let k = Droppable::new(i); | |
3282 | let v = m.remove(&k); | |
3283 | ||
3284 | assert!(v.is_some()); | |
3285 | ||
3286 | DROP_VECTOR.with(|v| { | |
3287 | assert_eq!(v.borrow()[i], 1); | |
3288 | assert_eq!(v.borrow()[i + 100], 1); | |
3289 | }); | |
3290 | } | |
3291 | ||
3292 | DROP_VECTOR.with(|v| { | |
3293 | for i in 0..50 { | |
3294 | assert_eq!(v.borrow()[i], 0); | |
3295 | assert_eq!(v.borrow()[i + 100], 0); | |
3296 | } | |
3297 | ||
3298 | for i in 50..100 { | |
3299 | assert_eq!(v.borrow()[i], 1); | |
3300 | assert_eq!(v.borrow()[i + 100], 1); | |
3301 | } | |
3302 | }); | |
3303 | } | |
3304 | ||
3305 | DROP_VECTOR.with(|v| { | |
3306 | for i in 0..200 { | |
3307 | assert_eq!(v.borrow()[i], 0); | |
3308 | } | |
3309 | }); | |
3310 | } | |
3311 | ||
3312 | #[test] | |
3313 | fn test_into_iter_drops() { | |
3314 | DROP_VECTOR.with(|v| { | |
3315 | *v.borrow_mut() = vec![0; 200]; | |
3316 | }); | |
3317 | ||
3318 | let hm = { | |
3319 | let mut hm = HashMap::new(); | |
3320 | ||
3321 | DROP_VECTOR.with(|v| { | |
3322 | for i in 0..200 { | |
3323 | assert_eq!(v.borrow()[i], 0); | |
3324 | } | |
3325 | }); | |
3326 | ||
3327 | for i in 0..100 { | |
3328 | let d1 = Droppable::new(i); | |
3329 | let d2 = Droppable::new(i + 100); | |
3330 | hm.insert(d1, d2); | |
3331 | } | |
3332 | ||
3333 | DROP_VECTOR.with(|v| { | |
3334 | for i in 0..200 { | |
3335 | assert_eq!(v.borrow()[i], 1); | |
3336 | } | |
3337 | }); | |
3338 | ||
3339 | hm | |
3340 | }; | |
3341 | ||
3342 | // By the way, ensure that cloning doesn't screw up the dropping. | |
3343 | drop(hm.clone()); | |
3344 | ||
3345 | { | |
3346 | let mut half = hm.into_iter().take(50); | |
3347 | ||
3348 | DROP_VECTOR.with(|v| { | |
3349 | for i in 0..200 { | |
3350 | assert_eq!(v.borrow()[i], 1); | |
3351 | } | |
3352 | }); | |
3353 | ||
3354 | for _ in half.by_ref() {} | |
3355 | ||
3356 | DROP_VECTOR.with(|v| { | |
3357 | let nk = (0..100).filter(|&i| v.borrow()[i] == 1).count(); | |
3358 | ||
3359 | let nv = (0..100).filter(|&i| v.borrow()[i + 100] == 1).count(); | |
3360 | ||
3361 | assert_eq!(nk, 50); | |
3362 | assert_eq!(nv, 50); | |
3363 | }); | |
3364 | }; | |
3365 | ||
3366 | DROP_VECTOR.with(|v| { | |
3367 | for i in 0..200 { | |
3368 | assert_eq!(v.borrow()[i], 0); | |
3369 | } | |
3370 | }); | |
3371 | } | |
3372 | ||
3373 | #[test] | |
3374 | fn test_empty_remove() { | |
3375 | let mut m: HashMap<i32, bool> = HashMap::new(); | |
3376 | assert_eq!(m.remove(&0), None); | |
3377 | } | |
3378 | ||
3379 | #[test] | |
3380 | fn test_empty_entry() { | |
3381 | let mut m: HashMap<i32, bool> = HashMap::new(); | |
3382 | match m.entry(0) { | |
3383 | Occupied(_) => panic!(), | |
3384 | Vacant(_) => {} | |
3385 | } | |
3386 | assert!(*m.entry(0).or_insert(true)); | |
3387 | assert_eq!(m.len(), 1); | |
3388 | } | |
3389 | ||
3390 | #[test] | |
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); | |
3402 | } | |
3403 | ||
3404 | #[test] | |
3405 | #[cfg_attr(miri, ignore)] // FIXME: takes too long | |
3406 | fn test_lots_of_insertions() { | |
3407 | let mut m = HashMap::new(); | |
3408 | ||
3409 | // Try this a few times to make sure we never screw up the hashmap's | |
3410 | // internal state. | |
3411 | for _ in 0..10 { | |
3412 | assert!(m.is_empty()); | |
3413 | ||
3414 | for i in 1..1001 { | |
3415 | assert!(m.insert(i, i).is_none()); | |
3416 | ||
3417 | for j in 1..=i { | |
3418 | let r = m.get(&j); | |
3419 | assert_eq!(r, Some(&j)); | |
3420 | } | |
3421 | ||
3422 | for j in i + 1..1001 { | |
3423 | let r = m.get(&j); | |
3424 | assert_eq!(r, None); | |
3425 | } | |
3426 | } | |
3427 | ||
3428 | for i in 1001..2001 { | |
3429 | assert!(!m.contains_key(&i)); | |
3430 | } | |
3431 | ||
3432 | // remove forwards | |
3433 | for i in 1..1001 { | |
3434 | assert!(m.remove(&i).is_some()); | |
3435 | ||
3436 | for j in 1..=i { | |
3437 | assert!(!m.contains_key(&j)); | |
3438 | } | |
3439 | ||
3440 | for j in i + 1..1001 { | |
3441 | assert!(m.contains_key(&j)); | |
3442 | } | |
3443 | } | |
3444 | ||
3445 | for i in 1..1001 { | |
3446 | assert!(!m.contains_key(&i)); | |
3447 | } | |
3448 | ||
3449 | for i in 1..1001 { | |
3450 | assert!(m.insert(i, i).is_none()); | |
3451 | } | |
3452 | ||
3453 | // remove backwards | |
3454 | for i in (1..1001).rev() { | |
3455 | assert!(m.remove(&i).is_some()); | |
3456 | ||
3457 | for j in i..1001 { | |
3458 | assert!(!m.contains_key(&j)); | |
3459 | } | |
3460 | ||
3461 | for j in 1..i { | |
3462 | assert!(m.contains_key(&j)); | |
3463 | } | |
3464 | } | |
3465 | } | |
3466 | } | |
3467 | ||
3468 | #[test] | |
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()); | |
3474 | let new = 100; | |
3475 | match m.get_mut(&5) { | |
3476 | None => panic!(), | |
3477 | Some(x) => *x = new, | |
3478 | } | |
3479 | assert_eq!(m.get(&5), Some(&new)); | |
3480 | } | |
3481 | ||
3482 | #[test] | |
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); | |
3489 | } | |
3490 | ||
3491 | #[test] | |
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); | |
3500 | } | |
3501 | ||
3502 | #[test] | |
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); | |
3517 | } | |
3518 | ||
3519 | #[test] | |
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()); | |
3526 | } | |
3527 | ||
3528 | #[test] | |
3529 | fn test_remove() { | |
3530 | let mut m = HashMap::new(); | |
3531 | m.insert(1, 2); | |
3532 | assert_eq!(m.remove(&1), Some(2)); | |
3533 | assert_eq!(m.remove(&1), None); | |
3534 | } | |
3535 | ||
3536 | #[test] | |
3537 | fn test_remove_entry() { | |
3538 | let mut m = HashMap::new(); | |
3539 | m.insert(1, 2); | |
3540 | assert_eq!(m.remove_entry(&1), Some((1, 2))); | |
3541 | assert_eq!(m.remove(&1), None); | |
3542 | } | |
3543 | ||
3544 | #[test] | |
3545 | fn test_iterate() { | |
3546 | let mut m = HashMap::with_capacity(4); | |
3547 | for i in 0..32 { | |
3548 | assert!(m.insert(i, i * 2).is_none()); | |
3549 | } | |
3550 | assert_eq!(m.len(), 32); | |
3551 | ||
3552 | let mut observed: u32 = 0; | |
3553 | ||
3554 | for (k, v) in &m { | |
3555 | assert_eq!(*v, *k * 2); | |
3556 | observed |= 1 << *k; | |
3557 | } | |
3558 | assert_eq!(observed, 0xFFFF_FFFF); | |
3559 | } | |
3560 | ||
3561 | #[test] | |
3562 | fn test_keys() { | |
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)); | |
3570 | } | |
3571 | ||
3572 | #[test] | |
3573 | fn test_values() { | |
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')); | |
3581 | } | |
3582 | ||
3583 | #[test] | |
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 | |
3589 | } | |
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)); | |
3595 | } | |
3596 | ||
3597 | #[test] | |
3598 | fn test_find() { | |
3599 | let mut m = HashMap::new(); | |
3600 | assert!(m.get(&1).is_none()); | |
3601 | m.insert(1, 2); | |
3602 | match m.get(&1) { | |
3603 | None => panic!(), | |
3604 | Some(v) => assert_eq!(*v, 2), | |
3605 | } | |
3606 | } | |
3607 | ||
3608 | #[test] | |
3609 | fn test_eq() { | |
3610 | let mut m1 = HashMap::new(); | |
3611 | m1.insert(1, 2); | |
3612 | m1.insert(2, 3); | |
3613 | m1.insert(3, 4); | |
3614 | ||
3615 | let mut m2 = HashMap::new(); | |
3616 | m2.insert(1, 2); | |
3617 | m2.insert(2, 3); | |
3618 | ||
3619 | assert!(m1 != m2); | |
3620 | ||
3621 | m2.insert(3, 4); | |
3622 | ||
3623 | assert_eq!(m1, m2); | |
3624 | } | |
3625 | ||
3626 | #[test] | |
3627 | fn test_show() { | |
3628 | let mut map = HashMap::new(); | |
3629 | let empty: HashMap<i32, i32> = HashMap::new(); | |
3630 | ||
3631 | map.insert(1, 2); | |
3632 | map.insert(3, 4); | |
3633 | ||
3634 | let map_str = format!("{:?}", map); | |
3635 | ||
3636 | assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}"); | |
3637 | assert_eq!(format!("{:?}", empty), "{}"); | |
3638 | } | |
3639 | ||
3640 | #[test] | |
3641 | fn test_expand() { | |
3642 | let mut m = HashMap::new(); | |
3643 | ||
3644 | assert_eq!(m.len(), 0); | |
3645 | assert!(m.is_empty()); | |
3646 | ||
3647 | let mut i = 0; | |
3648 | let old_raw_cap = m.raw_capacity(); | |
3649 | while old_raw_cap == m.raw_capacity() { | |
3650 | m.insert(i, i); | |
3651 | i += 1; | |
3652 | } | |
3653 | ||
3654 | assert_eq!(m.len(), i); | |
3655 | assert!(!m.is_empty()); | |
3656 | } | |
3657 | ||
3658 | #[test] | |
3659 | fn test_behavior_resize_policy() { | |
3660 | let mut m = HashMap::new(); | |
3661 | ||
3662 | assert_eq!(m.len(), 0); | |
3663 | assert_eq!(m.raw_capacity(), 1); | |
3664 | assert!(m.is_empty()); | |
3665 | ||
3666 | m.insert(0, 0); | |
3667 | m.remove(&0); | |
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(); | |
3672 | ||
3673 | assert_eq!(raw_cap, initial_raw_cap * 2); | |
3674 | ||
3675 | let mut i = 0; | |
3676 | for _ in 0..raw_cap * 3 / 4 { | |
3677 | m.insert(i, i); | |
3678 | i += 1; | |
3679 | } | |
3680 | // three quarters full | |
3681 | ||
3682 | assert_eq!(m.len(), i); | |
3683 | assert_eq!(m.raw_capacity(), raw_cap); | |
3684 | ||
3685 | for _ in 0..raw_cap / 4 { | |
3686 | m.insert(i, i); | |
3687 | i += 1; | |
3688 | } | |
3689 | // half full | |
3690 | ||
3691 | let new_raw_cap = m.raw_capacity(); | |
3692 | assert_eq!(new_raw_cap, raw_cap * 2); | |
3693 | ||
3694 | for _ in 0..raw_cap / 2 - 1 { | |
3695 | i -= 1; | |
3696 | m.remove(&i); | |
3697 | assert_eq!(m.raw_capacity(), new_raw_cap); | |
3698 | } | |
3699 | // A little more than one quarter full. | |
3700 | m.shrink_to_fit(); | |
3701 | assert_eq!(m.raw_capacity(), raw_cap); | |
3702 | // again, a little more than half full | |
3703 | for _ in 0..raw_cap / 2 { | |
3704 | i -= 1; | |
3705 | m.remove(&i); | |
3706 | } | |
3707 | m.shrink_to_fit(); | |
3708 | ||
3709 | assert_eq!(m.len(), i); | |
3710 | assert!(!m.is_empty()); | |
3711 | assert_eq!(m.raw_capacity(), initial_raw_cap); | |
3712 | } | |
3713 | ||
3714 | #[test] | |
3715 | fn test_reserve_shrink_to_fit() { | |
3716 | let mut m = HashMap::new(); | |
3717 | m.insert(0, 0); | |
3718 | m.remove(&0); | |
3719 | assert!(m.capacity() >= m.len()); | |
3720 | for i in 0..128 { | |
3721 | m.insert(i, i); | |
3722 | } | |
3723 | m.reserve(256); | |
3724 | ||
3725 | let usable_cap = m.capacity(); | |
3726 | for i in 128..(128 + 256) { | |
3727 | m.insert(i, i); | |
3728 | assert_eq!(m.capacity(), usable_cap); | |
3729 | } | |
3730 | ||
3731 | for i in 100..(128 + 256) { | |
3732 | assert_eq!(m.remove(&i), Some(i)); | |
3733 | } | |
3734 | m.shrink_to_fit(); | |
3735 | ||
3736 | assert_eq!(m.len(), 100); | |
3737 | assert!(!m.is_empty()); | |
3738 | assert!(m.capacity() >= m.len()); | |
3739 | ||
3740 | for i in 0..100 { | |
3741 | assert_eq!(m.remove(&i), Some(i)); | |
3742 | } | |
3743 | m.shrink_to_fit(); | |
3744 | m.insert(0, 0); | |
3745 | ||
3746 | assert_eq!(m.len(), 1); | |
3747 | assert!(m.capacity() >= m.len()); | |
3748 | assert_eq!(m.remove(&0), Some(0)); | |
3749 | } | |
3750 | ||
3751 | #[test] | |
3752 | fn test_from_iter() { | |
3753 | let xs = [(1, 1), (2, 2), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
3754 | ||
3755 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
3756 | ||
3757 | for &(k, v) in &xs { | |
3758 | assert_eq!(map.get(&k), Some(&v)); | |
3759 | } | |
3760 | ||
3761 | assert_eq!(map.iter().len(), xs.len() - 1); | |
3762 | } | |
3763 | ||
3764 | #[test] | |
3765 | fn test_size_hint() { | |
3766 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
3767 | ||
3768 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
3769 | ||
3770 | let mut iter = map.iter(); | |
3771 | ||
3772 | for _ in iter.by_ref().take(3) {} | |
3773 | ||
3774 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
3775 | } | |
3776 | ||
3777 | #[test] | |
3778 | fn test_iter_len() { | |
3779 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
3780 | ||
3781 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
3782 | ||
3783 | let mut iter = map.iter(); | |
3784 | ||
3785 | for _ in iter.by_ref().take(3) {} | |
3786 | ||
3787 | assert_eq!(iter.len(), 3); | |
3788 | } | |
3789 | ||
3790 | #[test] | |
3791 | fn test_mut_size_hint() { | |
3792 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
3793 | ||
3794 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
3795 | ||
3796 | let mut iter = map.iter_mut(); | |
3797 | ||
3798 | for _ in iter.by_ref().take(3) {} | |
3799 | ||
3800 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
3801 | } | |
3802 | ||
3803 | #[test] | |
3804 | fn test_iter_mut_len() { | |
3805 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
3806 | ||
3807 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
3808 | ||
3809 | let mut iter = map.iter_mut(); | |
3810 | ||
3811 | for _ in iter.by_ref().take(3) {} | |
3812 | ||
3813 | assert_eq!(iter.len(), 3); | |
3814 | } | |
3815 | ||
3816 | #[test] | |
3817 | fn test_index() { | |
3818 | let mut map = HashMap::new(); | |
3819 | ||
3820 | map.insert(1, 2); | |
3821 | map.insert(2, 1); | |
3822 | map.insert(3, 4); | |
3823 | ||
3824 | assert_eq!(map[&2], 1); | |
3825 | } | |
3826 | ||
3827 | #[test] | |
3828 | #[should_panic] | |
3829 | fn test_index_nonexistent() { | |
3830 | let mut map = HashMap::new(); | |
3831 | ||
3832 | map.insert(1, 2); | |
3833 | map.insert(2, 1); | |
3834 | map.insert(3, 4); | |
3835 | ||
3836 | map[&4]; | |
3837 | } | |
3838 | ||
3839 | #[test] | |
3840 | fn test_entry() { | |
3841 | let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; | |
3842 | ||
3843 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
3844 | ||
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); | |
3851 | } | |
3852 | } | |
3853 | assert_eq!(map.get(&1).unwrap(), &100); | |
3854 | assert_eq!(map.len(), 6); | |
3855 | ||
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; | |
3862 | *v = new_v; | |
3863 | } | |
3864 | } | |
3865 | assert_eq!(map.get(&2).unwrap(), &200); | |
3866 | assert_eq!(map.len(), 6); | |
3867 | ||
3868 | // Existing key (take) | |
3869 | match map.entry(3) { | |
3870 | Vacant(_) => unreachable!(), | |
3871 | Occupied(view) => { | |
3872 | assert_eq!(view.remove(), 30); | |
3873 | } | |
3874 | } | |
3875 | assert_eq!(map.get(&3), None); | |
3876 | assert_eq!(map.len(), 5); | |
3877 | ||
3878 | // Inexistent key (insert) | |
3879 | match map.entry(10) { | |
3880 | Occupied(_) => unreachable!(), | |
3881 | Vacant(view) => { | |
3882 | assert_eq!(*view.insert(1000), 1000); | |
3883 | } | |
3884 | } | |
3885 | assert_eq!(map.get(&10).unwrap(), &1000); | |
3886 | assert_eq!(map.len(), 6); | |
3887 | } | |
3888 | ||
3889 | #[test] | |
3890 | fn test_entry_take_doesnt_corrupt() { | |
3891 | #![allow(deprecated)] //rand | |
3892 | // Test for #19292 | |
3893 | fn check(m: &HashMap<i32, ()>) { | |
3894 | for k in m.keys() { | |
3895 | assert!(m.contains_key(k), "{} is in keys() but not in the map?", k); | |
3896 | } | |
3897 | } | |
3898 | ||
3899 | let mut m = HashMap::new(); | |
3900 | ||
3901 | let mut rng = { | |
3902 | let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; | |
3903 | SmallRng::from_seed(seed) | |
3904 | }; | |
3905 | ||
3906 | // Populate the map with some items. | |
3907 | for _ in 0..50 { | |
3908 | let x = rng.gen_range(-10, 10); | |
3909 | m.insert(x, ()); | |
3910 | } | |
3911 | ||
3912 | for _ in 0..1000 { | |
3913 | let x = rng.gen_range(-10, 10); | |
3914 | match m.entry(x) { | |
3915 | Vacant(_) => {} | |
3916 | Occupied(e) => { | |
3917 | e.remove(); | |
3918 | } | |
3919 | } | |
3920 | ||
3921 | check(&m); | |
3922 | } | |
3923 | } | |
3924 | ||
3925 | #[test] | |
3926 | fn test_extend_ref() { | |
3927 | let mut a = HashMap::new(); | |
3928 | a.insert(1, "one"); | |
3929 | let mut b = HashMap::new(); | |
3930 | b.insert(2, "two"); | |
3931 | b.insert(3, "three"); | |
3932 | ||
3933 | a.extend(&b); | |
3934 | ||
3935 | assert_eq!(a.len(), 3); | |
3936 | assert_eq!(a[&1], "one"); | |
3937 | assert_eq!(a[&2], "two"); | |
3938 | assert_eq!(a[&3], "three"); | |
3939 | } | |
3940 | ||
3941 | #[test] | |
3942 | fn test_capacity_not_less_than_len() { | |
3943 | let mut a = HashMap::new(); | |
3944 | let mut item = 0; | |
3945 | ||
3946 | for _ in 0..116 { | |
3947 | a.insert(item, 0); | |
3948 | item += 1; | |
3949 | } | |
3950 | ||
3951 | assert!(a.capacity() > a.len()); | |
3952 | ||
3953 | let free = a.capacity() - a.len(); | |
3954 | for _ in 0..free { | |
3955 | a.insert(item, 0); | |
3956 | item += 1; | |
3957 | } | |
3958 | ||
3959 | assert_eq!(a.len(), a.capacity()); | |
3960 | ||
3961 | // Insert at capacity should cause allocation. | |
3962 | a.insert(item, 0); | |
3963 | assert!(a.capacity() > a.len()); | |
3964 | } | |
3965 | ||
3966 | #[test] | |
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); | |
3975 | ||
3976 | match a.entry(key.clone()) { | |
3977 | Vacant(_) => panic!(), | |
3978 | Occupied(e) => assert_eq!(key, *e.key()), | |
3979 | } | |
3980 | assert_eq!(a.len(), 1); | |
3981 | assert_eq!(a[key], value); | |
3982 | } | |
3983 | ||
3984 | #[test] | |
3985 | fn test_vacant_entry_key() { | |
3986 | let mut a = HashMap::new(); | |
3987 | let key = "hello there"; | |
3988 | let value = "value goes here"; | |
3989 | ||
3990 | assert!(a.is_empty()); | |
3991 | match a.entry(key.clone()) { | |
3992 | Occupied(_) => panic!(), | |
3993 | Vacant(e) => { | |
3994 | assert_eq!(key, *e.key()); | |
3995 | e.insert(value.clone()); | |
3996 | } | |
3997 | } | |
3998 | assert_eq!(a.len(), 1); | |
3999 | assert_eq!(a[key], value); | |
4000 | } | |
4001 | ||
4002 | #[test] | |
4003 | fn test_occupied_entry_replace_entry_with() { | |
4004 | let mut a = HashMap::new(); | |
4005 | ||
4006 | let key = "a key"; | |
4007 | let value = "an initial value"; | |
4008 | let new_value = "a new value"; | |
4009 | ||
4010 | let entry = a.entry(key).insert(value).replace_entry_with(|k, v| { | |
4011 | assert_eq!(k, &key); | |
4012 | assert_eq!(v, value); | |
4013 | Some(new_value) | |
4014 | }); | |
4015 | ||
4016 | match entry { | |
4017 | Occupied(e) => { | |
4018 | assert_eq!(e.key(), &key); | |
4019 | assert_eq!(e.get(), &new_value); | |
4020 | } | |
4021 | Vacant(_) => panic!(), | |
4022 | } | |
4023 | ||
4024 | assert_eq!(a[key], new_value); | |
4025 | assert_eq!(a.len(), 1); | |
4026 | ||
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); | |
4031 | None | |
4032 | }), | |
4033 | Vacant(_) => panic!(), | |
4034 | }; | |
4035 | ||
4036 | match entry { | |
4037 | Vacant(e) => assert_eq!(e.key(), &key), | |
4038 | Occupied(_) => panic!(), | |
4039 | } | |
4040 | ||
4041 | assert!(!a.contains_key(key)); | |
4042 | assert_eq!(a.len(), 0); | |
4043 | } | |
4044 | ||
4045 | #[test] | |
4046 | fn test_entry_and_replace_entry_with() { | |
4047 | let mut a = HashMap::new(); | |
4048 | ||
4049 | let key = "a key"; | |
4050 | let value = "an initial value"; | |
4051 | let new_value = "a new value"; | |
4052 | ||
4053 | let entry = a.entry(key).and_replace_entry_with(|_, _| panic!()); | |
4054 | ||
4055 | match entry { | |
4056 | Vacant(e) => assert_eq!(e.key(), &key), | |
4057 | Occupied(_) => panic!(), | |
4058 | } | |
4059 | ||
4060 | a.insert(key, value); | |
4061 | ||
4062 | let entry = a.entry(key).and_replace_entry_with(|k, v| { | |
4063 | assert_eq!(k, &key); | |
4064 | assert_eq!(v, value); | |
4065 | Some(new_value) | |
4066 | }); | |
4067 | ||
4068 | match entry { | |
4069 | Occupied(e) => { | |
4070 | assert_eq!(e.key(), &key); | |
4071 | assert_eq!(e.get(), &new_value); | |
4072 | } | |
4073 | Vacant(_) => panic!(), | |
4074 | } | |
4075 | ||
4076 | assert_eq!(a[key], new_value); | |
4077 | assert_eq!(a.len(), 1); | |
4078 | ||
4079 | let entry = a.entry(key).and_replace_entry_with(|k, v| { | |
4080 | assert_eq!(k, &key); | |
4081 | assert_eq!(v, new_value); | |
4082 | None | |
4083 | }); | |
4084 | ||
4085 | match entry { | |
4086 | Vacant(e) => assert_eq!(e.key(), &key), | |
4087 | Occupied(_) => panic!(), | |
4088 | } | |
4089 | ||
4090 | assert!(!a.contains_key(key)); | |
4091 | assert_eq!(a.len(), 0); | |
4092 | } | |
4093 | ||
4094 | #[test] | |
4095 | fn test_raw_occupied_entry_replace_entry_with() { | |
4096 | let mut a = HashMap::new(); | |
4097 | ||
4098 | let key = "a key"; | |
4099 | let value = "an initial value"; | |
4100 | let new_value = "a new value"; | |
4101 | ||
4102 | let entry = a | |
4103 | .raw_entry_mut() | |
4104 | .from_key(&key) | |
4105 | .insert(key, value) | |
4106 | .replace_entry_with(|k, v| { | |
4107 | assert_eq!(k, &key); | |
4108 | assert_eq!(v, value); | |
4109 | Some(new_value) | |
4110 | }); | |
4111 | ||
4112 | match entry { | |
4113 | RawEntryMut::Occupied(e) => { | |
4114 | assert_eq!(e.key(), &key); | |
4115 | assert_eq!(e.get(), &new_value); | |
4116 | } | |
4117 | RawEntryMut::Vacant(_) => panic!(), | |
4118 | } | |
4119 | ||
4120 | assert_eq!(a[key], new_value); | |
4121 | assert_eq!(a.len(), 1); | |
4122 | ||
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); | |
4127 | None | |
4128 | }), | |
4129 | RawEntryMut::Vacant(_) => panic!(), | |
4130 | }; | |
4131 | ||
4132 | match entry { | |
4133 | RawEntryMut::Vacant(_) => {} | |
4134 | RawEntryMut::Occupied(_) => panic!(), | |
4135 | } | |
4136 | ||
4137 | assert!(!a.contains_key(key)); | |
4138 | assert_eq!(a.len(), 0); | |
4139 | } | |
4140 | ||
4141 | #[test] | |
4142 | fn test_raw_entry_and_replace_entry_with() { | |
4143 | let mut a = HashMap::new(); | |
4144 | ||
4145 | let key = "a key"; | |
4146 | let value = "an initial value"; | |
4147 | let new_value = "a new value"; | |
4148 | ||
4149 | let entry = a | |
4150 | .raw_entry_mut() | |
4151 | .from_key(&key) | |
4152 | .and_replace_entry_with(|_, _| panic!()); | |
4153 | ||
4154 | match entry { | |
4155 | RawEntryMut::Vacant(_) => {} | |
4156 | RawEntryMut::Occupied(_) => panic!(), | |
4157 | } | |
4158 | ||
4159 | a.insert(key, value); | |
4160 | ||
4161 | let entry = a | |
4162 | .raw_entry_mut() | |
4163 | .from_key(&key) | |
4164 | .and_replace_entry_with(|k, v| { | |
4165 | assert_eq!(k, &key); | |
4166 | assert_eq!(v, value); | |
4167 | Some(new_value) | |
4168 | }); | |
4169 | ||
4170 | match entry { | |
4171 | RawEntryMut::Occupied(e) => { | |
4172 | assert_eq!(e.key(), &key); | |
4173 | assert_eq!(e.get(), &new_value); | |
4174 | } | |
4175 | RawEntryMut::Vacant(_) => panic!(), | |
4176 | } | |
4177 | ||
4178 | assert_eq!(a[key], new_value); | |
4179 | assert_eq!(a.len(), 1); | |
4180 | ||
4181 | let entry = a | |
4182 | .raw_entry_mut() | |
4183 | .from_key(&key) | |
4184 | .and_replace_entry_with(|k, v| { | |
4185 | assert_eq!(k, &key); | |
4186 | assert_eq!(v, new_value); | |
4187 | None | |
4188 | }); | |
4189 | ||
4190 | match entry { | |
4191 | RawEntryMut::Vacant(_) => {} | |
4192 | RawEntryMut::Occupied(_) => panic!(), | |
4193 | } | |
4194 | ||
4195 | assert!(!a.contains_key(key)); | |
4196 | assert_eq!(a.len(), 0); | |
4197 | } | |
4198 | ||
4199 | #[test] | |
4200 | fn test_replace_entry_with_doesnt_corrupt() { | |
4201 | #![allow(deprecated)] //rand | |
4202 | // Test for #19292 | |
4203 | fn check(m: &HashMap<i32, ()>) { | |
4204 | for k in m.keys() { | |
4205 | assert!(m.contains_key(k), "{} is in keys() but not in the map?", k); | |
4206 | } | |
4207 | } | |
4208 | ||
4209 | let mut m = HashMap::new(); | |
4210 | ||
4211 | let mut rng = { | |
4212 | let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; | |
4213 | SmallRng::from_seed(seed) | |
4214 | }; | |
4215 | ||
4216 | // Populate the map with some items. | |
4217 | for _ in 0..50 { | |
4218 | let x = rng.gen_range(-10, 10); | |
4219 | m.insert(x, ()); | |
4220 | } | |
4221 | ||
4222 | for _ in 0..1000 { | |
4223 | let x = rng.gen_range(-10, 10); | |
4224 | m.entry(x).and_replace_entry_with(|_, _| None); | |
4225 | check(&m); | |
4226 | } | |
4227 | } | |
4228 | ||
4229 | #[test] | |
4230 | fn test_retain() { | |
4231 | let mut map: HashMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect(); | |
4232 | ||
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); | |
4238 | } | |
4239 | ||
4240 | #[test] | |
4241 | fn test_drain_filter() { | |
4242 | { | |
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); | |
4249 | } | |
4250 | { | |
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); | |
4254 | } | |
4255 | } | |
4256 | ||
4257 | #[test] | |
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(); | |
4261 | ||
4262 | const MAX_USIZE: usize = usize::MAX; | |
4263 | ||
4264 | if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) { | |
4265 | } else { | |
4266 | panic!("usize::MAX should trigger an overflow!"); | |
4267 | } | |
4268 | ||
4269 | if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 8) { | |
4270 | } else { | |
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) { | |
4275 | } else { | |
4276 | panic!("usize::MAX / 8 should trigger an OOM!"); | |
4277 | } | |
4278 | } | |
4279 | } | |
4280 | ||
4281 | #[test] | |
4282 | fn test_raw_entry() { | |
4283 | use super::RawEntryMut::{Occupied, Vacant}; | |
4284 | ||
4285 | let xs = [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; | |
4286 | ||
4287 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4288 | ||
4289 | let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 { | |
4290 | use core::hash::{BuildHasher, Hash, Hasher}; | |
4291 | ||
4292 | let mut hasher = map.hasher().build_hasher(); | |
4293 | k.hash(&mut hasher); | |
4294 | hasher.finish() | |
4295 | }; | |
4296 | ||
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); | |
4303 | } | |
4304 | } | |
4305 | let hash1 = compute_hash(&map, 1); | |
4306 | assert_eq!(map.raw_entry().from_key(&1).unwrap(), (&1, &100)); | |
4307 | assert_eq!( | |
4308 | map.raw_entry().from_hash(hash1, |k| *k == 1).unwrap(), | |
4309 | (&1, &100) | |
4310 | ); | |
4311 | assert_eq!( | |
4312 | map.raw_entry().from_key_hashed_nocheck(hash1, &1).unwrap(), | |
4313 | (&1, &100) | |
4314 | ); | |
4315 | assert_eq!(map.len(), 6); | |
4316 | ||
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; | |
4323 | *v = new_v; | |
4324 | } | |
4325 | } | |
4326 | let hash2 = compute_hash(&map, 2); | |
4327 | assert_eq!(map.raw_entry().from_key(&2).unwrap(), (&2, &200)); | |
4328 | assert_eq!( | |
4329 | map.raw_entry().from_hash(hash2, |k| *k == 2).unwrap(), | |
4330 | (&2, &200) | |
4331 | ); | |
4332 | assert_eq!( | |
4333 | map.raw_entry().from_key_hashed_nocheck(hash2, &2).unwrap(), | |
4334 | (&2, &200) | |
4335 | ); | |
4336 | assert_eq!(map.len(), 6); | |
4337 | ||
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!(), | |
4342 | Occupied(view) => { | |
4343 | assert_eq!(view.remove_entry(), (3, 30)); | |
4344 | } | |
4345 | } | |
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); | |
4350 | ||
4351 | // Nonexistent key (insert) | |
4352 | match map.raw_entry_mut().from_key(&10) { | |
4353 | Occupied(_) => unreachable!(), | |
4354 | Vacant(view) => { | |
4355 | assert_eq!(view.insert(10, 1000), (&mut 10, &mut 1000)); | |
4356 | } | |
4357 | } | |
4358 | assert_eq!(map.raw_entry().from_key(&10).unwrap(), (&10, &1000)); | |
4359 | assert_eq!(map.len(), 6); | |
4360 | ||
4361 | // Ensure all lookup methods produce equivalent results. | |
4362 | for k in 0..12 { | |
4363 | let hash = compute_hash(&map, k); | |
4364 | let v = map.get(&k).cloned(); | |
4365 | let kv = v.as_ref().map(|v| (&k, v)); | |
4366 | ||
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); | |
4370 | ||
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), | |
4374 | } | |
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), | |
4378 | } | |
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), | |
4382 | } | |
4383 | } | |
4384 | } | |
4385 | ||
4386 | #[test] | |
4387 | fn test_key_without_hash_impl() { | |
4388 | #[derive(Debug)] | |
4389 | struct IntWrapper(u64); | |
4390 | ||
4391 | let mut m: HashMap<IntWrapper, (), ()> = HashMap::default(); | |
4392 | { | |
4393 | assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none()); | |
4394 | } | |
4395 | { | |
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, | |
4399 | }; | |
4400 | vacant_entry.insert_with_hasher(0, IntWrapper(0), (), |k| k.0); | |
4401 | } | |
4402 | { | |
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()); | |
4406 | } | |
4407 | { | |
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, | |
4411 | }; | |
4412 | vacant_entry.insert_with_hasher(1, IntWrapper(1), (), |k| k.0); | |
4413 | } | |
4414 | { | |
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()); | |
4418 | } | |
4419 | { | |
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"), | |
4423 | }; | |
4424 | occupied_entry.remove(); | |
4425 | } | |
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()); | |
4429 | } | |
4430 | ||
4431 | #[test] | |
4432 | #[cfg(feature = "raw")] | |
4433 | fn test_into_iter_refresh() { | |
4434 | use core::hash::{BuildHasher, Hash, Hasher}; | |
4435 | ||
4436 | #[cfg(miri)] | |
4437 | const N: usize = 32; | |
4438 | #[cfg(not(miri))] | |
4439 | const N: usize = 128; | |
4440 | ||
4441 | let mut rng = rand::thread_rng(); | |
4442 | for n in 0..N { | |
4443 | let mut m = HashMap::new(); | |
4444 | for i in 0..n { | |
4445 | assert!(m.insert(i, 2 * i).is_none()); | |
4446 | } | |
4447 | let hasher = m.hasher().clone(); | |
4448 | ||
4449 | let mut it = unsafe { m.table.iter() }; | |
4450 | assert_eq!(it.len(), n); | |
4451 | ||
4452 | let mut i = 0; | |
4453 | let mut left = n; | |
4454 | let mut removed = Vec::new(); | |
4455 | loop { | |
4456 | // occasionally remove some elements | |
4457 | if i < n && rng.gen_bool(0.1) { | |
4458 | let mut hsh = hasher.build_hasher(); | |
4459 | i.hash(&mut hsh); | |
4460 | let hash = hsh.finish(); | |
4461 | ||
4462 | unsafe { | |
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); | |
4467 | removed.push(t); | |
4468 | left -= 1; | |
4469 | } else { | |
4470 | assert!(removed.contains(&(i, 2 * i)), "{} not in {:?}", i, removed); | |
4471 | let e = m | |
4472 | .table | |
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); | |
4477 | } | |
4478 | left += 1; | |
4479 | } | |
4480 | } | |
4481 | } | |
4482 | ||
4483 | let e = it.next(); | |
4484 | if e.is_none() { | |
4485 | break; | |
4486 | } | |
4487 | assert!(i < n); | |
4488 | let t = unsafe { e.unwrap().as_ref() }; | |
4489 | assert!(!removed.contains(t)); | |
4490 | let (k, v) = t; | |
4491 | assert_eq!(*v, 2 * k); | |
4492 | i += 1; | |
4493 | } | |
4494 | assert!(i <= n); | |
4495 | ||
4496 | // just for safety: | |
4497 | assert_eq!(m.table.len(), left); | |
4498 | } | |
4499 | } | |
4500 | ||
4501 | #[test] | |
4502 | fn test_const_with_hasher() { | |
4503 | use core::hash::BuildHasher; | |
4504 | use std::borrow::ToOwned; | |
4505 | use std::collections::hash_map::DefaultHasher; | |
4506 | ||
4507 | #[derive(Clone)] | |
4508 | struct MyHasher; | |
4509 | impl BuildHasher for MyHasher { | |
4510 | type Hasher = DefaultHasher; | |
4511 | ||
4512 | fn build_hasher(&self) -> DefaultHasher { | |
4513 | DefaultHasher::new() | |
4514 | } | |
4515 | } | |
4516 | ||
4517 | const EMPTY_MAP: HashMap<u32, std::string::String, MyHasher> = | |
4518 | HashMap::with_hasher(MyHasher); | |
4519 | ||
4520 | let mut map = EMPTY_MAP.clone(); | |
4521 | map.insert(17, "seventeen".to_owned()); | |
4522 | assert_eq!("seventeen", map[&17]); | |
4523 | } | |
4524 | } |