Bug 1071489 - Make nsTArrays BinaryIndexOf use our unified binary search implementation. r=waldo
authorGeorg Fritzsche <georg.fritzsche@googlemail.com>
Tue, 23 Sep 2014 13:15:53 +0200
changeset 222489 6c5cf0e394adf47d7a578c425510aa6bb42fa306
parent 222488 587112ab2e73c3a67477c723261b1308eb47121a
child 222490 d6710f2fc838d71df51db08ae231fe08ce176509
push id7107
push userraliiev@mozilla.com
push dateMon, 13 Oct 2014 17:43:31 +0000
treeherdermozilla-aurora@b4b34e0acc75 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs1071489
milestone35.0a1
Bug 1071489 - Make nsTArrays BinaryIndexOf use our unified binary search implementation. r=waldo
xpcom/glue/nsTArray.h
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -696,21 +696,40 @@ struct nsTArray_TypedBase<JS::Heap<E>, D
     Derived* self = static_cast<Derived*>(this);
     return *reinterpret_cast<FallibleTArray<E> *>(self);
   }
 };
 
 namespace detail {
 
 template<class Item, class Comparator>
-struct ItemComparator
+struct ItemComparatorEq
 {
   const Item& mItem;
   const Comparator& mComp;
-  ItemComparator(const Item& aItem, const Comparator& aComp)
+  ItemComparatorEq(const Item& aItem, const Comparator& aComp)
+    : mItem(aItem)
+    , mComp(aComp)
+  {}
+  template<class T>
+  int operator()(const T& aElement) const {
+    if (mComp.Equals(aElement, mItem)) {
+      return 0;
+    }
+
+    return mComp.LessThan(aElement, mItem) ? 1 : -1;
+  }
+};
+
+template<class Item, class Comparator>
+struct ItemComparatorFirstElementGT
+{
+  const Item& mItem;
+  const Comparator& mComp;
+  ItemComparatorFirstElementGT(const Item& aItem, const Comparator& aComp)
     : mItem(aItem)
     , mComp(aComp)
   {}
   template<class T>
   int operator()(const T& aElement) const {
     if (mComp.LessThan(aElement, mItem) ||
         mComp.Equals(aElement, mItem)) {
       return 1;
@@ -1060,35 +1079,30 @@ public:
   index_type LastIndexOf(const Item& aItem,
                          index_type aStart = NoIndex) const
   {
     return LastIndexOf(aItem, aStart, nsDefaultComparator<elem_type, Item>());
   }
 
   // This method searches for the offset for the element in this array
   // that is equal to the given element. The array is assumed to be sorted.
+  // If there is more than one equivalent element, there is no guarantee
+  // on which one will be returned.
   // @param aItem  The item to search for.
   // @param aComp  The Comparator used.
   // @return       The index of the found element or NoIndex if not found.
   template<class Item, class Comparator>
   index_type BinaryIndexOf(const Item& aItem, const Comparator& aComp) const
   {
-    index_type low = 0, high = Length();
-    while (high > low) {
-      index_type mid = (high + low) >> 1;
-      if (aComp.Equals(ElementAt(mid), aItem)) {
-        return mid;
-      }
-      if (aComp.LessThan(ElementAt(mid), aItem)) {
-        low = mid + 1;
-      } else {
-        high = mid;
-      }
-    }
-    return NoIndex;
+    using mozilla::BinarySearchIf;
+    typedef ::detail::ItemComparatorEq<Item, Comparator> Cmp;
+
+    size_t index;
+    bool found = BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index);
+    return found ? index : NoIndex;
   }
 
   // This method searches for the offset for the element in this array
   // that is equal to the given element. The array is assumed to be sorted.
   // This method assumes that 'operator==' and 'operator<' are defined.
   // @param aItem  The item to search for.
   // @return       The index of the found element or NoIndex if not found.
   template<class Item>
@@ -1246,17 +1260,17 @@ public:
   // @param aComp  The Comparator used.
   // @return        The index of greatest element <= to |aItem|
   // @precondition The array is sorted
   template<class Item, class Comparator>
   index_type IndexOfFirstElementGt(const Item& aItem,
                                    const Comparator& aComp) const
   {
     using mozilla::BinarySearchIf;
-    typedef ::detail::ItemComparator<Item, Comparator> Cmp;
+    typedef ::detail::ItemComparatorFirstElementGT<Item, Comparator> Cmp;
 
     size_t index;
     BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index);
     return index;
   }
 
   // A variation on the IndexOfFirstElementGt method defined above.
   template<class Item>