| 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_ |