Merge pull request #486 from SYaoJun/223_emplace_back
perf: Replace push_back with emplace_back to optimize object construc…
diff --git a/.clang-tidy b/.clang-tidy
new file mode 100644
index 0000000..d0cdc6e
--- /dev/null
+++ b/.clang-tidy
@@ -0,0 +1,36 @@
+# 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.
+---
+Checks: |
+ clang-diagnostic-*,
+ clang-analyzer-*,
+ -clang-analyzer-alpha*,
+ google-*,
+ modernize-*,
+ -modernize-avoid-c-arrays,
+ -modernize-use-trailing-return-type,
+ -modernize-use-nodiscard,
+
+CheckOptions:
+ - key: google-readability-braces-around-statements.ShortStatementLines
+ value: '0'
+ - key: google-readability-function-size.StatementThreshold
+ value: '800'
+ - key: google-readability-namespace-comments.ShortNamespaceLines
+ value: '10'
+ - key: google-readability-namespace-comments.SpacesBeforeComments
+ value: '2'
\ No newline at end of file
diff --git a/.github/workflows/hardening.yml b/.github/workflows/hardening.yml
new file mode 100644
index 0000000..e264ebd
--- /dev/null
+++ b/.github/workflows/hardening.yml
@@ -0,0 +1,59 @@
+name: libc++ Hardening Tests
+
+on:
+ push:
+ branches:
+ - master
+ pull_request:
+ branches:
+ - master
+ workflow_dispatch:
+
+env:
+ BUILD_TYPE: Debug
+
+jobs:
+ hardening-test:
+ name: C++17 with libc++ Hardening Mode
+ runs-on: ubuntu-latest
+
+ steps:
+ - name: Checkout
+ uses: actions/checkout@v4
+ with:
+ submodules: true
+ persist-credentials: false
+
+ - name: Install LLVM and libc++
+ run: |
+ # Install LLVM/Clang with libc++
+ wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | sudo apt-key add -
+ sudo add-apt-repository "deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-18 main"
+ sudo apt-get update
+ sudo apt-get install -y clang-18 libc++-18-dev libc++abi-18-dev
+
+ - name: Configure with C++17 and libc++ hardening
+ env:
+ CC: clang-18
+ CXX: clang++-18
+ run: |
+ cmake -B build -S . \
+ -DCMAKE_BUILD_TYPE=${{ env.BUILD_TYPE }} \
+ -DCMAKE_CXX_STANDARD=17 \
+ -DBUILD_TESTS=ON \
+ -DCMAKE_CXX_FLAGS="-stdlib=libc++ -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG" \
+ -DCMAKE_EXE_LINKER_FLAGS="-stdlib=libc++ -lc++abi"
+
+ - name: Build hardening tests
+ run: cmake --build build --target hardening_test --config ${{ env.BUILD_TYPE }}
+
+ - name: Run hardening tests
+ run: |
+ cd build
+ ./common/test/hardening_test "[deserialize_hardening]"
+
+ - name: Report results
+ if: always()
+ run: |
+ echo "✅ Tests passed with libc++ hardening enabled!"
+ echo "This verifies the fix for issue #477 prevents SIGABRT."
diff --git a/.pre-commit-config.yaml b/.pre-commit-config.yaml
new file mode 100644
index 0000000..262fd02
--- /dev/null
+++ b/.pre-commit-config.yaml
@@ -0,0 +1,29 @@
+# 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.
+
+# To use this, install the python package `pre-commit` and
+# run once `pre-commit install`. This will setup a git pre-commit-hook
+# that is executed on each commit and will report the linting problems.
+# To run all hooks on all files use `pre-commit run -a`
+
+repos:
+ - repo: https://github.com/pocc/pre-commit-hooks
+ rev: v1.3.5
+ hooks:
+ - id: clang-tidy
+ args: ['--quiet', '-p=build/compile_commands.json', '--config-file=.clang-tidy']
+ types_or: [c++, c]
\ No newline at end of file
diff --git a/common/include/serde.hpp b/common/include/serde.hpp
index ad20fe6..c4e46d7 100644
--- a/common/include/serde.hpp
+++ b/common/include/serde.hpp
@@ -132,6 +132,11 @@
/// ItemsSketch<String> with ArrayOfStringsSerDe in Java.
/// The length of each string is stored as a 32-bit integer (historically),
/// which may be too wasteful. Treat this as an example.
+///
+/// This implementation treats std::string as an arbitrary byte container.
+/// It does not check whether string contents are valid UTF-8.
+///
+/// Use a UTF-8-validating SerDe when cross-language portability is required.
template<>
struct serde<std::string> {
/// @copydoc serde::serialize
diff --git a/common/test/CMakeLists.txt b/common/test/CMakeLists.txt
index 7593bd0..c3e937a 100644
--- a/common/test/CMakeLists.txt
+++ b/common/test/CMakeLists.txt
@@ -75,10 +75,15 @@
# now the integration test part
add_executable(integration_test)
-target_link_libraries(integration_test count cpc density fi hll kll req sampling theta tuple common_test_lib)
+target_link_libraries(integration_test count cpc density fi hll kll req sampling theta tuple quantiles common_test_lib)
+# Use CMAKE_CXX_STANDARD if defined, otherwise C++11
+set(_integration_cxx_standard 11)
+if(DEFINED CMAKE_CXX_STANDARD)
+ set(_integration_cxx_standard ${CMAKE_CXX_STANDARD})
+endif()
set_target_properties(integration_test PROPERTIES
- CXX_STANDARD 11
+ CXX_STANDARD ${_integration_cxx_standard}
CXX_STANDARD_REQUIRED YES
)
@@ -91,3 +96,39 @@
PRIVATE
integration_test.cpp
)
+
+# Separate hardening test executable (header-only, no pre-compiled libs)
+# This ensures the sketch code is compiled with C++17 + hardening
+# Always build this target - it will use CMAKE_CXX_STANDARD if set (and >= 17), otherwise C++17
+
+add_executable(hardening_test)
+target_link_libraries(hardening_test common common_test_lib)
+
+# Include directories for header-only sketch implementations
+target_include_directories(hardening_test PRIVATE
+ ${CMAKE_SOURCE_DIR}/quantiles/include
+ ${CMAKE_SOURCE_DIR}/kll/include
+ ${CMAKE_SOURCE_DIR}/req/include
+ ${CMAKE_SOURCE_DIR}/common/include
+)
+
+# Use C++17 minimum for hardening tests
+set(_hardening_cxx_standard 17)
+if(DEFINED CMAKE_CXX_STANDARD AND CMAKE_CXX_STANDARD GREATER_EQUAL 17)
+ set(_hardening_cxx_standard ${CMAKE_CXX_STANDARD})
+endif()
+set_target_properties(hardening_test PROPERTIES
+ CXX_STANDARD ${_hardening_cxx_standard}
+ CXX_STANDARD_REQUIRED YES
+)
+message(STATUS "hardening_test will use C++${_hardening_cxx_standard}")
+
+add_test(
+ NAME hardening_test
+ COMMAND hardening_test "[deserialize_hardening]"
+)
+
+target_sources(hardening_test
+ PRIVATE
+ deserialize_hardening_test.cpp
+)
diff --git a/common/test/deserialize_hardening_test.cpp b/common/test/deserialize_hardening_test.cpp
new file mode 100644
index 0000000..64e654b
--- /dev/null
+++ b/common/test/deserialize_hardening_test.cpp
@@ -0,0 +1,188 @@
+/*
+ * 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.
+ */
+
+#include <catch2/catch.hpp>
+#include <sstream>
+#include <vector>
+
+// Include all affected sketch types
+#include <quantiles_sketch.hpp>
+#include <kll_sketch.hpp>
+#include <req_sketch.hpp>
+
+namespace datasketches {
+
+/**
+ * Test for fix of issue #477:
+ * BUG: SIGABRT in deserialize(): dereferencing empty std::optional (libc++ verbose_abort)
+ *
+ * These tests exercise the actual deserialization code path that contained the bug.
+ * With buggy code (&*tmp on empty optional) and hardening enabled, these will SIGABRT.
+ * With fixed code (aligned_storage), these pass normally.
+ *
+ * IMPORTANT: These tests actually call deserialize() on multi-item sketches, which
+ * exercises the buggy code path where min/max are deserialized.
+ */
+
+TEST_CASE("quantiles_sketch: deserialize multi-item sketch", "[deserialize_hardening]") {
+ // Create sketch with multiple items (so min/max are stored in serialization)
+ quantiles_sketch<double> sketch(128);
+ for (int i = 0; i < 1000; i++) {
+ sketch.update(static_cast<double>(i));
+ }
+
+ // Serialize
+ auto bytes = sketch.serialize();
+
+ // Deserialize - WITH BUGGY CODE AND HARDENING, THIS WILL SIGABRT HERE
+ // The bug is: sd.deserialize(is, &*tmp, 1) where tmp is empty optional
+ auto sketch2 = quantiles_sketch<double>::deserialize(bytes.data(), bytes.size());
+
+ // Verify deserialization worked correctly
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ REQUIRE(sketch2.get_min_item() == sketch.get_min_item());
+ REQUIRE(sketch2.get_max_item() == sketch.get_max_item());
+ REQUIRE(sketch2.get_quantile(0.5) == sketch.get_quantile(0.5));
+}
+
+TEST_CASE("quantiles_sketch: deserialize from stream", "[deserialize_hardening]") {
+ quantiles_sketch<float> sketch(256);
+ for (int i = 0; i < 2000; i++) {
+ sketch.update(static_cast<float>(i) * 0.5f);
+ }
+
+ // Serialize to stream
+ std::stringstream ss;
+ sketch.serialize(ss);
+
+ // Deserialize from stream - exercises the buggy code path
+ auto sketch2 = quantiles_sketch<float>::deserialize(ss);
+
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ REQUIRE(sketch2.get_min_item() == sketch.get_min_item());
+ REQUIRE(sketch2.get_max_item() == sketch.get_max_item());
+}
+
+TEST_CASE("kll_sketch: deserialize multi-item sketch", "[deserialize_hardening]") {
+ kll_sketch<float> sketch(200);
+ for (int i = 0; i < 1500; i++) {
+ sketch.update(static_cast<float>(i));
+ }
+
+ auto bytes = sketch.serialize();
+
+ // Deserialize - exercises buggy &*tmp code path
+ auto sketch2 = kll_sketch<float>::deserialize(bytes.data(), bytes.size());
+
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ REQUIRE(sketch2.get_min_item() == sketch.get_min_item());
+ REQUIRE(sketch2.get_max_item() == sketch.get_max_item());
+}
+
+TEST_CASE("kll_sketch: deserialize from stream", "[deserialize_hardening]") {
+ kll_sketch<int> sketch(400);
+ for (int i = 0; i < 3000; i++) {
+ sketch.update(i);
+ }
+
+ std::stringstream ss;
+ sketch.serialize(ss);
+
+ // Deserialize from stream
+ auto sketch2 = kll_sketch<int>::deserialize(ss);
+
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ REQUIRE(sketch2.get_min_item() == sketch.get_min_item());
+ REQUIRE(sketch2.get_max_item() == sketch.get_max_item());
+}
+
+TEST_CASE("req_sketch: deserialize multi-level sketch", "[deserialize_hardening]") {
+ // REQ sketch only has the bug when num_levels > 1
+ // We need to add enough items to trigger multiple levels
+ req_sketch<float> sketch(12);
+ for (int i = 0; i < 10000; i++) {
+ sketch.update(static_cast<float>(i));
+ }
+
+ auto bytes = sketch.serialize();
+
+ // Deserialize - exercises buggy code path when num_levels > 1
+ auto sketch2 = req_sketch<float>::deserialize(bytes.data(), bytes.size());
+
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ REQUIRE(sketch2.get_min_item() == sketch.get_min_item());
+ REQUIRE(sketch2.get_max_item() == sketch.get_max_item());
+}
+
+TEST_CASE("req_sketch: deserialize from stream", "[deserialize_hardening]") {
+ req_sketch<double> sketch(20);
+ for (int i = 0; i < 15000; i++) {
+ sketch.update(static_cast<double>(i) * 0.1);
+ }
+
+ std::stringstream ss;
+ sketch.serialize(ss);
+
+ // Deserialize from stream
+ auto sketch2 = req_sketch<double>::deserialize(ss);
+
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ REQUIRE(sketch2.get_min_item() == sketch.get_min_item());
+ REQUIRE(sketch2.get_max_item() == sketch.get_max_item());
+}
+
+TEST_CASE("multiple sketch types: stress test", "[deserialize_hardening]") {
+ SECTION("quantiles with various sizes") {
+ for (int k : {64, 128, 256}) {
+ quantiles_sketch<int> sketch(k);
+ for (int i = 0; i < 5000; i++) {
+ sketch.update(i);
+ }
+ auto bytes = sketch.serialize();
+ auto sketch2 = quantiles_sketch<int>::deserialize(bytes.data(), bytes.size());
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ }
+ }
+
+ SECTION("kll with various sizes") {
+ for (int k : {100, 200, 400}) {
+ kll_sketch<double> sketch(k);
+ for (int i = 0; i < 4000; i++) {
+ sketch.update(static_cast<double>(i) / 10.0);
+ }
+ auto bytes = sketch.serialize();
+ auto sketch2 = kll_sketch<double>::deserialize(bytes.data(), bytes.size());
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ }
+ }
+
+ SECTION("req with various sizes") {
+ for (int k : {12, 20}) {
+ req_sketch<float> sketch(k);
+ for (int i = 0; i < 8000; i++) {
+ sketch.update(static_cast<float>(i));
+ }
+ auto bytes = sketch.serialize();
+ auto sketch2 = req_sketch<float>::deserialize(bytes.data(), bytes.size());
+ REQUIRE(sketch2.get_n() == sketch.get_n());
+ }
+ }
+}
+
+} // namespace datasketches
diff --git a/count/include/count_min_impl.hpp b/count/include/count_min_impl.hpp
index 45376e7..2f2629f 100644
--- a/count/include/count_min_impl.hpp
+++ b/count/include/count_min_impl.hpp
@@ -39,7 +39,9 @@
_sketch_array((num_hashes*num_buckets < 1<<30) ? num_hashes*num_buckets : 0, 0, _allocator),
_seed(seed),
_total_weight(0) {
- if (num_buckets < 3) throw std::invalid_argument("Using fewer than 3 buckets incurs relative error greater than 1.");
+ if (num_buckets < 3) {
+ throw std::invalid_argument("Using fewer than 3 buckets incurs relative error greater than 1.");
+ }
// This check is to ensure later compatibility with a Java implementation whose maximum size can only
// be 2^31-1. We check only against 2^30 for simplicity.
@@ -74,7 +76,7 @@
template<typename W, typename A>
double count_min_sketch<W,A>::get_relative_error() const {
- return exp(1.0) / double(_num_buckets);
+ return exp(1.0) / static_cast<double>(_num_buckets);
}
template<typename W, typename A>
@@ -147,7 +149,7 @@
template<typename W, typename A>
W count_min_sketch<W,A>::get_estimate(const std::string& item) const {
- if (item.empty()) return 0; // Empty strings are not inserted into the sketch.
+ if (item.empty()) { return 0; } // Empty strings are not inserted into the sketch.
return get_estimate(item.c_str(), item.length());
}
@@ -176,7 +178,7 @@
template<typename W, typename A>
void count_min_sketch<W,A>::update(const std::string& item, W weight) {
- if (item.empty()) return;
+ if (item.empty()) { return; }
update(item.c_str(), item.length(), weight);
}
@@ -201,7 +203,7 @@
template<typename W, typename A>
W count_min_sketch<W,A>::get_upper_bound(const std::string& item) const {
- if (item.empty()) return 0; // Empty strings are not inserted into the sketch.
+ if (item.empty()) { return 0; } // Empty strings are not inserted into the sketch.
return get_upper_bound(item.c_str(), item.length());
}
@@ -218,7 +220,7 @@
template<typename W, typename A>
W count_min_sketch<W,A>::get_lower_bound(const std::string& item) const {
- if (item.empty()) return 0; // Empty strings are not inserted into the sketch.
+ if (item.empty()) { return 0; } // Empty strings are not inserted into the sketch.
return get_lower_bound(item.c_str(), item.length());
}
@@ -232,17 +234,13 @@
/*
* Merges this sketch into other_sketch sketch by elementwise summing of buckets
*/
- if (this == &other_sketch) {
- throw std::invalid_argument( "Cannot merge a sketch with itself." );
- }
+ if (this == &other_sketch) { throw std::invalid_argument( "Cannot merge a sketch with itself." ); }
bool acceptable_config =
(get_num_hashes() == other_sketch.get_num_hashes()) &&
(get_num_buckets() == other_sketch.get_num_buckets()) &&
(get_seed() == other_sketch.get_seed());
- if (!acceptable_config) {
- throw std::invalid_argument( "Incompatible sketch configuration." );
- }
+ if (!acceptable_config) { throw std::invalid_argument( "Incompatible sketch configuration." ); }
// Merge step - iterate over the other vector and add the weights to this sketch
auto it = _sketch_array.begin(); // This is a std::vector iterator.
@@ -290,7 +288,7 @@
write(os, nhashes);
write(os, seed_hash);
write(os, unused8);
- if (is_empty()) return; // sketch is empty, no need to write further bytes.
+ if (is_empty()) { return; } // sketch is empty, no need to write further bytes.
// Long 2
write(os, _total_weight);
@@ -327,7 +325,7 @@
}
count_min_sketch c(nhashes, nbuckets, seed, allocator);
const bool is_empty = (flags_byte & (1 << flags::IS_EMPTY)) > 0;
- if (is_empty == 1) return c; // sketch is empty, no need to read further.
+ if (is_empty == 1) { return c; } // sketch is empty, no need to read further.
// Set the sketch weight and read in the sketch values
const auto weight = read<W>(is);
@@ -373,7 +371,7 @@
ptr += copy_to_mem(nhashes, ptr);
ptr += copy_to_mem(seed_hash, ptr);
ptr += copy_to_mem(null_characters_8, ptr);
- if (is_empty()) return bytes; // sketch is empty, no need to write further bytes.
+ if (is_empty()) { return bytes; } // sketch is empty, no need to write further bytes.
// Long 2
const W t_weight = _total_weight;
@@ -423,7 +421,7 @@
}
count_min_sketch c(nhashes, nbuckets, seed, allocator);
const bool is_empty = (flags_byte & (1 << flags::IS_EMPTY)) > 0;
- if (is_empty) return c; // sketch is empty, no need to read further.
+ if (is_empty) { return c; } // sketch is empty, no need to read further.
ensure_minimum_memory(size, sizeof(W) * (1 + nbuckets * nhashes));
@@ -449,8 +447,7 @@
// count the number of used entries in the sketch
uint64_t num_nonzero = 0;
for (const auto entry: _sketch_array) {
- if (entry != static_cast<W>(0.0))
- ++num_nonzero;
+ if (entry != static_cast<W>(0.0)) { ++num_nonzero; }
}
// Using a temporary stream for implementation here does not comply with AllocatorAwareContainer requirements.
diff --git a/cpc/include/cpc_compressor_impl.hpp b/cpc/include/cpc_compressor_impl.hpp
index 062e2e0..0cc24b1 100644
--- a/cpc/include/cpc_compressor_impl.hpp
+++ b/cpc/include/cpc_compressor_impl.hpp
@@ -157,7 +157,7 @@
break;
case cpc_sketch_alloc<A>::flavor::PINNED:
compress_pinned_flavor(source, result);
- if (result.window_data.size() == 0) throw std::logic_error("window is not expected");
+ if (result.window_data.size() == 0) throw std::logic_error("window is expected");
break;
case cpc_sketch_alloc<A>::flavor::SLIDING:
compress_sliding_flavor(source, result);
diff --git a/fi/include/frequent_items_sketch.hpp b/fi/include/frequent_items_sketch.hpp
index 0aa9514..87ee174 100644
--- a/fi/include/frequent_items_sketch.hpp
+++ b/fi/include/frequent_items_sketch.hpp
@@ -44,6 +44,11 @@
* Based on Java implementation here:
* https://github.com/apache/datasketches-java/blob/master/src/main/java/org/apache/datasketches/frequencies/ItemsSketch.java
* @author Alexander Saydakov
+ *
+ * Sketch that may retain string values.
+ * For sketches containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
*/
template<
typename T,
@@ -74,6 +79,8 @@
/**
* Update this sketch with an item and a positive weight (frequency count).
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item for which the weight should be increased (lvalue)
* @param weight the amount by which the weight of the item should be increased
* A count of zero is a no-op, and a negative count will throw an exception.
@@ -82,6 +89,8 @@
/**
* Update this sketch with an item and a positive weight (frequency count).
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item for which the weight should be increased (rvalue)
* @param weight the amount by which the weight of the item should be increased
* A count of zero is a no-op, and a negative count will throw an exception.
@@ -91,6 +100,8 @@
/**
* This function merges the other sketch into this one.
* The other sketch may be of a different size.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param other sketch to be merged into this (lvalue)
*/
void merge(const frequent_items_sketch& other);
@@ -98,6 +109,8 @@
/**
* This function merges the other sketch into this one.
* The other sketch may be of a different size.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param other sketch to be merged into this (rvalue)
*/
void merge(frequent_items_sketch&& other);
diff --git a/kll/include/kll_sketch.hpp b/kll/include/kll_sketch.hpp
index 904587a..d672c41 100644
--- a/kll/include/kll_sketch.hpp
+++ b/kll/include/kll_sketch.hpp
@@ -46,6 +46,11 @@
* and nearly optimal accuracy per retained item.
* See <a href="https://arxiv.org/abs/1603.05346v2">Optimal Quantile Approximation in Streams</a>.
*
+ * Sketch that may retain string values.
+ * For sketches containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
+ *
* <p>This is a stochastic streaming sketch that enables near real-time analysis of the
* approximate distribution of items from a very large stream in a single pass, requiring only
* that the items are comparable.
@@ -56,7 +61,7 @@
* <p>As of May 2020, this implementation produces serialized sketches which are binary-compatible
* with the equivalent Java implementation only when template parameter T = float
* (32-bit single precision values).
- *
+ *
* <p>Given an input stream of <i>N</i> items, the <i>natural rank</i> of any specific
* item is defined as its index <i>(1 to N)</i> in inclusive mode
* or <i>(0 to N-1)</i> in exclusive mode
@@ -225,6 +230,8 @@
/**
* Updates this sketch with the given data item.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item from a stream of items
*/
template<typename FwdT>
@@ -232,6 +239,8 @@
/**
* Merges another sketch into this one.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param other sketch to merge into this one
*/
template<typename FwdSk>
diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp
index fde0a31..44fe6a1 100644
--- a/kll/include/kll_sketch_impl.hpp
+++ b/kll/include/kll_sketch_impl.hpp
@@ -24,6 +24,7 @@
#include <iomanip>
#include <sstream>
#include <stdexcept>
+#include <type_traits>
#include "conditional_forward.hpp"
#include "count_zeros.hpp"
@@ -481,18 +482,22 @@
read(is, levels.data(), sizeof(levels[0]) * num_levels);
}
levels[num_levels] = capacity;
- optional<T> tmp; // space to deserialize min and max
optional<T> min_item;
optional<T> max_item;
if (!is_single_item) {
- sd.deserialize(is, &*tmp, 1);
+ // Space to deserialize min and max.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ sd.deserialize(is, tmp, 1);
// serde call did not throw, repackage and cleanup
- min_item.emplace(*tmp);
- (*tmp).~T();
- sd.deserialize(is, &*tmp, 1);
+ min_item.emplace(std::move(*tmp));
+ tmp->~T();
+ sd.deserialize(is, tmp, 1);
// serde call did not throw, repackage and cleanup
- max_item.emplace(*tmp);
- (*tmp).~T();
+ max_item.emplace(std::move(*tmp));
+ tmp->~T();
}
A alloc(allocator);
auto items_buffer_deleter = [capacity, &alloc](T* ptr) { alloc.deallocate(ptr, capacity); };
@@ -565,18 +570,22 @@
ptr += copy_from_mem(ptr, levels.data(), sizeof(levels[0]) * num_levels);
}
levels[num_levels] = capacity;
- optional<T> tmp; // space to deserialize min and max
optional<T> min_item;
optional<T> max_item;
if (!is_single_item) {
- ptr += sd.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ // Space to deserialize min and max.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ ptr += sd.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde call did not throw, repackage and cleanup
- min_item.emplace(*tmp);
- (*tmp).~T();
- ptr += sd.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ min_item.emplace(std::move(*tmp));
+ tmp->~T();
+ ptr += sd.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde call did not throw, repackage and cleanup
- max_item.emplace(*tmp);
- (*tmp).~T();
+ max_item.emplace(std::move(*tmp));
+ tmp->~T();
}
A alloc(allocator);
auto items_buffer_deleter = [capacity, &alloc](T* ptr) { alloc.deallocate(ptr, capacity); };
diff --git a/kll/test/kll_sketch_deserialize_from_java_test.cpp b/kll/test/kll_sketch_deserialize_from_java_test.cpp
index 795486a..65efc3e 100644
--- a/kll/test/kll_sketch_deserialize_from_java_test.cpp
+++ b/kll/test/kll_sketch_deserialize_from_java_test.cpp
@@ -100,4 +100,28 @@
}
}
+TEST_CASE("kll long", "[serde_compat]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(testBinaryInputPath + "kll_long_n" + std::to_string(n) + "_java.sk", std::ios::binary);
+ const auto sketch = kll_sketch<long>::deserialize(is);
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > kll_constants::DEFAULT_K));
+ REQUIRE(sketch.get_n() == n);
+ if (n > 0) {
+ REQUIRE(sketch.get_min_item() == 1);
+ REQUIRE(sketch.get_max_item() == static_cast<long>(n));
+ uint64_t weight = 0;
+ for (const auto pair: sketch) {
+ REQUIRE(pair.first >= sketch.get_min_item());
+ REQUIRE(pair.first <= sketch.get_max_item());
+ weight += pair.second;
+ }
+ REQUIRE(weight == sketch.get_n());
+ }
+ }
+}
+
} /* namespace datasketches */
diff --git a/kll/test/kll_sketch_serialize_for_java.cpp b/kll/test/kll_sketch_serialize_for_java.cpp
index 00b8913..22b7577 100644
--- a/kll/test/kll_sketch_serialize_for_java.cpp
+++ b/kll/test/kll_sketch_serialize_for_java.cpp
@@ -43,6 +43,16 @@
}
}
+TEST_CASE("kll sketch long generate", "[serialize_for_java]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ kll_sketch<long> sketch;
+ for (unsigned i = 1; i <= n; ++i) sketch.update(i);
+ std::ofstream os("kll_long_n" + std::to_string(n) + "_cpp.sk", std::ios::binary);
+ sketch.serialize(os);
+ }
+}
+
struct compare_as_number {
bool operator()(const std::string& a, const std::string& b) const {
return std::stoi(a) < std::stoi(b);
diff --git a/quantiles/include/quantiles_sketch.hpp b/quantiles/include/quantiles_sketch.hpp
index b1e2e3c..e995e3e 100644
--- a/quantiles/include/quantiles_sketch.hpp
+++ b/quantiles/include/quantiles_sketch.hpp
@@ -47,6 +47,11 @@
* The analysis is obtained using get_rank() and get_quantile() functions,
* the Probability Mass Function from get_PMF() and the Cumulative Distribution Function from get_CDF().
*
+ * Sketch that may retain string values.
+ * For sketches containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
+ *
* <p>Consider a large stream of one million values such as packet sizes coming into a network node.
* The natural rank of any specific size value is its index in the hypothetical sorted
* array of values.
@@ -206,6 +211,8 @@
/**
* Updates this sketch with the given data item.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item from a stream of items
*/
template<typename FwdT>
@@ -213,6 +220,8 @@
/**
* Merges another sketch into this one.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param other sketch to merge into this one
*/
template<typename FwdSk>
diff --git a/quantiles/include/quantiles_sketch_impl.hpp b/quantiles/include/quantiles_sketch_impl.hpp
index 50c82c1..2dacf21 100644
--- a/quantiles/include/quantiles_sketch_impl.hpp
+++ b/quantiles/include/quantiles_sketch_impl.hpp
@@ -25,6 +25,7 @@
#include <stdexcept>
#include <iomanip>
#include <sstream>
+#include <type_traits>
#include "count_zeros.hpp"
#include "conditional_forward.hpp"
@@ -393,18 +394,22 @@
const bool is_compact = (serial_version == 2) | ((flags_byte & (1 << flags::IS_COMPACT)) > 0);
const bool is_sorted = (flags_byte & (1 << flags::IS_SORTED)) > 0;
- optional<T> tmp; // space to deserialize min and max
optional<T> min_item;
optional<T> max_item;
- serde.deserialize(is, &*tmp, 1);
+ // Space to deserialize min and max.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ serde.deserialize(is, tmp, 1);
// serde call did not throw, repackage and cleanup
- min_item.emplace(*tmp);
- (*tmp).~T();
- serde.deserialize(is, &*tmp, 1);
+ min_item.emplace(std::move(*tmp));
+ tmp->~T();
+ serde.deserialize(is, tmp, 1);
// serde call did not throw, repackage and cleanup
- max_item.emplace(*tmp);
- (*tmp).~T();
+ max_item.emplace(std::move(*tmp));
+ tmp->~T();
if (serial_version == 1) {
read<uint64_t>(is); // no longer used
@@ -507,18 +512,22 @@
const bool is_compact = (serial_version == 2) | ((flags_byte & (1 << flags::IS_COMPACT)) > 0);
const bool is_sorted = (flags_byte & (1 << flags::IS_SORTED)) > 0;
- optional<T> tmp; // space to deserialize min and max
optional<T> min_item;
optional<T> max_item;
- ptr += serde.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ // Space to deserialize min and max.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ ptr += serde.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde call did not throw, repackage and cleanup
- min_item.emplace(*tmp);
- (*tmp).~T();
- ptr += serde.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ min_item.emplace(std::move(*tmp));
+ tmp->~T();
+ ptr += serde.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde call did not throw, repackage and cleanup
- max_item.emplace(*tmp);
- (*tmp).~T();
+ max_item.emplace(std::move(*tmp));
+ tmp->~T();
if (serial_version == 1) {
uint64_t unused_long;
diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index 21ccac0..52295bd 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -35,6 +35,11 @@
* "Relative Error Streaming Quantiles" by Graham Cormode, Zohar Karnin, Edo Liberty,
* Justin Thaler, Pavel Veselý, and loosely derived from a Python prototype written by Pavel Veselý.
*
+ * Sketch that may retain string values.
+ * For sketches containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
+ *
* <p>Reference: https://arxiv.org/abs/2004.01668</p>
*
* <p>This implementation differs from the algorithm described in the paper in the following:</p>
@@ -179,6 +184,8 @@
/**
* Updates this sketch with the given data item.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item from a stream of items
*/
template<typename FwdT>
@@ -186,6 +193,8 @@
/**
* Merges another sketch into this one.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param other sketch to merge into this one
*/
template<typename FwdSk>
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index a28e74e..3c1c2fc 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -22,6 +22,7 @@
#include <sstream>
#include <stdexcept>
+#include <type_traits>
namespace datasketches {
@@ -461,7 +462,6 @@
const bool hra = flags_byte & (1 << flags::IS_HIGH_RANK);
if (is_empty) return req_sketch(k, hra, comparator, allocator);
- optional<T> tmp; // space to deserialize min and max
optional<T> min_item;
optional<T> max_item;
@@ -472,14 +472,19 @@
uint64_t n = 1;
if (num_levels > 1) {
n = read<uint64_t>(is);
- sd.deserialize(is, &*tmp, 1);
+ // Space to deserialize min and max.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ sd.deserialize(is, tmp, 1);
// serde call did not throw, repackage and cleanup
- min_item.emplace(*tmp);
- (*tmp).~T();
- sd.deserialize(is, &*tmp, 1);
+ min_item.emplace(std::move(*tmp));
+ tmp->~T();
+ sd.deserialize(is, tmp, 1);
// serde call did not throw, repackage and cleanup
- max_item.emplace(*tmp);
- (*tmp).~T();
+ max_item.emplace(std::move(*tmp));
+ tmp->~T();
}
if (raw_items) {
@@ -537,7 +542,6 @@
const bool hra = flags_byte & (1 << flags::IS_HIGH_RANK);
if (is_empty) return req_sketch(k, hra, comparator, allocator);
- optional<T> tmp; // space to deserialize min and max
optional<T> min_item;
optional<T> max_item;
@@ -549,14 +553,19 @@
if (num_levels > 1) {
ensure_minimum_memory(end_ptr - ptr, sizeof(n));
ptr += copy_from_mem(ptr, n);
- ptr += sd.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ // Space to deserialize min and max.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ ptr += sd.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde call did not throw, repackage and cleanup
- min_item.emplace(*tmp);
- (*tmp).~T();
- ptr += sd.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ min_item.emplace(std::move(*tmp));
+ tmp->~T();
+ ptr += sd.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde call did not throw, repackage and cleanup
- max_item.emplace(*tmp);
- (*tmp).~T();
+ max_item.emplace(std::move(*tmp));
+ tmp->~T();
}
if (raw_items) {
diff --git a/sampling/include/ebpps_sample_impl.hpp b/sampling/include/ebpps_sample_impl.hpp
index 88a86ae..c48b32a 100644
--- a/sampling/include/ebpps_sample_impl.hpp
+++ b/sampling/include/ebpps_sample_impl.hpp
@@ -28,6 +28,7 @@
#include <cmath>
#include <string>
#include <sstream>
+#include <type_traits>
namespace datasketches {
@@ -365,11 +366,15 @@
optional<T> partial_item;
if (has_partial) {
- optional<T> tmp; // space to deserialize
- ptr += sd.deserialize(ptr, end_ptr - ptr, &*tmp, 1);
+ // Space to deserialize.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ ptr += sd.deserialize(ptr, end_ptr - ptr, tmp, 1);
// serde did not throw so place item and clean up
- partial_item.emplace(*tmp);
- (*tmp).~T();
+ partial_item.emplace(std::move(*tmp));
+ tmp->~T();
}
return std::pair<ebpps_sample<T,A>, size_t>(
@@ -400,11 +405,15 @@
optional<T> partial_item;
if (has_partial) {
- optional<T> tmp; // space to deserialize
- sd.deserialize(is, &*tmp, 1);
+ // Space to deserialize.
+ // serde::deserialize expects allocated but not initialized storage.
+ typename std::aligned_storage<sizeof(T), alignof(T)>::type tmp_storage;
+ T* tmp = reinterpret_cast<T*>(&tmp_storage);
+
+ sd.deserialize(is, tmp, 1);
// serde did not throw so place item and clean up
- partial_item.emplace(*tmp);
- (*tmp).~T();
+ partial_item.emplace(std::move(*tmp));
+ tmp->~T();
}
if (!is.good()) throw std::runtime_error("error reading from std::istream");
diff --git a/sampling/include/ebpps_sketch.hpp b/sampling/include/ebpps_sketch.hpp
index 038b5a3..615d37b 100644
--- a/sampling/include/ebpps_sketch.hpp
+++ b/sampling/include/ebpps_sketch.hpp
@@ -50,6 +50,11 @@
* The sample may be smaller than k and the resulting size of the sample potentially includes
* a probabilistic component, meaning the resulting sample size is not always constant.
*
+ * Sketch that may retain string values.
+ * For sketches containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
+ *
* @author Jon Malkin
*/
template<
@@ -71,6 +76,8 @@
/**
* Updates this sketch with the given data item with the given weight.
* This method takes an lvalue.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item an item from a stream of items
* @param weight the weight of the item
*/
@@ -79,6 +86,8 @@
/**
* Updates this sketch with the given data item with the given weight.
* This method takes an rvalue.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item an item from a stream of items
* @param weight the weight of the item
*/
@@ -87,6 +96,8 @@
/**
* Merges the provided sketch into the current one.
* This method takes an lvalue.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param sketch the sketch to merge into the current object
*/
void merge(const ebpps_sketch<T, A>& sketch);
@@ -94,6 +105,8 @@
/**
* Merges the provided sketch into the current one.
* This method takes an rvalue.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param sketch the sketch to merge into the current object
*/
void merge(ebpps_sketch<T, A>&& sketch);
diff --git a/sampling/include/var_opt_sketch.hpp b/sampling/include/var_opt_sketch.hpp
index 1324883..6b157ca 100644
--- a/sampling/include/var_opt_sketch.hpp
+++ b/sampling/include/var_opt_sketch.hpp
@@ -57,6 +57,11 @@
* optimal (varopt) sampling is related to reservoir sampling, with improved error bounds for
* subset sum estimation.
*
+ * Sketch that may retain string values.
+ * For sketches containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
+ *
* author Kevin Lang
* author Jon Malkin
*/
@@ -111,6 +116,8 @@
/**
* Updates this sketch with the given data item with the given weight.
* This method takes an lvalue.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item an item from a stream of items
* @param weight the weight of the item
*/
@@ -119,6 +126,8 @@
/**
* Updates this sketch with the given data item with the given weight.
* This method takes an rvalue.
+ * If cross-language portability is required, callers should ensure that
+ * the input string uses a compatible encoding (valid UTF-8).
* @param item an item from a stream of items
* @param weight the weight of the item
*/
diff --git a/sampling/include/var_opt_union.hpp b/sampling/include/var_opt_union.hpp
index 0e4f76d..68d1ac4 100644
--- a/sampling/include/var_opt_union.hpp
+++ b/sampling/include/var_opt_union.hpp
@@ -65,13 +65,17 @@
/**
* Updates this union with the given sketch
* This method takes an lvalue.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param sk a sketch to add to the union
*/
void update(const var_opt_sketch<T, A>& sk);
-
+
/**
* Updates this union with the given sketch
* This method takes an rvalue.
+ * If sketches contain strings, callers are responsible for ensuring that
+ * both sketches were built using compatible string encodings.
* @param sk a sketch to add to the union
*/
void update(var_opt_sketch<T, A>&& sk);
diff --git a/tuple/CMakeLists.txt b/tuple/CMakeLists.txt
index 4b0a48c..54df11e 100644
--- a/tuple/CMakeLists.txt
+++ b/tuple/CMakeLists.txt
@@ -54,4 +54,6 @@
include/array_tuple_intersection_impl.hpp
include/array_tuple_a_not_b.hpp
include/array_tuple_a_not_b_impl.hpp
+ include/array_of_strings_sketch.hpp
+ include/array_of_strings_sketch_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/tuple/include/array_of_strings_sketch.hpp b/tuple/include/array_of_strings_sketch.hpp
new file mode 100644
index 0000000..296c0a8
--- /dev/null
+++ b/tuple/include/array_of_strings_sketch.hpp
@@ -0,0 +1,164 @@
+/*
+ * 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.
+ */
+
+#ifndef ARRAY_OF_STRINGS_SKETCH_HPP_
+#define ARRAY_OF_STRINGS_SKETCH_HPP_
+
+#include <memory>
+#include <string>
+
+#include "array_tuple_sketch.hpp"
+#include "xxhash64.h"
+
+namespace datasketches {
+
+using array_of_strings = array<std::string>;
+
+// default update policy for an array of strings
+class default_array_of_strings_update_policy {
+public:
+ default_array_of_strings_update_policy() = default;
+
+ array_of_strings create() const;
+
+ void update(array_of_strings& array, const array_of_strings& input) const;
+
+ void update(array_of_strings& array, const array_of_strings* input) const;
+};
+
+/**
+ * Serializer/deserializer for an array of strings.
+ *
+ * Requirements:
+ * - Array size must be <= 127.
+ *
+ * This serde does not perform UTF-8 validation. Callers must ensure strings
+ * are valid UTF-8 before serialization to guarantee interoperability with
+ * Java, Go, and Rust implementations.
+ */
+template<typename Allocator = std::allocator<array_of_strings>>
+struct default_array_of_strings_serde {
+ using summary_allocator = typename std::allocator_traits<Allocator>::template rebind_alloc<array_of_strings>;
+
+ explicit default_array_of_strings_serde(const Allocator& allocator = Allocator());
+
+ void serialize(std::ostream& os, const array_of_strings* items, unsigned num) const;
+ void deserialize(std::istream& is, array_of_strings* items, unsigned num) const;
+ size_t serialize(void* ptr, size_t capacity, const array_of_strings* items, unsigned num) const;
+ size_t deserialize(const void* ptr, size_t capacity, array_of_strings* items, unsigned num) const;
+ size_t size_of_item(const array_of_strings& item) const;
+
+private:
+ summary_allocator summary_allocator_;
+ static void check_num_nodes(uint8_t num_nodes);
+ static uint32_t compute_total_bytes(const array_of_strings& item);
+};
+
+/**
+ * Hashes an array of strings using ArrayOfStrings-compatible hashing.
+ */
+uint64_t hash_array_of_strings_key(const array_of_strings& key);
+
+/**
+ * Extended class of compact_tuple_sketch for array of strings.
+ *
+ * Requirements:
+ * - Array size must be <= 127.
+ *
+ * UTF-8 compatibility:
+ * Serialized sketches are intended to be language and platform independent.
+ * Other implementations (Java, Go, Rust) enforce UTF-8 encoding for strings.
+ * This C++ implementation does not validate UTF-8; it is the caller's
+ * responsibility to ensure all strings are valid UTF-8 before calling update().
+ * Non-UTF-8 strings may serialize successfully but will fail to deserialize
+ * in other language implementations.
+ */
+template<typename Allocator = std::allocator<array_of_strings>>
+class compact_array_of_strings_tuple_sketch:
+ public compact_tuple_sketch<array_of_strings, Allocator> {
+public:
+ using Base = compact_tuple_sketch<array_of_strings, Allocator>;
+ using vector_bytes = typename Base::vector_bytes;
+ using Base::serialize;
+
+ /**
+ * Copy constructor.
+ * Constructs a compact sketch from another sketch (update or compact)
+ * @param other sketch to be constructed from
+ * @param ordered if true make the resulting sketch ordered
+ */
+ template<typename Sketch>
+ compact_array_of_strings_tuple_sketch(const Sketch& sketch, bool ordered = true);
+
+ /**
+ * This method deserializes a sketch from a given stream.
+ * @param is input stream
+ * @param seed the seed for the hash function that was used to create the sketch
+ * @param sd instance of a SerDe
+ * @param allocator instance of an Allocator
+ * @return an instance of the sketch
+ */
+ template<typename SerDe = default_array_of_strings_serde<Allocator>>
+ static compact_array_of_strings_tuple_sketch deserialize(std::istream& is, uint64_t seed = DEFAULT_SEED,
+ const SerDe& sd = SerDe(), const Allocator& allocator = Allocator());
+
+ /**
+ * This method deserializes a sketch from a given array of bytes.
+ * @param bytes pointer to the array of bytes
+ * @param size the size of the array
+ * @param seed the seed for the hash function that was used to create the sketch
+ * @param sd instance of a SerDe
+ * @param allocator instance of an Allocator
+ * @return an instance of the sketch
+ */
+ template<typename SerDe = default_array_of_strings_serde<Allocator>>
+ static compact_array_of_strings_tuple_sketch deserialize(const void* bytes, size_t size, uint64_t seed = DEFAULT_SEED,
+ const SerDe& sd = SerDe(), const Allocator& allocator = Allocator());
+
+private:
+ explicit compact_array_of_strings_tuple_sketch(Base&& base);
+};
+
+/**
+ * Convenience alias for update_tuple_sketch for array of strings
+ */
+template<typename Allocator = std::allocator<array_of_strings>,
+ typename Policy = default_array_of_strings_update_policy>
+using update_array_of_strings_tuple_sketch = update_tuple_sketch<
+ array_of_strings,
+ array_of_strings,
+ Policy,
+ Allocator
+>;
+
+/**
+ * Converts an array of strings tuple sketch to a compact sketch (ordered or unordered).
+ * @param sketch input sketch
+ * @param ordered optional flag to specify if an ordered sketch should be produced
+ * @return compact array of strings sketch
+ */
+template<typename Allocator = std::allocator<array_of_strings>, typename Policy = default_array_of_strings_update_policy>
+compact_array_of_strings_tuple_sketch<Allocator> compact_array_of_strings_sketch(
+ const update_array_of_strings_tuple_sketch<Allocator, Policy>& sketch, bool ordered = true);
+
+} /* namespace datasketches */
+
+#include "array_of_strings_sketch_impl.hpp"
+
+#endif
diff --git a/tuple/include/array_of_strings_sketch_impl.hpp b/tuple/include/array_of_strings_sketch_impl.hpp
new file mode 100644
index 0000000..400df47
--- /dev/null
+++ b/tuple/include/array_of_strings_sketch_impl.hpp
@@ -0,0 +1,274 @@
+/*
+ * 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.
+ */
+
+#ifndef ARRAY_OF_STRINGS_SKETCH_IMPL_HPP_
+#define ARRAY_OF_STRINGS_SKETCH_IMPL_HPP_
+
+#include <stdexcept>
+
+#include "common_defs.hpp"
+
+namespace datasketches {
+
+inline array_of_strings default_array_of_strings_update_policy::create() const {
+ return array_of_strings(0, "");
+}
+
+inline void default_array_of_strings_update_policy::update(
+ array_of_strings& array, const array_of_strings& input
+) const {
+ const auto length = static_cast<size_t>(input.size());
+ array = array_of_strings(static_cast<uint8_t>(length), "");
+ for (size_t i = 0; i < length; ++i) array[i] = input[i];
+}
+
+inline void default_array_of_strings_update_policy::update(
+ array_of_strings& array, const array_of_strings* input
+) const {
+ if (input == nullptr) {
+ array = array_of_strings(0, "");
+ return;
+ }
+ const auto length = static_cast<size_t>(input->size());
+ array = array_of_strings(static_cast<uint8_t>(length), "");
+ for (size_t i = 0; i < length; ++i) array[i] = (*input)[i];
+}
+
+inline uint64_t hash_array_of_strings_key(const array_of_strings& key) {
+ // Matches Java Util.PRIME for ArrayOfStrings key hashing.
+ static constexpr uint64_t STRING_ARR_HASH_SEED = 0x7A3CCA71ULL;
+ XXHash64 hasher(STRING_ARR_HASH_SEED);
+ const auto size = static_cast<size_t>(key.size());
+ for (size_t i = 0; i < size; ++i) {
+ const auto& entry = key[i];
+ hasher.add(entry.data(), entry.size());
+ if (i + 1 < size) hasher.add(",", 1);
+ }
+ return hasher.hash();
+}
+
+template<typename Allocator, typename Policy>
+compact_array_of_strings_tuple_sketch<Allocator> compact_array_of_strings_sketch(
+ const update_array_of_strings_tuple_sketch<Allocator, Policy>& sketch, bool ordered
+) {
+ return compact_array_of_strings_tuple_sketch<Allocator>(sketch, ordered);
+}
+
+template<typename Allocator>
+template<typename Sketch>
+compact_array_of_strings_tuple_sketch<Allocator>::compact_array_of_strings_tuple_sketch(
+ const Sketch& sketch, bool ordered
+): Base(sketch, ordered) {}
+
+template<typename Allocator>
+compact_array_of_strings_tuple_sketch<Allocator>::compact_array_of_strings_tuple_sketch(
+ Base&& base
+): Base(std::move(base)) {}
+
+template<typename Allocator>
+template<typename SerDe>
+auto compact_array_of_strings_tuple_sketch<Allocator>::deserialize(
+ std::istream& is, uint64_t seed, const SerDe& sd, const Allocator& allocator
+) -> compact_array_of_strings_tuple_sketch {
+ auto base = Base::deserialize(is, seed, sd, allocator);
+ return compact_array_of_strings_tuple_sketch(std::move(base));
+}
+
+template<typename Allocator>
+template<typename SerDe>
+auto compact_array_of_strings_tuple_sketch<Allocator>::deserialize(
+ const void* bytes, size_t size, uint64_t seed, const SerDe& sd, const Allocator& allocator
+) -> compact_array_of_strings_tuple_sketch {
+ auto base = Base::deserialize(bytes, size, seed, sd, allocator);
+ return compact_array_of_strings_tuple_sketch(std::move(base));
+}
+
+template<typename Allocator>
+default_array_of_strings_serde<Allocator>::default_array_of_strings_serde(const Allocator& allocator):
+ summary_allocator_(allocator) {}
+
+template<typename Allocator>
+void default_array_of_strings_serde<Allocator>::serialize(
+ std::ostream& os, const array_of_strings* items, unsigned num
+) const {
+ unsigned i = 0;
+ try {
+ for (; i < num; ++i) {
+ const uint32_t total_bytes = compute_total_bytes(items[i]);
+ const uint8_t num_nodes = static_cast<uint8_t>(items[i].size());
+ write(os, total_bytes);
+ write(os, num_nodes);
+ const std::string* data = items[i].data();
+ for (uint8_t j = 0; j < num_nodes; ++j) {
+ const uint32_t length = static_cast<uint32_t>(data[j].size());
+ write(os, length);
+ os.write(data[j].data(), length);
+ }
+ }
+ } catch (std::runtime_error& e) {
+ if (std::string(e.what()).find("size exceeds 127") != std::string::npos) throw;
+ throw std::runtime_error("array_of_strings stream write failed at item " + std::to_string(i));
+ }
+}
+
+template<typename Allocator>
+void default_array_of_strings_serde<Allocator>::deserialize(
+ std::istream& is, array_of_strings* items, unsigned num
+) const {
+ unsigned i = 0;
+ bool failure = false;
+ try {
+ for (; i < num; ++i) {
+ read<uint32_t>(is); // total_bytes
+ if (!is) { failure = true; break; }
+ const uint8_t num_nodes = read<uint8_t>(is);
+ if (!is) { failure = true; break; }
+ check_num_nodes(num_nodes);
+ array_of_strings array(num_nodes, "");
+ for (uint8_t j = 0; j < num_nodes; ++j) {
+ const uint32_t length = read<uint32_t>(is);
+ if (!is) { failure = true; break; }
+ std::string value(length, '\0');
+ if (length != 0) {
+ is.read(&value[0], length);
+ if (!is) { failure = true; break; }
+ }
+ array[j] = std::move(value);
+ }
+ if (failure) break;
+ summary_allocator alloc(summary_allocator_);
+ std::allocator_traits<summary_allocator>::construct(alloc, &items[i], std::move(array));
+ }
+ } catch (std::exception& e) {
+ summary_allocator alloc(summary_allocator_);
+ for (unsigned j = 0; j < i; ++j) {
+ std::allocator_traits<summary_allocator>::destroy(alloc, &items[j]);
+ }
+ if (std::string(e.what()).find("size exceeds 127") != std::string::npos) throw;
+ throw std::runtime_error("array_of_strings stream read failed at item " + std::to_string(i));
+ }
+ if (failure) {
+ summary_allocator alloc(summary_allocator_);
+ for (unsigned j = 0; j < i; ++j) {
+ std::allocator_traits<summary_allocator>::destroy(alloc, &items[j]);
+ }
+ throw std::runtime_error("array_of_strings stream read failed at item " + std::to_string(i));
+ }
+}
+
+template<typename Allocator>
+size_t default_array_of_strings_serde<Allocator>::serialize(
+ void* ptr, size_t capacity, const array_of_strings* items, unsigned num
+) const {
+ uint8_t* ptr8 = static_cast<uint8_t*>(ptr);
+ size_t bytes_written = 0;
+
+ for (unsigned i = 0; i < num; ++i) {
+ const uint32_t total_bytes = compute_total_bytes(items[i]);
+ const uint8_t num_nodes = static_cast<uint8_t>(items[i].size());
+ check_memory_size(bytes_written + total_bytes, capacity);
+ bytes_written += copy_to_mem(total_bytes, ptr8 + bytes_written);
+ bytes_written += copy_to_mem(num_nodes, ptr8 + bytes_written);
+ const std::string* data = items[i].data();
+ for (uint8_t j = 0; j < num_nodes; ++j) {
+ const uint32_t length = static_cast<uint32_t>(data[j].size());
+
+ bytes_written += copy_to_mem(length, ptr8 + bytes_written);
+ bytes_written += copy_to_mem(data[j].data(), ptr8 + bytes_written, length);
+ }
+ }
+ return bytes_written;
+}
+
+template<typename Allocator>
+size_t default_array_of_strings_serde<Allocator>::deserialize(
+ const void* ptr, size_t capacity, array_of_strings* items, unsigned num
+) const {
+ const uint8_t* ptr8 = static_cast<const uint8_t*>(ptr);
+ size_t bytes_read = 0;
+
+ unsigned i = 0;
+
+ try {
+ for (; i < num; ++i) {
+ check_memory_size(bytes_read + sizeof(uint32_t), capacity);
+ const size_t item_start = bytes_read;
+ uint32_t total_bytes;
+ bytes_read += copy_from_mem(ptr8 + bytes_read, total_bytes);
+ check_memory_size(item_start + total_bytes, capacity);
+
+ check_memory_size(bytes_read + sizeof(uint8_t), capacity);
+ uint8_t num_nodes;
+ bytes_read += copy_from_mem(ptr8 + bytes_read, num_nodes);
+ check_num_nodes(num_nodes);
+
+ array_of_strings array(num_nodes, "");
+ for (uint8_t j = 0; j < num_nodes; ++j) {
+ check_memory_size(bytes_read + sizeof(uint32_t), capacity);
+ uint32_t length;
+ bytes_read += copy_from_mem(ptr8 + bytes_read, length);
+
+ check_memory_size(bytes_read + length, capacity);
+ std::string value(length, '\0');
+ if (length != 0) {
+ bytes_read += copy_from_mem(ptr8 + bytes_read, &value[0], length);
+ }
+ array[j] = std::move(value);
+ }
+ summary_allocator alloc(summary_allocator_);
+ std::allocator_traits<summary_allocator>::construct(alloc, &items[i], std::move(array));
+ }
+ } catch (std::exception& e) {
+ summary_allocator alloc(summary_allocator_);
+ for (unsigned j = 0; j < i; ++j) {
+ std::allocator_traits<summary_allocator>::destroy(alloc, &items[j]);
+ }
+ if (std::string(e.what()).find("size exceeds 127") != std::string::npos) throw;
+ throw std::runtime_error("array_of_strings bytes read failed at item " + std::to_string(i));
+ }
+ return bytes_read;
+}
+
+template<typename Allocator>
+size_t default_array_of_strings_serde<Allocator>::size_of_item(const array_of_strings& item) const {
+ return compute_total_bytes(item);
+}
+
+template<typename Allocator>
+void default_array_of_strings_serde<Allocator>::check_num_nodes(uint8_t num_nodes) {
+ if (num_nodes > 127) {
+ throw std::runtime_error("array_of_strings size exceeds 127");
+ }
+}
+
+template<typename Allocator>
+uint32_t default_array_of_strings_serde<Allocator>::compute_total_bytes(const array_of_strings& item) {
+ const auto count = item.size();
+ check_num_nodes(static_cast<uint8_t>(count));
+ size_t total = sizeof(uint32_t) + sizeof(uint8_t) + count * sizeof(uint32_t);
+ const std::string* data = item.data();
+ for (uint32_t j = 0; j < count; ++j) {
+ total += data[j].size();
+ }
+ return static_cast<uint32_t>(total);
+}
+
+} /* namespace datasketches */
+
+#endif
diff --git a/tuple/include/array_tuple_sketch.hpp b/tuple/include/array_tuple_sketch.hpp
index 547b240..d331f8b 100644
--- a/tuple/include/array_tuple_sketch.hpp
+++ b/tuple/include/array_tuple_sketch.hpp
@@ -22,6 +22,8 @@
#include <vector>
#include <memory>
+#include <type_traits>
+#include <algorithm>
#include "serde.hpp"
#include "tuple_sketch.hpp"
@@ -34,17 +36,18 @@
public:
using value_type = T;
using allocator_type = Allocator;
+ using alloc_traits = std::allocator_traits<Allocator>;
- explicit array(uint8_t size, T value, const Allocator& allocator = Allocator()):
+ explicit array(uint8_t size, const T& value, const Allocator& allocator = Allocator()):
allocator_(allocator), size_(size), array_(allocator_.allocate(size_)) {
- std::fill(array_, array_ + size_, value);
+ init_values(value, std::is_trivially_copyable<T>());
}
array(const array& other):
allocator_(other.allocator_),
size_(other.size_),
array_(allocator_.allocate(size_))
{
- std::copy(other.array_, other.array_ + size_, array_);
+ copy_from(other, std::is_trivially_copyable<T>());
}
array(array&& other) noexcept:
allocator_(std::move(other.allocator_)),
@@ -52,9 +55,13 @@
array_(other.array_)
{
other.array_ = nullptr;
+ other.size_ = 0;
}
~array() {
- if (array_ != nullptr) allocator_.deallocate(array_, size_);
+ if (array_ != nullptr) {
+ destroy_values(std::is_trivially_destructible<T>());
+ allocator_.deallocate(array_, size_);
+ }
}
array& operator=(const array& other) {
array copy(other);
@@ -75,10 +82,34 @@
T* data() { return array_; }
const T* data() const { return array_; }
bool operator==(const array& other) const {
+ if (size_ != other.size_) return false;
for (uint8_t i = 0; i < size_; ++i) if (array_[i] != other.array_[i]) return false;
return true;
}
private:
+ void init_values(const T& value, std::true_type) {
+ std::fill(array_, array_ + size_, value);
+ }
+ void init_values(const T& value, std::false_type) {
+ for (uint8_t i = 0; i < size_; ++i) {
+ alloc_traits::construct(allocator_, array_ + i, value);
+ }
+ }
+ void copy_from(const array& other, std::true_type) {
+ std::copy(other.array_, other.array_ + size_, array_);
+ }
+ void copy_from(const array& other, std::false_type) {
+ for (uint8_t i = 0; i < size_; ++i) {
+ alloc_traits::construct(allocator_, array_ + i, other.array_[i]);
+ }
+ }
+ void destroy_values(std::true_type) {}
+ void destroy_values(std::false_type) {
+ for (uint8_t i = 0; i < size_; ++i) {
+ alloc_traits::destroy(allocator_, array_ + i);
+ }
+ }
+
Allocator allocator_;
uint8_t size_;
T* array_;
diff --git a/tuple/include/tuple_sketch.hpp b/tuple/include/tuple_sketch.hpp
index cbfd9f1..7b636a7 100644
--- a/tuple/include/tuple_sketch.hpp
+++ b/tuple/include/tuple_sketch.hpp
@@ -46,6 +46,11 @@
/**
* Base class for Tuple sketch.
* This is an extension of Theta sketch that allows keeping arbitrary Summary associated with each retained key.
+ *
+ * Summary that may retain string values.
+ * For Summary containing strings, cross-language portability depends on
+ * using compatible string encodings. This class does not by itself enforce
+ * UTF-8 validity for all string inputs.
*/
template<
typename Summary,
@@ -253,6 +258,9 @@
/**
* Update this sketch with a given string.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* @param key string to update the sketch with
* @param value to update the sketch with
*/
@@ -261,6 +269,9 @@
/**
* Update this sketch with a given unsigned 64-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* @param key uint64_t to update the sketch with
* @param value to update the sketch with
*/
@@ -269,6 +280,9 @@
/**
* Update this sketch with a given signed 64-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* @param key int64_t to update the sketch with
* @param value to update the sketch with
*/
@@ -277,6 +291,9 @@
/**
* Update this sketch with a given unsigned 32-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key uint32_t to update the sketch with
* @param value to update the sketch with
@@ -286,6 +303,9 @@
/**
* Update this sketch with a given signed 32-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key int32_t to update the sketch with
* @param value to update the sketch with
@@ -295,6 +315,9 @@
/**
* Update this sketch with a given unsigned 16-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key uint16_t to update the sketch with
* @param value to update the sketch with
@@ -304,6 +327,9 @@
/**
* Update this sketch with a given signed 16-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key int16_t to update the sketch with
* @param value to update the sketch with
@@ -313,6 +339,9 @@
/**
* Update this sketch with a given unsigned 8-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key uint8_t to update the sketch with
* @param value to update the sketch with
@@ -322,6 +351,9 @@
/**
* Update this sketch with a given signed 8-bit integer.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key int8_t to update the sketch with
* @param value to update the sketch with
@@ -331,6 +363,9 @@
/**
* Update this sketch with a given double-precision floating point value.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key double to update the sketch with
* @param value to update the sketch with
@@ -340,6 +375,9 @@
/**
* Update this sketch with a given floating point value.
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* For compatibility with Java implementation.
* @param key float to update the sketch with
* @param value to update the sketch with
@@ -357,6 +395,9 @@
* Otherwise two sketches that should represent overlapping sets will be disjoint
* For instance, for signed 32-bit values call update(int32_t) method above,
* which does widening conversion to int64_t, if compatibility with Java is expected
+ * If the summary contains strings and cross-language portability is required,
+ * callers should ensure that any strings in the summary
+ * use a compatible encoding (valid UTF-8).
* @param key pointer to the data
* @param length of the data in bytes
* @param value to update the sketch with
diff --git a/tuple/test/CMakeLists.txt b/tuple/test/CMakeLists.txt
index 4ca6a50..3d7ccca 100644
--- a/tuple/test/CMakeLists.txt
+++ b/tuple/test/CMakeLists.txt
@@ -44,6 +44,7 @@
tuple_a_not_b_test.cpp
tuple_jaccard_similarity_test.cpp
array_of_doubles_sketch_test.cpp
+ array_of_strings_sketch_test.cpp
engagement_test.cpp
)
@@ -52,6 +53,7 @@
PRIVATE
aod_sketch_deserialize_from_java_test.cpp
tuple_sketch_deserialize_from_java_test.cpp
+ aos_sketch_deserialize_from_java_test.cpp
)
endif()
@@ -60,5 +62,6 @@
PRIVATE
aod_sketch_serialize_for_java.cpp
tuple_sketch_serialize_for_java.cpp
+ aos_sketch_serialize_for_java.cpp
)
endif()
diff --git a/tuple/test/aos_sketch_deserialize_from_java_test.cpp b/tuple/test/aos_sketch_deserialize_from_java_test.cpp
new file mode 100644
index 0000000..af37d6c
--- /dev/null
+++ b/tuple/test/aos_sketch_deserialize_from_java_test.cpp
@@ -0,0 +1,283 @@
+/*
+* 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.
+ */
+
+#include <catch2/catch.hpp>
+#include <fstream>
+#include <vector>
+
+#include "array_of_strings_sketch.hpp"
+
+namespace datasketches {
+ // assume the binary sketches for this test have been generated by datasketches-java code
+ // in the subdirectory called "java" in the root directory of this project
+ static std::string testBinaryInputPath = std::string(TEST_BINARY_INPUT_PATH) + "../../java/";
+
+ static std::vector<uint8_t> read_binary_file(const std::string& path) {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ is.seekg(0, std::ios::end);
+ const auto size = static_cast<size_t>(is.tellg());
+ is.seekg(0, std::ios::beg);
+ std::vector<uint8_t> bytes(size);
+ if (size != 0) {
+ is.read(reinterpret_cast<char*>(bytes.data()), size);
+ }
+ return bytes;
+ }
+
+ TEST_CASE("aos sketch one value", "[serde_compat]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ const auto path = testBinaryInputPath + "aos_1_n" + std::to_string(n) + "_java.sk";
+ SECTION("stream") {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ is, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > 1000));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 1);
+ }
+ }
+ SECTION("bytes") {
+ const auto bytes = read_binary_file(path);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > 1000));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 1);
+ }
+ }
+ }
+ }
+
+ TEST_CASE("aos sketch three values", "[serde_compat]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ const auto path = testBinaryInputPath + "aos_3_n" + std::to_string(n) + "_java.sk";
+ SECTION("stream") {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ is, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > 1000));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 3);
+ }
+ }
+ SECTION("bytes") {
+ const auto bytes = read_binary_file(path);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > 1000));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 3);
+ }
+ }
+ }
+ }
+
+ TEST_CASE("aos sketch non-empty no entries", "[serde_compat]") {
+ const auto path = testBinaryInputPath + "aos_1_non_empty_no_entries_java.sk";
+ SECTION("stream") {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ is, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE(sketch.get_num_retained() == 0);
+ }
+ SECTION("bytes") {
+ const auto bytes = read_binary_file(path);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE(sketch.get_num_retained() == 0);
+ }
+ }
+
+ TEST_CASE("aos sketch multi keys strings", "[serde_compat]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ const auto path = testBinaryInputPath + "aos_multikey_n" + std::to_string(n) + "_java.sk";
+ SECTION("stream") {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ is, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > 1000));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 1);
+ }
+ }
+ SECTION("bytes") {
+ const auto bytes = read_binary_file(path);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.is_estimation_mode() == (n > 1000));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 1);
+ }
+ }
+ }
+ }
+
+ TEST_CASE("aos sketch unicode strings", "[serde_compat]") {
+ const auto path = testBinaryInputPath + "aos_unicode_java.sk";
+ auto check = [](const compact_array_of_strings_tuple_sketch<>& sketch) {
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE_FALSE(sketch.is_estimation_mode());
+ REQUIRE(sketch.get_num_retained() == 3);
+
+ const std::vector<std::vector<std::string>> expected_values = {
+ {"밸류", "값"},
+ {"📦", "🎁"},
+ {"ценить1", "ценить2"}
+ };
+ std::vector<bool> matched(expected_values.size(), false);
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+ REQUIRE(entry.second.size() == 2);
+
+ bool found = false;
+ for (size_t i = 0; i < expected_values.size(); ++i) {
+ if (matched[i]) continue;
+ const auto& expected = expected_values[i];
+ if (entry.second.size() != expected.size()) continue;
+ bool equal = true;
+ for (size_t j = 0; j < expected.size(); ++j) {
+ if (entry.second[j] != expected[j]) {
+ equal = false;
+ break;
+ }
+ }
+ if (equal) {
+ matched[i] = true;
+ found = true;
+ break;
+ }
+ }
+ REQUIRE(found);
+ }
+ for (bool found: matched) REQUIRE(found);
+ };
+ SECTION("stream") {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ is, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ check(sketch);
+ }
+ SECTION("bytes") {
+ const auto bytes = read_binary_file(path);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ check(sketch);
+ }
+ }
+
+ TEST_CASE("aos sketch empty strings", "[serde_compat]") {
+ const auto path = testBinaryInputPath + "aos_empty_strings_java.sk";
+ auto check = [](const compact_array_of_strings_tuple_sketch<>& sketch) {
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE_FALSE(sketch.is_estimation_mode());
+ REQUIRE(sketch.get_num_retained() == 3);
+ const std::vector<std::vector<std::string>> expected_values = {
+ {"empty_key_value"},
+ {""},
+ {"", ""}
+ };
+ std::vector<bool> matched(expected_values.size(), false);
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.first < sketch.get_theta64());
+
+ bool found = false;
+ for (size_t i = 0; i < expected_values.size(); ++i) {
+ if (matched[i]) continue;
+ const auto& expected = expected_values[i];
+ if (entry.second.size() != expected.size()) continue;
+ bool equal = true;
+ for (size_t j = 0; j < expected.size(); ++j) {
+ if (entry.second[j] != expected[j]) {
+ equal = false;
+ break;
+ }
+ }
+ if (equal) {
+ matched[i] = true;
+ found = true;
+ break;
+ }
+ }
+ REQUIRE(found);
+ }
+ for (bool found: matched) REQUIRE(found);
+ };
+ SECTION("stream") {
+ std::ifstream is;
+ is.exceptions(std::ios::failbit | std::ios::badbit);
+ is.open(path, std::ios::binary);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ is, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ check(sketch);
+ }
+ SECTION("bytes") {
+ const auto bytes = read_binary_file(path);
+ const auto sketch = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+ check(sketch);
+ }
+ }
+}
diff --git a/tuple/test/aos_sketch_serialize_for_java.cpp b/tuple/test/aos_sketch_serialize_for_java.cpp
new file mode 100644
index 0000000..c6eb0df
--- /dev/null
+++ b/tuple/test/aos_sketch_serialize_for_java.cpp
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+
+#include <catch2/catch.hpp>
+#include <fstream>
+#include <initializer_list>
+
+#include "array_of_strings_sketch.hpp"
+
+namespace datasketches {
+
+using aos_sketch = update_array_of_strings_tuple_sketch<>;
+using array_of_strings = array<std::string>;
+
+static array_of_strings make_array(std::initializer_list<std::string> items) {
+ array_of_strings array(static_cast<uint8_t>(items.size()), "");
+ size_t i = 0;
+ for (const auto& item: items) {
+ array[static_cast<uint8_t>(i)] = item;
+ ++i;
+ }
+ return array;
+}
+
+TEST_CASE("aos sketch generate one value", "[serialize_for_java]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ auto sketch = aos_sketch::builder().build();
+ for (unsigned i = 0; i < n; ++i) {
+ array_of_strings key(1, "");
+ key[0] = std::to_string(i);
+ array_of_strings value(1, "");
+ value[0] = "value" + std::to_string(i);
+ sketch.update(hash_array_of_strings_key(key), value);
+ }
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ std::ofstream os("aos_1_n" + std::to_string(n) + "_cpp.sk", std::ios::binary);
+ compact_array_of_strings_sketch(sketch).serialize(os, default_array_of_strings_serde<>());
+ }
+}
+
+TEST_CASE("aos sketch generate three values", "[serialize_for_java]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ auto sketch = aos_sketch::builder().build();
+ for (unsigned i = 0; i < n; ++i) {
+ array_of_strings key(1, "");
+ key[0] = std::to_string(i);
+ array_of_strings value(3, "");
+ value[0] = "a" + std::to_string(i);
+ value[1] = "b" + std::to_string(i);
+ value[2] = "c" + std::to_string(i);
+ sketch.update(hash_array_of_strings_key(key), value);
+ }
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ std::ofstream os("aos_3_n" + std::to_string(n) + "_cpp.sk", std::ios::binary);
+ compact_array_of_strings_sketch(sketch).serialize(os, default_array_of_strings_serde<>());
+ }
+}
+
+TEST_CASE("aos sketch generate non-empty no entries", "[serialize_for_java]") {
+ auto sketch = aos_sketch::builder()
+ .set_lg_k(12)
+ .set_resize_factor(resize_factor::X8)
+ .set_p(0.01f)
+ .build();
+ array_of_strings key(1, "");
+ key[0] = "key1";
+ array_of_strings value(1, "");
+ value[0] = "value1";
+ sketch.update(hash_array_of_strings_key(key), value);
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE(sketch.get_num_retained() == 0);
+ std::ofstream os("aos_1_non_empty_no_entries_cpp.sk", std::ios::binary);
+ compact_array_of_strings_sketch(sketch).serialize(os, default_array_of_strings_serde<>());
+}
+
+TEST_CASE("aos sketch generate multi key strings", "[serialize_for_java]") {
+ const unsigned n_arr[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000};
+ for (const unsigned n: n_arr) {
+ auto sketch = aos_sketch::builder().build();
+ for (unsigned i = 0; i < n; ++i) {
+ array_of_strings key(2, "");
+ key[0] = "key" + std::to_string(i);
+ key[1] = "subkey" + std::to_string(i % 10);
+ array_of_strings value(1, "");
+ value[0] = "value" + std::to_string(i);
+ sketch.update(hash_array_of_strings_key(key), value);
+ }
+ REQUIRE(sketch.is_empty() == (n == 0));
+ REQUIRE(sketch.get_estimate() == Approx(n).margin(n * 0.03));
+ std::ofstream os("aos_multikey_n" + std::to_string(n) + "_cpp.sk", std::ios::binary);
+ compact_array_of_strings_sketch(sketch).serialize(os, default_array_of_strings_serde<>());
+ }
+}
+
+TEST_CASE("aos sketch generate unicode strings", "[serialize_for_java]") {
+ auto sketch = aos_sketch::builder().build();
+ sketch.update(
+ hash_array_of_strings_key(make_array({u8"키", u8"열쇠"})),
+ make_array({u8"밸류", u8"값"})
+ );
+ sketch.update(
+ hash_array_of_strings_key(make_array({u8"🔑", u8"🗝️"})),
+ make_array({u8"📦", u8"🎁"})
+ );
+ sketch.update(
+ hash_array_of_strings_key(make_array({u8"ключ1", u8"ключ2"})),
+ make_array({u8"ценить1", u8"ценить2"})
+ );
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE(sketch.get_num_retained() == 3);
+ std::ofstream os("aos_unicode_cpp.sk", std::ios::binary);
+ compact_array_of_strings_sketch(sketch).serialize(os, default_array_of_strings_serde<>());
+}
+
+TEST_CASE("aos sketch generate empty strings", "[serialize_for_java]") {
+ auto sketch = aos_sketch::builder().build();
+ sketch.update(hash_array_of_strings_key(make_array({""})), make_array({"empty_key_value"}));
+ sketch.update(hash_array_of_strings_key(make_array({"empty_value_key"})), make_array({""}));
+ sketch.update(hash_array_of_strings_key(make_array({"", ""})), make_array({"", ""}));
+ REQUIRE_FALSE(sketch.is_empty());
+ REQUIRE(sketch.get_num_retained() == 3);
+ std::ofstream os("aos_empty_strings_cpp.sk", std::ios::binary);
+ compact_array_of_strings_sketch(sketch).serialize(os, default_array_of_strings_serde<>());
+}
+
+} /* namespace datasketches */
diff --git a/tuple/test/array_of_strings_sketch_test.cpp b/tuple/test/array_of_strings_sketch_test.cpp
new file mode 100644
index 0000000..5507c07
--- /dev/null
+++ b/tuple/test/array_of_strings_sketch_test.cpp
@@ -0,0 +1,270 @@
+/*
+ * 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.
+ */
+
+#include <algorithm>
+#include <fstream>
+#include <sstream>
+#include <string>
+#include <vector>
+
+#include <catch2/catch.hpp>
+
+#include "array_of_strings_sketch.hpp"
+
+namespace datasketches {
+
+TEST_CASE("aos update policy", "[tuple_sketch]") {
+ default_array_of_strings_update_policy policy;
+
+ SECTION("create empty") {
+ auto values = policy.create();
+ REQUIRE(values.size() == 0);
+ }
+
+ SECTION("replace array") {
+ auto values = policy.create();
+
+ array_of_strings input(2, "", std::allocator<std::string>());
+ input[0] = "alpha";
+ input[1] = "beta";
+ policy.update(values, input);
+ REQUIRE(values.size() == 2);
+ REQUIRE(values[0] == "alpha");
+ REQUIRE(values[1] == "beta");
+ input[0] = "changed";
+ REQUIRE(values[0] == "alpha");
+
+ array_of_strings input2(1, "", std::allocator<std::string>());
+ input2[0] = "gamma";
+ policy.update(values, input2);
+ REQUIRE(values.size() == 1);
+ REQUIRE(values[0] == "gamma");
+ }
+
+ SECTION("nullptr clears") {
+ array_of_strings values(2, "", std::allocator<std::string>());
+ values[0] = "one";
+ values[1] = "two";
+
+ policy.update(values, nullptr);
+ REQUIRE(values.size() == 0);
+ }
+
+ SECTION("pointer input copies") {
+ auto values = policy.create();
+
+ array_of_strings input(2, "", std::allocator<std::string>());
+ input[0] = "first";
+ input[1] = "second";
+ policy.update(values, &input);
+ REQUIRE(values.size() == 2);
+ REQUIRE(values[1] == "second");
+ input[1] = "changed";
+ REQUIRE(values[1] == "second");
+ }
+}
+
+TEST_CASE("aos sketch update", "[tuple_sketch]") {
+ auto make_array = [](std::initializer_list<const char*> entries) {
+ array_of_strings array(static_cast<uint8_t>(entries.size()), "", std::allocator<std::string>());
+ uint8_t i = 0;
+ for (const auto* entry: entries) array[i++] = entry;
+ return array;
+ };
+
+ SECTION("same key replaces summary") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().build();
+
+ sketch.update(
+ hash_array_of_strings_key(make_array({"alpha", "beta"})),
+ make_array({"first"})
+ );
+ sketch.update(
+ hash_array_of_strings_key(make_array({"alpha", "beta"})),
+ make_array({"second", "third"})
+ );
+
+ REQUIRE(sketch.get_num_retained() == 1);
+
+ auto it = sketch.begin();
+ REQUIRE(it != sketch.end());
+ REQUIRE(it->second.size() == 2);
+ REQUIRE(it->second[0] == "second");
+ REQUIRE(it->second[1] == "third");
+ }
+
+ SECTION("distinct keys retain multiple entries") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().build();
+
+ sketch.update(
+ hash_array_of_strings_key(make_array({"a", "bc"})),
+ make_array({"one"})
+ );
+ sketch.update(
+ hash_array_of_strings_key(make_array({"ab", "c"})),
+ make_array({"two"})
+ );
+
+ REQUIRE(sketch.get_num_retained() == 2);
+
+ bool saw_one = false;
+ bool saw_two = false;
+ for (const auto& entry: sketch) {
+ REQUIRE(entry.second.size() == 1);
+ if (entry.second[0] == "one") saw_one = true;
+ if (entry.second[0] == "two") saw_two = true;
+ }
+ REQUIRE(saw_one);
+ REQUIRE(saw_two);
+ }
+
+ SECTION("empty key") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().build();
+
+ sketch.update(hash_array_of_strings_key(make_array({})), make_array({"value"}));
+ REQUIRE(sketch.get_num_retained() == 1);
+
+ auto it = sketch.begin();
+ REQUIRE(it != sketch.end());
+ REQUIRE(it->second.size() == 1);
+ REQUIRE(it->second[0] == "value");
+ }
+}
+
+TEST_CASE("aos sketch: serialize deserialize", "[tuple_sketch]") {
+ auto make_array = [](std::initializer_list<std::string> entries) {
+ array_of_strings array(static_cast<uint8_t>(entries.size()), "", std::allocator<std::string>());
+ uint8_t i = 0;
+ for (const auto& entry: entries) array[i++] = entry;
+ return array;
+ };
+
+ auto collect_entries = [](const compact_array_of_strings_tuple_sketch<>& sketch) {
+ typedef std::pair<uint64_t, array_of_strings> entry_type;
+ std::vector<entry_type> entries;
+ for (const auto& entry: sketch) entries.push_back(entry);
+ struct entry_less {
+ bool operator()(const entry_type& lhs, const entry_type& rhs) const {
+ return lhs.first < rhs.first;
+ }
+ };
+ std::sort(entries.begin(), entries.end(), entry_less());
+ return entries;
+ };
+
+ auto check_round_trip = [&](const compact_array_of_strings_tuple_sketch<>& compact_sketch) {
+ std::stringstream ss;
+ ss.exceptions(std::ios::failbit | std::ios::badbit);
+ compact_sketch.serialize(ss, default_array_of_strings_serde<>());
+ auto deserialized_stream = compact_array_of_strings_tuple_sketch<>::deserialize(
+ ss, DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+
+ auto bytes = compact_sketch.serialize(0, default_array_of_strings_serde<>());
+ auto deserialized_bytes = compact_array_of_strings_tuple_sketch<>::deserialize(
+ bytes.data(), bytes.size(), DEFAULT_SEED, default_array_of_strings_serde<>()
+ );
+
+ const compact_array_of_strings_tuple_sketch<>* deserialized_list[2] = {
+ &deserialized_stream,
+ &deserialized_bytes
+ };
+ for (int list_index = 0; list_index < 2; ++list_index) {
+ const compact_array_of_strings_tuple_sketch<>* deserialized = deserialized_list[list_index];
+ REQUIRE(compact_sketch.is_empty() == deserialized->is_empty());
+ REQUIRE(compact_sketch.is_estimation_mode() == deserialized->is_estimation_mode());
+ REQUIRE(compact_sketch.is_ordered() == deserialized->is_ordered());
+ REQUIRE(compact_sketch.get_num_retained() == deserialized->get_num_retained());
+ REQUIRE(compact_sketch.get_theta() == Approx(deserialized->get_theta()).margin(1e-10));
+ REQUIRE(compact_sketch.get_estimate() == Approx(deserialized->get_estimate()).margin(1e-10));
+ REQUIRE(compact_sketch.get_lower_bound(1) == Approx(deserialized->get_lower_bound(1)).margin(1e-10));
+ REQUIRE(compact_sketch.get_upper_bound(1) == Approx(deserialized->get_upper_bound(1)).margin(1e-10));
+
+ auto original_entries = collect_entries(compact_sketch);
+ auto round_trip_entries = collect_entries(*deserialized);
+ REQUIRE(original_entries.size() == round_trip_entries.size());
+ for (size_t i = 0; i < original_entries.size(); ++i) {
+ REQUIRE(original_entries[i].first == round_trip_entries[i].first);
+ REQUIRE(original_entries[i].second.size() == round_trip_entries[i].second.size());
+ for (size_t j = 0; j < original_entries[i].second.size(); ++j) {
+ REQUIRE(original_entries[i].second[static_cast<uint8_t>(j)] ==
+ round_trip_entries[i].second[static_cast<uint8_t>(j)]);
+ }
+ }
+ }
+ };
+
+ auto run_tests = [&](const update_array_of_strings_tuple_sketch<>& sketch) {
+ auto ordered = compact_array_of_strings_sketch(sketch, true);
+ auto unordered = compact_array_of_strings_sketch(sketch, false);
+ check_round_trip(ordered);
+ check_round_trip(unordered);
+ };
+
+ SECTION("empty sketch") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().build();
+ run_tests(sketch);
+ }
+
+ SECTION("single entry sketch") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().build();
+ sketch.update(hash_array_of_strings_key(make_array({"key"})), make_array({"value"}));
+ run_tests(sketch);
+ }
+
+ SECTION("multiple entries exact mode") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().set_lg_k(8).build();
+ for (int i = 0; i < 50; ++i) {
+ sketch.update(
+ hash_array_of_strings_key(make_array({std::string("key-") + std::to_string(i)})),
+ make_array({std::string("value-") + std::to_string(i), "extra"})
+ );
+ }
+ REQUIRE_FALSE(sketch.is_estimation_mode());
+ run_tests(sketch);
+ }
+
+ SECTION("multiple entries estimation mode") {
+ auto sketch = update_array_of_strings_tuple_sketch<>::builder().build();
+ for (int i = 0; i < 10000; ++i) {
+ sketch.update(
+ hash_array_of_strings_key(make_array({std::string("key-") + std::to_string(i)})),
+ make_array({std::string("value-") + std::to_string(i)})
+ );
+ }
+ REQUIRE(sketch.is_estimation_mode());
+ run_tests(sketch);
+ }
+}
+
+TEST_CASE("aos serde validation", "[tuple_sketch]") {
+ default_array_of_strings_serde<> serde;
+
+ SECTION("too many nodes rejected") {
+ array_of_strings array(128, "", std::allocator<std::string>());
+ std::stringstream ss;
+ ss.exceptions(std::ios::failbit | std::ios::badbit);
+ REQUIRE_THROWS_WITH(
+ serde.serialize(ss, &array, 1),
+ Catch::Matchers::Contains("size exceeds 127")
+ );
+ }
+}
+
+} /* namespace datasketches */
