1mod hash;
6mod pbf;
7
8pub use pbf::{
9 best_way_const, new_bloom_filter, new_pbf, restore_pbf, BloomFilter, PageBloomFilter,
10};
11
12#[macro_export]
13macro_rules! new_bloom_filter_fast {
14 ($item:expr, $fpr:expr) => {
15 $crate::PageBloomFilter::<{ $crate::best_way_const($fpr) }>::from_estimate($item, $fpr)
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 = "0000000010000000000000004000000000000000000000100100000000010000\
106 0000000200000000000000000000040000000000040000008040000000000000\
107 0000004000004180020000002000000000000100080080000000800000000010\
108 0000000080000000000000000000410000800040000000800000000000002000";
109 let expected: Vec<u8> = hex
110 .as_bytes()
111 .chunks_exact(2)
112 .map(|pair| {
113 let digits = std::str::from_utf8(pair).unwrap();
114 u8::from_str_radix(digits, 16).unwrap()
115 })
116 .collect();
117 assert_eq!(expected.as_slice(), bf.get_data());
118}
119
120#[test]
121fn test_new_fast() {
122 let bf = new_bloom_filter_fast!(500, 0.01);
123 assert_eq!(7, bf.get_way());
124 assert_eq!(7, bf.get_page_level());
125 assert_eq!(640, bf.get_data().len());
126}
127
128#[test]
129fn test_operate() {
130 let _doit = |way: u8| {
131 let mut bf = pbf::new_pbf(way, 7, 3);
132 for i in 0..200 {
133 assert!(bf.set(&(i as u64).to_le_bytes()));
134 }
135 for i in 0..200 {
136 assert!(bf.test(&(i as u64).to_le_bytes()));
137 }
138 for i in 200..400 {
139 assert!(!bf.test(&(i as u64).to_le_bytes()));
140 }
141 };
142 for i in 4..9 {
143 _doit(i as u8);
144 }
145}
146
147#[test]
148fn test_clear_resets_unique_cnt() {
149 let mut bf = pbf::new_pbf(4, 7, 3);
150 let key = (123_u64).to_le_bytes();
151 assert!(bf.set(&key));
152 assert_eq!(1, bf.get_unique_cnt());
153 assert!(bf.test(&key));
154
155 bf.clear();
156
157 assert_eq!(0, bf.get_unique_cnt());
158 assert!(!bf.test(&key));
159}
160
161#[test]
162#[ignore]
163fn benchmark() {
164 let n = 1000000_usize;
165 let mut bf = pbf::new_bloom_filter(n, 0.01);
166
167 let set = std::time::Instant::now();
168 for i in 0..(n / 2) {
169 bf.set(&(i as u64).to_le_bytes());
170 }
171 println!(
172 "pbf-set: {:.2}ns/op",
173 (set.elapsed().as_nanos() as u64) as f64 / (n / 2) as f64
174 );
175
176 let test = std::time::Instant::now();
177 for i in 0..n {
178 bf.test(&(i as u64).to_le_bytes());
179 }
180 println!(
181 "pbf-test: {:.2}ns/op",
182 (test.elapsed().as_nanos() as u64) as f64 / n as f64
183 );
184
185 let mut fast = new_bloom_filter_fast!(n, 0.01);
186
187 let set = std::time::Instant::now();
188 for i in 0..(n / 2) {
189 fast.set(&(i as u64).to_le_bytes());
190 }
191 println!(
192 "pbf-fast-set: {:.2}ns/op",
193 (set.elapsed().as_nanos() as u64) as f64 / (n / 2) as f64
194 );
195
196 let test = std::time::Instant::now();
197 for i in 0..n {
198 fast.test(&(i as u64).to_le_bytes());
199 }
200 println!(
201 "pbf-fast-test: {:.2}ns/op",
202 (test.elapsed().as_nanos() as u64) as f64 / n as f64
203 );
204}