1cfg_if::cfg_if! {
2 if #[cfg(all(
3 target_feature = "sse2",
4 any(target_arch = "x86", target_arch = "x86_64"),
5 not(miri),
6 not(feature = "no_simd"),
7 ))] {
8 mod sse2;
9 use sse2 as imp;
10 } else {
11 mod no_simd;
12 use no_simd as imp;
13 }
14}
15
16pub use imp::GroupQuery;
17pub use imp::GROUP_SIZE;
18
19// While GROUP_SIZE is target-dependent for performance reasons,
20// we always do probing as if it was the same as REFERENCE_GROUP_SIZE.
21// This way the same slot indices will be assigned to the same
22// entries no matter the underlying target. This allows the
23// binary format of the table to be portable.
24pub const REFERENCE_GROUP_SIZE: usize = 16;
25
26#[cfg(test)]
27mod tests {
28 use super::*;
29
30 const EMPTY_GROUP: [u8; GROUP_SIZE] = [255; GROUP_SIZE];
31
32 fn full_group() -> [u8; GROUP_SIZE] {
33 let mut group = [0; GROUP_SIZE];
34 for i in 0..group.len() {
35 group[i] = i as u8;
36 }
37 group
38 }
39
40 #[test]
41 fn full() {
42 let mut q = GroupQuery::from(&full_group(), 42);
43
44 assert_eq!(Iterator::count(&mut q), 0);
45 assert!(!q.any_empty());
46 assert_eq!(q.first_empty(), None);
47 }
48
49 #[test]
50 fn all_empty() {
51 let mut q = GroupQuery::from(&EMPTY_GROUP, 31);
52
53 assert_eq!(Iterator::count(&mut q), 0);
54 assert!(q.any_empty());
55 assert_eq!(q.first_empty(), Some(0));
56 }
57
58 #[test]
59 fn partially_filled() {
60 for filled_up_to_index in 0..=(GROUP_SIZE - 2) {
61 let mut group = EMPTY_GROUP;
62
63 for i in 0..=filled_up_to_index {
64 group[i] = 42;
65 }
66
67 let mut q = GroupQuery::from(&group, 77);
68
69 assert_eq!(Iterator::count(&mut q), 0);
70 assert!(q.any_empty());
71 assert_eq!(q.first_empty(), Some(filled_up_to_index + 1));
72 }
73 }
74
75 #[test]
76 fn match_iter() {
77 let expected: Vec<_> = (0..GROUP_SIZE).filter(|x| x % 3 == 0).collect();
78
79 let mut group = full_group();
80
81 for i in &expected {
82 group[*i] = 103;
83 }
84
85 let mut q = GroupQuery::from(&group, 103);
86
87 let matches: Vec<usize> = (&mut q).collect();
88
89 assert_eq!(matches, expected);
90 assert!(!q.any_empty());
91 assert_eq!(q.first_empty(), None);
92 }
93
94 #[test]
95 fn match_iter_with_empty() {
96 let expected: Vec<_> = (0..GROUP_SIZE).filter(|x| x % 3 == 2).collect();
97
98 let mut group = full_group();
99
100 for i in &expected {
101 group[*i] = 99;
102 }
103
104 // Clear a few slots
105 group[3] = 255;
106 group[4] = 255;
107 group[GROUP_SIZE - 1] = 255;
108
109 let mut q = GroupQuery::from(&group, 99);
110
111 let matches: Vec<usize> = (&mut q).collect();
112
113 assert_eq!(matches, expected);
114 assert!(q.any_empty());
115 assert_eq!(q.first_empty(), Some(3));
116 }
117}
118