Bug 998507 - add BinarySearch (r=sunfish)
authorLuke Wagner <luke@mozilla.com>
Tue, 15 Apr 2014 21:30:26 -0500
changeset 199184 0de0cedf6a7dd87c4a76a198243a5280402550b0
parent 199183 4d232ce4ffb53d5fe15b3d1849088a7841323462
child 199185 39041565bfa9a7f5b9e983df9f8e2fb8a3e6a3c4
push id486
push userasasaki@mozilla.com
push dateMon, 14 Jul 2014 18:39:42 +0000
treeherdermozilla-release@d33428174ff1 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssunfish
bugs998507
milestone31.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 998507 - add BinarySearch (r=sunfish)
js/src/jit/AsmJSSignalHandlers.cpp
mfbt/BinarySearch.h
mfbt/moz.build
mfbt/tests/TestBinarySearch.cpp
mfbt/tests/moz.build
--- a/js/src/jit/AsmJSSignalHandlers.cpp
+++ b/js/src/jit/AsmJSSignalHandlers.cpp
@@ -1,16 +1,18 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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 "jit/AsmJSSignalHandlers.h"
 
+#include "mozilla/BinarySearch.h"
+
 #include "assembler/assembler/MacroAssembler.h"
 #include "jit/AsmJSModule.h"
 
 using namespace js;
 using namespace js::jit;
 using namespace mozilla;
 
 using JS::GenericNaN;
@@ -202,45 +204,39 @@ SetXMMRegToNaN(bool isFloat32, T *xmm_re
     } else {
         JS_STATIC_ASSERT(sizeof(T) == 2 * sizeof(double));
         double *dbls = reinterpret_cast<double*>(xmm_reg);
         dbls[0] = GenericNaN();
         dbls[1] = 0;
     }
 }
 
+struct GetHeapAccessOffset
+{
+    const AsmJSModule &module;
+    explicit GetHeapAccessOffset(const AsmJSModule &module) : module(module) {}
+    uintptr_t operator[](size_t index) const {
+        return module.heapAccess(index).offset();
+    }
+};
+
 // Perform a binary search on the projected offsets of the known heap accesses
 // in the module.
 static const AsmJSHeapAccess *
 LookupHeapAccess(const AsmJSModule &module, uint8_t *pc)
 {
     JS_ASSERT(module.containsPC(pc));
-    size_t targetOffset = pc - module.codeBase();
+
+    uintptr_t pcOff = pc - module.codeBase();
 
-    if (module.numHeapAccesses() == 0)
+    size_t match;
+    if (!BinarySearch(GetHeapAccessOffset(module), 0, module.numHeapAccesses(), pcOff, &match))
         return nullptr;
 
-    size_t low = 0;
-    size_t high = module.numHeapAccesses() - 1;
-    while (high - low >= 2) {
-        size_t mid = low + (high - low) / 2;
-        uint32_t midOffset = module.heapAccess(mid).offset();
-        if (targetOffset == midOffset)
-            return &module.heapAccess(mid);
-        if (targetOffset < midOffset)
-            high = mid;
-        else
-            low = mid;
-    }
-    if (targetOffset == module.heapAccess(low).offset())
-        return &module.heapAccess(low);
-    if (targetOffset == module.heapAccess(high).offset())
-        return &module.heapAccess(high);
-
-    return nullptr;
+    return &module.heapAccess(match);
 }
 #endif
 
 #if defined(XP_WIN)
 # include "jswin.h"
 #else
 # include <signal.h>
 # include <sys/mman.h>
new file mode 100644
--- /dev/null
+++ b/mfbt/BinarySearch.h
@@ -0,0 +1,62 @@
+/* -*- 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>
+
+namespace mozilla {
+
+/*
+ * The algorithm searches the given container 'c' over the sorted index range
+ * [begin, end) for an index 'i' where 'c[i] == target'. If such an index 'i' is
+ * found, BinarySearch returns 'true' and the index is returned via the outparam
+ * 'matchOrInsertionPoint'. If no index is found, BinarySearch returns 'false'
+ * and the outparam returns the first index in [begin, end] where 'target' 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);
+ */
+
+template <typename Container, typename T>
+bool
+BinarySearch(const Container &c, size_t begin, size_t end, T target, size_t *matchOrInsertionPoint)
+{
+  MOZ_ASSERT(begin <= end);
+
+  size_t low = begin;
+  size_t high = end;
+  while (low != high) {
+    size_t middle = low + (high - low) / 2;
+    const T &middleValue = c[middle];
+
+    if (target == middleValue) {
+      *matchOrInsertionPoint = middle;
+      return true;
+    }
+
+    if (target < middleValue)
+      high = middle;
+    else
+      low = middle + 1;
+  }
+
+  *matchOrInsertionPoint = low;
+  return false;
+}
+
+} // namespace mozilla
+
+#endif // mozilla_BinarySearch_h
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -11,16 +11,17 @@ LIBRARY_NAME = 'mfbt'
 EXPORTS.mozilla = [
     'Alignment.h',
     'AllocPolicy.h',
     'Array.h',
     'ArrayUtils.h',
     'Assertions.h',
     'Atomics.h',
     'Attributes.h',
+    'BinarySearch.h',
     'BloomFilter.h',
     'Casting.h',
     'ChaosMode.h',
     'Char16.h',
     'CheckedInt.h',
     'Compiler.h',
     'Compression.h',
     'Constants.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestBinarySearch.cpp
@@ -0,0 +1,75 @@
+/* -*- 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 "mozilla/Assertions.h"
+#include "mozilla/BinarySearch.h"
+#include "mozilla/Vector.h"
+
+using mozilla::Vector;
+using mozilla::BinarySearch;
+
+struct Person
+{
+  int age;
+  int id;
+  Person(int age, int id) : age(age), id(id) {}
+};
+
+struct GetAge
+{
+  Vector<Person> &v;
+  GetAge(Vector<Person> &v) : v(v) {}
+  int operator[](size_t index) const { return v[index].age; }
+};
+
+int main()
+{
+  size_t m;
+
+  Vector<int> v1;
+  v1.append(2);
+  v1.append(4);
+  v1.append(6);
+  v1.append(8);
+
+  MOZ_ASSERT(!BinarySearch(v1, 0, v1.length(), 1, &m) && m == 0);
+  MOZ_ASSERT( BinarySearch(v1, 0, v1.length(), 2, &m) && m == 0);
+  MOZ_ASSERT(!BinarySearch(v1, 0, v1.length(), 3, &m) && m == 1);
+  MOZ_ASSERT( BinarySearch(v1, 0, v1.length(), 4, &m) && m == 1);
+  MOZ_ASSERT(!BinarySearch(v1, 0, v1.length(), 5, &m) && m == 2);
+  MOZ_ASSERT( BinarySearch(v1, 0, v1.length(), 6, &m) && m == 2);
+  MOZ_ASSERT(!BinarySearch(v1, 0, v1.length(), 7, &m) && m == 3);
+  MOZ_ASSERT( BinarySearch(v1, 0, v1.length(), 8, &m) && m == 3);
+  MOZ_ASSERT(!BinarySearch(v1, 0, v1.length(), 9, &m) && m == 4);
+
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 1, &m) && m == 1);
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 2, &m) && m == 1);
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 3, &m) && m == 1);
+  MOZ_ASSERT( BinarySearch(v1, 1, 3, 4, &m) && m == 1);
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 5, &m) && m == 2);
+  MOZ_ASSERT( BinarySearch(v1, 1, 3, 6, &m) && m == 2);
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 7, &m) && m == 3);
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 8, &m) && m == 3);
+  MOZ_ASSERT(!BinarySearch(v1, 1, 3, 9, &m) && m == 3);
+
+  MOZ_ASSERT(!BinarySearch(v1, 0, 0, 0, &m) && m == 0);
+  MOZ_ASSERT(!BinarySearch(v1, 0, 0, 9, &m) && m == 0);
+
+  Vector<int> v2;
+  MOZ_ASSERT(!BinarySearch(v2, 0, 0, 0, &m) && m == 0);
+  MOZ_ASSERT(!BinarySearch(v2, 0, 0, 9, &m) && m == 0);
+
+  Vector<Person> v3;
+  v3.append(Person(2, 42));
+  v3.append(Person(4, 13));
+  v3.append(Person(6, 360));
+  MOZ_ASSERT(!BinarySearch(GetAge(v3), 0, v3.length(), 1, &m) && m == 0);
+  MOZ_ASSERT( BinarySearch(GetAge(v3), 0, v3.length(), 2, &m) && m == 0);
+  MOZ_ASSERT(!BinarySearch(GetAge(v3), 0, v3.length(), 3, &m) && m == 1);
+  MOZ_ASSERT( BinarySearch(GetAge(v3), 0, v3.length(), 4, &m) && m == 1);
+  MOZ_ASSERT(!BinarySearch(GetAge(v3), 0, v3.length(), 5, &m) && m == 2);
+  MOZ_ASSERT( BinarySearch(GetAge(v3), 0, v3.length(), 6, &m) && m == 2);
+  MOZ_ASSERT(!BinarySearch(GetAge(v3), 0, v3.length(), 7, &m) && m == 3);
+}
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -1,16 +1,17 @@
 # -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
 # vim: set filetype=python:
 # 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/.
 
 CPP_UNIT_TESTS += [
     'TestAtomics.cpp',
+    'TestBinarySearch.cpp',
     'TestBloomFilter.cpp',
     'TestCasting.cpp',
     'TestCeilingFloor.cpp',
     'TestCheckedInt.cpp',
     'TestCountPopulation.cpp',
     'TestCountZeroes.cpp',
     'TestEndian.cpp',
     'TestEnumSet.cpp',