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: &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
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&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
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(name:"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, 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
561impl<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