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