From e6918187568dbd01842d8d1d2c808ce16a894239 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 21 Apr 2024 13:54:28 +0200 Subject: Adding upstream version 18.2.2. Signed-off-by: Daniel Baumann --- src/test/common/test_bounded_key_counter.cc | 200 ++++++++++++++++++++++++++++ 1 file changed, 200 insertions(+) create mode 100644 src/test/common/test_bounded_key_counter.cc (limited to 'src/test/common/test_bounded_key_counter.cc') diff --git a/src/test/common/test_bounded_key_counter.cc b/src/test/common/test_bounded_key_counter.cc new file mode 100644 index 000000000..a87394051 --- /dev/null +++ b/src/test/common/test_bounded_key_counter.cc @@ -0,0 +1,200 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab +/* + * Ceph - scalable distributed file system + * + * Copyright (C) 2015 Red Hat + * + * This is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License version 2.1, as published by the Free Software + * Foundation. See file COPYING. + * + */ +#include "common/bounded_key_counter.h" +#include + +namespace { + +// call get_highest() and return the number of callbacks +template +size_t count_highest(BoundedKeyCounter& counter, size_t count) +{ + size_t callbacks = 0; + counter.get_highest(count, [&callbacks] (const Key& key, Count count) { + ++callbacks; + }); + return callbacks; +} + +// call get_highest() and return the key/value pairs as a vector +template >> +Vector get_highest(BoundedKeyCounter& counter, size_t count) +{ + Vector results; + counter.get_highest(count, [&results] (const Key& key, Count count) { + results.emplace_back(key, count); + }); + return results; +} + +} // anonymous namespace + +TEST(BoundedKeyCounter, Insert) +{ + BoundedKeyCounter counter(2); + EXPECT_EQ(1, counter.insert(0)); // insert new key + EXPECT_EQ(2, counter.insert(0)); // increment counter + EXPECT_EQ(7, counter.insert(0, 5)); // add 5 to counter + EXPECT_EQ(1, counter.insert(1)); // insert new key + EXPECT_EQ(0, counter.insert(2)); // reject new key +} + +TEST(BoundedKeyCounter, Erase) +{ + BoundedKeyCounter counter(10); + + counter.erase(0); // ok to erase nonexistent key + EXPECT_EQ(1, counter.insert(1, 1)); + EXPECT_EQ(2, counter.insert(2, 2)); + EXPECT_EQ(3, counter.insert(3, 3)); + counter.erase(2); + counter.erase(1); + counter.erase(3); + counter.erase(3); + EXPECT_EQ(0u, count_highest(counter, 10)); +} + +TEST(BoundedKeyCounter, Size) +{ + BoundedKeyCounter counter(4); + EXPECT_EQ(0u, counter.size()); + EXPECT_EQ(1, counter.insert(1, 1)); + EXPECT_EQ(1u, counter.size()); + EXPECT_EQ(2, counter.insert(2, 2)); + EXPECT_EQ(2u, counter.size()); + EXPECT_EQ(3, counter.insert(3, 3)); + EXPECT_EQ(3u, counter.size()); + EXPECT_EQ(4, counter.insert(4, 4)); + EXPECT_EQ(4u, counter.size()); + EXPECT_EQ(0, counter.insert(5, 5)); // reject new key + EXPECT_EQ(4u, counter.size()); // size unchanged + EXPECT_EQ(5, counter.insert(4, 1)); // update existing key + EXPECT_EQ(4u, counter.size()); // size unchanged + counter.erase(2); + EXPECT_EQ(3u, counter.size()); + counter.erase(2); // erase duplicate + EXPECT_EQ(3u, counter.size()); // size unchanged + counter.erase(4); + EXPECT_EQ(2u, counter.size()); + counter.erase(1); + EXPECT_EQ(1u, counter.size()); + counter.erase(3); + EXPECT_EQ(0u, counter.size()); + EXPECT_EQ(6, counter.insert(6, 6)); + EXPECT_EQ(1u, counter.size()); + counter.clear(); + EXPECT_EQ(0u, counter.size()); +} + +TEST(BoundedKeyCounter, GetHighest) +{ + BoundedKeyCounter counter(10); + using Vector = std::vector>; + + EXPECT_EQ(0u, count_highest(counter, 0)); // ok to request 0 + EXPECT_EQ(0u, count_highest(counter, 10)); // empty + EXPECT_EQ(0u, count_highest(counter, 999)); // ok to request count >> 10 + + EXPECT_EQ(1, counter.insert(1, 1)); + EXPECT_EQ(Vector({{1,1}}), get_highest(counter, 10)); + EXPECT_EQ(2, counter.insert(2, 2)); + EXPECT_EQ(Vector({{2,2},{1,1}}), get_highest(counter, 10)); + EXPECT_EQ(3, counter.insert(3, 3)); + EXPECT_EQ(Vector({{3,3},{2,2},{1,1}}), get_highest(counter, 10)); + EXPECT_EQ(3, counter.insert(4, 3)); // insert duplicated count=3 + // still returns 4 entries (but order of {3,3} and {4,3} is unspecified) + EXPECT_EQ(4u, count_highest(counter, 10)); + counter.erase(3); + EXPECT_EQ(Vector({{4,3},{2,2},{1,1}}), get_highest(counter, 10)); + EXPECT_EQ(0u, count_highest(counter, 0)); // requesting 0 still returns 0 +} + +TEST(BoundedKeyCounter, Clear) +{ + BoundedKeyCounter counter(2); + EXPECT_EQ(1, counter.insert(0)); // insert new key + EXPECT_EQ(1, counter.insert(1)); // insert new key + EXPECT_EQ(2u, count_highest(counter, 2)); // return 2 entries + + counter.clear(); + + EXPECT_EQ(0u, count_highest(counter, 2)); // return 0 entries + EXPECT_EQ(1, counter.insert(1)); // insert new key + EXPECT_EQ(1, counter.insert(2)); // insert new unique key + EXPECT_EQ(2u, count_highest(counter, 2)); // return 2 entries +} + +// tests for partial sort and invalidation +TEST(BoundedKeyCounter, GetNumSorted) +{ + struct MockCounter : public BoundedKeyCounter { + using BoundedKeyCounter::BoundedKeyCounter; + // expose as public for testing sort invalidations + using BoundedKeyCounter::get_num_sorted; + }; + + MockCounter counter(10); + + EXPECT_EQ(0u, counter.get_num_sorted()); + EXPECT_EQ(0u, count_highest(counter, 10)); + EXPECT_EQ(0u, counter.get_num_sorted()); + + EXPECT_EQ(2, counter.insert(2, 2)); + EXPECT_EQ(3, counter.insert(3, 3)); + EXPECT_EQ(4, counter.insert(4, 4)); + EXPECT_EQ(0u, counter.get_num_sorted()); + + EXPECT_EQ(0u, count_highest(counter, 0)); + EXPECT_EQ(0u, counter.get_num_sorted()); + EXPECT_EQ(1u, count_highest(counter, 1)); + EXPECT_EQ(1u, counter.get_num_sorted()); + EXPECT_EQ(2u, count_highest(counter, 2)); + EXPECT_EQ(2u, counter.get_num_sorted()); + EXPECT_EQ(3u, count_highest(counter, 10)); + EXPECT_EQ(3u, counter.get_num_sorted()); + + EXPECT_EQ(1, counter.insert(1, 1)); // insert at bottom does not invalidate + EXPECT_EQ(3u, counter.get_num_sorted()); + + EXPECT_EQ(4u, count_highest(counter, 10)); + EXPECT_EQ(4u, counter.get_num_sorted()); + + EXPECT_EQ(5, counter.insert(5, 5)); // insert at top invalidates sort + EXPECT_EQ(0u, counter.get_num_sorted()); + + EXPECT_EQ(0u, count_highest(counter, 0)); + EXPECT_EQ(0u, counter.get_num_sorted()); + EXPECT_EQ(1u, count_highest(counter, 1)); + EXPECT_EQ(1u, counter.get_num_sorted()); + EXPECT_EQ(2u, count_highest(counter, 2)); + EXPECT_EQ(2u, counter.get_num_sorted()); + EXPECT_EQ(3u, count_highest(counter, 3)); + EXPECT_EQ(3u, counter.get_num_sorted()); + EXPECT_EQ(4u, count_highest(counter, 4)); + EXPECT_EQ(4u, counter.get_num_sorted()); + EXPECT_EQ(5u, count_highest(counter, 10)); + EXPECT_EQ(5u, counter.get_num_sorted()); + + // updating an existing counter only invalidates entries <= that counter + EXPECT_EQ(2, counter.insert(1)); // invalidates {1,2} and {2,2} + EXPECT_EQ(3u, counter.get_num_sorted()); + + EXPECT_EQ(5u, count_highest(counter, 10)); + EXPECT_EQ(5u, counter.get_num_sorted()); + + counter.clear(); // invalidates sort + EXPECT_EQ(0u, counter.get_num_sorted()); +} + -- cgit v1.2.3