kakoune

Fork of kakoune, an acceptable text editor
git clone git://git.laack.co/kakoune.git
Log | Files | Refs

hash_map.hh (12650B)


      1 #ifndef hash_map_hh_INCLUDED
      2 #define hash_map_hh_INCLUDED
      3 
      4 #include "hash.hh"
      5 #include "memory.hh"
      6 #include "vector.hh"
      7 
      8 namespace Kakoune
      9 {
     10 
     11 template<typename T>
     12 constexpr void constexpr_swap(T& lhs, T& rhs)
     13 {
     14     T tmp = std::move(lhs);
     15     lhs = std::move(rhs);
     16     rhs = std::move(tmp);
     17 }
     18 
     19 template<MemoryDomain domain,
     20          template<typename, MemoryDomain> class Container>
     21 struct HashIndex
     22 {
     23     struct Entry
     24     {
     25         size_t hash = 0;
     26         int index = -1;
     27     };
     28 
     29     static constexpr float max_fill_rate = 0.5f;
     30 
     31     constexpr HashIndex() = default;
     32     constexpr HashIndex(size_t count)
     33     {
     34         const size_t min_size = (size_t)(count / max_fill_rate) + 1;
     35         size_t new_size = 4;
     36         while (new_size < min_size)
     37             new_size *= 2;
     38         m_entries.resize(new_size);
     39     }
     40 
     41     using ContainerType = Container<Entry, domain>;
     42 
     43     constexpr void resize(size_t new_size)
     44     {
     45         kak_assert(new_size > m_entries.size());
     46         ContainerType old_entries = std::move(m_entries);
     47         m_entries.resize(new_size);
     48         for (auto& entry : old_entries)
     49         {
     50             if (entry.index >= 0)
     51                 add(entry.hash, entry.index);
     52         }
     53     }
     54 
     55     constexpr void reserve(size_t count)
     56     {
     57         if (count == 0)
     58             return;
     59 
     60         const size_t min_size = (size_t)(count / max_fill_rate) + 1;
     61         size_t new_size = m_entries.empty() ? 4 : m_entries.size();
     62         while (new_size < min_size)
     63             new_size *= 2;
     64 
     65         if (new_size > m_entries.size())
     66             resize(new_size);
     67     }
     68 
     69     constexpr void add(size_t hash, int index)
     70     {
     71         Entry entry{hash, index};
     72         while (true)
     73         {
     74             auto target_slot = compute_slot(entry.hash);
     75             for (auto slot = target_slot; slot < m_entries.size(); ++slot)
     76             {
     77                 if (m_entries[slot].index < 0)
     78                 {
     79                     m_entries[slot] = entry;
     80                     return;
     81                 }
     82 
     83                 // Robin hood hashing
     84                 auto candidate_slot = compute_slot(m_entries[slot].hash);
     85                 if (target_slot < candidate_slot)
     86                 {
     87                     constexpr_swap(m_entries[slot], entry);
     88                     target_slot = candidate_slot;
     89                 }
     90             }
     91             // no free entries found, resize, try again
     92             resize(m_entries.size() * 2);
     93         }
     94     }
     95 
     96     constexpr void remove(size_t hash, int index)
     97     {
     98         for (auto slot = compute_slot(hash); slot < m_entries.size(); ++slot)
     99         {
    100             kak_assert(m_entries[slot].index >= 0);
    101             if (m_entries[slot].index == index)
    102             {
    103                 m_entries[slot].index = -1;
    104                 // Recompact following entries
    105                 for (auto next = slot+1; next < m_entries.size(); ++next)
    106                 {
    107                     if (m_entries[next].index < 0 or
    108                         compute_slot(m_entries[next].hash) == next)
    109                         break;
    110                     kak_assert(compute_slot(m_entries[next].hash) < next);
    111                     constexpr_swap(m_entries[next-1], m_entries[next]);
    112                 }
    113                 break;
    114             }
    115         }
    116     }
    117 
    118     constexpr void ordered_fix_entries(int index)
    119     {
    120         for (auto& entry : m_entries)
    121         {
    122             if (entry.index >= index)
    123                 --entry.index;
    124         }
    125     }
    126 
    127     constexpr void unordered_fix_entries(size_t hash, int old_index, int new_index)
    128     {
    129         for (auto slot = compute_slot(hash); slot < m_entries.size(); ++slot)
    130         {
    131             if (m_entries[slot].index == old_index)
    132             {
    133                 m_entries[slot].index = new_index;
    134                 return;
    135             }
    136         }
    137         kak_assert(false); // entry not found ?!
    138     }
    139 
    140     constexpr const Entry& operator[](size_t index) const { return m_entries[index]; }
    141     constexpr size_t size() const { return m_entries.size(); }
    142     constexpr size_t compute_slot(size_t hash) const
    143     {
    144         // We assume entries.size() is power of 2
    145         return hash & (m_entries.size()-1);
    146     }
    147 
    148     constexpr void clear() { m_entries.clear(); }
    149 
    150 private:
    151     ContainerType m_entries;
    152 };
    153 
    154 template<typename Key, typename Value>
    155 struct HashItem
    156 {
    157     Key key{};
    158     Value value{};
    159 
    160     friend bool operator==(const HashItem&, const HashItem&) = default;
    161 };
    162 
    163 template<typename Key>
    164 struct HashItem<Key, void>
    165 {
    166     Key key;
    167 
    168     friend bool operator==(const HashItem&, const HashItem&) = default;
    169 };
    170 
    171 template<typename Key, typename Value,
    172          MemoryDomain domain = MemoryDomain::Undefined,
    173          template<typename, MemoryDomain> class Container = Vector,
    174          bool multi_key = false>
    175 struct HashMap
    176 {
    177     static constexpr bool has_value = not std::is_void_v<Value>;
    178     using Item = std::conditional_t<has_value, HashItem<Key, Value>, Key>;
    179     using EffectiveValue = std::conditional_t<has_value, Value, const Key>;
    180     using ContainerType = Container<Item, domain>;
    181 
    182     constexpr HashMap() = default;
    183 
    184     constexpr HashMap(std::initializer_list<Item> val) : m_items(val), m_index(val.size())
    185     {
    186         for (int i = 0; i < m_items.size(); ++i)
    187             m_index.add(hash_value(m_items[i].key), i);
    188     }
    189 
    190     template<typename Iterator>
    191     constexpr HashMap(Iterator begin, Iterator end)
    192     {
    193         while (begin != end)
    194             insert(*begin++);
    195     }
    196 
    197     constexpr EffectiveValue& insert(Item item, size_t hash)
    198     {
    199         kak_assert(hash == hash_value(item_key(item)));
    200         if constexpr (not multi_key)
    201         {
    202             if (auto index = find_index(item_key(item), hash); index >= 0)
    203             {
    204                 m_items[index] = std::move(item);
    205                 return item_value(m_items[index]);
    206             }
    207         }
    208 
    209         m_index.reserve(m_items.size()+1);
    210         m_index.add(hash, (int)m_items.size());
    211         m_items.push_back(std::move(item));
    212         return item_value(m_items.back());
    213     }
    214 
    215     constexpr EffectiveValue& insert(Item item)
    216     {
    217         const auto hash = hash_value(item_key(item));
    218         return insert(std::move(item), hash);
    219     }
    220 
    221     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    222     constexpr int find_index(const KeyType& key, size_t hash) const
    223     {
    224         for (auto slot = m_index.compute_slot(hash); slot < m_index.size(); ++slot)
    225         {
    226             auto& entry = m_index[slot];
    227             if (entry.index < 0)
    228                 return -1;
    229             if (entry.hash == hash and item_key(m_items[entry.index]) == key)
    230                 return entry.index;
    231         }
    232         return -1;
    233     }
    234 
    235     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    236     constexpr int find_index(const KeyType& key) const { return find_index(key, hash_value(key)); }
    237 
    238     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    239     constexpr bool contains(const KeyType& key) const { return find_index(key) >= 0; }
    240 
    241     template<typename KeyType> requires IsHashCompatible<Key, std::remove_cvref_t<KeyType>>
    242     constexpr EffectiveValue& operator[](KeyType&& key)
    243     {
    244         const auto hash = hash_value(key);
    245         auto index = find_index(key, hash);
    246         if (index >= 0)
    247             return item_value(m_items[index]);
    248 
    249         m_index.reserve(m_items.size()+1);
    250         m_index.add(hash, (int)m_items.size());
    251         m_items.push_back({Key(std::forward<KeyType>(key))});
    252         return item_value(m_items.back());
    253     }
    254 
    255     template<typename KeyType> requires IsHashCompatible<Key, std::remove_cvref_t<KeyType>>
    256     constexpr const EffectiveValue& get(KeyType&& key) const
    257     {
    258         return const_cast<HashMap&>(*this).get(key);
    259     }
    260 
    261     template<typename KeyType> requires IsHashCompatible<Key, std::remove_cvref_t<KeyType>>
    262     constexpr EffectiveValue& get(KeyType&& key)
    263     {
    264         const auto hash = hash_value(key);
    265         auto index = find_index(key, hash);
    266         kak_assert(index >= 0);
    267         return item_value(m_items[index]);
    268     }
    269 
    270     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    271     constexpr void remove(const KeyType& key)
    272     {
    273         const auto hash = hash_value(key);
    274         int index = find_index(key, hash);
    275         if (index >= 0)
    276         {
    277             [[maybe_unused]] Item keepalive = std::move(m_items[index]);
    278             m_items.erase(m_items.begin() + index);
    279             m_index.remove(hash, index);
    280             m_index.ordered_fix_entries(index);
    281         }
    282     }
    283 
    284     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    285     constexpr void unordered_remove(const KeyType& key)
    286     {
    287         const auto hash = hash_value(key);
    288         int index = find_index(key, hash);
    289         if (index >= 0)
    290         {
    291             [[maybe_unused]] Item keepalive = std::move(m_items[index]);
    292             m_items[index] = std::move(m_items.back());
    293             m_items.pop_back();
    294             m_index.remove(hash, index);
    295             if (index != m_items.size())
    296                 m_index.unordered_fix_entries(hash_value(item_key(m_items[index])), m_items.size(), index);
    297         }
    298     }
    299 
    300     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    301     constexpr void erase(const KeyType& key) { return unordered_remove(key); }
    302 
    303     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    304     constexpr void remove_all(const KeyType& key)
    305     {
    306         const auto hash = hash_value(key);
    307         for (int index = find_index(key, hash); index >= 0;
    308              index = find_index(key, hash))
    309         {
    310             [[maybe_unused]] Item keepalive = std::move(m_items[index]);
    311             m_items.erase(m_items.begin() + index);
    312             m_index.remove(hash, index);
    313             m_index.ordered_fix_entries(index);
    314         }
    315     }
    316 
    317     using iterator = typename ContainerType::iterator;
    318     constexpr iterator begin() { return m_items.begin(); }
    319     constexpr iterator end() { return m_items.end(); }
    320 
    321     using const_iterator = typename ContainerType::const_iterator;
    322     constexpr const_iterator begin() const { return m_items.begin(); }
    323     constexpr const_iterator end() const { return m_items.end(); }
    324 
    325     Item& item(size_t index) { return m_items[index]; }
    326     const Item& item(size_t index) const { return m_items[index]; }
    327 
    328     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    329     constexpr iterator find(const KeyType& key)
    330     {
    331         auto index = find_index(key);
    332         return index >= 0 ? begin() + index : end();
    333     }
    334 
    335     template<typename KeyType> requires IsHashCompatible<Key, KeyType>
    336     constexpr const_iterator find(const KeyType& key) const
    337     {
    338         return const_cast<HashMap*>(this)->find(key);
    339     }
    340 
    341     constexpr void remove(const const_iterator& it)
    342     {
    343         auto index = it - m_items.begin();
    344         const auto hash = hash_value(it->key);
    345         m_index.remove(hash, index);
    346         m_items.erase(it);
    347         m_index.ordered_fix_entries(index);
    348     }
    349 
    350     constexpr void clear() { m_items.clear(); m_index.clear(); }
    351 
    352     constexpr size_t size() const { return m_items.size(); }
    353     constexpr bool empty() const { return m_items.empty(); }
    354     constexpr void reserve(size_t size)
    355     {
    356         m_items.reserve(size);
    357         m_index.reserve(size);
    358     }
    359 
    360     // Equality is taking the order of insertion into account
    361     template<MemoryDomain otherDomain>
    362     constexpr bool operator==(const HashMap<Key, Value, otherDomain, Container>& other) const
    363     {
    364         return size() == other.size() and std::equal(begin(), end(), other.begin());
    365     }
    366 
    367 private:
    368     static auto& item_value(auto& item)
    369     {
    370         if constexpr (has_value) { return item.value; } else { return item; }
    371     }
    372 
    373     static const Key& item_key(const Item& item)
    374     {
    375         if constexpr (has_value) { return item.key; } else { return item; }
    376     }
    377 
    378     ContainerType m_items;
    379     HashIndex<domain, Container> m_index;
    380 };
    381 
    382 template<typename Key, typename Value,
    383          MemoryDomain domain = MemoryDomain::Undefined,
    384          template<typename, MemoryDomain> class Container = Vector>
    385  using MultiHashMap = HashMap<Key, Value, domain, Container, true>;
    386 
    387 template<typename Value,
    388          MemoryDomain domain = MemoryDomain::Undefined,
    389          template<typename, MemoryDomain> class Container = Vector>
    390  using HashSet = HashMap<Value, void, domain, Container>;
    391 
    392 template<typename Value,
    393          MemoryDomain domain = MemoryDomain::Undefined,
    394          template<typename, MemoryDomain> class Container = Vector>
    395  using MultiHashSet = HashMap<Value, void, domain, Container, true>;
    396 
    397 void profile_hash_maps();
    398 
    399 }
    400 
    401 #endif // hash_map_hh_INCLUDED