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 0 : static constexpr bool hash_is_perfect =
85 : FixedHashMap_detail::is_perfect<Hash, MaxSize>;
86 :
87 : public:
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 (" << size_
464 : << ") is not equal to the maximum size then please file an issue "
465 : "with the code you used to produce this error. "
466 : << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
467 : "past the last element stored, then this "
468 : "error may also be triggered."
469 : : ""));
470 : }
471 : // data_it points to either the existing element or a new bucket to place the
472 : // element.
473 : const auto is_new_entry = not is_set(*data_it);
474 : if (is_new_entry or Assign) {
475 : if (is_new_entry) {
476 : ++size_;
477 : }
478 : data_it->emplace(std::move(key), std::forward<M>(obj));
479 : }
480 : return std::make_pair(iterator{data_it, data_.end()}, is_new_entry);
481 : }
482 :
483 : template <size_t MaxSize, class Key, class ValueType, class Hash,
484 : class KeyEqual>
485 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
486 : const const_iterator& pos) -> iterator {
487 : auto next_it = &(unconst(pos).get_optional());
488 : --size_;
489 : next_it->reset();
490 : // pos now points to an unset entry, advance to next valid one
491 : do {
492 : ++next_it;
493 : if (next_it == data_.end()) {
494 : next_it = data_.begin();
495 : }
496 : if (is_set(*next_it)) {
497 : return {next_it, data_.end()};
498 : }
499 : } while (next_it != &pos.get_optional());
500 : return end();
501 : }
502 :
503 : template <size_t MaxSize, class Key, class ValueType, class Hash,
504 : class KeyEqual>
505 : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
506 : const key_type& key) {
507 : auto it = get_data_entry<false>(key);
508 : if (it == data_.end() or not is_set(*it)) {
509 : return 0;
510 : }
511 : it->reset();
512 : --size_;
513 : return 1;
514 : }
515 :
516 : template <size_t MaxSize, class Key, class ValueType, class Hash,
517 : class KeyEqual>
518 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
519 : const key_type& key) -> mapped_type& {
520 : auto it = get_data_entry<false>(key);
521 : if (it == data_.end() or not is_set(*it)) {
522 : // Use `ERROR_AS` instead of `throw` to print a backtrace.
523 : ERROR_AS(get_output(key) + " not in FixedHashMap", std::out_of_range);
524 : }
525 : return it->value().second;
526 : }
527 :
528 : template <size_t MaxSize, class Key, class ValueType, class Hash,
529 : class KeyEqual>
530 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
531 : const key_type& key) const -> const mapped_type& {
532 : // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
533 : return const_cast<FixedHashMap&>(*this).at(key);
534 : }
535 :
536 : template <size_t MaxSize, class Key, class ValueType, class Hash,
537 : class KeyEqual>
538 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator[](
539 : const key_type& key) -> mapped_type& {
540 : auto it = get_data_entry<true>(key);
541 : if (it == data_.end()) {
542 : ERROR("Unable to insert element into FixedHashMap of maximum size "
543 : << MaxSize << " because it is full. If the current size (" << size_
544 : << ") is not equal to the maximum size then please file an issue "
545 : "with the code you used to produce this error. "
546 : << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
547 : "past the last element stored, then this "
548 : "error may also be triggered."
549 : : ""));
550 : }
551 : if (not is_set(*it)) {
552 : ++size_;
553 : it->emplace(key, mapped_type{});
554 : }
555 : return it->value().second;
556 : }
557 :
558 : template <size_t MaxSize, class Key, class ValueType, class Hash,
559 : class KeyEqual>
560 : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::count(
561 : const key_type& key) const {
562 : const auto it = get_data_entry(key);
563 : return it == data_.end() or not is_set(*it) ? 0 : 1;
564 : }
565 :
566 : template <size_t MaxSize, class Key, class ValueType, class Hash,
567 : class KeyEqual>
568 : template <bool IsInserting>
569 0 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::get_data_entry(
570 : const Key& key) -> typename storage_type::iterator {
571 : const auto hashed_key = hash(key);
572 : auto it = data_.begin() + hashed_key;
573 : if constexpr (not hash_is_perfect) {
574 : // First search for an existing key.
575 : while (not is_set(*it) or it->value().first != key) {
576 : if (++it == data_.end()) {
577 : it = data_.begin();
578 : }
579 : if (UNLIKELY(it == data_.begin() + hashed_key)) {
580 : // not found, return end iterator to storage_type
581 : it = data_.end();
582 : break;
583 : }
584 : }
585 : // If we are inserting an element but couldn't find an existing key, then
586 : // find the first available bucket.
587 : if (IsInserting and it == data_.end()) {
588 : it = data_.begin() + hashed_key;
589 : while (is_set(*it)) {
590 : if (++it == data_.end()) {
591 : it = data_.begin();
592 : }
593 : if (UNLIKELY(it == data_.begin() + hashed_key)) {
594 : // could not find any open bucket
595 : return data_.end();
596 : }
597 : }
598 : }
599 : }
600 : return it;
601 : }
602 :
603 : template <size_t MaxSize, class Key, class ValueType, class Hash,
604 : class KeyEqual>
605 0 : bool operator==(
606 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
607 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
608 : if (a.size_ != b.size_) {
609 : return false;
610 : }
611 : for (const auto& [key, value] : a) {
612 : const auto found_in_b = b.find(key);
613 : if (found_in_b == b.end() or found_in_b->second != value) {
614 : return false;
615 : }
616 : }
617 : return true;
618 : }
619 :
620 : template <size_t MaxSize, class Key, class ValueType, class Hash,
621 : class KeyEqual>
622 0 : bool operator!=(
623 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
624 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
625 : return not(a == b);
626 : }
627 :
628 : template <size_t MaxSize, class Key, class ValueType, class Hash,
629 : class KeyEqual>
630 0 : std::ostream& operator<<(
631 : std::ostream& os,
632 : const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& m) {
633 : unordered_print_helper(
634 : os, std::begin(m), std::end(m),
635 : [](std::ostream& out,
636 : const typename FixedHashMap<MaxSize, Key, ValueType, Hash,
637 : KeyEqual>::value_type& entry) {
638 : out << "[";
639 : print_value(out, entry.first);
640 : out << ",";
641 : print_value(out, entry.second);
642 : out << "]";
643 : });
644 : return os;
645 : }
|
