papaya/map.rs
1use crate::raw::utils::MapGuard;
2use crate::raw::{self, InsertResult};
3use crate::Equivalent;
4use seize::{Collector, Guard, LocalGuard, OwnedGuard};
5
6use std::collections::hash_map::RandomState;
7use std::fmt;
8use std::hash::{BuildHasher, Hash};
9use std::marker::PhantomData;
10
11/// A concurrent hash table.
12///
13/// Most hash table operations require a [`Guard`](crate::Guard), which can be acquired through
14/// [`HashMap::guard`] or using the [`HashMap::pin`] API. See the [crate-level documentation](crate#usage)
15/// for details.
16pub struct HashMap<K, V, S = RandomState> {
17 raw: raw::HashMap<K, V, S>,
18}
19
20// Safety: `HashMap` acts as a single-threaded collection on a single thread.
21// References to keys and values cannot outlive the map's lifetime on a given
22// thread.
23unsafe impl<K: Send, V: Send, S: Send> Send for HashMap<K, V, S> {}
24
25// Safety: We only ever hand out `&{K, V}` through shared references to the map,
26// and never `&mut {K, V}` except through synchronized memory reclamation.
27//
28// However, we require `{K, V}: Send` as keys and values may be removed and dropped
29// on a different thread than they were created on through shared access to the
30// `HashMap`.
31//
32// Additionally, `HashMap` owns its `seize::Collector` and never exposes it,
33// so multiple threads cannot be involved in reclamation without sharing the
34// `HashMap` itself. If this was not true, we would require stricter bounds
35// on `HashMap` operations themselves.
36unsafe impl<K: Send + Sync, V: Send + Sync, S: Sync> Sync for HashMap<K, V, S> {}
37
38/// A builder for a [`HashMap`].
39///
40/// # Examples
41///
42/// ```rust
43/// use papaya::{HashMap, ResizeMode};
44/// use seize::Collector;
45/// use std::collections::hash_map::RandomState;
46///
47/// let map: HashMap<i32, i32> = HashMap::builder()
48/// // Set the initial capacity.
49/// .capacity(2048)
50/// // Set the hasher.
51/// .hasher(RandomState::new())
52/// // Set the resize mode.
53/// .resize_mode(ResizeMode::Blocking)
54/// // Set a custom garbage collector.
55/// .collector(Collector::new().batch_size(128))
56/// // Construct the hash map.
57/// .build();
58/// ```
59pub struct HashMapBuilder<K, V, S = RandomState> {
60 hasher: S,
61 capacity: usize,
62 collector: Collector,
63 resize_mode: ResizeMode,
64 _kv: PhantomData<(K, V)>,
65}
66
67impl<K, V> HashMapBuilder<K, V> {
68 /// Set the hash builder used to hash keys.
69 ///
70 /// Warning: `hash_builder` is normally randomly generated, and is designed
71 /// to allow HashMaps to be resistant to attacks that cause many collisions
72 /// and very poor performance. Setting it manually using this function can
73 /// expose a DoS attack vector.
74 ///
75 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
76 /// the HashMap to be useful, see its documentation for details.
77 pub fn hasher<S>(self, hasher: S) -> HashMapBuilder<K, V, S> {
78 HashMapBuilder {
79 hasher,
80 capacity: self.capacity,
81 collector: self.collector,
82 resize_mode: self.resize_mode,
83 _kv: PhantomData,
84 }
85 }
86}
87
88impl<K, V, S> HashMapBuilder<K, V, S> {
89 /// Set the initial capacity of the map.
90 ///
91 /// The table should be able to hold at least `capacity` elements before resizing.
92 /// However, the capacity is an estimate, and the table may prematurely resize due
93 /// to poor hash distribution. If `capacity` is 0, the hash map will not allocate.
94 pub fn capacity(self, capacity: usize) -> HashMapBuilder<K, V, S> {
95 HashMapBuilder {
96 capacity,
97 hasher: self.hasher,
98 collector: self.collector,
99 resize_mode: self.resize_mode,
100 _kv: PhantomData,
101 }
102 }
103
104 /// Set the resizing mode of the map. See [`ResizeMode`] for details.
105 pub fn resize_mode(self, resize_mode: ResizeMode) -> Self {
106 HashMapBuilder {
107 resize_mode,
108 hasher: self.hasher,
109 capacity: self.capacity,
110 collector: self.collector,
111 _kv: PhantomData,
112 }
113 }
114
115 /// Set the [`seize::Collector`] used for garbage collection.
116 ///
117 /// This method may be useful when you want more control over garbage collection.
118 ///
119 /// Note that all `Guard` references used to access the map must be produced by
120 /// the provided `collector`.
121 pub fn collector(self, collector: Collector) -> Self {
122 HashMapBuilder {
123 collector,
124 hasher: self.hasher,
125 capacity: self.capacity,
126 resize_mode: self.resize_mode,
127 _kv: PhantomData,
128 }
129 }
130
131 /// Construct a [`HashMap`] from the builder, using the configured options.
132 pub fn build(self) -> HashMap<K, V, S> {
133 HashMap {
134 raw: raw::HashMap::new(self.capacity, self.hasher, self.collector, self.resize_mode),
135 }
136 }
137}
138
139impl<K, V, S> fmt::Debug for HashMapBuilder<K, V, S> {
140 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
141 f.debug_struct("HashMapBuilder")
142 .field("capacity", &self.capacity)
143 .field("collector", &self.collector)
144 .field("resize_mode", &self.resize_mode)
145 .finish()
146 }
147}
148
149/// Resize behavior for a [`HashMap`].
150///
151/// Hash maps must resize when the underlying table becomes full, migrating all key and value pairs
152/// to a new table. This type allows you to configure the resizing behavior when passed to
153/// [`HashMapBuilder::resize_mode`].
154#[derive(Debug)]
155pub enum ResizeMode {
156 /// Writers copy a constant number of key/value pairs to the new table before making
157 /// progress.
158 ///
159 /// Incremental resizes avoids latency spikes that can occur when insert operations have
160 /// to resize a large table. However, they reduce parallelism during the resize and so can reduce
161 /// overall throughput. Incremental resizing also means reads or write operations during an
162 /// in-progress resize may have to search both the current and new table before succeeding, trading
163 /// off median latency during a resize for tail latency.
164 ///
165 /// This is the default resize mode, with a chunk size of `64`.
166 Incremental(usize),
167 /// All writes to the map must wait till the resize completes before making progress.
168 ///
169 /// Blocking resizes tend to be better in terms of throughput, especially in setups with
170 /// multiple writers that can perform the resize in parallel. However, they can lead to latency
171 /// spikes for insert operations that have to resize large tables.
172 ///
173 /// If insert latency is not a concern, such as if the keys in your map are stable, enabling blocking
174 /// resizes may yield better performance.
175 ///
176 /// Blocking resizing may also be a better option if you rely heavily on iteration or similar
177 /// operations, as they require completing any in-progress resizes for consistency.
178 Blocking,
179}
180
181impl Default for ResizeMode {
182 fn default() -> Self {
183 // Incremental resizing is a good default for most workloads as it avoids
184 // unexpected latency spikes.
185 ResizeMode::Incremental(64)
186 }
187}
188
189impl<K, V> HashMap<K, V> {
190 /// Creates an empty `HashMap`.
191 ///
192 /// The hash map is initially created with a capacity of 0, so it will not allocate
193 /// until it is first inserted into.
194 ///
195 /// # Examples
196 ///
197 /// ```
198 /// use papaya::HashMap;
199 /// let map: HashMap<&str, i32> = HashMap::new();
200 /// ```
201 pub fn new() -> HashMap<K, V> {
202 HashMap::with_capacity_and_hasher(0, RandomState::new())
203 }
204
205 /// Creates an empty `HashMap` with the specified capacity.
206 ///
207 /// The table should be able to hold at least `capacity` elements before resizing.
208 /// However, the capacity is an estimate, and the table may prematurely resize due
209 /// to poor hash distribution. If `capacity` is 0, the hash map will not allocate.
210 ///
211 /// Note that the `HashMap` may grow and shrink as elements are inserted or removed,
212 /// but it is guaranteed to never shrink below the initial capacity.
213 ///
214 /// # Examples
215 ///
216 /// ```
217 /// use papaya::HashMap;
218 /// let map: HashMap<&str, i32> = HashMap::with_capacity(10);
219 /// ```
220 pub fn with_capacity(capacity: usize) -> HashMap<K, V> {
221 HashMap::with_capacity_and_hasher(capacity, RandomState::new())
222 }
223
224 /// Returns a builder for a `HashMap`.
225 ///
226 /// The builder can be used for more complex configuration, such as using
227 /// a custom [`Collector`], or [`ResizeMode`].
228 pub fn builder() -> HashMapBuilder<K, V> {
229 HashMapBuilder {
230 capacity: 0,
231 hasher: RandomState::default(),
232 collector: Collector::new(),
233 resize_mode: ResizeMode::default(),
234 _kv: PhantomData,
235 }
236 }
237}
238
239impl<K, V, S> Default for HashMap<K, V, S>
240where
241 S: Default,
242{
243 fn default() -> Self {
244 HashMap::with_hasher(S::default())
245 }
246}
247
248impl<K, V, S> HashMap<K, V, S> {
249 /// Creates an empty `HashMap` which will use the given hash builder to hash
250 /// keys.
251 ///
252 /// Warning: `hash_builder` is normally randomly generated, and is designed
253 /// to allow HashMaps to be resistant to attacks that cause many collisions
254 /// and very poor performance. Setting it manually using this function can
255 /// expose a DoS attack vector.
256 ///
257 /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
258 /// the HashMap to be useful, see its documentation for details.
259 ///
260 /// # Examples
261 ///
262 /// ```
263 /// use papaya::HashMap;
264 /// use std::hash::RandomState;
265 ///
266 /// let s = RandomState::new();
267 /// let map = HashMap::with_hasher(s);
268 /// map.pin().insert(1, 2);
269 /// ```
270 pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S> {
271 HashMap::with_capacity_and_hasher(0, hash_builder)
272 }
273
274 /// Creates an empty `HashMap` with at least the specified capacity, using
275 /// `hash_builder` to hash the keys.
276 ///
277 /// The table should be able to hold at least `capacity` elements before resizing.
278 /// However, the capacity is an estimate, and the table may prematurely resize due
279 /// to poor hash distribution. If `capacity` is 0, the hash map will not allocate.
280 ///
281 /// Warning: `hash_builder` is normally randomly generated, and is designed
282 /// to allow HashMaps to be resistant to attacks that cause many collisions
283 /// and very poor performance. Setting it manually using this function can
284 /// expose a DoS attack vector.
285 ///
286 /// The `hasher` passed should implement the [`BuildHasher`] trait for
287 /// the HashMap to be useful, see its documentation for details.
288 ///
289 /// # Examples
290 ///
291 /// ```
292 /// use papaya::HashMap;
293 /// use std::hash::RandomState;
294 ///
295 /// let s = RandomState::new();
296 /// let map = HashMap::with_capacity_and_hasher(10, s);
297 /// map.pin().insert(1, 2);
298 /// ```
299 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashMap<K, V, S> {
300 HashMap {
301 raw: raw::HashMap::new(
302 capacity,
303 hash_builder,
304 Collector::default(),
305 ResizeMode::default(),
306 ),
307 }
308 }
309
310 /// Returns a pinned reference to the map.
311 ///
312 /// The returned reference manages a guard internally, preventing garbage collection
313 /// for as long as it is held. See the [crate-level documentation](crate#usage) for details.
314 #[inline]
315 pub fn pin(&self) -> HashMapRef<'_, K, V, S, LocalGuard<'_>> {
316 HashMapRef {
317 guard: self.raw.guard(),
318 map: self,
319 }
320 }
321
322 /// Returns a pinned reference to the map.
323 ///
324 /// Unlike [`HashMap::pin`], the returned reference implements `Send` and `Sync`,
325 /// allowing it to be held across `.await` points in work-stealing schedulers.
326 /// This is especially useful for iterators.
327 ///
328 /// The returned reference manages a guard internally, preventing garbage collection
329 /// for as long as it is held. See the [crate-level documentation](crate#usage) for details.
330 #[inline]
331 pub fn pin_owned(&self) -> HashMapRef<'_, K, V, S, OwnedGuard<'_>> {
332 HashMapRef {
333 guard: self.raw.owned_guard(),
334 map: self,
335 }
336 }
337
338 /// Returns a guard for use with this map.
339 ///
340 /// Note that holding on to a guard prevents garbage collection.
341 /// See the [crate-level documentation](crate#usage) for details.
342 #[inline]
343 pub fn guard(&self) -> LocalGuard<'_> {
344 self.raw.collector().enter()
345 }
346
347 /// Returns an owned guard for use with this map.
348 ///
349 /// Owned guards implement `Send` and `Sync`, allowing them to be held across
350 /// `.await` points in work-stealing schedulers. This is especially useful
351 /// for iterators.
352 ///
353 /// Note that holding on to a guard prevents garbage collection.
354 /// See the [crate-level documentation](crate#usage) for details.
355 #[inline]
356 pub fn owned_guard(&self) -> OwnedGuard<'_> {
357 self.raw.collector().enter_owned()
358 }
359}
360
361impl<K, V, S> HashMap<K, V, S>
362where
363 K: Hash + Eq,
364 S: BuildHasher,
365{
366 /// Returns the number of entries in the map.
367 ///
368 /// # Examples
369 ///
370 /// ```
371 /// use papaya::HashMap;
372 ///
373 /// let map = HashMap::new();
374 ///
375 /// map.pin().insert(1, "a");
376 /// map.pin().insert(2, "b");
377 /// assert!(map.len() == 2);
378 /// ```
379 #[inline]
380 pub fn len(&self) -> usize {
381 self.raw.len()
382 }
383
384 /// Returns `true` if the map is empty. Otherwise returns `false`.
385 ///
386 /// # Examples
387 ///
388 /// ```
389 /// use papaya::HashMap;
390 ///
391 /// let map = HashMap::new();
392 /// assert!(map.is_empty());
393 /// map.pin().insert("a", 1);
394 /// assert!(!map.is_empty());
395 /// ```
396 #[inline]
397 pub fn is_empty(&self) -> bool {
398 self.len() == 0
399 }
400
401 /// Returns `true` if the map contains a value for the specified key.
402 ///
403 /// The key may be any borrowed form of the map's key type, but
404 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
405 /// the key type.
406 ///
407 /// [`Eq`]: std::cmp::Eq
408 /// [`Hash`]: std::hash::Hash
409 ///
410 ///
411 /// # Examples
412 ///
413 /// ```
414 /// use papaya::HashMap;
415 ///
416 /// let map = HashMap::new();
417 /// map.pin().insert(1, "a");
418 /// assert_eq!(map.pin().contains_key(&1), true);
419 /// assert_eq!(map.pin().contains_key(&2), false);
420 /// ```
421 #[inline]
422 pub fn contains_key<Q>(&self, key: &Q, guard: &impl Guard) -> bool
423 where
424 Q: Equivalent<K> + Hash + ?Sized,
425 {
426 self.get(key, self.raw.verify(guard)).is_some()
427 }
428
429 /// Returns a reference to the value corresponding to the key.
430 ///
431 /// The key may be any borrowed form of the map's key type, but
432 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
433 /// the key type.
434 ///
435 /// [`Eq`]: std::cmp::Eq
436 /// [`Hash`]: std::hash::Hash
437 ///
438 /// # Examples
439 ///
440 /// ```
441 /// use papaya::HashMap;
442 ///
443 /// let map = HashMap::new();
444 /// map.pin().insert(1, "a");
445 /// assert_eq!(map.pin().get(&1), Some(&"a"));
446 /// assert_eq!(map.pin().get(&2), None);
447 /// ```
448 #[inline]
449 pub fn get<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<&'g V>
450 where
451 K: 'g,
452 Q: Equivalent<K> + Hash + ?Sized,
453 {
454 match self.raw.get(key, self.raw.verify(guard)) {
455 Some((_, v)) => Some(v),
456 None => None,
457 }
458 }
459
460 /// Returns the key-value pair corresponding to the supplied key.
461 ///
462 /// The supplied key may be any borrowed form of the map's key type, but
463 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
464 /// the key type.
465 ///
466 /// [`Eq`]: std::cmp::Eq
467 /// [`Hash`]: std::hash::Hash
468 ///
469 /// # Examples
470 ///
471 /// ```
472 /// use papaya::HashMap;
473 ///
474 /// let map = HashMap::new();
475 /// map.pin().insert(1, "a");
476 /// assert_eq!(map.pin().get_key_value(&1), Some((&1, &"a")));
477 /// assert_eq!(map.pin().get_key_value(&2), None);
478 /// ```
479 #[inline]
480 pub fn get_key_value<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<(&'g K, &'g V)>
481 where
482 Q: Equivalent<K> + Hash + ?Sized,
483 {
484 self.raw.get(key, self.raw.verify(guard))
485 }
486
487 /// Inserts a key-value pair into the map.
488 ///
489 /// If the map did not have this key present, [`None`] is returned.
490 ///
491 /// If the map did have this key present, the value is updated, and the old
492 /// value is returned. The key is not updated, though; this matters for
493 /// types that can be `==` without being identical. See the [standard library
494 /// documentation] for details.
495 ///
496 /// [standard library documentation]: https://doc.rust-lang.org/std/collections/index.html#insert-and-complex-keys
497 ///
498 /// # Examples
499 ///
500 /// ```
501 /// use papaya::HashMap;
502 ///
503 /// let map = HashMap::new();
504 /// assert_eq!(map.pin().insert(37, "a"), None);
505 /// assert_eq!(map.pin().is_empty(), false);
506 ///
507 /// map.pin().insert(37, "b");
508 /// assert_eq!(map.pin().insert(37, "c"), Some(&"b"));
509 /// assert_eq!(map.pin().get(&37), Some(&"c"));
510 /// ```
511 #[inline]
512 pub fn insert<'g>(&self, key: K, value: V, guard: &'g impl Guard) -> Option<&'g V> {
513 match self.raw.insert(key, value, true, self.raw.verify(guard)) {
514 InsertResult::Inserted(_) => None,
515 InsertResult::Replaced(value) => Some(value),
516 InsertResult::Error { .. } => unreachable!(),
517 }
518 }
519
520 /// Tries to insert a key-value pair into the map, and returns
521 /// a reference to the value that was inserted.
522 ///
523 /// If the map already had this key present, nothing is updated, and
524 /// an error containing the existing value is returned.
525 ///
526 /// # Examples
527 ///
528 /// ```
529 /// use papaya::HashMap;
530 ///
531 /// let map = HashMap::new();
532 /// let map = map.pin();
533 ///
534 /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
535 ///
536 /// let err = map.try_insert(37, "b").unwrap_err();
537 /// assert_eq!(err.current, &"a");
538 /// assert_eq!(err.not_inserted, "b");
539 /// ```
540 #[inline]
541 pub fn try_insert<'g>(
542 &self,
543 key: K,
544 value: V,
545 guard: &'g impl Guard,
546 ) -> Result<&'g V, OccupiedError<'g, V>> {
547 // Safety: Checked the guard above.
548 match self.raw.insert(key, value, false, self.raw.verify(guard)) {
549 InsertResult::Inserted(value) => Ok(value),
550 InsertResult::Error {
551 current,
552 not_inserted,
553 } => Err(OccupiedError {
554 current,
555 not_inserted,
556 }),
557 InsertResult::Replaced(_) => unreachable!(),
558 }
559 }
560
561 /// Tries to insert a key and value computed from a closure into the map,
562 /// and returns a reference to the value that was inserted.
563 ///
564 /// If the map already had this key present, nothing is updated, and
565 /// the existing value is returned.
566 ///
567 /// # Examples
568 ///
569 /// ```
570 /// use papaya::HashMap;
571 ///
572 /// let map = HashMap::new();
573 /// let map = map.pin();
574 ///
575 /// assert_eq!(map.try_insert_with(37, || "a").unwrap(), &"a");
576 ///
577 /// let current = map.try_insert_with(37, || "b").unwrap_err();
578 /// assert_eq!(current, &"a");
579 /// ```
580 #[inline]
581 pub fn try_insert_with<'g, F>(
582 &self,
583 key: K,
584 f: F,
585 guard: &'g impl Guard,
586 ) -> Result<&'g V, &'g V>
587 where
588 F: FnOnce() -> V,
589 K: 'g,
590 {
591 self.raw.try_insert_with(key, f, self.raw.verify(guard))
592 }
593
594 /// Returns a reference to the value corresponding to the key, or inserts a default value.
595 ///
596 /// If the given key is present, the corresponding value is returned. If it is not present,
597 /// the provided `value` is inserted, and a reference to the newly inserted value is returned.
598 ///
599 /// # Examples
600 ///
601 /// ```
602 /// use papaya::HashMap;
603 ///
604 /// let map = HashMap::new();
605 /// assert_eq!(map.pin().get_or_insert("a", 3), &3);
606 /// assert_eq!(map.pin().get_or_insert("a", 6), &3);
607 /// ```
608 #[inline]
609 pub fn get_or_insert<'g>(&self, key: K, value: V, guard: &'g impl Guard) -> &'g V {
610 // Note that we use `try_insert` instead of `compute` or `get_or_insert_with` here, as it
611 // allows us to avoid the closure indirection.
612 match self.try_insert(key, value, guard) {
613 Ok(inserted) => inserted,
614 Err(OccupiedError { current, .. }) => current,
615 }
616 }
617
618 /// Returns a reference to the value corresponding to the key, or inserts a default value
619 /// computed from a closure.
620 ///
621 /// If the given key is present, the corresponding value is returned. If it is not present,
622 /// the value computed from `f` is inserted, and a reference to the newly inserted value is
623 /// returned.
624 ///
625 ///
626 /// # Examples
627 ///
628 /// ```
629 /// use papaya::HashMap;
630 ///
631 /// let map = HashMap::new();
632 /// assert_eq!(map.pin().get_or_insert_with("a", || 3), &3);
633 /// assert_eq!(map.pin().get_or_insert_with("a", || 6), &3);
634 /// ```
635 #[inline]
636 pub fn get_or_insert_with<'g, F>(&self, key: K, f: F, guard: &'g impl Guard) -> &'g V
637 where
638 F: FnOnce() -> V,
639 K: 'g,
640 {
641 self.raw.get_or_insert_with(key, f, self.raw.verify(guard))
642 }
643
644 /// Updates an existing entry atomically.
645 ///
646 /// If the value for the specified `key` is present, the new value is computed and stored the
647 /// using the provided update function, and the new value is returned. Otherwise, `None`
648 /// is returned.
649 ///
650 ///
651 /// The update function is given the current value associated with the given key and returns the
652 /// new value to be stored. The operation is applied atomically only if the state of the entry remains
653 /// the same, meaning that it is not concurrently modified in any way. If the entry is
654 /// modified, the operation is retried with the new entry, similar to a traditional [compare-and-swap](https://en.wikipedia.org/wiki/Compare-and-swap)
655 /// operation.
656 ///
657 /// Note that the `update` function should be pure as it may be called multiple times, and the output
658 /// for a given entry may be memoized across retries.
659 ///
660 ///
661 /// # Examples
662 ///
663 /// ```
664 /// use papaya::HashMap;
665 ///
666 /// let map = HashMap::new();
667 /// map.pin().insert("a", 1);
668 /// assert_eq!(map.pin().get(&"a"), Some(&1));
669 ///
670 /// map.pin().update("a", |v| v + 1);
671 /// assert_eq!(map.pin().get(&"a"), Some(&2));
672 /// ```
673 #[inline]
674 pub fn update<'g, F>(&self, key: K, update: F, guard: &'g impl Guard) -> Option<&'g V>
675 where
676 F: Fn(&V) -> V,
677 K: 'g,
678 {
679 self.raw.update(key, update, self.raw.verify(guard))
680 }
681
682 /// Updates an existing entry or inserts a default value.
683 ///
684 /// If the value for the specified `key` is present, the new value is computed and stored the
685 /// using the provided update function, and the new value is returned. Otherwise, the provided
686 /// `value` is inserted into the map, and a reference to the newly inserted value is returned.
687 ///
688 /// See [`HashMap::update`] for details about how atomic updates are performed.
689 ///
690 /// # Examples
691 ///
692 /// ```
693 /// use papaya::HashMap;
694 ///
695 /// let map = HashMap::new();
696 /// assert_eq!(*map.pin().update_or_insert("a", |i| i + 1, 0), 0);
697 /// assert_eq!(*map.pin().update_or_insert("a", |i| i + 1, 0), 1);
698 /// ```
699 #[inline]
700 pub fn update_or_insert<'g, F>(
701 &self,
702 key: K,
703 update: F,
704 value: V,
705 guard: &'g impl Guard,
706 ) -> &'g V
707 where
708 F: Fn(&V) -> V,
709 K: 'g,
710 {
711 self.update_or_insert_with(key, update, || value, guard)
712 }
713
714 /// Updates an existing entry or inserts a default value computed from a closure.
715 ///
716 /// If the value for the specified `key` is present, the new value is computed and stored the
717 /// using the provided update function, and the new value is returned. Otherwise, the value
718 /// computed by `f` is inserted into the map, and a reference to the newly inserted value is
719 /// returned.
720 ///
721 /// See [`HashMap::update`] for details about how atomic updates are performed.
722 ///
723 /// # Examples
724 ///
725 /// ```
726 /// use papaya::HashMap;
727 ///
728 /// let map = HashMap::new();
729 /// assert_eq!(*map.pin().update_or_insert_with("a", |i| i + 1, || 0), 0);
730 /// assert_eq!(*map.pin().update_or_insert_with("a", |i| i + 1, || 0), 1);
731 /// ```
732 #[inline]
733 pub fn update_or_insert_with<'g, U, F>(
734 &self,
735 key: K,
736 update: U,
737 f: F,
738 guard: &'g impl Guard,
739 ) -> &'g V
740 where
741 F: FnOnce() -> V,
742 U: Fn(&V) -> V,
743 K: 'g,
744 {
745 self.raw
746 .update_or_insert_with(key, update, f, self.raw.verify(guard))
747 }
748
749 /// Updates an entry with a compare-and-swap (CAS) function.
750 ///
751 /// This method allows you to perform complex operations on the map atomically. The `compute`
752 /// closure is given the current state of the entry and returns the operation that should be
753 /// performed. The operation is applied atomically only if the state of the entry remains the same,
754 /// meaning it is not concurrently modified in any way.
755 ///
756 /// Note that the `compute` function should be pure as it may be called multiple times, and
757 /// the output for a given entry may be memoized across retries.
758 ///
759 /// In most cases you can avoid this method and instead use a higher-level atomic operation.
760 /// See the [crate-level documentation](crate#atomic-operations) for details.
761 ///
762 /// # Examples
763 ///
764 /// ```rust
765 /// use papaya::{HashMap, Operation, Compute};
766 ///
767 /// let map = HashMap::new();
768 /// let map = map.pin();
769 ///
770 /// let compute = |entry| match entry {
771 /// // Remove the value if it is even.
772 /// Some((_key, value)) if value % 2 == 0 => {
773 /// Operation::Remove
774 /// }
775 ///
776 /// // Increment the value if it is odd.
777 /// Some((_key, value)) => {
778 /// Operation::Insert(value + 1)
779 /// }
780 ///
781 /// // Do nothing if the key does not exist
782 /// None => Operation::Abort(()),
783 /// };
784 ///
785 /// assert_eq!(map.compute('A', compute), Compute::Aborted(()));
786 ///
787 /// map.insert('A', 1);
788 /// assert_eq!(map.compute('A', compute), Compute::Updated {
789 /// old: (&'A', &1),
790 /// new: (&'A', &2),
791 /// });
792 /// assert_eq!(map.compute('A', compute), Compute::Removed(&'A', &2));
793 /// ```
794 #[inline]
795 pub fn compute<'g, F, T>(
796 &self,
797 key: K,
798 compute: F,
799 guard: &'g impl Guard,
800 ) -> Compute<'g, K, V, T>
801 where
802 F: FnMut(Option<(&'g K, &'g V)>) -> Operation<V, T>,
803 {
804 self.raw.compute(key, compute, self.raw.verify(guard))
805 }
806
807 /// Removes a key from the map, returning the value at the key if the key
808 /// was previously in the map.
809 ///
810 /// The key may be any borrowed form of the map's key type, but
811 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
812 /// the key type.
813 ///
814 /// # Examples
815 ///
816 /// ```
817 /// use papaya::HashMap;
818 ///
819 /// let map = HashMap::new();
820 /// map.pin().insert(1, "a");
821 /// assert_eq!(map.pin().remove(&1), Some(&"a"));
822 /// assert_eq!(map.pin().remove(&1), None);
823 /// ```
824 #[inline]
825 pub fn remove<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<&'g V>
826 where
827 K: 'g,
828 Q: Equivalent<K> + Hash + ?Sized,
829 {
830 match self.raw.remove(key, self.raw.verify(guard)) {
831 Some((_, value)) => Some(value),
832 None => None,
833 }
834 }
835
836 /// Removes a key from the map, returning the stored key and value if the
837 /// key was previously in the map.
838 ///
839 /// The key may be any borrowed form of the map's key type, but
840 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
841 /// the key type.
842 ///
843 /// # Examples
844 ///
845 /// ```
846 /// use papaya::HashMap;
847 ///
848 /// let map = HashMap::new();
849 /// map.pin().insert(1, "a");
850 /// assert_eq!(map.pin().get(&1), Some(&"a"));
851 /// assert_eq!(map.pin().remove_entry(&1), Some((&1, &"a")));
852 /// assert_eq!(map.pin().remove(&1), None);
853 /// ```
854 #[inline]
855 pub fn remove_entry<'g, Q>(&self, key: &Q, guard: &'g impl Guard) -> Option<(&'g K, &'g V)>
856 where
857 K: 'g,
858 Q: Equivalent<K> + Hash + ?Sized,
859 {
860 self.raw.remove(key, self.raw.verify(guard))
861 }
862
863 /// Conditionally removes a key from the map based on the provided closure.
864 ///
865 /// If the key is found in the map and the closure returns `true` given the key and its value,
866 /// the key and value are returned successfully. Note that the returned entry is guaranteed to
867 /// be the same entry that the closure returned `true` for. However, the closure returning `true`
868 /// does not guarantee that the entry is removed in the presence of concurrent modifications.
869 ///
870 /// If the key is not found in the map, `Ok(None)` is returned.
871 ///
872 /// If the closure returns `false`, an error is returned containing the entry provided to the closure.
873 ///
874 /// # Examples
875 ///
876 /// ```
877 /// use papaya::HashMap;
878 ///
879 /// let map = HashMap::new();
880 /// map.pin().insert(1, "a");
881 ///
882 /// assert_eq!(map.pin().remove_if(&1, |k, v| *v == "b"), Err((&1, &"a")));
883 /// assert_eq!(map.pin().get(&1), Some(&"a"));
884 /// assert_eq!(map.pin().remove_if(&1, |k, v| *v == "a"), Ok(Some((&1, &"a"))));
885 /// assert_eq!(map.pin().remove_if(&1, |_, _| true), Ok(None));
886 /// ```
887 #[inline]
888 pub fn remove_if<'g, Q, F>(
889 &self,
890 key: &Q,
891 should_remove: F,
892 guard: &'g impl Guard,
893 ) -> Result<Option<(&'g K, &'g V)>, (&'g K, &'g V)>
894 where
895 Q: Equivalent<K> + Hash + ?Sized,
896 F: FnMut(&K, &V) -> bool,
897 {
898 self.raw
899 .remove_if(key, should_remove, self.raw.verify(guard))
900 }
901
902 /// Tries to reserve capacity for `additional` more elements to be inserted
903 /// in the `HashMap`.
904 ///
905 /// After calling this method, the table should be able to hold at least `capacity` elements
906 /// before resizing. However, the capacity is an estimate, and the table may prematurely resize
907 /// due to poor hash distribution. The collection may also reserve more space to avoid frequent
908 /// reallocations.
909 ///
910 /// # Panics
911 ///
912 /// Panics if the new allocation size overflows `usize`.
913 ///
914 /// # Examples
915 ///
916 /// ```
917 /// use papaya::HashMap;
918 ///
919 /// let map: HashMap<&str, i32> = HashMap::new();
920 /// map.pin().reserve(10);
921 /// ```
922 #[inline]
923 pub fn reserve(&self, additional: usize, guard: &impl Guard) {
924 self.raw.reserve(additional, self.raw.verify(guard))
925 }
926
927 /// Clears the map, removing all key-value pairs.
928 ///
929 /// Note that this method will block until any in-progress resizes are
930 /// completed before proceeding. See the [consistency](crate#consistency)
931 /// section for details.
932 ///
933 /// # Examples
934 ///
935 /// ```
936 /// use papaya::HashMap;
937 ///
938 /// let map = HashMap::new();
939 ///
940 /// map.pin().insert(1, "a");
941 /// map.pin().clear();
942 /// assert!(map.pin().is_empty());
943 /// ```
944 #[inline]
945 pub fn clear(&self, guard: &impl Guard) {
946 self.raw.clear(self.raw.verify(guard))
947 }
948
949 /// Retains only the elements specified by the predicate.
950 ///
951 /// In other words, remove all pairs `(k, v)` for which `f(&k, &v)` returns `false`.
952 /// The elements are visited in unsorted (and unspecified) order.
953 ///
954 /// Note the function may be called more than once for a given key if its value is
955 /// concurrently modified during removal.
956 ///
957 /// Additionally, this method will block until any in-progress resizes are
958 /// completed before proceeding. See the [consistency](crate#consistency)
959 /// section for details.
960 ///
961 /// # Examples
962 ///
963 /// ```
964 /// use papaya::HashMap;
965 ///
966 /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x * 10)).collect();
967 /// map.pin().retain(|&k, _| k % 2 == 0);
968 /// assert_eq!(map.len(), 4);
969 /// ```
970 #[inline]
971 pub fn retain<F>(&self, f: F, guard: &impl Guard)
972 where
973 F: FnMut(&K, &V) -> bool,
974 {
975 self.raw.retain(f, self.raw.verify(guard))
976 }
977
978 /// An iterator visiting all key-value pairs in arbitrary order.
979 /// The iterator element type is `(&K, &V)`.
980 ///
981 /// Note that this method will block until any in-progress resizes are
982 /// completed before proceeding. See the [consistency](crate#consistency)
983 /// section for details.
984 ///
985 /// # Examples
986 ///
987 /// ```
988 /// use papaya::HashMap;
989 ///
990 /// let map = HashMap::from([
991 /// ("a", 1),
992 /// ("b", 2),
993 /// ("c", 3),
994 /// ]);
995 ///
996 /// for (key, val) in map.pin().iter() {
997 /// println!("key: {key} val: {val}");
998 /// }
999 #[inline]
1000 pub fn iter<'g, G>(&self, guard: &'g G) -> Iter<'g, K, V, G>
1001 where
1002 G: Guard,
1003 {
1004 Iter {
1005 raw: self.raw.iter(self.raw.verify(guard)),
1006 }
1007 }
1008
1009 /// An iterator visiting all keys in arbitrary order.
1010 /// The iterator element type is `&K`.
1011 ///
1012 /// Note that this method will block until any in-progress resizes are
1013 /// completed before proceeding. See the [consistency](crate#consistency)
1014 /// section for details.
1015 ///
1016 /// # Examples
1017 ///
1018 /// ```
1019 /// use papaya::HashMap;
1020 ///
1021 /// let map = HashMap::from([
1022 /// ("a", 1),
1023 /// ("b", 2),
1024 /// ("c", 3),
1025 /// ]);
1026 ///
1027 /// for key in map.pin().keys() {
1028 /// println!("{key}");
1029 /// }
1030 /// ```
1031 #[inline]
1032 pub fn keys<'g, G>(&self, guard: &'g G) -> Keys<'g, K, V, G>
1033 where
1034 G: Guard,
1035 {
1036 Keys {
1037 iter: self.iter(guard),
1038 }
1039 }
1040
1041 /// An iterator visiting all values in arbitrary order.
1042 /// The iterator element type is `&V`.
1043 ///
1044 /// Note that this method will block until any in-progress resizes are
1045 /// completed before proceeding. See the [consistency](crate#consistency)
1046 /// section for details.
1047 ///
1048 /// # Examples
1049 ///
1050 /// ```
1051 /// use papaya::HashMap;
1052 ///
1053 /// let map = HashMap::from([
1054 /// ("a", 1),
1055 /// ("b", 2),
1056 /// ("c", 3),
1057 /// ]);
1058 ///
1059 /// for value in map.pin().values() {
1060 /// println!("{value}");
1061 /// }
1062 /// ```
1063 #[inline]
1064 pub fn values<'g, G>(&self, guard: &'g G) -> Values<'g, K, V, G>
1065 where
1066 G: Guard,
1067 {
1068 Values {
1069 iter: self.iter(guard),
1070 }
1071 }
1072}
1073
1074/// An operation to perform on given entry in a [`HashMap`].
1075///
1076/// See [`HashMap::compute`] for details.
1077#[derive(Debug, PartialEq, Eq)]
1078pub enum Operation<V, T> {
1079 /// Insert the given value.
1080 Insert(V),
1081
1082 /// Remove the entry from the map.
1083 Remove,
1084
1085 /// Abort the operation with the given value.
1086 Abort(T),
1087}
1088
1089/// The result of a [`compute`](HashMap::compute) operation.
1090///
1091/// Contains information about the [`Operation`] that was performed.
1092#[derive(Debug, PartialEq, Eq)]
1093pub enum Compute<'g, K, V, T> {
1094 /// The given entry was inserted.
1095 Inserted(&'g K, &'g V),
1096
1097 /// The entry was updated.
1098 Updated {
1099 /// The entry that was replaced.
1100 old: (&'g K, &'g V),
1101
1102 /// The entry that was inserted.
1103 new: (&'g K, &'g V),
1104 },
1105
1106 /// The given entry was removed.
1107 Removed(&'g K, &'g V),
1108
1109 /// The operation was aborted with the given value.
1110 Aborted(T),
1111}
1112
1113/// An error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
1114///
1115/// Contains the existing value, and the value that was not inserted.
1116#[derive(Debug, PartialEq, Eq)]
1117pub struct OccupiedError<'a, V: 'a> {
1118 /// The value in the map that was already present.
1119 pub current: &'a V,
1120 /// The value which was not inserted, because the entry was already occupied.
1121 pub not_inserted: V,
1122}
1123
1124impl<K, V, S> PartialEq for HashMap<K, V, S>
1125where
1126 K: Hash + Eq,
1127 V: PartialEq,
1128 S: BuildHasher,
1129{
1130 fn eq(&self, other: &Self) -> bool {
1131 if self.len() != other.len() {
1132 return false;
1133 }
1134
1135 let (guard1, guard2) = (&self.guard(), &other.guard());
1136
1137 let mut iter = self.iter(guard1);
1138 iter.all(|(key, value)| other.get(key, guard2).map_or(false, |v| *value == *v))
1139 }
1140}
1141
1142impl<K, V, S> Eq for HashMap<K, V, S>
1143where
1144 K: Hash + Eq,
1145 V: Eq,
1146 S: BuildHasher,
1147{
1148}
1149
1150impl<K, V, S> fmt::Debug for HashMap<K, V, S>
1151where
1152 K: Hash + Eq + fmt::Debug,
1153 V: fmt::Debug,
1154 S: BuildHasher,
1155{
1156 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1157 let guard = self.guard();
1158 f.debug_map().entries(self.iter(&guard)).finish()
1159 }
1160}
1161
1162impl<K, V, S> Extend<(K, V)> for &HashMap<K, V, S>
1163where
1164 K: Hash + Eq,
1165 S: BuildHasher,
1166{
1167 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
1168 // from `hashbrown::HashMap::extend`:
1169 // Keys may be already present or show multiple times in the iterator.
1170 // Reserve the entire hint lower bound if the map is empty.
1171 // Otherwise reserve half the hint (rounded up), so the map
1172 // will only resize twice in the worst case.
1173 let iter = iter.into_iter();
1174 let reserve = if self.is_empty() {
1175 iter.size_hint().0
1176 } else {
1177 (iter.size_hint().0 + 1) / 2
1178 };
1179
1180 let guard = self.guard();
1181 self.reserve(reserve, &guard);
1182
1183 for (key, value) in iter {
1184 self.insert(key, value, &guard);
1185 }
1186 }
1187}
1188
1189impl<'a, K, V, S> Extend<(&'a K, &'a V)> for &HashMap<K, V, S>
1190where
1191 K: Copy + Hash + Eq,
1192 V: Copy,
1193 S: BuildHasher,
1194{
1195 fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
1196 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1197 }
1198}
1199
1200impl<K, V, const N: usize> From<[(K, V); N]> for HashMap<K, V, RandomState>
1201where
1202 K: Hash + Eq,
1203{
1204 fn from(arr: [(K, V); N]) -> Self {
1205 HashMap::from_iter(arr)
1206 }
1207}
1208
1209impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
1210where
1211 K: Hash + Eq,
1212 S: BuildHasher + Default,
1213{
1214 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
1215 let mut iter = iter.into_iter();
1216
1217 if let Some((key, value)) = iter.next() {
1218 let (lower, _) = iter.size_hint();
1219 let map = HashMap::with_capacity_and_hasher(lower.saturating_add(1), S::default());
1220
1221 // Ideally we could use an unprotected guard here. However, `insert`
1222 // returns references to values that were replaced and retired, so
1223 // we need a "real" guard. A `raw_insert` method that strictly returns
1224 // pointers would fix this.
1225 {
1226 let map = map.pin();
1227 map.insert(key, value);
1228 for (key, value) in iter {
1229 map.insert(key, value);
1230 }
1231 }
1232
1233 map
1234 } else {
1235 Self::default()
1236 }
1237 }
1238}
1239
1240impl<K, V, S> Clone for HashMap<K, V, S>
1241where
1242 K: Clone + Hash + Eq,
1243 V: Clone,
1244 S: BuildHasher + Clone,
1245{
1246 fn clone(&self) -> HashMap<K, V, S> {
1247 let other = HashMap::builder()
1248 .capacity(self.len())
1249 .hasher(self.raw.hasher.clone())
1250 .collector(self.raw.collector().clone())
1251 .build();
1252
1253 {
1254 let (guard1, guard2) = (&self.guard(), &other.guard());
1255 for (key, value) in self.iter(guard1) {
1256 other.insert(key.clone(), value.clone(), guard2);
1257 }
1258 }
1259
1260 other
1261 }
1262}
1263
1264/// A pinned reference to a [`HashMap`].
1265///
1266/// This type is created with [`HashMap::pin`] and can be used to easily access a [`HashMap`]
1267/// without explicitly managing a guard. See the [crate-level documentation](crate#usage) for details.
1268pub struct HashMapRef<'map, K, V, S, G> {
1269 guard: MapGuard<G>,
1270 map: &'map HashMap<K, V, S>,
1271}
1272
1273impl<'map, K, V, S, G> HashMapRef<'map, K, V, S, G>
1274where
1275 K: Hash + Eq,
1276 S: BuildHasher,
1277 G: Guard,
1278{
1279 /// Returns a reference to the inner [`HashMap`].
1280 #[inline]
1281 pub fn map(&self) -> &'map HashMap<K, V, S> {
1282 self.map
1283 }
1284
1285 /// Returns the number of entries in the map.
1286 ///
1287 /// See [`HashMap::len`] for details.
1288 #[inline]
1289 pub fn len(&self) -> usize {
1290 self.map.raw.len()
1291 }
1292
1293 /// Returns `true` if the map is empty. Otherwise returns `false`.
1294 ///
1295 /// See [`HashMap::is_empty`] for details.
1296 #[inline]
1297 pub fn is_empty(&self) -> bool {
1298 self.len() == 0
1299 }
1300
1301 /// Returns `true` if the map contains a value for the specified key.
1302 ///
1303 /// See [`HashMap::contains_key`] for details.
1304 #[inline]
1305 pub fn contains_key<Q>(&self, key: &Q) -> bool
1306 where
1307 Q: Equivalent<K> + Hash + ?Sized,
1308 {
1309 self.get(key).is_some()
1310 }
1311
1312 /// Returns a reference to the value corresponding to the key.
1313 ///
1314 /// See [`HashMap::get`] for details.
1315 #[inline]
1316 pub fn get<Q>(&self, key: &Q) -> Option<&V>
1317 where
1318 Q: Equivalent<K> + Hash + ?Sized,
1319 {
1320 match self.map.raw.get(key, &self.guard) {
1321 Some((_, v)) => Some(v),
1322 None => None,
1323 }
1324 }
1325
1326 /// Returns the key-value pair corresponding to the supplied key.
1327 ///
1328 /// See [`HashMap::get_key_value`] for details.
1329 #[inline]
1330 pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
1331 where
1332 Q: Equivalent<K> + Hash + ?Sized,
1333 {
1334 self.map.raw.get(key, &self.guard)
1335 }
1336
1337 /// Inserts a key-value pair into the map.
1338 ///
1339 /// See [`HashMap::insert`] for details.
1340 #[inline]
1341 pub fn insert(&self, key: K, value: V) -> Option<&V> {
1342 match self.map.raw.insert(key, value, true, &self.guard) {
1343 InsertResult::Inserted(_) => None,
1344 InsertResult::Replaced(value) => Some(value),
1345 InsertResult::Error { .. } => unreachable!(),
1346 }
1347 }
1348
1349 /// Tries to insert a key-value pair into the map, and returns
1350 /// a reference to the value that was inserted.
1351 ///
1352 /// See [`HashMap::try_insert`] for details.
1353 #[inline]
1354 pub fn try_insert(&self, key: K, value: V) -> Result<&V, OccupiedError<'_, V>> {
1355 match self.map.raw.insert(key, value, false, &self.guard) {
1356 InsertResult::Inserted(value) => Ok(value),
1357 InsertResult::Error {
1358 current,
1359 not_inserted,
1360 } => Err(OccupiedError {
1361 current,
1362 not_inserted,
1363 }),
1364 InsertResult::Replaced(_) => unreachable!(),
1365 }
1366 }
1367
1368 /// Tries to insert a key and value computed from a closure into the map,
1369 /// and returns a reference to the value that was inserted.
1370 ///
1371 /// See [`HashMap::try_insert_with`] for details.
1372 #[inline]
1373 pub fn try_insert_with<F>(&self, key: K, f: F) -> Result<&V, &V>
1374 where
1375 F: FnOnce() -> V,
1376 {
1377 self.map.raw.try_insert_with(key, f, &self.guard)
1378 }
1379
1380 /// Returns a reference to the value corresponding to the key, or inserts a default value.
1381 ///
1382 /// See [`HashMap::get_or_insert`] for details.
1383 #[inline]
1384 pub fn get_or_insert(&self, key: K, value: V) -> &V {
1385 // Note that we use `try_insert` instead of `compute` or `get_or_insert_with` here, as it
1386 // allows us to avoid the closure indirection.
1387 match self.try_insert(key, value) {
1388 Ok(inserted) => inserted,
1389 Err(OccupiedError { current, .. }) => current,
1390 }
1391 }
1392
1393 /// Returns a reference to the value corresponding to the key, or inserts a default value
1394 /// computed from a closure.
1395 ///
1396 /// See [`HashMap::get_or_insert_with`] for details.
1397 #[inline]
1398 pub fn get_or_insert_with<F>(&self, key: K, f: F) -> &V
1399 where
1400 F: FnOnce() -> V,
1401 {
1402 self.map.raw.get_or_insert_with(key, f, &self.guard)
1403 }
1404
1405 /// Updates an existing entry atomically.
1406 ///
1407 /// See [`HashMap::update`] for details.
1408 #[inline]
1409 pub fn update<F>(&self, key: K, update: F) -> Option<&V>
1410 where
1411 F: Fn(&V) -> V,
1412 {
1413 self.map.raw.update(key, update, &self.guard)
1414 }
1415
1416 /// Updates an existing entry or inserts a default value.
1417 ///
1418 /// See [`HashMap::update_or_insert`] for details.
1419 #[inline]
1420 pub fn update_or_insert<F>(&self, key: K, update: F, value: V) -> &V
1421 where
1422 F: Fn(&V) -> V,
1423 {
1424 self.update_or_insert_with(key, update, || value)
1425 }
1426
1427 /// Updates an existing entry or inserts a default value computed from a closure.
1428 ///
1429 /// See [`HashMap::update_or_insert_with`] for details.
1430 #[inline]
1431 pub fn update_or_insert_with<U, F>(&self, key: K, update: U, f: F) -> &V
1432 where
1433 F: FnOnce() -> V,
1434 U: Fn(&V) -> V,
1435 {
1436 self.map
1437 .raw
1438 .update_or_insert_with(key, update, f, &self.guard)
1439 }
1440
1441 // Updates an entry with a compare-and-swap (CAS) function.
1442 //
1443 /// See [`HashMap::compute`] for details.
1444 #[inline]
1445 pub fn compute<'g, F, T>(&'g self, key: K, compute: F) -> Compute<'g, K, V, T>
1446 where
1447 F: FnMut(Option<(&'g K, &'g V)>) -> Operation<V, T>,
1448 {
1449 self.map.raw.compute(key, compute, &self.guard)
1450 }
1451
1452 /// Removes a key from the map, returning the value at the key if the key
1453 /// was previously in the map.
1454 ///
1455 /// See [`HashMap::remove`] for details.
1456 #[inline]
1457 pub fn remove<Q>(&self, key: &Q) -> Option<&V>
1458 where
1459 Q: Equivalent<K> + Hash + ?Sized,
1460 {
1461 match self.map.raw.remove(key, &self.guard) {
1462 Some((_, value)) => Some(value),
1463 None => None,
1464 }
1465 }
1466
1467 /// Removes a key from the map, returning the stored key and value if the
1468 /// key was previously in the map.
1469 ///
1470 /// See [`HashMap::remove_entry`] for details.
1471 #[inline]
1472 pub fn remove_entry<Q>(&self, key: &Q) -> Option<(&K, &V)>
1473 where
1474 Q: Equivalent<K> + Hash + ?Sized,
1475 {
1476 self.map.raw.remove(key, &self.guard)
1477 }
1478
1479 /// Conditionally removes a key from the map based on the provided closure.
1480 ///
1481 /// See [`HashMap::remove_if`] for details.
1482 #[inline]
1483 pub fn remove_if<Q, F>(&self, key: &Q, should_remove: F) -> Result<Option<(&K, &V)>, (&K, &V)>
1484 where
1485 Q: Equivalent<K> + Hash + ?Sized,
1486 F: FnMut(&K, &V) -> bool,
1487 {
1488 self.map.raw.remove_if(key, should_remove, &self.guard)
1489 }
1490
1491 /// Clears the map, removing all key-value pairs.
1492 ///
1493 /// See [`HashMap::clear`] for details.
1494 #[inline]
1495 pub fn clear(&self) {
1496 self.map.raw.clear(&self.guard)
1497 }
1498
1499 /// Retains only the elements specified by the predicate.
1500 ///
1501 /// See [`HashMap::retain`] for details.
1502 #[inline]
1503 pub fn retain<F>(&mut self, f: F)
1504 where
1505 F: FnMut(&K, &V) -> bool,
1506 {
1507 self.map.raw.retain(f, &self.guard)
1508 }
1509
1510 /// Tries to reserve capacity for `additional` more elements to be inserted
1511 /// in the map.
1512 ///
1513 /// See [`HashMap::reserve`] for details.
1514 #[inline]
1515 pub fn reserve(&self, additional: usize) {
1516 self.map.raw.reserve(additional, &self.guard)
1517 }
1518
1519 /// An iterator visiting all key-value pairs in arbitrary order.
1520 /// The iterator element type is `(&K, &V)`.
1521 ///
1522 /// See [`HashMap::iter`] for details.
1523 #[inline]
1524 pub fn iter(&self) -> Iter<'_, K, V, G> {
1525 Iter {
1526 raw: self.map.raw.iter(&self.guard),
1527 }
1528 }
1529
1530 /// An iterator visiting all keys in arbitrary order.
1531 /// The iterator element type is `&K`.
1532 ///
1533 /// See [`HashMap::keys`] for details.
1534 #[inline]
1535 pub fn keys(&self) -> Keys<'_, K, V, G> {
1536 Keys { iter: self.iter() }
1537 }
1538
1539 /// An iterator visiting all values in arbitrary order.
1540 /// The iterator element type is `&V`.
1541 ///
1542 /// See [`HashMap::values`] for details.
1543 #[inline]
1544 pub fn values(&self) -> Values<'_, K, V, G> {
1545 Values { iter: self.iter() }
1546 }
1547}
1548
1549impl<K, V, S, G> fmt::Debug for HashMapRef<'_, K, V, S, G>
1550where
1551 K: Hash + Eq + fmt::Debug,
1552 V: fmt::Debug,
1553 S: BuildHasher,
1554 G: Guard,
1555{
1556 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1557 f.debug_map().entries(self.iter()).finish()
1558 }
1559}
1560
1561impl<'a, K, V, S, G> IntoIterator for &'a HashMapRef<'_, K, V, S, G>
1562where
1563 K: Hash + Eq,
1564 S: BuildHasher,
1565 G: Guard,
1566{
1567 type Item = (&'a K, &'a V);
1568 type IntoIter = Iter<'a, K, V, G>;
1569
1570 fn into_iter(self) -> Self::IntoIter {
1571 self.iter()
1572 }
1573}
1574
1575/// An iterator over a map's entries.
1576///
1577/// This struct is created by the [`iter`](HashMap::iter) method on [`HashMap`]. See its documentation for details.
1578pub struct Iter<'g, K, V, G> {
1579 raw: raw::Iter<'g, K, V, MapGuard<G>>,
1580}
1581
1582impl<'g, K: 'g, V: 'g, G> Iterator for Iter<'g, K, V, G>
1583where
1584 G: Guard,
1585{
1586 type Item = (&'g K, &'g V);
1587
1588 #[inline]
1589 fn next(&mut self) -> Option<Self::Item> {
1590 self.raw.next()
1591 }
1592}
1593
1594impl<K, V, G> fmt::Debug for Iter<'_, K, V, G>
1595where
1596 K: fmt::Debug,
1597 V: fmt::Debug,
1598 G: Guard,
1599{
1600 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1601 f.debug_list()
1602 .entries(Iter {
1603 raw: self.raw.clone(),
1604 })
1605 .finish()
1606 }
1607}
1608
1609/// An iterator over a map's keys.
1610///
1611/// This struct is created by the [`keys`](HashMap::keys) method on [`HashMap`]. See its documentation for details.
1612pub struct Keys<'g, K, V, G> {
1613 iter: Iter<'g, K, V, G>,
1614}
1615
1616impl<'g, K: 'g, V: 'g, G> Iterator for Keys<'g, K, V, G>
1617where
1618 G: Guard,
1619{
1620 type Item = &'g K;
1621
1622 #[inline]
1623 fn next(&mut self) -> Option<Self::Item> {
1624 let (key, _) = self.iter.next()?;
1625 Some(key)
1626 }
1627}
1628
1629impl<K, V, G> fmt::Debug for Keys<'_, K, V, G>
1630where
1631 K: fmt::Debug,
1632 V: fmt::Debug,
1633 G: Guard,
1634{
1635 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1636 f.debug_tuple("Keys").field(&self.iter).finish()
1637 }
1638}
1639
1640/// An iterator over a map's values.
1641///
1642/// This struct is created by the [`values`](HashMap::values) method on [`HashMap`]. See its documentation for details.
1643pub struct Values<'g, K, V, G> {
1644 iter: Iter<'g, K, V, G>,
1645}
1646
1647impl<'g, K: 'g, V: 'g, G> Iterator for Values<'g, K, V, G>
1648where
1649 G: Guard,
1650{
1651 type Item = &'g V;
1652
1653 #[inline]
1654 fn next(&mut self) -> Option<Self::Item> {
1655 let (_, value) = self.iter.next()?;
1656 Some(value)
1657 }
1658}
1659
1660impl<K, V, G> fmt::Debug for Values<'_, K, V, G>
1661where
1662 K: fmt::Debug,
1663 V: fmt::Debug,
1664 G: Guard,
1665{
1666 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1667 f.debug_tuple("Values").field(&self.iter).finish()
1668 }
1669}