summaryrefslogtreecommitdiffstats
path: root/vendor/hashbrown-0.12.3/src/raw
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/hashbrown-0.12.3/src/raw')
-rw-r--r--vendor/hashbrown-0.12.3/src/raw/alloc.rs73
-rw-r--r--vendor/hashbrown-0.12.3/src/raw/bitmask.rs122
-rw-r--r--vendor/hashbrown-0.12.3/src/raw/generic.rs154
-rw-r--r--vendor/hashbrown-0.12.3/src/raw/mod.rs2460
-rw-r--r--vendor/hashbrown-0.12.3/src/raw/sse2.rs146
5 files changed, 2955 insertions, 0 deletions
diff --git a/vendor/hashbrown-0.12.3/src/raw/alloc.rs b/vendor/hashbrown-0.12.3/src/raw/alloc.rs
new file mode 100644
index 000000000..ba09ea9de
--- /dev/null
+++ b/vendor/hashbrown-0.12.3/src/raw/alloc.rs
@@ -0,0 +1,73 @@
+pub(crate) use self::inner::{do_alloc, Allocator, Global};
+
+#[cfg(feature = "nightly")]
+mod inner {
+ use crate::alloc::alloc::Layout;
+ pub use crate::alloc::alloc::{Allocator, Global};
+ use core::ptr::NonNull;
+
+ #[allow(clippy::map_err_ignore)]
+ pub fn do_alloc<A: Allocator>(alloc: &A, layout: Layout) -> Result<NonNull<u8>, ()> {
+ match alloc.allocate(layout) {
+ Ok(ptr) => Ok(ptr.as_non_null_ptr()),
+ Err(_) => Err(()),
+ }
+ }
+
+ #[cfg(feature = "bumpalo")]
+ unsafe impl Allocator for crate::BumpWrapper<'_> {
+ #[inline]
+ fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, core::alloc::AllocError> {
+ match self.0.try_alloc_layout(layout) {
+ Ok(ptr) => Ok(NonNull::slice_from_raw_parts(ptr, layout.size())),
+ Err(_) => Err(core::alloc::AllocError),
+ }
+ }
+ #[inline]
+ unsafe fn deallocate(&self, _ptr: NonNull<u8>, _layout: Layout) {}
+ }
+}
+
+#[cfg(not(feature = "nightly"))]
+mod inner {
+ use crate::alloc::alloc::{alloc, dealloc, Layout};
+ use core::ptr::NonNull;
+
+ #[allow(clippy::missing_safety_doc)] // not exposed outside of this crate
+ pub unsafe trait Allocator {
+ fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()>;
+ unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
+ }
+
+ #[derive(Copy, Clone)]
+ pub struct Global;
+ unsafe impl Allocator for Global {
+ #[inline]
+ fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()> {
+ unsafe { NonNull::new(alloc(layout)).ok_or(()) }
+ }
+ #[inline]
+ unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
+ dealloc(ptr.as_ptr(), layout);
+ }
+ }
+ impl Default for Global {
+ #[inline]
+ fn default() -> Self {
+ Global
+ }
+ }
+
+ pub fn do_alloc<A: Allocator>(alloc: &A, layout: Layout) -> Result<NonNull<u8>, ()> {
+ alloc.allocate(layout)
+ }
+
+ #[cfg(feature = "bumpalo")]
+ unsafe impl Allocator for crate::BumpWrapper<'_> {
+ #[allow(clippy::map_err_ignore)]
+ fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()> {
+ self.0.try_alloc_layout(layout).map_err(|_| ())
+ }
+ unsafe fn deallocate(&self, _ptr: NonNull<u8>, _layout: Layout) {}
+ }
+}
diff --git a/vendor/hashbrown-0.12.3/src/raw/bitmask.rs b/vendor/hashbrown-0.12.3/src/raw/bitmask.rs
new file mode 100644
index 000000000..7d4f9fc38
--- /dev/null
+++ b/vendor/hashbrown-0.12.3/src/raw/bitmask.rs
@@ -0,0 +1,122 @@
+use super::imp::{BitMaskWord, BITMASK_MASK, BITMASK_STRIDE};
+#[cfg(feature = "nightly")]
+use core::intrinsics;
+
+/// A bit mask which contains the result of a `Match` operation on a `Group` and
+/// allows iterating through them.
+///
+/// The bit mask is arranged so that low-order bits represent lower memory
+/// addresses for group match results.
+///
+/// For implementation reasons, the bits in the set may be sparsely packed, so
+/// that there is only one bit-per-byte used (the high bit, 7). If this is the
+/// case, `BITMASK_STRIDE` will be 8 to indicate a divide-by-8 should be
+/// performed on counts/indices to normalize this difference. `BITMASK_MASK` is
+/// similarly a mask of all the actually-used bits.
+#[derive(Copy, Clone)]
+pub struct BitMask(pub BitMaskWord);
+
+#[allow(clippy::use_self)]
+impl BitMask {
+ /// Returns a new `BitMask` with all bits inverted.
+ #[inline]
+ #[must_use]
+ pub fn invert(self) -> Self {
+ BitMask(self.0 ^ BITMASK_MASK)
+ }
+
+ /// Flip the bit in the mask for the entry at the given index.
+ ///
+ /// Returns the bit's previous state.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)]
+ #[cfg(feature = "raw")]
+ pub unsafe fn flip(&mut self, index: usize) -> bool {
+ // NOTE: The + BITMASK_STRIDE - 1 is to set the high bit.
+ let mask = 1 << (index * BITMASK_STRIDE + BITMASK_STRIDE - 1);
+ self.0 ^= mask;
+ // The bit was set if the bit is now 0.
+ self.0 & mask == 0
+ }
+
+ /// Returns a new `BitMask` with the lowest bit removed.
+ #[inline]
+ #[must_use]
+ pub fn remove_lowest_bit(self) -> Self {
+ BitMask(self.0 & (self.0 - 1))
+ }
+ /// Returns whether the `BitMask` has at least one set bit.
+ #[inline]
+ pub fn any_bit_set(self) -> bool {
+ self.0 != 0
+ }
+
+ /// Returns the first set bit in the `BitMask`, if there is one.
+ #[inline]
+ pub fn lowest_set_bit(self) -> Option<usize> {
+ if self.0 == 0 {
+ None
+ } else {
+ Some(unsafe { self.lowest_set_bit_nonzero() })
+ }
+ }
+
+ /// Returns the first set bit in the `BitMask`, if there is one. The
+ /// bitmask must not be empty.
+ #[inline]
+ #[cfg(feature = "nightly")]
+ pub unsafe fn lowest_set_bit_nonzero(self) -> usize {
+ intrinsics::cttz_nonzero(self.0) as usize / BITMASK_STRIDE
+ }
+ #[inline]
+ #[cfg(not(feature = "nightly"))]
+ pub unsafe fn lowest_set_bit_nonzero(self) -> usize {
+ self.trailing_zeros()
+ }
+
+ /// Returns the number of trailing zeroes in the `BitMask`.
+ #[inline]
+ pub fn trailing_zeros(self) -> usize {
+ // ARM doesn't have a trailing_zeroes instruction, and instead uses
+ // reverse_bits (RBIT) + leading_zeroes (CLZ). However older ARM
+ // versions (pre-ARMv7) don't have RBIT and need to emulate it
+ // instead. Since we only have 1 bit set in each byte on ARM, we can
+ // use swap_bytes (REV) + leading_zeroes instead.
+ if cfg!(target_arch = "arm") && BITMASK_STRIDE % 8 == 0 {
+ self.0.swap_bytes().leading_zeros() as usize / BITMASK_STRIDE
+ } else {
+ self.0.trailing_zeros() as usize / BITMASK_STRIDE
+ }
+ }
+
+ /// Returns the number of leading zeroes in the `BitMask`.
+ #[inline]
+ pub fn leading_zeros(self) -> usize {
+ self.0.leading_zeros() as usize / BITMASK_STRIDE
+ }
+}
+
+impl IntoIterator for BitMask {
+ type Item = usize;
+ type IntoIter = BitMaskIter;
+
+ #[inline]
+ fn into_iter(self) -> BitMaskIter {
+ BitMaskIter(self)
+ }
+}
+
+/// Iterator over the contents of a `BitMask`, returning the indices of set
+/// bits.
+pub struct BitMaskIter(BitMask);
+
+impl Iterator for BitMaskIter {
+ type Item = usize;
+
+ #[inline]
+ fn next(&mut self) -> Option<usize> {
+ let bit = self.0.lowest_set_bit()?;
+ self.0 = self.0.remove_lowest_bit();
+ Some(bit)
+ }
+}
diff --git a/vendor/hashbrown-0.12.3/src/raw/generic.rs b/vendor/hashbrown-0.12.3/src/raw/generic.rs
new file mode 100644
index 000000000..b4d31e62c
--- /dev/null
+++ b/vendor/hashbrown-0.12.3/src/raw/generic.rs
@@ -0,0 +1,154 @@
+use super::bitmask::BitMask;
+use super::EMPTY;
+use core::{mem, ptr};
+
+// Use the native word size as the group size. Using a 64-bit group size on
+// a 32-bit architecture will just end up being more expensive because
+// shifts and multiplies will need to be emulated.
+#[cfg(any(
+ target_pointer_width = "64",
+ target_arch = "aarch64",
+ target_arch = "x86_64",
+ target_arch = "wasm32",
+))]
+type GroupWord = u64;
+#[cfg(all(
+ target_pointer_width = "32",
+ not(target_arch = "aarch64"),
+ not(target_arch = "x86_64"),
+ not(target_arch = "wasm32"),
+))]
+type GroupWord = u32;
+
+pub type BitMaskWord = GroupWord;
+pub const BITMASK_STRIDE: usize = 8;
+// We only care about the highest bit of each byte for the mask.
+#[allow(clippy::cast_possible_truncation, clippy::unnecessary_cast)]
+pub const BITMASK_MASK: BitMaskWord = 0x8080_8080_8080_8080_u64 as GroupWord;
+
+/// Helper function to replicate a byte across a `GroupWord`.
+#[inline]
+fn repeat(byte: u8) -> GroupWord {
+ GroupWord::from_ne_bytes([byte; Group::WIDTH])
+}
+
+/// Abstraction over a group of control bytes which can be scanned in
+/// parallel.
+///
+/// This implementation uses a word-sized integer.
+#[derive(Copy, Clone)]
+pub struct Group(GroupWord);
+
+// We perform all operations in the native endianness, and convert to
+// little-endian just before creating a BitMask. The can potentially
+// enable the compiler to eliminate unnecessary byte swaps if we are
+// only checking whether a BitMask is empty.
+#[allow(clippy::use_self)]
+impl Group {
+ /// Number of bytes in the group.
+ pub const WIDTH: usize = mem::size_of::<Self>();
+
+ /// Returns a full group of empty bytes, suitable for use as the initial
+ /// value for an empty hash table.
+ ///
+ /// This is guaranteed to be aligned to the group size.
+ #[inline]
+ pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
+ #[repr(C)]
+ struct AlignedBytes {
+ _align: [Group; 0],
+ bytes: [u8; Group::WIDTH],
+ }
+ const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
+ _align: [],
+ bytes: [EMPTY; Group::WIDTH],
+ };
+ &ALIGNED_BYTES.bytes
+ }
+
+ /// Loads a group of bytes starting at the given address.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)] // unaligned load
+ pub unsafe fn load(ptr: *const u8) -> Self {
+ Group(ptr::read_unaligned(ptr.cast()))
+ }
+
+ /// Loads a group of bytes starting at the given address, which must be
+ /// aligned to `mem::align_of::<Group>()`.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)]
+ pub unsafe fn load_aligned(ptr: *const u8) -> Self {
+ // FIXME: use align_offset once it stabilizes
+ debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
+ Group(ptr::read(ptr.cast()))
+ }
+
+ /// Stores the group of bytes to the given address, which must be
+ /// aligned to `mem::align_of::<Group>()`.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)]
+ pub unsafe fn store_aligned(self, ptr: *mut u8) {
+ // FIXME: use align_offset once it stabilizes
+ debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
+ ptr::write(ptr.cast(), self.0);
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which *may*
+ /// have the given value.
+ ///
+ /// This function may return a false positive in certain cases where
+ /// the byte in the group differs from the searched value only in its
+ /// lowest bit. This is fine because:
+ /// - This never happens for `EMPTY` and `DELETED`, only full entries.
+ /// - The check for key equality will catch these.
+ /// - This only happens if there is at least 1 true match.
+ /// - The chance of this happening is very low (< 1% chance per byte).
+ #[inline]
+ pub fn match_byte(self, byte: u8) -> BitMask {
+ // This algorithm is derived from
+ // https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
+ let cmp = self.0 ^ repeat(byte);
+ BitMask((cmp.wrapping_sub(repeat(0x01)) & !cmp & repeat(0x80)).to_le())
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which are
+ /// `EMPTY`.
+ #[inline]
+ pub fn match_empty(self) -> BitMask {
+ // If the high bit is set, then the byte must be either:
+ // 1111_1111 (EMPTY) or 1000_0000 (DELETED).
+ // So we can just check if the top two bits are 1 by ANDing them.
+ BitMask((self.0 & (self.0 << 1) & repeat(0x80)).to_le())
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which are
+ /// `EMPTY` or `DELETED`.
+ #[inline]
+ pub fn match_empty_or_deleted(self) -> BitMask {
+ // A byte is EMPTY or DELETED iff the high bit is set
+ BitMask((self.0 & repeat(0x80)).to_le())
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which are full.
+ #[inline]
+ pub fn match_full(self) -> BitMask {
+ self.match_empty_or_deleted().invert()
+ }
+
+ /// Performs the following transformation on all bytes in the group:
+ /// - `EMPTY => EMPTY`
+ /// - `DELETED => EMPTY`
+ /// - `FULL => DELETED`
+ #[inline]
+ pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
+ // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
+ // and high_bit = 0 (FULL) to 1000_0000
+ //
+ // Here's this logic expanded to concrete values:
+ // let full = 1000_0000 (true) or 0000_0000 (false)
+ // !1000_0000 + 1 = 0111_1111 + 1 = 1000_0000 (no carry)
+ // !0000_0000 + 0 = 1111_1111 + 0 = 1111_1111 (no carry)
+ let full = !self.0 & repeat(0x80);
+ Group(!full + (full >> 7))
+ }
+}
diff --git a/vendor/hashbrown-0.12.3/src/raw/mod.rs b/vendor/hashbrown-0.12.3/src/raw/mod.rs
new file mode 100644
index 000000000..211b818a5
--- /dev/null
+++ b/vendor/hashbrown-0.12.3/src/raw/mod.rs
@@ -0,0 +1,2460 @@
+use crate::alloc::alloc::{handle_alloc_error, Layout};
+use crate::scopeguard::{guard, ScopeGuard};
+use crate::TryReserveError;
+use core::iter::FusedIterator;
+use core::marker::PhantomData;
+use core::mem;
+use core::mem::ManuallyDrop;
+use core::mem::MaybeUninit;
+use core::ptr::NonNull;
+use core::{hint, ptr};
+
+cfg_if! {
+ // Use the SSE2 implementation if possible: it allows us to scan 16 buckets
+ // at once instead of 8. We don't bother with AVX since it would require
+ // runtime dispatch and wouldn't gain us much anyways: the probability of
+ // finding a match drops off drastically after the first few buckets.
+ //
+ // I attempted an implementation on ARM using NEON instructions, but it
+ // turns out that most NEON instructions have multi-cycle latency, which in
+ // the end outweighs any gains over the generic implementation.
+ if #[cfg(all(
+ target_feature = "sse2",
+ any(target_arch = "x86", target_arch = "x86_64"),
+ not(miri)
+ ))] {
+ mod sse2;
+ use sse2 as imp;
+ } else {
+ #[path = "generic.rs"]
+ mod generic;
+ use generic as imp;
+ }
+}
+
+mod alloc;
+pub(crate) use self::alloc::{do_alloc, Allocator, Global};
+
+mod bitmask;
+
+use self::bitmask::{BitMask, BitMaskIter};
+use self::imp::Group;
+
+// Branch prediction hint. This is currently only available on nightly but it
+// consistently improves performance by 10-15%.
+#[cfg(feature = "nightly")]
+use core::intrinsics::{likely, unlikely};
+
+// On stable we can use #[cold] to get a equivalent effect: this attributes
+// suggests that the function is unlikely to be called
+#[cfg(not(feature = "nightly"))]
+#[inline]
+#[cold]
+fn cold() {}
+
+#[cfg(not(feature = "nightly"))]
+#[inline]
+fn likely(b: bool) -> bool {
+ if !b {
+ cold();
+ }
+ b
+}
+#[cfg(not(feature = "nightly"))]
+#[inline]
+fn unlikely(b: bool) -> bool {
+ if b {
+ cold();
+ }
+ b
+}
+
+#[inline]
+unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
+ to.offset_from(from) as usize
+}
+
+/// Whether memory allocation errors should return an error or abort.
+#[derive(Copy, Clone)]
+enum Fallibility {
+ Fallible,
+ Infallible,
+}
+
+impl Fallibility {
+ /// Error to return on capacity overflow.
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn capacity_overflow(self) -> TryReserveError {
+ match self {
+ Fallibility::Fallible => TryReserveError::CapacityOverflow,
+ Fallibility::Infallible => panic!("Hash table capacity overflow"),
+ }
+ }
+
+ /// Error to return on allocation error.
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn alloc_err(self, layout: Layout) -> TryReserveError {
+ match self {
+ Fallibility::Fallible => TryReserveError::AllocError { layout },
+ Fallibility::Infallible => handle_alloc_error(layout),
+ }
+ }
+}
+
+/// Control byte value for an empty bucket.
+const EMPTY: u8 = 0b1111_1111;
+
+/// Control byte value for a deleted bucket.
+const DELETED: u8 = 0b1000_0000;
+
+/// Checks whether a control byte represents a full bucket (top bit is clear).
+#[inline]
+fn is_full(ctrl: u8) -> bool {
+ ctrl & 0x80 == 0
+}
+
+/// Checks whether a control byte represents a special value (top bit is set).
+#[inline]
+fn is_special(ctrl: u8) -> bool {
+ ctrl & 0x80 != 0
+}
+
+/// Checks whether a special control value is EMPTY (just check 1 bit).
+#[inline]
+fn special_is_empty(ctrl: u8) -> bool {
+ debug_assert!(is_special(ctrl));
+ ctrl & 0x01 != 0
+}
+
+/// Primary hash function, used to select the initial bucket to probe from.
+#[inline]
+#[allow(clippy::cast_possible_truncation)]
+fn h1(hash: u64) -> usize {
+ // On 32-bit platforms we simply ignore the higher hash bits.
+ hash as usize
+}
+
+/// Secondary hash function, saved in the low 7 bits of the control byte.
+#[inline]
+#[allow(clippy::cast_possible_truncation)]
+fn h2(hash: u64) -> u8 {
+ // Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
+ // value, some hash functions (such as FxHash) produce a usize result
+ // instead, which means that the top 32 bits are 0 on 32-bit platforms.
+ let hash_len = usize::min(mem::size_of::<usize>(), mem::size_of::<u64>());
+ let top7 = hash >> (hash_len * 8 - 7);
+ (top7 & 0x7f) as u8 // truncation
+}
+
+/// Probe sequence based on triangular numbers, which is guaranteed (since our
+/// table size is a power of two) to visit every group of elements exactly once.
+///
+/// A triangular probe has us jump by 1 more group every time. So first we
+/// jump by 1 group (meaning we just continue our linear scan), then 2 groups
+/// (skipping over 1 group), then 3 groups (skipping over 2 groups), and so on.
+///
+/// Proof that the probe will visit every group in the table:
+/// <https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/>
+struct ProbeSeq {
+ pos: usize,
+ stride: usize,
+}
+
+impl ProbeSeq {
+ #[inline]
+ fn move_next(&mut self, bucket_mask: usize) {
+ // We should have found an empty bucket by now and ended the probe.
+ debug_assert!(
+ self.stride <= bucket_mask,
+ "Went past end of probe sequence"
+ );
+
+ self.stride += Group::WIDTH;
+ self.pos += self.stride;
+ self.pos &= bucket_mask;
+ }
+}
+
+/// Returns the number of buckets needed to hold the given number of items,
+/// taking the maximum load factor into account.
+///
+/// Returns `None` if an overflow occurs.
+// Workaround for emscripten bug emscripten-core/emscripten-fastcomp#258
+#[cfg_attr(target_os = "emscripten", inline(never))]
+#[cfg_attr(not(target_os = "emscripten"), inline)]
+fn capacity_to_buckets(cap: usize) -> Option<usize> {
+ debug_assert_ne!(cap, 0);
+
+ // For small tables we require at least 1 empty bucket so that lookups are
+ // guaranteed to terminate if an element doesn't exist in the table.
+ if cap < 8 {
+ // We don't bother with a table size of 2 buckets since that can only
+ // hold a single element. Instead we skip directly to a 4 bucket table
+ // which can hold 3 elements.
+ return Some(if cap < 4 { 4 } else { 8 });
+ }
+
+ // Otherwise require 1/8 buckets to be empty (87.5% load)
+ //
+ // Be careful when modifying this, calculate_layout relies on the
+ // overflow check here.
+ let adjusted_cap = cap.checked_mul(8)? / 7;
+
+ // Any overflows will have been caught by the checked_mul. Also, any
+ // rounding errors from the division above will be cleaned up by
+ // next_power_of_two (which can't overflow because of the previous division).
+ Some(adjusted_cap.next_power_of_two())
+}
+
+/// Returns the maximum effective capacity for the given bucket mask, taking
+/// the maximum load factor into account.
+#[inline]
+fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {
+ if bucket_mask < 8 {
+ // For tables with 1/2/4/8 buckets, we always reserve one empty slot.
+ // Keep in mind that the bucket mask is one less than the bucket count.
+ bucket_mask
+ } else {
+ // For larger tables we reserve 12.5% of the slots as empty.
+ ((bucket_mask + 1) / 8) * 7
+ }
+}
+
+/// Helper which allows the max calculation for ctrl_align to be statically computed for each T
+/// while keeping the rest of `calculate_layout_for` independent of `T`
+#[derive(Copy, Clone)]
+struct TableLayout {
+ size: usize,
+ ctrl_align: usize,
+}
+
+impl TableLayout {
+ #[inline]
+ fn new<T>() -> Self {
+ let layout = Layout::new::<T>();
+ Self {
+ size: layout.size(),
+ ctrl_align: usize::max(layout.align(), Group::WIDTH),
+ }
+ }
+
+ #[inline]
+ fn calculate_layout_for(self, buckets: usize) -> Option<(Layout, usize)> {
+ debug_assert!(buckets.is_power_of_two());
+
+ let TableLayout { size, ctrl_align } = self;
+ // Manual layout calculation since Layout methods are not yet stable.
+ let ctrl_offset =
+ size.checked_mul(buckets)?.checked_add(ctrl_align - 1)? & !(ctrl_align - 1);
+ let len = ctrl_offset.checked_add(buckets + Group::WIDTH)?;
+
+ Some((
+ unsafe { Layout::from_size_align_unchecked(len, ctrl_align) },
+ ctrl_offset,
+ ))
+ }
+}
+
+/// Returns a Layout which describes the allocation required for a hash table,
+/// and the offset of the control bytes in the allocation.
+/// (the offset is also one past last element of buckets)
+///
+/// Returns `None` if an overflow occurs.
+#[cfg_attr(feature = "inline-more", inline)]
+fn calculate_layout<T>(buckets: usize) -> Option<(Layout, usize)> {
+ TableLayout::new::<T>().calculate_layout_for(buckets)
+}
+
+/// A reference to a hash table bucket containing a `T`.
+///
+/// This is usually just a pointer to the element itself. However if the element
+/// is a ZST, then we instead track the index of the element in the table so
+/// that `erase` works properly.
+pub struct Bucket<T> {
+ // Actually it is pointer to next element than element itself
+ // this is needed to maintain pointer arithmetic invariants
+ // keeping direct pointer to element introduces difficulty.
+ // Using `NonNull` for variance and niche layout
+ ptr: NonNull<T>,
+}
+
+// This Send impl is needed for rayon support. This is safe since Bucket is
+// never exposed in a public API.
+unsafe impl<T> Send for Bucket<T> {}
+
+impl<T> Clone for Bucket<T> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Self { ptr: self.ptr }
+ }
+}
+
+impl<T> Bucket<T> {
+ #[inline]
+ unsafe fn from_base_index(base: NonNull<T>, index: usize) -> Self {
+ let ptr = if mem::size_of::<T>() == 0 {
+ // won't overflow because index must be less than length
+ (index + 1) as *mut T
+ } else {
+ base.as_ptr().sub(index)
+ };
+ Self {
+ ptr: NonNull::new_unchecked(ptr),
+ }
+ }
+ #[inline]
+ unsafe fn to_base_index(&self, base: NonNull<T>) -> usize {
+ if mem::size_of::<T>() == 0 {
+ self.ptr.as_ptr() as usize - 1
+ } else {
+ offset_from(base.as_ptr(), self.ptr.as_ptr())
+ }
+ }
+ #[inline]
+ pub fn as_ptr(&self) -> *mut T {
+ if mem::size_of::<T>() == 0 {
+ // Just return an arbitrary ZST pointer which is properly aligned
+ mem::align_of::<T>() as *mut T
+ } else {
+ unsafe { self.ptr.as_ptr().sub(1) }
+ }
+ }
+ #[inline]
+ unsafe fn next_n(&self, offset: usize) -> Self {
+ let ptr = if mem::size_of::<T>() == 0 {
+ (self.ptr.as_ptr() as usize + offset) as *mut T
+ } else {
+ self.ptr.as_ptr().sub(offset)
+ };
+ Self {
+ ptr: NonNull::new_unchecked(ptr),
+ }
+ }
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub unsafe fn drop(&self) {
+ self.as_ptr().drop_in_place();
+ }
+ #[inline]
+ pub unsafe fn read(&self) -> T {
+ self.as_ptr().read()
+ }
+ #[inline]
+ pub unsafe fn write(&self, val: T) {
+ self.as_ptr().write(val);
+ }
+ #[inline]
+ pub unsafe fn as_ref<'a>(&self) -> &'a T {
+ &*self.as_ptr()
+ }
+ #[inline]
+ pub unsafe fn as_mut<'a>(&self) -> &'a mut T {
+ &mut *self.as_ptr()
+ }
+ #[cfg(feature = "raw")]
+ #[inline]
+ pub unsafe fn copy_from_nonoverlapping(&self, other: &Self) {
+ self.as_ptr().copy_from_nonoverlapping(other.as_ptr(), 1);
+ }
+}
+
+/// A raw hash table with an unsafe API.
+pub struct RawTable<T, A: Allocator + Clone = Global> {
+ table: RawTableInner<A>,
+ // Tell dropck that we own instances of T.
+ marker: PhantomData<T>,
+}
+
+/// Non-generic part of `RawTable` which allows functions to be instantiated only once regardless
+/// of how many different key-value types are used.
+struct RawTableInner<A> {
+ // Mask to get an index from a hash value. The value is one less than the
+ // number of buckets in the table.
+ bucket_mask: usize,
+
+ // [Padding], T1, T2, ..., Tlast, C1, C2, ...
+ // ^ points here
+ ctrl: NonNull<u8>,
+
+ // Number of elements that can be inserted before we need to grow the table
+ growth_left: usize,
+
+ // Number of elements in the table, only really used by len()
+ items: usize,
+
+ alloc: A,
+}
+
+impl<T> RawTable<T, Global> {
+ /// Creates a new empty hash table without allocating any memory.
+ ///
+ /// In effect this returns a table with exactly 1 bucket. However we can
+ /// leave the data pointer dangling since that bucket is never written to
+ /// due to our load factor forcing us to always have at least 1 free bucket.
+ #[inline]
+ pub const fn new() -> Self {
+ Self {
+ table: RawTableInner::new_in(Global),
+ marker: PhantomData,
+ }
+ }
+
+ /// Attempts to allocate a new hash table with at least enough capacity
+ /// for inserting the given number of elements without reallocating.
+ #[cfg(feature = "raw")]
+ pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
+ Self::try_with_capacity_in(capacity, Global)
+ }
+
+ /// Allocates a new hash table with at least enough capacity for inserting
+ /// the given number of elements without reallocating.
+ pub fn with_capacity(capacity: usize) -> Self {
+ Self::with_capacity_in(capacity, Global)
+ }
+}
+
+impl<T, A: Allocator + Clone> RawTable<T, A> {
+ /// Creates a new empty hash table without allocating any memory, using the
+ /// given allocator.
+ ///
+ /// In effect this returns a table with exactly 1 bucket. However we can
+ /// leave the data pointer dangling since that bucket is never written to
+ /// due to our load factor forcing us to always have at least 1 free bucket.
+ #[inline]
+ pub fn new_in(alloc: A) -> Self {
+ Self {
+ table: RawTableInner::new_in(alloc),
+ marker: PhantomData,
+ }
+ }
+
+ /// Allocates a new hash table with the given number of buckets.
+ ///
+ /// The control bytes are left uninitialized.
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn new_uninitialized(
+ alloc: A,
+ buckets: usize,
+ fallibility: Fallibility,
+ ) -> Result<Self, TryReserveError> {
+ debug_assert!(buckets.is_power_of_two());
+
+ Ok(Self {
+ table: RawTableInner::new_uninitialized(
+ alloc,
+ TableLayout::new::<T>(),
+ buckets,
+ fallibility,
+ )?,
+ marker: PhantomData,
+ })
+ }
+
+ /// Attempts to allocate a new hash table with at least enough capacity
+ /// for inserting the given number of elements without reallocating.
+ fn fallible_with_capacity(
+ alloc: A,
+ capacity: usize,
+ fallibility: Fallibility,
+ ) -> Result<Self, TryReserveError> {
+ Ok(Self {
+ table: RawTableInner::fallible_with_capacity(
+ alloc,
+ TableLayout::new::<T>(),
+ capacity,
+ fallibility,
+ )?,
+ marker: PhantomData,
+ })
+ }
+
+ /// Attempts to allocate a new hash table using the given allocator, with at least enough
+ /// capacity for inserting the given number of elements without reallocating.
+ #[cfg(feature = "raw")]
+ pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
+ Self::fallible_with_capacity(alloc, capacity, Fallibility::Fallible)
+ }
+
+ /// Allocates a new hash table using the given allocator, with at least enough capacity for
+ /// inserting the given number of elements without reallocating.
+ pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
+ // Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
+ match Self::fallible_with_capacity(alloc, capacity, Fallibility::Infallible) {
+ Ok(capacity) => capacity,
+ Err(_) => unsafe { hint::unreachable_unchecked() },
+ }
+ }
+
+ /// Returns a reference to the underlying allocator.
+ #[inline]
+ pub fn allocator(&self) -> &A {
+ &self.table.alloc
+ }
+
+ /// Deallocates the table without dropping any entries.
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn free_buckets(&mut self) {
+ self.table.free_buckets(TableLayout::new::<T>());
+ }
+
+ /// Returns pointer to one past last element of data table.
+ #[inline]
+ pub unsafe fn data_end(&self) -> NonNull<T> {
+ NonNull::new_unchecked(self.table.ctrl.as_ptr().cast())
+ }
+
+ /// Returns pointer to start of data table.
+ #[inline]
+ #[cfg(feature = "nightly")]
+ pub unsafe fn data_start(&self) -> *mut T {
+ self.data_end().as_ptr().wrapping_sub(self.buckets())
+ }
+
+ /// Returns the index of a bucket from a `Bucket`.
+ #[inline]
+ pub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize {
+ bucket.to_base_index(self.data_end())
+ }
+
+ /// Returns a pointer to an element in the table.
+ #[inline]
+ pub unsafe fn bucket(&self, index: usize) -> Bucket<T> {
+ debug_assert_ne!(self.table.bucket_mask, 0);
+ debug_assert!(index < self.buckets());
+ Bucket::from_base_index(self.data_end(), index)
+ }
+
+ /// Erases an element from the table without dropping it.
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[deprecated(since = "0.8.1", note = "use erase or remove instead")]
+ pub unsafe fn erase_no_drop(&mut self, item: &Bucket<T>) {
+ let index = self.bucket_index(item);
+ self.table.erase(index);
+ }
+
+ /// Erases an element from the table, dropping it in place.
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[allow(clippy::needless_pass_by_value)]
+ #[allow(deprecated)]
+ pub unsafe fn erase(&mut self, item: Bucket<T>) {
+ // Erase the element from the table first since drop might panic.
+ self.erase_no_drop(&item);
+ item.drop();
+ }
+
+ /// Finds and erases an element from the table, dropping it in place.
+ /// Returns true if an element was found.
+ #[cfg(feature = "raw")]
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn erase_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> bool {
+ // Avoid `Option::map` because it bloats LLVM IR.
+ if let Some(bucket) = self.find(hash, eq) {
+ unsafe {
+ self.erase(bucket);
+ }
+ true
+ } else {
+ false
+ }
+ }
+
+ /// Removes an element from the table, returning it.
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[allow(clippy::needless_pass_by_value)]
+ #[allow(deprecated)]
+ pub unsafe fn remove(&mut self, item: Bucket<T>) -> T {
+ self.erase_no_drop(&item);
+ item.read()
+ }
+
+ /// Finds and removes an element from the table, returning it.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn remove_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<T> {
+ // Avoid `Option::map` because it bloats LLVM IR.
+ match self.find(hash, eq) {
+ Some(bucket) => Some(unsafe { self.remove(bucket) }),
+ None => None,
+ }
+ }
+
+ /// Marks all table buckets as empty without dropping their contents.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn clear_no_drop(&mut self) {
+ self.table.clear_no_drop();
+ }
+
+ /// Removes all elements from the table without freeing the backing memory.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn clear(&mut self) {
+ // Ensure that the table is reset even if one of the drops panic
+ let mut self_ = guard(self, |self_| self_.clear_no_drop());
+ unsafe {
+ self_.drop_elements();
+ }
+ }
+
+ unsafe fn drop_elements(&mut self) {
+ if mem::needs_drop::<T>() && !self.is_empty() {
+ for item in self.iter() {
+ item.drop();
+ }
+ }
+ }
+
+ /// Shrinks the table to fit `max(self.len(), min_size)` elements.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn shrink_to(&mut self, min_size: usize, hasher: impl Fn(&T) -> u64) {
+ // Calculate the minimal number of elements that we need to reserve
+ // space for.
+ let min_size = usize::max(self.table.items, min_size);
+ if min_size == 0 {
+ *self = Self::new_in(self.table.alloc.clone());
+ return;
+ }
+
+ // Calculate the number of buckets that we need for this number of
+ // elements. If the calculation overflows then the requested bucket
+ // count must be larger than what we have right and nothing needs to be
+ // done.
+ let min_buckets = match capacity_to_buckets(min_size) {
+ Some(buckets) => buckets,
+ None => return,
+ };
+
+ // If we have more buckets than we need, shrink the table.
+ if min_buckets < self.buckets() {
+ // Fast path if the table is empty
+ if self.table.items == 0 {
+ *self = Self::with_capacity_in(min_size, self.table.alloc.clone());
+ } else {
+ // Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
+ if self
+ .resize(min_size, hasher, Fallibility::Infallible)
+ .is_err()
+ {
+ unsafe { hint::unreachable_unchecked() }
+ }
+ }
+ }
+ }
+
+ /// Ensures that at least `additional` items can be inserted into the table
+ /// without reallocation.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64) {
+ if additional > self.table.growth_left {
+ // Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
+ if self
+ .reserve_rehash(additional, hasher, Fallibility::Infallible)
+ .is_err()
+ {
+ unsafe { hint::unreachable_unchecked() }
+ }
+ }
+ }
+
+ /// Tries to ensure that at least `additional` items can be inserted into
+ /// the table without reallocation.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn try_reserve(
+ &mut self,
+ additional: usize,
+ hasher: impl Fn(&T) -> u64,
+ ) -> Result<(), TryReserveError> {
+ if additional > self.table.growth_left {
+ self.reserve_rehash(additional, hasher, Fallibility::Fallible)
+ } else {
+ Ok(())
+ }
+ }
+
+ /// Out-of-line slow path for `reserve` and `try_reserve`.
+ #[cold]
+ #[inline(never)]
+ fn reserve_rehash(
+ &mut self,
+ additional: usize,
+ hasher: impl Fn(&T) -> u64,
+ fallibility: Fallibility,
+ ) -> Result<(), TryReserveError> {
+ unsafe {
+ self.table.reserve_rehash_inner(
+ additional,
+ &|table, index| hasher(table.bucket::<T>(index).as_ref()),
+ fallibility,
+ TableLayout::new::<T>(),
+ if mem::needs_drop::<T>() {
+ Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T)))
+ } else {
+ None
+ },
+ )
+ }
+ }
+
+ /// Allocates a new table of a different size and moves the contents of the
+ /// current table into it.
+ fn resize(
+ &mut self,
+ capacity: usize,
+ hasher: impl Fn(&T) -> u64,
+ fallibility: Fallibility,
+ ) -> Result<(), TryReserveError> {
+ unsafe {
+ self.table.resize_inner(
+ capacity,
+ &|table, index| hasher(table.bucket::<T>(index).as_ref()),
+ fallibility,
+ TableLayout::new::<T>(),
+ )
+ }
+ }
+
+ /// Inserts a new element into the table, and returns its raw bucket.
+ ///
+ /// This does not check if the given element already exists in the table.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn insert(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> Bucket<T> {
+ unsafe {
+ let mut index = self.table.find_insert_slot(hash);
+
+ // We can avoid growing the table once we have reached our load
+ // factor if we are replacing a tombstone. This works since the
+ // number of EMPTY slots does not change in this case.
+ let old_ctrl = *self.table.ctrl(index);
+ if unlikely(self.table.growth_left == 0 && special_is_empty(old_ctrl)) {
+ self.reserve(1, hasher);
+ index = self.table.find_insert_slot(hash);
+ }
+
+ self.table.record_item_insert_at(index, old_ctrl, hash);
+
+ let bucket = self.bucket(index);
+ bucket.write(value);
+ bucket
+ }
+ }
+
+ /// Attempts to insert a new element without growing the table and return its raw bucket.
+ ///
+ /// Returns an `Err` containing the given element if inserting it would require growing the
+ /// table.
+ ///
+ /// This does not check if the given element already exists in the table.
+ #[cfg(feature = "raw")]
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn try_insert_no_grow(&mut self, hash: u64, value: T) -> Result<Bucket<T>, T> {
+ unsafe {
+ match self.table.prepare_insert_no_grow(hash) {
+ Ok(index) => {
+ let bucket = self.bucket(index);
+ bucket.write(value);
+ Ok(bucket)
+ }
+ Err(()) => Err(value),
+ }
+ }
+ }
+
+ /// Inserts a new element into the table, and returns a mutable reference to it.
+ ///
+ /// This does not check if the given element already exists in the table.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn insert_entry(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> &mut T {
+ unsafe { self.insert(hash, value, hasher).as_mut() }
+ }
+
+ /// Inserts a new element into the table, without growing the table.
+ ///
+ /// There must be enough space in the table to insert the new element.
+ ///
+ /// This does not check if the given element already exists in the table.
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[cfg(any(feature = "raw", feature = "rustc-internal-api"))]
+ pub unsafe fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> {
+ let (index, old_ctrl) = self.table.prepare_insert_slot(hash);
+ let bucket = self.table.bucket(index);
+
+ // If we are replacing a DELETED entry then we don't need to update
+ // the load counter.
+ self.table.growth_left -= special_is_empty(old_ctrl) as usize;
+
+ bucket.write(value);
+ self.table.items += 1;
+ bucket
+ }
+
+ /// Temporary removes a bucket, applying the given function to the removed
+ /// element and optionally put back the returned value in the same bucket.
+ ///
+ /// Returns `true` if the bucket still contains an element
+ ///
+ /// This does not check if the given bucket is actually occupied.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub unsafe fn replace_bucket_with<F>(&mut self, bucket: Bucket<T>, f: F) -> bool
+ where
+ F: FnOnce(T) -> Option<T>,
+ {
+ let index = self.bucket_index(&bucket);
+ let old_ctrl = *self.table.ctrl(index);
+ debug_assert!(is_full(old_ctrl));
+ let old_growth_left = self.table.growth_left;
+ let item = self.remove(bucket);
+ if let Some(new_item) = f(item) {
+ self.table.growth_left = old_growth_left;
+ self.table.set_ctrl(index, old_ctrl);
+ self.table.items += 1;
+ self.bucket(index).write(new_item);
+ true
+ } else {
+ false
+ }
+ }
+
+ /// Searches for an element in the table.
+ #[inline]
+ pub fn find(&self, hash: u64, mut eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
+ let result = self.table.find_inner(hash, &mut |index| unsafe {
+ eq(self.bucket(index).as_ref())
+ });
+
+ // Avoid `Option::map` because it bloats LLVM IR.
+ match result {
+ Some(index) => Some(unsafe { self.bucket(index) }),
+ None => None,
+ }
+ }
+
+ /// Gets a reference to an element in the table.
+ #[inline]
+ pub fn get(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T> {
+ // Avoid `Option::map` because it bloats LLVM IR.
+ match self.find(hash, eq) {
+ Some(bucket) => Some(unsafe { bucket.as_ref() }),
+ None => None,
+ }
+ }
+
+ /// Gets a mutable reference to an element in the table.
+ #[inline]
+ pub fn get_mut(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&mut T> {
+ // Avoid `Option::map` because it bloats LLVM IR.
+ match self.find(hash, eq) {
+ Some(bucket) => Some(unsafe { bucket.as_mut() }),
+ None => None,
+ }
+ }
+
+ /// Attempts to get mutable references to `N` entries in the table at once.
+ ///
+ /// Returns an array of length `N` with the results of each query.
+ ///
+ /// At most one mutable reference will be returned to any entry. `None` will be returned if any
+ /// of the hashes are duplicates. `None` will be returned if the hash is not found.
+ ///
+ /// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to
+ /// the `i`th key to be looked up.
+ pub fn get_many_mut<const N: usize>(
+ &mut self,
+ hashes: [u64; N],
+ eq: impl FnMut(usize, &T) -> bool,
+ ) -> Option<[&'_ mut T; N]> {
+ unsafe {
+ let ptrs = self.get_many_mut_pointers(hashes, eq)?;
+
+ for (i, &cur) in ptrs.iter().enumerate() {
+ if ptrs[..i].iter().any(|&prev| ptr::eq::<T>(prev, cur)) {
+ return None;
+ }
+ }
+ // All bucket are distinct from all previous buckets so we're clear to return the result
+ // of the lookup.
+
+ // TODO use `MaybeUninit::array_assume_init` here instead once that's stable.
+ Some(mem::transmute_copy(&ptrs))
+ }
+ }
+
+ pub unsafe fn get_many_unchecked_mut<const N: usize>(
+ &mut self,
+ hashes: [u64; N],
+ eq: impl FnMut(usize, &T) -> bool,
+ ) -> Option<[&'_ mut T; N]> {
+ let ptrs = self.get_many_mut_pointers(hashes, eq)?;
+ Some(mem::transmute_copy(&ptrs))
+ }
+
+ unsafe fn get_many_mut_pointers<const N: usize>(
+ &mut self,
+ hashes: [u64; N],
+ mut eq: impl FnMut(usize, &T) -> bool,
+ ) -> Option<[*mut T; N]> {
+ // TODO use `MaybeUninit::uninit_array` here instead once that's stable.
+ let mut outs: MaybeUninit<[*mut T; N]> = MaybeUninit::uninit();
+ let outs_ptr = outs.as_mut_ptr();
+
+ for (i, &hash) in hashes.iter().enumerate() {
+ let cur = self.find(hash, |k| eq(i, k))?;
+ *(*outs_ptr).get_unchecked_mut(i) = cur.as_mut();
+ }
+
+ // TODO use `MaybeUninit::array_assume_init` here instead once that's stable.
+ Some(outs.assume_init())
+ }
+
+ /// Returns the number of elements the map can hold without reallocating.
+ ///
+ /// This number is a lower bound; the table might be able to hold
+ /// more, but is guaranteed to be able to hold at least this many.
+ #[inline]
+ pub fn capacity(&self) -> usize {
+ self.table.items + self.table.growth_left
+ }
+
+ /// Returns the number of elements in the table.
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.table.items
+ }
+
+ /// Returns `true` if the table contains no elements.
+ #[inline]
+ pub fn is_empty(&self) -> bool {
+ self.len() == 0
+ }
+
+ /// Returns the number of buckets in the table.
+ #[inline]
+ pub fn buckets(&self) -> usize {
+ self.table.bucket_mask + 1
+ }
+
+ /// Returns an iterator over every element in the table. It is up to
+ /// the caller to ensure that the `RawTable` outlives the `RawIter`.
+ /// Because we cannot make the `next` method unsafe on the `RawIter`
+ /// struct, we have to make the `iter` method unsafe.
+ #[inline]
+ pub unsafe fn iter(&self) -> RawIter<T> {
+ let data = Bucket::from_base_index(self.data_end(), 0);
+ RawIter {
+ iter: RawIterRange::new(self.table.ctrl.as_ptr(), data, self.table.buckets()),
+ items: self.table.items,
+ }
+ }
+
+ /// Returns an iterator over occupied buckets that could match a given hash.
+ ///
+ /// `RawTable` only stores 7 bits of the hash value, so this iterator may
+ /// return items that have a hash value different than the one provided. You
+ /// should always validate the returned values before using them.
+ ///
+ /// It is up to the caller to ensure that the `RawTable` outlives the
+ /// `RawIterHash`. Because we cannot make the `next` method unsafe on the
+ /// `RawIterHash` struct, we have to make the `iter_hash` method unsafe.
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[cfg(feature = "raw")]
+ pub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<'_, T, A> {
+ RawIterHash::new(self, hash)
+ }
+
+ /// Returns an iterator which removes all elements from the table without
+ /// freeing the memory.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn drain(&mut self) -> RawDrain<'_, T, A> {
+ unsafe {
+ let iter = self.iter();
+ self.drain_iter_from(iter)
+ }
+ }
+
+ /// Returns an iterator which removes all elements from the table without
+ /// freeing the memory.
+ ///
+ /// Iteration starts at the provided iterator's current location.
+ ///
+ /// It is up to the caller to ensure that the iterator is valid for this
+ /// `RawTable` and covers all items that remain in the table.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub unsafe fn drain_iter_from(&mut self, iter: RawIter<T>) -> RawDrain<'_, T, A> {
+ debug_assert_eq!(iter.len(), self.len());
+ RawDrain {
+ iter,
+ table: ManuallyDrop::new(mem::replace(self, Self::new_in(self.table.alloc.clone()))),
+ orig_table: NonNull::from(self),
+ marker: PhantomData,
+ }
+ }
+
+ /// Returns an iterator which consumes all elements from the table.
+ ///
+ /// Iteration starts at the provided iterator's current location.
+ ///
+ /// It is up to the caller to ensure that the iterator is valid for this
+ /// `RawTable` and covers all items that remain in the table.
+ pub unsafe fn into_iter_from(self, iter: RawIter<T>) -> RawIntoIter<T, A> {
+ debug_assert_eq!(iter.len(), self.len());
+
+ let alloc = self.table.alloc.clone();
+ let allocation = self.into_allocation();
+ RawIntoIter {
+ iter,
+ allocation,
+ marker: PhantomData,
+ alloc,
+ }
+ }
+
+ /// Converts the table into a raw allocation. The contents of the table
+ /// should be dropped using a `RawIter` before freeing the allocation.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub(crate) fn into_allocation(self) -> Option<(NonNull<u8>, Layout)> {
+ let alloc = if self.table.is_empty_singleton() {
+ None
+ } else {
+ // Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
+ let (layout, ctrl_offset) = match calculate_layout::<T>(self.table.buckets()) {
+ Some(lco) => lco,
+ None => unsafe { hint::unreachable_unchecked() },
+ };
+ Some((
+ unsafe { NonNull::new_unchecked(self.table.ctrl.as_ptr().sub(ctrl_offset)) },
+ layout,
+ ))
+ };
+ mem::forget(self);
+ alloc
+ }
+}
+
+unsafe impl<T, A: Allocator + Clone> Send for RawTable<T, A>
+where
+ T: Send,
+ A: Send,
+{
+}
+unsafe impl<T, A: Allocator + Clone> Sync for RawTable<T, A>
+where
+ T: Sync,
+ A: Sync,
+{
+}
+
+impl<A> RawTableInner<A> {
+ #[inline]
+ const fn new_in(alloc: A) -> Self {
+ Self {
+ // Be careful to cast the entire slice to a raw pointer.
+ ctrl: unsafe { NonNull::new_unchecked(Group::static_empty() as *const _ as *mut u8) },
+ bucket_mask: 0,
+ items: 0,
+ growth_left: 0,
+ alloc,
+ }
+ }
+}
+
+impl<A: Allocator + Clone> RawTableInner<A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn new_uninitialized(
+ alloc: A,
+ table_layout: TableLayout,
+ buckets: usize,
+ fallibility: Fallibility,
+ ) -> Result<Self, TryReserveError> {
+ debug_assert!(buckets.is_power_of_two());
+
+ // Avoid `Option::ok_or_else` because it bloats LLVM IR.
+ let (layout, ctrl_offset) = match table_layout.calculate_layout_for(buckets) {
+ Some(lco) => lco,
+ None => return Err(fallibility.capacity_overflow()),
+ };
+
+ // We need an additional check to ensure that the allocation doesn't
+ // exceed `isize::MAX`. We can skip this check on 64-bit systems since
+ // such allocations will never succeed anyways.
+ //
+ // This mirrors what Vec does in the standard library.
+ if mem::size_of::<usize>() < 8 && layout.size() > isize::MAX as usize {
+ return Err(fallibility.capacity_overflow());
+ }
+
+ let ptr: NonNull<u8> = match do_alloc(&alloc, layout) {
+ Ok(block) => block.cast(),
+ Err(_) => return Err(fallibility.alloc_err(layout)),
+ };
+
+ let ctrl = NonNull::new_unchecked(ptr.as_ptr().add(ctrl_offset));
+ Ok(Self {
+ ctrl,
+ bucket_mask: buckets - 1,
+ items: 0,
+ growth_left: bucket_mask_to_capacity(buckets - 1),
+ alloc,
+ })
+ }
+
+ #[inline]
+ fn fallible_with_capacity(
+ alloc: A,
+ table_layout: TableLayout,
+ capacity: usize,
+ fallibility: Fallibility,
+ ) -> Result<Self, TryReserveError> {
+ if capacity == 0 {
+ Ok(Self::new_in(alloc))
+ } else {
+ unsafe {
+ let buckets =
+ capacity_to_buckets(capacity).ok_or_else(|| fallibility.capacity_overflow())?;
+
+ let result = Self::new_uninitialized(alloc, table_layout, buckets, fallibility)?;
+ result.ctrl(0).write_bytes(EMPTY, result.num_ctrl_bytes());
+
+ Ok(result)
+ }
+ }
+ }
+
+ /// Searches for an empty or deleted bucket which is suitable for inserting
+ /// a new element and sets the hash for that slot.
+ ///
+ /// There must be at least 1 empty bucket in the table.
+ #[inline]
+ unsafe fn prepare_insert_slot(&self, hash: u64) -> (usize, u8) {
+ let index = self.find_insert_slot(hash);
+ let old_ctrl = *self.ctrl(index);
+ self.set_ctrl_h2(index, hash);
+ (index, old_ctrl)
+ }
+
+ /// Searches for an empty or deleted bucket which is suitable for inserting
+ /// a new element.
+ ///
+ /// There must be at least 1 empty bucket in the table.
+ #[inline]
+ fn find_insert_slot(&self, hash: u64) -> usize {
+ let mut probe_seq = self.probe_seq(hash);
+ loop {
+ unsafe {
+ let group = Group::load(self.ctrl(probe_seq.pos));
+ if let Some(bit) = group.match_empty_or_deleted().lowest_set_bit() {
+ let result = (probe_seq.pos + bit) & self.bucket_mask;
+
+ // In tables smaller than the group width, trailing control
+ // bytes outside the range of the table are filled with
+ // EMPTY entries. These will unfortunately trigger a
+ // match, but once masked may point to a full bucket that
+ // is already occupied. We detect this situation here and
+ // perform a second scan starting at the beginning of the
+ // table. This second scan is guaranteed to find an empty
+ // slot (due to the load factor) before hitting the trailing
+ // control bytes (containing EMPTY).
+ if unlikely(is_full(*self.ctrl(result))) {
+ debug_assert!(self.bucket_mask < Group::WIDTH);
+ debug_assert_ne!(probe_seq.pos, 0);
+ return Group::load_aligned(self.ctrl(0))
+ .match_empty_or_deleted()
+ .lowest_set_bit_nonzero();
+ }
+
+ return result;
+ }
+ }
+ probe_seq.move_next(self.bucket_mask);
+ }
+ }
+
+ /// Searches for an element in the table. This uses dynamic dispatch to reduce the amount of
+ /// code generated, but it is eliminated by LLVM optimizations.
+ #[inline]
+ fn find_inner(&self, hash: u64, eq: &mut dyn FnMut(usize) -> bool) -> Option<usize> {
+ let h2_hash = h2(hash);
+ let mut probe_seq = self.probe_seq(hash);
+
+ loop {
+ let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };
+
+ for bit in group.match_byte(h2_hash) {
+ let index = (probe_seq.pos + bit) & self.bucket_mask;
+
+ if likely(eq(index)) {
+ return Some(index);
+ }
+ }
+
+ if likely(group.match_empty().any_bit_set()) {
+ return None;
+ }
+
+ probe_seq.move_next(self.bucket_mask);
+ }
+ }
+
+ #[allow(clippy::mut_mut)]
+ #[inline]
+ unsafe fn prepare_rehash_in_place(&mut self) {
+ // Bulk convert all full control bytes to DELETED, and all DELETED
+ // control bytes to EMPTY. This effectively frees up all buckets
+ // containing a DELETED entry.
+ for i in (0..self.buckets()).step_by(Group::WIDTH) {
+ let group = Group::load_aligned(self.ctrl(i));
+ let group = group.convert_special_to_empty_and_full_to_deleted();
+ group.store_aligned(self.ctrl(i));
+ }
+
+ // Fix up the trailing control bytes. See the comments in set_ctrl
+ // for the handling of tables smaller than the group width.
+ if self.buckets() < Group::WIDTH {
+ self.ctrl(0)
+ .copy_to(self.ctrl(Group::WIDTH), self.buckets());
+ } else {
+ self.ctrl(0)
+ .copy_to(self.ctrl(self.buckets()), Group::WIDTH);
+ }
+ }
+
+ #[inline]
+ unsafe fn bucket<T>(&self, index: usize) -> Bucket<T> {
+ debug_assert_ne!(self.bucket_mask, 0);
+ debug_assert!(index < self.buckets());
+ Bucket::from_base_index(self.data_end(), index)
+ }
+
+ #[inline]
+ unsafe fn bucket_ptr(&self, index: usize, size_of: usize) -> *mut u8 {
+ debug_assert_ne!(self.bucket_mask, 0);
+ debug_assert!(index < self.buckets());
+ let base: *mut u8 = self.data_end().as_ptr();
+ base.sub((index + 1) * size_of)
+ }
+
+ #[inline]
+ unsafe fn data_end<T>(&self) -> NonNull<T> {
+ NonNull::new_unchecked(self.ctrl.as_ptr().cast())
+ }
+
+ /// Returns an iterator-like object for a probe sequence on the table.
+ ///
+ /// This iterator never terminates, but is guaranteed to visit each bucket
+ /// group exactly once. The loop using `probe_seq` must terminate upon
+ /// reaching a group containing an empty bucket.
+ #[inline]
+ fn probe_seq(&self, hash: u64) -> ProbeSeq {
+ ProbeSeq {
+ pos: h1(hash) & self.bucket_mask,
+ stride: 0,
+ }
+ }
+
+ /// Returns the index of a bucket for which a value must be inserted if there is enough rooom
+ /// in the table, otherwise returns error
+ #[cfg(feature = "raw")]
+ #[inline]
+ unsafe fn prepare_insert_no_grow(&mut self, hash: u64) -> Result<usize, ()> {
+ let index = self.find_insert_slot(hash);
+ let old_ctrl = *self.ctrl(index);
+ if unlikely(self.growth_left == 0 && special_is_empty(old_ctrl)) {
+ Err(())
+ } else {
+ self.record_item_insert_at(index, old_ctrl, hash);
+ Ok(index)
+ }
+ }
+
+ #[inline]
+ unsafe fn record_item_insert_at(&mut self, index: usize, old_ctrl: u8, hash: u64) {
+ self.growth_left -= usize::from(special_is_empty(old_ctrl));
+ self.set_ctrl_h2(index, hash);
+ self.items += 1;
+ }
+
+ #[inline]
+ fn is_in_same_group(&self, i: usize, new_i: usize, hash: u64) -> bool {
+ let probe_seq_pos = self.probe_seq(hash).pos;
+ let probe_index =
+ |pos: usize| (pos.wrapping_sub(probe_seq_pos) & self.bucket_mask) / Group::WIDTH;
+ probe_index(i) == probe_index(new_i)
+ }
+
+ /// Sets a control byte to the hash, and possibly also the replicated control byte at
+ /// the end of the array.
+ #[inline]
+ unsafe fn set_ctrl_h2(&self, index: usize, hash: u64) {
+ self.set_ctrl(index, h2(hash));
+ }
+
+ #[inline]
+ unsafe fn replace_ctrl_h2(&self, index: usize, hash: u64) -> u8 {
+ let prev_ctrl = *self.ctrl(index);
+ self.set_ctrl_h2(index, hash);
+ prev_ctrl
+ }
+
+ /// Sets a control byte, and possibly also the replicated control byte at
+ /// the end of the array.
+ #[inline]
+ unsafe fn set_ctrl(&self, index: usize, ctrl: u8) {
+ // Replicate the first Group::WIDTH control bytes at the end of
+ // the array without using a branch:
+ // - If index >= Group::WIDTH then index == index2.
+ // - Otherwise index2 == self.bucket_mask + 1 + index.
+ //
+ // The very last replicated control byte is never actually read because
+ // we mask the initial index for unaligned loads, but we write it
+ // anyways because it makes the set_ctrl implementation simpler.
+ //
+ // If there are fewer buckets than Group::WIDTH then this code will
+ // replicate the buckets at the end of the trailing group. For example
+ // with 2 buckets and a group size of 4, the control bytes will look
+ // like this:
+ //
+ // Real | Replicated
+ // ---------------------------------------------
+ // | [A] | [B] | [EMPTY] | [EMPTY] | [A] | [B] |
+ // ---------------------------------------------
+ let index2 = ((index.wrapping_sub(Group::WIDTH)) & self.bucket_mask) + Group::WIDTH;
+
+ *self.ctrl(index) = ctrl;
+ *self.ctrl(index2) = ctrl;
+ }
+
+ /// Returns a pointer to a control byte.
+ #[inline]
+ unsafe fn ctrl(&self, index: usize) -> *mut u8 {
+ debug_assert!(index < self.num_ctrl_bytes());
+ self.ctrl.as_ptr().add(index)
+ }
+
+ #[inline]
+ fn buckets(&self) -> usize {
+ self.bucket_mask + 1
+ }
+
+ #[inline]
+ fn num_ctrl_bytes(&self) -> usize {
+ self.bucket_mask + 1 + Group::WIDTH
+ }
+
+ #[inline]
+ fn is_empty_singleton(&self) -> bool {
+ self.bucket_mask == 0
+ }
+
+ #[allow(clippy::mut_mut)]
+ #[inline]
+ unsafe fn prepare_resize(
+ &self,
+ table_layout: TableLayout,
+ capacity: usize,
+ fallibility: Fallibility,
+ ) -> Result<crate::scopeguard::ScopeGuard<Self, impl FnMut(&mut Self)>, TryReserveError> {
+ debug_assert!(self.items <= capacity);
+
+ // Allocate and initialize the new table.
+ let mut new_table = RawTableInner::fallible_with_capacity(
+ self.alloc.clone(),
+ table_layout,
+ capacity,
+ fallibility,
+ )?;
+ new_table.growth_left -= self.items;
+ new_table.items = self.items;
+
+ // The hash function may panic, in which case we simply free the new
+ // table without dropping any elements that may have been copied into
+ // it.
+ //
+ // This guard is also used to free the old table on success, see
+ // the comment at the bottom of this function.
+ Ok(guard(new_table, move |self_| {
+ if !self_.is_empty_singleton() {
+ self_.free_buckets(table_layout);
+ }
+ }))
+ }
+
+ /// Reserves or rehashes to make room for `additional` more elements.
+ ///
+ /// This uses dynamic dispatch to reduce the amount of
+ /// code generated, but it is eliminated by LLVM optimizations when inlined.
+ #[allow(clippy::inline_always)]
+ #[inline(always)]
+ unsafe fn reserve_rehash_inner(
+ &mut self,
+ additional: usize,
+ hasher: &dyn Fn(&mut Self, usize) -> u64,
+ fallibility: Fallibility,
+ layout: TableLayout,
+ drop: Option<fn(*mut u8)>,
+ ) -> Result<(), TryReserveError> {
+ // Avoid `Option::ok_or_else` because it bloats LLVM IR.
+ let new_items = match self.items.checked_add(additional) {
+ Some(new_items) => new_items,
+ None => return Err(fallibility.capacity_overflow()),
+ };
+ let full_capacity = bucket_mask_to_capacity(self.bucket_mask);
+ if new_items <= full_capacity / 2 {
+ // Rehash in-place without re-allocating if we have plenty of spare
+ // capacity that is locked up due to DELETED entries.
+ self.rehash_in_place(hasher, layout.size, drop);
+ Ok(())
+ } else {
+ // Otherwise, conservatively resize to at least the next size up
+ // to avoid churning deletes into frequent rehashes.
+ self.resize_inner(
+ usize::max(new_items, full_capacity + 1),
+ hasher,
+ fallibility,
+ layout,
+ )
+ }
+ }
+
+ /// Allocates a new table of a different size and moves the contents of the
+ /// current table into it.
+ ///
+ /// This uses dynamic dispatch to reduce the amount of
+ /// code generated, but it is eliminated by LLVM optimizations when inlined.
+ #[allow(clippy::inline_always)]
+ #[inline(always)]
+ unsafe fn resize_inner(
+ &mut self,
+ capacity: usize,
+ hasher: &dyn Fn(&mut Self, usize) -> u64,
+ fallibility: Fallibility,
+ layout: TableLayout,
+ ) -> Result<(), TryReserveError> {
+ let mut new_table = self.prepare_resize(layout, capacity, fallibility)?;
+
+ // Copy all elements to the new table.
+ for i in 0..self.buckets() {
+ if !is_full(*self.ctrl(i)) {
+ continue;
+ }
+
+ // This may panic.
+ let hash = hasher(self, i);
+
+ // We can use a simpler version of insert() here since:
+ // - there are no DELETED entries.
+ // - we know there is enough space in the table.
+ // - all elements are unique.
+ let (index, _) = new_table.prepare_insert_slot(hash);
+
+ ptr::copy_nonoverlapping(
+ self.bucket_ptr(i, layout.size),
+ new_table.bucket_ptr(index, layout.size),
+ layout.size,
+ );
+ }
+
+ // We successfully copied all elements without panicking. Now replace
+ // self with the new table. The old table will have its memory freed but
+ // the items will not be dropped (since they have been moved into the
+ // new table).
+ mem::swap(self, &mut new_table);
+
+ Ok(())
+ }
+
+ /// Rehashes the contents of the table in place (i.e. without changing the
+ /// allocation).
+ ///
+ /// If `hasher` panics then some the table's contents may be lost.
+ ///
+ /// This uses dynamic dispatch to reduce the amount of
+ /// code generated, but it is eliminated by LLVM optimizations when inlined.
+ #[allow(clippy::inline_always)]
+ #[cfg_attr(feature = "inline-more", inline(always))]
+ #[cfg_attr(not(feature = "inline-more"), inline)]
+ unsafe fn rehash_in_place(
+ &mut self,
+ hasher: &dyn Fn(&mut Self, usize) -> u64,
+ size_of: usize,
+ drop: Option<fn(*mut u8)>,
+ ) {
+ // If the hash function panics then properly clean up any elements
+ // that we haven't rehashed yet. We unfortunately can't preserve the
+ // element since we lost their hash and have no way of recovering it
+ // without risking another panic.
+ self.prepare_rehash_in_place();
+
+ let mut guard = guard(self, move |self_| {
+ if let Some(drop) = drop {
+ for i in 0..self_.buckets() {
+ if *self_.ctrl(i) == DELETED {
+ self_.set_ctrl(i, EMPTY);
+ drop(self_.bucket_ptr(i, size_of));
+ self_.items -= 1;
+ }
+ }
+ }
+ self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items;
+ });
+
+ // At this point, DELETED elements are elements that we haven't
+ // rehashed yet. Find them and re-insert them at their ideal
+ // position.
+ 'outer: for i in 0..guard.buckets() {
+ if *guard.ctrl(i) != DELETED {
+ continue;
+ }
+
+ let i_p = guard.bucket_ptr(i, size_of);
+
+ 'inner: loop {
+ // Hash the current item
+ let hash = hasher(*guard, i);
+
+ // Search for a suitable place to put it
+ let new_i = guard.find_insert_slot(hash);
+ let new_i_p = guard.bucket_ptr(new_i, size_of);
+
+ // Probing works by scanning through all of the control
+ // bytes in groups, which may not be aligned to the group
+ // size. If both the new and old position fall within the
+ // same unaligned group, then there is no benefit in moving
+ // it and we can just continue to the next item.
+ if likely(guard.is_in_same_group(i, new_i, hash)) {
+ guard.set_ctrl_h2(i, hash);
+ continue 'outer;
+ }
+
+ // We are moving the current item to a new position. Write
+ // our H2 to the control byte of the new position.
+ let prev_ctrl = guard.replace_ctrl_h2(new_i, hash);
+ if prev_ctrl == EMPTY {
+ guard.set_ctrl(i, EMPTY);
+ // If the target slot is empty, simply move the current
+ // element into the new slot and clear the old control
+ // byte.
+ ptr::copy_nonoverlapping(i_p, new_i_p, size_of);
+ continue 'outer;
+ } else {
+ // If the target slot is occupied, swap the two elements
+ // and then continue processing the element that we just
+ // swapped into the old slot.
+ debug_assert_eq!(prev_ctrl, DELETED);
+ ptr::swap_nonoverlapping(i_p, new_i_p, size_of);
+ continue 'inner;
+ }
+ }
+ }
+
+ guard.growth_left = bucket_mask_to_capacity(guard.bucket_mask) - guard.items;
+
+ mem::forget(guard);
+ }
+
+ #[inline]
+ unsafe fn free_buckets(&mut self, table_layout: TableLayout) {
+ // Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
+ let (layout, ctrl_offset) = match table_layout.calculate_layout_for(self.buckets()) {
+ Some(lco) => lco,
+ None => hint::unreachable_unchecked(),
+ };
+ self.alloc.deallocate(
+ NonNull::new_unchecked(self.ctrl.as_ptr().sub(ctrl_offset)),
+ layout,
+ );
+ }
+
+ /// Marks all table buckets as empty without dropping their contents.
+ #[inline]
+ fn clear_no_drop(&mut self) {
+ if !self.is_empty_singleton() {
+ unsafe {
+ self.ctrl(0).write_bytes(EMPTY, self.num_ctrl_bytes());
+ }
+ }
+ self.items = 0;
+ self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
+ }
+
+ #[inline]
+ unsafe fn erase(&mut self, index: usize) {
+ debug_assert!(is_full(*self.ctrl(index)));
+ let index_before = index.wrapping_sub(Group::WIDTH) & self.bucket_mask;
+ let empty_before = Group::load(self.ctrl(index_before)).match_empty();
+ let empty_after = Group::load(self.ctrl(index)).match_empty();
+
+ // If we are inside a continuous block of Group::WIDTH full or deleted
+ // cells then a probe window may have seen a full block when trying to
+ // insert. We therefore need to keep that block non-empty so that
+ // lookups will continue searching to the next probe window.
+ //
+ // Note that in this context `leading_zeros` refers to the bytes at the
+ // end of a group, while `trailing_zeros` refers to the bytes at the
+ // beginning of a group.
+ let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH {
+ DELETED
+ } else {
+ self.growth_left += 1;
+ EMPTY
+ };
+ self.set_ctrl(index, ctrl);
+ self.items -= 1;
+ }
+}
+
+impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> {
+ fn clone(&self) -> Self {
+ if self.table.is_empty_singleton() {
+ Self::new_in(self.table.alloc.clone())
+ } else {
+ unsafe {
+ // Avoid `Result::ok_or_else` because it bloats LLVM IR.
+ let new_table = match Self::new_uninitialized(
+ self.table.alloc.clone(),
+ self.table.buckets(),
+ Fallibility::Infallible,
+ ) {
+ Ok(table) => table,
+ Err(_) => hint::unreachable_unchecked(),
+ };
+
+ // If cloning fails then we need to free the allocation for the
+ // new table. However we don't run its drop since its control
+ // bytes are not initialized yet.
+ let mut guard = guard(ManuallyDrop::new(new_table), |new_table| {
+ new_table.free_buckets();
+ });
+
+ guard.clone_from_spec(self);
+
+ // Disarm the scope guard and return the newly created table.
+ ManuallyDrop::into_inner(ScopeGuard::into_inner(guard))
+ }
+ }
+ }
+
+ fn clone_from(&mut self, source: &Self) {
+ if source.table.is_empty_singleton() {
+ *self = Self::new_in(self.table.alloc.clone());
+ } else {
+ unsafe {
+ // Make sure that if any panics occurs, we clear the table and
+ // leave it in an empty state.
+ let mut self_ = guard(self, |self_| {
+ self_.clear_no_drop();
+ });
+
+ // First, drop all our elements without clearing the control
+ // bytes. If this panics then the scope guard will clear the
+ // table, leaking any elements that were not dropped yet.
+ //
+ // This leak is unavoidable: we can't try dropping more elements
+ // since this could lead to another panic and abort the process.
+ self_.drop_elements();
+
+ // If necessary, resize our table to match the source.
+ if self_.buckets() != source.buckets() {
+ // Skip our drop by using ptr::write.
+ if !self_.table.is_empty_singleton() {
+ self_.free_buckets();
+ }
+ (&mut **self_ as *mut Self).write(
+ // Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
+ match Self::new_uninitialized(
+ self_.table.alloc.clone(),
+ source.buckets(),
+ Fallibility::Infallible,
+ ) {
+ Ok(table) => table,
+ Err(_) => hint::unreachable_unchecked(),
+ },
+ );
+ }
+
+ self_.clone_from_spec(source);
+
+ // Disarm the scope guard if cloning was successful.
+ ScopeGuard::into_inner(self_);
+ }
+ }
+ }
+}
+
+/// Specialization of `clone_from` for `Copy` types
+trait RawTableClone {
+ unsafe fn clone_from_spec(&mut self, source: &Self);
+}
+impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
+ default_fn! {
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn clone_from_spec(&mut self, source: &Self) {
+ self.clone_from_impl(source);
+ }
+ }
+}
+#[cfg(feature = "nightly")]
+impl<T: Copy, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn clone_from_spec(&mut self, source: &Self) {
+ source
+ .table
+ .ctrl(0)
+ .copy_to_nonoverlapping(self.table.ctrl(0), self.table.num_ctrl_bytes());
+ source
+ .data_start()
+ .copy_to_nonoverlapping(self.data_start(), self.table.buckets());
+
+ self.table.items = source.table.items;
+ self.table.growth_left = source.table.growth_left;
+ }
+}
+
+impl<T: Clone, A: Allocator + Clone> RawTable<T, A> {
+ /// Common code for clone and clone_from. Assumes:
+ /// - `self.buckets() == source.buckets()`.
+ /// - Any existing elements have been dropped.
+ /// - The control bytes are not initialized yet.
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn clone_from_impl(&mut self, source: &Self) {
+ // Copy the control bytes unchanged. We do this in a single pass
+ source
+ .table
+ .ctrl(0)
+ .copy_to_nonoverlapping(self.table.ctrl(0), self.table.num_ctrl_bytes());
+
+ // The cloning of elements may panic, in which case we need
+ // to make sure we drop only the elements that have been
+ // cloned so far.
+ let mut guard = guard((0, &mut *self), |(index, self_)| {
+ if mem::needs_drop::<T>() && !self_.is_empty() {
+ for i in 0..=*index {
+ if is_full(*self_.table.ctrl(i)) {
+ self_.bucket(i).drop();
+ }
+ }
+ }
+ });
+
+ for from in source.iter() {
+ let index = source.bucket_index(&from);
+ let to = guard.1.bucket(index);
+ to.write(from.as_ref().clone());
+
+ // Update the index in case we need to unwind.
+ guard.0 = index;
+ }
+
+ // Successfully cloned all items, no need to clean up.
+ mem::forget(guard);
+
+ self.table.items = source.table.items;
+ self.table.growth_left = source.table.growth_left;
+ }
+
+ /// Variant of `clone_from` to use when a hasher is available.
+ #[cfg(feature = "raw")]
+ pub fn clone_from_with_hasher(&mut self, source: &Self, hasher: impl Fn(&T) -> u64) {
+ // If we have enough capacity in the table, just clear it and insert
+ // elements one by one. We don't do this if we have the same number of
+ // buckets as the source since we can just copy the contents directly
+ // in that case.
+ if self.table.buckets() != source.table.buckets()
+ && bucket_mask_to_capacity(self.table.bucket_mask) >= source.len()
+ {
+ self.clear();
+
+ let guard_self = guard(&mut *self, |self_| {
+ // Clear the partially copied table if a panic occurs, otherwise
+ // items and growth_left will be out of sync with the contents
+ // of the table.
+ self_.clear();
+ });
+
+ unsafe {
+ for item in source.iter() {
+ // This may panic.
+ let item = item.as_ref().clone();
+ let hash = hasher(&item);
+
+ // We can use a simpler version of insert() here since:
+ // - there are no DELETED entries.
+ // - we know there is enough space in the table.
+ // - all elements are unique.
+ let (index, _) = guard_self.table.prepare_insert_slot(hash);
+ guard_self.bucket(index).write(item);
+ }
+ }
+
+ // Successfully cloned all items, no need to clean up.
+ mem::forget(guard_self);
+
+ self.table.items = source.table.items;
+ self.table.growth_left -= source.table.items;
+ } else {
+ self.clone_from(source);
+ }
+ }
+}
+
+impl<T, A: Allocator + Clone + Default> Default for RawTable<T, A> {
+ #[inline]
+ fn default() -> Self {
+ Self::new_in(Default::default())
+ }
+}
+
+#[cfg(feature = "nightly")]
+unsafe impl<#[may_dangle] T, A: Allocator + Clone> Drop for RawTable<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn drop(&mut self) {
+ if !self.table.is_empty_singleton() {
+ unsafe {
+ self.drop_elements();
+ self.free_buckets();
+ }
+ }
+ }
+}
+#[cfg(not(feature = "nightly"))]
+impl<T, A: Allocator + Clone> Drop for RawTable<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn drop(&mut self) {
+ if !self.table.is_empty_singleton() {
+ unsafe {
+ self.drop_elements();
+ self.free_buckets();
+ }
+ }
+ }
+}
+
+impl<T, A: Allocator + Clone> IntoIterator for RawTable<T, A> {
+ type Item = T;
+ type IntoIter = RawIntoIter<T, A>;
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn into_iter(self) -> RawIntoIter<T, A> {
+ unsafe {
+ let iter = self.iter();
+ self.into_iter_from(iter)
+ }
+ }
+}
+
+/// Iterator over a sub-range of a table. Unlike `RawIter` this iterator does
+/// not track an item count.
+pub(crate) struct RawIterRange<T> {
+ // Mask of full buckets in the current group. Bits are cleared from this
+ // mask as each element is processed.
+ current_group: BitMask,
+
+ // Pointer to the buckets for the current group.
+ data: Bucket<T>,
+
+ // Pointer to the next group of control bytes,
+ // Must be aligned to the group size.
+ next_ctrl: *const u8,
+
+ // Pointer one past the last control byte of this range.
+ end: *const u8,
+}
+
+impl<T> RawIterRange<T> {
+ /// Returns a `RawIterRange` covering a subset of a table.
+ ///
+ /// The control byte address must be aligned to the group size.
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn new(ctrl: *const u8, data: Bucket<T>, len: usize) -> Self {
+ debug_assert_ne!(len, 0);
+ debug_assert_eq!(ctrl as usize % Group::WIDTH, 0);
+ let end = ctrl.add(len);
+
+ // Load the first group and advance ctrl to point to the next group
+ let current_group = Group::load_aligned(ctrl).match_full();
+ let next_ctrl = ctrl.add(Group::WIDTH);
+
+ Self {
+ current_group,
+ data,
+ next_ctrl,
+ end,
+ }
+ }
+
+ /// Splits a `RawIterRange` into two halves.
+ ///
+ /// Returns `None` if the remaining range is smaller than or equal to the
+ /// group width.
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[cfg(feature = "rayon")]
+ pub(crate) fn split(mut self) -> (Self, Option<RawIterRange<T>>) {
+ unsafe {
+ if self.end <= self.next_ctrl {
+ // Nothing to split if the group that we are current processing
+ // is the last one.
+ (self, None)
+ } else {
+ // len is the remaining number of elements after the group that
+ // we are currently processing. It must be a multiple of the
+ // group size (small tables are caught by the check above).
+ let len = offset_from(self.end, self.next_ctrl);
+ debug_assert_eq!(len % Group::WIDTH, 0);
+
+ // Split the remaining elements into two halves, but round the
+ // midpoint down in case there is an odd number of groups
+ // remaining. This ensures that:
+ // - The tail is at least 1 group long.
+ // - The split is roughly even considering we still have the
+ // current group to process.
+ let mid = (len / 2) & !(Group::WIDTH - 1);
+
+ let tail = Self::new(
+ self.next_ctrl.add(mid),
+ self.data.next_n(Group::WIDTH).next_n(mid),
+ len - mid,
+ );
+ debug_assert_eq!(
+ self.data.next_n(Group::WIDTH).next_n(mid).ptr,
+ tail.data.ptr
+ );
+ debug_assert_eq!(self.end, tail.end);
+ self.end = self.next_ctrl.add(mid);
+ debug_assert_eq!(self.end.add(Group::WIDTH), tail.next_ctrl);
+ (self, Some(tail))
+ }
+ }
+ }
+
+ /// # Safety
+ /// If DO_CHECK_PTR_RANGE is false, caller must ensure that we never try to iterate
+ /// after yielding all elements.
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn next_impl<const DO_CHECK_PTR_RANGE: bool>(&mut self) -> Option<Bucket<T>> {
+ loop {
+ if let Some(index) = self.current_group.lowest_set_bit() {
+ self.current_group = self.current_group.remove_lowest_bit();
+ return Some(self.data.next_n(index));
+ }
+
+ if DO_CHECK_PTR_RANGE && self.next_ctrl >= self.end {
+ return None;
+ }
+
+ // We might read past self.end up to the next group boundary,
+ // but this is fine because it only occurs on tables smaller
+ // than the group size where the trailing control bytes are all
+ // EMPTY. On larger tables self.end is guaranteed to be aligned
+ // to the group size (since tables are power-of-two sized).
+ self.current_group = Group::load_aligned(self.next_ctrl).match_full();
+ self.data = self.data.next_n(Group::WIDTH);
+ self.next_ctrl = self.next_ctrl.add(Group::WIDTH);
+ }
+ }
+}
+
+// We make raw iterators unconditionally Send and Sync, and let the PhantomData
+// in the actual iterator implementations determine the real Send/Sync bounds.
+unsafe impl<T> Send for RawIterRange<T> {}
+unsafe impl<T> Sync for RawIterRange<T> {}
+
+impl<T> Clone for RawIterRange<T> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn clone(&self) -> Self {
+ Self {
+ data: self.data.clone(),
+ next_ctrl: self.next_ctrl,
+ current_group: self.current_group,
+ end: self.end,
+ }
+ }
+}
+
+impl<T> Iterator for RawIterRange<T> {
+ type Item = Bucket<T>;
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn next(&mut self) -> Option<Bucket<T>> {
+ unsafe {
+ // SAFETY: We set checker flag to true.
+ self.next_impl::<true>()
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ // We don't have an item count, so just guess based on the range size.
+ let remaining_buckets = if self.end > self.next_ctrl {
+ unsafe { offset_from(self.end, self.next_ctrl) }
+ } else {
+ 0
+ };
+
+ // Add a group width to include the group we are currently processing.
+ (0, Some(Group::WIDTH + remaining_buckets))
+ }
+}
+
+impl<T> FusedIterator for RawIterRange<T> {}
+
+/// Iterator which returns a raw pointer to every full bucket in the table.
+///
+/// For maximum flexibility this iterator is not bound by a lifetime, but you
+/// must observe several rules when using it:
+/// - You must not free the hash table while iterating (including via growing/shrinking).
+/// - It is fine to erase a bucket that has been yielded by the iterator.
+/// - Erasing a bucket that has not yet been yielded by the iterator may still
+/// result in the iterator yielding that bucket (unless `reflect_remove` is called).
+/// - It is unspecified whether an element inserted after the iterator was
+/// created will be yielded by that iterator (unless `reflect_insert` is called).
+/// - The order in which the iterator yields bucket is unspecified and may
+/// change in the future.
+pub struct RawIter<T> {
+ pub(crate) iter: RawIterRange<T>,
+ items: usize,
+}
+
+impl<T> RawIter<T> {
+ /// Refresh the iterator so that it reflects a removal from the given bucket.
+ ///
+ /// For the iterator to remain valid, this method must be called once
+ /// for each removed bucket before `next` is called again.
+ ///
+ /// This method should be called _before_ the removal is made. It is not necessary to call this
+ /// method if you are removing an item that this iterator yielded in the past.
+ #[cfg(feature = "raw")]
+ pub fn reflect_remove(&mut self, b: &Bucket<T>) {
+ self.reflect_toggle_full(b, false);
+ }
+
+ /// Refresh the iterator so that it reflects an insertion into the given bucket.
+ ///
+ /// For the iterator to remain valid, this method must be called once
+ /// for each insert before `next` is called again.
+ ///
+ /// This method does not guarantee that an insertion of a bucket with a greater
+ /// index than the last one yielded will be reflected in the iterator.
+ ///
+ /// This method should be called _after_ the given insert is made.
+ #[cfg(feature = "raw")]
+ pub fn reflect_insert(&mut self, b: &Bucket<T>) {
+ self.reflect_toggle_full(b, true);
+ }
+
+ /// Refresh the iterator so that it reflects a change to the state of the given bucket.
+ #[cfg(feature = "raw")]
+ fn reflect_toggle_full(&mut self, b: &Bucket<T>, is_insert: bool) {
+ unsafe {
+ if b.as_ptr() > self.iter.data.as_ptr() {
+ // The iterator has already passed the bucket's group.
+ // So the toggle isn't relevant to this iterator.
+ return;
+ }
+
+ if self.iter.next_ctrl < self.iter.end
+ && b.as_ptr() <= self.iter.data.next_n(Group::WIDTH).as_ptr()
+ {
+ // The iterator has not yet reached the bucket's group.
+ // We don't need to reload anything, but we do need to adjust the item count.
+
+ if cfg!(debug_assertions) {
+ // Double-check that the user isn't lying to us by checking the bucket state.
+ // To do that, we need to find its control byte. We know that self.iter.data is
+ // at self.iter.next_ctrl - Group::WIDTH, so we work from there:
+ let offset = offset_from(self.iter.data.as_ptr(), b.as_ptr());
+ let ctrl = self.iter.next_ctrl.sub(Group::WIDTH).add(offset);
+ // This method should be called _before_ a removal, or _after_ an insert,
+ // so in both cases the ctrl byte should indicate that the bucket is full.
+ assert!(is_full(*ctrl));
+ }
+
+ if is_insert {
+ self.items += 1;
+ } else {
+ self.items -= 1;
+ }
+
+ return;
+ }
+
+ // The iterator is at the bucket group that the toggled bucket is in.
+ // We need to do two things:
+ //
+ // - Determine if the iterator already yielded the toggled bucket.
+ // If it did, we're done.
+ // - Otherwise, update the iterator cached group so that it won't
+ // yield a to-be-removed bucket, or _will_ yield a to-be-added bucket.
+ // We'll also need to update the item count accordingly.
+ if let Some(index) = self.iter.current_group.lowest_set_bit() {
+ let next_bucket = self.iter.data.next_n(index);
+ if b.as_ptr() > next_bucket.as_ptr() {
+ // The toggled bucket is "before" the bucket the iterator would yield next. We
+ // therefore don't need to do anything --- the iterator has already passed the
+ // bucket in question.
+ //
+ // The item count must already be correct, since a removal or insert "prior" to
+ // the iterator's position wouldn't affect the item count.
+ } else {
+ // The removed bucket is an upcoming bucket. We need to make sure it does _not_
+ // get yielded, and also that it's no longer included in the item count.
+ //
+ // NOTE: We can't just reload the group here, both since that might reflect
+ // inserts we've already passed, and because that might inadvertently unset the
+ // bits for _other_ removals. If we do that, we'd have to also decrement the
+ // item count for those other bits that we unset. But the presumably subsequent
+ // call to reflect for those buckets might _also_ decrement the item count.
+ // Instead, we _just_ flip the bit for the particular bucket the caller asked
+ // us to reflect.
+ let our_bit = offset_from(self.iter.data.as_ptr(), b.as_ptr());
+ let was_full = self.iter.current_group.flip(our_bit);
+ debug_assert_ne!(was_full, is_insert);
+
+ if is_insert {
+ self.items += 1;
+ } else {
+ self.items -= 1;
+ }
+
+ if cfg!(debug_assertions) {
+ if b.as_ptr() == next_bucket.as_ptr() {
+ // The removed bucket should no longer be next
+ debug_assert_ne!(self.iter.current_group.lowest_set_bit(), Some(index));
+ } else {
+ // We should not have changed what bucket comes next.
+ debug_assert_eq!(self.iter.current_group.lowest_set_bit(), Some(index));
+ }
+ }
+ }
+ } else {
+ // We must have already iterated past the removed item.
+ }
+ }
+ }
+
+ unsafe fn drop_elements(&mut self) {
+ if mem::needs_drop::<T>() && self.len() != 0 {
+ for item in self {
+ item.drop();
+ }
+ }
+ }
+}
+
+impl<T> Clone for RawIter<T> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn clone(&self) -> Self {
+ Self {
+ iter: self.iter.clone(),
+ items: self.items,
+ }
+ }
+}
+
+impl<T> Iterator for RawIter<T> {
+ type Item = Bucket<T>;
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn next(&mut self) -> Option<Bucket<T>> {
+ // Inner iterator iterates over buckets
+ // so it can do unnecessary work if we already yielded all items.
+ if self.items == 0 {
+ return None;
+ }
+
+ let nxt = unsafe {
+ // SAFETY: We check number of items to yield using `items` field.
+ self.iter.next_impl::<false>()
+ };
+
+ if nxt.is_some() {
+ self.items -= 1;
+ }
+
+ nxt
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (self.items, Some(self.items))
+ }
+}
+
+impl<T> ExactSizeIterator for RawIter<T> {}
+impl<T> FusedIterator for RawIter<T> {}
+
+/// Iterator which consumes a table and returns elements.
+pub struct RawIntoIter<T, A: Allocator + Clone = Global> {
+ iter: RawIter<T>,
+ allocation: Option<(NonNull<u8>, Layout)>,
+ marker: PhantomData<T>,
+ alloc: A,
+}
+
+impl<T, A: Allocator + Clone> RawIntoIter<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn iter(&self) -> RawIter<T> {
+ self.iter.clone()
+ }
+}
+
+unsafe impl<T, A: Allocator + Clone> Send for RawIntoIter<T, A>
+where
+ T: Send,
+ A: Send,
+{
+}
+unsafe impl<T, A: Allocator + Clone> Sync for RawIntoIter<T, A>
+where
+ T: Sync,
+ A: Sync,
+{
+}
+
+#[cfg(feature = "nightly")]
+unsafe impl<#[may_dangle] T, A: Allocator + Clone> Drop for RawIntoIter<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn drop(&mut self) {
+ unsafe {
+ // Drop all remaining elements
+ self.iter.drop_elements();
+
+ // Free the table
+ if let Some((ptr, layout)) = self.allocation {
+ self.alloc.deallocate(ptr, layout);
+ }
+ }
+ }
+}
+#[cfg(not(feature = "nightly"))]
+impl<T, A: Allocator + Clone> Drop for RawIntoIter<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn drop(&mut self) {
+ unsafe {
+ // Drop all remaining elements
+ self.iter.drop_elements();
+
+ // Free the table
+ if let Some((ptr, layout)) = self.allocation {
+ self.alloc.deallocate(ptr, layout);
+ }
+ }
+ }
+}
+
+impl<T, A: Allocator + Clone> Iterator for RawIntoIter<T, A> {
+ type Item = T;
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn next(&mut self) -> Option<T> {
+ unsafe { Some(self.iter.next()?.read()) }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<T, A: Allocator + Clone> ExactSizeIterator for RawIntoIter<T, A> {}
+impl<T, A: Allocator + Clone> FusedIterator for RawIntoIter<T, A> {}
+
+/// Iterator which consumes elements without freeing the table storage.
+pub struct RawDrain<'a, T, A: Allocator + Clone = Global> {
+ iter: RawIter<T>,
+
+ // The table is moved into the iterator for the duration of the drain. This
+ // ensures that an empty table is left if the drain iterator is leaked
+ // without dropping.
+ table: ManuallyDrop<RawTable<T, A>>,
+ orig_table: NonNull<RawTable<T, A>>,
+
+ // We don't use a &'a mut RawTable<T> because we want RawDrain to be
+ // covariant over T.
+ marker: PhantomData<&'a RawTable<T, A>>,
+}
+
+impl<T, A: Allocator + Clone> RawDrain<'_, T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn iter(&self) -> RawIter<T> {
+ self.iter.clone()
+ }
+}
+
+unsafe impl<T, A: Allocator + Copy> Send for RawDrain<'_, T, A>
+where
+ T: Send,
+ A: Send,
+{
+}
+unsafe impl<T, A: Allocator + Copy> Sync for RawDrain<'_, T, A>
+where
+ T: Sync,
+ A: Sync,
+{
+}
+
+impl<T, A: Allocator + Clone> Drop for RawDrain<'_, T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn drop(&mut self) {
+ unsafe {
+ // Drop all remaining elements. Note that this may panic.
+ self.iter.drop_elements();
+
+ // Reset the contents of the table now that all elements have been
+ // dropped.
+ self.table.clear_no_drop();
+
+ // Move the now empty table back to its original location.
+ self.orig_table
+ .as_ptr()
+ .copy_from_nonoverlapping(&*self.table, 1);
+ }
+ }
+}
+
+impl<T, A: Allocator + Clone> Iterator for RawDrain<'_, T, A> {
+ type Item = T;
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn next(&mut self) -> Option<T> {
+ unsafe {
+ let item = self.iter.next()?;
+ Some(item.read())
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.iter.size_hint()
+ }
+}
+
+impl<T, A: Allocator + Clone> ExactSizeIterator for RawDrain<'_, T, A> {}
+impl<T, A: Allocator + Clone> FusedIterator for RawDrain<'_, T, A> {}
+
+/// Iterator over occupied buckets that could match a given hash.
+///
+/// `RawTable` only stores 7 bits of the hash value, so this iterator may return
+/// items that have a hash value different than the one provided. You should
+/// always validate the returned values before using them.
+pub struct RawIterHash<'a, T, A: Allocator + Clone = Global> {
+ inner: RawIterHashInner<'a, A>,
+ _marker: PhantomData<T>,
+}
+
+struct RawIterHashInner<'a, A: Allocator + Clone> {
+ table: &'a RawTableInner<A>,
+
+ // The top 7 bits of the hash.
+ h2_hash: u8,
+
+ // The sequence of groups to probe in the search.
+ probe_seq: ProbeSeq,
+
+ group: Group,
+
+ // The elements within the group with a matching h2-hash.
+ bitmask: BitMaskIter,
+}
+
+impl<'a, T, A: Allocator + Clone> RawIterHash<'a, T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[cfg(feature = "raw")]
+ fn new(table: &'a RawTable<T, A>, hash: u64) -> Self {
+ RawIterHash {
+ inner: RawIterHashInner::new(&table.table, hash),
+ _marker: PhantomData,
+ }
+ }
+}
+impl<'a, A: Allocator + Clone> RawIterHashInner<'a, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ #[cfg(feature = "raw")]
+ fn new(table: &'a RawTableInner<A>, hash: u64) -> Self {
+ unsafe {
+ let h2_hash = h2(hash);
+ let probe_seq = table.probe_seq(hash);
+ let group = Group::load(table.ctrl(probe_seq.pos));
+ let bitmask = group.match_byte(h2_hash).into_iter();
+
+ RawIterHashInner {
+ table,
+ h2_hash,
+ probe_seq,
+ group,
+ bitmask,
+ }
+ }
+ }
+}
+
+impl<'a, T, A: Allocator + Clone> Iterator for RawIterHash<'a, T, A> {
+ type Item = Bucket<T>;
+
+ fn next(&mut self) -> Option<Bucket<T>> {
+ unsafe {
+ match self.inner.next() {
+ Some(index) => Some(self.inner.table.bucket(index)),
+ None => None,
+ }
+ }
+ }
+}
+
+impl<'a, A: Allocator + Clone> Iterator for RawIterHashInner<'a, A> {
+ type Item = usize;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ unsafe {
+ loop {
+ if let Some(bit) = self.bitmask.next() {
+ let index = (self.probe_seq.pos + bit) & self.table.bucket_mask;
+ return Some(index);
+ }
+ if likely(self.group.match_empty().any_bit_set()) {
+ return None;
+ }
+ self.probe_seq.move_next(self.table.bucket_mask);
+ self.group = Group::load(self.table.ctrl(self.probe_seq.pos));
+ self.bitmask = self.group.match_byte(self.h2_hash).into_iter();
+ }
+ }
+ }
+}
+
+#[cfg(test)]
+mod test_map {
+ use super::*;
+
+ fn rehash_in_place<T>(table: &mut RawTable<T>, hasher: impl Fn(&T) -> u64) {
+ unsafe {
+ table.table.rehash_in_place(
+ &|table, index| hasher(table.bucket::<T>(index).as_ref()),
+ mem::size_of::<T>(),
+ if mem::needs_drop::<T>() {
+ Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T)))
+ } else {
+ None
+ },
+ );
+ }
+ }
+
+ #[test]
+ fn rehash() {
+ let mut table = RawTable::new();
+ let hasher = |i: &u64| *i;
+ for i in 0..100 {
+ table.insert(i, i, hasher);
+ }
+
+ for i in 0..100 {
+ unsafe {
+ assert_eq!(table.find(i, |x| *x == i).map(|b| b.read()), Some(i));
+ }
+ assert!(table.find(i + 100, |x| *x == i + 100).is_none());
+ }
+
+ rehash_in_place(&mut table, hasher);
+
+ for i in 0..100 {
+ unsafe {
+ assert_eq!(table.find(i, |x| *x == i).map(|b| b.read()), Some(i));
+ }
+ assert!(table.find(i + 100, |x| *x == i + 100).is_none());
+ }
+ }
+}
diff --git a/vendor/hashbrown-0.12.3/src/raw/sse2.rs b/vendor/hashbrown-0.12.3/src/raw/sse2.rs
new file mode 100644
index 000000000..a0bf6da80
--- /dev/null
+++ b/vendor/hashbrown-0.12.3/src/raw/sse2.rs
@@ -0,0 +1,146 @@
+use super::bitmask::BitMask;
+use super::EMPTY;
+use core::mem;
+
+#[cfg(target_arch = "x86")]
+use core::arch::x86;
+#[cfg(target_arch = "x86_64")]
+use core::arch::x86_64 as x86;
+
+pub type BitMaskWord = u16;
+pub const BITMASK_STRIDE: usize = 1;
+pub const BITMASK_MASK: BitMaskWord = 0xffff;
+
+/// Abstraction over a group of control bytes which can be scanned in
+/// parallel.
+///
+/// This implementation uses a 128-bit SSE value.
+#[derive(Copy, Clone)]
+pub struct Group(x86::__m128i);
+
+// FIXME: https://github.com/rust-lang/rust-clippy/issues/3859
+#[allow(clippy::use_self)]
+impl Group {
+ /// Number of bytes in the group.
+ pub const WIDTH: usize = mem::size_of::<Self>();
+
+ /// Returns a full group of empty bytes, suitable for use as the initial
+ /// value for an empty hash table.
+ ///
+ /// This is guaranteed to be aligned to the group size.
+ #[inline]
+ #[allow(clippy::items_after_statements)]
+ pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
+ #[repr(C)]
+ struct AlignedBytes {
+ _align: [Group; 0],
+ bytes: [u8; Group::WIDTH],
+ }
+ const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
+ _align: [],
+ bytes: [EMPTY; Group::WIDTH],
+ };
+ &ALIGNED_BYTES.bytes
+ }
+
+ /// Loads a group of bytes starting at the given address.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)] // unaligned load
+ pub unsafe fn load(ptr: *const u8) -> Self {
+ Group(x86::_mm_loadu_si128(ptr.cast()))
+ }
+
+ /// Loads a group of bytes starting at the given address, which must be
+ /// aligned to `mem::align_of::<Group>()`.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)]
+ pub unsafe fn load_aligned(ptr: *const u8) -> Self {
+ // FIXME: use align_offset once it stabilizes
+ debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
+ Group(x86::_mm_load_si128(ptr.cast()))
+ }
+
+ /// Stores the group of bytes to the given address, which must be
+ /// aligned to `mem::align_of::<Group>()`.
+ #[inline]
+ #[allow(clippy::cast_ptr_alignment)]
+ pub unsafe fn store_aligned(self, ptr: *mut u8) {
+ // FIXME: use align_offset once it stabilizes
+ debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
+ x86::_mm_store_si128(ptr.cast(), self.0);
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which have
+ /// the given value.
+ #[inline]
+ pub fn match_byte(self, byte: u8) -> BitMask {
+ #[allow(
+ clippy::cast_possible_wrap, // byte: u8 as i8
+ // byte: i32 as u16
+ // note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the
+ // upper 16-bits of the i32 are zeroed:
+ clippy::cast_sign_loss,
+ clippy::cast_possible_truncation
+ )]
+ unsafe {
+ let cmp = x86::_mm_cmpeq_epi8(self.0, x86::_mm_set1_epi8(byte as i8));
+ BitMask(x86::_mm_movemask_epi8(cmp) as u16)
+ }
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which are
+ /// `EMPTY`.
+ #[inline]
+ pub fn match_empty(self) -> BitMask {
+ self.match_byte(EMPTY)
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which are
+ /// `EMPTY` or `DELETED`.
+ #[inline]
+ pub fn match_empty_or_deleted(self) -> BitMask {
+ #[allow(
+ // byte: i32 as u16
+ // note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the
+ // upper 16-bits of the i32 are zeroed:
+ clippy::cast_sign_loss,
+ clippy::cast_possible_truncation
+ )]
+ unsafe {
+ // A byte is EMPTY or DELETED iff the high bit is set
+ BitMask(x86::_mm_movemask_epi8(self.0) as u16)
+ }
+ }
+
+ /// Returns a `BitMask` indicating all bytes in the group which are full.
+ #[inline]
+ pub fn match_full(&self) -> BitMask {
+ self.match_empty_or_deleted().invert()
+ }
+
+ /// Performs the following transformation on all bytes in the group:
+ /// - `EMPTY => EMPTY`
+ /// - `DELETED => EMPTY`
+ /// - `FULL => DELETED`
+ #[inline]
+ pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
+ // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
+ // and high_bit = 0 (FULL) to 1000_0000
+ //
+ // Here's this logic expanded to concrete values:
+ // let special = 0 > byte = 1111_1111 (true) or 0000_0000 (false)
+ // 1111_1111 | 1000_0000 = 1111_1111
+ // 0000_0000 | 1000_0000 = 1000_0000
+ #[allow(
+ clippy::cast_possible_wrap, // byte: 0x80_u8 as i8
+ )]
+ unsafe {
+ let zero = x86::_mm_setzero_si128();
+ let special = x86::_mm_cmpgt_epi8(zero, self.0);
+ Group(x86::_mm_or_si128(
+ special,
+ x86::_mm_set1_epi8(0x80_u8 as i8),
+ ))
+ }
+ }
+}