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             :     size_t version = 0;
     186             :     p | version;
     187             :     // Remember to increment the version number when making changes to this
     188             :     // function. Retain support for unpacking data written by previous versions
     189             :     // whenever possible. See `Domain` docs for details.
     190             :     if (version >= 0) {
     191             :       p | data_;
     192             :       p | size_;
     193             :     }
     194             :   }
     195             : 
     196             :  private:
     197             :   template <size_t FMaxSize, class FKey, class FValueType, class FHash,
     198             :             class FKeyEqual>
     199             :   // NOLINTNEXTLINE(readability-redundant-declaration) false positive
     200           0 :   friend bool operator==(
     201             :       const FixedHashMap<FMaxSize, FKey, FValueType, FHash, FKeyEqual>& a,
     202             :       const FixedHashMap<FMaxSize, FKey, FValueType, FHash, FKeyEqual>& b);
     203             : 
     204             :   template <bool Assign, class M>
     205           0 :   std::pair<iterator, bool> insert_or_assign_impl(key_type&& key, M&& obj);
     206             : 
     207           0 :   using storage_type = std::array<std::optional<value_type>, MaxSize>;
     208             : 
     209           0 :   SPECTRE_ALWAYS_INLINE size_type hash(const key_type& key) const {
     210             :     if constexpr (hash_is_perfect) {
     211             :       return Hash{}(key);
     212             :     } else {
     213             :       return Hash{}(key) % MaxSize;
     214             :     }
     215             :   }
     216             : 
     217             :   template <bool IsInserting>
     218           0 :   typename storage_type::iterator get_data_entry(const Key& key);
     219             : 
     220           0 :   typename storage_type::const_iterator get_data_entry(const Key& key) const {
     221             :     // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
     222             :     return const_cast<FixedHashMap&>(*this).get_data_entry<false>(key);
     223             :   }
     224             : 
     225           0 :   iterator unconst(const const_iterator& it) {
     226             :     return iterator(&it.get_optional() - data_.begin() + data_.begin(),
     227             :                     data_.end());
     228             :   }
     229             : 
     230           0 :   SPECTRE_ALWAYS_INLINE static bool is_set(
     231             :       const std::optional<value_type>& opt) {
     232             :     return static_cast<bool>(opt);
     233             :   }
     234             : 
     235           0 :   storage_type data_{};
     236           0 :   size_t size_ = 0;
     237             : };
     238             : 
     239             : /// \cond HIDDEN_SYMBOLS
     240             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     241             :           class KeyEqual>
     242             : class FixedHashMapIterator {
     243             :  public:
     244             :   using iterator_category = std::forward_iterator_tag;
     245             :   using value_type = std::remove_const_t<ValueType>;
     246             :   using difference_type = ptrdiff_t;
     247             :   using pointer = ValueType*;
     248             :   using reference = ValueType&;
     249             : 
     250             :   FixedHashMapIterator() = default;
     251             : 
     252             :   /// Implicit conversion from mutable to const iterator.
     253             :   // NOLINTNEXTLINE(google-explicit-constructor)
     254             :   operator FixedHashMapIterator<MaxSize, Key, const ValueType, Hash, KeyEqual>()
     255             :       const {
     256             :     return {entry_, end_};
     257             :   }
     258             : 
     259             :   reference operator*() const {
     260             :     ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
     261             :     ASSERT(is_set(*entry_),
     262             :            "FixedHashMapIterator points to an invalid value in the map.");
     263             :     // deference pointer, then dereference std::optional
     264             :     return entry_->value();
     265             :   }
     266             :   pointer operator->() const {
     267             :     ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
     268             :     ASSERT(is_set(*entry_),
     269             :            "FixedHashMapIterator points to an invalid value in the map.");
     270             :     return std::addressof(entry_->value());
     271             :   }
     272             : 
     273             :   FixedHashMapIterator& operator++();
     274             :   FixedHashMapIterator operator++(int);
     275             : 
     276             :  private:
     277             :   friend class FixedHashMap<MaxSize, Key, typename value_type::second_type,
     278             :                             Hash, KeyEqual>;
     279             :   friend class FixedHashMapIterator<MaxSize, Key, value_type, Hash, KeyEqual>;
     280             : 
     281             :   friend bool operator==(const FixedHashMapIterator& a,
     282             :                          const FixedHashMapIterator& b) {
     283             :     return a.entry_ == b.entry_;
     284             :   }
     285             :   friend bool operator<(const FixedHashMapIterator& a,
     286             :                         const FixedHashMapIterator& b) {
     287             :     return a.entry_ < b.entry_;
     288             :   }
     289             : 
     290             :   // The rest of the comparison operators don't need access to the
     291             :   // class internals, but they need to be instantiated for each
     292             :   // instantiation of the class.
     293             :   friend bool operator!=(const FixedHashMapIterator& a,
     294             :                          const FixedHashMapIterator& b) {
     295             :     return not(a == b);
     296             :   }
     297             :   friend bool operator>(const FixedHashMapIterator& a,
     298             :                         const FixedHashMapIterator& b) {
     299             :     return b < a;
     300             :   }
     301             :   friend bool operator<=(const FixedHashMapIterator& a,
     302             :                          const FixedHashMapIterator& b) {
     303             :     return not(b < a);
     304             :   }
     305             :   friend bool operator>=(const FixedHashMapIterator& a,
     306             :                          const FixedHashMapIterator& b) {
     307             :     return not(a < b);
     308             :   }
     309             : 
     310             :   using map_optional_type = std::optional<std::remove_const_t<ValueType>>;
     311             :   using optional_type =
     312             :       tmpl::conditional_t<std::is_const<ValueType>::value,
     313             :                           const map_optional_type, map_optional_type>;
     314             : 
     315             :   SPECTRE_ALWAYS_INLINE static bool is_set(const optional_type& opt) {
     316             :     return static_cast<bool>(opt);
     317             :   }
     318             : 
     319             :   FixedHashMapIterator(optional_type* const entry, optional_type* const end)
     320             :       : entry_(entry), end_(end) {
     321             :     if (entry_ != end_ and not*entry_) {
     322             :       operator++();
     323             :     }
     324             :   }
     325             : 
     326             :   optional_type& get_optional() const { return *entry_; }
     327             : 
     328             :   optional_type* entry_{nullptr};
     329             :   optional_type* end_{nullptr};
     330             : };
     331             : 
     332             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     333             :           class KeyEqual>
     334             : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>&
     335             : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++() {
     336             :   ASSERT(entry_ != end_,
     337             :          "Tried to increment an end iterator, which is undefined behavior.");
     338             :   // Move to next element, which might not be the next element in the std::array
     339             :   do {
     340             :     ++entry_;  // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
     341             :   } while (entry_ < end_ and not is_set(*entry_));
     342             :   return *this;
     343             : }
     344             : 
     345             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     346             :           class KeyEqual>
     347             : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>
     348             : FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++(int) {
     349             :   const auto ret = *this;
     350             :   operator++();
     351             :   return ret;
     352             : }
     353             : /// \endcond
     354             : 
     355             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     356             :           class KeyEqual>
     357             : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&
     358             : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator=(
     359             :     const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& other) {
     360             :   if (this == &other) {
     361             :     return *this;
     362             :   }
     363             :   clear();
     364             :   size_ = other.size_;
     365             :   for (size_t i = 0; i < data_.size(); ++i) {
     366             :     const auto& other_optional = gsl::at(other.data_, i);
     367             :     if (is_set(other_optional)) {
     368             :       // The std::optionals cannot be assigned to because they
     369             :       // contain the map keys, which are const, so we have to replace
     370             :       // the contents instead, since that counts as a destroy +
     371             :       // initialize.
     372             :       gsl::at(data_, i).emplace(*other_optional);
     373             :     }
     374             :   }
     375             :   return *this;
     376             : }
     377             : 
     378             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     379             :           class KeyEqual>
     380             : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&
     381             : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator=(
     382             :     FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>&& other) {
     383             :   if (this == &other) {
     384             :     return *this;
     385             :   }
     386             :   clear();
     387             :   size_ = other.size_;
     388             :   for (size_t i = 0; i < data_.size(); ++i) {
     389             :     auto& other_optional = gsl::at(other.data_, i);
     390             :     if (is_set(other_optional)) {
     391             :       // The std::optionals cannot be assigned to because they
     392             :       // contain the map keys, which are const, so we have to replace
     393             :       // the contents instead, since that counts as a destroy +
     394             :       // initialize.
     395             :       gsl::at(data_, i).emplace(std::move(*other_optional));
     396             :     }
     397             :   }
     398             :   return *this;
     399             : }
     400             : 
     401             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     402             :           class KeyEqual>
     403             : FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::FixedHashMap(
     404             :     std::initializer_list<value_type> init) {
     405             :   // size_ is set by calling insert
     406             :   for (const auto& entry : init) {
     407             :     insert(entry);
     408             :   }
     409             : }
     410             : 
     411             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     412             :           class KeyEqual>
     413             : void FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::clear() {
     414             :   for (auto& entry : data_) {
     415             :     entry.reset();
     416             :   }
     417             :   size_ = 0;
     418             : }
     419             : 
     420             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     421             :           class KeyEqual>
     422             : template <bool Assign, class M>
     423             : auto FixedHashMap<MaxSize, Key, ValueType, Hash,
     424           0 :                   KeyEqual>::insert_or_assign_impl(key_type&& key, M&& obj)
     425             :     -> std::pair<iterator, bool> {
     426             :   auto data_it = get_data_entry<true>(key);
     427             :   if (UNLIKELY(data_it == data_.end())) {
     428             :     ERROR("Unable to insert element into FixedHashMap of maximum size "
     429             :           << MaxSize << " because it is full. If the current size (" << size_
     430             :           << ") is not equal to the maximum size then please file an issue "
     431             :              "with the code you used to produce this error. "
     432             :           << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
     433             :                                 "past the last element stored, then this "
     434             :                                 "error may also be triggered."
     435             :                               : ""));
     436             :   }
     437             :   // data_it points to either the existing element or a new bucket to place the
     438             :   // element.
     439             :   const auto is_new_entry = not is_set(*data_it);
     440             :   if (is_new_entry or Assign) {
     441             :     if (is_new_entry) {
     442             :       ++size_;
     443             :     }
     444             :     data_it->emplace(std::move(key), std::forward<M>(obj));
     445             :   }
     446             :   return std::make_pair(iterator{data_it, data_.end()}, is_new_entry);
     447             : }
     448             : 
     449             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     450             :           class KeyEqual>
     451             : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
     452             :     const const_iterator& pos) -> iterator {
     453             :   auto next_it = &(unconst(pos).get_optional());
     454             :   --size_;
     455             :   next_it->reset();
     456             :   // pos now points to an unset entry, advance to next valid one
     457             :   do {
     458             :     ++next_it;
     459             :     if (next_it == data_.end()) {
     460             :       next_it = data_.begin();
     461             :     }
     462             :     if (is_set(*next_it)) {
     463             :       return {next_it, data_.end()};
     464             :     }
     465             :   } while (next_it != &pos.get_optional());
     466             :   return end();
     467             : }
     468             : 
     469             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     470             :           class KeyEqual>
     471             : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::erase(
     472             :     const key_type& key) {
     473             :   auto it = get_data_entry<false>(key);
     474             :   if (it == data_.end() or not is_set(*it)) {
     475             :     return 0;
     476             :   }
     477             :   it->reset();
     478             :   --size_;
     479             :   return 1;
     480             : }
     481             : 
     482             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     483             :           class KeyEqual>
     484             : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
     485             :     const key_type& key) -> mapped_type& {
     486             :   auto it = get_data_entry<false>(key);
     487             :   if (it == data_.end() or not is_set(*it)) {
     488             :     // Use `ERROR_AS` instead of `throw` to print a backtrace.
     489             :     ERROR_AS(get_output(key) + " not in FixedHashMap", std::out_of_range);
     490             :   }
     491             :   return it->value().second;
     492             : }
     493             : 
     494             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     495             :           class KeyEqual>
     496             : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::at(
     497             :     const key_type& key) const -> const mapped_type& {
     498             :   // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
     499             :   return const_cast<FixedHashMap&>(*this).at(key);
     500             : }
     501             : 
     502             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     503             :           class KeyEqual>
     504             : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::operator[](
     505             :     const key_type& key) -> mapped_type& {
     506             :   auto it = get_data_entry<true>(key);
     507             :   if (it == data_.end()) {
     508             :     ERROR("Unable to insert element into FixedHashMap of maximum size "
     509             :           << MaxSize << " because it is full. If the current size (" << size_
     510             :           << ") is not equal to the maximum size then please file an issue "
     511             :              "with the code you used to produce this error. "
     512             :           << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
     513             :                                 "past the last element stored, then this "
     514             :                                 "error may also be triggered."
     515             :                               : ""));
     516             :   }
     517             :   if (not is_set(*it)) {
     518             :     ++size_;
     519             :     it->emplace(key, mapped_type{});
     520             :   }
     521             :   return it->value().second;
     522             : }
     523             : 
     524             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     525             :           class KeyEqual>
     526             : size_t FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::count(
     527             :     const key_type& key) const {
     528             :   const auto it = get_data_entry(key);
     529             :   return it == data_.end() or not is_set(*it) ? 0 : 1;
     530             : }
     531             : 
     532             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     533             :           class KeyEqual>
     534             : template <bool IsInserting>
     535           0 : auto FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>::get_data_entry(
     536             :     const Key& key) -> typename storage_type::iterator {
     537             :   const auto hashed_key = hash(key);
     538             :   auto it = data_.begin() + hashed_key;
     539             :   if constexpr (not hash_is_perfect) {
     540             :     // First search for an existing key.
     541             :     while (not is_set(*it) or it->value().first != key) {
     542             :       if (++it == data_.end()) {
     543             :         it = data_.begin();
     544             :       }
     545             :       if (UNLIKELY(it == data_.begin() + hashed_key)) {
     546             :         // not found, return end iterator to storage_type
     547             :         it = data_.end();
     548             :         break;
     549             :       }
     550             :     }
     551             :     // If we are inserting an element but couldn't find an existing key, then
     552             :     // find the first available bucket.
     553             :     if (IsInserting and it == data_.end()) {
     554             :       it = data_.begin() + hashed_key;
     555             :       while (is_set(*it)) {
     556             :         if (++it == data_.end()) {
     557             :           it = data_.begin();
     558             :         }
     559             :         if (UNLIKELY(it == data_.begin() + hashed_key)) {
     560             :           // could not find any open bucket
     561             :           return data_.end();
     562             :         }
     563             :       }
     564             :     }
     565             :   }
     566             :   return it;
     567             : }
     568             : 
     569             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     570             :           class KeyEqual>
     571           0 : bool operator==(
     572             :     const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
     573             :     const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
     574             :   if (a.size_ != b.size_) {
     575             :     return false;
     576             :   }
     577             :   for (const auto& [key, value] : a) {
     578             :     const auto found_in_b = b.find(key);
     579             :     if (found_in_b == b.end() or found_in_b->second != value) {
     580             :       return false;
     581             :     }
     582             :   }
     583             :   return true;
     584             : }
     585             : 
     586             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     587             :           class KeyEqual>
     588           0 : bool operator!=(
     589             :     const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& a,
     590             :     const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& b) {
     591             :   return not(a == b);
     592             : }
     593             : 
     594             : template <size_t MaxSize, class Key, class ValueType, class Hash,
     595             :           class KeyEqual>
     596           0 : std::ostream& operator<<(
     597             :     std::ostream& os,
     598             :     const FixedHashMap<MaxSize, Key, ValueType, Hash, KeyEqual>& m) {
     599             :   unordered_print_helper(
     600             :       os, std::begin(m), std::end(m),
     601             :       [](std::ostream& out,
     602             :          const typename FixedHashMap<MaxSize, Key, ValueType, Hash,
     603             :                                      KeyEqual>::value_type& entry) {
     604             :         out << "[";
     605             :         print_value(out, entry.first);
     606             :         out << ",";
     607             :         print_value(out, entry.second);
     608             :         out << "]";
     609             :       });
     610             :   return os;
     611             : }