Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <array>
7 : #include <cstddef>
8 : #include <iterator>
9 : #include <memory> // std::addressof
10 : #include <optional>
11 : #include <pup.h>
12 : #include <pup_stl.h>
13 : #include <stdexcept>
14 : #include <type_traits>
15 :
16 : #include "Utilities/Algorithm.hpp"
17 : #include "Utilities/ConstantExpressions.hpp"
18 : #include "Utilities/ErrorHandling/Assert.hpp"
19 : #include "Utilities/ErrorHandling/Error.hpp"
20 : #include "Utilities/ForceInline.hpp"
21 : #include "Utilities/GetOutput.hpp"
22 : #include "Utilities/Gsl.hpp"
23 : #include "Utilities/Numeric.hpp"
24 : #include "Utilities/PrintHelpers.hpp"
25 : #include "Utilities/Serialization/PupStlCpp17.hpp"
26 : #include "Utilities/TMPL.hpp"
27 : #include "Utilities/TypeTraits.hpp"
28 :
29 : /// \cond
30 : template <size_t MaxSize, class Key, class ValueType, class Hash,
31 : class KeyEqual>
32 : class FixedHashMapIterator;
33 : /// \endcond
34 :
35 : namespace FixedHashMap_detail {
36 : template <typename T, typename = std::void_t<>>
37 : struct has_is_perfect_member : std::false_type {};
38 :
39 : template <typename T>
40 : struct has_is_perfect_member<T,
41 : std::void_t<decltype(T::template is_perfect<0>)>>
42 : : std::true_type {};
43 :
44 : template <typename T>
45 : constexpr bool has_is_perfect_member_v = has_is_perfect_member<T>::value;
46 :
47 : template <class T, size_t MaxSize,
48 : bool HasIsPerfect = has_is_perfect_member_v<T>>
49 : constexpr bool is_perfect = T::template is_perfect<MaxSize>;
50 :
51 : template <class T, size_t MaxSize>
52 : constexpr bool is_perfect<T, MaxSize, false> = false;
53 : } // namespace FixedHashMap_detail
54 :
55 : /*!
56 : * \ingroup DataStructuresGroup
57 : * \brief A hash table with a compile-time specified maximum size and ability to
58 : * efficiently handle perfect hashes.
59 : *
60 : * There are a few requirements on the types passed to `FixedHashMap`. These
61 : * are:
62 : * - `Key` is CopyConstructible for copy and move semantics, as well as
63 : * serialization
64 : * - `ValueType` is MoveConstructible
65 : * - If `Hash` is a perfect hash for some values of `MaxSize` then in order to
66 : * use the perfect hashing improvements `Hash` must have a member variable
67 : * template `is_perfect` that takes as its only template parameter a `size_t`
68 : * equal to `MaxSize`. A perfect hash must map each `Key` to `[0, MaxSize)`
69 : * uniquely.
70 : * - Keys are distinct.
71 : *
72 : * The interface is similar to std::unordered_map, so see the documentation for
73 : * that for details.
74 : *
75 : * #### Implementation Details
76 : *
77 : * - Uses linear probing for non-perfect hashes.
78 : * - The hash `Hash` is assumed to be a perfect hash for `MaxSize` if
79 : * `Hash::template is_perfect<MaxSize>` is true.
80 : */
81 : template <size_t MaxSize, class Key, class ValueType,
82 : class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
83 1 : class FixedHashMap {
84 : public:
85 0 : static constexpr bool hash_is_perfect =
86 : FixedHashMap_detail::is_perfect<Hash, MaxSize>;
87 :
88 0 : using key_type = Key;
89 0 : using mapped_type = ValueType;
90 0 : using value_type = std::pair<const key_type, mapped_type>;
91 0 : using size_type = size_t;
92 0 : using difference_type = ptrdiff_t;
93 0 : using hasher = Hash;
94 0 : using key_equal = KeyEqual;
95 0 : using reference = value_type&;
96 0 : using const_reference = const value_type&;
97 0 : using pointer = value_type*;
98 0 : using const_pointer = const value_type*;
99 0 : using iterator =
100 : FixedHashMapIterator<MaxSize, key_type, value_type, hasher, key_equal>;
101 0 : using const_iterator =
102 : FixedHashMapIterator<MaxSize, key_type, const value_type, hasher,
103 : key_equal>;
104 :
105 0 : FixedHashMap() = default;
106 0 : FixedHashMap(std::initializer_list<value_type> init);
107 0 : FixedHashMap(const FixedHashMap&) = default;
108 0 : FixedHashMap& operator=(const FixedHashMap& other);
109 0 : FixedHashMap(FixedHashMap&&) = default;
110 0 : FixedHashMap& operator=(FixedHashMap&& other);
111 0 : ~FixedHashMap() = default;
112 :
113 0 : iterator begin() { return unconst(cbegin()); }
114 0 : const_iterator begin() const {
115 : return const_iterator(data_.begin(), data_.end());
116 : }
117 0 : const_iterator cbegin() const { return begin(); }
118 :
119 0 : iterator end() { return unconst(cend()); }
120 0 : const_iterator end() const {
121 : return const_iterator(data_.end(), data_.end());
122 : }
123 0 : const_iterator cend() const { return end(); }
124 :
125 0 : bool empty() const { return size_ == 0; }
126 0 : size_t size() const { return size_; }
127 :
128 0 : void clear();
129 :
130 : /// @{
131 : /// Inserts the element if it does not exists.
132 1 : std::pair<iterator, bool> insert(const value_type& value) {
133 : return insert(value_type(value));
134 : }
135 1 : std::pair<iterator, bool> insert(value_type&& value) {
136 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
137 : return insert_or_assign_impl<false>(const_cast<key_type&&>(value.first),
138 : std::move(value.second));
139 : }
140 : template <typename... Args>
141 1 : std::pair<iterator, bool> emplace(Args&&... args) {
142 : return insert(value_type(std::forward<Args>(args)...));
143 : }
144 : /// @}
145 : /// @{
146 : /// Inserts the element if it does not exists, otherwise assigns to it the new
147 : /// value.
148 : template <class M>
149 1 : std::pair<iterator, bool> insert_or_assign(const key_type& key, M&& obj) {
150 : return insert_or_assign(key_type{key}, std::forward<M>(obj));
151 : }
152 : template <class M>
153 1 : std::pair<iterator, bool> insert_or_assign(key_type&& key, M&& obj) {
154 : return insert_or_assign_impl<true>(std::move(key), std::forward<M>(obj));
155 : }
156 : /// @}
157 :
158 0 : iterator erase(const const_iterator& pos);
159 0 : size_t erase(const key_type& key);
160 :
161 0 : mapped_type& at(const key_type& key);
162 0 : const mapped_type& at(const key_type& key) const;
163 0 : mapped_type& operator[](const key_type& key);
164 :
165 0 : size_t count(const key_type& key) const;
166 0 : iterator find(const key_type& key) {
167 : return unconst(std::as_const(*this).find(key));
168 : }
169 0 : const_iterator find(const key_type& key) const {
170 : auto it = get_data_entry(key);
171 : return it != data_.end() and is_set(*it) ? const_iterator(&*it, data_.end())
172 : : end();
173 : }
174 :
175 : /// Check if `key` is in the map
176 1 : bool contains(const key_type& key) const { return find(key) != end(); }
177 :
178 : /// Get key equal function object
179 1 : key_equal key_eq() const { return key_equal{}; }
180 : /// Get hash function object
181 1 : hasher hash_function() const { return hasher{}; }
182 :
183 : // NOLINTNEXTLINE(google-runtime-references)
184 0 : void pup(PUP::er& p);
185 :
186 : private:
187 : template <size_t FMaxSize, class FKey, class FValueType, class FHash,
188 : class FKeyEqual>
189 : // NOLINTNEXTLINE(readability-redundant-declaration) false positive
190 0 : friend bool operator==(
191 : const FixedHashMap<FMaxSize, FKey, FValueType, FHash, FKeyEqual>& a,
192 : const FixedHashMap<FMaxSize, FKey, FValueType, FHash, FKeyEqual>& b);
193 :
194 : template <bool Assign, class M>
195 0 : std::pair<iterator, bool> insert_or_assign_impl(key_type&& key, M&& obj);
196 :
197 0 : using storage_type = std::array<std::optional<value_type>, MaxSize>;
198 :
199 0 : SPECTRE_ALWAYS_INLINE size_type hash(const key_type& key) const {
200 : if constexpr (hash_is_perfect) {
201 : return Hash{}(key);
202 : } else {
203 : return Hash{}(key) % MaxSize;
204 : }
205 : }
206 :
207 : template <bool IsInserting>
208 0 : typename storage_type::iterator get_data_entry(const Key& key);
209 :
210 0 : typename storage_type::const_iterator get_data_entry(const Key& key) const {
211 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
212 : return const_cast<FixedHashMap&>(*this).get_data_entry<false>(key);
213 : }
214 :
215 0 : iterator unconst(const const_iterator& it) {
216 : return iterator(&it.get_optional() - data_.begin() + data_.begin(),
217 : data_.end());
218 : }
219 :
220 0 : SPECTRE_ALWAYS_INLINE static bool is_set(
221 : const std::optional<value_type>& opt) {
222 : return static_cast<bool>(opt);
223 : }
224 :
225 0 : storage_type data_{};
226 0 : tmpl::conditional_t<(MaxSize <= 255), uint8_t, size_t> size_ = 0;
227 : };
228 :
229 : template <size_t MaxSize, class Key, class ValueType, class Hash,
230 : class KeyEqual>
231 : void FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::pup(PUP::er& p) {
232 : // Remember to increment the version number when making changes to this
233 : // function. Retain support for unpacking data written by previous versions
234 : // whenever possible. See `Domain` docs for details.
235 : const uint8_t current_version = 1;
236 : if (p.isUnpacking()) {
237 : uint8_t version_read{0};
238 : p | version_read;
239 : if (LIKELY(version_read > 0)) {
240 : p | data_;
241 : p | size_;
242 : } else {
243 : // Read next 3 bytes.
244 : p | version_read;
245 : p | version_read;
246 : p | version_read;
247 : // Read "bottom" of version
248 : uint32_t old_version{0};
249 : p | old_version;
250 : if (UNLIKELY(old_version > 0)) {
251 : ERROR(
252 : "Incompatible version format for Direction. Expected to receive "
253 : "version 0 but got "
254 : << old_version);
255 : }
256 : p | data_;
257 : if constexpr (MaxSize <= 255) {
258 : size_t read_size{0};
259 : p | read_size;
260 : size_ = static_cast<uint8_t>(read_size);
261 : } else {
262 : p | size_;
263 : }
264 : }
265 : } else {
266 : uint8_t version_write = current_version;
267 : p | version_write;
268 : p | data_;
269 : p | size_;
270 : }
271 : }
272 :
273 : /// \cond HIDDEN_SYMBOLS
274 : template <size_t MaxSize, class Key, class ValueType, class Hash,
275 : class KeyEqual>
276 : class FixedHashMapIterator {
277 : public:
278 : using iterator_category = std::forward_iterator_tag;
279 : using value_type = std::remove_const_t<ValueType>;
280 : using difference_type = ptrdiff_t;
281 : using pointer = ValueType*;
282 : using reference = ValueType&;
283 :
284 : FixedHashMapIterator() = default;
285 :
286 : /// Implicit conversion from mutable to const iterator.
287 : // NOLINTNEXTLINE(google-explicit-constructor)
288 : operator FixedHashMapIterator<MaxSize, Key, const ValueType, Hash, KeyEqual>()
289 : const {
290 : return {entry_, end_};
291 : }
292 :
293 : reference operator*() const {
294 : ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
295 : ASSERT(is_set(*entry_),
296 : "FixedHashMapIterator points to an invalid value in the map.");
297 : // deference pointer, then dereference std::optional
298 : return entry_->value();
299 : }
300 : pointer operator->() const {
301 : ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
302 : ASSERT(is_set(*entry_),
303 : "FixedHashMapIterator points to an invalid value in the map.");
304 : return std::addressof(entry_->value());
305 : }
306 :
307 : FixedHashMapIterator& operator++();
308 : FixedHashMapIterator operator++(int);
309 :
310 : private:
311 : friend class FixedHashMap<MaxSize, Key, typename value_type::second_type,
312 : Hash, KeyEqual>;
313 : friend class FixedHashMapIterator<MaxSize, Key, value_type, Hash, KeyEqual>;
314 :
315 : friend bool operator==(const FixedHashMapIterator& a,
316 : const FixedHashMapIterator& b) {
317 : return a.entry_ == b.entry_;
318 : }
319 : friend bool operator<(const FixedHashMapIterator& a,
320 : const FixedHashMapIterator& b) {
321 : return a.entry_ < b.entry_;
322 : }
323 :
324 : // The rest of the comparison operators don't need access to the
325 : // class internals, but they need to be instantiated for each
326 : // instantiation of the class.
327 : friend bool operator!=(const FixedHashMapIterator& a,
328 : const FixedHashMapIterator& b) {
329 : return not(a == b);
330 : }
331 : friend bool operator>(const FixedHashMapIterator& a,
332 : const FixedHashMapIterator& b) {
333 : return b < a;
334 : }
335 : friend bool operator<=(const FixedHashMapIterator& a,
336 : const FixedHashMapIterator& b) {
337 : return not(b < a);
338 : }
339 : friend bool operator>=(const FixedHashMapIterator& a,
340 : const FixedHashMapIterator& b) {
341 : return not(a < b);
342 : }
343 :
344 : using map_optional_type = std::optional<std::remove_const_t<ValueType>>;
345 : using optional_type =
346 : tmpl::conditional_t<std::is_const<ValueType>::value,
347 : const map_optional_type, map_optional_type>;
348 :
349 : SPECTRE_ALWAYS_INLINE static bool is_set(const optional_type& opt) {
350 : return static_cast<bool>(opt);
351 : }
352 :
353 : FixedHashMapIterator(optional_type* const entry, optional_type* const end)
354 : : entry_(entry), end_(end) {
355 : if (entry_ != end_ and not*entry_) {
356 : operator++();
357 : }
358 : }
359 :
360 : optional_type& get_optional() const { return *entry_; }
361 :
362 : optional_type* entry_{nullptr};
363 : optional_type* end_{nullptr};
364 : };
365 :
366 : template <size_t MaxSize, class Key, class ValueType, class Hash,
367 : class KeyEqual>
368 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>&
369 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++() {
370 : ASSERT(entry_ != end_,
371 : "Tried to increment an end iterator, which is undefined behavior.");
372 : // Move to next element, which might not be the next element in the std::array
373 : do {
374 : ++entry_; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
375 : } while (entry_ < end_ and not is_set(*entry_));
376 : return *this;
377 : }
378 :
379 : template <size_t MaxSize, class Key, class ValueType, class Hash,
380 : class KeyEqual>
381 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>
382 : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++(int) {
383 : const auto ret = *this;
384 : operator++();
385 : return ret;
386 : }
387 : /// \endcond
388 :
389 : template <size_t MaxSize, class Key, class ValueType, class Hash,
390 : class KeyEqual>
391 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&
392 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator=(
393 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& other) {
394 : if (this == &other) {
395 : return *this;
396 : }
397 : clear();
398 : size_ = other.size_;
399 : for (size_t i = 0; i < data_.size(); ++i) {
400 : const auto& other_optional = gsl::at(other.data_, i);
401 : if (is_set(other_optional)) {
402 : // The std::optionals cannot be assigned to because they
403 : // contain the map keys, which are const, so we have to replace
404 : // the contents instead, since that counts as a destroy +
405 : // initialize.
406 : gsl::at(data_, i).emplace(*other_optional);
407 : }
408 : }
409 : return *this;
410 : }
411 :
412 : template <size_t MaxSize, class Key, class ValueType, class Hash,
413 : class KeyEqual>
414 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&
415 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator=(
416 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&& other) {
417 : if (this == &other) {
418 : return *this;
419 : }
420 : clear();
421 : size_ = other.size_;
422 : for (size_t i = 0; i < data_.size(); ++i) {
423 : auto& other_optional = gsl::at(other.data_, i);
424 : if (is_set(other_optional)) {
425 : // The std::optionals cannot be assigned to because they
426 : // contain the map keys, which are const, so we have to replace
427 : // the contents instead, since that counts as a destroy +
428 : // initialize.
429 : gsl::at(data_, i).emplace(std::move(*other_optional));
430 : }
431 : }
432 : return *this;
433 : }
434 :
435 : template <size_t MaxSize, class Key, class ValueType, class Hash,
436 : class KeyEqual>
437 : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::FixedHashMap(
438 : std::initializer_list<value_type> init) {
439 : // size_ is set by calling insert
440 : for (const auto& entry : init) {
441 : insert(entry);
442 : }
443 : }
444 :
445 : template <size_t MaxSize, class Key, class ValueType, class Hash,
446 : class KeyEqual>
447 : void FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::clear() {
448 : for (auto& entry : data_) {
449 : entry.reset();
450 : }
451 : size_ = 0;
452 : }
453 :
454 : template <size_t MaxSize, class Key, class ValueType, class Hash,
455 : class KeyEqual>
456 : template <bool Assign, class M>
457 : auto FixedHashMap<MaxSize, Key, ValueType, Hash,
458 0 : KeyEqual>::insert_or_assign_impl(key_type&& key, M&& obj)
459 : -> std::pair<iterator, bool> {
460 : auto data_it = get_data_entry<true>(key);
461 : if (UNLIKELY(data_it == data_.end())) {
462 : ERROR("Unable to insert element into FixedHashMap of maximum size "
463 : << MaxSize << " because it is full. If the current size ("
464 : << static_cast<size_t>(size_)
465 : << ") is not equal to the maximum size then please file an issue "
466 : "with the code you used to produce this error. "
467 : << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
468 : "past the last element stored, then this "
469 : "error may also be triggered."
470 : : ""));
471 : }
472 : // data_it points to either the existing element or a new bucket to place the
473 : // element.
474 : const auto is_new_entry = not is_set(*data_it);
475 : if (is_new_entry or Assign) {
476 : if (is_new_entry) {
477 : ++size_;
478 : }
479 : data_it->emplace(std::move(key), std::forward<M>(obj));
480 : }
481 : return std::make_pair(iterator{data_it, data_.end()}, is_new_entry);
482 : }
483 :
484 : template <size_t MaxSize, class Key, class ValueType, class Hash,
485 : class KeyEqual>
486 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
487 : const const_iterator& pos) -> iterator {
488 : auto next_it = &(unconst(pos).get_optional());
489 : --size_;
490 : next_it->reset();
491 : // pos now points to an unset entry, advance to next valid one
492 : do {
493 : ++next_it;
494 : if (next_it == data_.end()) {
495 : next_it = data_.begin();
496 : }
497 : if (is_set(*next_it)) {
498 : return {next_it, data_.end()};
499 : }
500 : } while (next_it != &pos.get_optional());
501 : return end();
502 : }
503 :
504 : template <size_t MaxSize, class Key, class ValueType, class Hash,
505 : class KeyEqual>
506 : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
507 : const key_type& key) {
508 : auto it = get_data_entry<false>(key);
509 : if (it == data_.end() or not is_set(*it)) {
510 : return 0;
511 : }
512 : it->reset();
513 : --size_;
514 : return 1;
515 : }
516 :
517 : template <size_t MaxSize, class Key, class ValueType, class Hash,
518 : class KeyEqual>
519 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
520 : const key_type& key) -> mapped_type& {
521 : auto it = get_data_entry<false>(key);
522 : if (it == data_.end() or not is_set(*it)) {
523 : // Use `ERROR_AS` instead of `throw` to print a backtrace.
524 : ERROR_AS(get_output(key) + " not in FixedHashMap", std::out_of_range);
525 : }
526 : return it->value().second;
527 : }
528 :
529 : template <size_t MaxSize, class Key, class ValueType, class Hash,
530 : class KeyEqual>
531 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
532 : const key_type& key) const -> const mapped_type& {
533 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
534 : return const_cast<FixedHashMap&>(*this).at(key);
535 : }
536 :
537 : template <size_t MaxSize, class Key, class ValueType, class Hash,
538 : class KeyEqual>
539 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator[](
540 : const key_type& key) -> mapped_type& {
541 : auto it = get_data_entry<true>(key);
542 : if (it == data_.end()) {
543 : ERROR("Unable to insert element into FixedHashMap of maximum size "
544 : << MaxSize << " because it is full. If the current size ("
545 : << static_cast<size_t>(size_)
546 : << ") is not equal to the maximum size then please file an issue "
547 : "with the code you used to produce this error. "
548 : << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
549 : "past the last element stored, then this "
550 : "error may also be triggered."
551 : : ""));
552 : }
553 : if (not is_set(*it)) {
554 : ++size_;
555 : it->emplace(key, mapped_type{});
556 : }
557 : return it->value().second;
558 : }
559 :
560 : template <size_t MaxSize, class Key, class ValueType, class Hash,
561 : class KeyEqual>
562 : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::count(
563 : const key_type& key) const {
564 : const auto it = get_data_entry(key);
565 : return it == data_.end() or not is_set(*it) ? 0 : 1;
566 : }
567 :
568 : template <size_t MaxSize, class Key, class ValueType, class Hash,
569 : class KeyEqual>
570 : template <bool IsInserting>
571 0 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::get_data_entry(
572 : const Key& key) -> typename storage_type::iterator {
573 : const auto hashed_key = hash(key);
574 : auto it = data_.begin() + hashed_key;
575 : if constexpr (not hash_is_perfect) {
576 : // First search for an existing key.
577 : while (not is_set(*it) or it->value().first != key) {
578 : if (++it == data_.end()) {
579 : it = data_.begin();
580 : }
581 : if (UNLIKELY(it == data_.begin() + hashed_key)) {
582 : // not found, return end iterator to storage_type
583 : it = data_.end();
584 : break;
585 : }
586 : }
587 : // If we are inserting an element but couldn't find an existing key, then
588 : // find the first available bucket.
589 : if (IsInserting and it == data_.end()) {
590 : it = data_.begin() + hashed_key;
591 : while (is_set(*it)) {
592 : if (++it == data_.end()) {
593 : it = data_.begin();
594 : }
595 : if (UNLIKELY(it == data_.begin() + hashed_key)) {
596 : // could not find any open bucket
597 : return data_.end();
598 : }
599 : }
600 : }
601 : }
602 : return it;
603 : }
604 :
605 : template <size_t MaxSize, class Key, class ValueType, class Hash,
606 : class KeyEqual>
607 0 : bool operator==(
608 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
609 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
610 : if (a.size_ != b.size_) {
611 : return false;
612 : }
613 : for (const auto& [key, value] : a) {
614 : const auto found_in_b = b.find(key);
615 : if (found_in_b == b.end() or found_in_b->second != value) {
616 : return false;
617 : }
618 : }
619 : return true;
620 : }
621 :
622 : template <size_t MaxSize, class Key, class ValueType, class Hash,
623 : class KeyEqual>
624 0 : bool operator!=(
625 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
626 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
627 : return not(a == b);
628 : }
629 :
630 : template <size_t MaxSize, class Key, class ValueType, class Hash,
631 : class KeyEqual>
632 0 : std::ostream& operator<<(
633 : std::ostream& os,
634 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& m) {
635 : unordered_print_helper(
636 : os, std::begin(m), std::end(m),
637 : [](std::ostream& out,
638 : const typename FixedHashMap<MaxSize, Key, ValueType, Hash,
639 : KeyEqual>::value_type& entry) {
640 : out << "[";
641 : print_value(out, entry.first);
642 : out << ",";
643 : print_value(out, entry.second);
644 : out << "]";
645 : });
646 : return os;
647 : }
|
