This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch codex/kll-api-and-performance in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit f6868d264e0189b4cb61169a8a4dda17e7175af9 Author: tison <[email protected]> AuthorDate: Wed Sep 2 12:08:29 2026 +0800 refactor(kll): unify item ordering and serialization --- datasketches/src/kll/mod.rs | 8 +- datasketches/src/kll/order.rs | 57 ++++++ datasketches/src/kll/sketch.rs | 269 ++++------------------------- datasketches/src/kll/sorted_view.rs | 31 ++-- datasketches/src/kll/value.rs | 121 +++++++++++++ tests-integration/tests/kll_test/sketch.rs | 6 +- tests-integration/tests/serde_tests/kll.rs | 4 + 7 files changed, 237 insertions(+), 259 deletions(-) diff --git a/datasketches/src/kll/mod.rs b/datasketches/src/kll/mod.rs index c98a931..cf7679d 100644 --- a/datasketches/src/kll/mod.rs +++ b/datasketches/src/kll/mod.rs @@ -37,14 +37,16 @@ //! ``` mod capacity; +mod order; mod serialization; mod sketch; mod sorted_view; +mod value; -pub use self::sketch::KllComparator; -pub use self::sketch::KllItem; +pub use self::order::KllComparator; +pub use self::order::NaturalOrder; pub use self::sketch::KllSketch; -pub use self::sketch::NaturalOrder; +pub use self::value::KllValue; /// Default value of parameter k. const DEFAULT_K: u16 = 200; diff --git a/datasketches/src/kll/order.rs b/datasketches/src/kll/order.rs new file mode 100644 index 0000000..daf2264 --- /dev/null +++ b/datasketches/src/kll/order.rs @@ -0,0 +1,57 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::cmp::Ordering; + +/// Defines the ordering used by a KLL sketch. +/// +/// Accepted values must form a total order. Sketches can be merged only when their comparators are +/// compatible: they must accept the same values and order every pair of accepted values +/// identically. +pub trait KllComparator<T>: Clone { + /// Compares two accepted values. + fn compare(&self, left: &T, right: &T) -> Ordering; + + /// Returns whether `item` belongs to this comparator's ordered domain. + /// + /// Updates with rejected values are ignored. The default accepts every value. + fn accepts(&self, _item: &T) -> bool { + true + } + + /// Returns whether `other` defines the same ordered domain and comparison semantics. + fn is_compatible(&self, other: &Self) -> bool; +} + +/// Uses the value's natural partial ordering and rejects unordered values such as NaN. +#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)] +pub struct NaturalOrder; + +impl<T: PartialOrd> KllComparator<T> for NaturalOrder { + fn compare(&self, left: &T, right: &T) -> Ordering { + left.partial_cmp(right) + .expect("accepted KLL values must be totally ordered") + } + + fn accepts(&self, item: &T) -> bool { + item.partial_cmp(item).is_some() + } + + fn is_compatible(&self, _other: &Self) -> bool { + true + } +} diff --git a/datasketches/src/kll/sketch.rs b/datasketches/src/kll/sketch.rs index f1cf175..8153bd0 100644 --- a/datasketches/src/kll/sketch.rs +++ b/datasketches/src/kll/sketch.rs @@ -23,6 +23,8 @@ use super::MAX_K; use super::MIN_K; use super::capacity::level_capacity; use super::capacity::total_capacity; +use super::order::KllComparator; +use super::order::NaturalOrder; use super::serialization::DATA_START; use super::serialization::DATA_START_SINGLE_ITEM; use super::serialization::EMPTY_SIZE_BYTES; @@ -35,6 +37,7 @@ use super::serialization::PREAMBLE_INTS_SHORT; use super::serialization::SERIAL_VERSION_1; use super::serialization::SERIAL_VERSION_2; use super::sorted_view::build_sorted_view; +use super::value::KllValue; use crate::codec::SketchBytes; use crate::codec::SketchSlice; use crate::codec::assert::ensure_serial_version_is; @@ -42,53 +45,6 @@ use crate::codec::assert::insufficient_data; use crate::codec::family::Family; use crate::error::Error; -/// Trait implemented by item types supported by [`KllSketch`]. -/// -/// Implementations must provide a total ordering via `cmp`. -/// For floating-point types, ensure `cmp` handles NaN consistently and `is_nan` -/// returns true for values that should be ignored by updates. -pub trait KllItem: Clone { - /// Compare two items. - fn cmp(a: &Self, b: &Self) -> Ordering; - - /// Returns true if the item is NaN. - fn is_nan(_value: &Self) -> bool { - false - } -} - -/// Ordering policy used by a [`KllSketch`]. -/// -/// A sketch and every sketch merged into it must use equivalent ordering policies. -pub trait KllComparator<T>: Clone { - /// Compare two items. - fn compare(&self, left: &T, right: &T) -> Ordering; -} - -/// Uses the natural ordering supplied by [`KllItem::cmp`]. -#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)] -pub struct NaturalOrder; - -impl<T: KllItem> KllComparator<T> for NaturalOrder { - fn compare(&self, left: &T, right: &T) -> Ordering { - T::cmp(left, right) - } -} - -trait KllSerde: KllItem { - /// Minimum serialized size in bytes for one item. - const MIN_SERIALIZED_SIZE: usize; - - /// Serialized size in bytes. - fn serialized_size(value: &Self) -> usize; - - /// Serialize a single item into the buffer. - fn serialize(value: &Self, bytes: &mut SketchBytes); - - /// Deserialize a single item from the input. - fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error>; -} - /// KLL sketch for estimating quantiles and ranks. /// /// See the [kll module level documentation](crate::kll) for more. @@ -105,7 +61,7 @@ pub struct KllSketch<T, C = NaturalOrder> { max_item: Option<T>, } -impl<T: KllItem> Default for KllSketch<T> { +impl<T: Clone + PartialOrd> Default for KllSketch<T> { fn default() -> Self { Self::make( NaturalOrder, @@ -120,7 +76,7 @@ impl<T: KllItem> Default for KllSketch<T> { } } -impl<T: KllItem> KllSketch<T> { +impl<T: Clone + PartialOrd> KllSketch<T> { /// Creates a new sketch with the given value of k. /// /// # Errors @@ -139,7 +95,7 @@ impl<T: KllItem> KllSketch<T> { } } -impl<T: KllItem, C: KllComparator<T>> KllSketch<T, C> { +impl<T: Clone, C: KllComparator<T>> KllSketch<T, C> { /// Creates a new sketch with the given value of k and ordering policy. /// /// # Errors @@ -207,7 +163,7 @@ impl<T: KllItem, C: KllComparator<T>> KllSketch<T, C> { /// /// NaN values are ignored for floating-point types. pub fn update(&mut self, item: T) { - if T::is_nan(&item) { + if !self.comparator.accepts(&item) { return; } self.update_min_max(&item); @@ -307,7 +263,7 @@ impl<T: KllItem, C: KllComparator<T>> KllSketch<T, C> { } } -fn serialized_size<T: KllSerde, C: KllComparator<T>>(sketch: &KllSketch<T, C>) -> usize { +fn serialized_size<T: KllValue, C: KllComparator<T>>(sketch: &KllSketch<T, C>) -> usize { if sketch.is_empty() { return EMPTY_SIZE_BYTES; } @@ -331,7 +287,7 @@ fn serialized_size<T: KllSerde, C: KllComparator<T>>(sketch: &KllSketch<T, C>) - size } -fn serialize_with_serde<T: KllSerde, C: KllComparator<T>>(sketch: &KllSketch<T, C>) -> Vec<u8> { +fn serialize_with_serde<T: KllValue, C: KllComparator<T>>(sketch: &KllSketch<T, C>) -> Vec<u8> { let size = serialized_size(sketch); let mut bytes = SketchBytes::with_capacity(size); @@ -403,7 +359,7 @@ fn serialize_with_serde<T: KllSerde, C: KllComparator<T>>(sketch: &KllSketch<T, bytes.into_bytes() } -fn deserialize_with_serde<T: KllSerde, C: KllComparator<T>>( +fn deserialize_with_serde<T: KllValue, C: KllComparator<T>>( bytes: &[u8], comparator: C, ) -> Result<KllSketch<T, C>, Error> { @@ -590,83 +546,36 @@ fn deserialize_with_serde<T: KllSerde, C: KllComparator<T>>( Ok(sketch) } -impl<C: KllComparator<f32>> KllSketch<f32, C> { - /// Serializes the sketch to bytes. - pub fn serialize(&self) -> Vec<u8> { - serialize_with_serde(self) - } - - /// Deserializes a sketch using the supplied ordering policy. - pub fn deserialize_with_comparator(bytes: &[u8], comparator: C) -> Result<Self, Error> { - deserialize_with_serde(bytes, comparator) - } -} - -impl KllSketch<f32> { - /// Deserializes a sketch from bytes. - pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> { - deserialize_with_serde(bytes, NaturalOrder) - } -} - -impl<C: KllComparator<f64>> KllSketch<f64, C> { - /// Serializes the sketch to bytes. - pub fn serialize(&self) -> Vec<u8> { - serialize_with_serde(self) - } - - /// Deserializes a sketch using the supplied ordering policy. - pub fn deserialize_with_comparator(bytes: &[u8], comparator: C) -> Result<Self, Error> { - deserialize_with_serde(bytes, comparator) - } -} - -impl KllSketch<f64> { - /// Deserializes a sketch from bytes. - pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> { - deserialize_with_serde(bytes, NaturalOrder) - } -} - -impl<C: KllComparator<i64>> KllSketch<i64, C> { - /// Serializes the sketch to bytes. - pub fn serialize(&self) -> Vec<u8> { - serialize_with_serde(self) - } - - /// Deserializes a sketch using the supplied ordering policy. - pub fn deserialize_with_comparator(bytes: &[u8], comparator: C) -> Result<Self, Error> { - deserialize_with_serde(bytes, comparator) - } -} - -impl KllSketch<i64> { - /// Deserializes a sketch from bytes. - pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> { - deserialize_with_serde(bytes, NaturalOrder) - } -} - -impl<C: KllComparator<String>> KllSketch<String, C> { +impl<T: KllValue, C: KllComparator<T>> KllSketch<T, C> { /// Serializes the sketch to bytes. pub fn serialize(&self) -> Vec<u8> { serialize_with_serde(self) } /// Deserializes a sketch using the supplied ordering policy. + /// + /// # Errors + /// + /// Returns `InvalidData` if the image is truncated, malformed, or inconsistent with + /// `comparator`. pub fn deserialize_with_comparator(bytes: &[u8], comparator: C) -> Result<Self, Error> { deserialize_with_serde(bytes, comparator) } } -impl KllSketch<String> { +impl<T: KllValue + PartialOrd> KllSketch<T> { /// Deserializes a sketch from bytes. + /// + /// # Errors + /// + /// Returns `InvalidData` if the image is truncated, malformed, or contains values that are not + /// naturally ordered. pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> { deserialize_with_serde(bytes, NaturalOrder) } } -impl<T: KllItem, C: KllComparator<T>> KllSketch<T, C> { +impl<T: Clone, C: KllComparator<T>> KllSketch<T, C> { fn make( comparator: C, k: u16, @@ -863,8 +772,10 @@ impl<T: KllItem, C: KllComparator<T>> KllSketch<T, C> { .as_ref() .ok_or_else(|| Error::deserial("non-empty sketch must have a maximum item"))?; - if T::is_nan(min_item) || T::is_nan(max_item) { - return Err(Error::deserial("minimum and maximum items must not be NaN")); + if !self.comparator.accepts(min_item) || !self.comparator.accepts(max_item) { + return Err(Error::deserial( + "minimum and maximum items must belong to the comparator's ordered domain", + )); } if self.comparator.compare(min_item, max_item) == Ordering::Greater { return Err(Error::deserial( @@ -894,8 +805,10 @@ impl<T: KllItem, C: KllComparator<T>> KllSketch<T, C> { } for item in level { - if T::is_nan(item) { - return Err(Error::deserial("retained items must not be NaN")); + if !self.comparator.accepts(item) { + return Err(Error::deserial( + "retained items must belong to the comparator's ordered domain", + )); } if self.comparator.compare(item, min_item) == Ordering::Less || self.comparator.compare(item, max_item) == Ordering::Greater @@ -933,7 +846,7 @@ fn normalized_rank_error(k: u16, pmf: bool) -> f64 { } } -fn downsample<T: KllItem>(items: Vec<T>, offset: bool, use_up: bool) -> Vec<T> { +fn downsample<T: Clone>(items: Vec<T>, offset: bool, use_up: bool) -> Vec<T> { let len = items.len(); debug_assert!(len % 2 == 0, "length must be even"); let offset = usize::from(offset); @@ -958,7 +871,7 @@ fn take_leftover<T>(items: &mut Vec<T>, level: usize, is_level_zero_sorted: bool } } -fn merge_sorted_vec<T: KllItem, C: KllComparator<T>>( +fn merge_sorted_vec<T: Clone, C: KllComparator<T>>( left: Vec<T>, right: Vec<T>, comparator: &C, @@ -979,7 +892,7 @@ fn merge_sorted_vec<T: KllItem, C: KllComparator<T>>( merged } -fn general_compress<T: KllItem, C: KllComparator<T>>( +fn general_compress<T: Clone, C: KllComparator<T>>( mut levels_in: Vec<Vec<T>>, k: u16, m: u8, @@ -1052,117 +965,3 @@ fn general_compress<T: KllItem, C: KllComparator<T>>( levels_out.truncate(current_num_levels); levels_out } - -impl KllItem for f32 { - fn cmp(a: &Self, b: &Self) -> Ordering { - a.partial_cmp(b).unwrap_or(Ordering::Greater) - } - - fn is_nan(value: &Self) -> bool { - value.is_nan() - } -} - -impl KllSerde for f32 { - const MIN_SERIALIZED_SIZE: usize = 4; - - fn serialized_size(_value: &Self) -> usize { - 4 - } - - fn serialize(value: &Self, bytes: &mut SketchBytes) { - bytes.write_f32_le(*value); - } - - fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { - input - .read_f32_le() - .map_err(|_| Error::insufficient_data("f32")) - } -} - -impl KllItem for f64 { - fn cmp(a: &Self, b: &Self) -> Ordering { - a.partial_cmp(b).unwrap_or(Ordering::Greater) - } - - fn is_nan(value: &Self) -> bool { - value.is_nan() - } -} - -impl KllSerde for f64 { - const MIN_SERIALIZED_SIZE: usize = 8; - - fn serialized_size(_value: &Self) -> usize { - 8 - } - - fn serialize(value: &Self, bytes: &mut SketchBytes) { - bytes.write_f64_le(*value); - } - - fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { - input - .read_f64_le() - .map_err(|_| Error::insufficient_data("f64")) - } -} - -impl KllItem for i64 { - fn cmp(a: &Self, b: &Self) -> Ordering { - a.cmp(b) - } -} - -impl KllSerde for i64 { - const MIN_SERIALIZED_SIZE: usize = 8; - - fn serialized_size(_value: &Self) -> usize { - 8 - } - - fn serialize(value: &Self, bytes: &mut SketchBytes) { - bytes.write_i64_le(*value); - } - - fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { - input - .read_i64_le() - .map_err(|_| Error::insufficient_data("i64")) - } -} - -impl KllItem for String { - fn cmp(a: &Self, b: &Self) -> Ordering { - a.cmp(b) - } -} - -impl KllSerde for String { - const MIN_SERIALIZED_SIZE: usize = 4; - - fn serialized_size(value: &Self) -> usize { - 4 + value.len() - } - - fn serialize(value: &Self, bytes: &mut SketchBytes) { - bytes.write_u32_le(value.len() as u32); - bytes.write(value.as_bytes()); - } - - fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { - let len = input - .read_u32_le() - .map_err(|_| Error::insufficient_data("string_len"))? as usize; - let bytes = input - .remaining() - .get(..len) - .ok_or_else(|| Error::insufficient_data("string_bytes"))?; - let value = std::str::from_utf8(bytes) - .map_err(|_| Error::deserial("invalid utf-8 string"))? - .to_owned(); - input.advance(len as u64); - Ok(value) - } -} diff --git a/datasketches/src/kll/sorted_view.rs b/datasketches/src/kll/sorted_view.rs index 075a472..4ab8838 100644 --- a/datasketches/src/kll/sorted_view.rs +++ b/datasketches/src/kll/sorted_view.rs @@ -17,11 +17,10 @@ use std::cmp::Ordering; -use super::sketch::KllComparator; -use super::sketch::KllItem; +use super::order::KllComparator; #[derive(Debug, Clone)] -pub struct SortedView<T: KllItem, C: KllComparator<T>> { +pub struct SortedView<T: Clone, C: KllComparator<T>> { comparator: C, entries: Vec<Entry<T>>, total_weight: u64, @@ -33,7 +32,7 @@ struct Entry<T> { weight: u64, } -impl<T: KllItem, C: KllComparator<T>> SortedView<T, C> { +impl<T: Clone, C: KllComparator<T>> SortedView<T, C> { fn new(mut entries: Vec<Entry<T>>, comparator: C) -> Self { entries.sort_by(|a, b| comparator.compare(&a.item, &b.item)); let mut total_weight = 0u64; @@ -104,7 +103,7 @@ impl<T: KllItem, C: KllComparator<T>> SortedView<T, C> { } } -pub fn build_sorted_view<T: KllItem, C: KllComparator<T>>( +pub fn build_sorted_view<T: Clone, C: KllComparator<T>>( levels: &[Vec<T>], comparator: C, ) -> SortedView<T, C> { @@ -125,10 +124,10 @@ pub fn build_sorted_view<T: KllItem, C: KllComparator<T>>( } #[track_caller] -fn check_split_points<T: KllItem, C: KllComparator<T>>(split_points: &[T], comparator: &C) { +fn check_split_points<T, C: KllComparator<T>>(split_points: &[T], comparator: &C) { assert!( - split_points.iter().all(|point| !T::is_nan(point)), - "split_points must not contain NaN values" + split_points.iter().all(|point| comparator.accepts(point)), + "split_points must belong to the comparator's ordered domain" ); for pair in split_points.windows(2) { assert!( @@ -138,11 +137,7 @@ fn check_split_points<T: KllItem, C: KllComparator<T>>(split_points: &[T], compa } } -fn lower_bound<T: KllItem, C: KllComparator<T>>( - entries: &[Entry<T>], - item: &T, - comparator: &C, -) -> usize { +fn lower_bound<T, C: KllComparator<T>>(entries: &[Entry<T>], item: &T, comparator: &C) -> usize { let mut left = 0usize; let mut right = entries.len(); while left < right { @@ -156,11 +151,7 @@ fn lower_bound<T: KllItem, C: KllComparator<T>>( left } -fn upper_bound<T: KllItem, C: KllComparator<T>>( - entries: &[Entry<T>], - item: &T, - comparator: &C, -) -> usize { +fn upper_bound<T, C: KllComparator<T>>(entries: &[Entry<T>], item: &T, comparator: &C) -> usize { let mut left = 0usize; let mut right = entries.len(); while left < right { @@ -174,7 +165,7 @@ fn upper_bound<T: KllItem, C: KllComparator<T>>( left } -fn lower_bound_by_weight<T: KllItem>(entries: &[Entry<T>], weight: u64) -> usize { +fn lower_bound_by_weight<T>(entries: &[Entry<T>], weight: u64) -> usize { let mut left = 0usize; let mut right = entries.len(); while left < right { @@ -188,7 +179,7 @@ fn lower_bound_by_weight<T: KllItem>(entries: &[Entry<T>], weight: u64) -> usize left } -fn upper_bound_by_weight<T: KllItem>(entries: &[Entry<T>], weight: u64) -> usize { +fn upper_bound_by_weight<T>(entries: &[Entry<T>], weight: u64) -> usize { let mut left = 0usize; let mut right = entries.len(); while left < right { diff --git a/datasketches/src/kll/value.rs b/datasketches/src/kll/value.rs new file mode 100644 index 0000000..e14057a --- /dev/null +++ b/datasketches/src/kll/value.rs @@ -0,0 +1,121 @@ +// 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 crate::codec::SketchBytes; +use crate::codec::SketchSlice; +use crate::error::Error; + +/// Defines the compact binary representation of a KLL item. +/// +/// This trait is required only for serialization. In-memory KLL operations support any cloneable +/// item type with a [`KllComparator`](crate::kll::KllComparator). The encoded representation must +/// preserve the comparator's ordering across a round trip. +pub trait KllValue: Clone { + /// Minimum number of bytes required to encode one value. + const MIN_SERIALIZED_SIZE: usize; + + /// Returns the number of bytes required to encode `value`. + fn serialized_size(value: &Self) -> usize; + + /// Serializes `value` into `bytes`. + fn serialize(value: &Self, bytes: &mut SketchBytes); + + /// Deserializes one value from `input`. + fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error>; +} + +impl KllValue for f32 { + const MIN_SERIALIZED_SIZE: usize = 4; + + fn serialized_size(_value: &Self) -> usize { + 4 + } + + fn serialize(value: &Self, bytes: &mut SketchBytes) { + bytes.write_f32_le(*value); + } + + fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { + input + .read_f32_le() + .map_err(|_| Error::insufficient_data("f32")) + } +} + +impl KllValue for f64 { + const MIN_SERIALIZED_SIZE: usize = 8; + + fn serialized_size(_value: &Self) -> usize { + 8 + } + + fn serialize(value: &Self, bytes: &mut SketchBytes) { + bytes.write_f64_le(*value); + } + + fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { + input + .read_f64_le() + .map_err(|_| Error::insufficient_data("f64")) + } +} + +impl KllValue for i64 { + const MIN_SERIALIZED_SIZE: usize = 8; + + fn serialized_size(_value: &Self) -> usize { + 8 + } + + fn serialize(value: &Self, bytes: &mut SketchBytes) { + bytes.write_i64_le(*value); + } + + fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { + input + .read_i64_le() + .map_err(|_| Error::insufficient_data("i64")) + } +} + +impl KllValue for String { + const MIN_SERIALIZED_SIZE: usize = 4; + + fn serialized_size(value: &Self) -> usize { + 4 + value.len() + } + + fn serialize(value: &Self, bytes: &mut SketchBytes) { + bytes.write_u32_le(value.len() as u32); + bytes.write(value.as_bytes()); + } + + fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { + let len = input + .read_u32_le() + .map_err(|_| Error::insufficient_data("string_len"))? as usize; + let bytes = input + .remaining() + .get(..len) + .ok_or_else(|| Error::insufficient_data("string_bytes"))?; + let value = std::str::from_utf8(bytes) + .map_err(|_| Error::deserial("invalid utf-8 string"))? + .to_owned(); + input.advance(len as u64); + Ok(value) + } +} diff --git a/tests-integration/tests/kll_test/sketch.rs b/tests-integration/tests/kll_test/sketch.rs index 18e68c4..7fcca7e 100644 --- a/tests-integration/tests/kll_test/sketch.rs +++ b/tests-integration/tests/kll_test/sketch.rs @@ -47,6 +47,10 @@ impl KllComparator<String> for NumericStringOrder { .unwrap() .cmp(&right.parse::<u64>().unwrap()) } + + fn is_compatible(&self, _other: &Self) -> bool { + true + } } #[test] @@ -245,7 +249,7 @@ fn test_out_of_order_split_points_panics() { } #[test] -#[should_panic(expected = "split_points must not contain NaN values")] +#[should_panic(expected = "split_points must belong to the comparator's ordered domain")] fn test_nan_split_point_panics() { let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); sketch.update(0.0); diff --git a/tests-integration/tests/serde_tests/kll.rs b/tests-integration/tests/serde_tests/kll.rs index fad3eb3..aac4099 100644 --- a/tests-integration/tests/serde_tests/kll.rs +++ b/tests-integration/tests/serde_tests/kll.rs @@ -42,6 +42,10 @@ impl KllComparator<String> for NumericStringOrder { fn compare(&self, left: &String, right: &String) -> Ordering { parse_string_value(left).cmp(&parse_string_value(right)) } + + fn is_compatible(&self, _other: &Self) -> bool { + true + } } fn test_f32_file(path: PathBuf, expected_n: usize) { --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
