1use crate::hash_map::{equivalent, make_hash, make_hasher};
2use crate::raw::{Allocator, Bucket, Global, RawTable};
3use crate::{Equivalent, HashMap};
4use core::fmt::{self, Debug};
5use core::hash::{BuildHasher, Hash};
6use core::mem;
7
8impl<K, V, S, A: Allocator> HashMap<K, V, S, A> {
9 /// Creates a raw entry builder for the `HashMap`.
10 ///
11 /// Raw entries provide the lowest level of control for searching and
12 /// manipulating a map. They must be manually initialized with a hash and
13 /// then manually searched. After this, insertions into a vacant entry
14 /// still require an owned key to be provided.
15 ///
16 /// Raw entries are useful for such exotic situations as:
17 ///
18 /// * Hash memoization
19 /// * Deferring the creation of an owned key until it is known to be required
20 /// * Using a search key that doesn't work with the Borrow trait
21 /// * Using custom comparison logic without newtype wrappers
22 ///
23 /// Because raw entries provide much more low-level control, it's much easier
24 /// to put the `HashMap` into an inconsistent state which, while memory-safe,
25 /// will cause the map to produce seemingly random results. Higher-level and
26 /// more foolproof APIs like `entry` should be preferred when possible.
27 ///
28 /// In particular, the hash used to initialized the raw entry must still be
29 /// consistent with the hash of the key that is ultimately stored in the entry.
30 /// This is because implementations of `HashMap` may need to recompute hashes
31 /// when resizing, at which point only the keys are available.
32 ///
33 /// Raw entries give mutable access to the keys. This must not be used
34 /// to modify how the key would compare or hash, as the map will not re-evaluate
35 /// where the key should go, meaning the keys may become "lost" if their
36 /// location does not reflect their state. For instance, if you change a key
37 /// so that the map now contains keys which compare equal, search may start
38 /// acting erratically, with two keys randomly masking each other. Implementations
39 /// are free to assume this doesn't happen (within the limits of memory-safety).
40 ///
41 /// # Examples
42 ///
43 /// ```
44 /// use core::hash::{BuildHasher, Hash};
45 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
46 ///
47 /// let mut map = HashMap::new();
48 /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
49 ///
50 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
51 /// use core::hash::Hasher;
52 /// let mut state = hash_builder.build_hasher();
53 /// key.hash(&mut state);
54 /// state.finish()
55 /// }
56 ///
57 /// // Existing key (insert and update)
58 /// match map.raw_entry_mut().from_key(&"a") {
59 /// RawEntryMut::Vacant(_) => unreachable!(),
60 /// RawEntryMut::Occupied(mut view) => {
61 /// assert_eq!(view.get(), &100);
62 /// let v = view.get_mut();
63 /// let new_v = (*v) * 10;
64 /// *v = new_v;
65 /// assert_eq!(view.insert(1111), 1000);
66 /// }
67 /// }
68 ///
69 /// assert_eq!(map[&"a"], 1111);
70 /// assert_eq!(map.len(), 3);
71 ///
72 /// // Existing key (take)
73 /// let hash = compute_hash(map.hasher(), &"c");
74 /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"c") {
75 /// RawEntryMut::Vacant(_) => unreachable!(),
76 /// RawEntryMut::Occupied(view) => {
77 /// assert_eq!(view.remove_entry(), ("c", 300));
78 /// }
79 /// }
80 /// assert_eq!(map.raw_entry().from_key(&"c"), None);
81 /// assert_eq!(map.len(), 2);
82 ///
83 /// // Nonexistent key (insert and update)
84 /// let key = "d";
85 /// let hash = compute_hash(map.hasher(), &key);
86 /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) {
87 /// RawEntryMut::Occupied(_) => unreachable!(),
88 /// RawEntryMut::Vacant(view) => {
89 /// let (k, value) = view.insert("d", 4000);
90 /// assert_eq!((*k, *value), ("d", 4000));
91 /// *value = 40000;
92 /// }
93 /// }
94 /// assert_eq!(map[&"d"], 40000);
95 /// assert_eq!(map.len(), 3);
96 ///
97 /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) {
98 /// RawEntryMut::Vacant(_) => unreachable!(),
99 /// RawEntryMut::Occupied(view) => {
100 /// assert_eq!(view.remove_entry(), ("d", 40000));
101 /// }
102 /// }
103 /// assert_eq!(map.get(&"d"), None);
104 /// assert_eq!(map.len(), 2);
105 /// ```
106 #[cfg_attr(feature = "inline-more", inline)]
107 pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S, A> {
108 RawEntryBuilderMut { map: self }
109 }
110
111 /// Creates a raw immutable entry builder for the `HashMap`.
112 ///
113 /// Raw entries provide the lowest level of control for searching and
114 /// manipulating a map. They must be manually initialized with a hash and
115 /// then manually searched.
116 ///
117 /// This is useful for
118 /// * Hash memoization
119 /// * Using a search key that doesn't work with the Borrow trait
120 /// * Using custom comparison logic without newtype wrappers
121 ///
122 /// Unless you are in such a situation, higher-level and more foolproof APIs like
123 /// `get` should be preferred.
124 ///
125 /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
126 ///
127 /// # Examples
128 ///
129 /// ```
130 /// use core::hash::{BuildHasher, Hash};
131 /// use hashbrown::HashMap;
132 ///
133 /// let mut map = HashMap::new();
134 /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
135 ///
136 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
137 /// use core::hash::Hasher;
138 /// let mut state = hash_builder.build_hasher();
139 /// key.hash(&mut state);
140 /// state.finish()
141 /// }
142 ///
143 /// for k in ["a", "b", "c", "d", "e", "f"] {
144 /// let hash = compute_hash(map.hasher(), k);
145 /// let v = map.get(&k).cloned();
146 /// let kv = v.as_ref().map(|v| (&k, v));
147 ///
148 /// println!("Key: {} and value: {:?}", k, v);
149 ///
150 /// assert_eq!(map.raw_entry().from_key(&k), kv);
151 /// assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
152 /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
153 /// }
154 /// ```
155 #[cfg_attr(feature = "inline-more", inline)]
156 pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S, A> {
157 RawEntryBuilder { map: self }
158 }
159}
160
161/// A builder for computing where in a [`HashMap`] a key-value pair would be stored.
162///
163/// See the [`HashMap::raw_entry_mut`] docs for usage examples.
164///
165/// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
166///
167/// # Examples
168///
169/// ```
170/// use hashbrown::hash_map::{RawEntryBuilderMut, RawEntryMut::Vacant, RawEntryMut::Occupied};
171/// use hashbrown::HashMap;
172/// use core::hash::{BuildHasher, Hash};
173///
174/// let mut map = HashMap::new();
175/// map.extend([(1, 11), (2, 12), (3, 13), (4, 14), (5, 15), (6, 16)]);
176/// assert_eq!(map.len(), 6);
177///
178/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
179/// use core::hash::Hasher;
180/// let mut state = hash_builder.build_hasher();
181/// key.hash(&mut state);
182/// state.finish()
183/// }
184///
185/// let builder: RawEntryBuilderMut<_, _, _> = map.raw_entry_mut();
186///
187/// // Existing key
188/// match builder.from_key(&6) {
189/// Vacant(_) => unreachable!(),
190/// Occupied(view) => assert_eq!(view.get(), &16),
191/// }
192///
193/// for key in 0..12 {
194/// let hash = compute_hash(map.hasher(), &key);
195/// let value = map.get(&key).cloned();
196/// let key_value = value.as_ref().map(|v| (&key, v));
197///
198/// println!("Key: {} and value: {:?}", key, value);
199///
200/// match map.raw_entry_mut().from_key(&key) {
201/// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value),
202/// Vacant(_) => assert_eq!(value, None),
203/// }
204/// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &key) {
205/// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value),
206/// Vacant(_) => assert_eq!(value, None),
207/// }
208/// match map.raw_entry_mut().from_hash(hash, |q| *q == key) {
209/// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value),
210/// Vacant(_) => assert_eq!(value, None),
211/// }
212/// }
213///
214/// assert_eq!(map.len(), 6);
215/// ```
216pub struct RawEntryBuilderMut<'a, K, V, S, A: Allocator = Global> {
217 map: &'a mut HashMap<K, V, S, A>,
218}
219
220/// A view into a single entry in a map, which may either be vacant or occupied.
221///
222/// This is a lower-level version of [`Entry`].
223///
224/// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`],
225/// then calling one of the methods of that [`RawEntryBuilderMut`].
226///
227/// [`HashMap`]: struct.HashMap.html
228/// [`Entry`]: enum.Entry.html
229/// [`raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
230/// [`RawEntryBuilderMut`]: struct.RawEntryBuilderMut.html
231///
232/// # Examples
233///
234/// ```
235/// use core::hash::{BuildHasher, Hash};
236/// use hashbrown::hash_map::{HashMap, RawEntryMut, RawOccupiedEntryMut};
237///
238/// let mut map = HashMap::new();
239/// map.extend([('a', 1), ('b', 2), ('c', 3)]);
240/// assert_eq!(map.len(), 3);
241///
242/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
243/// use core::hash::Hasher;
244/// let mut state = hash_builder.build_hasher();
245/// key.hash(&mut state);
246/// state.finish()
247/// }
248///
249/// // Existing key (insert)
250/// let raw: RawEntryMut<_, _, _> = map.raw_entry_mut().from_key(&'a');
251/// let _raw_o: RawOccupiedEntryMut<_, _, _> = raw.insert('a', 10);
252/// assert_eq!(map.len(), 3);
253///
254/// // Nonexistent key (insert)
255/// map.raw_entry_mut().from_key(&'d').insert('d', 40);
256/// assert_eq!(map.len(), 4);
257///
258/// // Existing key (or_insert)
259/// let hash = compute_hash(map.hasher(), &'b');
260/// let kv = map
261/// .raw_entry_mut()
262/// .from_key_hashed_nocheck(hash, &'b')
263/// .or_insert('b', 20);
264/// assert_eq!(kv, (&mut 'b', &mut 2));
265/// *kv.1 = 20;
266/// assert_eq!(map.len(), 4);
267///
268/// // Nonexistent key (or_insert)
269/// let hash = compute_hash(map.hasher(), &'e');
270/// let kv = map
271/// .raw_entry_mut()
272/// .from_key_hashed_nocheck(hash, &'e')
273/// .or_insert('e', 50);
274/// assert_eq!(kv, (&mut 'e', &mut 50));
275/// assert_eq!(map.len(), 5);
276///
277/// // Existing key (or_insert_with)
278/// let hash = compute_hash(map.hasher(), &'c');
279/// let kv = map
280/// .raw_entry_mut()
281/// .from_hash(hash, |q| q == &'c')
282/// .or_insert_with(|| ('c', 30));
283/// assert_eq!(kv, (&mut 'c', &mut 3));
284/// *kv.1 = 30;
285/// assert_eq!(map.len(), 5);
286///
287/// // Nonexistent key (or_insert_with)
288/// let hash = compute_hash(map.hasher(), &'f');
289/// let kv = map
290/// .raw_entry_mut()
291/// .from_hash(hash, |q| q == &'f')
292/// .or_insert_with(|| ('f', 60));
293/// assert_eq!(kv, (&mut 'f', &mut 60));
294/// assert_eq!(map.len(), 6);
295///
296/// println!("Our HashMap: {:?}", map);
297///
298/// let mut vec: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
299/// // The `Iter` iterator produces items in arbitrary order, so the
300/// // items must be sorted to test them against a sorted array.
301/// vec.sort_unstable();
302/// assert_eq!(vec, [('a', 10), ('b', 20), ('c', 30), ('d', 40), ('e', 50), ('f', 60)]);
303/// ```
304pub enum RawEntryMut<'a, K, V, S, A: Allocator = Global> {
305 /// An occupied entry.
306 ///
307 /// # Examples
308 ///
309 /// ```
310 /// use hashbrown::{hash_map::RawEntryMut, HashMap};
311 /// let mut map: HashMap<_, _> = [("a", 100), ("b", 200)].into();
312 ///
313 /// match map.raw_entry_mut().from_key(&"a") {
314 /// RawEntryMut::Vacant(_) => unreachable!(),
315 /// RawEntryMut::Occupied(_) => { }
316 /// }
317 /// ```
318 Occupied(RawOccupiedEntryMut<'a, K, V, S, A>),
319 /// A vacant entry.
320 ///
321 /// # Examples
322 ///
323 /// ```
324 /// use hashbrown::{hash_map::RawEntryMut, HashMap};
325 /// let mut map: HashMap<&str, i32> = HashMap::new();
326 ///
327 /// match map.raw_entry_mut().from_key("a") {
328 /// RawEntryMut::Occupied(_) => unreachable!(),
329 /// RawEntryMut::Vacant(_) => { }
330 /// }
331 /// ```
332 Vacant(RawVacantEntryMut<'a, K, V, S, A>),
333}
334
335/// A view into an occupied entry in a `HashMap`.
336/// It is part of the [`RawEntryMut`] enum.
337///
338/// [`RawEntryMut`]: enum.RawEntryMut.html
339///
340/// # Examples
341///
342/// ```
343/// use core::hash::{BuildHasher, Hash};
344/// use hashbrown::hash_map::{HashMap, RawEntryMut, RawOccupiedEntryMut};
345///
346/// let mut map = HashMap::new();
347/// map.extend([("a", 10), ("b", 20), ("c", 30)]);
348///
349/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
350/// use core::hash::Hasher;
351/// let mut state = hash_builder.build_hasher();
352/// key.hash(&mut state);
353/// state.finish()
354/// }
355///
356/// let _raw_o: RawOccupiedEntryMut<_, _, _> = map.raw_entry_mut().from_key(&"a").insert("a", 100);
357/// assert_eq!(map.len(), 3);
358///
359/// // Existing key (insert and update)
360/// match map.raw_entry_mut().from_key(&"a") {
361/// RawEntryMut::Vacant(_) => unreachable!(),
362/// RawEntryMut::Occupied(mut view) => {
363/// assert_eq!(view.get(), &100);
364/// let v = view.get_mut();
365/// let new_v = (*v) * 10;
366/// *v = new_v;
367/// assert_eq!(view.insert(1111), 1000);
368/// }
369/// }
370///
371/// assert_eq!(map[&"a"], 1111);
372/// assert_eq!(map.len(), 3);
373///
374/// // Existing key (take)
375/// let hash = compute_hash(map.hasher(), &"c");
376/// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"c") {
377/// RawEntryMut::Vacant(_) => unreachable!(),
378/// RawEntryMut::Occupied(view) => {
379/// assert_eq!(view.remove_entry(), ("c", 30));
380/// }
381/// }
382/// assert_eq!(map.raw_entry().from_key(&"c"), None);
383/// assert_eq!(map.len(), 2);
384///
385/// let hash = compute_hash(map.hasher(), &"b");
386/// match map.raw_entry_mut().from_hash(hash, |q| *q == "b") {
387/// RawEntryMut::Vacant(_) => unreachable!(),
388/// RawEntryMut::Occupied(view) => {
389/// assert_eq!(view.remove_entry(), ("b", 20));
390/// }
391/// }
392/// assert_eq!(map.get(&"b"), None);
393/// assert_eq!(map.len(), 1);
394/// ```
395pub struct RawOccupiedEntryMut<'a, K, V, S, A: Allocator = Global> {
396 elem: Bucket<(K, V)>,
397 table: &'a mut RawTable<(K, V), A>,
398 hash_builder: &'a S,
399}
400
401unsafe impl<K, V, S, A> Send for RawOccupiedEntryMut<'_, K, V, S, A>
402where
403 K: Send,
404 V: Send,
405 S: Send,
406 A: Send + Allocator,
407{
408}
409unsafe impl<K, V, S, A> Sync for RawOccupiedEntryMut<'_, K, V, S, A>
410where
411 K: Sync,
412 V: Sync,
413 S: Sync,
414 A: Sync + Allocator,
415{
416}
417
418/// A view into a vacant entry in a `HashMap`.
419/// It is part of the [`RawEntryMut`] enum.
420///
421/// [`RawEntryMut`]: enum.RawEntryMut.html
422///
423/// # Examples
424///
425/// ```
426/// use core::hash::{BuildHasher, Hash};
427/// use hashbrown::hash_map::{HashMap, RawEntryMut, RawVacantEntryMut};
428///
429/// let mut map = HashMap::<&str, i32>::new();
430///
431/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
432/// use core::hash::Hasher;
433/// let mut state = hash_builder.build_hasher();
434/// key.hash(&mut state);
435/// state.finish()
436/// }
437///
438/// let raw_v: RawVacantEntryMut<_, _, _> = match map.raw_entry_mut().from_key(&"a") {
439/// RawEntryMut::Vacant(view) => view,
440/// RawEntryMut::Occupied(_) => unreachable!(),
441/// };
442/// raw_v.insert("a", 10);
443/// assert!(map[&"a"] == 10 && map.len() == 1);
444///
445/// // Nonexistent key (insert and update)
446/// let hash = compute_hash(map.hasher(), &"b");
447/// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"b") {
448/// RawEntryMut::Occupied(_) => unreachable!(),
449/// RawEntryMut::Vacant(view) => {
450/// let (k, value) = view.insert("b", 2);
451/// assert_eq!((*k, *value), ("b", 2));
452/// *value = 20;
453/// }
454/// }
455/// assert!(map[&"b"] == 20 && map.len() == 2);
456///
457/// let hash = compute_hash(map.hasher(), &"c");
458/// match map.raw_entry_mut().from_hash(hash, |q| *q == "c") {
459/// RawEntryMut::Occupied(_) => unreachable!(),
460/// RawEntryMut::Vacant(view) => {
461/// assert_eq!(view.insert("c", 30), (&mut "c", &mut 30));
462/// }
463/// }
464/// assert!(map[&"c"] == 30 && map.len() == 3);
465/// ```
466pub struct RawVacantEntryMut<'a, K, V, S, A: Allocator = Global> {
467 table: &'a mut RawTable<(K, V), A>,
468 hash_builder: &'a S,
469}
470
471/// A builder for computing where in a [`HashMap`] a key-value pair would be stored.
472///
473/// See the [`HashMap::raw_entry`] docs for usage examples.
474///
475/// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry
476///
477/// # Examples
478///
479/// ```
480/// use hashbrown::hash_map::{HashMap, RawEntryBuilder};
481/// use core::hash::{BuildHasher, Hash};
482///
483/// let mut map = HashMap::new();
484/// map.extend([(1, 10), (2, 20), (3, 30)]);
485///
486/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
487/// use core::hash::Hasher;
488/// let mut state = hash_builder.build_hasher();
489/// key.hash(&mut state);
490/// state.finish()
491/// }
492///
493/// for k in 0..6 {
494/// let hash = compute_hash(map.hasher(), &k);
495/// let v = map.get(&k).cloned();
496/// let kv = v.as_ref().map(|v| (&k, v));
497///
498/// println!("Key: {} and value: {:?}", k, v);
499/// let builder: RawEntryBuilder<_, _, _> = map.raw_entry();
500/// assert_eq!(builder.from_key(&k), kv);
501/// assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
502/// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
503/// }
504/// ```
505pub struct RawEntryBuilder<'a, K, V, S, A: Allocator = Global> {
506 map: &'a HashMap<K, V, S, A>,
507}
508
509impl<'a, K, V, S, A: Allocator> RawEntryBuilderMut<'a, K, V, S, A> {
510 /// Creates a `RawEntryMut` from the given key.
511 ///
512 /// # Examples
513 ///
514 /// ```
515 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
516 ///
517 /// let mut map: HashMap<&str, u32> = HashMap::new();
518 /// let key = "a";
519 /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_key(&key);
520 /// entry.insert(key, 100);
521 /// assert_eq!(map[&"a"], 100);
522 /// ```
523 #[cfg_attr(feature = "inline-more", inline)]
524 #[allow(clippy::wrong_self_convention)]
525 pub fn from_key<Q>(self, k: &Q) -> RawEntryMut<'a, K, V, S, A>
526 where
527 S: BuildHasher,
528 Q: Hash + Equivalent<K> + ?Sized,
529 {
530 let hash = make_hash::<Q, S>(&self.map.hash_builder, k);
531 self.from_key_hashed_nocheck(hash, k)
532 }
533
534 /// Creates a `RawEntryMut` from the given key and its hash.
535 ///
536 /// # Examples
537 ///
538 /// ```
539 /// use core::hash::{BuildHasher, Hash};
540 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
541 ///
542 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
543 /// use core::hash::Hasher;
544 /// let mut state = hash_builder.build_hasher();
545 /// key.hash(&mut state);
546 /// state.finish()
547 /// }
548 ///
549 /// let mut map: HashMap<&str, u32> = HashMap::new();
550 /// let key = "a";
551 /// let hash = compute_hash(map.hasher(), &key);
552 /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_key_hashed_nocheck(hash, &key);
553 /// entry.insert(key, 100);
554 /// assert_eq!(map[&"a"], 100);
555 /// ```
556 #[inline]
557 #[allow(clippy::wrong_self_convention)]
558 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S, A>
559 where
560 Q: Equivalent<K> + ?Sized,
561 {
562 self.from_hash(hash, equivalent(k))
563 }
564}
565
566impl<'a, K, V, S, A: Allocator> RawEntryBuilderMut<'a, K, V, S, A> {
567 /// Creates a `RawEntryMut` from the given hash and matching function.
568 ///
569 /// # Examples
570 ///
571 /// ```
572 /// use core::hash::{BuildHasher, Hash};
573 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
574 ///
575 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
576 /// use core::hash::Hasher;
577 /// let mut state = hash_builder.build_hasher();
578 /// key.hash(&mut state);
579 /// state.finish()
580 /// }
581 ///
582 /// let mut map: HashMap<&str, u32> = HashMap::new();
583 /// let key = "a";
584 /// let hash = compute_hash(map.hasher(), &key);
585 /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_hash(hash, |k| k == &key);
586 /// entry.insert(key, 100);
587 /// assert_eq!(map[&"a"], 100);
588 /// ```
589 #[cfg_attr(feature = "inline-more", inline)]
590 #[allow(clippy::wrong_self_convention)]
591 pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S, A>
592 where
593 for<'b> F: FnMut(&'b K) -> bool,
594 {
595 self.search(hash, is_match)
596 }
597
598 #[cfg_attr(feature = "inline-more", inline)]
599 fn search<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S, A>
600 where
601 for<'b> F: FnMut(&'b K) -> bool,
602 {
603 match self.map.table.find(hash, |(k, _)| is_match(k)) {
604 Some(elem) => RawEntryMut::Occupied(RawOccupiedEntryMut {
605 elem,
606 table: &mut self.map.table,
607 hash_builder: &self.map.hash_builder,
608 }),
609 None => RawEntryMut::Vacant(RawVacantEntryMut {
610 table: &mut self.map.table,
611 hash_builder: &self.map.hash_builder,
612 }),
613 }
614 }
615}
616
617impl<'a, K, V, S, A: Allocator> RawEntryBuilder<'a, K, V, S, A> {
618 /// Access an immutable entry by key.
619 ///
620 /// # Examples
621 ///
622 /// ```
623 /// use hashbrown::HashMap;
624 ///
625 /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
626 /// let key = "a";
627 /// assert_eq!(map.raw_entry().from_key(&key), Some((&"a", &100)));
628 /// ```
629 #[cfg_attr(feature = "inline-more", inline)]
630 #[allow(clippy::wrong_self_convention)]
631 pub fn from_key<Q>(self, k: &Q) -> Option<(&'a K, &'a V)>
632 where
633 S: BuildHasher,
634 Q: Hash + Equivalent<K> + ?Sized,
635 {
636 let hash = make_hash::<Q, S>(&self.map.hash_builder, k);
637 self.from_key_hashed_nocheck(hash, k)
638 }
639
640 /// Access an immutable entry by a key and its hash.
641 ///
642 /// # Examples
643 ///
644 /// ```
645 /// use core::hash::{BuildHasher, Hash};
646 /// use hashbrown::HashMap;
647 ///
648 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
649 /// use core::hash::Hasher;
650 /// let mut state = hash_builder.build_hasher();
651 /// key.hash(&mut state);
652 /// state.finish()
653 /// }
654 ///
655 /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
656 /// let key = "a";
657 /// let hash = compute_hash(map.hasher(), &key);
658 /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &key), Some((&"a", &100)));
659 /// ```
660 #[cfg_attr(feature = "inline-more", inline)]
661 #[allow(clippy::wrong_self_convention)]
662 pub fn from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
663 where
664 Q: Equivalent<K> + ?Sized,
665 {
666 self.from_hash(hash, equivalent(k))
667 }
668
669 #[cfg_attr(feature = "inline-more", inline)]
670 fn search<F>(self, hash: u64, mut is_match: F) -> Option<(&'a K, &'a V)>
671 where
672 F: FnMut(&K) -> bool,
673 {
674 match self.map.table.get(hash, |(k, _)| is_match(k)) {
675 Some((key, value)) => Some((key, value)),
676 None => None,
677 }
678 }
679
680 /// Access an immutable entry by hash and matching function.
681 ///
682 /// # Examples
683 ///
684 /// ```
685 /// use core::hash::{BuildHasher, Hash};
686 /// use hashbrown::HashMap;
687 ///
688 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
689 /// use core::hash::Hasher;
690 /// let mut state = hash_builder.build_hasher();
691 /// key.hash(&mut state);
692 /// state.finish()
693 /// }
694 ///
695 /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
696 /// let key = "a";
697 /// let hash = compute_hash(map.hasher(), &key);
698 /// assert_eq!(map.raw_entry().from_hash(hash, |k| k == &key), Some((&"a", &100)));
699 /// ```
700 #[cfg_attr(feature = "inline-more", inline)]
701 #[allow(clippy::wrong_self_convention)]
702 pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
703 where
704 F: FnMut(&K) -> bool,
705 {
706 self.search(hash, is_match)
707 }
708}
709
710impl<'a, K, V, S, A: Allocator> RawEntryMut<'a, K, V, S, A> {
711 /// Sets the value of the entry, and returns a `RawOccupiedEntryMut`.
712 ///
713 /// # Examples
714 ///
715 /// ```
716 /// use hashbrown::HashMap;
717 ///
718 /// let mut map: HashMap<&str, u32> = HashMap::new();
719 /// let entry = map.raw_entry_mut().from_key("horseyland").insert("horseyland", 37);
720 ///
721 /// assert_eq!(entry.remove_entry(), ("horseyland", 37));
722 /// ```
723 #[cfg_attr(feature = "inline-more", inline)]
724 pub fn insert(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A>
725 where
726 K: Hash,
727 S: BuildHasher,
728 {
729 match self {
730 RawEntryMut::Occupied(mut entry) => {
731 entry.insert(value);
732 entry
733 }
734 RawEntryMut::Vacant(entry) => entry.insert_entry(key, value),
735 }
736 }
737
738 /// Ensures a value is in the entry by inserting the default if empty, and returns
739 /// mutable references to the key and value in the entry.
740 ///
741 /// # Examples
742 ///
743 /// ```
744 /// use hashbrown::HashMap;
745 ///
746 /// let mut map: HashMap<&str, u32> = HashMap::new();
747 ///
748 /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3);
749 /// assert_eq!(map["poneyland"], 3);
750 ///
751 /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2;
752 /// assert_eq!(map["poneyland"], 6);
753 /// ```
754 #[cfg_attr(feature = "inline-more", inline)]
755 pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V)
756 where
757 K: Hash,
758 S: BuildHasher,
759 {
760 match self {
761 RawEntryMut::Occupied(entry) => entry.into_key_value(),
762 RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val),
763 }
764 }
765
766 /// Ensures a value is in the entry by inserting the result of the default function if empty,
767 /// and returns mutable references to the key and value in the entry.
768 ///
769 /// # Examples
770 ///
771 /// ```
772 /// use hashbrown::HashMap;
773 ///
774 /// let mut map: HashMap<&str, String> = HashMap::new();
775 ///
776 /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| {
777 /// ("poneyland", "hoho".to_string())
778 /// });
779 ///
780 /// assert_eq!(map["poneyland"], "hoho".to_string());
781 /// ```
782 #[cfg_attr(feature = "inline-more", inline)]
783 pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V)
784 where
785 F: FnOnce() -> (K, V),
786 K: Hash,
787 S: BuildHasher,
788 {
789 match self {
790 RawEntryMut::Occupied(entry) => entry.into_key_value(),
791 RawEntryMut::Vacant(entry) => {
792 let (k, v) = default();
793 entry.insert(k, v)
794 }
795 }
796 }
797
798 /// Provides in-place mutable access to an occupied entry before any
799 /// potential inserts into the map.
800 ///
801 /// # Examples
802 ///
803 /// ```
804 /// use hashbrown::HashMap;
805 ///
806 /// let mut map: HashMap<&str, u32> = HashMap::new();
807 ///
808 /// map.raw_entry_mut()
809 /// .from_key("poneyland")
810 /// .and_modify(|_k, v| { *v += 1 })
811 /// .or_insert("poneyland", 42);
812 /// assert_eq!(map["poneyland"], 42);
813 ///
814 /// map.raw_entry_mut()
815 /// .from_key("poneyland")
816 /// .and_modify(|_k, v| { *v += 1 })
817 /// .or_insert("poneyland", 0);
818 /// assert_eq!(map["poneyland"], 43);
819 /// ```
820 #[cfg_attr(feature = "inline-more", inline)]
821 pub fn and_modify<F>(self, f: F) -> Self
822 where
823 F: FnOnce(&mut K, &mut V),
824 {
825 match self {
826 RawEntryMut::Occupied(mut entry) => {
827 {
828 let (k, v) = entry.get_key_value_mut();
829 f(k, v);
830 }
831 RawEntryMut::Occupied(entry)
832 }
833 RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry),
834 }
835 }
836
837 /// Provides shared access to the key and owned access to the value of
838 /// an occupied entry and allows to replace or remove it based on the
839 /// value of the returned option.
840 ///
841 /// # Examples
842 ///
843 /// ```
844 /// use hashbrown::HashMap;
845 /// use hashbrown::hash_map::RawEntryMut;
846 ///
847 /// let mut map: HashMap<&str, u32> = HashMap::new();
848 ///
849 /// let entry = map
850 /// .raw_entry_mut()
851 /// .from_key("poneyland")
852 /// .and_replace_entry_with(|_k, _v| panic!());
853 ///
854 /// match entry {
855 /// RawEntryMut::Vacant(_) => {},
856 /// RawEntryMut::Occupied(_) => panic!(),
857 /// }
858 ///
859 /// map.insert("poneyland", 42);
860 ///
861 /// let entry = map
862 /// .raw_entry_mut()
863 /// .from_key("poneyland")
864 /// .and_replace_entry_with(|k, v| {
865 /// assert_eq!(k, &"poneyland");
866 /// assert_eq!(v, 42);
867 /// Some(v + 1)
868 /// });
869 ///
870 /// match entry {
871 /// RawEntryMut::Occupied(e) => {
872 /// assert_eq!(e.key(), &"poneyland");
873 /// assert_eq!(e.get(), &43);
874 /// },
875 /// RawEntryMut::Vacant(_) => panic!(),
876 /// }
877 ///
878 /// assert_eq!(map["poneyland"], 43);
879 ///
880 /// let entry = map
881 /// .raw_entry_mut()
882 /// .from_key("poneyland")
883 /// .and_replace_entry_with(|_k, _v| None);
884 ///
885 /// match entry {
886 /// RawEntryMut::Vacant(_) => {},
887 /// RawEntryMut::Occupied(_) => panic!(),
888 /// }
889 ///
890 /// assert!(!map.contains_key("poneyland"));
891 /// ```
892 #[cfg_attr(feature = "inline-more", inline)]
893 pub fn and_replace_entry_with<F>(self, f: F) -> Self
894 where
895 F: FnOnce(&K, V) -> Option<V>,
896 {
897 match self {
898 RawEntryMut::Occupied(entry) => entry.replace_entry_with(f),
899 RawEntryMut::Vacant(_) => self,
900 }
901 }
902}
903
904impl<'a, K, V, S, A: Allocator> RawOccupiedEntryMut<'a, K, V, S, A> {
905 /// Gets a reference to the key in the entry.
906 ///
907 /// # Examples
908 ///
909 /// ```
910 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
911 ///
912 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
913 ///
914 /// match map.raw_entry_mut().from_key(&"a") {
915 /// RawEntryMut::Vacant(_) => panic!(),
916 /// RawEntryMut::Occupied(o) => assert_eq!(o.key(), &"a")
917 /// }
918 /// ```
919 #[cfg_attr(feature = "inline-more", inline)]
920 pub fn key(&self) -> &K {
921 unsafe { &self.elem.as_ref().0 }
922 }
923
924 /// Gets a mutable reference to the key in the entry.
925 ///
926 /// # Examples
927 ///
928 /// ```
929 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
930 /// use std::rc::Rc;
931 ///
932 /// let key_one = Rc::new("a");
933 /// let key_two = Rc::new("a");
934 ///
935 /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
936 /// map.insert(key_one.clone(), 10);
937 ///
938 /// assert_eq!(map[&key_one], 10);
939 /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
940 ///
941 /// match map.raw_entry_mut().from_key(&key_one) {
942 /// RawEntryMut::Vacant(_) => panic!(),
943 /// RawEntryMut::Occupied(mut o) => {
944 /// *o.key_mut() = key_two.clone();
945 /// }
946 /// }
947 /// assert_eq!(map[&key_two], 10);
948 /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
949 /// ```
950 #[cfg_attr(feature = "inline-more", inline)]
951 pub fn key_mut(&mut self) -> &mut K {
952 unsafe { &mut self.elem.as_mut().0 }
953 }
954
955 /// Converts the entry into a mutable reference to the key in the entry
956 /// with a lifetime bound to the map itself.
957 ///
958 /// # Examples
959 ///
960 /// ```
961 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
962 /// use std::rc::Rc;
963 ///
964 /// let key_one = Rc::new("a");
965 /// let key_two = Rc::new("a");
966 ///
967 /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
968 /// map.insert(key_one.clone(), 10);
969 ///
970 /// assert_eq!(map[&key_one], 10);
971 /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
972 ///
973 /// let inside_key: &mut Rc<&str>;
974 ///
975 /// match map.raw_entry_mut().from_key(&key_one) {
976 /// RawEntryMut::Vacant(_) => panic!(),
977 /// RawEntryMut::Occupied(o) => inside_key = o.into_key(),
978 /// }
979 /// *inside_key = key_two.clone();
980 ///
981 /// assert_eq!(map[&key_two], 10);
982 /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
983 /// ```
984 #[cfg_attr(feature = "inline-more", inline)]
985 pub fn into_key(self) -> &'a mut K {
986 unsafe { &mut self.elem.as_mut().0 }
987 }
988
989 /// Gets a reference to the value in the entry.
990 ///
991 /// # Examples
992 ///
993 /// ```
994 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
995 ///
996 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
997 ///
998 /// match map.raw_entry_mut().from_key(&"a") {
999 /// RawEntryMut::Vacant(_) => panic!(),
1000 /// RawEntryMut::Occupied(o) => assert_eq!(o.get(), &100),
1001 /// }
1002 /// ```
1003 #[cfg_attr(feature = "inline-more", inline)]
1004 pub fn get(&self) -> &V {
1005 unsafe { &self.elem.as_ref().1 }
1006 }
1007
1008 /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
1009 /// with a lifetime bound to the map itself.
1010 ///
1011 /// # Examples
1012 ///
1013 /// ```
1014 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1015 ///
1016 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1017 ///
1018 /// let value: &mut u32;
1019 ///
1020 /// match map.raw_entry_mut().from_key(&"a") {
1021 /// RawEntryMut::Vacant(_) => panic!(),
1022 /// RawEntryMut::Occupied(o) => value = o.into_mut(),
1023 /// }
1024 /// *value += 900;
1025 ///
1026 /// assert_eq!(map[&"a"], 1000);
1027 /// ```
1028 #[cfg_attr(feature = "inline-more", inline)]
1029 pub fn into_mut(self) -> &'a mut V {
1030 unsafe { &mut self.elem.as_mut().1 }
1031 }
1032
1033 /// Gets a mutable reference to the value in the entry.
1034 ///
1035 /// # Examples
1036 ///
1037 /// ```
1038 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1039 ///
1040 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1041 ///
1042 /// match map.raw_entry_mut().from_key(&"a") {
1043 /// RawEntryMut::Vacant(_) => panic!(),
1044 /// RawEntryMut::Occupied(mut o) => *o.get_mut() += 900,
1045 /// }
1046 ///
1047 /// assert_eq!(map[&"a"], 1000);
1048 /// ```
1049 #[cfg_attr(feature = "inline-more", inline)]
1050 pub fn get_mut(&mut self) -> &mut V {
1051 unsafe { &mut self.elem.as_mut().1 }
1052 }
1053
1054 /// Gets a reference to the key and value in the entry.
1055 ///
1056 /// # Examples
1057 ///
1058 /// ```
1059 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1060 ///
1061 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1062 ///
1063 /// match map.raw_entry_mut().from_key(&"a") {
1064 /// RawEntryMut::Vacant(_) => panic!(),
1065 /// RawEntryMut::Occupied(o) => assert_eq!(o.get_key_value(), (&"a", &100)),
1066 /// }
1067 /// ```
1068 #[cfg_attr(feature = "inline-more", inline)]
1069 pub fn get_key_value(&self) -> (&K, &V) {
1070 unsafe {
1071 let (key, value) = self.elem.as_ref();
1072 (key, value)
1073 }
1074 }
1075
1076 /// Gets a mutable reference to the key and value in the entry.
1077 ///
1078 /// # Examples
1079 ///
1080 /// ```
1081 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1082 /// use std::rc::Rc;
1083 ///
1084 /// let key_one = Rc::new("a");
1085 /// let key_two = Rc::new("a");
1086 ///
1087 /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
1088 /// map.insert(key_one.clone(), 10);
1089 ///
1090 /// assert_eq!(map[&key_one], 10);
1091 /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
1092 ///
1093 /// match map.raw_entry_mut().from_key(&key_one) {
1094 /// RawEntryMut::Vacant(_) => panic!(),
1095 /// RawEntryMut::Occupied(mut o) => {
1096 /// let (inside_key, inside_value) = o.get_key_value_mut();
1097 /// *inside_key = key_two.clone();
1098 /// *inside_value = 100;
1099 /// }
1100 /// }
1101 /// assert_eq!(map[&key_two], 100);
1102 /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
1103 /// ```
1104 #[cfg_attr(feature = "inline-more", inline)]
1105 pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
1106 unsafe {
1107 let &mut (ref mut key, ref mut value) = self.elem.as_mut();
1108 (key, value)
1109 }
1110 }
1111
1112 /// Converts the `OccupiedEntry` into a mutable reference to the key and value in the entry
1113 /// with a lifetime bound to the map itself.
1114 ///
1115 /// # Examples
1116 ///
1117 /// ```
1118 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1119 /// use std::rc::Rc;
1120 ///
1121 /// let key_one = Rc::new("a");
1122 /// let key_two = Rc::new("a");
1123 ///
1124 /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
1125 /// map.insert(key_one.clone(), 10);
1126 ///
1127 /// assert_eq!(map[&key_one], 10);
1128 /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
1129 ///
1130 /// let inside_key: &mut Rc<&str>;
1131 /// let inside_value: &mut u32;
1132 /// match map.raw_entry_mut().from_key(&key_one) {
1133 /// RawEntryMut::Vacant(_) => panic!(),
1134 /// RawEntryMut::Occupied(o) => {
1135 /// let tuple = o.into_key_value();
1136 /// inside_key = tuple.0;
1137 /// inside_value = tuple.1;
1138 /// }
1139 /// }
1140 /// *inside_key = key_two.clone();
1141 /// *inside_value = 100;
1142 /// assert_eq!(map[&key_two], 100);
1143 /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
1144 /// ```
1145 #[cfg_attr(feature = "inline-more", inline)]
1146 pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
1147 unsafe {
1148 let &mut (ref mut key, ref mut value) = self.elem.as_mut();
1149 (key, value)
1150 }
1151 }
1152
1153 /// Sets the value of the entry, and returns the entry's old value.
1154 ///
1155 /// # Examples
1156 ///
1157 /// ```
1158 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1159 ///
1160 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1161 ///
1162 /// match map.raw_entry_mut().from_key(&"a") {
1163 /// RawEntryMut::Vacant(_) => panic!(),
1164 /// RawEntryMut::Occupied(mut o) => assert_eq!(o.insert(1000), 100),
1165 /// }
1166 ///
1167 /// assert_eq!(map[&"a"], 1000);
1168 /// ```
1169 #[cfg_attr(feature = "inline-more", inline)]
1170 pub fn insert(&mut self, value: V) -> V {
1171 mem::replace(self.get_mut(), value)
1172 }
1173
1174 /// Sets the value of the entry, and returns the entry's old value.
1175 ///
1176 /// # Examples
1177 ///
1178 /// ```
1179 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1180 /// use std::rc::Rc;
1181 ///
1182 /// let key_one = Rc::new("a");
1183 /// let key_two = Rc::new("a");
1184 ///
1185 /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
1186 /// map.insert(key_one.clone(), 10);
1187 ///
1188 /// assert_eq!(map[&key_one], 10);
1189 /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
1190 ///
1191 /// match map.raw_entry_mut().from_key(&key_one) {
1192 /// RawEntryMut::Vacant(_) => panic!(),
1193 /// RawEntryMut::Occupied(mut o) => {
1194 /// let old_key = o.insert_key(key_two.clone());
1195 /// assert!(Rc::ptr_eq(&old_key, &key_one));
1196 /// }
1197 /// }
1198 /// assert_eq!(map[&key_two], 10);
1199 /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
1200 /// ```
1201 #[cfg_attr(feature = "inline-more", inline)]
1202 pub fn insert_key(&mut self, key: K) -> K {
1203 mem::replace(self.key_mut(), key)
1204 }
1205
1206 /// Takes the value out of the entry, and returns it.
1207 ///
1208 /// # Examples
1209 ///
1210 /// ```
1211 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1212 ///
1213 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1214 ///
1215 /// match map.raw_entry_mut().from_key(&"a") {
1216 /// RawEntryMut::Vacant(_) => panic!(),
1217 /// RawEntryMut::Occupied(o) => assert_eq!(o.remove(), 100),
1218 /// }
1219 /// assert_eq!(map.get(&"a"), None);
1220 /// ```
1221 #[cfg_attr(feature = "inline-more", inline)]
1222 pub fn remove(self) -> V {
1223 self.remove_entry().1
1224 }
1225
1226 /// Take the ownership of the key and value from the map.
1227 ///
1228 /// # Examples
1229 ///
1230 /// ```
1231 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1232 ///
1233 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1234 ///
1235 /// match map.raw_entry_mut().from_key(&"a") {
1236 /// RawEntryMut::Vacant(_) => panic!(),
1237 /// RawEntryMut::Occupied(o) => assert_eq!(o.remove_entry(), ("a", 100)),
1238 /// }
1239 /// assert_eq!(map.get(&"a"), None);
1240 /// ```
1241 #[cfg_attr(feature = "inline-more", inline)]
1242 pub fn remove_entry(self) -> (K, V) {
1243 unsafe { self.table.remove(self.elem).0 }
1244 }
1245
1246 /// Provides shared access to the key and owned access to the value of
1247 /// the entry and allows to replace or remove it based on the
1248 /// value of the returned option.
1249 ///
1250 /// # Examples
1251 ///
1252 /// ```
1253 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1254 ///
1255 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1256 ///
1257 /// let raw_entry = match map.raw_entry_mut().from_key(&"a") {
1258 /// RawEntryMut::Vacant(_) => panic!(),
1259 /// RawEntryMut::Occupied(o) => o.replace_entry_with(|k, v| {
1260 /// assert_eq!(k, &"a");
1261 /// assert_eq!(v, 100);
1262 /// Some(v + 900)
1263 /// }),
1264 /// };
1265 /// let raw_entry = match raw_entry {
1266 /// RawEntryMut::Vacant(_) => panic!(),
1267 /// RawEntryMut::Occupied(o) => o.replace_entry_with(|k, v| {
1268 /// assert_eq!(k, &"a");
1269 /// assert_eq!(v, 1000);
1270 /// None
1271 /// }),
1272 /// };
1273 /// match raw_entry {
1274 /// RawEntryMut::Vacant(_) => { },
1275 /// RawEntryMut::Occupied(_) => panic!(),
1276 /// };
1277 /// assert_eq!(map.get(&"a"), None);
1278 /// ```
1279 #[cfg_attr(feature = "inline-more", inline)]
1280 pub fn replace_entry_with<F>(self, f: F) -> RawEntryMut<'a, K, V, S, A>
1281 where
1282 F: FnOnce(&K, V) -> Option<V>,
1283 {
1284 unsafe {
1285 let still_occupied = self
1286 .table
1287 .replace_bucket_with(self.elem.clone(), |(key, value)| {
1288 f(&key, value).map(|new_value| (key, new_value))
1289 });
1290
1291 if still_occupied {
1292 RawEntryMut::Occupied(self)
1293 } else {
1294 RawEntryMut::Vacant(RawVacantEntryMut {
1295 table: self.table,
1296 hash_builder: self.hash_builder,
1297 })
1298 }
1299 }
1300 }
1301}
1302
1303impl<'a, K, V, S, A: Allocator> RawVacantEntryMut<'a, K, V, S, A> {
1304 /// Sets the value of the entry with the `VacantEntry`'s key,
1305 /// and returns a mutable reference to it.
1306 ///
1307 /// # Examples
1308 ///
1309 /// ```
1310 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1311 ///
1312 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1313 ///
1314 /// match map.raw_entry_mut().from_key(&"c") {
1315 /// RawEntryMut::Occupied(_) => panic!(),
1316 /// RawEntryMut::Vacant(v) => assert_eq!(v.insert("c", 300), (&mut "c", &mut 300)),
1317 /// }
1318 ///
1319 /// assert_eq!(map[&"c"], 300);
1320 /// ```
1321 #[cfg_attr(feature = "inline-more", inline)]
1322 pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
1323 where
1324 K: Hash,
1325 S: BuildHasher,
1326 {
1327 let hash = make_hash::<K, S>(self.hash_builder, &key);
1328 self.insert_hashed_nocheck(hash, key, value)
1329 }
1330
1331 /// Sets the value of the entry with the `VacantEntry`'s key,
1332 /// and returns a mutable reference to it.
1333 ///
1334 /// # Examples
1335 ///
1336 /// ```
1337 /// use core::hash::{BuildHasher, Hash};
1338 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1339 ///
1340 /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
1341 /// use core::hash::Hasher;
1342 /// let mut state = hash_builder.build_hasher();
1343 /// key.hash(&mut state);
1344 /// state.finish()
1345 /// }
1346 ///
1347 /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
1348 /// let key = "c";
1349 /// let hash = compute_hash(map.hasher(), &key);
1350 ///
1351 /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &key) {
1352 /// RawEntryMut::Occupied(_) => panic!(),
1353 /// RawEntryMut::Vacant(v) => assert_eq!(
1354 /// v.insert_hashed_nocheck(hash, key, 300),
1355 /// (&mut "c", &mut 300)
1356 /// ),
1357 /// }
1358 ///
1359 /// assert_eq!(map[&"c"], 300);
1360 /// ```
1361 #[cfg_attr(feature = "inline-more", inline)]
1362 #[allow(clippy::shadow_unrelated)]
1363 pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
1364 where
1365 K: Hash,
1366 S: BuildHasher,
1367 {
1368 let &mut (ref mut k, ref mut v) = self.table.insert_entry(
1369 hash,
1370 (key, value),
1371 make_hasher::<_, V, S>(self.hash_builder),
1372 );
1373 (k, v)
1374 }
1375
1376 /// Set the value of an entry with a custom hasher function.
1377 ///
1378 /// # Examples
1379 ///
1380 /// ```
1381 /// use core::hash::{BuildHasher, Hash};
1382 /// use hashbrown::hash_map::{HashMap, RawEntryMut};
1383 ///
1384 /// fn make_hasher<K, S>(hash_builder: &S) -> impl Fn(&K) -> u64 + '_
1385 /// where
1386 /// K: Hash + ?Sized,
1387 /// S: BuildHasher,
1388 /// {
1389 /// move |key: &K| {
1390 /// use core::hash::Hasher;
1391 /// let mut state = hash_builder.build_hasher();
1392 /// key.hash(&mut state);
1393 /// state.finish()
1394 /// }
1395 /// }
1396 ///
1397 /// let mut map: HashMap<&str, u32> = HashMap::new();
1398 /// let key = "a";
1399 /// let hash_builder = map.hasher().clone();
1400 /// let hash = make_hasher(&hash_builder)(&key);
1401 ///
1402 /// match map.raw_entry_mut().from_hash(hash, |q| q == &key) {
1403 /// RawEntryMut::Occupied(_) => panic!(),
1404 /// RawEntryMut::Vacant(v) => assert_eq!(
1405 /// v.insert_with_hasher(hash, key, 100, make_hasher(&hash_builder)),
1406 /// (&mut "a", &mut 100)
1407 /// ),
1408 /// }
1409 /// map.extend([("b", 200), ("c", 300), ("d", 400), ("e", 500), ("f", 600)]);
1410 /// assert_eq!(map[&"a"], 100);
1411 /// ```
1412 #[cfg_attr(feature = "inline-more", inline)]
1413 pub fn insert_with_hasher<H>(
1414 self,
1415 hash: u64,
1416 key: K,
1417 value: V,
1418 hasher: H,
1419 ) -> (&'a mut K, &'a mut V)
1420 where
1421 H: Fn(&K) -> u64,
1422 {
1423 let &mut (ref mut k, ref mut v) = self
1424 .table
1425 .insert_entry(hash, (key, value), |x| hasher(&x.0));
1426 (k, v)
1427 }
1428
1429 #[cfg_attr(feature = "inline-more", inline)]
1430 fn insert_entry(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A>
1431 where
1432 K: Hash,
1433 S: BuildHasher,
1434 {
1435 let hash = make_hash::<K, S>(self.hash_builder, &key);
1436 let elem = self.table.insert(
1437 hash,
1438 (key, value),
1439 make_hasher::<_, V, S>(self.hash_builder),
1440 );
1441 RawOccupiedEntryMut {
1442 elem,
1443 table: self.table,
1444 hash_builder: self.hash_builder,
1445 }
1446 }
1447}
1448
1449impl<K, V, S, A: Allocator> Debug for RawEntryBuilderMut<'_, K, V, S, A> {
1450 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1451 f.debug_struct(name:"RawEntryBuilder").finish()
1452 }
1453}
1454
1455impl<K: Debug, V: Debug, S, A: Allocator> Debug for RawEntryMut<'_, K, V, S, A> {
1456 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1457 match *self {
1458 RawEntryMut::Vacant(ref v: &RawVacantEntryMut<'_, K, …, …, …>) => f.debug_tuple(name:"RawEntry").field(v).finish(),
1459 RawEntryMut::Occupied(ref o: &RawOccupiedEntryMut<'_, K, …, …, …>) => f.debug_tuple(name:"RawEntry").field(o).finish(),
1460 }
1461 }
1462}
1463
1464impl<K: Debug, V: Debug, S, A: Allocator> Debug for RawOccupiedEntryMut<'_, K, V, S, A> {
1465 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1466 f&mut DebugStruct<'_, '_>.debug_struct("RawOccupiedEntryMut")
1467 .field("key", self.key())
1468 .field(name:"value", self.get())
1469 .finish()
1470 }
1471}
1472
1473impl<K, V, S, A: Allocator> Debug for RawVacantEntryMut<'_, K, V, S, A> {
1474 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1475 f.debug_struct(name:"RawVacantEntryMut").finish()
1476 }
1477}
1478
1479impl<K, V, S, A: Allocator> Debug for RawEntryBuilder<'_, K, V, S, A> {
1480 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1481 f.debug_struct(name:"RawEntryBuilder").finish()
1482 }
1483}
1484
1485#[cfg(test)]
1486mod test_map {
1487 use super::HashMap;
1488 use super::RawEntryMut;
1489
1490 #[test]
1491 fn test_raw_occupied_entry_replace_entry_with() {
1492 let mut a = HashMap::new();
1493
1494 let key = "a key";
1495 let value = "an initial value";
1496 let new_value = "a new value";
1497
1498 let entry = a
1499 .raw_entry_mut()
1500 .from_key(&key)
1501 .insert(key, value)
1502 .replace_entry_with(|k, v| {
1503 assert_eq!(k, &key);
1504 assert_eq!(v, value);
1505 Some(new_value)
1506 });
1507
1508 match entry {
1509 RawEntryMut::Occupied(e) => {
1510 assert_eq!(e.key(), &key);
1511 assert_eq!(e.get(), &new_value);
1512 }
1513 RawEntryMut::Vacant(_) => panic!(),
1514 }
1515
1516 assert_eq!(a[key], new_value);
1517 assert_eq!(a.len(), 1);
1518
1519 let entry = match a.raw_entry_mut().from_key(&key) {
1520 RawEntryMut::Occupied(e) => e.replace_entry_with(|k, v| {
1521 assert_eq!(k, &key);
1522 assert_eq!(v, new_value);
1523 None
1524 }),
1525 RawEntryMut::Vacant(_) => panic!(),
1526 };
1527
1528 match entry {
1529 RawEntryMut::Vacant(_) => {}
1530 RawEntryMut::Occupied(_) => panic!(),
1531 }
1532
1533 assert!(!a.contains_key(key));
1534 assert_eq!(a.len(), 0);
1535 }
1536
1537 #[test]
1538 fn test_raw_entry_and_replace_entry_with() {
1539 let mut a = HashMap::new();
1540
1541 let key = "a key";
1542 let value = "an initial value";
1543 let new_value = "a new value";
1544
1545 let entry = a
1546 .raw_entry_mut()
1547 .from_key(&key)
1548 .and_replace_entry_with(|_, _| panic!());
1549
1550 match entry {
1551 RawEntryMut::Vacant(_) => {}
1552 RawEntryMut::Occupied(_) => panic!(),
1553 }
1554
1555 a.insert(key, value);
1556
1557 let entry = a
1558 .raw_entry_mut()
1559 .from_key(&key)
1560 .and_replace_entry_with(|k, v| {
1561 assert_eq!(k, &key);
1562 assert_eq!(v, value);
1563 Some(new_value)
1564 });
1565
1566 match entry {
1567 RawEntryMut::Occupied(e) => {
1568 assert_eq!(e.key(), &key);
1569 assert_eq!(e.get(), &new_value);
1570 }
1571 RawEntryMut::Vacant(_) => panic!(),
1572 }
1573
1574 assert_eq!(a[key], new_value);
1575 assert_eq!(a.len(), 1);
1576
1577 let entry = a
1578 .raw_entry_mut()
1579 .from_key(&key)
1580 .and_replace_entry_with(|k, v| {
1581 assert_eq!(k, &key);
1582 assert_eq!(v, new_value);
1583 None
1584 });
1585
1586 match entry {
1587 RawEntryMut::Vacant(_) => {}
1588 RawEntryMut::Occupied(_) => panic!(),
1589 }
1590
1591 assert!(!a.contains_key(key));
1592 assert_eq!(a.len(), 0);
1593 }
1594
1595 #[test]
1596 fn test_raw_entry() {
1597 use super::RawEntryMut::{Occupied, Vacant};
1598
1599 let xs = [(1_i32, 10_i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
1600
1601 let mut map: HashMap<_, _> = xs.iter().copied().collect();
1602
1603 let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 {
1604 super::make_hash::<i32, _>(map.hasher(), &k)
1605 };
1606
1607 // Existing key (insert)
1608 match map.raw_entry_mut().from_key(&1) {
1609 Vacant(_) => unreachable!(),
1610 Occupied(mut view) => {
1611 assert_eq!(view.get(), &10);
1612 assert_eq!(view.insert(100), 10);
1613 }
1614 }
1615 let hash1 = compute_hash(&map, 1);
1616 assert_eq!(map.raw_entry().from_key(&1).unwrap(), (&1, &100));
1617 assert_eq!(
1618 map.raw_entry().from_hash(hash1, |k| *k == 1).unwrap(),
1619 (&1, &100)
1620 );
1621 assert_eq!(
1622 map.raw_entry().from_key_hashed_nocheck(hash1, &1).unwrap(),
1623 (&1, &100)
1624 );
1625 assert_eq!(map.len(), 6);
1626
1627 // Existing key (update)
1628 match map.raw_entry_mut().from_key(&2) {
1629 Vacant(_) => unreachable!(),
1630 Occupied(mut view) => {
1631 let v = view.get_mut();
1632 let new_v = (*v) * 10;
1633 *v = new_v;
1634 }
1635 }
1636 let hash2 = compute_hash(&map, 2);
1637 assert_eq!(map.raw_entry().from_key(&2).unwrap(), (&2, &200));
1638 assert_eq!(
1639 map.raw_entry().from_hash(hash2, |k| *k == 2).unwrap(),
1640 (&2, &200)
1641 );
1642 assert_eq!(
1643 map.raw_entry().from_key_hashed_nocheck(hash2, &2).unwrap(),
1644 (&2, &200)
1645 );
1646 assert_eq!(map.len(), 6);
1647
1648 // Existing key (take)
1649 let hash3 = compute_hash(&map, 3);
1650 match map.raw_entry_mut().from_key_hashed_nocheck(hash3, &3) {
1651 Vacant(_) => unreachable!(),
1652 Occupied(view) => {
1653 assert_eq!(view.remove_entry(), (3, 30));
1654 }
1655 }
1656 assert_eq!(map.raw_entry().from_key(&3), None);
1657 assert_eq!(map.raw_entry().from_hash(hash3, |k| *k == 3), None);
1658 assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash3, &3), None);
1659 assert_eq!(map.len(), 5);
1660
1661 // Nonexistent key (insert)
1662 match map.raw_entry_mut().from_key(&10) {
1663 Occupied(_) => unreachable!(),
1664 Vacant(view) => {
1665 assert_eq!(view.insert(10, 1000), (&mut 10, &mut 1000));
1666 }
1667 }
1668 assert_eq!(map.raw_entry().from_key(&10).unwrap(), (&10, &1000));
1669 assert_eq!(map.len(), 6);
1670
1671 // Ensure all lookup methods produce equivalent results.
1672 for k in 0..12 {
1673 let hash = compute_hash(&map, k);
1674 let v = map.get(&k).copied();
1675 let kv = v.as_ref().map(|v| (&k, v));
1676
1677 assert_eq!(map.raw_entry().from_key(&k), kv);
1678 assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
1679 assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
1680
1681 match map.raw_entry_mut().from_key(&k) {
1682 Occupied(o) => assert_eq!(Some(o.get_key_value()), kv),
1683 Vacant(_) => assert_eq!(v, None),
1684 }
1685 match map.raw_entry_mut().from_key_hashed_nocheck(hash, &k) {
1686 Occupied(o) => assert_eq!(Some(o.get_key_value()), kv),
1687 Vacant(_) => assert_eq!(v, None),
1688 }
1689 match map.raw_entry_mut().from_hash(hash, |q| *q == k) {
1690 Occupied(o) => assert_eq!(Some(o.get_key_value()), kv),
1691 Vacant(_) => assert_eq!(v, None),
1692 }
1693 }
1694 }
1695
1696 #[test]
1697 fn test_key_without_hash_impl() {
1698 #[derive(Debug)]
1699 struct IntWrapper(u64);
1700
1701 let mut m: HashMap<IntWrapper, (), ()> = HashMap::default();
1702 {
1703 assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none());
1704 }
1705 {
1706 let vacant_entry = match m.raw_entry_mut().from_hash(0, |k| k.0 == 0) {
1707 RawEntryMut::Occupied(..) => panic!("Found entry for key 0"),
1708 RawEntryMut::Vacant(e) => e,
1709 };
1710 vacant_entry.insert_with_hasher(0, IntWrapper(0), (), |k| k.0);
1711 }
1712 {
1713 assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_some());
1714 assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_none());
1715 assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none());
1716 }
1717 {
1718 let vacant_entry = match m.raw_entry_mut().from_hash(1, |k| k.0 == 1) {
1719 RawEntryMut::Occupied(..) => panic!("Found entry for key 1"),
1720 RawEntryMut::Vacant(e) => e,
1721 };
1722 vacant_entry.insert_with_hasher(1, IntWrapper(1), (), |k| k.0);
1723 }
1724 {
1725 assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_some());
1726 assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_some());
1727 assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none());
1728 }
1729 {
1730 let occupied_entry = match m.raw_entry_mut().from_hash(0, |k| k.0 == 0) {
1731 RawEntryMut::Occupied(e) => e,
1732 RawEntryMut::Vacant(..) => panic!("Couldn't find entry for key 0"),
1733 };
1734 occupied_entry.remove();
1735 }
1736 assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none());
1737 assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_some());
1738 assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none());
1739 }
1740}
1741