1 use alloc::{Global, Alloc, Layout, LayoutErr, handle_alloc_error};
2 use collections::CollectionAllocErr;
3 use hash::{BuildHasher, Hash, Hasher};
5 use mem::{size_of, needs_drop};
7 use ops::{Deref, DerefMut};
8 use ptr::{self, Unique, NonNull};
11 use self::BucketState::*;
13 /// Integer type used for stored hash values.
15 /// No more than bit_width(usize) bits are needed to select a bucket.
17 /// The most significant bit is ours to use for tagging `SafeHash`.
19 /// (Even if we could have usize::MAX bytes allocated for buckets,
20 /// each bucket stores at least a `HashUint`, so there can be no more than
21 /// usize::MAX / size_of(usize) buckets.)
22 type HashUint = usize;
24 const EMPTY_BUCKET: HashUint = 0;
25 const EMPTY: usize = 1;
27 /// Special `Unique<HashUint>` that uses the lower bit of the pointer
28 /// to expose a boolean tag.
29 /// Note: when the pointer is initialized to EMPTY `.ptr()` will return
30 /// null and the tag functions shouldn't be used.
31 struct TaggedHashUintPtr(Unique<HashUint>);
33 impl TaggedHashUintPtr {
35 unsafe fn new(ptr: *mut HashUint) -> Self {
36 debug_assert!(ptr as usize & 1 == 0 || ptr as usize == EMPTY as usize);
37 TaggedHashUintPtr(Unique::new_unchecked(ptr))
41 fn set_tag(&mut self, value: bool) {
42 let mut usize_ptr = self.0.as_ptr() as usize;
49 self.0 = Unique::new_unchecked(usize_ptr as *mut HashUint)
54 fn tag(&self) -> bool {
55 (self.0.as_ptr() as usize) & 1 == 1
59 fn ptr(&self) -> *mut HashUint {
60 (self.0.as_ptr() as usize & !1) as *mut HashUint
64 /// The raw hashtable, providing safe-ish access to the unzipped and highly
65 /// optimized arrays of hashes, and key-value pairs.
67 /// This design is a lot faster than the naive
68 /// `Vec<Option<(u64, K, V)>>`, because we don't pay for the overhead of an
69 /// option on every element, and we get a generally more cache-aware design.
71 /// Essential invariants of this structure:
73 /// - if `t.hashes[i] == EMPTY_BUCKET`, then `Bucket::at_index(&t, i).raw`
74 /// points to 'undefined' contents. Don't read from it. This invariant is
75 /// enforced outside this module with the `EmptyBucket`, `FullBucket`,
76 /// and `SafeHash` types.
78 /// - An `EmptyBucket` is only constructed at an index with
79 /// a hash of EMPTY_BUCKET.
81 /// - A `FullBucket` is only constructed at an index with a
82 /// non-EMPTY_BUCKET hash.
84 /// - A `SafeHash` is only constructed for non-`EMPTY_BUCKET` hash. We get
85 /// around hashes of zero by changing them to 0x8000_0000_0000_0000,
86 /// which will likely map to the same bucket, while not being confused
89 /// - Both "arrays represented by pointers" are the same length:
90 /// `capacity`. This is set at creation and never changes. The arrays
91 /// are unzipped and are more cache aware (scanning through 8 hashes
92 /// brings in at most 2 cache lines, since they're all right beside each
93 /// other). This layout may waste space in padding such as in a map from
94 /// u64 to u8, but is a more cache conscious layout as the key-value pairs
95 /// are only very shortly probed and the desired value will be in the same
96 /// or next cache line.
98 /// You can kind of think of this module/data structure as a safe wrapper
99 /// around just the "table" part of the hashtable. It enforces some
100 /// invariants at the type level and employs some performance trickery,
101 /// but in general is just a tricked out `Vec<Option<(u64, K, V)>>`.
103 /// The hashtable also exposes a special boolean tag. The tag defaults to false
104 /// when the RawTable is created and is accessible with the `tag` and `set_tag`
106 pub struct RawTable<K, V> {
107 capacity_mask: usize,
109 hashes: TaggedHashUintPtr,
111 // Because K/V do not appear directly in any of the types in the struct,
112 // inform rustc that in fact instances of K and V are reachable from here.
113 marker: marker::PhantomData<(K, V)>,
116 // An unsafe view of a RawTable bucket
117 // Valid indexes are within [0..table_capacity)
118 pub struct RawBucket<K, V> {
119 hash_start: *mut HashUint,
120 // We use *const to ensure covariance with respect to K and V
121 pair_start: *const (K, V),
123 _marker: marker::PhantomData<(K, V)>,
126 impl<K, V> Copy for RawBucket<K, V> {}
127 impl<K, V> Clone for RawBucket<K, V> {
128 fn clone(&self) -> RawBucket<K, V> {
133 pub struct Bucket<K, V, M> {
134 raw: RawBucket<K, V>,
138 impl<K, V, M: Copy> Copy for Bucket<K, V, M> {}
139 impl<K, V, M: Copy> Clone for Bucket<K, V, M> {
140 fn clone(&self) -> Bucket<K, V, M> {
145 pub struct EmptyBucket<K, V, M> {
146 raw: RawBucket<K, V>,
150 pub struct FullBucket<K, V, M> {
151 raw: RawBucket<K, V>,
155 pub type FullBucketMut<'table, K, V> = FullBucket<K, V, &'table mut RawTable<K, V>>;
157 pub enum BucketState<K, V, M> {
158 Empty(EmptyBucket<K, V, M>),
159 Full(FullBucket<K, V, M>),
162 // A GapThenFull encapsulates the state of two consecutive buckets at once.
163 // The first bucket, called the gap, is known to be empty.
164 // The second bucket is full.
165 pub struct GapThenFull<K, V, M> {
166 gap: EmptyBucket<K, V, ()>,
167 full: FullBucket<K, V, M>,
170 /// A hash that is not zero, since we use a hash of zero to represent empty
172 #[derive(PartialEq, Copy, Clone)]
173 pub struct SafeHash {
178 /// Peek at the hash value, which is guaranteed to be non-zero.
180 pub fn inspect(&self) -> HashUint {
185 pub fn new(hash: u64) -> Self {
186 // We need to avoid 0 in order to prevent collisions with
187 // EMPTY_HASH. We can maintain our precious uniform distribution
188 // of initial indexes by unconditionally setting the MSB,
189 // effectively reducing the hashes by one bit.
191 // Truncate hash to fit in `HashUint`.
192 let hash_bits = size_of::<HashUint>() * 8;
193 SafeHash { hash: (1 << (hash_bits - 1)) | (hash as HashUint) }
197 /// We need to remove hashes of 0. That's reserved for empty buckets.
198 /// This function wraps up `hash_keyed` to be the only way outside this
199 /// module to generate a SafeHash.
200 pub fn make_hash<T: ?Sized, S>(hash_state: &S, t: &T) -> SafeHash
204 let mut state = hash_state.build_hasher();
206 SafeHash::new(state.finish())
209 // `replace` casts a `*HashUint` to a `*SafeHash`. Since we statically
210 // ensure that a `FullBucket` points to an index with a non-zero hash,
211 // and a `SafeHash` is just a `HashUint` with a different name, this is
214 // This test ensures that a `SafeHash` really IS the same size as a
215 // `HashUint`. If you need to change the size of `SafeHash` (and
216 // consequently made this test fail), `replace` needs to be
217 // modified to no longer assume this.
219 fn can_alias_safehash_as_hash() {
220 assert_eq!(size_of::<SafeHash>(), size_of::<HashUint>())
223 // RawBucket methods are unsafe as it's possible to
224 // make a RawBucket point to invalid memory using safe code.
225 impl<K, V> RawBucket<K, V> {
226 unsafe fn hash(&self) -> *mut HashUint {
227 self.hash_start.add(self.idx)
229 unsafe fn pair(&self) -> *mut (K, V) {
230 self.pair_start.add(self.idx) as *mut (K, V)
232 unsafe fn hash_pair(&self) -> (*mut HashUint, *mut (K, V)) {
233 (self.hash(), self.pair())
237 // Buckets hold references to the table.
238 impl<K, V, M> FullBucket<K, V, M> {
239 /// Borrow a reference to the table.
240 pub fn table(&self) -> &M {
243 /// Borrow a mutable reference to the table.
244 pub fn table_mut(&mut self) -> &mut M {
247 /// Move out the reference to the table.
248 pub fn into_table(self) -> M {
251 /// Gets the raw index.
252 pub fn index(&self) -> usize {
255 /// Gets the raw bucket.
256 pub fn raw(&self) -> RawBucket<K, V> {
261 impl<K, V, M> EmptyBucket<K, V, M> {
262 /// Borrow a reference to the table.
263 pub fn table(&self) -> &M {
266 /// Borrow a mutable reference to the table.
267 pub fn table_mut(&mut self) -> &mut M {
272 impl<K, V, M> Bucket<K, V, M> {
273 /// Gets the raw index.
274 pub fn index(&self) -> usize {
278 pub fn into_table(self) -> M {
283 impl<K, V, M> Deref for FullBucket<K, V, M>
284 where M: Deref<Target = RawTable<K, V>>
286 type Target = RawTable<K, V>;
287 fn deref(&self) -> &RawTable<K, V> {
292 /// `Put` is implemented for types which provide access to a table and cannot be invalidated
293 /// by filling a bucket. A similar implementation for `Take` is possible.
294 pub trait Put<K, V> {
295 unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V>;
299 impl<'t, K, V> Put<K, V> for &'t mut RawTable<K, V> {
300 unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
305 impl<K, V, M> Put<K, V> for Bucket<K, V, M>
308 unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
309 self.table.borrow_table_mut()
313 impl<K, V, M> Put<K, V> for FullBucket<K, V, M>
316 unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
317 self.table.borrow_table_mut()
321 impl<K, V, M: Deref<Target = RawTable<K, V>>> Bucket<K, V, M> {
323 pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> {
324 Bucket::at_index(table, hash.inspect() as usize)
327 pub fn new_from(r: RawBucket<K, V>, t: M)
337 pub fn at_index(table: M, ib_index: usize) -> Bucket<K, V, M> {
338 // if capacity is 0, then the RawBucket will be populated with bogus pointers.
339 // This is an uncommon case though, so avoid it in release builds.
340 debug_assert!(table.capacity() > 0,
341 "Table should have capacity at this point");
342 let ib_index = ib_index & table.capacity_mask;
344 raw: table.raw_bucket_at(ib_index),
349 pub fn first(table: M) -> Bucket<K, V, M> {
351 raw: table.raw_bucket_at(0),
356 // "So a few of the first shall be last: for many be called,
359 // We'll most likely encounter a few buckets at the beginning that
360 // have their initial buckets near the end of the table. They were
361 // placed at the beginning as the probe wrapped around the table
362 // during insertion. We must skip forward to a bucket that won't
363 // get reinserted too early and won't unfairly steal others spot.
364 // This eliminates the need for robin hood.
365 pub fn head_bucket(table: M) -> Bucket<K, V, M> {
366 let mut bucket = Bucket::first(table);
369 bucket = match bucket.peek() {
371 if full.displacement() == 0 {
372 // This bucket occupies its ideal spot.
373 // It indicates the start of another "cluster".
374 bucket = full.into_bucket();
377 // Leaving this bucket in the last cluster for later.
381 // Encountered a hole between clusters.
390 /// Reads a bucket at a given index, returning an enum indicating whether
391 /// it's initialized or not. You need to match on this enum to get
392 /// the appropriate types to call most of the other functions in
394 pub fn peek(self) -> BucketState<K, V, M> {
395 match unsafe { *self.raw.hash() } {
411 /// Modifies the bucket in place to make it point to the next slot.
412 pub fn next(&mut self) {
413 self.raw.idx = self.raw.idx.wrapping_add(1) & self.table.capacity_mask;
416 /// Modifies the bucket in place to make it point to the previous slot.
417 pub fn prev(&mut self) {
418 self.raw.idx = self.raw.idx.wrapping_sub(1) & self.table.capacity_mask;
422 impl<K, V, M: Deref<Target = RawTable<K, V>>> EmptyBucket<K, V, M> {
424 pub fn next(self) -> Bucket<K, V, M> {
425 let mut bucket = self.into_bucket();
431 pub fn into_bucket(self) -> Bucket<K, V, M> {
438 pub fn gap_peek(self) -> Result<GapThenFull<K, V, M>, Bucket<K, V, M>> {
439 let gap = EmptyBucket {
444 match self.next().peek() {
451 Empty(e) => Err(e.into_bucket()),
456 impl<K, V, M> EmptyBucket<K, V, M>
459 /// Puts given key and value pair, along with the key's hash,
460 /// into this bucket in the hashtable. Note how `self` is 'moved' into
461 /// this function, because this slot will no longer be empty when
462 /// we return! A `FullBucket` is returned for later use, pointing to
463 /// the newly-filled slot in the hashtable.
465 /// Use `make_hash` to construct a `SafeHash` to pass to this function.
466 pub fn put(mut self, hash: SafeHash, key: K, value: V) -> FullBucket<K, V, M> {
468 *self.raw.hash() = hash.inspect();
469 ptr::write(self.raw.pair(), (key, value));
471 self.table.borrow_table_mut().size += 1;
481 impl<K, V, M: Deref<Target = RawTable<K, V>>> FullBucket<K, V, M> {
483 pub fn next(self) -> Bucket<K, V, M> {
484 let mut bucket = self.into_bucket();
490 pub fn into_bucket(self) -> Bucket<K, V, M> {
497 /// Duplicates the current position. This can be useful for operations
498 /// on two or more buckets.
499 pub fn stash(self) -> FullBucket<K, V, Self> {
506 /// Gets the distance between this bucket and the 'ideal' location
507 /// as determined by the key's hash stored in it.
509 /// In the cited blog posts above, this is called the "distance to
510 /// initial bucket", or DIB. Also known as "probe count".
511 pub fn displacement(&self) -> usize {
512 // Calculates the distance one has to travel when going from
513 // `hash mod capacity` onwards to `idx mod capacity`, wrapping around
514 // if the destination is not reached before the end of the table.
515 (self.raw.idx.wrapping_sub(self.hash().inspect() as usize)) & self.table.capacity_mask
519 pub fn hash(&self) -> SafeHash {
520 unsafe { SafeHash { hash: *self.raw.hash() } }
523 /// Gets references to the key and value at a given index.
524 pub fn read(&self) -> (&K, &V) {
526 let pair_ptr = self.raw.pair();
527 (&(*pair_ptr).0, &(*pair_ptr).1)
532 // We take a mutable reference to the table instead of accepting anything that
533 // implements `DerefMut` to prevent fn `take` from being called on `stash`ed
535 impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
536 /// Removes this bucket's key and value from the hashtable.
538 /// This works similarly to `put`, building an `EmptyBucket` out of the
540 pub fn take(self) -> (EmptyBucket<K, V, &'t mut RawTable<K, V>>, K, V) {
541 self.table.size -= 1;
544 *self.raw.hash() = EMPTY_BUCKET;
545 let (k, v) = ptr::read(self.raw.pair());
556 // This use of `Put` is misleading and restrictive, but safe and sufficient for our use cases
557 // where `M` is a full bucket or table reference type with mutable access to the table.
558 impl<K, V, M> FullBucket<K, V, M>
561 pub fn replace(&mut self, h: SafeHash, k: K, v: V) -> (SafeHash, K, V) {
563 let old_hash = ptr::replace(self.raw.hash() as *mut SafeHash, h);
564 let (old_key, old_val) = ptr::replace(self.raw.pair(), (k, v));
566 (old_hash, old_key, old_val)
571 impl<K, V, M> FullBucket<K, V, M>
572 where M: Deref<Target = RawTable<K, V>> + DerefMut
574 /// Gets mutable references to the key and value at a given index.
575 pub fn read_mut(&mut self) -> (&mut K, &mut V) {
577 let pair_ptr = self.raw.pair();
578 (&mut (*pair_ptr).0, &mut (*pair_ptr).1)
583 impl<'t, K, V, M> FullBucket<K, V, M>
584 where M: Deref<Target = RawTable<K, V>> + 't
586 /// Exchange a bucket state for immutable references into the table.
587 /// Because the underlying reference to the table is also consumed,
588 /// no further changes to the structure of the table are possible;
589 /// in exchange for this, the returned references have a longer lifetime
590 /// than the references returned by `read()`.
591 pub fn into_refs(self) -> (&'t K, &'t V) {
593 let pair_ptr = self.raw.pair();
594 (&(*pair_ptr).0, &(*pair_ptr).1)
599 impl<'t, K, V, M> FullBucket<K, V, M>
600 where M: Deref<Target = RawTable<K, V>> + DerefMut + 't
602 /// This works similarly to `into_refs`, exchanging a bucket state
603 /// for mutable references into the table.
604 pub fn into_mut_refs(self) -> (&'t mut K, &'t mut V) {
606 let pair_ptr = self.raw.pair();
607 (&mut (*pair_ptr).0, &mut (*pair_ptr).1)
612 impl<K, V, M> GapThenFull<K, V, M>
613 where M: Deref<Target = RawTable<K, V>>
616 pub fn full(&self) -> &FullBucket<K, V, M> {
620 pub fn into_table(self) -> M {
621 self.full.into_table()
624 pub fn shift(mut self) -> Result<GapThenFull<K, V, M>, Bucket<K, V, M>> {
626 let (gap_hash, gap_pair) = self.gap.raw.hash_pair();
627 let (full_hash, full_pair) = self.full.raw.hash_pair();
628 *gap_hash = mem::replace(&mut *full_hash, EMPTY_BUCKET);
629 ptr::copy_nonoverlapping(full_pair, gap_pair, 1);
632 let FullBucket { raw: prev_raw, .. } = self.full;
634 match self.full.next().peek() {
636 self.gap.raw = prev_raw;
642 Empty(b) => Err(b.into_bucket()),
647 // Returns a Layout which describes the allocation required for a hash table,
648 // and the offset of the array of (key, value) pairs in the allocation.
650 fn calculate_layout<K, V>(capacity: usize) -> Result<(Layout, usize), LayoutErr> {
651 let hashes = Layout::array::<HashUint>(capacity)?;
652 let pairs = Layout::array::<(K, V)>(capacity)?;
653 hashes.extend(pairs).map(|(layout, _)| {
654 // LLVM seems to have trouble properly const-propagating pairs.align(),
655 // possibly due to the use of NonZeroUsize. This little hack allows it
656 // to generate optimal code.
658 // See https://github.com/rust-lang/rust/issues/51346 for more details.
661 hashes.size() + hashes.padding_needed_for(mem::align_of::<(K, V)>()),
666 pub(crate) enum Fallibility {
671 use self::Fallibility::*;
673 impl<K, V> RawTable<K, V> {
674 /// Does not initialize the buckets. The caller should ensure they,
675 /// at the very least, set every hash to EMPTY_BUCKET.
676 /// Returns an error if it cannot allocate or capacity overflows.
677 unsafe fn new_uninitialized_internal(
679 fallibility: Fallibility,
680 ) -> Result<RawTable<K, V>, CollectionAllocErr> {
684 capacity_mask: capacity.wrapping_sub(1),
685 hashes: TaggedHashUintPtr::new(EMPTY as *mut HashUint),
686 marker: marker::PhantomData,
690 // Allocating hashmaps is a little tricky. We need to allocate two
691 // arrays, but since we know their sizes and alignments up front,
692 // we just allocate a single array, and then have the subarrays
694 let (layout, _) = calculate_layout::<K, V>(capacity)?;
695 let buffer = Global.alloc(layout).map_err(|e| match fallibility {
696 Infallible => handle_alloc_error(layout),
701 capacity_mask: capacity.wrapping_sub(1),
703 hashes: TaggedHashUintPtr::new(buffer.cast().as_ptr()),
704 marker: marker::PhantomData,
708 /// Does not initialize the buckets. The caller should ensure they,
709 /// at the very least, set every hash to EMPTY_BUCKET.
710 unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V> {
711 match Self::new_uninitialized_internal(capacity, Infallible) {
712 Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
713 Err(CollectionAllocErr::AllocErr) => unreachable!(),
714 Ok(table) => { table }
719 fn raw_bucket_at(&self, index: usize) -> RawBucket<K, V> {
720 let (_, pairs_offset) = calculate_layout::<K, V>(self.capacity())
721 .unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() });
722 let buffer = self.hashes.ptr() as *mut u8;
725 hash_start: buffer as *mut HashUint,
726 pair_start: buffer.add(pairs_offset) as *const (K, V),
728 _marker: marker::PhantomData,
736 fallibility: Fallibility,
737 ) -> Result<RawTable<K, V>, CollectionAllocErr> {
739 let ret = RawTable::new_uninitialized_internal(capacity, fallibility)?;
741 ptr::write_bytes(ret.hashes.ptr(), 0, capacity);
747 /// Tries to create a new raw table from a given capacity. If it cannot allocate,
748 /// it returns with AllocErr.
750 pub fn try_new(capacity: usize) -> Result<RawTable<K, V>, CollectionAllocErr> {
751 Self::new_internal(capacity, Fallible)
754 /// Creates a new raw table from a given capacity. All buckets are
757 pub fn new(capacity: usize) -> RawTable<K, V> {
758 match Self::new_internal(capacity, Infallible) {
759 Err(CollectionAllocErr::CapacityOverflow) => panic!("capacity overflow"),
760 Err(CollectionAllocErr::AllocErr) => unreachable!(),
761 Ok(table) => { table }
765 /// The hashtable's capacity, similar to a vector's.
766 pub fn capacity(&self) -> usize {
767 self.capacity_mask.wrapping_add(1)
770 /// The number of elements ever `put` in the hashtable, minus the number
771 /// of elements ever `take`n.
772 pub fn size(&self) -> usize {
776 fn raw_buckets(&self) -> RawBuckets<K, V> {
778 raw: self.raw_bucket_at(0),
779 elems_left: self.size,
780 marker: marker::PhantomData,
784 pub fn iter(&self) -> Iter<K, V> {
786 iter: self.raw_buckets(),
790 pub fn iter_mut(&mut self) -> IterMut<K, V> {
792 iter: self.raw_buckets(),
793 _marker: marker::PhantomData,
797 pub fn into_iter(self) -> IntoIter<K, V> {
798 let RawBuckets { raw, elems_left, .. } = self.raw_buckets();
799 // Replace the marker regardless of lifetime bounds on parameters.
804 marker: marker::PhantomData,
810 pub fn drain(&mut self) -> Drain<K, V> {
811 let RawBuckets { raw, elems_left, .. } = self.raw_buckets();
812 // Replace the marker regardless of lifetime bounds on parameters.
817 marker: marker::PhantomData,
819 table: NonNull::from(self),
820 marker: marker::PhantomData,
824 /// Drops buckets in reverse order. It leaves the table in an inconsistent
825 /// state and should only be used for dropping the table's remaining
826 /// entries. It's used in the implementation of Drop.
827 unsafe fn rev_drop_buckets(&mut self) {
828 // initialize the raw bucket past the end of the table
829 let mut raw = self.raw_bucket_at(self.capacity());
830 let mut elems_left = self.size;
832 while elems_left != 0 {
835 if *raw.hash() != EMPTY_BUCKET {
837 ptr::drop_in_place(raw.pair());
842 /// Sets the table tag.
843 pub fn set_tag(&mut self, value: bool) {
844 self.hashes.set_tag(value)
847 /// Gets the table tag.
848 pub fn tag(&self) -> bool {
853 /// A raw iterator. The basis for some other iterators in this module. Although
854 /// this interface is safe, it's not used outside this module.
855 struct RawBuckets<'a, K, V> {
856 raw: RawBucket<K, V>,
859 // Strictly speaking, this should be &'a (K,V), but that would
860 // require that K:'a, and we often use RawBuckets<'static...> for
861 // move iterations, so that messes up a lot of other things. So
862 // just use `&'a (K,V)` as this is not a publicly exposed type
864 marker: marker::PhantomData<&'a ()>,
867 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
868 impl<'a, K, V> Clone for RawBuckets<'a, K, V> {
869 fn clone(&self) -> RawBuckets<'a, K, V> {
872 elems_left: self.elems_left,
873 marker: marker::PhantomData,
879 impl<'a, K, V> Iterator for RawBuckets<'a, K, V> {
880 type Item = RawBucket<K, V>;
882 fn next(&mut self) -> Option<RawBucket<K, V>> {
883 if self.elems_left == 0 {
891 if *item.hash() != EMPTY_BUCKET {
892 self.elems_left -= 1;
899 fn size_hint(&self) -> (usize, Option<usize>) {
900 (self.elems_left, Some(self.elems_left))
904 impl<'a, K, V> ExactSizeIterator for RawBuckets<'a, K, V> {
905 fn len(&self) -> usize {
910 /// Iterator over shared references to entries in a table.
911 pub struct Iter<'a, K: 'a, V: 'a> {
912 iter: RawBuckets<'a, K, V>,
915 unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {}
916 unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {}
918 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
919 impl<'a, K, V> Clone for Iter<'a, K, V> {
920 fn clone(&self) -> Iter<'a, K, V> {
922 iter: self.iter.clone(),
927 /// Iterator over mutable references to entries in a table.
928 pub struct IterMut<'a, K: 'a, V: 'a> {
929 iter: RawBuckets<'a, K, V>,
930 // To ensure invariance with respect to V
931 _marker: marker::PhantomData<&'a mut V>,
934 unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {}
935 // Both K: Sync and K: Send are correct for IterMut's Send impl,
936 // but Send is the more useful bound
937 unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {}
939 impl<'a, K: 'a, V: 'a> IterMut<'a, K, V> {
940 pub fn iter(&self) -> Iter<K, V> {
942 iter: self.iter.clone(),
947 /// Iterator over the entries in a table, consuming the table.
948 pub struct IntoIter<K, V> {
949 table: RawTable<K, V>,
950 iter: RawBuckets<'static, K, V>,
953 unsafe impl<K: Sync, V: Sync> Sync for IntoIter<K, V> {}
954 unsafe impl<K: Send, V: Send> Send for IntoIter<K, V> {}
956 impl<K, V> IntoIter<K, V> {
957 pub fn iter(&self) -> Iter<K, V> {
959 iter: self.iter.clone(),
964 /// Iterator over the entries in a table, clearing the table.
965 pub struct Drain<'a, K: 'a, V: 'a> {
966 table: NonNull<RawTable<K, V>>,
967 iter: RawBuckets<'static, K, V>,
968 marker: marker::PhantomData<&'a RawTable<K, V>>,
971 unsafe impl<'a, K: Sync, V: Sync> Sync for Drain<'a, K, V> {}
972 unsafe impl<'a, K: Send, V: Send> Send for Drain<'a, K, V> {}
974 impl<'a, K, V> Drain<'a, K, V> {
975 pub fn iter(&self) -> Iter<K, V> {
977 iter: self.iter.clone(),
982 impl<'a, K, V> Iterator for Iter<'a, K, V> {
983 type Item = (&'a K, &'a V);
985 fn next(&mut self) -> Option<(&'a K, &'a V)> {
986 self.iter.next().map(|raw| unsafe {
987 let pair_ptr = raw.pair();
988 (&(*pair_ptr).0, &(*pair_ptr).1)
992 fn size_hint(&self) -> (usize, Option<usize>) {
993 self.iter.size_hint()
997 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
998 fn len(&self) -> usize {
1003 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1004 type Item = (&'a K, &'a mut V);
1006 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1007 self.iter.next().map(|raw| unsafe {
1008 let pair_ptr = raw.pair();
1009 (&(*pair_ptr).0, &mut (*pair_ptr).1)
1013 fn size_hint(&self) -> (usize, Option<usize>) {
1014 self.iter.size_hint()
1018 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
1019 fn len(&self) -> usize {
1024 impl<K, V> Iterator for IntoIter<K, V> {
1025 type Item = (SafeHash, K, V);
1027 fn next(&mut self) -> Option<(SafeHash, K, V)> {
1028 self.iter.next().map(|raw| {
1029 self.table.size -= 1;
1031 let (k, v) = ptr::read(raw.pair());
1032 (SafeHash { hash: *raw.hash() }, k, v)
1037 fn size_hint(&self) -> (usize, Option<usize>) {
1038 self.iter.size_hint()
1042 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1043 fn len(&self) -> usize {
1048 impl<'a, K, V> Iterator for Drain<'a, K, V> {
1049 type Item = (SafeHash, K, V);
1052 fn next(&mut self) -> Option<(SafeHash, K, V)> {
1053 self.iter.next().map(|raw| {
1055 self.table.as_mut().size -= 1;
1056 let (k, v) = ptr::read(raw.pair());
1057 (SafeHash { hash: ptr::replace(&mut *raw.hash(), EMPTY_BUCKET) }, k, v)
1062 fn size_hint(&self) -> (usize, Option<usize>) {
1063 self.iter.size_hint()
1067 impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
1068 fn len(&self) -> usize {
1073 impl<'a, K: 'a, V: 'a> Drop for Drain<'a, K, V> {
1074 fn drop(&mut self) {
1075 self.for_each(drop);
1079 impl<K: Clone, V: Clone> Clone for RawTable<K, V> {
1080 fn clone(&self) -> RawTable<K, V> {
1082 let cap = self.capacity();
1083 let mut new_ht = RawTable::new_uninitialized(cap);
1085 let mut new_buckets = new_ht.raw_bucket_at(0);
1086 let mut buckets = self.raw_bucket_at(0);
1087 while buckets.idx < cap {
1088 *new_buckets.hash() = *buckets.hash();
1089 if *new_buckets.hash() != EMPTY_BUCKET {
1090 let pair_ptr = buckets.pair();
1091 let kv = ((*pair_ptr).0.clone(), (*pair_ptr).1.clone());
1092 ptr::write(new_buckets.pair(), kv);
1095 new_buckets.idx += 1;
1098 new_ht.size = self.size();
1099 new_ht.set_tag(self.tag());
1106 unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for RawTable<K, V> {
1107 fn drop(&mut self) {
1108 if self.capacity() == 0 {
1112 // This is done in reverse because we've likely partially taken
1113 // some elements out with `.into_iter()` from the front.
1114 // Check if the size is 0, so we don't do a useless scan when
1115 // dropping empty tables such as on resize.
1116 // Also avoid double drop of elements that have been already moved out.
1118 if needs_drop::<(K, V)>() {
1119 // avoid linear runtime for types that don't need drop
1120 self.rev_drop_buckets();
1124 let (layout, _) = calculate_layout::<K, V>(self.capacity())
1125 .unwrap_or_else(|_| unsafe { hint::unreachable_unchecked() });
1127 Global.dealloc(NonNull::new_unchecked(self.hashes.ptr()).cast(), layout);
1128 // Remember how everything was allocated out of one buffer
1129 // during initialization? We only need one call to free here.