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 91cab4e refactor(xor): keep the fingerprint layout private (#334)
91cab4e is described below
commit 91cab4ea5f4eeed982de3d8630f78da3acf19f19
Author: tison <[email protected]>
AuthorDate: Fri Nov 6 18:56:05 2026 +0800
refactor(xor): keep the fingerprint layout private (#334)
---
CHANGELOG.md | 2 +-
CONTRIBUTING.md | 2 -
Cargo.lock | 1 -
README.md | 2 +-
benchmarks/xor/query_shards.rs | 15 +--
datasketches/src/xor/filter.rs | 124 ++++-------------
datasketches/src/xor/mod.rs | 26 +---
tests-integration/Cargo.toml | 1 -
tests-integration/tests/serde_tests/xor.rs | 84 +-----------
tests-integration/tests/xor_test/filter.rs | 47 +++++++
tests-integration/tests/xor_test/fingerprints.rs | 163 -----------------------
tests-integration/tests/xor_test/main.rs | 1 -
12 files changed, 83 insertions(+), 385 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 74e356d..1960df5 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,7 +7,7 @@ All significant changes to this project will be documented in
this file.
### New features
* Add `HllUnion::serialize` to serialize union results directly.
-* Add immutable `XorFilter` behind the `xor` feature, with 8-, 16-, and 32-bit
fingerprints. Build from distinct precomputed hashes or import a seed and
fingerprints with `from_fingerprints`. `XorFilterBuilder` accepts values or
hashes individually or in batches. Inputs may repeat. Serialization stores no
item count; readers must support the encoded fingerprint width.
+* Add `XorFilter` and `XorFilterBuilder` behind the `xor` feature for
immutable membership queries on values or precomputed hashes. Filters support
8-, 16-, and 32-bit fingerprints and can be serialized for later queries.
### Improvements
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index dab6a11..50b1ded 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -192,8 +192,6 @@ cargo x prepare-testdata java
If no language is specified, all languages are prepared. These directories are
not stored in Git. Run the command before the first test run and again whenever
the pinned TCK revision changes. It requires network access and replaces the
selected generated directories.
-The pinned TCK revision does not yet contain XOR filter snapshots. Until it
does, `serde_tests/xor.rs` retains small hexadecimal fixtures generated from
the Java implementation, with the source revision and inputs documented
alongside them. Keep these separate from the synchronized `*_generated_files`
directories; replace them with TCK fixtures when available.
-
## Code of Conduct
We expect all community members to follow our [Code of
Conduct](https://www.apache.org/foundation/policies/conduct.html).
diff --git a/Cargo.lock b/Cargo.lock
index ccc8f1a..3cbfdf6 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -735,7 +735,6 @@ dependencies = [
"googletest",
"insta",
"quickcheck",
- "xorf",
]
[[package]]
diff --git a/README.md b/README.md
index 40c3131..0e38d6b 100644
--- a/README.md
+++ b/README.md
@@ -83,7 +83,7 @@ See the [API documentation](https://docs.rs/datasketches) for
configuration, acc
The minimum supported Rust version is 1.86.0. The crate currently supports
little-endian targets only.
-Supported serialization formats are tested with fixtures produced by Apache
DataSketches Java, C++, and Go through the [DataSketches
TCK](https://github.com/apache/datasketches-tck). XOR also uses Java fixtures
until TCK snapshots are available. Its standard format supports 8-, 16-, and
32-bit fingerprints; readers must support the encoded width. Use
`XorFilter::from_fingerprints` to import a seed and fingerprints from another
format.
+Cross-language serialization tests use Java, C++, and Go fixtures from the
[DataSketches TCK](https://github.com/apache/datasketches-tck).
Serialization compatibility does not imply that an ordinary Rust `Hash`
implementation produces the same update bytes across languages. When sketches
must represent the same inputs across implementations, use
`hash::value::{raw_bytes, canonical_float, sign_extend, natural_extend}` (and
the constructors within those modules) to select matching input encodings. When
interoperating with an implementation that skips empty strings, skip them
before updating here as well.
diff --git a/benchmarks/xor/query_shards.rs b/benchmarks/xor/query_shards.rs
index 2df7c63..d0f9190 100644
--- a/benchmarks/xor/query_shards.rs
+++ b/benchmarks/xor/query_shards.rs
@@ -21,7 +21,6 @@ use benchmarks::Bencher;
use benchmarks::Runner;
use datasketches::xor::XorFilter;
use datasketches::xor::XorFilterType;
-use datasketches::xor::XorFingerprints;
use xorf::Filter;
use crate::xor::hashes_with_offset;
@@ -29,8 +28,7 @@ use crate::xor::hashes_with_offset;
const SHARDS: usize = 32;
const QUERIES: usize = 256;
-// Storage formats can choose a fingerprint width at runtime. Give both peers
-// this dispatch, and import identical payloads.
+// Both implementations dispatch on fingerprint width at runtime.
enum Reference {
Xor8(xorf::Xor8),
Xor16(xorf::Xor16),
@@ -54,15 +52,6 @@ impl Reference {
Self::Xor32(filter) => filter.contains(&key),
}
}
-
- fn into_datasketches(self) -> XorFilter {
- let (seed, fingerprints) = match self {
- Self::Xor8(f) => (f.seed, XorFingerprints::Xor8(f.fingerprints)),
- Self::Xor16(f) => (f.seed, XorFingerprints::Xor16(f.fingerprints)),
- Self::Xor32(f) => (f.seed, XorFingerprints::Xor32(f.fingerprints)),
- };
- XorFilter::from_fingerprints(seed, fingerprints).unwrap()
- }
}
fn query<F>(
@@ -116,7 +105,7 @@ pub fn register(runner: &mut Runner) {
b,
cardinality,
present,
- |keys| Reference::new(keys,
kind).into_datasketches(),
+ |keys| XorFilter::from_hashes(keys, kind,
1).unwrap(),
XorFilter::contains_hash,
)
}),
diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
index 7aefd4d..3be436f 100644
--- a/datasketches/src/xor/filter.rs
+++ b/datasketches/src/xor/filter.rs
@@ -72,20 +72,14 @@ impl XorFilterType {
}
}
-/// Owned fingerprint slots for importing and exporting an application-defined
format.
-///
-/// Slots are ordered as three consecutive, equally sized segments.
#[derive(Debug, Clone, PartialEq, Eq)]
-pub enum XorFingerprints {
- /// 8-bit fingerprint slots.
+enum Fingerprints {
Xor8(Box<[u8]>),
- /// 16-bit fingerprint slots.
Xor16(Box<[u16]>),
- /// 32-bit fingerprint slots.
Xor32(Box<[u32]>),
}
-impl XorFingerprints {
+impl Fingerprints {
fn len(&self) -> usize {
match self {
Self::Xor8(values) => values.len(),
@@ -105,8 +99,6 @@ impl XorFingerprints {
/// An [`XorFilter`] builder for values or precomputed hashes.
///
-/// Inputs may repeat. Temporary memory use can grow linearly with the total
input count.
-///
/// Query values with [`XorFilter::contains`] and precomputed hashes with
/// [`XorFilter::contains_hash`].
#[derive(Debug)]
@@ -151,11 +143,11 @@ impl XorFilterBuilder {
self.hashes.extend(hashes);
}
- /// Consumes the builder and creates a filter from the distinct hashes.
+ /// Consumes the builder and creates the filter.
///
/// # Errors
///
- /// Returns an error if the set of distinct hashes is too large or no
valid layout is found.
+ /// Returns an error if the input is too large or no valid layout is found.
pub fn build(mut self) -> Result<XorFilter, Error> {
self.hashes.sort_unstable();
self.hashes.dedup();
@@ -174,7 +166,7 @@ pub struct XorFilter {
// Cache the derived length to avoid division on every query.
segment_length: usize,
seed: u64,
- fingerprints: XorFingerprints,
+ fingerprints: Fingerprints,
}
impl XorFilter {
@@ -249,21 +241,21 @@ impl XorFilter {
drop(queue);
let fingerprints = match filter_type {
- XorFilterType::Xor8 => XorFingerprints::Xor8(assign_fingerprints(
+ XorFilterType::Xor8 => Fingerprints::Xor8(assign_fingerprints(
capacity,
segment_length,
&stack_hash,
&stack_index,
|hash| fingerprint(hash) as u8,
)),
- XorFilterType::Xor16 => XorFingerprints::Xor16(assign_fingerprints(
+ XorFilterType::Xor16 => Fingerprints::Xor16(assign_fingerprints(
capacity,
segment_length,
&stack_hash,
&stack_index,
|hash| fingerprint(hash) as u16,
)),
- XorFilterType::Xor32 => XorFingerprints::Xor32(assign_fingerprints(
+ XorFilterType::Xor32 => Fingerprints::Xor32(assign_fingerprints(
capacity,
segment_length,
&stack_hash,
@@ -279,57 +271,6 @@ impl XorFilter {
})
}
- /// Imports a filter from its stored seed and fingerprint slots.
- ///
- /// Pass the original filter's [`seed`](Self::seed), which can differ from
the initial
- /// construction seed. Preserve the fingerprint order and query with the
original input hashes.
- ///
- /// # Errors
- ///
- /// Returns an error unless the payload has three equal segments of
`1..=u32::MAX` slots each.
- ///
- /// # Examples
- ///
- /// ```
- /// use datasketches::xor::XorFilter;
- /// use datasketches::xor::XorFilterType;
- ///
- /// let filter = XorFilter::from_hashes(&[10, 20, 30],
XorFilterType::Xor8, 0)?;
- /// let imported = XorFilter::from_fingerprints(filter.seed(),
filter.fingerprints().clone())?;
- /// assert!(imported.contains_hash(20));
- /// # Ok::<(), datasketches::error::Error>(())
- /// ```
- pub fn from_fingerprints(seed: u64, fingerprints: XorFingerprints) ->
Result<Self, Error> {
- let slots = fingerprints.len();
- if slots == 0 {
- return Err(Error::invalid_argument(
- "xor filter fingerprint array must not be empty",
- ));
- }
- if slots % 3 != 0 {
- return Err(Error::invalid_argument(format!(
- "xor filter fingerprint slot count must be a multiple of 3,
got {slots}"
- )));
- }
- let segment_length = slots / 3;
- if segment_length > u32::MAX as usize {
- return Err(Error::invalid_argument(format!(
- "xor filter segment length must be at most {}, got
{segment_length}",
- u32::MAX
- )));
- }
- Ok(Self {
- segment_length,
- seed,
- fingerprints,
- })
- }
-
- /// Returns the fingerprint slots for application-defined serialization.
- pub fn fingerprints(&self) -> &XorFingerprints {
- &self.fingerprints
- }
-
/// Returns `true` if an item is possibly in the input set.
///
/// A `false` result means the item was definitely absent; a `true` result
may be a false
@@ -349,48 +290,38 @@ impl XorFilter {
let [h0, h1, h2] = indexes(mixed, self.segment_length);
match &self.fingerprints {
- XorFingerprints::Xor8(fingerprints) => {
+ Fingerprints::Xor8(fingerprints) => {
fingerprint(mixed) as u8 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
}
- XorFingerprints::Xor16(fingerprints) => {
+ Fingerprints::Xor16(fingerprints) => {
fingerprint(mixed) as u16 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
}
- XorFingerprints::Xor32(fingerprints) => {
+ Fingerprints::Xor32(fingerprints) => {
fingerprint(mixed) as u32 == fingerprints[h0] ^
fingerprints[h1] ^ fingerprints[h2]
}
}
}
- /// Returns the fingerprint representation.
- pub fn filter_type(&self) -> XorFilterType {
+ fn filter_type(&self) -> XorFilterType {
match &self.fingerprints {
- XorFingerprints::Xor8(_) => XorFilterType::Xor8,
- XorFingerprints::Xor16(_) => XorFilterType::Xor16,
- XorFingerprints::Xor32(_) => XorFilterType::Xor32,
+ Fingerprints::Xor8(_) => XorFilterType::Xor8,
+ Fingerprints::Xor16(_) => XorFilterType::Xor16,
+ Fingerprints::Xor32(_) => XorFilterType::Xor32,
}
}
- /// Returns the seed paired with these fingerprints for queries and
imports.
- pub fn seed(&self) -> u64 {
- self.seed
- }
-
/// Returns the estimated in-memory size of the filter in bytes.
pub fn estimated_size(&self) -> usize {
size_of::<Self>() + self.fingerprints.byte_len()
}
- /// Serializes the filter using DataSketches family `22`, version `1`.
- ///
- /// Supports 8-, 16-, and 32-bit fingerprints, recorded in the header's
fingerprint width
- /// field. Integers and fingerprints are little-endian. Readers must
support the encoded
- /// fingerprint width; implementations limited to 8/16 bits cannot read
32-bit images.
+ /// Serializes the filter in the DataSketches format.
///
/// # Errors
///
/// Returns [`InvalidArgument`](crate::error::ErrorKind::InvalidArgument)
if the fingerprint
- /// slot count exceeds `i32::MAX` or the serialized size overflows
`usize`. Construction and
- /// imports allow larger capacities than the standard format.
+ /// slot count exceeds `i32::MAX` or the serialized size overflows
`usize`. Construction allows
+ /// larger capacities than the standard format.
pub fn serialize(&self) -> Result<Vec<u8>, Error> {
if self.fingerprints.len() > i32::MAX as usize {
return Err(Error::invalid_argument(
@@ -410,13 +341,13 @@ impl XorFilter {
bytes.write_u64_le(self.seed);
match &self.fingerprints {
- XorFingerprints::Xor8(fingerprints) => bytes.write(fingerprints),
- XorFingerprints::Xor16(fingerprints) => {
+ Fingerprints::Xor8(fingerprints) => bytes.write(fingerprints),
+ Fingerprints::Xor16(fingerprints) => {
for &fingerprint in fingerprints.iter() {
bytes.write_u16_le(fingerprint);
}
}
- XorFingerprints::Xor32(fingerprints) => {
+ Fingerprints::Xor32(fingerprints) => {
for &fingerprint in fingerprints.iter() {
bytes.write_u32_le(fingerprint);
}
@@ -428,7 +359,6 @@ impl XorFilter {
/// Deserializes an owned filter from bytes.
///
- /// Accepts 8-, 16-, and 32-bit images within the limits of
[`serialize`](Self::serialize).
/// Trailing bytes are ignored.
///
/// # Errors
@@ -501,13 +431,7 @@ impl XorFilter {
}
let fingerprints = match filter_type {
- XorFilterType::Xor8 => {
- let mut values = vec![0_u8; capacity].into_boxed_slice();
- cursor
- .read_exact(&mut values)
- .map_err(insufficient_data("fingerprints"))?;
- XorFingerprints::Xor8(values)
- }
+ XorFilterType::Xor8 =>
Fingerprints::Xor8(cursor.remaining()[..capacity].into()),
XorFilterType::Xor16 => {
let mut values = Vec::with_capacity(capacity);
for _ in 0..capacity {
@@ -517,7 +441,7 @@ impl XorFilter {
.map_err(insufficient_data("fingerprints"))?,
);
}
- XorFingerprints::Xor16(values.into_boxed_slice())
+ Fingerprints::Xor16(values.into_boxed_slice())
}
XorFilterType::Xor32 => {
let mut values = Vec::with_capacity(capacity);
@@ -528,7 +452,7 @@ impl XorFilter {
.map_err(insufficient_data("fingerprints"))?,
);
}
- XorFingerprints::Xor32(values.into_boxed_slice())
+ Fingerprints::Xor32(values.into_boxed_slice())
}
};
diff --git a/datasketches/src/xor/mod.rs b/datasketches/src/xor/mod.rs
index 9f386ce..3f14674 100644
--- a/datasketches/src/xor/mod.rs
+++ b/datasketches/src/xor/mod.rs
@@ -17,35 +17,20 @@
//! XOR filters for immutable probabilistic set membership.
//!
-//! An XOR filter is built from the complete input set and cannot be updated
afterward. Compared
-//! with a Bloom filter at the same false-positive probability, it generally
needs less space and
-//! performs exactly three fingerprint reads per query.
-//!
-//! [`XorFilterBuilder`] accepts values or precomputed hashes, including
duplicates.
-//! Use [`XorFilter::from_hashes`] when the hashes are already distinct.
+//! Use [`XorFilterBuilder`] to build a filter from values or precomputed
hashes. A negative
+//! query result rules out membership. A positive result may be a false
positive.
//!
//! # Cross-language hashing
//!
-//! Standard serialization supports 8-, 16-, and 32-bit fingerprints using
family `22`, version `1`.
-//! Interoperability requires the reader to support the encoded fingerprint
width. The format
-//! stores the seed, segment layout, and fingerprints, without an item count.
-//! Construction may choose a different valid fingerprint array from another
implementation;
-//! byte-for-byte equality of independently constructed filters is not
guaranteed. Rust's
-//! [`Hash`](std::hash::Hash) implementations do not always encode values like
other languages. Use
-//! the strategies in [`crate::hash::value`] when the input hashes must match
another DataSketches
-//! implementation. A filter built through the precomputed-hash APIs remains
portable only when
-//! every reader uses the same external hash function.
+//! Rust's [`Hash`](std::hash::Hash) may encode a value differently from other
languages. Use
+//! [`crate::hash::value`] to match the input encoding of another DataSketches
implementation.
+//! For precomputed hashes, use the same hash function when building and
querying the filter.
//!
//! Java hashes integer scalars as 64-bit little-endian values and strings as
UTF-8 bytes with
//! xxHash64 seed `0`. Use `u64`/`i64` and [`crate::hash::value::raw_bytes`]
accordingly. Java
//! skips empty strings; callers must do so explicitly here. External hashes
(for example XXH3)
//! must use the precomputed-hash APIs throughout; Java's typed query API will
not match them.
//!
-//! # Application-defined storage
-//!
-//! [`XorFilter::from_fingerprints`] restores a filter from its stored
[`seed`](XorFilter::seed)
-//! and [`fingerprints`](XorFilter::fingerprints).
-//!
//! # Examples
//!
//! ```
@@ -69,4 +54,3 @@ mod filter;
pub use self::filter::XorFilter;
pub use self::filter::XorFilterBuilder;
pub use self::filter::XorFilterType;
-pub use self::filter::XorFingerprints;
diff --git a/tests-integration/Cargo.toml b/tests-integration/Cargo.toml
index 78d9eec..44a802e 100644
--- a/tests-integration/Cargo.toml
+++ b/tests-integration/Cargo.toml
@@ -23,7 +23,6 @@ edition.workspace = true
rust-version.workspace = true
[dev-dependencies]
-xorf = { version = "=0.13.0", default-features = false }
datasketches = { workspace = true, features = [
"bloom",
"countmin",
diff --git a/tests-integration/tests/serde_tests/xor.rs
b/tests-integration/tests/serde_tests/xor.rs
index 2a9aa35..de8dbe5 100644
--- a/tests-integration/tests/serde_tests/xor.rs
+++ b/tests-integration/tests/serde_tests/xor.rs
@@ -19,7 +19,6 @@ use datasketches::error::ErrorKind;
use datasketches::xor::XorFilter;
use datasketches::xor::XorFilterBuilder;
use datasketches::xor::XorFilterType;
-use datasketches::xor::XorFingerprints;
// Generated from datasketches-java commit
c179c5bc00d5aadaed8c68ce11d14d812abe08d6.
// XorFilterBuilder.create([1, 2, 3, Long.MIN_VALUE], bits, 42).toByteArray().
@@ -49,7 +48,6 @@ fn java_images_round_trip_byte_for_byte() {
let restored = XorFilter::deserialize(&expected).unwrap();
assert_eq!(restored.serialize().unwrap(), expected);
assert_eq!(built.serialize().unwrap(), expected);
- assert_eq!(restored.filter_type(), ty);
for value in values {
assert!(built.contains(&value));
assert!(
@@ -210,85 +208,9 @@ fn xor32_image_preserves_full_width_little_endian_slots() {
let bytes = decode_hex(concat!(
"0201162001000000",
"efcdab8967452301",
- "67452301efcdab89ffffffff",
+ "67452301efcdab899c5f4186",
));
- let filter = XorFilter::from_fingerprints(
- 0x0123_4567_89ab_cdef,
- XorFingerprints::Xor32(vec![0x0123_4567, 0x89ab_cdef,
u32::MAX].into_boxed_slice()),
- )
- .unwrap();
+ let filter = XorFilter::deserialize(&bytes).unwrap();
+ assert!(filter.contains_hash(0));
assert_eq!(filter.serialize().unwrap(), bytes);
- assert_eq!(XorFilter::deserialize(&bytes).unwrap(), filter);
-}
-
-#[test]
-fn fingerprints_preserve_an_application_storage_layout() {
- use datasketches::codec::SketchSlice;
- // Synthetic storage fixtures with public xorf 0.13.0 payloads for [0, 1,
2, u64::MAX].
- // This test-only envelope omits cardinality: magic, width:u8,
segment:u32, seed:u64,
- // and little-endian slots. It is not a production storage format.
- let images = [
- concat!(
-
"54455354080c000000c15c0289ec2d0a91ad000000000000000000ca000000000000000000dc00300000000000000000",
- "0000000000",
- ),
- concat!(
-
"54455354100c000000c15c0289ec2d0a91aded000000000000000000000000000000000000ca18000000000000000000",
-
"000000000000000000dcb9000030fc0000000000000000000000000000000000000000000000000000",
- ),
- concat!(
-
"54455354200c000000c15c0289ec2d0a91adedfc84000000000000000000000000000000000000000000000000000000",
-
"000000000000000000ca187b8e0000000000000000000000000000000000000000000000000000000000000000000000",
-
"00dcb969ee0000000030fcf3490000000000000000000000000000000000000000000000000000000000000000000000",
- "0000000000000000000000000000000000",
- ),
- ];
- for image in images {
- let bytes = decode_hex(image);
- let mut cursor = SketchSlice::new(&bytes);
- assert_eq!(&bytes[..4], b"TEST");
- let mut magic = [0; 4];
- cursor.read_exact(&mut magic).unwrap();
- let width = cursor.read_u8().unwrap();
- let segment = cursor.read_u32_le().unwrap() as usize;
- let seed = cursor.read_u64_le().unwrap();
- let slots = cursor.remaining().len() / usize::from(width / 8);
- assert_eq!(segment * 3, slots);
- let payload = match width {
- 8 => XorFingerprints::Xor8(cursor.remaining().into()),
- 16 => {
- XorFingerprints::Xor16((0..slots).map(|_|
cursor.read_u16_le().unwrap()).collect())
- }
- 32 => {
- XorFingerprints::Xor32((0..slots).map(|_|
cursor.read_u32_le().unwrap()).collect())
- }
- _ => unreachable!(),
- };
- let filter = XorFilter::from_fingerprints(seed, payload).unwrap();
- for hash in [0, 1, 2, u64::MAX] {
- assert!(filter.contains_hash(hash));
- }
-
- let seed = filter.seed();
- let payload = filter.fingerprints();
- let segment = match payload {
- XorFingerprints::Xor8(values) => values.len() / 3,
- XorFingerprints::Xor16(values) => values.len() / 3,
- XorFingerprints::Xor32(values) => values.len() / 3,
- };
- let mut encoded = b"TEST".to_vec();
- encoded.push(width);
- encoded.extend((segment as u32).to_le_bytes());
- encoded.extend(seed.to_le_bytes());
- match payload {
- XorFingerprints::Xor8(values) => encoded.extend_from_slice(values),
- XorFingerprints::Xor16(values) => {
- encoded.extend(values.iter().flat_map(|v| v.to_le_bytes()))
- }
- XorFingerprints::Xor32(values) => {
- encoded.extend(values.iter().flat_map(|v| v.to_le_bytes()))
- }
- }
- assert_eq!(encoded, bytes);
- }
}
diff --git a/tests-integration/tests/xor_test/filter.rs
b/tests-integration/tests/xor_test/filter.rs
index 2deec7f..780ac2d 100644
--- a/tests-integration/tests/xor_test/filter.rs
+++ b/tests-integration/tests/xor_test/filter.rs
@@ -15,6 +15,7 @@
// specific language governing permissions and limitations
// under the License.
+use datasketches::error::ErrorKind;
use datasketches::xor::XorFilter;
use datasketches::xor::XorFilterBuilder;
use datasketches::xor::XorFilterType;
@@ -107,3 +108,49 @@ fn false_positive_rates_follow_fingerprint_width() {
);
assert!(false_positives16 < false_positives8);
}
+
+#[test]
+fn distinct_construction_is_bounded_and_does_not_deduplicate() {
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let error = XorFilter::from_hashes(&[1, 2, 1], kind, 0).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ assert!(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, 0).unwrap();
+ for key in keys {
+ assert!(f.contains_hash(key));
+ }
+ }
+ }
+}
+
+#[test]
+fn construction_recovers_after_an_unpeelable_first_attempt() {
+ // This distinct set needs two attempts with base seed 1. All fingerprint
widths
+ // share the peeling graph, so each must reset the failed attempt's
accumulators.
+ let keys: Vec<_> = (917_504..917_504 + 16_384u64)
+ .map(|i| {
+ let mut z = i.wrapping_add(0x9e3779b97f4a7c15);
+ z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
+ z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
+ z ^ (z >> 31)
+ })
+ .collect();
+ for kind in [
+ XorFilterType::Xor8,
+ XorFilterType::Xor16,
+ XorFilterType::Xor32,
+ ] {
+ let filter = XorFilter::from_hashes(&keys, kind, 1).unwrap();
+ for &key in &keys {
+ assert!(filter.contains_hash(key));
+ }
+ let mut reversed = keys.clone();
+ reversed.reverse();
+ assert_eq!(filter, XorFilter::from_hashes(&reversed, kind,
1).unwrap());
+ }
+}
diff --git a/tests-integration/tests/xor_test/fingerprints.rs
b/tests-integration/tests/xor_test/fingerprints.rs
deleted file mode 100644
index b5d000c..0000000
--- a/tests-integration/tests/xor_test/fingerprints.rs
+++ /dev/null
@@ -1,163 +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::error::ErrorKind;
-use datasketches::xor::XorFilter;
-use datasketches::xor::XorFilterType;
-use datasketches::xor::XorFingerprints;
-use xorf::Filter;
-
-#[test]
-fn fingerprints_interoperate_with_xorf_in_both_directions() {
- let keys: Vec<_> = (0..16_384u64)
- .map(|n| n.wrapping_mul(0x9e3779b97f4a7c15))
- .collect();
- for kind in [
- XorFilterType::Xor8,
- XorFilterType::Xor16,
- XorFilterType::Xor32,
- ] {
- let (seed, payload) = match kind {
- XorFilterType::Xor8 => {
- let f = xorf::Xor8::from(&keys);
- (f.seed, XorFingerprints::Xor8(f.fingerprints))
- }
- XorFilterType::Xor16 => {
- let f = xorf::Xor16::from(&keys);
- (f.seed, XorFingerprints::Xor16(f.fingerprints))
- }
- XorFilterType::Xor32 => {
- let f = xorf::Xor32::from(&keys);
- (f.seed, XorFingerprints::Xor32(f.fingerprints))
- }
- };
- let imported = XorFilter::from_fingerprints(seed, payload).unwrap();
- assert_eq!(
- XorFilter::deserialize(&imported.serialize().unwrap()).unwrap(),
- imported
- );
- for &key in &keys {
- assert!(imported.contains_hash(key));
- }
-
- let built = XorFilter::from_hashes(&keys, kind, 0).unwrap();
- let seed = built.seed();
- let payload = built.fingerprints().clone();
- // Compare all answers, including false positives, after exporting the
fingerprints.
- let reference: Box<dyn Filter<u64>> = match payload {
- XorFingerprints::Xor8(fingerprints) => Box::new(xorf::Xor8 {
- seed,
- block_length: fingerprints.len() / 3,
- fingerprints,
- }),
- XorFingerprints::Xor16(fingerprints) => Box::new(xorf::Xor16 {
- seed,
- block_length: fingerprints.len() / 3,
- fingerprints,
- }),
- XorFingerprints::Xor32(fingerprints) => Box::new(xorf::Xor32 {
- seed,
- block_length: fingerprints.len() / 3,
- fingerprints,
- }),
- };
- for key in keys.iter().copied().chain(0..100_000) {
- assert_eq!(built.contains_hash(key), reference.contains(&key));
- }
- }
-}
-
-#[test]
-fn fingerprints_reject_invalid_layouts() {
- for (length, reason) in [(0, "empty"), (2, "multiple of 3"), (4, "multiple
of 3")] {
- let error = XorFilter::from_fingerprints(0,
XorFingerprints::Xor8(vec![0; length].into()))
- .unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
- assert!(error.message().contains(reason), "{error}");
- }
-}
-
-#[test]
-fn distinct_construction_is_bounded_and_does_not_deduplicate() {
- for kind in [
- XorFilterType::Xor8,
- XorFilterType::Xor16,
- XorFilterType::Xor32,
- ] {
- let error = XorFilter::from_hashes(&[1, 2, 1], kind, 0).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
- assert!(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, 0).unwrap();
- for key in keys {
- assert!(f.contains_hash(key));
- }
- }
- }
-}
-
-#[test]
-fn construction_recovers_after_an_unpeelable_first_attempt() {
- // This distinct set needs two attempts with base seed 1. All fingerprint
widths
- // share the peeling graph, so each must reset the failed attempt's
accumulators.
- let keys: Vec<_> = (917_504..917_504 + 16_384u64)
- .map(|i| {
- let mut z = i.wrapping_add(0x9e3779b97f4a7c15);
- z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
- z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
- z ^ (z >> 31)
- })
- .collect();
- let first_seed = XorFilter::from_hashes(&[], XorFilterType::Xor8, 1)
- .unwrap()
- .seed();
- let reference = xorf::Xor8::from(&keys);
- assert_ne!(reference.seed, first_seed);
- for kind in [
- XorFilterType::Xor8,
- XorFilterType::Xor16,
- XorFilterType::Xor32,
- ] {
- let filter = XorFilter::from_hashes(&keys, kind, 1).unwrap();
- assert_eq!(filter.seed(), reference.seed);
- for &key in &keys {
- assert!(filter.contains_hash(key));
- }
- let mut reversed = keys.clone();
- reversed.reverse();
- assert_eq!(filter, XorFilter::from_hashes(&reversed, kind,
1).unwrap());
- }
-}
-
-#[test]
-fn empty_input_uses_fingerprint_queries() {
- for kind in [
- XorFilterType::Xor8,
- XorFilterType::Xor16,
- XorFilterType::Xor32,
- ] {
- let empty = XorFilter::from_hashes(&[], kind, 0).unwrap();
- let zero_hash = empty.seed().wrapping_neg();
- // This query produces a false positive even though the input set is
empty.
- assert!(empty.contains_hash(zero_hash));
- let imported =
- XorFilter::from_fingerprints(empty.seed(),
empty.fingerprints().clone()).unwrap();
- for hash in (0..1_000).chain([zero_hash]) {
- assert_eq!(imported.contains_hash(hash),
empty.contains_hash(hash));
- }
- }
-}
diff --git a/tests-integration/tests/xor_test/main.rs
b/tests-integration/tests/xor_test/main.rs
index 34b0359..2b29745 100644
--- a/tests-integration/tests/xor_test/main.rs
+++ b/tests-integration/tests/xor_test/main.rs
@@ -16,4 +16,3 @@
// under the License.
mod filter;
-mod fingerprints;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]