The Tor Browser: mfbt/BinarySearch.h@97036ab72558

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.

     1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

     2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */

     3 /* This Source Code Form is subject to the terms of the Mozilla Public

     4  * License, v. 2.0. If a copy of the MPL was not distributed with this

     5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     7 #ifndef mozilla_BinarySearch_h

     8 #define mozilla_BinarySearch_h

    10 #include "mozilla/Assertions.h"

    12 #include <stddef.h>

    14 namespace mozilla {

    16 /*

    17  * The algorithm searches the given container 'c' over the sorted index range

    18  * [begin, end) for an index 'i' where 'c[i] == target'. If such an index 'i' is

    19  * found, BinarySearch returns 'true' and the index is returned via the outparam

    20  * 'matchOrInsertionPoint'. If no index is found, BinarySearch returns 'false'

    21  * and the outparam returns the first index in [begin, end] where 'target' can

    22  * be inserted to maintain sorted order.

    23  *

    24  * Example:

    25  *

    26  *   Vector<int> sortedInts = ...

    27  *

    28  *   size_t match;

    29  *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match))

    30  *     printf("found 13 at %lu\n", match);

    31  */

    33 template <typename Container, typename T>

    34 bool

    35 BinarySearch(const Container &c, size_t begin, size_t end, T target, size_t *matchOrInsertionPoint)

    36 {

    37   MOZ_ASSERT(begin <= end);

    39   size_t low = begin;

    40   size_t high = end;

    41   while (low != high) {

    42     size_t middle = low + (high - low) / 2;

    43     const T &middleValue = c[middle];

    45     MOZ_ASSERT(c[low] <= c[middle]);

    46     MOZ_ASSERT(c[middle] <= c[high - 1]);

    47     MOZ_ASSERT(c[low] <= c[high - 1]);

    49     if (target == middleValue) {

    50       *matchOrInsertionPoint = middle;

    51       return true;

    52     }

    54     if (target < middleValue)

    55       high = middle;

    56     else

    57       low = middle + 1;

    58   }

    60   *matchOrInsertionPoint = low;

    61   return false;

    62 }

    64 } // namespace mozilla

    66 #endif // mozilla_BinarySearch_h

The Tor Browser / file revision

mfbt/BinarySearch.h@97036ab72558

mfbt/BinarySearch.h