From 6c3297d497c0398dad05c6763af482f5d7e298eb Mon Sep 17 00:00:00 2001
From: chunmei-liu <chunmei.liu@intel.com>
Date: Mon, 13 Sep 2021 16:02:57 -0700
Subject: [PATCH] crimson/seastore:: add binary search for lba and omap
 iterator search

Signed-off-by: chunmei-liu <chunmei.liu@intel.com>
---
 src/crimson/common/fixed_kv_node_layout.h     | 33 +++++++++++------
 .../btree/string_kv_node_layout.h             | 37 ++++++++-----------
 2 files changed, 37 insertions(+), 33 deletions(-)

diff --git a/src/crimson/common/fixed_kv_node_layout.h b/src/crimson/common/fixed_kv_node_layout.h
index b13302881b82d..d2b0f88495ed9 100644
--- a/src/crimson/common/fixed_kv_node_layout.h
+++ b/src/crimson/common/fixed_kv_node_layout.h
@@ -3,8 +3,11 @@
 
 #pragma once
 
+#include <algorithm>
 #include <iostream>
 
+#include <boost/iterator/counting_iterator.hpp>
+
 #include "include/byteorder.h"
 
 #include "crimson/common/layout.h"
@@ -386,26 +389,32 @@ public:
   }
 
   const_iterator lower_bound(K l) const {
-    auto ret = begin();
-    for (; ret != end(); ++ret) {
-      if (ret->get_key() >= l)
-	break;
-    }
-    return ret;
+    auto it = std::lower_bound(boost::make_counting_iterator<uint16_t>(0),
+	                       boost::make_counting_iterator<uint16_t>(get_size()),
+		               l,
+		               [this](uint16_t i, K key) {
+			         const_iterator iter(this, i);
+			         return iter->get_key() < key;
+			       });
+    return const_iterator(this, *it);
   }
+
   iterator lower_bound(K l) {
     const auto &tref = *this;
     return iterator(this, tref.lower_bound(l).offset);
   }
 
   const_iterator upper_bound(K l) const {
-    auto ret = begin();
-    for (; ret != end(); ++ret) {
-      if (ret->get_key() > l)
-	break;
-    }
-    return ret;
+    auto it = std::upper_bound(boost::make_counting_iterator<uint16_t>(0),
+	                       boost::make_counting_iterator<uint16_t>(get_size()),
+		               l,
+		               [this](K key, uint16_t i) {
+			         const_iterator iter(this, i);
+			         return key < iter->get_key();
+			       });
+    return const_iterator(this, *it);
   }
+
   iterator upper_bound(K l) {
     const auto &tref = *this;
     return iterator(this, tref.upper_bound(l).offset);
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 92ef56f464812..9948a4292fd98 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
@@ -559,20 +559,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<uint16_t>(0),
+                               boost::make_counting_iterator<uint16_t>(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) {
@@ -581,13 +575,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<uint16_t>(0),
+                               boost::make_counting_iterator<uint16_t>(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) {
-- 
2.39.5