Debian Codegraph @

tests/hash_policy_testing.h

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