1use std::num::NonZeroU64;
2
3pub const GROUP_SIZE: usize = 8;
4
5type GroupWord = u64;
6type NonZeroGroupWord = NonZeroU64;
7
8pub struct GroupQuery {
9 eq_mask: GroupWord,
10 empty_mask: GroupWord,
11}
12
13#[inline]
14fn repeat(byte: u8) -> GroupWord {
15 GroupWord::from_ne_bytes([byte; GROUP_SIZE])
16}
17
18impl GroupQuery {
19 #[inline]
20 pub fn from(group: &[u8; GROUP_SIZE], h2: u8) -> GroupQuery {
21 // Adapted from this gem:
22 // https://github.com/rust-lang/hashbrown/blob/bbb5d3bb1c23569c15e54c670bc0c3669ae3e7dc/src/raw/generic.rs#L93-L109
23 // which in turn is based on
24 // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
25 //
26 // Note the mask generated by the code below can contain false
27 // positives. But we don't care because it's rare and we need
28 // to compare keys anyway. In other words, a false positive here
29 // has pretty much the same effect as a hash collision, something
30 // that we need to deal with in any case anyway.
31
32 let group = GroupWord::from_le_bytes(*group);
33 let cmp = group ^ repeat(h2);
34 let high_bit_greater_than_128 = (!cmp) & repeat(0x80);
35 let high_bit_greater_than_128_or_zero = cmp.wrapping_sub(repeat(0x01));
36 let eq_mask = high_bit_greater_than_128_or_zero & high_bit_greater_than_128;
37
38 let empty_mask = group & repeat(0x80);
39
40 GroupQuery {
41 eq_mask,
42 empty_mask,
43 }
44 }
45
46 #[inline]
47 pub fn any_empty(&self) -> bool {
48 self.empty_mask != 0
49 }
50
51 #[inline]
52 pub fn first_empty(&self) -> Option<usize> {
53 Some((NonZeroGroupWord::new(self.empty_mask)?.trailing_zeros() / 8) as usize)
54 }
55}
56
57impl Iterator for GroupQuery {
58 type Item = usize;
59
60 #[inline]
61 fn next(&mut self) -> Option<usize> {
62 let index: u32 = NonZeroGroupWord::new(self.eq_mask)?.trailing_zeros() / 8;
63
64 // Clear the lowest bit
65 // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
66 self.eq_mask &= self.eq_mask - 1;
67
68 Some(index as usize)
69 }
70}
71