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 // Generates random values for testing. Specialized only for the few types we 16 // care about. 17 18 #ifndef ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_ 19 #define ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_ 20 21 #include <stdint.h> 22 23 #include <algorithm> 24 #include <cassert> 25 #include <iosfwd> 26 #include <random> 27 #include <tuple> 28 #include <type_traits> 29 #include <utility> 30 #include <vector> 31 32 #include "absl/container/internal/hash_policy_testing.h" 33 #include "absl/memory/memory.h" 34 #include "absl/meta/type_traits.h" 35 #include "absl/strings/string_view.h" 36 37 namespace absl { 38 ABSL_NAMESPACE_BEGIN 39 namespace container_internal { 40 namespace hash_internal { 41 namespace generator_internal { 42 43 template <class Container, class = void> 44 struct IsMap : std::false_type {}; 45 46 template <class Map> 47 struct IsMap<Map, absl::void_t<typename Map::mapped_type>> : std::true_type {}; 48 49 } // namespace generator_internal 50 51 std::mt19937_64* GetSharedRng(); 52 53 enum Enum { 54 kEnumEmpty, 55 kEnumDeleted, 56 }; 57 58 enum class EnumClass : uint64_t { 59 kEmpty, 60 kDeleted, 61 }; 62 63 inline std::ostream& operator<<(std::ostream& o, const EnumClass& ec) { 64 return o << static_cast<uint64_t>(ec); 65 } 66 67 template <class T, class E = void> 68 struct Generator; 69 70 template <class T> 71 struct Generator<T, typename std::enable_if<std::is_integral<T>::value>::type> { 72 T operator()() const { 73 std::uniform_int_distribution<T> dist; 74 return dist(*GetSharedRng()); 75 } 76 }; 77 78 template <> 79 struct Generator<Enum> { 80 Enum operator()() const { 81 std::uniform_int_distribution<typename std::underlying_type<Enum>::type> 82 dist; 83 while (true) { 84 auto variate = dist(*GetSharedRng()); 85 if (variate != kEnumEmpty && variate != kEnumDeleted) 86 return static_cast<Enum>(variate); 87 } 88 } 89 }; 90 91 template <> 92 struct Generator<EnumClass> { 93 EnumClass operator()() const { 94 std::uniform_int_distribution< 95 typename std::underlying_type<EnumClass>::type> 96 dist; 97 while (true) { 98 EnumClass variate = static_cast<EnumClass>(dist(*GetSharedRng())); 99 if (variate != EnumClass::kEmpty && variate != EnumClass::kDeleted) 100 return static_cast<EnumClass>(variate); 101 } 102 } 103 }; 104 105 template <> 106 struct Generator<std::string> { 107 std::string operator()() const; 108 }; 109 110 template <> 111 struct Generator<absl::string_view> { 112 absl::string_view operator()() const; 113 }; 114 115 template <> 116 struct Generator<NonStandardLayout> { 117 NonStandardLayout operator()() const { 118 return NonStandardLayout(Generator<std::string>()()); 119 } 120 }; 121 122 template <class K, class V> 123 struct Generator<std::pair<K, V>> { 124 std::pair<K, V> operator()() const { 125 return std::pair<K, V>(Generator<typename std::decay<K>::type>()(), 126 Generator<typename std::decay<V>::type>()()); 127 } 128 }; 129 130 template <class... Ts> 131 struct Generator<std::tuple<Ts...>> { 132 std::tuple<Ts...> operator()() const { 133 return std::tuple<Ts...>(Generator<typename std::decay<Ts>::type>()()...); 134 } 135 }; 136 137 template <class T> 138 struct Generator<std::unique_ptr<T>> { 139 std::unique_ptr<T> operator()() const { 140 return absl::make_unique<T>(Generator<T>()()); 141 } 142 }; 143 144 template <class U> 145 struct Generator<U, absl::void_t<decltype(std::declval<U&>().key()), 146 decltype(std::declval<U&>().value())>> 147 : Generator<std::pair< 148 typename std::decay<decltype(std::declval<U&>().key())>::type, 149 typename std::decay<decltype(std::declval<U&>().value())>::type>> {}; 150 151 template <class Container> 152 using GeneratedType = decltype( 153 std::declval<const Generator< 154 typename std::conditional<generator_internal::IsMap<Container>::value, 155 typename Container::value_type, 156 typename Container::key_type>::type>&>()()); 157 158 // Naive wrapper that performs a linear search of previous values. 159 // Beware this is O(SQR), which is reasonable for smaller kMaxValues. 160 template <class T, size_t kMaxValues = 64, class E = void> 161 struct UniqueGenerator { 162 Generator<T, E> gen; 163 std::vector<T> values; 164 165 T operator()() { 166 assert(values.size() < kMaxValues); 167 for (;;) { 168 T value = gen(); 169 if (std::find(values.begin(), values.end(), value) == values.end()) { 170 values.push_back(value); 171 return value; 172 } 173 } 174 } 175 }; 176 177 } // namespace hash_internal 178 } // namespace container_internal 179 ABSL_NAMESPACE_END 180 } // namespace absl 181 182 #endif // ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_ 183