]>
Commit | Line | Data |
---|---|---|
6a06907d | 1 | use crate::raw::{Allocator, Bucket, Global, RawDrain, RawIntoIter, RawIter, RawTable}; |
3dfed10e | 2 | use crate::TryReserveError; |
6a06907d XL |
3 | #[cfg(feature = "nightly")] |
4 | use crate::UnavailableMutError; | |
48663c56 XL |
5 | use core::borrow::Borrow; |
6 | use core::fmt::{self, Debug}; | |
6a06907d | 7 | use core::hash::{BuildHasher, Hash}; |
48663c56 XL |
8 | use core::iter::{FromIterator, FusedIterator}; |
9 | use core::marker::PhantomData; | |
10 | use core::mem; | |
6a06907d XL |
11 | #[cfg(feature = "nightly")] |
12 | use core::mem::MaybeUninit; | |
48663c56 XL |
13 | use core::ops::Index; |
14 | ||
e74abb32 XL |
15 | /// Default hasher for `HashMap`. |
16 | #[cfg(feature = "ahash")] | |
3dfed10e | 17 | pub type DefaultHashBuilder = ahash::RandomState; |
e74abb32 XL |
18 | |
19 | /// Dummy default hasher for `HashMap`. | |
20 | #[cfg(not(feature = "ahash"))] | |
21 | pub enum DefaultHashBuilder {} | |
48663c56 XL |
22 | |
23 | /// A hash map implemented with quadratic probing and SIMD lookup. | |
24 | /// | |
e74abb32 | 25 | /// The default hashing algorithm is currently [`AHash`], though this is |
48663c56 XL |
26 | /// subject to change at any point in the future. This hash function is very |
27 | /// fast for all types of keys, but this algorithm will typically *not* protect | |
28 | /// against attacks such as HashDoS. | |
29 | /// | |
30 | /// The hashing algorithm can be replaced on a per-`HashMap` basis using the | |
31 | /// [`default`], [`with_hasher`], and [`with_capacity_and_hasher`] methods. Many | |
32 | /// alternative algorithms are available on crates.io, such as the [`fnv`] crate. | |
33 | /// | |
34 | /// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although | |
35 | /// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`. | |
36 | /// If you implement these yourself, it is important that the following | |
37 | /// property holds: | |
38 | /// | |
39 | /// ```text | |
40 | /// k1 == k2 -> hash(k1) == hash(k2) | |
41 | /// ``` | |
42 | /// | |
43 | /// In other words, if two keys are equal, their hashes must be equal. | |
44 | /// | |
45 | /// It is a logic error for a key to be modified in such a way that the key's | |
46 | /// hash, as determined by the [`Hash`] trait, or its equality, as determined by | |
47 | /// the [`Eq`] trait, changes while it is in the map. This is normally only | |
48 | /// possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. | |
49 | /// | |
50 | /// It is also a logic error for the [`Hash`] implementation of a key to panic. | |
51 | /// This is generally only possible if the trait is implemented manually. If a | |
52 | /// panic does occur then the contents of the `HashMap` may become corrupted and | |
53 | /// some items may be dropped from the table. | |
54 | /// | |
55 | /// # Examples | |
56 | /// | |
57 | /// ``` | |
58 | /// use hashbrown::HashMap; | |
59 | /// | |
60 | /// // Type inference lets us omit an explicit type signature (which | |
61 | /// // would be `HashMap<String, String>` in this example). | |
62 | /// let mut book_reviews = HashMap::new(); | |
63 | /// | |
64 | /// // Review some books. | |
65 | /// book_reviews.insert( | |
66 | /// "Adventures of Huckleberry Finn".to_string(), | |
67 | /// "My favorite book.".to_string(), | |
68 | /// ); | |
69 | /// book_reviews.insert( | |
70 | /// "Grimms' Fairy Tales".to_string(), | |
71 | /// "Masterpiece.".to_string(), | |
72 | /// ); | |
73 | /// book_reviews.insert( | |
74 | /// "Pride and Prejudice".to_string(), | |
75 | /// "Very enjoyable.".to_string(), | |
76 | /// ); | |
77 | /// book_reviews.insert( | |
78 | /// "The Adventures of Sherlock Holmes".to_string(), | |
79 | /// "Eye lyked it alot.".to_string(), | |
80 | /// ); | |
81 | /// | |
82 | /// // Check for a specific one. | |
83 | /// // When collections store owned values (String), they can still be | |
84 | /// // queried using references (&str). | |
85 | /// if !book_reviews.contains_key("Les Misérables") { | |
86 | /// println!("We've got {} reviews, but Les Misérables ain't one.", | |
87 | /// book_reviews.len()); | |
88 | /// } | |
89 | /// | |
90 | /// // oops, this review has a lot of spelling mistakes, let's delete it. | |
91 | /// book_reviews.remove("The Adventures of Sherlock Holmes"); | |
92 | /// | |
93 | /// // Look up the values associated with some keys. | |
94 | /// let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; | |
95 | /// for &book in &to_find { | |
96 | /// match book_reviews.get(book) { | |
97 | /// Some(review) => println!("{}: {}", book, review), | |
98 | /// None => println!("{} is unreviewed.", book) | |
99 | /// } | |
100 | /// } | |
101 | /// | |
102 | /// // Look up the value for a key (will panic if the key is not found). | |
103 | /// println!("Review for Jane: {}", book_reviews["Pride and Prejudice"]); | |
104 | /// | |
105 | /// // Iterate over everything. | |
106 | /// for (book, review) in &book_reviews { | |
107 | /// println!("{}: \"{}\"", book, review); | |
108 | /// } | |
109 | /// ``` | |
110 | /// | |
111 | /// `HashMap` also implements an [`Entry API`](#method.entry), which allows | |
112 | /// for more complex methods of getting, setting, updating and removing keys and | |
113 | /// their values: | |
114 | /// | |
115 | /// ``` | |
116 | /// use hashbrown::HashMap; | |
117 | /// | |
118 | /// // type inference lets us omit an explicit type signature (which | |
119 | /// // would be `HashMap<&str, u8>` in this example). | |
120 | /// let mut player_stats = HashMap::new(); | |
121 | /// | |
122 | /// fn random_stat_buff() -> u8 { | |
123 | /// // could actually return some random value here - let's just return | |
124 | /// // some fixed value for now | |
125 | /// 42 | |
126 | /// } | |
127 | /// | |
128 | /// // insert a key only if it doesn't already exist | |
129 | /// player_stats.entry("health").or_insert(100); | |
130 | /// | |
131 | /// // insert a key using a function that provides a new value only if it | |
132 | /// // doesn't already exist | |
133 | /// player_stats.entry("defence").or_insert_with(random_stat_buff); | |
134 | /// | |
135 | /// // update a key, guarding against the key possibly not being set | |
136 | /// let stat = player_stats.entry("attack").or_insert(100); | |
137 | /// *stat += random_stat_buff(); | |
138 | /// ``` | |
139 | /// | |
140 | /// The easiest way to use `HashMap` with a custom key type is to derive [`Eq`] and [`Hash`]. | |
141 | /// We must also derive [`PartialEq`]. | |
142 | /// | |
143 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
144 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
145 | /// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html | |
146 | /// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html | |
147 | /// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html | |
148 | /// [`default`]: #method.default | |
149 | /// [`with_hasher`]: #method.with_hasher | |
150 | /// [`with_capacity_and_hasher`]: #method.with_capacity_and_hasher | |
151 | /// [`fnv`]: https://crates.io/crates/fnv | |
e74abb32 | 152 | /// [`AHash`]: https://crates.io/crates/ahash |
48663c56 XL |
153 | /// |
154 | /// ``` | |
155 | /// use hashbrown::HashMap; | |
156 | /// | |
157 | /// #[derive(Hash, Eq, PartialEq, Debug)] | |
158 | /// struct Viking { | |
159 | /// name: String, | |
160 | /// country: String, | |
161 | /// } | |
162 | /// | |
163 | /// impl Viking { | |
164 | /// /// Creates a new Viking. | |
165 | /// fn new(name: &str, country: &str) -> Viking { | |
166 | /// Viking { name: name.to_string(), country: country.to_string() } | |
167 | /// } | |
168 | /// } | |
169 | /// | |
170 | /// // Use a HashMap to store the vikings' health points. | |
171 | /// let mut vikings = HashMap::new(); | |
172 | /// | |
173 | /// vikings.insert(Viking::new("Einar", "Norway"), 25); | |
174 | /// vikings.insert(Viking::new("Olaf", "Denmark"), 24); | |
175 | /// vikings.insert(Viking::new("Harald", "Iceland"), 12); | |
176 | /// | |
177 | /// // Use derived implementation to print the status of the vikings. | |
178 | /// for (viking, health) in &vikings { | |
179 | /// println!("{:?} has {} hp", viking, health); | |
180 | /// } | |
181 | /// ``` | |
182 | /// | |
183 | /// A `HashMap` with fixed list of elements can be initialized from an array: | |
184 | /// | |
185 | /// ``` | |
186 | /// use hashbrown::HashMap; | |
187 | /// | |
3dfed10e XL |
188 | /// let timber_resources: HashMap<&str, i32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)] |
189 | /// .iter().cloned().collect(); | |
190 | /// // use the values stored in map | |
48663c56 | 191 | /// ``` |
6a06907d | 192 | pub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator + Clone = Global> { |
48663c56 | 193 | pub(crate) hash_builder: S, |
6a06907d | 194 | pub(crate) table: RawTable<(K, V), A>, |
48663c56 XL |
195 | } |
196 | ||
3dfed10e XL |
197 | impl<K: Clone, V: Clone, S: Clone> Clone for HashMap<K, V, S> { |
198 | fn clone(&self) -> Self { | |
199 | HashMap { | |
200 | hash_builder: self.hash_builder.clone(), | |
201 | table: self.table.clone(), | |
202 | } | |
203 | } | |
204 | ||
205 | fn clone_from(&mut self, source: &Self) { | |
206 | self.table.clone_from(&source.table); | |
207 | ||
208 | // Update hash_builder only if we successfully cloned all elements. | |
209 | self.hash_builder.clone_from(&source.hash_builder); | |
210 | } | |
211 | } | |
212 | ||
6a06907d XL |
213 | /// Ensures that a single closure type across uses of this which, in turn prevents multiple |
214 | /// instances of any functions like RawTable::reserve from being generated | |
e74abb32 | 215 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d XL |
216 | pub(crate) fn make_hasher<K, Q, V, S>(hash_builder: &S) -> impl Fn(&(Q, V)) -> u64 + '_ |
217 | where | |
218 | K: Borrow<Q>, | |
219 | Q: Hash, | |
220 | S: BuildHasher, | |
221 | { | |
222 | move |val| make_hash::<K, Q, S>(hash_builder, &val.0) | |
223 | } | |
224 | ||
225 | /// Ensures that a single closure type across uses of this which, in turn prevents multiple | |
226 | /// instances of any functions like RawTable::reserve from being generated | |
227 | #[cfg_attr(feature = "inline-more", inline)] | |
228 | fn equivalent_key<Q, K, V>(k: &Q) -> impl Fn(&(K, V)) -> bool + '_ | |
229 | where | |
230 | K: Borrow<Q>, | |
231 | Q: ?Sized + Eq, | |
232 | { | |
233 | move |x| k.eq(x.0.borrow()) | |
234 | } | |
235 | ||
236 | /// Ensures that a single closure type across uses of this which, in turn prevents multiple | |
237 | /// instances of any functions like RawTable::reserve from being generated | |
238 | #[cfg_attr(feature = "inline-more", inline)] | |
239 | fn equivalent<Q, K>(k: &Q) -> impl Fn(&K) -> bool + '_ | |
240 | where | |
241 | K: Borrow<Q>, | |
242 | Q: ?Sized + Eq, | |
243 | { | |
244 | move |x| k.eq(x.borrow()) | |
245 | } | |
246 | ||
247 | #[cfg_attr(feature = "inline-more", inline)] | |
248 | pub(crate) fn make_hash<K, Q, S>(hash_builder: &S, val: &Q) -> u64 | |
249 | where | |
250 | K: Borrow<Q>, | |
251 | Q: Hash + ?Sized, | |
252 | S: BuildHasher, | |
253 | { | |
254 | use core::hash::Hasher; | |
255 | let mut state = hash_builder.build_hasher(); | |
256 | val.hash(&mut state); | |
257 | state.finish() | |
258 | } | |
259 | ||
260 | #[cfg_attr(feature = "inline-more", inline)] | |
261 | pub(crate) fn make_insert_hash<K, S>(hash_builder: &S, val: &K) -> u64 | |
262 | where | |
263 | K: Hash, | |
264 | S: BuildHasher, | |
265 | { | |
266 | use core::hash::Hasher; | |
48663c56 XL |
267 | let mut state = hash_builder.build_hasher(); |
268 | val.hash(&mut state); | |
269 | state.finish() | |
270 | } | |
271 | ||
e74abb32 | 272 | #[cfg(feature = "ahash")] |
48663c56 XL |
273 | impl<K, V> HashMap<K, V, DefaultHashBuilder> { |
274 | /// Creates an empty `HashMap`. | |
275 | /// | |
276 | /// The hash map is initially created with a capacity of 0, so it will not allocate until it | |
277 | /// is first inserted into. | |
278 | /// | |
279 | /// # Examples | |
280 | /// | |
281 | /// ``` | |
282 | /// use hashbrown::HashMap; | |
283 | /// let mut map: HashMap<&str, i32> = HashMap::new(); | |
284 | /// ``` | |
e74abb32 | 285 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
286 | pub fn new() -> Self { |
287 | Self::default() | |
288 | } | |
289 | ||
290 | /// Creates an empty `HashMap` with the specified capacity. | |
291 | /// | |
292 | /// The hash map will be able to hold at least `capacity` elements without | |
293 | /// reallocating. If `capacity` is 0, the hash map will not allocate. | |
294 | /// | |
295 | /// # Examples | |
296 | /// | |
297 | /// ``` | |
298 | /// use hashbrown::HashMap; | |
299 | /// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10); | |
300 | /// ``` | |
e74abb32 | 301 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
302 | pub fn with_capacity(capacity: usize) -> Self { |
303 | Self::with_capacity_and_hasher(capacity, DefaultHashBuilder::default()) | |
304 | } | |
305 | } | |
306 | ||
6a06907d XL |
307 | #[cfg(feature = "ahash")] |
308 | impl<K, V, A: Allocator + Clone> HashMap<K, V, DefaultHashBuilder, A> { | |
309 | /// Creates an empty `HashMap` using the given allocator. | |
310 | /// | |
311 | /// The hash map is initially created with a capacity of 0, so it will not allocate until it | |
312 | /// is first inserted into. | |
313 | #[cfg_attr(feature = "inline-more", inline)] | |
314 | pub fn new_in(alloc: A) -> Self { | |
315 | Self::with_hasher_in(DefaultHashBuilder::default(), alloc) | |
316 | } | |
317 | ||
318 | /// Creates an empty `HashMap` with the specified capacity using the given allocator. | |
319 | /// | |
320 | /// The hash map will be able to hold at least `capacity` elements without | |
321 | /// reallocating. If `capacity` is 0, the hash map will not allocate. | |
322 | #[cfg_attr(feature = "inline-more", inline)] | |
323 | pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { | |
324 | Self::with_capacity_and_hasher_in(capacity, DefaultHashBuilder::default(), alloc) | |
325 | } | |
326 | } | |
327 | ||
48663c56 XL |
328 | impl<K, V, S> HashMap<K, V, S> { |
329 | /// Creates an empty `HashMap` which will use the given hash builder to hash | |
330 | /// keys. | |
331 | /// | |
332 | /// The created map has the default initial capacity. | |
333 | /// | |
334 | /// Warning: `hash_builder` is normally randomly generated, and | |
335 | /// is designed to allow HashMaps to be resistant to attacks that | |
336 | /// cause many collisions and very poor performance. Setting it | |
337 | /// manually using this function can expose a DoS attack vector. | |
338 | /// | |
3dfed10e XL |
339 | /// The `hash_builder` passed should implement the [`BuildHasher`] trait for |
340 | /// the HashMap to be useful, see its documentation for details. | |
341 | /// | |
48663c56 XL |
342 | /// # Examples |
343 | /// | |
344 | /// ``` | |
345 | /// use hashbrown::HashMap; | |
346 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
347 | /// | |
348 | /// let s = DefaultHashBuilder::default(); | |
349 | /// let mut map = HashMap::with_hasher(s); | |
350 | /// map.insert(1, 2); | |
351 | /// ``` | |
3dfed10e XL |
352 | /// |
353 | /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html | |
e74abb32 | 354 | #[cfg_attr(feature = "inline-more", inline)] |
1b1a35ee | 355 | pub const fn with_hasher(hash_builder: S) -> Self { |
48663c56 XL |
356 | Self { |
357 | hash_builder, | |
358 | table: RawTable::new(), | |
359 | } | |
360 | } | |
361 | ||
362 | /// Creates an empty `HashMap` with the specified capacity, using `hash_builder` | |
363 | /// to hash the keys. | |
364 | /// | |
365 | /// The hash map will be able to hold at least `capacity` elements without | |
366 | /// reallocating. If `capacity` is 0, the hash map will not allocate. | |
367 | /// | |
368 | /// Warning: `hash_builder` is normally randomly generated, and | |
369 | /// is designed to allow HashMaps to be resistant to attacks that | |
370 | /// cause many collisions and very poor performance. Setting it | |
371 | /// manually using this function can expose a DoS attack vector. | |
372 | /// | |
3dfed10e XL |
373 | /// The `hash_builder` passed should implement the [`BuildHasher`] trait for |
374 | /// the HashMap to be useful, see its documentation for details. | |
375 | /// | |
48663c56 XL |
376 | /// # Examples |
377 | /// | |
378 | /// ``` | |
379 | /// use hashbrown::HashMap; | |
380 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
381 | /// | |
382 | /// let s = DefaultHashBuilder::default(); | |
383 | /// let mut map = HashMap::with_capacity_and_hasher(10, s); | |
384 | /// map.insert(1, 2); | |
385 | /// ``` | |
3dfed10e XL |
386 | /// |
387 | /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html | |
e74abb32 | 388 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
389 | pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self { |
390 | Self { | |
391 | hash_builder, | |
392 | table: RawTable::with_capacity(capacity), | |
393 | } | |
394 | } | |
6a06907d XL |
395 | } |
396 | ||
397 | impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { | |
398 | /// Creates an empty `HashMap` which will use the given hash builder to hash | |
399 | /// keys. It will be allocated with the given allocator. | |
400 | /// | |
401 | /// The created map has the default initial capacity. | |
402 | /// | |
403 | /// Warning: `hash_builder` is normally randomly generated, and | |
404 | /// is designed to allow HashMaps to be resistant to attacks that | |
405 | /// cause many collisions and very poor performance. Setting it | |
406 | /// manually using this function can expose a DoS attack vector. | |
407 | /// | |
408 | /// # Examples | |
409 | /// | |
410 | /// ``` | |
411 | /// use hashbrown::HashMap; | |
412 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
413 | /// | |
414 | /// let s = DefaultHashBuilder::default(); | |
415 | /// let mut map = HashMap::with_hasher(s); | |
416 | /// map.insert(1, 2); | |
417 | /// ``` | |
418 | #[cfg_attr(feature = "inline-more", inline)] | |
419 | pub fn with_hasher_in(hash_builder: S, alloc: A) -> Self { | |
420 | Self { | |
421 | hash_builder, | |
422 | table: RawTable::new_in(alloc), | |
423 | } | |
424 | } | |
425 | ||
426 | /// Creates an empty `HashMap` with the specified capacity, using `hash_builder` | |
427 | /// to hash the keys. It will be allocated with the given allocator. | |
428 | /// | |
429 | /// The hash map will be able to hold at least `capacity` elements without | |
430 | /// reallocating. If `capacity` is 0, the hash map will not allocate. | |
431 | /// | |
432 | /// Warning: `hash_builder` is normally randomly generated, and | |
433 | /// is designed to allow HashMaps to be resistant to attacks that | |
434 | /// cause many collisions and very poor performance. Setting it | |
435 | /// manually using this function can expose a DoS attack vector. | |
436 | /// | |
437 | /// # Examples | |
438 | /// | |
439 | /// ``` | |
440 | /// use hashbrown::HashMap; | |
441 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
442 | /// | |
443 | /// let s = DefaultHashBuilder::default(); | |
444 | /// let mut map = HashMap::with_capacity_and_hasher(10, s); | |
445 | /// map.insert(1, 2); | |
446 | /// ``` | |
447 | #[cfg_attr(feature = "inline-more", inline)] | |
448 | pub fn with_capacity_and_hasher_in(capacity: usize, hash_builder: S, alloc: A) -> Self { | |
449 | Self { | |
450 | hash_builder, | |
451 | table: RawTable::with_capacity_in(capacity, alloc), | |
452 | } | |
453 | } | |
48663c56 XL |
454 | |
455 | /// Returns a reference to the map's [`BuildHasher`]. | |
456 | /// | |
457 | /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html | |
458 | /// | |
459 | /// # Examples | |
460 | /// | |
461 | /// ``` | |
462 | /// use hashbrown::HashMap; | |
463 | /// use hashbrown::hash_map::DefaultHashBuilder; | |
464 | /// | |
465 | /// let hasher = DefaultHashBuilder::default(); | |
466 | /// let map: HashMap<i32, i32> = HashMap::with_hasher(hasher); | |
467 | /// let hasher: &DefaultHashBuilder = map.hasher(); | |
468 | /// ``` | |
e74abb32 | 469 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
470 | pub fn hasher(&self) -> &S { |
471 | &self.hash_builder | |
472 | } | |
473 | ||
474 | /// Returns the number of elements the map can hold without reallocating. | |
475 | /// | |
476 | /// This number is a lower bound; the `HashMap<K, V>` might be able to hold | |
477 | /// more, but is guaranteed to be able to hold at least this many. | |
478 | /// | |
479 | /// # Examples | |
480 | /// | |
481 | /// ``` | |
482 | /// use hashbrown::HashMap; | |
483 | /// let map: HashMap<i32, i32> = HashMap::with_capacity(100); | |
484 | /// assert!(map.capacity() >= 100); | |
485 | /// ``` | |
e74abb32 | 486 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
487 | pub fn capacity(&self) -> usize { |
488 | self.table.capacity() | |
489 | } | |
490 | ||
491 | /// An iterator visiting all keys in arbitrary order. | |
492 | /// The iterator element type is `&'a K`. | |
493 | /// | |
494 | /// # Examples | |
495 | /// | |
496 | /// ``` | |
497 | /// use hashbrown::HashMap; | |
498 | /// | |
499 | /// let mut map = HashMap::new(); | |
500 | /// map.insert("a", 1); | |
501 | /// map.insert("b", 2); | |
502 | /// map.insert("c", 3); | |
503 | /// | |
504 | /// for key in map.keys() { | |
505 | /// println!("{}", key); | |
506 | /// } | |
507 | /// ``` | |
e74abb32 | 508 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
509 | pub fn keys(&self) -> Keys<'_, K, V> { |
510 | Keys { inner: self.iter() } | |
511 | } | |
512 | ||
513 | /// An iterator visiting all values in arbitrary order. | |
514 | /// The iterator element type is `&'a V`. | |
515 | /// | |
516 | /// # Examples | |
517 | /// | |
518 | /// ``` | |
519 | /// use hashbrown::HashMap; | |
520 | /// | |
521 | /// let mut map = HashMap::new(); | |
522 | /// map.insert("a", 1); | |
523 | /// map.insert("b", 2); | |
524 | /// map.insert("c", 3); | |
525 | /// | |
526 | /// for val in map.values() { | |
527 | /// println!("{}", val); | |
528 | /// } | |
529 | /// ``` | |
e74abb32 | 530 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
531 | pub fn values(&self) -> Values<'_, K, V> { |
532 | Values { inner: self.iter() } | |
533 | } | |
534 | ||
535 | /// An iterator visiting all values mutably in arbitrary order. | |
536 | /// The iterator element type is `&'a mut V`. | |
537 | /// | |
538 | /// # Examples | |
539 | /// | |
540 | /// ``` | |
541 | /// use hashbrown::HashMap; | |
542 | /// | |
543 | /// let mut map = HashMap::new(); | |
544 | /// | |
545 | /// map.insert("a", 1); | |
546 | /// map.insert("b", 2); | |
547 | /// map.insert("c", 3); | |
548 | /// | |
549 | /// for val in map.values_mut() { | |
550 | /// *val = *val + 10; | |
551 | /// } | |
552 | /// | |
553 | /// for val in map.values() { | |
554 | /// println!("{}", val); | |
555 | /// } | |
556 | /// ``` | |
e74abb32 | 557 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
558 | pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { |
559 | ValuesMut { | |
560 | inner: self.iter_mut(), | |
561 | } | |
562 | } | |
563 | ||
564 | /// An iterator visiting all key-value pairs in arbitrary order. | |
565 | /// The iterator element type is `(&'a K, &'a V)`. | |
566 | /// | |
567 | /// # Examples | |
568 | /// | |
569 | /// ``` | |
570 | /// use hashbrown::HashMap; | |
571 | /// | |
572 | /// let mut map = HashMap::new(); | |
573 | /// map.insert("a", 1); | |
574 | /// map.insert("b", 2); | |
575 | /// map.insert("c", 3); | |
576 | /// | |
577 | /// for (key, val) in map.iter() { | |
578 | /// println!("key: {} val: {}", key, val); | |
579 | /// } | |
580 | /// ``` | |
e74abb32 | 581 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
582 | pub fn iter(&self) -> Iter<'_, K, V> { |
583 | // Here we tie the lifetime of self to the iter. | |
584 | unsafe { | |
585 | Iter { | |
586 | inner: self.table.iter(), | |
587 | marker: PhantomData, | |
588 | } | |
589 | } | |
590 | } | |
591 | ||
592 | /// An iterator visiting all key-value pairs in arbitrary order, | |
593 | /// with mutable references to the values. | |
594 | /// The iterator element type is `(&'a K, &'a mut V)`. | |
595 | /// | |
596 | /// # Examples | |
597 | /// | |
598 | /// ``` | |
599 | /// use hashbrown::HashMap; | |
600 | /// | |
601 | /// let mut map = HashMap::new(); | |
602 | /// map.insert("a", 1); | |
603 | /// map.insert("b", 2); | |
604 | /// map.insert("c", 3); | |
605 | /// | |
606 | /// // Update all values | |
607 | /// for (_, val) in map.iter_mut() { | |
608 | /// *val *= 2; | |
609 | /// } | |
610 | /// | |
611 | /// for (key, val) in &map { | |
612 | /// println!("key: {} val: {}", key, val); | |
613 | /// } | |
614 | /// ``` | |
e74abb32 | 615 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
616 | pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { |
617 | // Here we tie the lifetime of self to the iter. | |
618 | unsafe { | |
619 | IterMut { | |
620 | inner: self.table.iter(), | |
621 | marker: PhantomData, | |
622 | } | |
623 | } | |
624 | } | |
625 | ||
626 | #[cfg(test)] | |
e74abb32 | 627 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
628 | fn raw_capacity(&self) -> usize { |
629 | self.table.buckets() | |
630 | } | |
631 | ||
632 | /// Returns the number of elements in the map. | |
633 | /// | |
634 | /// # Examples | |
635 | /// | |
636 | /// ``` | |
637 | /// use hashbrown::HashMap; | |
638 | /// | |
639 | /// let mut a = HashMap::new(); | |
640 | /// assert_eq!(a.len(), 0); | |
641 | /// a.insert(1, "a"); | |
642 | /// assert_eq!(a.len(), 1); | |
643 | /// ``` | |
e74abb32 | 644 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
645 | pub fn len(&self) -> usize { |
646 | self.table.len() | |
647 | } | |
648 | ||
649 | /// Returns `true` if the map contains no elements. | |
650 | /// | |
651 | /// # Examples | |
652 | /// | |
653 | /// ``` | |
654 | /// use hashbrown::HashMap; | |
655 | /// | |
656 | /// let mut a = HashMap::new(); | |
657 | /// assert!(a.is_empty()); | |
658 | /// a.insert(1, "a"); | |
659 | /// assert!(!a.is_empty()); | |
660 | /// ``` | |
e74abb32 | 661 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
662 | pub fn is_empty(&self) -> bool { |
663 | self.len() == 0 | |
664 | } | |
665 | ||
666 | /// Clears the map, returning all key-value pairs as an iterator. Keeps the | |
667 | /// allocated memory for reuse. | |
668 | /// | |
669 | /// # Examples | |
670 | /// | |
671 | /// ``` | |
672 | /// use hashbrown::HashMap; | |
673 | /// | |
674 | /// let mut a = HashMap::new(); | |
675 | /// a.insert(1, "a"); | |
676 | /// a.insert(2, "b"); | |
677 | /// | |
678 | /// for (k, v) in a.drain().take(1) { | |
679 | /// assert!(k == 1 || k == 2); | |
680 | /// assert!(v == "a" || v == "b"); | |
681 | /// } | |
682 | /// | |
683 | /// assert!(a.is_empty()); | |
684 | /// ``` | |
e74abb32 | 685 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d | 686 | pub fn drain(&mut self) -> Drain<'_, K, V, A> { |
29967ef6 XL |
687 | Drain { |
688 | inner: self.table.drain(), | |
48663c56 XL |
689 | } |
690 | } | |
691 | ||
3dfed10e XL |
692 | /// Retains only the elements specified by the predicate. |
693 | /// | |
694 | /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`. | |
695 | /// | |
696 | /// # Examples | |
697 | /// | |
698 | /// ``` | |
699 | /// use hashbrown::HashMap; | |
700 | /// | |
701 | /// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect(); | |
702 | /// map.retain(|&k, _| k % 2 == 0); | |
703 | /// assert_eq!(map.len(), 4); | |
704 | /// ``` | |
705 | pub fn retain<F>(&mut self, mut f: F) | |
706 | where | |
707 | F: FnMut(&K, &mut V) -> bool, | |
708 | { | |
709 | // Here we only use `iter` as a temporary, preventing use-after-free | |
710 | unsafe { | |
711 | for item in self.table.iter() { | |
712 | let &mut (ref key, ref mut value) = item.as_mut(); | |
713 | if !f(key, value) { | |
714 | self.table.erase(item); | |
715 | } | |
716 | } | |
717 | } | |
718 | } | |
719 | ||
1b1a35ee | 720 | /// Drains elements which are true under the given predicate, |
3dfed10e XL |
721 | /// and returns an iterator over the removed items. |
722 | /// | |
1b1a35ee | 723 | /// In other words, move all pairs `(k, v)` such that `f(&k,&mut v)` returns `true` out |
3dfed10e XL |
724 | /// into another iterator. |
725 | /// | |
1b1a35ee | 726 | /// When the returned DrainedFilter is dropped, any remaining elements that satisfy |
3dfed10e XL |
727 | /// the predicate are dropped from the table. |
728 | /// | |
729 | /// # Examples | |
730 | /// | |
731 | /// ``` | |
732 | /// use hashbrown::HashMap; | |
733 | /// | |
1b1a35ee XL |
734 | /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect(); |
735 | /// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect(); | |
736 | /// | |
737 | /// let mut evens = drained.keys().cloned().collect::<Vec<_>>(); | |
738 | /// let mut odds = map.keys().cloned().collect::<Vec<_>>(); | |
739 | /// evens.sort(); | |
740 | /// odds.sort(); | |
741 | /// | |
742 | /// assert_eq!(evens, vec![0, 2, 4, 6]); | |
743 | /// assert_eq!(odds, vec![1, 3, 5, 7]); | |
3dfed10e XL |
744 | /// ``` |
745 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 746 | pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, K, V, F, A> |
3dfed10e XL |
747 | where |
748 | F: FnMut(&K, &mut V) -> bool, | |
749 | { | |
750 | DrainFilter { | |
751 | f, | |
752 | inner: DrainFilterInner { | |
753 | iter: unsafe { self.table.iter() }, | |
754 | table: &mut self.table, | |
755 | }, | |
756 | } | |
757 | } | |
758 | ||
48663c56 XL |
759 | /// Clears the map, removing all key-value pairs. Keeps the allocated memory |
760 | /// for reuse. | |
761 | /// | |
762 | /// # Examples | |
763 | /// | |
764 | /// ``` | |
765 | /// use hashbrown::HashMap; | |
766 | /// | |
767 | /// let mut a = HashMap::new(); | |
768 | /// a.insert(1, "a"); | |
769 | /// a.clear(); | |
770 | /// assert!(a.is_empty()); | |
771 | /// ``` | |
e74abb32 | 772 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
773 | pub fn clear(&mut self) { |
774 | self.table.clear(); | |
775 | } | |
776 | } | |
777 | ||
6a06907d | 778 | impl<K, V, S, A> HashMap<K, V, S, A> |
48663c56 XL |
779 | where |
780 | K: Eq + Hash, | |
781 | S: BuildHasher, | |
6a06907d | 782 | A: Allocator + Clone, |
48663c56 XL |
783 | { |
784 | /// Reserves capacity for at least `additional` more elements to be inserted | |
785 | /// in the `HashMap`. The collection may reserve more space to avoid | |
786 | /// frequent reallocations. | |
787 | /// | |
788 | /// # Panics | |
789 | /// | |
790 | /// Panics if the new allocation size overflows [`usize`]. | |
791 | /// | |
792 | /// [`usize`]: https://doc.rust-lang.org/std/primitive.usize.html | |
793 | /// | |
794 | /// # Examples | |
795 | /// | |
796 | /// ``` | |
797 | /// use hashbrown::HashMap; | |
798 | /// let mut map: HashMap<&str, i32> = HashMap::new(); | |
799 | /// map.reserve(10); | |
800 | /// ``` | |
e74abb32 | 801 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 802 | pub fn reserve(&mut self, additional: usize) { |
48663c56 | 803 | self.table |
6a06907d | 804 | .reserve(additional, make_hasher::<K, _, V, S>(&self.hash_builder)); |
48663c56 XL |
805 | } |
806 | ||
807 | /// Tries to reserve capacity for at least `additional` more elements to be inserted | |
808 | /// in the given `HashMap<K,V>`. The collection may reserve more space to avoid | |
809 | /// frequent reallocations. | |
810 | /// | |
811 | /// # Errors | |
812 | /// | |
813 | /// If the capacity overflows, or the allocator reports a failure, then an error | |
814 | /// is returned. | |
815 | /// | |
816 | /// # Examples | |
817 | /// | |
818 | /// ``` | |
819 | /// use hashbrown::HashMap; | |
820 | /// let mut map: HashMap<&str, isize> = HashMap::new(); | |
821 | /// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?"); | |
822 | /// ``` | |
e74abb32 | 823 | #[cfg_attr(feature = "inline-more", inline)] |
3dfed10e | 824 | pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { |
48663c56 | 825 | self.table |
6a06907d | 826 | .try_reserve(additional, make_hasher::<K, _, V, S>(&self.hash_builder)) |
48663c56 XL |
827 | } |
828 | ||
829 | /// Shrinks the capacity of the map as much as possible. It will drop | |
830 | /// down as much as possible while maintaining the internal rules | |
831 | /// and possibly leaving some space in accordance with the resize policy. | |
832 | /// | |
833 | /// # Examples | |
834 | /// | |
835 | /// ``` | |
836 | /// use hashbrown::HashMap; | |
837 | /// | |
838 | /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100); | |
839 | /// map.insert(1, 2); | |
840 | /// map.insert(3, 4); | |
841 | /// assert!(map.capacity() >= 100); | |
842 | /// map.shrink_to_fit(); | |
843 | /// assert!(map.capacity() >= 2); | |
844 | /// ``` | |
e74abb32 | 845 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 846 | pub fn shrink_to_fit(&mut self) { |
6a06907d XL |
847 | self.table |
848 | .shrink_to(0, make_hasher::<K, _, V, S>(&self.hash_builder)); | |
48663c56 XL |
849 | } |
850 | ||
851 | /// Shrinks the capacity of the map with a lower limit. It will drop | |
852 | /// down no lower than the supplied limit while maintaining the internal rules | |
853 | /// and possibly leaving some space in accordance with the resize policy. | |
854 | /// | |
855 | /// This function does nothing if the current capacity is smaller than the | |
856 | /// supplied minimum capacity. | |
857 | /// | |
858 | /// # Examples | |
859 | /// | |
860 | /// ``` | |
861 | /// use hashbrown::HashMap; | |
862 | /// | |
863 | /// let mut map: HashMap<i32, i32> = HashMap::with_capacity(100); | |
864 | /// map.insert(1, 2); | |
865 | /// map.insert(3, 4); | |
866 | /// assert!(map.capacity() >= 100); | |
867 | /// map.shrink_to(10); | |
868 | /// assert!(map.capacity() >= 10); | |
869 | /// map.shrink_to(0); | |
870 | /// assert!(map.capacity() >= 2); | |
871 | /// map.shrink_to(10); | |
872 | /// assert!(map.capacity() >= 2); | |
873 | /// ``` | |
e74abb32 | 874 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 875 | pub fn shrink_to(&mut self, min_capacity: usize) { |
48663c56 | 876 | self.table |
6a06907d | 877 | .shrink_to(min_capacity, make_hasher::<K, _, V, S>(&self.hash_builder)); |
48663c56 XL |
878 | } |
879 | ||
880 | /// Gets the given key's corresponding entry in the map for in-place manipulation. | |
881 | /// | |
882 | /// # Examples | |
883 | /// | |
884 | /// ``` | |
885 | /// use hashbrown::HashMap; | |
886 | /// | |
887 | /// let mut letters = HashMap::new(); | |
888 | /// | |
889 | /// for ch in "a short treatise on fungi".chars() { | |
890 | /// let counter = letters.entry(ch).or_insert(0); | |
891 | /// *counter += 1; | |
892 | /// } | |
893 | /// | |
894 | /// assert_eq!(letters[&'s'], 2); | |
895 | /// assert_eq!(letters[&'t'], 3); | |
896 | /// assert_eq!(letters[&'u'], 1); | |
897 | /// assert_eq!(letters.get(&'y'), None); | |
898 | /// ``` | |
e74abb32 | 899 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d XL |
900 | pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S, A> { |
901 | let hash = make_insert_hash::<K, S>(&self.hash_builder, &key); | |
902 | if let Some(elem) = self.table.find(hash, equivalent_key(&key)) { | |
48663c56 | 903 | Entry::Occupied(OccupiedEntry { |
1b1a35ee | 904 | hash, |
48663c56 XL |
905 | key: Some(key), |
906 | elem, | |
907 | table: self, | |
908 | }) | |
909 | } else { | |
910 | Entry::Vacant(VacantEntry { | |
911 | hash, | |
912 | key, | |
913 | table: self, | |
914 | }) | |
915 | } | |
916 | } | |
917 | ||
918 | /// Returns a reference to the value corresponding to the key. | |
919 | /// | |
920 | /// The key may be any borrowed form of the map's key type, but | |
921 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
922 | /// the key type. | |
923 | /// | |
924 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
925 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
926 | /// | |
927 | /// # Examples | |
928 | /// | |
929 | /// ``` | |
930 | /// use hashbrown::HashMap; | |
931 | /// | |
932 | /// let mut map = HashMap::new(); | |
933 | /// map.insert(1, "a"); | |
934 | /// assert_eq!(map.get(&1), Some(&"a")); | |
935 | /// assert_eq!(map.get(&2), None); | |
936 | /// ``` | |
937 | #[inline] | |
938 | pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> | |
939 | where | |
940 | K: Borrow<Q>, | |
941 | Q: Hash + Eq, | |
942 | { | |
3dfed10e | 943 | // Avoid `Option::map` because it bloats LLVM IR. |
29967ef6 XL |
944 | match self.get_inner(k) { |
945 | Some(&(_, ref v)) => Some(v), | |
3dfed10e XL |
946 | None => None, |
947 | } | |
48663c56 XL |
948 | } |
949 | ||
950 | /// Returns the key-value pair corresponding to the supplied key. | |
951 | /// | |
952 | /// The supplied key may be any borrowed form of the map's key type, but | |
953 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
954 | /// the key type. | |
955 | /// | |
956 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
957 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
958 | /// | |
959 | /// # Examples | |
960 | /// | |
961 | /// ``` | |
962 | /// use hashbrown::HashMap; | |
963 | /// | |
964 | /// let mut map = HashMap::new(); | |
965 | /// map.insert(1, "a"); | |
966 | /// assert_eq!(map.get_key_value(&1), Some((&1, &"a"))); | |
967 | /// assert_eq!(map.get_key_value(&2), None); | |
968 | /// ``` | |
969 | #[inline] | |
970 | pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)> | |
971 | where | |
972 | K: Borrow<Q>, | |
973 | Q: Hash + Eq, | |
974 | { | |
3dfed10e | 975 | // Avoid `Option::map` because it bloats LLVM IR. |
29967ef6 XL |
976 | match self.get_inner(k) { |
977 | Some(&(ref key, ref value)) => Some((key, value)), | |
3dfed10e XL |
978 | None => None, |
979 | } | |
980 | } | |
981 | ||
29967ef6 XL |
982 | #[inline] |
983 | fn get_inner<Q: ?Sized>(&self, k: &Q) -> Option<&(K, V)> | |
984 | where | |
985 | K: Borrow<Q>, | |
986 | Q: Hash + Eq, | |
987 | { | |
6a06907d XL |
988 | let hash = make_hash::<K, Q, S>(&self.hash_builder, k); |
989 | self.table.get(hash, equivalent_key(k)) | |
29967ef6 XL |
990 | } |
991 | ||
3dfed10e XL |
992 | /// Returns the key-value pair corresponding to the supplied key, with a mutable reference to value. |
993 | /// | |
994 | /// The supplied key may be any borrowed form of the map's key type, but | |
995 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
996 | /// the key type. | |
997 | /// | |
998 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
999 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1000 | /// | |
1001 | /// # Examples | |
1002 | /// | |
1003 | /// ``` | |
1004 | /// use hashbrown::HashMap; | |
1005 | /// | |
1006 | /// let mut map = HashMap::new(); | |
1007 | /// map.insert(1, "a"); | |
1008 | /// let (k, v) = map.get_key_value_mut(&1).unwrap(); | |
1009 | /// assert_eq!(k, &1); | |
1010 | /// assert_eq!(v, &mut "a"); | |
1011 | /// *v = "b"; | |
1012 | /// assert_eq!(map.get_key_value_mut(&1), Some((&1, &mut "b"))); | |
1013 | /// assert_eq!(map.get_key_value_mut(&2), None); | |
1014 | /// ``` | |
1015 | #[inline] | |
1016 | pub fn get_key_value_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<(&K, &mut V)> | |
1017 | where | |
1018 | K: Borrow<Q>, | |
1019 | Q: Hash + Eq, | |
1020 | { | |
3dfed10e | 1021 | // Avoid `Option::map` because it bloats LLVM IR. |
29967ef6 XL |
1022 | match self.get_inner_mut(k) { |
1023 | Some(&mut (ref key, ref mut value)) => Some((key, value)), | |
3dfed10e XL |
1024 | None => None, |
1025 | } | |
48663c56 XL |
1026 | } |
1027 | ||
1028 | /// Returns `true` if the map contains a value for the specified key. | |
1029 | /// | |
1030 | /// The key may be any borrowed form of the map's key type, but | |
1031 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
1032 | /// the key type. | |
1033 | /// | |
1034 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
1035 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1036 | /// | |
1037 | /// # Examples | |
1038 | /// | |
1039 | /// ``` | |
1040 | /// use hashbrown::HashMap; | |
1041 | /// | |
1042 | /// let mut map = HashMap::new(); | |
1043 | /// map.insert(1, "a"); | |
1044 | /// assert_eq!(map.contains_key(&1), true); | |
1045 | /// assert_eq!(map.contains_key(&2), false); | |
1046 | /// ``` | |
e74abb32 | 1047 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1048 | pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool |
1049 | where | |
1050 | K: Borrow<Q>, | |
1051 | Q: Hash + Eq, | |
1052 | { | |
29967ef6 | 1053 | self.get_inner(k).is_some() |
48663c56 XL |
1054 | } |
1055 | ||
1056 | /// Returns a mutable reference to the value corresponding to the key. | |
1057 | /// | |
1058 | /// The key may be any borrowed form of the map's key type, but | |
1059 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
1060 | /// the key type. | |
1061 | /// | |
1062 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
1063 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1064 | /// | |
1065 | /// # Examples | |
1066 | /// | |
1067 | /// ``` | |
1068 | /// use hashbrown::HashMap; | |
1069 | /// | |
1070 | /// let mut map = HashMap::new(); | |
1071 | /// map.insert(1, "a"); | |
1072 | /// if let Some(x) = map.get_mut(&1) { | |
1073 | /// *x = "b"; | |
1074 | /// } | |
1075 | /// assert_eq!(map[&1], "b"); | |
1076 | /// ``` | |
e74abb32 | 1077 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1078 | pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> |
1079 | where | |
1080 | K: Borrow<Q>, | |
1081 | Q: Hash + Eq, | |
1082 | { | |
3dfed10e | 1083 | // Avoid `Option::map` because it bloats LLVM IR. |
29967ef6 XL |
1084 | match self.get_inner_mut(k) { |
1085 | Some(&mut (_, ref mut v)) => Some(v), | |
3dfed10e XL |
1086 | None => None, |
1087 | } | |
48663c56 XL |
1088 | } |
1089 | ||
29967ef6 XL |
1090 | #[inline] |
1091 | fn get_inner_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut (K, V)> | |
1092 | where | |
1093 | K: Borrow<Q>, | |
1094 | Q: Hash + Eq, | |
1095 | { | |
6a06907d XL |
1096 | let hash = make_hash::<K, Q, S>(&self.hash_builder, k); |
1097 | self.table.get_mut(hash, equivalent_key(k)) | |
1098 | } | |
1099 | ||
1100 | /// Attempts to get mutable references to `N` values in the map at once. | |
1101 | /// | |
1102 | /// Returns an array of length `N` with the results of each query. For soundness, | |
1103 | /// at most one mutable reference will be returned to any value. An | |
1104 | /// `Err(UnavailableMutError::Duplicate(i))` in the returned array indicates that a suitable | |
1105 | /// key-value pair exists, but a mutable reference to the value already occurs at index `i` in | |
1106 | /// the returned array. | |
1107 | /// | |
1108 | /// This method is available only if the `nightly` feature is enabled. | |
1109 | /// | |
1110 | /// # Examples | |
1111 | /// | |
1112 | /// ``` | |
1113 | /// use hashbrown::{HashMap, UnavailableMutError}; | |
1114 | /// | |
1115 | /// let mut libraries = HashMap::new(); | |
1116 | /// libraries.insert("Bodleian Library".to_string(), 1602); | |
1117 | /// libraries.insert("Athenæum".to_string(), 1807); | |
1118 | /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691); | |
1119 | /// libraries.insert("Library of Congress".to_string(), 1800); | |
1120 | /// | |
1121 | /// let got = libraries.get_each_mut([ | |
1122 | /// "Athenæum", | |
1123 | /// "New York Public Library", | |
1124 | /// "Athenæum", | |
1125 | /// "Library of Congress", | |
1126 | /// ]); | |
1127 | /// assert_eq!( | |
1128 | /// got, | |
1129 | /// [ | |
1130 | /// Ok(&mut 1807), | |
1131 | /// Err(UnavailableMutError::Absent), | |
1132 | /// Err(UnavailableMutError::Duplicate(0)), | |
1133 | /// Ok(&mut 1800), | |
1134 | /// ] | |
1135 | /// ); | |
1136 | /// ``` | |
1137 | #[cfg(feature = "nightly")] | |
1138 | pub fn get_each_mut<Q: ?Sized, const N: usize>( | |
1139 | &mut self, | |
1140 | ks: [&Q; N], | |
1141 | ) -> [Result<&'_ mut V, UnavailableMutError>; N] | |
1142 | where | |
1143 | K: Borrow<Q>, | |
1144 | Q: Hash + Eq, | |
1145 | { | |
1146 | let mut pairs = self.get_each_inner_mut(ks); | |
1147 | // TODO use `MaybeUninit::uninit_array` here instead once that's stable. | |
1148 | let mut out: [MaybeUninit<Result<&'_ mut V, UnavailableMutError>>; N] = | |
1149 | unsafe { MaybeUninit::uninit().assume_init() }; | |
1150 | for i in 0..N { | |
1151 | out[i] = MaybeUninit::new( | |
1152 | mem::replace(&mut pairs[i], Err(UnavailableMutError::Absent)).map(|(_, v)| v), | |
1153 | ); | |
1154 | } | |
1155 | unsafe { MaybeUninit::array_assume_init(out) } | |
1156 | } | |
1157 | ||
1158 | /// Attempts to get mutable references to `N` values in the map at once, with immutable | |
1159 | /// references to the corresponding keys. | |
1160 | /// | |
1161 | /// Returns an array of length `N` with the results of each query. For soundness, | |
1162 | /// at most one mutable reference will be returned to any value. An | |
1163 | /// `Err(UnavailableMutError::Duplicate(i))` in the returned array indicates that a suitable | |
1164 | /// key-value pair exists, but a mutable reference to the value already occurs at index `i` in | |
1165 | /// the returned array. | |
1166 | /// | |
1167 | /// This method is available only if the `nightly` feature is enabled. | |
1168 | /// | |
1169 | /// # Examples | |
1170 | /// | |
1171 | /// ``` | |
1172 | /// use hashbrown::{HashMap, UnavailableMutError}; | |
1173 | /// | |
1174 | /// let mut libraries = HashMap::new(); | |
1175 | /// libraries.insert("Bodleian Library".to_string(), 1602); | |
1176 | /// libraries.insert("Athenæum".to_string(), 1807); | |
1177 | /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691); | |
1178 | /// libraries.insert("Library of Congress".to_string(), 1800); | |
1179 | /// | |
1180 | /// let got = libraries.get_each_key_value_mut([ | |
1181 | /// "Bodleian Library", | |
1182 | /// "Herzogin-Anna-Amalia-Bibliothek", | |
1183 | /// "Herzogin-Anna-Amalia-Bibliothek", | |
1184 | /// "Gewandhaus", | |
1185 | /// ]); | |
1186 | /// assert_eq!( | |
1187 | /// got, | |
1188 | /// [ | |
1189 | /// Ok((&"Bodleian Library".to_string(), &mut 1602)), | |
1190 | /// Ok((&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut 1691)), | |
1191 | /// Err(UnavailableMutError::Duplicate(1)), | |
1192 | /// Err(UnavailableMutError::Absent), | |
1193 | /// ] | |
1194 | /// ); | |
1195 | /// ``` | |
1196 | #[cfg(feature = "nightly")] | |
1197 | pub fn get_each_key_value_mut<Q: ?Sized, const N: usize>( | |
1198 | &mut self, | |
1199 | ks: [&Q; N], | |
1200 | ) -> [Result<(&'_ K, &'_ mut V), UnavailableMutError>; N] | |
1201 | where | |
1202 | K: Borrow<Q>, | |
1203 | Q: Hash + Eq, | |
1204 | { | |
1205 | let mut pairs = self.get_each_inner_mut(ks); | |
1206 | // TODO use `MaybeUninit::uninit_array` here instead once that's stable. | |
1207 | let mut out: [MaybeUninit<Result<(&'_ K, &'_ mut V), UnavailableMutError>>; N] = | |
1208 | unsafe { MaybeUninit::uninit().assume_init() }; | |
1209 | for i in 0..N { | |
1210 | out[i] = MaybeUninit::new( | |
1211 | mem::replace(&mut pairs[i], Err(UnavailableMutError::Absent)) | |
1212 | .map(|(k, v)| (&*k, v)), | |
1213 | ); | |
1214 | } | |
1215 | unsafe { MaybeUninit::array_assume_init(out) } | |
1216 | } | |
1217 | ||
1218 | #[cfg(feature = "nightly")] | |
1219 | fn get_each_inner_mut<Q: ?Sized, const N: usize>( | |
1220 | &mut self, | |
1221 | ks: [&Q; N], | |
1222 | ) -> [Result<&'_ mut (K, V), UnavailableMutError>; N] | |
1223 | where | |
1224 | K: Borrow<Q>, | |
1225 | Q: Hash + Eq, | |
1226 | { | |
1227 | let mut hashes = [0_u64; N]; | |
1228 | for i in 0..N { | |
1229 | hashes[i] = make_hash::<K, Q, S>(&self.hash_builder, ks[i]); | |
1230 | } | |
1231 | self.table | |
1232 | .get_each_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow())) | |
29967ef6 XL |
1233 | } |
1234 | ||
48663c56 XL |
1235 | /// Inserts a key-value pair into the map. |
1236 | /// | |
1237 | /// If the map did not have this key present, [`None`] is returned. | |
1238 | /// | |
1239 | /// If the map did have this key present, the value is updated, and the old | |
1240 | /// value is returned. The key is not updated, though; this matters for | |
1241 | /// types that can be `==` without being identical. See the [module-level | |
1242 | /// documentation] for more. | |
1243 | /// | |
1244 | /// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None | |
1245 | /// [module-level documentation]: index.html#insert-and-complex-keys | |
1246 | /// | |
1247 | /// # Examples | |
1248 | /// | |
1249 | /// ``` | |
1250 | /// use hashbrown::HashMap; | |
1251 | /// | |
1252 | /// let mut map = HashMap::new(); | |
1253 | /// assert_eq!(map.insert(37, "a"), None); | |
1254 | /// assert_eq!(map.is_empty(), false); | |
1255 | /// | |
1256 | /// map.insert(37, "b"); | |
1257 | /// assert_eq!(map.insert(37, "c"), Some("b")); | |
1258 | /// assert_eq!(map[&37], "c"); | |
1259 | /// ``` | |
e74abb32 | 1260 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 1261 | pub fn insert(&mut self, k: K, v: V) -> Option<V> { |
6a06907d XL |
1262 | let hash = make_insert_hash::<K, S>(&self.hash_builder, &k); |
1263 | if let Some((_, item)) = self.table.get_mut(hash, equivalent_key(&k)) { | |
29967ef6 XL |
1264 | Some(mem::replace(item, v)) |
1265 | } else { | |
29967ef6 | 1266 | self.table |
6a06907d | 1267 | .insert(hash, (k, v), make_hasher::<K, _, V, S>(&self.hash_builder)); |
29967ef6 | 1268 | None |
48663c56 XL |
1269 | } |
1270 | } | |
1271 | ||
6a06907d XL |
1272 | /// Tries to insert a key-value pair into the map, and returns |
1273 | /// a mutable reference to the value in the entry. | |
1274 | /// | |
1275 | /// # Errors | |
1276 | /// | |
1277 | /// If the map already had this key present, nothing is updated, and | |
1278 | /// an error containing the occupied entry and the value is returned. | |
1279 | /// | |
1280 | /// # Examples | |
1281 | /// | |
1282 | /// Basic usage: | |
1283 | /// | |
1284 | /// ``` | |
1285 | /// use hashbrown::HashMap; | |
1286 | /// | |
1287 | /// let mut map = HashMap::new(); | |
1288 | /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a"); | |
1289 | /// | |
1290 | /// let err = map.try_insert(37, "b").unwrap_err(); | |
1291 | /// assert_eq!(err.entry.key(), &37); | |
1292 | /// assert_eq!(err.entry.get(), &"a"); | |
1293 | /// assert_eq!(err.value, "b"); | |
1294 | /// ``` | |
1295 | #[cfg_attr(feature = "inline-more", inline)] | |
1296 | pub fn try_insert( | |
1297 | &mut self, | |
1298 | key: K, | |
1299 | value: V, | |
1300 | ) -> Result<&mut V, OccupiedError<'_, K, V, S, A>> { | |
1301 | match self.entry(key) { | |
1302 | Entry::Occupied(entry) => Err(OccupiedError { entry, value }), | |
1303 | Entry::Vacant(entry) => Ok(entry.insert(value)), | |
1304 | } | |
1305 | } | |
1306 | ||
48663c56 XL |
1307 | /// Removes a key from the map, returning the value at the key if the key |
1308 | /// was previously in the map. | |
1309 | /// | |
1310 | /// The key may be any borrowed form of the map's key type, but | |
1311 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
1312 | /// the key type. | |
1313 | /// | |
1314 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
1315 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1316 | /// | |
1317 | /// # Examples | |
1318 | /// | |
1319 | /// ``` | |
1320 | /// use hashbrown::HashMap; | |
1321 | /// | |
1322 | /// let mut map = HashMap::new(); | |
1323 | /// map.insert(1, "a"); | |
1324 | /// assert_eq!(map.remove(&1), Some("a")); | |
1325 | /// assert_eq!(map.remove(&1), None); | |
1326 | /// ``` | |
e74abb32 | 1327 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1328 | pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> |
1329 | where | |
1330 | K: Borrow<Q>, | |
1331 | Q: Hash + Eq, | |
1332 | { | |
3dfed10e XL |
1333 | // Avoid `Option::map` because it bloats LLVM IR. |
1334 | match self.remove_entry(k) { | |
1335 | Some((_, v)) => Some(v), | |
1336 | None => None, | |
1337 | } | |
48663c56 XL |
1338 | } |
1339 | ||
1340 | /// Removes a key from the map, returning the stored key and value if the | |
1341 | /// key was previously in the map. | |
1342 | /// | |
1343 | /// The key may be any borrowed form of the map's key type, but | |
1344 | /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for | |
1345 | /// the key type. | |
1346 | /// | |
1347 | /// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html | |
1348 | /// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html | |
1349 | /// | |
1350 | /// # Examples | |
1351 | /// | |
1352 | /// ``` | |
1353 | /// use hashbrown::HashMap; | |
1354 | /// | |
48663c56 XL |
1355 | /// let mut map = HashMap::new(); |
1356 | /// map.insert(1, "a"); | |
1357 | /// assert_eq!(map.remove_entry(&1), Some((1, "a"))); | |
1358 | /// assert_eq!(map.remove(&1), None); | |
48663c56 | 1359 | /// ``` |
e74abb32 | 1360 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1361 | pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)> |
1362 | where | |
1363 | K: Borrow<Q>, | |
1364 | Q: Hash + Eq, | |
1365 | { | |
6a06907d XL |
1366 | let hash = make_hash::<K, Q, S>(&self.hash_builder, k); |
1367 | self.table.remove_entry(hash, equivalent_key(k)) | |
48663c56 | 1368 | } |
48663c56 XL |
1369 | } |
1370 | ||
6a06907d | 1371 | impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { |
48663c56 XL |
1372 | /// Creates a raw entry builder for the HashMap. |
1373 | /// | |
1374 | /// Raw entries provide the lowest level of control for searching and | |
1375 | /// manipulating a map. They must be manually initialized with a hash and | |
1376 | /// then manually searched. After this, insertions into a vacant entry | |
1377 | /// still require an owned key to be provided. | |
1378 | /// | |
1379 | /// Raw entries are useful for such exotic situations as: | |
1380 | /// | |
1381 | /// * Hash memoization | |
1382 | /// * Deferring the creation of an owned key until it is known to be required | |
1383 | /// * Using a search key that doesn't work with the Borrow trait | |
1384 | /// * Using custom comparison logic without newtype wrappers | |
1385 | /// | |
1386 | /// Because raw entries provide much more low-level control, it's much easier | |
1387 | /// to put the HashMap into an inconsistent state which, while memory-safe, | |
1388 | /// will cause the map to produce seemingly random results. Higher-level and | |
1389 | /// more foolproof APIs like `entry` should be preferred when possible. | |
1390 | /// | |
1391 | /// In particular, the hash used to initialized the raw entry must still be | |
1392 | /// consistent with the hash of the key that is ultimately stored in the entry. | |
1393 | /// This is because implementations of HashMap may need to recompute hashes | |
1394 | /// when resizing, at which point only the keys are available. | |
1395 | /// | |
1396 | /// Raw entries give mutable access to the keys. This must not be used | |
1397 | /// to modify how the key would compare or hash, as the map will not re-evaluate | |
1398 | /// where the key should go, meaning the keys may become "lost" if their | |
1399 | /// location does not reflect their state. For instance, if you change a key | |
1400 | /// so that the map now contains keys which compare equal, search may start | |
1401 | /// acting erratically, with two keys randomly masking each other. Implementations | |
1402 | /// are free to assume this doesn't happen (within the limits of memory-safety). | |
e74abb32 | 1403 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d | 1404 | pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S, A> { |
48663c56 XL |
1405 | RawEntryBuilderMut { map: self } |
1406 | } | |
1407 | ||
1408 | /// Creates a raw immutable entry builder for the HashMap. | |
1409 | /// | |
1410 | /// Raw entries provide the lowest level of control for searching and | |
1411 | /// manipulating a map. They must be manually initialized with a hash and | |
1412 | /// then manually searched. | |
1413 | /// | |
1414 | /// This is useful for | |
1415 | /// * Hash memoization | |
1416 | /// * Using a search key that doesn't work with the Borrow trait | |
1417 | /// * Using custom comparison logic without newtype wrappers | |
1418 | /// | |
1419 | /// Unless you are in such a situation, higher-level and more foolproof APIs like | |
1420 | /// `get` should be preferred. | |
1421 | /// | |
1422 | /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`. | |
e74abb32 | 1423 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d | 1424 | pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S, A> { |
48663c56 XL |
1425 | RawEntryBuilder { map: self } |
1426 | } | |
1427 | } | |
1428 | ||
6a06907d | 1429 | impl<K, V, S, A> PartialEq for HashMap<K, V, S, A> |
48663c56 XL |
1430 | where |
1431 | K: Eq + Hash, | |
1432 | V: PartialEq, | |
1433 | S: BuildHasher, | |
6a06907d | 1434 | A: Allocator + Clone, |
48663c56 XL |
1435 | { |
1436 | fn eq(&self, other: &Self) -> bool { | |
1437 | if self.len() != other.len() { | |
1438 | return false; | |
1439 | } | |
1440 | ||
1441 | self.iter() | |
1442 | .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v)) | |
1443 | } | |
1444 | } | |
1445 | ||
6a06907d | 1446 | impl<K, V, S, A> Eq for HashMap<K, V, S, A> |
48663c56 XL |
1447 | where |
1448 | K: Eq + Hash, | |
1449 | V: Eq, | |
1450 | S: BuildHasher, | |
6a06907d | 1451 | A: Allocator + Clone, |
48663c56 XL |
1452 | { |
1453 | } | |
1454 | ||
6a06907d | 1455 | impl<K, V, S, A> Debug for HashMap<K, V, S, A> |
48663c56 XL |
1456 | where |
1457 | K: Debug, | |
1458 | V: Debug, | |
6a06907d | 1459 | A: Allocator + Clone, |
48663c56 XL |
1460 | { |
1461 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1462 | f.debug_map().entries(self.iter()).finish() | |
1463 | } | |
1464 | } | |
1465 | ||
6a06907d | 1466 | impl<K, V, S, A> Default for HashMap<K, V, S, A> |
48663c56 | 1467 | where |
3dfed10e | 1468 | S: Default, |
6a06907d | 1469 | A: Default + Allocator + Clone, |
48663c56 | 1470 | { |
6a06907d | 1471 | /// Creates an empty `HashMap<K, V, S, A>`, with the `Default` value for the hasher and allocator. |
e74abb32 | 1472 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 1473 | fn default() -> Self { |
6a06907d | 1474 | Self::with_hasher_in(Default::default(), Default::default()) |
48663c56 XL |
1475 | } |
1476 | } | |
1477 | ||
6a06907d | 1478 | impl<K, Q: ?Sized, V, S, A> Index<&Q> for HashMap<K, V, S, A> |
48663c56 XL |
1479 | where |
1480 | K: Eq + Hash + Borrow<Q>, | |
1481 | Q: Eq + Hash, | |
1482 | S: BuildHasher, | |
6a06907d | 1483 | A: Allocator + Clone, |
48663c56 XL |
1484 | { |
1485 | type Output = V; | |
1486 | ||
1487 | /// Returns a reference to the value corresponding to the supplied key. | |
1488 | /// | |
1489 | /// # Panics | |
1490 | /// | |
1491 | /// Panics if the key is not present in the `HashMap`. | |
e74abb32 | 1492 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1493 | fn index(&self, key: &Q) -> &V { |
1494 | self.get(key).expect("no entry found for key") | |
1495 | } | |
1496 | } | |
1497 | ||
1498 | /// An iterator over the entries of a `HashMap`. | |
1499 | /// | |
1500 | /// This `struct` is created by the [`iter`] method on [`HashMap`]. See its | |
1501 | /// documentation for more. | |
1502 | /// | |
1503 | /// [`iter`]: struct.HashMap.html#method.iter | |
1504 | /// [`HashMap`]: struct.HashMap.html | |
1505 | pub struct Iter<'a, K, V> { | |
1506 | inner: RawIter<(K, V)>, | |
1507 | marker: PhantomData<(&'a K, &'a V)>, | |
1508 | } | |
1509 | ||
1510 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` | |
1511 | impl<K, V> Clone for Iter<'_, K, V> { | |
e74abb32 | 1512 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1513 | fn clone(&self) -> Self { |
1514 | Iter { | |
1515 | inner: self.inner.clone(), | |
1516 | marker: PhantomData, | |
1517 | } | |
1518 | } | |
1519 | } | |
1520 | ||
1521 | impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> { | |
1522 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1523 | f.debug_list().entries(self.clone()).finish() | |
1524 | } | |
1525 | } | |
1526 | ||
1527 | /// A mutable iterator over the entries of a `HashMap`. | |
1528 | /// | |
1529 | /// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its | |
1530 | /// documentation for more. | |
1531 | /// | |
1532 | /// [`iter_mut`]: struct.HashMap.html#method.iter_mut | |
1533 | /// [`HashMap`]: struct.HashMap.html | |
1534 | pub struct IterMut<'a, K, V> { | |
1535 | inner: RawIter<(K, V)>, | |
1536 | // To ensure invariance with respect to V | |
1537 | marker: PhantomData<(&'a K, &'a mut V)>, | |
1538 | } | |
1539 | ||
1540 | // We override the default Send impl which has K: Sync instead of K: Send. Both | |
1541 | // are correct, but this one is more general since it allows keys which | |
1542 | // implement Send but not Sync. | |
1543 | unsafe impl<K: Send, V: Send> Send for IterMut<'_, K, V> {} | |
1544 | ||
1545 | impl<K, V> IterMut<'_, K, V> { | |
1546 | /// Returns a iterator of references over the remaining items. | |
e74abb32 | 1547 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1548 | pub(super) fn iter(&self) -> Iter<'_, K, V> { |
1549 | Iter { | |
1550 | inner: self.inner.clone(), | |
1551 | marker: PhantomData, | |
1552 | } | |
1553 | } | |
1554 | } | |
1555 | ||
1556 | /// An owning iterator over the entries of a `HashMap`. | |
1557 | /// | |
3dfed10e | 1558 | /// This `struct` is created by the [`into_iter`] method on [`HashMap`] |
48663c56 XL |
1559 | /// (provided by the `IntoIterator` trait). See its documentation for more. |
1560 | /// | |
1561 | /// [`into_iter`]: struct.HashMap.html#method.into_iter | |
1562 | /// [`HashMap`]: struct.HashMap.html | |
6a06907d XL |
1563 | pub struct IntoIter<K, V, A: Allocator + Clone = Global> { |
1564 | inner: RawIntoIter<(K, V), A>, | |
48663c56 XL |
1565 | } |
1566 | ||
6a06907d | 1567 | impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> { |
48663c56 | 1568 | /// Returns a iterator of references over the remaining items. |
e74abb32 | 1569 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1570 | pub(super) fn iter(&self) -> Iter<'_, K, V> { |
1571 | Iter { | |
1572 | inner: self.inner.iter(), | |
1573 | marker: PhantomData, | |
1574 | } | |
1575 | } | |
1576 | } | |
1577 | ||
1578 | /// An iterator over the keys of a `HashMap`. | |
1579 | /// | |
1580 | /// This `struct` is created by the [`keys`] method on [`HashMap`]. See its | |
1581 | /// documentation for more. | |
1582 | /// | |
1583 | /// [`keys`]: struct.HashMap.html#method.keys | |
1584 | /// [`HashMap`]: struct.HashMap.html | |
1585 | pub struct Keys<'a, K, V> { | |
1586 | inner: Iter<'a, K, V>, | |
1587 | } | |
1588 | ||
1589 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` | |
1590 | impl<K, V> Clone for Keys<'_, K, V> { | |
e74abb32 | 1591 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1592 | fn clone(&self) -> Self { |
1593 | Keys { | |
1594 | inner: self.inner.clone(), | |
1595 | } | |
1596 | } | |
1597 | } | |
1598 | ||
1599 | impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> { | |
1600 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1601 | f.debug_list().entries(self.clone()).finish() | |
1602 | } | |
1603 | } | |
1604 | ||
1605 | /// An iterator over the values of a `HashMap`. | |
1606 | /// | |
1607 | /// This `struct` is created by the [`values`] method on [`HashMap`]. See its | |
1608 | /// documentation for more. | |
1609 | /// | |
1610 | /// [`values`]: struct.HashMap.html#method.values | |
1611 | /// [`HashMap`]: struct.HashMap.html | |
1612 | pub struct Values<'a, K, V> { | |
1613 | inner: Iter<'a, K, V>, | |
1614 | } | |
1615 | ||
1616 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` | |
1617 | impl<K, V> Clone for Values<'_, K, V> { | |
e74abb32 | 1618 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1619 | fn clone(&self) -> Self { |
1620 | Values { | |
1621 | inner: self.inner.clone(), | |
1622 | } | |
1623 | } | |
1624 | } | |
1625 | ||
1626 | impl<K, V: Debug> fmt::Debug for Values<'_, K, V> { | |
1627 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1628 | f.debug_list().entries(self.clone()).finish() | |
1629 | } | |
1630 | } | |
1631 | ||
1632 | /// A draining iterator over the entries of a `HashMap`. | |
1633 | /// | |
1634 | /// This `struct` is created by the [`drain`] method on [`HashMap`]. See its | |
1635 | /// documentation for more. | |
1636 | /// | |
1637 | /// [`drain`]: struct.HashMap.html#method.drain | |
1638 | /// [`HashMap`]: struct.HashMap.html | |
6a06907d XL |
1639 | pub struct Drain<'a, K, V, A: Allocator + Clone = Global> { |
1640 | inner: RawDrain<'a, (K, V), A>, | |
48663c56 XL |
1641 | } |
1642 | ||
6a06907d | 1643 | impl<K, V, A: Allocator + Clone> Drain<'_, K, V, A> { |
48663c56 | 1644 | /// Returns a iterator of references over the remaining items. |
e74abb32 | 1645 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1646 | pub(super) fn iter(&self) -> Iter<'_, K, V> { |
1647 | Iter { | |
1648 | inner: self.inner.iter(), | |
1649 | marker: PhantomData, | |
1650 | } | |
1651 | } | |
1652 | } | |
1653 | ||
3dfed10e XL |
1654 | /// A draining iterator over entries of a `HashMap` which don't satisfy the predicate `f`. |
1655 | /// | |
1656 | /// This `struct` is created by the [`drain_filter`] method on [`HashMap`]. See its | |
1657 | /// documentation for more. | |
1658 | /// | |
1659 | /// [`drain_filter`]: struct.HashMap.html#method.drain_filter | |
1660 | /// [`HashMap`]: struct.HashMap.html | |
6a06907d | 1661 | pub struct DrainFilter<'a, K, V, F, A: Allocator + Clone = Global> |
3dfed10e XL |
1662 | where |
1663 | F: FnMut(&K, &mut V) -> bool, | |
1664 | { | |
1665 | f: F, | |
6a06907d | 1666 | inner: DrainFilterInner<'a, K, V, A>, |
3dfed10e XL |
1667 | } |
1668 | ||
6a06907d | 1669 | impl<'a, K, V, F, A> Drop for DrainFilter<'a, K, V, F, A> |
3dfed10e XL |
1670 | where |
1671 | F: FnMut(&K, &mut V) -> bool, | |
6a06907d | 1672 | A: Allocator + Clone, |
3dfed10e XL |
1673 | { |
1674 | #[cfg_attr(feature = "inline-more", inline)] | |
1675 | fn drop(&mut self) { | |
1676 | while let Some(item) = self.next() { | |
1677 | let guard = ConsumeAllOnDrop(self); | |
1678 | drop(item); | |
1679 | mem::forget(guard); | |
1680 | } | |
1681 | } | |
1682 | } | |
1683 | ||
1684 | pub(super) struct ConsumeAllOnDrop<'a, T: Iterator>(pub &'a mut T); | |
1685 | ||
1686 | impl<T: Iterator> Drop for ConsumeAllOnDrop<'_, T> { | |
1687 | #[cfg_attr(feature = "inline-more", inline)] | |
1688 | fn drop(&mut self) { | |
1689 | self.0.for_each(drop) | |
1690 | } | |
1691 | } | |
1692 | ||
6a06907d | 1693 | impl<K, V, F, A> Iterator for DrainFilter<'_, K, V, F, A> |
3dfed10e XL |
1694 | where |
1695 | F: FnMut(&K, &mut V) -> bool, | |
6a06907d | 1696 | A: Allocator + Clone, |
3dfed10e XL |
1697 | { |
1698 | type Item = (K, V); | |
1699 | ||
1700 | #[cfg_attr(feature = "inline-more", inline)] | |
1701 | fn next(&mut self) -> Option<Self::Item> { | |
1702 | self.inner.next(&mut self.f) | |
1703 | } | |
1b1a35ee XL |
1704 | |
1705 | #[inline] | |
1706 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1707 | (0, self.inner.iter.size_hint().1) | |
1708 | } | |
3dfed10e XL |
1709 | } |
1710 | ||
1b1a35ee XL |
1711 | impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {} |
1712 | ||
3dfed10e | 1713 | /// Portions of `DrainFilter` shared with `set::DrainFilter` |
6a06907d | 1714 | pub(super) struct DrainFilterInner<'a, K, V, A: Allocator + Clone> { |
3dfed10e | 1715 | pub iter: RawIter<(K, V)>, |
6a06907d | 1716 | pub table: &'a mut RawTable<(K, V), A>, |
3dfed10e XL |
1717 | } |
1718 | ||
6a06907d | 1719 | impl<K, V, A: Allocator + Clone> DrainFilterInner<'_, K, V, A> { |
3dfed10e XL |
1720 | #[cfg_attr(feature = "inline-more", inline)] |
1721 | pub(super) fn next<F>(&mut self, f: &mut F) -> Option<(K, V)> | |
1722 | where | |
1723 | F: FnMut(&K, &mut V) -> bool, | |
1724 | { | |
1725 | unsafe { | |
1726 | while let Some(item) = self.iter.next() { | |
1727 | let &mut (ref key, ref mut value) = item.as_mut(); | |
1b1a35ee | 1728 | if f(key, value) { |
3dfed10e XL |
1729 | return Some(self.table.remove(item)); |
1730 | } | |
1731 | } | |
1732 | } | |
1733 | None | |
1734 | } | |
1735 | } | |
1736 | ||
48663c56 XL |
1737 | /// A mutable iterator over the values of a `HashMap`. |
1738 | /// | |
1739 | /// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its | |
1740 | /// documentation for more. | |
1741 | /// | |
1742 | /// [`values_mut`]: struct.HashMap.html#method.values_mut | |
1743 | /// [`HashMap`]: struct.HashMap.html | |
1744 | pub struct ValuesMut<'a, K, V> { | |
1745 | inner: IterMut<'a, K, V>, | |
1746 | } | |
1747 | ||
1748 | /// A builder for computing where in a [`HashMap`] a key-value pair would be stored. | |
1749 | /// | |
1750 | /// See the [`HashMap::raw_entry_mut`] docs for usage examples. | |
1751 | /// | |
1752 | /// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut | |
6a06907d XL |
1753 | pub struct RawEntryBuilderMut<'a, K, V, S, A: Allocator + Clone = Global> { |
1754 | map: &'a mut HashMap<K, V, S, A>, | |
48663c56 XL |
1755 | } |
1756 | ||
1757 | /// A view into a single entry in a map, which may either be vacant or occupied. | |
1758 | /// | |
1759 | /// This is a lower-level version of [`Entry`]. | |
1760 | /// | |
e74abb32 XL |
1761 | /// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`], |
1762 | /// then calling one of the methods of that [`RawEntryBuilderMut`]. | |
48663c56 XL |
1763 | /// |
1764 | /// [`HashMap`]: struct.HashMap.html | |
1765 | /// [`Entry`]: enum.Entry.html | |
e74abb32 XL |
1766 | /// [`raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut |
1767 | /// [`RawEntryBuilderMut`]: struct.RawEntryBuilderMut.html | |
6a06907d | 1768 | pub enum RawEntryMut<'a, K, V, S, A: Allocator + Clone = Global> { |
48663c56 | 1769 | /// An occupied entry. |
6a06907d | 1770 | Occupied(RawOccupiedEntryMut<'a, K, V, S, A>), |
48663c56 | 1771 | /// A vacant entry. |
6a06907d | 1772 | Vacant(RawVacantEntryMut<'a, K, V, S, A>), |
48663c56 XL |
1773 | } |
1774 | ||
1775 | /// A view into an occupied entry in a `HashMap`. | |
1776 | /// It is part of the [`RawEntryMut`] enum. | |
1777 | /// | |
1778 | /// [`RawEntryMut`]: enum.RawEntryMut.html | |
6a06907d | 1779 | pub struct RawOccupiedEntryMut<'a, K, V, S, A: Allocator + Clone = Global> { |
48663c56 | 1780 | elem: Bucket<(K, V)>, |
6a06907d | 1781 | table: &'a mut RawTable<(K, V), A>, |
1b1a35ee | 1782 | hash_builder: &'a S, |
48663c56 XL |
1783 | } |
1784 | ||
6a06907d | 1785 | unsafe impl<K, V, S, A> Send for RawOccupiedEntryMut<'_, K, V, S, A> |
e74abb32 XL |
1786 | where |
1787 | K: Send, | |
1788 | V: Send, | |
6a06907d | 1789 | A: Send + Allocator + Clone, |
e74abb32 XL |
1790 | { |
1791 | } | |
6a06907d | 1792 | unsafe impl<K, V, S, A> Sync for RawOccupiedEntryMut<'_, K, V, S, A> |
e74abb32 XL |
1793 | where |
1794 | K: Sync, | |
1795 | V: Sync, | |
6a06907d | 1796 | A: Send + Allocator + Clone, |
e74abb32 XL |
1797 | { |
1798 | } | |
1799 | ||
48663c56 XL |
1800 | /// A view into a vacant entry in a `HashMap`. |
1801 | /// It is part of the [`RawEntryMut`] enum. | |
1802 | /// | |
1803 | /// [`RawEntryMut`]: enum.RawEntryMut.html | |
6a06907d XL |
1804 | pub struct RawVacantEntryMut<'a, K, V, S, A: Allocator + Clone = Global> { |
1805 | table: &'a mut RawTable<(K, V), A>, | |
48663c56 XL |
1806 | hash_builder: &'a S, |
1807 | } | |
1808 | ||
1809 | /// A builder for computing where in a [`HashMap`] a key-value pair would be stored. | |
1810 | /// | |
1811 | /// See the [`HashMap::raw_entry`] docs for usage examples. | |
1812 | /// | |
1813 | /// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry | |
6a06907d XL |
1814 | pub struct RawEntryBuilder<'a, K, V, S, A: Allocator + Clone = Global> { |
1815 | map: &'a HashMap<K, V, S, A>, | |
48663c56 XL |
1816 | } |
1817 | ||
6a06907d | 1818 | impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> { |
48663c56 | 1819 | /// Creates a `RawEntryMut` from the given key. |
e74abb32 | 1820 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 1821 | #[allow(clippy::wrong_self_convention)] |
6a06907d | 1822 | pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S, A> |
48663c56 | 1823 | where |
3dfed10e | 1824 | S: BuildHasher, |
48663c56 XL |
1825 | K: Borrow<Q>, |
1826 | Q: Hash + Eq, | |
1827 | { | |
6a06907d XL |
1828 | let hash = make_hash::<K, Q, S>(&self.map.hash_builder, k); |
1829 | self.from_key_hashed_nocheck(hash, k) | |
48663c56 XL |
1830 | } |
1831 | ||
1832 | /// Creates a `RawEntryMut` from the given key and its hash. | |
1833 | #[inline] | |
1834 | #[allow(clippy::wrong_self_convention)] | |
6a06907d | 1835 | pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S, A> |
48663c56 XL |
1836 | where |
1837 | K: Borrow<Q>, | |
1838 | Q: Eq, | |
1839 | { | |
6a06907d | 1840 | self.from_hash(hash, equivalent(k)) |
48663c56 XL |
1841 | } |
1842 | } | |
1843 | ||
6a06907d | 1844 | impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> { |
48663c56 | 1845 | /// Creates a `RawEntryMut` from the given hash. |
e74abb32 | 1846 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 1847 | #[allow(clippy::wrong_self_convention)] |
6a06907d | 1848 | pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S, A> |
48663c56 XL |
1849 | where |
1850 | for<'b> F: FnMut(&'b K) -> bool, | |
1851 | { | |
1852 | self.search(hash, is_match) | |
1853 | } | |
1854 | ||
e74abb32 | 1855 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d | 1856 | fn search<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S, A> |
48663c56 XL |
1857 | where |
1858 | for<'b> F: FnMut(&'b K) -> bool, | |
1859 | { | |
1860 | match self.map.table.find(hash, |(k, _)| is_match(k)) { | |
1861 | Some(elem) => RawEntryMut::Occupied(RawOccupiedEntryMut { | |
1862 | elem, | |
1863 | table: &mut self.map.table, | |
1b1a35ee | 1864 | hash_builder: &self.map.hash_builder, |
48663c56 XL |
1865 | }), |
1866 | None => RawEntryMut::Vacant(RawVacantEntryMut { | |
1867 | table: &mut self.map.table, | |
1868 | hash_builder: &self.map.hash_builder, | |
1869 | }), | |
1870 | } | |
1871 | } | |
1872 | } | |
1873 | ||
6a06907d | 1874 | impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> { |
48663c56 | 1875 | /// Access an entry by key. |
e74abb32 | 1876 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1877 | #[allow(clippy::wrong_self_convention)] |
1878 | pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)> | |
1879 | where | |
3dfed10e | 1880 | S: BuildHasher, |
48663c56 XL |
1881 | K: Borrow<Q>, |
1882 | Q: Hash + Eq, | |
1883 | { | |
6a06907d XL |
1884 | let hash = make_hash::<K, Q, S>(&self.map.hash_builder, k); |
1885 | self.from_key_hashed_nocheck(hash, k) | |
48663c56 XL |
1886 | } |
1887 | ||
1888 | /// Access an entry by a key and its hash. | |
e74abb32 | 1889 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1890 | #[allow(clippy::wrong_self_convention)] |
1891 | pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)> | |
1892 | where | |
1893 | K: Borrow<Q>, | |
29967ef6 | 1894 | Q: Eq, |
48663c56 | 1895 | { |
6a06907d | 1896 | self.from_hash(hash, equivalent(k)) |
48663c56 XL |
1897 | } |
1898 | ||
e74abb32 | 1899 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1900 | fn search<F>(self, hash: u64, mut is_match: F) -> Option<(&'a K, &'a V)> |
1901 | where | |
1902 | F: FnMut(&K) -> bool, | |
1903 | { | |
29967ef6 XL |
1904 | match self.map.table.get(hash, |(k, _)| is_match(k)) { |
1905 | Some(&(ref key, ref value)) => Some((key, value)), | |
3dfed10e XL |
1906 | None => None, |
1907 | } | |
48663c56 XL |
1908 | } |
1909 | ||
1910 | /// Access an entry by hash. | |
e74abb32 | 1911 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1912 | #[allow(clippy::wrong_self_convention)] |
1913 | pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)> | |
1914 | where | |
1915 | F: FnMut(&K) -> bool, | |
1916 | { | |
1917 | self.search(hash, is_match) | |
1918 | } | |
1919 | } | |
1920 | ||
6a06907d | 1921 | impl<'a, K, V, S, A: Allocator + Clone> RawEntryMut<'a, K, V, S, A> { |
e74abb32 XL |
1922 | /// Sets the value of the entry, and returns a RawOccupiedEntryMut. |
1923 | /// | |
1924 | /// # Examples | |
1925 | /// | |
1926 | /// ``` | |
1927 | /// use hashbrown::HashMap; | |
1928 | /// | |
1929 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
1930 | /// let entry = map.raw_entry_mut().from_key("horseyland").insert("horseyland", 37); | |
1931 | /// | |
1932 | /// assert_eq!(entry.remove_entry(), ("horseyland", 37)); | |
1933 | /// ``` | |
1934 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 1935 | pub fn insert(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A> |
e74abb32 XL |
1936 | where |
1937 | K: Hash, | |
1938 | S: BuildHasher, | |
1939 | { | |
1940 | match self { | |
1941 | RawEntryMut::Occupied(mut entry) => { | |
1942 | entry.insert(value); | |
1943 | entry | |
1944 | } | |
1945 | RawEntryMut::Vacant(entry) => entry.insert_entry(key, value), | |
1946 | } | |
1947 | } | |
1948 | ||
48663c56 XL |
1949 | /// Ensures a value is in the entry by inserting the default if empty, and returns |
1950 | /// mutable references to the key and value in the entry. | |
1951 | /// | |
1952 | /// # Examples | |
1953 | /// | |
1954 | /// ``` | |
1955 | /// use hashbrown::HashMap; | |
1956 | /// | |
1957 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
1958 | /// | |
1959 | /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3); | |
1960 | /// assert_eq!(map["poneyland"], 3); | |
1961 | /// | |
1962 | /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2; | |
1963 | /// assert_eq!(map["poneyland"], 6); | |
1964 | /// ``` | |
e74abb32 | 1965 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1966 | pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V) |
1967 | where | |
1968 | K: Hash, | |
1969 | S: BuildHasher, | |
1970 | { | |
1971 | match self { | |
1972 | RawEntryMut::Occupied(entry) => entry.into_key_value(), | |
1973 | RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val), | |
1974 | } | |
1975 | } | |
1976 | ||
1977 | /// Ensures a value is in the entry by inserting the result of the default function if empty, | |
1978 | /// and returns mutable references to the key and value in the entry. | |
1979 | /// | |
1980 | /// # Examples | |
1981 | /// | |
1982 | /// ``` | |
1983 | /// use hashbrown::HashMap; | |
1984 | /// | |
1985 | /// let mut map: HashMap<&str, String> = HashMap::new(); | |
1986 | /// | |
1987 | /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| { | |
1988 | /// ("poneyland", "hoho".to_string()) | |
1989 | /// }); | |
1990 | /// | |
1991 | /// assert_eq!(map["poneyland"], "hoho".to_string()); | |
1992 | /// ``` | |
e74abb32 | 1993 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
1994 | pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V) |
1995 | where | |
1996 | F: FnOnce() -> (K, V), | |
1997 | K: Hash, | |
1998 | S: BuildHasher, | |
1999 | { | |
2000 | match self { | |
2001 | RawEntryMut::Occupied(entry) => entry.into_key_value(), | |
2002 | RawEntryMut::Vacant(entry) => { | |
2003 | let (k, v) = default(); | |
2004 | entry.insert(k, v) | |
2005 | } | |
2006 | } | |
2007 | } | |
2008 | ||
2009 | /// Provides in-place mutable access to an occupied entry before any | |
2010 | /// potential inserts into the map. | |
2011 | /// | |
2012 | /// # Examples | |
2013 | /// | |
2014 | /// ``` | |
2015 | /// use hashbrown::HashMap; | |
2016 | /// | |
2017 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2018 | /// | |
2019 | /// map.raw_entry_mut() | |
2020 | /// .from_key("poneyland") | |
2021 | /// .and_modify(|_k, v| { *v += 1 }) | |
2022 | /// .or_insert("poneyland", 42); | |
2023 | /// assert_eq!(map["poneyland"], 42); | |
2024 | /// | |
2025 | /// map.raw_entry_mut() | |
2026 | /// .from_key("poneyland") | |
2027 | /// .and_modify(|_k, v| { *v += 1 }) | |
2028 | /// .or_insert("poneyland", 0); | |
2029 | /// assert_eq!(map["poneyland"], 43); | |
2030 | /// ``` | |
e74abb32 | 2031 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2032 | pub fn and_modify<F>(self, f: F) -> Self |
2033 | where | |
2034 | F: FnOnce(&mut K, &mut V), | |
2035 | { | |
2036 | match self { | |
2037 | RawEntryMut::Occupied(mut entry) => { | |
2038 | { | |
2039 | let (k, v) = entry.get_key_value_mut(); | |
2040 | f(k, v); | |
2041 | } | |
2042 | RawEntryMut::Occupied(entry) | |
2043 | } | |
2044 | RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry), | |
2045 | } | |
2046 | } | |
1b1a35ee XL |
2047 | |
2048 | /// Provides shared access to the key and owned access to the value of | |
2049 | /// an occupied entry and allows to replace or remove it based on the | |
2050 | /// value of the returned option. | |
2051 | /// | |
2052 | /// # Examples | |
2053 | /// | |
2054 | /// ``` | |
2055 | /// use hashbrown::HashMap; | |
2056 | /// use hashbrown::hash_map::RawEntryMut; | |
2057 | /// | |
2058 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2059 | /// | |
2060 | /// let entry = map | |
2061 | /// .raw_entry_mut() | |
2062 | /// .from_key("poneyland") | |
2063 | /// .and_replace_entry_with(|_k, _v| panic!()); | |
2064 | /// | |
2065 | /// match entry { | |
2066 | /// RawEntryMut::Vacant(_) => {}, | |
2067 | /// RawEntryMut::Occupied(_) => panic!(), | |
2068 | /// } | |
2069 | /// | |
2070 | /// map.insert("poneyland", 42); | |
2071 | /// | |
2072 | /// let entry = map | |
2073 | /// .raw_entry_mut() | |
2074 | /// .from_key("poneyland") | |
2075 | /// .and_replace_entry_with(|k, v| { | |
2076 | /// assert_eq!(k, &"poneyland"); | |
2077 | /// assert_eq!(v, 42); | |
2078 | /// Some(v + 1) | |
2079 | /// }); | |
2080 | /// | |
2081 | /// match entry { | |
2082 | /// RawEntryMut::Occupied(e) => { | |
2083 | /// assert_eq!(e.key(), &"poneyland"); | |
2084 | /// assert_eq!(e.get(), &43); | |
2085 | /// }, | |
2086 | /// RawEntryMut::Vacant(_) => panic!(), | |
2087 | /// } | |
2088 | /// | |
2089 | /// assert_eq!(map["poneyland"], 43); | |
2090 | /// | |
2091 | /// let entry = map | |
2092 | /// .raw_entry_mut() | |
2093 | /// .from_key("poneyland") | |
2094 | /// .and_replace_entry_with(|_k, _v| None); | |
2095 | /// | |
2096 | /// match entry { | |
2097 | /// RawEntryMut::Vacant(_) => {}, | |
2098 | /// RawEntryMut::Occupied(_) => panic!(), | |
2099 | /// } | |
2100 | /// | |
2101 | /// assert!(!map.contains_key("poneyland")); | |
2102 | /// ``` | |
2103 | #[cfg_attr(feature = "inline-more", inline)] | |
2104 | pub fn and_replace_entry_with<F>(self, f: F) -> Self | |
2105 | where | |
2106 | F: FnOnce(&K, V) -> Option<V>, | |
2107 | { | |
2108 | match self { | |
2109 | RawEntryMut::Occupied(entry) => entry.replace_entry_with(f), | |
2110 | RawEntryMut::Vacant(_) => self, | |
2111 | } | |
2112 | } | |
48663c56 XL |
2113 | } |
2114 | ||
6a06907d | 2115 | impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { |
48663c56 | 2116 | /// Gets a reference to the key in the entry. |
e74abb32 | 2117 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2118 | pub fn key(&self) -> &K { |
2119 | unsafe { &self.elem.as_ref().0 } | |
2120 | } | |
2121 | ||
2122 | /// Gets a mutable reference to the key in the entry. | |
e74abb32 | 2123 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2124 | pub fn key_mut(&mut self) -> &mut K { |
2125 | unsafe { &mut self.elem.as_mut().0 } | |
2126 | } | |
2127 | ||
2128 | /// Converts the entry into a mutable reference to the key in the entry | |
2129 | /// with a lifetime bound to the map itself. | |
e74abb32 | 2130 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2131 | pub fn into_key(self) -> &'a mut K { |
2132 | unsafe { &mut self.elem.as_mut().0 } | |
2133 | } | |
2134 | ||
2135 | /// Gets a reference to the value in the entry. | |
e74abb32 | 2136 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2137 | pub fn get(&self) -> &V { |
2138 | unsafe { &self.elem.as_ref().1 } | |
2139 | } | |
2140 | ||
2141 | /// Converts the OccupiedEntry into a mutable reference to the value in the entry | |
2142 | /// with a lifetime bound to the map itself. | |
e74abb32 | 2143 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2144 | pub fn into_mut(self) -> &'a mut V { |
2145 | unsafe { &mut self.elem.as_mut().1 } | |
2146 | } | |
2147 | ||
2148 | /// Gets a mutable reference to the value in the entry. | |
e74abb32 | 2149 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2150 | pub fn get_mut(&mut self) -> &mut V { |
2151 | unsafe { &mut self.elem.as_mut().1 } | |
2152 | } | |
2153 | ||
2154 | /// Gets a reference to the key and value in the entry. | |
e74abb32 | 2155 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2156 | pub fn get_key_value(&mut self) -> (&K, &V) { |
2157 | unsafe { | |
2158 | let &(ref key, ref value) = self.elem.as_ref(); | |
2159 | (key, value) | |
2160 | } | |
2161 | } | |
2162 | ||
2163 | /// Gets a mutable reference to the key and value in the entry. | |
e74abb32 | 2164 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2165 | pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) { |
2166 | unsafe { | |
2167 | let &mut (ref mut key, ref mut value) = self.elem.as_mut(); | |
2168 | (key, value) | |
2169 | } | |
2170 | } | |
2171 | ||
2172 | /// Converts the OccupiedEntry into a mutable reference to the key and value in the entry | |
2173 | /// with a lifetime bound to the map itself. | |
e74abb32 | 2174 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2175 | pub fn into_key_value(self) -> (&'a mut K, &'a mut V) { |
2176 | unsafe { | |
2177 | let &mut (ref mut key, ref mut value) = self.elem.as_mut(); | |
2178 | (key, value) | |
2179 | } | |
2180 | } | |
2181 | ||
2182 | /// Sets the value of the entry, and returns the entry's old value. | |
e74abb32 | 2183 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2184 | pub fn insert(&mut self, value: V) -> V { |
2185 | mem::replace(self.get_mut(), value) | |
2186 | } | |
2187 | ||
2188 | /// Sets the value of the entry, and returns the entry's old value. | |
e74abb32 | 2189 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2190 | pub fn insert_key(&mut self, key: K) -> K { |
2191 | mem::replace(self.key_mut(), key) | |
2192 | } | |
2193 | ||
2194 | /// Takes the value out of the entry, and returns it. | |
e74abb32 | 2195 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2196 | pub fn remove(self) -> V { |
2197 | self.remove_entry().1 | |
2198 | } | |
2199 | ||
2200 | /// Take the ownership of the key and value from the map. | |
e74abb32 | 2201 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 2202 | pub fn remove_entry(self) -> (K, V) { |
3dfed10e | 2203 | unsafe { self.table.remove(self.elem) } |
48663c56 | 2204 | } |
1b1a35ee XL |
2205 | |
2206 | /// Provides shared access to the key and owned access to the value of | |
2207 | /// the entry and allows to replace or remove it based on the | |
2208 | /// value of the returned option. | |
2209 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 2210 | pub fn replace_entry_with<F>(self, f: F) -> RawEntryMut<'a, K, V, S, A> |
1b1a35ee XL |
2211 | where |
2212 | F: FnOnce(&K, V) -> Option<V>, | |
2213 | { | |
2214 | unsafe { | |
2215 | let still_occupied = self | |
2216 | .table | |
2217 | .replace_bucket_with(self.elem.clone(), |(key, value)| { | |
2218 | f(&key, value).map(|new_value| (key, new_value)) | |
2219 | }); | |
2220 | ||
2221 | if still_occupied { | |
2222 | RawEntryMut::Occupied(self) | |
2223 | } else { | |
2224 | RawEntryMut::Vacant(RawVacantEntryMut { | |
2225 | table: self.table, | |
2226 | hash_builder: self.hash_builder, | |
2227 | }) | |
2228 | } | |
2229 | } | |
2230 | } | |
48663c56 XL |
2231 | } |
2232 | ||
6a06907d | 2233 | impl<'a, K, V, S, A: Allocator + Clone> RawVacantEntryMut<'a, K, V, S, A> { |
48663c56 XL |
2234 | /// Sets the value of the entry with the VacantEntry's key, |
2235 | /// and returns a mutable reference to it. | |
e74abb32 | 2236 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2237 | pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V) |
2238 | where | |
2239 | K: Hash, | |
2240 | S: BuildHasher, | |
2241 | { | |
6a06907d XL |
2242 | let hash = make_insert_hash::<K, S>(self.hash_builder, &key); |
2243 | self.insert_hashed_nocheck(hash, key, value) | |
48663c56 XL |
2244 | } |
2245 | ||
2246 | /// Sets the value of the entry with the VacantEntry's key, | |
2247 | /// and returns a mutable reference to it. | |
e74abb32 | 2248 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2249 | #[allow(clippy::shadow_unrelated)] |
2250 | pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) | |
2251 | where | |
2252 | K: Hash, | |
2253 | S: BuildHasher, | |
2254 | { | |
6a06907d XL |
2255 | let &mut (ref mut k, ref mut v) = self.table.insert_entry( |
2256 | hash, | |
2257 | (key, value), | |
2258 | make_hasher::<K, _, V, S>(self.hash_builder), | |
2259 | ); | |
2260 | (k, v) | |
48663c56 XL |
2261 | } |
2262 | ||
2263 | /// Set the value of an entry with a custom hasher function. | |
e74abb32 | 2264 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2265 | pub fn insert_with_hasher<H>( |
2266 | self, | |
2267 | hash: u64, | |
2268 | key: K, | |
2269 | value: V, | |
2270 | hasher: H, | |
2271 | ) -> (&'a mut K, &'a mut V) | |
2272 | where | |
48663c56 XL |
2273 | H: Fn(&K) -> u64, |
2274 | { | |
29967ef6 XL |
2275 | let &mut (ref mut k, ref mut v) = self |
2276 | .table | |
2277 | .insert_entry(hash, (key, value), |x| hasher(&x.0)); | |
2278 | (k, v) | |
48663c56 | 2279 | } |
e74abb32 XL |
2280 | |
2281 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 2282 | fn insert_entry(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A> |
e74abb32 XL |
2283 | where |
2284 | K: Hash, | |
2285 | S: BuildHasher, | |
2286 | { | |
6a06907d XL |
2287 | let hash = make_insert_hash::<K, S>(self.hash_builder, &key); |
2288 | let elem = self.table.insert( | |
2289 | hash, | |
2290 | (key, value), | |
2291 | make_hasher::<K, _, V, S>(self.hash_builder), | |
2292 | ); | |
e74abb32 XL |
2293 | RawOccupiedEntryMut { |
2294 | elem, | |
2295 | table: self.table, | |
1b1a35ee | 2296 | hash_builder: self.hash_builder, |
e74abb32 XL |
2297 | } |
2298 | } | |
48663c56 XL |
2299 | } |
2300 | ||
6a06907d | 2301 | impl<K, V, S, A: Allocator + Clone> Debug for RawEntryBuilderMut<'_, K, V, S, A> { |
48663c56 XL |
2302 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2303 | f.debug_struct("RawEntryBuilder").finish() | |
2304 | } | |
2305 | } | |
2306 | ||
6a06907d | 2307 | impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for RawEntryMut<'_, K, V, S, A> { |
48663c56 XL |
2308 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2309 | match *self { | |
2310 | RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(), | |
2311 | RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(), | |
2312 | } | |
2313 | } | |
2314 | } | |
2315 | ||
6a06907d | 2316 | impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for RawOccupiedEntryMut<'_, K, V, S, A> { |
48663c56 XL |
2317 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2318 | f.debug_struct("RawOccupiedEntryMut") | |
2319 | .field("key", self.key()) | |
2320 | .field("value", self.get()) | |
2321 | .finish() | |
2322 | } | |
2323 | } | |
2324 | ||
6a06907d | 2325 | impl<K, V, S, A: Allocator + Clone> Debug for RawVacantEntryMut<'_, K, V, S, A> { |
48663c56 XL |
2326 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2327 | f.debug_struct("RawVacantEntryMut").finish() | |
2328 | } | |
2329 | } | |
2330 | ||
6a06907d | 2331 | impl<K, V, S, A: Allocator + Clone> Debug for RawEntryBuilder<'_, K, V, S, A> { |
48663c56 XL |
2332 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2333 | f.debug_struct("RawEntryBuilder").finish() | |
2334 | } | |
2335 | } | |
2336 | ||
2337 | /// A view into a single entry in a map, which may either be vacant or occupied. | |
2338 | /// | |
2339 | /// This `enum` is constructed from the [`entry`] method on [`HashMap`]. | |
2340 | /// | |
2341 | /// [`HashMap`]: struct.HashMap.html | |
2342 | /// [`entry`]: struct.HashMap.html#method.entry | |
6a06907d XL |
2343 | pub enum Entry<'a, K, V, S, A = Global> |
2344 | where | |
2345 | A: Allocator + Clone, | |
2346 | { | |
48663c56 | 2347 | /// An occupied entry. |
6a06907d | 2348 | Occupied(OccupiedEntry<'a, K, V, S, A>), |
48663c56 XL |
2349 | |
2350 | /// A vacant entry. | |
6a06907d | 2351 | Vacant(VacantEntry<'a, K, V, S, A>), |
48663c56 XL |
2352 | } |
2353 | ||
6a06907d | 2354 | impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for Entry<'_, K, V, S, A> { |
48663c56 XL |
2355 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2356 | match *self { | |
2357 | Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), | |
2358 | Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(), | |
2359 | } | |
2360 | } | |
2361 | } | |
2362 | ||
2363 | /// A view into an occupied entry in a `HashMap`. | |
2364 | /// It is part of the [`Entry`] enum. | |
2365 | /// | |
2366 | /// [`Entry`]: enum.Entry.html | |
6a06907d | 2367 | pub struct OccupiedEntry<'a, K, V, S, A: Allocator + Clone = Global> { |
1b1a35ee | 2368 | hash: u64, |
48663c56 XL |
2369 | key: Option<K>, |
2370 | elem: Bucket<(K, V)>, | |
6a06907d | 2371 | table: &'a mut HashMap<K, V, S, A>, |
48663c56 XL |
2372 | } |
2373 | ||
6a06907d | 2374 | unsafe impl<K, V, S, A> Send for OccupiedEntry<'_, K, V, S, A> |
48663c56 XL |
2375 | where |
2376 | K: Send, | |
2377 | V: Send, | |
2378 | S: Send, | |
6a06907d | 2379 | A: Send + Allocator + Clone, |
48663c56 XL |
2380 | { |
2381 | } | |
6a06907d | 2382 | unsafe impl<K, V, S, A> Sync for OccupiedEntry<'_, K, V, S, A> |
48663c56 XL |
2383 | where |
2384 | K: Sync, | |
2385 | V: Sync, | |
2386 | S: Sync, | |
6a06907d | 2387 | A: Sync + Allocator + Clone, |
48663c56 XL |
2388 | { |
2389 | } | |
2390 | ||
6a06907d | 2391 | impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for OccupiedEntry<'_, K, V, S, A> { |
48663c56 XL |
2392 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2393 | f.debug_struct("OccupiedEntry") | |
2394 | .field("key", self.key()) | |
2395 | .field("value", self.get()) | |
2396 | .finish() | |
2397 | } | |
2398 | } | |
2399 | ||
2400 | /// A view into a vacant entry in a `HashMap`. | |
2401 | /// It is part of the [`Entry`] enum. | |
2402 | /// | |
2403 | /// [`Entry`]: enum.Entry.html | |
6a06907d | 2404 | pub struct VacantEntry<'a, K, V, S, A: Allocator + Clone = Global> { |
48663c56 XL |
2405 | hash: u64, |
2406 | key: K, | |
6a06907d | 2407 | table: &'a mut HashMap<K, V, S, A>, |
48663c56 XL |
2408 | } |
2409 | ||
6a06907d | 2410 | impl<K: Debug, V, S, A: Allocator + Clone> Debug for VacantEntry<'_, K, V, S, A> { |
48663c56 XL |
2411 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2412 | f.debug_tuple("VacantEntry").field(self.key()).finish() | |
2413 | } | |
2414 | } | |
2415 | ||
6a06907d XL |
2416 | /// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists. |
2417 | /// | |
2418 | /// Contains the occupied entry, and the value that was not inserted. | |
2419 | pub struct OccupiedError<'a, K, V, S, A: Allocator + Clone = Global> { | |
2420 | /// The entry in the map that was already occupied. | |
2421 | pub entry: OccupiedEntry<'a, K, V, S, A>, | |
2422 | /// The value which was not inserted, because the entry was already occupied. | |
2423 | pub value: V, | |
2424 | } | |
2425 | ||
2426 | impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for OccupiedError<'_, K, V, S, A> { | |
2427 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2428 | f.debug_struct("OccupiedError") | |
2429 | .field("key", self.entry.key()) | |
2430 | .field("old_value", self.entry.get()) | |
2431 | .field("new_value", &self.value) | |
2432 | .finish() | |
2433 | } | |
2434 | } | |
2435 | ||
2436 | impl<'a, K: Debug, V: Debug, S, A: Allocator + Clone> fmt::Display | |
2437 | for OccupiedError<'a, K, V, S, A> | |
2438 | { | |
2439 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2440 | write!( | |
2441 | f, | |
2442 | "failed to insert {:?}, key {:?} already exists with value {:?}", | |
2443 | self.value, | |
2444 | self.entry.key(), | |
2445 | self.entry.get(), | |
2446 | ) | |
2447 | } | |
2448 | } | |
2449 | ||
2450 | impl<'a, K, V, S, A: Allocator + Clone> IntoIterator for &'a HashMap<K, V, S, A> { | |
48663c56 XL |
2451 | type Item = (&'a K, &'a V); |
2452 | type IntoIter = Iter<'a, K, V>; | |
2453 | ||
e74abb32 | 2454 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2455 | fn into_iter(self) -> Iter<'a, K, V> { |
2456 | self.iter() | |
2457 | } | |
2458 | } | |
2459 | ||
6a06907d | 2460 | impl<'a, K, V, S, A: Allocator + Clone> IntoIterator for &'a mut HashMap<K, V, S, A> { |
48663c56 XL |
2461 | type Item = (&'a K, &'a mut V); |
2462 | type IntoIter = IterMut<'a, K, V>; | |
2463 | ||
e74abb32 | 2464 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2465 | fn into_iter(self) -> IterMut<'a, K, V> { |
2466 | self.iter_mut() | |
2467 | } | |
2468 | } | |
2469 | ||
6a06907d | 2470 | impl<K, V, S, A: Allocator + Clone> IntoIterator for HashMap<K, V, S, A> { |
48663c56 | 2471 | type Item = (K, V); |
6a06907d | 2472 | type IntoIter = IntoIter<K, V, A>; |
48663c56 XL |
2473 | |
2474 | /// Creates a consuming iterator, that is, one that moves each key-value | |
2475 | /// pair out of the map in arbitrary order. The map cannot be used after | |
2476 | /// calling this. | |
2477 | /// | |
2478 | /// # Examples | |
2479 | /// | |
2480 | /// ``` | |
2481 | /// use hashbrown::HashMap; | |
2482 | /// | |
2483 | /// let mut map = HashMap::new(); | |
2484 | /// map.insert("a", 1); | |
2485 | /// map.insert("b", 2); | |
2486 | /// map.insert("c", 3); | |
2487 | /// | |
2488 | /// // Not possible with .iter() | |
2489 | /// let vec: Vec<(&str, i32)> = map.into_iter().collect(); | |
2490 | /// ``` | |
e74abb32 | 2491 | #[cfg_attr(feature = "inline-more", inline)] |
6a06907d | 2492 | fn into_iter(self) -> IntoIter<K, V, A> { |
48663c56 XL |
2493 | IntoIter { |
2494 | inner: self.table.into_iter(), | |
2495 | } | |
2496 | } | |
2497 | } | |
2498 | ||
2499 | impl<'a, K, V> Iterator for Iter<'a, K, V> { | |
2500 | type Item = (&'a K, &'a V); | |
2501 | ||
e74abb32 | 2502 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 2503 | fn next(&mut self) -> Option<(&'a K, &'a V)> { |
3dfed10e XL |
2504 | // Avoid `Option::map` because it bloats LLVM IR. |
2505 | match self.inner.next() { | |
2506 | Some(x) => unsafe { | |
2507 | let r = x.as_ref(); | |
2508 | Some((&r.0, &r.1)) | |
1b1a35ee | 2509 | }, |
3dfed10e XL |
2510 | None => None, |
2511 | } | |
48663c56 | 2512 | } |
e74abb32 | 2513 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2514 | fn size_hint(&self) -> (usize, Option<usize>) { |
2515 | self.inner.size_hint() | |
2516 | } | |
2517 | } | |
2518 | impl<K, V> ExactSizeIterator for Iter<'_, K, V> { | |
e74abb32 | 2519 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2520 | fn len(&self) -> usize { |
2521 | self.inner.len() | |
2522 | } | |
2523 | } | |
2524 | ||
2525 | impl<K, V> FusedIterator for Iter<'_, K, V> {} | |
2526 | ||
2527 | impl<'a, K, V> Iterator for IterMut<'a, K, V> { | |
2528 | type Item = (&'a K, &'a mut V); | |
2529 | ||
e74abb32 | 2530 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 2531 | fn next(&mut self) -> Option<(&'a K, &'a mut V)> { |
3dfed10e XL |
2532 | // Avoid `Option::map` because it bloats LLVM IR. |
2533 | match self.inner.next() { | |
2534 | Some(x) => unsafe { | |
2535 | let r = x.as_mut(); | |
2536 | Some((&r.0, &mut r.1)) | |
1b1a35ee | 2537 | }, |
3dfed10e XL |
2538 | None => None, |
2539 | } | |
48663c56 | 2540 | } |
e74abb32 | 2541 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2542 | fn size_hint(&self) -> (usize, Option<usize>) { |
2543 | self.inner.size_hint() | |
2544 | } | |
2545 | } | |
2546 | impl<K, V> ExactSizeIterator for IterMut<'_, K, V> { | |
e74abb32 | 2547 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2548 | fn len(&self) -> usize { |
2549 | self.inner.len() | |
2550 | } | |
2551 | } | |
2552 | impl<K, V> FusedIterator for IterMut<'_, K, V> {} | |
2553 | ||
2554 | impl<K, V> fmt::Debug for IterMut<'_, K, V> | |
2555 | where | |
2556 | K: fmt::Debug, | |
2557 | V: fmt::Debug, | |
2558 | { | |
2559 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2560 | f.debug_list().entries(self.iter()).finish() | |
2561 | } | |
2562 | } | |
2563 | ||
6a06907d | 2564 | impl<K, V, A: Allocator + Clone> Iterator for IntoIter<K, V, A> { |
48663c56 XL |
2565 | type Item = (K, V); |
2566 | ||
e74abb32 | 2567 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2568 | fn next(&mut self) -> Option<(K, V)> { |
2569 | self.inner.next() | |
2570 | } | |
e74abb32 | 2571 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2572 | fn size_hint(&self) -> (usize, Option<usize>) { |
2573 | self.inner.size_hint() | |
2574 | } | |
2575 | } | |
6a06907d | 2576 | impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, V, A> { |
e74abb32 | 2577 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2578 | fn len(&self) -> usize { |
2579 | self.inner.len() | |
2580 | } | |
2581 | } | |
6a06907d | 2582 | impl<K, V, A: Allocator + Clone> FusedIterator for IntoIter<K, V, A> {} |
48663c56 | 2583 | |
6a06907d | 2584 | impl<K: Debug, V: Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, V, A> { |
48663c56 XL |
2585 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
2586 | f.debug_list().entries(self.iter()).finish() | |
2587 | } | |
2588 | } | |
2589 | ||
2590 | impl<'a, K, V> Iterator for Keys<'a, K, V> { | |
2591 | type Item = &'a K; | |
2592 | ||
e74abb32 | 2593 | #[cfg_attr(feature = "inline-more", inline)] |
3dfed10e XL |
2594 | fn next(&mut self) -> Option<&'a K> { |
2595 | // Avoid `Option::map` because it bloats LLVM IR. | |
2596 | match self.inner.next() { | |
2597 | Some((k, _)) => Some(k), | |
2598 | None => None, | |
2599 | } | |
48663c56 | 2600 | } |
e74abb32 | 2601 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2602 | fn size_hint(&self) -> (usize, Option<usize>) { |
2603 | self.inner.size_hint() | |
2604 | } | |
2605 | } | |
2606 | impl<K, V> ExactSizeIterator for Keys<'_, K, V> { | |
e74abb32 | 2607 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2608 | fn len(&self) -> usize { |
2609 | self.inner.len() | |
2610 | } | |
2611 | } | |
2612 | impl<K, V> FusedIterator for Keys<'_, K, V> {} | |
2613 | ||
2614 | impl<'a, K, V> Iterator for Values<'a, K, V> { | |
2615 | type Item = &'a V; | |
2616 | ||
e74abb32 | 2617 | #[cfg_attr(feature = "inline-more", inline)] |
3dfed10e XL |
2618 | fn next(&mut self) -> Option<&'a V> { |
2619 | // Avoid `Option::map` because it bloats LLVM IR. | |
2620 | match self.inner.next() { | |
2621 | Some((_, v)) => Some(v), | |
2622 | None => None, | |
2623 | } | |
48663c56 | 2624 | } |
e74abb32 | 2625 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2626 | fn size_hint(&self) -> (usize, Option<usize>) { |
2627 | self.inner.size_hint() | |
2628 | } | |
2629 | } | |
2630 | impl<K, V> ExactSizeIterator for Values<'_, K, V> { | |
e74abb32 | 2631 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2632 | fn len(&self) -> usize { |
2633 | self.inner.len() | |
2634 | } | |
2635 | } | |
2636 | impl<K, V> FusedIterator for Values<'_, K, V> {} | |
2637 | ||
2638 | impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { | |
2639 | type Item = &'a mut V; | |
2640 | ||
e74abb32 | 2641 | #[cfg_attr(feature = "inline-more", inline)] |
3dfed10e XL |
2642 | fn next(&mut self) -> Option<&'a mut V> { |
2643 | // Avoid `Option::map` because it bloats LLVM IR. | |
2644 | match self.inner.next() { | |
2645 | Some((_, v)) => Some(v), | |
2646 | None => None, | |
2647 | } | |
48663c56 | 2648 | } |
e74abb32 | 2649 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2650 | fn size_hint(&self) -> (usize, Option<usize>) { |
2651 | self.inner.size_hint() | |
2652 | } | |
2653 | } | |
2654 | impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { | |
e74abb32 | 2655 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2656 | fn len(&self) -> usize { |
2657 | self.inner.len() | |
2658 | } | |
2659 | } | |
2660 | impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} | |
2661 | ||
2662 | impl<K, V> fmt::Debug for ValuesMut<'_, K, V> | |
2663 | where | |
2664 | K: fmt::Debug, | |
2665 | V: fmt::Debug, | |
2666 | { | |
2667 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2668 | f.debug_list().entries(self.inner.iter()).finish() | |
2669 | } | |
2670 | } | |
2671 | ||
6a06907d | 2672 | impl<'a, K, V, A: Allocator + Clone> Iterator for Drain<'a, K, V, A> { |
48663c56 XL |
2673 | type Item = (K, V); |
2674 | ||
e74abb32 | 2675 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2676 | fn next(&mut self) -> Option<(K, V)> { |
2677 | self.inner.next() | |
2678 | } | |
e74abb32 | 2679 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2680 | fn size_hint(&self) -> (usize, Option<usize>) { |
2681 | self.inner.size_hint() | |
2682 | } | |
2683 | } | |
6a06907d | 2684 | impl<K, V, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, V, A> { |
e74abb32 | 2685 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2686 | fn len(&self) -> usize { |
2687 | self.inner.len() | |
2688 | } | |
2689 | } | |
6a06907d | 2690 | impl<K, V, A: Allocator + Clone> FusedIterator for Drain<'_, K, V, A> {} |
48663c56 | 2691 | |
6a06907d | 2692 | impl<K, V, A> fmt::Debug for Drain<'_, K, V, A> |
48663c56 XL |
2693 | where |
2694 | K: fmt::Debug, | |
2695 | V: fmt::Debug, | |
6a06907d | 2696 | A: Allocator + Clone, |
48663c56 XL |
2697 | { |
2698 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2699 | f.debug_list().entries(self.iter()).finish() | |
2700 | } | |
2701 | } | |
2702 | ||
6a06907d | 2703 | impl<'a, K, V, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { |
e74abb32 XL |
2704 | /// Sets the value of the entry, and returns an OccupiedEntry. |
2705 | /// | |
2706 | /// # Examples | |
2707 | /// | |
2708 | /// ``` | |
2709 | /// use hashbrown::HashMap; | |
2710 | /// | |
2711 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2712 | /// let entry = map.entry("horseyland").insert(37); | |
2713 | /// | |
2714 | /// assert_eq!(entry.key(), &"horseyland"); | |
2715 | /// ``` | |
2716 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 2717 | pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S, A> |
e74abb32 XL |
2718 | where |
2719 | K: Hash, | |
2720 | S: BuildHasher, | |
2721 | { | |
2722 | match self { | |
2723 | Entry::Occupied(mut entry) => { | |
2724 | entry.insert(value); | |
2725 | entry | |
2726 | } | |
2727 | Entry::Vacant(entry) => entry.insert_entry(value), | |
2728 | } | |
2729 | } | |
2730 | ||
48663c56 XL |
2731 | /// Ensures a value is in the entry by inserting the default if empty, and returns |
2732 | /// a mutable reference to the value in the entry. | |
2733 | /// | |
2734 | /// # Examples | |
2735 | /// | |
2736 | /// ``` | |
2737 | /// use hashbrown::HashMap; | |
2738 | /// | |
2739 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2740 | /// | |
2741 | /// map.entry("poneyland").or_insert(3); | |
2742 | /// assert_eq!(map["poneyland"], 3); | |
2743 | /// | |
2744 | /// *map.entry("poneyland").or_insert(10) *= 2; | |
2745 | /// assert_eq!(map["poneyland"], 6); | |
2746 | /// ``` | |
e74abb32 | 2747 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2748 | pub fn or_insert(self, default: V) -> &'a mut V |
2749 | where | |
2750 | K: Hash, | |
2751 | S: BuildHasher, | |
2752 | { | |
2753 | match self { | |
2754 | Entry::Occupied(entry) => entry.into_mut(), | |
2755 | Entry::Vacant(entry) => entry.insert(default), | |
2756 | } | |
2757 | } | |
2758 | ||
2759 | /// Ensures a value is in the entry by inserting the result of the default function if empty, | |
2760 | /// and returns a mutable reference to the value in the entry. | |
2761 | /// | |
2762 | /// # Examples | |
2763 | /// | |
2764 | /// ``` | |
2765 | /// use hashbrown::HashMap; | |
2766 | /// | |
2767 | /// let mut map: HashMap<&str, String> = HashMap::new(); | |
2768 | /// let s = "hoho".to_string(); | |
2769 | /// | |
2770 | /// map.entry("poneyland").or_insert_with(|| s); | |
2771 | /// | |
2772 | /// assert_eq!(map["poneyland"], "hoho".to_string()); | |
2773 | /// ``` | |
e74abb32 | 2774 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2775 | pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V |
2776 | where | |
2777 | K: Hash, | |
2778 | S: BuildHasher, | |
2779 | { | |
2780 | match self { | |
2781 | Entry::Occupied(entry) => entry.into_mut(), | |
2782 | Entry::Vacant(entry) => entry.insert(default()), | |
2783 | } | |
2784 | } | |
2785 | ||
6a06907d XL |
2786 | /// Ensures a value is in the entry by inserting, if empty, the result of the default function. |
2787 | /// This method allows for generating key-derived values for insertion by providing the default | |
2788 | /// function a reference to the key that was moved during the `.entry(key)` method call. | |
2789 | /// | |
2790 | /// The reference to the moved key is provided so that cloning or copying the key is | |
2791 | /// unnecessary, unlike with `.or_insert_with(|| ... )`. | |
3dfed10e XL |
2792 | /// |
2793 | /// # Examples | |
2794 | /// | |
2795 | /// ``` | |
2796 | /// use hashbrown::HashMap; | |
2797 | /// | |
2798 | /// let mut map: HashMap<&str, usize> = HashMap::new(); | |
2799 | /// | |
2800 | /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count()); | |
2801 | /// | |
2802 | /// assert_eq!(map["poneyland"], 9); | |
2803 | /// ``` | |
2804 | #[cfg_attr(feature = "inline-more", inline)] | |
2805 | pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V | |
2806 | where | |
2807 | K: Hash, | |
2808 | S: BuildHasher, | |
2809 | { | |
2810 | match self { | |
2811 | Entry::Occupied(entry) => entry.into_mut(), | |
2812 | Entry::Vacant(entry) => { | |
2813 | let value = default(entry.key()); | |
2814 | entry.insert(value) | |
2815 | } | |
2816 | } | |
2817 | } | |
2818 | ||
48663c56 XL |
2819 | /// Returns a reference to this entry's key. |
2820 | /// | |
2821 | /// # Examples | |
2822 | /// | |
2823 | /// ``` | |
2824 | /// use hashbrown::HashMap; | |
2825 | /// | |
2826 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2827 | /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); | |
2828 | /// ``` | |
e74abb32 | 2829 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2830 | pub fn key(&self) -> &K { |
2831 | match *self { | |
2832 | Entry::Occupied(ref entry) => entry.key(), | |
2833 | Entry::Vacant(ref entry) => entry.key(), | |
2834 | } | |
2835 | } | |
2836 | ||
2837 | /// Provides in-place mutable access to an occupied entry before any | |
2838 | /// potential inserts into the map. | |
2839 | /// | |
2840 | /// # Examples | |
2841 | /// | |
2842 | /// ``` | |
2843 | /// use hashbrown::HashMap; | |
2844 | /// | |
2845 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2846 | /// | |
2847 | /// map.entry("poneyland") | |
2848 | /// .and_modify(|e| { *e += 1 }) | |
2849 | /// .or_insert(42); | |
2850 | /// assert_eq!(map["poneyland"], 42); | |
2851 | /// | |
2852 | /// map.entry("poneyland") | |
2853 | /// .and_modify(|e| { *e += 1 }) | |
2854 | /// .or_insert(42); | |
2855 | /// assert_eq!(map["poneyland"], 43); | |
2856 | /// ``` | |
e74abb32 | 2857 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2858 | pub fn and_modify<F>(self, f: F) -> Self |
2859 | where | |
2860 | F: FnOnce(&mut V), | |
2861 | { | |
2862 | match self { | |
2863 | Entry::Occupied(mut entry) => { | |
2864 | f(entry.get_mut()); | |
2865 | Entry::Occupied(entry) | |
2866 | } | |
2867 | Entry::Vacant(entry) => Entry::Vacant(entry), | |
2868 | } | |
2869 | } | |
1b1a35ee XL |
2870 | |
2871 | /// Provides shared access to the key and owned access to the value of | |
2872 | /// an occupied entry and allows to replace or remove it based on the | |
2873 | /// value of the returned option. | |
2874 | /// | |
2875 | /// # Examples | |
2876 | /// | |
2877 | /// ``` | |
2878 | /// use hashbrown::HashMap; | |
2879 | /// use hashbrown::hash_map::Entry; | |
2880 | /// | |
2881 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2882 | /// | |
2883 | /// let entry = map | |
2884 | /// .entry("poneyland") | |
2885 | /// .and_replace_entry_with(|_k, _v| panic!()); | |
2886 | /// | |
2887 | /// match entry { | |
2888 | /// Entry::Vacant(e) => { | |
2889 | /// assert_eq!(e.key(), &"poneyland"); | |
2890 | /// } | |
2891 | /// Entry::Occupied(_) => panic!(), | |
2892 | /// } | |
2893 | /// | |
2894 | /// map.insert("poneyland", 42); | |
2895 | /// | |
2896 | /// let entry = map | |
2897 | /// .entry("poneyland") | |
2898 | /// .and_replace_entry_with(|k, v| { | |
2899 | /// assert_eq!(k, &"poneyland"); | |
2900 | /// assert_eq!(v, 42); | |
2901 | /// Some(v + 1) | |
2902 | /// }); | |
2903 | /// | |
2904 | /// match entry { | |
2905 | /// Entry::Occupied(e) => { | |
2906 | /// assert_eq!(e.key(), &"poneyland"); | |
2907 | /// assert_eq!(e.get(), &43); | |
2908 | /// } | |
2909 | /// Entry::Vacant(_) => panic!(), | |
2910 | /// } | |
2911 | /// | |
2912 | /// assert_eq!(map["poneyland"], 43); | |
2913 | /// | |
2914 | /// let entry = map | |
2915 | /// .entry("poneyland") | |
2916 | /// .and_replace_entry_with(|_k, _v| None); | |
2917 | /// | |
2918 | /// match entry { | |
2919 | /// Entry::Vacant(e) => assert_eq!(e.key(), &"poneyland"), | |
2920 | /// Entry::Occupied(_) => panic!(), | |
2921 | /// } | |
2922 | /// | |
2923 | /// assert!(!map.contains_key("poneyland")); | |
2924 | /// ``` | |
2925 | #[cfg_attr(feature = "inline-more", inline)] | |
2926 | pub fn and_replace_entry_with<F>(self, f: F) -> Self | |
2927 | where | |
2928 | F: FnOnce(&K, V) -> Option<V>, | |
2929 | { | |
2930 | match self { | |
2931 | Entry::Occupied(entry) => entry.replace_entry_with(f), | |
2932 | Entry::Vacant(_) => self, | |
2933 | } | |
2934 | } | |
48663c56 XL |
2935 | } |
2936 | ||
6a06907d | 2937 | impl<'a, K, V: Default, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { |
48663c56 XL |
2938 | /// Ensures a value is in the entry by inserting the default value if empty, |
2939 | /// and returns a mutable reference to the value in the entry. | |
2940 | /// | |
2941 | /// # Examples | |
2942 | /// | |
2943 | /// ``` | |
48663c56 XL |
2944 | /// use hashbrown::HashMap; |
2945 | /// | |
2946 | /// let mut map: HashMap<&str, Option<u32>> = HashMap::new(); | |
2947 | /// map.entry("poneyland").or_default(); | |
2948 | /// | |
2949 | /// assert_eq!(map["poneyland"], None); | |
48663c56 | 2950 | /// ``` |
e74abb32 | 2951 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2952 | pub fn or_default(self) -> &'a mut V |
2953 | where | |
2954 | K: Hash, | |
2955 | S: BuildHasher, | |
2956 | { | |
2957 | match self { | |
2958 | Entry::Occupied(entry) => entry.into_mut(), | |
2959 | Entry::Vacant(entry) => entry.insert(Default::default()), | |
2960 | } | |
2961 | } | |
2962 | } | |
2963 | ||
6a06907d | 2964 | impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { |
48663c56 XL |
2965 | /// Gets a reference to the key in the entry. |
2966 | /// | |
2967 | /// # Examples | |
2968 | /// | |
2969 | /// ``` | |
2970 | /// use hashbrown::HashMap; | |
2971 | /// | |
2972 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2973 | /// map.entry("poneyland").or_insert(12); | |
2974 | /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); | |
2975 | /// ``` | |
e74abb32 | 2976 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
2977 | pub fn key(&self) -> &K { |
2978 | unsafe { &self.elem.as_ref().0 } | |
2979 | } | |
2980 | ||
2981 | /// Take the ownership of the key and value from the map. | |
2982 | /// | |
2983 | /// # Examples | |
2984 | /// | |
2985 | /// ``` | |
2986 | /// use hashbrown::HashMap; | |
2987 | /// use hashbrown::hash_map::Entry; | |
2988 | /// | |
2989 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
2990 | /// map.entry("poneyland").or_insert(12); | |
2991 | /// | |
2992 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
2993 | /// // We delete the entry from the map. | |
2994 | /// o.remove_entry(); | |
2995 | /// } | |
2996 | /// | |
2997 | /// assert_eq!(map.contains_key("poneyland"), false); | |
2998 | /// ``` | |
e74abb32 | 2999 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 | 3000 | pub fn remove_entry(self) -> (K, V) { |
3dfed10e | 3001 | unsafe { self.table.table.remove(self.elem) } |
48663c56 XL |
3002 | } |
3003 | ||
3004 | /// Gets a reference to the value in the entry. | |
3005 | /// | |
3006 | /// # Examples | |
3007 | /// | |
3008 | /// ``` | |
3009 | /// use hashbrown::HashMap; | |
3010 | /// use hashbrown::hash_map::Entry; | |
3011 | /// | |
3012 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3013 | /// map.entry("poneyland").or_insert(12); | |
3014 | /// | |
3015 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
3016 | /// assert_eq!(o.get(), &12); | |
3017 | /// } | |
3018 | /// ``` | |
e74abb32 | 3019 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3020 | pub fn get(&self) -> &V { |
3021 | unsafe { &self.elem.as_ref().1 } | |
3022 | } | |
3023 | ||
3024 | /// Gets a mutable reference to the value in the entry. | |
3025 | /// | |
3026 | /// If you need a reference to the `OccupiedEntry` which may outlive the | |
3027 | /// destruction of the `Entry` value, see [`into_mut`]. | |
3028 | /// | |
3029 | /// [`into_mut`]: #method.into_mut | |
3030 | /// | |
3031 | /// # Examples | |
3032 | /// | |
3033 | /// ``` | |
3034 | /// use hashbrown::HashMap; | |
3035 | /// use hashbrown::hash_map::Entry; | |
3036 | /// | |
3037 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3038 | /// map.entry("poneyland").or_insert(12); | |
3039 | /// | |
3040 | /// assert_eq!(map["poneyland"], 12); | |
3041 | /// if let Entry::Occupied(mut o) = map.entry("poneyland") { | |
3042 | /// *o.get_mut() += 10; | |
3043 | /// assert_eq!(*o.get(), 22); | |
3044 | /// | |
3045 | /// // We can use the same Entry multiple times. | |
3046 | /// *o.get_mut() += 2; | |
3047 | /// } | |
3048 | /// | |
3049 | /// assert_eq!(map["poneyland"], 24); | |
3050 | /// ``` | |
e74abb32 | 3051 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3052 | pub fn get_mut(&mut self) -> &mut V { |
3053 | unsafe { &mut self.elem.as_mut().1 } | |
3054 | } | |
3055 | ||
3056 | /// Converts the OccupiedEntry into a mutable reference to the value in the entry | |
3057 | /// with a lifetime bound to the map itself. | |
3058 | /// | |
3059 | /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`]. | |
3060 | /// | |
3061 | /// [`get_mut`]: #method.get_mut | |
3062 | /// | |
3063 | /// # Examples | |
3064 | /// | |
3065 | /// ``` | |
3066 | /// use hashbrown::HashMap; | |
3067 | /// use hashbrown::hash_map::Entry; | |
3068 | /// | |
3069 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3070 | /// map.entry("poneyland").or_insert(12); | |
3071 | /// | |
3072 | /// assert_eq!(map["poneyland"], 12); | |
3073 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
3074 | /// *o.into_mut() += 10; | |
3075 | /// } | |
3076 | /// | |
3077 | /// assert_eq!(map["poneyland"], 22); | |
3078 | /// ``` | |
e74abb32 | 3079 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3080 | pub fn into_mut(self) -> &'a mut V { |
3081 | unsafe { &mut self.elem.as_mut().1 } | |
3082 | } | |
3083 | ||
3084 | /// Sets the value of the entry, and returns the entry's old value. | |
3085 | /// | |
3086 | /// # Examples | |
3087 | /// | |
3088 | /// ``` | |
3089 | /// use hashbrown::HashMap; | |
3090 | /// use hashbrown::hash_map::Entry; | |
3091 | /// | |
3092 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3093 | /// map.entry("poneyland").or_insert(12); | |
3094 | /// | |
3095 | /// if let Entry::Occupied(mut o) = map.entry("poneyland") { | |
3096 | /// assert_eq!(o.insert(15), 12); | |
3097 | /// } | |
3098 | /// | |
3099 | /// assert_eq!(map["poneyland"], 15); | |
3100 | /// ``` | |
e74abb32 | 3101 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3102 | pub fn insert(&mut self, mut value: V) -> V { |
3103 | let old_value = self.get_mut(); | |
3104 | mem::swap(&mut value, old_value); | |
3105 | value | |
3106 | } | |
3107 | ||
3108 | /// Takes the value out of the entry, and returns it. | |
3109 | /// | |
3110 | /// # Examples | |
3111 | /// | |
3112 | /// ``` | |
3113 | /// use hashbrown::HashMap; | |
3114 | /// use hashbrown::hash_map::Entry; | |
3115 | /// | |
3116 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3117 | /// map.entry("poneyland").or_insert(12); | |
3118 | /// | |
3119 | /// if let Entry::Occupied(o) = map.entry("poneyland") { | |
3120 | /// assert_eq!(o.remove(), 12); | |
3121 | /// } | |
3122 | /// | |
3123 | /// assert_eq!(map.contains_key("poneyland"), false); | |
3124 | /// ``` | |
e74abb32 | 3125 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3126 | pub fn remove(self) -> V { |
3127 | self.remove_entry().1 | |
3128 | } | |
3129 | ||
3130 | /// Replaces the entry, returning the old key and value. The new key in the hash map will be | |
3131 | /// the key used to create this entry. | |
3132 | /// | |
6a06907d XL |
3133 | /// # Panics |
3134 | /// | |
3135 | /// Will panic if this OccupiedEntry was created through [`Entry::insert`]. | |
3136 | /// | |
48663c56 XL |
3137 | /// # Examples |
3138 | /// | |
3139 | /// ``` | |
3140 | /// use hashbrown::hash_map::{Entry, HashMap}; | |
3141 | /// use std::rc::Rc; | |
3142 | /// | |
3143 | /// let mut map: HashMap<Rc<String>, u32> = HashMap::new(); | |
3144 | /// map.insert(Rc::new("Stringthing".to_string()), 15); | |
3145 | /// | |
3146 | /// let my_key = Rc::new("Stringthing".to_string()); | |
3147 | /// | |
3148 | /// if let Entry::Occupied(entry) = map.entry(my_key) { | |
3149 | /// // Also replace the key with a handle to our other key. | |
3150 | /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16); | |
3151 | /// } | |
3152 | /// | |
3153 | /// ``` | |
e74abb32 | 3154 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3155 | pub fn replace_entry(self, value: V) -> (K, V) { |
3156 | let entry = unsafe { self.elem.as_mut() }; | |
3157 | ||
3158 | let old_key = mem::replace(&mut entry.0, self.key.unwrap()); | |
3159 | let old_value = mem::replace(&mut entry.1, value); | |
3160 | ||
3161 | (old_key, old_value) | |
3162 | } | |
3163 | ||
3164 | /// Replaces the key in the hash map with the key used to create this entry. | |
3165 | /// | |
6a06907d XL |
3166 | /// # Panics |
3167 | /// | |
3168 | /// Will panic if this OccupiedEntry was created through [`Entry::insert`]. | |
3169 | /// | |
48663c56 XL |
3170 | /// # Examples |
3171 | /// | |
3172 | /// ``` | |
3173 | /// use hashbrown::hash_map::{Entry, HashMap}; | |
3174 | /// use std::rc::Rc; | |
3175 | /// | |
3176 | /// let mut map: HashMap<Rc<String>, u32> = HashMap::new(); | |
3177 | /// let mut known_strings: Vec<Rc<String>> = Vec::new(); | |
3178 | /// | |
3179 | /// // Initialise known strings, run program, etc. | |
3180 | /// | |
3181 | /// reclaim_memory(&mut map, &known_strings); | |
3182 | /// | |
3183 | /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) { | |
3184 | /// for s in known_strings { | |
3185 | /// if let Entry::Occupied(entry) = map.entry(s.clone()) { | |
3186 | /// // Replaces the entry's key with our version of it in `known_strings`. | |
3187 | /// entry.replace_key(); | |
3188 | /// } | |
3189 | /// } | |
3190 | /// } | |
3191 | /// ``` | |
e74abb32 | 3192 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3193 | pub fn replace_key(self) -> K { |
3194 | let entry = unsafe { self.elem.as_mut() }; | |
3195 | mem::replace(&mut entry.0, self.key.unwrap()) | |
3196 | } | |
1b1a35ee XL |
3197 | |
3198 | /// Provides shared access to the key and owned access to the value of | |
3199 | /// the entry and allows to replace or remove it based on the | |
3200 | /// value of the returned option. | |
3201 | /// | |
3202 | /// # Examples | |
3203 | /// | |
3204 | /// ``` | |
3205 | /// use hashbrown::HashMap; | |
3206 | /// use hashbrown::hash_map::Entry; | |
3207 | /// | |
3208 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3209 | /// map.insert("poneyland", 42); | |
3210 | /// | |
3211 | /// let entry = match map.entry("poneyland") { | |
3212 | /// Entry::Occupied(e) => { | |
3213 | /// e.replace_entry_with(|k, v| { | |
3214 | /// assert_eq!(k, &"poneyland"); | |
3215 | /// assert_eq!(v, 42); | |
3216 | /// Some(v + 1) | |
3217 | /// }) | |
3218 | /// } | |
3219 | /// Entry::Vacant(_) => panic!(), | |
3220 | /// }; | |
3221 | /// | |
3222 | /// match entry { | |
3223 | /// Entry::Occupied(e) => { | |
3224 | /// assert_eq!(e.key(), &"poneyland"); | |
3225 | /// assert_eq!(e.get(), &43); | |
3226 | /// } | |
3227 | /// Entry::Vacant(_) => panic!(), | |
3228 | /// } | |
3229 | /// | |
3230 | /// assert_eq!(map["poneyland"], 43); | |
3231 | /// | |
3232 | /// let entry = match map.entry("poneyland") { | |
3233 | /// Entry::Occupied(e) => e.replace_entry_with(|_k, _v| None), | |
3234 | /// Entry::Vacant(_) => panic!(), | |
3235 | /// }; | |
3236 | /// | |
3237 | /// match entry { | |
3238 | /// Entry::Vacant(e) => { | |
3239 | /// assert_eq!(e.key(), &"poneyland"); | |
3240 | /// } | |
3241 | /// Entry::Occupied(_) => panic!(), | |
3242 | /// } | |
3243 | /// | |
3244 | /// assert!(!map.contains_key("poneyland")); | |
3245 | /// ``` | |
3246 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 3247 | pub fn replace_entry_with<F>(self, f: F) -> Entry<'a, K, V, S, A> |
1b1a35ee XL |
3248 | where |
3249 | F: FnOnce(&K, V) -> Option<V>, | |
3250 | { | |
3251 | unsafe { | |
3252 | let mut spare_key = None; | |
3253 | ||
3254 | self.table | |
3255 | .table | |
3256 | .replace_bucket_with(self.elem.clone(), |(key, value)| { | |
3257 | if let Some(new_value) = f(&key, value) { | |
3258 | Some((key, new_value)) | |
3259 | } else { | |
3260 | spare_key = Some(key); | |
3261 | None | |
3262 | } | |
3263 | }); | |
3264 | ||
3265 | if let Some(key) = spare_key { | |
3266 | Entry::Vacant(VacantEntry { | |
3267 | hash: self.hash, | |
3268 | key, | |
3269 | table: self.table, | |
3270 | }) | |
3271 | } else { | |
3272 | Entry::Occupied(self) | |
3273 | } | |
3274 | } | |
3275 | } | |
48663c56 XL |
3276 | } |
3277 | ||
6a06907d | 3278 | impl<'a, K, V, S, A: Allocator + Clone> VacantEntry<'a, K, V, S, A> { |
48663c56 XL |
3279 | /// Gets a reference to the key that would be used when inserting a value |
3280 | /// through the `VacantEntry`. | |
3281 | /// | |
3282 | /// # Examples | |
3283 | /// | |
3284 | /// ``` | |
3285 | /// use hashbrown::HashMap; | |
3286 | /// | |
3287 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3288 | /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); | |
3289 | /// ``` | |
e74abb32 | 3290 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3291 | pub fn key(&self) -> &K { |
3292 | &self.key | |
3293 | } | |
3294 | ||
3295 | /// Take ownership of the key. | |
3296 | /// | |
3297 | /// # Examples | |
3298 | /// | |
3299 | /// ``` | |
3300 | /// use hashbrown::HashMap; | |
3301 | /// use hashbrown::hash_map::Entry; | |
3302 | /// | |
3303 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3304 | /// | |
3305 | /// if let Entry::Vacant(v) = map.entry("poneyland") { | |
3306 | /// v.into_key(); | |
3307 | /// } | |
3308 | /// ``` | |
e74abb32 | 3309 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3310 | pub fn into_key(self) -> K { |
3311 | self.key | |
3312 | } | |
3313 | ||
3314 | /// Sets the value of the entry with the VacantEntry's key, | |
3315 | /// and returns a mutable reference to it. | |
3316 | /// | |
3317 | /// # Examples | |
3318 | /// | |
3319 | /// ``` | |
3320 | /// use hashbrown::HashMap; | |
3321 | /// use hashbrown::hash_map::Entry; | |
3322 | /// | |
3323 | /// let mut map: HashMap<&str, u32> = HashMap::new(); | |
3324 | /// | |
3325 | /// if let Entry::Vacant(o) = map.entry("poneyland") { | |
3326 | /// o.insert(37); | |
3327 | /// } | |
3328 | /// assert_eq!(map["poneyland"], 37); | |
3329 | /// ``` | |
e74abb32 | 3330 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3331 | pub fn insert(self, value: V) -> &'a mut V |
3332 | where | |
3333 | K: Hash, | |
3334 | S: BuildHasher, | |
3335 | { | |
29967ef6 | 3336 | let table = &mut self.table.table; |
6a06907d XL |
3337 | let entry = table.insert_entry( |
3338 | self.hash, | |
3339 | (self.key, value), | |
3340 | make_hasher::<K, _, V, S>(&self.table.hash_builder), | |
3341 | ); | |
29967ef6 | 3342 | &mut entry.1 |
48663c56 | 3343 | } |
e74abb32 XL |
3344 | |
3345 | #[cfg_attr(feature = "inline-more", inline)] | |
6a06907d | 3346 | fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A> |
e74abb32 XL |
3347 | where |
3348 | K: Hash, | |
3349 | S: BuildHasher, | |
3350 | { | |
6a06907d XL |
3351 | let elem = self.table.table.insert( |
3352 | self.hash, | |
3353 | (self.key, value), | |
3354 | make_hasher::<K, _, V, S>(&self.table.hash_builder), | |
3355 | ); | |
e74abb32 | 3356 | OccupiedEntry { |
1b1a35ee | 3357 | hash: self.hash, |
e74abb32 XL |
3358 | key: None, |
3359 | elem, | |
3360 | table: self.table, | |
3361 | } | |
3362 | } | |
48663c56 XL |
3363 | } |
3364 | ||
6a06907d | 3365 | impl<K, V, S, A> FromIterator<(K, V)> for HashMap<K, V, S, A> |
48663c56 XL |
3366 | where |
3367 | K: Eq + Hash, | |
3368 | S: BuildHasher + Default, | |
6a06907d | 3369 | A: Default + Allocator + Clone, |
48663c56 | 3370 | { |
e74abb32 | 3371 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3372 | fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self { |
3373 | let iter = iter.into_iter(); | |
6a06907d XL |
3374 | let mut map = |
3375 | Self::with_capacity_and_hasher_in(iter.size_hint().0, S::default(), A::default()); | |
48663c56 XL |
3376 | iter.for_each(|(k, v)| { |
3377 | map.insert(k, v); | |
3378 | }); | |
3379 | map | |
3380 | } | |
3381 | } | |
3382 | ||
3dfed10e XL |
3383 | /// Inserts all new key-values from the iterator and replaces values with existing |
3384 | /// keys with new values returned from the iterator. | |
6a06907d | 3385 | impl<K, V, S, A> Extend<(K, V)> for HashMap<K, V, S, A> |
48663c56 XL |
3386 | where |
3387 | K: Eq + Hash, | |
3388 | S: BuildHasher, | |
6a06907d | 3389 | A: Allocator + Clone, |
48663c56 | 3390 | { |
e74abb32 | 3391 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3392 | fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { |
3393 | // Keys may be already present or show multiple times in the iterator. | |
3394 | // Reserve the entire hint lower bound if the map is empty. | |
3395 | // Otherwise reserve half the hint (rounded up), so the map | |
3396 | // will only resize twice in the worst case. | |
3397 | let iter = iter.into_iter(); | |
3398 | let reserve = if self.is_empty() { | |
3399 | iter.size_hint().0 | |
3400 | } else { | |
3401 | (iter.size_hint().0 + 1) / 2 | |
3402 | }; | |
3403 | self.reserve(reserve); | |
3404 | iter.for_each(move |(k, v)| { | |
3405 | self.insert(k, v); | |
3406 | }); | |
3407 | } | |
3dfed10e XL |
3408 | |
3409 | #[inline] | |
3410 | #[cfg(feature = "nightly")] | |
3411 | fn extend_one(&mut self, (k, v): (K, V)) { | |
3412 | self.insert(k, v); | |
3413 | } | |
3414 | ||
3415 | #[inline] | |
3416 | #[cfg(feature = "nightly")] | |
3417 | fn extend_reserve(&mut self, additional: usize) { | |
3418 | // Keys may be already present or show multiple times in the iterator. | |
3419 | // Reserve the entire hint lower bound if the map is empty. | |
3420 | // Otherwise reserve half the hint (rounded up), so the map | |
3421 | // will only resize twice in the worst case. | |
3422 | let reserve = if self.is_empty() { | |
3423 | additional | |
3424 | } else { | |
3425 | (additional + 1) / 2 | |
3426 | }; | |
3427 | self.reserve(reserve); | |
3428 | } | |
48663c56 XL |
3429 | } |
3430 | ||
6a06907d | 3431 | impl<'a, K, V, S, A> Extend<(&'a K, &'a V)> for HashMap<K, V, S, A> |
48663c56 XL |
3432 | where |
3433 | K: Eq + Hash + Copy, | |
3434 | V: Copy, | |
3435 | S: BuildHasher, | |
6a06907d | 3436 | A: Allocator + Clone, |
48663c56 | 3437 | { |
e74abb32 | 3438 | #[cfg_attr(feature = "inline-more", inline)] |
48663c56 XL |
3439 | fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) { |
3440 | self.extend(iter.into_iter().map(|(&key, &value)| (key, value))); | |
3441 | } | |
3dfed10e XL |
3442 | |
3443 | #[inline] | |
3444 | #[cfg(feature = "nightly")] | |
3445 | fn extend_one(&mut self, (k, v): (&'a K, &'a V)) { | |
3446 | self.insert(*k, *v); | |
3447 | } | |
3448 | ||
3449 | #[inline] | |
3450 | #[cfg(feature = "nightly")] | |
3451 | fn extend_reserve(&mut self, additional: usize) { | |
3452 | Extend::<(K, V)>::extend_reserve(self, additional); | |
3453 | } | |
48663c56 XL |
3454 | } |
3455 | ||
3456 | #[allow(dead_code)] | |
3457 | fn assert_covariance() { | |
3458 | fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> { | |
3459 | v | |
3460 | } | |
3461 | fn map_val<'new>(v: HashMap<u8, &'static str>) -> HashMap<u8, &'new str> { | |
3462 | v | |
3463 | } | |
3464 | fn iter_key<'a, 'new>(v: Iter<'a, &'static str, u8>) -> Iter<'a, &'new str, u8> { | |
3465 | v | |
3466 | } | |
3467 | fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> { | |
3468 | v | |
3469 | } | |
6a06907d XL |
3470 | fn into_iter_key<'new, A: Allocator + Clone>( |
3471 | v: IntoIter<&'static str, u8, A>, | |
3472 | ) -> IntoIter<&'new str, u8, A> { | |
48663c56 XL |
3473 | v |
3474 | } | |
6a06907d XL |
3475 | fn into_iter_val<'new, A: Allocator + Clone>( |
3476 | v: IntoIter<u8, &'static str, A>, | |
3477 | ) -> IntoIter<u8, &'new str, A> { | |
48663c56 XL |
3478 | v |
3479 | } | |
3480 | fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> { | |
3481 | v | |
3482 | } | |
3483 | fn keys_val<'a, 'new>(v: Keys<'a, u8, &'static str>) -> Keys<'a, u8, &'new str> { | |
3484 | v | |
3485 | } | |
3486 | fn values_key<'a, 'new>(v: Values<'a, &'static str, u8>) -> Values<'a, &'new str, u8> { | |
3487 | v | |
3488 | } | |
3489 | fn values_val<'a, 'new>(v: Values<'a, u8, &'static str>) -> Values<'a, u8, &'new str> { | |
3490 | v | |
3491 | } | |
3492 | fn drain<'new>( | |
3493 | d: Drain<'static, &'static str, &'static str>, | |
3494 | ) -> Drain<'new, &'new str, &'new str> { | |
3495 | d | |
3496 | } | |
3497 | } | |
3498 | ||
3499 | #[cfg(test)] | |
3500 | mod test_map { | |
3501 | use super::DefaultHashBuilder; | |
3502 | use super::Entry::{Occupied, Vacant}; | |
3503 | use super::{HashMap, RawEntryMut}; | |
3dfed10e | 3504 | use crate::TryReserveError::*; |
48663c56 | 3505 | use rand::{rngs::SmallRng, Rng, SeedableRng}; |
6a06907d | 3506 | use std::borrow::ToOwned; |
48663c56 XL |
3507 | use std::cell::RefCell; |
3508 | use std::usize; | |
3509 | use std::vec::Vec; | |
3510 | ||
3511 | #[test] | |
3512 | fn test_zero_capacities() { | |
3513 | type HM = HashMap<i32, i32>; | |
3514 | ||
3515 | let m = HM::new(); | |
3516 | assert_eq!(m.capacity(), 0); | |
3517 | ||
3518 | let m = HM::default(); | |
3519 | assert_eq!(m.capacity(), 0); | |
3520 | ||
3521 | let m = HM::with_hasher(DefaultHashBuilder::default()); | |
3522 | assert_eq!(m.capacity(), 0); | |
3523 | ||
3524 | let m = HM::with_capacity(0); | |
3525 | assert_eq!(m.capacity(), 0); | |
3526 | ||
3527 | let m = HM::with_capacity_and_hasher(0, DefaultHashBuilder::default()); | |
3528 | assert_eq!(m.capacity(), 0); | |
3529 | ||
3530 | let mut m = HM::new(); | |
3531 | m.insert(1, 1); | |
3532 | m.insert(2, 2); | |
3533 | m.remove(&1); | |
3534 | m.remove(&2); | |
3535 | m.shrink_to_fit(); | |
3536 | assert_eq!(m.capacity(), 0); | |
3537 | ||
3538 | let mut m = HM::new(); | |
3539 | m.reserve(0); | |
3540 | assert_eq!(m.capacity(), 0); | |
3541 | } | |
3542 | ||
3543 | #[test] | |
3544 | fn test_create_capacity_zero() { | |
3545 | let mut m = HashMap::with_capacity(0); | |
3546 | ||
3547 | assert!(m.insert(1, 1).is_none()); | |
3548 | ||
3549 | assert!(m.contains_key(&1)); | |
3550 | assert!(!m.contains_key(&0)); | |
3551 | } | |
3552 | ||
3553 | #[test] | |
3554 | fn test_insert() { | |
3555 | let mut m = HashMap::new(); | |
3556 | assert_eq!(m.len(), 0); | |
3557 | assert!(m.insert(1, 2).is_none()); | |
3558 | assert_eq!(m.len(), 1); | |
3559 | assert!(m.insert(2, 4).is_none()); | |
3560 | assert_eq!(m.len(), 2); | |
3561 | assert_eq!(*m.get(&1).unwrap(), 2); | |
3562 | assert_eq!(*m.get(&2).unwrap(), 4); | |
3563 | } | |
3564 | ||
3565 | #[test] | |
3566 | fn test_clone() { | |
3567 | let mut m = HashMap::new(); | |
3568 | assert_eq!(m.len(), 0); | |
3569 | assert!(m.insert(1, 2).is_none()); | |
3570 | assert_eq!(m.len(), 1); | |
3571 | assert!(m.insert(2, 4).is_none()); | |
3572 | assert_eq!(m.len(), 2); | |
3573 | let m2 = m.clone(); | |
3574 | assert_eq!(*m2.get(&1).unwrap(), 2); | |
3575 | assert_eq!(*m2.get(&2).unwrap(), 4); | |
3576 | assert_eq!(m2.len(), 2); | |
3577 | } | |
3578 | ||
3dfed10e XL |
3579 | #[test] |
3580 | fn test_clone_from() { | |
3581 | let mut m = HashMap::new(); | |
3582 | let mut m2 = HashMap::new(); | |
3583 | assert_eq!(m.len(), 0); | |
3584 | assert!(m.insert(1, 2).is_none()); | |
3585 | assert_eq!(m.len(), 1); | |
3586 | assert!(m.insert(2, 4).is_none()); | |
3587 | assert_eq!(m.len(), 2); | |
3588 | m2.clone_from(&m); | |
3589 | assert_eq!(*m2.get(&1).unwrap(), 2); | |
3590 | assert_eq!(*m2.get(&2).unwrap(), 4); | |
3591 | assert_eq!(m2.len(), 2); | |
3592 | } | |
3593 | ||
48663c56 XL |
3594 | thread_local! { static DROP_VECTOR: RefCell<Vec<i32>> = RefCell::new(Vec::new()) } |
3595 | ||
3596 | #[derive(Hash, PartialEq, Eq)] | |
3597 | struct Droppable { | |
3598 | k: usize, | |
3599 | } | |
3600 | ||
3601 | impl Droppable { | |
3602 | fn new(k: usize) -> Droppable { | |
3603 | DROP_VECTOR.with(|slot| { | |
3604 | slot.borrow_mut()[k] += 1; | |
3605 | }); | |
3606 | ||
3607 | Droppable { k } | |
3608 | } | |
3609 | } | |
3610 | ||
3611 | impl Drop for Droppable { | |
3612 | fn drop(&mut self) { | |
3613 | DROP_VECTOR.with(|slot| { | |
3614 | slot.borrow_mut()[self.k] -= 1; | |
3615 | }); | |
3616 | } | |
3617 | } | |
3618 | ||
3619 | impl Clone for Droppable { | |
3620 | fn clone(&self) -> Self { | |
3621 | Droppable::new(self.k) | |
3622 | } | |
3623 | } | |
3624 | ||
3625 | #[test] | |
3626 | fn test_drops() { | |
3627 | DROP_VECTOR.with(|slot| { | |
3628 | *slot.borrow_mut() = vec![0; 200]; | |
3629 | }); | |
3630 | ||
3631 | { | |
3632 | let mut m = HashMap::new(); | |
3633 | ||
3634 | DROP_VECTOR.with(|v| { | |
3635 | for i in 0..200 { | |
3636 | assert_eq!(v.borrow()[i], 0); | |
3637 | } | |
3638 | }); | |
3639 | ||
3640 | for i in 0..100 { | |
3641 | let d1 = Droppable::new(i); | |
3642 | let d2 = Droppable::new(i + 100); | |
3643 | m.insert(d1, d2); | |
3644 | } | |
3645 | ||
3646 | DROP_VECTOR.with(|v| { | |
3647 | for i in 0..200 { | |
3648 | assert_eq!(v.borrow()[i], 1); | |
3649 | } | |
3650 | }); | |
3651 | ||
3652 | for i in 0..50 { | |
3653 | let k = Droppable::new(i); | |
3654 | let v = m.remove(&k); | |
3655 | ||
3656 | assert!(v.is_some()); | |
3657 | ||
3658 | DROP_VECTOR.with(|v| { | |
3659 | assert_eq!(v.borrow()[i], 1); | |
3660 | assert_eq!(v.borrow()[i + 100], 1); | |
3661 | }); | |
3662 | } | |
3663 | ||
3664 | DROP_VECTOR.with(|v| { | |
3665 | for i in 0..50 { | |
3666 | assert_eq!(v.borrow()[i], 0); | |
3667 | assert_eq!(v.borrow()[i + 100], 0); | |
3668 | } | |
3669 | ||
3670 | for i in 50..100 { | |
3671 | assert_eq!(v.borrow()[i], 1); | |
3672 | assert_eq!(v.borrow()[i + 100], 1); | |
3673 | } | |
3674 | }); | |
3675 | } | |
3676 | ||
3677 | DROP_VECTOR.with(|v| { | |
3678 | for i in 0..200 { | |
3679 | assert_eq!(v.borrow()[i], 0); | |
3680 | } | |
3681 | }); | |
3682 | } | |
3683 | ||
3684 | #[test] | |
3685 | fn test_into_iter_drops() { | |
3686 | DROP_VECTOR.with(|v| { | |
3687 | *v.borrow_mut() = vec![0; 200]; | |
3688 | }); | |
3689 | ||
3690 | let hm = { | |
3691 | let mut hm = HashMap::new(); | |
3692 | ||
3693 | DROP_VECTOR.with(|v| { | |
3694 | for i in 0..200 { | |
3695 | assert_eq!(v.borrow()[i], 0); | |
3696 | } | |
3697 | }); | |
3698 | ||
3699 | for i in 0..100 { | |
3700 | let d1 = Droppable::new(i); | |
3701 | let d2 = Droppable::new(i + 100); | |
3702 | hm.insert(d1, d2); | |
3703 | } | |
3704 | ||
3705 | DROP_VECTOR.with(|v| { | |
3706 | for i in 0..200 { | |
3707 | assert_eq!(v.borrow()[i], 1); | |
3708 | } | |
3709 | }); | |
3710 | ||
3711 | hm | |
3712 | }; | |
3713 | ||
3714 | // By the way, ensure that cloning doesn't screw up the dropping. | |
3715 | drop(hm.clone()); | |
3716 | ||
3717 | { | |
3718 | let mut half = hm.into_iter().take(50); | |
3719 | ||
3720 | DROP_VECTOR.with(|v| { | |
3721 | for i in 0..200 { | |
3722 | assert_eq!(v.borrow()[i], 1); | |
3723 | } | |
3724 | }); | |
3725 | ||
3726 | for _ in half.by_ref() {} | |
3727 | ||
3728 | DROP_VECTOR.with(|v| { | |
3729 | let nk = (0..100).filter(|&i| v.borrow()[i] == 1).count(); | |
3730 | ||
3731 | let nv = (0..100).filter(|&i| v.borrow()[i + 100] == 1).count(); | |
3732 | ||
3733 | assert_eq!(nk, 50); | |
3734 | assert_eq!(nv, 50); | |
3735 | }); | |
3736 | }; | |
3737 | ||
3738 | DROP_VECTOR.with(|v| { | |
3739 | for i in 0..200 { | |
3740 | assert_eq!(v.borrow()[i], 0); | |
3741 | } | |
3742 | }); | |
3743 | } | |
3744 | ||
3745 | #[test] | |
3746 | fn test_empty_remove() { | |
3747 | let mut m: HashMap<i32, bool> = HashMap::new(); | |
3748 | assert_eq!(m.remove(&0), None); | |
3749 | } | |
3750 | ||
3751 | #[test] | |
3752 | fn test_empty_entry() { | |
3753 | let mut m: HashMap<i32, bool> = HashMap::new(); | |
3754 | match m.entry(0) { | |
3755 | Occupied(_) => panic!(), | |
3756 | Vacant(_) => {} | |
3757 | } | |
3758 | assert!(*m.entry(0).or_insert(true)); | |
3759 | assert_eq!(m.len(), 1); | |
3760 | } | |
3761 | ||
3762 | #[test] | |
3763 | fn test_empty_iter() { | |
3764 | let mut m: HashMap<i32, bool> = HashMap::new(); | |
3765 | assert_eq!(m.drain().next(), None); | |
3766 | assert_eq!(m.keys().next(), None); | |
3767 | assert_eq!(m.values().next(), None); | |
3768 | assert_eq!(m.values_mut().next(), None); | |
3769 | assert_eq!(m.iter().next(), None); | |
3770 | assert_eq!(m.iter_mut().next(), None); | |
3771 | assert_eq!(m.len(), 0); | |
3772 | assert!(m.is_empty()); | |
3773 | assert_eq!(m.into_iter().next(), None); | |
3774 | } | |
3775 | ||
3776 | #[test] | |
3dfed10e | 3777 | #[cfg_attr(miri, ignore)] // FIXME: takes too long |
48663c56 XL |
3778 | fn test_lots_of_insertions() { |
3779 | let mut m = HashMap::new(); | |
3780 | ||
3781 | // Try this a few times to make sure we never screw up the hashmap's | |
3782 | // internal state. | |
3783 | for _ in 0..10 { | |
3784 | assert!(m.is_empty()); | |
3785 | ||
3786 | for i in 1..1001 { | |
3787 | assert!(m.insert(i, i).is_none()); | |
3788 | ||
3789 | for j in 1..=i { | |
3790 | let r = m.get(&j); | |
3791 | assert_eq!(r, Some(&j)); | |
3792 | } | |
3793 | ||
3794 | for j in i + 1..1001 { | |
3795 | let r = m.get(&j); | |
3796 | assert_eq!(r, None); | |
3797 | } | |
3798 | } | |
3799 | ||
3800 | for i in 1001..2001 { | |
3801 | assert!(!m.contains_key(&i)); | |
3802 | } | |
3803 | ||
3804 | // remove forwards | |
3805 | for i in 1..1001 { | |
3806 | assert!(m.remove(&i).is_some()); | |
3807 | ||
3808 | for j in 1..=i { | |
3809 | assert!(!m.contains_key(&j)); | |
3810 | } | |
3811 | ||
3812 | for j in i + 1..1001 { | |
3813 | assert!(m.contains_key(&j)); | |
3814 | } | |
3815 | } | |
3816 | ||
3817 | for i in 1..1001 { | |
3818 | assert!(!m.contains_key(&i)); | |
3819 | } | |
3820 | ||
3821 | for i in 1..1001 { | |
3822 | assert!(m.insert(i, i).is_none()); | |
3823 | } | |
3824 | ||
3825 | // remove backwards | |
3826 | for i in (1..1001).rev() { | |
3827 | assert!(m.remove(&i).is_some()); | |
3828 | ||
3829 | for j in i..1001 { | |
3830 | assert!(!m.contains_key(&j)); | |
3831 | } | |
3832 | ||
3833 | for j in 1..i { | |
3834 | assert!(m.contains_key(&j)); | |
3835 | } | |
3836 | } | |
3837 | } | |
3838 | } | |
3839 | ||
3840 | #[test] | |
3841 | fn test_find_mut() { | |
3842 | let mut m = HashMap::new(); | |
3843 | assert!(m.insert(1, 12).is_none()); | |
3844 | assert!(m.insert(2, 8).is_none()); | |
3845 | assert!(m.insert(5, 14).is_none()); | |
3846 | let new = 100; | |
3847 | match m.get_mut(&5) { | |
3848 | None => panic!(), | |
3849 | Some(x) => *x = new, | |
3850 | } | |
3851 | assert_eq!(m.get(&5), Some(&new)); | |
3852 | } | |
3853 | ||
3854 | #[test] | |
3855 | fn test_insert_overwrite() { | |
3856 | let mut m = HashMap::new(); | |
3857 | assert!(m.insert(1, 2).is_none()); | |
3858 | assert_eq!(*m.get(&1).unwrap(), 2); | |
3859 | assert!(!m.insert(1, 3).is_none()); | |
3860 | assert_eq!(*m.get(&1).unwrap(), 3); | |
3861 | } | |
3862 | ||
3863 | #[test] | |
3864 | fn test_insert_conflicts() { | |
3865 | let mut m = HashMap::with_capacity(4); | |
3866 | assert!(m.insert(1, 2).is_none()); | |
3867 | assert!(m.insert(5, 3).is_none()); | |
3868 | assert!(m.insert(9, 4).is_none()); | |
3869 | assert_eq!(*m.get(&9).unwrap(), 4); | |
3870 | assert_eq!(*m.get(&5).unwrap(), 3); | |
3871 | assert_eq!(*m.get(&1).unwrap(), 2); | |
3872 | } | |
3873 | ||
3874 | #[test] | |
3875 | fn test_conflict_remove() { | |
3876 | let mut m = HashMap::with_capacity(4); | |
3877 | assert!(m.insert(1, 2).is_none()); | |
3878 | assert_eq!(*m.get(&1).unwrap(), 2); | |
3879 | assert!(m.insert(5, 3).is_none()); | |
3880 | assert_eq!(*m.get(&1).unwrap(), 2); | |
3881 | assert_eq!(*m.get(&5).unwrap(), 3); | |
3882 | assert!(m.insert(9, 4).is_none()); | |
3883 | assert_eq!(*m.get(&1).unwrap(), 2); | |
3884 | assert_eq!(*m.get(&5).unwrap(), 3); | |
3885 | assert_eq!(*m.get(&9).unwrap(), 4); | |
3886 | assert!(m.remove(&1).is_some()); | |
3887 | assert_eq!(*m.get(&9).unwrap(), 4); | |
3888 | assert_eq!(*m.get(&5).unwrap(), 3); | |
3889 | } | |
3890 | ||
3891 | #[test] | |
3892 | fn test_is_empty() { | |
3893 | let mut m = HashMap::with_capacity(4); | |
3894 | assert!(m.insert(1, 2).is_none()); | |
3895 | assert!(!m.is_empty()); | |
3896 | assert!(m.remove(&1).is_some()); | |
3897 | assert!(m.is_empty()); | |
3898 | } | |
3899 | ||
3900 | #[test] | |
3901 | fn test_remove() { | |
3902 | let mut m = HashMap::new(); | |
3903 | m.insert(1, 2); | |
3904 | assert_eq!(m.remove(&1), Some(2)); | |
3905 | assert_eq!(m.remove(&1), None); | |
3906 | } | |
3907 | ||
3908 | #[test] | |
3909 | fn test_remove_entry() { | |
3910 | let mut m = HashMap::new(); | |
3911 | m.insert(1, 2); | |
3912 | assert_eq!(m.remove_entry(&1), Some((1, 2))); | |
3913 | assert_eq!(m.remove(&1), None); | |
3914 | } | |
3915 | ||
3916 | #[test] | |
3917 | fn test_iterate() { | |
3918 | let mut m = HashMap::with_capacity(4); | |
3919 | for i in 0..32 { | |
3920 | assert!(m.insert(i, i * 2).is_none()); | |
3921 | } | |
3922 | assert_eq!(m.len(), 32); | |
3923 | ||
3924 | let mut observed: u32 = 0; | |
3925 | ||
3926 | for (k, v) in &m { | |
3927 | assert_eq!(*v, *k * 2); | |
3928 | observed |= 1 << *k; | |
3929 | } | |
3930 | assert_eq!(observed, 0xFFFF_FFFF); | |
3931 | } | |
3932 | ||
3933 | #[test] | |
3934 | fn test_keys() { | |
3935 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
3936 | let map: HashMap<_, _> = vec.into_iter().collect(); | |
3937 | let keys: Vec<_> = map.keys().cloned().collect(); | |
3938 | assert_eq!(keys.len(), 3); | |
3939 | assert!(keys.contains(&1)); | |
3940 | assert!(keys.contains(&2)); | |
3941 | assert!(keys.contains(&3)); | |
3942 | } | |
3943 | ||
3944 | #[test] | |
3945 | fn test_values() { | |
3946 | let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')]; | |
3947 | let map: HashMap<_, _> = vec.into_iter().collect(); | |
3948 | let values: Vec<_> = map.values().cloned().collect(); | |
3949 | assert_eq!(values.len(), 3); | |
3950 | assert!(values.contains(&'a')); | |
3951 | assert!(values.contains(&'b')); | |
3952 | assert!(values.contains(&'c')); | |
3953 | } | |
3954 | ||
3955 | #[test] | |
3956 | fn test_values_mut() { | |
3957 | let vec = vec![(1, 1), (2, 2), (3, 3)]; | |
3958 | let mut map: HashMap<_, _> = vec.into_iter().collect(); | |
3959 | for value in map.values_mut() { | |
3960 | *value = (*value) * 2 | |
3961 | } | |
3962 | let values: Vec<_> = map.values().cloned().collect(); | |
3963 | assert_eq!(values.len(), 3); | |
3964 | assert!(values.contains(&2)); | |
3965 | assert!(values.contains(&4)); | |
3966 | assert!(values.contains(&6)); | |
3967 | } | |
3968 | ||
3969 | #[test] | |
3970 | fn test_find() { | |
3971 | let mut m = HashMap::new(); | |
3972 | assert!(m.get(&1).is_none()); | |
3973 | m.insert(1, 2); | |
3974 | match m.get(&1) { | |
3975 | None => panic!(), | |
3976 | Some(v) => assert_eq!(*v, 2), | |
3977 | } | |
3978 | } | |
3979 | ||
3980 | #[test] | |
3981 | fn test_eq() { | |
3982 | let mut m1 = HashMap::new(); | |
3983 | m1.insert(1, 2); | |
3984 | m1.insert(2, 3); | |
3985 | m1.insert(3, 4); | |
3986 | ||
3987 | let mut m2 = HashMap::new(); | |
3988 | m2.insert(1, 2); | |
3989 | m2.insert(2, 3); | |
3990 | ||
3991 | assert!(m1 != m2); | |
3992 | ||
3993 | m2.insert(3, 4); | |
3994 | ||
3995 | assert_eq!(m1, m2); | |
3996 | } | |
3997 | ||
3998 | #[test] | |
3999 | fn test_show() { | |
4000 | let mut map = HashMap::new(); | |
4001 | let empty: HashMap<i32, i32> = HashMap::new(); | |
4002 | ||
4003 | map.insert(1, 2); | |
4004 | map.insert(3, 4); | |
4005 | ||
4006 | let map_str = format!("{:?}", map); | |
4007 | ||
4008 | assert!(map_str == "{1: 2, 3: 4}" || map_str == "{3: 4, 1: 2}"); | |
4009 | assert_eq!(format!("{:?}", empty), "{}"); | |
4010 | } | |
4011 | ||
4012 | #[test] | |
4013 | fn test_expand() { | |
4014 | let mut m = HashMap::new(); | |
4015 | ||
4016 | assert_eq!(m.len(), 0); | |
4017 | assert!(m.is_empty()); | |
4018 | ||
4019 | let mut i = 0; | |
4020 | let old_raw_cap = m.raw_capacity(); | |
4021 | while old_raw_cap == m.raw_capacity() { | |
4022 | m.insert(i, i); | |
4023 | i += 1; | |
4024 | } | |
4025 | ||
4026 | assert_eq!(m.len(), i); | |
4027 | assert!(!m.is_empty()); | |
4028 | } | |
4029 | ||
4030 | #[test] | |
4031 | fn test_behavior_resize_policy() { | |
4032 | let mut m = HashMap::new(); | |
4033 | ||
4034 | assert_eq!(m.len(), 0); | |
4035 | assert_eq!(m.raw_capacity(), 1); | |
4036 | assert!(m.is_empty()); | |
4037 | ||
4038 | m.insert(0, 0); | |
4039 | m.remove(&0); | |
4040 | assert!(m.is_empty()); | |
4041 | let initial_raw_cap = m.raw_capacity(); | |
4042 | m.reserve(initial_raw_cap); | |
4043 | let raw_cap = m.raw_capacity(); | |
4044 | ||
4045 | assert_eq!(raw_cap, initial_raw_cap * 2); | |
4046 | ||
4047 | let mut i = 0; | |
4048 | for _ in 0..raw_cap * 3 / 4 { | |
4049 | m.insert(i, i); | |
4050 | i += 1; | |
4051 | } | |
4052 | // three quarters full | |
4053 | ||
4054 | assert_eq!(m.len(), i); | |
4055 | assert_eq!(m.raw_capacity(), raw_cap); | |
4056 | ||
4057 | for _ in 0..raw_cap / 4 { | |
4058 | m.insert(i, i); | |
4059 | i += 1; | |
4060 | } | |
4061 | // half full | |
4062 | ||
4063 | let new_raw_cap = m.raw_capacity(); | |
4064 | assert_eq!(new_raw_cap, raw_cap * 2); | |
4065 | ||
4066 | for _ in 0..raw_cap / 2 - 1 { | |
4067 | i -= 1; | |
4068 | m.remove(&i); | |
4069 | assert_eq!(m.raw_capacity(), new_raw_cap); | |
4070 | } | |
4071 | // A little more than one quarter full. | |
4072 | m.shrink_to_fit(); | |
4073 | assert_eq!(m.raw_capacity(), raw_cap); | |
4074 | // again, a little more than half full | |
4075 | for _ in 0..raw_cap / 2 { | |
4076 | i -= 1; | |
4077 | m.remove(&i); | |
4078 | } | |
4079 | m.shrink_to_fit(); | |
4080 | ||
4081 | assert_eq!(m.len(), i); | |
4082 | assert!(!m.is_empty()); | |
4083 | assert_eq!(m.raw_capacity(), initial_raw_cap); | |
4084 | } | |
4085 | ||
4086 | #[test] | |
4087 | fn test_reserve_shrink_to_fit() { | |
4088 | let mut m = HashMap::new(); | |
4089 | m.insert(0, 0); | |
4090 | m.remove(&0); | |
4091 | assert!(m.capacity() >= m.len()); | |
4092 | for i in 0..128 { | |
4093 | m.insert(i, i); | |
4094 | } | |
4095 | m.reserve(256); | |
4096 | ||
4097 | let usable_cap = m.capacity(); | |
4098 | for i in 128..(128 + 256) { | |
4099 | m.insert(i, i); | |
4100 | assert_eq!(m.capacity(), usable_cap); | |
4101 | } | |
4102 | ||
4103 | for i in 100..(128 + 256) { | |
4104 | assert_eq!(m.remove(&i), Some(i)); | |
4105 | } | |
4106 | m.shrink_to_fit(); | |
4107 | ||
4108 | assert_eq!(m.len(), 100); | |
4109 | assert!(!m.is_empty()); | |
4110 | assert!(m.capacity() >= m.len()); | |
4111 | ||
4112 | for i in 0..100 { | |
4113 | assert_eq!(m.remove(&i), Some(i)); | |
4114 | } | |
4115 | m.shrink_to_fit(); | |
4116 | m.insert(0, 0); | |
4117 | ||
4118 | assert_eq!(m.len(), 1); | |
4119 | assert!(m.capacity() >= m.len()); | |
4120 | assert_eq!(m.remove(&0), Some(0)); | |
4121 | } | |
4122 | ||
4123 | #[test] | |
4124 | fn test_from_iter() { | |
3dfed10e | 4125 | let xs = [(1, 1), (2, 2), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; |
48663c56 XL |
4126 | |
4127 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4128 | ||
4129 | for &(k, v) in &xs { | |
4130 | assert_eq!(map.get(&k), Some(&v)); | |
4131 | } | |
3dfed10e XL |
4132 | |
4133 | assert_eq!(map.iter().len(), xs.len() - 1); | |
48663c56 XL |
4134 | } |
4135 | ||
4136 | #[test] | |
4137 | fn test_size_hint() { | |
4138 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
4139 | ||
4140 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4141 | ||
4142 | let mut iter = map.iter(); | |
4143 | ||
4144 | for _ in iter.by_ref().take(3) {} | |
4145 | ||
4146 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
4147 | } | |
4148 | ||
4149 | #[test] | |
4150 | fn test_iter_len() { | |
4151 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
4152 | ||
4153 | let map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4154 | ||
4155 | let mut iter = map.iter(); | |
4156 | ||
4157 | for _ in iter.by_ref().take(3) {} | |
4158 | ||
4159 | assert_eq!(iter.len(), 3); | |
4160 | } | |
4161 | ||
4162 | #[test] | |
4163 | fn test_mut_size_hint() { | |
4164 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
4165 | ||
4166 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4167 | ||
4168 | let mut iter = map.iter_mut(); | |
4169 | ||
4170 | for _ in iter.by_ref().take(3) {} | |
4171 | ||
4172 | assert_eq!(iter.size_hint(), (3, Some(3))); | |
4173 | } | |
4174 | ||
4175 | #[test] | |
4176 | fn test_iter_mut_len() { | |
4177 | let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]; | |
4178 | ||
4179 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4180 | ||
4181 | let mut iter = map.iter_mut(); | |
4182 | ||
4183 | for _ in iter.by_ref().take(3) {} | |
4184 | ||
4185 | assert_eq!(iter.len(), 3); | |
4186 | } | |
4187 | ||
4188 | #[test] | |
4189 | fn test_index() { | |
4190 | let mut map = HashMap::new(); | |
4191 | ||
4192 | map.insert(1, 2); | |
4193 | map.insert(2, 1); | |
4194 | map.insert(3, 4); | |
4195 | ||
4196 | assert_eq!(map[&2], 1); | |
4197 | } | |
4198 | ||
4199 | #[test] | |
4200 | #[should_panic] | |
4201 | fn test_index_nonexistent() { | |
4202 | let mut map = HashMap::new(); | |
4203 | ||
4204 | map.insert(1, 2); | |
4205 | map.insert(2, 1); | |
4206 | map.insert(3, 4); | |
4207 | ||
4208 | map[&4]; | |
4209 | } | |
4210 | ||
4211 | #[test] | |
4212 | fn test_entry() { | |
4213 | let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; | |
4214 | ||
4215 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4216 | ||
4217 | // Existing key (insert) | |
4218 | match map.entry(1) { | |
4219 | Vacant(_) => unreachable!(), | |
4220 | Occupied(mut view) => { | |
4221 | assert_eq!(view.get(), &10); | |
4222 | assert_eq!(view.insert(100), 10); | |
4223 | } | |
4224 | } | |
4225 | assert_eq!(map.get(&1).unwrap(), &100); | |
4226 | assert_eq!(map.len(), 6); | |
4227 | ||
4228 | // Existing key (update) | |
4229 | match map.entry(2) { | |
4230 | Vacant(_) => unreachable!(), | |
4231 | Occupied(mut view) => { | |
4232 | let v = view.get_mut(); | |
4233 | let new_v = (*v) * 10; | |
4234 | *v = new_v; | |
4235 | } | |
4236 | } | |
4237 | assert_eq!(map.get(&2).unwrap(), &200); | |
4238 | assert_eq!(map.len(), 6); | |
4239 | ||
4240 | // Existing key (take) | |
4241 | match map.entry(3) { | |
4242 | Vacant(_) => unreachable!(), | |
4243 | Occupied(view) => { | |
4244 | assert_eq!(view.remove(), 30); | |
4245 | } | |
4246 | } | |
4247 | assert_eq!(map.get(&3), None); | |
4248 | assert_eq!(map.len(), 5); | |
4249 | ||
4250 | // Inexistent key (insert) | |
4251 | match map.entry(10) { | |
4252 | Occupied(_) => unreachable!(), | |
4253 | Vacant(view) => { | |
4254 | assert_eq!(*view.insert(1000), 1000); | |
4255 | } | |
4256 | } | |
4257 | assert_eq!(map.get(&10).unwrap(), &1000); | |
4258 | assert_eq!(map.len(), 6); | |
4259 | } | |
4260 | ||
4261 | #[test] | |
4262 | fn test_entry_take_doesnt_corrupt() { | |
4263 | #![allow(deprecated)] //rand | |
4264 | // Test for #19292 | |
4265 | fn check(m: &HashMap<i32, ()>) { | |
4266 | for k in m.keys() { | |
4267 | assert!(m.contains_key(k), "{} is in keys() but not in the map?", k); | |
4268 | } | |
4269 | } | |
4270 | ||
4271 | let mut m = HashMap::new(); | |
4272 | ||
48663c56 XL |
4273 | let mut rng = { |
4274 | let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; | |
4275 | SmallRng::from_seed(seed) | |
4276 | }; | |
4277 | ||
4278 | // Populate the map with some items. | |
4279 | for _ in 0..50 { | |
4280 | let x = rng.gen_range(-10, 10); | |
4281 | m.insert(x, ()); | |
4282 | } | |
4283 | ||
4284 | for _ in 0..1000 { | |
4285 | let x = rng.gen_range(-10, 10); | |
4286 | match m.entry(x) { | |
4287 | Vacant(_) => {} | |
4288 | Occupied(e) => { | |
4289 | e.remove(); | |
4290 | } | |
4291 | } | |
4292 | ||
4293 | check(&m); | |
4294 | } | |
4295 | } | |
4296 | ||
4297 | #[test] | |
4298 | fn test_extend_ref() { | |
4299 | let mut a = HashMap::new(); | |
4300 | a.insert(1, "one"); | |
4301 | let mut b = HashMap::new(); | |
4302 | b.insert(2, "two"); | |
4303 | b.insert(3, "three"); | |
4304 | ||
4305 | a.extend(&b); | |
4306 | ||
4307 | assert_eq!(a.len(), 3); | |
4308 | assert_eq!(a[&1], "one"); | |
4309 | assert_eq!(a[&2], "two"); | |
4310 | assert_eq!(a[&3], "three"); | |
4311 | } | |
4312 | ||
4313 | #[test] | |
4314 | fn test_capacity_not_less_than_len() { | |
4315 | let mut a = HashMap::new(); | |
4316 | let mut item = 0; | |
4317 | ||
4318 | for _ in 0..116 { | |
4319 | a.insert(item, 0); | |
4320 | item += 1; | |
4321 | } | |
4322 | ||
4323 | assert!(a.capacity() > a.len()); | |
4324 | ||
4325 | let free = a.capacity() - a.len(); | |
4326 | for _ in 0..free { | |
4327 | a.insert(item, 0); | |
4328 | item += 1; | |
4329 | } | |
4330 | ||
4331 | assert_eq!(a.len(), a.capacity()); | |
4332 | ||
4333 | // Insert at capacity should cause allocation. | |
4334 | a.insert(item, 0); | |
4335 | assert!(a.capacity() > a.len()); | |
4336 | } | |
4337 | ||
4338 | #[test] | |
4339 | fn test_occupied_entry_key() { | |
4340 | let mut a = HashMap::new(); | |
4341 | let key = "hello there"; | |
4342 | let value = "value goes here"; | |
4343 | assert!(a.is_empty()); | |
4344 | a.insert(key.clone(), value.clone()); | |
4345 | assert_eq!(a.len(), 1); | |
4346 | assert_eq!(a[key], value); | |
4347 | ||
4348 | match a.entry(key.clone()) { | |
4349 | Vacant(_) => panic!(), | |
4350 | Occupied(e) => assert_eq!(key, *e.key()), | |
4351 | } | |
4352 | assert_eq!(a.len(), 1); | |
4353 | assert_eq!(a[key], value); | |
4354 | } | |
4355 | ||
4356 | #[test] | |
4357 | fn test_vacant_entry_key() { | |
4358 | let mut a = HashMap::new(); | |
4359 | let key = "hello there"; | |
4360 | let value = "value goes here"; | |
4361 | ||
4362 | assert!(a.is_empty()); | |
4363 | match a.entry(key.clone()) { | |
4364 | Occupied(_) => panic!(), | |
4365 | Vacant(e) => { | |
4366 | assert_eq!(key, *e.key()); | |
4367 | e.insert(value.clone()); | |
4368 | } | |
4369 | } | |
4370 | assert_eq!(a.len(), 1); | |
4371 | assert_eq!(a[key], value); | |
4372 | } | |
4373 | ||
1b1a35ee XL |
4374 | #[test] |
4375 | fn test_occupied_entry_replace_entry_with() { | |
4376 | let mut a = HashMap::new(); | |
4377 | ||
4378 | let key = "a key"; | |
4379 | let value = "an initial value"; | |
4380 | let new_value = "a new value"; | |
4381 | ||
4382 | let entry = a.entry(key).insert(value).replace_entry_with(|k, v| { | |
4383 | assert_eq!(k, &key); | |
4384 | assert_eq!(v, value); | |
4385 | Some(new_value) | |
4386 | }); | |
4387 | ||
4388 | match entry { | |
4389 | Occupied(e) => { | |
4390 | assert_eq!(e.key(), &key); | |
4391 | assert_eq!(e.get(), &new_value); | |
4392 | } | |
4393 | Vacant(_) => panic!(), | |
4394 | } | |
4395 | ||
4396 | assert_eq!(a[key], new_value); | |
4397 | assert_eq!(a.len(), 1); | |
4398 | ||
4399 | let entry = match a.entry(key) { | |
4400 | Occupied(e) => e.replace_entry_with(|k, v| { | |
4401 | assert_eq!(k, &key); | |
4402 | assert_eq!(v, new_value); | |
4403 | None | |
4404 | }), | |
4405 | Vacant(_) => panic!(), | |
4406 | }; | |
4407 | ||
4408 | match entry { | |
4409 | Vacant(e) => assert_eq!(e.key(), &key), | |
4410 | Occupied(_) => panic!(), | |
4411 | } | |
4412 | ||
4413 | assert!(!a.contains_key(key)); | |
4414 | assert_eq!(a.len(), 0); | |
4415 | } | |
4416 | ||
4417 | #[test] | |
4418 | fn test_entry_and_replace_entry_with() { | |
4419 | let mut a = HashMap::new(); | |
4420 | ||
4421 | let key = "a key"; | |
4422 | let value = "an initial value"; | |
4423 | let new_value = "a new value"; | |
4424 | ||
4425 | let entry = a.entry(key).and_replace_entry_with(|_, _| panic!()); | |
4426 | ||
4427 | match entry { | |
4428 | Vacant(e) => assert_eq!(e.key(), &key), | |
4429 | Occupied(_) => panic!(), | |
4430 | } | |
4431 | ||
4432 | a.insert(key, value); | |
4433 | ||
4434 | let entry = a.entry(key).and_replace_entry_with(|k, v| { | |
4435 | assert_eq!(k, &key); | |
4436 | assert_eq!(v, value); | |
4437 | Some(new_value) | |
4438 | }); | |
4439 | ||
4440 | match entry { | |
4441 | Occupied(e) => { | |
4442 | assert_eq!(e.key(), &key); | |
4443 | assert_eq!(e.get(), &new_value); | |
4444 | } | |
4445 | Vacant(_) => panic!(), | |
4446 | } | |
4447 | ||
4448 | assert_eq!(a[key], new_value); | |
4449 | assert_eq!(a.len(), 1); | |
4450 | ||
4451 | let entry = a.entry(key).and_replace_entry_with(|k, v| { | |
4452 | assert_eq!(k, &key); | |
4453 | assert_eq!(v, new_value); | |
4454 | None | |
4455 | }); | |
4456 | ||
4457 | match entry { | |
4458 | Vacant(e) => assert_eq!(e.key(), &key), | |
4459 | Occupied(_) => panic!(), | |
4460 | } | |
4461 | ||
4462 | assert!(!a.contains_key(key)); | |
4463 | assert_eq!(a.len(), 0); | |
4464 | } | |
4465 | ||
4466 | #[test] | |
4467 | fn test_raw_occupied_entry_replace_entry_with() { | |
4468 | let mut a = HashMap::new(); | |
4469 | ||
4470 | let key = "a key"; | |
4471 | let value = "an initial value"; | |
4472 | let new_value = "a new value"; | |
4473 | ||
4474 | let entry = a | |
4475 | .raw_entry_mut() | |
4476 | .from_key(&key) | |
4477 | .insert(key, value) | |
4478 | .replace_entry_with(|k, v| { | |
4479 | assert_eq!(k, &key); | |
4480 | assert_eq!(v, value); | |
4481 | Some(new_value) | |
4482 | }); | |
4483 | ||
4484 | match entry { | |
4485 | RawEntryMut::Occupied(e) => { | |
4486 | assert_eq!(e.key(), &key); | |
4487 | assert_eq!(e.get(), &new_value); | |
4488 | } | |
4489 | RawEntryMut::Vacant(_) => panic!(), | |
4490 | } | |
4491 | ||
4492 | assert_eq!(a[key], new_value); | |
4493 | assert_eq!(a.len(), 1); | |
4494 | ||
4495 | let entry = match a.raw_entry_mut().from_key(&key) { | |
4496 | RawEntryMut::Occupied(e) => e.replace_entry_with(|k, v| { | |
4497 | assert_eq!(k, &key); | |
4498 | assert_eq!(v, new_value); | |
4499 | None | |
4500 | }), | |
4501 | RawEntryMut::Vacant(_) => panic!(), | |
4502 | }; | |
4503 | ||
4504 | match entry { | |
4505 | RawEntryMut::Vacant(_) => {} | |
4506 | RawEntryMut::Occupied(_) => panic!(), | |
4507 | } | |
4508 | ||
4509 | assert!(!a.contains_key(key)); | |
4510 | assert_eq!(a.len(), 0); | |
4511 | } | |
4512 | ||
4513 | #[test] | |
4514 | fn test_raw_entry_and_replace_entry_with() { | |
4515 | let mut a = HashMap::new(); | |
4516 | ||
4517 | let key = "a key"; | |
4518 | let value = "an initial value"; | |
4519 | let new_value = "a new value"; | |
4520 | ||
4521 | let entry = a | |
4522 | .raw_entry_mut() | |
4523 | .from_key(&key) | |
4524 | .and_replace_entry_with(|_, _| panic!()); | |
4525 | ||
4526 | match entry { | |
4527 | RawEntryMut::Vacant(_) => {} | |
4528 | RawEntryMut::Occupied(_) => panic!(), | |
4529 | } | |
4530 | ||
4531 | a.insert(key, value); | |
4532 | ||
4533 | let entry = a | |
4534 | .raw_entry_mut() | |
4535 | .from_key(&key) | |
4536 | .and_replace_entry_with(|k, v| { | |
4537 | assert_eq!(k, &key); | |
4538 | assert_eq!(v, value); | |
4539 | Some(new_value) | |
4540 | }); | |
4541 | ||
4542 | match entry { | |
4543 | RawEntryMut::Occupied(e) => { | |
4544 | assert_eq!(e.key(), &key); | |
4545 | assert_eq!(e.get(), &new_value); | |
4546 | } | |
4547 | RawEntryMut::Vacant(_) => panic!(), | |
4548 | } | |
4549 | ||
4550 | assert_eq!(a[key], new_value); | |
4551 | assert_eq!(a.len(), 1); | |
4552 | ||
4553 | let entry = a | |
4554 | .raw_entry_mut() | |
4555 | .from_key(&key) | |
4556 | .and_replace_entry_with(|k, v| { | |
4557 | assert_eq!(k, &key); | |
4558 | assert_eq!(v, new_value); | |
4559 | None | |
4560 | }); | |
4561 | ||
4562 | match entry { | |
4563 | RawEntryMut::Vacant(_) => {} | |
4564 | RawEntryMut::Occupied(_) => panic!(), | |
4565 | } | |
4566 | ||
4567 | assert!(!a.contains_key(key)); | |
4568 | assert_eq!(a.len(), 0); | |
4569 | } | |
4570 | ||
4571 | #[test] | |
4572 | fn test_replace_entry_with_doesnt_corrupt() { | |
4573 | #![allow(deprecated)] //rand | |
4574 | // Test for #19292 | |
4575 | fn check(m: &HashMap<i32, ()>) { | |
4576 | for k in m.keys() { | |
4577 | assert!(m.contains_key(k), "{} is in keys() but not in the map?", k); | |
4578 | } | |
4579 | } | |
4580 | ||
4581 | let mut m = HashMap::new(); | |
4582 | ||
4583 | let mut rng = { | |
4584 | let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; | |
4585 | SmallRng::from_seed(seed) | |
4586 | }; | |
4587 | ||
4588 | // Populate the map with some items. | |
4589 | for _ in 0..50 { | |
4590 | let x = rng.gen_range(-10, 10); | |
4591 | m.insert(x, ()); | |
4592 | } | |
4593 | ||
4594 | for _ in 0..1000 { | |
4595 | let x = rng.gen_range(-10, 10); | |
4596 | m.entry(x).and_replace_entry_with(|_, _| None); | |
4597 | check(&m); | |
4598 | } | |
4599 | } | |
4600 | ||
48663c56 XL |
4601 | #[test] |
4602 | fn test_retain() { | |
4603 | let mut map: HashMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect(); | |
4604 | ||
4605 | map.retain(|&k, _| k % 2 == 0); | |
4606 | assert_eq!(map.len(), 50); | |
4607 | assert_eq!(map[&2], 20); | |
4608 | assert_eq!(map[&4], 40); | |
4609 | assert_eq!(map[&6], 60); | |
4610 | } | |
4611 | ||
4612 | #[test] | |
3dfed10e XL |
4613 | fn test_drain_filter() { |
4614 | { | |
4615 | let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x * 10)).collect(); | |
4616 | let drained = map.drain_filter(|&k, _| k % 2 == 0); | |
4617 | let mut out = drained.collect::<Vec<_>>(); | |
4618 | out.sort_unstable(); | |
1b1a35ee | 4619 | assert_eq!(vec![(0, 0), (2, 20), (4, 40), (6, 60)], out); |
3dfed10e XL |
4620 | assert_eq!(map.len(), 4); |
4621 | } | |
4622 | { | |
4623 | let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x * 10)).collect(); | |
4624 | drop(map.drain_filter(|&k, _| k % 2 == 0)); | |
4625 | assert_eq!(map.len(), 4); | |
4626 | } | |
4627 | } | |
4628 | ||
4629 | #[test] | |
4630 | #[cfg_attr(miri, ignore)] // FIXME: no OOM signalling (https://github.com/rust-lang/miri/issues/613) | |
48663c56 XL |
4631 | fn test_try_reserve() { |
4632 | let mut empty_bytes: HashMap<u8, u8> = HashMap::new(); | |
4633 | ||
4634 | const MAX_USIZE: usize = usize::MAX; | |
4635 | ||
4636 | if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) { | |
4637 | } else { | |
4638 | panic!("usize::MAX should trigger an overflow!"); | |
4639 | } | |
4640 | ||
3dfed10e | 4641 | if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 8) { |
48663c56 XL |
4642 | } else { |
4643 | // This may succeed if there is enough free memory. Attempt to | |
4644 | // allocate a second hashmap to ensure the allocation will fail. | |
4645 | let mut empty_bytes2: HashMap<u8, u8> = HashMap::new(); | |
3dfed10e | 4646 | if let Err(AllocError { .. }) = empty_bytes2.try_reserve(MAX_USIZE / 8) { |
48663c56 XL |
4647 | } else { |
4648 | panic!("usize::MAX / 8 should trigger an OOM!"); | |
4649 | } | |
4650 | } | |
4651 | } | |
4652 | ||
4653 | #[test] | |
4654 | fn test_raw_entry() { | |
4655 | use super::RawEntryMut::{Occupied, Vacant}; | |
4656 | ||
4657 | let xs = [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; | |
4658 | ||
4659 | let mut map: HashMap<_, _> = xs.iter().cloned().collect(); | |
4660 | ||
4661 | let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 { | |
6a06907d | 4662 | super::make_insert_hash::<i32, _>(map.hasher(), &k) |
48663c56 XL |
4663 | }; |
4664 | ||
4665 | // Existing key (insert) | |
4666 | match map.raw_entry_mut().from_key(&1) { | |
4667 | Vacant(_) => unreachable!(), | |
4668 | Occupied(mut view) => { | |
4669 | assert_eq!(view.get(), &10); | |
4670 | assert_eq!(view.insert(100), 10); | |
4671 | } | |
4672 | } | |
4673 | let hash1 = compute_hash(&map, 1); | |
4674 | assert_eq!(map.raw_entry().from_key(&1).unwrap(), (&1, &100)); | |
4675 | assert_eq!( | |
4676 | map.raw_entry().from_hash(hash1, |k| *k == 1).unwrap(), | |
4677 | (&1, &100) | |
4678 | ); | |
4679 | assert_eq!( | |
4680 | map.raw_entry().from_key_hashed_nocheck(hash1, &1).unwrap(), | |
4681 | (&1, &100) | |
4682 | ); | |
4683 | assert_eq!(map.len(), 6); | |
4684 | ||
4685 | // Existing key (update) | |
4686 | match map.raw_entry_mut().from_key(&2) { | |
4687 | Vacant(_) => unreachable!(), | |
4688 | Occupied(mut view) => { | |
4689 | let v = view.get_mut(); | |
4690 | let new_v = (*v) * 10; | |
4691 | *v = new_v; | |
4692 | } | |
4693 | } | |
4694 | let hash2 = compute_hash(&map, 2); | |
4695 | assert_eq!(map.raw_entry().from_key(&2).unwrap(), (&2, &200)); | |
4696 | assert_eq!( | |
4697 | map.raw_entry().from_hash(hash2, |k| *k == 2).unwrap(), | |
4698 | (&2, &200) | |
4699 | ); | |
4700 | assert_eq!( | |
4701 | map.raw_entry().from_key_hashed_nocheck(hash2, &2).unwrap(), | |
4702 | (&2, &200) | |
4703 | ); | |
4704 | assert_eq!(map.len(), 6); | |
4705 | ||
4706 | // Existing key (take) | |
4707 | let hash3 = compute_hash(&map, 3); | |
4708 | match map.raw_entry_mut().from_key_hashed_nocheck(hash3, &3) { | |
4709 | Vacant(_) => unreachable!(), | |
4710 | Occupied(view) => { | |
4711 | assert_eq!(view.remove_entry(), (3, 30)); | |
4712 | } | |
4713 | } | |
4714 | assert_eq!(map.raw_entry().from_key(&3), None); | |
4715 | assert_eq!(map.raw_entry().from_hash(hash3, |k| *k == 3), None); | |
4716 | assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash3, &3), None); | |
4717 | assert_eq!(map.len(), 5); | |
4718 | ||
4719 | // Nonexistent key (insert) | |
4720 | match map.raw_entry_mut().from_key(&10) { | |
4721 | Occupied(_) => unreachable!(), | |
4722 | Vacant(view) => { | |
4723 | assert_eq!(view.insert(10, 1000), (&mut 10, &mut 1000)); | |
4724 | } | |
4725 | } | |
4726 | assert_eq!(map.raw_entry().from_key(&10).unwrap(), (&10, &1000)); | |
4727 | assert_eq!(map.len(), 6); | |
4728 | ||
4729 | // Ensure all lookup methods produce equivalent results. | |
4730 | for k in 0..12 { | |
4731 | let hash = compute_hash(&map, k); | |
4732 | let v = map.get(&k).cloned(); | |
4733 | let kv = v.as_ref().map(|v| (&k, v)); | |
4734 | ||
4735 | assert_eq!(map.raw_entry().from_key(&k), kv); | |
4736 | assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv); | |
4737 | assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv); | |
4738 | ||
4739 | match map.raw_entry_mut().from_key(&k) { | |
4740 | Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv), | |
4741 | Vacant(_) => assert_eq!(v, None), | |
4742 | } | |
4743 | match map.raw_entry_mut().from_key_hashed_nocheck(hash, &k) { | |
4744 | Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv), | |
4745 | Vacant(_) => assert_eq!(v, None), | |
4746 | } | |
4747 | match map.raw_entry_mut().from_hash(hash, |q| *q == k) { | |
4748 | Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv), | |
4749 | Vacant(_) => assert_eq!(v, None), | |
4750 | } | |
4751 | } | |
4752 | } | |
4753 | ||
4754 | #[test] | |
4755 | fn test_key_without_hash_impl() { | |
4756 | #[derive(Debug)] | |
4757 | struct IntWrapper(u64); | |
4758 | ||
3dfed10e | 4759 | let mut m: HashMap<IntWrapper, (), ()> = HashMap::default(); |
48663c56 XL |
4760 | { |
4761 | assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none()); | |
4762 | } | |
4763 | { | |
4764 | let vacant_entry = match m.raw_entry_mut().from_hash(0, |k| k.0 == 0) { | |
4765 | RawEntryMut::Occupied(..) => panic!("Found entry for key 0"), | |
4766 | RawEntryMut::Vacant(e) => e, | |
4767 | }; | |
4768 | vacant_entry.insert_with_hasher(0, IntWrapper(0), (), |k| k.0); | |
4769 | } | |
4770 | { | |
4771 | assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_some()); | |
4772 | assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_none()); | |
4773 | assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none()); | |
4774 | } | |
4775 | { | |
4776 | let vacant_entry = match m.raw_entry_mut().from_hash(1, |k| k.0 == 1) { | |
4777 | RawEntryMut::Occupied(..) => panic!("Found entry for key 1"), | |
4778 | RawEntryMut::Vacant(e) => e, | |
4779 | }; | |
4780 | vacant_entry.insert_with_hasher(1, IntWrapper(1), (), |k| k.0); | |
4781 | } | |
4782 | { | |
4783 | assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_some()); | |
4784 | assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_some()); | |
4785 | assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none()); | |
4786 | } | |
4787 | { | |
4788 | let occupied_entry = match m.raw_entry_mut().from_hash(0, |k| k.0 == 0) { | |
4789 | RawEntryMut::Occupied(e) => e, | |
4790 | RawEntryMut::Vacant(..) => panic!("Couldn't find entry for key 0"), | |
4791 | }; | |
4792 | occupied_entry.remove(); | |
4793 | } | |
4794 | assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none()); | |
4795 | assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_some()); | |
4796 | assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none()); | |
4797 | } | |
3dfed10e XL |
4798 | |
4799 | #[test] | |
4800 | #[cfg(feature = "raw")] | |
4801 | fn test_into_iter_refresh() { | |
4802 | use core::hash::{BuildHasher, Hash, Hasher}; | |
4803 | ||
4804 | #[cfg(miri)] | |
4805 | const N: usize = 32; | |
4806 | #[cfg(not(miri))] | |
4807 | const N: usize = 128; | |
4808 | ||
4809 | let mut rng = rand::thread_rng(); | |
4810 | for n in 0..N { | |
4811 | let mut m = HashMap::new(); | |
4812 | for i in 0..n { | |
4813 | assert!(m.insert(i, 2 * i).is_none()); | |
4814 | } | |
4815 | let hasher = m.hasher().clone(); | |
4816 | ||
4817 | let mut it = unsafe { m.table.iter() }; | |
4818 | assert_eq!(it.len(), n); | |
4819 | ||
4820 | let mut i = 0; | |
4821 | let mut left = n; | |
4822 | let mut removed = Vec::new(); | |
4823 | loop { | |
4824 | // occasionally remove some elements | |
4825 | if i < n && rng.gen_bool(0.1) { | |
4826 | let mut hsh = hasher.build_hasher(); | |
4827 | i.hash(&mut hsh); | |
4828 | let hash = hsh.finish(); | |
4829 | ||
4830 | unsafe { | |
4831 | let e = m.table.find(hash, |q| q.0.eq(&i)); | |
4832 | if let Some(e) = e { | |
4833 | it.reflect_remove(&e); | |
4834 | let t = m.table.remove(e); | |
4835 | removed.push(t); | |
4836 | left -= 1; | |
4837 | } else { | |
4838 | assert!(removed.contains(&(i, 2 * i)), "{} not in {:?}", i, removed); | |
6a06907d XL |
4839 | let e = m.table.insert( |
4840 | hash, | |
4841 | (i, 2 * i), | |
4842 | super::make_hasher::<usize, _, usize, _>(&hasher), | |
4843 | ); | |
3dfed10e XL |
4844 | it.reflect_insert(&e); |
4845 | if let Some(p) = removed.iter().position(|e| e == &(i, 2 * i)) { | |
4846 | removed.swap_remove(p); | |
4847 | } | |
4848 | left += 1; | |
4849 | } | |
4850 | } | |
4851 | } | |
4852 | ||
4853 | let e = it.next(); | |
4854 | if e.is_none() { | |
4855 | break; | |
4856 | } | |
4857 | assert!(i < n); | |
4858 | let t = unsafe { e.unwrap().as_ref() }; | |
4859 | assert!(!removed.contains(t)); | |
4860 | let (k, v) = t; | |
4861 | assert_eq!(*v, 2 * k); | |
4862 | i += 1; | |
4863 | } | |
4864 | assert!(i <= n); | |
4865 | ||
4866 | // just for safety: | |
4867 | assert_eq!(m.table.len(), left); | |
4868 | } | |
4869 | } | |
1b1a35ee XL |
4870 | |
4871 | #[test] | |
4872 | fn test_const_with_hasher() { | |
4873 | use core::hash::BuildHasher; | |
1b1a35ee XL |
4874 | use std::collections::hash_map::DefaultHasher; |
4875 | ||
4876 | #[derive(Clone)] | |
4877 | struct MyHasher; | |
4878 | impl BuildHasher for MyHasher { | |
4879 | type Hasher = DefaultHasher; | |
4880 | ||
4881 | fn build_hasher(&self) -> DefaultHasher { | |
4882 | DefaultHasher::new() | |
4883 | } | |
4884 | } | |
4885 | ||
4886 | const EMPTY_MAP: HashMap<u32, std::string::String, MyHasher> = | |
4887 | HashMap::with_hasher(MyHasher); | |
4888 | ||
4889 | let mut map = EMPTY_MAP.clone(); | |
4890 | map.insert(17, "seventeen".to_owned()); | |
4891 | assert_eq!("seventeen", map[&17]); | |
4892 | } | |
6a06907d XL |
4893 | |
4894 | #[test] | |
4895 | #[cfg(feature = "nightly")] | |
4896 | fn test_get_each_mut() { | |
4897 | use crate::UnavailableMutError::*; | |
4898 | ||
4899 | let mut map = HashMap::new(); | |
4900 | map.insert("foo".to_owned(), 0); | |
4901 | map.insert("bar".to_owned(), 10); | |
4902 | map.insert("baz".to_owned(), 20); | |
4903 | map.insert("qux".to_owned(), 30); | |
4904 | ||
4905 | let xs = map.get_each_mut(["foo", "dud", "foo", "qux"]); | |
4906 | assert_eq!( | |
4907 | xs, | |
4908 | [Ok(&mut 0), Err(Absent), Err(Duplicate(0)), Ok(&mut 30)] | |
4909 | ); | |
4910 | ||
4911 | let ys = map.get_each_key_value_mut(["bar", "baz", "baz", "dip"]); | |
4912 | assert_eq!( | |
4913 | ys, | |
4914 | [ | |
4915 | Ok((&"bar".to_owned(), &mut 10)), | |
4916 | Ok((&"baz".to_owned(), &mut 20)), | |
4917 | Err(Duplicate(1)), | |
4918 | Err(Absent), | |
4919 | ] | |
4920 | ); | |
4921 | } | |
48663c56 | 4922 | } |