This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new b0b70ed refactor(bloom)!: rewrite BloomFilter internals and
streamline tests (#359)
b0b70ed is described below
commit b0b70edd73c0fd8009e0d3016d9810e6d901e350
Author: tison <[email protected]>
AuthorDate: Sat Nov 14 23:03:37 2026 +0800
refactor(bloom)!: rewrite BloomFilter internals and streamline tests (#359)
Signed-off-by: tison <[email protected]>
---
CHANGELOG.md | 2 +
benchmarks/bloom/mod.rs | 2 +
benchmarks/bloom/query.rs | 104 +++
datasketches/examples/bloom_difference.rs | 10 +-
datasketches/src/bloom/filter.rs | 630 ++++++++++++++++
datasketches/src/bloom/mod.rs | 138 +---
datasketches/src/bloom/sketch.rs | 1012 --------------------------
tests-integration/tests/bloom_test/filter.rs | 390 ++++++++++
tests-integration/tests/bloom_test/main.rs | 2 +-
tests-integration/tests/bloom_test/sketch.rs | 339 ---------
tests-integration/tests/serde_tests/bloom.rs | 31 +-
11 files changed, 1184 insertions(+), 1476 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 0dafb20..2635ae1 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,7 +6,9 @@ All significant changes to this project will be documented in
this file.
### Breaking changes
+* `BloomFilter::capacity` now returns `u64` instead of `usize`; update callers
expecting `usize` to use `u64` or convert explicitly.
* `BloomFilter::contains` and `BloomFilter::contains_and_insert` now take
`item: T` (`T: Hash`) by value instead of `&T`, matching `BloomFilter::insert`.
Pass `&item` to retain owned values such as `String` or `Vec<u8>` without
cloning, and remove explicit turbofish type arguments (or change `T` to `&T`)
on borrowed calls such as `contains::<u64>(&value)`.
+* Fix 32-bit (`wasm32`) double hashing in `BloomFilter` to use the full 64-bit
hash consistently with 64-bit targets, Java, C++, and Go. 64-bit targets and
serialized formats are unchanged; rebuild or re-ingest filters created on
32-bit targets instead of mixing them across versions.
* `CountMinSketch::new` and `CountMinSketch::with_seed` now create serial
version 2 sketches, require `num_hashes` in `1..=127`, and emit images that
require a version 2 reader. Version 2 enables cross-language interchange when
using `i64` counters and the documented input encodings, while existing version
1 images remain readable, updatable, and serializable as version 1.
`CountMinSketch::merge` rejects mixing version 1 and version 2 sketches;
upgrade readers before writers and rebuild [...]
* `CpcSketch::max_serialized_bytes` and `ReqSketch::serialized_size_bytes` are
removed; serialize the sketch and inspect `len()` on the returned byte buffer
when the encoded size is needed.
* `ThetaJaccardSimilarity::compute` and `TupleJaccardSimilarity::compute` now
return `datasketches::common::JaccardSimilarity` instead of
`datasketches::thetacommon::JaccardSimilarity`, and `datasketches::thetacommon`
is no longer part of the public API.
diff --git a/benchmarks/bloom/mod.rs b/benchmarks/bloom/mod.rs
index 4839176..3e621a9 100644
--- a/benchmarks/bloom/mod.rs
+++ b/benchmarks/bloom/mod.rs
@@ -15,8 +15,10 @@
// specific language governing permissions and limitations
// under the License.
+mod query;
mod update;
pub fn register(runner: &mut benchmarks::Runner) {
+ query::register(runner);
update::register(runner);
}
diff --git a/benchmarks/bloom/query.rs b/benchmarks/bloom/query.rs
new file mode 100644
index 0000000..f0fa7fe
--- /dev/null
+++ b/benchmarks/bloom/query.rs
@@ -0,0 +1,104 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use benchmarks::Bencher;
+use benchmarks::Runner;
+use datasketches::bloom::BloomFilter;
+use datasketches::bloom::BloomFilterBuilder;
+use datasketches::hash::value::raw_bytes;
+
+use crate::hash_inputs::ITEMS;
+use crate::hash_inputs::bytes_32_values;
+
+fn populated_u64_filter() -> BloomFilter {
+ let mut filter = BloomFilterBuilder::with_accuracy(ITEMS as u64, 0.01)
+ .build()
+ .unwrap();
+ for value in 0..ITEMS as u64 {
+ filter.insert(value);
+ }
+ filter
+}
+
+fn populated_bytes_32_filter(values: &[[u8; 32]]) -> BloomFilter {
+ let mut filter = BloomFilterBuilder::with_accuracy(ITEMS as u64, 0.01)
+ .build()
+ .unwrap();
+ for value in values {
+ filter.insert(raw_bytes::from_slice(value));
+ }
+ filter
+}
+
+fn present_u64(bencher: Bencher) {
+ let filter = populated_u64_filter();
+
+ bencher.bench_local(|| {
+ for value in 0..ITEMS as u64 {
+ black_box(filter.contains(black_box(value)));
+ }
+ });
+}
+
+fn absent_u64(bencher: Bencher) {
+ let filter = populated_u64_filter();
+
+ bencher.bench_local(|| {
+ for value in ITEMS as u64..(ITEMS * 2) as u64 {
+ black_box(filter.contains(black_box(value)));
+ }
+ });
+}
+
+fn present_bytes_32(bencher: Bencher) {
+ let values = bytes_32_values();
+ let filter = populated_bytes_32_filter(&values);
+
+ bencher.bench_local(|| {
+ for value in &values {
+
black_box(filter.contains(raw_bytes::from_slice(black_box(value))));
+ }
+ });
+}
+
+fn absent_bytes_32(bencher: Bencher) {
+ let present = bytes_32_values();
+ let filter = populated_bytes_32_filter(&present);
+ let absent: Vec<[u8; 32]> = present
+ .into_iter()
+ .map(|mut bytes| {
+ // Distinct high byte ensures none of these 32-byte keys were
inserted.
+ bytes[31] = 1;
+ bytes
+ })
+ .collect();
+
+ bencher.bench_local(|| {
+ for value in &absent {
+
black_box(filter.contains(raw_bytes::from_slice(black_box(value))));
+ }
+ });
+}
+
+pub fn register(runner: &mut Runner) {
+ runner.case("bloom::query::present_u64", 2_000, present_u64);
+ runner.case("bloom::query::absent_u64", 2_000, absent_u64);
+ runner.case("bloom::query::present_bytes_32", 1_000, present_bytes_32);
+ runner.case("bloom::query::absent_bytes_32", 1_000, absent_bytes_32);
+}
diff --git a/datasketches/examples/bloom_difference.rs
b/datasketches/examples/bloom_difference.rs
index 9d5e99a..b4f1754 100644
--- a/datasketches/examples/bloom_difference.rs
+++ b/datasketches/examples/bloom_difference.rs
@@ -23,12 +23,14 @@
use datasketches::bloom::BloomFilter;
use datasketches::bloom::BloomFilterBuilder;
-/// Returns the shared filter configuration published by the origin.
+/// Returns an empty filter using the shared configuration published by the
origin.
///
/// Both sides of a difference must use identical capacity, hash count, and
seed, so the
/// parameters are distributed rather than chosen independently by each node.
-fn published_config() -> BloomFilterBuilder {
+fn published_filter() -> BloomFilter {
BloomFilterBuilder::with_accuracy(CACHED_OBJECTS, 0.01)
+ .build()
+ .unwrap()
}
/// Number of objects cached by the edge node.
@@ -41,13 +43,13 @@ fn purged_objects() -> impl Iterator<Item = u64> {
fn main() {
// The edge node records every object it caches.
- let mut cached = published_config().build().unwrap();
+ let mut cached = published_filter();
for object in 0..CACHED_OBJECTS {
cached.insert(object);
}
// The origin records every purged object using the same published
configuration.
- let mut purged = published_config().build().unwrap();
+ let mut purged = published_filter();
for object in purged_objects() {
purged.insert(object);
}
diff --git a/datasketches/src/bloom/filter.rs b/datasketches/src/bloom/filter.rs
new file mode 100644
index 0000000..838cbf4
--- /dev/null
+++ b/datasketches/src/bloom/filter.rs
@@ -0,0 +1,630 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::fmt;
+use std::hash::Hash;
+use std::hash::Hasher;
+
+use crate::codec::SketchBytes;
+use crate::codec::SketchSlice;
+use crate::codec::assert::ensure_preamble_longs_in_range;
+use crate::codec::assert::ensure_serial_version_is;
+use crate::codec::assert::insufficient_data;
+use crate::codec::family::Family;
+use crate::error::Error;
+use crate::error::ErrorKind;
+use crate::hash::DEFAULT_UPDATE_SEED;
+use crate::hash::XxHash64;
+
+const SERIAL_VERSION: u8 = 1;
+const EMPTY_FLAG_MASK: u8 = 1 << 2;
+const MIN_NUM_BITS: u64 = 1;
+const MAX_WORDS: u64 = i32::MAX as u64 - Family::BLOOMFILTER.max_pre_longs as
u64;
+const MAX_NUM_BITS: u64 = MAX_WORDS * 64;
+const MAX_ALLOCATABLE_WORDS: u64 = (isize::MAX as usize / size_of::<u64>()) as
u64;
+const MIN_NUM_HASHES: u16 = 1;
+const MAX_NUM_HASHES: u16 = i16::MAX as u16;
+
+/// Builder for creating [`BloomFilter`] instances.
+///
+/// Construct a builder using [`with_accuracy`](Self::with_accuracy)
(recommended) or
+/// [`with_size`](Self::with_size), optionally set [`seed`](Self::seed), and
finalize with
+/// [`build`](Self::build). Parameters are validated when `build` is called.
+#[derive(Debug, Clone)]
+pub struct BloomFilterBuilder {
+ mode: SizingMode,
+ seed: u64,
+}
+
+#[derive(Debug, Clone)]
+enum SizingMode {
+ Accuracy { max_items: u64, fpp: f64 },
+ Size { num_bits: u64, num_hashes: u16 },
+}
+
+impl BloomFilterBuilder {
+ /// Creates a builder sized for `max_items` at target false-positive
probability `fpp`, using
+ /// the default hash seed (`9001`).
+ ///
+ /// `max_items` is a sizing assumption, not an insertion limit. Inserting
more distinct items
+ /// remains valid, though the actual false-positive probability can exceed
`fpp`. An `fpp` of
+ /// `1.0` creates the minimal allocation: 64 bits and 1 hash function.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let filter = BloomFilterBuilder::with_accuracy(10_000, 0.01)
+ /// .seed(42)
+ /// .build()
+ /// .unwrap();
+ /// assert_eq!(filter.seed(), 42);
+ /// ```
+ pub fn with_accuracy(max_items: u64, fpp: f64) -> Self {
+ Self {
+ mode: SizingMode::Accuracy { max_items, fpp },
+ seed: DEFAULT_UPDATE_SEED,
+ }
+ }
+
+ /// Creates a builder with at least `num_bits` bits and `num_hashes` hash
functions, using the
+ /// default hash seed (`9001`).
+ ///
+ /// Capacity is rounded up to a multiple of 64 bits.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let filter = BloomFilterBuilder::with_size(10_000, 7).build().unwrap();
+ /// assert_eq!(filter.capacity(), 10_048);
+ /// assert_eq!(filter.num_hashes(), 7);
+ /// ```
+ pub fn with_size(num_bits: u64, num_hashes: u16) -> Self {
+ Self {
+ mode: SizingMode::Size {
+ num_bits,
+ num_hashes,
+ },
+ seed: DEFAULT_UPDATE_SEED,
+ }
+ }
+
+ /// Sets the hash seed used by the constructed filter (default: `9001`).
+ ///
+ /// Filters with different seeds cannot be combined via set operations.
+ pub fn seed(mut self, seed: u64) -> Self {
+ self.seed = seed;
+ self
+ }
+
+ /// Validates the builder configuration and allocates the [`BloomFilter`].
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](ErrorKind::InvalidArgument) if:
+ /// * In accuracy mode, `max_items` is zero, `fpp` is outside `(0.0,
1.0]`, or the target
+ /// exceeds the serialized format or addressable allocation limits.
+ /// * In size mode, `num_bits` is zero or exceeds the serialized format or
addressable
+ /// allocation limits, or `num_hashes` is outside `1..=32767`.
+ pub fn build(self) -> Result<BloomFilter, Error> {
+ let (num_bits, num_hashes) = match self.mode {
+ SizingMode::Accuracy { max_items, fpp } => {
+ if max_items == 0 {
+ return Err(Error::invalid_argument("max_items must be
greater than 0"));
+ }
+ if !(fpp > 0.0 && fpp <= 1.0) {
+ return Err(Error::invalid_argument("fpp must be in (0.0,
1.0]"));
+ }
+
+ let n = max_items as f64;
+ let ln2_squared = std::f64::consts::LN_2 *
std::f64::consts::LN_2;
+ let bits = (-n * fpp.ln() / ln2_squared).ceil();
+ if bits > MAX_NUM_BITS as f64 {
+ return Err(Error::invalid_argument(format!(
+ "target accuracy requires {bits:.0} bits, but at most
{MAX_NUM_BITS} are supported"
+ )));
+ }
+
+ let num_bits = (bits as u64).max(MIN_NUM_BITS);
+ let num_hashes = (num_bits as f64 / n * std::f64::consts::LN_2)
+ .ceil()
+ .clamp(f64::from(MIN_NUM_HASHES),
f64::from(MAX_NUM_HASHES))
+ as u16;
+ (num_bits, num_hashes)
+ }
+ SizingMode::Size {
+ num_bits,
+ num_hashes,
+ } => {
+ if !(MIN_NUM_BITS..=MAX_NUM_BITS).contains(&num_bits) {
+ return Err(Error::invalid_argument(format!(
+ "num_bits must be within
{MIN_NUM_BITS}..={MAX_NUM_BITS}, got {num_bits}"
+ )));
+ }
+ if !(MIN_NUM_HASHES..=MAX_NUM_HASHES).contains(&num_hashes) {
+ return Err(Error::invalid_argument(format!(
+ "num_hashes must be within
{MIN_NUM_HASHES}..={MAX_NUM_HASHES}, got {num_hashes}"
+ )));
+ }
+ (num_bits, num_hashes)
+ }
+ };
+
+ let bits = BitArray::new(num_bits)?;
+ Ok(BloomFilter {
+ seed: self.seed,
+ num_hashes,
+ bits,
+ })
+ }
+}
+
+/// A Bloom filter for probabilistic set membership testing.
+///
+/// A `false` result from [`contains`](Self::contains) proves that the item
was not inserted; a
+/// `true` result may be a false positive. Unlike resizing sketches, a Bloom
filter has a fixed
+/// bit capacity chosen at construction.
+///
+/// See [`BloomFilterBuilder`] and the [module level documentation](super) for
more.
+#[derive(Clone, PartialEq, Eq)]
+pub struct BloomFilter {
+ seed: u64,
+ num_hashes: u16,
+ bits: BitArray,
+}
+
+impl BloomFilter {
+ /// Returns `true` if `item` is possibly in the filter, or `false` if it
was definitely not
+ /// inserted.
+ #[inline]
+ pub fn contains<T: Hash>(&self, item: T) -> bool {
+ if self.is_empty() {
+ return false;
+ }
+ let (h0, h1) = self.hash_pair(item);
+ self.bits.contains(h0, h1, self.num_hashes)
+ }
+
+ /// Inserts `item` and returns `true` if all of its probe bits were
already set.
+ #[inline]
+ pub fn contains_and_insert<T: Hash>(&mut self, item: T) -> bool {
+ let (h0, h1) = self.hash_pair(item);
+ self.bits.contains_and_insert(h0, h1, self.num_hashes)
+ }
+
+ /// Inserts `item` into the filter.
+ #[inline]
+ pub fn insert<T: Hash>(&mut self, item: T) {
+ let (h0, h1) = self.hash_pair(item);
+ self.bits.insert(h0, h1, self.num_hashes);
+ }
+
+ /// Clears all bits while preserving capacity, hash count, and seed.
+ pub fn reset(&mut self) {
+ self.bits.words.fill(0);
+ self.bits.bits_used = 0;
+ }
+
+ /// Merges `other` into `self` via bitwise OR (union).
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](ErrorKind::InvalidArgument) if
+ /// [`is_compatible`](Self::is_compatible) is `false`.
+ pub fn union(&mut self, other: &Self) -> Result<(), Error> {
+ self.ensure_compatible(other)?;
+ self.bits
+ .combine(&other.bits, |word, other_word| *word |= other_word);
+ Ok(())
+ }
+
+ /// Intersects `self` with `other` via bitwise AND.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](ErrorKind::InvalidArgument) if
+ /// [`is_compatible`](Self::is_compatible) is `false`.
+ pub fn intersect(&mut self, other: &Self) -> Result<(), Error> {
+ self.ensure_compatible(other)?;
+ self.bits
+ .combine(&other.bits, |word, other_word| *word &= other_word);
+ Ok(())
+ }
+
+ /// Excludes `other` from `self` via bitwise AND-NOT (`self & !other`).
+ ///
+ /// Items inserted into `other` return `false` afterward; items inserted
only into `self`
+ /// remain present unless one of their bit positions is set in `other`.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidArgument`](ErrorKind::InvalidArgument) if
+ /// [`is_compatible`](Self::is_compatible) is `false`.
+ pub fn difference(&mut self, other: &Self) -> Result<(), Error> {
+ self.ensure_compatible(other)?;
+ self.bits
+ .combine(&other.bits, |word, other_word| *word &= !other_word);
+ Ok(())
+ }
+
+ /// Returns `true` if no bits are set in the filter.
+ #[inline]
+ pub fn is_empty(&self) -> bool {
+ self.bits.bits_used == 0
+ }
+
+ /// Returns the number of bits currently set to `1`.
+ pub fn bits_used(&self) -> u64 {
+ self.bits.bits_used
+ }
+
+ /// Returns the total bit capacity of the filter (always a positive
multiple of 64).
+ pub fn capacity(&self) -> u64 {
+ self.bits.capacity()
+ }
+
+ /// Returns the number of hash probes performed per item (`k`).
+ pub fn num_hashes(&self) -> u16 {
+ self.num_hashes
+ }
+
+ /// Returns the hash seed used by this filter.
+ pub fn seed(&self) -> u64 {
+ self.seed
+ }
+
+ /// Returns the fraction of bits currently set (`bits_used / capacity`).
+ pub fn load_factor(&self) -> f64 {
+ self.bits_used() as f64 / self.capacity() as f64
+ }
+
+ /// Returns the estimated false-positive probability
(`load_factor^num_hashes`).
+ pub fn estimated_fpp(&self) -> f64 {
+ self.load_factor().powi(i32::from(self.num_hashes))
+ }
+
+ /// Returns `true` if `self` and `other` have identical capacity,
`num_hashes`, and `seed`.
+ pub fn is_compatible(&self, other: &Self) -> bool {
+ self.bits.words.len() == other.bits.words.len()
+ && self.num_hashes == other.num_hashes
+ && self.seed == other.seed
+ }
+
+ /// Returns the estimated heap allocation of the filter's backing bit
array in bytes.
+ pub fn estimated_size(&self) -> usize {
+ size_of_val::<[u64]>(&self.bits.words)
+ }
+
+ /// Serializes the filter in the DataSketches binary format.
+ pub fn serialize(&self) -> Vec<u8> {
+ let is_empty = self.is_empty();
+ let preamble_longs = if is_empty {
+ Family::BLOOMFILTER.min_pre_longs
+ } else {
+ Family::BLOOMFILTER.max_pre_longs
+ };
+ let payload_bytes = if is_empty {
+ 0
+ } else {
+ size_of_val::<[u64]>(&self.bits.words)
+ };
+ let capacity = usize::from(preamble_longs) * size_of::<u64>() +
payload_bytes;
+ let mut bytes = SketchBytes::with_capacity(capacity);
+
+ bytes.write_u8(preamble_longs);
+ bytes.write_u8(SERIAL_VERSION);
+ bytes.write_u8(Family::BLOOMFILTER.id);
+ bytes.write_u8(if is_empty { EMPTY_FLAG_MASK } else { 0 });
+ bytes.write_u16_le(self.num_hashes);
+ bytes.write_u16_le(0);
+ bytes.write_u64_le(self.seed);
+ self.bits.serialize(&mut bytes);
+
+ bytes.into_bytes()
+ }
+
+ /// Deserializes a filter from DataSketches binary bytes.
+ ///
+ /// # Errors
+ ///
+ /// Returns [`InvalidData`](ErrorKind::InvalidData) if the header, bit
count, or payload is
+ /// malformed, truncated, or exceeds supported limits.
+ pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> {
+ let mut cursor = SketchSlice::new(bytes);
+
+ let preamble_longs = cursor
+ .read_u8()
+ .map_err(insufficient_data("preamble_longs"))?;
+ let serial_version = cursor
+ .read_u8()
+ .map_err(insufficient_data("serial_version"))?;
+ let family_id =
cursor.read_u8().map_err(insufficient_data("family_id"))?;
+ let flags = cursor.read_u8().map_err(insufficient_data("flags"))?;
+
+ Family::BLOOMFILTER.validate_id(family_id)?;
+ ensure_serial_version_is(SERIAL_VERSION, serial_version)?;
+ ensure_preamble_longs_in_range(
+
Family::BLOOMFILTER.min_pre_longs..=Family::BLOOMFILTER.max_pre_longs,
+ preamble_longs,
+ )?;
+
+ let is_empty = (flags & EMPTY_FLAG_MASK) != 0;
+ let num_hashes = cursor
+ .read_u16_le()
+ .map_err(insufficient_data("num_hashes"))?;
+ if !(MIN_NUM_HASHES..=MAX_NUM_HASHES).contains(&num_hashes) {
+ return Err(Error::deserial(format!(
+ "invalid num_hashes: expected [{MIN_NUM_HASHES},
{MAX_NUM_HASHES}], got {num_hashes}"
+ )));
+ }
+ let _unused = cursor
+ .read_u16_le()
+ .map_err(insufficient_data("unused_header"))?;
+ let seed = cursor.read_u64_le().map_err(insufficient_data("seed"))?;
+ let bits = BitArray::deserialize(cursor, is_empty)?;
+
+ Ok(Self {
+ seed,
+ num_hashes,
+ bits,
+ })
+ }
+
+ fn ensure_compatible(&self, other: &Self) -> Result<(), Error> {
+ if !self.is_compatible(other) {
+ return Err(Error::invalid_argument(
+ "Bloom filters must have matching capacity, number of hashes,
and seed",
+ ));
+ }
+ Ok(())
+ }
+
+ #[inline(always)]
+ fn hash_pair<T: Hash>(&self, item: T) -> (u64, u64) {
+ let mut hasher = XxHash64::with_seed(self.seed);
+ item.hash(&mut hasher);
+ let h0 = hasher.finish();
+
+ let mut hasher = XxHash64::with_seed(h0);
+ item.hash(&mut hasher);
+ let h1 = hasher.finish();
+
+ (h0, h1)
+ }
+}
+
+impl fmt::Debug for BloomFilter {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("BloomFilter")
+ .field("seed", &self.seed)
+ .field("num_hashes", &self.num_hashes)
+ .field("capacity", &self.capacity())
+ .field("bits_used", &self.bits_used())
+ .field("is_empty", &self.is_empty())
+ .finish()
+ }
+}
+
+// Scalar fields precede `words` so derived `PartialEq` short-circuits on
`bits_used`.
+#[derive(Clone, PartialEq, Eq)]
+struct BitArray {
+ bits_used: u64,
+ multiplier: u64,
+ shift: u32,
+ words: Box<[u64]>,
+}
+
+impl BitArray {
+ fn new(num_bits: u64) -> Result<Self, Error> {
+ let num_words = num_bits.div_ceil(64);
+ if !(1..=MAX_WORDS).contains(&num_words) {
+ return Err(Error::invalid_argument(format!(
+ "num_bits must be within {MIN_NUM_BITS}..={MAX_NUM_BITS}, got
{num_bits}"
+ )));
+ }
+ let word_len = allocatable_len(num_words, ErrorKind::InvalidArgument)?;
+ let words = vec![0_u64; word_len].into_boxed_slice();
+ Ok(Self::from_words(0, words))
+ }
+
+ fn deserialize(mut cursor: SketchSlice<'_>, is_empty: bool) ->
Result<Self, Error> {
+ let num_longs = cursor
+ .read_i32_le()
+ .map_err(insufficient_data("num_longs"))?;
+ let _unused =
cursor.read_u32_le().map_err(insufficient_data("unused"))?;
+
+ if !(1..=MAX_WORDS as i32).contains(&num_longs) {
+ return Err(Error::deserial(format!(
+ "invalid num_longs: expected [1, {MAX_WORDS}], got {num_longs}"
+ )));
+ }
+ let num_words = num_longs as u64;
+ let word_len = allocatable_len(num_words, ErrorKind::InvalidData)?;
+
+ if !is_empty {
+ let payload_bytes = num_words
+ .checked_add(1)
+ .and_then(|words| words.checked_mul(size_of::<u64>() as u64))
+ .and_then(|bytes| usize::try_from(bytes).ok())
+ .ok_or_else(|| Error::deserial("Bloom filter payload length
overflows"))?;
+ let available_bytes = cursor.remaining().len();
+ if available_bytes < payload_bytes {
+ return Err(Error::insufficient_data_of(
+ "Bloom filter payload",
+ format_args!("expected {payload_bytes} bytes, got
{available_bytes}"),
+ ));
+ }
+ }
+
+ let mut words = vec![0_u64; word_len].into_boxed_slice();
+ let bits_used = if is_empty {
+ 0
+ } else {
+ let serialized_num_bits_set = cursor
+ .read_u64_le()
+ .map_err(insufficient_data("num_bits_set"))?;
+ let mut ones = 0_u64;
+ for word in &mut words {
+ *word = cursor
+ .read_u64_le()
+ .map_err(insufficient_data("bit_array"))?;
+ ones += u64::from(word.count_ones());
+ }
+ if serialized_num_bits_set != u64::MAX && serialized_num_bits_set
!= ones {
+ return Err(Error::deserial(format!(
+ "invalid num_bits_set: expected {ones}, got
{serialized_num_bits_set}"
+ )));
+ }
+ ones
+ };
+
+ Ok(Self::from_words(bits_used, words))
+ }
+
+ fn serialize(&self, bytes: &mut SketchBytes) {
+ bytes.write_i32_le(self.words.len() as i32);
+ bytes.write_u32_le(0);
+ if self.bits_used != 0 {
+ bytes.write_u64_le(self.bits_used);
+ for &word in &self.words {
+ bytes.write_u64_le(word);
+ }
+ }
+ }
+
+ fn from_words(bits_used: u64, words: Box<[u64]>) -> Self {
+ let capacity = (words.len() as u64) << 6;
+ // `capacity` is a positive multiple of 64, so `2^(l - 1) < capacity
<= 2^l`
+ // and `ceil(2^(63 + l) / capacity)` fits in `u64`.
+ let l = 64 - (capacity - 1).leading_zeros();
+ let multiplier = (1_u128 << (63 + l)).div_ceil(u128::from(capacity))
as u64;
+ Self {
+ bits_used,
+ multiplier,
+ shift: l - 1,
+ words,
+ }
+ }
+
+ #[inline]
+ fn capacity(&self) -> u64 {
+ (self.words.len() as u64) << 6
+ }
+
+ #[inline(always)]
+ fn contains(&self, h0: u64, h1: u64, num_hashes: u16) -> bool {
+ let capacity = self.capacity();
+ let multiplier = self.multiplier;
+ let shift = self.shift;
+ let words = &*self.words;
+ for i in 1..=num_hashes {
+ let (word_index, mask) = probe_slot(h0, h1, i, capacity,
multiplier, shift);
+ if (words[word_index] & mask) == 0 {
+ return false;
+ }
+ }
+ true
+ }
+
+ #[inline(always)]
+ fn insert(&mut self, h0: u64, h1: u64, num_hashes: u16) {
+ let capacity = self.capacity();
+ let multiplier = self.multiplier;
+ let shift = self.shift;
+ let words = &mut *self.words;
+ let mut bits_added = 0_u64;
+ for i in 1..=num_hashes {
+ let (word_index, mask) = probe_slot(h0, h1, i, capacity,
multiplier, shift);
+ let word = &mut words[word_index];
+ let was_set = (*word & mask) != 0;
+ *word |= mask;
+ bits_added += u64::from(!was_set);
+ }
+ self.bits_used += bits_added;
+ }
+
+ #[inline(always)]
+ fn contains_and_insert(&mut self, h0: u64, h1: u64, num_hashes: u16) ->
bool {
+ let capacity = self.capacity();
+ let multiplier = self.multiplier;
+ let shift = self.shift;
+ let words = &mut *self.words;
+ let mut bits_added = 0_u64;
+ for i in 1..=num_hashes {
+ let (word_index, mask) = probe_slot(h0, h1, i, capacity,
multiplier, shift);
+ let word = &mut words[word_index];
+ if (*word & mask) == 0 {
+ *word |= mask;
+ bits_added += 1;
+ }
+ }
+ if bits_added != 0 {
+ self.bits_used += bits_added;
+ return false;
+ }
+ true
+ }
+
+ fn combine(&mut self, other: &Self, op: impl Fn(&mut u64, u64)) {
+ debug_assert_eq!(self.words.len(), other.words.len());
+ let mut bits_used = 0_u64;
+ for (word, &other_word) in self.words.iter_mut().zip(&other.words) {
+ op(word, other_word);
+ bits_used += u64::from(word.count_ones());
+ }
+ self.bits_used = bits_used;
+ }
+}
+
+fn allocatable_len(num_words: u64, kind: ErrorKind) -> Result<usize, Error> {
+ if num_words > MAX_ALLOCATABLE_WORDS {
+ return Err(Error::new(
+ kind,
+ format!(
+ "requested {num_words} words exceeds maximum addressable
allocation ({MAX_ALLOCATABLE_WORDS})"
+ ),
+ ));
+ }
+ Ok(num_words as usize)
+}
+
+#[inline(always)]
+fn probe_slot(
+ h0: u64,
+ h1: u64,
+ i: u16,
+ capacity: u64,
+ multiplier: u64,
+ shift: u32,
+) -> (usize, u64) {
+ let shifted = h0.wrapping_add(u64::from(i).wrapping_mul(h1)) >> 1;
+ let bit_index = bit_index(shifted, capacity, multiplier, shift);
+ let word_index = (bit_index >> 6) as usize;
+ let mask = 1_u64 << (bit_index & 63);
+ (word_index, mask)
+}
+
+#[inline(always)]
+fn bit_index(shifted: u64, capacity: u64, multiplier: u64, shift: u32) -> u64 {
+ debug_assert!(shifted < 1 << 63);
+ // Granlund-Montgomery invariant division: (multiplier * shifted) >> (63 +
l).
+ let quotient = ((u128::from(shifted) * u128::from(multiplier)) >> 64) as
u64 >> shift;
+ shifted - quotient * capacity
+}
diff --git a/datasketches/src/bloom/mod.rs b/datasketches/src/bloom/mod.rs
index 90f23ed..fd172ba 100644
--- a/datasketches/src/bloom/mod.rs
+++ b/datasketches/src/bloom/mod.rs
@@ -15,23 +15,16 @@
// specific language governing permissions and limitations
// under the License.
-//! Bloom Filter implementation for probabilistic set membership testing.
+//! Bloom filters for probabilistic set membership testing.
//!
-//! A Bloom filter is a space-efficient probabilistic data structure used to
test whether
-//! an element is a member of a set. False positive matches are possible, but
false negatives
-//! are not. In other words, a query returns either "possibly in set" or
"definitely not in set".
+//! [`BloomFilter`] tests whether an element may belong to a set with no false
negatives and a
+//! tunable false-positive probability. Unlike resizing sketches, its capacity
is fixed at
+//! construction.
//!
-//! # Properties
-//!
-//! * **No false negatives**: If an item was inserted, `contains()` will
always return `true`
-//! * **Possible false positives**: `contains()` may return `true` for items
never inserted
-//! * **Fixed size**: Unlike typical sketches, Bloom filters do not resize
automatically
-//! * **Linear space**: Size is proportional to the expected number of
distinct items
-//!
-//! Set operations transform the represented set:
[`union()`](BloomFilter::union) keeps items
-//! from either filter, and [`intersect()`](BloomFilter::intersect) keeps only
items in both.
-//! [`difference()`](BloomFilter::difference) excludes the right filter's
items exactly, but
-//! may also drop left items whose hash positions collide with the right
filter.
+//! Construct a filter via [`BloomFilterBuilder`], using
[`BloomFilterBuilder::with_accuracy`]
+//! from a target distinct-item count and false-positive probability, or
+//! [`BloomFilterBuilder::with_size`] to specify bit count and hash count
directly. Both modes
+//! accept an optional [`BloomFilterBuilder::seed`].
//!
//! # Cross-language hashing
//!
@@ -45,124 +38,47 @@
//! Skip empty strings and byte slices before inserting into the filter. For
these inputs,
//! return `false` without querying the filter, including for queries combined
with insertion.
//!
-//! # Usage
+//! # Examples
//!
//! ```
//! use datasketches::bloom::BloomFilter;
//! use datasketches::bloom::BloomFilterBuilder;
//!
-//! // Create a filter optimized for 1000 items with 1% false positive rate
//! let mut filter = BloomFilterBuilder::with_accuracy(1000, 0.01)
//! .build()
//! .unwrap();
-//!
-//! // Insert items
//! filter.insert("apple");
-//! filter.insert("banana");
//! filter.insert(42_u64);
+//! assert!(filter.contains("apple"));
+//! assert!(!filter.contains("grape"));
//!
-//! // Check membership
-//! assert!(filter.contains("apple")); // true - possibly present (and known
to be inserted here)
-//! assert!(!filter.contains("grape")); // false - definitely not present
-//!
-//! // Get statistics
-//! println!("Capacity: {} bits", filter.capacity());
-//! println!("Bits used: {}", filter.bits_used());
-//! println!("Est. FPP: {:.4}%", filter.estimated_fpp() * 100.0);
-//! ```
-//!
-//! # Creating Filters
-//!
-//! There are two ways to create a Bloom filter:
-//!
-//! ## By Accuracy (Recommended)
-//!
-//! Derive the size and number of hash functions from an expected
distinct-item count and a target
-//! false-positive probability:
-//!
-//! ```
-//! use datasketches::bloom::BloomFilterBuilder;
-//!
-//! let filter = BloomFilterBuilder::with_accuracy(
-//! 10_000, // Expected max items
-//! 0.01, // Target false positive probability (1%)
-//! )
-//! .seed(9001) // Optional: custom seed
-//! .build()
-//! .unwrap();
-//! ```
-//!
-//! `max_items` is a sizing assumption, not an insertion limit. The filter
continues accepting
-//! distinct items beyond that count, but its false-positive probability can
then exceed the target.
-//! Accuracy inputs are validated by `build`: `max_items` must be positive,
`fpp` must be in
-//! `(0.0, 1.0]`, and the requested target must fit the serialized Bloom
filter format. An `fpp` of
-//! `1.0` is accepted and creates the smallest allocation: 64 bits and one
hash function.
-//!
-//! ## By Size (Manual)
-//!
-//! Specify the requested bit count and number of hash functions. Capacity is
rounded up to a
-//! multiple of 64 bits:
-//!
-//! ```
-//! use datasketches::bloom::BloomFilterBuilder;
-//!
-//! let filter = BloomFilterBuilder::with_size(
-//! 95_851, // Number of bits
-//! 7, // Number of hash functions
-//! )
-//! .build()
-//! .unwrap();
-//! ```
-//!
-//! Manual construction requires a positive bit count supported by the
serialized format and a
-//! hash-function count in `1..=32767`. The requested bit count is rounded up
to a multiple of 64,
-//! which is the value returned by [`BloomFilter::capacity`].
-//!
-//! # Set Operations
-//!
-//! Bloom filters support efficient set operations:
-//!
-//! ```
-//! use datasketches::bloom::BloomFilterBuilder;
-//!
-//! let mut filter1 = BloomFilterBuilder::with_accuracy(100, 0.01)
+//! let manual = BloomFilterBuilder::with_size(10_000, 7)
+//! .seed(42)
//! .build()
//! .unwrap();
-//! let mut filter2 = BloomFilterBuilder::with_accuracy(100, 0.01)
+//! assert_eq!(manual.capacity(), 10_048);
+//! assert_eq!(manual.num_hashes(), 7);
+//! assert_eq!(manual.seed(), 42);
+//!
+//! let mut other = BloomFilterBuilder::with_accuracy(1000, 0.01)
//! .build()
//! .unwrap();
+//! other.insert("banana");
+//! filter.union(&other).unwrap();
+//! assert!(filter.contains("apple"));
+//! assert!(filter.contains("banana"));
//!
-//! filter1.insert("a");
-//! filter2.insert("b");
-//!
-//! // Union: recognizes items from either filter
-//! filter1.union(&filter2).unwrap();
-//! assert!(filter1.contains("a"));
-//! assert!(filter1.contains("b"));
-//!
-//! // Intersect: recognizes only items in both filters
-//! // filter1.intersect(&filter2).unwrap();
-//!
-//! // Difference: recognizes items in filter1 that are definitely not in
filter2
-//! filter1.difference(&filter2).unwrap();
-//! assert!(filter1.contains("a"));
-//! assert!(!filter1.contains("b"));
+//! let restored = BloomFilter::deserialize(&filter.serialize()).unwrap();
+//! assert_eq!(filter, restored);
//! ```
//!
-//! # Implementation Details
-//!
-//! * Derives `k` hash functions from two XXHash64 hashes using double hashing
-//! (Kirsch-Mitzenmacher).
-//! * Bits packed efficiently in `u64` words
-//! * Compatible serialization format (family ID: 21)
-//!
//! # References
//!
//! * Bloom, Burton H. (1970). "Space/time trade-offs in hash coding with
allowable errors"
//! * Kirsch and Mitzenmacher (2008). "Less Hashing, Same Performance:
Building a Better Bloom
//! Filter"
-mod sketch;
+mod filter;
-pub use self::sketch::BloomFilter;
-pub use self::sketch::BloomFilterBuilder;
+pub use self::filter::BloomFilter;
+pub use self::filter::BloomFilterBuilder;
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
deleted file mode 100644
index 59b644b..0000000
--- a/datasketches/src/bloom/sketch.rs
+++ /dev/null
@@ -1,1012 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-use std::fmt;
-use std::hash::Hash;
-use std::hash::Hasher;
-
-use crate::codec::SketchBytes;
-use crate::codec::SketchSlice;
-use crate::codec::assert::ensure_preamble_longs_in_range;
-use crate::codec::assert::ensure_serial_version_is;
-use crate::codec::assert::insufficient_data;
-use crate::codec::family::Family;
-use crate::error::Error;
-use crate::hash::DEFAULT_UPDATE_SEED;
-use crate::hash::XxHash64;
-
-// Serialization constants
-const SERIAL_VERSION: u8 = 1;
-const EMPTY_FLAG_MASK: u8 = 1 << 2;
-
-/// A Bloom filter for probabilistic set membership testing.
-///
-/// Provides fast membership queries with:
-/// * No false negatives (inserted items always return `true`)
-/// * Tunable false positive rate
-/// * Constant space usage
-///
-/// See the [module level documentation](super) for more.
-#[derive(Clone, PartialEq)]
-pub struct BloomFilter {
- /// Hash seed for all hash functions
- seed: u64,
- /// Number of hash functions (k).
- num_hashes: u16,
- /// Count of bits set to 1 (for statistics)
- num_bits_set: u64,
- /// Bit array packed into u64 words
- bit_array: Box<[u64]>,
- /// Reduces shifted hashes modulo the bit capacity; derived from
`bit_array`.
- reducer: CapacityReducer,
-}
-
-impl BloomFilter {
- /// Returns `true` if an item is possibly in the set.
- ///
- /// A `false` result means the item was definitely not inserted; a `true`
result may be a false
- /// positive.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .build()
- /// .unwrap();
- /// filter.insert("apple");
- ///
- /// assert!(filter.contains("apple")); // true - possibly present (and
known to be inserted here)
- /// assert!(!filter.contains("grape")); // false - definitely not present
- /// ```
- #[inline]
- pub fn contains<T: Hash>(&self, item: T) -> bool {
- if self.is_empty() {
- return false;
- }
-
- let (h0, h1) = self.compute_hash(item);
- self.check_bits(h0, h1)
- }
-
- /// Returns `true` if an item was possibly present before inserting it.
- ///
- /// This is more efficient than calling `contains()` then `insert()`
separately.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .build()
- /// .unwrap();
- ///
- /// let was_present = filter.contains_and_insert("apple");
- /// assert!(!was_present); // First insertion
- ///
- /// let was_present = filter.contains_and_insert("apple");
- /// assert!(was_present); // Now it's in the set
- /// ```
- #[inline]
- pub fn contains_and_insert<T: Hash>(&mut self, item: T) -> bool {
- let (h0, h1) = self.compute_hash(item);
- let num_hashes = self.num_hashes;
- let reducer = self.reducer;
- let bit_array = &mut *self.bit_array;
- let mut bits_added = 0;
- for i in 1..=num_hashes {
- let bit_index = reducer.bit_index(h0, h1, i);
- let word_index = bit_index >> 6;
- let bit_offset = bit_index & 63;
- let mask = 1u64 << bit_offset;
- let word = &mut bit_array[word_index];
-
- if (*word & mask) == 0 {
- *word |= mask;
- bits_added += 1;
- }
- }
- if bits_added != 0 {
- self.num_bits_set += bits_added;
- return false;
- }
- true
- }
-
- /// Inserts an item into the filter.
- ///
- /// After insertion, `contains(item)` will always return `true`.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .build()
- /// .unwrap();
- ///
- /// filter.insert("apple");
- /// filter.insert(42_u64);
- /// filter.insert(&[1, 2, 3]);
- ///
- /// assert!(filter.contains("apple"));
- /// ```
- #[inline]
- pub fn insert<T: Hash>(&mut self, item: T) {
- let (h0, h1) = self.compute_hash(item);
- let num_hashes = self.num_hashes;
- let reducer = self.reducer;
- let bit_array = &mut *self.bit_array;
- let mut bits_added = 0;
- for i in 1..=num_hashes {
- let bit_index = reducer.bit_index(h0, h1, i);
- let word_index = bit_index >> 6;
- let bit_offset = bit_index & 63;
- let mask = 1u64 << bit_offset;
- let word = &mut bit_array[word_index];
- let was_set = (*word & mask) != 0;
-
- *word |= mask;
- bits_added += u64::from(!was_set);
- }
- self.num_bits_set += bits_added;
- }
-
- /// Resets the filter to its initial empty state.
- ///
- /// Clears all bits while preserving capacity and configuration.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .build()
- /// .unwrap();
- /// filter.insert("apple");
- /// assert!(!filter.is_empty());
- ///
- /// filter.reset();
- /// assert!(filter.is_empty());
- /// assert!(!filter.contains("apple"));
- /// ```
- pub fn reset(&mut self) {
- self.bit_array.fill(0);
- self.num_bits_set = 0
- }
-
- /// Merges another filter into this one via bitwise OR (union).
- ///
- /// After merging, this filter will recognize items from either filter
- /// (plus any false positives from either).
- ///
- /// # Errors
- ///
- /// Returns an error if the filters are not compatible (different size,
number of hashes, or
- /// seed). Use [`is_compatible()`](Self::is_compatible) to check first
when an error is not
- /// expected.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut f1 = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(123)
- /// .build()
- /// .unwrap();
- /// let mut f2 = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(123)
- /// .build()
- /// .unwrap();
- ///
- /// f1.insert("a");
- /// f2.insert("b");
- ///
- /// f1.union(&f2).unwrap();
- /// assert!(f1.contains("a"));
- /// assert!(f1.contains("b"));
- /// ```
- pub fn union(&mut self, other: &BloomFilter) -> Result<(), Error> {
- if !self.is_compatible(other) {
- return Err(Error::invalid_argument(
- "Bloom filters must have matching capacity, number of hashes,
and seed",
- ));
- }
-
- // Count bits during union operation (single pass)
- let mut num_bits_set = 0;
- for (word, other_word) in
self.bit_array.iter_mut().zip(&other.bit_array) {
- *word |= *other_word;
- num_bits_set += word.count_ones() as u64;
- }
- self.num_bits_set = num_bits_set;
- Ok(())
- }
-
- /// Intersects this filter with another via bitwise AND.
- ///
- /// After intersection, this filter will recognize only items present in
both
- /// filters (plus false positives).
- ///
- /// # Errors
- ///
- /// Returns an error if the filters are not compatible (different size,
number of hashes, or
- /// seed).
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut f1 = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(123)
- /// .build()
- /// .unwrap();
- /// let mut f2 = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(123)
- /// .build()
- /// .unwrap();
- ///
- /// f1.insert("a");
- /// f1.insert("b");
- /// f2.insert("b");
- /// f2.insert("c");
- ///
- /// f1.intersect(&f2).unwrap();
- /// assert!(f1.contains("b")); // In both
- /// // "a" and "c" likely return false now
- /// ```
- pub fn intersect(&mut self, other: &BloomFilter) -> Result<(), Error> {
- if !self.is_compatible(other) {
- return Err(Error::invalid_argument(
- "Bloom filters must have matching capacity, number of hashes,
and seed",
- ));
- }
-
- // Count bits during intersect operation (single pass)
- let mut num_bits_set = 0;
- for (word, other_word) in
self.bit_array.iter_mut().zip(&other.bit_array) {
- *word &= *other_word;
- num_bits_set += word.count_ones() as u64;
- }
- self.num_bits_set = num_bits_set;
- Ok(())
- }
-
- /// Computes the approximate set difference with another filter via
bitwise AND-NOT.
- ///
- /// After this operation, the filter approximates the set of items
inserted into this
- /// filter but not into `other`:
- /// * Items inserted into `other` always return `false`: they are excluded
exactly.
- /// * Items inserted only into this filter keep returning `true` as long
as none of their hash
- /// positions is occupied in `other`. Unlike [`union()`](Self::union) and
- /// [`intersect()`](Self::intersect), this operation can drop items,
with a probability that
- /// grows with `other`'s load factor.
- /// * Items never inserted into this filter may return `true` (false
positives), at a rate no
- /// higher than this filter's false positive rate before the operation.
- ///
- /// This operation is also known as A NOT B.
- ///
- /// # Errors
- ///
- /// Returns an error if the filters are not compatible (different size,
number of hashes, or
- /// seed). Use [`is_compatible()`](Self::is_compatible) to check first
when an error is not
- /// expected.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut left = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(123)
- /// .build()
- /// .unwrap();
- /// let mut right = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(123)
- /// .build()
- /// .unwrap();
- ///
- /// left.insert("apple");
- /// left.insert("shared");
- /// right.insert("grape");
- /// right.insert("shared");
- ///
- /// left.difference(&right).unwrap();
- /// assert!(left.contains("apple")); // Only in the left filter
- /// assert!(!left.contains("shared")); // In both filters: excluded exactly
- /// ```
- pub fn difference(&mut self, other: &BloomFilter) -> Result<(), Error> {
- if !self.is_compatible(other) {
- return Err(Error::invalid_argument(
- "Bloom filters must have matching capacity, number of hashes,
and seed",
- ));
- }
-
- // Count bits during difference operation (single pass)
- let mut num_bits_set = 0;
- for (word, other_word) in
self.bit_array.iter_mut().zip(&other.bit_array) {
- *word &= !*other_word;
- num_bits_set += word.count_ones() as u64;
- }
- self.num_bits_set = num_bits_set;
- Ok(())
- }
-
- /// Returns `true` if no bits are set in the filter.
- ///
- /// This is the case when no items were inserted, after
[`reset()`](Self::reset), or when a
- /// set operation cleared every bit.
- #[inline]
- pub fn is_empty(&self) -> bool {
- self.num_bits_set == 0
- }
-
- /// Returns the number of bits set to 1.
- ///
- /// Useful for monitoring filter saturation.
- pub fn bits_used(&self) -> u64 {
- self.num_bits_set
- }
-
- /// Returns the total number of bits in the filter (capacity).
- pub fn capacity(&self) -> usize {
- self.bit_array.len() * 64
- }
-
- /// Returns the number of hash functions (`k`).
- ///
- /// The `k` hash functions are derived from two base hashes using double
hashing.
- /// Their bit positions may repeat.
- pub fn num_hashes(&self) -> u16 {
- self.num_hashes
- }
-
- /// Returns the hash seed.
- pub fn seed(&self) -> u64 {
- self.seed
- }
-
- /// Returns the current load factor (fraction of bits set).
- ///
- /// Values near 0.5 indicate the filter is approaching saturation.
- /// Values above 0.5 indicate degraded false positive rates.
- pub fn load_factor(&self) -> f64 {
- self.num_bits_set as f64 / self.capacity() as f64
- }
-
- /// Returns the estimated current false positive probability.
- ///
- /// Uses the approximation: `load_factor^k`
- /// where:
- /// * load_factor = fraction of bits set (bits_used / capacity)
- /// * k = num_hashes
- ///
- /// This assumes uniform bit distribution and is more accurate than
- /// trying to estimate insertion count from the load factor.
- pub fn estimated_fpp(&self) -> f64 {
- let k = self.num_hashes as f64;
- let load = self.load_factor();
-
- // FPP ≈ load^k
- // This is the standard approximation when load factor is known
directly
- load.powf(k)
- }
-
- /// Returns `true` if two filters are compatible for merging.
- ///
- /// Filters are compatible if they have the same:
- /// * Capacity (number of bits)
- /// * Number of hash functions
- /// * Seed
- pub fn is_compatible(&self, other: &Self) -> bool {
- self.bit_array.len() == other.bit_array.len()
- && self.num_hashes == other.num_hashes
- && self.seed == other.seed
- }
-
- /// Serializes the filter to a byte vector.
- ///
- /// The serialized data can be read by other DataSketches implementations.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilter;
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .build()
- /// .unwrap();
- /// filter.insert("test");
- ///
- /// let bytes = filter.serialize();
- /// let restored = BloomFilter::deserialize(&bytes).unwrap();
- /// assert!(restored.contains("test"));
- /// ```
- pub fn serialize(&self) -> Vec<u8> {
- let is_empty = self.is_empty();
- let preamble_longs = if is_empty {
- Family::BLOOMFILTER.min_pre_longs
- } else {
- Family::BLOOMFILTER.max_pre_longs
- };
-
- let capacity = 8 * preamble_longs as usize
- + if is_empty {
- 0
- } else {
- self.bit_array.len() * 8
- };
- let mut bytes = SketchBytes::with_capacity(capacity);
-
- // Preamble
- bytes.write_u8(preamble_longs); // Byte 0
- bytes.write_u8(SERIAL_VERSION); // Byte 1
- bytes.write_u8(Family::BLOOMFILTER.id); // Byte 2
- bytes.write_u8(if is_empty { EMPTY_FLAG_MASK } else { 0 }); // Byte 3:
flags
- bytes.write_u16_le(self.num_hashes); // Bytes 4-5
- bytes.write_u16_le(0); // Bytes 6-7: unused
-
- bytes.write_u64_le(self.seed);
-
- // Bit array capacity is stored as number of 64-bit words (int32) +
unused padding (uint32).
- let num_longs = self.bit_array.len() as i32;
- bytes.write_i32_le(num_longs);
- bytes.write_u32_le(0); // unused
-
- if !is_empty {
- bytes.write_u64_le(self.num_bits_set);
-
- // Bit array
- for &word in &self.bit_array {
- bytes.write_u64_le(word);
- }
- }
-
- bytes.into_bytes()
- }
-
- /// Deserializes a filter from bytes.
- ///
- /// Also accepts data serialized by other DataSketches implementations.
- ///
- /// # Errors
- ///
- /// Returns an error if:
- /// * The data is truncated or corrupted.
- /// * The family ID does not identify a Bloom filter.
- /// * The serial version is unsupported.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilter;
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let original = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .build()
- /// .unwrap();
- /// let bytes = original.serialize();
- ///
- /// let restored = BloomFilter::deserialize(&bytes).unwrap();
- /// assert_eq!(original, restored);
- /// ```
- pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> {
- let mut cursor = SketchSlice::new(bytes);
-
- // Read preamble
- let preamble_longs = cursor
- .read_u8()
- .map_err(insufficient_data("preamble_longs"))?;
- let serial_version = cursor
- .read_u8()
- .map_err(insufficient_data("serial_version"))?;
- let family_id =
cursor.read_u8().map_err(insufficient_data("family_id"))?;
-
- // Byte 3: flags byte (directly after family_id)
- let flags = cursor.read_u8().map_err(insufficient_data("flags"))?;
-
- // Validate
- Family::BLOOMFILTER.validate_id(family_id)?;
- ensure_serial_version_is(SERIAL_VERSION, serial_version)?;
- ensure_preamble_longs_in_range(
-
Family::BLOOMFILTER.min_pre_longs..=Family::BLOOMFILTER.max_pre_longs,
- preamble_longs,
- )?;
-
- let is_empty = (flags & EMPTY_FLAG_MASK) != 0;
-
- // Bytes 4-5: num_hashes (u16)
- let num_hashes = cursor
- .read_u16_le()
- .map_err(insufficient_data("num_hashes"))?;
- if num_hashes == 0 || num_hashes > i16::MAX as u16 {
- return Err(Error::deserial(format!(
- "invalid num_hashes: expected [1, {}], got {}",
- i16::MAX,
- num_hashes
- )));
- }
- // Bytes 6-7: unused (u16)
- let _unused = cursor
- .read_u16_le()
- .map_err(insufficient_data("unused_header"))?;
- let seed = cursor.read_u64_le().map_err(insufficient_data("seed"))?;
-
- // Bit array capacity is stored as number of 64-bit words (int32) +
unused padding (uint32).
- let num_longs = cursor
- .read_i32_le()
- .map_err(insufficient_data("num_longs"))?;
- let _unused =
cursor.read_u32_le().map_err(insufficient_data("unused"))?;
-
- if num_longs <= 0 {
- return Err(Error::deserial(format!(
- "invalid num_longs: expected at least 1, got {}",
- num_longs
- )));
- }
-
- let num_words = num_longs as usize;
- if !is_empty {
- let payload_bytes = num_words
- .checked_add(1)
- .and_then(|words| words.checked_mul(size_of::<u64>()))
- .ok_or_else(|| Error::deserial("Bloom filter payload length
overflows"))?;
- let available_bytes = cursor.remaining().len();
- if available_bytes < payload_bytes {
- return Err(Error::insufficient_data_of(
- "Bloom filter payload",
- format_args!("expected {payload_bytes} bytes, got
{available_bytes}"),
- ));
- }
- }
- let mut bit_array = vec![0u64; num_words].into_boxed_slice();
- let num_bits_set = if is_empty {
- 0
- } else {
- let serialized_num_bits_set = cursor
- .read_u64_le()
- .map_err(insufficient_data("num_bits_set"))?;
-
- let mut count = 0;
- for word in &mut bit_array {
- *word = cursor
- .read_u64_le()
- .map_err(insufficient_data("bit_array"))?;
- count += word.count_ones() as u64;
- }
- if serialized_num_bits_set != u64::MAX && serialized_num_bits_set
!= count {
- return Err(Error::deserial(format!(
- "invalid num_bits_set: expected {count}, got
{serialized_num_bits_set}"
- )));
- }
- count
- };
-
- Ok(BloomFilter {
- seed,
- num_hashes,
- num_bits_set,
- reducer: CapacityReducer::new(bit_array.len() as u64 * 64),
- bit_array,
- })
- }
-
- /// Computes the two base hash values using XXHash64.
- ///
- /// Uses a two-hash approach:
- /// * h0 = XXHash64(item, seed)
- /// * h1 = XXHash64(item, h0)
- #[inline]
- fn compute_hash<T: Hash>(&self, item: T) -> (u64, u64) {
- // First hash with the configured seed
- let mut hasher = XxHash64::with_seed(self.seed);
- item.hash(&mut hasher);
- let h0 = hasher.finish();
-
- // Second hash using h0 as the seed
- let mut hasher = XxHash64::with_seed(h0);
- item.hash(&mut hasher);
- let h1 = hasher.finish();
-
- (h0, h1)
- }
-
- /// Checks if all k bits are set for the given hash values.
- #[inline]
- fn check_bits(&self, h0: u64, h1: u64) -> bool {
- let num_hashes = self.num_hashes;
- let reducer = self.reducer;
- let bit_array = &*self.bit_array;
- for i in 1..=num_hashes {
- let bit_index = reducer.bit_index(h0, h1, i);
- let word_index = bit_index >> 6;
- let bit_offset = bit_index & 63;
- let mask = 1u64 << bit_offset;
- if (bit_array[word_index] & mask) == 0 {
- return false;
- }
- }
- true
- }
-
- /// Returns an estimate of the filter's memory usage in bytes.
- pub fn estimated_size(&self) -> usize {
- self.bit_array.len() * size_of::<u64>()
- }
-}
-
-impl fmt::Debug for BloomFilter {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_struct("BloomFilter")
- .field("seed", &self.seed)
- .field("num_hashes", &self.num_hashes)
- .field("capacity", &self.capacity())
- .field("bits_used", &self.num_bits_set)
- .field("is_empty", &self.is_empty())
- .finish()
- }
-}
-
-/// Reduces shifted hashes (below `2^63`) modulo the bit capacity without a
hardware division.
-#[derive(Clone, Copy, PartialEq)]
-struct CapacityReducer {
- capacity: u64,
- /// `ceil(2^(63 + l) / capacity)` with `l = ceil(log2(capacity))`.
- multiplier: u64,
- /// `l - 1`.
- shift: u32,
-}
-
-impl CapacityReducer {
- /// `capacity` is a positive multiple of 64.
- fn new(capacity: u64) -> Self {
- // `capacity > 2^(l - 1)`, so the multiplier is below `2^64`.
- let l = 64 - (capacity - 1).leading_zeros();
- let multiplier = (1u128 << (63 + l)).div_ceil(u128::from(capacity)) as
u64;
- Self {
- capacity,
- multiplier,
- shift: l - 1,
- }
- }
-
- /// Computes a bit index using double hashing (Kirsch-Mitzenmacher):
- /// `((h0 + i * h1) >> 1) % capacity`, where `i` is 1-based.
- #[inline]
- fn bit_index(self, h0: u64, h1: u64, i: u16) -> usize {
- // The conversion to `usize` truncates the hash on 32-bit targets.
Filters serialized
- // there depend on it, so it is part of the bit layout.
- let hash = h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
- self.remainder((hash >> 1) as u64) as usize
- }
-
- /// Returns `hash % capacity` for every `hash < 2^63`, using division by
an invariant integer
- /// (Granlund and Montgomery, 1994): `hash / capacity == (multiplier *
hash) >> (63 + l)`,
- /// which is one high multiply and one shift.
- #[inline]
- fn remainder(self, hash: u64) -> u64 {
- debug_assert!(hash < 1 << 63);
- let quotient =
- ((u128::from(hash) * u128::from(self.multiplier)) >> 64) as u64 >>
self.shift;
- hash - quotient * self.capacity
- }
-}
-
-/// Builder for creating [`BloomFilter`] instances.
-///
-/// Provides two construction modes:
-/// * [`with_accuracy()`](Self::with_accuracy): Specify target items and false
positive rate
-/// (recommended)
-/// * [`with_size()`](Self::with_size): Specify requested bit count and number
of hash functions
-/// (manual)
-///
-/// Configuration is stored without validation and checked when
[`build()`](Self::build) is called.
-/// Accuracy construction treats `max_items` as a sizing assumption, not an
insertion limit. The
-/// filter continues accepting items beyond that count, but its false-positive
probability can then
-/// exceed the requested target.
-#[derive(Debug, Clone)]
-pub struct BloomFilterBuilder {
- mode: BloomFilterBuilderMode,
- seed: u64,
-}
-
-#[derive(Debug, Clone)]
-enum BloomFilterBuilderMode {
- Accuracy { max_items: u64, fpp: f64 },
- Size { num_bits: u64, num_hashes: u16 },
-}
-
-impl BloomFilterBuilder {
- /// Minimum allowed requested Bloom filter size, in bits.
- const MIN_NUM_BITS: u64 = 1;
- /// Maximum allowed requested Bloom filter size, in bits.
- ///
- /// Derived from serialization limits so the encoded sketch length fits in
a signed 32-bit size
- /// field.
- const MAX_NUM_BITS: u64 = (i32::MAX as u64 -
Family::BLOOMFILTER.max_pre_longs as u64) * 64;
- /// Minimum allowed number of hash functions.
- const MIN_NUM_HASHES: u16 = 1;
- /// Maximum allowed number of hash functions.
- const MAX_NUM_HASHES: u16 = i16::MAX as u16;
-
- /// Creates a builder that derives its parameters from a target accuracy.
- ///
- /// Uses the standard Bloom filter sizing formulas to choose the requested
number of bits and
- /// hash functions. The parameters are validated when
[`build()`](Self::build) is called.
- ///
- /// `max_items` is the expected maximum number of distinct items, not a
hard insertion limit.
- /// Inserting more distinct items remains valid but can increase the
false-positive probability
- /// beyond `fpp`. An `fpp` of `1.0` is accepted and creates the smallest
allocation: 64 bits and
- /// one hash function.
- ///
- /// # Arguments
- ///
- /// * `max_items`: Maximum expected number of distinct items.
- /// * `fpp`: Target false positive probability (for example, `0.01` for
`1%`).
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// // Optimal for 10,000 items with 1% FPP
- /// let filter = BloomFilterBuilder::with_accuracy(10_000, 0.01)
- /// .seed(42)
- /// .build()
- /// .unwrap();
- /// ```
- pub fn with_accuracy(max_items: u64, fpp: f64) -> Self {
- BloomFilterBuilder {
- mode: BloomFilterBuilderMode::Accuracy { max_items, fpp },
- seed: DEFAULT_UPDATE_SEED,
- }
- }
-
- /// Creates a builder with manual size specification.
- ///
- /// Use this when you want precise control over the requested filter size,
- /// or when working with pre-calculated parameters.
- /// The parameters are validated when [`build()`](Self::build) is called.
- ///
- /// The underlying storage is word-based, so the actual capacity is rounded
- /// up to the next multiple of 64 bits.
- ///
- /// `num_bits` must be positive and fit the serialized Bloom filter
format. `num_hashes` must be
- /// in the range `1..=32767`. These constraints are checked by
[`build()`](Self::build).
- ///
- /// # Arguments
- ///
- /// * `num_bits`: Total number of bits in the filter.
- /// * `num_hashes`: Number of hash functions (`k`); see
[`BloomFilter::num_hashes`].
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let filter = BloomFilterBuilder::with_size(10_000, 7).build().unwrap();
- /// ```
- pub fn with_size(num_bits: u64, num_hashes: u16) -> Self {
- BloomFilterBuilder {
- mode: BloomFilterBuilderMode::Size {
- num_bits,
- num_hashes,
- },
- seed: DEFAULT_UPDATE_SEED,
- }
- }
-
- /// Sets a custom hash seed (default: 9001).
- ///
- /// **Important**: Filters with different seeds cannot be merged.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::bloom::BloomFilterBuilder;
- ///
- /// let filter = BloomFilterBuilder::with_accuracy(100, 0.01)
- /// .seed(12345)
- /// .build()
- /// .unwrap();
- /// ```
- pub fn seed(mut self, seed: u64) -> Self {
- self.seed = seed;
- self
- }
-
- /// Builds the Bloom filter.
- ///
- /// # Errors
- ///
- /// In accuracy mode, returns an error if `max_items` is zero, `fpp` is
outside `(0.0, 1.0]`, or
- /// the target requires more bits than the serialized format supports.
- ///
- /// In manual size mode, returns an error if `num_bits` is zero or exceeds
the serialized format
- /// limit, or if `num_hashes` is outside `1..=32767`.
- ///
- /// Valid configurations may still request more memory than the current
process can allocate.
- pub fn build(self) -> Result<BloomFilter, Error> {
- let (num_bits, num_hashes) = match self.mode {
- BloomFilterBuilderMode::Accuracy { max_items, fpp } => {
- if max_items == 0 {
- return Err(Error::invalid_argument("max_items must be
greater than 0"));
- }
- if !(fpp > 0.0 && fpp <= 1.0) {
- return Err(Error::invalid_argument("fpp must be in (0.0,
1.0]"));
- }
-
- let n = max_items as f64;
- let ln2_squared = std::f64::consts::LN_2 *
std::f64::consts::LN_2;
- let bits = (-n * fpp.ln() / ln2_squared).ceil();
- if bits > Self::MAX_NUM_BITS as f64 {
- return Err(Error::invalid_argument(format!(
- "target accuracy requires {bits:.0} bits, but at most
{} are supported",
- Self::MAX_NUM_BITS
- )));
- }
-
- let num_bits = (bits as u64).max(Self::MIN_NUM_BITS);
- let num_hashes = (num_bits as f64 / n *
std::f64::consts::LN_2).ceil().clamp(
- f64::from(Self::MIN_NUM_HASHES),
- f64::from(Self::MAX_NUM_HASHES),
- ) as u16;
- (num_bits, num_hashes)
- }
- BloomFilterBuilderMode::Size {
- num_bits,
- num_hashes,
- } => {
- if
!(Self::MIN_NUM_BITS..=Self::MAX_NUM_BITS).contains(&num_bits) {
- return Err(Error::invalid_argument(format!(
- "num_bits must be between {} and {}, got {}",
- Self::MIN_NUM_BITS,
- Self::MAX_NUM_BITS,
- num_bits
- )));
- }
- if
!(Self::MIN_NUM_HASHES..=Self::MAX_NUM_HASHES).contains(&num_hashes) {
- return Err(Error::invalid_argument(format!(
- "num_hashes must be between {} and {}, got {}",
- Self::MIN_NUM_HASHES,
- Self::MAX_NUM_HASHES,
- num_hashes
- )));
- }
- (num_bits, num_hashes)
- }
- };
- let num_words = num_bits.div_ceil(64) as usize;
- let bit_array = vec![0u64; num_words].into_boxed_slice();
-
- Ok(BloomFilter {
- seed: self.seed,
- num_hashes,
- num_bits_set: 0,
- reducer: CapacityReducer::new(bit_array.len() as u64 * 64),
- bit_array,
- })
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- /// The cached-multiplier reduction must equal the `%` operator it
replaces for every hash.
- #[test]
- fn bit_index_equals_remainder_of_shifted_hash() {
- let mut hashes = vec![
- 0,
- 1,
- 2,
- 63,
- 64,
- 65,
- u64::MAX,
- u64::MAX - 1,
- 1 << 63,
- (1 << 63) - 1,
- 0x9e37_79b9_7f4a_7c15,
- ];
- let mut state = 0x2545_f491_4f6c_dd1d_u64;
- for _ in 0..200 {
- state ^= state << 13;
- state ^= state >> 7;
- state ^= state << 17;
- hashes.push(state);
- }
-
- for num_bits in [
- 1, 64, 65, 127, 1_000, 4_096, 4_097, 95_851, 131_072, 3_000_017,
- ] {
- let filter = BloomFilterBuilder::with_size(num_bits,
1).build().unwrap();
- let capacity = filter.capacity();
- for &h0 in &hashes {
- for &h1 in &hashes {
- for i in [1, 2, 3, 7, 64, 1_000, u16::MAX] {
- let hash =
h0.wrapping_add(u64::from(i).wrapping_mul(h1)) as usize;
- assert_eq!(
- filter.reducer.bit_index(h0, h1, i),
- (hash >> 1) % capacity,
- "capacity {capacity}, h0 {h0}, h1 {h1}, i {i}"
- );
- }
- }
- }
- }
- }
-
- /// The reducer must equal `%` for every shifted hash (below `2^63`) and
every supported
- /// capacity, including capacities too large to allocate here.
- #[test]
- fn capacity_reducer_equals_remainder_for_supported_capacities() {
- let max = BloomFilterBuilder::MAX_NUM_BITS;
- let capacities = [
- 64,
- 128,
- 192,
- 4_096,
- 4_160,
- 95_872,
- 131_072,
- 3_000_064,
- 1 << 36,
- (1 << 36) + 64,
- (1 << 37) - 64,
- max - 64,
- max,
- ];
- let mut state = 0x2545_f491_4f6c_dd1d_u64;
- for capacity in capacities {
- assert_eq!(capacity % 64, 0);
- let reducer = CapacityReducer::new(capacity);
- let max_quotient = ((1u64 << 63) - 1) / capacity;
- let mut hashes = vec![
- 0,
- 1,
- capacity - 1,
- capacity,
- capacity + 1,
- max_quotient * capacity - 1,
- max_quotient * capacity,
- (1 << 63) - capacity,
- (1 << 63) - 1,
- ];
- for _ in 0..10_000 {
- state ^= state << 13;
- state ^= state >> 7;
- state ^= state << 17;
- hashes.push(state >> 1);
- }
- for hash in hashes {
- assert_eq!(
- reducer.remainder(hash),
- hash % capacity,
- "capacity {capacity}, hash {hash}"
- );
- }
- }
- }
-}
diff --git a/tests-integration/tests/bloom_test/filter.rs
b/tests-integration/tests/bloom_test/filter.rs
new file mode 100644
index 0000000..ed7dee5
--- /dev/null
+++ b/tests-integration/tests/bloom_test/filter.rs
@@ -0,0 +1,390 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use datasketches::bloom::BloomFilter;
+use datasketches::bloom::BloomFilterBuilder;
+use datasketches::error::ErrorKind;
+use datasketches::hash::value::raw_bytes;
+use googletest::assert_that;
+use googletest::prelude::ge;
+use googletest::prelude::gt;
+use googletest::prelude::le;
+
+const NUM_BITS: u64 = 65_536;
+const NUM_HASHES: u16 = 5;
+const SEED: u64 = 123;
+
+fn filter() -> BloomFilter {
+ BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED)
+ .build()
+ .unwrap()
+}
+
+fn decode_hex(input: &str) -> Vec<u8> {
+ assert_eq!(input.len() % 2, 0);
+ input
+ .as_bytes()
+ .chunks_exact(2)
+ .map(|digits| {
+ let digits = std::str::from_utf8(digits).unwrap();
+ u8::from_str_radix(digits, 16).unwrap()
+ })
+ .collect()
+}
+
+#[test]
+fn lifecycle_statistics_and_reset() {
+ let mut filter = filter();
+ let empty = filter.clone();
+ assert_eq!(filter, empty);
+ assert_eq!(filter.capacity(), NUM_BITS);
+ assert_eq!(filter.num_hashes(), NUM_HASHES);
+ assert_eq!(filter.seed(), SEED);
+ assert!(filter.is_empty());
+ assert_eq!(filter.bits_used(), 0);
+ assert_eq!(filter.load_factor(), 0.0);
+ assert_eq!(filter.estimated_fpp(), 0.0);
+ assert!(!filter.contains("apple"));
+ assert_that!(filter.estimated_size(), ge((NUM_BITS / 8) as usize));
+
+ let larger = BloomFilterBuilder::with_size(NUM_BITS * 2, NUM_HASHES)
+ .build()
+ .unwrap();
+ assert_that!(larger.estimated_size(), gt(filter.estimated_size()));
+
+ assert!(!filter.contains_and_insert("apple"));
+ assert!(filter.contains_and_insert("apple"));
+ assert!(filter.contains("apple"));
+ assert!(!filter.is_empty());
+ assert_ne!(filter, empty);
+ assert_that!(filter.bits_used(), gt(0));
+ assert_that!(filter.load_factor(), gt(0.0));
+ assert_that!(filter.estimated_fpp(), gt(0.0));
+
+ filter.reset();
+ assert_eq!(filter, empty);
+ assert!(filter.is_empty());
+ assert_eq!(filter.bits_used(), 0);
+ assert_eq!(filter.load_factor(), 0.0);
+ assert_eq!(filter.estimated_fpp(), 0.0);
+ assert!(!filter.contains("apple"));
+}
+
+#[test]
+fn insert_and_contains_and_insert_are_equivalent() {
+ let mut inserted = filter();
+ let mut checked = inserted.clone();
+
+ for value in 0..128_u64 {
+ let was_present = inserted.contains(value);
+ assert_eq!(checked.contains_and_insert(value), was_present);
+ inserted.insert(value);
+ assert!(inserted.contains(value));
+ assert_eq!(checked, inserted);
+ }
+}
+
+#[test]
+fn equivalent_borrowed_and_value_inputs_match() {
+ let owned_text = String::from("apple");
+ let owned_bytes = vec![1_u8, 2, 3, 4];
+ let ids = [7_u64, 11_u64];
+
+ let mut from_borrows = filter();
+ from_borrows.insert(&owned_text);
+ from_borrows.insert(&owned_bytes);
+ for id in &ids {
+ from_borrows.insert(id);
+ }
+ from_borrows.insert(raw_bytes::from_string(String::from("payload")));
+
+ let mut from_slices_and_values = filter();
+ assert!(!from_slices_and_values.contains_and_insert(owned_text.as_str()));
+
assert!(!from_slices_and_values.contains_and_insert(owned_bytes.as_slice()));
+ for id in ids {
+ assert!(!from_slices_and_values.contains_and_insert(id));
+ }
+
assert!(!from_slices_and_values.contains_and_insert(raw_bytes::from_str("payload")));
+
+ assert_eq!(from_borrows, from_slices_and_values);
+
+ assert!(from_borrows.contains(&owned_text));
+ assert!(from_borrows.contains(owned_text.as_str()));
+ assert!(from_borrows.contains(&owned_bytes));
+ assert!(from_borrows.contains(owned_bytes.as_slice()));
+ for id in &ids {
+ assert!(from_borrows.contains(id));
+ assert!(from_borrows.contains(*id));
+ }
+ assert!(from_borrows.contains(raw_bytes::from_slice(b"payload")));
+
+ assert!(from_slices_and_values.contains_and_insert(&owned_text));
+ assert!(from_slices_and_values.contains_and_insert(&owned_bytes));
+ assert_eq!(from_slices_and_values, from_borrows);
+}
+
+#[test]
+fn within_item_collisions_and_repeated_inserts_preserve_bit_count() {
+ // Exercise one hash and force within-item collisions: 65 hashes cannot
+ // select distinct positions in a 64-bit filter.
+ for num_hashes in [1, 65] {
+ let mut inserted = BloomFilterBuilder::with_size(64, num_hashes)
+ .build()
+ .unwrap();
+ let mut checked = inserted.clone();
+ inserted.insert(42_u64);
+ assert!(!checked.contains_and_insert(42_u64));
+
+ for filter in [&mut inserted, &mut checked] {
+ let before_repeat = filter.clone();
+ filter.insert(42_u64);
+ assert_eq!(*filter, before_repeat);
+ assert!(filter.contains_and_insert(42_u64));
+ assert_eq!(*filter, before_repeat);
+
+ // Recount the backing bits independently of either insertion path.
+ let restored =
BloomFilter::deserialize(&filter.serialize()).unwrap();
+ assert_eq!(restored, *filter);
+ assert_eq!(restored.bits_used(), filter.bits_used());
+ }
+ }
+}
+
+#[test]
+fn union_intersect_and_difference_preserve_set_semantics() {
+ let mut left = filter();
+ left.insert("shared");
+ left.insert("left");
+
+ let mut right = filter();
+ right.insert("shared");
+ right.insert("right");
+
+ let left_bits = left.bits_used();
+ let right_bits = right.bits_used();
+
+ let mut intersection = left.clone();
+ intersection.intersect(&right).unwrap();
+ assert!(intersection.contains("shared"));
+ assert_that!(intersection.bits_used(), le(left_bits));
+ assert_that!(intersection.bits_used(), le(right_bits));
+ assert_eq!(
+ BloomFilter::deserialize(&intersection.serialize()).unwrap(),
+ intersection
+ );
+
+ let mut union = left.clone();
+ union.union(&right).unwrap();
+ assert!(union.contains("shared"));
+ assert!(union.contains("left"));
+ assert!(union.contains("right"));
+ assert_that!(union.bits_used(), ge(left_bits));
+ assert_that!(union.bits_used(), ge(right_bits));
+ assert_eq!(BloomFilter::deserialize(&union.serialize()).unwrap(), union);
+
+ let mut diff_disjoint = left.clone();
+ diff_disjoint.difference(&right).unwrap();
+ assert!(diff_disjoint.contains("left"));
+ assert!(!diff_disjoint.contains("shared"));
+ assert!(!diff_disjoint.contains("right"));
+
+ let mut diff_empty = left.clone();
+ diff_empty.difference(&filter()).unwrap();
+ assert_eq!(diff_empty, left);
+
+ let mut diff_self = left.clone();
+ diff_self.difference(&left).unwrap();
+ assert!(diff_self.is_empty());
+ assert_eq!(diff_self.bits_used(), 0);
+ assert!(!diff_self.contains("shared"));
+ assert!(!diff_self.contains("left"));
+ assert_eq!(
+ BloomFilter::deserialize(&diff_self.serialize()).unwrap(),
+ diff_self
+ );
+
+ let mut bulk_left = filter();
+ let mut bulk_right = filter();
+ for i in 0..100_u64 {
+ bulk_left.insert(i);
+ bulk_right.insert(i);
+ }
+ for i in 100..200_u64 {
+ bulk_left.insert(i);
+ }
+ let bulk_left_bits = bulk_left.bits_used();
+ bulk_left.difference(&bulk_right).unwrap();
+ for i in 0..100_u64 {
+ assert!(!bulk_left.contains(i));
+ }
+ assert_that!(bulk_left.bits_used(), le(bulk_left_bits));
+ assert_eq!(
+ BloomFilter::deserialize(&bulk_left.serialize()).unwrap(),
+ bulk_left
+ );
+}
+
+#[test]
+fn compatibility_checks_and_incompatible_set_operations_are_rejected() {
+ let baseline = filter();
+ assert!(baseline.is_compatible(&filter()));
+
+ let incompatible = [
+ BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED + 1)
+ .build()
+ .unwrap(),
+ BloomFilterBuilder::with_size(NUM_BITS * 2, NUM_HASHES)
+ .seed(SEED)
+ .build()
+ .unwrap(),
+ BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES + 1)
+ .seed(SEED)
+ .build()
+ .unwrap(),
+ ];
+
+ for other in &incompatible {
+ assert!(!baseline.is_compatible(other));
+
+ let mut union = baseline.clone();
+ assert_eq!(
+ union.union(other).unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(union, baseline);
+
+ let mut intersect = baseline.clone();
+ assert_eq!(
+ intersect.intersect(other).unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(intersect, baseline);
+
+ let mut difference = baseline.clone();
+ assert_eq!(
+ difference.difference(other).unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(difference, baseline);
+ }
+}
+
+#[test]
+fn builder_validation_and_word_rounding() {
+ let builder = BloomFilterBuilder::with_size(65, 3).seed(42);
+ let _ = format!("{builder:?}");
+ let size_seeded = builder.clone().build().unwrap();
+ assert_eq!(size_seeded, builder.build().unwrap());
+ assert_eq!(size_seeded.capacity(), 128);
+ assert_eq!(size_seeded.num_hashes(), 3);
+ assert_eq!(size_seeded.seed(), 42);
+
+ let rounded = BloomFilterBuilder::with_size(65, 3).build().unwrap();
+ assert_eq!(rounded.capacity(), 128);
+ assert_eq!(rounded.num_hashes(), 3);
+ assert_eq!(rounded.seed(), 9001);
+
+ let trivial = BloomFilterBuilder::with_accuracy(100, 1.0).build().unwrap();
+ assert_eq!(trivial.capacity(), 64);
+ assert_eq!(trivial.num_hashes(), 1);
+ assert_eq!(trivial.seed(), 9001);
+
+ let acc = BloomFilterBuilder::with_accuracy(100, 0.01)
+ .build()
+ .unwrap();
+ assert_eq!(acc.seed(), 9001);
+ let acc_seeded = BloomFilterBuilder::with_accuracy(100, 0.01)
+ .seed(42)
+ .build()
+ .unwrap();
+ assert_eq!(acc_seeded.seed(), 42);
+ assert_eq!(acc_seeded.capacity(), acc.capacity());
+ assert_eq!(acc_seeded.num_hashes(), acc.num_hashes());
+ assert_eq!(
+ acc_seeded,
+ BloomFilterBuilder::with_size(acc.capacity(), acc.num_hashes())
+ .seed(42)
+ .build()
+ .unwrap()
+ );
+
+ for (max_items, fpp) in [
+ (0, 0.01),
+ (100, 0.0),
+ (100, 1.5),
+ (100, f64::NAN),
+ (u64::MAX, 0.01),
+ ] {
+ assert_eq!(
+ BloomFilterBuilder::with_accuracy(max_items, fpp)
+ .build()
+ .unwrap_err()
+ .kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(
+ BloomFilterBuilder::with_accuracy(max_items, fpp)
+ .seed(42)
+ .build()
+ .unwrap_err()
+ .kind(),
+ ErrorKind::InvalidArgument
+ );
+ }
+
+ for (num_bits, num_hashes) in [(0, 3), (u64::MAX, 3), (128, 0), (128,
32_768)] {
+ assert_eq!(
+ BloomFilterBuilder::with_size(num_bits, num_hashes)
+ .build()
+ .unwrap_err()
+ .kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(
+ BloomFilterBuilder::with_size(num_bits, num_hashes)
+ .seed(42)
+ .build()
+ .unwrap_err()
+ .kind(),
+ ErrorKind::InvalidArgument
+ );
+ }
+}
+
+#[test]
+fn serialized_bit_layout_matches_cross_language_vector() {
+ let expected = decode_hex(concat!(
+ "04011500030000002923000000000000",
+ "03000000000000000300000000000000",
+ "0000000000000000",
+ "0008080000000000",
+ "0000000400000000",
+ ));
+ let mut filter = BloomFilterBuilder::with_size(192, 3)
+ .seed(9001)
+ .build()
+ .unwrap();
+ filter.insert(0_u64);
+
+ assert_eq!(filter.serialize(), expected);
+
+ let restored = BloomFilter::deserialize(&expected).unwrap();
+ assert_eq!(restored, filter);
+ assert!(restored.contains(0_u64));
+}
diff --git a/tests-integration/tests/bloom_test/main.rs
b/tests-integration/tests/bloom_test/main.rs
index 825a628..2b29745 100644
--- a/tests-integration/tests/bloom_test/main.rs
+++ b/tests-integration/tests/bloom_test/main.rs
@@ -15,4 +15,4 @@
// specific language governing permissions and limitations
// under the License.
-mod sketch;
+mod filter;
diff --git a/tests-integration/tests/bloom_test/sketch.rs
b/tests-integration/tests/bloom_test/sketch.rs
deleted file mode 100644
index 3db1292..0000000
--- a/tests-integration/tests/bloom_test/sketch.rs
+++ /dev/null
@@ -1,339 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-use datasketches::bloom::BloomFilter;
-use datasketches::bloom::BloomFilterBuilder;
-use datasketches::error::ErrorKind;
-use datasketches::hash::value::raw_bytes;
-use googletest::assert_that;
-use googletest::prelude::ge;
-use googletest::prelude::gt;
-use googletest::prelude::le;
-
-const NUM_BITS: u64 = 65_536;
-const NUM_HASHES: u16 = 5;
-const SEED: u64 = 123;
-
-fn filter() -> BloomFilter {
- BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
- .seed(SEED)
- .build()
- .unwrap()
-}
-
-#[test]
-fn test_membership_statistics_and_reset() {
- let mut filter = filter();
- assert_eq!(filter.capacity(), NUM_BITS as usize);
- assert_eq!(filter.num_hashes(), NUM_HASHES);
- assert_eq!(filter.seed(), SEED);
- assert!(filter.is_empty());
- assert!(!filter.contains("apple"));
-
- assert!(!filter.contains_and_insert("apple"));
- assert!(filter.contains_and_insert("apple"));
- assert_that!(filter.bits_used(), gt(0));
- assert_that!(filter.load_factor(), gt(0.0));
- assert_that!(filter.estimated_fpp(), gt(0.0));
-
- filter.reset();
- assert!(filter.is_empty());
- assert_eq!(filter.bits_used(), 0);
- assert!(!filter.contains("apple"));
-}
-
-#[test]
-fn test_insert_matches_membership_and_insert() {
- let mut inserted = filter();
- let mut checked = inserted.clone();
-
- for value in 0..128_u64 {
- let was_present = inserted.contains(value);
- assert_eq!(checked.contains_and_insert(value), was_present);
- inserted.insert(value);
- assert!(inserted.contains(value));
- assert_eq!(checked, inserted);
- }
-}
-
-#[test]
-fn test_equivalent_borrowed_and_owned_inputs_match() {
- let owned_text = String::from("apple");
- let owned_bytes = vec![1_u8, 2, 3, 4];
- let ids = [7_u64, 11_u64];
-
- let mut from_borrows = filter();
- from_borrows.insert(&owned_text);
- from_borrows.insert(&owned_bytes);
- for id in &ids {
- from_borrows.insert(id);
- }
- from_borrows.insert(raw_bytes::from_string(String::from("payload")));
-
- let mut from_slices_and_values = filter();
- assert!(!from_slices_and_values.contains_and_insert(owned_text.as_str()));
-
assert!(!from_slices_and_values.contains_and_insert(owned_bytes.as_slice()));
- for id in ids {
- assert!(!from_slices_and_values.contains_and_insert(id));
- }
-
assert!(!from_slices_and_values.contains_and_insert(raw_bytes::from_str("payload")));
-
- assert_eq!(from_borrows, from_slices_and_values);
-
- assert!(from_borrows.contains(&owned_text));
- assert!(from_borrows.contains(owned_text.as_str()));
- assert!(from_borrows.contains(&owned_bytes));
- assert!(from_borrows.contains(owned_bytes.as_slice()));
- for id in &ids {
- assert!(from_borrows.contains(id));
- assert!(from_borrows.contains(*id));
- }
- assert!(from_borrows.contains(raw_bytes::from_slice(b"payload")));
-
- assert!(from_slices_and_values.contains_and_insert(&owned_text));
- assert!(from_slices_and_values.contains_and_insert(&owned_bytes));
- assert_eq!(from_slices_and_values, from_borrows);
-}
-
-#[test]
-fn test_collisions_and_repeated_inserts_do_not_overcount_bits() {
- // Exercise one hash and force within-item collisions: 65 hashes cannot
- // select distinct positions in a 64-bit filter.
- for num_hashes in [1, 65] {
- let mut inserted = BloomFilterBuilder::with_size(64, num_hashes)
- .build()
- .unwrap();
- let mut checked = inserted.clone();
- inserted.insert(42_u64);
- assert!(!checked.contains_and_insert(42_u64));
-
- for filter in [&mut inserted, &mut checked] {
- let before_repeat = filter.clone();
- filter.insert(42_u64);
- assert_eq!(*filter, before_repeat);
- assert!(filter.contains_and_insert(42_u64));
- assert_eq!(*filter, before_repeat);
-
- // Recount the backing bits independently of either insertion path.
- assert_eq!(
- BloomFilter::deserialize(&filter.serialize()).unwrap(),
- *filter
- );
- }
- }
-}
-
-#[test]
-fn test_union_and_intersection() {
- let mut left = filter();
- left.insert("shared");
- left.insert("left");
-
- let mut right = filter();
- right.insert("shared");
- right.insert("right");
-
- let left_bits = left.bits_used();
- let right_bits = right.bits_used();
-
- let mut intersection = left.clone();
- intersection.intersect(&right).unwrap();
- assert!(intersection.contains("shared"));
- let intersection_bits = intersection.bits_used();
- assert_that!(intersection_bits, le(left_bits));
- assert_that!(intersection_bits, le(right_bits));
-
- let mut union = left;
- union.union(&right).unwrap();
- assert!(union.contains("shared"));
- assert!(union.contains("left"));
- assert!(union.contains("right"));
- assert_that!(union.bits_used(), ge(left_bits));
- assert_that!(union.bits_used(), ge(right_bits));
-}
-
-#[test]
-fn test_difference_excludes_right_items_exactly() {
- let mut left = filter();
- let mut right = filter();
- for i in 0..100_u64 {
- left.insert(i);
- right.insert(i);
- }
- for i in 100..200_u64 {
- left.insert(i);
- }
-
- let left_bits = left.bits_used();
- left.difference(&right).unwrap();
-
- // Items inserted into the right filter are excluded exactly.
- for i in 0..100_u64 {
- assert!(!left.contains(i));
- }
- assert_that!(left.bits_used(), le(left_bits));
-
- // The bit count must stay consistent with the backing array.
- let restored = BloomFilter::deserialize(&left.serialize()).unwrap();
- assert_eq!(restored, left);
-}
-
-#[test]
-fn test_difference_keeps_disjoint_items() {
- let mut left = filter();
- left.insert("shared");
- left.insert("left");
-
- let mut right = filter();
- right.insert("shared");
- right.insert("right");
-
- left.difference(&right).unwrap();
- assert!(left.contains("left"));
- assert!(!left.contains("shared"));
- assert!(!left.contains("right"));
-}
-
-#[test]
-fn test_difference_with_self_clears_filter() {
- let mut left = filter();
- left.insert("apple");
- left.insert("banana");
-
- let same = left.clone();
- left.difference(&same).unwrap();
- assert!(left.is_empty());
- assert_eq!(left.bits_used(), 0);
- assert!(!left.contains("apple"));
-}
-
-#[test]
-fn test_difference_with_empty_right_is_identity() {
- let mut left = filter();
- left.insert("apple");
-
- let original = left.clone();
- left.difference(&filter()).unwrap();
- assert_eq!(left, original);
-}
-
-#[test]
-fn test_difference_rejects_incompatible_filters() {
- let mut left = filter();
- let right = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
- .seed(SEED + 1)
- .build()
- .unwrap();
- let error = left.difference(&right).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_compatibility_checks_all_configuration() {
- let baseline = filter();
- assert!(baseline.is_compatible(&filter()));
-
- let different_seed = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
- .seed(SEED + 1)
- .build()
- .unwrap();
- let different_size = BloomFilterBuilder::with_size(NUM_BITS * 2,
NUM_HASHES)
- .seed(SEED)
- .build()
- .unwrap();
- let different_hashes = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES
+ 1)
- .seed(SEED)
- .build()
- .unwrap();
-
- assert!(!baseline.is_compatible(&different_seed));
- assert!(!baseline.is_compatible(&different_size));
- assert!(!baseline.is_compatible(&different_hashes));
-}
-
-#[test]
-fn test_union_rejects_incompatible_filters() {
- let mut left = filter();
- let right = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
- .seed(SEED + 1)
- .build()
- .unwrap();
- let error = left.union(&right).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_intersection_rejects_incompatible_filters() {
- let mut left = filter();
- let right = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
- .seed(SEED + 1)
- .build()
- .unwrap();
- let error = left.intersect(&right).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_requested_size_rounds_to_word_boundary() {
- let filter = BloomFilterBuilder::with_size(65, 3).build().unwrap();
- assert_eq!(filter.capacity(), 128);
-}
-
-#[test]
-fn test_accuracy_builder_rejects_zero_items_at_build() {
- let error = BloomFilterBuilder::with_accuracy(0, 0.01)
- .build()
- .unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_accuracy_builder_rejects_invalid_probability_at_build() {
- for fpp in [0.0, 1.5, f64::NAN] {
- let error = BloomFilterBuilder::with_accuracy(100, fpp)
- .build()
- .unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
- }
-}
-
-#[test]
-fn test_accuracy_builder_accepts_one_probability() {
- let filter = BloomFilterBuilder::with_accuracy(100, 1.0).build().unwrap();
- assert_eq!(filter.capacity(), 64);
- assert_eq!(filter.num_hashes(), 1);
-}
-
-#[test]
-fn test_size_builder_rejects_zero_bits_at_build() {
- let error = BloomFilterBuilder::with_size(0, 3).build().unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_size_builder_rejects_zero_hashes_at_build() {
- let error = BloomFilterBuilder::with_size(128, 0).build().unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
-
-#[test]
-fn test_accuracy_builder_rejects_unrepresentable_target() {
- let error = BloomFilterBuilder::with_accuracy(u64::MAX, 0.01)
- .build()
- .unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
-}
diff --git a/tests-integration/tests/serde_tests/bloom.rs
b/tests-integration/tests/serde_tests/bloom.rs
index fe35297..2931e55 100644
--- a/tests-integration/tests/serde_tests/bloom.rs
+++ b/tests-integration/tests/serde_tests/bloom.rs
@@ -20,6 +20,7 @@ use std::path::PathBuf;
use datasketches::bloom::BloomFilter;
use datasketches::bloom::BloomFilterBuilder;
+use datasketches::error::ErrorKind;
use googletest::assert_that;
use googletest::prelude::gt;
@@ -137,7 +138,10 @@ fn test_cached_num_bits_set_is_validated_or_recomputed() {
bytes[NUM_BITS_SET_OFFSET..NUM_BITS_SET_OFFSET + size_of::<u64>()]
.copy_from_slice(&serialized_count.to_le_bytes());
- assert!(BloomFilter::deserialize(&bytes).is_err());
+ assert_eq!(
+ BloomFilter::deserialize(&bytes).unwrap_err().kind(),
+ ErrorKind::InvalidData
+ );
}
let mut dirty = filter.serialize();
@@ -150,16 +154,25 @@ fn test_cached_num_bits_set_is_validated_or_recomputed() {
}
#[test]
-fn test_nonempty_payload_length_is_checked_before_allocating() {
+fn test_invalid_num_longs_are_rejected() {
const NUM_LONGS_OFFSET: usize = 16;
- let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ let empty = BloomFilterBuilder::with_accuracy(100, 0.01)
.build()
.unwrap();
- filter.insert("apple");
- let mut bytes = filter.serialize();
- bytes[NUM_LONGS_OFFSET..NUM_LONGS_OFFSET + size_of::<i32>()]
- .copy_from_slice(&i32::MAX.to_le_bytes());
-
- assert!(BloomFilter::deserialize(&bytes).is_err());
+ let mut non_empty = empty.clone();
+ non_empty.insert("apple");
+
+ for base in [empty.serialize(), non_empty.serialize()] {
+ for num_longs in [0_i32, -1, i32::MAX] {
+ let mut corrupted = base.clone();
+ corrupted[NUM_LONGS_OFFSET..NUM_LONGS_OFFSET + size_of::<i32>()]
+ .copy_from_slice(&num_longs.to_le_bytes());
+
+ assert_eq!(
+ BloomFilter::deserialize(&corrupted).unwrap_err().kind(),
+ ErrorKind::InvalidData
+ );
+ }
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]