fixing binary search for cases when element is not in array

[vitalybuka]

Maybe:

TEST(SanitizerCommon, InternalBinarySearchVsLowerBound) {
  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>()));
      }
    }
  }
}

[aizatsky]

Added, the test. Thanks.

compiler-rt/trunk/lib/sanitizer_common/sanitizer_common.h

for (j = 0; j < i; j = max_ind) {
       if (max_ind != j)
         Swap((*v)[j], (*v)[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) {
-  uptr not_found = last + 1;
-  while (last >= first) {
+  while (last > first) {
     uptr mid = (first + last) / 2;
     if (comp(v[mid], val))
       first = mid + 1;
-    else if (comp(val, v[mid]))
-      last = mid - 1;
     else
-      return mid;
+      last = mid;
   }
-  return not_found;
+  return first;
 }
 
 // Represents a binary loaded into virtual memory (e.g. this can be an
 // executable or a shared object).
 class LoadedModule {
  public:
   LoadedModule() : full_name_(nullptr), base_address_(0) { ranges_.clear(); }
   void set(const char *module_name, uptr base_address);

compiler-rt/trunk/lib/sanitizer_common/sanitizer_stackdepot.cc

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

compiler-rt/trunk/lib/sanitizer_common/tests/sanitizer_common_test.cc

 //===-- sanitizer_common_test.cc ------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file is a part of ThreadSanitizer/AddressSanitizer runtime.
 //
 //===----------------------------------------------------------------------===//
+#include <algorithm>
+
 #include "sanitizer_common/sanitizer_allocator_internal.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_flags.h"
 #include "sanitizer_common/sanitizer_libc.h"
 #include "sanitizer_common/sanitizer_platform.h"
 
 #include "sanitizer_pthread_wrappers.h"
 

 }
 
 bool UptrLess(uptr a, uptr b) {
   return a < b;
 }
 
 TEST(SanitizerCommon, InternalBinarySearch) {
   static const uptr kSize = 5;
-  uptr arr[kSize];
-  for (uptr i = 0; i < kSize; i++) arr[i] = i * i;
-
-  for (uptr i = 0; i < kSize; i++)
-    ASSERT_EQ(InternalBinarySearch(arr, 0, kSize, i * i, UptrLess), i);
+  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));
+}
+
+TEST(SanitizerCommon, InternalBinarySearchVsLowerBound) {
+  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);
+    }
 
-  ASSERT_EQ(InternalBinarySearch(arr, 0, kSize, 7, UptrLess), kSize + 1);
+    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>()));
+      }
+    }
+  }
 }
 
 #if SANITIZER_LINUX && !SANITIZER_ANDROID
 TEST(SanitizerCommon, FindPathToBinary) {
   char *true_path = FindPathToBinary("true");
   EXPECT_NE((char*)0, internal_strstr(true_path, "/bin/true"));
   InternalFree(true_path);
   EXPECT_EQ(0, FindPathToBinary("unexisting_binary.ergjeorj"));