From 96be3f122c3bb617aa2adfdb7f1f6d971d077376 Mon Sep 17 00:00:00 2001 From: Alex Ainscow Date: Mon, 10 Mar 2025 11:31:45 +0000 Subject: [PATCH] common/include: Add map type election and fmt::format to interval_map Add capability to choose the type of map used in interval_map. The default will be std::map and so should not change any existing implementation. This behaviour is already available in interval_set. The intention is to enable a more efficient map library which suits a particular application. The optimized EC code, which is coming soon, will use a boost::flat_map here since it deals with large numbers of very small (usually single-entry) interval_maps. Also adds fmt::format support and refactors print functions in both set and map. Signed-off-by: Alex Ainscow --- src/common/interval_map.h | 70 ++++++++++++++++++---------- src/include/interval_set.h | 49 +++++++++++++------ src/test/common/test_interval_map.cc | 49 +++++++++++++++---- src/test/common/test_interval_set.cc | 30 ++++++++++++ 4 files changed, 152 insertions(+), 46 deletions(-) diff --git a/src/common/interval_map.h b/src/common/interval_map.h index 433a018da9d24..e363d938b78c1 100644 --- a/src/common/interval_map.h +++ b/src/common/interval_map.h @@ -18,7 +18,6 @@ #include "include/interval_set.h" #include -template /** * interval_map * @@ -31,13 +30,14 @@ template * commutativity, which doesn't work if we want more recent insertions * to overwrite previous ones. */ +template class C = std::map> class interval_map { S s; - using map = std::map >; - using mapiter = typename std::map >::iterator; - using cmapiter = typename std::map >::const_iterator; - map m; - std::pair get_range(K off, K len) { + using Map = C >; + using Mapiter = typename Map::iterator; + using Cmapiter = typename Map::const_iterator; + Map m; + std::pair get_range(K off, K len) { // fst is first iterator with end after off (may be end) auto fst = m.upper_bound(off); if (fst != m.begin()) @@ -49,7 +49,7 @@ class interval_map { auto lst = m.lower_bound(off + len); return std::make_pair(fst, lst); } - std::pair get_range(K off, K len) const { + std::pair get_range(K off, K len) const { // fst is first iterator with end after off (may be end) auto fst = get_range_fst(off); @@ -57,7 +57,7 @@ class interval_map { auto lst = m.lower_bound(off + len); return std::make_pair(fst, lst); } - cmapiter get_range_fst(K off) const { + Cmapiter get_range_fst(K off) const { // fst is first iterator with end after off (may be end) auto fst = m.upper_bound(off); if (fst != m.begin()) @@ -67,7 +67,7 @@ class interval_map { return fst; } - void try_merge(mapiter niter) { + void try_merge(Mapiter niter) { if (niter != m.begin()) { auto prev = niter; prev--; @@ -109,7 +109,7 @@ class interval_map { } public: interval_map() = default; - interval_map(std::initializer_list l) { + interval_map(std::initializer_list l) { for (auto& v : l) { insert(v.first, v.second.first, v.second.second); } @@ -202,17 +202,23 @@ public: bool empty() const { return m.empty(); } - interval_set get_interval_set() const { - interval_set ret; + interval_set get_interval_set() const { + interval_set ret; for (auto &&i: *this) { ret.insert(i.get_off(), i.get_len()); } return ret; } + template + void to_interval_set(interval_set &set) const { + for (auto &&i: *this) { + set.insert(i.get_off(), i.get_len()); + } + } class const_iterator { - cmapiter it; - const_iterator(cmapiter &&it) : it(std::move(it)) {} - const_iterator(const cmapiter &it) : it(it) {} + Cmapiter it; + const_iterator(Cmapiter &&it) : it(std::move(it)) {} + const_iterator(const Cmapiter &it) : it(it) {} friend class interval_map; public: @@ -302,25 +308,41 @@ public: return m == rhs.m; } - std::ostream &print(std::ostream &out) const { + void print(std::ostream &os) const { bool first = true; - out << "{"; + os << "{"; for (auto &&i: *this) { if (first) { first = false; } else { - out << ","; + os << ","; } - out << i.get_off() << "~" << i.get_len() << "(" + os << i.get_off() << "~" << i.get_len() << "(" << s.length(i.get_val()) << ")"; } - return out << "}"; + os << "}"; + } + + std::string fmt_print() const + requires has_formatter { + std::string str = "{"; + bool first = true; + for (auto &&i: *this) { + if (first) { + first = false; + } else { + str += ","; + } + str += fmt::format("{}~{}({})", i.get_off(), i.get_len(), + s.length(i.get_val())); + } + str += "}"; + return str; } }; -template -std::ostream &operator<<(std::ostream &out, const interval_map &m) { - return m.print(out); -} +// make sure fmt::range would not try (and fail) to treat interval_map as a range +template class C> +struct fmt::is_range, char> : std::false_type {}; #endif diff --git a/src/include/interval_set.h b/src/include/interval_set.h index ef4fbf09d9ba9..e93ba7601e287 100644 --- a/src/include/interval_set.h +++ b/src/include/interval_set.h @@ -19,6 +19,9 @@ #include #include #include +#include +#include "common/fmt_common.h" +#include "common/dout.h" #include "encoding.h" @@ -246,6 +249,35 @@ class interval_set { return const_iterator(m.end()); } + void print(std::ostream& os) const { + os << "["; + bool first = true; + for (const auto& [start, len] : *this) { + if (!first) { + os << ","; + } + os << start << "~" << len; + first = false; + } + os << "]"; + } + + std::string fmt_print() const + requires has_formatter { + std::string s = "["; + bool first = true; + for (const auto& [start, len] : *this) { + if (!first) { + s += ","; + } else { + first = false; + } + s += fmt::format("{}~{}", start, len); + } + s += "]"; + return s; + } + // helpers private: auto find_inc(T start) const { @@ -963,19 +995,8 @@ public: } }; - -template class C> -inline std::ostream& operator<<(std::ostream& out, const interval_set &s) { - out << "["; - bool first = true; - for (const auto& [start, len] : s) { - if (!first) out << ","; - out << start << "~" << len; - first = false; - } - out << "]"; - return out; -} - +// make sure fmt::range would not try (and fail) to treat interval_set as a range +template class C, bool strict> +struct fmt::is_range, char> : std::false_type {}; #endif diff --git a/src/test/common/test_interval_map.cc b/src/test/common/test_interval_map.cc index 39bf291f60612..04c3379ddbb4e 100644 --- a/src/test/common/test_interval_map.cc +++ b/src/test/common/test_interval_map.cc @@ -27,11 +27,15 @@ public: using TestType = T; }; -template +template class _map = std::map> struct bufferlist_test_type { using key = _key; using value = bufferlist; + static constexpr bool can_merge() { + return _can_merge::value; + } + struct make_splitter { template struct apply { @@ -57,6 +61,9 @@ struct bufferlist_test_type { }; }; + using splitter = boost::mpl::apply; + using imap = interval_map; + struct generate_random { bufferlist operator()(key len) { bufferlist bl; @@ -70,21 +77,27 @@ struct bufferlist_test_type { }; }; -using IntervalMapTypes = ::testing::Types< bufferlist_test_type >; +using IntervalMapTypes = ::testing::Types< + bufferlist_test_type, + bufferlist_test_type, + bufferlist_test_type, + bufferlist_test_type +>; TYPED_TEST_SUITE(IntervalMapTest, IntervalMapTypes); +// Someone with more C++ foo can probably figure out a better way of doing this. +// However, for now, we skip some tests if using the wrong merge. #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; (void)imap(); \ + using splitter = TT::splitter; \ + using imap = TT::imap; (void)imap(); \ typename TT::generate_random gen; \ val v(gen(5)); \ - splitter split; (void)split.split(0, 0, v); + splitter split; (void)split.split(0, 0, v); \ + { _can_merge cm; if(TT::can_merge() != cm()) return; } #define USING_NO_MERGE USING(std::false_type) #define USING_WITH_MERGE USING(std::true_type) @@ -371,4 +384,24 @@ TYPED_TEST(IntervalMapTest, get_start_end_off) m.insert(20,5, gen(5)); ASSERT_EQ(5, m.get_start_off()); ASSERT_EQ(25, m.get_end_off()); -} \ No newline at end of file +} + +TYPED_TEST(IntervalMapTest, print) { + USING_NO_MERGE; + imap m; + + { + std::ostringstream out; + m.insert(0, 5, gen(5)); + out << m; + ASSERT_EQ("{0~5(5)}", fmt::format("{}", m)); + EXPECT_EQ("{0~5(5)}", out.str() ); + } + { + std::ostringstream out; + m.insert(10, 5, gen(5)); + out << m; + ASSERT_EQ("{0~5(5),10~5(5)}", fmt::format("{}", m)); + EXPECT_EQ("{0~5(5),10~5(5)}", out.str() ); + } +} diff --git a/src/test/common/test_interval_set.cc b/src/test/common/test_interval_set.cc index 4830d7aab0b34..75d4c83da2e8c 100644 --- a/src/test/common/test_interval_set.cc +++ b/src/test/common/test_interval_set.cc @@ -1859,4 +1859,34 @@ TYPED_TEST(IntervalSetTest, subtract) { ASSERT_STRICT_DEATH(iset1.subtract(iset2), ASSERT_EQ(iset1, iset3)); } + + // Subtract identical + { + ISet iset1, iset2; + iset1.union_insert(0, 5); + iset2.union_insert(0, 5); + + iset1.subtract(iset2); + ASSERT_TRUE(iset1.empty()); + } +} + +TYPED_TEST(IntervalSetTest, print) { + typedef typename TestFixture::ISet ISet; + + ISet iset; + { + std::ostringstream out; + iset.insert(0, 5); + out << iset; + ASSERT_EQ("[0~5]", fmt::format("{}", iset)); + EXPECT_EQ("[0~5]", out.str() ); + } + { + std::ostringstream out; + iset.insert(10, 5); + out << iset; + ASSERT_EQ("[0~5,10~5]", fmt::format("{}", iset)); + EXPECT_EQ("[0~5,10~5]", out.str() ); + } } -- 2.39.5