author | Luke Wagner <luke@mozilla.com> |
Tue, 15 Apr 2014 21:30:26 -0500 | |
changeset 179622 | 0de0cedf6a7dd87c4a76a198243a5280402550b0 |
parent 179621 | 4d232ce4ffb53d5fe15b3d1849088a7841323462 |
child 179623 | 39041565bfa9a7f5b9e983df9f8e2fb8a3e6a3c4 |
push id | 26632 |
push user | kwierso@gmail.com |
push date | Wed, 23 Apr 2014 00:54:42 +0000 |
treeherder | mozilla-central@02515cf4fcfd [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | sunfish |
bugs | 998507 |
milestone | 31.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
|
--- 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',