1 | use self::RustcEntry::*; |
2 | use crate::map::{make_hash, Drain, HashMap, IntoIter, Iter, IterMut}; |
3 | use crate::raw::{Allocator, Bucket, Global, RawTable}; |
4 | use core::fmt::{self, Debug}; |
5 | use core::hash::{BuildHasher, Hash}; |
6 | use core::mem; |
7 | |
8 | impl<K, V, S, A> HashMap<K, V, S, A> |
9 | where |
10 | K: Eq + Hash, |
11 | S: BuildHasher, |
12 | A: Allocator, |
13 | { |
14 | /// Gets the given key's corresponding entry in the map for in-place manipulation. |
15 | /// |
16 | /// # Examples |
17 | /// |
18 | /// ``` |
19 | /// use hashbrown::HashMap; |
20 | /// |
21 | /// let mut letters = HashMap::new(); |
22 | /// |
23 | /// for ch in "a short treatise on fungi" .chars() { |
24 | /// let counter = letters.rustc_entry(ch).or_insert(0); |
25 | /// *counter += 1; |
26 | /// } |
27 | /// |
28 | /// assert_eq!(letters[&'s' ], 2); |
29 | /// assert_eq!(letters[&'t' ], 3); |
30 | /// assert_eq!(letters[&'u' ], 1); |
31 | /// assert_eq!(letters.get(&'y' ), None); |
32 | /// ``` |
33 | #[cfg_attr (feature = "inline-more" , inline)] |
34 | pub fn rustc_entry(&mut self, key: K) -> RustcEntry<'_, K, V, A> { |
35 | let hash = make_hash(&self.hash_builder, &key); |
36 | if let Some(elem) = self.table.find(hash, |q| q.0.eq(&key)) { |
37 | RustcEntry::Occupied(RustcOccupiedEntry { |
38 | elem, |
39 | table: &mut self.table, |
40 | }) |
41 | } else { |
42 | // Ideally we would put this in VacantEntry::insert, but Entry is not |
43 | // generic over the BuildHasher and adding a generic parameter would be |
44 | // a breaking change. |
45 | self.reserve(1); |
46 | |
47 | RustcEntry::Vacant(RustcVacantEntry { |
48 | hash, |
49 | key, |
50 | table: &mut self.table, |
51 | }) |
52 | } |
53 | } |
54 | } |
55 | |
56 | /// A view into a single entry in a map, which may either be vacant or occupied. |
57 | /// |
58 | /// This `enum` is constructed from the [`rustc_entry`] method on [`HashMap`]. |
59 | /// |
60 | /// [`HashMap`]: struct.HashMap.html |
61 | /// [`rustc_entry`]: struct.HashMap.html#method.rustc_entry |
62 | pub enum RustcEntry<'a, K, V, A = Global> |
63 | where |
64 | A: Allocator, |
65 | { |
66 | /// An occupied entry. |
67 | Occupied(RustcOccupiedEntry<'a, K, V, A>), |
68 | |
69 | /// A vacant entry. |
70 | Vacant(RustcVacantEntry<'a, K, V, A>), |
71 | } |
72 | |
73 | impl<K: Debug, V: Debug, A: Allocator> Debug for RustcEntry<'_, K, V, A> { |
74 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
75 | match *self { |
76 | Vacant(ref v: &RustcVacantEntry<'_, K, V, …>) => f.debug_tuple(name:"Entry" ).field(v).finish(), |
77 | Occupied(ref o: &RustcOccupiedEntry<'_, K, …, …>) => f.debug_tuple(name:"Entry" ).field(o).finish(), |
78 | } |
79 | } |
80 | } |
81 | |
82 | /// A view into an occupied entry in a `HashMap`. |
83 | /// It is part of the [`RustcEntry`] enum. |
84 | /// |
85 | /// [`RustcEntry`]: enum.RustcEntry.html |
86 | pub struct RustcOccupiedEntry<'a, K, V, A = Global> |
87 | where |
88 | A: Allocator, |
89 | { |
90 | elem: Bucket<(K, V)>, |
91 | table: &'a mut RawTable<(K, V), A>, |
92 | } |
93 | |
94 | unsafe impl<K, V, A> Send for RustcOccupiedEntry<'_, K, V, A> |
95 | where |
96 | K: Send, |
97 | V: Send, |
98 | A: Allocator + Send, |
99 | { |
100 | } |
101 | unsafe impl<K, V, A> Sync for RustcOccupiedEntry<'_, K, V, A> |
102 | where |
103 | K: Sync, |
104 | V: Sync, |
105 | A: Allocator + Sync, |
106 | { |
107 | } |
108 | |
109 | impl<K: Debug, V: Debug, A: Allocator> Debug for RustcOccupiedEntry<'_, K, V, A> { |
110 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
111 | f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry" ) |
112 | .field("key" , self.key()) |
113 | .field(name:"value" , self.get()) |
114 | .finish() |
115 | } |
116 | } |
117 | |
118 | /// A view into a vacant entry in a `HashMap`. |
119 | /// It is part of the [`RustcEntry`] enum. |
120 | /// |
121 | /// [`RustcEntry`]: enum.RustcEntry.html |
122 | pub struct RustcVacantEntry<'a, K, V, A = Global> |
123 | where |
124 | A: Allocator, |
125 | { |
126 | hash: u64, |
127 | key: K, |
128 | table: &'a mut RawTable<(K, V), A>, |
129 | } |
130 | |
131 | impl<K: Debug, V, A: Allocator> Debug for RustcVacantEntry<'_, K, V, A> { |
132 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
133 | f.debug_tuple(name:"VacantEntry" ).field(self.key()).finish() |
134 | } |
135 | } |
136 | |
137 | impl<'a, K, V, A: Allocator> RustcEntry<'a, K, V, A> { |
138 | /// Sets the value of the entry, and returns a RustcOccupiedEntry. |
139 | /// |
140 | /// # Examples |
141 | /// |
142 | /// ``` |
143 | /// use hashbrown::HashMap; |
144 | /// |
145 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
146 | /// let entry = map.rustc_entry("horseyland" ).insert(37); |
147 | /// |
148 | /// assert_eq!(entry.key(), &"horseyland" ); |
149 | /// ``` |
150 | pub fn insert(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> { |
151 | match self { |
152 | Vacant(entry) => entry.insert_entry(value), |
153 | Occupied(mut entry) => { |
154 | entry.insert(value); |
155 | entry |
156 | } |
157 | } |
158 | } |
159 | |
160 | /// Ensures a value is in the entry by inserting the default if empty, and returns |
161 | /// a mutable reference to the value in the entry. |
162 | /// |
163 | /// # Examples |
164 | /// |
165 | /// ``` |
166 | /// use hashbrown::HashMap; |
167 | /// |
168 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
169 | /// |
170 | /// map.rustc_entry("poneyland" ).or_insert(3); |
171 | /// assert_eq!(map["poneyland" ], 3); |
172 | /// |
173 | /// *map.rustc_entry("poneyland" ).or_insert(10) *= 2; |
174 | /// assert_eq!(map["poneyland" ], 6); |
175 | /// ``` |
176 | #[cfg_attr (feature = "inline-more" , inline)] |
177 | pub fn or_insert(self, default: V) -> &'a mut V |
178 | where |
179 | K: Hash, |
180 | { |
181 | match self { |
182 | Occupied(entry) => entry.into_mut(), |
183 | Vacant(entry) => entry.insert(default), |
184 | } |
185 | } |
186 | |
187 | /// Ensures a value is in the entry by inserting the result of the default function if empty, |
188 | /// and returns a mutable reference to the value in the entry. |
189 | /// |
190 | /// # Examples |
191 | /// |
192 | /// ``` |
193 | /// use hashbrown::HashMap; |
194 | /// |
195 | /// let mut map: HashMap<&str, String> = HashMap::new(); |
196 | /// let s = "hoho" .to_string(); |
197 | /// |
198 | /// map.rustc_entry("poneyland" ).or_insert_with(|| s); |
199 | /// |
200 | /// assert_eq!(map["poneyland" ], "hoho" .to_string()); |
201 | /// ``` |
202 | #[cfg_attr (feature = "inline-more" , inline)] |
203 | pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V |
204 | where |
205 | K: Hash, |
206 | { |
207 | match self { |
208 | Occupied(entry) => entry.into_mut(), |
209 | Vacant(entry) => entry.insert(default()), |
210 | } |
211 | } |
212 | |
213 | /// Returns a reference to this entry's key. |
214 | /// |
215 | /// # Examples |
216 | /// |
217 | /// ``` |
218 | /// use hashbrown::HashMap; |
219 | /// |
220 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
221 | /// assert_eq!(map.rustc_entry("poneyland" ).key(), &"poneyland" ); |
222 | /// ``` |
223 | #[cfg_attr (feature = "inline-more" , inline)] |
224 | pub fn key(&self) -> &K { |
225 | match *self { |
226 | Occupied(ref entry) => entry.key(), |
227 | Vacant(ref entry) => entry.key(), |
228 | } |
229 | } |
230 | |
231 | /// Provides in-place mutable access to an occupied entry before any |
232 | /// potential inserts into the map. |
233 | /// |
234 | /// # Examples |
235 | /// |
236 | /// ``` |
237 | /// use hashbrown::HashMap; |
238 | /// |
239 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
240 | /// |
241 | /// map.rustc_entry("poneyland" ) |
242 | /// .and_modify(|e| { *e += 1 }) |
243 | /// .or_insert(42); |
244 | /// assert_eq!(map["poneyland" ], 42); |
245 | /// |
246 | /// map.rustc_entry("poneyland" ) |
247 | /// .and_modify(|e| { *e += 1 }) |
248 | /// .or_insert(42); |
249 | /// assert_eq!(map["poneyland" ], 43); |
250 | /// ``` |
251 | #[cfg_attr (feature = "inline-more" , inline)] |
252 | pub fn and_modify<F>(self, f: F) -> Self |
253 | where |
254 | F: FnOnce(&mut V), |
255 | { |
256 | match self { |
257 | Occupied(mut entry) => { |
258 | f(entry.get_mut()); |
259 | Occupied(entry) |
260 | } |
261 | Vacant(entry) => Vacant(entry), |
262 | } |
263 | } |
264 | } |
265 | |
266 | impl<'a, K, V: Default, A: Allocator> RustcEntry<'a, K, V, A> { |
267 | /// Ensures a value is in the entry by inserting the default value if empty, |
268 | /// and returns a mutable reference to the value in the entry. |
269 | /// |
270 | /// # Examples |
271 | /// |
272 | /// ``` |
273 | /// # fn main() { |
274 | /// use hashbrown::HashMap; |
275 | /// |
276 | /// let mut map: HashMap<&str, Option<u32>> = HashMap::new(); |
277 | /// map.rustc_entry("poneyland" ).or_default(); |
278 | /// |
279 | /// assert_eq!(map["poneyland" ], None); |
280 | /// # } |
281 | /// ``` |
282 | #[cfg_attr (feature = "inline-more" , inline)] |
283 | pub fn or_default(self) -> &'a mut V |
284 | where |
285 | K: Hash, |
286 | { |
287 | match self { |
288 | Occupied(entry) => entry.into_mut(), |
289 | Vacant(entry) => entry.insert(Default::default()), |
290 | } |
291 | } |
292 | } |
293 | |
294 | impl<'a, K, V, A: Allocator> RustcOccupiedEntry<'a, K, V, A> { |
295 | /// Gets a reference to the key in the entry. |
296 | /// |
297 | /// # Examples |
298 | /// |
299 | /// ``` |
300 | /// use hashbrown::HashMap; |
301 | /// |
302 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
303 | /// map.rustc_entry("poneyland" ).or_insert(12); |
304 | /// assert_eq!(map.rustc_entry("poneyland" ).key(), &"poneyland" ); |
305 | /// ``` |
306 | #[cfg_attr (feature = "inline-more" , inline)] |
307 | pub fn key(&self) -> &K { |
308 | unsafe { &self.elem.as_ref().0 } |
309 | } |
310 | |
311 | /// Take the ownership of the key and value from the map. |
312 | /// |
313 | /// # Examples |
314 | /// |
315 | /// ``` |
316 | /// use hashbrown::HashMap; |
317 | /// use hashbrown::hash_map::RustcEntry; |
318 | /// |
319 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
320 | /// map.rustc_entry("poneyland" ).or_insert(12); |
321 | /// |
322 | /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland" ) { |
323 | /// // We delete the entry from the map. |
324 | /// o.remove_entry(); |
325 | /// } |
326 | /// |
327 | /// assert_eq!(map.contains_key("poneyland" ), false); |
328 | /// ``` |
329 | #[cfg_attr (feature = "inline-more" , inline)] |
330 | pub fn remove_entry(self) -> (K, V) { |
331 | unsafe { self.table.remove(self.elem).0 } |
332 | } |
333 | |
334 | /// Gets a reference to the value in the entry. |
335 | /// |
336 | /// # Examples |
337 | /// |
338 | /// ``` |
339 | /// use hashbrown::HashMap; |
340 | /// use hashbrown::hash_map::RustcEntry; |
341 | /// |
342 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
343 | /// map.rustc_entry("poneyland" ).or_insert(12); |
344 | /// |
345 | /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland" ) { |
346 | /// assert_eq!(o.get(), &12); |
347 | /// } |
348 | /// ``` |
349 | #[cfg_attr (feature = "inline-more" , inline)] |
350 | pub fn get(&self) -> &V { |
351 | unsafe { &self.elem.as_ref().1 } |
352 | } |
353 | |
354 | /// Gets a mutable reference to the value in the entry. |
355 | /// |
356 | /// If you need a reference to the `RustcOccupiedEntry` which may outlive the |
357 | /// destruction of the `RustcEntry` value, see [`into_mut`]. |
358 | /// |
359 | /// [`into_mut`]: #method.into_mut |
360 | /// |
361 | /// # Examples |
362 | /// |
363 | /// ``` |
364 | /// use hashbrown::HashMap; |
365 | /// use hashbrown::hash_map::RustcEntry; |
366 | /// |
367 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
368 | /// map.rustc_entry("poneyland" ).or_insert(12); |
369 | /// |
370 | /// assert_eq!(map["poneyland" ], 12); |
371 | /// if let RustcEntry::Occupied(mut o) = map.rustc_entry("poneyland" ) { |
372 | /// *o.get_mut() += 10; |
373 | /// assert_eq!(*o.get(), 22); |
374 | /// |
375 | /// // We can use the same RustcEntry multiple times. |
376 | /// *o.get_mut() += 2; |
377 | /// } |
378 | /// |
379 | /// assert_eq!(map["poneyland" ], 24); |
380 | /// ``` |
381 | #[cfg_attr (feature = "inline-more" , inline)] |
382 | pub fn get_mut(&mut self) -> &mut V { |
383 | unsafe { &mut self.elem.as_mut().1 } |
384 | } |
385 | |
386 | /// Converts the RustcOccupiedEntry into a mutable reference to the value in the entry |
387 | /// with a lifetime bound to the map itself. |
388 | /// |
389 | /// If you need multiple references to the `RustcOccupiedEntry`, see [`get_mut`]. |
390 | /// |
391 | /// [`get_mut`]: #method.get_mut |
392 | /// |
393 | /// # Examples |
394 | /// |
395 | /// ``` |
396 | /// use hashbrown::HashMap; |
397 | /// use hashbrown::hash_map::RustcEntry; |
398 | /// |
399 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
400 | /// map.rustc_entry("poneyland" ).or_insert(12); |
401 | /// |
402 | /// assert_eq!(map["poneyland" ], 12); |
403 | /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland" ) { |
404 | /// *o.into_mut() += 10; |
405 | /// } |
406 | /// |
407 | /// assert_eq!(map["poneyland" ], 22); |
408 | /// ``` |
409 | #[cfg_attr (feature = "inline-more" , inline)] |
410 | pub fn into_mut(self) -> &'a mut V { |
411 | unsafe { &mut self.elem.as_mut().1 } |
412 | } |
413 | |
414 | /// Sets the value of the entry, and returns the entry's old value. |
415 | /// |
416 | /// # Examples |
417 | /// |
418 | /// ``` |
419 | /// use hashbrown::HashMap; |
420 | /// use hashbrown::hash_map::RustcEntry; |
421 | /// |
422 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
423 | /// map.rustc_entry("poneyland" ).or_insert(12); |
424 | /// |
425 | /// if let RustcEntry::Occupied(mut o) = map.rustc_entry("poneyland" ) { |
426 | /// assert_eq!(o.insert(15), 12); |
427 | /// } |
428 | /// |
429 | /// assert_eq!(map["poneyland" ], 15); |
430 | /// ``` |
431 | #[cfg_attr (feature = "inline-more" , inline)] |
432 | pub fn insert(&mut self, value: V) -> V { |
433 | mem::replace(self.get_mut(), value) |
434 | } |
435 | |
436 | /// Takes the value out of the entry, and returns it. |
437 | /// |
438 | /// # Examples |
439 | /// |
440 | /// ``` |
441 | /// use hashbrown::HashMap; |
442 | /// use hashbrown::hash_map::RustcEntry; |
443 | /// |
444 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
445 | /// map.rustc_entry("poneyland" ).or_insert(12); |
446 | /// |
447 | /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland" ) { |
448 | /// assert_eq!(o.remove(), 12); |
449 | /// } |
450 | /// |
451 | /// assert_eq!(map.contains_key("poneyland" ), false); |
452 | /// ``` |
453 | #[cfg_attr (feature = "inline-more" , inline)] |
454 | pub fn remove(self) -> V { |
455 | self.remove_entry().1 |
456 | } |
457 | } |
458 | |
459 | impl<'a, K, V, A: Allocator> RustcVacantEntry<'a, K, V, A> { |
460 | /// Gets a reference to the key that would be used when inserting a value |
461 | /// through the `RustcVacantEntry`. |
462 | /// |
463 | /// # Examples |
464 | /// |
465 | /// ``` |
466 | /// use hashbrown::HashMap; |
467 | /// |
468 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
469 | /// assert_eq!(map.rustc_entry("poneyland" ).key(), &"poneyland" ); |
470 | /// ``` |
471 | #[cfg_attr (feature = "inline-more" , inline)] |
472 | pub fn key(&self) -> &K { |
473 | &self.key |
474 | } |
475 | |
476 | /// Take ownership of the key. |
477 | /// |
478 | /// # Examples |
479 | /// |
480 | /// ``` |
481 | /// use hashbrown::HashMap; |
482 | /// use hashbrown::hash_map::RustcEntry; |
483 | /// |
484 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
485 | /// |
486 | /// if let RustcEntry::Vacant(v) = map.rustc_entry("poneyland" ) { |
487 | /// v.into_key(); |
488 | /// } |
489 | /// ``` |
490 | #[cfg_attr (feature = "inline-more" , inline)] |
491 | pub fn into_key(self) -> K { |
492 | self.key |
493 | } |
494 | |
495 | /// Sets the value of the entry with the RustcVacantEntry's key, |
496 | /// and returns a mutable reference to it. |
497 | /// |
498 | /// # Examples |
499 | /// |
500 | /// ``` |
501 | /// use hashbrown::HashMap; |
502 | /// use hashbrown::hash_map::RustcEntry; |
503 | /// |
504 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
505 | /// |
506 | /// if let RustcEntry::Vacant(o) = map.rustc_entry("poneyland" ) { |
507 | /// o.insert(37); |
508 | /// } |
509 | /// assert_eq!(map["poneyland" ], 37); |
510 | /// ``` |
511 | #[cfg_attr (feature = "inline-more" , inline)] |
512 | pub fn insert(self, value: V) -> &'a mut V { |
513 | unsafe { |
514 | let bucket = self.table.insert_no_grow(self.hash, (self.key, value)); |
515 | &mut bucket.as_mut().1 |
516 | } |
517 | } |
518 | |
519 | /// Sets the value of the entry with the RustcVacantEntry's key, |
520 | /// and returns a RustcOccupiedEntry. |
521 | /// |
522 | /// # Examples |
523 | /// |
524 | /// ``` |
525 | /// use hashbrown::HashMap; |
526 | /// use hashbrown::hash_map::RustcEntry; |
527 | /// |
528 | /// let mut map: HashMap<&str, u32> = HashMap::new(); |
529 | /// |
530 | /// if let RustcEntry::Vacant(v) = map.rustc_entry("poneyland" ) { |
531 | /// let o = v.insert_entry(37); |
532 | /// assert_eq!(o.get(), &37); |
533 | /// } |
534 | /// ``` |
535 | #[cfg_attr (feature = "inline-more" , inline)] |
536 | pub fn insert_entry(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> { |
537 | let bucket = unsafe { self.table.insert_no_grow(self.hash, (self.key, value)) }; |
538 | RustcOccupiedEntry { |
539 | elem: bucket, |
540 | table: self.table, |
541 | } |
542 | } |
543 | } |
544 | |
545 | impl<K, V> IterMut<'_, K, V> { |
546 | /// Returns a iterator of references over the remaining items. |
547 | #[cfg_attr (feature = "inline-more" , inline)] |
548 | pub fn rustc_iter(&self) -> Iter<'_, K, V> { |
549 | self.iter() |
550 | } |
551 | } |
552 | |
553 | impl<K, V, A: Allocator> IntoIter<K, V, A> { |
554 | /// Returns a iterator of references over the remaining items. |
555 | #[cfg_attr (feature = "inline-more" , inline)] |
556 | pub fn rustc_iter(&self) -> Iter<'_, K, V> { |
557 | self.iter() |
558 | } |
559 | } |
560 | |
561 | impl<K, V, A: Allocator> Drain<'_, K, V, A> { |
562 | /// Returns a iterator of references over the remaining items. |
563 | #[cfg_attr (feature = "inline-more" , inline)] |
564 | pub fn rustc_iter(&self) -> Iter<'_, K, V> { |
565 | self.iter() |
566 | } |
567 | } |
568 | |