1#[cfg(test)]
6use crate::pbf::BloomFilter;
7
8mod hash;
9pub mod pbf;
10
11#[macro_export]
12macro_rules! new_bloom_filter_fast {
13 ($item:expr, $fpr:expr) => {
14 $crate::pbf::PageBloomFilter::<{ $crate::pbf::best_way_const($fpr) }>::from_estimate($item, $fpr)
15 };
16}
17
18
19#[test]
20fn test_hash() {
21 let expected = [
22 [0x232706fc6bf50919_u64, 0x8b72ee65b4e851c7_u64],
23 [0x50209687d54ec67e_u64, 0x62fe85108df1cf6d_u64],
24 [0xfbe67d8368f3fb4f_u64, 0xb54a5a89706d5a5a_u64],
25 [0x2882d11a5846ccfa_u64, 0x6b21b0e870109222_u64],
26 [0xf5e0d56325d6d000_u64, 0xaf8703c9f9ac75e5_u64],
27 [0x59a0f67b7ae7a5ad_u64, 0x84d7aeabc053b848_u64],
28 [0xf01562a268e42c21_u64, 0xdfe994ab22873e7e_u64],
29 [0x16133104620725dd_u64, 0xa5ca36afa7182e6a_u64],
30 [0x7a9378dcdf599479_u64, 0x30f5a569a74ecdd7_u64],
31 [0xd9f07bdc76c20a78_u64, 0x34f0621847f7888a_u64],
32 [0x332a4fff07df83da_u64, 0xfa40557cc0ea6b72_u64],
33 [0x976beeefd11659dc_u64, 0x8a3187b6a72d0039_u64],
34 [0xc3fcc139e4c6832a_u64, 0xdadfeff6e01e2f2e_u64],
35 [0x86130593c7746a6f_u64, 0x8ac9fb14904fe39d_u64],
36 [0x70550dbe5cdde280_u64, 0xddb95757282706c0_u64],
37 [0x67211fbaf6b9122d_u64, 0x68f4e8f3bbc700db_u64],
38 [0xe2d06846964b80ad_u64, 0x6005068ac75c4c20_u64],
39 [0xd55b3c010258ce93_u64, 0x981c8b03659d9950_u64],
40 [0x5a2507daa032fa13_u64, 0x0d1c989bfc0c6cf7_u64],
41 [0xaf8618678ae5cd55_u64, 0xe0b75cfad427eefc_u64],
42 [0xad5a7047e8a139d8_u64, 0x183621cf988a753e_u64],
43 [0x8fc110192723cd5e_u64, 0x203129f80764b844_u64],
44 [0x50170b4485d7af19_u64, 0x7f2c79d145db7d35_u64],
45 [0x7c32444652212bf3_u64, 0x27fd51b9156e2ad2_u64],
46 [0x90e571225cce7360_u64, 0xf743b8f6f7433428_u64],
47 [0x9919537c1add41e1_u64, 0x7ff0158f05b261f2_u64],
48 [0x3a70a8070883029f_u64, 0xc5dcba911815d20a_u64],
49 [0xcc32b418290e2879_u64, 0xbb7945d6d79b5dfb_u64],
50 [0xde493e4646077aeb_u64, 0x465c2ea52660973a_u64],
51 [0x4d3ad9b55316f970_u64, 0x9137e3040a7d87bb_u64],
52 [0x1547de75efe848f4_u64, 0x21ae3f08b5330aac_u64],
53 [0xe2ead0cc6aab6aff_u64, 0x29a20bccf77e70a7_u64],
54 [0x3dc2f4a9e9b451b4_u64, 0x27de306dde7b60d2_u64],
55 [0xce247654a4de9f51_u64, 0x040097e45e948d66_u64],
56 [0xbc118f2ba2305503_u64, 0x810f05d0ea32853f_u64],
57 [0xb55cd8bdcac2a118_u64, 0x4e93b65164705d2a_u64],
58 [0xb7c97db807c32f38_u64, 0x510723230adef63d_u64],
59 ];
60 let key = "0123456789abcdefghijklmnopqrstuvwxyz".as_bytes();
61 for i in 0..expected.len() {
62 let code = hash::hash128(&key[..i]);
63 assert_eq!(expected[i], code);
64 }
65}
66
67#[test]
68fn test_new() {
69 let bf = pbf::new_bloom_filter(500, 0.01);
70 assert!(bf.valid());
71 assert_eq!(7, bf.get_way());
72 assert_eq!(7, bf.get_page_level());
73 assert_eq!(640, bf.get_data().len());
74}
75
76#[test]
77fn test_new_small() {
78 let bf = pbf::new_bloom_filter(1, 0.1);
79 assert!(bf.valid());
80 assert_eq!(4, bf.get_way());
81 assert_eq!(6, bf.get_page_level());
82 assert_eq!(1, bf.get_page_num());
83 assert_eq!(64, bf.get_data().len());
84}
85
86#[test]
87#[should_panic(expected = "pageNum should be in [1, 1 << 18)")]
88fn test_page_num_limit() {
89 let _ = pbf::PageBloomFilter::<4>::new(6, 1 << 18);
90}
91
92#[test]
93fn test_stable_bitmap_layout() {
94 let mut bf = pbf::new_bloom_filter(1, 0.01);
95 let keys: &[&[u8]] = &[
96 b"alpha",
97 "中文键".as_bytes(),
98 b"",
99 &[0x00, 0x01, 0x02, 0x03, 0xff],
100 ];
101 for key in keys {
102 assert!(bf.set(key));
103 }
104
105 let hex =
106 "0000000010000000000000004000000000000000000000100100000000010000\
107 0000000200000000000000000000040000000000040000008040000000000000\
108 0000004000004180020000002000000000000100080080000000800000000010\
109 0000000080000000000000000000410000800040000000800000000000002000";
110 let expected: Vec<u8> = hex
111 .as_bytes()
112 .chunks_exact(2)
113 .map(|pair| {
114 let digits = std::str::from_utf8(pair).unwrap();
115 u8::from_str_radix(digits, 16).unwrap()
116 })
117 .collect();
118 assert_eq!(expected.as_slice(), bf.get_data());
119}
120
121#[test]
122fn test_new_fast() {
123 let bf = new_bloom_filter_fast!(500, 0.01);
124 assert_eq!(7, bf.get_way());
125 assert_eq!(7, bf.get_page_level());
126 assert_eq!(640, bf.get_data().len());
127}
128
129#[test]
130fn test_operate() {
131 let _doit = |way: u8| {
132 let mut bf = pbf::new_pbf(way, 7, 3);
133 for i in 0..200 {
134 assert!(bf.set(&(i as u64).to_le_bytes()));
135 }
136 for i in 0..200 {
137 assert!(bf.test(&(i as u64).to_le_bytes()));
138 }
139 for i in 200..400 {
140 assert!(!bf.test(&(i as u64).to_le_bytes()));
141 }
142 };
143 for i in 4..9 {
144 _doit(i as u8);
145 }
146}
147
148#[test]
149fn test_clear_resets_unique_cnt() {
150 let mut bf = pbf::new_pbf(4, 7, 3);
151 let key = (123_u64).to_le_bytes();
152 assert!(bf.set(&key));
153 assert_eq!(1, bf.get_unique_cnt());
154 assert!(bf.test(&key));
155
156 bf.clear();
157
158 assert_eq!(0, bf.get_unique_cnt());
159 assert!(!bf.test(&key));
160}
161
162#[test]
163#[ignore]
164fn benchmark() {
165 let n = 1000000_usize;
166 let mut bf = pbf::new_bloom_filter(n, 0.01);
167
168 let set = std::time::Instant::now();
169 for i in 0..(n/2) {
170 bf.set(&(i as u64).to_le_bytes());
171 }
172 println!("pbf-set: {:.2}ns/op", (set.elapsed().as_nanos() as u64) as f64 / (n/2) as f64);
173
174 let test = std::time::Instant::now();
175 for i in 0..n {
176 bf.test(&(i as u64).to_le_bytes());
177 }
178 println!("pbf-test: {:.2}ns/op", (test.elapsed().as_nanos() as u64) as f64 / n as f64);
179
180 let mut fast = new_bloom_filter_fast!(n, 0.01);
181
182 let set = std::time::Instant::now();
183 for i in 0..(n/2) {
184 fast.set(&(i as u64).to_le_bytes());
185 }
186 println!("pbf-fast-set: {:.2}ns/op", (set.elapsed().as_nanos() as u64) as f64 / (n/2) as f64);
187
188 let test = std::time::Instant::now();
189 for i in 0..n {
190 fast.test(&(i as u64).to_le_bytes());
191 }
192 println!("pbf-fast-test: {:.2}ns/op", (test.elapsed().as_nanos() as u64) as f64 / n as f64);
193}