From 30d51abea16ec7e7450cfb46a561e4c50193e870 Mon Sep 17 00:00:00 2001
From: "yurys@chromium.org"
 <yurys@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Tue, 10 Apr 2012 11:24:09 +0000
Subject: [PATCH] Use SortedListBSearch instead of custom one in heap profiler
 Review URL: https://chromiumcodereview.appspot.com/10006032

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@11252 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/list-inl.h           | 23 +++++++++++++++++------
 src/list.h               |  8 +++++---
 src/profile-generator.cc | 31 ++++++++++++++++---------------
 3 files changed, 38 insertions(+), 24 deletions(-)

diff --git a/src/list-inl.h b/src/list-inl.h
index 7c2c83f0f..35ee3f5e8 100644
--- a/src/list-inl.h
+++ b/src/list-inl.h
@@ -207,20 +207,19 @@ void List<T, P>::Initialize(int capacity) {
 }
 
 
-template <typename T>
-int SortedListBSearch(
-    const List<T>& list, T elem, int (*cmp)(const T* x, const T* y)) {
+template <typename T, typename P>
+int SortedListBSearch(const List<T>& list, P cmp) {
   int low = 0;
   int high = list.length() - 1;
   while (low <= high) {
     int mid = (low + high) / 2;
     T mid_elem = list[mid];
 
-    if (cmp(&mid_elem, &elem) > 0) {
+    if (cmp(&mid_elem) > 0) {
       high = mid - 1;
       continue;
     }
-    if (cmp(&mid_elem, &elem) < 0) {
+    if (cmp(&mid_elem) < 0) {
       low = mid + 1;
       continue;
     }
@@ -231,9 +230,21 @@ int SortedListBSearch(
 }
 
 
+template<typename T>
+class ElementCmp {
+ public:
+  explicit ElementCmp(T e) : elem_(e) {}
+  int operator()(const T* other) {
+    return PointerValueCompare(other, &elem_);
+  }
+ private:
+  T elem_;
+};
+
+
 template <typename T>
 int SortedListBSearch(const List<T>& list, T elem) {
-  return SortedListBSearch<T>(list, elem, PointerValueCompare<T>);
+  return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
 }
 
 
diff --git a/src/list.h b/src/list.h
index adddea41f..a210dfb1b 100644
--- a/src/list.h
+++ b/src/list.h
@@ -173,9 +173,11 @@ typedef List<Handle<Code> > CodeHandleList;
 
 // Perform binary search for an element in an already sorted
 // list. Returns the index of the element of -1 if it was not found.
-template <typename T>
-int SortedListBSearch(
-    const List<T>& list, T elem, int (*cmp)(const T* x, const T* y));
+// |cmp| is a predicate that takes a pointer to an element of the List
+// and returns +1 if it is greater, -1 if it is less than the element
+// being searched.
+template <typename T, class P>
+int SortedListBSearch(const List<T>& list, P cmp);
 template <typename T>
 int SortedListBSearch(const List<T>& list, T elem);
 
diff --git a/src/profile-generator.cc b/src/profile-generator.cc
index e895cccdf..be9c5d7dd 100644
--- a/src/profile-generator.cc
+++ b/src/profile-generator.cc
@@ -1256,24 +1256,25 @@ HeapEntry* HeapSnapshot::GetNextEntryToInit() {
 }
 
 
+class FindEntryById {
+ public:
+  explicit FindEntryById(SnapshotObjectId id) : id_(id) { }
+  int operator()(HeapEntry* const* entry) {
+    if ((*entry)->id() == id_) return 0;
+    return (*entry)->id() < id_ ? -1 : 1;
+  }
+ private:
+  SnapshotObjectId id_;
+};
+
+
 HeapEntry* HeapSnapshot::GetEntryById(SnapshotObjectId id) {
   List<HeapEntry*>* entries_by_id = GetSortedEntriesList();
-
   // Perform a binary search by id.
-  int low = 0;
-  int high = entries_by_id->length() - 1;
-  while (low <= high) {
-    int mid =
-        (static_cast<unsigned int>(low) + static_cast<unsigned int>(high)) >> 1;
-    SnapshotObjectId mid_id = entries_by_id->at(mid)->id();
-    if (mid_id > id)
-      high = mid - 1;
-    else if (mid_id < id)
-      low = mid + 1;
-    else
-      return entries_by_id->at(mid);
-  }
-  return NULL;
+  int index = SortedListBSearch(*entries_by_id, FindEntryById(id));
+  if (index == -1)
+    return NULL;
+  return entries_by_id->at(index);
 }
 
 
-- 
2.34.1