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 6d232dc  refactor(xor): encapsulate width-polymorphic operations on 
Fingerprints (#358)
6d232dc is described below

commit 6d232dcaf289a933f64a752ffe289fe74b2eb891
Author: tison <[email protected]>
AuthorDate: Thu Nov 12 17:26:52 2026 +0800

    refactor(xor): encapsulate width-polymorphic operations on Fingerprints 
(#358)
---
 datasketches/src/xor/filter.rs | 237 +++++++++++++++++++++--------------------
 1 file changed, 122 insertions(+), 115 deletions(-)

diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs
index eb2a651..d3d984d 100644
--- a/datasketches/src/xor/filter.rs
+++ b/datasketches/src/xor/filter.rs
@@ -18,7 +18,6 @@
 use std::fmt;
 use std::hash::Hash;
 use std::hash::Hasher;
-use std::ops::BitXor;
 
 use crate::codec::SketchBytes;
 use crate::codec::SketchSlice;
@@ -82,13 +81,120 @@ enum Fingerprints {
 }
 
 impl Fingerprints {
+    fn assign(
+        filter_type: XorFilterType,
+        capacity: usize,
+        segment_length: usize,
+        stack_hash: &[u64],
+        stack_index: &[u32],
+    ) -> Self {
+        macro_rules! assign_slots {
+            ($ty:ty) => {{
+                let mut slots: Box<[$ty]> = vec![0; 
capacity].into_boxed_slice();
+                for (&hash, &index) in 
stack_hash.iter().zip(stack_index).rev() {
+                    let [h0, h1, h2] = indexes(hash, segment_length);
+                    slots[index as usize] =
+                        (fingerprint(hash) as $ty) ^ slots[h0] ^ slots[h1] ^ 
slots[h2];
+                }
+                slots
+            }};
+        }
+
+        match filter_type {
+            XorFilterType::Xor8 => Self::Xor8(assign_slots!(u8)),
+            XorFilterType::Xor16 => Self::Xor16(assign_slots!(u16)),
+            XorFilterType::Xor32 => Self::Xor32(assign_slots!(u32)),
+        }
+    }
+
+    #[inline(always)]
+    fn contains(&self, mixed: u64, segment_length: usize) -> bool {
+        let [h0, h1, h2] = indexes(mixed, segment_length);
+        match self {
+            Self::Xor8(slots) => fingerprint(mixed) as u8 == slots[h0] ^ 
slots[h1] ^ slots[h2],
+            Self::Xor16(slots) => fingerprint(mixed) as u16 == slots[h0] ^ 
slots[h1] ^ slots[h2],
+            Self::Xor32(slots) => fingerprint(mixed) as u32 == slots[h0] ^ 
slots[h1] ^ slots[h2],
+        }
+    }
+
+    const fn filter_type(&self) -> XorFilterType {
+        match self {
+            Self::Xor8(_) => XorFilterType::Xor8,
+            Self::Xor16(_) => XorFilterType::Xor16,
+            Self::Xor32(_) => XorFilterType::Xor32,
+        }
+    }
+
     fn byte_len(&self) -> usize {
         match self {
-            Self::Xor8(values) => size_of_val::<[u8]>(values),
-            Self::Xor16(values) => size_of_val::<[u16]>(values),
-            Self::Xor32(values) => size_of_val::<[u32]>(values),
+            Self::Xor8(slots) => size_of_val::<[u8]>(slots),
+            Self::Xor16(slots) => size_of_val::<[u16]>(slots),
+            Self::Xor32(slots) => size_of_val::<[u32]>(slots),
+        }
+    }
+
+    fn serialize(&self, bytes: &mut SketchBytes) {
+        match self {
+            Self::Xor8(slots) => bytes.write(slots),
+            Self::Xor16(slots) => {
+                for &slot in slots.iter() {
+                    bytes.write_u16_le(slot);
+                }
+            }
+            Self::Xor32(slots) => {
+                for &slot in slots.iter() {
+                    bytes.write_u32_le(slot);
+                }
+            }
         }
     }
+
+    fn deserialize(
+        filter_type: XorFilterType,
+        capacity: usize,
+        mut cursor: SketchSlice<'_>,
+    ) -> Result<Self, Error> {
+        let fingerprint_bytes = capacity
+            .checked_mul(filter_type.bytes_per_fingerprint())
+            .ok_or_else(|| Error::deserial("xor filter fingerprint size 
overflow"))?;
+        if cursor.remaining().len() < fingerprint_bytes {
+            return Err(Error::insufficient_data_of(
+                "fingerprints",
+                format!(
+                    "expected {fingerprint_bytes} bytes, got {}",
+                    cursor.remaining().len()
+                ),
+            ));
+        }
+
+        let fingerprints = match filter_type {
+            XorFilterType::Xor8 => 
Self::Xor8(cursor.remaining()[..capacity].into()),
+            XorFilterType::Xor16 => {
+                let mut slots = Vec::with_capacity(capacity);
+                for _ in 0..capacity {
+                    slots.push(
+                        cursor
+                            .read_u16_le()
+                            .map_err(insufficient_data("fingerprints"))?,
+                    );
+                }
+                Self::Xor16(slots.into_boxed_slice())
+            }
+            XorFilterType::Xor32 => {
+                let mut slots = Vec::with_capacity(capacity);
+                for _ in 0..capacity {
+                    slots.push(
+                        cursor
+                            .read_u32_le()
+                            .map_err(insufficient_data("fingerprints"))?,
+                    );
+                }
+                Self::Xor32(slots.into_boxed_slice())
+            }
+        };
+
+        Ok(fingerprints)
+    }
 }
 
 /// An [`XorFilter`] builder for values or precomputed hashes.
@@ -277,29 +383,13 @@ impl XorFilter {
         drop(count);
         drop(queue);
 
-        let fingerprints = match filter_type {
-            XorFilterType::Xor8 => Fingerprints::Xor8(assign_fingerprints(
-                capacity,
-                segment_length,
-                &stack_hash,
-                &stack_index,
-                |hash| fingerprint(hash) as u8,
-            )),
-            XorFilterType::Xor16 => Fingerprints::Xor16(assign_fingerprints(
-                capacity,
-                segment_length,
-                &stack_hash,
-                &stack_index,
-                |hash| fingerprint(hash) as u16,
-            )),
-            XorFilterType::Xor32 => Fingerprints::Xor32(assign_fingerprints(
-                capacity,
-                segment_length,
-                &stack_hash,
-                &stack_index,
-                |hash| fingerprint(hash) as u32,
-            )),
-        };
+        let fingerprints = Fingerprints::assign(
+            filter_type,
+            capacity,
+            segment_length,
+            &stack_hash,
+            &stack_index,
+        );
 
         Ok(Self {
             segment_length,
@@ -320,32 +410,16 @@ impl XorFilter {
     /// Returns `true` if a precomputed 64-bit hash is possibly in the input 
set.
     ///
     /// Use the same hash function for construction and queries.
-    // Keep the width dispatch in the caller's hot loop, including across 
crates.
+    // Inline through Fingerprints::contains so width dispatch stays in the 
caller's hot loop.
     #[inline(always)]
     pub fn contains_hash(&self, hash: u64) -> bool {
         let mixed = mix(hash, self.seed);
-        let [h0, h1, h2] = indexes(mixed, self.segment_length);
-
-        match &self.fingerprints {
-            Fingerprints::Xor8(fingerprints) => {
-                fingerprint(mixed) as u8 == fingerprints[h0] ^ 
fingerprints[h1] ^ fingerprints[h2]
-            }
-            Fingerprints::Xor16(fingerprints) => {
-                fingerprint(mixed) as u16 == fingerprints[h0] ^ 
fingerprints[h1] ^ fingerprints[h2]
-            }
-            Fingerprints::Xor32(fingerprints) => {
-                fingerprint(mixed) as u32 == fingerprints[h0] ^ 
fingerprints[h1] ^ fingerprints[h2]
-            }
-        }
+        self.fingerprints.contains(mixed, self.segment_length)
     }
 
     /// Returns the fingerprint representation used by this filter.
     pub fn filter_type(&self) -> XorFilterType {
-        match &self.fingerprints {
-            Fingerprints::Xor8(_) => XorFilterType::Xor8,
-            Fingerprints::Xor16(_) => XorFilterType::Xor16,
-            Fingerprints::Xor32(_) => XorFilterType::Xor32,
-        }
+        self.fingerprints.filter_type()
     }
 
     /// Returns the estimated in-memory size of the filter in bytes.
@@ -366,20 +440,7 @@ impl XorFilter {
         bytes.write_u64_le(self.seed);
         bytes.write_i32_le(self.segment_length as i32);
         bytes.write_u32_le(0); // Pad the preamble to three 64-bit words.
-
-        match &self.fingerprints {
-            Fingerprints::Xor8(fingerprints) => bytes.write(fingerprints),
-            Fingerprints::Xor16(fingerprints) => {
-                for &fingerprint in fingerprints.iter() {
-                    bytes.write_u16_le(fingerprint);
-                }
-            }
-            Fingerprints::Xor32(fingerprints) => {
-                for &fingerprint in fingerprints.iter() {
-                    bytes.write_u32_le(fingerprint);
-                }
-            }
-        }
+        self.fingerprints.serialize(&mut bytes);
 
         bytes.into_bytes()
     }
@@ -456,44 +517,7 @@ impl XorFilter {
             )));
         }
 
-        let fingerprint_bytes = capacity
-            .checked_mul(filter_type.bytes_per_fingerprint())
-            .ok_or_else(|| Error::deserial("xor filter fingerprint size 
overflow"))?;
-        if cursor.remaining().len() < fingerprint_bytes {
-            return Err(Error::insufficient_data_of(
-                "fingerprints",
-                format!(
-                    "expected {fingerprint_bytes} bytes, got {}",
-                    cursor.remaining().len()
-                ),
-            ));
-        }
-
-        let fingerprints = match filter_type {
-            XorFilterType::Xor8 => 
Fingerprints::Xor8(cursor.remaining()[..capacity].into()),
-            XorFilterType::Xor16 => {
-                let mut values = Vec::with_capacity(capacity);
-                for _ in 0..capacity {
-                    values.push(
-                        cursor
-                            .read_u16_le()
-                            .map_err(insufficient_data("fingerprints"))?,
-                    );
-                }
-                Fingerprints::Xor16(values.into_boxed_slice())
-            }
-            XorFilterType::Xor32 => {
-                let mut values = Vec::with_capacity(capacity);
-                for _ in 0..capacity {
-                    values.push(
-                        cursor
-                            .read_u32_le()
-                            .map_err(insufficient_data("fingerprints"))?,
-                    );
-                }
-                Fingerprints::Xor32(values.into_boxed_slice())
-            }
-        };
+        let fingerprints = Fingerprints::deserialize(filter_type, capacity, 
cursor)?;
 
         Ok(Self {
             segment_length,
@@ -652,23 +676,6 @@ fn peel_block<const BLOCK: usize>(
     }
 }
 
-fn assign_fingerprints<T: Copy + Default + BitXor<Output = T>>(
-    capacity: usize,
-    segment_length: usize,
-    stack_hash: &[u64],
-    stack_index: &[u32],
-    fingerprint_of: impl Fn(u64) -> T,
-) -> Box<[T]> {
-    let mut fingerprints = vec![T::default(); capacity].into_boxed_slice();
-    for (&hash, &index) in stack_hash.iter().zip(stack_index).rev() {
-        let index = index as usize;
-        let [h0, h1, h2] = indexes(hash, segment_length);
-        fingerprints[index] =
-            fingerprint_of(hash) ^ fingerprints[h0] ^ fingerprints[h1] ^ 
fingerprints[h2];
-    }
-    fingerprints
-}
-
 #[inline]
 fn indexes(hash: u64, segment_length: usize) -> [usize; 3] {
     [


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to