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::test_insert()::::value_type&)> [with T =
141: // ...]::' declared with greater visibility than the type of its field
142: // 'MapTester::test_insert()::::value_type&)> [with T =
143: // ...]::
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:     {
460:       std::size_t cap_before;

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:     }

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));

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;

485:       // has the effect of clearing the map
486:       PetscCallCXX(map.swap(alt));
487:     }
488:     PetscCall(check_map_is_truly_empty(map));

490:     // test erase by std::swap with empty map
491:     PetscCallCXX(map = backup);
492:     {
493:       using std::swap;
494:       map_type alt;

496:       // has the effect of clearing the map
497:       PetscCallCXX(swap(map, alt));
498:     }
499:     PetscCall(check_map_is_truly_empty(map));

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:   }

509:   PetscErrorCode test_erase() noexcept
510:   {
511:     map_type map;

513:     PetscFunctionBegin;
514:     PetscCall(test_erase(map));
515:     PetscFunctionReturn(PETSC_SUCCESS);
516:   }

518:   // stupid dummy function because auto-lambdas are C++14
519:   template <typename It>
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";

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;

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());

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:   }

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());

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:       };

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);

601:       auto moved_copy = std::move(map_copy);

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:   }

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:   }

625: private:
626:   PETSC_NODISCARD std::vector<value_type> make_key_values(std::size_t size = 100) const noexcept
627:   {
628:     std::vector<value_type> v(size);

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

638: template <typename... T, typename... 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: }

644: int main(int argc, char *argv[])
645: {
646:   PetscViewer vwr;
647:   PetscRandom rand;

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));

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:     };

684:     // generator functions
685:     const auto make_int = [&] {
686:       PetscReal x = 0.;

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.;

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));

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:     };

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());

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());

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());

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:   }

736:   PetscCall(PetscRandomDestroy(&rand));
737:   PetscCall(PetscFinalize());
738:   return 0;
739: }

741: /*TEST

743:   test:
744:     suffix: umap_0

746: TEST*/