container/internal/hash_generator_testing.h

0001 // Copyright 2018 The Abseil Authors.
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //      https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014 //
0015 // Generates random values for testing. Specialized only for the few types we
0016 // care about.
0017
0018 #ifndef ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_
0019 #define ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_
0020
0021 #include <stdint.h>
0022
0023 #include <algorithm>
0024 #include <cassert>
0025 #include <iosfwd>
0026 #include <random>
0027 #include <tuple>
0028 #include <type_traits>
0029 #include <utility>
0030 #include <vector>
0031
0032 #include "absl/container/internal/hash_policy_testing.h"
0033 #include "absl/memory/memory.h"
0034 #include "absl/meta/type_traits.h"
0035 #include "absl/strings/string_view.h"
0036
0037 namespace absl {
0038 ABSL_NAMESPACE_BEGIN
0039 namespace container_internal {
0040 namespace hash_internal {
0041 namespace generator_internal {
0042
0043 template <class Container, class = void>
0044 struct IsMap : std::false_type {};
0045
0046 template <class Map>
0047 struct IsMap<Map, absl::void_t<typename Map::mapped_type>> : std::true_type {};
0048
0049 }  // namespace generator_internal
0050
0051 std::mt19937_64* GetSharedRng();
0052
0053 enum Enum {
0054   kEnumEmpty,
0055   kEnumDeleted,
0056 };
0057
0058 enum class EnumClass : uint64_t {
0059   kEmpty,
0060   kDeleted,
0061 };
0062
0063 inline std::ostream& operator<<(std::ostream& o, const EnumClass& ec) {
0064   return o << static_cast<uint64_t>(ec);
0065 }
0066
0067 template <class T, class E = void>
0068 struct Generator;
0069
0070 template <class T>
0071 struct Generator<T, typename std::enable_if<std::is_integral<T>::value>::type> {
0072   T operator()() const {
0073     std::uniform_int_distribution<T> dist;
0074     return dist(*GetSharedRng());
0075   }
0076 };
0077
0078 template <>
0079 struct Generator<Enum> {
0080   Enum operator()() const {
0081     std::uniform_int_distribution<typename std::underlying_type<Enum>::type>
0082         dist;
0083     while (true) {
0084       auto variate = dist(*GetSharedRng());
0085       if (variate != kEnumEmpty && variate != kEnumDeleted)
0086         return static_cast<Enum>(variate);
0087     }
0088   }
0089 };
0090
0091 template <>
0092 struct Generator<EnumClass> {
0093   EnumClass operator()() const {
0094     std::uniform_int_distribution<
0095         typename std::underlying_type<EnumClass>::type>
0096         dist;
0097     while (true) {
0098       EnumClass variate = static_cast<EnumClass>(dist(*GetSharedRng()));
0099       if (variate != EnumClass::kEmpty && variate != EnumClass::kDeleted)
0100         return static_cast<EnumClass>(variate);
0101     }
0102   }
0103 };
0104
0105 template <>
0106 struct Generator<std::string> {
0107   std::string operator()() const;
0108 };
0109
0110 template <>
0111 struct Generator<absl::string_view> {
0112   absl::string_view operator()() const;
0113 };
0114
0115 template <>
0116 struct Generator<NonStandardLayout> {
0117   NonStandardLayout operator()() const {
0118     return NonStandardLayout(Generator<std::string>()());
0119   }
0120 };
0121
0122 template <class K, class V>
0123 struct Generator<std::pair<K, V>> {
0124   std::pair<K, V> operator()() const {
0125     return std::pair<K, V>(Generator<typename std::decay<K>::type>()(),
0126                            Generator<typename std::decay<V>::type>()());
0127   }
0128 };
0129
0130 template <class... Ts>
0131 struct Generator<std::tuple<Ts...>> {
0132   std::tuple<Ts...> operator()() const {
0133     return std::tuple<Ts...>(Generator<typename std::decay<Ts>::type>()()...);
0134   }
0135 };
0136
0137 template <class T>
0138 struct Generator<std::unique_ptr<T>> {
0139   std::unique_ptr<T> operator()() const {
0140     return absl::make_unique<T>(Generator<T>()());
0141   }
0142 };
0143
0144 template <class U>
0145 struct Generator<U, absl::void_t<decltype(std::declval<U&>().key()),
0146                                 decltype(std::declval<U&>().value())>>
0147     : Generator<std::pair<
0148           typename std::decay<decltype(std::declval<U&>().key())>::type,
0149           typename std::decay<decltype(std::declval<U&>().value())>::type>> {};
0150
0151 template <class Container>
0152 using GeneratedType = decltype(
0153     std::declval<const Generator<
0154         typename std::conditional<generator_internal::IsMap<Container>::value,
0155                                   typename Container::value_type,
0156                                   typename Container::key_type>::type>&>()());
0157
0158 // Naive wrapper that performs a linear search of previous values.
0159 // Beware this is O(SQR), which is reasonable for smaller kMaxValues.
0160 template <class T, size_t kMaxValues = 64, class E = void>
0161 struct UniqueGenerator {
0162   Generator<T, E> gen;
0163   std::vector<T> values;
0164
0165   T operator()() {
0166     assert(values.size() < kMaxValues);
0167     for (;;) {
0168       T value = gen();
0169       if (std::find(values.begin(), values.end(), value) == values.end()) {
0170         values.push_back(value);
0171         return value;
0172       }
0173     }
0174   }
0175 };
0176
0177 }  // namespace hash_internal
0178 }  // namespace container_internal
0179 ABSL_NAMESPACE_END
0180 }  // namespace absl
0181
0182 #endif  // ABSL_CONTAINER_INTERNAL_HASH_GENERATOR_TESTING_H_