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