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