/rust/registry/src/index.crates.io-1949cf8c6b5b557f/parcel_selectors-0.28.3/bloom.rs

Source
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */

//! Counting and non-counting Bloom filters tuned for use as ancestor filters
//! for selector matching.

use std::fmt::{self, Debug};

// The top 8 bits of the 32-bit hash value are not used by the bloom filter.
// Consumers may rely on this to pack hashes more efficiently.
pub const BLOOM_HASH_MASK: u32 = 0x00ffffff;
const KEY_SIZE: usize = 12;

const ARRAY_SIZE: usize = 1 << KEY_SIZE;
const KEY_MASK: u32 = (1 << KEY_SIZE) - 1;

/// A counting Bloom filter with 8-bit counters.
pub type BloomFilter = CountingBloomFilter<BloomStorageU8>;

/// A counting Bloom filter with parameterized storage to handle
/// counters of different sizes.  For now we assume that having two hash
/// functions is enough, but we may revisit that decision later.
///
/// The filter uses an array with 2**KeySize entries.
///
/// Assuming a well-distributed hash function, a Bloom filter with
/// array size M containing N elements and
/// using k hash function has expected false positive rate exactly
///
/// $  (1 - (1 - 1/M)^{kN})^k  $
///
/// because each array slot has a
///
/// $  (1 - 1/M)^{kN}  $
///
/// chance of being 0, and the expected false positive rate is the
/// probability that all of the k hash functions will hit a nonzero
/// slot.
///
/// For reasonable assumptions (M large, kN large, which should both
/// hold if we're worried about false positives) about M and kN this
/// becomes approximately
///
/// $$  (1 - \exp(-kN/M))^k   $$
///
/// For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$,
/// or in other words
///
/// $$    N/M = -0.5 * \ln(1 - \sqrt(r))   $$
///
/// where r is the false positive rate.  This can be used to compute
/// the desired KeySize for a given load N and false positive rate r.
///
/// If N/M is assumed small, then the false positive rate can
/// further be approximated as 4*N^2/M^2.  So increasing KeySize by
/// 1, which doubles M, reduces the false positive rate by about a
/// factor of 4, and a false positive rate of 1% corresponds to
/// about M/N == 20.
///
/// What this means in practice is that for a few hundred keys using a
/// KeySize of 12 gives false positive rates on the order of 0.25-4%.
///
/// Similarly, using a KeySize of 10 would lead to a 4% false
/// positive rate for N == 100 and to quite bad false positive
/// rates for larger N.
#[derive(Clone, Default)]
pub struct CountingBloomFilter<S>
where
  S: BloomStorage,
{
  storage: S,
}

impl<S> CountingBloomFilter<S>
where
  S: BloomStorage,
{
  /// Creates a new bloom filter.
  #[inline]
  pub fn new() -> Self {
    Default::default()
  }

  #[inline]
  pub fn clear(&mut self) {
    self.storage = Default::default();
  }

  // Slow linear accessor to make sure the bloom filter is zeroed. This should
  // never be used in release builds.
  #[cfg(debug_assertions)]
  pub fn is_zeroed(&self) -> bool {
    self.storage.is_zeroed()
  }

  #[cfg(not(debug_assertions))]
  pub fn is_zeroed(&self) -> bool {
    unreachable!()
  }

  /// Inserts an item with a particular hash into the bloom filter.
  #[inline]
  pub fn insert_hash(&mut self, hash: u32) {
    self.storage.adjust_first_slot(hash, true);
    self.storage.adjust_second_slot(hash, true);
  }

  /// Removes an item with a particular hash from the bloom filter.
  #[inline]
  pub fn remove_hash(&mut self, hash: u32) {
    self.storage.adjust_first_slot(hash, false);
    self.storage.adjust_second_slot(hash, false);
  }

  /// Check whether the filter might contain an item with the given hash.
  /// This can sometimes return true even if the item is not in the filter,
  /// but will never return false for items that are actually in the filter.
  #[inline]
  pub fn might_contain_hash(&self, hash: u32) -> bool {
    !self.storage.first_slot_is_empty(hash) && !self.storage.second_slot_is_empty(hash)
  }
}

impl<S> Debug for CountingBloomFilter<S>
where
  S: BloomStorage,
{
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    let mut slots_used = 0;
    for i in 0..ARRAY_SIZE {
      if !self.storage.slot_is_empty(i) {
        slots_used += 1;
      }
    }
    write!(f, "BloomFilter({}/{})", slots_used, ARRAY_SIZE)
  }
}

pub trait BloomStorage: Clone + Default {
  fn slot_is_empty(&self, index: usize) -> bool;
  fn adjust_slot(&mut self, index: usize, increment: bool);
  fn is_zeroed(&self) -> bool;

  #[inline]
  fn first_slot_is_empty(&self, hash: u32) -> bool {
    self.slot_is_empty(Self::first_slot_index(hash))
  }

  #[inline]
  fn second_slot_is_empty(&self, hash: u32) -> bool {
    self.slot_is_empty(Self::second_slot_index(hash))
  }

  #[inline]
  fn adjust_first_slot(&mut self, hash: u32, increment: bool) {
    self.adjust_slot(Self::first_slot_index(hash), increment)
  }

  #[inline]
  fn adjust_second_slot(&mut self, hash: u32, increment: bool) {
    self.adjust_slot(Self::second_slot_index(hash), increment)
  }

  #[inline]
  fn first_slot_index(hash: u32) -> usize {
    hash1(hash) as usize
  }

  #[inline]
  fn second_slot_index(hash: u32) -> usize {
    hash2(hash) as usize
  }
}

/// Storage class for a CountingBloomFilter that has 8-bit counters.
pub struct BloomStorageU8 {
  counters: [u8; ARRAY_SIZE],
}

impl BloomStorage for BloomStorageU8 {
  #[inline]
  fn adjust_slot(&mut self, index: usize, increment: bool) {
    let slot = &mut self.counters[index];
    if *slot != 0xff {
      // full
      if increment {
        *slot += 1;
      } else {
        *slot -= 1;
      }
    }
  }

  #[inline]
  fn slot_is_empty(&self, index: usize) -> bool {
    self.counters[index] == 0
  }

  #[inline]
  fn is_zeroed(&self) -> bool {
    self.counters.iter().all(|x| *x == 0)
  }
}

impl Default for BloomStorageU8 {
  fn default() -> Self {
    BloomStorageU8 {
      counters: [0; ARRAY_SIZE],
    }
  }
}

impl Clone for BloomStorageU8 {
  fn clone(&self) -> Self {
    BloomStorageU8 {
      counters: self.counters,
    }
  }
}

/// Storage class for a CountingBloomFilter that has 1-bit counters.
pub struct BloomStorageBool {
  counters: [u8; ARRAY_SIZE / 8],
}

impl BloomStorage for BloomStorageBool {
  #[inline]
  fn adjust_slot(&mut self, index: usize, increment: bool) {
    let bit = 1 << (index % 8);
    let byte = &mut self.counters[index / 8];

    // Since we have only one bit for storage, decrementing it
    // should never do anything.  Assert against an accidental
    // decrementing of a bit that was never set.
    assert!(
      increment || (*byte & bit) != 0,
      "should not decrement if slot is already false"
    );

    if increment {
      *byte |= bit;
    }
  }

  #[inline]
  fn slot_is_empty(&self, index: usize) -> bool {
    let bit = 1 << (index % 8);
    (self.counters[index / 8] & bit) == 0
  }

  #[inline]
  fn is_zeroed(&self) -> bool {
    self.counters.iter().all(|x| *x == 0)
  }
}

impl Default for BloomStorageBool {
  fn default() -> Self {
    BloomStorageBool {
      counters: [0; ARRAY_SIZE / 8],
    }
  }
}

impl Clone for BloomStorageBool {
  fn clone(&self) -> Self {
    BloomStorageBool {
      counters: self.counters,
    }
  }
}

#[inline]
fn hash1(hash: u32) -> u32 {
  hash & KEY_MASK
}

#[inline]
fn hash2(hash: u32) -> u32 {
  (hash >> KEY_SIZE) & KEY_MASK
}

#[test]
fn create_and_insert_some_stuff() {
  use rustc_hash::FxHasher;
  use std::hash::{Hash, Hasher};
  use std::mem::transmute;

  fn hash_as_str(i: usize) -> u32 {
    let mut hasher = FxHasher::default();
    let s = i.to_string();
    s.hash(&mut hasher);
    let hash: u64 = hasher.finish();
    (hash >> 32) as u32 ^ (hash as u32)
  }

  let mut bf = BloomFilter::new();

  // Statically assert that ARRAY_SIZE is a multiple of 8, which
  // BloomStorageBool relies on.
  unsafe {
    transmute::<[u8; ARRAY_SIZE % 8], [u8; 0]>([]);
  }

  for i in 0_usize..1000 {
    bf.insert_hash(hash_as_str(i));
  }

  for i in 0_usize..1000 {
    assert!(bf.might_contain_hash(hash_as_str(i)));
  }

  let false_positives = (1001_usize..2000).filter(|i| bf.might_contain_hash(hash_as_str(*i))).count();

  assert!(false_positives < 190, "{} is not < 190", false_positives); // 19%.

  for i in 0_usize..100 {
    bf.remove_hash(hash_as_str(i));
  }

  for i in 100_usize..1000 {
    assert!(bf.might_contain_hash(hash_as_str(i)));
  }

  let false_positives = (0_usize..100).filter(|i| bf.might_contain_hash(hash_as_str(*i))).count();

  assert!(false_positives < 20, "{} is not < 20", false_positives); // 20%.

  bf.clear();

  for i in 0_usize..2000 {
    assert!(!bf.might_contain_hash(hash_as_str(i)));
  }
}

#[cfg(feature = "bench")]
#[cfg(test)]
mod bench {
  extern crate test;
  use super::BloomFilter;

  #[derive(Default)]
  struct HashGenerator(u32);

  impl HashGenerator {
    fn next(&mut self) -> u32 {
      // Each hash is split into two twelve-bit segments, which are used
      // as an index into an array. We increment each by 64 so that we
      // hit the next cache line, and then another 1 so that our wrapping
      // behavior leads us to different entries each time.
      //
      // Trying to simulate cold caches is rather difficult with the cargo
      // benchmarking setup, so it may all be moot depending on the number
      // of iterations that end up being run. But we might as well.
      self.0 += (65) + (65 << super::KEY_SIZE);
      self.0
    }
  }

  #[bench]
  fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
    b.iter(|| {
      let mut gen1 = HashGenerator::default();
      let mut gen2 = HashGenerator::default();
      let mut bf = BloomFilter::new();
      for _ in 0_usize..1000 {
        bf.insert_hash(gen1.next());
      }
      for _ in 0_usize..100 {
        bf.remove_hash(gen2.next());
      }
      for _ in 100_usize..200 {
        test::black_box(bf.might_contain_hash(gen2.next()));
      }
    });
  }

  #[bench]
  fn might_contain_10(b: &mut test::Bencher) {
    let bf = BloomFilter::new();
    let mut gen = HashGenerator::default();
    b.iter(|| {
      for _ in 0..10 {
        test::black_box(bf.might_contain_hash(gen.next()));
      }
    });
  }

  #[bench]
  fn clear(b: &mut test::Bencher) {
    let mut bf = Box::new(BloomFilter::new());
    b.iter(|| test::black_box(&mut bf).clear());
  }

  #[bench]
  fn insert_10(b: &mut test::Bencher) {
    let mut bf = BloomFilter::new();
    let mut gen = HashGenerator::default();
    b.iter(|| {
      for _ in 0..10 {
        test::black_box(bf.insert_hash(gen.next()));
      }
    });
  }

  #[bench]
  fn remove_10(b: &mut test::Bencher) {
    let mut bf = BloomFilter::new();
    let mut gen = HashGenerator::default();
    // Note: this will underflow, and that's ok.
    b.iter(|| {
      for _ in 0..10 {
        bf.remove_hash(gen.next())
      }
    });
  }
}

Coverage Report

Created: 2026-10-28 07:08

Line	Count	Source
1		/* This Source Code Form is subject to the terms of the Mozilla Public
2		* License, v. 2.0. If a copy of the MPL was not distributed with this
3		* file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5		//! Counting and non-counting Bloom filters tuned for use as ancestor filters
6		//! for selector matching.
7
8		use std::fmt::{self, Debug};
9
10		// The top 8 bits of the 32-bit hash value are not used by the bloom filter.
11		// Consumers may rely on this to pack hashes more efficiently.
12		pub const BLOOM_HASH_MASK: u32 = 0x00ffffff;
13		const KEY_SIZE: usize = 12;
14
15		const ARRAY_SIZE: usize = 1 << KEY_SIZE;
16		const KEY_MASK: u32 = (1 << KEY_SIZE) - 1;
17
18		/// A counting Bloom filter with 8-bit counters.
19		pub type BloomFilter = CountingBloomFilter<BloomStorageU8>;
20
21		/// A counting Bloom filter with parameterized storage to handle
22		/// counters of different sizes. For now we assume that having two hash
23		/// functions is enough, but we may revisit that decision later.
24		///
25		/// The filter uses an array with 2**KeySize entries.
26		///
27		/// Assuming a well-distributed hash function, a Bloom filter with
28		/// array size M containing N elements and
29		/// using k hash function has expected false positive rate exactly
30		///
31		/// $ (1 - (1 - 1/M)^{kN})^k $
32		///
33		/// because each array slot has a
34		///
35		/// $ (1 - 1/M)^{kN} $
36		///
37		/// chance of being 0, and the expected false positive rate is the
38		/// probability that all of the k hash functions will hit a nonzero
39		/// slot.
40		///
41		/// For reasonable assumptions (M large, kN large, which should both
42		/// hold if we're worried about false positives) about M and kN this
43		/// becomes approximately
44		///
45		/// $$ (1 - \exp(-kN/M))^k $$
46		///
47		/// For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$,
48		/// or in other words
49		///
50		/// $$ N/M = -0.5 * \ln(1 - \sqrt(r)) $$
51		///
52		/// where r is the false positive rate. This can be used to compute
53		/// the desired KeySize for a given load N and false positive rate r.
54		///
55		/// If N/M is assumed small, then the false positive rate can
56		/// further be approximated as 4*N^2/M^2. So increasing KeySize by
57		/// 1, which doubles M, reduces the false positive rate by about a
58		/// factor of 4, and a false positive rate of 1% corresponds to
59		/// about M/N == 20.
60		///
61		/// What this means in practice is that for a few hundred keys using a
62		/// KeySize of 12 gives false positive rates on the order of 0.25-4%.
63		///
64		/// Similarly, using a KeySize of 10 would lead to a 4% false
65		/// positive rate for N == 100 and to quite bad false positive
66		/// rates for larger N.
67		#[derive(Clone, Default)]
68		pub struct CountingBloomFilter<S>
69		where
70		S: BloomStorage,
71		{
72		storage: S,
73		}
74
75		impl<S> CountingBloomFilter<S>
76		where
77		S: BloomStorage,
78		{
79		/// Creates a new bloom filter.
80		#[inline]
81	0	pub fn new() -> Self {
82	0	Default::default()
83	0	}
84
85		#[inline]
86	0	pub fn clear(&mut self) {
87	0	self.storage = Default::default();
88	0	}
89
90		// Slow linear accessor to make sure the bloom filter is zeroed. This should
91		// never be used in release builds.
92		#[cfg(debug_assertions)]
93		pub fn is_zeroed(&self) -> bool {
94		self.storage.is_zeroed()
95		}
96
97		#[cfg(not(debug_assertions))]
98	0	pub fn is_zeroed(&self) -> bool {
99	0	unreachable!()
100		}
101
102		/// Inserts an item with a particular hash into the bloom filter.
103		#[inline]
104	0	pub fn insert_hash(&mut self, hash: u32) {
105	0	self.storage.adjust_first_slot(hash, true);
106	0	self.storage.adjust_second_slot(hash, true);
107	0	}
108
109		/// Removes an item with a particular hash from the bloom filter.
110		#[inline]
111	0	pub fn remove_hash(&mut self, hash: u32) {
112	0	self.storage.adjust_first_slot(hash, false);
113	0	self.storage.adjust_second_slot(hash, false);
114	0	}
115
116		/// Check whether the filter might contain an item with the given hash.
117		/// This can sometimes return true even if the item is not in the filter,
118		/// but will never return false for items that are actually in the filter.
119		#[inline]
120	0	pub fn might_contain_hash(&self, hash: u32) -> bool {
121	0	!self.storage.first_slot_is_empty(hash) && !self.storage.second_slot_is_empty(hash)
122	0	}
123		}
124
125		impl<S> Debug for CountingBloomFilter<S>
126		where
127		S: BloomStorage,
128		{
129	0	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
130	0	let mut slots_used = 0;
131	0	for i in 0..ARRAY_SIZE {
132	0	if !self.storage.slot_is_empty(i) {
133	0	slots_used += 1;
134	0	}
135		}
136	0	write!(f, "BloomFilter({}/{})", slots_used, ARRAY_SIZE)
137	0	}
138		}
139
140		pub trait BloomStorage: Clone + Default {
141		fn slot_is_empty(&self, index: usize) -> bool;
142		fn adjust_slot(&mut self, index: usize, increment: bool);
143		fn is_zeroed(&self) -> bool;
144
145		#[inline]
146	0	fn first_slot_is_empty(&self, hash: u32) -> bool {
147	0	self.slot_is_empty(Self::first_slot_index(hash))
148	0	}
149
150		#[inline]
151	0	fn second_slot_is_empty(&self, hash: u32) -> bool {
152	0	self.slot_is_empty(Self::second_slot_index(hash))
153	0	}
154
155		#[inline]
156	0	fn adjust_first_slot(&mut self, hash: u32, increment: bool) {
157	0	self.adjust_slot(Self::first_slot_index(hash), increment)
158	0	}
159
160		#[inline]
161	0	fn adjust_second_slot(&mut self, hash: u32, increment: bool) {
162	0	self.adjust_slot(Self::second_slot_index(hash), increment)
163	0	}
164
165		#[inline]
166	0	fn first_slot_index(hash: u32) -> usize {
167	0	hash1(hash) as usize
168	0	}
169
170		#[inline]
171	0	fn second_slot_index(hash: u32) -> usize {
172	0	hash2(hash) as usize
173	0	}
174		}
175
176		/// Storage class for a CountingBloomFilter that has 8-bit counters.
177		pub struct BloomStorageU8 {
178		counters: [u8; ARRAY_SIZE],
179		}
180
181		impl BloomStorage for BloomStorageU8 {
182		#[inline]
183	0	fn adjust_slot(&mut self, index: usize, increment: bool) {
184	0	let slot = &mut self.counters[index];
185	0	if *slot != 0xff {
186		// full
187	0	if increment {
188	0	*slot += 1;
189	0	} else {
190	0	*slot -= 1;
191	0	}
192	0	}
193	0	}
194
195		#[inline]
196	0	fn slot_is_empty(&self, index: usize) -> bool {
197	0	self.counters[index] == 0
198	0	}
199
200		#[inline]
201	0	fn is_zeroed(&self) -> bool {
202	0	self.counters.iter().all(\|x\| *x == 0)
203	0	}
204		}
205
206		impl Default for BloomStorageU8 {
207	0	fn default() -> Self {
208	0	BloomStorageU8 {
209	0	counters: [0; ARRAY_SIZE],
210	0	}
211	0	}
212		}
213
214		impl Clone for BloomStorageU8 {
215	0	fn clone(&self) -> Self {
216	0	BloomStorageU8 {
217	0	counters: self.counters,
218	0	}
219	0	}
220		}
221
222		/// Storage class for a CountingBloomFilter that has 1-bit counters.
223		pub struct BloomStorageBool {
224		counters: [u8; ARRAY_SIZE / 8],
225		}
226
227		impl BloomStorage for BloomStorageBool {
228		#[inline]
229	0	fn adjust_slot(&mut self, index: usize, increment: bool) {
230	0	let bit = 1 << (index % 8);
231	0	let byte = &mut self.counters[index / 8];
232
233		// Since we have only one bit for storage, decrementing it
234		// should never do anything. Assert against an accidental
235		// decrementing of a bit that was never set.
236	0	assert!(
237	0	increment \|\| (*byte & bit) != 0,
238		"should not decrement if slot is already false"
239		);
240
241	0	if increment {
242	0	*byte \|= bit;
243	0	}
244	0	}
245
246		#[inline]
247	0	fn slot_is_empty(&self, index: usize) -> bool {
248	0	let bit = 1 << (index % 8);
249	0	(self.counters[index / 8] & bit) == 0
250	0	}
251
252		#[inline]
253	0	fn is_zeroed(&self) -> bool {
254	0	self.counters.iter().all(\|x\| *x == 0)
255	0	}
256		}
257
258		impl Default for BloomStorageBool {
259	0	fn default() -> Self {
260	0	BloomStorageBool {
261	0	counters: [0; ARRAY_SIZE / 8],
262	0	}
263	0	}
264		}
265
266		impl Clone for BloomStorageBool {
267	0	fn clone(&self) -> Self {
268	0	BloomStorageBool {
269	0	counters: self.counters,
270	0	}
271	0	}
272		}
273
274		#[inline]
275	0	fn hash1(hash: u32) -> u32 {
276	0	hash & KEY_MASK
277	0	}
278
279		#[inline]
280	0	fn hash2(hash: u32) -> u32 {
281	0	(hash >> KEY_SIZE) & KEY_MASK
282	0	}
283
284		#[test]
285		fn create_and_insert_some_stuff() {
286		use rustc_hash::FxHasher;
287		use std::hash::{Hash, Hasher};
288		use std::mem::transmute;
289
290		fn hash_as_str(i: usize) -> u32 {
291		let mut hasher = FxHasher::default();
292		let s = i.to_string();
293		s.hash(&mut hasher);
294		let hash: u64 = hasher.finish();
295		(hash >> 32) as u32 ^ (hash as u32)
296		}
297
298		let mut bf = BloomFilter::new();
299
300		// Statically assert that ARRAY_SIZE is a multiple of 8, which
301		// BloomStorageBool relies on.
302		unsafe {
303		transmute::<[u8; ARRAY_SIZE % 8], [u8; 0]>([]);
304		}
305
306		for i in 0_usize..1000 {
307		bf.insert_hash(hash_as_str(i));
308		}
309
310		for i in 0_usize..1000 {
311		assert!(bf.might_contain_hash(hash_as_str(i)));
312		}
313
314		let false_positives = (1001_usize..2000).filter(\|i\| bf.might_contain_hash(hash_as_str(*i))).count();
315
316		assert!(false_positives < 190, "{} is not < 190", false_positives); // 19%.
317
318		for i in 0_usize..100 {
319		bf.remove_hash(hash_as_str(i));
320		}
321
322		for i in 100_usize..1000 {
323		assert!(bf.might_contain_hash(hash_as_str(i)));
324		}
325
326		let false_positives = (0_usize..100).filter(\|i\| bf.might_contain_hash(hash_as_str(*i))).count();
327
328		assert!(false_positives < 20, "{} is not < 20", false_positives); // 20%.
329
330		bf.clear();
331
332		for i in 0_usize..2000 {
333		assert!(!bf.might_contain_hash(hash_as_str(i)));
334		}
335		}
336
337		#[cfg(feature = "bench")]
338		#[cfg(test)]
339		mod bench {
340		extern crate test;
341		use super::BloomFilter;
342
343		#[derive(Default)]
344		struct HashGenerator(u32);
345
346		impl HashGenerator {
347		fn next(&mut self) -> u32 {
348		// Each hash is split into two twelve-bit segments, which are used
349		// as an index into an array. We increment each by 64 so that we
350		// hit the next cache line, and then another 1 so that our wrapping
351		// behavior leads us to different entries each time.
352		//
353		// Trying to simulate cold caches is rather difficult with the cargo
354		// benchmarking setup, so it may all be moot depending on the number
355		// of iterations that end up being run. But we might as well.
356		self.0 += (65) + (65 << super::KEY_SIZE);
357		self.0
358		}
359		}
360
361		#[bench]
362		fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
363		b.iter(\|\| {
364		let mut gen1 = HashGenerator::default();
365		let mut gen2 = HashGenerator::default();
366		let mut bf = BloomFilter::new();
367		for _ in 0_usize..1000 {
368		bf.insert_hash(gen1.next());
369		}
370		for _ in 0_usize..100 {
371		bf.remove_hash(gen2.next());
372		}
373		for _ in 100_usize..200 {
374		test::black_box(bf.might_contain_hash(gen2.next()));
375		}
376		});
377		}
378
379		#[bench]
380		fn might_contain_10(b: &mut test::Bencher) {
381		let bf = BloomFilter::new();
382		let mut gen = HashGenerator::default();
383		b.iter(\|\| {
384		for _ in 0..10 {
385		test::black_box(bf.might_contain_hash(gen.next()));
386		}
387		});
388		}
389
390		#[bench]
391		fn clear(b: &mut test::Bencher) {
392		let mut bf = Box::new(BloomFilter::new());
393		b.iter(\|\| test::black_box(&mut bf).clear());
394		}
395
396		#[bench]
397		fn insert_10(b: &mut test::Bencher) {
398		let mut bf = BloomFilter::new();
399		let mut gen = HashGenerator::default();
400		b.iter(\|\| {
401		for _ in 0..10 {
402		test::black_box(bf.insert_hash(gen.next()));
403		}
404		});
405		}
406
407		#[bench]
408		fn remove_10(b: &mut test::Bencher) {
409		let mut bf = BloomFilter::new();
410		let mut gen = HashGenerator::default();
411		// Note: this will underflow, and that's ok.
412		b.iter(\|\| {
413		for _ in 0..10 {
414		bf.remove_hash(gen.next())
415		}
416		});
417		}
418		}