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