hash_generator_testing.h (4768B)
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 : uint64_t { 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 return static_cast<Enum>(dist(*GetSharedRng())); 84 } 85 }; 86 87 template <> 88 struct Generator<EnumClass> { 89 EnumClass operator()() const { 90 std::uniform_int_distribution< 91 typename std::underlying_type<EnumClass>::type> 92 dist; 93 return static_cast<EnumClass>(dist(*GetSharedRng())); 94 } 95 }; 96 97 template <> 98 struct Generator<std::string> { 99 std::string operator()() const; 100 }; 101 102 template <> 103 struct Generator<absl::string_view> { 104 absl::string_view operator()() const; 105 }; 106 107 template <> 108 struct Generator<NonStandardLayout> { 109 NonStandardLayout operator()() const { 110 return NonStandardLayout(Generator<std::string>()()); 111 } 112 }; 113 114 template <class K, class V> 115 struct Generator<std::pair<K, V>> { 116 std::pair<K, V> operator()() const { 117 return std::pair<K, V>(Generator<typename std::decay<K>::type>()(), 118 Generator<typename std::decay<V>::type>()()); 119 } 120 }; 121 122 template <class... Ts> 123 struct Generator<std::tuple<Ts...>> { 124 std::tuple<Ts...> operator()() const { 125 return std::tuple<Ts...>(Generator<typename std::decay<Ts>::type>()()...); 126 } 127 }; 128 129 template <class T> 130 struct Generator<std::unique_ptr<T>> { 131 std::unique_ptr<T> operator()() const { 132 return absl::make_unique<T>(Generator<T>()()); 133 } 134 }; 135 136 template <class U> 137 struct Generator<U, absl::void_t<decltype(std::declval<U&>().key()), 138 decltype(std::declval<U&>().value())>> 139 : Generator<std::pair< 140 typename std::decay<decltype(std::declval<U&>().key())>::type, 141 typename std::decay<decltype(std::declval<U&>().value())>::type>> {}; 142 143 template <class Container> 144 using GeneratedType = decltype( 145 std::declval<const Generator< 146 typename std::conditional<generator_internal::IsMap<Container>::value, 147 typename Container::value_type, 148 typename Container::key_type>::type>&>()()); 149 150 // Naive wrapper that performs a linear search of previous values. 151 // Beware this is O(SQR), which is reasonable for smaller kMaxValues. 152 template <class T, size_t kMaxValues = 64, class E = void> 153 struct UniqueGenerator { 154 Generator<T, E> gen; 155 std::vector<T> values; 156 157 T operator()() { 158 assert(values.size() < kMaxValues); 159 for (;;) { 160 T value = gen(); 161 if (std::find(values.begin(), values.end(), value) == values.end()) { 162 values.push_back(value); 163 return value; 164 } 165 } 166 } 167 }; 168 169 } // namespace hash_internal 170 } // namespace container_internal 171 ABSL_NAMESPACE_END 172 } // namespace absl 173 174 #endif // ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_