This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch 5.3.x in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 5b7d42f65fae80d436e47d1b55976b38af973264 Author: Rusty Conover <[email protected]> AuthorDate: Tue Oct 27 09:53:42 2026 -0400 fix: req_sketch truncated k to 8 bits (#552) (cherry picked from commit 31e615c809511e08fa5e78717d23b02768fd75cb, the merge of #552) --- req/include/req_common.hpp | 2 ++ req/include/req_sketch.hpp | 4 +++- req/include/req_sketch_impl.hpp | 5 ++++- req/test/req_sketch_test.cpp | 33 +++++++++++++++++++++++++++++++++ 4 files changed, 42 insertions(+), 2 deletions(-) diff --git a/req/include/req_common.hpp b/req/include/req_common.hpp index aaead872..4bd9f7f6 100755 --- a/req/include/req_common.hpp +++ b/req/include/req_common.hpp @@ -31,6 +31,8 @@ namespace datasketches { namespace req_constants { /// minimum value of parameter K const uint16_t MIN_K = 4; + /// maximum value of parameter K + const uint16_t MAX_K = 1024; /// initial number of sections const uint8_t INIT_NUM_SECTIONS = 3; /// multiplier for nominal capacity diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp index 52295bd2..2e2bc309 100755 --- a/req/include/req_sketch.hpp +++ b/req/include/req_sketch.hpp @@ -98,12 +98,14 @@ public: /** * Constructor - * @param k Controls the size and error of the sketch. It must be even and in the range [4, 1024], inclusive. + * @param k Controls the size and error of the sketch. It must be no greater than 1024. + * Values below 4 are raised to 4, and odd values are rounded down to the nearest even value. * Value of 12 roughly corresponds to 1% relative error guarantee at 95% confidence. * @param hra if true, the default, the high ranks are prioritized for better * accuracy. Otherwise the low ranks are prioritized for better accuracy. * @param comparator strict weak ordering function (see C++ named requirements: Compare) * @param allocator used by this sketch to allocate memory + * @throws std::invalid_argument if k is greater than 1024 */ explicit req_sketch(uint16_t k, bool hra = true, const Comparator& comparator = Comparator(), const Allocator& allocator = Allocator()); diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp index 7f0b4557..8acea8bc 100755 --- a/req/include/req_sketch_impl.hpp +++ b/req/include/req_sketch_impl.hpp @@ -30,7 +30,7 @@ template<typename T, typename C, typename A> req_sketch<T, C, A>::req_sketch(uint16_t k, bool hra, const C& comparator, const A& allocator): comparator_(comparator), allocator_(allocator), -k_(std::max<uint8_t>(static_cast<int>(k) & -2, static_cast<int>(req_constants::MIN_K))), //rounds down one if odd +k_(std::max<uint16_t>(static_cast<int>(k) & -2, static_cast<int>(req_constants::MIN_K))), //rounds down one if odd hra_(hra), max_nom_size_(0), num_retained_(0), @@ -40,6 +40,9 @@ min_item_(), max_item_(), sorted_view_(nullptr) { + if (k > req_constants::MAX_K) { + throw std::invalid_argument("K must be <= " + std::to_string(req_constants::MAX_K) + ": " + std::to_string(k)); + } grow(); } diff --git a/req/test/req_sketch_test.cpp b/req/test/req_sketch_test.cpp index 8de8f865..c8cf5cbe 100755 --- a/req/test/req_sketch_test.cpp +++ b/req/test/req_sketch_test.cpp @@ -54,6 +54,39 @@ TEST_CASE("req sketch: empty", "[req_sketch]") { REQUIRE_THROWS_AS(sketch.get_PMF(split_points, 1), std::runtime_error); } +TEST_CASE("req sketch: k above 255", "[req_sketch]") { + // k used to be truncated to 8 bits: 256 became 4 and 500 became 244 + REQUIRE(req_sketch<float>(256).get_k() == 256); + REQUIRE(req_sketch<float>(500).get_k() == 500); + REQUIRE(req_sketch<float>(1024).get_k() == 1024); + REQUIRE(req_sketch<float>(1001).get_k() == 1000); // rounds down if odd + + req_sketch<float> sketch(1024); + const size_t n = 100000; + for (size_t i = 0; i < n; i++) sketch.update(static_cast<float>(i)); + REQUIRE(sketch.is_estimation_mode()); + auto bytes = sketch.serialize(); + auto sketch2 = req_sketch<float>::deserialize(bytes.data(), bytes.size()); + REQUIRE(sketch2.get_k() == 1024); + REQUIRE(sketch2.get_n() == n); + REQUIRE(sketch2.get_num_retained() == sketch.get_num_retained()); +} + +TEST_CASE("req sketch: k bounds", "[req_sketch]") { + for (bool hra: {true, false}) { + REQUIRE(req_sketch<float>(0, hra).get_k() == 4); + REQUIRE(req_sketch<float>(3, hra).get_k() == 4); + REQUIRE(req_sketch<float>(4, hra).get_k() == 4); + REQUIRE(req_sketch<float>(5, hra).get_k() == 4); + REQUIRE(req_sketch<float>(1023, hra).get_k() == 1022); + REQUIRE(req_sketch<float>(1024, hra).get_k() == 1024); + // Reject the original k, even if rounding down would put it in range. + REQUIRE_THROWS_AS(req_sketch<float>(1025, hra), std::invalid_argument); + REQUIRE_THROWS_AS(req_sketch<float>(1026, hra), std::invalid_argument); + REQUIRE_THROWS_AS(req_sketch<float>(std::numeric_limits<uint16_t>::max(), hra), std::invalid_argument); + } +} + TEST_CASE("req sketch: single value, lra", "[req_sketch]") { req_sketch<float> sketch(12, false); sketch.update(1.0f); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
