1 files changed, 247 insertions, 0 deletions
diff --git a/mfbt/BinarySearch.h b/mfbt/BinarySearch.h
new file mode 100644
index 0000000000..f3aeac30a0
--- /dev/null
+++ b/mfbt/BinarySearch.h
@@ -0,0 +1,247 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* 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/. */
+
+#ifndef mozilla_BinarySearch_h
+#define mozilla_BinarySearch_h
+
+#include "mozilla/Assertions.h"
+
+#include <stddef.h>
+#include <utility>
+
+namespace mozilla {
+
+/*
+ * The BinarySearch() algorithm searches the given container |aContainer| over
+ * the sorted index range [aBegin, aEnd) for an index |i| where
+ * |aContainer[i] == aTarget|.
+ * If such an index |i| is found, BinarySearch returns |true| and the index is
+ * returned via the outparam |aMatchOrInsertionPoint|. If no index is found,
+ * BinarySearch returns |false| and the outparam returns the first index in
+ * [aBegin, aEnd] where |aTarget| can be inserted to maintain sorted order.
+ *
+ * Example:
+ *
+ *   Vector<int> sortedInts = ...
+ *
+ *   size_t match;
+ *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
+ *     printf("found 13 at %lu\n", match);
+ *   }
+ *
+ * The BinarySearchIf() version behaves similarly, but takes |aComparator|, a
+ * functor to compare the values with, instead of a value to find.
+ * That functor should take one argument - the value to compare - and return an
+ * |int| with the comparison result:
+ *
+ *   * 0, if the argument is equal to,
+ *   * less than 0, if the argument is greater than,
+ *   * greater than 0, if the argument is less than
+ *
+ * the value.
+ *
+ * Example:
+ *
+ *   struct Comparator {
+ *     int operator()(int aVal) const {
+ *       if (mTarget < aVal) { return -1; }
+ *       if (mTarget > aVal) { return 1; }
+ *       return 0;
+ *     }
+ *     explicit Comparator(int aTarget) : mTarget(aTarget) {}
+ *     const int mTarget;
+ *   };
+ *
+ *   Vector<int> sortedInts = ...
+ *
+ *   size_t match;
+ *   if (BinarySearchIf(sortedInts, 0, sortedInts.length(), Comparator(13),
+ * &match)) { printf("found 13 at %lu\n", match);
+ *   }
+ *
+ */
+
+template <typename Container, typename Comparator>
+bool BinarySearchIf(const Container& aContainer, size_t aBegin, size_t aEnd,
+                    const Comparator& aCompare,
+                    size_t* aMatchOrInsertionPoint) {
+  MOZ_ASSERT(aBegin <= aEnd);
+
+  size_t low = aBegin;
+  size_t high = aEnd;
+  while (high != low) {
+    size_t middle = low + (high - low) / 2;
+
+    // Allow any intermediate type so long as it provides a suitable ordering
+    // relation.
+    const int result = aCompare(aContainer[middle]);
+
+    if (result == 0) {
+      *aMatchOrInsertionPoint = middle;
+      return true;
+    }
+
+    if (result < 0) {
+      high = middle;
+    } else {
+      low = middle + 1;
+    }
+  }
+
+  *aMatchOrInsertionPoint = low;
+  return false;
+}
+
+namespace detail {
+
+template <class T>
+class BinarySearchDefaultComparator {
+ public:
+  explicit BinarySearchDefaultComparator(const T& aTarget) : mTarget(aTarget) {}
+
+  template <class U>
+  int operator()(const U& aVal) const {
+    if (mTarget == aVal) {
+      return 0;
+    }
+
+    if (mTarget < aVal) {
+      return -1;
+    }
+
+    return 1;
+  }
+
+ private:
+  const T& mTarget;
+};
+
+}  // namespace detail
+
+template <typename Container, typename T>
+bool BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
+                  T aTarget, size_t* aMatchOrInsertionPoint) {
+  return BinarySearchIf(aContainer, aBegin, aEnd,
+                        detail::BinarySearchDefaultComparator<T>(aTarget),
+                        aMatchOrInsertionPoint);
+}
+
+/*
+ * LowerBound(), UpperBound(), and EqualRange() are equivalent to
+ * std::lower_bound(), std::upper_bound(), and std::equal_range() respectively.
+ *
+ * LowerBound() returns an index pointing to the first element in the range
+ * in which each element is considered *not less than* the given value passed
+ * via |aCompare|, or the length of |aContainer| if no such element is found.
+ *
+ * UpperBound() returns an index pointing to the first element in the range
+ * in which each element is considered *greater than* the given value passed
+ * via |aCompare|, or the length of |aContainer| if no such element is found.
+ *
+ * EqualRange() returns a range [first, second) containing all elements are
+ * considered equivalent to the given value via |aCompare|.  If you need
+ * either the first or last index of the range, LowerBound() or UpperBound(),
+ * which is slightly faster than EqualRange(), should suffice.
+ *
+ * Example (another example is given in TestBinarySearch.cpp):
+ *
+ *   Vector<const char*> sortedStrings = ...
+ *
+ *   struct Comparator {
+ *     const nsACString& mStr;
+ *     explicit Comparator(const nsACString& aStr) : mStr(aStr) {}
+ *     int32_t operator()(const char* aVal) const {
+ *       return Compare(mStr, nsDependentCString(aVal));
+ *     }
+ *   };
+ *
+ *   auto bounds = EqualRange(sortedStrings, 0, sortedStrings.length(),
+ *                            Comparator("needle I'm looking for"_ns));
+ *   printf("Found the range [%zd %zd)\n", bounds.first(), bounds.second());
+ *
+ */
+template <typename Container, typename Comparator>
+size_t LowerBound(const Container& aContainer, size_t aBegin, size_t aEnd,
+                  const Comparator& aCompare) {
+  MOZ_ASSERT(aBegin <= aEnd);
+
+  size_t low = aBegin;
+  size_t high = aEnd;
+  while (high != low) {
+    size_t middle = low + (high - low) / 2;
+
+    // Allow any intermediate type so long as it provides a suitable ordering
+    // relation.
+    const int result = aCompare(aContainer[middle]);
+
+    // The range returning from LowerBound does include elements
+    // equivalent to the given value i.e. aCompare(element) == 0
+    if (result <= 0) {
+      high = middle;
+    } else {
+      low = middle + 1;
+    }
+  }
+
+  return low;
+}
+
+template <typename Container, typename Comparator>
+size_t UpperBound(const Container& aContainer, size_t aBegin, size_t aEnd,
+                  const Comparator& aCompare) {
+  MOZ_ASSERT(aBegin <= aEnd);
+
+  size_t low = aBegin;
+  size_t high = aEnd;
+  while (high != low) {
+    size_t middle = low + (high - low) / 2;
+
+    // Allow any intermediate type so long as it provides a suitable ordering
+    // relation.
+    const int result = aCompare(aContainer[middle]);
+
+    // The range returning from UpperBound does NOT include elements
+    // equivalent to the given value i.e. aCompare(element) == 0
+    if (result < 0) {
+      high = middle;
+    } else {
+      low = middle + 1;
+    }
+  }
+
+  return high;
+}
+
+template <typename Container, typename Comparator>
+std::pair<size_t, size_t> EqualRange(const Container& aContainer, size_t aBegin,
+                                     size_t aEnd, const Comparator& aCompare) {
+  MOZ_ASSERT(aBegin <= aEnd);
+
+  size_t low = aBegin;
+  size_t high = aEnd;
+  while (high != low) {
+    size_t middle = low + (high - low) / 2;
+
+    // Allow any intermediate type so long as it provides a suitable ordering
+    // relation.
+    const int result = aCompare(aContainer[middle]);
+
+    if (result < 0) {
+      high = middle;
+    } else if (result > 0) {
+      low = middle + 1;
+    } else {
+      return {LowerBound(aContainer, low, middle, aCompare),
+              UpperBound(aContainer, middle + 1, high, aCompare)};
+    }
+  }
+
+  return {low, high};
+}
+
+}  // namespace mozilla
+
+#endif  // mozilla_BinarySearch_h