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