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/time/time.h" 29 30 namespace absl { 31 ABSL_NAMESPACE_BEGIN 32 namespace container_internal { 33 34 // Like remove_const but propagates the removal through std::pair. 35 template <typename T> 36 struct remove_pair_const { 37 using type = typename std::remove_const<T>::type; 38 }; 39 template <typename T, typename U> 40 struct remove_pair_const<std::pair<T, U> > { 41 using type = std::pair<typename remove_pair_const<T>::type, 42 typename remove_pair_const<U>::type>; 43 }; 44 45 // Utility class to provide an accessor for a key given a value. The default 46 // behavior is to treat the value as a pair and return the first element. 47 template <typename K, typename V> 48 struct KeyOfValue { 49 struct type { 50 const K& operator()(const V& p) const { return p.first; } 51 }; 52 }; 53 54 // Partial specialization of KeyOfValue class for when the key and value are 55 // the same type such as in set<> and btree_set<>. 56 template <typename K> 57 struct KeyOfValue<K, K> { 58 struct type { 59 const K& operator()(const K& k) const { return k; } 60 }; 61 }; 62 63 inline char* GenerateDigits(char buf[16], unsigned val, unsigned maxval) { 64 assert(val <= maxval); 65 constexpr unsigned kBase = 64; // avoid integer division. 66 unsigned p = 15; 67 buf[p--] = 0; 68 while (maxval > 0) { 69 buf[p--] = ' ' + (val % kBase); 70 val /= kBase; 71 maxval /= kBase; 72 } 73 return buf + p + 1; 74 } 75 76 template <typename K> 77 struct Generator { 78 int maxval; 79 explicit Generator(int m) : maxval(m) {} 80 K operator()(int i) const { 81 assert(i <= maxval); 82 return K(i); 83 } 84 }; 85 86 template <> 87 struct Generator<absl::Time> { 88 int maxval; 89 explicit Generator(int m) : maxval(m) {} 90 absl::Time operator()(int i) const { return absl::FromUnixMillis(i); } 91 }; 92 93 template <> 94 struct Generator<std::string> { 95 int maxval; 96 explicit Generator(int m) : maxval(m) {} 97 std::string operator()(int i) const { 98 char buf[16]; 99 return GenerateDigits(buf, i, maxval); 100 } 101 }; 102 103 template <typename T, typename U> 104 struct Generator<std::pair<T, U> > { 105 Generator<typename remove_pair_const<T>::type> tgen; 106 Generator<typename remove_pair_const<U>::type> ugen; 107 108 explicit Generator(int m) : tgen(m), ugen(m) {} 109 std::pair<T, U> operator()(int i) const { 110 return std::make_pair(tgen(i), ugen(i)); 111 } 112 }; 113 114 // Generate n values for our tests and benchmarks. Value range is [0, maxval]. 115 inline std::vector<int> GenerateNumbersWithSeed(int n, int maxval, int seed) { 116 // NOTE: Some tests rely on generated numbers not changing between test runs. 117 // We use std::minstd_rand0 because it is well-defined, but don't use 118 // std::uniform_int_distribution because platforms use different algorithms. 119 std::minstd_rand0 rng(seed); 120 121 std::vector<int> values; 122 absl::flat_hash_set<int> unique_values; 123 if (values.size() < n) { 124 for (int i = values.size(); i < n; i++) { 125 int value; 126 do { 127 value = static_cast<int>(rng()) % (maxval + 1); 128 } while (!unique_values.insert(value).second); 129 130 values.push_back(value); 131 } 132 } 133 return values; 134 } 135 136 // Generates n values in the range [0, maxval]. 137 template <typename V> 138 std::vector<V> GenerateValuesWithSeed(int n, int maxval, int seed) { 139 const std::vector<int> nums = GenerateNumbersWithSeed(n, maxval, seed); 140 Generator<V> gen(maxval); 141 std::vector<V> vec; 142 143 vec.reserve(n); 144 for (int i = 0; i < n; i++) { 145 vec.push_back(gen(nums[i])); 146 } 147 148 return vec; 149 } 150 151 } // namespace container_internal 152 ABSL_NAMESPACE_END 153 } // namespace absl 154 155 #endif // ABSL_CONTAINER_BTREE_TEST_H_ 156