hashbrown/
rustc_entry.rs

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                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
62pub enum RustcEntry<'a, K, V, A = Global>
63where
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
73impl<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) => f.debug_tuple("Entry").field(v).finish(),
77            Occupied(ref o) => f.debug_tuple("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
86pub struct RustcOccupiedEntry<'a, K, V, A = Global>
87where
88    A: Allocator,
89{
90    elem: Bucket<(K, V)>,
91    table: &'a mut RawTable<(K, V), A>,
92}
93
94unsafe impl<K, V, A> Send for RustcOccupiedEntry<'_, K, V, A>
95where
96    K: Send,
97    V: Send,
98    A: Allocator + Send,
99{
100}
101unsafe impl<K, V, A> Sync for RustcOccupiedEntry<'_, K, V, A>
102where
103    K: Sync,
104    V: Sync,
105    A: Allocator + Sync,
106{
107}
108
109impl<K: Debug, V: Debug, A: Allocator> Debug for RustcOccupiedEntry<'_, K, V, A> {
110    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
111        f.debug_struct("OccupiedEntry")
112            .field("key", self.key())
113            .field("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
122pub struct RustcVacantEntry<'a, K, V, A = Global>
123where
124    A: Allocator,
125{
126    hash: u64,
127    key: K,
128    table: &'a mut RawTable<(K, V), A>,
129}
130
131impl<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("VacantEntry").field(self.key()).finish()
134    }
135}
136
137impl<'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
266impl<'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
294impl<'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
459impl<'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
545impl<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
553impl<K, V> IntoIter<K, V> {
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
561impl<K, V> Drain<'_, K, V> {
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}
hashbrown/rustc_entry.rs

hashbrown/
rustc_entry.rs
