1use core::{fmt, iter::FusedIterator, marker::PhantomData};
2
3use crate::{
4 raw::{
5 Allocator, Bucket, Global, InsertSlot, RawDrain, RawExtractIf, RawIntoIter, RawIter,
6 RawTable,
7 },
8 TryReserveError,
9};
10
11/// Low-level hash table with explicit hashing.
12///
13/// The primary use case for this type over [`HashMap`] or [`HashSet`] is to
14/// support types that do not implement the [`Hash`] and [`Eq`] traits, but
15/// instead require additional data not contained in the key itself to compute a
16/// hash and compare two elements for equality.
17///
18/// Examples of when this can be useful include:
19/// - An `IndexMap` implementation where indices into a `Vec` are stored as
20/// elements in a `HashTable<usize>`. Hashing and comparing the elements
21/// requires indexing the associated `Vec` to get the actual value referred to
22/// by the index.
23/// - Avoiding re-computing a hash when it is already known.
24/// - Mutating the key of an element in a way that doesn't affect its hash.
25///
26/// To achieve this, `HashTable` methods that search for an element in the table
27/// require a hash value and equality function to be explicitly passed in as
28/// arguments. The method will then iterate over the elements with the given
29/// hash and call the equality function on each of them, until a match is found.
30///
31/// In most cases, a `HashTable` will not be exposed directly in an API. It will
32/// instead be wrapped in a helper type which handles the work of calculating
33/// hash values and comparing elements.
34///
35/// Due to its low-level nature, this type provides fewer guarantees than
36/// [`HashMap`] and [`HashSet`]. Specifically, the API allows you to shoot
37/// yourself in the foot by having multiple elements with identical keys in the
38/// table. The table itself will still function correctly and lookups will
39/// arbitrarily return one of the matching elements. However you should avoid
40/// doing this because it changes the runtime of hash table operations from
41/// `O(1)` to `O(k)` where `k` is the number of duplicate entries.
42///
43/// [`HashMap`]: super::HashMap
44/// [`HashSet`]: super::HashSet
45pub struct HashTable<T, A = Global>
46where
47 A: Allocator,
48{
49 pub(crate) raw: RawTable<T, A>,
50}
51
52impl<T> HashTable<T, Global> {
53 /// Creates an empty `HashTable`.
54 ///
55 /// The hash table is initially created with a capacity of 0, so it will not allocate until it
56 /// is first inserted into.
57 ///
58 /// # Examples
59 ///
60 /// ```
61 /// use hashbrown::HashTable;
62 /// let mut table: HashTable<&str> = HashTable::new();
63 /// assert_eq!(table.len(), 0);
64 /// assert_eq!(table.capacity(), 0);
65 /// ```
66 pub const fn new() -> Self {
67 Self {
68 raw: RawTable::new(),
69 }
70 }
71
72 /// Creates an empty `HashTable` with the specified capacity.
73 ///
74 /// The hash table will be able to hold at least `capacity` elements without
75 /// reallocating. If `capacity` is 0, the hash table will not allocate.
76 ///
77 /// # Examples
78 ///
79 /// ```
80 /// use hashbrown::HashTable;
81 /// let mut table: HashTable<&str> = HashTable::with_capacity(10);
82 /// assert_eq!(table.len(), 0);
83 /// assert!(table.capacity() >= 10);
84 /// ```
85 pub fn with_capacity(capacity: usize) -> Self {
86 Self {
87 raw: RawTable::with_capacity(capacity),
88 }
89 }
90}
91
92impl<T, A> HashTable<T, A>
93where
94 A: Allocator,
95{
96 /// Creates an empty `HashTable` using the given allocator.
97 ///
98 /// The hash table is initially created with a capacity of 0, so it will not allocate until it
99 /// is first inserted into.
100 ///
101 /// # Examples
102 ///
103 /// ```
104 /// # #[cfg(feature = "nightly")]
105 /// # fn test() {
106 /// use ahash::AHasher;
107 /// use bumpalo::Bump;
108 /// use hashbrown::HashTable;
109 /// use std::hash::{BuildHasher, BuildHasherDefault};
110 ///
111 /// let bump = Bump::new();
112 /// let mut table = HashTable::new_in(&bump);
113 /// let hasher = BuildHasherDefault::<AHasher>::default();
114 /// let hasher = |val: &_| hasher.hash_one(val);
115 ///
116 /// // The created HashTable holds none elements
117 /// assert_eq!(table.len(), 0);
118 ///
119 /// // The created HashTable also doesn't allocate memory
120 /// assert_eq!(table.capacity(), 0);
121 ///
122 /// // Now we insert element inside created HashTable
123 /// table.insert_unique(hasher(&"One"), "One", hasher);
124 /// // We can see that the HashTable holds 1 element
125 /// assert_eq!(table.len(), 1);
126 /// // And it also allocates some capacity
127 /// assert!(table.capacity() > 1);
128 /// # }
129 /// # fn main() {
130 /// # #[cfg(feature = "nightly")]
131 /// # test()
132 /// # }
133 /// ```
134 pub const fn new_in(alloc: A) -> Self {
135 Self {
136 raw: RawTable::new_in(alloc),
137 }
138 }
139
140 /// Creates an empty `HashTable` with the specified capacity using the given allocator.
141 ///
142 /// The hash table will be able to hold at least `capacity` elements without
143 /// reallocating. If `capacity` is 0, the hash table will not allocate.
144 ///
145 /// # Examples
146 ///
147 /// ```
148 /// # #[cfg(feature = "nightly")]
149 /// # fn test() {
150 /// use ahash::AHasher;
151 /// use bumpalo::Bump;
152 /// use hashbrown::HashTable;
153 /// use std::hash::{BuildHasher, BuildHasherDefault};
154 ///
155 /// let bump = Bump::new();
156 /// let mut table = HashTable::with_capacity_in(5, &bump);
157 /// let hasher = BuildHasherDefault::<AHasher>::default();
158 /// let hasher = |val: &_| hasher.hash_one(val);
159 ///
160 /// // The created HashTable holds none elements
161 /// assert_eq!(table.len(), 0);
162 /// // But it can hold at least 5 elements without reallocating
163 /// let empty_map_capacity = table.capacity();
164 /// assert!(empty_map_capacity >= 5);
165 ///
166 /// // Now we insert some 5 elements inside created HashTable
167 /// table.insert_unique(hasher(&"One"), "One", hasher);
168 /// table.insert_unique(hasher(&"Two"), "Two", hasher);
169 /// table.insert_unique(hasher(&"Three"), "Three", hasher);
170 /// table.insert_unique(hasher(&"Four"), "Four", hasher);
171 /// table.insert_unique(hasher(&"Five"), "Five", hasher);
172 ///
173 /// // We can see that the HashTable holds 5 elements
174 /// assert_eq!(table.len(), 5);
175 /// // But its capacity isn't changed
176 /// assert_eq!(table.capacity(), empty_map_capacity)
177 /// # }
178 /// # fn main() {
179 /// # #[cfg(feature = "nightly")]
180 /// # test()
181 /// # }
182 /// ```
183 pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
184 Self {
185 raw: RawTable::with_capacity_in(capacity, alloc),
186 }
187 }
188
189 /// Returns a reference to the underlying allocator.
190 pub fn allocator(&self) -> &A {
191 self.raw.allocator()
192 }
193
194 /// Returns a reference to an entry in the table with the given hash and
195 /// which satisfies the equality function passed.
196 ///
197 /// This method will call `eq` for all entries with the given hash, but may
198 /// also call it for entries with a different hash. `eq` should only return
199 /// true for the desired entry, at which point the search is stopped.
200 ///
201 /// # Examples
202 ///
203 /// ```
204 /// # #[cfg(feature = "nightly")]
205 /// # fn test() {
206 /// use ahash::AHasher;
207 /// use hashbrown::HashTable;
208 /// use std::hash::{BuildHasher, BuildHasherDefault};
209 ///
210 /// let mut table = HashTable::new();
211 /// let hasher = BuildHasherDefault::<AHasher>::default();
212 /// let hasher = |val: &_| hasher.hash_one(val);
213 /// table.insert_unique(hasher(&1), 1, hasher);
214 /// table.insert_unique(hasher(&2), 2, hasher);
215 /// table.insert_unique(hasher(&3), 3, hasher);
216 /// assert_eq!(table.find(hasher(&2), |&val| val == 2), Some(&2));
217 /// assert_eq!(table.find(hasher(&4), |&val| val == 4), None);
218 /// # }
219 /// # fn main() {
220 /// # #[cfg(feature = "nightly")]
221 /// # test()
222 /// # }
223 /// ```
224 pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T> {
225 self.raw.get(hash, eq)
226 }
227
228 /// Returns a mutable reference to an entry in the table with the given hash
229 /// and which satisfies the equality function passed.
230 ///
231 /// This method will call `eq` for all entries with the given hash, but may
232 /// also call it for entries with a different hash. `eq` should only return
233 /// true for the desired entry, at which point the search is stopped.
234 ///
235 /// When mutating an entry, you should ensure that it still retains the same
236 /// hash value as when it was inserted, otherwise lookups of that entry may
237 /// fail to find it.
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// # #[cfg(feature = "nightly")]
243 /// # fn test() {
244 /// use ahash::AHasher;
245 /// use hashbrown::HashTable;
246 /// use std::hash::{BuildHasher, BuildHasherDefault};
247 ///
248 /// let mut table = HashTable::new();
249 /// let hasher = BuildHasherDefault::<AHasher>::default();
250 /// let hasher = |val: &_| hasher.hash_one(val);
251 /// table.insert_unique(hasher(&1), (1, "a"), |val| hasher(&val.0));
252 /// if let Some(val) = table.find_mut(hasher(&1), |val| val.0 == 1) {
253 /// val.1 = "b";
254 /// }
255 /// assert_eq!(table.find(hasher(&1), |val| val.0 == 1), Some(&(1, "b")));
256 /// assert_eq!(table.find(hasher(&2), |val| val.0 == 2), None);
257 /// # }
258 /// # fn main() {
259 /// # #[cfg(feature = "nightly")]
260 /// # test()
261 /// # }
262 /// ```
263 pub fn find_mut(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&mut T> {
264 self.raw.get_mut(hash, eq)
265 }
266
267 /// Returns an `OccupiedEntry` for an entry in the table with the given hash
268 /// and which satisfies the equality function passed.
269 ///
270 /// This can be used to remove the entry from the table. Call
271 /// [`HashTable::entry`] instead if you wish to insert an entry if the
272 /// lookup fails.
273 ///
274 /// This method will call `eq` for all entries with the given hash, but may
275 /// also call it for entries with a different hash. `eq` should only return
276 /// true for the desired entry, at which point the search is stopped.
277 ///
278 /// # Examples
279 ///
280 /// ```
281 /// # #[cfg(feature = "nightly")]
282 /// # fn test() {
283 /// use ahash::AHasher;
284 /// use hashbrown::HashTable;
285 /// use std::hash::{BuildHasher, BuildHasherDefault};
286 ///
287 /// let mut table = HashTable::new();
288 /// let hasher = BuildHasherDefault::<AHasher>::default();
289 /// let hasher = |val: &_| hasher.hash_one(val);
290 /// table.insert_unique(hasher(&1), (1, "a"), |val| hasher(&val.0));
291 /// if let Ok(entry) = table.find_entry(hasher(&1), |val| val.0 == 1) {
292 /// entry.remove();
293 /// }
294 /// assert_eq!(table.find(hasher(&1), |val| val.0 == 1), None);
295 /// # }
296 /// # fn main() {
297 /// # #[cfg(feature = "nightly")]
298 /// # test()
299 /// # }
300 /// ```
301 pub fn find_entry(
302 &mut self,
303 hash: u64,
304 eq: impl FnMut(&T) -> bool,
305 ) -> Result<OccupiedEntry<'_, T, A>, AbsentEntry<'_, T, A>> {
306 match self.raw.find(hash, eq) {
307 Some(bucket) => Ok(OccupiedEntry {
308 hash,
309 bucket,
310 table: self,
311 }),
312 None => Err(AbsentEntry { table: self }),
313 }
314 }
315
316 /// Returns an `Entry` for an entry in the table with the given hash
317 /// and which satisfies the equality function passed.
318 ///
319 /// This can be used to remove the entry from the table, or insert a new
320 /// entry with the given hash if one doesn't already exist.
321 ///
322 /// This method will call `eq` for all entries with the given hash, but may
323 /// also call it for entries with a different hash. `eq` should only return
324 /// true for the desired entry, at which point the search is stopped.
325 ///
326 /// This method may grow the table in preparation for an insertion. Call
327 /// [`HashTable::find_entry`] if this is undesirable.
328 ///
329 /// `hasher` is called if entries need to be moved or copied to a new table.
330 /// This must return the same hash value that each entry was inserted with.
331 ///
332 /// # Examples
333 ///
334 /// ```
335 /// # #[cfg(feature = "nightly")]
336 /// # fn test() {
337 /// use ahash::AHasher;
338 /// use hashbrown::hash_table::Entry;
339 /// use hashbrown::HashTable;
340 /// use std::hash::{BuildHasher, BuildHasherDefault};
341 ///
342 /// let mut table = HashTable::new();
343 /// let hasher = BuildHasherDefault::<AHasher>::default();
344 /// let hasher = |val: &_| hasher.hash_one(val);
345 /// table.insert_unique(hasher(&1), (1, "a"), |val| hasher(&val.0));
346 /// if let Entry::Occupied(entry) = table.entry(hasher(&1), |val| val.0 == 1, |val| hasher(&val.0))
347 /// {
348 /// entry.remove();
349 /// }
350 /// if let Entry::Vacant(entry) = table.entry(hasher(&2), |val| val.0 == 2, |val| hasher(&val.0)) {
351 /// entry.insert((2, "b"));
352 /// }
353 /// assert_eq!(table.find(hasher(&1), |val| val.0 == 1), None);
354 /// assert_eq!(table.find(hasher(&2), |val| val.0 == 2), Some(&(2, "b")));
355 /// # }
356 /// # fn main() {
357 /// # #[cfg(feature = "nightly")]
358 /// # test()
359 /// # }
360 /// ```
361 pub fn entry(
362 &mut self,
363 hash: u64,
364 eq: impl FnMut(&T) -> bool,
365 hasher: impl Fn(&T) -> u64,
366 ) -> Entry<'_, T, A> {
367 match self.raw.find_or_find_insert_slot(hash, eq, hasher) {
368 Ok(bucket) => Entry::Occupied(OccupiedEntry {
369 hash,
370 bucket,
371 table: self,
372 }),
373 Err(insert_slot) => Entry::Vacant(VacantEntry {
374 hash,
375 insert_slot,
376 table: self,
377 }),
378 }
379 }
380
381 /// Inserts an element into the `HashTable` with the given hash value, but
382 /// without checking whether an equivalent element already exists within the
383 /// table.
384 ///
385 /// `hasher` is called if entries need to be moved or copied to a new table.
386 /// This must return the same hash value that each entry was inserted with.
387 ///
388 /// # Examples
389 ///
390 /// ```
391 /// # #[cfg(feature = "nightly")]
392 /// # fn test() {
393 /// use ahash::AHasher;
394 /// use hashbrown::HashTable;
395 /// use std::hash::{BuildHasher, BuildHasherDefault};
396 ///
397 /// let mut v = HashTable::new();
398 /// let hasher = BuildHasherDefault::<AHasher>::default();
399 /// let hasher = |val: &_| hasher.hash_one(val);
400 /// v.insert_unique(hasher(&1), 1, hasher);
401 /// # }
402 /// # fn main() {
403 /// # #[cfg(feature = "nightly")]
404 /// # test()
405 /// # }
406 /// ```
407 pub fn insert_unique(
408 &mut self,
409 hash: u64,
410 value: T,
411 hasher: impl Fn(&T) -> u64,
412 ) -> OccupiedEntry<'_, T, A> {
413 let bucket = self.raw.insert(hash, value, hasher);
414 OccupiedEntry {
415 hash,
416 bucket,
417 table: self,
418 }
419 }
420
421 /// Clears the table, removing all values.
422 ///
423 /// # Examples
424 ///
425 /// ```
426 /// # #[cfg(feature = "nightly")]
427 /// # fn test() {
428 /// use ahash::AHasher;
429 /// use hashbrown::HashTable;
430 /// use std::hash::{BuildHasher, BuildHasherDefault};
431 ///
432 /// let mut v = HashTable::new();
433 /// let hasher = BuildHasherDefault::<AHasher>::default();
434 /// let hasher = |val: &_| hasher.hash_one(val);
435 /// v.insert_unique(hasher(&1), 1, hasher);
436 /// v.clear();
437 /// assert!(v.is_empty());
438 /// # }
439 /// # fn main() {
440 /// # #[cfg(feature = "nightly")]
441 /// # test()
442 /// # }
443 /// ```
444 pub fn clear(&mut self) {
445 self.raw.clear();
446 }
447
448 /// Shrinks the capacity of the table as much as possible. It will drop
449 /// down as much as possible while maintaining the internal rules
450 /// and possibly leaving some space in accordance with the resize policy.
451 ///
452 /// `hasher` is called if entries need to be moved or copied to a new table.
453 /// This must return the same hash value that each entry was inserted with.
454 ///
455 /// # Examples
456 ///
457 /// ```
458 /// # #[cfg(feature = "nightly")]
459 /// # fn test() {
460 /// use ahash::AHasher;
461 /// use hashbrown::HashTable;
462 /// use std::hash::{BuildHasher, BuildHasherDefault};
463 ///
464 /// let mut table = HashTable::with_capacity(100);
465 /// let hasher = BuildHasherDefault::<AHasher>::default();
466 /// let hasher = |val: &_| hasher.hash_one(val);
467 /// table.insert_unique(hasher(&1), 1, hasher);
468 /// table.insert_unique(hasher(&2), 2, hasher);
469 /// assert!(table.capacity() >= 100);
470 /// table.shrink_to_fit(hasher);
471 /// assert!(table.capacity() >= 2);
472 /// # }
473 /// # fn main() {
474 /// # #[cfg(feature = "nightly")]
475 /// # test()
476 /// # }
477 /// ```
478 pub fn shrink_to_fit(&mut self, hasher: impl Fn(&T) -> u64) {
479 self.raw.shrink_to(self.len(), hasher)
480 }
481
482 /// Shrinks the capacity of the table with a lower limit. It will drop
483 /// down no lower than the supplied limit while maintaining the internal rules
484 /// and possibly leaving some space in accordance with the resize policy.
485 ///
486 /// `hasher` is called if entries need to be moved or copied to a new table.
487 /// This must return the same hash value that each entry was inserted with.
488 ///
489 /// Panics if the current capacity is smaller than the supplied
490 /// minimum capacity.
491 ///
492 /// # Examples
493 ///
494 /// ```
495 /// # #[cfg(feature = "nightly")]
496 /// # fn test() {
497 /// use ahash::AHasher;
498 /// use hashbrown::HashTable;
499 /// use std::hash::{BuildHasher, BuildHasherDefault};
500 ///
501 /// let mut table = HashTable::with_capacity(100);
502 /// let hasher = BuildHasherDefault::<AHasher>::default();
503 /// let hasher = |val: &_| hasher.hash_one(val);
504 /// table.insert_unique(hasher(&1), 1, hasher);
505 /// table.insert_unique(hasher(&2), 2, hasher);
506 /// assert!(table.capacity() >= 100);
507 /// table.shrink_to(10, hasher);
508 /// assert!(table.capacity() >= 10);
509 /// table.shrink_to(0, hasher);
510 /// assert!(table.capacity() >= 2);
511 /// # }
512 /// # fn main() {
513 /// # #[cfg(feature = "nightly")]
514 /// # test()
515 /// # }
516 /// ```
517 pub fn shrink_to(&mut self, min_capacity: usize, hasher: impl Fn(&T) -> u64) {
518 self.raw.shrink_to(min_capacity, hasher);
519 }
520
521 /// Reserves capacity for at least `additional` more elements to be inserted
522 /// in the `HashTable`. The collection may reserve more space to avoid
523 /// frequent reallocations.
524 ///
525 /// `hasher` is called if entries need to be moved or copied to a new table.
526 /// This must return the same hash value that each entry was inserted with.
527 ///
528 /// # Panics
529 ///
530 /// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program
531 /// in case of allocation error. Use [`try_reserve`](HashTable::try_reserve) instead
532 /// if you want to handle memory allocation failure.
533 ///
534 /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html
535 /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
536 ///
537 /// # Examples
538 ///
539 /// ```
540 /// # #[cfg(feature = "nightly")]
541 /// # fn test() {
542 /// use ahash::AHasher;
543 /// use hashbrown::HashTable;
544 /// use std::hash::{BuildHasher, BuildHasherDefault};
545 ///
546 /// let mut table: HashTable<i32> = HashTable::new();
547 /// let hasher = BuildHasherDefault::<AHasher>::default();
548 /// let hasher = |val: &_| hasher.hash_one(val);
549 /// table.reserve(10, hasher);
550 /// assert!(table.capacity() >= 10);
551 /// # }
552 /// # fn main() {
553 /// # #[cfg(feature = "nightly")]
554 /// # test()
555 /// # }
556 /// ```
557 pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64) {
558 self.raw.reserve(additional, hasher)
559 }
560
561 /// Tries to reserve capacity for at least `additional` more elements to be inserted
562 /// in the given `HashTable`. The collection may reserve more space to avoid
563 /// frequent reallocations.
564 ///
565 /// `hasher` is called if entries need to be moved or copied to a new table.
566 /// This must return the same hash value that each entry was inserted with.
567 ///
568 /// # Errors
569 ///
570 /// If the capacity overflows, or the allocator reports a failure, then an error
571 /// is returned.
572 ///
573 /// # Examples
574 ///
575 /// ```
576 /// # #[cfg(feature = "nightly")]
577 /// # fn test() {
578 /// use ahash::AHasher;
579 /// use hashbrown::HashTable;
580 /// use std::hash::{BuildHasher, BuildHasherDefault};
581 ///
582 /// let mut table: HashTable<i32> = HashTable::new();
583 /// let hasher = BuildHasherDefault::<AHasher>::default();
584 /// let hasher = |val: &_| hasher.hash_one(val);
585 /// table
586 /// .try_reserve(10, hasher)
587 /// .expect("why is the test harness OOMing on 10 bytes?");
588 /// # }
589 /// # fn main() {
590 /// # #[cfg(feature = "nightly")]
591 /// # test()
592 /// # }
593 /// ```
594 pub fn try_reserve(
595 &mut self,
596 additional: usize,
597 hasher: impl Fn(&T) -> u64,
598 ) -> Result<(), TryReserveError> {
599 self.raw.try_reserve(additional, hasher)
600 }
601
602 /// Returns the number of elements the table can hold without reallocating.
603 ///
604 /// # Examples
605 ///
606 /// ```
607 /// use hashbrown::HashTable;
608 /// let table: HashTable<i32> = HashTable::with_capacity(100);
609 /// assert!(table.capacity() >= 100);
610 /// ```
611 pub fn capacity(&self) -> usize {
612 self.raw.capacity()
613 }
614
615 /// Returns the number of elements in the table.
616 ///
617 /// # Examples
618 ///
619 /// ```
620 /// # #[cfg(feature = "nightly")]
621 /// # fn test() {
622 /// use ahash::AHasher;
623 /// use hashbrown::HashTable;
624 /// use std::hash::{BuildHasher, BuildHasherDefault};
625 ///
626 /// let hasher = BuildHasherDefault::<AHasher>::default();
627 /// let hasher = |val: &_| hasher.hash_one(val);
628 /// let mut v = HashTable::new();
629 /// assert_eq!(v.len(), 0);
630 /// v.insert_unique(hasher(&1), 1, hasher);
631 /// assert_eq!(v.len(), 1);
632 /// # }
633 /// # fn main() {
634 /// # #[cfg(feature = "nightly")]
635 /// # test()
636 /// # }
637 /// ```
638 pub fn len(&self) -> usize {
639 self.raw.len()
640 }
641
642 /// Returns `true` if the set contains no elements.
643 ///
644 /// # Examples
645 ///
646 /// ```
647 /// # #[cfg(feature = "nightly")]
648 /// # fn test() {
649 /// use ahash::AHasher;
650 /// use hashbrown::HashTable;
651 /// use std::hash::{BuildHasher, BuildHasherDefault};
652 ///
653 /// let hasher = BuildHasherDefault::<AHasher>::default();
654 /// let hasher = |val: &_| hasher.hash_one(val);
655 /// let mut v = HashTable::new();
656 /// assert!(v.is_empty());
657 /// v.insert_unique(hasher(&1), 1, hasher);
658 /// assert!(!v.is_empty());
659 /// # }
660 /// # fn main() {
661 /// # #[cfg(feature = "nightly")]
662 /// # test()
663 /// # }
664 /// ```
665 pub fn is_empty(&self) -> bool {
666 self.raw.is_empty()
667 }
668
669 /// An iterator visiting all elements in arbitrary order.
670 /// The iterator element type is `&'a T`.
671 ///
672 /// # Examples
673 ///
674 /// ```
675 /// # #[cfg(feature = "nightly")]
676 /// # fn test() {
677 /// use ahash::AHasher;
678 /// use hashbrown::HashTable;
679 /// use std::hash::{BuildHasher, BuildHasherDefault};
680 ///
681 /// let mut table = HashTable::new();
682 /// let hasher = BuildHasherDefault::<AHasher>::default();
683 /// let hasher = |val: &_| hasher.hash_one(val);
684 /// table.insert_unique(hasher(&"a"), "b", hasher);
685 /// table.insert_unique(hasher(&"b"), "b", hasher);
686 ///
687 /// // Will print in an arbitrary order.
688 /// for x in table.iter() {
689 /// println!("{}", x);
690 /// }
691 /// # }
692 /// # fn main() {
693 /// # #[cfg(feature = "nightly")]
694 /// # test()
695 /// # }
696 /// ```
697 pub fn iter(&self) -> Iter<'_, T> {
698 Iter {
699 inner: unsafe { self.raw.iter() },
700 marker: PhantomData,
701 }
702 }
703
704 /// An iterator visiting all elements in arbitrary order,
705 /// with mutable references to the elements.
706 /// The iterator element type is `&'a mut T`.
707 ///
708 /// # Examples
709 ///
710 /// ```
711 /// # #[cfg(feature = "nightly")]
712 /// # fn test() {
713 /// use ahash::AHasher;
714 /// use hashbrown::HashTable;
715 /// use std::hash::{BuildHasher, BuildHasherDefault};
716 ///
717 /// let mut table = HashTable::new();
718 /// let hasher = BuildHasherDefault::<AHasher>::default();
719 /// let hasher = |val: &_| hasher.hash_one(val);
720 /// table.insert_unique(hasher(&1), 1, hasher);
721 /// table.insert_unique(hasher(&2), 2, hasher);
722 /// table.insert_unique(hasher(&3), 3, hasher);
723 ///
724 /// // Update all values
725 /// for val in table.iter_mut() {
726 /// *val *= 2;
727 /// }
728 ///
729 /// assert_eq!(table.len(), 3);
730 /// let mut vec: Vec<i32> = Vec::new();
731 ///
732 /// for val in &table {
733 /// println!("val: {}", val);
734 /// vec.push(*val);
735 /// }
736 ///
737 /// // The `Iter` iterator produces items in arbitrary order, so the
738 /// // items must be sorted to test them against a sorted array.
739 /// vec.sort_unstable();
740 /// assert_eq!(vec, [2, 4, 6]);
741 ///
742 /// assert_eq!(table.len(), 3);
743 /// # }
744 /// # fn main() {
745 /// # #[cfg(feature = "nightly")]
746 /// # test()
747 /// # }
748 /// ```
749 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
750 IterMut {
751 inner: unsafe { self.raw.iter() },
752 marker: PhantomData,
753 }
754 }
755
756 /// Retains only the elements specified by the predicate.
757 ///
758 /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
759 ///
760 /// # Examples
761 ///
762 /// ```
763 /// # #[cfg(feature = "nightly")]
764 /// # fn test() {
765 /// use ahash::AHasher;
766 /// use hashbrown::HashTable;
767 /// use std::hash::{BuildHasher, BuildHasherDefault};
768 ///
769 /// let mut table = HashTable::new();
770 /// let hasher = BuildHasherDefault::<AHasher>::default();
771 /// let hasher = |val: &_| hasher.hash_one(val);
772 /// for x in 1..=6 {
773 /// table.insert_unique(hasher(&x), x, hasher);
774 /// }
775 /// table.retain(|&mut x| x % 2 == 0);
776 /// assert_eq!(table.len(), 3);
777 /// # }
778 /// # fn main() {
779 /// # #[cfg(feature = "nightly")]
780 /// # test()
781 /// # }
782 /// ```
783 pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) {
784 // Here we only use `iter` as a temporary, preventing use-after-free
785 unsafe {
786 for item in self.raw.iter() {
787 if !f(item.as_mut()) {
788 self.raw.erase(item);
789 }
790 }
791 }
792 }
793
794 /// Clears the set, returning all elements in an iterator.
795 ///
796 /// # Examples
797 ///
798 /// ```
799 /// # #[cfg(feature = "nightly")]
800 /// # fn test() {
801 /// use ahash::AHasher;
802 /// use hashbrown::HashTable;
803 /// use std::hash::{BuildHasher, BuildHasherDefault};
804 ///
805 /// let mut table = HashTable::new();
806 /// let hasher = BuildHasherDefault::<AHasher>::default();
807 /// let hasher = |val: &_| hasher.hash_one(val);
808 /// for x in 1..=3 {
809 /// table.insert_unique(hasher(&x), x, hasher);
810 /// }
811 /// assert!(!table.is_empty());
812 ///
813 /// // print 1, 2, 3 in an arbitrary order
814 /// for i in table.drain() {
815 /// println!("{}", i);
816 /// }
817 ///
818 /// assert!(table.is_empty());
819 /// # }
820 /// # fn main() {
821 /// # #[cfg(feature = "nightly")]
822 /// # test()
823 /// # }
824 /// ```
825 pub fn drain(&mut self) -> Drain<'_, T, A> {
826 Drain {
827 inner: self.raw.drain(),
828 }
829 }
830
831 /// Drains elements which are true under the given predicate,
832 /// and returns an iterator over the removed items.
833 ///
834 /// In other words, move all elements `e` such that `f(&e)` returns `true` out
835 /// into another iterator.
836 ///
837 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
838 /// or the iteration short-circuits, then the remaining elements will be retained.
839 /// Use [`retain()`] with a negated predicate if you do not need the returned iterator.
840 ///
841 /// [`retain()`]: HashTable::retain
842 ///
843 /// # Examples
844 ///
845 /// ```
846 /// # #[cfg(feature = "nightly")]
847 /// # fn test() {
848 /// use ahash::AHasher;
849 /// use hashbrown::HashTable;
850 /// use std::hash::{BuildHasher, BuildHasherDefault};
851 ///
852 /// let mut table = HashTable::new();
853 /// let hasher = BuildHasherDefault::<AHasher>::default();
854 /// let hasher = |val: &_| hasher.hash_one(val);
855 /// for x in 0..8 {
856 /// table.insert_unique(hasher(&x), x, hasher);
857 /// }
858 /// let drained: Vec<i32> = table.extract_if(|&mut v| v % 2 == 0).collect();
859 ///
860 /// let mut evens = drained.into_iter().collect::<Vec<_>>();
861 /// let mut odds = table.into_iter().collect::<Vec<_>>();
862 /// evens.sort();
863 /// odds.sort();
864 ///
865 /// assert_eq!(evens, vec![0, 2, 4, 6]);
866 /// assert_eq!(odds, vec![1, 3, 5, 7]);
867 /// # }
868 /// # fn main() {
869 /// # #[cfg(feature = "nightly")]
870 /// # test()
871 /// # }
872 /// ```
873 pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A>
874 where
875 F: FnMut(&mut T) -> bool,
876 {
877 ExtractIf {
878 f,
879 inner: RawExtractIf {
880 iter: unsafe { self.raw.iter() },
881 table: &mut self.raw,
882 },
883 }
884 }
885
886 /// Attempts to get mutable references to `N` values in the map at once.
887 ///
888 /// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to
889 /// the `i`th key to be looked up.
890 ///
891 /// Returns an array of length `N` with the results of each query. For soundness, at most one
892 /// mutable reference will be returned to any value. `None` will be returned if any of the
893 /// keys are duplicates or missing.
894 ///
895 /// # Examples
896 ///
897 /// ```
898 /// # #[cfg(feature = "nightly")]
899 /// # fn test() {
900 /// use ahash::AHasher;
901 /// use hashbrown::hash_table::Entry;
902 /// use hashbrown::HashTable;
903 /// use std::hash::{BuildHasher, BuildHasherDefault};
904 ///
905 /// let mut libraries: HashTable<(&str, u32)> = HashTable::new();
906 /// let hasher = BuildHasherDefault::<AHasher>::default();
907 /// let hasher = |val: &_| hasher.hash_one(val);
908 /// for (k, v) in [
909 /// ("Bodleian Library", 1602),
910 /// ("Athenæum", 1807),
911 /// ("Herzogin-Anna-Amalia-Bibliothek", 1691),
912 /// ("Library of Congress", 1800),
913 /// ] {
914 /// libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k));
915 /// }
916 ///
917 /// let keys = ["Athenæum", "Library of Congress"];
918 /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
919 /// assert_eq!(
920 /// got,
921 /// Some([&mut ("Athenæum", 1807), &mut ("Library of Congress", 1800),]),
922 /// );
923 ///
924 /// // Missing keys result in None
925 /// let keys = ["Athenæum", "New York Public Library"];
926 /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
927 /// assert_eq!(got, None);
928 ///
929 /// // Duplicate keys result in None
930 /// let keys = ["Athenæum", "Athenæum"];
931 /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
932 /// assert_eq!(got, None);
933 /// # }
934 /// # fn main() {
935 /// # #[cfg(feature = "nightly")]
936 /// # test()
937 /// # }
938 /// ```
939 pub fn get_many_mut<const N: usize>(
940 &mut self,
941 hashes: [u64; N],
942 eq: impl FnMut(usize, &T) -> bool,
943 ) -> Option<[&'_ mut T; N]> {
944 self.raw.get_many_mut(hashes, eq)
945 }
946
947 /// Attempts to get mutable references to `N` values in the map at once, without validating that
948 /// the values are unique.
949 ///
950 /// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to
951 /// the `i`th key to be looked up.
952 ///
953 /// Returns an array of length `N` with the results of each query. `None` will be returned if
954 /// any of the keys are missing.
955 ///
956 /// For a safe alternative see [`get_many_mut`](`HashTable::get_many_mut`).
957 ///
958 /// # Safety
959 ///
960 /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting
961 /// references are not used.
962 ///
963 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
964 ///
965 /// # Examples
966 ///
967 /// ```
968 /// # #[cfg(feature = "nightly")]
969 /// # fn test() {
970 /// use ahash::AHasher;
971 /// use hashbrown::hash_table::Entry;
972 /// use hashbrown::HashTable;
973 /// use std::hash::{BuildHasher, BuildHasherDefault};
974 ///
975 /// let mut libraries: HashTable<(&str, u32)> = HashTable::new();
976 /// let hasher = BuildHasherDefault::<AHasher>::default();
977 /// let hasher = |val: &_| hasher.hash_one(val);
978 /// for (k, v) in [
979 /// ("Bodleian Library", 1602),
980 /// ("Athenæum", 1807),
981 /// ("Herzogin-Anna-Amalia-Bibliothek", 1691),
982 /// ("Library of Congress", 1800),
983 /// ] {
984 /// libraries.insert_unique(hasher(&k), (k, v), |(k, _)| hasher(&k));
985 /// }
986 ///
987 /// let keys = ["Athenæum", "Library of Congress"];
988 /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
989 /// assert_eq!(
990 /// got,
991 /// Some([&mut ("Athenæum", 1807), &mut ("Library of Congress", 1800),]),
992 /// );
993 ///
994 /// // Missing keys result in None
995 /// let keys = ["Athenæum", "New York Public Library"];
996 /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
997 /// assert_eq!(got, None);
998 ///
999 /// // Duplicate keys result in None
1000 /// let keys = ["Athenæum", "Athenæum"];
1001 /// let got = libraries.get_many_mut(keys.map(|k| hasher(&k)), |i, val| keys[i] == val.0);
1002 /// assert_eq!(got, None);
1003 /// # }
1004 /// # fn main() {
1005 /// # #[cfg(feature = "nightly")]
1006 /// # test()
1007 /// # }
1008 /// ```
1009 pub unsafe fn get_many_unchecked_mut<const N: usize>(
1010 &mut self,
1011 hashes: [u64; N],
1012 eq: impl FnMut(usize, &T) -> bool,
1013 ) -> Option<[&'_ mut T; N]> {
1014 self.raw.get_many_unchecked_mut(hashes, eq)
1015 }
1016}
1017
1018impl<T, A> IntoIterator for HashTable<T, A>
1019where
1020 A: Allocator,
1021{
1022 type Item = T;
1023 type IntoIter = IntoIter<T, A>;
1024
1025 fn into_iter(self) -> IntoIter<T, A> {
1026 IntoIter {
1027 inner: self.raw.into_iter(),
1028 }
1029 }
1030}
1031
1032impl<'a, T, A> IntoIterator for &'a HashTable<T, A>
1033where
1034 A: Allocator,
1035{
1036 type Item = &'a T;
1037 type IntoIter = Iter<'a, T>;
1038
1039 fn into_iter(self) -> Iter<'a, T> {
1040 self.iter()
1041 }
1042}
1043
1044impl<'a, T, A> IntoIterator for &'a mut HashTable<T, A>
1045where
1046 A: Allocator,
1047{
1048 type Item = &'a mut T;
1049 type IntoIter = IterMut<'a, T>;
1050
1051 fn into_iter(self) -> IterMut<'a, T> {
1052 self.iter_mut()
1053 }
1054}
1055
1056impl<T, A> Default for HashTable<T, A>
1057where
1058 A: Allocator + Default,
1059{
1060 fn default() -> Self {
1061 Self {
1062 raw: Default::default(),
1063 }
1064 }
1065}
1066
1067impl<T, A> Clone for HashTable<T, A>
1068where
1069 T: Clone,
1070 A: Allocator + Clone,
1071{
1072 fn clone(&self) -> Self {
1073 Self {
1074 raw: self.raw.clone(),
1075 }
1076 }
1077}
1078
1079impl<T, A> fmt::Debug for HashTable<T, A>
1080where
1081 T: fmt::Debug,
1082 A: Allocator,
1083{
1084 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1085 f.debug_set().entries(self.iter()).finish()
1086 }
1087}
1088
1089/// A view into a single entry in a table, which may either be vacant or occupied.
1090///
1091/// This `enum` is constructed from the [`entry`] method on [`HashTable`].
1092///
1093/// [`HashTable`]: struct.HashTable.html
1094/// [`entry`]: struct.HashTable.html#method.entry
1095///
1096/// # Examples
1097///
1098/// ```
1099/// # #[cfg(feature = "nightly")]
1100/// # fn test() {
1101/// use ahash::AHasher;
1102/// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry};
1103/// use std::hash::{BuildHasher, BuildHasherDefault};
1104///
1105/// let mut table = HashTable::new();
1106/// let hasher = BuildHasherDefault::<AHasher>::default();
1107/// let hasher = |val: &_| hasher.hash_one(val);
1108/// for x in ["a", "b", "c"] {
1109/// table.insert_unique(hasher(&x), x, hasher);
1110/// }
1111/// assert_eq!(table.len(), 3);
1112///
1113/// // Existing value (insert)
1114/// let entry: Entry<_> = table.entry(hasher(&"a"), |&x| x == "a", hasher);
1115/// let _raw_o: OccupiedEntry<_, _> = entry.insert("a");
1116/// assert_eq!(table.len(), 3);
1117/// // Nonexistent value (insert)
1118/// table.entry(hasher(&"d"), |&x| x == "d", hasher).insert("d");
1119///
1120/// // Existing value (or_insert)
1121/// table
1122/// .entry(hasher(&"b"), |&x| x == "b", hasher)
1123/// .or_insert("b");
1124/// // Nonexistent value (or_insert)
1125/// table
1126/// .entry(hasher(&"e"), |&x| x == "e", hasher)
1127/// .or_insert("e");
1128///
1129/// println!("Our HashTable: {:?}", table);
1130///
1131/// let mut vec: Vec<_> = table.iter().copied().collect();
1132/// // The `Iter` iterator produces items in arbitrary order, so the
1133/// // items must be sorted to test them against a sorted array.
1134/// vec.sort_unstable();
1135/// assert_eq!(vec, ["a", "b", "c", "d", "e"]);
1136/// # }
1137/// # fn main() {
1138/// # #[cfg(feature = "nightly")]
1139/// # test()
1140/// # }
1141/// ```
1142pub enum Entry<'a, T, A = Global>
1143where
1144 A: Allocator,
1145{
1146 /// An occupied entry.
1147 ///
1148 /// # Examples
1149 ///
1150 /// ```
1151 /// # #[cfg(feature = "nightly")]
1152 /// # fn test() {
1153 /// use ahash::AHasher;
1154 /// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry};
1155 /// use std::hash::{BuildHasher, BuildHasherDefault};
1156 ///
1157 /// let mut table = HashTable::new();
1158 /// let hasher = BuildHasherDefault::<AHasher>::default();
1159 /// let hasher = |val: &_| hasher.hash_one(val);
1160 /// for x in ["a", "b"] {
1161 /// table.insert_unique(hasher(&x), x, hasher);
1162 /// }
1163 ///
1164 /// match table.entry(hasher(&"a"), |&x| x == "a", hasher) {
1165 /// Entry::Vacant(_) => unreachable!(),
1166 /// Entry::Occupied(_) => {}
1167 /// }
1168 /// # }
1169 /// # fn main() {
1170 /// # #[cfg(feature = "nightly")]
1171 /// # test()
1172 /// # }
1173 /// ```
1174 Occupied(OccupiedEntry<'a, T, A>),
1175
1176 /// A vacant entry.
1177 ///
1178 /// # Examples
1179 ///
1180 /// ```
1181 /// # #[cfg(feature = "nightly")]
1182 /// # fn test() {
1183 /// use ahash::AHasher;
1184 /// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry};
1185 /// use std::hash::{BuildHasher, BuildHasherDefault};
1186 ///
1187 /// let mut table = HashTable::<&str>::new();
1188 /// let hasher = BuildHasherDefault::<AHasher>::default();
1189 /// let hasher = |val: &_| hasher.hash_one(val);
1190 ///
1191 /// match table.entry(hasher(&"a"), |&x| x == "a", hasher) {
1192 /// Entry::Vacant(_) => {}
1193 /// Entry::Occupied(_) => unreachable!(),
1194 /// }
1195 /// # }
1196 /// # fn main() {
1197 /// # #[cfg(feature = "nightly")]
1198 /// # test()
1199 /// # }
1200 /// ```
1201 Vacant(VacantEntry<'a, T, A>),
1202}
1203
1204impl<T: fmt::Debug, A: Allocator> fmt::Debug for Entry<'_, T, A> {
1205 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1206 match *self {
1207 Entry::Vacant(ref v: &VacantEntry<'_, T, A>) => f.debug_tuple("Entry").field(v).finish(),
1208 Entry::Occupied(ref o: &OccupiedEntry<'_, T, A>) => f.debug_tuple("Entry").field(o).finish(),
1209 }
1210 }
1211}
1212
1213impl<'a, T, A> Entry<'a, T, A>
1214where
1215 A: Allocator,
1216{
1217 /// Sets the value of the entry, replacing any existing value if there is
1218 /// one, and returns an [`OccupiedEntry`].
1219 ///
1220 /// # Examples
1221 ///
1222 /// ```
1223 /// # #[cfg(feature = "nightly")]
1224 /// # fn test() {
1225 /// use ahash::AHasher;
1226 /// use hashbrown::HashTable;
1227 /// use std::hash::{BuildHasher, BuildHasherDefault};
1228 ///
1229 /// let mut table: HashTable<&str> = HashTable::new();
1230 /// let hasher = BuildHasherDefault::<AHasher>::default();
1231 /// let hasher = |val: &_| hasher.hash_one(val);
1232 ///
1233 /// let entry = table
1234 /// .entry(hasher(&"horseyland"), |&x| x == "horseyland", hasher)
1235 /// .insert("horseyland");
1236 ///
1237 /// assert_eq!(entry.get(), &"horseyland");
1238 /// # }
1239 /// # fn main() {
1240 /// # #[cfg(feature = "nightly")]
1241 /// # test()
1242 /// # }
1243 /// ```
1244 pub fn insert(self, value: T) -> OccupiedEntry<'a, T, A> {
1245 match self {
1246 Entry::Occupied(mut entry) => {
1247 *entry.get_mut() = value;
1248 entry
1249 }
1250 Entry::Vacant(entry) => entry.insert(value),
1251 }
1252 }
1253
1254 /// Ensures a value is in the entry by inserting if it was vacant.
1255 ///
1256 /// Returns an [`OccupiedEntry`] pointing to the now-occupied entry.
1257 ///
1258 /// # Examples
1259 ///
1260 /// ```
1261 /// # #[cfg(feature = "nightly")]
1262 /// # fn test() {
1263 /// use ahash::AHasher;
1264 /// use hashbrown::HashTable;
1265 /// use std::hash::{BuildHasher, BuildHasherDefault};
1266 ///
1267 /// let mut table: HashTable<&str> = HashTable::new();
1268 /// let hasher = BuildHasherDefault::<AHasher>::default();
1269 /// let hasher = |val: &_| hasher.hash_one(val);
1270 ///
1271 /// // nonexistent key
1272 /// table
1273 /// .entry(hasher(&"poneyland"), |&x| x == "poneyland", hasher)
1274 /// .or_insert("poneyland");
1275 /// assert!(table
1276 /// .find(hasher(&"poneyland"), |&x| x == "poneyland")
1277 /// .is_some());
1278 ///
1279 /// // existing key
1280 /// table
1281 /// .entry(hasher(&"poneyland"), |&x| x == "poneyland", hasher)
1282 /// .or_insert("poneyland");
1283 /// assert!(table
1284 /// .find(hasher(&"poneyland"), |&x| x == "poneyland")
1285 /// .is_some());
1286 /// assert_eq!(table.len(), 1);
1287 /// # }
1288 /// # fn main() {
1289 /// # #[cfg(feature = "nightly")]
1290 /// # test()
1291 /// # }
1292 /// ```
1293 pub fn or_insert(self, default: T) -> OccupiedEntry<'a, T, A> {
1294 match self {
1295 Entry::Occupied(entry) => entry,
1296 Entry::Vacant(entry) => entry.insert(default),
1297 }
1298 }
1299
1300 /// Ensures a value is in the entry by inserting the result of the default function if empty..
1301 ///
1302 /// Returns an [`OccupiedEntry`] pointing to the now-occupied entry.
1303 ///
1304 /// # Examples
1305 ///
1306 /// ```
1307 /// # #[cfg(feature = "nightly")]
1308 /// # fn test() {
1309 /// use ahash::AHasher;
1310 /// use hashbrown::HashTable;
1311 /// use std::hash::{BuildHasher, BuildHasherDefault};
1312 ///
1313 /// let mut table: HashTable<String> = HashTable::new();
1314 /// let hasher = BuildHasherDefault::<AHasher>::default();
1315 /// let hasher = |val: &_| hasher.hash_one(val);
1316 ///
1317 /// table
1318 /// .entry(hasher("poneyland"), |x| x == "poneyland", |val| hasher(val))
1319 /// .or_insert_with(|| "poneyland".to_string());
1320 ///
1321 /// assert!(table
1322 /// .find(hasher(&"poneyland"), |x| x == "poneyland")
1323 /// .is_some());
1324 /// # }
1325 /// # fn main() {
1326 /// # #[cfg(feature = "nightly")]
1327 /// # test()
1328 /// # }
1329 /// ```
1330 pub fn or_insert_with(self, default: impl FnOnce() -> T) -> OccupiedEntry<'a, T, A> {
1331 match self {
1332 Entry::Occupied(entry) => entry,
1333 Entry::Vacant(entry) => entry.insert(default()),
1334 }
1335 }
1336
1337 /// Provides in-place mutable access to an occupied entry before any
1338 /// potential inserts into the table.
1339 ///
1340 /// # Examples
1341 ///
1342 /// ```
1343 /// # #[cfg(feature = "nightly")]
1344 /// # fn test() {
1345 /// use ahash::AHasher;
1346 /// use hashbrown::HashTable;
1347 /// use std::hash::{BuildHasher, BuildHasherDefault};
1348 ///
1349 /// let mut table: HashTable<(&str, u32)> = HashTable::new();
1350 /// let hasher = BuildHasherDefault::<AHasher>::default();
1351 /// let hasher = |val: &_| hasher.hash_one(val);
1352 ///
1353 /// table
1354 /// .entry(
1355 /// hasher(&"poneyland"),
1356 /// |&(x, _)| x == "poneyland",
1357 /// |(k, _)| hasher(&k),
1358 /// )
1359 /// .and_modify(|(_, v)| *v += 1)
1360 /// .or_insert(("poneyland", 42));
1361 /// assert_eq!(
1362 /// table.find(hasher(&"poneyland"), |&(k, _)| k == "poneyland"),
1363 /// Some(&("poneyland", 42))
1364 /// );
1365 ///
1366 /// table
1367 /// .entry(
1368 /// hasher(&"poneyland"),
1369 /// |&(x, _)| x == "poneyland",
1370 /// |(k, _)| hasher(&k),
1371 /// )
1372 /// .and_modify(|(_, v)| *v += 1)
1373 /// .or_insert(("poneyland", 42));
1374 /// assert_eq!(
1375 /// table.find(hasher(&"poneyland"), |&(k, _)| k == "poneyland"),
1376 /// Some(&("poneyland", 43))
1377 /// );
1378 /// # }
1379 /// # fn main() {
1380 /// # #[cfg(feature = "nightly")]
1381 /// # test()
1382 /// # }
1383 /// ```
1384 pub fn and_modify(self, f: impl FnOnce(&mut T)) -> Self {
1385 match self {
1386 Entry::Occupied(mut entry) => {
1387 f(entry.get_mut());
1388 Entry::Occupied(entry)
1389 }
1390 Entry::Vacant(entry) => Entry::Vacant(entry),
1391 }
1392 }
1393}
1394
1395/// A view into an occupied entry in a `HashTable`.
1396/// It is part of the [`Entry`] enum.
1397///
1398/// [`Entry`]: enum.Entry.html
1399///
1400/// # Examples
1401///
1402/// ```
1403/// # #[cfg(feature = "nightly")]
1404/// # fn test() {
1405/// use ahash::AHasher;
1406/// use hashbrown::hash_table::{Entry, HashTable, OccupiedEntry};
1407/// use std::hash::{BuildHasher, BuildHasherDefault};
1408///
1409/// let mut table = HashTable::new();
1410/// let hasher = BuildHasherDefault::<AHasher>::default();
1411/// let hasher = |val: &_| hasher.hash_one(val);
1412/// for x in ["a", "b", "c"] {
1413/// table.insert_unique(hasher(&x), x, hasher);
1414/// }
1415/// assert_eq!(table.len(), 3);
1416///
1417/// let _entry_o: OccupiedEntry<_, _> = table.find_entry(hasher(&"a"), |&x| x == "a").unwrap();
1418/// assert_eq!(table.len(), 3);
1419///
1420/// // Existing key
1421/// match table.entry(hasher(&"a"), |&x| x == "a", hasher) {
1422/// Entry::Vacant(_) => unreachable!(),
1423/// Entry::Occupied(view) => {
1424/// assert_eq!(view.get(), &"a");
1425/// }
1426/// }
1427///
1428/// assert_eq!(table.len(), 3);
1429///
1430/// // Existing key (take)
1431/// match table.entry(hasher(&"c"), |&x| x == "c", hasher) {
1432/// Entry::Vacant(_) => unreachable!(),
1433/// Entry::Occupied(view) => {
1434/// assert_eq!(view.remove().0, "c");
1435/// }
1436/// }
1437/// assert_eq!(table.find(hasher(&"c"), |&x| x == "c"), None);
1438/// assert_eq!(table.len(), 2);
1439/// # }
1440/// # fn main() {
1441/// # #[cfg(feature = "nightly")]
1442/// # test()
1443/// # }
1444/// ```
1445pub struct OccupiedEntry<'a, T, A = Global>
1446where
1447 A: Allocator,
1448{
1449 hash: u64,
1450 bucket: Bucket<T>,
1451 table: &'a mut HashTable<T, A>,
1452}
1453
1454unsafe impl<T, A> Send for OccupiedEntry<'_, T, A>
1455where
1456 T: Send,
1457 A: Send + Allocator,
1458{
1459}
1460unsafe impl<T, A> Sync for OccupiedEntry<'_, T, A>
1461where
1462 T: Sync,
1463 A: Sync + Allocator,
1464{
1465}
1466
1467impl<T: fmt::Debug, A: Allocator> fmt::Debug for OccupiedEntry<'_, T, A> {
1468 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1469 f.debug_struct("OccupiedEntry")
1470 .field("value", self.get())
1471 .finish()
1472 }
1473}
1474
1475impl<'a, T, A> OccupiedEntry<'a, T, A>
1476where
1477 A: Allocator,
1478{
1479 /// Takes the value out of the entry, and returns it along with a
1480 /// `VacantEntry` that can be used to insert another value with the same
1481 /// hash as the one that was just removed.
1482 ///
1483 /// # Examples
1484 ///
1485 /// ```
1486 /// # #[cfg(feature = "nightly")]
1487 /// # fn test() {
1488 /// use ahash::AHasher;
1489 /// use hashbrown::hash_table::Entry;
1490 /// use hashbrown::HashTable;
1491 /// use std::hash::{BuildHasher, BuildHasherDefault};
1492 ///
1493 /// let mut table: HashTable<&str> = HashTable::new();
1494 /// let hasher = BuildHasherDefault::<AHasher>::default();
1495 /// let hasher = |val: &_| hasher.hash_one(val);
1496 /// // The table is empty
1497 /// assert!(table.is_empty() && table.capacity() == 0);
1498 ///
1499 /// table.insert_unique(hasher(&"poneyland"), "poneyland", hasher);
1500 /// let capacity_before_remove = table.capacity();
1501 ///
1502 /// if let Entry::Occupied(o) = table.entry(hasher(&"poneyland"), |&x| x == "poneyland", hasher) {
1503 /// assert_eq!(o.remove().0, "poneyland");
1504 /// }
1505 ///
1506 /// assert!(table
1507 /// .find(hasher(&"poneyland"), |&x| x == "poneyland")
1508 /// .is_none());
1509 /// // Now table hold none elements but capacity is equal to the old one
1510 /// assert!(table.len() == 0 && table.capacity() == capacity_before_remove);
1511 /// # }
1512 /// # fn main() {
1513 /// # #[cfg(feature = "nightly")]
1514 /// # test()
1515 /// # }
1516 /// ```
1517 pub fn remove(self) -> (T, VacantEntry<'a, T, A>) {
1518 let (val, slot) = unsafe { self.table.raw.remove(self.bucket) };
1519 (
1520 val,
1521 VacantEntry {
1522 hash: self.hash,
1523 insert_slot: slot,
1524 table: self.table,
1525 },
1526 )
1527 }
1528
1529 /// Gets a reference to the value in the entry.
1530 ///
1531 /// # Examples
1532 ///
1533 /// ```
1534 /// # #[cfg(feature = "nightly")]
1535 /// # fn test() {
1536 /// use ahash::AHasher;
1537 /// use hashbrown::hash_table::Entry;
1538 /// use hashbrown::HashTable;
1539 /// use std::hash::{BuildHasher, BuildHasherDefault};
1540 ///
1541 /// let mut table: HashTable<&str> = HashTable::new();
1542 /// let hasher = BuildHasherDefault::<AHasher>::default();
1543 /// let hasher = |val: &_| hasher.hash_one(val);
1544 /// table.insert_unique(hasher(&"poneyland"), "poneyland", hasher);
1545 ///
1546 /// match table.entry(hasher(&"poneyland"), |&x| x == "poneyland", hasher) {
1547 /// Entry::Vacant(_) => panic!(),
1548 /// Entry::Occupied(entry) => assert_eq!(entry.get(), &"poneyland"),
1549 /// }
1550 /// # }
1551 /// # fn main() {
1552 /// # #[cfg(feature = "nightly")]
1553 /// # test()
1554 /// # }
1555 /// ```
1556 pub fn get(&self) -> &T {
1557 unsafe { self.bucket.as_ref() }
1558 }
1559
1560 /// Gets a mutable reference to the value in the entry.
1561 ///
1562 /// If you need a reference to the `OccupiedEntry` which may outlive the
1563 /// destruction of the `Entry` value, see [`into_mut`].
1564 ///
1565 /// [`into_mut`]: #method.into_mut
1566 ///
1567 /// # Examples
1568 ///
1569 /// ```
1570 /// # #[cfg(feature = "nightly")]
1571 /// # fn test() {
1572 /// use ahash::AHasher;
1573 /// use hashbrown::hash_table::Entry;
1574 /// use hashbrown::HashTable;
1575 /// use std::hash::{BuildHasher, BuildHasherDefault};
1576 ///
1577 /// let mut table: HashTable<(&str, u32)> = HashTable::new();
1578 /// let hasher = BuildHasherDefault::<AHasher>::default();
1579 /// let hasher = |val: &_| hasher.hash_one(val);
1580 /// table.insert_unique(hasher(&"poneyland"), ("poneyland", 12), |(k, _)| hasher(&k));
1581 ///
1582 /// assert_eq!(
1583 /// table.find(hasher(&"poneyland"), |&(x, _)| x == "poneyland",),
1584 /// Some(&("poneyland", 12))
1585 /// );
1586 ///
1587 /// if let Entry::Occupied(mut o) = table.entry(
1588 /// hasher(&"poneyland"),
1589 /// |&(x, _)| x == "poneyland",
1590 /// |(k, _)| hasher(&k),
1591 /// ) {
1592 /// o.get_mut().1 += 10;
1593 /// assert_eq!(o.get().1, 22);
1594 ///
1595 /// // We can use the same Entry multiple times.
1596 /// o.get_mut().1 += 2;
1597 /// }
1598 ///
1599 /// assert_eq!(
1600 /// table.find(hasher(&"poneyland"), |&(x, _)| x == "poneyland",),
1601 /// Some(&("poneyland", 24))
1602 /// );
1603 /// # }
1604 /// # fn main() {
1605 /// # #[cfg(feature = "nightly")]
1606 /// # test()
1607 /// # }
1608 /// ```
1609 pub fn get_mut(&mut self) -> &mut T {
1610 unsafe { self.bucket.as_mut() }
1611 }
1612
1613 /// Converts the OccupiedEntry into a mutable reference to the value in the entry
1614 /// with a lifetime bound to the table itself.
1615 ///
1616 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
1617 ///
1618 /// [`get_mut`]: #method.get_mut
1619 ///
1620 /// # Examples
1621 ///
1622 /// ```
1623 /// # #[cfg(feature = "nightly")]
1624 /// # fn test() {
1625 /// use ahash::AHasher;
1626 /// use hashbrown::hash_table::Entry;
1627 /// use hashbrown::HashTable;
1628 /// use std::hash::{BuildHasher, BuildHasherDefault};
1629 ///
1630 /// let mut table: HashTable<(&str, u32)> = HashTable::new();
1631 /// let hasher = BuildHasherDefault::<AHasher>::default();
1632 /// let hasher = |val: &_| hasher.hash_one(val);
1633 /// table.insert_unique(hasher(&"poneyland"), ("poneyland", 12), |(k, _)| hasher(&k));
1634 ///
1635 /// assert_eq!(
1636 /// table.find(hasher(&"poneyland"), |&(x, _)| x == "poneyland",),
1637 /// Some(&("poneyland", 12))
1638 /// );
1639 ///
1640 /// let value: &mut (&str, u32);
1641 /// match table.entry(
1642 /// hasher(&"poneyland"),
1643 /// |&(x, _)| x == "poneyland",
1644 /// |(k, _)| hasher(&k),
1645 /// ) {
1646 /// Entry::Occupied(entry) => value = entry.into_mut(),
1647 /// Entry::Vacant(_) => panic!(),
1648 /// }
1649 /// value.1 += 10;
1650 ///
1651 /// assert_eq!(
1652 /// table.find(hasher(&"poneyland"), |&(x, _)| x == "poneyland",),
1653 /// Some(&("poneyland", 22))
1654 /// );
1655 /// # }
1656 /// # fn main() {
1657 /// # #[cfg(feature = "nightly")]
1658 /// # test()
1659 /// # }
1660 /// ```
1661 pub fn into_mut(self) -> &'a mut T {
1662 unsafe { self.bucket.as_mut() }
1663 }
1664
1665 /// Converts the OccupiedEntry into a mutable reference to the underlying
1666 /// table.
1667 pub fn into_table(self) -> &'a mut HashTable<T, A> {
1668 self.table
1669 }
1670}
1671
1672/// A view into a vacant entry in a `HashTable`.
1673/// It is part of the [`Entry`] enum.
1674///
1675/// [`Entry`]: enum.Entry.html
1676///
1677/// # Examples
1678///
1679/// ```
1680/// # #[cfg(feature = "nightly")]
1681/// # fn test() {
1682/// use ahash::AHasher;
1683/// use hashbrown::hash_table::{Entry, HashTable, VacantEntry};
1684/// use std::hash::{BuildHasher, BuildHasherDefault};
1685///
1686/// let mut table: HashTable<&str> = HashTable::new();
1687/// let hasher = BuildHasherDefault::<AHasher>::default();
1688/// let hasher = |val: &_| hasher.hash_one(val);
1689///
1690/// let entry_v: VacantEntry<_, _> = match table.entry(hasher(&"a"), |&x| x == "a", hasher) {
1691/// Entry::Vacant(view) => view,
1692/// Entry::Occupied(_) => unreachable!(),
1693/// };
1694/// entry_v.insert("a");
1695/// assert!(table.find(hasher(&"a"), |&x| x == "a").is_some() && table.len() == 1);
1696///
1697/// // Nonexistent key (insert)
1698/// match table.entry(hasher(&"b"), |&x| x == "b", hasher) {
1699/// Entry::Vacant(view) => {
1700/// view.insert("b");
1701/// }
1702/// Entry::Occupied(_) => unreachable!(),
1703/// }
1704/// assert!(table.find(hasher(&"b"), |&x| x == "b").is_some() && table.len() == 2);
1705/// # }
1706/// # fn main() {
1707/// # #[cfg(feature = "nightly")]
1708/// # test()
1709/// # }
1710/// ```
1711pub struct VacantEntry<'a, T, A = Global>
1712where
1713 A: Allocator,
1714{
1715 hash: u64,
1716 insert_slot: InsertSlot,
1717 table: &'a mut HashTable<T, A>,
1718}
1719
1720impl<T: fmt::Debug, A: Allocator> fmt::Debug for VacantEntry<'_, T, A> {
1721 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1722 f.write_str("VacantEntry")
1723 }
1724}
1725
1726impl<'a, T, A> VacantEntry<'a, T, A>
1727where
1728 A: Allocator,
1729{
1730 /// Inserts a new element into the table with the hash that was used to
1731 /// obtain the `VacantEntry`.
1732 ///
1733 /// An `OccupiedEntry` is returned for the newly inserted element.
1734 ///
1735 /// # Examples
1736 ///
1737 /// ```
1738 /// # #[cfg(feature = "nightly")]
1739 /// # fn test() {
1740 /// use ahash::AHasher;
1741 /// use hashbrown::hash_table::Entry;
1742 /// use hashbrown::HashTable;
1743 /// use std::hash::{BuildHasher, BuildHasherDefault};
1744 ///
1745 /// let mut table: HashTable<&str> = HashTable::new();
1746 /// let hasher = BuildHasherDefault::<AHasher>::default();
1747 /// let hasher = |val: &_| hasher.hash_one(val);
1748 ///
1749 /// if let Entry::Vacant(o) = table.entry(hasher(&"poneyland"), |&x| x == "poneyland", hasher) {
1750 /// o.insert("poneyland");
1751 /// }
1752 /// assert_eq!(
1753 /// table.find(hasher(&"poneyland"), |&x| x == "poneyland"),
1754 /// Some(&"poneyland")
1755 /// );
1756 /// # }
1757 /// # fn main() {
1758 /// # #[cfg(feature = "nightly")]
1759 /// # test()
1760 /// # }
1761 /// ```
1762 pub fn insert(self, value: T) -> OccupiedEntry<'a, T, A> {
1763 let bucket = unsafe {
1764 self.table
1765 .raw
1766 .insert_in_slot(self.hash, self.insert_slot, value)
1767 };
1768 OccupiedEntry {
1769 hash: self.hash,
1770 bucket,
1771 table: self.table,
1772 }
1773 }
1774
1775 /// Converts the VacantEntry into a mutable reference to the underlying
1776 /// table.
1777 pub fn into_table(self) -> &'a mut HashTable<T, A> {
1778 self.table
1779 }
1780}
1781
1782/// Type representing the absence of an entry, as returned by [`HashTable::find_entry`].
1783///
1784/// This type only exists due to [limitations] in Rust's NLL borrow checker. In
1785/// the future, `find_entry` will return an `Option<OccupiedEntry>` and this
1786/// type will be removed.
1787///
1788/// [limitations]: https://smallcultfollowing.com/babysteps/blog/2018/06/15/mir-based-borrow-check-nll-status-update/#polonius
1789///
1790/// # Examples
1791///
1792/// ```
1793/// # #[cfg(feature = "nightly")]
1794/// # fn test() {
1795/// use ahash::AHasher;
1796/// use hashbrown::hash_table::{AbsentEntry, Entry, HashTable};
1797/// use std::hash::{BuildHasher, BuildHasherDefault};
1798///
1799/// let mut table: HashTable<&str> = HashTable::new();
1800/// let hasher = BuildHasherDefault::<AHasher>::default();
1801/// let hasher = |val: &_| hasher.hash_one(val);
1802///
1803/// let entry_v: AbsentEntry<_, _> = table.find_entry(hasher(&"a"), |&x| x == "a").unwrap_err();
1804/// entry_v
1805/// .into_table()
1806/// .insert_unique(hasher(&"a"), "a", hasher);
1807/// assert!(table.find(hasher(&"a"), |&x| x == "a").is_some() && table.len() == 1);
1808///
1809/// // Nonexistent key (insert)
1810/// match table.entry(hasher(&"b"), |&x| x == "b", hasher) {
1811/// Entry::Vacant(view) => {
1812/// view.insert("b");
1813/// }
1814/// Entry::Occupied(_) => unreachable!(),
1815/// }
1816/// assert!(table.find(hasher(&"b"), |&x| x == "b").is_some() && table.len() == 2);
1817/// # }
1818/// # fn main() {
1819/// # #[cfg(feature = "nightly")]
1820/// # test()
1821/// # }
1822/// ```
1823pub struct AbsentEntry<'a, T, A = Global>
1824where
1825 A: Allocator,
1826{
1827 table: &'a mut HashTable<T, A>,
1828}
1829
1830impl<T: fmt::Debug, A: Allocator> fmt::Debug for AbsentEntry<'_, T, A> {
1831 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1832 f.write_str("AbsentEntry")
1833 }
1834}
1835
1836impl<'a, T, A> AbsentEntry<'a, T, A>
1837where
1838 A: Allocator,
1839{
1840 /// Converts the AbsentEntry into a mutable reference to the underlying
1841 /// table.
1842 pub fn into_table(self) -> &'a mut HashTable<T, A> {
1843 self.table
1844 }
1845}
1846
1847/// An iterator over the entries of a `HashTable` in arbitrary order.
1848/// The iterator element type is `&'a T`.
1849///
1850/// This `struct` is created by the [`iter`] method on [`HashTable`]. See its
1851/// documentation for more.
1852///
1853/// [`iter`]: struct.HashTable.html#method.iter
1854/// [`HashTable`]: struct.HashTable.html
1855pub struct Iter<'a, T> {
1856 inner: RawIter<T>,
1857 marker: PhantomData<&'a T>,
1858}
1859
1860impl<'a, T> Iterator for Iter<'a, T> {
1861 type Item = &'a T;
1862
1863 fn next(&mut self) -> Option<Self::Item> {
1864 // Avoid `Option::map` because it bloats LLVM IR.
1865 match self.inner.next() {
1866 Some(bucket) => Some(unsafe { bucket.as_ref() }),
1867 None => None,
1868 }
1869 }
1870
1871 fn size_hint(&self) -> (usize, Option<usize>) {
1872 self.inner.size_hint()
1873 }
1874
1875 fn fold<B, F>(self, init: B, mut f: F) -> B
1876 where
1877 Self: Sized,
1878 F: FnMut(B, Self::Item) -> B,
1879 {
1880 self.inner
1881 .fold(init, |acc, bucket| unsafe { f(acc, bucket.as_ref()) })
1882 }
1883}
1884
1885impl<T> ExactSizeIterator for Iter<'_, T> {
1886 fn len(&self) -> usize {
1887 self.inner.len()
1888 }
1889}
1890
1891impl<T> FusedIterator for Iter<'_, T> {}
1892
1893/// A mutable iterator over the entries of a `HashTable` in arbitrary order.
1894/// The iterator element type is `&'a mut T`.
1895///
1896/// This `struct` is created by the [`iter_mut`] method on [`HashTable`]. See its
1897/// documentation for more.
1898///
1899/// [`iter_mut`]: struct.HashTable.html#method.iter_mut
1900/// [`HashTable`]: struct.HashTable.html
1901pub struct IterMut<'a, T> {
1902 inner: RawIter<T>,
1903 marker: PhantomData<&'a mut T>,
1904}
1905
1906impl<'a, T> Iterator for IterMut<'a, T> {
1907 type Item = &'a mut T;
1908
1909 fn next(&mut self) -> Option<Self::Item> {
1910 // Avoid `Option::map` because it bloats LLVM IR.
1911 match self.inner.next() {
1912 Some(bucket) => Some(unsafe { bucket.as_mut() }),
1913 None => None,
1914 }
1915 }
1916
1917 fn size_hint(&self) -> (usize, Option<usize>) {
1918 self.inner.size_hint()
1919 }
1920
1921 fn fold<B, F>(self, init: B, mut f: F) -> B
1922 where
1923 Self: Sized,
1924 F: FnMut(B, Self::Item) -> B,
1925 {
1926 self.inner
1927 .fold(init, |acc, bucket| unsafe { f(acc, bucket.as_mut()) })
1928 }
1929}
1930
1931impl<T> ExactSizeIterator for IterMut<'_, T> {
1932 fn len(&self) -> usize {
1933 self.inner.len()
1934 }
1935}
1936
1937impl<T> FusedIterator for IterMut<'_, T> {}
1938
1939/// An owning iterator over the entries of a `HashTable` in arbitrary order.
1940/// The iterator element type is `T`.
1941///
1942/// This `struct` is created by the [`into_iter`] method on [`HashTable`]
1943/// (provided by the [`IntoIterator`] trait). See its documentation for more.
1944/// The table cannot be used after calling that method.
1945///
1946/// [`into_iter`]: struct.HashTable.html#method.into_iter
1947/// [`HashTable`]: struct.HashTable.html
1948/// [`IntoIterator`]: https://doc.rust-lang.org/core/iter/trait.IntoIterator.html
1949pub struct IntoIter<T, A = Global>
1950where
1951 A: Allocator,
1952{
1953 inner: RawIntoIter<T, A>,
1954}
1955
1956impl<T, A> Iterator for IntoIter<T, A>
1957where
1958 A: Allocator,
1959{
1960 type Item = T;
1961
1962 fn next(&mut self) -> Option<Self::Item> {
1963 self.inner.next()
1964 }
1965
1966 fn size_hint(&self) -> (usize, Option<usize>) {
1967 self.inner.size_hint()
1968 }
1969
1970 fn fold<B, F>(self, init: B, f: F) -> B
1971 where
1972 Self: Sized,
1973 F: FnMut(B, Self::Item) -> B,
1974 {
1975 self.inner.fold(init, f)
1976 }
1977}
1978
1979impl<T, A> ExactSizeIterator for IntoIter<T, A>
1980where
1981 A: Allocator,
1982{
1983 fn len(&self) -> usize {
1984 self.inner.len()
1985 }
1986}
1987
1988impl<T, A> FusedIterator for IntoIter<T, A> where A: Allocator {}
1989
1990/// A draining iterator over the items of a `HashTable`.
1991///
1992/// This `struct` is created by the [`drain`] method on [`HashTable`].
1993/// See its documentation for more.
1994///
1995/// [`HashTable`]: struct.HashTable.html
1996/// [`drain`]: struct.HashTable.html#method.drain
1997pub struct Drain<'a, T, A: Allocator = Global> {
1998 inner: RawDrain<'a, T, A>,
1999}
2000
2001impl<T, A: Allocator> Drain<'_, T, A> {
2002 /// Returns a iterator of references over the remaining items.
2003 fn iter(&self) -> Iter<'_, T> {
2004 Iter {
2005 inner: self.inner.iter(),
2006 marker: PhantomData,
2007 }
2008 }
2009}
2010
2011impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
2012 type Item = T;
2013
2014 fn next(&mut self) -> Option<T> {
2015 self.inner.next()
2016 }
2017 fn size_hint(&self) -> (usize, Option<usize>) {
2018 self.inner.size_hint()
2019 }
2020}
2021impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
2022 fn len(&self) -> usize {
2023 self.inner.len()
2024 }
2025}
2026impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}
2027
2028impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
2029 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2030 f.debug_list().entries(self.iter()).finish()
2031 }
2032}
2033
2034/// A draining iterator over entries of a `HashTable` which don't satisfy the predicate `f`.
2035///
2036/// This `struct` is created by [`HashTable::extract_if`]. See its
2037/// documentation for more.
2038#[must_use = "Iterators are lazy unless consumed"]
2039pub struct ExtractIf<'a, T, F, A: Allocator = Global>
2040where
2041 F: FnMut(&mut T) -> bool,
2042{
2043 f: F,
2044 inner: RawExtractIf<'a, T, A>,
2045}
2046
2047impl<T, F, A: Allocator> Iterator for ExtractIf<'_, T, F, A>
2048where
2049 F: FnMut(&mut T) -> bool,
2050{
2051 type Item = T;
2052
2053 #[inline]
2054 fn next(&mut self) -> Option<Self::Item> {
2055 self.inner.next(|val| (self.f)(val))
2056 }
2057
2058 #[inline]
2059 fn size_hint(&self) -> (usize, Option<usize>) {
2060 (0, self.inner.iter.size_hint().1)
2061 }
2062}
2063
2064impl<T, F, A: Allocator> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&mut T) -> bool {}
2065