| 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 |
#ifndef THIS_HASH_MAP |
| 16 |
#define THIS_HASH_MAP flat_hash_map |
| 17 |
#define THIS_TEST_NAME FlatHashMap |
| 18 |
#define ORIG_FLAT_HASH_MAP 1 |
| 19 |
#endif |
| 20 |
|
| 21 |
#ifndef THIS_EXTRA_TPL_PARAMS |
| 22 |
#define THIS_EXTRA_TPL_PARAMS |
| 23 |
#endif |
| 24 |
|
| 25 |
#ifndef THIS_EXTRA_TPL_PARAMS_NULLMUTEX |
| 26 |
#define THIS_EXTRA_TPL_PARAMS_NULLMUTEX |
| 27 |
#endif |
| 28 |
|
| 29 |
#include "parallel_hashmap/phmap.h" |
| 30 |
|
| 31 |
#if defined(PHMAP_HAVE_STD_ANY) |
| 32 |
#include <any> |
| 33 |
#endif |
| 34 |
|
| 35 |
#ifdef _MSC_VER |
| 36 |
#pragma warning(push) |
| 37 |
#pragma warning(disable: 4710 4711) |
| 38 |
#endif |
| 39 |
|
| 40 |
#include "hash_generator_testing.h" |
| 41 |
#include "unordered_map_constructor_test.h" |
| 42 |
#include "unordered_map_lookup_test.h" |
| 43 |
#include "unordered_map_members_test.h" |
| 44 |
#include "unordered_map_modifiers_test.h" |
| 45 |
|
| 46 |
#ifdef _MSC_VER |
| 47 |
#pragma warning(pop) |
| 48 |
#endif |
| 49 |
|
| 50 |
namespace phmap { |
| 51 |
namespace priv { |
| 52 |
namespace { |
| 53 |
using ::phmap::priv::hash_internal::Enum; |
| 54 |
using ::phmap::priv::hash_internal::EnumClass; |
| 55 |
using ::testing::_; |
| 56 |
using ::testing::Pair; |
| 57 |
using ::testing::UnorderedElementsAre; |
| 58 |
|
| 59 |
template <class K, class V> |
| 60 |
using Map = THIS_HASH_MAP<K, V, StatefulTestingHash, StatefulTestingEqual, |
| 61 |
Alloc<std::pair<const K, V>> THIS_EXTRA_TPL_PARAMS>; |
| 62 |
|
| 63 |
|
| 64 |
template <class K, class V, class H = phmap::priv::hash_default_hash<K>, |
| 65 |
class Eq = phmap::priv::hash_default_eq<K>, |
| 66 |
class Alloc = phmap::priv::Allocator< |
| 67 |
phmap::priv::Pair<const K, V>>> |
| 68 |
using ThisMap = THIS_HASH_MAP<K, V, H, Eq, Alloc THIS_EXTRA_TPL_PARAMS>; |
| 69 |
|
| 70 |
template <class K, class V, class H = phmap::priv::hash_default_hash<K>, |
| 71 |
class Eq = phmap::priv::hash_default_eq<K>, |
| 72 |
class Alloc = phmap::priv::Allocator< |
| 73 |
phmap::priv::Pair<const K, V>>> |
| 74 |
using ThisMap_NullMutex = THIS_HASH_MAP<K, V, H, Eq, Alloc THIS_EXTRA_TPL_PARAMS_NULLMUTEX>; |
| 75 |
|
| 76 |
static_assert(!std::is_standard_layout<NonStandardLayout>(), ""); |
| 77 |
|
| 78 |
using MapTypes = |
| 79 |
::testing::Types<Map<int, int>, Map<std::string, int>, |
| 80 |
Map<Enum, std::string>, Map<EnumClass, int>, |
| 81 |
Map<int, NonStandardLayout>, Map<NonStandardLayout, int>>; |
| 82 |
|
| 83 |
INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, ConstructorTest, MapTypes); |
| 84 |
INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, LookupTest, MapTypes); |
| 85 |
INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, MembersTest, MapTypes); |
| 86 |
INSTANTIATE_TYPED_TEST_SUITE_P(THIS_TEST_NAME, ModifiersTest, MapTypes); |
| 87 |
|
| 88 |
|
| 89 |
|
| 90 |
TEST(THIS_TEST_NAME, StandardLayout) { |
| 91 |
struct Int { |
| 92 |
explicit Int(size_t val) : value(val) {} |
| 93 |
Int() : value(0) { ADD_FAILURE(); } |
| 94 |
Int(const Int& other) : value(other.value) { ADD_FAILURE(); } |
| 95 |
Int(Int&&) = default; |
| 96 |
bool operator==(const Int& other) const { return value == other.value; } |
| 97 |
size_t value; |
| 98 |
}; |
| 99 |
static_assert(std::is_standard_layout<Int>(), ""); |
| 100 |
|
| 101 |
struct Hash { |
| 102 |
size_t operator()(const Int& obj) const { return obj.value; } |
| 103 |
}; |
| 104 |
|
| 105 |
// Verify that neither the key nor the value get default-constructed or |
| 106 |
// copy-constructed. |
| 107 |
{ |
| 108 |
ThisMap<Int, Int, Hash> m; |
| 109 |
m.try_emplace(Int(1), Int(2)); |
| 110 |
m.try_emplace(Int(3), Int(4)); |
| 111 |
m.erase(Int(1)); |
| 112 |
m.rehash(2 * m.bucket_count()); |
| 113 |
} |
| 114 |
{ |
| 115 |
ThisMap<Int, Int, Hash> m; |
| 116 |
m.try_emplace(Int(1), Int(2)); |
| 117 |
m.try_emplace(Int(3), Int(4)); |
| 118 |
m.erase(Int(1)); |
| 119 |
m.clear(); |
| 120 |
} |
| 121 |
} |
| 122 |
|
| 123 |
// gcc becomes unhappy if this is inside the method, so pull it out here. |
| 124 |
struct balast {}; |
| 125 |
|
| 126 |
TEST(THIS_TEST_NAME, IteratesMsan) { |
| 127 |
// Because SwissTable randomizes on pointer addresses, we keep old tables |
| 128 |
// around to ensure we don't reuse old memory. |
| 129 |
std::vector<ThisMap<int, balast>> garbage; |
| 130 |
for (int i = 0; i < 100; ++i) { |
| 131 |
ThisMap<int, balast> t; |
| 132 |
for (int j = 0; j < 100; ++j) { |
| 133 |
t[j]; |
| 134 |
for (const auto& p : t) EXPECT_THAT(p, Pair(_, _)); |
| 135 |
} |
| 136 |
garbage.push_back(std::move(t)); |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
// Demonstration of the "Lazy Key" pattern. This uses heterogeneous insert to |
| 141 |
// avoid creating expensive key elements when the item is already present in the |
| 142 |
// map. |
| 143 |
struct LazyInt { |
| 144 |
explicit LazyInt(size_t val, int* tracker_) |
| 145 |
: value(val), tracker(tracker_) {} |
| 146 |
|
| 147 |
explicit operator size_t() const { |
| 148 |
++*tracker; |
| 149 |
return value; |
| 150 |
} |
| 151 |
|
| 152 |
size_t value; |
| 153 |
int* tracker; |
| 154 |
}; |
| 155 |
|
| 156 |
struct Hash { |
| 157 |
using is_transparent = void; |
| 158 |
int* tracker; |
| 159 |
size_t operator()(size_t obj) const { |
| 160 |
++*tracker; |
| 161 |
return obj; |
| 162 |
} |
| 163 |
size_t operator()(const LazyInt& obj) const { |
| 164 |
++*tracker; |
| 165 |
return obj.value; |
| 166 |
} |
| 167 |
}; |
| 168 |
|
| 169 |
struct Eq { |
| 170 |
using is_transparent = void; |
| 171 |
bool operator()(size_t lhs, size_t rhs) const { |
| 172 |
return lhs == rhs; |
| 173 |
} |
| 174 |
bool operator()(size_t lhs, const LazyInt& rhs) const { |
| 175 |
return lhs == rhs.value; |
| 176 |
} |
| 177 |
}; |
| 178 |
|
| 179 |
TEST(THIS_TEST_NAME, PtrKet) { |
| 180 |
using H = ThisMap<void *, bool>; |
| 181 |
H hash; |
| 182 |
int a, b; |
| 183 |
hash.insert(H::value_type(&a, true)); |
| 184 |
hash.insert(H::value_type(&b, false)); |
| 185 |
} |
| 186 |
|
| 187 |
TEST(THIS_TEST_NAME, LazyKeyPattern) { |
| 188 |
// hashes are only guaranteed in opt mode, we use assertions to track internal |
| 189 |
// state that can cause extra calls to hash. |
| 190 |
int conversions = 0; |
| 191 |
int hashes = 0; |
| 192 |
ThisMap<size_t, size_t, Hash, Eq> m(0, Hash{&hashes}); |
| 193 |
m.reserve(3); |
| 194 |
|
| 195 |
m[LazyInt(1, &conversions)] = 1; |
| 196 |
EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 1))); |
| 197 |
EXPECT_EQ(conversions, 1); |
| 198 |
#ifdef NDEBUG |
| 199 |
EXPECT_EQ(hashes, 1); |
| 200 |
#endif |
| 201 |
|
| 202 |
m[LazyInt(1, &conversions)] = 2; |
| 203 |
EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2))); |
| 204 |
EXPECT_EQ(conversions, 1); |
| 205 |
#ifdef NDEBUG |
| 206 |
EXPECT_EQ(hashes, 2); |
| 207 |
#endif |
| 208 |
|
| 209 |
m.try_emplace(LazyInt(2, &conversions), 3); |
| 210 |
EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2), Pair(2, 3))); |
| 211 |
EXPECT_EQ(conversions, 2); |
| 212 |
#if defined(NDEBUG) && ORIG_FLAT_HASH_MAP |
| 213 |
// for parallel maps, the reserve(3) above is not sufficient to guarantee that a submap will not resize and therefore rehash |
| 214 |
EXPECT_EQ(hashes, 3); |
| 215 |
#endif |
| 216 |
|
| 217 |
m.try_emplace(LazyInt(2, &conversions), 4); |
| 218 |
EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 2), Pair(2, 3))); |
| 219 |
EXPECT_EQ(conversions, 2); |
| 220 |
#if defined(NDEBUG) && ORIG_FLAT_HASH_MAP |
| 221 |
// for parallel maps, the reserve(3) above is not sufficient to guarantee that a submap will not resize and therefore rehash |
| 222 |
EXPECT_EQ(hashes, 4); |
| 223 |
#endif |
| 224 |
} |
| 225 |
|
| 226 |
TEST(THIS_TEST_NAME, BitfieldArgument) { |
| 227 |
union { |
| 228 |
int n : 1; |
| 229 |
}; |
| 230 |
n = 0; |
| 231 |
ThisMap<int, int> m; |
| 232 |
m.erase(n); |
| 233 |
m.count(n); |
| 234 |
m.prefetch(n); |
| 235 |
m.find(n); |
| 236 |
m.contains(n); |
| 237 |
m.equal_range(n); |
| 238 |
m.insert_or_assign(n, n); |
| 239 |
m.insert_or_assign(m.end(), n, n); |
| 240 |
m.try_emplace(n); |
| 241 |
m.try_emplace(m.end(), n); |
| 242 |
m.at(n); |
| 243 |
m[n]; |
| 244 |
} |
| 245 |
|
| 246 |
TEST(THIS_TEST_NAME, MergeExtractInsert) { |
| 247 |
// We can't test mutable keys, or non-copyable keys with ThisMap. |
| 248 |
// Test that the nodes have the proper API. |
| 249 |
ThisMap<int, int> m = {{1, 7}, {2, 9}}; |
| 250 |
auto node = m.extract(1); |
| 251 |
EXPECT_TRUE(node); |
| 252 |
EXPECT_EQ(node.key(), 1); |
| 253 |
EXPECT_EQ(node.mapped(), 7); |
| 254 |
EXPECT_THAT(m, UnorderedElementsAre(Pair(2, 9))); |
| 255 |
|
| 256 |
node.mapped() = 17; |
| 257 |
m.insert(std::move(node)); |
| 258 |
EXPECT_THAT(m, UnorderedElementsAre(Pair(1, 17), Pair(2, 9))); |
| 259 |
} |
| 260 |
|
| 261 |
#if 0 && !defined(__ANDROID__) && !defined(__APPLE__) && !defined(__EMSCRIPTEN__) && defined(PHMAP_HAVE_STD_ANY) |
| 262 |
TEST(THIS_TEST_NAME, Any) { |
| 263 |
ThisMap<int, std::any> m; |
| 264 |
m.emplace(1, 7); |
| 265 |
auto it = m.find(1); |
| 266 |
ASSERT_NE(it, m.end()); |
| 267 |
EXPECT_EQ(7, std::any_cast<int>(it->second)); |
| 268 |
|
| 269 |
m.emplace(std::piecewise_construct, std::make_tuple(2), std::make_tuple(8)); |
| 270 |
it = m.find(2); |
| 271 |
ASSERT_NE(it, m.end()); |
| 272 |
EXPECT_EQ(8, std::any_cast<int>(it->second)); |
| 273 |
|
| 274 |
m.emplace(std::piecewise_construct, std::make_tuple(3), |
| 275 |
std::make_tuple(std::any(9))); |
| 276 |
it = m.find(3); |
| 277 |
ASSERT_NE(it, m.end()); |
| 278 |
EXPECT_EQ(9, std::any_cast<int>(it->second)); |
| 279 |
|
| 280 |
struct H { |
| 281 |
size_t operator()(const std::any&) const { return 0; } |
| 282 |
}; |
| 283 |
struct E { |
| 284 |
bool operator()(const std::any&, const std::any&) const { return true; } |
| 285 |
}; |
| 286 |
ThisMap<std::any, int, H, E> m2; |
| 287 |
m2.emplace(1, 7); |
| 288 |
auto it2 = m2.find(1); |
| 289 |
ASSERT_NE(it2, m2.end()); |
| 290 |
EXPECT_EQ(7, it2->second); |
| 291 |
} |
| 292 |
#endif // __ANDROID__ |
| 293 |
|
| 294 |
} // namespace |
| 295 |
} // namespace priv |
| 296 |
} // namespace phmap |