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