From 4a85e0d7381ba61f7135cefdf8925e95932fa441 Mon Sep 17 00:00:00 2001 From: Chanyoung Park Date: Mon, 11 Aug 2025 03:02:04 +0000 Subject: [PATCH] crimson/.../string_kv_node_layout: switch linear to binary search Signed-off-by: Chanyoung Park --- .../btree/string_kv_node_layout.h | 54 ++++++++----------- 1 file changed, 21 insertions(+), 33 deletions(-) diff --git a/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h b/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h index 9370213ef2a18..16ce1d2dc0c61 100644 --- a/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h +++ b/src/crimson/os/seastore/omap_manager/btree/string_kv_node_layout.h @@ -597,11 +597,8 @@ public: } const_iterator find_string_key(std::string_view str) const { - auto iter = string_lower_bound(str); - if (iter.get_key() == str) { - return iter; - } - return iter_cend(); + auto it = string_lower_bound(str); + return (it != iter_cend() && it.get_key() == str) ? it : iter_cend(); } iterator find_string_key(std::string_view str) { @@ -1182,20 +1179,14 @@ public: } const_iterator string_lower_bound(std::string_view str) const { - uint16_t start = 0, end = get_size(); - while (start != end) { - unsigned mid = (start + end) / 2; - const_iterator iter(this, mid); - std::string s = iter->get_key(); - if (s < str) { - start = ++mid; - } else if (s > str) { - end = mid; - } else { - return iter; - } - } - return const_iterator(this, start); + auto it = std::lower_bound(boost::make_counting_iterator(0), + boost::make_counting_iterator(get_size()), + str, + [this](uint16_t i, std::string_view str) { + const_iterator iter(this, i); + return iter->get_key() < str; + }); + return const_iterator(this, *it); } iterator string_lower_bound(std::string_view str) { @@ -1204,13 +1195,14 @@ public: } const_iterator string_upper_bound(std::string_view str) const { - auto ret = iter_begin(); - for (; ret != iter_end(); ++ret) { - std::string s = ret->get_key(); - if (s > str) - break; - } - return ret; + auto it = std::upper_bound(boost::make_counting_iterator(0), + boost::make_counting_iterator(get_size()), + str, + [this](std::string_view str, uint16_t i) { + const_iterator iter(this, i); + return str < iter->get_key(); + }); + return const_iterator(this, *it); } iterator string_upper_bound(std::string_view str) { @@ -1219,14 +1211,10 @@ public: } const_iterator find_string_key(std::string_view str) const { - auto ret = iter_begin(); - for (; ret != iter_end(); ++ret) { - std::string s = ret->get_key(); - if (s == str) - break; - } - return ret; + auto it = string_lower_bound(str); + return (it != iter_end() && it.get_key() == str) ? it : iter_end(); } + iterator find_string_key(std::string_view str) { const auto &tref = *this; return iterator(this, tref.find_string_key(str).index); -- 2.39.5