1 static const char help[] = "Tests UnorderedMap.\n";
2
3 #include <petsc/private/cpp/unordered_map.hpp>
4 #include <petscviewer.h>
5
6 #include <sstream> // std::ostringstream
7 #include <string>
8 #include <vector>
9 #include <algorithm> // std::sort
10
11 // ==========================================================================================
12 // Setup
13 // ==========================================================================================
14
15 // see https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x
hash_combine(std::size_t &)16 static inline void hash_combine(std::size_t &) noexcept { }
17
18 template <typename T, typename... Rest>
hash_combine(std::size_t & seed,const T & v,Rest &&...rest)19 static inline void hash_combine(std::size_t &seed, const T &v, Rest &&...rest) noexcept
20 {
21 std::hash<T> hasher;
22 seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
23 hash_combine(seed, std::forward<Rest>(rest)...);
24 }
25
26 #define MAKE_HASHABLE(type, ...) \
27 namespace std \
28 { \
29 template <> \
30 struct hash<type> { \
31 std::size_t operator()(const type &t) const noexcept \
32 { \
33 std::size_t ret = 0; \
34 hash_combine(ret, __VA_ARGS__); \
35 return ret; \
36 } \
37 }; \
38 }
39
40 using pair_type = std::pair<int, double>;
41 MAKE_HASHABLE(pair_type, t.first, t.second)
42
43 using namespace Petsc::util;
44
45 struct Foo {
46 int x{};
47 double y{};
48
49 constexpr Foo() noexcept = default;
FooFoo50 constexpr Foo(int x, double y) noexcept : x(x), y(y) { }
51
operator ==Foo52 bool operator==(const Foo &other) const noexcept { return x == other.x && y == other.y; }
operator !=Foo53 bool operator!=(const Foo &other) const noexcept { return !(*this == other); }
operator <Foo54 bool operator<(const Foo &other) const noexcept { return std::tie(x, y) < std::tie(other.x, other.y); }
55
to_stringFoo56 PetscErrorCode to_string(std::string &buf) const noexcept
57 {
58 PetscFunctionBegin;
59 PetscCallCXX(buf = std::to_string(x) + ", " + std::to_string(y));
60 PetscFunctionReturn(PETSC_SUCCESS);
61 }
62
operator <<(std::ostream & oss,const Foo & f)63 friend std::ostream &operator<<(std::ostream &oss, const Foo &f) noexcept
64 {
65 std::string ret;
66
67 PetscFunctionBegin;
68 PetscCallAbort(PETSC_COMM_SELF, f.to_string(ret));
69 oss << ret;
70 PetscFunctionReturn(oss);
71 }
72 };
73
74 MAKE_HASHABLE(Foo, t.x, t.y)
75
76 struct Bar {
77 std::vector<int> x{};
78 std::string y{};
79
80 Bar() noexcept = default;
BarBar81 Bar(std::vector<int> x, std::string y) noexcept : x(std::move(x)), y(std::move(y)) { }
82
operator ==Bar83 bool operator==(const Bar &other) const noexcept { return x == other.x && y == other.y; }
operator <Bar84 bool operator<(const Bar &other) const noexcept { return std::tie(x, y) < std::tie(other.x, other.y); }
85
to_stringBar86 PetscErrorCode to_string(std::string &buf) const noexcept
87 {
88 PetscFunctionBegin;
89 PetscCallCXX(buf = '<');
90 for (std::size_t i = 0; i < x.size(); ++i) {
91 PetscCallCXX(buf += std::to_string(x[i]));
92 if (i + 1 != x.size()) PetscCallCXX(buf += ", ");
93 }
94 PetscCallCXX(buf += ">, <" + y + '>');
95 PetscFunctionReturn(PETSC_SUCCESS);
96 }
97
operator <<(std::ostream & oss,const Bar & b)98 friend std::ostream &operator<<(std::ostream &oss, const Bar &b) noexcept
99 {
100 std::string ret;
101
102 PetscFunctionBegin;
103 PetscCallAbort(PETSC_COMM_SELF, b.to_string(ret));
104 oss << ret;
105 PetscFunctionReturn(oss);
106 }
107 };
108
109 struct BadHash {
110 template <typename T>
operator ()BadHash111 constexpr std::size_t operator()(const T &) const noexcept
112 {
113 return 1;
114 }
115 };
116
117 template <typename T>
118 struct Printer {
119 using signature = PetscErrorCode(const T &, std::string &);
120
121 mutable std::string buffer;
122 std::function<signature> printer;
123
124 template <typename F>
PrinterPrinter125 Printer(F &&printer) noexcept : printer(std::forward<F>(printer))
126 {
127 }
128
operator ()Printer129 PETSC_NODISCARD const char *operator()(const T &value) const noexcept
130 {
131 PetscFunctionBegin;
132 PetscCallAbort(PETSC_COMM_SELF, this->printer(value, this->buffer));
133 PetscFunctionReturn(this->buffer.c_str());
134 }
135 };
136
137 #if defined(__GNUC__)
138 // gcc 6.4 through 7.5 have a visibility bug:
139 //
140 // error: 'MapTester<T>::test_insert()::<lambda(MapTester<T>::value_type&)> [with T =
141 // ...]::<lambda(...)>' declared with greater visibility than the type of its field
142 // 'MapTester<T>::test_insert()::<lambda(MapTester<T>::value_type&)> [with T =
143 // ...]::<lambda(const char*, const insert_return_type&)
144 //
145 // Error message implies that the visibility of the lambda in question is greater than the
146 // visibility of the capture list value "this".
147 //
148 // Since lambdas are translated into the classes with the operator()(...) and (it seems like)
149 // captured values are translated into the fields of this class it looks like for some reason
150 // the visibility of that class is higher than the one of those fields.
151 //
152 // see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80947
153 #if ((__GNUC__ == 6) && (__GNUC_MINOR__ >= 4)) || ((__GNUC__ == 7) && (__GNUC_MINOR__ <= 5))
154 #define PETSC_GCC_LAMBDA_VISIBILITY_WORKAROUND 1
155 #endif
156 #endif
157
158 #ifdef PETSC_GCC_LAMBDA_VISIBILITY_WORKAROUND
159 #pragma GCC visibility push(hidden)
160 #endif
161 template <typename... T>
162 class MapTester {
163 public:
164 using map_type = Petsc::UnorderedMap<T...>;
165 using key_type = typename map_type::key_type;
166 using value_type = typename map_type::value_type;
167 using mapped_type = typename map_type::mapped_type;
168
169 const PetscViewer vwr;
170 const std::string map_name;
171 Printer<key_type> key_printer;
172 Printer<mapped_type> value_printer;
173 std::function<value_type(void)> generator;
174
view_map(const map_type & map) const175 PetscErrorCode view_map(const map_type &map) const noexcept
176 {
177 std::ostringstream oss;
178
179 PetscFunctionBegin;
180 PetscCallCXX(oss << std::boolalpha);
181 PetscCallCXX(oss << "map: '" << this->map_name << "'\n");
182 PetscCallCXX(oss << " size: " << map.size() << '\n');
183 PetscCallCXX(oss << " capacity: " << map.capacity() << '\n');
184 PetscCallCXX(oss << " bucket count: " << map.bucket_count() << '\n');
185 PetscCallCXX(oss << " empty: " << map.empty() << '\n');
186 PetscCallCXX(oss << " flag bucket width: " << map_type::flag_bucket_width::value << '\n');
187 PetscCallCXX(oss << " flag pairs per bucket: " << map_type::flag_pairs_per_bucket::value << '\n');
188 PetscCallCXX(oss << " {\n");
189 for (auto &&entry : map) PetscCallCXX(oss << " key: [" << this->key_printer(entry.first) << "] -> [" << this->value_printer(entry.second) << "]\n");
190 PetscCallCXX(oss << " }\n");
191 PetscCall(PetscViewerASCIIPrintf(vwr, "%s", oss.str().c_str()));
192 PetscFunctionReturn(PETSC_SUCCESS);
193 }
194
195 #define MapCheck(map__, cond__, comm__, ierr__, base_mess__, ...) \
196 do { \
197 if (PetscUnlikely(!(cond__))) { \
198 PetscCall(this->view_map(map__)); \
199 SETERRQ(comm__, ierr__, "%s: " base_mess__, this->map_name.c_str(), __VA_ARGS__); \
200 } \
201 } while (0)
202
check_size_capacity_coherent(map_type & map) const203 PetscErrorCode check_size_capacity_coherent(map_type &map) const noexcept
204 {
205 const auto msize = map.size();
206 const auto mcap = map.capacity();
207
208 PetscFunctionBegin;
209 MapCheck(map, msize == map.size(), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map size appears to change each time it is called! first call: %zu, second call %zu", msize, map.size());
210 MapCheck(map, mcap == map.capacity(), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map capacity appears to change each time it is called! first call: %zu, second call %zu", mcap, map.capacity());
211 MapCheck(map, msize >= 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map size %zu unexpected!", msize);
212 MapCheck(map, mcap >= 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map capacity %zu unexpected!", mcap);
213 MapCheck(map, mcap >= msize, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map capacity %zu < map size %zu!", mcap, msize);
214 PetscFunctionReturn(PETSC_SUCCESS);
215 }
216
check_size_capacity_coherent(map_type & map,std::size_t expected_size,std::size_t expected_min_capacity) const217 PetscErrorCode check_size_capacity_coherent(map_type &map, std::size_t expected_size, std::size_t expected_min_capacity) const noexcept
218 {
219 PetscFunctionBegin;
220 PetscCall(check_size_capacity_coherent(map));
221 MapCheck(map, map.size() == expected_size, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map size %zu did not increase (from %zu) after insertion!", map.size(), expected_size);
222 MapCheck(map, map.capacity() >= expected_min_capacity, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map capacity %zu did not increase (from %zu)!", map.capacity(), expected_min_capacity);
223 PetscFunctionReturn(PETSC_SUCCESS);
224 }
225
test_insert(map_type & map)226 PetscErrorCode test_insert(map_type &map) noexcept
227 {
228 auto key = key_type{};
229 auto value = mapped_type{};
230 auto size_before = map.size();
231 auto capacity_before = map.capacity();
232
233 const auto check_all_reinsert = [&](value_type &key_value) {
234 using insert_return_type = std::pair<typename map_type::iterator, bool>;
235 auto &key = key_value.first;
236 auto &value = key_value.second;
237 const auto key_const = key;
238 const auto value_const = value;
239 const auto pair = std::make_pair(key_const, value_const);
240 const auto check_reinsert = [&](const char op[], const insert_return_type &ret) {
241 PetscFunctionBegin;
242 MapCheck(map, !ret.second, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s reinserted key '%s'", op, this->key_printer(key));
243 MapCheck(map, ret.first->first == key, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s returned iterator key '%s' != expected '%s'", this->key_printer(ret.first->first), op, this->key_printer(key));
244 MapCheck(map, ret.first->second == value, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s returned iterator value '%s' != expected '%s'", op, this->value_printer(ret.first->second), this->value_printer(value));
245 MapCheck(map, map[key] == value, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s map[%s] '%s' != '%s'", op, this->key_printer(key), this->value_printer(map[key]), this->value_printer(value));
246 MapCheck(map, map[key_const] == value_const, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s changed value '%s' != expected '%s'", op, this->value_printer(map[key_const]), this->value_printer(value_const));
247 PetscFunctionReturn(PETSC_SUCCESS);
248 };
249
250 PetscFunctionBegin;
251 #define CHECK_REINSERT(...) check_reinsert(PetscStringize(__VA_ARGS__), __VA_ARGS__)
252 // check the following operations don't clobber values
253 PetscCall(CHECK_REINSERT(map.emplace(key, value)));
254 PetscCall(CHECK_REINSERT(map.emplace(std::piecewise_construct, std::make_tuple(key), std::make_tuple(value))));
255 PetscCall(CHECK_REINSERT(map.insert(std::make_pair(key, value))));
256 PetscCall(CHECK_REINSERT(map.insert(pair)));
257 #undef CHECK_REINSERT
258 PetscFunctionReturn(PETSC_SUCCESS);
259 };
260
261 PetscFunctionBegin;
262 PetscCall(this->check_size_capacity_coherent(map));
263 // put key in map
264 PetscCallCXX(map[key] = value);
265 // check we properly sized up
266 PetscCall(this->check_size_capacity_coherent(map, size_before + 1, capacity_before));
267 // and that the value matches
268 MapCheck(map, map[key] == value, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map default key %s != map value %s", this->key_printer(key), this->value_printer(value));
269 // and that the following operations don't clobber the value
270 {
271 value_type kv{key, value};
272
273 PetscCall(check_all_reinsert(kv));
274 }
275
276 // test that clearing workings
277 capacity_before = map.capacity();
278 PetscCall(map.clear());
279 // should have size = 0 (but capacity unchanged)
280 PetscCall(this->check_size_capacity_coherent(map, 0, capacity_before));
281
282 // test that all inserted values are found in the map
283 const auto test_map_contains_expected_items = [&](std::function<PetscErrorCode(std::vector<value_type> &)> fill_map, std::size_t kv_size) {
284 auto key_value_pairs = this->make_key_values(kv_size);
285 std::vector<std::size_t> found_key_value(key_value_pairs.size());
286
287 PetscFunctionBegin;
288 PetscCall(map.clear());
289 PetscCall(this->check_size_capacity_coherent(map, 0, 0));
290 PetscCall(fill_map(key_value_pairs));
291 // map size should exactly match the size of the vector, but we don't care about capacity
292 PetscCall(this->check_size_capacity_coherent(map, key_value_pairs.size(), 0));
293
294 // sort the vector so we can use std::binary_search on it
295 PetscCallCXX(std::sort(key_value_pairs.begin(), key_value_pairs.end()));
296 for (auto it = map.cbegin(); it != map.cend(); ++it) {
297 const auto kv_begin = key_value_pairs.cbegin();
298 const auto found = std::lower_bound(kv_begin, key_value_pairs.cend(), *it);
299 const auto dist = std::distance(kv_begin, found);
300
301 // check that the value returned exists in our expected range
302 MapCheck(map, found != key_value_pairs.cend(), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map contained key-value pair (%s, %s) not present in input range!", this->key_printer(it->first), this->value_printer(it->second));
303 MapCheck(map, dist >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Index of found key-value pair (%s -> %s) %td is < 0", this->key_printer(it->first), this->value_printer(it->second), static_cast<std::ptrdiff_t>(dist));
304 // record that we found this particular entry
305 PetscCallCXX(++found_key_value.at(static_cast<std::size_t>(dist)));
306 }
307
308 // there should only be 1 instance of each key-value in the map
309 for (std::size_t i = 0; i < found_key_value.size(); ++i) {
310 MapCheck(map, found_key_value[i] == 1, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map failed to insert key %s (value %s), have find count %zu", this->key_printer(key_value_pairs[i].first), this->value_printer(key_value_pairs[i].second), found_key_value[i]);
311 }
312 PetscFunctionReturn(PETSC_SUCCESS);
313 };
314
315 // clang-format off
316 PetscCall(
317 test_map_contains_expected_items(
318 [&](std::vector<value_type> &key_value_pairs)
319 {
320 PetscFunctionBegin;
321 for (auto &&key_value : key_value_pairs) {
322 PetscCallCXX(map[key_value.first] = key_value.second);
323 PetscCall(check_all_reinsert(key_value));
324 }
325 PetscFunctionReturn(PETSC_SUCCESS);
326 },
327 108
328 )
329 );
330 // clang-format on
331
332 // test that inserting using std algorithms work
333 {
334 value_type saved_value;
335
336 // clang-format off
337 PetscCall(
338 test_map_contains_expected_items(
339 [&](std::vector<value_type> &key_value_pairs)
340 {
341 PetscFunctionBegin;
342 // save this for later
343 PetscCallCXX(saved_value = key_value_pairs.front());
344 // test the algorithm insert works as expected
345 PetscCallCXX(std::copy(key_value_pairs.cbegin(), key_value_pairs.cend(), std::inserter(map, map.begin())));
346 PetscFunctionReturn(PETSC_SUCCESS);
347 },
348 179
349 )
350 );
351 // clang-format on
352 auto it = map.find(saved_value.first);
353
354 // can't use map[] since that might inadvertently insert it
355 MapCheck(map, it != map.end(), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map failed no longer contains key-value pair (%s -> %s) after std::copy() and container went out of scope", this->key_printer(saved_value.first), this->value_printer(saved_value.second));
356 MapCheck(map, it->first == saved_value.first, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map founnd iterator key (%s) does not match expected key (%s) after std::copy() insertion", this->key_printer(it->first), this->key_printer(saved_value.first));
357 MapCheck(map, it->second == saved_value.second, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map founnd iterator value (%s) does not match expected value (%s) after std::copy() insertion", this->value_printer(it->second), this->value_printer(saved_value.second));
358 }
359 PetscFunctionReturn(PETSC_SUCCESS);
360 }
361
test_insert()362 PetscErrorCode test_insert() noexcept
363 {
364 map_type map;
365
366 PetscFunctionBegin;
367 PetscCall(test_insert(map));
368 PetscFunctionReturn(PETSC_SUCCESS);
369 }
370
test_find(map_type & map)371 PetscErrorCode test_find(map_type &map) noexcept
372 {
373 PetscFunctionBegin;
374 {
375 const auto sample_values = this->make_key_values(145);
376
377 map = map_type(sample_values.begin(), sample_values.end());
378 for (auto &&kv : sample_values) {
379 auto &&key = kv.first;
380 auto &&value = kv.second;
381 auto it = map.find(key);
382
383 MapCheck(map, it != map.end(), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Failed to find %s in map", this->key_printer(key));
384 MapCheck(map, it->first == key, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Find iterator key %s != expected %s", this->key_printer(it->first), this->key_printer(key));
385 MapCheck(map, it->second == value, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Find iterator value %s != expected %s", this->value_printer(it->second), this->value_printer(value));
386 MapCheck(map, map.contains(key), PETSC_COMM_SELF, PETSC_ERR_PLIB, "map.contains(key) reports false, even though map.find(key) successfully found it! key: %s", this->key_printer(key));
387 MapCheck(map, map.count(key) == 1, PETSC_COMM_SELF, PETSC_ERR_PLIB, "map.count(%s) %zu != 1", this->key_printer(key), map.count(key));
388
389 {
390 const auto range = map.equal_range(key);
391 const auto &range_begin = range.first;
392 const auto range_size = std::distance(range_begin, range.second);
393
394 MapCheck(map, range_size == 1, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map equal_range() returned a range of size %zu != 1", range_size);
395 MapCheck(map, range_begin->first == key, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Equal range iterator key %s != expected %s", this->key_printer(range_begin->first), this->key_printer(key));
396 MapCheck(map, range_begin->second == value, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Equal range iterator value %s != expected %s", this->value_printer(range_begin->second), this->value_printer(value));
397 }
398 }
399 }
400 PetscFunctionReturn(PETSC_SUCCESS);
401 }
402
test_find()403 PetscErrorCode test_find() noexcept
404 {
405 map_type map;
406
407 PetscFunctionBegin;
408 PetscCall(test_find(map));
409 PetscFunctionReturn(PETSC_SUCCESS);
410 }
411
test_erase(map_type & map)412 PetscErrorCode test_erase(map_type &map) noexcept
413 {
414 auto sample_values = this->make_key_values(57);
415 const map_type backup(sample_values.cbegin(), sample_values.cend());
416 const auto check_map_is_truly_empty = [&](map_type &map) {
417 PetscFunctionBegin;
418 MapCheck(map, map.size() == 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Erasing map via iterator range didn't work, map has size %zu", map.size());
419 MapCheck(map, map.empty(), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Erasing map via iterators didn't work, map is not empty, has size %zu", map.size());
420 // this loop should never actually fire!
421 for (auto it = map.begin(); it != map.end(); ++it) MapCheck(map, false, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Erasing via iterator range did not work, map.begin() != map.end()%s", "");
422 PetscFunctionReturn(PETSC_SUCCESS);
423 };
424
425 PetscFunctionBegin;
426 PetscCallCXX(map = backup);
427 // test single erase from iterator works
428 {
429 const auto it = map.begin();
430 const auto begin_key = it->first;
431 const auto begin_val = it->second;
432
433 PetscCallCXX(map.erase(it));
434 for (auto &&kv : map) MapCheck(map, kv.first != begin_key, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Erasing %s did not work, found again in map", this->key_printer(begin_key));
435 // reinsert the value
436 PetscCallCXX(map[begin_key] = begin_val);
437 }
438
439 // test erase from iterator
440 for (auto it = map.begin(); it != map.end(); ++it) {
441 const auto before = it;
442
443 PetscCallCXX(map.erase(it));
444 MapCheck(map, before == it, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Iterator changed during erase%s", "");
445 MapCheck(map, map.occupied(before) == false, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Iterator (%s -> %s) occupied after erase", this->key_printer(before->first), this->value_printer(before->second));
446 }
447
448 // test erase from iterator range
449 PetscCall(check_map_is_truly_empty(map));
450 PetscCallCXX(map = backup);
451 PetscCallCXX(map.erase(map.begin(), map.end()));
452 PetscCall(check_map_is_truly_empty(map));
453
454 // test erase by clear
455 PetscCallCXX(map = backup);
456 PetscCall(map.clear());
457 PetscCall(check_map_is_truly_empty(map));
458
459 {
460 std::size_t cap_before;
461
462 PetscCallCXX(map = backup);
463 cap_before = map.capacity();
464 PetscCall(map.clear());
465 PetscCall(check_map_is_truly_empty(map));
466 MapCheck(map, map.capacity() == cap_before, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map capacity decreased on clear(), capacity before %zu != current capacity %zu", cap_before, map.capacity());
467 PetscCall(map.shrink_to_fit());
468 MapCheck(map, map.capacity() == 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map capacity should be 0 (have %zu) after clear() -> shrink_to_fit()!", map.capacity());
469 PetscCall(check_map_is_truly_empty(map));
470 }
471
472 // test that clear works OK (used to be a bug when inserting after clear)
473 PetscCallCXX(map.insert(generator()));
474 PetscCallCXX(map.insert(generator()));
475 PetscCallCXX(map.insert(generator()));
476 PetscCallCXX(map.insert(generator()));
477 PetscCallCXX(map.erase(map.begin(), map.end()));
478 PetscCall(check_map_is_truly_empty(map));
479
480 // test erase by member function swapping with empty map
481 for (auto &&kv : sample_values) PetscCallCXX(map.emplace(kv.first, kv.second));
482 {
483 map_type alt;
484
485 // has the effect of clearing the map
486 PetscCallCXX(map.swap(alt));
487 }
488 PetscCall(check_map_is_truly_empty(map));
489
490 // test erase by std::swap with empty map
491 PetscCallCXX(map = backup);
492 {
493 using std::swap;
494 map_type alt;
495
496 // has the effect of clearing the map
497 PetscCallCXX(swap(map, alt));
498 }
499 PetscCall(check_map_is_truly_empty(map));
500
501 // test erase by key, use new values to change it up
502 sample_values = this->make_key_values();
503 std::copy(sample_values.cbegin(), sample_values.cend(), std::inserter(map, map.begin()));
504 for (auto &&kv : sample_values) PetscCallCXX(map.erase(kv.first));
505 PetscCall(check_map_is_truly_empty(map));
506 PetscFunctionReturn(PETSC_SUCCESS);
507 }
508
test_erase()509 PetscErrorCode test_erase() noexcept
510 {
511 map_type map;
512
513 PetscFunctionBegin;
514 PetscCall(test_erase(map));
515 PetscFunctionReturn(PETSC_SUCCESS);
516 }
517
518 // stupid dummy function because auto-lambdas are C++14
519 template <typename It>
test_iterators(map_type & map,It it,It it2)520 PetscErrorCode test_iterators(map_type &map, It it, It it2) noexcept
521 {
522 constexpr std::size_t max_iter = 10000;
523 constexpr auto is_normal = std::is_same<It, typename map_type::iterator>::value;
524 constexpr auto is_const = std::is_same<It, typename map_type::const_iterator>::value;
525 static_assert(is_normal || is_const, "");
526 constexpr const char *it_name = is_normal ? "Non-const" : "Const";
527
528 PetscFunctionBegin;
529 MapCheck(map, it == it2, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator does not equal itself?", it_name);
530 PetscCallCXX(++it);
531 PetscCallCXX(it2++);
532 MapCheck(map, it == it2, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator does not equal itself after ++it, and it2++", it_name);
533 PetscCallCXX(--it);
534 PetscCallCXX(it2--);
535 MapCheck(map, it == it2, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator does not equal itself after --it, and it2--", it_name);
536 MapCheck(map, map.size() < max_iter, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Forward progress test only works properly if the map size (%zu) < %zu", map.size(), max_iter);
537 // check that the prefix and postfix increment and decerement make forward progress
538 {
539 std::size_t i;
540
541 // increment
542 PetscCallCXX(it = map.begin());
543 for (i = 0; i < max_iter; ++i) {
544 if (it == map.end()) break;
545 PetscCallCXX(++it);
546 }
547 MapCheck(map, i < max_iter, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator did not appear to make forward progress using prefix increment! Reached maximum iteration count %zu for map of size %zu", it_name, max_iter, map.size());
548 PetscCallCXX(it = map.begin());
549 for (i = 0; i < max_iter; ++i) {
550 if (it == map.end()) break;
551 PetscCallCXX(it++);
552 }
553 MapCheck(map, i < max_iter, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator did not appear to make forward progress using postfix increment! Reached maximum iteration count %zu for map of size %zu", it_name, max_iter, map.size());
554
555 // decrement
556 PetscCallCXX(it = std::prev(map.end()));
557 for (i = 0; i < max_iter; ++i) {
558 if (it == map.begin()) break;
559 PetscCallCXX(--it);
560 }
561 MapCheck(map, i < max_iter, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator did not appear to make forward progress using prefix decrement! Reached maximum iteration count %zu for map of size %zu", it_name, max_iter, map.size());
562 PetscCallCXX(it = std::prev(map.end()));
563 for (i = 0; i < max_iter; ++i) {
564 if (it == map.begin()) break;
565 PetscCallCXX(it--);
566 }
567 MapCheck(map, i < max_iter, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator did not appear to make forward progress using postfix decrement! Reached maximum iteration count %zu for map of size %zu", it_name, max_iter, map.size());
568 }
569 PetscFunctionReturn(PETSC_SUCCESS);
570 }
571
test_misc()572 PetscErrorCode test_misc() noexcept
573 {
574 const auto sample_values = this->make_key_values(97);
575 map_type map(sample_values.begin(), sample_values.end());
576
577 PetscFunctionBegin;
578 PetscCall(this->test_iterators(map, map.begin(), map.begin()));
579 PetscCall(this->test_iterators(map, map.cbegin(), map.cbegin()));
580 {
581 const auto backup = map;
582 auto map_copy = map;
583 const auto check_original_map_did_not_change = [&](const char op[]) {
584 PetscFunctionBegin;
585 // the original map should not have changed at all
586 MapCheck(map, map == backup, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map does not equal the original map after %s", op);
587 PetscFunctionReturn(PETSC_SUCCESS);
588 };
589
590 MapCheck(map_copy, map == map_copy, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Copy of map does not equal the original map%s", "");
591 PetscCall(check_original_map_did_not_change("move assign"));
592 // test that the copied map works OK
593 PetscCall(this->test_insert(map_copy));
594 PetscCall(check_original_map_did_not_change("test_insert()"));
595 PetscCall(this->test_find(map_copy));
596 PetscCall(check_original_map_did_not_change("test_find()"));
597 PetscCall(this->test_erase(map_copy));
598 PetscCall(check_original_map_did_not_change("test_erase()"));
599 PetscCallCXX(map_copy = map);
600
601 auto moved_copy = std::move(map_copy);
602
603 MapCheck(moved_copy, map == moved_copy, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Moved copy of map does not equal the original map%s", "");
604 PetscCall(check_original_map_did_not_change("move assign"));
605 PetscCall(this->test_insert(moved_copy));
606 PetscCall(check_original_map_did_not_change("test_insert()"));
607 PetscCall(this->test_find(moved_copy));
608 PetscCall(check_original_map_did_not_change("test_find()"));
609 PetscCall(this->test_erase(moved_copy));
610 PetscCall(check_original_map_did_not_change("test_erase()"));
611 }
612 PetscFunctionReturn(PETSC_SUCCESS);
613 }
614
test()615 PetscErrorCode test() noexcept
616 {
617 PetscFunctionBegin;
618 PetscCall(this->test_insert());
619 PetscCall(this->test_find());
620 PetscCall(this->test_erase());
621 PetscCall(this->test_misc());
622 PetscFunctionReturn(PETSC_SUCCESS);
623 }
624
625 private:
make_key_values(std::size_t size=100) const626 PETSC_NODISCARD std::vector<value_type> make_key_values(std::size_t size = 100) const noexcept
627 {
628 std::vector<value_type> v(size);
629
630 std::generate(v.begin(), v.end(), this->generator);
631 return v;
632 }
633 };
634 #ifdef PETSC_GCC_LAMBDA_VISIBILITY_WORKAROUND
635 #pragma GCC visibility pop
636 #endif
637
638 template <typename... T, typename... Args>
make_tester(PetscViewer vwr,const char name[],Args &&...args)639 PETSC_NODISCARD static MapTester<T...> make_tester(PetscViewer vwr, const char name[], Args &&...args)
640 {
641 return {vwr, name, std::forward<Args>(args)...};
642 }
643
main(int argc,char * argv[])644 int main(int argc, char *argv[])
645 {
646 PetscViewer vwr;
647 PetscRandom rand;
648
649 PetscFunctionBeginUser;
650 PetscCall(PetscInitialize(&argc, &argv, nullptr, help));
651 PetscCall(PetscRandomCreate(PETSC_COMM_SELF, &rand));
652 PetscCall(PetscRandomSetInterval(rand, INT_MIN, INT_MAX));
653 PetscCall(PetscRandomSetFromOptions(rand));
654 PetscCall(PetscViewerASCIIGetStdout(PETSC_COMM_WORLD, &vwr));
655
656 {
657 // printer functions
658 const auto int_printer = [](int key, std::string &buf) {
659 PetscFunctionBegin;
660 PetscCallCXX(buf = std::to_string(key));
661 PetscFunctionReturn(PETSC_SUCCESS);
662 };
663 const auto double_printer = [](double value, std::string &buf) {
664 PetscFunctionBegin;
665 PetscCallCXX(buf = std::to_string(value));
666 PetscFunctionReturn(PETSC_SUCCESS);
667 };
668 const auto foo_printer = [](const Foo &key, std::string &buf) {
669 PetscFunctionBegin;
670 PetscCall(key.to_string(buf));
671 PetscFunctionReturn(PETSC_SUCCESS);
672 };
673 const auto bar_printer = [](const Bar &value, std::string &buf) {
674 PetscFunctionBegin;
675 PetscCall(value.to_string(buf));
676 PetscFunctionReturn(PETSC_SUCCESS);
677 };
678 const auto pair_printer = [](const std::pair<int, double> &value, std::string &buf) {
679 PetscFunctionBegin;
680 PetscCallCXX(buf = '<' + std::to_string(value.first) + ", " + std::to_string(value.second) + '>');
681 PetscFunctionReturn(PETSC_SUCCESS);
682 };
683
684 // generator functions
685 const auto make_int = [&] {
686 PetscReal x = 0.;
687
688 PetscFunctionBegin;
689 PetscCallAbort(PETSC_COMM_SELF, PetscRandomGetValueReal(rand, &x));
690 PetscFunctionReturn(static_cast<int>(x));
691 };
692 const auto make_double = [&] {
693 PetscReal x = 0.;
694
695 PetscFunctionBegin;
696 PetscCallAbort(PETSC_COMM_SELF, PetscRandomGetValueReal(rand, &x));
697 PetscFunctionReturn(static_cast<double>(x));
698 };
699 const auto make_foo = [&] {
700 PetscFunctionBegin;
701 auto ret = Foo{make_int(), make_double()};
702 PetscFunctionReturn(ret);
703 };
704 const auto make_bar = [&] {
705 constexpr std::size_t max_size = 14, min_size = 1;
706 const auto isize = std::abs(make_int());
707 std::vector<int> x(std::max(static_cast<std::size_t>(isize) % max_size, min_size));
708
709 PetscFunctionBegin;
710 PetscCallCXXAbort(PETSC_COMM_SELF, std::generate(x.begin(), x.end(), make_int));
711 auto ret = Bar{std::move(x), std::to_string(isize)};
712 PetscFunctionReturn(ret);
713 };
714
715 const auto int_double_generator = [&] { return std::make_pair(make_int(), make_double()); };
716 PetscCall(make_tester<int, double>(vwr, "int-double basic map", int_printer, double_printer, int_double_generator).test());
717 PetscCall(make_tester<int, double, BadHash>(vwr, "int-double bad hash map", int_printer, double_printer, int_double_generator).test());
718
719 const auto int_foo_generator = [&] { return std::make_pair(make_int(), make_foo()); };
720 PetscCall(make_tester<int, Foo, BadHash>(vwr, "int-foo bad hash map", int_printer, foo_printer, int_foo_generator).test());
721
722 const auto foo_bar_generator = [&] { return std::make_pair(make_foo(), make_bar()); };
723 PetscCall(make_tester<Foo, Bar>(vwr, "foo-bar basic map", foo_printer, bar_printer, foo_bar_generator).test());
724 PetscCall(make_tester<Foo, Bar, BadHash>(vwr, "foo-bar bad hash map", foo_printer, bar_printer, foo_bar_generator).test());
725
726 // these test that the indirect_hasher and indirect_equals classes don't barf, since the
727 // value_type of the map and hashers is both the same thing
728 const auto pair_pair_generator = [&] {
729 auto pair = std::make_pair(make_int(), make_double());
730 return std::make_pair(pair, pair);
731 };
732 PetscCall(make_tester<std::pair<int, double>, std::pair<int, double>>(vwr, "pair<int, double>-pair<int, double> basic map", pair_printer, pair_printer, pair_pair_generator).test());
733 PetscCall(make_tester<std::pair<int, double>, std::pair<int, double>, BadHash>(vwr, "pair<int, double>-pair<int, double> bad hash map", pair_printer, pair_printer, pair_pair_generator).test());
734 }
735
736 PetscCall(PetscRandomDestroy(&rand));
737 PetscCall(PetscFinalize());
738 return 0;
739 }
740
741 /*TEST
742
743 test:
744 suffix: umap_0
745 output_file: output/empty.out
746
747 TEST*/
748