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