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 7ce0afb feat!: validate REQ rank bounds, add KLL/REQ estimated_size,
and refine traits (#370)
7ce0afb is described below
commit 7ce0afbcffe86db3c56f9f6babe2c2bc9678e1ba
Author: tison <[email protected]>
AuthorDate: Sun Nov 15 21:25:50 2026 +0800
feat!: validate REQ rank bounds, add KLL/REQ estimated_size, and refine
traits (#370)
---
CHANGELOG.md | 5 ++
datasketches/examples/bloom_difference.rs | 3 +-
datasketches/src/bloom/filter.rs | 5 +-
datasketches/src/bloom/mod.rs | 6 +-
datasketches/src/codec/decode.rs | 21 ++++---
datasketches/src/codec/encode.rs | 1 +
datasketches/src/common/jaccard_similarity.rs | 2 +-
datasketches/src/common/num_std_dev.rs | 2 +-
datasketches/src/common/resize.rs | 2 +-
datasketches/src/common/search_criteria.rs | 2 +-
datasketches/src/countmin/sketch.rs | 4 +-
datasketches/src/frequencies/serialization.rs | 2 +-
datasketches/src/frequencies/sketch.rs | 2 +-
datasketches/src/hll/array4.rs | 2 +-
datasketches/src/hll/array6.rs | 2 +-
datasketches/src/hll/array8.rs | 36 ++++++++----
datasketches/src/hll/aux_map.rs | 27 ---------
datasketches/src/hll/container.rs | 27 ---------
datasketches/src/hll/estimator.rs | 4 +-
datasketches/src/hll/hash_set.rs | 2 +-
datasketches/src/hll/list.rs | 2 +-
datasketches/src/hll/mod.rs | 2 +-
datasketches/src/hll/mode.rs | 2 +-
datasketches/src/hll/sketch.rs | 2 +-
datasketches/src/kll/sketch.rs | 12 +++-
datasketches/src/kll/value.rs | 2 +-
datasketches/src/req/compactor.rs | 5 ++
datasketches/src/req/iter.rs | 20 +++++++
datasketches/src/req/mod.rs | 2 +-
datasketches/src/req/sketch.rs | 56 +++++++++++++-----
datasketches/src/tdigest/sketch.rs | 3 +-
datasketches/src/thetafamily/theta/sketch.rs | 5 +-
datasketches/src/thetafamily/tuple/sketch.rs | 3 +-
datasketches/src/thetafamily/tuple/union.rs | 2 +-
datasketches/src/xor/filter.rs | 11 +---
tests-integration/tests/bloom_test/filter.rs | 78 ++++++++++++++++---------
tests-integration/tests/countmin_test/sketch.rs | 32 ++++++----
tests-integration/tests/hll_test/union.rs | 40 +++++++++++--
tests-integration/tests/hll_test/update.rs | 24 --------
tests-integration/tests/req_test/bounds.rs | 68 +++++++++++++++------
tests-integration/tests/req_test/property.rs | 10 +++-
tests-integration/tests/serde_tests/bloom.rs | 14 ++++-
tests-integration/tests/serde_tests/countmin.rs | 24 ++++++--
tests-integration/tests/serde_tests/hll.rs | 69 ++++++++++++++++++----
tests-integration/tests/serde_tests/kll.rs | 5 +-
tests-integration/tests/serde_tests/xor.rs | 7 ++-
tests-integration/tests/xor_test/filter.rs | 64 ++++++++++++++------
47 files changed, 465 insertions(+), 256 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index cebd4c3..dac3ca8 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -16,14 +16,19 @@ All significant changes to this project will be documented
in this file.
* `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.
* `FrequentItemsSketch::update_with_count` and
`FrequentItemsSketch::update_with_count_ref` are renamed to
`update_with_weight` and `update_with_weight_ref` to match weighted update
naming across the crate.
* `ReqSketch::num_retained` now returns `usize` instead of `u32`, matching
`KllSketch`, `ThetaSketch`, and `TupleSketch`.
+* `ReqSketch::rank_lower_bound` and `ReqSketch::rank_upper_bound` now return
`Result<f64, Error>`, returning `InvalidArgument` when `rank` is NaN or outside
`[0.0, 1.0]` even on empty or exact-mode sketches.
+* `SketchSlice::advance` now takes `n: usize` instead of `u64` and panics if
`n > self.remaining().len()`.
+* Remove `PartialEq` from `BloomFilter`, `CountMinSketch`, `HllSketch`,
`JaccardSimilarity`, and `KllSketch`.
### New features
+* Add `KllSketch::estimated_size` and `ReqSketch::estimated_size` to estimate
sketch memory usage in bytes.
* Add `CpcUnion::serialize`, `HllUnion::serialize`, `ThetaUnion::serialize`,
`ThetaUnion::serialize_compressed`, and `TupleUnion::serialize` to encode union
results without calling `to_sketch`. Direct serialization avoids intermediate
sketch allocations for `HllUnion` and `CpcUnion`, lets `HllUnion::serialize`
target any `HllType` (`Hll4`, `Hll6`, or `Hll8`) at the union's effective
`lg_k`, supports v4 compressed output via `ThetaUnion::serialize_compressed`,
and encodes `TupleUnion` sum [...]
* Add `XorFilter`, `XorFilterBuilder`, and `XorFilterType` 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
+* Implement `Clone` for `TDigest`, `ThetaSketchBuilder`, `TupleSketchBuilder`,
and `TupleUnionBuilder`; derive `Eq` and `Hash` across `NumStdDev`,
`ResizeFactor`, and `SearchCriteria`, and `Hash` across `ErrorType`, `HllType`,
and `RankAccuracy`; and implement `Debug` for `ReqSketchIterator`,
`SketchSlice`, and `SketchBytes` (plus `Clone` and `Default` on codec types).
* Improve the readability of `Debug` output across sketches, filters, views,
and stateful set operators, and implement `Debug` for `TDigest`.
### Performance improvements
diff --git a/datasketches/examples/bloom_difference.rs
b/datasketches/examples/bloom_difference.rs
index b4f1754..4d5c915 100644
--- a/datasketches/examples/bloom_difference.rs
+++ b/datasketches/examples/bloom_difference.rs
@@ -86,6 +86,7 @@ fn main() {
// Ship the resulting filter to a sibling node; the purge filter is
discarded.
let bytes = cached.serialize();
let shipped = BloomFilter::deserialize(&bytes).unwrap();
- assert_eq!(shipped, cached);
+ assert_eq!(shipped.bits_used(), cached.bits_used());
+ assert_eq!(shipped.serialize(), bytes);
println!("Shipped filter: {} bytes", bytes.len());
}
diff --git a/datasketches/src/bloom/filter.rs b/datasketches/src/bloom/filter.rs
index 7c66c99..9e70f14 100644
--- a/datasketches/src/bloom/filter.rs
+++ b/datasketches/src/bloom/filter.rs
@@ -191,7 +191,7 @@ impl BloomFilterBuilder {
/// bit capacity chosen at construction.
///
/// See [`BloomFilterBuilder`] and the [module level documentation](super) for
more.
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone)]
pub struct BloomFilter {
seed: u64,
num_hashes: u16,
@@ -438,8 +438,7 @@ impl fmt::Debug for BloomFilter {
}
}
-// Scalar fields precede `words` so derived `PartialEq` short-circuits on
`bits_used`.
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone)]
struct BitArray {
bits_used: u64,
multiplier: u64,
diff --git a/datasketches/src/bloom/mod.rs b/datasketches/src/bloom/mod.rs
index fd172ba..385b0da 100644
--- a/datasketches/src/bloom/mod.rs
+++ b/datasketches/src/bloom/mod.rs
@@ -69,7 +69,11 @@
//! assert!(filter.contains("banana"));
//!
//! let restored = BloomFilter::deserialize(&filter.serialize()).unwrap();
-//! assert_eq!(filter, restored);
+//! assert!(restored.contains("apple"));
+//! assert!(restored.contains("banana"));
+//! assert!(!restored.contains("grape"));
+//! assert_eq!(restored.bits_used(), filter.bits_used());
+//! assert_eq!(restored.serialize(), filter.serialize());
//! ```
//!
//! # References
diff --git a/datasketches/src/codec/decode.rs b/datasketches/src/codec/decode.rs
index 4da01c1..6266ec0 100644
--- a/datasketches/src/codec/decode.rs
+++ b/datasketches/src/codec/decode.rs
@@ -16,28 +16,29 @@
// under the License.
use std::io;
-use std::io::Cursor;
use std::io::Read;
/// A wrapper around a byte slice that provides methods for reading various
types of data from it.
+#[derive(Debug, Clone)]
pub struct SketchSlice<'a> {
- slice: Cursor<&'a [u8]>,
+ slice: &'a [u8],
}
impl SketchSlice<'_> {
/// Creates a new `SketchSlice` from the given byte slice.
#[inline]
pub fn new(slice: &[u8]) -> SketchSlice<'_> {
- SketchSlice {
- slice: Cursor::new(slice),
- }
+ SketchSlice { slice }
}
/// Advances the position of the slice by `n` bytes.
+ ///
+ /// # Panics
+ ///
+ /// Panics if `n > self.remaining().len()`.
#[inline]
- pub fn advance(&mut self, n: u64) {
- let pos = self.slice.position();
- self.slice.set_position(pos + n);
+ pub fn advance(&mut self, n: usize) {
+ self.slice = &self.slice[n..];
}
/// Returns the not-yet-read portion of the underlying slice.
@@ -46,9 +47,7 @@ impl SketchSlice<'_> {
/// bytes it consumed; pair it with [`advance`](Self::advance).
#[inline]
pub fn remaining(&self) -> &[u8] {
- let buf = self.slice.get_ref();
- let pos = (self.slice.position() as usize).min(buf.len());
- &buf[pos..]
+ self.slice
}
/// Reads exactly `buf.len()` bytes from the slice into `buf`.
diff --git a/datasketches/src/codec/encode.rs b/datasketches/src/codec/encode.rs
index 28754ee..1aa4193 100644
--- a/datasketches/src/codec/encode.rs
+++ b/datasketches/src/codec/encode.rs
@@ -16,6 +16,7 @@
// under the License.
/// A simple wrapper around a `Vec<u8>` that provides methods for writing
various types of data.
+#[derive(Debug, Clone, Default)]
pub struct SketchBytes {
bytes: Vec<u8>,
}
diff --git a/datasketches/src/common/jaccard_similarity.rs
b/datasketches/src/common/jaccard_similarity.rs
index e253226..23fdc63 100644
--- a/datasketches/src/common/jaccard_similarity.rs
+++ b/datasketches/src/common/jaccard_similarity.rs
@@ -18,7 +18,7 @@
/// Jaccard similarity estimate and confidence bounds for two sketches.
///
/// The bounds use a 95.4% confidence interval, equivalent to +/- 2 standard
deviations.
-#[derive(Clone, Copy, Debug, PartialEq)]
+#[derive(Clone, Copy, Debug)]
pub struct JaccardSimilarity {
lower_bound: f64,
estimate: f64,
diff --git a/datasketches/src/common/num_std_dev.rs
b/datasketches/src/common/num_std_dev.rs
index 99ef21f..9288b98 100644
--- a/datasketches/src/common/num_std_dev.rs
+++ b/datasketches/src/common/num_std_dev.rs
@@ -35,7 +35,7 @@ static DELTA_OF_NUM_STD_DEVS: [f64; 4] = [
/// confidence intervals with greater certainty that the true value falls
within
/// the bounds.
#[repr(u8)]
-#[derive(Debug, Clone, Copy, PartialEq)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum NumStdDev {
/// One standard deviation (\~68% confidence interval).
One = 1,
diff --git a/datasketches/src/common/resize.rs
b/datasketches/src/common/resize.rs
index 60e41f7..eb28f19 100644
--- a/datasketches/src/common/resize.rs
+++ b/datasketches/src/common/resize.rs
@@ -41,7 +41,7 @@
/// assert_eq!(factor.value(), 4);
/// assert_eq!(factor.lg_value(), 2);
/// ```
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ResizeFactor {
/// Does not resize; configures the sketch at full size.
X1,
diff --git a/datasketches/src/common/search_criteria.rs
b/datasketches/src/common/search_criteria.rs
index 3e98ca6..648e051 100644
--- a/datasketches/src/common/search_criteria.rs
+++ b/datasketches/src/common/search_criteria.rs
@@ -16,7 +16,7 @@
// under the License.
/// Selects the rank definition used by rank, quantile, PMF, and CDF queries.
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum SearchCriteria {
/// Define rank as the fraction of values less than or equal to the
boundary.
Inclusive,
diff --git a/datasketches/src/countmin/sketch.rs
b/datasketches/src/countmin/sketch.rs
index 79359f3..d3a3532 100644
--- a/datasketches/src/countmin/sketch.rs
+++ b/datasketches/src/countmin/sketch.rs
@@ -47,7 +47,7 @@ const MAX_TABLE_ENTRIES: usize = 1 << 30;
/// with configurable relative error and confidence.
///
/// See the [module level documentation](super) for more.
-#[derive(Clone, PartialEq)]
+#[derive(Clone)]
pub struct CountMinSketch<T: CountMinValue> {
num_hashes: u8,
buckets: BucketCount,
@@ -159,7 +159,7 @@ impl SerialVersion {
}
}
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
struct BucketCount {
count: u32,
multiplier: u128,
diff --git a/datasketches/src/frequencies/serialization.rs
b/datasketches/src/frequencies/serialization.rs
index 12def20..e32ada7 100644
--- a/datasketches/src/frequencies/serialization.rs
+++ b/datasketches/src/frequencies/serialization.rs
@@ -68,7 +68,7 @@ impl FrequentItemValue for String {
let value = std::str::from_utf8(&cursor.remaining()[..len])
.map(str::to_owned)
.map_err(|_| Error::deserial("invalid UTF-8 string payload"))?;
- cursor.advance(len as u64);
+ cursor.advance(len);
Ok(value)
}
}
diff --git a/datasketches/src/frequencies/sketch.rs
b/datasketches/src/frequencies/sketch.rs
index efcdfd8..a4cec1d 100644
--- a/datasketches/src/frequencies/sketch.rs
+++ b/datasketches/src/frequencies/sketch.rs
@@ -95,7 +95,7 @@ fn validate_lg_map_sizes(lg_max: u8, lg_cur: u8) ->
Result<(), Error> {
}
/// Error guarantees for frequent item queries.
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ErrorType {
/// Includes items if the upper bound exceeds the threshold (no false
negatives).
NoFalseNegatives,
diff --git a/datasketches/src/hll/array4.rs b/datasketches/src/hll/array4.rs
index 28daa80..afe07e2 100644
--- a/datasketches/src/hll/array4.rs
+++ b/datasketches/src/hll/array4.rs
@@ -48,7 +48,7 @@ impl AuxFormat {
}
/// Registers stored as four-bit offsets from their current minimum.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub struct Array4 {
lg_config_k: u8,
/// Even slots occupy the low nibble; odd slots occupy the high nibble.
diff --git a/datasketches/src/hll/array6.rs b/datasketches/src/hll/array6.rs
index b1fe163..103ab73 100644
--- a/datasketches/src/hll/array6.rs
+++ b/datasketches/src/hll/array6.rs
@@ -30,7 +30,7 @@ use crate::hll::serialization::write_hll_preamble;
const VAL_MASK_6: u16 = 0x3F;
/// Registers packed into consecutive six-bit fields.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub struct Array6 {
lg_config_k: u8,
bytes: Box<[u8]>,
diff --git a/datasketches/src/hll/array8.rs b/datasketches/src/hll/array8.rs
index f45fdae..ac266a0 100644
--- a/datasketches/src/hll/array8.rs
+++ b/datasketches/src/hll/array8.rs
@@ -43,20 +43,12 @@ pub struct Array8 {
}
/// Zero-register count and estimator used for cardinality queries.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
struct Estimation {
num_zeros: u32,
estimator: Estimator,
}
-impl PartialEq for Array8 {
- fn eq(&self, other: &Self) -> bool {
- self.lg_config_k == other.lg_config_k
- && self.bytes == other.bytes
- && self.estimation() == other.estimation()
- }
-}
-
impl Array8 {
pub fn new(lg_config_k: u8) -> Self {
let k = 1 << lg_config_k;
@@ -697,6 +689,28 @@ mod tests {
use crate::hll::HllSketch;
use crate::hll::array4::Array4;
+ fn canonical_hll4_bytes(sketch: &HllSketch) -> Vec<u8> {
+ let mut bytes = sketch.serialize();
+ bytes[4] = 0;
+ let aux_start = HLL_PREAMBLE_SIZE + (1usize <<
(sketch.lg_config_k() - 1));
+ let mut aux: Vec<u32> = bytes[aux_start..]
+ .chunks_exact(4)
+ .map(|chunk| u32::from_le_bytes(chunk.try_into().unwrap()))
+ .collect();
+ aux.sort_unstable();
+ for (dst, coupon) in
bytes[aux_start..].chunks_exact_mut(4).zip(aux) {
+ dst.copy_from_slice(&coupon.to_le_bytes());
+ }
+ bytes
+ }
+
+ fn assert_hll4_eq(actual: &HllSketch, expected: &HllSketch) {
+ assert_eq!(actual.lg_config_k(), expected.lg_config_k());
+ assert_eq!(actual.target_type(), expected.target_type());
+ assert_eq!(actual.is_empty(), expected.is_empty());
+ assert_eq!(canonical_hll4_bytes(actual),
canonical_hll4_bytes(expected));
+ }
+
let lg_k = 4u8;
let k = 1usize << lg_k;
let mut arr8 = Array8::new(lg_k);
@@ -720,7 +734,7 @@ mod tests {
let decoded = HllSketch::deserialize(&direct_bytes).unwrap();
let expected = HllSketch::from_mode(lg_k,
crate::hll::mode::Mode::Array4(arr4.clone()));
- assert_eq!(decoded, expected);
+ assert_hll4_eq(&decoded, &expected);
assert_eq!(decoded.estimate(), expected.estimate());
assert_eq!(decoded.composite_estimate(),
expected.composite_estimate());
for std_dev in [NumStdDev::One, NumStdDev::Two, NumStdDev::Three] {
@@ -734,7 +748,7 @@ mod tests {
let direct_ooo = arr8.serialize_as(lg_k, HllType::Hll4);
let decoded_ooo = HllSketch::deserialize(&direct_ooo).unwrap();
let expected_ooo = HllSketch::from_mode(lg_k,
crate::hll::mode::Mode::Array4(arr4));
- assert_eq!(decoded_ooo, expected_ooo);
+ assert_hll4_eq(&decoded_ooo, &expected_ooo);
assert_eq!(decoded_ooo.estimate(), expected_ooo.estimate());
assert_eq!(
decoded_ooo.composite_estimate(),
diff --git a/datasketches/src/hll/aux_map.rs b/datasketches/src/hll/aux_map.rs
index 2ce25a3..b1c519b 100644
--- a/datasketches/src/hll/aux_map.rs
+++ b/datasketches/src/hll/aux_map.rs
@@ -28,33 +28,6 @@ pub struct AuxMap {
count: u32,
}
-impl PartialEq for AuxMap {
- fn eq(&self, other: &Self) -> bool {
- // Capacity and slot order do not affect the logical entries.
- if self.lg_config_k != other.lg_config_k || self.count != other.count {
- return false;
- }
-
- let mut entries1: Vec<Coupon> = self
- .entries
- .iter()
- .filter(|&&e| !e.is_empty())
- .copied()
- .collect();
- let mut entries2: Vec<Coupon> = other
- .entries
- .iter()
- .filter(|&&e| !e.is_empty())
- .copied()
- .collect();
-
- entries1.sort_unstable();
- entries2.sort_unstable();
-
- entries1 == entries2
- }
-}
-
/// Initial table sizes from datasketches-cpp:
///
<https://github.com/apache/datasketches-cpp/blob/5a055521/hll/include/HllUtil.hpp>
fn lg_aux_arr_ints(lg_config_k: u8) -> u8 {
diff --git a/datasketches/src/hll/container.rs
b/datasketches/src/hll/container.rs
index bc8cab6..49d2129 100644
--- a/datasketches/src/hll/container.rs
+++ b/datasketches/src/hll/container.rs
@@ -31,33 +31,6 @@ pub struct Container {
pub len: usize,
}
-impl PartialEq for Container {
- fn eq(&self, other: &Self) -> bool {
- // Capacity and slot order do not affect the logical coupon contents.
- if self.len != other.len {
- return false;
- }
-
- let mut coupons1: Vec<Coupon> = self
- .coupons
- .iter()
- .filter(|&&c| !c.is_empty())
- .copied()
- .collect();
- let mut coupons2: Vec<Coupon> = other
- .coupons
- .iter()
- .filter(|&&c| !c.is_empty())
- .copied()
- .collect();
-
- coupons1.sort_unstable();
- coupons2.sort_unstable();
-
- coupons1 == coupons2
- }
-}
-
impl Container {
pub fn new(lg_size: usize) -> Self {
Self {
diff --git a/datasketches/src/hll/estimator.rs
b/datasketches/src/hll/estimator.rs
index 631d31f..998b01d 100644
--- a/datasketches/src/hll/estimator.rs
+++ b/datasketches/src/hll/estimator.rs
@@ -30,7 +30,7 @@ use crate::hll::cubic_interpolation;
use crate::hll::harmonic_numbers;
/// Selects the estimate that is valid for the current register history.
-#[derive(Debug, Clone, Copy, PartialEq)]
+#[derive(Debug, Clone, Copy)]
pub enum EstimateState {
/// The register updates have a known order, so the HIP accumulator is
valid.
Hip(f64),
@@ -40,7 +40,7 @@ pub enum EstimateState {
/// KxQ caches the sum of `2^-register`. Splitting the sum at register value
32 preserves
/// precision when large and small contributions coexist.
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub struct Estimator {
state: EstimateState,
/// KxQ register for values < 32 (larger inverse powers)
diff --git a/datasketches/src/hll/hash_set.rs b/datasketches/src/hll/hash_set.rs
index d78be7c..3b5dc05 100644
--- a/datasketches/src/hll/hash_set.rs
+++ b/datasketches/src/hll/hash_set.rs
@@ -31,7 +31,7 @@ use crate::hll::serialization::SERIAL_VERSION;
use crate::hll::serialization::SET_PREAMBLE_SIZE;
use crate::hll::serialization::encode_mode_byte;
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub struct HashSet {
container: Container,
}
diff --git a/datasketches/src/hll/list.rs b/datasketches/src/hll/list.rs
index 748b187..1e6ab35 100644
--- a/datasketches/src/hll/list.rs
+++ b/datasketches/src/hll/list.rs
@@ -30,7 +30,7 @@ use crate::hll::serialization::LIST_PREINTS;
use crate::hll::serialization::SERIAL_VERSION;
use crate::hll::serialization::encode_mode_byte;
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub struct List {
container: Container,
}
diff --git a/datasketches/src/hll/mod.rs b/datasketches/src/hll/mod.rs
index ed6651c..fba26a7 100644
--- a/datasketches/src/hll/mod.rs
+++ b/datasketches/src/hll/mod.rs
@@ -94,7 +94,7 @@ pub use self::union::HllUnion;
///
/// For the same `lg_k` and input, all three types produce the same estimates.
/// They trade memory usage against update speed.
-#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum HllType {
/// Uses 4 bits per HLL bucket and has the smallest storage footprint.
///
diff --git a/datasketches/src/hll/mode.rs b/datasketches/src/hll/mode.rs
index ad3cc16..1043629 100644
--- a/datasketches/src/hll/mode.rs
+++ b/datasketches/src/hll/mode.rs
@@ -22,7 +22,7 @@ use crate::hll::array8::Array8;
use crate::hll::hash_set::HashSet;
use crate::hll::list::List;
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone)]
pub enum Mode {
List { list: List, hll_type: HllType },
Set { set: HashSet, hll_type: HllType },
diff --git a/datasketches/src/hll/sketch.rs b/datasketches/src/hll/sketch.rs
index a62bea9..e931959 100644
--- a/datasketches/src/hll/sketch.rs
+++ b/datasketches/src/hll/sketch.rs
@@ -56,7 +56,7 @@ use crate::hll::serialization::extract_tgt_hll_type;
/// A HyperLogLog sketch.
///
/// See the [module level documentation](super) for more.
-#[derive(Clone, PartialEq)]
+#[derive(Clone)]
pub struct HllSketch {
lg_config_k: u8,
mode: Mode,
diff --git a/datasketches/src/kll/sketch.rs b/datasketches/src/kll/sketch.rs
index b985d0a..848aaf2 100644
--- a/datasketches/src/kll/sketch.rs
+++ b/datasketches/src/kll/sketch.rs
@@ -50,7 +50,7 @@ use crate::error::Error;
/// KLL sketch for estimating quantiles and ranks.
///
/// See the [kll module level documentation](crate::kll) for more.
-#[derive(Clone, PartialEq)]
+#[derive(Clone)]
pub struct KllSketch<T> {
k: u16,
m: u8,
@@ -352,6 +352,16 @@ impl<T: Clone + Ord> KllSketch<T> {
pub fn normalized_pmf_error(&self) -> f64 {
normalized_rank_error(self.min_k, true)
}
+
+ /// Returns an estimate of the sketch's memory usage in bytes.
+ pub fn estimated_size(&self) -> usize {
+ self.levels.capacity() * size_of::<Vec<T>>()
+ + self
+ .levels
+ .iter()
+ .map(|level| level.capacity() * size_of::<T>())
+ .sum::<usize>()
+ }
}
fn serialized_size<T: KllValue + Ord>(sketch: &KllSketch<T>) -> usize {
diff --git a/datasketches/src/kll/value.rs b/datasketches/src/kll/value.rs
index b69f369..bc844e1 100644
--- a/datasketches/src/kll/value.rs
+++ b/datasketches/src/kll/value.rs
@@ -216,7 +216,7 @@ impl KllValue for String {
let value = std::str::from_utf8(&input.remaining()[..len])
.map_err(|error| Error::deserial(format!("invalid UTF-8 string:
{error}")))?
.to_owned();
- input.advance(len as u64);
+ input.advance(len);
Ok(value)
}
}
diff --git a/datasketches/src/req/compactor.rs
b/datasketches/src/req/compactor.rs
index d2f8c92..4885d1e 100644
--- a/datasketches/src/req/compactor.rs
+++ b/datasketches/src/req/compactor.rs
@@ -242,6 +242,11 @@ where
1u64 << self.lg_weight
}
+ /// Returns an estimate of memory usage in bytes.
+ pub fn estimated_size(&self) -> usize {
+ self.items.capacity() * size_of::<T>() +
self.scratch_buffer.capacity() * size_of::<T>()
+ }
+
fn ensure_enough_sections(&mut self) -> bool {
let Some(threshold) = self
.num_sections
diff --git a/datasketches/src/req/iter.rs b/datasketches/src/req/iter.rs
index b36c2f4..94c10c9 100644
--- a/datasketches/src/req/iter.rs
+++ b/datasketches/src/req/iter.rs
@@ -17,6 +17,8 @@
//! Iterator implementations for REQ sketch inspection.
+use std::fmt;
+
use crate::req::compactor::Compactor;
/// Iterator over (item, weight) pairs in a REQ sketch.
@@ -25,6 +27,7 @@ use crate::req::compactor::Compactor;
/// which depend on the level of the compactor they're stored in.
///
/// Items are borrowed from the sketch, so iteration does not clone or
allocate.
+#[must_use = "iterators are lazy and do nothing unless consumed"]
pub struct ReqSketchIterator<'a, T> {
compactors: &'a [Compactor<T>],
current_level: usize,
@@ -32,6 +35,23 @@ pub struct ReqSketchIterator<'a, T> {
current_weight: u64,
}
+impl<T> fmt::Debug for ReqSketchIterator<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("ReqSketchIterator")
+ .field("current_level", &self.current_level)
+ .field("num_levels", &self.compactors.len())
+ .field("current_weight", &self.current_weight)
+ .field(
+ "remaining_in_level",
+ &self
+ .current_level_iter
+ .as_ref()
+ .map_or(0, |iter| iter.len()),
+ )
+ .finish()
+ }
+}
+
impl<'a, T: Clone + Ord> ReqSketchIterator<'a, T> {
/// Creates a new iterator over the compactors.
pub(super) fn new(compactors: &'a [Compactor<T>]) -> Self {
diff --git a/datasketches/src/req/mod.rs b/datasketches/src/req/mod.rs
index ff0ed71..82e2446 100644
--- a/datasketches/src/req/mod.rs
+++ b/datasketches/src/req/mod.rs
@@ -70,7 +70,7 @@ const MIN_K: u16 = 4;
const MAX_K: u16 = 1024;
/// Selects which tail of the rank domain the sketch optimizes for.
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
pub enum RankAccuracy {
/// Optimize for accuracy at high ranks (near 1.0).
#[default]
diff --git a/datasketches/src/req/sketch.rs b/datasketches/src/req/sketch.rs
index 261b9e3..fa452d2 100644
--- a/datasketches/src/req/sketch.rs
+++ b/datasketches/src/req/sketch.rs
@@ -150,6 +150,17 @@ where
self.max_item.as_ref()
}
+ /// Returns an estimate of the sketch's memory usage in bytes.
+ pub fn estimated_size(&self) -> usize {
+ self.compactors.capacity() * size_of::<Compactor<T>>()
+ + self
+ .compactors
+ .iter()
+ .map(Compactor::estimated_size)
+ .sum::<usize>()
+ + self.promotion_buf.capacity() * size_of::<T>()
+ }
+
/// Updates the sketch with a new item.
///
/// # Panics
@@ -224,11 +235,7 @@ where
/// Returns `InvalidArgument` if `rank` is NaN or outside `[0.0, 1.0]`,
even if the sketch is
/// empty.
pub fn quantile(&self, rank: f64, criteria: SearchCriteria) ->
Result<Option<T>, Error> {
- if !(0.0..=1.0).contains(&rank) {
- return Err(Error::invalid_argument(format!(
- "rank {rank} must be in [0, 1]"
- )));
- }
+ validate_rank(rank)?;
if self.is_empty() {
return Ok(None);
}
@@ -260,11 +267,7 @@ where
) -> Result<Option<Vec<T>>, Error> {
// Reject invalid ranks before paying for the view build.
for &r in ranks {
- if !(0.0..=1.0).contains(&r) {
- return Err(Error::invalid_argument(format!(
- "rank {r} must be in [0, 1]"
- )));
- }
+ validate_rank(r)?;
}
if self.is_empty() {
return Ok(None);
@@ -417,29 +420,41 @@ where
/// Returns the lower bound for the normalized `rank` at the requested
confidence level.
///
/// In exact mode, including an empty sketch, the bound equals `rank`.
- pub fn rank_lower_bound(&self, rank: f64, num_std_dev: NumStdDev) -> f64 {
- self.compute_rank_lower_bound(
+ ///
+ /// # Errors
+ ///
+ /// Returns `InvalidArgument` if `rank` is NaN or outside `[0.0, 1.0]`,
even if the sketch is
+ /// empty.
+ pub fn rank_lower_bound(&self, rank: f64, num_std_dev: NumStdDev) ->
Result<f64, Error> {
+ validate_rank(rank)?;
+ Ok(self.compute_rank_lower_bound(
self.k,
self.compactors.len() as u8,
rank,
num_std_dev.as_u8(),
self.n,
matches!(self.rank_accuracy, RankAccuracy::HighRank),
- )
+ ))
}
/// Returns the upper bound for the normalized `rank` at the requested
confidence level.
///
/// In exact mode, including an empty sketch, the bound equals `rank`.
- pub fn rank_upper_bound(&self, rank: f64, num_std_dev: NumStdDev) -> f64 {
- self.compute_rank_upper_bound(
+ ///
+ /// # Errors
+ ///
+ /// Returns `InvalidArgument` if `rank` is NaN or outside `[0.0, 1.0]`,
even if the sketch is
+ /// empty.
+ pub fn rank_upper_bound(&self, rank: f64, num_std_dev: NumStdDev) ->
Result<f64, Error> {
+ validate_rank(rank)?;
+ Ok(self.compute_rank_upper_bound(
self.k,
self.compactors.len() as u8,
rank,
num_std_dev.as_u8(),
self.n,
matches!(self.rank_accuracy, RankAccuracy::HighRank),
- )
+ ))
}
const FIXED_RSE_FACTOR: f64 = 0.084;
@@ -871,3 +886,12 @@ where
self.num_retained = self.compactors.iter().map(|c|
c.num_items()).sum();
}
}
+
+fn validate_rank(rank: f64) -> Result<(), Error> {
+ if !(0.0..=1.0).contains(&rank) {
+ return Err(Error::invalid_argument(format!(
+ "rank {rank} must be in [0, 1]"
+ )));
+ }
+ Ok(())
+}
diff --git a/datasketches/src/tdigest/sketch.rs
b/datasketches/src/tdigest/sketch.rs
index 55d7549..e5055ce 100644
--- a/datasketches/src/tdigest/sketch.rs
+++ b/datasketches/src/tdigest/sketch.rs
@@ -607,6 +607,7 @@ impl TDigestMut {
/// Immutable (frozen) T-Digest sketch for estimating quantiles and ranks.
///
/// See the [module level documentation](super) for more.
+#[derive(Clone)]
pub struct TDigest {
k: u16,
@@ -1758,7 +1759,7 @@ fn merge_sorted_centroids(left: &mut Vec<Centroid>,
right: &[Centroid]) {
}
}
-#[derive(Debug, Clone, Copy, PartialEq)]
+#[derive(Debug, Clone, Copy)]
struct Centroid {
mean: f64,
weight: NonZeroU64,
diff --git a/datasketches/src/thetafamily/theta/sketch.rs
b/datasketches/src/thetafamily/theta/sketch.rs
index c8a43ab..a3ce436 100644
--- a/datasketches/src/thetafamily/theta/sketch.rs
+++ b/datasketches/src/thetafamily/theta/sketch.rs
@@ -380,6 +380,7 @@ impl ThetaSketch {
/// let compact = sketch.compact(true);
/// assert_eq!(compact.num_retained(), 1);
/// ```
+ #[must_use = "compact returns a new compact sketch without modifying this
sketch"]
pub fn compact(&self, ordered: bool) -> CompactThetaSketch {
let compact_state = if self.is_empty() {
debug_assert_eq!(self.num_retained(), 0);
@@ -887,7 +888,7 @@ impl CompactThetaSketch {
let payload = &cursor.remaining()[..required_bytes];
let entries = unpack_deltas(payload, num_entries, entry_bits, theta)?;
- cursor.advance(required_bytes as u64);
+ cursor.advance(required_bytes);
let ordered = (flags & FLAGS_IS_ORDERED) != 0;
@@ -908,7 +909,7 @@ impl CompactThetaSketch {
/// Builder for [`ThetaSketch`].
///
/// Configuration is stored without validation and checked when
[`build()`](Self::build) is called.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
pub struct ThetaSketchBuilder {
lg_k: u8,
resize_factor: ResizeFactor,
diff --git a/datasketches/src/thetafamily/tuple/sketch.rs
b/datasketches/src/thetafamily/tuple/sketch.rs
index 68816d9..ec6edf6 100644
--- a/datasketches/src/thetafamily/tuple/sketch.rs
+++ b/datasketches/src/thetafamily/tuple/sketch.rs
@@ -474,6 +474,7 @@ where
/// let compact = sketch.compact(true);
/// assert_eq!(compact.num_retained(), 1);
/// ```
+ #[must_use = "compact returns a new compact sketch without modifying this
sketch"]
pub fn compact(&self, ordered: bool) -> CompactTupleSketch<P::Summary> {
let compact_state = if self.is_empty() {
debug_assert_eq!(self.num_retained(), 0);
@@ -772,7 +773,7 @@ impl<S> CompactTupleSketch<S> {
/// summaries, or supply a custom policy.
///
/// Configuration is stored without validation and checked when
[`build()`](Self::build) is called.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
pub struct TupleSketchBuilder<P>
where
P: SummaryPolicy,
diff --git a/datasketches/src/thetafamily/tuple/union.rs
b/datasketches/src/thetafamily/tuple/union.rs
index 60c0254..9653d04 100644
--- a/datasketches/src/thetafamily/tuple/union.rs
+++ b/datasketches/src/thetafamily/tuple/union.rs
@@ -172,7 +172,7 @@ where
/// custom combine policy.
///
/// Configuration is stored without validation and checked when
[`build()`](Self::build) is called.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
pub struct TupleUnionBuilder<P>
where
P: SummaryCombinePolicy,
diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
index a812d18..3c65de6 100644
--- a/datasketches/src/xor/filter.rs
+++ b/datasketches/src/xor/filter.rs
@@ -45,7 +45,6 @@ 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`.
@@ -74,7 +73,7 @@ impl XorFilterType {
}
}
-#[derive(Debug, Clone, PartialEq, Eq)]
+#[derive(Debug, Clone)]
enum Fingerprints {
Xor8(Box<[u8]>),
Xor16(Box<[u16]>),
@@ -205,7 +204,6 @@ impl Fingerprints {
/// [`XorFilter::contains_hash`].
///
/// See the [module level documentation](super) for more.
-#[must_use]
#[derive(Clone)]
pub struct XorFilterBuilder {
filter_type: XorFilterType,
@@ -306,8 +304,7 @@ impl XorFilterBuilder {
/// changes.
///
/// See the [module level documentation](super) for more.
-#[must_use]
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone)]
pub struct XorFilter {
// Cache the derived length to avoid division on every query.
segment_length: usize,
@@ -445,7 +442,6 @@ 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))
@@ -455,7 +451,6 @@ 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);
@@ -468,13 +463,11 @@ 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());
diff --git a/tests-integration/tests/bloom_test/filter.rs
b/tests-integration/tests/bloom_test/filter.rs
index 2e3b29c..0d2ca99 100644
--- a/tests-integration/tests/bloom_test/filter.rs
+++ b/tests-integration/tests/bloom_test/filter.rs
@@ -35,6 +35,16 @@ fn filter() -> BloomFilter {
.unwrap()
}
+fn filter_snapshot(filter: &BloomFilter) -> (u64, u16, u64, u64, Vec<u8>) {
+ (
+ filter.capacity(),
+ filter.num_hashes(),
+ filter.seed(),
+ filter.bits_used(),
+ filter.serialize(),
+ )
+}
+
fn decode_hex(input: &str) -> Vec<u8> {
assert_eq!(input.len() % 2, 0);
input
@@ -51,7 +61,7 @@ fn decode_hex(input: &str) -> Vec<u8> {
fn lifecycle_statistics_and_reset() {
let mut filter = filter();
let empty = filter.clone();
- assert_eq!(filter, empty);
+ assert_eq!(filter_snapshot(&filter), filter_snapshot(&empty));
assert_eq!(filter.capacity(), NUM_BITS);
assert_eq!(filter.num_hashes(), NUM_HASHES);
assert_eq!(filter.seed(), SEED);
@@ -71,13 +81,13 @@ fn lifecycle_statistics_and_reset() {
assert!(filter.contains_and_insert("apple"));
assert!(filter.contains("apple"));
assert!(!filter.is_empty());
- assert_ne!(filter, empty);
+ assert_ne!(filter_snapshot(&filter), filter_snapshot(&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_eq!(filter_snapshot(&filter), filter_snapshot(&empty));
assert!(filter.is_empty());
assert_eq!(filter.bits_used(), 0);
assert_eq!(filter.load_factor(), 0.0);
@@ -95,7 +105,7 @@ fn insert_and_contains_and_insert_are_equivalent() {
assert_eq!(checked.contains_and_insert(value), was_present);
inserted.insert(value);
assert!(inserted.contains(value));
- assert_eq!(checked, inserted);
+ assert_eq!(filter_snapshot(&checked), filter_snapshot(&inserted));
}
}
@@ -121,7 +131,10 @@ fn equivalent_borrowed_and_value_inputs_match() {
}
assert!(!from_slices_and_values.contains_and_insert(raw_bytes::from_str("payload")));
- assert_eq!(from_borrows, from_slices_and_values);
+ assert_eq!(
+ filter_snapshot(&from_borrows),
+ filter_snapshot(&from_slices_and_values)
+ );
assert!(from_borrows.contains(&owned_text));
assert!(from_borrows.contains(owned_text.as_str()));
@@ -135,7 +148,10 @@ fn equivalent_borrowed_and_value_inputs_match() {
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);
+ assert_eq!(
+ filter_snapshot(&from_slices_and_values),
+ filter_snapshot(&from_borrows)
+ );
}
#[test]
@@ -153,13 +169,13 @@ fn
within_item_collisions_and_repeated_inserts_preserve_bit_count() {
for filter in [&mut inserted, &mut checked] {
let before_repeat = filter.clone();
filter.insert(42_u64);
- assert_eq!(*filter, before_repeat);
+ assert_eq!(filter_snapshot(filter),
filter_snapshot(&before_repeat));
assert!(filter.contains_and_insert(42_u64));
- assert_eq!(*filter, before_repeat);
+ assert_eq!(filter_snapshot(filter),
filter_snapshot(&before_repeat));
// Recount the backing bits independently of either insertion path.
let restored =
BloomFilter::deserialize(&filter.serialize()).unwrap();
- assert_eq!(restored, *filter);
+ assert_eq!(filter_snapshot(&restored), filter_snapshot(filter));
assert_eq!(restored.bits_used(), filter.bits_used());
}
}
@@ -184,8 +200,8 @@ fn union_intersect_and_difference_preserve_set_semantics() {
assert_that!(intersection.bits_used(), le(left_bits));
assert_that!(intersection.bits_used(), le(right_bits));
assert_eq!(
- BloomFilter::deserialize(&intersection.serialize()).unwrap(),
- intersection
+
filter_snapshot(&BloomFilter::deserialize(&intersection.serialize()).unwrap()),
+ filter_snapshot(&intersection)
);
let mut union = left.clone();
@@ -195,7 +211,10 @@ fn union_intersect_and_difference_preserve_set_semantics()
{
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);
+ assert_eq!(
+
filter_snapshot(&BloomFilter::deserialize(&union.serialize()).unwrap()),
+ filter_snapshot(&union)
+ );
let mut diff_disjoint = left.clone();
diff_disjoint.difference(&right).unwrap();
@@ -205,7 +224,7 @@ fn union_intersect_and_difference_preserve_set_semantics() {
let mut diff_empty = left.clone();
diff_empty.difference(&filter()).unwrap();
- assert_eq!(diff_empty, left);
+ assert_eq!(filter_snapshot(&diff_empty), filter_snapshot(&left));
let mut diff_self = left.clone();
diff_self.difference(&left).unwrap();
@@ -214,8 +233,8 @@ fn union_intersect_and_difference_preserve_set_semantics() {
assert!(!diff_self.contains("shared"));
assert!(!diff_self.contains("left"));
assert_eq!(
- BloomFilter::deserialize(&diff_self.serialize()).unwrap(),
- diff_self
+
filter_snapshot(&BloomFilter::deserialize(&diff_self.serialize()).unwrap()),
+ filter_snapshot(&diff_self)
);
let mut bulk_left = filter();
@@ -234,8 +253,8 @@ fn union_intersect_and_difference_preserve_set_semantics() {
}
assert_that!(bulk_left.bits_used(), le(bulk_left_bits));
assert_eq!(
- BloomFilter::deserialize(&bulk_left.serialize()).unwrap(),
- bulk_left
+
filter_snapshot(&BloomFilter::deserialize(&bulk_left.serialize()).unwrap()),
+ filter_snapshot(&bulk_left)
);
}
@@ -264,21 +283,21 @@ fn incompatible_set_operations_are_rejected() {
union.union(other).unwrap_err().kind(),
ErrorKind::InvalidArgument
);
- assert_eq!(union, baseline);
+ assert_eq!(filter_snapshot(&union), filter_snapshot(&baseline));
let mut intersect = baseline.clone();
assert_eq!(
intersect.intersect(other).unwrap_err().kind(),
ErrorKind::InvalidArgument
);
- assert_eq!(intersect, baseline);
+ assert_eq!(filter_snapshot(&intersect), filter_snapshot(&baseline));
let mut difference = baseline.clone();
assert_eq!(
difference.difference(other).unwrap_err().kind(),
ErrorKind::InvalidArgument
);
- assert_eq!(difference, baseline);
+ assert_eq!(filter_snapshot(&difference), filter_snapshot(&baseline));
}
}
@@ -287,7 +306,10 @@ 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!(
+ filter_snapshot(&size_seeded),
+ filter_snapshot(&builder.build().unwrap())
+ );
assert_eq!(size_seeded.capacity(), 128);
assert_eq!(size_seeded.num_hashes(), 3);
assert_eq!(size_seeded.seed(), 42);
@@ -314,11 +336,13 @@ fn builder_validation_and_word_rounding() {
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()
+ filter_snapshot(&acc_seeded),
+ filter_snapshot(
+ &BloomFilterBuilder::with_size(acc.capacity(), acc.num_hashes())
+ .seed(42)
+ .build()
+ .unwrap()
+ )
);
for (max_items, fpp) in [
@@ -406,6 +430,6 @@ fn serialized_bit_layout_matches_cross_language_vector() {
assert_eq!(filter.serialize(), expected);
let restored = BloomFilter::deserialize(&expected).unwrap();
- assert_eq!(restored, filter);
+ assert_eq!(filter_snapshot(&restored), filter_snapshot(&filter));
assert!(restored.contains(0_u64));
}
diff --git a/tests-integration/tests/countmin_test/sketch.rs
b/tests-integration/tests/countmin_test/sketch.rs
index 5f76b8c..86326c2 100644
--- a/tests-integration/tests/countmin_test/sketch.rs
+++ b/tests-integration/tests/countmin_test/sketch.rs
@@ -20,6 +20,7 @@ use std::panic::AssertUnwindSafe;
use std::panic::catch_unwind;
use datasketches::countmin::CountMinSketch;
+use datasketches::countmin::CountMinValue;
use datasketches::countmin::UnsignedCountMinValue;
use datasketches::error::ErrorKind;
use datasketches::hash::value::natural_extend;
@@ -28,6 +29,16 @@ use googletest::assert_that;
use googletest::prelude::ge;
use googletest::prelude::le;
+fn sketch_snapshot<T: CountMinValue>(sketch: &CountMinSketch<T>) -> (u8, u32,
u64, T, Vec<u8>) {
+ (
+ sketch.num_hashes(),
+ sketch.num_buckets(),
+ sketch.seed(),
+ sketch.total_weight(),
+ sketch.serialize(),
+ )
+}
+
#[test]
fn weight_overflow_preserves_unsigned_state() {
let mut sketch = CountMinSketch::<u8>::new(2, 8).unwrap();
@@ -40,12 +51,12 @@ fn weight_overflow_preserves_unsigned_state() {
sketch.update_with_weight("x", 0);
assert!(catch_unwind(AssertUnwindSafe(|| sketch.update("x"))).is_err());
- assert_eq!(sketch, before);
+ assert_eq!(sketch_snapshot(&sketch), sketch_snapshot(&before));
assert_eq!(
sketch.merge(&one).unwrap_err().kind(),
ErrorKind::InvalidArgument
);
- assert_eq!(sketch, before);
+ assert_eq!(sketch_snapshot(&sketch), sketch_snapshot(&before));
}
#[test]
@@ -53,7 +64,8 @@ fn weight_overflow_preserves_signed_state() {
let mut sketch = CountMinSketch::<i8>::new(2, 8).unwrap();
let empty = sketch.clone();
assert!(catch_unwind(AssertUnwindSafe(|| sketch.update_with_weight("x",
i8::MIN))).is_err());
- assert_eq!(sketch, empty);
+ assert_eq!(sketch_snapshot(&sketch), sketch_snapshot(&empty));
+ assert_eq!(sketch.estimate("x"), 0);
sketch.update_with_weight("x", -i8::MAX);
assert_eq!(sketch.total_weight(), i8::MAX);
@@ -61,10 +73,10 @@ fn weight_overflow_preserves_signed_state() {
let before = sketch.clone();
// Cancellation reduces the counter, but still increases the absolute
stream weight.
assert!(catch_unwind(AssertUnwindSafe(|| sketch.update("x"))).is_err());
- assert_eq!(sketch, before);
+ assert_eq!(sketch_snapshot(&sketch), sketch_snapshot(&before));
assert_eq!(
- CountMinSketch::<i8>::deserialize(&sketch.serialize()).unwrap(),
- sketch
+
sketch_snapshot(&CountMinSketch::<i8>::deserialize(&sketch.serialize()).unwrap()),
+ sketch_snapshot(&sketch)
);
}
@@ -338,11 +350,11 @@ fn decay_identity_and_halving_preserve_the_whole_sketch()
{
let mut decayed = sketch.clone();
decayed.decay(1.0);
- assert_eq!(decayed, sketch);
+ assert_eq!(sketch_snapshot(&decayed), sketch_snapshot(&sketch));
decayed.decay(0.5);
sketch.halve();
- assert_eq!(decayed, sketch);
+ assert_eq!(sketch_snapshot(&decayed), sketch_snapshot(&sketch));
}
check([u8::MAX / 2, u8::MAX / 4, 1]);
@@ -445,7 +457,7 @@ fn test_merge_incompatible() {
for other in &incompatible {
let error = left.merge(other).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
- assert_eq!(left, before);
+ assert_eq!(sketch_snapshot(&left), sketch_snapshot(&before));
}
}
@@ -456,7 +468,7 @@ fn value_wrappers_match_portable_item_encodings() {
let mut b = a.clone();
a.update_with_weight(&left, 7);
b.update_with_weight(&right, 7);
- assert_eq!(a, b);
+ assert_eq!(sketch_snapshot(&a), sketch_snapshot(&b));
}
assert_same_item(natural_extend::from_i8(-2), -2i64);
diff --git a/tests-integration/tests/hll_test/union.rs
b/tests-integration/tests/hll_test/union.rs
index 56c4e44..d6e632b 100644
--- a/tests-integration/tests/hll_test/union.rs
+++ b/tests-integration/tests/hll_test/union.rs
@@ -69,6 +69,38 @@ fn assert_same_estimate_and_bounds(actual: &HllSketch,
expected: &HllSketch) {
}
}
+fn canonical_hll_bytes(sketch: &HllSketch) -> Vec<u8> {
+ let mut bytes = sketch.serialize();
+ bytes[4] = 0; // lg_arr depends on table history / compact vs updatable
form
+ let trailing_offset = match bytes[7] & 0x3 {
+ // Set mode stores open-addressing coupons after the 12-byte preamble.
+ 1 => Some(12),
+ // HLL4 stores auxiliary exception coupons after the 40-byte preamble
and 4-bit nibbles.
+ 2 if sketch.target_type() == HllType::Hll4 => {
+ Some(40 + (1usize << (sketch.lg_config_k() - 1)))
+ }
+ _ => None,
+ };
+ if let Some(offset) = trailing_offset {
+ let mut coupons: Vec<u32> = bytes[offset..]
+ .chunks_exact(4)
+ .map(|chunk| u32::from_le_bytes(chunk.try_into().unwrap()))
+ .collect();
+ coupons.sort_unstable();
+ for (dst, coupon) in bytes[offset..].chunks_exact_mut(4).zip(coupons) {
+ dst.copy_from_slice(&coupon.to_le_bytes());
+ }
+ }
+ bytes
+}
+
+fn assert_hll_sketches_eq(actual: &HllSketch, expected: &HllSketch) {
+ assert_eq!(actual.lg_config_k(), expected.lg_config_k());
+ assert_eq!(actual.target_type(), expected.target_type());
+ assert_eq!(actual.is_empty(), expected.is_empty());
+ assert_eq!(canonical_hll_bytes(actual), canonical_hll_bytes(expected));
+}
+
fn serialize_flat_union(first: &HllSketch, second: &HllSketch, third:
&HllSketch) -> Vec<u8> {
let mut union = HllUnion::new(8).unwrap();
union.update(first);
@@ -854,10 +886,10 @@ fn
test_union_supports_shared_queries_after_dense_merges() {
);
assert_eq!(union.serialize(HllType::Hll8), bytes_hll8);
assert_eq!(union.serialize(HllType::Hll6), bytes_hll6);
- assert_eq!(
-
HllSketch::deserialize(&union.serialize(HllType::Hll4)).unwrap(),
- expected_hll4
- );
+ let restored_hll4 =
+
HllSketch::deserialize(&union.serialize(HllType::Hll4)).unwrap();
+ assert_hll_sketches_eq(&restored_hll4, &expected_hll4);
+ assert_same_estimate_and_bounds(&restored_hll4,
&expected_hll4);
});
}
});
diff --git a/tests-integration/tests/hll_test/update.rs
b/tests-integration/tests/hll_test/update.rs
index 50fd0b4..5869cbe 100644
--- a/tests-integration/tests/hll_test/update.rs
+++ b/tests-integration/tests/hll_test/update.rs
@@ -166,30 +166,6 @@ fn test_large_cardinality() {
assert_that!(relative_error, lt(0.05));
}
-#[test]
-fn test_equals_method() {
- let mut sketch1 = HllSketch::new(10, HllType::Hll8).unwrap();
- let mut sketch2 = HllSketch::new(10, HllType::Hll8).unwrap();
-
- // Both start equal (empty)
- assert!(sketch1.eq(&sketch2));
-
- // Add same values to both
- for i in 0..100 {
- sketch1.update(i);
- sketch2.update(i);
- }
-
- // Should still be equal
- assert!(sketch1.eq(&sketch2));
-
- // Add different value to sketch2
- sketch2.update(999);
-
- // Now they're different
- assert!(!sketch1.eq(&sketch2));
-}
-
#[test]
fn test_invalid_lg_k_low_returns_error() {
let error = HllSketch::new(3, HllType::Hll8).unwrap_err();
diff --git a/tests-integration/tests/req_test/bounds.rs
b/tests-integration/tests/req_test/bounds.rs
index a0c6199..74dd47f 100644
--- a/tests-integration/tests/req_test/bounds.rs
+++ b/tests-integration/tests/req_test/bounds.rs
@@ -20,6 +20,7 @@
use datasketches::common::NumStdDev;
use datasketches::common::SearchCriteria;
use datasketches::error::Error;
+use datasketches::error::ErrorKind;
use datasketches::req::RankAccuracy;
use datasketches::req::ReqSketch;
use googletest::assert_that;
@@ -32,7 +33,7 @@ use super::ReqF64;
use super::req_f64;
#[test]
-fn bounds_are_nested_and_in_unit_interval() {
+fn bounds_are_nested_and_in_unit_interval() -> Result<(), Error> {
let mut sketch: ReqSketch<ReqF64> = ReqSketch::new(12,
RankAccuracy::HighRank).unwrap();
for i in 0..50_000 {
@@ -43,12 +44,12 @@ fn bounds_are_nested_and_in_unit_interval() {
let bounds: Vec<(f64, f64)> = [NumStdDev::One, NumStdDev::Two,
NumStdDev::Three]
.into_iter()
.map(|sigma| {
- (
- sketch.rank_lower_bound(rank, sigma),
- sketch.rank_upper_bound(rank, sigma),
- )
+ Ok((
+ sketch.rank_lower_bound(rank, sigma)?,
+ sketch.rank_upper_bound(rank, sigma)?,
+ ))
})
- .collect();
+ .collect::<Result<_, Error>>()?;
for (lower, upper) in &bounds {
assert_that!(*lower, le(*upper));
@@ -61,6 +62,8 @@ fn bounds_are_nested_and_in_unit_interval() {
assert_that!(bounds[2].0, le(bounds[1].0));
assert_that!(bounds[1].1, le(bounds[2].1));
}
+
+ Ok(())
}
#[test]
@@ -80,8 +83,8 @@ fn theoretical_error_bounds_cover_uniform_quantiles() ->
Result<(), Error> {
let estimated_rank = sketch
.rank(&true_quantile, SearchCriteria::Inclusive)
.expect("the sketch is non-empty");
- let lower = sketch.rank_lower_bound(rank, NumStdDev::Three);
- let upper = sketch.rank_upper_bound(rank, NumStdDev::Three);
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Three)?;
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Three)?;
assert_that!(estimated_rank, all!(ge(lower), le(upper)), "rank:
{rank}");
}
@@ -99,10 +102,10 @@ fn hra_and_lra_bounds_are_tighter_at_their_target_end() ->
Result<(), Error> {
lra.update(req_f64(i as f64));
}
- let hra_error = (rank - hra.rank_lower_bound(rank, NumStdDev::Two))
- .max(hra.rank_upper_bound(rank, NumStdDev::Two) - rank);
- let lra_error = (rank - lra.rank_lower_bound(rank, NumStdDev::Two))
- .max(lra.rank_upper_bound(rank, NumStdDev::Two) - rank);
+ let hra_error = (rank - hra.rank_lower_bound(rank, NumStdDev::Two)?)
+ .max(hra.rank_upper_bound(rank, NumStdDev::Two)? - rank);
+ let lra_error = (rank - lra.rank_lower_bound(rank, NumStdDev::Two)?)
+ .max(lra.rank_upper_bound(rank, NumStdDev::Two)? - rank);
if rank >= 0.75 {
assert_that!(hra_error, le(lra_error));
@@ -115,7 +118,7 @@ fn hra_and_lra_bounds_are_tighter_at_their_target_end() ->
Result<(), Error> {
}
#[test]
-fn exact_mode_bounds_are_tight() {
+fn exact_mode_bounds_are_tight() -> Result<(), Error> {
let mut sketch: ReqSketch<ReqF64> = ReqSketch::default();
for i in 0..20 {
@@ -125,14 +128,16 @@ fn exact_mode_bounds_are_tight() {
assert!(!sketch.is_estimation_mode());
for rank in [0.1, 0.25, 0.5, 0.75, 0.9] {
- let lower = sketch.rank_lower_bound(rank, NumStdDev::Two);
- let upper = sketch.rank_upper_bound(rank, NumStdDev::Two);
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Two)?;
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Two)?;
assert_that!((upper - lower) / 2.0, lt(0.05));
}
+
+ Ok(())
}
#[test]
-fn high_rank_accuracy_matches_tight_thresholds() {
+fn high_rank_accuracy_matches_tight_thresholds() -> Result<(), Error> {
let mut sketch: ReqSketch<ReqF64> = ReqSketch::default();
let n = 50_000;
@@ -160,8 +165,35 @@ fn high_rank_accuracy_matches_tight_thresholds() {
}
for rank in [0.9, 0.99, 0.999] {
- let lower = sketch.rank_lower_bound(rank, NumStdDev::Three);
- let upper = sketch.rank_upper_bound(rank, NumStdDev::Three);
+ let lower = sketch.rank_lower_bound(rank, NumStdDev::Three)?;
+ let upper = sketch.rank_upper_bound(rank, NumStdDev::Three)?;
assert_that!(rank, all!(ge(lower), le(upper)));
}
+
+ Ok(())
+}
+
+#[test]
+fn rank_bounds_reject_invalid_ranks_across_sketch_states() {
+ for (n, expected_estimation) in [(0, false), (20, false), (1_000, true)] {
+ let mut sketch: ReqSketch<ReqF64> = ReqSketch::default();
+ for i in 0..n {
+ sketch.update(req_f64(i as f64));
+ }
+ assert_eq!(sketch.is_estimation_mode(), expected_estimation);
+
+ for rank in [f64::NAN, -0.1, 1.1, f64::INFINITY, f64::NEG_INFINITY] {
+ for error in [
+ sketch.rank_lower_bound(rank, NumStdDev::Two).unwrap_err(),
+ sketch.rank_upper_bound(rank, NumStdDev::Two).unwrap_err(),
+ ] {
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ }
+ }
+
+ if !expected_estimation {
+ assert_eq!(sketch.rank_lower_bound(0.5, NumStdDev::Two).unwrap(),
0.5);
+ assert_eq!(sketch.rank_upper_bound(0.5, NumStdDev::Two).unwrap(),
0.5);
+ }
+ }
}
diff --git a/tests-integration/tests/req_test/property.rs
b/tests-integration/tests/req_test/property.rs
index 24d91df..180ea9d 100644
--- a/tests-integration/tests/req_test/property.rs
+++ b/tests-integration/tests/req_test/property.rs
@@ -58,8 +58,14 @@ fn prop_quantile_rank_consistency() {
// interval for the target rank (plus a small cushion for snapping
to a
// stored item). This scales with k and n, unlike a fixed slack,
so it
// actually constrains the result instead of always passing.
- let lower = sketch.rank_lower_bound(rank, NumStdDev::Three) - 0.02;
- let upper = sketch.rank_upper_bound(rank, NumStdDev::Three) + 0.02;
+ let lower = sketch
+ .rank_lower_bound(rank, NumStdDev::Three)
+ .expect("rank_lower_bound should succeed")
+ - 0.02;
+ let upper = sketch
+ .rank_upper_bound(rank, NumStdDev::Three)
+ .expect("rank_upper_bound should succeed")
+ + 0.02;
assert!(
(lower..=upper).contains(&recovered),
"rank {rank} -> quantile {quantile} -> recovered {recovered},
expected within [{lower:.4}, {upper:.4}]"
diff --git a/tests-integration/tests/serde_tests/bloom.rs
b/tests-integration/tests/serde_tests/bloom.rs
index e4a4c74..68e26f3 100644
--- a/tests-integration/tests/serde_tests/bloom.rs
+++ b/tests-integration/tests/serde_tests/bloom.rs
@@ -26,6 +26,16 @@ use googletest::prelude::gt;
use crate::serialization_test_data;
+fn filter_snapshot(filter: &BloomFilter) -> (u64, u16, u64, u64, Vec<u8>) {
+ (
+ filter.capacity(),
+ filter.num_hashes(),
+ filter.seed(),
+ filter.bits_used(),
+ filter.serialize(),
+ )
+}
+
fn test_bloom_filter_file(path: PathBuf, expected_num_items: u64,
expected_num_hashes: u16) {
let bytes = fs::read(&path).unwrap();
let filter1 = BloomFilter::deserialize(&bytes).unwrap();
@@ -62,8 +72,8 @@ fn test_bloom_filter_file(path: PathBuf, expected_num_items:
u64, expected_num_h
});
assert_eq!(
- filter1,
- filter2,
+ filter_snapshot(&filter1),
+ filter_snapshot(&filter2),
"Filter changed after round-trip for {}",
path.display()
);
diff --git a/tests-integration/tests/serde_tests/countmin.rs
b/tests-integration/tests/serde_tests/countmin.rs
index a0a019d..d2eec69 100644
--- a/tests-integration/tests/serde_tests/countmin.rs
+++ b/tests-integration/tests/serde_tests/countmin.rs
@@ -19,6 +19,7 @@ use std::fs;
use std::hash::Hash;
use datasketches::countmin::CountMinSketch;
+use datasketches::countmin::CountMinValue;
use datasketches::error::ErrorKind;
use datasketches::hash::value::natural_extend;
use datasketches::hash::value::raw_bytes;
@@ -28,6 +29,16 @@ use tests_integration::ZERO_HASH_SEED;
use crate::serialization_test_data;
+fn sketch_snapshot<T: CountMinValue>(sketch: &CountMinSketch<T>) -> (u8, u32,
u64, T, Vec<u8>) {
+ (
+ sketch.num_hashes(),
+ sketch.num_buckets(),
+ sketch.seed(),
+ sketch.total_weight(),
+ sketch.serialize(),
+ )
+}
+
fn words_to_bytes<const N: usize>(words: [u64; N]) -> Vec<u8> {
words.into_iter().flat_map(u64::to_le_bytes).collect()
}
@@ -62,7 +73,10 @@ fn v2_reads_and_writes_the_published_image() {
let mut empty = bytes[..16].to_vec();
empty[3] = 1;
assert_eq!(sketch.serialize(), empty);
- assert_eq!(CountMinSketch::<i64>::deserialize(&empty).unwrap(), sketch);
+ assert_eq!(
+ sketch_snapshot(&CountMinSketch::<i64>::deserialize(&empty).unwrap()),
+ sketch_snapshot(&sketch)
+ );
sketch.update_with_weight(1i64, 10);
sketch.update_with_weight(9i64, 810);
@@ -70,7 +84,7 @@ fn v2_reads_and_writes_the_published_image() {
assert_eq!(sketch.serialize(), bytes);
let mut restored = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
- assert_eq!(restored, sketch);
+ assert_eq!(sketch_snapshot(&restored), sketch_snapshot(&sketch));
assert_eq!(restored.estimate(1u64), 10);
assert_eq!(restored.estimate(natural_extend::from_i8(9)), 810);
assert_eq!(restored.estimate(raw_bytes::from_str("apple")), 5);
@@ -164,8 +178,8 @@ fn legacy_image_preserves_wrappers_and_custom_hash_inputs()
{
assert_eq!(sketch.total_weight(), 73);
assert_eq!(sketch.serialize()[1], 1);
assert_eq!(
- CountMinSketch::<i64>::deserialize(&sketch.serialize()).unwrap(),
- sketch
+
sketch_snapshot(&CountMinSketch::<i64>::deserialize(&sketch.serialize()).unwrap()),
+ sketch_snapshot(&sketch)
);
}
@@ -232,7 +246,7 @@ fn rejects_merge_across_serial_versions() {
current.merge(&legacy).unwrap_err().kind(),
ErrorKind::InvalidArgument
);
- assert_eq!(current, before);
+ assert_eq!(sketch_snapshot(¤t), sketch_snapshot(&before));
}
#[test]
diff --git a/tests-integration/tests/serde_tests/hll.rs
b/tests-integration/tests/serde_tests/hll.rs
index 8aed0b1..9e30981 100644
--- a/tests-integration/tests/serde_tests/hll.rs
+++ b/tests-integration/tests/serde_tests/hll.rs
@@ -32,6 +32,42 @@ use googletest::prelude::near;
use crate::serialization_test_data;
+fn canonical_hll_bytes(sketch: &HllSketch) -> Vec<u8> {
+ let mut bytes = sketch.serialize();
+ bytes[4] = 0; // lg_arr depends on table history / compact vs updatable
form
+ let trailing_offset = match bytes[7] & 0x3 {
+ // Set mode stores open-addressing coupons after the 12-byte preamble.
+ 1 => Some(12),
+ // HLL4 stores auxiliary exception coupons after the 40-byte preamble
and 4-bit nibbles.
+ 2 if sketch.target_type() == HllType::Hll4 => {
+ Some(40 + (1usize << (sketch.lg_config_k() - 1)))
+ }
+ _ => None,
+ };
+ if let Some(offset) = trailing_offset {
+ let mut coupons: Vec<u32> = bytes[offset..]
+ .chunks_exact(4)
+ .map(|chunk| u32::from_le_bytes(chunk.try_into().unwrap()))
+ .collect();
+ coupons.sort_unstable();
+ for (dst, coupon) in bytes[offset..].chunks_exact_mut(4).zip(coupons) {
+ dst.copy_from_slice(&coupon.to_le_bytes());
+ }
+ }
+ bytes
+}
+
+fn assert_hll_sketches_eq(actual: &HllSketch, expected: &HllSketch, context:
&str) {
+ assert_eq!(actual.lg_config_k(), expected.lg_config_k(), "{context}");
+ assert_eq!(actual.target_type(), expected.target_type(), "{context}");
+ assert_eq!(actual.is_empty(), expected.is_empty(), "{context}");
+ assert_eq!(
+ canonical_hll_bytes(actual),
+ canonical_hll_bytes(expected),
+ "{context}"
+ );
+}
+
#[test]
fn union_serialization_preserves_result_and_subsequent_updates() {
for hll_type in [HllType::Hll4, HllType::Hll6, HllType::Hll8] {
@@ -55,7 +91,11 @@ fn
union_serialization_preserves_result_and_subsequent_updates() {
union.update_value(value);
restored.update(value);
}
- assert_eq!(union.to_sketch(HllType::Hll8), restored);
+ assert_hll_sketches_eq(
+ &union.to_sketch(HllType::Hll8),
+ &restored,
+ &format!("hll_type={hll_type:?}, count={count},
lg_max_k={lg_max_k}"),
+ );
union.reset();
for target_type in [HllType::Hll4, HllType::Hll6,
HllType::Hll8] {
@@ -94,7 +134,11 @@ fn assert_union_matches_sketch(
assert_eq!(restored.target_type(), target_type);
assert_eq!(restored.lg_config_k(), expected.lg_config_k());
assert_eq!(restored.is_empty(), expected.is_empty());
- assert_eq!(restored, expected);
+ assert_hll_sketches_eq(
+ &restored,
+ &expected,
+ &format!("target_type={target_type:?}, lg_k={}", union.lg_config_k()),
+ );
assert_eq!(restored.estimate(), expected.estimate());
assert_eq!(restored.composite_estimate(), expected.composite_estimate());
assert_eq!(restored.estimate(), union.estimate());
@@ -287,11 +331,13 @@ fn test_sketch_file(path: PathBuf, expected_cardinality:
usize, expected_lg_k: u
);
// Check that the sketches are functionally equal
- assert_eq!(
- sketch1,
- sketch2,
- "Sketches are not equal after round-trip for {}",
- path.display()
+ assert_hll_sketches_eq(
+ &sketch1,
+ &sketch2,
+ &format!(
+ "Sketches are not equal after round-trip for {}",
+ path.display()
+ ),
);
// Verify estimates match after round-trip
@@ -363,7 +409,7 @@ fn
hll_mode_round_trip_preserves_registers_and_rejects_truncation() {
let bytes = sketch.serialize();
let restored = HllSketch::deserialize(&bytes).unwrap();
- assert_eq!(restored, sketch, "hll_type: {hll_type:?}");
+ assert_hll_sketches_eq(&restored, &sketch, &format!("hll_type:
{hll_type:?}"));
assert!(HllSketch::deserialize(&bytes[..bytes.len() - 1]).is_err());
}
}
@@ -397,9 +443,10 @@ fn hll4_updatable_aux_table_matches_compact_image() {
updatable.extend_from_slice(&coupon.to_le_bytes());
}
- assert_eq!(
- HllSketch::deserialize(&updatable).unwrap(),
- HllSketch::deserialize(&compact).unwrap()
+ assert_hll_sketches_eq(
+ &HllSketch::deserialize(&updatable).unwrap(),
+ &HllSketch::deserialize(&compact).unwrap(),
+ "updatable vs compact HLL4",
);
}
diff --git a/tests-integration/tests/serde_tests/kll.rs
b/tests-integration/tests/serde_tests/kll.rs
index c6ab416..dd023da 100644
--- a/tests-integration/tests/serde_tests/kll.rs
+++ b/tests-integration/tests/serde_tests/kll.rs
@@ -408,9 +408,12 @@ fn test_custom_kll_value_roundtrip() {
let decoded =
KllSketch::<Record>::deserialize(&sketch.serialize()).unwrap();
- assert_eq!(decoded, sketch);
+ assert_eq!(decoded.serialize(), sketch.serialize());
+ assert_eq!(decoded.k(), sketch.k());
assert_eq!(decoded.n(), 1_000);
assert_eq!(decoded.num_retained(), sketch.num_retained());
+ assert_eq!(decoded.min_item(), sketch.min_item());
+ assert_eq!(decoded.max_item(), sketch.max_item());
}
#[test]
diff --git a/tests-integration/tests/serde_tests/xor.rs
b/tests-integration/tests/serde_tests/xor.rs
index cbff98e..0c05506 100644
--- a/tests-integration/tests/serde_tests/xor.rs
+++ b/tests-integration/tests/serde_tests/xor.rs
@@ -75,7 +75,7 @@ fn serialization_round_trips_standard_fingerprint_types() {
let restored = XorFilter::deserialize(&bytes).unwrap();
assert_eq!(restored.filter_type(), ty);
- assert_eq!(restored, original);
+ assert_eq!(restored.serialize(), bytes);
for hash in 0..count {
assert!(restored.contains_hash(hash));
}
@@ -154,7 +154,10 @@ fn trailing_storage_is_ignored() {
let mut bytes = original.serialize();
bytes.extend_from_slice(&[0xaa; 16]);
- assert_eq!(XorFilter::deserialize(&bytes).unwrap(), original);
+ assert_eq!(
+ XorFilter::deserialize(&bytes).unwrap().serialize(),
+ original.serialize()
+ );
}
}
diff --git a/tests-integration/tests/xor_test/filter.rs
b/tests-integration/tests/xor_test/filter.rs
index c0bb974..37fd347 100644
--- a/tests-integration/tests/xor_test/filter.rs
+++ b/tests-integration/tests/xor_test/filter.rs
@@ -66,16 +66,16 @@ fn builder_deduplicates_values_and_hashes() {
.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(),
+ duplicate_values.build().unwrap().serialize(),
+ distinct_values.build().unwrap().serialize(),
);
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(),
+ hashes.build().unwrap().serialize(),
+ XorFilter::from_hashes(&[7, 11], ty).unwrap().serialize(),
);
}
}
@@ -96,13 +96,23 @@ fn
default_seed_constructors_and_builder_clone_behave_consistently() {
.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.serialize(),
+ zero_seeded_builder.build().unwrap().serialize(),
+ );
assert_eq!(cloned_filter.filter_type(), ty);
- assert_ne!(cloned_filter, extended_builder.build().unwrap());
+ assert_ne!(
+ cloned_filter.serialize(),
+ extended_builder.build().unwrap().serialize(),
+ );
assert_eq!(
- XorFilter::from_hashes(&[10, 20, 30], ty).unwrap(),
- XorFilter::from_hashes_with_seed(&[10, 20, 30], ty, 0).unwrap(),
+ XorFilter::from_hashes(&[10, 20, 30], ty)
+ .unwrap()
+ .serialize(),
+ XorFilter::from_hashes_with_seed(&[10, 20, 30], ty, 0)
+ .unwrap()
+ .serialize(),
);
}
}
@@ -125,7 +135,10 @@ fn
equivalent_borrowed_and_value_inputs_build_identical_filters() {
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());
+ assert_eq!(
+ str_filter.serialize(),
+ by_str_batch.build().unwrap().serialize(),
+ );
for s in &strings {
assert!(str_filter.contains(s));
assert!(str_filter.contains(s.as_str()));
@@ -138,7 +151,10 @@ fn
equivalent_borrowed_and_value_inputs_build_identical_filters() {
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());
+ assert_eq!(
+ blob_filter.serialize(),
+ by_blob_batch.build().unwrap().serialize(),
+ );
for blob in &blobs {
assert!(blob_filter.contains(blob));
assert!(blob_filter.contains(blob.as_slice()));
@@ -153,7 +169,10 @@ fn
equivalent_borrowed_and_value_inputs_build_identical_filters() {
.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());
+ assert_eq!(
+ mixed_filter.serialize(),
+ by_mixed_batch.build().unwrap().serialize(),
+ );
for id in &ids {
assert!(mixed_filter.contains(id));
assert!(mixed_filter.contains(*id));
@@ -250,7 +269,10 @@ fn
builder_chaining_and_seed_override_behave_consistently() {
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());
+ assert_eq!(
+ chained.serialize(),
+ step_by_step.build().unwrap().serialize(),
+ );
for value in ["alpha", "beta", "gamma"] {
assert!(chained.contains(value));
@@ -266,20 +288,22 @@ fn
builder_chaining_and_seed_override_behave_consistently() {
.build()
.unwrap();
assert_eq!(
- overridden,
+ overridden.serialize(),
XorFilterBuilder::new(ty)
.seed(42)
.update_values(["gamma", "alpha", "beta"])
.build()
- .unwrap(),
+ .unwrap()
+ .serialize(),
);
assert_ne!(
- overridden,
+ overridden.serialize(),
XorFilterBuilder::new(ty)
.seed(1)
.update_values(["alpha", "beta", "gamma"])
.build()
- .unwrap(),
+ .unwrap()
+ .serialize(),
);
}
}
@@ -310,8 +334,10 @@ fn
construction_recovers_after_an_unpeelable_first_attempt() {
let mut reversed = keys.clone();
reversed.reverse();
assert_eq!(
- filter,
- XorFilter::from_hashes_with_seed(&reversed, kind, 1).unwrap(),
+ filter.serialize(),
+ XorFilter::from_hashes_with_seed(&reversed, kind, 1)
+ .unwrap()
+ .serialize(),
);
let builder_filter = XorFilterBuilder::new(kind)
@@ -320,6 +346,6 @@ fn
construction_recovers_after_an_unpeelable_first_attempt() {
.seed(1)
.build()
.unwrap();
- assert_eq!(builder_filter, filter);
+ assert_eq!(builder_filter.serialize(), filter.serialize());
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]