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*/