diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:45:59 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:45:59 +0000 |
commit | 19fcec84d8d7d21e796c7624e521b60d28ee21ed (patch) | |
tree | 42d26aa27d1e3f7c0b8bd3fd14e7d7082f5008dc /src/test/common/test_interval_map.cc | |
parent | Initial commit. (diff) | |
download | ceph-upstream.tar.xz ceph-upstream.zip |
Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/test/common/test_interval_map.cc')
-rw-r--r-- | src/test/common/test_interval_map.cc | 337 |
1 files changed, 337 insertions, 0 deletions
diff --git a/src/test/common/test_interval_map.cc b/src/test/common/test_interval_map.cc new file mode 100644 index 000000000..99f676f28 --- /dev/null +++ b/src/test/common/test_interval_map.cc @@ -0,0 +1,337 @@ +// -*- 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) 2016 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 <gtest/gtest.h> +#include <boost/random/mersenne_twister.hpp> +#include <boost/random/uniform_int_distribution.hpp> +#include <boost/mpl/apply.hpp> +#include "include/buffer.h" +#include "common/interval_map.h" + +using namespace std; + +template<typename T> +class IntervalMapTest : public ::testing::Test { +public: + using TestType = T; +}; + +template <typename _key> +struct bufferlist_test_type { + using key = _key; + using value = bufferlist; + + struct make_splitter { + template <typename merge_t> + struct apply { + bufferlist split( + key offset, + key len, + bufferlist &bu) const { + bufferlist bl; + bl.substr_of(bu, offset, len); + return bl; + } + bool can_merge(const bufferlist &left, const bufferlist &right) const { + return merge_t::value; + } + bufferlist merge(bufferlist &&left, bufferlist &&right) const { + bufferlist bl; + left.claim_append(right); + return std::move(left); + } + uint64_t length(const bufferlist &r) const { + return r.length(); + } + }; + }; + + struct generate_random { + bufferlist operator()(key len) { + bufferlist bl; + boost::random::mt19937 rng; + boost::random::uniform_int_distribution<> chr(0,255); + for (key i = 0; i < len; ++i) { + bl.append((char)chr(rng)); + } + return bl; + } + }; +}; + +using IntervalMapTypes = ::testing::Types< bufferlist_test_type<uint64_t> >; + +TYPED_TEST_SUITE(IntervalMapTest, IntervalMapTypes); + +#define USING(_can_merge) \ + using TT = typename TestFixture::TestType; \ + using key = typename TT::key; (void)key(0); \ + using val = typename TT::value; (void)val(0); \ + using splitter = typename boost::mpl::apply< \ + typename TT::make_splitter, \ + _can_merge>; \ + using imap = interval_map<key, val, splitter>; (void)imap(); \ + typename TT::generate_random gen; \ + val v(gen(5)); \ + splitter split; (void)split.split(0, 0, v); + +#define USING_NO_MERGE USING(std::false_type) +#define USING_WITH_MERGE USING(std::true_type) + +TYPED_TEST(IntervalMapTest, empty) { + USING_NO_MERGE; + imap m; + ASSERT_TRUE(m.empty()); +} + +TYPED_TEST(IntervalMapTest, insert) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(10, 5, vals[2]); + m.insert(5, 5, vals[1]); + ASSERT_EQ(m.ext_count(), 3u); + + unsigned i = 0; + for (auto &&ext: m) { + ASSERT_EQ(ext.get_len(), 5u); + ASSERT_EQ(ext.get_off(), 5u * i); + ASSERT_EQ(ext.get_val(), vals[i]); + ++i; + } + ASSERT_EQ(i, m.ext_count()); +} + +TYPED_TEST(IntervalMapTest, insert_begin_overlap) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(5, 5, vals[1]); + m.insert(10, 5, vals[2]); + m.insert(1, 5, vals[0]); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 1u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[0]); + ++iter; + + ASSERT_EQ(iter.get_off(), 6u); + ASSERT_EQ(iter.get_len(), 4u); + ASSERT_EQ(iter.get_val(), split.split(1, 4, vals[1])); + ++iter; + + ASSERT_EQ(iter.get_off(), 10u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, insert_end_overlap) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(5, 5, vals[1]); + m.insert(8, 5, vals[2]); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 0u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[0]); + ++iter; + + ASSERT_EQ(iter.get_off(), 5u); + ASSERT_EQ(iter.get_len(), 3u); + ASSERT_EQ(iter.get_val(), split.split(0, 3, vals[1])); + ++iter; + + ASSERT_EQ(iter.get_off(), 8u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, insert_middle_overlap) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(7), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(10, 5, vals[2]); + m.insert(4, 7, vals[1]); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 0u); + ASSERT_EQ(iter.get_len(), 4u); + ASSERT_EQ(iter.get_val(), split.split(0, 4, vals[0])); + ++iter; + + ASSERT_EQ(iter.get_off(), 4u); + ASSERT_EQ(iter.get_len(), 7u); + ASSERT_EQ(iter.get_val(), vals[1]); + ++iter; + + ASSERT_EQ(iter.get_off(), 11u); + ASSERT_EQ(iter.get_len(), 4u); + ASSERT_EQ(iter.get_val(), split.split(1, 4, vals[2])); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, insert_single_exact_overlap) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(0, 5, gen(5)); + m.insert(5, 5, vals[1]); + m.insert(10, 5, vals[2]); + m.insert(0, 5, vals[0]); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 0u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[0]); + ++iter; + + ASSERT_EQ(iter.get_off(), 5u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[1]); + ++iter; + + ASSERT_EQ(iter.get_off(), 10u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, insert_single_exact_overlap_end) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(5, 5, vals[1]); + m.insert(10, 5, gen(5)); + m.insert(10, 5, vals[2]); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 0u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[0]); + ++iter; + + ASSERT_EQ(iter.get_off(), 5u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[1]); + ++iter; + + ASSERT_EQ(iter.get_off(), 10u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, erase) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(5, 5, vals[1]); + m.insert(10, 5, vals[2]); + + m.erase(3, 5); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 0u); + ASSERT_EQ(iter.get_len(), 3u); + ASSERT_EQ(iter.get_val(), split.split(0, 3, vals[0])); + ++iter; + + ASSERT_EQ(iter.get_off(), 8u); + ASSERT_EQ(iter.get_len(), 2u); + ASSERT_EQ(iter.get_val(), split.split(3, 2, vals[1])); + ++iter; + + ASSERT_EQ(iter.get_off(), 10u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, erase_exact) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(5, 5, vals[1]); + m.insert(10, 5, vals[2]); + + m.erase(5, 5); + + auto iter = m.begin(); + ASSERT_EQ(iter.get_off(), 0u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[0]); + ++iter; + + ASSERT_EQ(iter.get_off(), 10u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, m.end()); +} + +TYPED_TEST(IntervalMapTest, get_containing_range) { + USING_NO_MERGE; + imap m; + vector<val> vals{gen(5), gen(5), gen(5), gen(5)}; + m.insert(0, 5, vals[0]); + m.insert(10, 5, vals[1]); + m.insert(20, 5, vals[2]); + m.insert(30, 5, vals[3]); + + auto rng = m.get_containing_range(5, 21); + auto iter = rng.first; + + ASSERT_EQ(iter.get_off(), 10u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[1]); + ++iter; + + ASSERT_EQ(iter.get_off(), 20u); + ASSERT_EQ(iter.get_len(), 5u); + ASSERT_EQ(iter.get_val(), vals[2]); + ++iter; + + ASSERT_EQ(iter, rng.second); +} + +TYPED_TEST(IntervalMapTest, merge) { + USING_WITH_MERGE; + imap m; + m.insert(10, 4, gen(4)); + m.insert(11, 1, gen(1)); +} |