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 {
WithIdWithId39   WithId() : id_(next_id<Derived>()) {}
WithIdWithId40   WithId(const WithId& that) : id_(that.id_) {}
WithIdWithId41   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 
idWithId52   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:
WithIdWithId60   explicit WithId(size_t id) : id_(id) {}
61 
62  private:
63   size_t id_;
64 
65   template <class T>
next_idWithId66   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 {
NonStandardLayoutNonStandardLayout76   NonStandardLayout() {}
NonStandardLayoutNonStandardLayout77   explicit NonStandardLayout(std::string s) : value(std::move(s)) {}
~NonStandardLayoutNonStandardLayout78   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>
AbslHashValueNonStandardLayout90   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>
operatorStatefulTestingHash101   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>
operatorStatefulTestingEqual110   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.
id_Alloc122   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>
AllocAlloc128   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 
idAlloc135   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 ( __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 9 ))
179 #define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 0
180 #else
181 #define ABSL_UNORDERED_SUPPORTS_ALLOC_CTORS 1
182 #endif
183 
184 #endif  // ABSL_CONTAINER_INTERNAL_HASH_POLICY_TESTING_H_
185