]>
git.proxmox.com Git - rustc.git/blob - vendor/hashbrown-0.11.2/src/raw/generic.rs
1 use super::bitmask
::BitMask
;
5 // Use the native word size as the group size. Using a 64-bit group size on
6 // a 32-bit architecture will just end up being more expensive because
7 // shifts and multiplies will need to be emulated.
9 target_pointer_width
= "64",
10 target_arch
= "aarch64",
11 target_arch
= "x86_64",
15 target_pointer_width
= "32",
16 not(target_arch
= "aarch64"),
17 not(target_arch
= "x86_64"),
21 pub type BitMaskWord
= GroupWord
;
22 pub const BITMASK_STRIDE
: usize = 8;
23 // We only care about the highest bit of each byte for the mask.
24 #[allow(clippy::cast_possible_truncation, clippy::unnecessary_cast)]
25 pub const BITMASK_MASK
: BitMaskWord
= 0x8080_8080_8080_8080_u64 as GroupWord
;
27 /// Helper function to replicate a byte across a `GroupWord`.
29 fn repeat(byte
: u8) -> GroupWord
{
30 GroupWord
::from_ne_bytes([byte
; Group
::WIDTH
])
33 /// Abstraction over a group of control bytes which can be scanned in
36 /// This implementation uses a word-sized integer.
37 #[derive(Copy, Clone)]
38 pub struct Group(GroupWord
);
40 // We perform all operations in the native endianess, and convert to
41 // little-endian just before creating a BitMask. The can potentially
42 // enable the compiler to eliminate unnecessary byte swaps if we are
43 // only checking whether a BitMask is empty.
44 #[allow(clippy::use_self)]
46 /// Number of bytes in the group.
47 pub const WIDTH
: usize = mem
::size_of
::<Self>();
49 /// Returns a full group of empty bytes, suitable for use as the initial
50 /// value for an empty hash table.
52 /// This is guaranteed to be aligned to the group size.
53 pub const fn static_empty() -> &'
static [u8; Group
::WIDTH
] {
57 bytes
: [u8; Group
::WIDTH
],
59 const ALIGNED_BYTES
: AlignedBytes
= AlignedBytes
{
61 bytes
: [EMPTY
; Group
::WIDTH
],
66 /// Loads a group of bytes starting at the given address.
68 #[allow(clippy::cast_ptr_alignment)] // unaligned load
69 pub unsafe fn load(ptr
: *const u8) -> Self {
70 Group(ptr
::read_unaligned(ptr
.cast()))
73 /// Loads a group of bytes starting at the given address, which must be
74 /// aligned to `mem::align_of::<Group>()`.
76 #[allow(clippy::cast_ptr_alignment)]
77 pub unsafe fn load_aligned(ptr
: *const u8) -> Self {
78 // FIXME: use align_offset once it stabilizes
79 debug_assert_eq
!(ptr
as usize & (mem
::align_of
::<Self>() - 1), 0);
80 Group(ptr
::read(ptr
.cast()))
83 /// Stores the group of bytes to the given address, which must be
84 /// aligned to `mem::align_of::<Group>()`.
86 #[allow(clippy::cast_ptr_alignment)]
87 pub unsafe fn store_aligned(self, ptr
: *mut u8) {
88 // FIXME: use align_offset once it stabilizes
89 debug_assert_eq
!(ptr
as usize & (mem
::align_of
::<Self>() - 1), 0);
90 ptr
::write(ptr
.cast(), self.0);
93 /// Returns a `BitMask` indicating all bytes in the group which *may*
94 /// have the given value.
96 /// This function may return a false positive in certain cases where
97 /// the byte in the group differs from the searched value only in its
98 /// lowest bit. This is fine because:
99 /// - This never happens for `EMPTY` and `DELETED`, only full entries.
100 /// - The check for key equality will catch these.
101 /// - This only happens if there is at least 1 true match.
102 /// - The chance of this happening is very low (< 1% chance per byte).
104 pub fn match_byte(self, byte
: u8) -> BitMask
{
105 // This algorithm is derived from
106 // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
107 let cmp
= self.0 ^
repeat(byte
);
108 BitMask((cmp
.wrapping_sub(repeat(0x01)) & !cmp
& repeat(0x80)).to_le())
111 /// Returns a `BitMask` indicating all bytes in the group which are
114 pub fn match_empty(self) -> BitMask
{
115 // If the high bit is set, then the byte must be either:
116 // 1111_1111 (EMPTY) or 1000_0000 (DELETED).
117 // So we can just check if the top two bits are 1 by ANDing them.
118 BitMask((self.0 & (self.0 << 1) & repeat(0x80)).to_le())
121 /// Returns a `BitMask` indicating all bytes in the group which are
122 /// `EMPTY` or `DELETED`.
124 pub fn match_empty_or_deleted(self) -> BitMask
{
125 // A byte is EMPTY or DELETED iff the high bit is set
126 BitMask((self.0 & repeat(0x80)).to_le())
129 /// Returns a `BitMask` indicating all bytes in the group which are full.
131 pub fn match_full(self) -> BitMask
{
132 self.match_empty_or_deleted().invert()
135 /// Performs the following transformation on all bytes in the group:
136 /// - `EMPTY => EMPTY`
137 /// - `DELETED => EMPTY`
138 /// - `FULL => DELETED`
140 pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
141 // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
142 // and high_bit = 0 (FULL) to 1000_0000
144 // Here's this logic expanded to concrete values:
145 // let full = 1000_0000 (true) or 0000_0000 (false)
146 // !1000_0000 + 1 = 0111_1111 + 1 = 1000_0000 (no carry)
147 // !0000_0000 + 0 = 1111_1111 + 0 = 1111_1111 (no carry)
148 let full
= !self.0 & repeat(0x80);
149 Group(!full
+ (full
>> 7))