hash_policy_testing.h (5356B)
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 // Utilities to help tests verify that hash tables properly handle stateful 16 // allocators and hash functions. 17 18 #ifndef ABSL_CONTAINER_INTERNAL_HASH_POLICY_TESTING_H_ 19 #define ABSL_CONTAINER_INTERNAL_HASH_POLICY_TESTING_H_ 20 21 #include <cstdlib> 22 #include <limits> 23 #include <memory> 24 #include <ostream> 25 #include <type_traits> 26 #include <utility> 27 #include <vector> 28 29 #include "absl/hash/hash.h" 30 #include "absl/strings/string_view.h" 31 32 namespace absl { 33 ABSL_NAMESPACE_BEGIN 34 namespace container_internal { 35 namespace hash_testing_internal { 36 37 template <class Derived> 38 struct WithId { 39 WithId() : id_(next_id<Derived>()) {} 40 WithId(const WithId& that) : id_(that.id_) {} 41 WithId(WithId&& that) : id_(that.id_) { that.id_ = 0; } 42 WithId& operator=(const WithId& that) { 43 id_ = that.id_; 44 return *this; 45 } 46 WithId& operator=(WithId&& that) { 47 id_ = that.id_; 48 that.id_ = 0; 49 return *this; 50 } 51 52 size_t id() const { return id_; } 53 54 friend bool operator==(const WithId& a, const WithId& b) { 55 return a.id_ == b.id_; 56 } 57 friend bool operator!=(const WithId& a, const WithId& b) { return !(a == b); } 58 59 protected: 60 explicit WithId(size_t id) : id_(id) {} 61 62 private: 63 size_t id_; 64 65 template <class T> 66 static size_t next_id() { 67 // 0 is reserved for moved from state. 68 static size_t gId = 1; 69 return gId++; 70 } 71 }; 72 73 } // namespace hash_testing_internal 74 75 struct NonStandardLayout { 76 NonStandardLayout() {} 77 explicit NonStandardLayout(std::string s) : value(std::move(s)) {} 78 virtual ~NonStandardLayout() {} 79 80 friend bool operator==(const NonStandardLayout& a, 81 const NonStandardLayout& b) { 82 return a.value == b.value; 83 } 84 friend bool operator!=(const NonStandardLayout& a, 85 const NonStandardLayout& b) { 86 return a.value != b.value; 87 } 88 89 template <typename H> 90 friend H AbslHashValue(H h, const NonStandardLayout& v) { 91 return H::combine(std::move(h), v.value); 92 } 93 94 std::string value; 95 }; 96 97 struct StatefulTestingHash 98 : absl::container_internal::hash_testing_internal::WithId< 99 StatefulTestingHash> { 100 template <class T> 101 size_t operator()(const T& t) const { 102 return absl::Hash<T>{}(t); 103 } 104 }; 105 106 struct StatefulTestingEqual 107 : absl::container_internal::hash_testing_internal::WithId< 108 StatefulTestingEqual> { 109 template <class T, class U> 110 bool operator()(const T& t, const U& u) const { 111 return t == u; 112 } 113 }; 114 115 // It is expected that Alloc() == Alloc() for all allocators so we cannot use 116 // WithId base. We need to explicitly assign ids. 117 template <class T = int> 118 struct Alloc : std::allocator<T> { 119 using propagate_on_container_swap = std::true_type; 120 121 // Using old paradigm for this to ensure compatibility. 122 explicit Alloc(size_t id = 0) : id_(id) {} 123 124 Alloc(const Alloc&) = default; 125 Alloc& operator=(const Alloc&) = default; 126 127 template <class U> 128 Alloc(const Alloc<U>& that) : std::allocator<T>(that), id_(that.id()) {} 129 130 template <class U> 131 struct rebind { 132 using other = Alloc<U>; 133 }; 134 135 size_t id() const { return id_; } 136 137 friend bool operator==(const Alloc& a, const Alloc& b) { 138 return a.id_ == b.id_; 139 } 140 friend bool operator!=(const Alloc& a, const Alloc& b) { return !(a == b); } 141 142 private: 143 size_t id_ = (std::numeric_limits<size_t>::max)(); 144 }; 145 146 template <class Map> 147 auto items(const Map& m) -> std::vector< 148 std::pair<typename Map::key_type, typename Map::mapped_type>> { 149 using std::get; 150 std::vector<std::pair<typename Map::key_type, typename Map::mapped_type>> res; 151 res.reserve(m.size()); 152 for (const auto& v : m) res.emplace_back(get<0>(v), get<1>(v)); 153 return res; 154 } 155 156 template <class Set> 157 auto keys(const Set& s) 158 -> std::vector<typename std::decay<typename Set::key_type>::type> { 159 std::vector<typename std::decay<typename Set::key_type>::type> res; 160 res.reserve(s.size()); 161 for (const auto& v : s) res.emplace_back(v); 162 return res; 163 } 164 165 } // namespace container_internal 166 ABSL_NAMESPACE_END 167 } // namespace absl 168 169 // ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS is false for glibcxx versions 170 // where the unordered containers are missing certain constructors that 171 // take allocator arguments. This test is defined ad-hoc for the platforms 172 // we care about (notably Crosstool 17) because libstdcxx's useless 173 // versioning scheme precludes a more principled solution. 174 // From GCC-4.9 Changelog: (src: https://gcc.gnu.org/gcc-4.9/changes.html) 175 // "the unordered associative containers in <unordered_map> and <unordered_set> 176 // meet the allocator-aware container requirements;" 177 #if defined(__GLIBCXX__) && __GLIBCXX__ <= 20140425 178 #define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 0 179 #else 180 #define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 1 181 #endif 182 183 #endif // ABSL_CONTAINER_INTERNAL_HASH_POLICY_TESTING_H_