tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

btree_test.h (4630B)

      1 // Copyright 2018 The Abseil Authors.
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      https://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 #ifndef ABSL_CONTAINER_BTREE_TEST_H_
     16 #define ABSL_CONTAINER_BTREE_TEST_H_
     17 
     18 #include <algorithm>
     19 #include <cassert>
     20 #include <random>
     21 #include <string>
     22 #include <utility>
     23 #include <vector>
     24 
     25 #include "absl/container/btree_map.h"
     26 #include "absl/container/btree_set.h"
     27 #include "absl/container/flat_hash_set.h"
     28 #include "absl/strings/cord.h"
     29 #include "absl/time/time.h"
     30 
     31 namespace absl {
     32 ABSL_NAMESPACE_BEGIN
     33 namespace container_internal {
     34 
     35 // Like remove_const but propagates the removal through std::pair.
     36 template <typename T>
     37 struct remove_pair_const {
     38  using type = typename std::remove_const<T>::type;
     39 };
     40 template <typename T, typename U>
     41 struct remove_pair_const<std::pair<T, U> > {
     42  using type = std::pair<typename remove_pair_const<T>::type,
     43                         typename remove_pair_const<U>::type>;
     44 };
     45 
     46 // Utility class to provide an accessor for a key given a value. The default
     47 // behavior is to treat the value as a pair and return the first element.
     48 template <typename K, typename V>
     49 struct KeyOfValue {
     50  struct type {
     51    const K& operator()(const V& p) const { return p.first; }
     52  };
     53 };
     54 
     55 // Partial specialization of KeyOfValue class for when the key and value are
     56 // the same type such as in set<> and btree_set<>.
     57 template <typename K>
     58 struct KeyOfValue<K, K> {
     59  struct type {
     60    const K& operator()(const K& k) const { return k; }
     61  };
     62 };
     63 
     64 inline char* GenerateDigits(char buf[16], unsigned val, unsigned maxval) {
     65  assert(val <= maxval);
     66  constexpr unsigned kBase = 64;  // avoid integer division.
     67  unsigned p = 15;
     68  buf[p--] = 0;
     69  while (maxval > 0) {
     70    buf[p--] = ' ' + (val % kBase);
     71    val /= kBase;
     72    maxval /= kBase;
     73  }
     74  return buf + p + 1;
     75 }
     76 
     77 template <typename K>
     78 struct Generator {
     79  int maxval;
     80  explicit Generator(int m) : maxval(m) {}
     81  K operator()(int i) const {
     82    assert(i <= maxval);
     83    return K(i);
     84  }
     85 };
     86 
     87 template <>
     88 struct Generator<absl::Time> {
     89  int maxval;
     90  explicit Generator(int m) : maxval(m) {}
     91  absl::Time operator()(int i) const { return absl::FromUnixMillis(i); }
     92 };
     93 
     94 template <>
     95 struct Generator<std::string> {
     96  int maxval;
     97  explicit Generator(int m) : maxval(m) {}
     98  std::string operator()(int i) const {
     99    char buf[16];
    100    return GenerateDigits(buf, i, maxval);
    101  }
    102 };
    103 
    104 template <>
    105 struct Generator<Cord> {
    106  int maxval;
    107  explicit Generator(int m) : maxval(m) {}
    108  Cord operator()(int i) const {
    109    char buf[16];
    110    return Cord(GenerateDigits(buf, i, maxval));
    111  }
    112 };
    113 
    114 template <typename T, typename U>
    115 struct Generator<std::pair<T, U> > {
    116  Generator<typename remove_pair_const<T>::type> tgen;
    117  Generator<typename remove_pair_const<U>::type> ugen;
    118 
    119  explicit Generator(int m) : tgen(m), ugen(m) {}
    120  std::pair<T, U> operator()(int i) const {
    121    return std::make_pair(tgen(i), ugen(i));
    122  }
    123 };
    124 
    125 // Generate n values for our tests and benchmarks. Value range is [0, maxval].
    126 inline std::vector<int> GenerateNumbersWithSeed(int n, int maxval, int seed) {
    127  // NOTE: Some tests rely on generated numbers not changing between test runs.
    128  // We use std::minstd_rand0 because it is well-defined, but don't use
    129  // std::uniform_int_distribution because platforms use different algorithms.
    130  std::minstd_rand0 rng(seed);
    131 
    132  std::vector<int> values;
    133  absl::flat_hash_set<int> unique_values;
    134  if (values.size() < n) {
    135    for (int i = values.size(); i < n; i++) {
    136      int value;
    137      do {
    138        value = static_cast<int>(rng()) % (maxval + 1);
    139      } while (!unique_values.insert(value).second);
    140 
    141      values.push_back(value);
    142    }
    143  }
    144  return values;
    145 }
    146 
    147 // Generates n values in the range [0, maxval].
    148 template <typename V>
    149 std::vector<V> GenerateValuesWithSeed(int n, int maxval, int seed) {
    150  const std::vector<int> nums = GenerateNumbersWithSeed(n, maxval, seed);
    151  Generator<V> gen(maxval);
    152  std::vector<V> vec;
    153 
    154  vec.reserve(n);
    155  for (int i = 0; i < n; i++) {
    156    vec.push_back(gen(nums[i]));
    157  }
    158 
    159  return vec;
    160 }
    161 
    162 }  // namespace container_internal
    163 ABSL_NAMESPACE_END
    164 }  // namespace absl
    165 
    166 #endif  // ABSL_CONTAINER_BTREE_TEST_H_