hashbrown/control/group/
generic.rs

1use super::super::{BitMask, Tag};
2use core::{mem, ptr};
3
4// Use the native word size as the group size. Using a 64-bit group size on
5// a 32-bit architecture will just end up being more expensive because
6// shifts and multiplies will need to be emulated.
7
8cfg_if! {
9    if #[cfg(any(
10        target_pointer_width = "64",
11        target_arch = "aarch64",
12        target_arch = "x86_64",
13        target_arch = "wasm32",
14    ))] {
15        type GroupWord = u64;
16        type NonZeroGroupWord = core::num::NonZeroU64;
17    } else {
18        type GroupWord = u32;
19        type NonZeroGroupWord = core::num::NonZeroU32;
20    }
21}
22
23pub(crate) type BitMaskWord = GroupWord;
24pub(crate) type NonZeroBitMaskWord = NonZeroGroupWord;
25pub(crate) const BITMASK_STRIDE: usize = 8;
26// We only care about the highest bit of each tag for the mask.
27#[allow(clippy::cast_possible_truncation, clippy::unnecessary_cast)]
28pub(crate) const BITMASK_MASK: BitMaskWord = u64::from_ne_bytes([Tag::DELETED.0; 8]) as GroupWord;
29pub(crate) const BITMASK_ITER_MASK: BitMaskWord = !0;
30
31/// Helper function to replicate a tag across a `GroupWord`.
32#[inline]
33fn repeat(tag: Tag) -> GroupWord {
34    GroupWord::from_ne_bytes([tag.0; Group::WIDTH])
35}
36
37/// Abstraction over a group of control tags which can be scanned in
38/// parallel.
39///
40/// This implementation uses a word-sized integer.
41#[derive(Copy, Clone)]
42pub(crate) struct Group(GroupWord);
43
44// We perform all operations in the native endianness, and convert to
45// little-endian just before creating a BitMask. The can potentially
46// enable the compiler to eliminate unnecessary byte swaps if we are
47// only checking whether a BitMask is empty.
48#[allow(clippy::use_self)]
49impl Group {
50    /// Number of bytes in the group.
51    pub(crate) const WIDTH: usize = mem::size_of::<Self>();
52
53    /// Returns a full group of empty tags, suitable for use as the initial
54    /// value for an empty hash table.
55    ///
56    /// This is guaranteed to be aligned to the group size.
57    #[inline]
58    pub(crate) const fn static_empty() -> &'static [Tag; Group::WIDTH] {
59        #[repr(C)]
60        struct AlignedTags {
61            _align: [Group; 0],
62            tags: [Tag; Group::WIDTH],
63        }
64        const ALIGNED_TAGS: AlignedTags = AlignedTags {
65            _align: [],
66            tags: [Tag::EMPTY; Group::WIDTH],
67        };
68        &ALIGNED_TAGS.tags
69    }
70
71    /// Loads a group of tags starting at the given address.
72    #[inline]
73    #[allow(clippy::cast_ptr_alignment)] // unaligned load
74    pub(crate) unsafe fn load(ptr: *const Tag) -> Self {
75        Group(ptr::read_unaligned(ptr.cast()))
76    }
77
78    /// Loads a group of tags starting at the given address, which must be
79    /// aligned to `mem::align_of::<Group>()`.
80    #[inline]
81    #[allow(clippy::cast_ptr_alignment)]
82    pub(crate) unsafe fn load_aligned(ptr: *const Tag) -> Self {
83        debug_assert_eq!(ptr.align_offset(mem::align_of::<Self>()), 0);
84        Group(ptr::read(ptr.cast()))
85    }
86
87    /// Stores the group of tags to the given address, which must be
88    /// aligned to `mem::align_of::<Group>()`.
89    #[inline]
90    #[allow(clippy::cast_ptr_alignment)]
91    pub(crate) unsafe fn store_aligned(self, ptr: *mut Tag) {
92        debug_assert_eq!(ptr.align_offset(mem::align_of::<Self>()), 0);
93        ptr::write(ptr.cast(), self.0);
94    }
95
96    /// Returns a `BitMask` indicating all tags in the group which *may*
97    /// have the given value.
98    ///
99    /// This function may return a false positive in certain cases where
100    /// the tag in the group differs from the searched value only in its
101    /// lowest bit. This is fine because:
102    /// - This never happens for `EMPTY` and `DELETED`, only full entries.
103    /// - The check for key equality will catch these.
104    /// - This only happens if there is at least 1 true match.
105    /// - The chance of this happening is very low (< 1% chance per byte).
106    #[inline]
107    pub(crate) fn match_tag(self, tag: Tag) -> BitMask {
108        // This algorithm is derived from
109        // https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
110        let cmp = self.0 ^ repeat(tag);
111        BitMask((cmp.wrapping_sub(repeat(Tag(0x01))) & !cmp & repeat(Tag::DELETED)).to_le())
112    }
113
114    /// Returns a `BitMask` indicating all tags in the group which are
115    /// `EMPTY`.
116    #[inline]
117    pub(crate) fn match_empty(self) -> BitMask {
118        // If the high bit is set, then the tag must be either:
119        // 1111_1111 (EMPTY) or 1000_0000 (DELETED).
120        // So we can just check if the top two bits are 1 by ANDing them.
121        BitMask((self.0 & (self.0 << 1) & repeat(Tag::DELETED)).to_le())
122    }
123
124    /// Returns a `BitMask` indicating all tags in the group which are
125    /// `EMPTY` or `DELETED`.
126    #[inline]
127    pub(crate) fn match_empty_or_deleted(self) -> BitMask {
128        // A tag is EMPTY or DELETED iff the high bit is set
129        BitMask((self.0 & repeat(Tag::DELETED)).to_le())
130    }
131
132    /// Returns a `BitMask` indicating all tags in the group which are full.
133    #[inline]
134    pub(crate) fn match_full(self) -> BitMask {
135        self.match_empty_or_deleted().invert()
136    }
137
138    /// Performs the following transformation on all tags in the group:
139    /// - `EMPTY => EMPTY`
140    /// - `DELETED => EMPTY`
141    /// - `FULL => DELETED`
142    #[inline]
143    pub(crate) fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
144        // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
145        // and high_bit = 0 (FULL) to 1000_0000
146        //
147        // Here's this logic expanded to concrete values:
148        //   let full = 1000_0000 (true) or 0000_0000 (false)
149        //   !1000_0000 + 1 = 0111_1111 + 1 = 1000_0000 (no carry)
150        //   !0000_0000 + 0 = 1111_1111 + 0 = 1111_1111 (no carry)
151        let full = !self.0 & repeat(Tag::DELETED);
152        Group(!full + (full >> 7))
153    }
154}
hashbrown/control/group/generic.rs

hashbrown/control/group/
generic.rs
