[sanitizer] Add a fast version of StackDepotGet() for use in LSan.

Add a class that holds a snapshot of the StackDepot optimized for querying by
ID. This allows us to speed up LSan dramatically.

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@189217 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 16 insertions, 0 deletions

diff --git a/lib/sanitizer_common/sanitizer_common.h b/lib/sanitizer_common/sanitizer_common.h
index 908d11d0e..512e8f6b7 100644
--- a/lib/sanitizer_common/sanitizer_common.h
+++ b/lib/sanitizer_common/sanitizer_common.h
@@ -380,6 +380,22 @@ void InternalSort(Container *v, uptr size, Compare comp) {
   }
 }
 
+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) {
+    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;
+  }
+  return not_found;
+}
+
 }  // namespace __sanitizer
 
 #endif  // SANITIZER_COMMON_H