Bug 1067989 - Unify some more binary search uses. r=waldo
authorGeorg Fritzsche <georg.fritzsche@googlemail.com>
Wed, 17 Sep 2014 15:46:24 +0200
changeset 206916 c984a4104674183ded2ca834f9bdb30d7d857247
parent 206915 28f303a138f1770f3619a87a18e18249a423c087
child 206917 a63b9ceeb754868a58dfb6c7794f87376c38b77e
push id8970
push userryanvm@gmail.com
push dateWed, 24 Sep 2014 21:13:34 +0000
treeherderfx-team@ea2894eea2d0 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs1067989
milestone35.0a1
Bug 1067989 - Unify some more binary search uses. r=waldo
accessible/base/ARIAMap.cpp
accessible/generic/HyperTextAccessible.cpp
content/base/src/nsDocument.cpp
content/base/src/nsPlainTextSerializer.cpp
content/html/content/src/HTMLFormElement.cpp
content/xul/templates/src/nsXULTreeBuilder.cpp
extensions/spellcheck/src/mozInlineSpellWordUtil.cpp
gfx/thebes/gfxFont.cpp
gfx/thebes/gfxFontUtils.cpp
gfx/thebes/gfxFontUtils.h
gfx/thebes/gfxMathTable.cpp
gfx/thebes/gfxSkipChars.cpp
gfx/thebes/gfxSkipChars.h
intl/locale/nsUConvPropertySearch.cpp
intl/unicharutil/nsUnicodeNormalizer.cpp
layout/generic/MathMLTextRunFactory.cpp
layout/generic/nsTextFrame.cpp
parser/html/jArray.h
parser/htmlparser/nsParser.cpp
xpcom/glue/nsTArray.h
xpcom/threads/TimerThread.cpp
--- a/accessible/base/ARIAMap.cpp
+++ b/accessible/base/ARIAMap.cpp
@@ -10,16 +10,18 @@
 #include "nsAccUtils.h"
 #include "nsCoreUtils.h"
 #include "Role.h"
 #include "States.h"
 
 #include "nsAttrName.h"
 #include "nsWhitespaceTokenizer.h"
 
+#include "mozilla/BinarySearch.h"
+
 using namespace mozilla;
 using namespace mozilla::a11y;
 using namespace mozilla::a11y::aria;
 
 static const uint32_t kGenericAccType = 0;
 
 /**
  *  This list of WAI-defined roles are currently hardcoded.
@@ -727,44 +729,49 @@ static const AttrCharacteristics gWAIUni
   {&nsGkAtoms::aria_setsize,           ATTR_BYPASSOBJ                               }, /* handled via groupPosition */
   {&nsGkAtoms::aria_sort,                               ATTR_VALTOKEN               },
   {&nsGkAtoms::aria_valuenow,          ATTR_BYPASSOBJ                               },
   {&nsGkAtoms::aria_valuemin,          ATTR_BYPASSOBJ                               },
   {&nsGkAtoms::aria_valuemax,          ATTR_BYPASSOBJ                               },
   {&nsGkAtoms::aria_valuetext,         ATTR_BYPASSOBJ                               }
 };
 
+namespace {
+
+struct RoleComparator
+{
+  const nsDependentSubstring& mRole;
+  RoleComparator(const nsDependentSubstring& aRole) : mRole(aRole) {}
+  int operator()(const nsRoleMapEntry& aEntry) const {
+    return Compare(mRole, aEntry.ARIARoleString());
+  }
+};
+
+}
+
 nsRoleMapEntry*
 aria::GetRoleMap(nsINode* aNode)
 {
   nsIContent* content = nsCoreUtils::GetRoleContent(aNode);
   nsAutoString roles;
   if (!content ||
       !content->GetAttr(kNameSpaceID_None, nsGkAtoms::role, roles) ||
       roles.IsEmpty()) {
     // We treat role="" as if the role attribute is absent (per aria spec:8.1.1)
     return nullptr;
   }
 
   nsWhitespaceTokenizer tokenizer(roles);
   while (tokenizer.hasMoreTokens()) {
     // Do a binary search through table for the next role in role list
     const nsDependentSubstring role = tokenizer.nextToken();
-    uint32_t low = 0;
-    uint32_t high = ArrayLength(sWAIRoleMaps);
-    while (low < high) {
-      uint32_t idx = (low + high) / 2;
-      int32_t compare = Compare(role, sWAIRoleMaps[idx].ARIARoleString());
-      if (compare == 0)
-        return sWAIRoleMaps + idx;
-
-      if (compare < 0)
-        high = idx;
-      else
-        low = idx + 1;
+    size_t idx;
+    if (BinarySearchIf(sWAIRoleMaps, 0, ArrayLength(sWAIRoleMaps),
+                       RoleComparator(role), &idx)) {
+      return sWAIRoleMaps + idx;
     }
   }
 
   // Always use some entry if there is a non-empty role string
   // To ensure an accessible object is created
   return &sLandmarkRoleMap;
 }
 
--- a/accessible/generic/HyperTextAccessible.cpp
+++ b/accessible/generic/HyperTextAccessible.cpp
@@ -26,16 +26,17 @@
 #include "nsFrameSelection.h"
 #include "nsILineIterator.h"
 #include "nsIInterfaceRequestorUtils.h"
 #include "nsIPersistentProperties2.h"
 #include "nsIScrollableFrame.h"
 #include "nsIServiceManager.h"
 #include "nsITextControlElement.h"
 #include "nsTextFragment.h"
+#include "mozilla/BinarySearch.h"
 #include "mozilla/dom/Element.h"
 #include "mozilla/EventStates.h"
 #include "mozilla/dom/Selection.h"
 #include "mozilla/MathAlgorithms.h"
 #include "gfxSkipChars.h"
 #include <algorithm>
 
 using namespace mozilla;
@@ -1846,35 +1847,27 @@ HyperTextAccessible::GetChildOffset(uint
 
   return mOffsets[aChildIndex - 1];
 }
 
 int32_t
 HyperTextAccessible::GetChildIndexAtOffset(uint32_t aOffset) const
 {
   uint32_t lastOffset = 0;
-  uint32_t offsetCount = mOffsets.Length();
+  const uint32_t offsetCount = mOffsets.Length();
+
   if (offsetCount > 0) {
     lastOffset = mOffsets[offsetCount - 1];
     if (aOffset < lastOffset) {
-      uint32_t low = 0, high = offsetCount;
-      while (high > low) {
-        uint32_t mid = (high + low) >> 1;
-        if (mOffsets[mid] == aOffset)
-          return mid < offsetCount - 1 ? mid + 1 : mid;
+      size_t index;
+      if (BinarySearch(mOffsets, 0, offsetCount, aOffset, &index)) {
+        return (index < (offsetCount - 1)) ? index + 1 : index;
+      }
 
-        if (mOffsets[mid] < aOffset)
-          low = mid + 1;
-        else
-          high = mid;
-      }
-      if (high == offsetCount)
-        return -1;
-
-      return low;
+      return (index == offsetCount) ? -1 : index;
     }
   }
 
   uint32_t childCount = ChildCount();
   while (mOffsets.Length() < childCount) {
     Accessible* child = GetChildAt(mOffsets.Length());
     lastOffset += nsAccUtils::TextLength(child);
     mOffsets.AppendElement(lastOffset);
--- a/content/base/src/nsDocument.cpp
+++ b/content/base/src/nsDocument.cpp
@@ -7,16 +7,17 @@
 /*
  * Base class for all our document implementations.
  */
 
 #include "nsDocument.h"
 
 #include "mozilla/ArrayUtils.h"
 #include "mozilla/AutoRestore.h"
+#include "mozilla/BinarySearch.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Likely.h"
 #include <algorithm>
 
 #ifdef MOZ_LOGGING
 // so we can get logging even in release builds
 #define FORCE_PR_LOG 1
@@ -544,16 +545,36 @@ nsIdentifierMapEntry::FireChangeCallback
 {
   if (!mChangeCallbacks)
     return;
 
   FireChangeArgs args = { aOldElement, aNewElement, aImageOnly, !!mImageElement };
   mChangeCallbacks->EnumerateEntries(FireChangeEnumerator, &args);
 }
 
+namespace {
+
+struct PositionComparator
+{
+  Element* const mElement;
+  PositionComparator(Element* const aElement) : mElement(aElement) {}
+
+  int operator()(void* aElement) const {
+    Element* curElement = static_cast<Element*>(aElement);
+    if (mElement == curElement) {
+      return 0;
+    }
+    if (nsContentUtils::PositionIsBefore(mElement, curElement)) {
+      return -1;
+    }
+    return 1;
+  }
+};
+} // namespace
+
 bool
 nsIdentifierMapEntry::AddIdElement(Element* aElement)
 {
   NS_PRECONDITION(aElement, "Must have element");
   NS_PRECONDITION(mIdContentList.IndexOf(nullptr) < 0,
                   "Why is null in our list?");
 
 #ifdef DEBUG
@@ -567,43 +588,30 @@ nsIdentifierMapEntry::AddIdElement(Eleme
       return false;
     NS_ASSERTION(currentElement == nullptr, "How did that happen?");
     FireChangeCallbacks(nullptr, aElement);
     return true;
   }
 
   // We seem to have multiple content nodes for the same id, or XUL is messing
   // with us.  Search for the right place to insert the content.
-  int32_t start = 0;
-  int32_t end = mIdContentList.Count();
-  do {
-    NS_ASSERTION(start < end, "Bogus start/end");
-
-    int32_t cur = (start + end) / 2;
-    NS_ASSERTION(cur >= start && cur < end, "What happened here?");
-
-    Element* curElement = static_cast<Element*>(mIdContentList[cur]);
-    if (curElement == aElement) {
-      // Already in the list, so already in the right spot.  Get out of here.
-      // XXXbz this only happens because XUL does all sorts of random
-      // UpdateIdTableEntry calls.  Hate, hate, hate!
-      return true;
-    }
-
-    if (nsContentUtils::PositionIsBefore(aElement, curElement)) {
-      end = cur;
-    } else {
-      start = cur + 1;
-    }
-  } while (start != end);
-
-  if (!mIdContentList.InsertElementAt(aElement, start))
+
+  size_t idx;
+  if (BinarySearchIf(mIdContentList, 0, mIdContentList.Count(),
+                     PositionComparator(aElement), &idx)) {
+    // Already in the list, so already in the right spot.  Get out of here.
+    // XXXbz this only happens because XUL does all sorts of random
+    // UpdateIdTableEntry calls.  Hate, hate, hate!
+    return true;
+  }
+
+  if (!mIdContentList.InsertElementAt(aElement, idx))
     return false;
 
-  if (start == 0) {
+  if (idx == 0) {
     Element* oldElement =
       static_cast<Element*>(mIdContentList.SafeElementAt(1));
     NS_ASSERTION(currentElement == oldElement, "How did that happen?");
     FireChangeCallbacks(oldElement, aElement);
   }
   return true;
 }
 
--- a/content/base/src/nsPlainTextSerializer.cpp
+++ b/content/base/src/nsPlainTextSerializer.cpp
@@ -16,16 +16,17 @@
 #include "nsNameSpaceManager.h"
 #include "nsTextFragment.h"
 #include "nsContentUtils.h"
 #include "nsReadableUtils.h"
 #include "nsUnicharUtils.h"
 #include "nsCRT.h"
 #include "mozilla/dom/Element.h"
 #include "mozilla/Preferences.h"
+#include "mozilla/BinarySearch.h"
 
 using namespace mozilla;
 using namespace mozilla::dom;
 
 #define PREF_STRUCTS "converter.html2txt.structs"
 #define PREF_HEADER_STRATEGY "converter.html2txt.header_strategy"
 
 static const  int32_t kTabSize=4;
@@ -1856,23 +1857,46 @@ int32_t HeaderLevel(nsIAtom* aTag)
  *    - All remaining characters (including all printable
  *      ISO 8859-1 and WGL4 characters, Unicode control characters,
  *      etc.) have a column width of 1.
  *
  * This implementation assumes that wchar_t characters are encoded
  * in ISO 10646.
  */
 
+namespace {
+
+struct interval
+{
+  uint16_t first;
+  uint16_t last;
+};
+
+struct CombiningComparator
+{
+  const char16_t mUcs;
+  CombiningComparator(char16_t ucs) : mUcs(ucs) {}
+  int operator()(const interval& combining) const {
+    if (mUcs > combining.last)
+      return 1;
+    if (mUcs < combining.first)
+      return -1;
+
+    MOZ_ASSERT(combining.first <= mUcs);
+    MOZ_ASSERT(mUcs <= combining.last);
+    return 0;
+  }
+};
+
+} // namespace
+
 int32_t GetUnicharWidth(char16_t ucs)
 {
   /* sorted list of non-overlapping intervals of non-spacing characters */
-  static const struct interval {
-    uint16_t first;
-    uint16_t last;
-  } combining[] = {
+  static const interval combining[] = {
     { 0x0300, 0x034E }, { 0x0360, 0x0362 }, { 0x0483, 0x0486 },
     { 0x0488, 0x0489 }, { 0x0591, 0x05A1 }, { 0x05A3, 0x05B9 },
     { 0x05BB, 0x05BD }, { 0x05BF, 0x05BF }, { 0x05C1, 0x05C2 },
     { 0x05C4, 0x05C4 }, { 0x064B, 0x0655 }, { 0x0670, 0x0670 },
     { 0x06D6, 0x06E4 }, { 0x06E7, 0x06E8 }, { 0x06EA, 0x06ED },
     { 0x0711, 0x0711 }, { 0x0730, 0x074A }, { 0x07A6, 0x07B0 },
     { 0x0901, 0x0902 }, { 0x093C, 0x093C }, { 0x0941, 0x0948 },
     { 0x094D, 0x094D }, { 0x0951, 0x0954 }, { 0x0962, 0x0963 },
@@ -1895,39 +1919,32 @@ int32_t GetUnicharWidth(char16_t ucs)
     { 0x0F71, 0x0F7E }, { 0x0F80, 0x0F84 }, { 0x0F86, 0x0F87 },
     { 0x0F90, 0x0F97 }, { 0x0F99, 0x0FBC }, { 0x0FC6, 0x0FC6 },
     { 0x102D, 0x1030 }, { 0x1032, 0x1032 }, { 0x1036, 0x1037 },
     { 0x1039, 0x1039 }, { 0x1058, 0x1059 }, { 0x17B7, 0x17BD },
     { 0x17C6, 0x17C6 }, { 0x17C9, 0x17D3 }, { 0x18A9, 0x18A9 },
     { 0x20D0, 0x20E3 }, { 0x302A, 0x302F }, { 0x3099, 0x309A },
     { 0xFB1E, 0xFB1E }, { 0xFE20, 0xFE23 }
   };
-  int32_t min = 0;
-  int32_t max = sizeof(combining) / sizeof(struct interval) - 1;
-  int32_t mid;
 
   /* test for 8-bit control characters */
   if (ucs == 0)
     return 0;
   if (ucs < 32 || (ucs >= 0x7f && ucs < 0xa0))
     return -1;
 
   /* first quick check for Latin-1 etc. characters */
   if (ucs < combining[0].first)
     return 1;
 
   /* binary search in table of non-spacing characters */
-  while (max >= min) {
-    mid = (min + max) / 2;
-    if (combining[mid].last < ucs)
-      min = mid + 1;
-    else if (combining[mid].first > ucs)
-      max = mid - 1;
-    else if (combining[mid].first <= ucs && combining[mid].last >= ucs)
-      return 0;
+  size_t idx;
+  if (BinarySearchIf(combining, 0, ArrayLength(combining),
+                     CombiningComparator(ucs), &idx)) {
+    return 0;
   }
 
   /* if we arrive here, ucs is not a combining or C0/C1 control character */
 
   /* fast test for majority of non-wide scripts */
   if (ucs < 0x1100)
     return 1;
 
--- a/content/html/content/src/HTMLFormElement.cpp
+++ b/content/html/content/src/HTMLFormElement.cpp
@@ -25,16 +25,17 @@
 #include "nsContentUtils.h"
 #include "nsInterfaceHashtable.h"
 #include "nsContentList.h"
 #include "nsCOMArray.h"
 #include "nsAutoPtr.h"
 #include "nsTArray.h"
 #include "nsIMutableArray.h"
 #include "nsIFormAutofillContentService.h"
+#include "mozilla/BinarySearch.h"
 
 // form submission
 #include "nsIFormSubmitObserver.h"
 #include "nsIObserverService.h"
 #include "nsICategoryManager.h"
 #include "nsCategoryManagerUtils.h"
 #include "nsISimpleEnumerator.h"
 #include "nsRange.h"
@@ -1066,27 +1067,42 @@ HTMLFormElement::PostPasswordEvent()
   }
 
   mFormPasswordEventDispatcher =
     new FormPasswordEventDispatcher(this,
                                     NS_LITERAL_STRING("DOMFormHasPassword"));
   mFormPasswordEventDispatcher->PostDOMEvent();
 }
 
+namespace {
+
+struct FormComparator
+{
+  Element* const mChild;
+  HTMLFormElement* const mForm;
+  FormComparator(Element* aChild, HTMLFormElement* aForm)
+    : mChild(aChild), mForm(aForm) {}
+  int operator()(Element* aElement) const {
+    return HTMLFormElement::CompareFormControlPosition(mChild, aElement, mForm);
+  }
+};
+
+} // namespace
+
 // This function return true if the element, once appended, is the last one in
 // the array.
 template<typename ElementType>
 static bool
 AddElementToList(nsTArray<ElementType*>& aList, ElementType* aChild,
                  HTMLFormElement* aForm)
 {
   NS_ASSERTION(aList.IndexOf(aChild) == aList.NoIndex,
                "aChild already in aList");
 
-  uint32_t count = aList.Length();
+  const uint32_t count = aList.Length();
   ElementType* element;
   bool lastElement = false;
 
   // Optimize most common case where we insert at the end.
   int32_t position = -1;
   if (count > 0) {
     element = aList[count - 1];
     position =
@@ -1097,33 +1113,21 @@ AddElementToList(nsTArray<ElementType*>&
   // empty, we append to the end. Otherwise, we do a binary search to
   // determine where the element should go.
   if (position >= 0 || count == 0) {
     // WEAK - don't addref
     aList.AppendElement(aChild);
     lastElement = true;
   }
   else {
-    int32_t low = 0, mid, high;
-    high = count - 1;
-
-    while (low <= high) {
-      mid = (low + high) / 2;
-
-      element = aList[mid];
-      position =
-        HTMLFormElement::CompareFormControlPosition(aChild, element, aForm);
-      if (position >= 0)
-        low = mid + 1;
-      else
-        high = mid - 1;
-    }
+    size_t idx;
+    BinarySearchIf(aList, 0, count, FormComparator(aChild, aForm), &idx);
 
     // WEAK - don't addref
-    aList.InsertElementAt(low, aChild);
+    aList.InsertElementAt(idx, aChild);
   }
 
   return lastElement;
 }
 
 nsresult
 HTMLFormElement::AddElement(nsGenericHTMLFormElement* aChild,
                             bool aUpdateValidity, bool aNotify)
@@ -2229,16 +2233,45 @@ HTMLFormElement::Clear()
   for (int32_t i = mImageElements.Length() - 1; i >= 0; i--) {
     mImageElements[i]->ClearForm(false);
   }
   mImageElements.Clear();
   mImageNameLookupTable.Clear();
   mPastNameLookupTable.Clear();
 }
 
+namespace {
+
+struct PositionComparator
+{
+  nsIContent* const mElement;
+  PositionComparator(nsIContent* const element) : mElement(element) {}
+
+  int operator()(nsIContent* aElement) const {
+    if (mElement == aElement) {
+      return 0;
+    }
+    if (nsContentUtils::PositionIsBefore(mElement, aElement)) {
+      return -1;
+    }
+    return 1;
+  }
+};
+
+struct NodeListAdaptor
+{
+  nsINodeList* const mList;
+  NodeListAdaptor(nsINodeList* aList) : mList(aList) {}
+  nsIContent* operator[](size_t aIdx) const {
+    return mList->Item(aIdx);
+  }
+};
+
+} // namespace
+
 nsresult
 HTMLFormElement::AddElementToTableInternal(
   nsInterfaceHashtable<nsStringHashKey,nsISupports>& aTable,
   nsIContent* aChild, const nsAString& aName)
 {
   nsCOMPtr<nsISupports> supports;
   aTable.Get(aName, getter_AddRefs(supports));
 
@@ -2300,34 +2333,23 @@ HTMLFormElement::AddElementToTableIntern
         return NS_OK;
       }
 
       // If a control has a name equal to its id, it could be in the
       // list already.
       if (list->IndexOf(aChild) != -1) {
         return NS_OK;
       }
-      
-      // first is the first possible insertion index, last is the last possible
-      // insertion index
-      uint32_t first = 0;
-      uint32_t last = list->Length() - 1;
-      uint32_t mid;
-      
-      // Stop when there is only one index in our range
-      while (last != first) {
-        mid = (first + last) / 2;
-          
-        if (nsContentUtils::PositionIsBefore(aChild, list->Item(mid)))
-          last = mid;
-        else
-          first = mid + 1;
-      }
 
-      list->InsertElementAt(aChild, first);
+      size_t idx;
+      DebugOnly<bool> found = BinarySearchIf(NodeListAdaptor(list), 0, list->Length(),
+                                             PositionComparator(aChild), &idx);
+      MOZ_ASSERT(!found, "should not have found an element");
+
+      list->InsertElementAt(aChild, idx);
     }
   }
 
   return NS_OK;
 }
 
 nsresult
 HTMLFormElement::AddImageElement(HTMLImageElement* aChild)
--- a/content/xul/templates/src/nsXULTreeBuilder.cpp
+++ b/content/xul/templates/src/nsXULTreeBuilder.cpp
@@ -26,16 +26,17 @@
 #include "nsIXULSortService.h"
 #include "nsTArray.h"
 #include "nsUnicharUtils.h"
 #include "nsNameSpaceManager.h"
 #include "nsDOMClassInfoID.h"
 #include "nsWhitespaceTokenizer.h"
 #include "nsTreeContentView.h"
 #include "nsIXULStore.h"
+#include "mozilla/BinarySearch.h"
 
 // For security check
 #include "nsIDocument.h"
 
 /**
  * A XUL template builder that serves as an tree view, allowing
  * (pretty much) arbitrary RDF to be presented in an tree.
  */
@@ -58,16 +59,18 @@ public:
 
     // nsIMutationObserver
     NS_DECL_NSIMUTATIONOBSERVER_NODEWILLBEDESTROYED
 
 protected:
     friend nsresult
     NS_NewXULTreeBuilder(nsISupports* aOuter, REFNSIID aIID, void** aResult);
 
+    friend struct ResultComparator;
+
     nsXULTreeBuilder();
     ~nsXULTreeBuilder();
 
     /**
      * Uninitialize the template builder
      */
     virtual void Uninit(bool aIsFinal);
 
@@ -1062,16 +1065,27 @@ nsXULTreeBuilder::GetInsertionLocations(
 
     nsTreeRows::iterator iter = mRows.FindByResource(container);
     if (iter == mRows.Last())
         return false;
 
     return (iter->mContainerState == nsTreeRows::eContainerState_Open);
 }
 
+struct ResultComparator
+{
+    nsXULTreeBuilder* const mTreebuilder;
+    nsIXULTemplateResult* const mResult;
+    ResultComparator(nsXULTreeBuilder* aTreebuilder, nsIXULTemplateResult* aResult)
+      : mTreebuilder(aTreebuilder), mResult(aResult) {}
+    int operator()(const nsTreeRows::Row& aSubtree) const {
+        return mTreebuilder->CompareResults(mResult, aSubtree.mMatch->mResult);
+    }
+};
+
 nsresult
 nsXULTreeBuilder::ReplaceMatch(nsIXULTemplateResult* aOldResult,
                                nsTemplateMatch* aNewMatch,
                                nsTemplateRule* aNewMatchRule,
                                void *aLocation)
 {
     if (! mBoxObject)
         return NS_OK;
@@ -1160,34 +1174,23 @@ nsXULTreeBuilder::ReplaceMatch(nsIXULTem
         else {
             parent = mRows.GetRoot();
         }
 
         if (parent) {
             // If we get here, then we're inserting into an open
             // container. By default, place the new element at the
             // end of the container
-            int32_t index = parent->Count();
+            size_t index = parent->Count();
 
             if (mSortVariable) {
-                // Figure out where to put the new element by doing an
-                // insertion sort.
-                int32_t left = 0;
-                int32_t right = index;
-
-                while (left < right) {
-                    index = (left + right) / 2;
-                    int32_t cmp = CompareResults((*parent)[index].mMatch->mResult, result);
-                    if (cmp < 0)
-                        left = ++index;
-                    else if (cmp > 0)
-                        right = index;
-                    else
-                        break;
-                }
+                // Figure out where to put the new element through
+                // binary search.
+                mozilla::BinarySearchIf(*parent, 0, parent->Count(),
+                                        ResultComparator(this, result), &index);
             }
 
             nsTreeRows::iterator iter =
                 mRows.InsertRowAt(aNewMatch, parent, index);
 
             mBoxObject->RowCountChanged(iter.GetRowIndex(), +1);
 
             // See if this newly added row is open; in which case,
--- a/extensions/spellcheck/src/mozInlineSpellWordUtil.cpp
+++ b/extensions/spellcheck/src/mozInlineSpellWordUtil.cpp
@@ -18,16 +18,17 @@
 #include "nsServiceManagerUtils.h"
 #include "nsIContent.h"
 #include "nsTextFragment.h"
 #include "mozilla/dom/Element.h"
 #include "nsRange.h"
 #include "nsContentUtils.h"
 #include "nsIFrame.h"
 #include <algorithm>
+#include "mozilla/BinarySearch.h"
 
 using namespace mozilla;
 
 // IsIgnorableCharacter
 //
 //    These characters are ones that we should ignore in input.
 
 inline bool IsIgnorableCharacter(char16_t ch)
@@ -653,115 +654,134 @@ mozInlineSpellWordUtil::MapDOMPositionTo
           offsetInContributedString <= map.mLength)
         return map.mSoftTextOffset + offsetInContributedString;
       return -1;
     }
   }
   return -1;
 }
 
+namespace {
+
+template<class T>
+class FirstLargerOffset
+{
+  int32_t mSoftTextOffset;
+
+public:
+  FirstLargerOffset(int32_t aSoftTextOffset) : mSoftTextOffset(aSoftTextOffset) {}
+  int operator()(const T& t) const {
+  // We want the first larger offset, so never return 0 (which would
+  // short-circuit evaluation before finding the last such offset).
+    return mSoftTextOffset < t.mSoftTextOffset ? -1 : 1;
+  }
+};
+
+template<class T>
+bool
+FindLastNongreaterOffset(const nsTArray<T>& aContainer, int32_t aSoftTextOffset, size_t* aIndex)
+{
+  if (aContainer.Length() == 0) {
+    return false;
+  }
+
+  BinarySearchIf(aContainer, 0, aContainer.Length(),
+                 FirstLargerOffset<T>(aSoftTextOffset), aIndex);
+  if (*aIndex > 0) {
+    // There was at least one mapping with offset <= aSoftTextOffset. Step back
+    // to find the last element with |mSoftTextOffset <= aSoftTextOffset|.
+    *aIndex -= 1;
+  } else {
+    // Every mapping had offset greater than aSoftTextOffset.
+    MOZ_ASSERT(aContainer[*aIndex].mSoftTextOffset > aSoftTextOffset);
+  }
+  return true;
+}
+
+} // namespace
+
 mozInlineSpellWordUtil::NodeOffset
 mozInlineSpellWordUtil::MapSoftTextOffsetToDOMPosition(int32_t aSoftTextOffset,
                                                        DOMMapHint aHint)
 {
   NS_ASSERTION(mSoftTextValid, "Soft text must be valid if we're to map out of it");
   if (!mSoftTextValid)
     return NodeOffset(nullptr, -1);
-  
-  // The invariant is that the range start..end includes the last mapping,
-  // if any, such that mSoftTextOffset <= aSoftTextOffset
-  int32_t start = 0;
-  int32_t end = mSoftTextDOMMapping.Length();
-  while (end - start >= 2) {
-    int32_t mid = (start + end)/2;
-    const DOMTextMapping& map = mSoftTextDOMMapping[mid];
-    if (map.mSoftTextOffset > aSoftTextOffset) {
-      end = mid;
-    } else {
-      start = mid;
-    }
+
+  // Find the last mapping, if any, such that mSoftTextOffset <= aSoftTextOffset
+  size_t index;
+  bool found = FindLastNongreaterOffset(mSoftTextDOMMapping, aSoftTextOffset, &index);
+  if (!found) {
+    return NodeOffset(nullptr, -1);
   }
-  
-  if (start >= end)
-    return NodeOffset(nullptr, -1);
 
-  // 'start' is now the last mapping, if any, such that
+  // 'index' is now the last mapping, if any, such that
   // mSoftTextOffset <= aSoftTextOffset.
   // If we're doing HINT_END, then we may want to return the end of the
   // the previous mapping instead of the start of this mapping
-  if (aHint == HINT_END && start > 0) {
-    const DOMTextMapping& map = mSoftTextDOMMapping[start - 1];
+  if (aHint == HINT_END && index > 0) {
+    const DOMTextMapping& map = mSoftTextDOMMapping[index - 1];
     if (map.mSoftTextOffset + map.mLength == aSoftTextOffset)
       return NodeOffset(map.mNodeOffset.mNode, map.mNodeOffset.mOffset + map.mLength);
   }
-  
+
   // We allow ourselves to return the end of this mapping even if we're
   // doing HINT_START. This will only happen if there is no mapping which this
   // point is the start of. I'm not 100% sure this is OK...
-  const DOMTextMapping& map = mSoftTextDOMMapping[start];
+  const DOMTextMapping& map = mSoftTextDOMMapping[index];
   int32_t offset = aSoftTextOffset - map.mSoftTextOffset;
   if (offset >= 0 && offset <= map.mLength)
     return NodeOffset(map.mNodeOffset.mNode, map.mNodeOffset.mOffset + offset);
-    
+
   return NodeOffset(nullptr, -1);
 }
 
 int32_t
 mozInlineSpellWordUtil::FindRealWordContaining(int32_t aSoftTextOffset,
     DOMMapHint aHint, bool aSearchForward)
 {
   NS_ASSERTION(mSoftTextValid, "Soft text must be valid if we're to map out of it");
   if (!mSoftTextValid)
     return -1;
 
-  // The invariant is that the range start..end includes the last word,
-  // if any, such that mSoftTextOffset <= aSoftTextOffset
-  int32_t start = 0;
-  int32_t end = mRealWords.Length();
-  while (end - start >= 2) {
-    int32_t mid = (start + end)/2;
-    const RealWord& word = mRealWords[mid];
-    if (word.mSoftTextOffset > aSoftTextOffset) {
-      end = mid;
-    } else {
-      start = mid;
-    }
+  // Find the last word, if any, such that mSoftTextOffset <= aSoftTextOffset
+  size_t index;
+  bool found = FindLastNongreaterOffset(mRealWords, aSoftTextOffset, &index);
+  if (!found) {
+    return -1;
   }
-  
-  if (start >= end)
-    return -1;
 
-  // 'start' is now the last word, if any, such that
+  // 'index' is now the last word, if any, such that
   // mSoftTextOffset <= aSoftTextOffset.
   // If we're doing HINT_END, then we may want to return the end of the
   // the previous word instead of the start of this word
-  if (aHint == HINT_END && start > 0) {
-    const RealWord& word = mRealWords[start - 1];
+  if (aHint == HINT_END && index > 0) {
+    const RealWord& word = mRealWords[index - 1];
     if (word.mSoftTextOffset + word.mLength == aSoftTextOffset)
-      return start - 1;
+      return index - 1;
   }
-  
+
   // We allow ourselves to return the end of this word even if we're
   // doing HINT_START. This will only happen if there is no word which this
   // point is the start of. I'm not 100% sure this is OK...
-  const RealWord& word = mRealWords[start];
+  const RealWord& word = mRealWords[index];
   int32_t offset = aSoftTextOffset - word.mSoftTextOffset;
   if (offset >= 0 && offset <= word.mLength)
-    return start;
+    return index;
 
   if (aSearchForward) {
     if (mRealWords[0].mSoftTextOffset > aSoftTextOffset) {
       // All words have mSoftTextOffset > aSoftTextOffset
       return 0;
     }
-    // 'start' is the last word such that mSoftTextOffset <= aSoftTextOffset.
-    // Word start+1, if it exists, will be the first with
+    // 'index' is the last word such that mSoftTextOffset <= aSoftTextOffset.
+    // Word index+1, if it exists, will be the first with
     // mSoftTextOffset > aSoftTextOffset.
-    if (start + 1 < int32_t(mRealWords.Length()))
-      return start + 1;
+    if (index + 1 < mRealWords.Length())
+      return index + 1;
   }
 
   return -1;
 }
 
 /*********** Word Splitting ************/
 
 // classifies a given character in the DOM word
--- a/gfx/thebes/gfxFont.cpp
+++ b/gfx/thebes/gfxFont.cpp
@@ -1,13 +1,14 @@
 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
+#include "mozilla/BinarySearch.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/MathAlgorithms.h"
 
 #ifdef MOZ_LOGGING
 #define FORCE_PR_LOG /* Allow logging in the release build */
 #endif
 #include "prlog.h"
 
--- a/gfx/thebes/gfxFontUtils.cpp
+++ b/gfx/thebes/gfxFontUtils.cpp
@@ -4,25 +4,27 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifdef MOZ_LOGGING
 #define FORCE_PR_LOG /* Allow logging in the release build */
 #include "prlog.h"
 #endif
 
 #include "mozilla/ArrayUtils.h"
+#include "mozilla/BinarySearch.h"
 
 #include "gfxFontUtils.h"
 #include "gfxColor.h"
 
 #include "nsServiceManagerUtils.h"
 
 #include "mozilla/dom/EncodingUtils.h"
 #include "mozilla/Preferences.h"
 #include "mozilla/Services.h"
+#include "mozilla/BinarySearch.h"
 
 #include "nsCOMPtr.h"
 #include "nsIUUIDGenerator.h"
 #include "nsIUnicodeDecoder.h"
 
 #include "harfbuzz/hb.h"
 
 #include "plbase64.h"
@@ -699,59 +701,57 @@ gfxFontUtils::MapCharToGlyphFormat12(con
     if (startCharCode <= aCh && groups[range].endCharCode >= aCh) {
         return groups[range].startGlyphId + aCh - startCharCode;
     }
 
     // Else it's not present, so return the .notdef glyph
     return 0;
 }
 
+namespace {
+
+struct Format14CmapWrapper
+{
+    const Format14Cmap& mCmap14;
+    Format14CmapWrapper(const Format14Cmap& cmap14) : mCmap14(cmap14) {}
+    uint32_t operator[](size_t index) const {
+        return mCmap14.varSelectorRecords[index].varSelector;
+    }
+};
+
+struct NonDefUVSTableWrapper
+{
+    const NonDefUVSTable& mTable;
+    NonDefUVSTableWrapper(const NonDefUVSTable& table) : mTable(table) {}
+    uint32_t operator[](size_t index) const {
+        return mTable.uvsMappings[index].unicodeValue;
+    }
+};
+
+} // namespace
+
 uint16_t
 gfxFontUtils::MapUVSToGlyphFormat14(const uint8_t *aBuf, uint32_t aCh, uint32_t aVS)
 {
+    using mozilla::BinarySearch;
     const Format14Cmap *cmap14 = reinterpret_cast<const Format14Cmap*>(aBuf);
 
-    // binary search in varSelectorRecords
-    uint32_t min = 0;
-    uint32_t max = cmap14->numVarSelectorRecords;
-    uint32_t nonDefUVSOffset = 0;
-    while (min < max) {
-        uint32_t index = (min + max) >> 1;
-        uint32_t varSelector = cmap14->varSelectorRecords[index].varSelector;
-        if (aVS == varSelector) {
-            nonDefUVSOffset = cmap14->varSelectorRecords[index].nonDefaultUVSOffset;
-            break;
-        }
-        if (aVS < varSelector) {
-            max = index;
-        } else {
-            min = index + 1;
-        }
-    }
-    if (!nonDefUVSOffset) {
+    size_t index;
+    if (!BinarySearch(Format14CmapWrapper(*cmap14),
+                      0, cmap14->numVarSelectorRecords, aVS, &index)) {
         return 0;
     }
 
+    const uint32_t nonDefUVSOffset = cmap14->varSelectorRecords[index].nonDefaultUVSOffset;
     const NonDefUVSTable *table = reinterpret_cast<const NonDefUVSTable*>
                                       (aBuf + nonDefUVSOffset);
 
-    // binary search in uvsMappings
-    min = 0;
-    max = table->numUVSMappings;
-    while (min < max) {
-        uint32_t index = (min + max) >> 1;
-        uint32_t unicodeValue = table->uvsMappings[index].unicodeValue;
-        if (aCh == unicodeValue) {
-            return table->uvsMappings[index].glyphID;
-        }
-        if (aCh < unicodeValue) {
-            max = index;
-        } else {
-            min = index + 1;
-        }
+    if (BinarySearch(NonDefUVSTableWrapper(*table), 0, table->numUVSMappings,
+                     aCh, &index)) {
+        return table->uvsMappings[index].glyphID;
     }
 
     return 0;
 }
 
 uint32_t
 gfxFontUtils::MapCharToGlyph(const uint8_t *aCmapBuf, uint32_t aBufLength,
                              uint32_t aUnicode, uint32_t aVarSelector)
@@ -1329,52 +1329,57 @@ const char* gfxFontUtils::gMSFontNameCha
     /* [5] ENCODING_ID_MICROSOFT_WANSUNG */     nullptr      ,
     /* [6] ENCODING_ID_MICROSOFT_JOHAB */       nullptr      ,
     /* [7] reserved */                          nullptr      ,
     /* [8] reserved */                          nullptr      ,
     /* [9] reserved */                          nullptr      ,
     /*[10] ENCODING_ID_MICROSOFT_UNICODEFULL */ ""
 };
 
+struct MacCharsetMappingComparator
+{
+    typedef gfxFontUtils::MacFontNameCharsetMapping MacFontNameCharsetMapping;
+    const MacFontNameCharsetMapping& mSearchValue;
+    MacCharsetMappingComparator(const MacFontNameCharsetMapping& aSearchValue)
+      : mSearchValue(aSearchValue) {}
+    int operator()(const MacFontNameCharsetMapping& aEntry) const {
+        if (mSearchValue < aEntry) {
+            return -1;
+        }
+        if (aEntry < mSearchValue) {
+            return 1;
+        }
+        return 0;
+    }
+};
+
 // Return the name of the charset we should use to decode a font name
 // given the name table attributes.
 // Special return values:
 //    ""       charset is UTF16BE, no need for a converter
 //    nullptr   unknown charset, do not attempt conversion
 const char*
 gfxFontUtils::GetCharsetForFontName(uint16_t aPlatform, uint16_t aScript, uint16_t aLanguage)
 {
     switch (aPlatform)
     {
     case PLATFORM_ID_UNICODE:
         return "";
 
     case PLATFORM_ID_MAC:
         {
-            uint32_t lo = 0, hi = ArrayLength(gMacFontNameCharsets);
             MacFontNameCharsetMapping searchValue = { aScript, aLanguage, nullptr };
             for (uint32_t i = 0; i < 2; ++i) {
-                // binary search; if not found, set language to ANY and try again
-                while (lo < hi) {
-                    uint32_t mid = (lo + hi) / 2;
-                    const MacFontNameCharsetMapping& entry = gMacFontNameCharsets[mid];
-                    if (entry < searchValue) {
-                        lo = mid + 1;
-                        continue;
-                    }
-                    if (searchValue < entry) {
-                        hi = mid;
-                        continue;
-                    }
-                    // found a match
-                    return entry.mCharsetName;
+                size_t idx;
+                if (BinarySearchIf(gMacFontNameCharsets, 0, ArrayLength(gMacFontNameCharsets),
+                                            MacCharsetMappingComparator(searchValue), &idx)) {
+                    return gMacFontNameCharsets[idx].mCharsetName;
                 }
 
-                // no match, so reset high bound for search and re-try
-                hi = ArrayLength(gMacFontNameCharsets);
+                // no match, so try again finding one in any language
                 searchValue.mLanguage = ANY;
             }
         }
         break;
 
     case PLATFORM_ID_ISO:
         if (aScript < ArrayLength(gISOFontNameCharsets)) {
             return gISOFontNameCharsets[aScript];
--- a/gfx/thebes/gfxFontUtils.h
+++ b/gfx/thebes/gfxFontUtils.h
@@ -962,16 +962,18 @@ public:
     static bool ValidateColorGlyphs(hb_blob_t* aCOLR, hb_blob_t* aCPAL);
     static bool GetColorGlyphLayers(hb_blob_t* aCOLR,
                                     hb_blob_t* aCPAL,
                                     uint32_t aGlyphId,
                                     nsTArray<uint16_t> &aGlyphs,
                                     nsTArray<mozilla::gfx::Color> &aColors);
 
 protected:
+    friend struct MacCharsetMappingComparator;
+
     static nsresult
     ReadNames(const char *aNameData, uint32_t aDataLen, uint32_t aNameID,
               int32_t aLangID, int32_t aPlatformID, nsTArray<nsString>& aNames);
 
     // convert opentype name-table platform/encoding/language values to a charset name
     // we can use to convert the name data to unicode, or "" if data is UTF16BE
     static const char*
     GetCharsetForFontName(uint16_t aPlatform, uint16_t aScript, uint16_t aLanguage);
--- a/gfx/thebes/gfxMathTable.cpp
+++ b/gfx/thebes/gfxMathTable.cpp
@@ -1,16 +1,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "gfxMathTable.h"
 
 #include "MathTableStructures.h"
 #include "harfbuzz/hb.h"
+#include "mozilla/BinarySearch.h"
 #include <algorithm>
 
 using namespace mozilla;
 
 gfxMathTable::gfxMathTable(hb_blob_t* aMathTable)
   : mMathTable(aMathTable)
   , mGlyphConstruction(nullptr)
   , mGlyphID(-1)
@@ -350,64 +351,80 @@ gfxMathTable::GetGlyphAssembly(uint32_t 
 
   // Verify the validity of the GlyphAssembly and return it.
   if (!ValidStructure(start, sizeof(GlyphAssembly))) {
     return nullptr;
   }
   return reinterpret_cast<const GlyphAssembly*>(start);
 }
 
+namespace {
+
+struct GlyphArrayWrapper
+{
+  const GlyphID* const mGlyphArray;
+  GlyphArrayWrapper(const GlyphID* const aGlyphArray) : mGlyphArray(aGlyphArray)
+  {}
+  uint16_t operator[](size_t index) const {
+    return mGlyphArray[index];
+  }
+};
+
+struct RangeRecordComparator
+{
+  const uint32_t mGlyph;
+  RangeRecordComparator(uint32_t aGlyph) : mGlyph(aGlyph) {}
+  int operator()(const RangeRecord& aRecord) const {
+    if (mGlyph < static_cast<uint16_t>(aRecord.mStart)) {
+      return -1;
+    }
+    if (mGlyph > static_cast<uint16_t>(aRecord.mEnd)) {
+      return 1;
+    }
+    return 0;
+  }
+};
+
+} // namespace
+
 int32_t
 gfxMathTable::GetCoverageIndex(const Coverage* aCoverage, uint32_t aGlyph)
 {
+  using mozilla::BinarySearch;
+  using mozilla::BinarySearchIf;
+
   if (uint16_t(aCoverage->mFormat) == 1) {
     // Coverage Format 1: list of individual glyph indices in the glyph set.
     const CoverageFormat1* table =
       reinterpret_cast<const CoverageFormat1*>(aCoverage);
-    uint16_t count = table->mGlyphCount;
+    const uint16_t count = table->mGlyphCount;
     const char* start = reinterpret_cast<const char*>(table + 1);
     if (ValidStructure(start, count * sizeof(GlyphID))) {
-      const GlyphID* glyphArray =
-        reinterpret_cast<const GlyphID*>(start);
-      uint32_t imin = 0, imax = count;
-      while (imin < imax) {
-        uint32_t imid = (imin + imax) >> 1;
-        uint16_t glyphMid = glyphArray[imid];
-        if (glyphMid == aGlyph) {
-          return imid;
-        }
-        if (glyphMid < aGlyph) {
-          imin = imid + 1;
-        } else {
-          imax = imid;
-        }
+      const GlyphID* glyphArray = reinterpret_cast<const GlyphID*>(start);
+      size_t index;
+
+      if (BinarySearch(GlyphArrayWrapper(glyphArray), 0, count, aGlyph, &index)) {
+        return index;
       }
     }
   } else if (uint16_t(aCoverage->mFormat) == 2) {
     // Coverage Format 2: ranges of consecutive indices.
     const CoverageFormat2* table =
       reinterpret_cast<const CoverageFormat2*>(aCoverage);
-    uint16_t count = table->mRangeCount;
+    const uint16_t count = table->mRangeCount;
     const char* start = reinterpret_cast<const char*>(table + 1);
     if (ValidStructure(start, count * sizeof(RangeRecord))) {
-      const RangeRecord* rangeArray =
-        reinterpret_cast<const RangeRecord*>(start);
-      uint32_t imin = 0, imax = count;
-      while (imin < imax) {
-        uint32_t imid = (imin + imax) >> 1;
-        uint16_t rStart = rangeArray[imid].mStart;
-        uint16_t rEnd = rangeArray[imid].mEnd;
-        if (rEnd < aGlyph) {
-          imin = imid + 1;
-        } else if (aGlyph < rStart) {
-          imax = imid;
-        } else {
-          return (uint16_t(rangeArray[imid].mStartCoverageIndex) +
-                  aGlyph - rStart);
-        }
+      const RangeRecord* rangeArray = reinterpret_cast<const RangeRecord*>(start);
+      size_t index;
+
+      if (BinarySearchIf(rangeArray, 0, count, RangeRecordComparator(aGlyph),
+                         &index)) {
+        uint16_t rStart = rangeArray[index].mStart;
+        uint16_t startCoverageIndex = rangeArray[index].mStartCoverageIndex;
+        return (startCoverageIndex + aGlyph - rStart);
       }
     }
   }
   return -1;
 }
 
 void
 gfxMathTable::SelectGlyphConstruction(uint32_t aGlyphID, bool aVertical)
--- a/gfx/thebes/gfxSkipChars.cpp
+++ b/gfx/thebes/gfxSkipChars.cpp
@@ -1,71 +1,85 @@
 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "gfxSkipChars.h"
+#include "mozilla/BinarySearch.h"
+
+struct SkippedRangeStartComparator
+{
+    const uint32_t mOffset;
+    SkippedRangeStartComparator(const uint32_t aOffset) : mOffset(aOffset) {}
+    int operator()(const gfxSkipChars::SkippedRange& aRange) const {
+        return (mOffset < aRange.Start()) ? -1 : 1;
+    }
+};
 
 void
 gfxSkipCharsIterator::SetOriginalOffset(int32_t aOffset)
 {
     aOffset += mOriginalStringToSkipCharsOffset;
     NS_ASSERTION(uint32_t(aOffset) <= mSkipChars->mCharCount,
                  "Invalid offset");
 
     mOriginalStringOffset = aOffset;
 
-    uint32_t rangeCount = mSkipChars->mRanges.Length();
+    const uint32_t rangeCount = mSkipChars->mRanges.Length();
     if (rangeCount == 0) {
         mSkippedStringOffset = aOffset;
         return;
     }
 
     // at start of string?
     if (aOffset == 0) {
         mSkippedStringOffset = 0;
         mCurrentRangeIndex =
             rangeCount && mSkipChars->mRanges[0].Start() == 0 ? 0 : -1;
         return;
     }
 
     // find the range that includes or precedes aOffset
-    uint32_t lo = 0, hi = rangeCount;
-    const gfxSkipChars::SkippedRange* ranges = mSkipChars->mRanges.Elements();
-    while (lo < hi) {
-        uint32_t mid = (lo + hi) / 2;
-        if (uint32_t(aOffset) < ranges[mid].Start()) {
-            hi = mid;
-        } else {
-            lo = mid + 1;
-        }
-    }
+    const nsTArray<gfxSkipChars::SkippedRange>& ranges = mSkipChars->mRanges;
+    size_t idx;
+    mozilla::BinarySearchIf(ranges, 0, rangeCount,
+                            SkippedRangeStartComparator(aOffset),
+                            &idx);
 
-    if (lo == rangeCount) {
+    if (idx == rangeCount) {
         mCurrentRangeIndex = rangeCount - 1;
-    } else if (uint32_t(aOffset) < ranges[lo].Start()) {
-        mCurrentRangeIndex = lo - 1;
+    } else if (uint32_t(aOffset) < ranges[idx].Start()) {
+        mCurrentRangeIndex = idx - 1;
         if (mCurrentRangeIndex == -1) {
             mSkippedStringOffset = aOffset;
             return;
         }
     } else {
-        mCurrentRangeIndex = lo;
+        mCurrentRangeIndex = idx;
     }
 
     const gfxSkipChars::SkippedRange& r = ranges[mCurrentRangeIndex];
     if (uint32_t(aOffset) < r.End()) {
         mSkippedStringOffset = r.SkippedOffset();
         return;
     }
 
     mSkippedStringOffset = aOffset - r.NextDelta();
 }
 
+struct SkippedRangeOffsetComparator
+{
+    const uint32_t mOffset;
+    SkippedRangeOffsetComparator(const uint32_t aOffset) : mOffset(aOffset) {}
+    int operator()(const gfxSkipChars::SkippedRange& aRange) const {
+        return (mOffset < aRange.SkippedOffset()) ? -1 : 1;
+    }
+};
+
 void
 gfxSkipCharsIterator::SetSkippedOffset(uint32_t aOffset)
 {
     NS_ASSERTION((mSkipChars->mRanges.IsEmpty() &&
                   aOffset <= mSkipChars->mCharCount) ||
                  (aOffset <= mSkipChars->LastRange().SkippedOffset() +
                                  mSkipChars->mCharCount -
                                  mSkipChars->LastRange().End()),
@@ -73,37 +87,32 @@ gfxSkipCharsIterator::SetSkippedOffset(u
     mSkippedStringOffset = aOffset;
 
     uint32_t rangeCount = mSkipChars->mRanges.Length();
     if (rangeCount == 0) {
         mOriginalStringOffset = aOffset;
         return;
     }
 
-    uint32_t lo = 0, hi = rangeCount;
-    const gfxSkipChars::SkippedRange* ranges = mSkipChars->mRanges.Elements();
-    while (lo < hi) {
-        uint32_t mid = (lo + hi) / 2;
-        if (aOffset < ranges[mid].SkippedOffset()) {
-            hi = mid;
-        } else {
-            lo = mid + 1;
-        }
-    }
+    const nsTArray<gfxSkipChars::SkippedRange>& ranges = mSkipChars->mRanges;
+    size_t idx;
+    mozilla::BinarySearchIf(ranges, 0, rangeCount,
+                            SkippedRangeOffsetComparator(aOffset),
+                            &idx);
 
-    if (lo == rangeCount) {
+    if (idx == rangeCount) {
         mCurrentRangeIndex = rangeCount - 1;
-    } else if (aOffset < ranges[lo].SkippedOffset()) {
-        mCurrentRangeIndex = lo - 1;
+    } else if (aOffset < ranges[idx].SkippedOffset()) {
+        mCurrentRangeIndex = idx - 1;
         if (mCurrentRangeIndex == -1) {
             mOriginalStringOffset = aOffset;
             return;
         }
     } else {
-        mCurrentRangeIndex = lo;
+        mCurrentRangeIndex = idx;
     }
 
     const gfxSkipChars::SkippedRange& r = ranges[mCurrentRangeIndex];
     mOriginalStringOffset = r.End() + aOffset - r.SkippedOffset();
 }
 
 bool
 gfxSkipCharsIterator::IsOriginalCharSkipped(int32_t* aRunLength) const
--- a/gfx/thebes/gfxSkipChars.h
+++ b/gfx/thebes/gfxSkipChars.h
@@ -20,16 +20,19 @@
 
 /**
  * The gfxSkipChars is represented as a sorted array of skipped ranges.
  *
  * A freshly-created gfxSkipChars means "all chars kept".
  */
 class gfxSkipChars
 {
+    friend struct SkippedRangeStartComparator;
+    friend struct SkippedRangeOffsetComparator;
+
 private:
     class SkippedRange
     {
     public:
         SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta)
             : mOffset(aOffset), mLength(aLength), mDelta(aDelta)
         { }
 
--- a/intl/locale/nsUConvPropertySearch.cpp
+++ b/intl/locale/nsUConvPropertySearch.cpp
@@ -1,35 +1,44 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "nsUConvPropertySearch.h"
 #include "nsCRT.h"
 #include "nsString.h"
+#include "mozilla/BinarySearch.h"
+
+namespace {
+
+struct PropertyComparator
+{
+  const nsCString& mKey;
+  PropertyComparator(const nsCString& aKey) : mKey(aKey) {}
+  int operator()(const char* (&aProperty)[3]) const {
+    return mKey.Compare(aProperty[0]);
+  }
+};
+
+}
 
 // static
 nsresult
 nsUConvPropertySearch::SearchPropertyValue(const char* aProperties[][3],
                                            int32_t aNumberOfProperties,
                                            const nsACString& aKey,
                                            nsACString& aValue)
 {
-  const char* key = PromiseFlatCString(aKey).get();
-  int32_t lo = 0;
-  int32_t hi = aNumberOfProperties - 1;
-  while (lo <= hi) {
-    uint32_t mid = (lo + hi) / 2;
-    int32_t comp = nsCRT::strcmp(aProperties[mid][0], key);
-    if (comp > 0) {
-      hi = mid - 1;
-    } else if (comp < 0) {
-      lo = mid + 1;
-    } else {
-      nsDependentCString val(aProperties[mid][1],
-                             NS_PTR_TO_UINT32(aProperties[mid][2]));
-      aValue.Assign(val);
-      return NS_OK;
-    }
+  using mozilla::BinarySearchIf;
+
+  const nsCString& flat = PromiseFlatCString(aKey);
+  size_t index;
+  if (BinarySearchIf(aProperties, 0, aNumberOfProperties,
+                     PropertyComparator(flat), &index)) {
+    nsDependentCString val(aProperties[index][1],
+                           NS_PTR_TO_UINT32(aProperties[index][2]));
+    aValue.Assign(val);
+    return NS_OK;
   }
+
   aValue.Truncate();
   return NS_ERROR_FAILURE;
 }
--- a/intl/unicharutil/nsUnicodeNormalizer.cpp
+++ b/intl/unicharutil/nsUnicodeNormalizer.cpp
@@ -51,16 +51,17 @@
  *    ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
  */
 
 #include <string.h>
 
 #include "nsMemory.h"
 #include "nsUnicodeNormalizer.h"
 #include "nsString.h"
+#include "mozilla/BinarySearch.h"
 
 NS_IMPL_ISUPPORTS(nsUnicodeNormalizer, nsIUnicodeNormalizer)
 
 
 nsUnicodeNormalizer::nsUnicodeNormalizer()
 {
 }
 
@@ -231,21 +232,33 @@ mdn__unicode_iscompositecandidate(uint32
 	 * composition candidate.
 	 */
 	if (compose_char(c, &dummy) == 0)
 		return (0);
 	else
 		return (1);
 }
 
+namespace {
+
+struct SequenceAdaptor
+{
+	const composition* const mSequence;
+	SequenceAdaptor(const composition* aSequence) : mSequence(aSequence) {}
+	uint32_t operator[](size_t aIdx) const {
+		return mSequence[aIdx].c2;
+	}
+};
+
+} // namespace
+
 static nsresult
 mdn__unicode_compose(uint32_t c1, uint32_t c2, uint32_t *compp)
 {
 	int32_t n;
-	int32_t lo, hi;
 	const struct composition *cseq;
 
 	//assert(compp != nullptr);
 
 	/*
 	 * Check for Hangul.
 	 */
 	if (LBase <= c1 && c1 < LBase + LCount &&
@@ -274,30 +287,22 @@ mdn__unicode_compose(uint32_t c1, uint32
 	 */
 	if ((n = compose_char(c1, &cseq)) == 0)
 		return (NS_SUCCESS_UNORM_NOTFOUND);
 
 	/*
 	 * The composite sequences are sorted by the 2nd character 'c2'.
 	 * So we can use binary search.
 	 */
-	lo = 0;
-	hi = n - 1;
-	while (lo <= hi) {
-		int32_t mid = (lo + hi) / 2;
+	size_t idx;
+	if (mozilla::BinarySearch(SequenceAdaptor(cseq), 0, n, c2, &idx)) {
+		*compp = cseq[idx].comp;
+		return (NS_OK);
+	}
 
-		if (cseq[mid].c2 < c2) {
-			lo = mid + 1;
-		} else if (cseq[mid].c2 > c2) {
-			hi = mid - 1;
-		} else {
-			*compp = cseq[mid].comp;
-			return (NS_OK);
-		}
-	}
 	return (NS_SUCCESS_UNORM_NOTFOUND);
 }
 
 
 #define WORKBUF_SIZE		128
 #define WORKBUF_SIZE_MAX	10000
 
 typedef struct {
--- a/layout/generic/MathMLTextRunFactory.cpp
+++ b/layout/generic/MathMLTextRunFactory.cpp
@@ -1,17 +1,18 @@
 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "MathMLTextRunFactory.h"
 
 #include "mozilla/ArrayUtils.h"
- 
+#include "mozilla/BinarySearch.h"
+
 #include "nsStyleConsts.h"
 #include "nsStyleContext.h"
 #include "nsTextFrameUtils.h"
 #include "nsFontMetrics.h"
 #include "nsDeviceContext.h"
 
 using namespace mozilla;
 
@@ -184,34 +185,39 @@ static const MathVarMapping gLatinExcept
   { 0x1D53F, 0x210D },
   { 0x1D545, 0x2115 },
   { 0x1D547, 0x2119 },
   { 0x1D548, 0x211A },
   { 0x1D549, 0x211D },
   { 0x1D551, 0x2124 }
 };
 
+namespace {
+
+struct MathVarMappingWrapper
+{
+  const MathVarMapping* const mTable;
+  MathVarMappingWrapper(const MathVarMapping* aTable) : mTable(aTable) {}
+  uint32_t operator[](size_t index) const {
+    return mTable[index].mKey;
+  }
+};
+
+} // namespace
+
 // Finds a MathVarMapping struct with the specified key (aKey) within aTable.
 // aTable must be an array, whose length is specified by aNumElements
 static uint32_t
 MathvarMappingSearch(uint32_t aKey, const MathVarMapping* aTable, uint32_t aNumElements)
 {
-  uint32_t low = 0;
-  uint32_t high = aNumElements;
-  while (high > low) {
-    uint32_t midPoint = (low+high) >> 1;
-    if (aKey == aTable[midPoint].mKey) {
-      return aTable[midPoint].mReplacement;
-    }
-    if (aKey > aTable[midPoint].mKey) {
-      low = midPoint + 1;
-    } else {
-      high = midPoint;
-    }
+  size_t index;
+  if (BinarySearch(MathVarMappingWrapper(aTable), 0, aNumElements, aKey, &index)) {
+    return aTable[index].mReplacement;
   }
+
   return 0;
 }
 
 #define GREEK_UPPER_THETA               0x03F4
 #define HOLE_GREEK_UPPER_THETA          0x03A2
 #define NABLA                           0x2207
 #define PARTIAL_DIFFERENTIAL            0x2202
 #define GREEK_UPPER_ALPHA               0x0391
--- a/layout/generic/nsTextFrame.cpp
+++ b/layout/generic/nsTextFrame.cpp
@@ -7,16 +7,17 @@
 
 #include "nsTextFrame.h"
 
 #include "mozilla/Attributes.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/Likely.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/TextEvents.h"
+#include "mozilla/BinarySearch.h"
 
 #include "nsCOMPtr.h"
 #include "nsBlockFrame.h"
 #include "nsCRT.h"
 #include "nsSplittableFrame.h"
 #include "nsLineLayout.h"
 #include "nsString.h"
 #include "nsUnicharUtils.h"
@@ -115,49 +116,43 @@ struct TabWidthStore {
  
   // Need to recalc tab offsets if frame content offset differs from this.
   int32_t mValidForContentOffset;
 
   // A TabWidth record for each tab character measured so far.
   nsTArray<TabWidth> mWidths;
 };
 
+namespace {
+
+struct TabwidthAdaptor
+{
+  const nsTArray<TabWidth>& mWidths;
+  TabwidthAdaptor(const nsTArray<TabWidth>& aWidths)
+    : mWidths(aWidths) {}
+  uint32_t operator[](size_t aIdx) const {
+    return mWidths[aIdx].mOffset;
+  }
+};
+
+} // namespace
+
 void
 TabWidthStore::ApplySpacing(gfxTextRun::PropertyProvider::Spacing *aSpacing,
                             uint32_t aOffset, uint32_t aLength)
 {
-  uint32_t i = 0, len = mWidths.Length();
+  size_t i = 0;
+  const size_t len = mWidths.Length();
 
   // If aOffset is non-zero, do a binary search to find where to start
   // processing the tab widths, in case the list is really long. (See bug
   // 953247.)
   // We need to start from the first entry where mOffset >= aOffset.
   if (aOffset > 0) {
-    uint32_t lo = 0, hi = len;
-    while (lo < hi) {
-      i = (lo + hi) / 2;
-      const TabWidth& tw = mWidths[i];
-      if (tw.mOffset < aOffset) {
-        // mWidths[i] precedes the target range; new search range
-        // will be [i+1, hi)
-        lo = ++i;
-        continue;
-      }
-      if (tw.mOffset > aOffset) {
-        // mWidths[i] is within (or beyond) the target range;
-        // new search range is [lo, i). If it turns out that
-        // mWidths[i] was the first entry within the range,
-        // we'll never move hi any further, and end up exiting
-        // when i == lo == this value of hi.
-        hi = i;
-        continue;
-      }
-      // Found an exact match for aOffset, so end search now
-      break;
-    }
+    mozilla::BinarySearch(TabwidthAdaptor(mWidths), 0, len, aOffset, &i);
   }
 
   uint32_t limit = aOffset + aLength;
   while (i < len) {
     const TabWidth& tw = mWidths[i];
     if (tw.mOffset >= limit) {
       break;
     }
--- a/parser/html/jArray.h
+++ b/parser/html/jArray.h
@@ -19,39 +19,30 @@
  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  * DEALINGS IN THE SOFTWARE.
  */
 
 #ifndef jArray_h
 #define jArray_h
 
 #include "mozilla/Attributes.h"
+#include "mozilla/BinarySearch.h"
 #include "mozilla/NullPtr.h"
 #include "nsDebug.h"
 
 template<class T, class L>
 struct staticJArray {
   const T* arr;
   const L length;
   operator T*() { return arr; }
   T& operator[] (L const index) { return ((T*)arr)[index]; }
   L binarySearch(T const elem) {
-    L lo = 0;
-    L hi = length - 1;
-    while (lo <= hi) {
-      L mid = (lo + hi) / 2;
-      if (arr[mid] > elem) {
-        hi = mid - 1;
-      } else if (arr[mid] < elem) {
-        lo = mid + 1;
-      } else {
-        return mid;
-      }
-    }
-    return -1;
+    size_t idx;
+    bool found = mozilla::BinarySearch(arr, 0, length, elem, &idx);
+    return found ? idx : -1;
   }
 };
 
 template<class T, class L>
 struct jArray {
   T* arr;
   L length;
   static jArray<T,L> newJArray(L const len) {
--- a/parser/htmlparser/nsParser.cpp
+++ b/parser/htmlparser/nsParser.cpp
@@ -37,16 +37,17 @@
 #include "mozilla/Mutex.h"
 #include "nsParserConstants.h"
 #include "nsCharsetSource.h"
 #include "nsContentUtils.h"
 #include "nsThreadUtils.h"
 #include "nsIHTMLContentSink.h"
 
 #include "mozilla/dom/EncodingUtils.h"
+#include "mozilla/BinarySearch.h"
 
 using namespace mozilla;
 using mozilla::dom::EncodingUtils;
 
 #define NS_PARSER_FLAG_PARSER_ENABLED         0x00000002
 #define NS_PARSER_FLAG_OBSERVERS_ENABLED      0x00000004
 #define NS_PARSER_FLAG_PENDING_CONTINUE_EVENT 0x00000008
 #define NS_PARSER_FLAG_FLUSH_TOKENS           0x00000020
@@ -632,16 +633,30 @@ VerifyPublicIDs()
         NS_NOTREACHED("doctype not lower case");
         printf("Doctype %s not lower case.\n", kPublicIDs[i].name);
       }
     }
   }
 }
 #endif
 
+namespace {
+
+struct PublicIdComparator
+{
+  const nsAutoCString& mPublicId;
+  PublicIdComparator(const nsAutoCString& aPublicId)
+    : mPublicId(aPublicId) {}
+  int operator()(const PubIDInfo& aInfo) const {
+    return nsCRT::strcmp(mPublicId.get(), aInfo.name);
+  }
+};
+
+} // namespace
+
 static void
 DetermineHTMLParseMode(const nsString& aBuffer,
                        nsDTDMode& aParseMode,
                        eParserDocType& aDocType)
 {
 #ifdef DEBUG
   VerifyPublicIDs();
 #endif
@@ -672,39 +687,25 @@ DetermineHTMLParseMode(const nsString& a
       // Yes, we want UCS2 to ASCII lossy conversion.
       nsAutoCString publicID;
       publicID.AssignWithConversion(publicIDUCS2);
 
       // See comment above definition of kPublicIDs about case
       // sensitivity.
       ToLowerCase(publicID);
 
-      // Binary search to see if we can find the correct public ID
-      // These must be signed since maximum can go below zero and we'll
-      // crash if it's unsigned.
-      int32_t minimum = 0;
-      int32_t maximum = ELEMENTS_OF(kPublicIDs) - 1;
-      int32_t index;
-      for (;;) {
-        index = (minimum + maximum) / 2;
-        int32_t comparison =
-            nsCRT::strcmp(publicID.get(), kPublicIDs[index].name);
-        if (comparison == 0)
-          break;
-        if (comparison < 0)
-          maximum = index - 1;
-        else
-          minimum = index + 1;
-
-        if (maximum < minimum) {
-          // The DOCTYPE is not in our list, so it must be full_standards.
-          aParseMode = eDTDMode_full_standards;
-          aDocType = eHTML_Strict;
-          return;
-        }
+      // Binary search to see if we can find the correct public ID.
+      size_t index;
+      bool found = BinarySearchIf(kPublicIDs, 0, ArrayLength(kPublicIDs),
+                                  PublicIdComparator(publicID), &index);
+      if (!found) {
+        // The DOCTYPE is not in our list, so it must be full_standards.
+        aParseMode = eDTDMode_full_standards;
+        aDocType = eHTML_Strict;
+        return;
       }
 
       switch ((resultFlags & PARSE_DTD_HAVE_SYSTEM_ID)
                 ? kPublicIDs[index].mode_if_sysid
                 : kPublicIDs[index].mode_if_no_sysid)
       {
         case PubIDInfo::eQuirks:
           aParseMode = eDTDMode_quirks;
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -5,16 +5,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef nsTArray_h__
 #define nsTArray_h__
 
 #include "nsTArrayForwardDeclare.h"
 #include "mozilla/Alignment.h"
 #include "mozilla/Assertions.h"
+#include "mozilla/BinarySearch.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/TypeTraits.h"
 
 #include <string.h>
 
 #include "nsCycleCollectionNoteChild.h"
 #include "nsAlgorithm.h"
@@ -692,16 +693,39 @@ struct nsTArray_TypedBase<JS::Heap<E>, D
 
   operator const FallibleTArray<E>&()
   {
     Derived* self = static_cast<Derived*>(this);
     return *reinterpret_cast<FallibleTArray<E> *>(self);
   }
 };
 
+namespace detail {
+
+template<class Item, class Comparator>
+struct ItemComparator
+{
+  const Item& mItem;
+  const Comparator& mComp;
+  ItemComparator(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;
+    } else {
+      return -1;
+    }
+  }
+};
+
+} // namespace detail
 
 //
 // nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
 // nsAutoTArray, and AutoFallibleTArray.
 //
 // The only situation in which you might need to use nsTArray_Impl in your code
 // is if you're writing code which mutates a TArray which may or may not be
 // infallible.
@@ -1221,33 +1245,22 @@ public:
   // @param aItem  The item to search for.
   // @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
   {
-    // invariant: low <= [idx] <= high
-    index_type low = 0, high = Length();
-    while (high > low) {
-      index_type mid = (high + low) >> 1;
-      // Comparators are not required to provide a LessThan(Item&, elem_type),
-      // so we can't do aComp.LessThan(aItem, ElementAt(mid)).
-      if (aComp.LessThan(ElementAt(mid), aItem) ||
-          aComp.Equals(ElementAt(mid), aItem)) {
-        // aItem >= ElementAt(mid), so our desired index is at least mid+1.
-        low = mid + 1;
-      } else {
-        // aItem < ElementAt(mid).  Our desired index is therefore at most mid.
-        high = mid;
-      }
-    }
-    MOZ_ASSERT(high == low);
-    return low;
+    using mozilla::BinarySearchIf;
+    typedef ::detail::ItemComparator<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>
   index_type
   IndexOfFirstElementGt(const Item& aItem) const
   {
     return IndexOfFirstElementGt(aItem, nsDefaultComparator<elem_type, Item>());
--- a/xpcom/threads/TimerThread.cpp
+++ b/xpcom/threads/TimerThread.cpp
@@ -10,16 +10,17 @@
 #include "nsThreadUtils.h"
 #include "pratom.h"
 
 #include "nsIObserverService.h"
 #include "nsIServiceManager.h"
 #include "mozilla/Services.h"
 #include "mozilla/ChaosMode.h"
 #include "mozilla/ArrayUtils.h"
+#include "mozilla/BinarySearch.h"
 
 #include <math.h>
 
 using namespace mozilla;
 
 NS_IMPL_ISUPPORTS(TimerThread, nsIRunnable, nsIObserver)
 
 TimerThread::TimerThread() :
@@ -169,16 +170,34 @@ TimerThread::Shutdown()
   PR_LOG(GetTimerLog(), PR_LOG_DEBUG, ("TimerThread::Shutdown end\n"));
   return NS_OK;
 }
 
 #ifdef MOZ_NUWA_PROCESS
 #include "ipc/Nuwa.h"
 #endif
 
+namespace {
+
+struct MicrosecondsToInterval
+{
+  PRIntervalTime operator[](size_t aMs) const {
+    return PR_MicrosecondsToInterval(aMs);
+  }
+};
+
+struct IntervalComparator
+{
+  int operator()(PRIntervalTime aInterval) const {
+    return (0 < aInterval) ? -1 : 1;
+  }
+};
+
+} // namespace
+
 /* void Run(); */
 NS_IMETHODIMP
 TimerThread::Run()
 {
   PR_SetCurrentThreadName("Timer");
 
 #ifdef MOZ_NUWA_PROCESS
   if (IsNuwaProcess()) {
@@ -186,38 +205,32 @@ TimerThread::Run()
                  "NuwaMarkCurrentThread is undefined!");
     NuwaMarkCurrentThread(nullptr, nullptr);
   }
 #endif
 
   MonitorAutoLock lock(mMonitor);
 
   // We need to know how many microseconds give a positive PRIntervalTime. This
-  // is platform-dependent, we calculate it at runtime now.
-  // First we find a value such that PR_MicrosecondsToInterval(high) = 1
-  int32_t low = 0, high = 1;
-  while (PR_MicrosecondsToInterval(high) == 0) {
-    high <<= 1;
+  // is platform-dependent and we calculate it at runtime, finding a value |v|
+  // such that |PR_MicrosecondsToInterval(v) > 0| and then binary-searching in
+  // the range [0, v) to find the ms-to-interval scale.
+  uint32_t usForPosInterval = 1;
+  while (PR_MicrosecondsToInterval(usForPosInterval) == 0) {
+    usForPosInterval <<= 1;
   }
-  // We now have
-  //    PR_MicrosecondsToInterval(low)  = 0
-  //    PR_MicrosecondsToInterval(high) = 1
-  // and we can proceed to find the critical value using binary search
-  while (high - low > 1) {
-    int32_t mid = (high + low) >> 1;
-    if (PR_MicrosecondsToInterval(mid) == 0) {
-      low = mid;
-    } else {
-      high = mid;
-    }
-  }
+
+  size_t usIntervalResolution;
+  BinarySearchIf(MicrosecondsToInterval(), 0, usForPosInterval, IntervalComparator(), &usIntervalResolution);
+  MOZ_ASSERT(PR_MicrosecondsToInterval(usIntervalResolution - 1) == 0);
+  MOZ_ASSERT(PR_MicrosecondsToInterval(usIntervalResolution) == 1);
 
   // Half of the amount of microseconds needed to get positive PRIntervalTime.
   // We use this to decide how to round our wait times later
-  int32_t halfMicrosecondsIntervalResolution = high >> 1;
+  int32_t halfMicrosecondsIntervalResolution = usIntervalResolution / 2;
   bool forceRunNextTimer = false;
 
   while (!mShutdown) {
     // Have to use PRIntervalTime here, since PR_WaitCondVar takes it
     PRIntervalTime waitFor;
     bool forceRunThisTimer = forceRunNextTimer;
     forceRunNextTimer = false;