SpECTRE Documentation Coverage Report
Current view: top level - DataStructures - FixedHashMap.hpp Hit Total Coverage
Commit: 697db44127ce57424c079f629b3283267ec6bd78 Lines: 9 64 14.1 %
Date: 2024-06-21 21:13:41
Legend: Lines: hit not hit

          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             : }

Generated by: LCOV version 1.14