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 6043d16 feat(xor): polish builder chaining and fix duplicate-hash
detection (#362)
6043d16 is described below
commit 6043d16fd526e023090794a2f0908ef0be4ee78a
Author: tison <[email protected]>
AuthorDate: Sun Nov 15 11:50:18 2026 +0800
feat(xor): polish builder chaining and fix duplicate-hash detection (#362)
* feat(xor): polish builder chaining, duplicate detection, and filter
accessors
Refine the `xor` module API and duplicate detection during construction:
- Return `&mut Self` from `XorFilterBuilder::{update, update_hash,
update_values, update_hashes}`, add `XorFilterBuilder::seed`, and change
`XorFilterBuilder::build` to borrow `&mut self` so callers can both chain
single-expression construction and reseed or reuse accumulated hashes across
builds.
- Add `XorFilter::seed` and `XorFilter::capacity` accessors (including
`capacity` in `Debug` output), rename `keys` to `hashes` in `from_hashes*`, and
annotate `XorFilterType`, `XorFilterBuilder`, `XorFilter`, and pure
query/serialization methods with `#[must_use]`.
- Replace the degree-2 XOR cancellation check in
`XorFilter::from_hashes_with_seed` with a fallback sort-and-adjacent-scan check
on `stack_hash` when attempt `0` fails to peel, detecting duplicates of any
multiplicity (including odd counts such as 3) immediately without penalizing
the fast first-attempt path.
- Clarify docstrings and examples across `datasketches/src/xor/`, and add
integration tests covering builder chaining, reseeding, multiplicity-3 and -4
duplicate rejection, and `seed()`/`capacity()` round-trips.
* refactor(xor): use owned XorFilterBuilder chaining and drop redundant
getters
Switch `XorFilterBuilder` methods (`seed`, `update`, `update_hash`,
`update_values`, and `update_hashes`) to take and return `Self` by value
alongside a consuming `build(mut self)`, and remove the redundant
`XorFilterBuilder::with_seed` constructor in favor of `.seed(...)`. This aligns
`XorFilterBuilder` with every other builder in the crate, lets `#[must_use]`
catch dropped chains at compile time, and drops accumulated hashes once built.
Remove `XorFilter::seed` and `XorFilter::capacity` along with the
`capacity` field from `XorFilter`'s `Debug` implementation, since `XorFilter`
is immutable, does not support set operations across instances, and stores an
internal winning SplitMix64 mixing seed rather than a user-supplied input hash
seed.
Update examples, doctests, benchmarks, and integration tests accordingly.
* refactor(xor): hoist initial peel attempt and defer duplicate check to
failure
Hoist the initial peeling attempt ahead of the retry loop in
`XorFilter::from_hashes_with_seed`, removing the `attempt != 0` branch inside
the loop as well as placeholder zero-initializations for `construction_seed`
and `stack_size`.
Defer the `sort_unstable` duplicate-hash check on `stack_hash` until all
`MAX_CONSTRUCTION_ATTEMPTS` peeling attempts fail, so valid distinct inputs
that require a retry do not pay sorting overhead while invalid duplicate inputs
of any multiplicity are still accurately rejected instead of reporting layout
failure.
Simplify the `XorFilter::from_hashes` and
`XorFilter::from_hashes_with_seed` docstrings to point callers with duplicate
or unhashed inputs directly to `XorFilterBuilder`.
---
benchmarks/xor/build.rs | 27 +++--
datasketches/src/xor/filter.rs | 187 ++++++++++++++++++-----------
datasketches/src/xor/mod.rs | 7 +-
tests-integration/tests/serde_tests/xor.rs | 12 +-
tests-integration/tests/xor_test/filter.rs | 140 ++++++++++++++++-----
5 files changed, 254 insertions(+), 119 deletions(-)
diff --git a/benchmarks/xor/build.rs b/benchmarks/xor/build.rs
index 05b1945..ec92ab5 100644
--- a/benchmarks/xor/build.rs
+++ b/benchmarks/xor/build.rs
@@ -43,9 +43,12 @@ fn xorf_distinct_8(bencher: Bencher, cardinality: usize) {
fn deduplicate_8(bencher: Bencher, rows: usize) {
let keys = repeated_hashes(rows);
bencher.bench_local(|| {
- let mut builder = XorFilterBuilder::new(XorFilterType::Xor8);
- builder.update_hashes(keys.iter().copied());
- black_box(builder.build().unwrap())
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor8)
+ .update_hashes(keys.iter().copied())
+ .build()
+ .unwrap(),
+ )
});
}
@@ -73,9 +76,12 @@ fn xorf_distinct_16(bencher: Bencher, cardinality: usize) {
fn deduplicate_16(bencher: Bencher, rows: usize) {
let keys = repeated_hashes(rows);
bencher.bench_local(|| {
- let mut builder = XorFilterBuilder::new(XorFilterType::Xor16);
- builder.update_hashes(keys.iter().copied());
- black_box(builder.build().unwrap())
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor16)
+ .update_hashes(keys.iter().copied())
+ .build()
+ .unwrap(),
+ )
});
}
@@ -103,9 +109,12 @@ fn xorf_distinct_32(bencher: Bencher, cardinality: usize) {
fn deduplicate_32(bencher: Bencher, rows: usize) {
let keys = repeated_hashes(rows);
bencher.bench_local(|| {
- let mut builder = XorFilterBuilder::new(XorFilterType::Xor32);
- builder.update_hashes(keys.iter().copied());
- black_box(builder.build().unwrap())
+ black_box(
+ XorFilterBuilder::new(XorFilterType::Xor32)
+ .update_hashes(keys.iter().copied())
+ .build()
+ .unwrap(),
+ )
});
}
diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
index d3d984d..a812d18 100644
--- a/datasketches/src/xor/filter.rs
+++ b/datasketches/src/xor/filter.rs
@@ -45,6 +45,7 @@ const SPLITMIX_MUL1: u64 = 0xbf58_476d_1ce4_e5b9;
const SPLITMIX_MUL2: u64 = 0x94d0_49bb_1331_11eb;
/// Fingerprint representation used by an [`XorFilter`].
+#[must_use]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum XorFilterType {
/// Uses 8-bit fingerprints and has an expected false-positive probability
of about `2^-8`.
@@ -199,10 +200,12 @@ impl Fingerprints {
/// An [`XorFilter`] builder for values or precomputed hashes.
///
+/// Accumulated hashes are sorted and deduplicated when [`build`](Self::build)
is called.
/// Query values with [`XorFilter::contains`] and precomputed hashes with
/// [`XorFilter::contains_hash`].
///
/// See the [module level documentation](super) for more.
+#[must_use]
#[derive(Clone)]
pub struct XorFilterBuilder {
filter_type: XorFilterType,
@@ -225,48 +228,69 @@ impl XorFilterBuilder {
///
/// Values are hashed independently of the construction seed.
pub fn new(filter_type: XorFilterType) -> Self {
- Self::with_seed(filter_type, DEFAULT_CONSTRUCTION_SEED)
- }
-
- /// Creates a builder with the given fingerprint width and initial
construction seed.
- ///
- /// The `seed` determines which layouts to try during construction. Values
are hashed
- /// independently of it.
- pub fn with_seed(filter_type: XorFilterType, seed: u64) -> Self {
Self {
filter_type,
- seed,
+ seed: DEFAULT_CONSTRUCTION_SEED,
hashes: Vec::new(),
}
}
- /// Adds a value.
+ /// Sets the initial construction seed used by [`build`](Self::build)
(default: `0`).
+ ///
+ /// The `seed` determines which layouts to try during construction. Values
are hashed
+ /// independently of this construction seed.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::xor::XorFilterBuilder;
+ /// use datasketches::xor::XorFilterType;
+ ///
+ /// let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+ /// .seed(42)
+ /// .update_values(["apple", "banana"])
+ /// .build()
+ /// .unwrap();
+ /// assert!(filter.contains("apple"));
+ /// ```
+ #[inline]
+ pub fn seed(mut self, seed: u64) -> Self {
+ self.seed = seed;
+ self
+ }
+
+ /// Adds a value to the builder.
#[inline]
- pub fn update<T: Hash>(&mut self, item: T) {
- self.update_hash(hash_item(item));
+ pub fn update<T: Hash>(self, item: T) -> Self {
+ self.update_hash(hash_item(item))
}
- /// Adds a precomputed 64-bit hash.
+ /// Adds a precomputed 64-bit hash to the builder.
#[inline]
- pub fn update_hash(&mut self, hash: u64) {
+ pub fn update_hash(mut self, hash: u64) -> Self {
self.hashes.push(hash);
+ self
}
- /// Adds a batch of values.
- pub fn update_values<T: Hash>(&mut self, items: impl IntoIterator<Item =
T>) {
- self.update_hashes(items.into_iter().map(hash_item));
+ /// Adds a batch of values to the builder.
+ pub fn update_values<T: Hash>(self, items: impl IntoIterator<Item = T>) ->
Self {
+ self.update_hashes(items.into_iter().map(hash_item))
}
- /// Adds a batch of precomputed 64-bit hashes.
- pub fn update_hashes(&mut self, hashes: impl IntoIterator<Item = u64>) {
+ /// Adds a batch of precomputed 64-bit hashes to the builder.
+ pub fn update_hashes(mut self, hashes: impl IntoIterator<Item = u64>) ->
Self {
self.hashes.extend(hashes);
+ self
}
- /// Consumes the builder and creates the filter.
+ /// Consumes the builder, sorts and deduplicates accumulated hashes, and
creates an
+ /// [`XorFilter`].
///
/// # Errors
///
- /// Returns an error if the input is too large or no valid layout is found.
+ /// Returns [`InvalidArgument`](crate::error::ErrorKind::InvalidArgument)
if the distinct
+ /// input is too large or construction cannot find a valid layout within
`100` internal
+ /// seed attempts.
pub fn build(mut self) -> Result<XorFilter, Error> {
self.hashes.sort_unstable();
self.hashes.dedup();
@@ -282,6 +306,7 @@ impl XorFilterBuilder {
/// changes.
///
/// See the [module level documentation](super) for more.
+#[must_use]
#[derive(Clone, PartialEq, Eq)]
pub struct XorFilter {
// Cache the derived length to avoid division on every query.
@@ -294,8 +319,12 @@ impl XorFilter {
/// Creates a filter from distinct precomputed 64-bit hashes using the
default construction
/// seed (`0`).
///
- /// The same set of hashes and filter type produce the same filter
regardless of input order.
- /// Query with [`contains_hash`](Self::contains_hash) using the same hash
function.
+ /// Use [`XorFilterBuilder`] instead when inputs may contain duplicates or
unhashed values.
+ ///
+ /// Starting from seed `0`, construction tries up to `100` internal mixing
seeds derived from
+ /// it until it finds a valid peeling layout. The same set of distinct
hashes and filter type
+ /// produce the same filter regardless of input order. Query with
+ /// [`contains_hash`](Self::contains_hash) using the same hash function.
///
/// # Errors
///
@@ -303,17 +332,20 @@ impl XorFilter {
///
/// - The input contains duplicate hashes.
/// - The input is too large to build a filter.
- /// - Construction cannot find a valid layout. For distinct hashes, try
another seed with
- /// [`from_hashes_with_seed`](Self::from_hashes_with_seed).
- pub fn from_hashes(keys: &[u64], filter_type: XorFilterType) ->
Result<Self, Error> {
- Self::from_hashes_with_seed(keys, filter_type,
DEFAULT_CONSTRUCTION_SEED)
+ /// - Construction cannot find a valid layout within `100` internal seed
attempts. For distinct
+ /// hashes, try another seed with
[`from_hashes_with_seed`](Self::from_hashes_with_seed).
+ pub fn from_hashes(hashes: &[u64], filter_type: XorFilterType) ->
Result<Self, Error> {
+ Self::from_hashes_with_seed(hashes, filter_type,
DEFAULT_CONSTRUCTION_SEED)
}
/// Creates a filter from distinct precomputed 64-bit hashes and an
explicit construction seed.
///
- /// The initial `seed` determines which layouts to try during
construction. The same set of
- /// hashes, filter type, and seed produce the same filter regardless of
input order.
- /// Query with [`contains_hash`](Self::contains_hash) using the same hash
function.
+ /// Use [`XorFilterBuilder`] instead when inputs may contain duplicates or
unhashed values.
+ ///
+ /// Starting from `seed`, construction tries up to `100` internal mixing
seeds derived from it
+ /// until it finds a valid peeling layout. The same set of distinct
hashes, filter type, and
+ /// initial `seed` produce the same filter regardless of input order.
Query with
+ /// [`contains_hash`](Self::contains_hash) using the same hash function.
///
/// # Errors
///
@@ -321,13 +353,14 @@ impl XorFilter {
///
/// - The input contains duplicate hashes.
/// - The input is too large to build a filter.
- /// - Construction cannot find a valid layout. For distinct hashes, try
another `seed`.
+ /// - Construction cannot find a valid layout within `100` internal seed
attempts. For distinct
+ /// hashes, try another `seed`.
pub fn from_hashes_with_seed(
- keys: &[u64],
+ hashes: &[u64],
filter_type: XorFilterType,
seed: u64,
) -> Result<Self, Error> {
- let num_items = keys.len();
+ let num_items = hashes.len();
let capacity = compute_capacity(num_items)?;
let segment_length = capacity / usize::from(NUM_HASHES);
let mut xor_mask = vec![0_u64; capacity];
@@ -337,44 +370,54 @@ impl XorFilter {
let mut stack_hash = vec![0_u64; num_items];
let mut stack_index = vec![0_u32; num_items];
- let mut rng_state = seed;
- let mut construction_seed = 0;
- let mut stack_size = 0;
- for attempt in 0..MAX_CONSTRUCTION_ATTEMPTS {
- if attempt != 0 {
+ let mut rng_state = seed.wrapping_add(SPLITMIX_GAMMA);
+ let mut construction_seed = splitmix64(rng_state);
+ let mut stack_size = map(
+ hashes,
+ construction_seed,
+ segment_length,
+ &mut xor_mask,
+ &mut count,
+ &mut queue,
+ &mut stack_hash,
+ &mut stack_index,
+ );
+ if stack_size != num_items {
+ for _ in 1..MAX_CONSTRUCTION_ATTEMPTS {
xor_mask.fill(0);
count.fill(0);
- }
- rng_state = rng_state.wrapping_add(SPLITMIX_GAMMA);
- construction_seed = splitmix64(rng_state);
- stack_size = map(
- keys,
- construction_seed,
- segment_length,
- &mut xor_mask,
- &mut count,
- &mut queue,
- &mut stack_hash,
- &mut stack_index,
- );
- if stack_size == num_items {
- break;
- }
- // For a fixed seed, mixing is a bijection, so two remaining
hashes that cancel
- // out are the same input hash. Reseeding cannot separate
duplicates.
- if count.iter().zip(&xor_mask).any(|(&c, &m)| c == 2 && m == 0) {
- return Err(
- Error::invalid_argument("xor filter input contains
duplicate hashes")
- .with_context("num_items", num_items),
+ rng_state = rng_state.wrapping_add(SPLITMIX_GAMMA);
+ construction_seed = splitmix64(rng_state);
+ stack_size = map(
+ hashes,
+ construction_seed,
+ segment_length,
+ &mut xor_mask,
+ &mut count,
+ &mut queue,
+ &mut stack_hash,
+ &mut stack_index,
);
+ if stack_size == num_items {
+ break;
+ }
+ }
+ if stack_size != num_items {
+ // Any duplicate hash prevents full peeling regardless of
multiplicity; sort after
+ // all attempts fail so valid distinct inputs never pay
sorting overhead on retry.
+ stack_hash.copy_from_slice(hashes);
+ stack_hash.sort_unstable();
+ if stack_hash.windows(2).any(|w| w[0] == w[1]) {
+ return Err(Error::invalid_argument(
+ "xor filter input contains duplicate hashes",
+ )
+ .with_context("num_items", num_items));
+ }
+ return Err(Error::invalid_argument(
+ "xor filter construction could not find a valid layout",
+ )
+ .with_context("num_items", num_items));
}
- }
-
- if stack_size != num_items {
- return Err(Error::invalid_argument(
- "xor filter construction could not find a valid layout",
- )
- .with_context("num_items", num_items));
}
// Assignment only needs the peel stack. Release the graph before
allocating the
@@ -402,6 +445,7 @@ impl XorFilter {
///
/// A `false` result means the item was definitely absent; a `true` result
may be a false
/// positive.
+ #[must_use]
#[inline]
pub fn contains<T: Hash>(&self, item: T) -> bool {
self.contains_hash(hash_item(item))
@@ -411,6 +455,7 @@ impl XorFilter {
///
/// Use the same hash function for construction and queries.
// Inline through Fingerprints::contains so width dispatch stays in the
caller's hot loop.
+ #[must_use]
#[inline(always)]
pub fn contains_hash(&self, hash: u64) -> bool {
let mixed = mix(hash, self.seed);
@@ -423,11 +468,13 @@ impl XorFilter {
}
/// Returns the estimated in-memory size of the filter in bytes.
+ #[must_use]
pub fn estimated_size(&self) -> usize {
size_of::<Self>() + self.fingerprints.byte_len()
}
/// Serializes the filter in the DataSketches format.
+ #[must_use]
pub fn serialize(&self) -> Vec<u8> {
let mut bytes = SketchBytes::with_capacity(PREAMBLE_BYTES +
self.fingerprints.byte_len());
@@ -563,7 +610,7 @@ fn compute_capacity(num_items: usize) -> Result<usize,
Error> {
}
fn map(
- keys: &[u64],
+ hashes: &[u64],
seed: u64,
segment_length: usize,
xor_mask: &mut [u64],
@@ -579,8 +626,8 @@ fn map(
let mut queues = split_segments(queue, segment_length + 1);
// Reuse the peel stack for mixed hashes while mapping one segment at a
time.
// This bounds the random-access working set without allocating another
buffer.
- for (&key, hash) in keys.iter().zip(stack_hash.iter_mut()) {
- *hash = mix(key, seed);
+ for (&raw_hash, mixed_slot) in hashes.iter().zip(stack_hash.iter_mut()) {
+ *mixed_slot = mix(raw_hash, seed);
}
for block in 0..3 {
for &hash in stack_hash.iter() {
diff --git a/datasketches/src/xor/mod.rs b/datasketches/src/xor/mod.rs
index 2d33090..cb949bc 100644
--- a/datasketches/src/xor/mod.rs
+++ b/datasketches/src/xor/mod.rs
@@ -41,9 +41,10 @@
//! use datasketches::xor::XorFilterBuilder;
//! use datasketches::xor::XorFilterType;
//!
-//! let mut builder = XorFilterBuilder::new(XorFilterType::Xor8);
-//! builder.update_values(["apple", "banana"]);
-//! let filter = builder.build().unwrap();
+//! let filter = XorFilterBuilder::new(XorFilterType::Xor8)
+//! .update_values(["apple", "banana"])
+//! .build()
+//! .unwrap();
//!
//! assert!(filter.contains("apple"));
//! ```
diff --git a/tests-integration/tests/serde_tests/xor.rs
b/tests-integration/tests/serde_tests/xor.rs
index d66553a..cbff98e 100644
--- a/tests-integration/tests/serde_tests/xor.rs
+++ b/tests-integration/tests/serde_tests/xor.rs
@@ -41,9 +41,11 @@ fn java_images_round_trip_byte_for_byte() {
(XorFilterType::Xor16, JAVA_XOR16_IMAGE),
] {
let expected = decode_hex(image);
- let mut builder = XorFilterBuilder::with_seed(ty, 42);
- builder.update_values(values);
- let built = builder.build().unwrap();
+ let built = XorFilterBuilder::new(ty)
+ .seed(42)
+ .update_values(values)
+ .build()
+ .unwrap();
let restored = XorFilter::deserialize(&expected).unwrap();
assert_eq!(restored.filter_type(), ty);
@@ -183,9 +185,9 @@ fn java_utf8_and_raw_byte_inputs_match() {
),
];
for (kind, image) in images {
- let mut builder = XorFilterBuilder::with_seed(kind, 42);
+ let mut builder = XorFilterBuilder::new(kind).seed(42);
for bytes in [b"hello".as_slice(), "数据🔎".as_bytes(), &[], &[0, 1,
255]] {
- builder.update(raw_bytes::from_slice(bytes));
+ builder = builder.update(raw_bytes::from_slice(bytes));
}
let built = builder.build().unwrap();
let expected = decode_hex(image);
diff --git a/tests-integration/tests/xor_test/filter.rs
b/tests-integration/tests/xor_test/filter.rs
index 3711155..c0bb974 100644
--- a/tests-integration/tests/xor_test/filter.rs
+++ b/tests-integration/tests/xor_test/filter.rs
@@ -23,9 +23,9 @@ use datasketches::xor::XorFilterType;
#[test]
fn values_have_no_false_negatives() {
- let mut builder = XorFilterBuilder::with_seed(XorFilterType::Xor8, 8123);
+ let mut builder = XorFilterBuilder::new(XorFilterType::Xor8).seed(8123);
for value in 0..10_000_u64 {
- builder.update(value);
+ builder = builder.update(value);
}
let filter = builder.build().unwrap();
assert_eq!(filter.filter_type(), XorFilterType::Xor8);
@@ -61,20 +61,18 @@ fn builder_deduplicates_values_and_hashes() {
XorFilterType::Xor16,
XorFilterType::Xor32,
] {
- let mut duplicate_values = XorFilterBuilder::new(ty);
- duplicate_values.update(7_u64);
- duplicate_values.update_values([11_u64, 7, 11]);
-
- let mut distinct_values = XorFilterBuilder::new(ty);
- distinct_values.update_values([11_u64, 7]);
+ let duplicate_values = XorFilterBuilder::new(ty)
+ .update(7_u64)
+ .update_values([11_u64, 7, 11]);
+ let distinct_values = XorFilterBuilder::new(ty).update_values([11_u64,
7]);
assert_eq!(
duplicate_values.build().unwrap(),
distinct_values.build().unwrap(),
);
- let mut hashes = XorFilterBuilder::new(ty);
- hashes.update_hash(7);
- hashes.update_hashes([11, 7, 11]);
+ let hashes = XorFilterBuilder::new(ty)
+ .update_hash(7)
+ .update_hashes([11, 7, 11]);
assert_eq!(
hashes.build().unwrap(),
XorFilter::from_hashes(&[7, 11], ty).unwrap(),
@@ -89,18 +87,18 @@ fn
default_seed_constructors_and_builder_clone_behave_consistently() {
XorFilterType::Xor16,
XorFilterType::Xor32,
] {
- let mut default_builder = XorFilterBuilder::new(ty);
- default_builder.update_values([1_u64, 2, 3]);
+ let default_builder = XorFilterBuilder::new(ty).update_values([1_u64,
2, 3]);
let cloned_builder = default_builder.clone();
- default_builder.update(4_u64);
+ let extended_builder = default_builder.update(4_u64);
- let mut zero_seeded_builder = XorFilterBuilder::with_seed(ty, 0);
- zero_seeded_builder.update_values([1_u64, 2, 3]);
+ let zero_seeded_builder = XorFilterBuilder::new(ty)
+ .seed(0)
+ .update_values([1_u64, 2, 3]);
let cloned_filter = cloned_builder.build().unwrap();
assert_eq!(cloned_filter, zero_seeded_builder.build().unwrap());
assert_eq!(cloned_filter.filter_type(), ty);
- assert_ne!(cloned_filter, default_builder.build().unwrap());
+ assert_ne!(cloned_filter, extended_builder.build().unwrap());
assert_eq!(
XorFilter::from_hashes(&[10, 20, 30], ty).unwrap(),
@@ -122,10 +120,10 @@ fn
equivalent_borrowed_and_value_inputs_build_identical_filters() {
] {
let mut by_str_update = XorFilterBuilder::new(ty);
for s in &strings {
- by_str_update.update(s);
+ by_str_update = by_str_update.update(s);
}
- let mut by_str_batch = XorFilterBuilder::new(ty);
- by_str_batch.update_values(strings.iter().map(String::as_str));
+ let by_str_batch =
+
XorFilterBuilder::new(ty).update_values(strings.iter().map(String::as_str));
let str_filter = by_str_update.build().unwrap();
assert_eq!(str_filter, by_str_batch.build().unwrap());
for s in &strings {
@@ -135,10 +133,10 @@ fn
equivalent_borrowed_and_value_inputs_build_identical_filters() {
let mut by_blob_update = XorFilterBuilder::new(ty);
for blob in &blobs {
- by_blob_update.update(blob);
+ by_blob_update = by_blob_update.update(blob);
}
- let mut by_blob_batch = XorFilterBuilder::new(ty);
- by_blob_batch.update_values(blobs.iter().map(Vec::as_slice));
+ let by_blob_batch =
+
XorFilterBuilder::new(ty).update_values(blobs.iter().map(Vec::as_slice));
let blob_filter = by_blob_update.build().unwrap();
assert_eq!(blob_filter, by_blob_batch.build().unwrap());
for blob in &blobs {
@@ -148,12 +146,12 @@ fn
equivalent_borrowed_and_value_inputs_build_identical_filters() {
let mut by_mixed_update = XorFilterBuilder::new(ty);
for id in &ids {
- by_mixed_update.update(id);
+ by_mixed_update = by_mixed_update.update(id);
}
-
by_mixed_update.update(raw_bytes::from_string(String::from("payload")));
- let mut by_mixed_batch = XorFilterBuilder::new(ty);
- by_mixed_batch.update_values(ids);
- by_mixed_batch.update(raw_bytes::from_str("payload"));
+ by_mixed_update =
by_mixed_update.update(raw_bytes::from_string(String::from("payload")));
+ let by_mixed_batch = XorFilterBuilder::new(ty)
+ .update_values(ids)
+ .update(raw_bytes::from_str("payload"));
let mixed_filter = by_mixed_update.build().unwrap();
assert_eq!(mixed_filter, by_mixed_batch.build().unwrap());
for id in &ids {
@@ -206,9 +204,22 @@ fn
distinct_construction_is_bounded_and_does_not_deduplicate() {
XorFilterType::Xor16,
XorFilterType::Xor32,
] {
- let error = XorFilter::from_hashes(&[1, 2, 1], kind).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
- assert!(error.message().contains("duplicate hashes"));
+ for duplicate_hashes in [
+ [1_u64, 2, 1].as_slice(),
+ &[1, 1, 1],
+ &[1, 2, 1, 3, 1],
+ &[1, 1, 1, 1],
+ ] {
+ let error = XorFilter::from_hashes(duplicate_hashes,
kind).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ assert!(error.message().contains("duplicate hashes"));
+
+ let seeded_error =
+ XorFilter::from_hashes_with_seed(duplicate_hashes, kind,
42).unwrap_err();
+ assert_eq!(seeded_error.kind(), ErrorKind::InvalidArgument);
+ assert!(seeded_error.message().contains("duplicate hashes"));
+ }
+
for keys in [vec![], vec![0], vec![u64::MAX], vec![0, u64::MAX]] {
let f = XorFilter::from_hashes(&keys, kind).unwrap();
for key in keys {
@@ -218,6 +229,61 @@ fn
distinct_construction_is_bounded_and_does_not_deduplicate() {
}
}
+#[test]
+fn builder_chaining_and_seed_override_behave_consistently() {
+ for ty in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let chained = XorFilterBuilder::new(ty)
+ .seed(42)
+ .update("alpha")
+ .update_hash(99)
+ .update_values(["beta", "gamma"])
+ .update_hashes([100, 101])
+ .build()
+ .unwrap();
+
+ let mut step_by_step = XorFilterBuilder::new(ty).seed(42);
+ step_by_step = step_by_step.update("alpha");
+ step_by_step = step_by_step.update_hash(99);
+ step_by_step = step_by_step.update_values(["beta", "gamma"]);
+ step_by_step = step_by_step.update_hashes([100, 101]);
+ assert_eq!(chained, step_by_step.build().unwrap());
+
+ for value in ["alpha", "beta", "gamma"] {
+ assert!(chained.contains(value));
+ }
+ for hash in [99, 100, 101] {
+ assert!(chained.contains_hash(hash));
+ }
+
+ let overridden = XorFilterBuilder::new(ty)
+ .seed(1)
+ .update_values(["alpha", "beta", "gamma"])
+ .seed(42)
+ .build()
+ .unwrap();
+ assert_eq!(
+ overridden,
+ XorFilterBuilder::new(ty)
+ .seed(42)
+ .update_values(["gamma", "alpha", "beta"])
+ .build()
+ .unwrap(),
+ );
+ assert_ne!(
+ overridden,
+ XorFilterBuilder::new(ty)
+ .seed(1)
+ .update_values(["alpha", "beta", "gamma"])
+ .build()
+ .unwrap(),
+ );
+ }
+}
+
#[test]
fn construction_recovers_after_an_unpeelable_first_attempt() {
// This distinct set needs two attempts with base seed 1. All fingerprint
widths
@@ -235,7 +301,9 @@ fn
construction_recovers_after_an_unpeelable_first_attempt() {
XorFilterType::Xor16,
XorFilterType::Xor32,
] {
+ let single_attempt = XorFilter::from_hashes_with_seed(&[keys[0]],
kind, 1).unwrap();
let filter = XorFilter::from_hashes_with_seed(&keys, kind, 1).unwrap();
+ assert_ne!(filter.serialize()[8..16],
single_attempt.serialize()[8..16]);
for &key in &keys {
assert!(filter.contains_hash(key));
}
@@ -243,7 +311,15 @@ fn
construction_recovers_after_an_unpeelable_first_attempt() {
reversed.reverse();
assert_eq!(
filter,
- XorFilter::from_hashes_with_seed(&reversed, kind, 1).unwrap()
+ XorFilter::from_hashes_with_seed(&reversed, kind, 1).unwrap(),
);
+
+ let builder_filter = XorFilterBuilder::new(kind)
+ .seed(99)
+ .update_hashes(keys.iter().copied())
+ .seed(1)
+ .build()
+ .unwrap();
+ assert_eq!(builder_filter, filter);
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]