From 0e6e218215ffec1e2b8e96a09187b4436a26080a Mon Sep 17 00:00:00 2001 From: Xuehan Xu Date: Tue, 18 Feb 2025 12:05:47 +0800 Subject: [PATCH] crimson/os/seastore/omap_manager: do binary search on omap nodes Signed-off-by: Xuehan Xu --- .../omap_manager/btree/omap_btree_node_impl.cc | 7 +++++-- .../omap_manager/btree/string_kv_node_layout.h | 10 ++++------ 2 files changed, 9 insertions(+), 8 deletions(-) diff --git a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc index df97f394a0d12..9db3d09440a91 100644 --- a/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc +++ b/src/crimson/os/seastore/omap_manager/btree/omap_btree_node_impl.cc @@ -495,8 +495,11 @@ OMapInnerNode::merge_entry( OMapInnerNode::internal_iterator_t OMapInnerNode::get_containing_child(const std::string &key) { - auto iter = std::find_if(iter_begin(), iter_end(), - [&key](auto it) { return it.contains(key); }); + auto iter = string_lower_bound(key); + if (iter == iter_end() || (iter != iter_begin() && iter.get_key() > key)) { + iter--; + } + assert(iter.contains(key)); return iter; } 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 3825ebef14553..93a9b8dedb154 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,13 +597,11 @@ 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; + auto iter = string_lower_bound(str); + if (iter.get_key() == str) { + return iter; } - return ret; + return iter_cend(); } iterator find_string_key(std::string_view str) { -- 2.39.5