mfbt/BinarySearch.h@97036ab72558 (annotated)
mfbt/BinarySearch.h
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
| michael@0 | 1 | /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ |
| michael@0 | 2 | /* vim: set ts=8 sts=2 et sw=2 tw=80: */ |
| michael@0 | 3 | /* This Source Code Form is subject to the terms of the Mozilla Public |
| michael@0 | 4 | * License, v. 2.0. If a copy of the MPL was not distributed with this |
| michael@0 | 5 | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
| michael@0 | 6 | |
| michael@0 | 7 | #ifndef mozilla_BinarySearch_h |
| michael@0 | 8 | #define mozilla_BinarySearch_h |
| michael@0 | 9 | |
| michael@0 | 10 | #include "mozilla/Assertions.h" |
| michael@0 | 11 | |
| michael@0 | 12 | #include <stddef.h> |
| michael@0 | 13 | |
| michael@0 | 14 | namespace mozilla { |
| michael@0 | 15 | |
| michael@0 | 16 | /* |
| michael@0 | 17 | * The algorithm searches the given container 'c' over the sorted index range |
| michael@0 | 18 | * [begin, end) for an index 'i' where 'c[i] == target'. If such an index 'i' is |
| michael@0 | 19 | * found, BinarySearch returns 'true' and the index is returned via the outparam |
| michael@0 | 20 | * 'matchOrInsertionPoint'. If no index is found, BinarySearch returns 'false' |
| michael@0 | 21 | * and the outparam returns the first index in [begin, end] where 'target' can |
| michael@0 | 22 | * be inserted to maintain sorted order. |
| michael@0 | 23 | * |
| michael@0 | 24 | * Example: |
| michael@0 | 25 | * |
| michael@0 | 26 | * Vector<int> sortedInts = ... |
| michael@0 | 27 | * |
| michael@0 | 28 | * size_t match; |
| michael@0 | 29 | * if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) |
| michael@0 | 30 | * printf("found 13 at %lu\n", match); |
| michael@0 | 31 | */ |
| michael@0 | 32 | |
| michael@0 | 33 | template <typename Container, typename T> |
| michael@0 | 34 | bool |
| michael@0 | 35 | BinarySearch(const Container &c, size_t begin, size_t end, T target, size_t *matchOrInsertionPoint) |
| michael@0 | 36 | { |
| michael@0 | 37 | MOZ_ASSERT(begin <= end); |
| michael@0 | 38 | |
| michael@0 | 39 | size_t low = begin; |
| michael@0 | 40 | size_t high = end; |
| michael@0 | 41 | while (low != high) { |
| michael@0 | 42 | size_t middle = low + (high - low) / 2; |
| michael@0 | 43 | const T &middleValue = c[middle]; |
| michael@0 | 44 | |
| michael@0 | 45 | MOZ_ASSERT(c[low] <= c[middle]); |
| michael@0 | 46 | MOZ_ASSERT(c[middle] <= c[high - 1]); |
| michael@0 | 47 | MOZ_ASSERT(c[low] <= c[high - 1]); |
| michael@0 | 48 | |
| michael@0 | 49 | if (target == middleValue) { |
| michael@0 | 50 | *matchOrInsertionPoint = middle; |
| michael@0 | 51 | return true; |
| michael@0 | 52 | } |
| michael@0 | 53 | |
| michael@0 | 54 | if (target < middleValue) |
| michael@0 | 55 | high = middle; |
| michael@0 | 56 | else |
| michael@0 | 57 | low = middle + 1; |
| michael@0 | 58 | } |
| michael@0 | 59 | |
| michael@0 | 60 | *matchOrInsertionPoint = low; |
| michael@0 | 61 | return false; |
| michael@0 | 62 | } |
| michael@0 | 63 | |
| michael@0 | 64 | } // namespace mozilla |
| michael@0 | 65 | |
| michael@0 | 66 | #endif // mozilla_BinarySearch_h |
