Actual source code: unordered_map.hpp
1: #pragma once
3: #if defined(__clang__)
4: #pragma clang diagnostic push
5: #pragma clang diagnostic ignored "-Wshorten-64-to-32"
6: #endif
8: #include <petsc/private/cpp/type_traits.hpp>
9: #include <petsc/private/cpp/utility.hpp>
10: #include <petsc/private/cpp/functional.hpp>
12: #if PETSC_CPP_VERSION >= 17
13: #include <optional>
14: #define PETSC_OPTIONAL_GET_KEY(...) *(__VA_ARGS__)
15: #define PETSC_KHASH_MAP_USE_OPTIONAL 1
16: #else
17: #define PETSC_OPTIONAL_GET_KEY(...) __VA_ARGS__
18: #define PETSC_KHASH_MAP_USE_OPTIONAL 0
19: #endif
21: #include <cstdint> // std::uint32_t
22: #include <climits> // CHAR_BIT
23: #include <iterator> // std::inserter
24: #include <limits> // std::numeric_limits
25: #include <algorithm> // std::fill
26: #include <vector>
28: namespace Petsc
29: {
31: namespace khash
32: {
34: // ==========================================================================================
35: // KHashTable - The hash table implementation which underpins UnorderedMap (and possibly
36: // UnorderedSet in the future).
37: //
38: // This class serves to implement the majority of functionality for both classes. In fact, it
39: // is possible to use -- without modification -- as a khash_unordered_set already.
40: //
41: // Template parameters are as follows:
42: //
43: // Value:
44: // The value type of the hash table, i.e. the set of unique items it stores
45: //
46: // Hash:
47: // The hasher type, provides a std::size_t operator()(const Value&) to produce a hash of Value
48: //
49: // Eq:
50: // The comparison type, provides a bool operator()(const Value&, const Value&) to compare two
51: // different Value's
52: // ==========================================================================================
54: template <typename Value, typename Hash, typename Eq>
55: class KHashTable : util::compressed_pair<Hash, Eq> {
56: // Note we derive from compressed_pair! This is to enable us to efficiently
57: // implement hash_function() and key_eq() since -- if Hash and Eq are empty -- we do not have
58: // to pay to store them due to empty base-class optimization.
59: template <bool>
60: class table_iterator;
62: template <bool>
63: friend class table_iterator;
65: public:
66: using value_type = Value;
67: using hasher = Hash;
68: using key_equal = Eq;
69: using size_type = std::size_t;
70: using reference = value_type &;
71: using const_reference = const value_type &;
72: using difference_type = std::ptrdiff_t;
73: using iterator = table_iterator</* is const = */ false>;
74: using const_iterator = table_iterator</* is const = */ true>;
75: using khash_int = std::uint32_t; // used as the internal iterator type
76: using flags_type = std::uint32_t;
78: using flag_bucket_width = std::integral_constant<unsigned long, sizeof(flags_type) * CHAR_BIT>;
79: using flag_pairs_per_bucket = std::integral_constant<unsigned long, flag_bucket_width::value / 2>;
81: static_assert(std::numeric_limits<flags_type>::is_integer && std::is_unsigned<flags_type>::value, "");
82: static_assert(flag_bucket_width::value % 2 == 0, "");
84: KHashTable() = default;
85: ~KHashTable() = default;
87: KHashTable(const KHashTable &) = default;
88: KHashTable &operator=(const KHashTable &) = default;
90: KHashTable(KHashTable &&) noexcept;
91: KHashTable &operator=(KHashTable &&) noexcept;
93: template <typename Iter>
94: KHashTable(Iter, Iter) noexcept;
96: PETSC_NODISCARD iterator begin() noexcept;
97: PETSC_NODISCARD const_iterator cbegin() const noexcept;
98: PETSC_NODISCARD const_iterator begin() const noexcept;
100: PETSC_NODISCARD iterator end() noexcept;
101: PETSC_NODISCARD const_iterator cend() const noexcept;
102: PETSC_NODISCARD const_iterator end() const noexcept;
104: PETSC_NODISCARD size_type bucket_count() const noexcept;
105: PETSC_NODISCARD size_type size() const noexcept;
106: PETSC_NODISCARD size_type capacity() const noexcept;
107: PETSC_NODISCARD bool empty() const noexcept;
109: PetscErrorCode reserve(size_type) noexcept;
110: PetscErrorCode resize(size_type) noexcept;
111: PetscErrorCode clear() noexcept;
113: PETSC_NODISCARD bool occupied(khash_int) const noexcept;
114: PETSC_NODISCARD bool occupied(const_iterator) const noexcept;
116: iterator erase(iterator) noexcept;
117: iterator erase(const_iterator) noexcept;
118: iterator erase(const_iterator, const_iterator) noexcept;
120: template <typename... Args>
121: std::pair<iterator, bool> emplace(Args &&...) noexcept;
123: std::pair<iterator, bool> insert(const value_type &) noexcept;
124: std::pair<iterator, bool> insert(value_type &&) noexcept;
125: iterator insert(const_iterator, const value_type &) noexcept;
126: iterator insert(const_iterator, value_type &&) noexcept;
128: hasher hash_function() const noexcept;
129: key_equal key_eq() const noexcept;
131: PetscErrorCode shrink_to_fit() noexcept;
133: void swap(KHashTable &) noexcept;
135: protected:
136: PETSC_NODISCARD iterator make_iterator_(khash_int) noexcept;
137: PETSC_NODISCARD const_iterator make_iterator_(khash_int) const noexcept;
139: template <typename T>
140: PetscErrorCode khash_find_(T &&, khash_int *) const noexcept;
142: // emplacement for the hash map, where key and value are constructed separately
143: template <typename KeyType, typename... ValueTypeArgs>
144: PETSC_NODISCARD std::pair<iterator, bool> find_and_emplace_(KeyType &&, ValueTypeArgs &&...) noexcept;
145: template <typename KeyValueType>
146: PETSC_NODISCARD std::pair<iterator, bool> find_and_emplace_(KeyValueType &&) noexcept;
148: private:
149: template <typename Iter>
150: KHashTable(Iter, Iter, std::input_iterator_tag) noexcept;
151: template <typename Iter>
152: KHashTable(Iter, Iter, std::random_access_iterator_tag) noexcept;
154: // Every element in the table has a pair of 2 flags that describe its current state. These
155: // are addressed via the *index* into values_ for the element. These flags are:
156: //
157: // 1. Empty: has the element *ever* been constructed? Note empty of yes implies deleted no.
158: // 2. Deleted: has the element been constructed and marked as deleted?
159: //
160: // Since these flags are combineable we can store them in compressed form in a bit-table,
161: // where each pair of consecutive 2*i and 2*i+1 bits denote the flags for element i.
162: //
163: // Thus if we use a vector of std::bitset's (which are each N-bits wide) we can effectively
164: // store N / 2 flags per index, for example:
165: //
166: // std::vector> flags;
167: //
168: // int flags_per_idx = 32 / 2; (16 pairs of flags)
169: // int value_index = 24;
170: // int flags_index = value_index / flags_per_idx; (index into the right bucket in flags)
171: // int flags_bucket_index = (value_index % flags_per_idx) << 1; (within that bucket grab the
172: // right entry)
173: //
174: // or visually speaking:
175: //
176: // flags = [
177: // [00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00],
178: // [00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00], <--- flags_index (1)
179: // ... ^--- flags_bucket_index (16)
180: // ]
181: //
182: // Thus to access a particular flag pair, one must right-shift flags[flags_index] by
183: // flags_bucket_index. Then the desired flag pair will be the first and second bits of the
184: // result.
185: PETSC_NODISCARD static constexpr khash_int flag_bucket_index_(khash_int) noexcept;
187: PETSC_NODISCARD static flags_type &flag_bucket_at_(khash_int, std::vector<flags_type> &) noexcept;
188: PETSC_NODISCARD static const flags_type &flag_bucket_at_(khash_int, const std::vector<flags_type> &) noexcept;
189: PETSC_NODISCARD flags_type &flag_bucket_at_(khash_int) noexcept;
190: PETSC_NODISCARD const flags_type &flag_bucket_at_(khash_int) const noexcept;
192: template <unsigned>
193: PETSC_NODISCARD static bool khash_test_flag_(khash_int, const std::vector<flags_type> &) noexcept;
194: PETSC_NODISCARD static bool khash_is_del_(khash_int, const std::vector<flags_type> &) noexcept;
195: PETSC_NODISCARD static bool khash_is_empty_(khash_int, const std::vector<flags_type> &) noexcept;
196: PETSC_NODISCARD static bool khash_is_either_(khash_int, const std::vector<flags_type> &) noexcept;
197: PETSC_NODISCARD static bool khash_occupied_(khash_int, const std::vector<flags_type> &) noexcept;
198: PETSC_NODISCARD bool khash_is_del_(khash_int) const noexcept;
199: PETSC_NODISCARD bool khash_is_empty_(khash_int) const noexcept;
200: PETSC_NODISCARD bool khash_is_either_(khash_int) const noexcept;
202: template <unsigned, bool>
203: static PetscErrorCode khash_set_flag_(khash_int, std::vector<flags_type> &) noexcept;
204: template <bool>
205: static PetscErrorCode khash_set_deleted_(khash_int, std::vector<flags_type> &) noexcept;
206: template <bool>
207: static PetscErrorCode khash_set_empty_(khash_int, std::vector<flags_type> &) noexcept;
208: template <bool>
209: static PetscErrorCode khash_set_both_(khash_int, std::vector<flags_type> &) noexcept;
210: template <bool>
211: PetscErrorCode khash_set_deleted_(khash_int) noexcept;
212: template <bool>
213: PetscErrorCode khash_set_empty_(khash_int) noexcept;
214: template <bool>
215: PetscErrorCode khash_set_both_(khash_int) noexcept;
217: // produce the default bit pattern:
218: //
219: // v--- deleted: no
220: // 0b101010 ... 10
221: // ^---- empty: yes
222: template <std::size_t mask_width>
223: static PETSC_CONSTEXPR_14 flags_type default_bit_pattern_impl_() noexcept
224: {
225: flags_type x{};
227: for (std::size_t i = 0; i < mask_width; ++i) {
228: if (i % 2) {
229: // odd,
230: x |= 1ULL << i;
231: } else {
232: // even
233: x &= ~(1UL << i);
234: }
235: }
236: return x;
237: }
239: public:
240: PETSC_NODISCARD static PETSC_CONSTEXPR_14 flags_type default_bit_pattern() noexcept
241: {
242: // forces constexpr evaluation, which may not be guaranteed. Note that after GCC 6.1+
243: // tries to constexpr-evaluate _any_ function marked constexpr and will inline evaluate
244: // default_bit_mask_impl_() at any optimization level > 0.
245: //
246: // clang constexpr evaluates this at 3.7 but is inconsistent between versions at which
247: // optimization level the call is fully unraveled.
248: PETSC_CONSTEXPR_14 auto ret = default_bit_pattern_impl_<flag_bucket_width::value>();
249: return ret;
250: }
252: private:
253: template <typename KeyType, typename ValueConstructor>
254: PETSC_NODISCARD std::pair<iterator, bool> find_and_emplace_final_(KeyType &&, ValueConstructor &&) noexcept;
256: PetscErrorCode khash_maybe_rehash_() noexcept;
257: PetscErrorCode khash_erase_(khash_int) noexcept;
259: #if PETSC_KHASH_MAP_USE_OPTIONAL
260: using internal_value_type = std::optional<value_type>;
261: #else
262: using internal_value_type = value_type;
263: #endif
265: std::vector<internal_value_type> values_{};
266: std::vector<flags_type> flags_{};
267: size_type count_ = 0;
268: size_type n_occupied_ = 0;
269: size_type upper_bound_ = 0;
270: };
272: // ==========================================================================================
273: // KHashTable::table_iterator
274: // ==========================================================================================
276: template <typename V, typename H, typename KE>
277: template <bool is_const_it>
278: class KHashTable<V, H, KE>::table_iterator {
279: template <typename U>
280: using conditional_const = util::conditional_t<is_const_it, util::add_const_t<U>, U>;
282: template <bool>
283: friend class table_iterator;
285: friend class KHashTable;
287: public:
288: // internal typedef
289: using table_type = conditional_const<KHashTable>;
290: using khash_int = typename table_type::khash_int;
292: // iterator-related typedefs
293: using iterator_category = std::bidirectional_iterator_tag;
294: using difference_type = typename table_type::difference_type;
295: using value_type = conditional_const<typename table_type::value_type>;
296: using reference = value_type &;
297: using pointer = value_type *;
299: table_iterator() noexcept = default;
300: table_iterator(table_type *map, khash_int it) noexcept : map_{std::move(map)}, it_{std::move(it)} { }
302: table_iterator(const table_iterator &) noexcept = default;
303: table_iterator &operator=(const table_iterator &) noexcept = default;
305: table_iterator(table_iterator &&) noexcept = default;
306: table_iterator &operator=(table_iterator &&) noexcept = default;
308: template <bool other_is_const_it, util::enable_if_t<is_const_it && !other_is_const_it> * = nullptr>
309: table_iterator(const table_iterator<other_is_const_it> &other) noexcept : table_iterator{other.map_, other.it_}
310: {
311: }
313: template <bool other_is_const_it, util::enable_if_t<is_const_it && !other_is_const_it> * = nullptr>
314: table_iterator &operator=(const table_iterator<other_is_const_it> &other) noexcept
315: {
316: // self assignment is OK here
317: PetscFunctionBegin;
318: map_ = other.map_;
319: it_ = other.it_;
320: PetscFunctionReturn(*this);
321: }
323: // prefix
324: table_iterator &operator--() noexcept
325: {
326: constexpr khash_int map_begin = 0;
328: PetscFunctionBegin;
329: // Use of map_begin + 1 instead of map_begin (like in operator++()) is deliberate. We do
330: // not want it_ == map_begin here since that would mean that the while-loop decrements it
331: // out of bounds!
332: // Likewise we are allowed to be 1 past the bucket size, otherwise backwards iteration
333: // would not work!
334: PetscCallAbort(PETSC_COMM_SELF, check_iterator_inbounds_(1, 1));
335: do {
336: --it_;
337: } while ((it_ > map_begin) && !map_->occupied(it_));
338: PetscFunctionReturn(*this);
339: }
341: // postfix
342: table_iterator operator--(int) noexcept
343: {
344: table_iterator old{*this};
346: PetscFunctionBegin;
347: --(*this);
348: PetscFunctionReturn(old);
349: }
351: // prefix
352: table_iterator &operator++() noexcept
353: {
354: khash_int map_end = 0;
356: PetscFunctionBegin;
357: PetscCallAbort(PETSC_COMM_SELF, check_iterator_inbounds_());
358: map_end = map_->bucket_count();
359: do {
360: ++it_;
361: } while (it_ != map_end && !map_->occupied(it_));
362: PetscFunctionReturn(*this);
363: }
365: // postfix
366: table_iterator operator++(int) noexcept
367: {
368: table_iterator old{*this};
370: PetscFunctionBegin;
371: ++(*this);
372: PetscFunctionReturn(old);
373: }
375: PETSC_NODISCARD reference operator*() const noexcept
376: {
377: PetscFunctionBegin;
378: PetscCallAbort(PETSC_COMM_SELF, check_iterator_inbounds_());
379: PetscFunctionReturn(PETSC_OPTIONAL_GET_KEY(map_->values_[it_]));
380: }
382: PETSC_NODISCARD pointer operator->() const noexcept
383: {
384: PetscFunctionBegin;
385: PetscCallAbort(PETSC_COMM_SELF, check_iterator_inbounds_());
386: PetscFunctionReturn(std::addressof(PETSC_OPTIONAL_GET_KEY(map_->values_[it_])));
387: }
389: template <bool rc>
390: PETSC_NODISCARD bool operator==(const table_iterator<rc> &r) const noexcept
391: {
392: return std::tie(map_, it_) == std::tie(r.map_, r.it_);
393: }
395: template <bool rc>
396: PETSC_NODISCARD bool operator!=(const table_iterator<rc> &r) const noexcept
397: {
398: return !(*this == r);
399: }
401: private:
402: table_type *map_ = nullptr;
403: khash_int it_ = 0;
405: PetscErrorCode check_iterator_inbounds_(int map_begin_offset = 0, int map_end_offset = 0) const noexcept
406: {
407: PetscFunctionBegin;
408: if (PetscDefined(USE_DEBUG)) {
409: std::int64_t map_begin = map_begin_offset;
410: std::int64_t map_end = map_end_offset;
412: PetscCheck(map_, PETSC_COMM_SELF, PETSC_ERR_ARG_NULL, "Iterator has a NULL map pointer");
413: map_end += map_->bucket_count();
414: PetscCheck((it_ >= map_begin) && (it_ < map_end), PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Iterator index value %" PRId32 " is out of range for map (%p): [%" PRId64 ", %" PRId64 ")", it_, (void *)map_, map_begin, map_end);
415: } else {
416: static_cast<void>(map_begin_offset);
417: static_cast<void>(map_end_offset);
418: }
419: PetscFunctionReturn(PETSC_SUCCESS);
420: }
421: };
423: // ==========================================================================================
424: // KHashTable - Private API
425: // ==========================================================================================
427: // Generic iterator constructor
428: template <typename V, typename H, typename KE>
429: template <typename Iter>
430: inline KHashTable<V, H, KE>::KHashTable(Iter first, Iter last, std::input_iterator_tag) noexcept
431: {
432: PetscFunctionBegin;
433: PetscCallCXXAbort(PETSC_COMM_SELF, std::copy(std::move(first), std::move(last), std::inserter(*this, begin())));
434: PetscFunctionReturnVoid();
435: }
437: // An optimization for random_access_iterators. Since these mandate that std::distance() is
438: // equivalent to end-begin, we can use this to pre-allocate the hashmap for free before we
439: // insert
440: template <typename V, typename H, typename KE>
441: template <typename Iter>
442: inline KHashTable<V, H, KE>::KHashTable(Iter first, Iter last, std::random_access_iterator_tag) noexcept
443: {
444: PetscFunctionBegin;
445: PetscCallAbort(PETSC_COMM_SELF, reserve(static_cast<size_type>(std::distance(first, last))));
446: PetscCallCXXAbort(PETSC_COMM_SELF, std::copy(std::move(first), std::move(last), std::inserter(*this, begin())));
447: PetscFunctionReturnVoid();
448: }
450: // ------------------------------------------------------------------------------------------
451: // KHashTable - Private API - flag bucket API - accessors
452: // ------------------------------------------------------------------------------------------
454: template <typename V, typename H, typename KE>
455: inline constexpr typename KHashTable<V, H, KE>::khash_int KHashTable<V, H, KE>::flag_bucket_index_(khash_int it) noexcept
456: {
457: return (it % flag_pairs_per_bucket::value) << 1;
458: }
460: template <typename V, typename H, typename KE>
461: inline typename KHashTable<V, H, KE>::flags_type &KHashTable<V, H, KE>::flag_bucket_at_(khash_int it, std::vector<flags_type> &flags) noexcept
462: {
463: return flags[it / flag_pairs_per_bucket::value];
464: }
466: template <typename V, typename H, typename KE>
467: inline const typename KHashTable<V, H, KE>::flags_type &KHashTable<V, H, KE>::flag_bucket_at_(khash_int it, const std::vector<flags_type> &flags) noexcept
468: {
469: return flags[it / flag_pairs_per_bucket::value];
470: }
472: template <typename V, typename H, typename KE>
473: inline typename KHashTable<V, H, KE>::flags_type &KHashTable<V, H, KE>::flag_bucket_at_(khash_int it) noexcept
474: {
475: return flag_bucket_at_(it, flags_);
476: }
478: template <typename V, typename H, typename KE>
479: inline const typename KHashTable<V, H, KE>::flags_type &KHashTable<V, H, KE>::flag_bucket_at_(khash_int it) const noexcept
480: {
481: return flag_bucket_at_(it, flags_);
482: }
484: // ------------------------------------------------------------------------------------------
485: // KHashTable - Private API - flag bucket API - query
486: // ------------------------------------------------------------------------------------------
488: template <typename V, typename H, typename KE>
489: template <unsigned selector>
490: inline bool KHashTable<V, H, KE>::khash_test_flag_(khash_int it, const std::vector<flags_type> &flags) noexcept
491: {
492: static_assert(selector > 0 || selector <= 3, "");
493: return (flag_bucket_at_(it, flags) >> flag_bucket_index_(it)) & selector;
494: }
496: template <typename V, typename H, typename KE>
497: inline bool KHashTable<V, H, KE>::khash_is_del_(khash_int it, const std::vector<flags_type> &flags) noexcept
498: {
499: return khash_test_flag_<1>(it, flags);
500: }
502: template <typename V, typename H, typename KE>
503: inline bool KHashTable<V, H, KE>::khash_is_empty_(khash_int it, const std::vector<flags_type> &flags) noexcept
504: {
505: return khash_test_flag_<2>(it, flags);
506: }
508: template <typename V, typename H, typename KE>
509: inline bool KHashTable<V, H, KE>::khash_is_either_(khash_int it, const std::vector<flags_type> &flags) noexcept
510: {
511: return khash_test_flag_<3>(it, flags);
512: }
514: template <typename V, typename H, typename KE>
515: inline bool KHashTable<V, H, KE>::khash_occupied_(khash_int it, const std::vector<flags_type> &flags) noexcept
516: {
517: return !khash_is_either_(it, flags);
518: }
520: template <typename V, typename H, typename KE>
521: inline bool KHashTable<V, H, KE>::khash_is_del_(khash_int it) const noexcept
522: {
523: return khash_is_del_(it, flags_);
524: }
526: template <typename V, typename H, typename KE>
527: inline bool KHashTable<V, H, KE>::khash_is_empty_(khash_int it) const noexcept
528: {
529: return khash_is_empty_(it, flags_);
530: }
532: template <typename V, typename H, typename KE>
533: inline bool KHashTable<V, H, KE>::khash_is_either_(khash_int it) const noexcept
534: {
535: return khash_is_either_(it, flags_);
536: }
538: // ------------------------------------------------------------------------------------------
539: // KHashTable - Private API - flag bucket API - set
540: // ------------------------------------------------------------------------------------------
542: template <typename V, typename H, typename KE>
543: template <unsigned flag_selector, bool set>
544: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_flag_(khash_int it, std::vector<flags_type> &flags) noexcept
545: {
546: static_assert(flag_selector > 0U && flag_selector <= 3U, "");
548: PetscFunctionBegin;
549: if (set) {
550: flag_bucket_at_(it, flags) |= flag_selector << flag_bucket_index_(it);
551: } else {
552: flag_bucket_at_(it, flags) &= ~(flag_selector << flag_bucket_index_(it));
553: }
554: PetscFunctionReturn(PETSC_SUCCESS);
555: }
557: template <typename V, typename H, typename KE>
558: template <bool b>
559: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_deleted_(khash_int it, std::vector<flags_type> &flags) noexcept
560: {
561: PetscFunctionBegin;
562: PetscCall(khash_set_flag_<1, b>(it, flags));
563: PetscFunctionReturn(PETSC_SUCCESS);
564: }
566: template <typename V, typename H, typename KE>
567: template <bool b>
568: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_empty_(khash_int it, std::vector<flags_type> &flags) noexcept
569: {
570: PetscFunctionBegin;
571: PetscCall(khash_set_flag_<2, b>(it, flags));
572: PetscFunctionReturn(PETSC_SUCCESS);
573: }
575: template <typename V, typename H, typename KE>
576: template <bool b>
577: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_both_(khash_int it, std::vector<flags_type> &flags) noexcept
578: {
579: PetscFunctionBegin;
580: PetscCall(khash_set_flag_<3, b>(it, flags));
581: PetscFunctionReturn(PETSC_SUCCESS);
582: }
584: template <typename V, typename H, typename KE>
585: template <bool b>
586: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_deleted_(khash_int it) noexcept
587: {
588: PetscFunctionBegin;
589: PetscCall(khash_set_deleted_<b>(it, flags_));
590: PetscFunctionReturn(PETSC_SUCCESS);
591: }
593: template <typename V, typename H, typename KE>
594: template <bool b>
595: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_empty_(khash_int it) noexcept
596: {
597: PetscFunctionBegin;
598: PetscCall(khash_set_empty_<b>(it, flags_));
599: PetscFunctionReturn(PETSC_SUCCESS);
600: }
602: template <typename V, typename H, typename KE>
603: template <bool b>
604: inline PetscErrorCode KHashTable<V, H, KE>::khash_set_both_(khash_int it) noexcept
605: {
606: PetscFunctionBegin;
607: PetscCall(khash_set_both_<b>(it, flags_));
608: PetscFunctionReturn(PETSC_SUCCESS);
609: }
611: template <typename V, typename H, typename KE>
612: template <typename KeyType, typename ValueConstructor>
613: inline std::pair<typename KHashTable<V, H, KE>::iterator, bool> KHashTable<V, H, KE>::find_and_emplace_final_(KeyType &&key, ValueConstructor &&constructor) noexcept
614: {
615: khash_int it = 0;
617: PetscFunctionBegin;
618: PetscCallAbort(PETSC_COMM_SELF, khash_maybe_rehash_());
619: {
620: const auto nb = bucket_count();
621: const auto mask = nb - 1;
622: const auto hash = hash_function()(key);
623: auto i = hash & mask;
625: PetscAssertAbort(nb > 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Have %zu bucket count after rehash", nb);
626: if (khash_is_empty_(i)) {
627: it = i; // for speed up
628: } else {
629: const auto last = i;
630: auto site = nb;
631: khash_int step = 0;
633: it = nb;
634: while (!khash_is_empty_(i) && (khash_is_del_(i) || !key_eq()(PETSC_OPTIONAL_GET_KEY(values_[i]), key))) {
635: if (khash_is_del_(i)) site = i;
636: ++step;
637: i = (i + step) & mask;
638: if (i == last) {
639: it = site;
640: break;
641: }
642: }
643: if (it == nb) {
644: // didn't find a completely empty place to put it, see if we can reuse an existing
645: // bucket
646: if (khash_is_empty_(i) && (site != nb)) {
647: // reuse a deleted element (I think)
648: it = site;
649: } else {
650: it = i;
651: }
652: }
653: }
654: }
655: if (occupied(it)) PetscFunctionReturn({make_iterator_(it), false});
656: // not present at all or deleted, so create (or replace) the element using the constructor
657: // lambda
658: PetscCallCXXAbort(PETSC_COMM_SELF, values_[it] = constructor());
659: ++count_;
660: if (khash_is_empty_(it)) ++n_occupied_;
661: // order matters, must do this _after_ we check is_empty() since this call sets is_empty to
662: // false!
663: PetscCallAbort(PETSC_COMM_SELF, khash_set_both_<false>(it));
664: PetscFunctionReturn({make_iterator_(it), true});
665: }
667: template <typename V, typename H, typename KE>
668: inline PetscErrorCode KHashTable<V, H, KE>::khash_maybe_rehash_() noexcept
669: {
670: PetscFunctionBegin;
671: if (n_occupied_ >= upper_bound_) {
672: auto target_size = bucket_count();
674: if (target_size > (size() << 1)) {
675: // clear "deleted" elements
676: --target_size;
677: } else {
678: // expand the hash table
679: ++target_size;
680: }
681: PetscCall(resize(target_size));
682: }
683: PetscFunctionReturn(PETSC_SUCCESS);
684: }
686: template <typename V, typename H, typename KE>
687: inline PetscErrorCode KHashTable<V, H, KE>::khash_erase_(khash_int it) noexcept
688: {
689: PetscFunctionBegin;
690: PetscAssert(it < bucket_count(), PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempting to erase iterator (index %d) which did not exist in the map", it);
691: PetscAssert(count_ > 0, PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempting to erase iterator (index %d) which did not exist in the map, have element count %zu", it, count_);
692: PetscAssert(occupied(it), PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Attempting to erase iterator (index %d) which exists in the map but is not occupied", it);
693: --count_;
694: PetscCall(khash_set_deleted_<true>(it));
695: PetscCallCXX(values_[it] = internal_value_type{});
696: PetscFunctionReturn(PETSC_SUCCESS);
697: }
699: // ==========================================================================================
700: // KHashTable - Protected API
701: // ==========================================================================================
703: template <typename V, typename H, typename KE>
704: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::make_iterator_(khash_int it) noexcept
705: {
706: return {this, it};
707: }
709: template <typename V, typename H, typename KE>
710: inline typename KHashTable<V, H, KE>::const_iterator KHashTable<V, H, KE>::make_iterator_(khash_int it) const noexcept
711: {
712: return {this, it};
713: }
715: template <typename V, typename H, typename KE>
716: template <typename T>
717: inline PetscErrorCode KHashTable<V, H, KE>::khash_find_(T &&key, khash_int *it) const noexcept
718: {
719: const auto nb = bucket_count();
720: auto ret = nb;
722: PetscFunctionBegin;
723: if (nb) {
724: const auto mask = nb - 1;
725: const auto hash = hash_function()(key);
726: auto i = hash & mask;
727: const auto last = i;
728: khash_int step = 0;
730: while (!khash_is_empty_(i) && (khash_is_del_(i) || !key_equal()(PETSC_OPTIONAL_GET_KEY(values_[i]), key))) {
731: ++step;
732: i = (i + step) & mask;
733: if (i == last) {
734: *it = ret;
735: PetscFunctionReturn(PETSC_SUCCESS);
736: }
737: }
738: if (occupied(i)) ret = i;
739: }
740: *it = ret;
741: PetscFunctionReturn(PETSC_SUCCESS);
742: }
744: template <typename V, typename H, typename KE>
745: template <typename KeyType, typename... ValueTypeArgs>
746: inline std::pair<typename KHashTable<V, H, KE>::iterator, bool> KHashTable<V, H, KE>::find_and_emplace_(KeyType &&key, ValueTypeArgs &&...value_ctor_args) noexcept
747: {
748: return find_and_emplace_final_(std::forward<KeyType>(key), [&] { return value_type{std::forward<ValueTypeArgs>(value_ctor_args)...}; });
749: }
751: template <typename V, typename H, typename KE>
752: template <typename KeyValueType>
753: inline std::pair<typename KHashTable<V, H, KE>::iterator, bool> KHashTable<V, H, KE>::find_and_emplace_(KeyValueType &&key_value) noexcept
754: {
755: return find_and_emplace_final_(std::forward<KeyValueType>(key_value), [&] { return std::forward<KeyValueType>(key_value); });
756: }
758: // ==========================================================================================
759: // KHashTable - Public API
760: // ==========================================================================================
762: // Generic iterator constructor
763: template <typename V, typename H, typename KE>
764: template <typename Iter>
765: inline KHashTable<V, H, KE>::KHashTable(Iter first, Iter last) noexcept : KHashTable(std::move(first), std::move(last), typename std::iterator_traits<Iter>::iterator_category{})
766: {
767: }
769: template <typename V, typename H, typename KE>
770: inline KHashTable<V, H, KE>::KHashTable(KHashTable &&other) noexcept :
771: values_(std::move(other.values_)), flags_(std::move(other.flags_)), count_(util::exchange(other.count_, 0)), n_occupied_(util::exchange(other.n_occupied_, 0)), upper_bound_(util::exchange(other.upper_bound_, 0))
772: {
773: }
775: template <typename V, typename H, typename KE>
776: inline KHashTable<V, H, KE> &KHashTable<V, H, KE>::operator=(KHashTable &&other) noexcept
777: {
778: PetscFunctionBegin;
779: if (this != &other) {
780: PetscCallCXXAbort(PETSC_COMM_SELF, values_ = std::move(other.values_));
781: PetscCallCXXAbort(PETSC_COMM_SELF, flags_ = std::move(other.flags_));
782: count_ = util::exchange(other.count_, 0);
783: n_occupied_ = util::exchange(other.n_occupied_, 0);
784: upper_bound_ = util::exchange(other.upper_bound_, 0);
785: }
786: PetscFunctionReturn(*this);
787: }
789: template <typename V, typename H, typename KE>
790: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::begin() noexcept
791: {
792: khash_int it = 0;
794: PetscFunctionBegin;
795: for (; it < bucket_count(); ++it) {
796: if (occupied(it)) break;
797: }
798: PetscFunctionReturn(make_iterator_(it));
799: }
801: template <typename V, typename H, typename KE>
802: inline typename KHashTable<V, H, KE>::const_iterator KHashTable<V, H, KE>::cbegin() const noexcept
803: {
804: khash_int it = 0;
806: PetscFunctionBegin;
807: for (; it < bucket_count(); ++it) {
808: if (occupied(it)) break;
809: }
810: PetscFunctionReturn(make_iterator_(it));
811: }
813: template <typename V, typename H, typename KE>
814: inline typename KHashTable<V, H, KE>::const_iterator KHashTable<V, H, KE>::begin() const noexcept
815: {
816: return cbegin();
817: }
819: template <typename V, typename H, typename KE>
820: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::end() noexcept
821: {
822: return make_iterator_(bucket_count());
823: }
825: template <typename V, typename H, typename KE>
826: inline typename KHashTable<V, H, KE>::const_iterator KHashTable<V, H, KE>::cend() const noexcept
827: {
828: return make_iterator_(bucket_count());
829: }
831: template <typename V, typename H, typename KE>
832: inline typename KHashTable<V, H, KE>::const_iterator KHashTable<V, H, KE>::end() const noexcept
833: {
834: return cend();
835: }
837: template <typename V, typename H, typename KE>
838: inline typename KHashTable<V, H, KE>::size_type KHashTable<V, H, KE>::bucket_count() const noexcept
839: {
840: return values_.size();
841: }
843: template <typename V, typename H, typename KE>
844: inline typename KHashTable<V, H, KE>::size_type KHashTable<V, H, KE>::size() const noexcept
845: {
846: return count_;
847: }
849: template <typename V, typename H, typename KE>
850: inline typename KHashTable<V, H, KE>::size_type KHashTable<V, H, KE>::capacity() const noexcept
851: {
852: return flags_.size() * flag_pairs_per_bucket::value;
853: }
855: template <typename V, typename H, typename KE>
856: inline bool KHashTable<V, H, KE>::empty() const noexcept
857: {
858: return size() == 0;
859: }
861: // REVIEW ME: should really be called rehash()
862: template <typename V, typename H, typename KE>
863: inline PetscErrorCode KHashTable<V, H, KE>::reserve(size_type req_size) noexcept
864: {
865: PetscFunctionBegin;
866: if (size() < req_size) PetscCall(resize(req_size));
867: PetscFunctionReturn(PETSC_SUCCESS);
868: }
870: namespace detail
871: {
873: // templated version of
874: // https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2. See also
875: // https://stackoverflow.com/questions/466204/rounding-up-to-next-power-of-2
876: template <typename T>
877: static inline PETSC_CONSTEXPR_14 T round_up_to_next_pow2(T v) noexcept
878: {
879: static_assert(std::numeric_limits<T>::is_integer && std::is_unsigned<T>::value, "");
880: if (v <= 1) return 1;
881: --v;
882: for (std::size_t i = 1; i < (sizeof(v) * CHAR_BIT); i *= 2) v |= v >> i;
883: ++v;
884: return v;
885: }
887: // compilers sadly don't yet recognize that the above is just searching for the next nonzero
888: // bit (https://godbolt.org/z/3q1qxqK4a) and won't emit the versions below, which usually
889: // boil down to a single tailor-made instruction.
890: //
891: // __builtin_clz():
892: // Returns the number of leading 0-bits in x, starting at the most significant bit
893: // position. If x is 0, the result is undefined.
894: //
895: // see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
897: #if PetscHasBuiltin(__builtin_clz)
898: template <>
899: inline constexpr unsigned int round_up_to_next_pow2(unsigned int v) noexcept
900: {
901: return v <= 1 ? 1 : 1 << ((sizeof(v) * CHAR_BIT) - __builtin_clz(v - 1));
902: }
903: #endif
905: #if PetscHasBuiltin(__builtin_clzl)
906: template <>
907: inline constexpr unsigned long round_up_to_next_pow2(unsigned long v) noexcept
908: {
909: return v <= 1 ? 1 : 1 << ((sizeof(v) * CHAR_BIT) - __builtin_clzl(v - 1));
910: }
911: #endif
913: // both MSVC and Intel compilers lie about having __builtin_clzll so just disable this
914: #if PetscHasBuiltin(__builtin_clzll) && !PetscDefined(HAVE_WINDOWS_COMPILERS)
915: template <>
916: inline constexpr unsigned long long round_up_to_next_pow2(unsigned long long v) noexcept
917: {
918: return v <= 1 ? 1 : 1 << ((sizeof(v) * CHAR_BIT) - __builtin_clzll(v - 1));
919: }
920: #endif
922: template <typename T>
923: static inline constexpr unsigned integer_log2(T x) noexcept
924: {
925: static_assert(std::numeric_limits<T>::is_integer && std::is_unsigned<T>::value, "");
926: return x ? 1 + integer_log2(x >> 1) : std::numeric_limits<unsigned>::max();
927: }
929: } // namespace detail
931: template <typename V, typename H, typename KE>
932: inline PetscErrorCode KHashTable<V, H, KE>::resize(size_type req_size) noexcept
933: {
934: constexpr size_type min_n_buckets = 4;
935: const auto new_n_buckets = std::max(detail::round_up_to_next_pow2(req_size), min_n_buckets);
936: const auto new_size = (new_n_buckets >> 1) + (new_n_buckets >> 2);
938: PetscFunctionBegin;
939: if (req_size == 0) {
940: // resize(0) is nominally equivalent to clear(), but clear() does not actually reduce
941: // capacity (only resets flags_ to default_bit_pattern()). So we manually kill the capacity
942: // first.
943: PetscCallCXX(flags_.clear());
944: PetscCall(clear());
945: PetscFunctionReturn(PETSC_SUCCESS);
946: }
947: // hash table count to be changed (shrink or expand); rehash
948: if (size() < new_size) {
949: const auto old_n_buckets = bucket_count();
950: const auto new_mask = new_n_buckets - 1;
951: const auto khash_fsize = [](size_type size) -> size_type {
952: if (size >= flag_pairs_per_bucket::value) {
953: // use constexpr here to force compiler to evaluate this at all optimization levels
954: constexpr auto shift_val = detail::integer_log2(flag_pairs_per_bucket::value);
956: return size >> shift_val;
957: }
958: return 1;
959: };
960: std::vector<flags_type> new_flags(khash_fsize(new_n_buckets), default_bit_pattern());
962: // grow the hash table, note order is important! we cannot just call
963: // values_.resize(new_n_buckets) because that might drop buckets containing data. The loop
964: // below (if new_n_buckets < bucket_count()) will compress the table, such that we can
965: // shrink afterwards
966: if (old_n_buckets < new_n_buckets) PetscCallCXX(values_.resize(new_n_buckets));
967: for (size_type i = 0; i < old_n_buckets; ++i) {
968: if (!occupied(i)) continue;
969: // kick-out process; sort of like in Cuckoo hashing
970: PetscCall(khash_set_deleted_<true>(i));
971: while (true) {
972: // key is updated every loop from the swap so need to recompute the hash function each
973: // time... could possibly consider stashing the hash value in the key-value pair
974: auto &key = values_[i];
975: const auto hash = hash_function()(PETSC_OPTIONAL_GET_KEY(key));
976: auto j = hash & new_mask;
977: khash_int step = 0;
979: while (!khash_is_empty_(j, new_flags)) {
980: ++step;
981: j = (j + step) & new_mask;
982: }
983: PetscCall(khash_set_empty_<false>(j, new_flags));
984: if (j < old_n_buckets && occupied(j)) {
985: using std::swap;
987: // i == j should never reach this point since occupied(j) (in this case equivalent
988: // to occupied(i)) should never be true because we call khash_set_deleted_(i)
989: // above!
990: PetscAssert(i != j, PETSC_COMM_SELF, PETSC_ERR_PLIB, "i %zu = j %zu. About to swap the same element!", static_cast<std::size_t>(i), static_cast<std::size_t>(j));
991: // kick out the existing element
992: PetscCallCXX(swap(values_[j], key));
993: // mark it as deleted in the old hash table
994: PetscCall(khash_set_deleted_<true>(j));
995: } else {
996: // write the element and jump out of the loop but check that we don't self
997: // move-assign
998: if (i != j) PetscCallCXX(values_[j] = std::move(key));
999: break;
1000: }
1001: }
1002: }
1004: // shrink the hash table
1005: if (old_n_buckets > new_n_buckets) PetscCallCXX(values_.resize(new_n_buckets));
1006: PetscCallCXX(flags_ = std::move(new_flags));
1007: n_occupied_ = count_;
1008: upper_bound_ = new_size;
1009: }
1010: PetscFunctionReturn(PETSC_SUCCESS);
1011: }
1013: template <typename V, typename H, typename KE>
1014: inline PetscErrorCode KHashTable<V, H, KE>::clear() noexcept
1015: {
1016: PetscFunctionBegin;
1017: PetscCallCXX(values_.clear());
1018: PetscCallCXX(std::fill(flags_.begin(), flags_.end(), default_bit_pattern()));
1019: count_ = 0;
1020: n_occupied_ = 0;
1021: upper_bound_ = 0;
1022: PetscAssert(size() == 0, PETSC_COMM_SELF, PETSC_ERR_PLIB, "clear() did not set size (%zu) to 0", size());
1023: PetscFunctionReturn(PETSC_SUCCESS);
1024: }
1026: template <typename V, typename H, typename KE>
1027: inline bool KHashTable<V, H, KE>::occupied(khash_int it) const noexcept
1028: {
1029: return khash_occupied_(it, flags_);
1030: }
1032: template <typename V, typename H, typename KE>
1033: inline bool KHashTable<V, H, KE>::occupied(const_iterator it) const noexcept
1034: {
1035: return occupied(it.it_);
1036: }
1038: template <typename V, typename H, typename KE>
1039: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::erase(iterator pos) noexcept
1040: {
1041: iterator ret(pos);
1043: PetscFunctionBegin;
1044: ++ret;
1045: PetscCallAbort(PETSC_COMM_SELF, khash_erase_(pos.it_));
1046: PetscFunctionReturn(ret);
1047: }
1049: template <typename V, typename H, typename KE>
1050: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::erase(const_iterator pos) noexcept
1051: {
1052: iterator ret(pos);
1054: PetscFunctionBegin;
1055: ++ret;
1056: PetscCallAbort(PETSC_COMM_SELF, khash_erase_(pos.it_));
1057: PetscFunctionReturn(ret);
1058: }
1060: template <typename V, typename H, typename KE>
1061: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::erase(const_iterator begin_pos, const_iterator end_pos) noexcept
1062: {
1063: PetscFunctionBegin;
1064: if (begin_pos == cbegin() && end_pos == cend()) {
1065: PetscCallAbort(PETSC_COMM_SELF, clear());
1066: PetscFunctionReturn(end());
1067: }
1068: for (; begin_pos != end_pos; ++begin_pos) PetscCallAbort(PETSC_COMM_SELF, khash_erase_(begin_pos.it_));
1069: PetscFunctionReturn(make_iterator_(begin_pos.it_));
1070: }
1072: template <typename V, typename H, typename KE>
1073: template <typename... Args>
1074: inline std::pair<typename KHashTable<V, H, KE>::iterator, bool> KHashTable<V, H, KE>::emplace(Args &&...args) noexcept
1075: {
1076: return find_and_emplace_(value_type{std::forward<Args>(args)...});
1077: }
1079: template <typename V, typename H, typename KE>
1080: inline std::pair<typename KHashTable<V, H, KE>::iterator, bool> KHashTable<V, H, KE>::insert(const value_type &val) noexcept
1081: {
1082: return find_and_emplace_(val);
1083: }
1085: template <typename V, typename H, typename KE>
1086: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::insert(const_iterator, const value_type &val) noexcept
1087: {
1088: return insert(val).first;
1089: }
1091: template <typename V, typename H, typename KE>
1092: inline std::pair<typename KHashTable<V, H, KE>::iterator, bool> KHashTable<V, H, KE>::insert(value_type &&val) noexcept
1093: {
1094: return find_and_emplace_(std::move(val));
1095: }
1097: template <typename V, typename H, typename KE>
1098: inline typename KHashTable<V, H, KE>::iterator KHashTable<V, H, KE>::insert(const_iterator, value_type &&val) noexcept
1099: {
1100: return insert(std::move(val)).first;
1101: }
1103: template <typename V, typename H, typename KE>
1104: inline typename KHashTable<V, H, KE>::hasher KHashTable<V, H, KE>::hash_function() const noexcept
1105: {
1106: return this->first();
1107: }
1109: template <typename V, typename H, typename KE>
1110: inline typename KHashTable<V, H, KE>::key_equal KHashTable<V, H, KE>::key_eq() const noexcept
1111: {
1112: return this->second();
1113: }
1115: template <typename V, typename H, typename KE>
1116: inline PetscErrorCode KHashTable<V, H, KE>::shrink_to_fit() noexcept
1117: {
1118: PetscFunctionBegin;
1119: PetscCall(resize(size()));
1120: PetscFunctionReturn(PETSC_SUCCESS);
1121: }
1123: template <typename V, typename H, typename KE>
1124: inline void KHashTable<V, H, KE>::swap(KHashTable &other) noexcept
1125: {
1126: PetscFunctionBegin;
1127: if (PetscUnlikely(this != &other)) {
1128: using std::swap;
1130: swap(values_, other.values_);
1131: swap(flags_, other.flags_);
1132: swap(count_, other.count_);
1133: swap(n_occupied_, other.n_occupied_);
1134: swap(upper_bound_, other.upper_bound_);
1135: }
1136: PetscFunctionReturnVoid();
1137: }
1139: namespace detail
1140: {
1142: template <typename KeyType, typename Hasher>
1143: struct indirect_hasher : Hasher {
1144: using nested_value_type = Hasher;
1145: using key_type = KeyType;
1147: template <typename T>
1148: PETSC_NODISCARD std::size_t operator()(const std::pair<key_type, T> &kv) const noexcept
1149: {
1150: return static_cast<const nested_value_type &>(*this)(kv.first);
1151: }
1153: template <typename T>
1154: PETSC_NODISCARD std::size_t operator()(const std::pair<key_type, T> &kv) noexcept
1155: {
1156: return static_cast<nested_value_type &>(*this)(kv.first);
1157: }
1159: using nested_value_type::operator();
1160: };
1162: template <typename KeyType, typename KeyEqual>
1163: struct indirect_equal : KeyEqual {
1164: using nested_value_type = KeyEqual;
1165: using key_type = KeyType;
1167: template <typename T>
1168: PETSC_NODISCARD bool operator()(const std::pair<key_type, T> &lhs, const std::pair<key_type, T> &rhs) const noexcept
1169: {
1170: return static_cast<const nested_value_type &>(*this)(lhs.first, rhs.first);
1171: }
1173: template <typename T>
1174: PETSC_NODISCARD bool operator()(const std::pair<key_type, T> &lhs, const key_type &rhs) const noexcept
1175: {
1176: return static_cast<const nested_value_type &>(*this)(lhs.first, rhs);
1177: }
1178: };
1180: } // namespace detail
1182: } // namespace khash
1184: // ==========================================================================================
1185: // UnorderedMap - A drop-in replacement for std::unordered_map that is more memory efficient
1186: // and performant.
1187: //
1188: // Has identical API to a C++17 conformant std::unordered_map, and behaves identically to
1189: // it. The only exception is iterator invalidation:
1190: //
1191: // Operation | std::unorderd_map | Petsc::UnorderedMap
1192: // --------------------------------------------|-----------------------|---------------------
1193: // - All read only operations, swap, std::swap | Never | Never
1194: // - clear, operator= | Always | Always
1195: // - rehash, reserve | Always | Only if causes
1196: // | | resizing
1197: // - insert, emplace, emplace_hint, operator[] | Only if causes rehash | Only if it causes
1198: // | | rehash, in which case
1199: // | | rehash will ALWAYS
1200: // | | resize
1201: // - erase | Only to the element | Only to the element
1202: // | erased | erased
1203: // ==========================================================================================
1204: template <typename K, typename T, typename H = std::hash<K>,
1205: #if PETSC_CPP_VERSION >= 14
1206: typename KE = std::equal_to<>
1207: #else
1208: typename KE = std::equal_to<K>
1209: #endif
1210: >
1211: class UnorderedMap;
1213: template <typename KeyType, typename T, typename Hash, typename KeyEqual>
1214: class UnorderedMap : public khash::KHashTable<std::pair<KeyType, T>, khash::detail::indirect_hasher<KeyType, Hash>, khash::detail::indirect_equal<KeyType, KeyEqual>> {
1215: using table_type = khash::KHashTable<std::pair<KeyType, T>, khash::detail::indirect_hasher<KeyType, Hash>, khash::detail::indirect_equal<KeyType, KeyEqual>>;
1216: using typename table_type::khash_int;
1218: public:
1219: // workaround for MSVC bug
1220: // https://developercommunity.visualstudio.com/t/error-c2244-unable-to-match-function-definition-to/225941
1221: using value_type = typename table_type::value_type;
1222: using key_type = typename value_type::first_type;
1223: using mapped_type = typename value_type::second_type;
1224: using hasher = typename table_type::hasher::nested_value_type;
1225: using key_equal = typename table_type::key_equal::nested_value_type;
1226: using size_type = typename table_type::size_type;
1227: using reference = typename table_type::reference;
1228: using const_reference = typename table_type::const_reference;
1229: using iterator = typename table_type::iterator;
1230: using const_iterator = typename table_type::const_iterator;
1232: using table_type::table_type; // inherit constructors
1234: PETSC_NODISCARD iterator find(const key_type &) noexcept;
1235: PETSC_NODISCARD const_iterator find(const key_type &) const noexcept;
1237: template <typename... Args>
1238: std::pair<iterator, bool> emplace(Args &&...) noexcept;
1240: using table_type::erase; // inherit erase overloads
1241: size_type erase(const key_type &) noexcept;
1243: mapped_type &operator[](const key_type &) noexcept;
1245: PETSC_NODISCARD std::pair<iterator, iterator> equal_range(const key_type &) noexcept;
1246: PETSC_NODISCARD std::pair<const_iterator, const_iterator> equal_range(const key_type &) const noexcept;
1248: PETSC_NODISCARD size_type count(const key_type &) const noexcept;
1249: PETSC_NODISCARD bool contains(const key_type &) const noexcept;
1251: // must be declared in class definition...
1252: friend void swap(UnorderedMap &lhs, UnorderedMap &rhs) noexcept
1253: {
1254: PetscFunctionBegin;
1255: PetscCallCXXAbort(PETSC_COMM_SELF, lhs.swap(rhs));
1256: PetscFunctionReturnVoid();
1257: }
1259: private:
1260: template <typename KeyTuple, typename ArgTuple>
1261: PETSC_NODISCARD std::pair<iterator, bool> emplace_(std::piecewise_construct_t, KeyTuple &&, ArgTuple &&) noexcept;
1262: template <typename Key, typename... Args>
1263: PETSC_NODISCARD std::pair<iterator, bool> emplace_(Key &&, Args &&...) noexcept;
1264: };
1266: // ==========================================================================================
1267: // UnorderedMap - Private API
1268: // ==========================================================================================
1270: template <typename K, typename T, typename H, typename KE>
1271: template <typename KeyTuple, typename MappedTuple>
1272: inline std::pair<typename UnorderedMap<K, T, H, KE>::iterator, bool> UnorderedMap<K, T, H, KE>::emplace_(std::piecewise_construct_t pcw, KeyTuple &&key_tuple, MappedTuple &&mapped_type_constructor_args) noexcept
1273: {
1274: // clang-format off
1275: return this->find_and_emplace_(
1276: std::get<0>(key_tuple),
1277: pcw,
1278: std::forward<KeyTuple>(key_tuple),
1279: std::forward<MappedTuple>(mapped_type_constructor_args)
1280: );
1281: // clang-format on
1282: }
1284: template <typename K, typename T, typename H, typename KE>
1285: template <typename Key, typename... Args>
1286: inline std::pair<typename UnorderedMap<K, T, H, KE>::iterator, bool> UnorderedMap<K, T, H, KE>::emplace_(Key &&key, Args &&...mapped_type_constructor_args) noexcept
1287: {
1288: return this->emplace_(std::piecewise_construct, std::forward_as_tuple(std::forward<Key>(key)), std::forward_as_tuple(std::forward<Args>(mapped_type_constructor_args)...));
1289: }
1291: // ==========================================================================================
1292: // UnorderedMap - Public API
1293: // ==========================================================================================
1295: template <typename K, typename T, typename H, typename KE>
1296: inline typename UnorderedMap<K, T, H, KE>::iterator UnorderedMap<K, T, H, KE>::find(const key_type &key) noexcept
1297: {
1298: khash_int it = 0;
1300: PetscFunctionBegin;
1301: PetscCallAbort(PETSC_COMM_SELF, this->khash_find_(key, &it));
1302: PetscFunctionReturn(this->make_iterator_(it));
1303: }
1305: template <typename K, typename T, typename H, typename KE>
1306: inline typename UnorderedMap<K, T, H, KE>::const_iterator UnorderedMap<K, T, H, KE>::find(const key_type &key) const noexcept
1307: {
1308: khash_int it = 0;
1310: PetscFunctionBegin;
1311: PetscCallAbort(PETSC_COMM_SELF, this->khash_find_(key, &it));
1312: PetscFunctionReturn(this->make_iterator_(it));
1313: }
1315: template <typename K, typename T, typename H, typename KE>
1316: template <typename... Args>
1317: inline std::pair<typename UnorderedMap<K, T, H, KE>::iterator, bool> UnorderedMap<K, T, H, KE>::emplace(Args &&...args) noexcept
1318: {
1319: return this->emplace_(std::forward<Args>(args)...);
1320: }
1322: template <typename K, typename T, typename H, typename KE>
1323: inline typename UnorderedMap<K, T, H, KE>::mapped_type &UnorderedMap<K, T, H, KE>::operator[](const key_type &key) noexcept
1324: {
1325: return this->emplace(key).first->second;
1326: }
1328: template <typename K, typename T, typename H, typename KE>
1329: inline typename UnorderedMap<K, T, H, KE>::size_type UnorderedMap<K, T, H, KE>::erase(const key_type &key) noexcept
1330: {
1331: PetscFunctionBegin;
1332: {
1333: auto it = this->find(key);
1335: if (it == this->end()) PetscFunctionReturn(0);
1336: PetscCallCXX(this->erase(it));
1337: }
1338: PetscFunctionReturn(1);
1339: }
1341: template <typename K, typename T, typename H, typename KE>
1342: inline std::pair<typename UnorderedMap<K, T, H, KE>::iterator, typename UnorderedMap<K, T, H, KE>::iterator> UnorderedMap<K, T, H, KE>::equal_range(const key_type &key) noexcept
1343: {
1344: auto it = this->find(key);
1345: return {it, it == this->end() ? it : std::next(it)};
1346: }
1348: template <typename K, typename T, typename H, typename KE>
1349: inline std::pair<typename UnorderedMap<K, T, H, KE>::const_iterator, typename UnorderedMap<K, T, H, KE>::const_iterator> UnorderedMap<K, T, H, KE>::equal_range(const key_type &key) const noexcept
1350: {
1351: auto it = this->find(key);
1352: return {it, it == this->end() ? it : std::next(it)};
1353: }
1355: template <typename K, typename T, typename H, typename KE>
1356: inline typename UnorderedMap<K, T, H, KE>::size_type UnorderedMap<K, T, H, KE>::count(const key_type &key) const noexcept
1357: {
1358: return this->contains(key);
1359: }
1361: template <typename K, typename T, typename H, typename KE>
1362: inline bool UnorderedMap<K, T, H, KE>::contains(const key_type &key) const noexcept
1363: {
1364: return this->find(key) != this->end();
1365: }
1367: // ==========================================================================================
1368: // UnorderedMap - Global functions
1369: // ==========================================================================================
1371: template <typename K, typename T, typename H, typename KE>
1372: PETSC_NODISCARD bool operator==(const UnorderedMap<K, T, H, KE> &lhs, const UnorderedMap<K, T, H, KE> &rhs) noexcept
1373: {
1374: PetscFunctionBegin;
1375: if (lhs.size() != rhs.size()) PetscFunctionReturn(false);
1376: for (auto it = lhs.begin(), lhs_end = lhs.end(), rhs_end = rhs.end(); it != lhs_end; ++it) {
1377: const auto rhs_it = rhs.find(it->first);
1379: if (rhs_it == rhs_end || !(*it == *rhs_it)) PetscFunctionReturn(false);
1380: }
1381: PetscFunctionReturn(true);
1382: }
1384: template <typename K, typename T, typename H, typename KE>
1385: PETSC_NODISCARD bool operator!=(const UnorderedMap<K, T, H, KE> &lhs, const UnorderedMap<K, T, H, KE> &rhs) noexcept
1386: {
1387: return !(lhs == rhs);
1388: }
1390: } // namespace Petsc
1392: #undef PETSC_OPTIONAL_GET_KEY
1394: #if defined(__clang__)
1395: #pragma clang diagnostic pop
1396: #endif