rename InternalBinarySearch to InternalLowerBound

[aizatsky]

Summary

The new name better corresponds to its logic.

[kcc]

Thanks!

lib/sanitizer_common/sanitizer_common.h

for (j = 0; j < i; j = max_ind) {
       else
         break;
     }
   }
 }
 
 // Works like std::lower_bound: finds the first element that is not less
 // than the val.
-template<class Container, class Value, class Compare>
-uptr InternalBinarySearch(const Container &v, uptr first, uptr last,
-                          const Value &val, Compare comp) {
+template <class Container, class Value, class Compare>
+uptr InternalLowerBound(const Container &v, uptr first, uptr last,
   while (last > first) {
     uptr mid = (first + last) / 2;
     if (comp(v[mid], val))
       first = mid + 1;
     else
       last = mid;
   }
   return first;

lib/sanitizer_common/sanitizer_stackdepot.cc

StackDepotReverseMap::StackDepotReverseMap()
   }
   InternalSort(&map_, map_.size(), IdDescPair::IdComparator);
 }
 
 StackTrace StackDepotReverseMap::Get(u32 id) {
   if (!map_.size())
     return StackTrace();
   IdDescPair pair = {id, nullptr};
-  uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair,
-                                  IdDescPair::IdComparator);
+  uptr idx =
+      InternalLowerBound(map_, 0, map_.size(), pair, IdDescPair::IdComparator);
   if (idx > map_.size() || map_[idx].id != id)
     return StackTrace();
   return map_[idx].desc->load();
 }
 
 } // namespace __sanitizer

lib/sanitizer_common/tests/sanitizer_common_test.cc

TEST(SanitizerCommon, ThreadStackTlsWorker) {
   PTHREAD_CREATE(&t, 0, WorkerThread, 0);
   PTHREAD_JOIN(t, 0);
 }
 
 bool UptrLess(uptr a, uptr b) {
   return a < b;
 }
 
-TEST(SanitizerCommon, InternalBinarySearch) {
+TEST(SanitizerCommon, InternalLowerBound) {
   static const uptr kSize = 5;
   int arr[kSize];
   arr[0] = 1;
   arr[1] = 3;
   arr[2] = 5;
   arr[3] = 7;
   arr[4] = 11;
 
-  EXPECT_EQ(0u, InternalBinarySearch(arr, 0, kSize, 0, UptrLess));
-  EXPECT_EQ(0u, InternalBinarySearch(arr, 0, kSize, 1, UptrLess));
-  EXPECT_EQ(1u, InternalBinarySearch(arr, 0, kSize, 2, UptrLess));
-  EXPECT_EQ(1u, InternalBinarySearch(arr, 0, kSize, 3, UptrLess));
-  EXPECT_EQ(2u, InternalBinarySearch(arr, 0, kSize, 4, UptrLess));
-  EXPECT_EQ(2u, InternalBinarySearch(arr, 0, kSize, 5, UptrLess));
-  EXPECT_EQ(3u, InternalBinarySearch(arr, 0, kSize, 6, UptrLess));
-  EXPECT_EQ(3u, InternalBinarySearch(arr, 0, kSize, 7, UptrLess));
-  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 8, UptrLess));
-  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 9, UptrLess));
-  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 10, UptrLess));
-  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 11, UptrLess));
-  EXPECT_EQ(5u, InternalBinarySearch(arr, 0, kSize, 12, UptrLess));
+  EXPECT_EQ(0u, InternalLowerBound(arr, 0, kSize, 0, UptrLess));
+  EXPECT_EQ(0u, InternalLowerBound(arr, 0, kSize, 1, UptrLess));
+  EXPECT_EQ(1u, InternalLowerBound(arr, 0, kSize, 2, UptrLess));
+  EXPECT_EQ(1u, InternalLowerBound(arr, 0, kSize, 3, UptrLess));
+  EXPECT_EQ(2u, InternalLowerBound(arr, 0, kSize, 4, UptrLess));
+  EXPECT_EQ(2u, InternalLowerBound(arr, 0, kSize, 5, UptrLess));
+  EXPECT_EQ(3u, InternalLowerBound(arr, 0, kSize, 6, UptrLess));
+  EXPECT_EQ(3u, InternalLowerBound(arr, 0, kSize, 7, UptrLess));
+  EXPECT_EQ(4u, InternalLowerBound(arr, 0, kSize, 8, UptrLess));
+  EXPECT_EQ(4u, InternalLowerBound(arr, 0, kSize, 9, UptrLess));
+  EXPECT_EQ(4u, InternalLowerBound(arr, 0, kSize, 10, UptrLess));
+  EXPECT_EQ(4u, InternalLowerBound(arr, 0, kSize, 11, UptrLess));
+  EXPECT_EQ(5u, InternalLowerBound(arr, 0, kSize, 12, UptrLess));
 }
 
-TEST(SanitizerCommon, InternalBinarySearchVsLowerBound) {
+TEST(SanitizerCommon, InternalLowerBoundVsStdLowerBound) {
   std::vector<int> data;
   auto create_item = [] (size_t i, size_t j) {
     auto v = i * 10000 + j;
     return ((v << 6) + (v >> 6) + 0x9e3779b9) % 100;
   };
   for (size_t i = 0; i < 1000; ++i) {
     data.resize(i);
     for (size_t j = 0; j < i; ++j) {
       data[j] = create_item(i, j);
     }
 
     std::sort(data.begin(), data.end());
 
     for (size_t j = 0; j < i; ++j) {
       int val = create_item(i, j);
       for (auto to_find : {val - 1, val, val + 1}) {
         uptr expected =
             std::lower_bound(data.begin(), data.end(), to_find) - data.begin();
-        EXPECT_EQ(expected, InternalBinarySearch(data.data(), 0, data.size(),
-                                                 to_find, std::less<int>()));
+        EXPECT_EQ(expected, InternalLowerBound(data.data(), 0, data.size(),
       }
     }
   }
 }
 
 #if SANITIZER_LINUX && !SANITIZER_ANDROID
 TEST(SanitizerCommon, FindPathToBinary) {
   char *true_path = FindPathToBinary("true");