Actual source code: ex64.cxx
1: static const char help[] = "Tests UnorderedMap.\n";
3: #include <petsc/private/cpp/unordered_map.hpp>
4: #include <petscviewer.h>
6: #include <sstream> // std::ostringstream
7: #include <string>
8: #include <vector>
9: #include <algorithm> // std::sort
11: // ==========================================================================================
12: // Setup
13: // ==========================================================================================
15: // see https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x
16: static inline void hash_combine(std::size_t &) noexcept { }
18: template <typename T, typename... 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: }
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: }
40: using pair_type = std::pair<int, double>;
41: MAKE_HASHABLE(pair_type, t.first, t.second);
43: using namespace Petsc::util;
45: struct Foo {
46: int x{};
47: double y{};
49: constexpr Foo() noexcept = default;
50: constexpr Foo(int x, double y) noexcept : x(x), y(y) { }
52: bool operator==(const Foo &other) const noexcept { return x == other.x && y == other.y; }
53: bool operator!=(const Foo &other) const noexcept { return !(*this == other); }
54: bool operator<(const Foo &other) const noexcept { return std::tie(x, y) < std::tie(other.x, other.y); }
56: 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: }
63: friend std::ostream &operator<<(std::ostream &oss, const Foo &f) noexcept
64: {
65: std::string ret;
67: PetscFunctionBegin;
68: PetscCallAbort(PETSC_COMM_SELF, f.to_string(ret));
69: oss << ret;
70: PetscFunctionReturn(oss);
71: }
72: };
74: MAKE_HASHABLE(Foo, t.x, t.y);
76: struct Bar {
77: std::vector<int> x{};
78: std::string y{};
80: Bar() noexcept = default;
81: Bar(std::vector<int> x, std::string y) noexcept : x(std::move(x)), y(std::move(y)) { }
83: bool operator==(const Bar &other) const noexcept { return x == other.x && y == other.y; }
84: bool operator<(const Bar &other) const noexcept { return std::tie(x, y) < std::tie(other.x, other.y); }
86: 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: }
98: friend std::ostream &operator<<(std::ostream &oss, const Bar &b) noexcept
99: {
100: std::string ret;
102: PetscFunctionBegin;
103: PetscCallAbort(PETSC_COMM_SELF, b.to_string(ret));
104: oss << ret;
105: PetscFunctionReturn(oss);
106: }
107: };
109: struct BadHash {
110: template <typename T>
111: constexpr std::size_t operator()(const T &) const noexcept
112: {
113: return 1;
114: }
115: };
117: template <typename T>
118: struct Printer {
119: using signature = PetscErrorCode(const T &, std::string &);
121: mutable std::string buffer;
122: std::function<signature> printer;
124: template <typename F>
125: Printer(F &&printer) noexcept : printer(std::forward<F>(printer))
126: {
127: }
129: 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: };
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
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;
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;
175: PetscErrorCode view_map(const map_type &map) const noexcept
176: {
177: std::ostringstream oss;
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: }
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)
203: PetscErrorCode check_size_capacity_coherent(map_type &map) const noexcept
204: {
205: const auto msize = map.size();
206: const auto mcap = map.capacity();
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: }
217: 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: }
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();
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: };
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: };
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};
273: PetscCall(check_all_reinsert(kv));
274: }
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));
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());
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));
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);
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: }
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: };
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
332: // test that inserting using std algorithms work
333: {
334: value_type saved_value;
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);
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: }
362: PetscErrorCode test_insert() noexcept
363: {
364: map_type map;
366: PetscFunctionBegin;
367: PetscCall(test_insert(map));
368: PetscFunctionReturn(PETSC_SUCCESS);
369: }
371: PetscErrorCode test_find(map_type &map) noexcept
372: {
373: PetscFunctionBegin;
374: {
375: const auto sample_values = this->make_key_values(145);
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);
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));
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);
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: }
403: PetscErrorCode test_find() noexcept
404: {
405: map_type map;
407: PetscFunctionBegin;
408: PetscCall(test_find(map));
409: PetscFunctionReturn(PETSC_SUCCESS);
410: }
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: };
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;
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: }
439: // test erase from iterator
440: for (auto it = map.begin(); it != map.end(); ++it) {
441: const auto before = it;
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: }
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));
454: // test erase by clear
455: PetscCallCXX(map = backup);
456: PetscCall(map.clear());
457: PetscCall(check_map_is_truly_empty(map));
459: // test that clear works OK (used to be a bug when inserting after clear)
460: PetscCallCXX(map.insert(generator()));
461: PetscCallCXX(map.insert(generator()));
462: PetscCallCXX(map.insert(generator()));
463: PetscCallCXX(map.insert(generator()));
464: PetscCallCXX(map.erase(map.begin(), map.end()));
465: PetscCall(check_map_is_truly_empty(map));
467: // test erase by member function swapping with empty map
468: for (auto &&kv : sample_values) PetscCallCXX(map.emplace(kv.first, kv.second));
469: {
470: map_type alt;
472: // has the effect of clearing the map
473: PetscCallCXX(map.swap(alt));
474: }
475: PetscCall(check_map_is_truly_empty(map));
477: // test erase by std::swap with empty map
478: PetscCallCXX(map = backup);
479: {
480: using std::swap;
481: map_type alt;
483: // has the effect of clearing the map
484: PetscCallCXX(swap(map, alt));
485: }
486: PetscCall(check_map_is_truly_empty(map));
488: // test erase by key, use new values to change it up
489: sample_values = this->make_key_values();
490: std::copy(sample_values.cbegin(), sample_values.cend(), std::inserter(map, map.begin()));
491: for (auto &&kv : sample_values) PetscCallCXX(map.erase(kv.first));
492: PetscCall(check_map_is_truly_empty(map));
493: PetscFunctionReturn(PETSC_SUCCESS);
494: }
496: PetscErrorCode test_erase() noexcept
497: {
498: map_type map;
500: PetscFunctionBegin;
501: PetscCall(test_erase(map));
502: PetscFunctionReturn(PETSC_SUCCESS);
503: }
505: // stupid dummy function because auto-lambdas are C++14
506: template <typename It>
507: PetscErrorCode test_iterators(map_type &map, It it, It it2) noexcept
508: {
509: constexpr std::size_t max_iter = 10000;
510: constexpr auto is_normal = std::is_same<It, typename map_type::iterator>::value;
511: constexpr auto is_const = std::is_same<It, typename map_type::const_iterator>::value;
512: static_assert(is_normal || is_const, "");
513: constexpr const char *it_name = is_normal ? "Non-const" : "Const";
515: PetscFunctionBegin;
516: MapCheck(map, it == it2, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator does not equal itself?", it_name);
517: PetscCallCXX(++it);
518: PetscCallCXX(it2++);
519: MapCheck(map, it == it2, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator does not equal itself after ++it, and it2++", it_name);
520: PetscCallCXX(--it);
521: PetscCallCXX(it2--);
522: MapCheck(map, it == it2, PETSC_COMM_SELF, PETSC_ERR_PLIB, "%s iterator does not equal itself after --it, and it2--", it_name);
523: 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);
524: // check that the prefix and postfix increment and decerement make forward progress
525: {
526: std::size_t i;
528: // increment
529: PetscCallCXX(it = map.begin());
530: for (i = 0; i < max_iter; ++i) {
531: if (it == map.end()) break;
532: PetscCallCXX(++it);
533: }
534: 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());
535: PetscCallCXX(it = map.begin());
536: for (i = 0; i < max_iter; ++i) {
537: if (it == map.end()) break;
538: PetscCallCXX(it++);
539: }
540: 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());
542: // decrement
543: PetscCallCXX(it = std::prev(map.end()));
544: for (i = 0; i < max_iter; ++i) {
545: if (it == map.begin()) break;
546: PetscCallCXX(--it);
547: }
548: 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());
549: PetscCallCXX(it = std::prev(map.end()));
550: for (i = 0; i < max_iter; ++i) {
551: if (it == map.begin()) break;
552: PetscCallCXX(it--);
553: }
554: 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());
555: }
557: PetscFunctionReturn(PETSC_SUCCESS);
558: }
560: PetscErrorCode test_misc() noexcept
561: {
562: const auto sample_values = this->make_key_values(97);
563: map_type map(sample_values.begin(), sample_values.end());
565: PetscFunctionBegin;
566: PetscCall(this->test_iterators(map, map.begin(), map.begin()));
567: PetscCall(this->test_iterators(map, map.cbegin(), map.cbegin()));
568: {
569: const auto backup = map;
570: auto map_copy = map;
571: const auto check_original_map_did_not_change = [&](const char op[]) {
572: PetscFunctionBegin;
573: // the original map should not have changed at all
574: MapCheck(map, map == backup, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Map does not equal the original map after %s", op);
575: PetscFunctionReturn(PETSC_SUCCESS);
576: };
578: MapCheck(map_copy, map == map_copy, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Copy of map does not equal the original map%s", "");
579: PetscCall(check_original_map_did_not_change("move assign"));
580: // test that the copied map works OK
581: PetscCall(this->test_insert(map_copy));
582: PetscCall(check_original_map_did_not_change("test_insert()"));
583: PetscCall(this->test_find(map_copy));
584: PetscCall(check_original_map_did_not_change("test_find()"));
585: PetscCall(this->test_erase(map_copy));
586: PetscCall(check_original_map_did_not_change("test_erase()"));
587: PetscCallCXX(map_copy = map);
589: auto moved_copy = std::move(map_copy);
591: MapCheck(moved_copy, map == moved_copy, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Moved copy of map does not equal the original map%s", "");
592: PetscCall(check_original_map_did_not_change("move assign"));
593: PetscCall(this->test_insert(moved_copy));
594: PetscCall(check_original_map_did_not_change("test_insert()"));
595: PetscCall(this->test_find(moved_copy));
596: PetscCall(check_original_map_did_not_change("test_find()"));
597: PetscCall(this->test_erase(moved_copy));
598: PetscCall(check_original_map_did_not_change("test_erase()"));
599: }
600: PetscFunctionReturn(PETSC_SUCCESS);
601: }
603: PetscErrorCode test() noexcept
604: {
605: PetscFunctionBegin;
606: PetscCall(this->test_insert());
607: PetscCall(this->test_find());
608: PetscCall(this->test_erase());
609: PetscCall(this->test_misc());
610: PetscFunctionReturn(PETSC_SUCCESS);
611: }
613: private:
614: PETSC_NODISCARD std::vector<value_type> make_key_values(std::size_t size = 100) const noexcept
615: {
616: std::vector<value_type> v(size);
618: std::generate(v.begin(), v.end(), this->generator);
619: return v;
620: }
621: };
622: #ifdef PETSC_GCC_LAMBDA_VISIBILITY_WORKAROUND
623: #pragma GCC visibility pop
624: #endif
626: template <typename... T, typename... Args>
627: PETSC_NODISCARD static MapTester<T...> make_tester(PetscViewer vwr, const char name[], Args &&...args)
628: {
629: return {vwr, name, std::forward<Args>(args)...};
630: }
632: int main(int argc, char *argv[])
633: {
634: PetscViewer vwr;
635: PetscRandom rand;
637: PetscFunctionBeginUser;
638: PetscCall(PetscInitialize(&argc, &argv, nullptr, help));
639: PetscCall(PetscRandomCreate(PETSC_COMM_SELF, &rand));
640: PetscCall(PetscRandomSetInterval(rand, INT_MIN, INT_MAX));
641: PetscCall(PetscRandomSetFromOptions(rand));
642: PetscCall(PetscViewerASCIIGetStdout(PETSC_COMM_WORLD, &vwr));
644: {
645: // printer functions
646: const auto int_printer = [](int key, std::string &buf) {
647: PetscFunctionBegin;
648: PetscCallCXX(buf = std::to_string(key));
649: PetscFunctionReturn(PETSC_SUCCESS);
650: };
651: const auto double_printer = [](double value, std::string &buf) {
652: PetscFunctionBegin;
653: PetscCallCXX(buf = std::to_string(value));
654: PetscFunctionReturn(PETSC_SUCCESS);
655: };
656: const auto foo_printer = [](const Foo &key, std::string &buf) {
657: PetscFunctionBegin;
658: PetscCall(key.to_string(buf));
659: PetscFunctionReturn(PETSC_SUCCESS);
660: };
661: const auto bar_printer = [](const Bar &value, std::string &buf) {
662: PetscFunctionBegin;
663: PetscCall(value.to_string(buf));
664: PetscFunctionReturn(PETSC_SUCCESS);
665: };
666: const auto pair_printer = [](const std::pair<int, double> &value, std::string &buf) {
667: PetscFunctionBegin;
668: PetscCallCXX(buf = '<' + std::to_string(value.first) + ", " + std::to_string(value.second) + '>');
669: PetscFunctionReturn(PETSC_SUCCESS);
670: };
672: // generator functions
673: const auto make_int = [&] {
674: PetscReal x = 0.;
676: PetscFunctionBegin;
677: PetscCallAbort(PETSC_COMM_SELF, PetscRandomGetValueReal(rand, &x));
678: PetscFunctionReturn(static_cast<int>(x));
679: };
680: const auto make_double = [&] {
681: PetscReal x = 0.;
683: PetscFunctionBegin;
684: PetscCallAbort(PETSC_COMM_SELF, PetscRandomGetValueReal(rand, &x));
685: PetscFunctionReturn(static_cast<double>(x));
686: };
687: const auto make_foo = [&] {
688: PetscFunctionBegin;
689: auto ret = Foo{make_int(), make_double()};
690: PetscFunctionReturn(ret);
691: };
692: const auto make_bar = [&] {
693: constexpr std::size_t max_size = 14, min_size = 1;
694: const auto isize = std::abs(make_int());
695: std::vector<int> x(std::max(static_cast<std::size_t>(isize) % max_size, min_size));
697: PetscFunctionBegin;
698: PetscCallCXXAbort(PETSC_COMM_SELF, std::generate(x.begin(), x.end(), make_int));
699: auto ret = Bar{std::move(x), std::to_string(isize)};
700: PetscFunctionReturn(ret);
701: };
703: const auto int_double_generator = [&] { return std::make_pair(make_int(), make_double()); };
704: PetscCall(make_tester<int, double>(vwr, "int-double basic map", int_printer, double_printer, int_double_generator).test());
705: PetscCall(make_tester<int, double, BadHash>(vwr, "int-double bad hash map", int_printer, double_printer, int_double_generator).test());
707: const auto int_foo_generator = [&] { return std::make_pair(make_int(), make_foo()); };
708: PetscCall(make_tester<int, Foo, BadHash>(vwr, "int-foo bad hash map", int_printer, foo_printer, int_foo_generator).test());
710: const auto foo_bar_generator = [&] { return std::make_pair(make_foo(), make_bar()); };
711: PetscCall(make_tester<Foo, Bar>(vwr, "foo-bar basic map", foo_printer, bar_printer, foo_bar_generator).test());
712: PetscCall(make_tester<Foo, Bar, BadHash>(vwr, "foo-bar bad hash map", foo_printer, bar_printer, foo_bar_generator).test());
714: // these test that the indirect_hasher and indirect_equals classes don't barf, since the
715: // value_type of the map and hashers is both the same thing
716: const auto pair_pair_generator = [&] {
717: auto pair = std::make_pair(make_int(), make_double());
718: return std::make_pair(pair, pair);
719: };
720: 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());
721: 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());
722: }
724: PetscCall(PetscRandomDestroy(&rand));
725: PetscCall(PetscFinalize());
726: return 0;
727: }
729: /*TEST
731: test:
732: suffix: umap_0
734: TEST*/