Lethe Open-Source Library version 1.2.0
Developer Guide
Loading...
Searching...
No Matches
unordered_dense.h
Go to the documentation of this file.
1///////////////////////// ankerl::unordered_dense::{map, set}
2////////////////////////////
3
4// A fast & densely stored hashmap and hashset based on robin-hood backward
5// shift deletion. Version 4.4.0 https://github.com/martinus/unordered_dense
6//
7// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
8// SPDX-License-Identifier: MIT
9// Copyright (c) 2022-2023 Martin Leitner-Ankerl <martin.ankerl@gmail.com>
10//
11// Permission is hereby granted, free of charge, to any person obtaining a copy
12// of this software and associated documentation files (the "Software"), to deal
13// in the Software without restriction, including without limitation the rights
14// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15// copies of the Software, and to permit persons to whom the Software is
16// furnished to do so, subject to the following conditions:
17//
18// The above copyright notice and this permission notice shall be included in
19// all copies or substantial portions of the Software.
20//
21// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27// SOFTWARE.
28
29#ifndef ANKERL_UNORDERED_DENSE_H
30#define ANKERL_UNORDERED_DENSE_H
31
32// see https://semver.org/spec/v2.0.0.html
33#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR \
34 4 // NOLINT(cppcoreguidelines-macro-usage) incompatible API changes
35#define ANKERL_UNORDERED_DENSE_VERSION_MINOR \
36 4 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible functionality
37#define ANKERL_UNORDERED_DENSE_VERSION_PATCH \
38 0 // NOLINT(cppcoreguidelines-macro-usage) backwards compatible bug fixes
39
40// API versioning with inline namespace, see
41// https://www.foonathan.net/2018/11/inline-namespaces/
42
43// NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
44#define ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch) \
45 v##major##_##minor##_##patch
46// NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
47#define ANKERL_UNORDERED_DENSE_VERSION_CONCAT(major, minor, patch) \
48 ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch)
49#define ANKERL_UNORDERED_DENSE_NAMESPACE \
50 ANKERL_UNORDERED_DENSE_VERSION_CONCAT(ANKERL_UNORDERED_DENSE_VERSION_MAJOR, \
51 ANKERL_UNORDERED_DENSE_VERSION_MINOR, \
52 ANKERL_UNORDERED_DENSE_VERSION_PATCH)
53
54#if defined(_MSVC_LANG)
55# define ANKERL_UNORDERED_DENSE_CPP_VERSION _MSVC_LANG
56#else
57# define ANKERL_UNORDERED_DENSE_CPP_VERSION __cplusplus
58#endif
59
60#if defined(__GNUC__)
61// NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
62# define ANKERL_UNORDERED_DENSE_PACK(decl) decl __attribute__((__packed__))
63#elif defined(_MSC_VER)
64// NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
65# define ANKERL_UNORDERED_DENSE_PACK(decl) \
66 __pragma(pack(push, 1)) decl __pragma(pack(pop))
67#endif
68
69// exceptions
70#if defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)
71# define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() \
72 1 // NOLINT(cppcoreguidelines-macro-usage)
73#else
74# define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() \
75 0 // NOLINT(cppcoreguidelines-macro-usage)
76#endif
77#ifdef _MSC_VER
78# define ANKERL_UNORDERED_DENSE_NOINLINE __declspec(noinline)
79#else
80# define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
81#endif
82
83// defined in unordered_dense.cpp
84#if !defined(ANKERL_UNORDERED_DENSE_EXPORT)
85# define ANKERL_UNORDERED_DENSE_EXPORT
86#endif
87
88#if ANKERL_UNORDERED_DENSE_CPP_VERSION < 201703L
89# error ankerl::unordered_dense requires C++17 or higher
90#else
91# include <array> // for array
92# include <cstdint> // for uint64_t, uint32_t, uint8_t, UINT64_C
93# include <cstring> // for size_t, memcpy, memset
94# include <functional> // for equal_to, hash
95# include <initializer_list> // for initializer_list
96# include <iterator> // for pair, distance
97# include <limits> // for numeric_limits
98# include <memory> // for allocator, allocator_traits, shared_ptr
99# include <optional> // for optional
100# include <stdexcept> // for out_of_range
101# include <string> // for basic_string
102# include <string_view> // for basic_string_view, hash
103# include <tuple> // for forward_as_tuple
104# include <type_traits> // for enable_if_t, declval, conditional_t, ena...
105# include <utility> // for forward, exchange, pair, as_const, piece...
106# include <vector> // for vector
107# if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() == 0
108# include <cstdlib> // for abort
109# endif
110
111# if defined(__has_include)
112# if __has_include(<memory_resource>)
113# define ANKERL_UNORDERED_DENSE_PMR \
114 std::pmr // NOLINT(cppcoreguidelines-macro-usage)
115# include <memory_resource> // for polymorphic_allocator
116# elif __has_include(<experimental/memory_resource>)
117# define ANKERL_UNORDERED_DENSE_PMR \
118 std::experimental::pmr // NOLINT(cppcoreguidelines-macro-usage)
119# include <experimental/memory_resource> // for polymorphic_allocator
120# endif
121# endif
122
123# if defined(_MSC_VER) && defined(_M_X64)
124# include <intrin.h>
125# pragma intrinsic(_umul128)
126# endif
127
128# if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
129# define ANKERL_UNORDERED_DENSE_LIKELY(x) \
130 __builtin_expect(x, 1) // NOLINT(cppcoreguidelines-macro-usage)
131# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) \
132 __builtin_expect(x, 0) // NOLINT(cppcoreguidelines-macro-usage)
133# else
134# define ANKERL_UNORDERED_DENSE_LIKELY(x) \
135 (x) // NOLINT(cppcoreguidelines-macro-usage)
136# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) \
137 (x) // NOLINT(cppcoreguidelines-macro-usage)
138# endif
139
140namespace ankerl::unordered_dense
141{
142 inline namespace ANKERL_UNORDERED_DENSE_NAMESPACE
143 {
144
145 namespace detail
146 {
147
148# if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()
149
150 // make sure this is not inlined as it is slow and dramatically enlarges
151 // code, thus making other inlinings more difficult. Throws are also
152 // generally the slow path.
153 [[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void
154 on_error_key_not_found()
155 {
156 throw std::out_of_range(
157 "ankerl::unordered_dense::map::at(): key not found");
158 }
159 [[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void
160 on_error_bucket_overflow()
161 {
162 throw std::overflow_error(
163 "ankerl::unordered_dense: reached max bucket size, cannot increase size");
164 }
165 [[noreturn]] inline ANKERL_UNORDERED_DENSE_NOINLINE void
166 on_error_too_many_elements()
167 {
168 throw std::out_of_range(
169 "ankerl::unordered_dense::map::replace(): too many elements");
170 }
171
172# else
173
174 [[noreturn]] inline void
175 on_error_key_not_found()
176 {
177 abort();
178 }
179 [[noreturn]] inline void
180 on_error_bucket_overflow()
181 {
182 abort();
183 }
184 [[noreturn]] inline void
185 on_error_too_many_elements()
186 {
187 abort();
188 }
189
190# endif
191
192 } // namespace detail
193
194 // hash
195 // ///////////////////////////////////////////////////////////////////////
196
197 // This is a stripped-down implementation of wyhash:
198 // https://github.com/wangyi-fudan/wyhash No big-endian support (because
199 // different values on different machines don't matter), hardcodes seed and
200 // the secret, reformats the code, and clang-tidy fixes.
201 namespace detail::wyhash
202 {
203
204 inline void
205 mum(uint64_t *a, uint64_t *b)
206 {
207# if defined(__SIZEOF_INT128__)
208 __uint128_t r = *a;
209 r *= *b;
210 *a = static_cast<uint64_t>(r);
211 *b = static_cast<uint64_t>(r >> 64U);
212# elif defined(_MSC_VER) && defined(_M_X64)
213 *a = _umul128(*a, *b, b);
214# else
215 uint64_t ha = *a >> 32U;
216 uint64_t hb = *b >> 32U;
217 uint64_t la = static_cast<uint32_t>(*a);
218 uint64_t lb = static_cast<uint32_t>(*b);
219 uint64_t hi{};
220 uint64_t lo{};
221 uint64_t rh = ha * hb;
222 uint64_t rm0 = ha * lb;
223 uint64_t rm1 = hb * la;
224 uint64_t rl = la * lb;
225 uint64_t t = rl + (rm0 << 32U);
226 auto c = static_cast<uint64_t>(t < rl);
227 lo = t + (rm1 << 32U);
228 c += static_cast<uint64_t>(lo < t);
229 hi = rh + (rm0 >> 32U) + (rm1 >> 32U) + c;
230 *a = lo;
231 *b = hi;
232# endif
233 }
234
235 // multiply and xor mix function, aka MUM
236 [[nodiscard]] inline auto
237 mix(uint64_t a, uint64_t b) -> uint64_t
238 {
239 mum(&a, &b);
240 return a ^ b;
241 }
242
243 // read functions. WARNING: we don't care about endianness, so results are
244 // different on big endian!
245 [[nodiscard]] inline auto
246 r8(const uint8_t *p) -> uint64_t
247 {
248 uint64_t v{};
249 std::memcpy(&v, p, 8U);
250 return v;
251 }
252
253 [[nodiscard]] inline auto
254 r4(const uint8_t *p) -> uint64_t
255 {
256 uint32_t v{};
257 std::memcpy(&v, p, 4);
258 return v;
259 }
260
261 // reads 1, 2, or 3 bytes
262 [[nodiscard]] inline auto
263 r3(const uint8_t *p, size_t k) -> uint64_t
264 {
265 return (static_cast<uint64_t>(p[0]) << 16U) |
266 (static_cast<uint64_t>(p[k >> 1U]) << 8U) | p[k - 1];
267 }
268
269 [[maybe_unused]] [[nodiscard]] inline auto
270 hash(void const *key, size_t len) -> uint64_t
271 {
272 static constexpr auto secret = std::array{UINT64_C(0xa0761d6478bd642f),
273 UINT64_C(0xe7037ed1a0b428db),
274 UINT64_C(0x8ebc6af09c88c6e3),
275 UINT64_C(0x589965cc75374cc3)};
276
277 auto const *p = static_cast<uint8_t const *>(key);
278 uint64_t seed = secret[0];
279 uint64_t a{};
280 uint64_t b{};
281 if (ANKERL_UNORDERED_DENSE_LIKELY(len <= 16))
282 {
283 if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 4))
284 {
285 a = (r4(p) << 32U) | r4(p + ((len >> 3U) << 2U));
286 b = (r4(p + len - 4) << 32U) |
287 r4(p + len - 4 - ((len >> 3U) << 2U));
288 }
289 else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0))
290 {
291 a = r3(p, len);
292 b = 0;
293 }
294 else
295 {
296 a = 0;
297 b = 0;
298 }
299 }
300 else
301 {
302 size_t i = len;
303 if (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 48))
304 {
305 uint64_t see1 = seed;
306 uint64_t see2 = seed;
307 do
308 {
309 seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
310 see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
311 see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
312 p += 48;
313 i -= 48;
314 }
315 while (ANKERL_UNORDERED_DENSE_LIKELY(i > 48));
316 seed ^= see1 ^ see2;
317 }
318 while (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 16))
319 {
320 seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
321 i -= 16;
322 p += 16;
323 }
324 a = r8(p + i - 16);
325 b = r8(p + i - 8);
326 }
327
328 return mix(secret[1] ^ len, mix(a ^ secret[1], b ^ seed));
329 }
330
331 [[nodiscard]] inline auto
332 hash(uint64_t x) -> uint64_t
333 {
334 return detail::wyhash::mix(x, UINT64_C(0x9E3779B97F4A7C15));
335 }
336
337 } // namespace detail::wyhash
338
339 ANKERL_UNORDERED_DENSE_EXPORT template <typename T, typename Enable = void>
340 struct hash
341 {
342 auto
343 operator()(T const &obj) const noexcept(noexcept(
344 std::declval<std::hash<T>>().operator()(std::declval<T const &>())))
345 -> uint64_t
346 {
347 return std::hash<T>{}(obj);
348 }
349 };
350
351 template <typename CharT>
352 struct hash<std::basic_string<CharT>>
353 {
354 using is_avalanching = void;
355 auto
356 operator()(std::basic_string<CharT> const &str) const noexcept -> uint64_t
357 {
358 return detail::wyhash::hash(str.data(), sizeof(CharT) * str.size());
359 }
360 };
361
362 template <typename CharT>
363 struct hash<std::basic_string_view<CharT>>
364 {
365 using is_avalanching = void;
366 auto
367 operator()(std::basic_string_view<CharT> const &sv) const noexcept
368 -> uint64_t
369 {
370 return detail::wyhash::hash(sv.data(), sizeof(CharT) * sv.size());
371 }
372 };
373
374 template <class T>
375 struct hash<T *>
376 {
377 using is_avalanching = void;
378 auto
379 operator()(T *ptr) const noexcept -> uint64_t
380 {
381 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
382 return detail::wyhash::hash(reinterpret_cast<uintptr_t>(ptr));
383 }
384 };
385
386 template <class T>
387 struct hash<std::unique_ptr<T>>
388 {
389 using is_avalanching = void;
390 auto
391 operator()(std::unique_ptr<T> const &ptr) const noexcept -> uint64_t
392 {
393 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
394 return detail::wyhash::hash(reinterpret_cast<uintptr_t>(ptr.get()));
395 }
396 };
397
398 template <class T>
399 struct hash<std::shared_ptr<T>>
400 {
401 using is_avalanching = void;
402 auto
403 operator()(std::shared_ptr<T> const &ptr) const noexcept -> uint64_t
404 {
405 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
406 return detail::wyhash::hash(reinterpret_cast<uintptr_t>(ptr.get()));
407 }
408 };
409
410 template <typename Enum>
411 struct hash<Enum, typename std::enable_if<std::is_enum<Enum>::value>::type>
412 {
413 using is_avalanching = void;
414 auto
415 operator()(Enum e) const noexcept -> uint64_t
416 {
417 using underlying = typename std::underlying_type_t<Enum>;
418 return detail::wyhash::hash(static_cast<underlying>(e));
419 }
420 };
421
422 template <typename... Args>
423 struct tuple_hash_helper
424 {
425 // Converts the value into 64bit. If it is an integral type, just cast it.
426 // Mixing is doing the rest. If it isn't an integral we need to hash it.
427 template <typename Arg>
428 [[nodiscard]] constexpr static auto
429 to64(Arg const &arg) -> uint64_t
430 {
431 if constexpr (std::is_integral_v<Arg> || std::is_enum_v<Arg>)
432 {
433 return static_cast<uint64_t>(arg);
434 }
435 else
436 {
437 return hash<Arg>{}(arg);
438 }
439 }
440
441 [[nodiscard]] static auto
442 mix64(uint64_t state, uint64_t v) -> uint64_t
443 {
444 return detail::wyhash::mix(state + v, uint64_t{0x9ddfea08eb382d69});
445 }
446
447 // Creates a buffer that holds all the data from each element of the
448 // tuple. If possible we memcpy the data directly. If not, we hash the
449 // object and use this for the array. Size of the array is known at
450 // compile time, and memcpy is optimized away, so filling the buffer is
451 // highly efficient. Finally, call wyhash with this buffer.
452 template <typename T, std::size_t... Idx>
453 [[nodiscard]] static auto
454 calc_hash(T const &t, std::index_sequence<Idx...>) noexcept -> uint64_t
455 {
456 auto h = uint64_t{};
457 ((h = mix64(h, to64(std::get<Idx>(t)))), ...);
458 return h;
459 }
460 };
461
462 template <typename... Args>
463 struct hash<std::tuple<Args...>> : tuple_hash_helper<Args...>
464 {
465 using is_avalanching = void;
466 auto
467 operator()(std::tuple<Args...> const &t) const noexcept -> uint64_t
468 {
469 return tuple_hash_helper<Args...>::calc_hash(
470 t, std::index_sequence_for<Args...>{});
471 }
472 };
473
474 template <typename A, typename B>
475 struct hash<std::pair<A, B>> : tuple_hash_helper<A, B>
476 {
477 using is_avalanching = void;
478 auto
479 operator()(std::pair<A, B> const &t) const noexcept -> uint64_t
480 {
481 return tuple_hash_helper<A, B>::calc_hash(
482 t, std::index_sequence_for<A, B>{});
483 }
484 };
485
486// NOLINTNEXTLINE(cppcoreguidelines-macro-usage)
487# define ANKERL_UNORDERED_DENSE_HASH_STATICCAST(T) \
488 template <> \
489 struct hash<T> \
490 { \
491 using is_avalanching = void; \
492 auto \
493 operator()(T const &obj) const noexcept -> uint64_t \
494 { \
495 return detail::wyhash::hash(static_cast<uint64_t>(obj)); \
496 } \
497 }
498
499# if defined(__GNUC__) && !defined(__clang__)
500# pragma GCC diagnostic push
501# pragma GCC diagnostic ignored "-Wuseless-cast"
502# endif
503 // see https://en.cppreference.com/w/cpp/utility/hash
504 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(bool);
505 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char);
506 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(signed char);
507 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned char);
508# if ANKERL_UNORDERED_DENSE_CPP_VERSION >= 202002L && defined(__cpp_char8_t)
509 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char8_t);
510# endif
511 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char16_t);
512 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char32_t);
513 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(wchar_t);
514 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(short);
515 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned short);
516 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(int);
517 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned int);
518 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(long);
519 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(long long);
520 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned long);
521 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(unsigned long long);
522
523# if defined(__GNUC__) && !defined(__clang__)
524# pragma GCC diagnostic pop
525# endif
526
527 // bucket_type //////////////////////////////////////////////////////////
528
529 namespace bucket_type
530 {
531
532 struct standard
533 {
534 static constexpr uint32_t dist_inc = 1U
535 << 8U; // skip 1 byte fingerprint
536 static constexpr uint32_t fingerprint_mask =
537 dist_inc - 1; // mask for 1 byte of fingerprint
538
539 uint32_t
540 m_dist_and_fingerprint; // upper 3 byte: distance to original bucket.
541 // lower byte: fingerprint from hash
542 uint32_t m_value_idx; // index into the m_values vector.
543 };
544
545 ANKERL_UNORDERED_DENSE_PACK(struct big {
546 static constexpr uint32_t dist_inc = 1U
547 << 8U; // skip 1 byte fingerprint
548 static constexpr uint32_t fingerprint_mask =
549 dist_inc - 1; // mask for 1 byte of fingerprint
550
551 uint32_t
552 m_dist_and_fingerprint; // upper 3 byte: distance to original bucket.
553 // lower byte: fingerprint from hash
554 size_t m_value_idx; // index into the m_values vector.
555 });
556
557 } // namespace bucket_type
558
559 namespace detail
560 {
561
562 struct nonesuch
563 {};
564
565 template <class Default,
566 class AlwaysVoid,
567 template <class...>
568 class Op,
569 class... Args>
570 struct detector
571 {
572 using value_t = std::false_type;
573 using type = Default;
574 };
575
576 template <class Default, template <class...> class Op, class... Args>
577 struct detector<Default, std::void_t<Op<Args...>>, Op, Args...>
578 {
579 using value_t = std::true_type;
580 using type = Op<Args...>;
581 };
582
583 template <template <class...> class Op, class... Args>
584 using is_detected =
585 typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
586
587 template <template <class...> class Op, class... Args>
588 constexpr bool is_detected_v = is_detected<Op, Args...>::value;
589
590 template <typename T>
591 using detect_avalanching = typename T::is_avalanching;
592
593 template <typename T>
594 using detect_is_transparent = typename T::is_transparent;
595
596 template <typename T>
597 using detect_iterator = typename T::iterator;
598
599 template <typename T>
600 using detect_reserve = decltype(std::declval<T &>().reserve(size_t{}));
601
602 // enable_if helpers
603
604 template <typename Mapped>
605 constexpr bool is_map_v = !std::is_void_v<Mapped>;
606
607 // clang-format off
608template <typename Hash, typename KeyEqual>
609constexpr bool is_transparent_v = is_detected_v<detect_is_transparent, Hash> && is_detected_v<detect_is_transparent, KeyEqual>;
610 // clang-format on
611
612 template <typename From, typename To1, typename To2>
613 constexpr bool is_neither_convertible_v =
614 !std::is_convertible_v<From, To1> && !std::is_convertible_v<From, To2>;
615
616 template <typename T>
617 constexpr bool has_reserve = is_detected_v<detect_reserve, T>;
618
619 // base type for map has mapped_type
620 template <class T>
621 struct base_table_type_map
622 {
623 using mapped_type = T;
624 };
625
626 // base type for set doesn't have mapped_type
627 struct base_table_type_set
628 {};
629
630 } // namespace detail
631
632 // Very much like std::deque, but faster for indexing (in most cases). As of
633 // now this doesn't implement the full std::vector API, but merely what's
634 // necessary to work as an underlying container for
635 // ankerl::unordered_dense::{map, set}. It allocates blocks of equal size
636 // and puts them into the m_blocks vector. That means it can grow simply by
637 // adding a new block to the back of m_blocks, and doesn't double its size
638 // like an std::vector. The disadvantage is that memory is not linear and
639 // thus there is one more indirection necessary for indexing.
640 template <typename T,
641 typename Allocator = std::allocator<T>,
642 size_t MaxSegmentSizeBytes = 4096>
643 class segmented_vector
644 {
645 template <bool IsConst>
646 class iter_t;
647
648 public:
649 using allocator_type = Allocator;
650 using pointer = typename std::allocator_traits<allocator_type>::pointer;
651 using const_pointer =
652 typename std::allocator_traits<allocator_type>::const_pointer;
653 using difference_type =
654 typename std::allocator_traits<allocator_type>::difference_type;
655 using value_type = T;
656 using size_type = std::size_t;
657 using reference = T &;
658 using const_reference = T const &;
659 using iterator = iter_t<false>;
660 using const_iterator = iter_t<true>;
661
662 private:
663 using vec_alloc = typename std::allocator_traits<
664 Allocator>::template rebind_alloc<pointer>;
665 std::vector<pointer, vec_alloc> m_blocks{};
666 size_t m_size{};
667
668 // Calculates the maximum number for x in (s << x) <= max_val
669 static constexpr auto
670 num_bits_closest(size_t max_val, size_t s) -> size_t
671 {
672 auto f = size_t{0};
673 while (s << (f + 1) <= max_val)
674 {
675 ++f;
676 }
677 return f;
678 }
679
680 using self_t = segmented_vector<T, Allocator, MaxSegmentSizeBytes>;
681 static constexpr auto num_bits =
682 num_bits_closest(MaxSegmentSizeBytes, sizeof(T));
683 static constexpr auto num_elements_in_block = 1U << num_bits;
684 static constexpr auto mask = num_elements_in_block - 1U;
685
686 /**
687 * Iterator class doubles as const_iterator and iterator
688 */
689 template <bool IsConst>
690 class iter_t
691 {
692 using ptr_t =
693 typename std::conditional_t<IsConst,
694 segmented_vector::const_pointer const *,
695 segmented_vector::pointer *>;
696 ptr_t m_data{};
697 size_t m_idx{};
698
699 template <bool B>
700 friend class iter_t;
701
702 public:
703 using difference_type = segmented_vector::difference_type;
704 using value_type = T;
705 using reference = typename std::
706 conditional_t<IsConst, value_type const &, value_type &>;
707 using pointer =
708 typename std::conditional_t<IsConst,
709 segmented_vector::const_pointer,
710 segmented_vector::pointer>;
711 using iterator_category = std::forward_iterator_tag;
712
713 iter_t() noexcept = default;
714
715 template <
716 bool OtherIsConst,
717 typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
718 // NOLINTNEXTLINE(google-explicit-constructor,hicpp-explicit-conversions)
719 constexpr iter_t(iter_t<OtherIsConst> const &other) noexcept
720 : m_data(other.m_data)
721 , m_idx(other.m_idx)
722 {}
723
724 constexpr iter_t(ptr_t data, size_t idx) noexcept
725 : m_data(data)
726 , m_idx(idx)
727 {}
728
729 template <
730 bool OtherIsConst,
731 typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
732 constexpr auto
733 operator=(iter_t<OtherIsConst> const &other) noexcept -> iter_t &
734 {
735 m_data = other.m_data;
736 m_idx = other.m_idx;
737 return *this;
738 }
739
740 constexpr auto
741 operator++() noexcept -> iter_t &
742 {
743 ++m_idx;
744 return *this;
745 }
746
747 constexpr auto
748 operator+(difference_type diff) noexcept -> iter_t
749 {
750 return {m_data,
751 static_cast<size_t>(static_cast<difference_type>(m_idx) +
752 diff)};
753 }
754
755 template <bool OtherIsConst>
756 constexpr auto
757 operator-(iter_t<OtherIsConst> const &other) noexcept -> difference_type
758 {
759 return static_cast<difference_type>(m_idx) -
760 static_cast<difference_type>(other.m_idx);
761 }
762
763 constexpr auto
764 operator*() const noexcept -> reference
765 {
766 return m_data[m_idx >> num_bits][m_idx & mask];
767 }
768
769 constexpr auto
770 operator->() const noexcept -> pointer
771 {
772 return &m_data[m_idx >> num_bits][m_idx & mask];
773 }
774
775 template <bool O>
776 constexpr auto
777 operator==(iter_t<O> const &o) const noexcept -> bool
778 {
779 return m_idx == o.m_idx;
780 }
781
782 template <bool O>
783 constexpr auto
784 operator!=(iter_t<O> const &o) const noexcept -> bool
785 {
786 return !(*this == o);
787 }
788 };
789
790 // slow path: need to allocate a new segment every once in a while
791 void
792 increase_capacity()
793 {
794 auto ba = Allocator(m_blocks.get_allocator());
795 pointer block =
796 std::allocator_traits<Allocator>::allocate(ba, num_elements_in_block);
797 m_blocks.push_back(block);
798 }
799
800 // Moves everything from other
801 void
802 append_everything_from(segmented_vector &&other)
803 {
804 reserve(size() + other.size());
805 for (auto &&o : other)
806 {
807 emplace_back(std::move(o));
808 }
809 }
810
811 // Copies everything from other
812 void
813 append_everything_from(segmented_vector const &other)
814 {
815 reserve(size() + other.size());
816 for (auto const &o : other)
817 {
818 emplace_back(o);
819 }
820 }
821
822 void
823 dealloc()
824 {
825 auto ba = Allocator(m_blocks.get_allocator());
826 for (auto ptr : m_blocks)
827 {
828 std::allocator_traits<Allocator>::deallocate(ba,
829 ptr,
830 num_elements_in_block);
831 }
832 }
833
834 [[nodiscard]] static constexpr auto
835 calc_num_blocks_for_capacity(size_t capacity)
836 {
837 return (capacity + num_elements_in_block - 1U) / num_elements_in_block;
838 }
839
840 public:
841 segmented_vector() = default;
842
843 // NOLINTNEXTLINE(google-explicit-constructor,hicpp-explicit-conversions)
844 segmented_vector(Allocator alloc)
845 : m_blocks(vec_alloc(alloc))
846 {}
847
848 segmented_vector(segmented_vector &&other, Allocator alloc)
849 : segmented_vector(alloc)
850 {
851 *this = std::move(other);
852 }
853
854 segmented_vector(segmented_vector const &other, Allocator alloc)
855 : m_blocks(vec_alloc(alloc))
856 {
857 append_everything_from(other);
858 }
859
860 segmented_vector(segmented_vector &&other) noexcept
861 : segmented_vector(std::move(other), get_allocator())
862 {}
863
864 segmented_vector(segmented_vector const &other)
865 {
866 append_everything_from(other);
867 }
868
869 auto
870 operator=(segmented_vector const &other) -> segmented_vector &
871 {
872 if (this == &other)
873 {
874 return *this;
875 }
876 clear();
877 append_everything_from(other);
878 return *this;
879 }
880
881 auto
882 operator=(segmented_vector &&other) noexcept -> segmented_vector &
883 {
884 clear();
885 dealloc();
886 if (other.get_allocator() == get_allocator())
887 {
888 m_blocks = std::move(other.m_blocks);
889 m_size = std::exchange(other.m_size, {});
890 }
891 else
892 {
893 // make sure to construct with other's allocator!
894 m_blocks =
895 std::vector<pointer, vec_alloc>(vec_alloc(other.get_allocator()));
896 append_everything_from(std::move(other));
897 }
898 return *this;
899 }
900
901 ~segmented_vector()
902 {
903 clear();
904 dealloc();
905 }
906
907 [[nodiscard]] constexpr auto
908 size() const -> size_t
909 {
910 return m_size;
911 }
912
913 [[nodiscard]] constexpr auto
914 capacity() const -> size_t
915 {
916 return m_blocks.size() * num_elements_in_block;
917 }
918
919 // Indexing is highly performance critical
920 [[nodiscard]] constexpr auto
921 operator[](size_t i) const noexcept -> T const &
922 {
923 return m_blocks[i >> num_bits][i & mask];
924 }
925
926 [[nodiscard]] constexpr auto
927 operator[](size_t i) noexcept -> T &
928 {
929 return m_blocks[i >> num_bits][i & mask];
930 }
931
932 [[nodiscard]] constexpr auto
933 begin() -> iterator
934 {
935 return {m_blocks.data(), 0U};
936 }
937 [[nodiscard]] constexpr auto
938 begin() const -> const_iterator
939 {
940 return {m_blocks.data(), 0U};
941 }
942 [[nodiscard]] constexpr auto
943 cbegin() const -> const_iterator
944 {
945 return {m_blocks.data(), 0U};
946 }
947
948 [[nodiscard]] constexpr auto
949 end() -> iterator
950 {
951 return {m_blocks.data(), m_size};
952 }
953 [[nodiscard]] constexpr auto
954 end() const -> const_iterator
955 {
956 return {m_blocks.data(), m_size};
957 }
958 [[nodiscard]] constexpr auto
959 cend() const -> const_iterator
960 {
961 return {m_blocks.data(), m_size};
962 }
963
964 [[nodiscard]] constexpr auto
965 back() -> reference
966 {
967 return operator[](m_size - 1);
968 }
969 [[nodiscard]] constexpr auto
970 back() const -> const_reference
971 {
972 return operator[](m_size - 1);
973 }
974
975 void
976 pop_back()
977 {
978 back().~T();
979 --m_size;
980 }
981
982 [[nodiscard]] auto
983 empty() const
984 {
985 return 0 == m_size;
986 }
987
988 void
989 reserve(size_t new_capacity)
990 {
991 m_blocks.reserve(calc_num_blocks_for_capacity(new_capacity));
992 while (new_capacity > capacity())
993 {
994 increase_capacity();
995 }
996 }
997
998 [[nodiscard]] auto
999 get_allocator() const -> allocator_type
1000 {
1001 return allocator_type{m_blocks.get_allocator()};
1002 }
1003
1004 template <class... Args>
1005 auto
1006 emplace_back(Args &&...args) -> reference
1007 {
1008 if (m_size == capacity())
1009 {
1010 increase_capacity();
1011 }
1012 auto *ptr = static_cast<void *>(&operator[](m_size));
1013 auto &ref = *new (ptr) T(std::forward<Args>(args)...);
1014 ++m_size;
1015 return ref;
1016 }
1017
1018 void
1019 clear()
1020 {
1021 if constexpr (!std::is_trivially_destructible_v<T>)
1022 {
1023 for (size_t i = 0, s = size(); i < s; ++i)
1024 {
1025 operator[](i).~T();
1026 }
1027 }
1028 m_size = 0;
1029 }
1030
1031 void
1032 shrink_to_fit()
1033 {
1034 auto ba = Allocator(m_blocks.get_allocator());
1035 auto num_blocks_required = calc_num_blocks_for_capacity(m_size);
1036 while (m_blocks.size() > num_blocks_required)
1037 {
1038 std::allocator_traits<Allocator>::deallocate(ba,
1039 m_blocks.back(),
1040 num_elements_in_block);
1041 m_blocks.pop_back();
1042 }
1043 m_blocks.shrink_to_fit();
1044 }
1045 };
1046
1047 namespace detail
1048 {
1049
1050 // This is it, the table. Doubles as map and set, and uses `void` for T
1051 // when its used as a set.
1052 template <class Key,
1053 class T, // when void, treat it as a set.
1054 class Hash,
1055 class KeyEqual,
1056 class AllocatorOrContainer,
1057 class Bucket,
1058 bool IsSegmented>
1059 class table : public std::conditional_t<is_map_v<T>,
1060 base_table_type_map<T>,
1061 base_table_type_set>
1062 {
1063 using underlying_value_type =
1064 typename std::conditional_t<is_map_v<T>, std::pair<Key, T>, Key>;
1065 using underlying_container_type = std::conditional_t<
1066 IsSegmented,
1067 segmented_vector<underlying_value_type, AllocatorOrContainer>,
1068 std::vector<underlying_value_type, AllocatorOrContainer>>;
1069
1070 public:
1071 using value_container_type = std::conditional_t<
1072 is_detected_v<detect_iterator, AllocatorOrContainer>,
1073 AllocatorOrContainer,
1074 underlying_container_type>;
1075
1076 private:
1077 using bucket_alloc = typename std::allocator_traits<
1078 typename value_container_type::allocator_type>::
1079 template rebind_alloc<Bucket>;
1080 using bucket_alloc_traits = std::allocator_traits<bucket_alloc>;
1081
1082 static constexpr uint8_t initial_shifts =
1083 64 - 2; // 2^(64-m_shift) number of buckets
1084 static constexpr float default_max_load_factor = 0.8F;
1085
1086 public:
1087 using key_type = Key;
1088 using value_type = typename value_container_type::value_type;
1089 using size_type = typename value_container_type::size_type;
1090 using difference_type = typename value_container_type::difference_type;
1091 using hasher = Hash;
1092 using key_equal = KeyEqual;
1093 using allocator_type = typename value_container_type::allocator_type;
1094 using reference = typename value_container_type::reference;
1095 using const_reference = typename value_container_type::const_reference;
1096 using pointer = typename value_container_type::pointer;
1097 using const_pointer = typename value_container_type::const_pointer;
1098 using const_iterator = typename value_container_type::const_iterator;
1099 using iterator =
1100 std::conditional_t<is_map_v<T>,
1101 typename value_container_type::iterator,
1102 const_iterator>;
1103 using bucket_type = Bucket;
1104
1105 private:
1106 using value_idx_type = decltype(Bucket::m_value_idx);
1107 using dist_and_fingerprint_type =
1108 decltype(Bucket::m_dist_and_fingerprint);
1109
1110 static_assert(
1111 std::is_trivially_destructible_v<Bucket>,
1112 "assert there's no need to call destructor / std::destroy");
1113 static_assert(std::is_trivially_copyable_v<Bucket>,
1114 "assert we can just memset / memcpy");
1115
1116 value_container_type
1117 m_values{}; // Contains all the key-value pairs in one densely stored
1118 // container. No holes.
1119 using bucket_pointer =
1120 typename std::allocator_traits<bucket_alloc>::pointer;
1121 bucket_pointer m_buckets{};
1122 size_t m_num_buckets = 0;
1123 size_t m_max_bucket_capacity = 0;
1124 float m_max_load_factor = default_max_load_factor;
1125 Hash m_hash{};
1126 KeyEqual m_equal{};
1127 uint8_t m_shifts = initial_shifts;
1128
1129 [[nodiscard]] auto
1130 next(value_idx_type bucket_idx) const -> value_idx_type
1131 {
1132 return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U ==
1133 m_num_buckets) ?
1134 0 :
1135 static_cast<value_idx_type>(bucket_idx + 1U);
1136 }
1137
1138 // Helper to access bucket through pointer types
1139 [[nodiscard]] static constexpr auto
1140 at(bucket_pointer bucket_ptr, size_t offset) -> Bucket &
1141 {
1142 return *(
1143 bucket_ptr +
1144 static_cast<
1145 typename std::allocator_traits<bucket_alloc>::difference_type>(
1146 offset));
1147 }
1148
1149 // use the dist_inc and dist_dec functions so that uint16_t types work
1150 // without warning
1151 [[nodiscard]] static constexpr auto
1152 dist_inc(dist_and_fingerprint_type x) -> dist_and_fingerprint_type
1153 {
1154 return static_cast<dist_and_fingerprint_type>(x + Bucket::dist_inc);
1155 }
1156
1157 [[nodiscard]] static constexpr auto
1158 dist_dec(dist_and_fingerprint_type x) -> dist_and_fingerprint_type
1159 {
1160 return static_cast<dist_and_fingerprint_type>(x - Bucket::dist_inc);
1161 }
1162
1163 // The goal of mixed_hash is to always produce a high quality 64bit
1164 // hash.
1165 template <typename K>
1166 [[nodiscard]] constexpr auto
1167 mixed_hash(K const &key) const -> uint64_t
1168 {
1169 if constexpr (is_detected_v<detect_avalanching, Hash>)
1170 {
1171 // we know that the hash is good because is_avalanching.
1172 if constexpr (sizeof(decltype(m_hash(key))) < sizeof(uint64_t))
1173 {
1174 // 32bit hash and is_avalanching => multiply with a constant
1175 // to avalanche bits upwards
1176 return m_hash(key) * UINT64_C(0x9ddfea08eb382d69);
1177 }
1178 else
1179 {
1180 // 64bit and is_avalanching => only use the hash itself.
1181 return m_hash(key);
1182 }
1183 }
1184 else
1185 {
1186 // not is_avalanching => apply wyhash
1187 return wyhash::hash(m_hash(key));
1188 }
1189 }
1190
1191 [[nodiscard]] constexpr auto
1192 dist_and_fingerprint_from_hash(uint64_t hash) const
1193 -> dist_and_fingerprint_type
1194 {
1195 return Bucket::dist_inc |
1196 (static_cast<dist_and_fingerprint_type>(hash) &
1197 Bucket::fingerprint_mask);
1198 }
1199
1200 [[nodiscard]] constexpr auto
1201 bucket_idx_from_hash(uint64_t hash) const -> value_idx_type
1202 {
1203 return static_cast<value_idx_type>(hash >> m_shifts);
1204 }
1205
1206 [[nodiscard]] static constexpr auto
1207 get_key(value_type const &vt) -> key_type const &
1208 {
1209 if constexpr (is_map_v<T>)
1210 {
1211 return vt.first;
1212 }
1213 else
1214 {
1215 return vt;
1216 }
1217 }
1218
1219 template <typename K>
1220 [[nodiscard]] auto
1221 next_while_less(K const &key) const -> Bucket
1222 {
1223 auto hash = mixed_hash(key);
1224 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1225 auto bucket_idx = bucket_idx_from_hash(hash);
1226
1227 while (dist_and_fingerprint <
1228 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
1229 {
1230 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1231 bucket_idx = next(bucket_idx);
1232 }
1233 return {dist_and_fingerprint, bucket_idx};
1234 }
1235
1236 void
1237 place_and_shift_up(Bucket bucket, value_idx_type place)
1238 {
1239 while (0 != at(m_buckets, place).m_dist_and_fingerprint)
1240 {
1241 bucket = std::exchange(at(m_buckets, place), bucket);
1242 bucket.m_dist_and_fingerprint =
1243 dist_inc(bucket.m_dist_and_fingerprint);
1244 place = next(place);
1245 }
1246 at(m_buckets, place) = bucket;
1247 }
1248
1249 [[nodiscard]] static constexpr auto
1250 calc_num_buckets(uint8_t shifts) -> size_t
1251 {
1252 return (std::min)(max_bucket_count(), size_t{1} << (64U - shifts));
1253 }
1254
1255 [[nodiscard]] constexpr auto
1256 calc_shifts_for_size(size_t s) const -> uint8_t
1257 {
1258 auto shifts = initial_shifts;
1259 while (shifts > 0 && static_cast<size_t>(
1260 static_cast<float>(calc_num_buckets(shifts)) *
1261 max_load_factor()) < s)
1262 {
1263 --shifts;
1264 }
1265 return shifts;
1266 }
1267
1268 // assumes m_values has data, m_buckets=m_buckets_end=nullptr, m_shifts
1269 // is INITIAL_SHIFTS
1270 void
1271 copy_buckets(table const &other)
1272 {
1273 // assumes m_values has already the correct data copied over.
1274 if (empty())
1275 {
1276 // when empty, at least allocate an initial buckets and clear
1277 // them.
1278 allocate_buckets_from_shift();
1279 clear_buckets();
1280 }
1281 else
1282 {
1283 m_shifts = other.m_shifts;
1284 allocate_buckets_from_shift();
1285 std::memcpy(m_buckets,
1286 other.m_buckets,
1287 sizeof(Bucket) * bucket_count());
1288 }
1289 }
1290
1291 /**
1292 * True when no element can be added any more without increasing the
1293 * size
1294 */
1295 [[nodiscard]] auto
1296 is_full() const -> bool
1297 {
1298 return size() > m_max_bucket_capacity;
1299 }
1300
1301 void
1302 deallocate_buckets()
1303 {
1304 auto ba = bucket_alloc(m_values.get_allocator());
1305 if (nullptr != m_buckets)
1306 {
1307 bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
1308 m_buckets = nullptr;
1309 }
1310 m_num_buckets = 0;
1311 m_max_bucket_capacity = 0;
1312 }
1313
1314 void
1315 allocate_buckets_from_shift()
1316 {
1317 auto ba = bucket_alloc(m_values.get_allocator());
1318 m_num_buckets = calc_num_buckets(m_shifts);
1319 m_buckets = bucket_alloc_traits::allocate(ba, m_num_buckets);
1320 if (m_num_buckets == max_bucket_count())
1321 {
1322 // reached the maximum, make sure we can use each bucket
1323 m_max_bucket_capacity = max_bucket_count();
1324 }
1325 else
1326 {
1327 m_max_bucket_capacity = static_cast<value_idx_type>(
1328 static_cast<float>(m_num_buckets) * max_load_factor());
1329 }
1330 }
1331
1332 void
1333 clear_buckets()
1334 {
1335 if (m_buckets != nullptr)
1336 {
1337 std::memset(&*m_buckets, 0, sizeof(Bucket) * bucket_count());
1338 }
1339 }
1340
1341 void
1342 clear_and_fill_buckets_from_values()
1343 {
1344 clear_buckets();
1345 for (value_idx_type
1346 value_idx = 0,
1347 end_idx = static_cast<value_idx_type>(m_values.size());
1348 value_idx < end_idx;
1349 ++value_idx)
1350 {
1351 auto const &key = get_key(m_values[value_idx]);
1352 auto [dist_and_fingerprint, bucket] = next_while_less(key);
1353
1354 // we know for certain that key has not yet been inserted, so no
1355 // need to check it.
1356 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket);
1357 }
1358 }
1359
1360 void
1361 increase_size()
1362 {
1363 if (m_max_bucket_capacity == max_bucket_count())
1364 {
1365 // remove the value again, we can't add it!
1366 m_values.pop_back();
1367 on_error_bucket_overflow();
1368 }
1369 --m_shifts;
1370 deallocate_buckets();
1371 allocate_buckets_from_shift();
1372 clear_and_fill_buckets_from_values();
1373 }
1374
1375 template <typename Op>
1376 void
1377 do_erase(value_idx_type bucket_idx, Op handle_erased_value)
1378 {
1379 auto const value_idx_to_remove =
1380 at(m_buckets, bucket_idx).m_value_idx;
1381
1382 // shift down until either empty or an element with correct spot is
1383 // found
1384 auto next_bucket_idx = next(bucket_idx);
1385 while (at(m_buckets, next_bucket_idx).m_dist_and_fingerprint >=
1386 Bucket::dist_inc * 2)
1387 {
1388 at(m_buckets, bucket_idx) = {
1389 dist_dec(at(m_buckets, next_bucket_idx).m_dist_and_fingerprint),
1390 at(m_buckets, next_bucket_idx).m_value_idx};
1391 bucket_idx =
1392 std::exchange(next_bucket_idx, next(next_bucket_idx));
1393 }
1394 at(m_buckets, bucket_idx) = {};
1395 handle_erased_value(std::move(m_values[value_idx_to_remove]));
1396
1397 // update m_values
1398 if (value_idx_to_remove != m_values.size() - 1)
1399 {
1400 // no luck, we'll have to replace the value with the last one and
1401 // update the index accordingly
1402 auto &val = m_values[value_idx_to_remove];
1403 val = std::move(m_values.back());
1404
1405 // update the values_idx of the moved entry. No need to play the
1406 // info game, just look until we find the values_idx
1407 auto mh = mixed_hash(get_key(val));
1408 bucket_idx = bucket_idx_from_hash(mh);
1409
1410 auto const values_idx_back =
1411 static_cast<value_idx_type>(m_values.size() - 1);
1412 while (values_idx_back != at(m_buckets, bucket_idx).m_value_idx)
1413 {
1414 bucket_idx = next(bucket_idx);
1415 }
1416 at(m_buckets, bucket_idx).m_value_idx = value_idx_to_remove;
1417 }
1418 m_values.pop_back();
1419 }
1420
1421 template <typename K, typename Op>
1422 auto
1423 do_erase_key(K &&key, Op handle_erased_value) -> size_t
1424 {
1425 if (empty())
1426 {
1427 return 0;
1428 }
1429
1430 auto [dist_and_fingerprint, bucket_idx] = next_while_less(key);
1431
1432 while (
1433 dist_and_fingerprint ==
1434 at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
1435 !m_equal(key,
1436 get_key(m_values[at(m_buckets, bucket_idx).m_value_idx])))
1437 {
1438 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1439 bucket_idx = next(bucket_idx);
1440 }
1441
1442 if (dist_and_fingerprint !=
1443 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
1444 {
1445 return 0;
1446 }
1447 do_erase(bucket_idx, handle_erased_value);
1448 return 1;
1449 }
1450
1451 template <class K, class M>
1452 auto
1453 do_insert_or_assign(K &&key, M &&mapped) -> std::pair<iterator, bool>
1454 {
1455 auto it_isinserted =
1456 try_emplace(std::forward<K>(key), std::forward<M>(mapped));
1457 if (!it_isinserted.second)
1458 {
1459 it_isinserted.first->second = std::forward<M>(mapped);
1460 }
1461 return it_isinserted;
1462 }
1463
1464 template <typename... Args>
1465 auto
1466 do_place_element(dist_and_fingerprint_type dist_and_fingerprint,
1467 value_idx_type bucket_idx,
1468 Args &&...args) -> std::pair<iterator, bool>
1469 {
1470 // emplace the new value. If that throws an exception, no harm done;
1471 // index is still in a valid state
1472 m_values.emplace_back(std::forward<Args>(args)...);
1473
1474 auto value_idx = static_cast<value_idx_type>(m_values.size() - 1);
1475 if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full()))
1476 {
1477 increase_size();
1478 }
1479 else
1480 {
1481 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
1482 }
1483
1484 // place element and shift up until we find an empty spot
1485 return {begin() + static_cast<difference_type>(value_idx), true};
1486 }
1487
1488 template <typename K, typename... Args>
1489 auto
1490 do_try_emplace(K &&key, Args &&...args) -> std::pair<iterator, bool>
1491 {
1492 auto hash = mixed_hash(key);
1493 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1494 auto bucket_idx = bucket_idx_from_hash(hash);
1495
1496 while (true)
1497 {
1498 auto *bucket = &at(m_buckets, bucket_idx);
1499 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint)
1500 {
1501 if (m_equal(key, get_key(m_values[bucket->m_value_idx])))
1502 {
1503 return {begin() + static_cast<difference_type>(
1504 bucket->m_value_idx),
1505 false};
1506 }
1507 }
1508 else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint)
1509 {
1510 return do_place_element(
1511 dist_and_fingerprint,
1512 bucket_idx,
1513 std::piecewise_construct,
1514 std::forward_as_tuple(std::forward<K>(key)),
1515 std::forward_as_tuple(std::forward<Args>(args)...));
1516 }
1517 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1518 bucket_idx = next(bucket_idx);
1519 }
1520 }
1521
1522 template <typename K>
1523 auto
1524 do_find(K const &key) -> iterator
1525 {
1526 if (ANKERL_UNORDERED_DENSE_UNLIKELY(empty()))
1527 {
1528 return end();
1529 }
1530
1531 auto mh = mixed_hash(key);
1532 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(mh);
1533 auto bucket_idx = bucket_idx_from_hash(mh);
1534 auto *bucket = &at(m_buckets, bucket_idx);
1535
1536 // unrolled loop. *Always* check a few directly, then enter the loop.
1537 // This is faster.
1538 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint &&
1539 m_equal(key, get_key(m_values[bucket->m_value_idx])))
1540 {
1541 return begin() +
1542 static_cast<difference_type>(bucket->m_value_idx);
1543 }
1544 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1545 bucket_idx = next(bucket_idx);
1546 bucket = &at(m_buckets, bucket_idx);
1547
1548 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint &&
1549 m_equal(key, get_key(m_values[bucket->m_value_idx])))
1550 {
1551 return begin() +
1552 static_cast<difference_type>(bucket->m_value_idx);
1553 }
1554 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1555 bucket_idx = next(bucket_idx);
1556 bucket = &at(m_buckets, bucket_idx);
1557
1558 while (true)
1559 {
1560 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint)
1561 {
1562 if (m_equal(key, get_key(m_values[bucket->m_value_idx])))
1563 {
1564 return begin() +
1565 static_cast<difference_type>(bucket->m_value_idx);
1566 }
1567 }
1568 else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint)
1569 {
1570 return end();
1571 }
1572 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1573 bucket_idx = next(bucket_idx);
1574 bucket = &at(m_buckets, bucket_idx);
1575 }
1576 }
1577
1578 template <typename K>
1579 auto
1580 do_find(K const &key) const -> const_iterator
1581 {
1582 return const_cast<table *>(this)->do_find(
1583 key); // NOLINT(cppcoreguidelines-pro-type-const-cast)
1584 }
1585
1586 template <typename K,
1587 typename Q = T,
1588 std::enable_if_t<is_map_v<Q>, bool> = true>
1589 auto
1590 do_at(K const &key) -> Q &
1591 {
1592 if (auto it = find(key); ANKERL_UNORDERED_DENSE_LIKELY(end() != it))
1593 {
1594 return it->second;
1595 }
1596 on_error_key_not_found();
1597 }
1598
1599 template <typename K,
1600 typename Q = T,
1601 std::enable_if_t<is_map_v<Q>, bool> = true>
1602 auto
1603 do_at(K const &key) const -> Q const &
1604 {
1605 return const_cast<table *>(this)->at(
1606 key); // NOLINT(cppcoreguidelines-pro-type-const-cast)
1607 }
1608
1609 public:
1610 explicit table(
1611 size_t bucket_count,
1612 Hash const &hash = Hash(),
1613 KeyEqual const &equal = KeyEqual(),
1614 allocator_type const &alloc_or_container = allocator_type())
1615 : m_values(alloc_or_container)
1616 , m_hash(hash)
1617 , m_equal(equal)
1618 {
1619 if (0 != bucket_count)
1620 {
1621 reserve(bucket_count);
1622 }
1623 else
1624 {
1625 allocate_buckets_from_shift();
1626 clear_buckets();
1627 }
1628 }
1629
1630 table()
1631 : table(0)
1632 {}
1633
1634 table(size_t bucket_count, allocator_type const &alloc)
1635 : table(bucket_count, Hash(), KeyEqual(), alloc)
1636 {}
1637
1638 table(size_t bucket_count,
1639 Hash const &hash,
1640 allocator_type const &alloc)
1641 : table(bucket_count, hash, KeyEqual(), alloc)
1642 {}
1643
1644 explicit table(allocator_type const &alloc)
1645 : table(0, Hash(), KeyEqual(), alloc)
1646 {}
1647
1648 template <class InputIt>
1649 table(InputIt first,
1650 InputIt last,
1651 size_type bucket_count = 0,
1652 Hash const &hash = Hash(),
1653 KeyEqual const &equal = KeyEqual(),
1654 allocator_type const &alloc = allocator_type())
1655 : table(bucket_count, hash, equal, alloc)
1656 {
1657 insert(first, last);
1658 }
1659
1660 template <class InputIt>
1661 table(InputIt first,
1662 InputIt last,
1663 size_type bucket_count,
1664 allocator_type const &alloc)
1665 : table(first, last, bucket_count, Hash(), KeyEqual(), alloc)
1666 {}
1667
1668 template <class InputIt>
1669 table(InputIt first,
1670 InputIt last,
1671 size_type bucket_count,
1672 Hash const &hash,
1673 allocator_type const &alloc)
1674 : table(first, last, bucket_count, hash, KeyEqual(), alloc)
1675 {}
1676
1677 table(table const &other)
1678 : table(other, other.m_values.get_allocator())
1679 {}
1680
1681 table(table const &other, allocator_type const &alloc)
1682 : m_values(other.m_values, alloc)
1683 , m_max_load_factor(other.m_max_load_factor)
1684 , m_hash(other.m_hash)
1685 , m_equal(other.m_equal)
1686 {
1687 copy_buckets(other);
1688 }
1689
1690 table(table &&other) noexcept
1691 : table(std::move(other), other.m_values.get_allocator())
1692 {}
1693
1694 table(table &&other, allocator_type const &alloc) noexcept
1695 : m_values(alloc)
1696 {
1697 *this = std::move(other);
1698 }
1699
1700 table(std::initializer_list<value_type> ilist,
1701 size_t bucket_count = 0,
1702 Hash const &hash = Hash(),
1703 KeyEqual const &equal = KeyEqual(),
1704 allocator_type const &alloc = allocator_type())
1705 : table(bucket_count, hash, equal, alloc)
1706 {
1707 insert(ilist);
1708 }
1709
1710 table(std::initializer_list<value_type> ilist,
1711 size_type bucket_count,
1712 allocator_type const &alloc)
1713 : table(ilist, bucket_count, Hash(), KeyEqual(), alloc)
1714 {}
1715
1716 table(std::initializer_list<value_type> init,
1717 size_type bucket_count,
1718 Hash const &hash,
1719 allocator_type const &alloc)
1720 : table(init, bucket_count, hash, KeyEqual(), alloc)
1721 {}
1722
1723 ~table()
1724 {
1725 if (nullptr != m_buckets)
1726 {
1727 auto ba = bucket_alloc(m_values.get_allocator());
1728 bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
1729 }
1730 }
1731
1732 auto
1733 operator=(table const &other) -> table &
1734 {
1735 if (&other != this)
1736 {
1737 deallocate_buckets(); // deallocate before m_values is set (might
1738 // have another allocator)
1739 m_values = other.m_values;
1740 m_max_load_factor = other.m_max_load_factor;
1741 m_hash = other.m_hash;
1742 m_equal = other.m_equal;
1743 m_shifts = initial_shifts;
1744 copy_buckets(other);
1745 }
1746 return *this;
1747 }
1748
1749 auto
1750 operator=(table &&other) noexcept(noexcept(
1751 std::is_nothrow_move_assignable_v<value_container_type>
1752 &&std::is_nothrow_move_assignable_v<Hash>
1753 &&std::is_nothrow_move_assignable_v<KeyEqual>)) -> table &
1754 {
1755 if (&other != this)
1756 {
1757 deallocate_buckets(); // deallocate before m_values is set (might
1758 // have another allocator)
1759 m_values = std::move(other.m_values);
1760 other.m_values.clear();
1761
1762 // we can only reuse m_buckets when both maps have the same
1763 // allocator!
1764 if (get_allocator() == other.get_allocator())
1765 {
1766 m_buckets = std::exchange(other.m_buckets, nullptr);
1767 m_num_buckets = std::exchange(other.m_num_buckets, 0);
1768 m_max_bucket_capacity =
1769 std::exchange(other.m_max_bucket_capacity, 0);
1770 m_shifts = std::exchange(other.m_shifts, initial_shifts);
1771 m_max_load_factor = std::exchange(other.m_max_load_factor,
1772 default_max_load_factor);
1773 m_hash = std::exchange(other.m_hash, {});
1774 m_equal = std::exchange(other.m_equal, {});
1775 other.allocate_buckets_from_shift();
1776 other.clear_buckets();
1777 }
1778 else
1779 {
1780 // set max_load_factor *before* copying the other's buckets,
1781 // so we have the same behavior
1782 m_max_load_factor = other.m_max_load_factor;
1783
1784 // copy_buckets sets m_buckets, m_num_buckets,
1785 // m_max_bucket_capacity, m_shifts
1786 copy_buckets(other);
1787 // clear's the other's buckets so other is now already usable.
1788 other.clear_buckets();
1789 m_hash = other.m_hash;
1790 m_equal = other.m_equal;
1791 }
1792 // map "other" is now already usable, it's empty.
1793 }
1794 return *this;
1795 }
1796
1797 auto
1798 operator=(std::initializer_list<value_type> ilist) -> table &
1799 {
1800 clear();
1801 insert(ilist);
1802 return *this;
1803 }
1804
1805 auto
1806 get_allocator() const noexcept -> allocator_type
1807 {
1808 return m_values.get_allocator();
1809 }
1810
1811 // iterators
1812 // //////////////////////////////////////////////////////////////
1813
1814 auto
1815 begin() noexcept -> iterator
1816 {
1817 return m_values.begin();
1818 }
1819
1820 auto
1821 begin() const noexcept -> const_iterator
1822 {
1823 return m_values.begin();
1824 }
1825
1826 auto
1827 cbegin() const noexcept -> const_iterator
1828 {
1829 return m_values.cbegin();
1830 }
1831
1832 auto
1833 end() noexcept -> iterator
1834 {
1835 return m_values.end();
1836 }
1837
1838 auto
1839 cend() const noexcept -> const_iterator
1840 {
1841 return m_values.cend();
1842 }
1843
1844 auto
1845 end() const noexcept -> const_iterator
1846 {
1847 return m_values.end();
1848 }
1849
1850 // capacity
1851 // ///////////////////////////////////////////////////////////////
1852
1853 [[nodiscard]] auto
1854 empty() const noexcept -> bool
1855 {
1856 return m_values.empty();
1857 }
1858
1859 [[nodiscard]] auto
1860 size() const noexcept -> size_t
1861 {
1862 return m_values.size();
1863 }
1864
1865 [[nodiscard]] static constexpr auto
1866 max_size() noexcept -> size_t
1867 {
1868 if constexpr ((std::numeric_limits<value_idx_type>::max)() ==
1869 (std::numeric_limits<size_t>::max)())
1870 {
1871 return size_t{1} << (sizeof(value_idx_type) * 8 - 1);
1872 }
1873 else
1874 {
1875 return size_t{1} << (sizeof(value_idx_type) * 8);
1876 }
1877 }
1878
1879 // modifiers
1880 // //////////////////////////////////////////////////////////////
1881
1882 void
1883 clear()
1884 {
1885 m_values.clear();
1886 clear_buckets();
1887 }
1888
1889 auto
1890 insert(value_type const &value) -> std::pair<iterator, bool>
1891 {
1892 return emplace(value);
1893 }
1894
1895 auto
1896 insert(value_type &&value) -> std::pair<iterator, bool>
1897 {
1898 return emplace(std::move(value));
1899 }
1900
1901 template <class P,
1902 std::enable_if_t<std::is_constructible_v<value_type, P &&>,
1903 bool> = true>
1904 auto
1905 insert(P &&value) -> std::pair<iterator, bool>
1906 {
1907 return emplace(std::forward<P>(value));
1908 }
1909
1910 auto
1911 insert(const_iterator /*hint*/, value_type const &value) -> iterator
1912 {
1913 return insert(value).first;
1914 }
1915
1916 auto
1917 insert(const_iterator /*hint*/, value_type &&value) -> iterator
1918 {
1919 return insert(std::move(value)).first;
1920 }
1921
1922 template <class P,
1923 std::enable_if_t<std::is_constructible_v<value_type, P &&>,
1924 bool> = true>
1925 auto
1926 insert(const_iterator /*hint*/, P &&value) -> iterator
1927 {
1928 return insert(std::forward<P>(value)).first;
1929 }
1930
1931 template <class InputIt>
1932 void
1933 insert(InputIt first, InputIt last)
1934 {
1935 while (first != last)
1936 {
1937 insert(*first);
1938 ++first;
1939 }
1940 }
1941
1942 void
1943 insert(std::initializer_list<value_type> ilist)
1944 {
1945 insert(ilist.begin(), ilist.end());
1946 }
1947
1948 // nonstandard API: *this is emptied.
1949 // Also see "A Standard flat_map"
1950 // https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0429r9.pdf
1951 auto
1952 extract() && -> value_container_type
1953 {
1954 return std::move(m_values);
1955 }
1956
1957 // nonstandard API:
1958 // Discards the internally held container and replaces it with the one
1959 // passed. Erases non-unique elements.
1960 auto
1961 replace(value_container_type &&container)
1962 {
1963 if (ANKERL_UNORDERED_DENSE_UNLIKELY(container.size() > max_size()))
1964 {
1965 on_error_too_many_elements();
1966 }
1967 auto shifts = calc_shifts_for_size(container.size());
1968 if (0 == m_num_buckets || shifts < m_shifts ||
1969 container.get_allocator() != m_values.get_allocator())
1970 {
1971 m_shifts = shifts;
1972 deallocate_buckets();
1973 allocate_buckets_from_shift();
1974 }
1975 clear_buckets();
1976
1977 m_values = std::move(container);
1978
1979 // can't use clear_and_fill_buckets_from_values() because container
1980 // elements might not be unique
1981 auto value_idx = value_idx_type{};
1982
1983 // loop until we reach the end of the container. duplicated entries
1984 // will be replaced with back().
1985 while (value_idx != static_cast<value_idx_type>(m_values.size()))
1986 {
1987 auto const &key = get_key(m_values[value_idx]);
1988
1989 auto hash = mixed_hash(key);
1990 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1991 auto bucket_idx = bucket_idx_from_hash(hash);
1992
1993 bool key_found = false;
1994 while (true)
1995 {
1996 auto const &bucket = at(m_buckets, bucket_idx);
1997 if (dist_and_fingerprint > bucket.m_dist_and_fingerprint)
1998 {
1999 break;
2000 }
2001 if (dist_and_fingerprint == bucket.m_dist_and_fingerprint &&
2002 m_equal(key, get_key(m_values[bucket.m_value_idx])))
2003 {
2004 key_found = true;
2005 break;
2006 }
2007 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
2008 bucket_idx = next(bucket_idx);
2009 }
2010
2011 if (key_found)
2012 {
2013 if (value_idx !=
2014 static_cast<value_idx_type>(m_values.size() - 1))
2015 {
2016 m_values[value_idx] = std::move(m_values.back());
2017 }
2018 m_values.pop_back();
2019 }
2020 else
2021 {
2022 place_and_shift_up({dist_and_fingerprint, value_idx},
2023 bucket_idx);
2024 ++value_idx;
2025 }
2026 }
2027 }
2028
2029 template <class M,
2030 typename Q = T,
2031 std::enable_if_t<is_map_v<Q>, bool> = true>
2032 auto
2033 insert_or_assign(Key const &key, M &&mapped)
2034 -> std::pair<iterator, bool>
2035 {
2036 return do_insert_or_assign(key, std::forward<M>(mapped));
2037 }
2038
2039 template <class M,
2040 typename Q = T,
2041 std::enable_if_t<is_map_v<Q>, bool> = true>
2042 auto
2043 insert_or_assign(Key &&key, M &&mapped) -> std::pair<iterator, bool>
2044 {
2045 return do_insert_or_assign(std::move(key), std::forward<M>(mapped));
2046 }
2047
2048 template <
2049 typename K,
2050 typename M,
2051 typename Q = T,
2052 typename H = Hash,
2053 typename KE = KeyEqual,
2054 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
2055 auto
2056 insert_or_assign(K &&key, M &&mapped) -> std::pair<iterator, bool>
2057 {
2058 return do_insert_or_assign(std::forward<K>(key),
2059 std::forward<M>(mapped));
2060 }
2061
2062 template <class M,
2063 typename Q = T,
2064 std::enable_if_t<is_map_v<Q>, bool> = true>
2065 auto
2066 insert_or_assign(const_iterator /*hint*/, Key const &key, M &&mapped)
2067 -> iterator
2068 {
2069 return do_insert_or_assign(key, std::forward<M>(mapped)).first;
2070 }
2071
2072 template <class M,
2073 typename Q = T,
2074 std::enable_if_t<is_map_v<Q>, bool> = true>
2075 auto
2076 insert_or_assign(const_iterator /*hint*/, Key &&key, M &&mapped)
2077 -> iterator
2078 {
2079 return do_insert_or_assign(std::move(key), std::forward<M>(mapped))
2080 .first;
2081 }
2082
2083 template <
2084 typename K,
2085 typename M,
2086 typename Q = T,
2087 typename H = Hash,
2088 typename KE = KeyEqual,
2089 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
2090 auto
2091 insert_or_assign(const_iterator /*hint*/, K &&key, M &&mapped)
2092 -> iterator
2093 {
2094 return do_insert_or_assign(std::forward<K>(key),
2095 std::forward<M>(mapped))
2096 .first;
2097 }
2098
2099 // Single arguments for unordered_set can be used without having to
2100 // construct the value_type
2101 template <class K,
2102 typename Q = T,
2103 typename H = Hash,
2104 typename KE = KeyEqual,
2105 std::enable_if_t<!is_map_v<Q> && is_transparent_v<H, KE>,
2106 bool> = true>
2107 auto
2108 emplace(K &&key) -> std::pair<iterator, bool>
2109 {
2110 auto hash = mixed_hash(key);
2111 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
2112 auto bucket_idx = bucket_idx_from_hash(hash);
2113
2114 while (dist_and_fingerprint <=
2115 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
2116 {
2117 if (dist_and_fingerprint ==
2118 at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
2119 m_equal(key, m_values[at(m_buckets, bucket_idx).m_value_idx]))
2120 {
2121 // found it, return without ever actually creating anything
2122 return {begin() + static_cast<difference_type>(
2123 at(m_buckets, bucket_idx).m_value_idx),
2124 false};
2125 }
2126 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
2127 bucket_idx = next(bucket_idx);
2128 }
2129
2130 // value is new, insert element first, so when exception happens we
2131 // are in a valid state
2132 return do_place_element(dist_and_fingerprint,
2133 bucket_idx,
2134 std::forward<K>(key));
2135 }
2136
2137 template <class... Args>
2138 auto
2139 emplace(Args &&...args) -> std::pair<iterator, bool>
2140 {
2141 // we have to instantiate the value_type to be able to access the key.
2142 // 1. emplace_back the object so it is constructed. 2. If the key is
2143 // already there, pop it later in the loop.
2144 auto &key =
2145 get_key(m_values.emplace_back(std::forward<Args>(args)...));
2146 auto hash = mixed_hash(key);
2147 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
2148 auto bucket_idx = bucket_idx_from_hash(hash);
2149
2150 while (dist_and_fingerprint <=
2151 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
2152 {
2153 if (dist_and_fingerprint ==
2154 at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
2155 m_equal(key,
2156 get_key(
2157 m_values[at(m_buckets, bucket_idx).m_value_idx])))
2158 {
2159 m_values
2160 .pop_back(); // value was already there, so get rid of it
2161 return {begin() + static_cast<difference_type>(
2162 at(m_buckets, bucket_idx).m_value_idx),
2163 false};
2164 }
2165 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
2166 bucket_idx = next(bucket_idx);
2167 }
2168
2169 // value is new, place the bucket and shift up until we find an empty
2170 // spot
2171 auto value_idx = static_cast<value_idx_type>(m_values.size() - 1);
2172 if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full()))
2173 {
2174 // increase_size just rehashes all the data we have in m_values
2175 increase_size();
2176 }
2177 else
2178 {
2179 // place element and shift up until we find an empty spot
2180 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
2181 }
2182 return {begin() + static_cast<difference_type>(value_idx), true};
2183 }
2184
2185 template <class... Args>
2186 auto
2187 emplace_hint(const_iterator /*hint*/, Args &&...args) -> iterator
2188 {
2189 return emplace(std::forward<Args>(args)...).first;
2190 }
2191
2192 template <class... Args,
2193 typename Q = T,
2194 std::enable_if_t<is_map_v<Q>, bool> = true>
2195 auto
2196 try_emplace(Key const &key, Args &&...args) -> std::pair<iterator, bool>
2197 {
2198 return do_try_emplace(key, std::forward<Args>(args)...);
2199 }
2200
2201 template <class... Args,
2202 typename Q = T,
2203 std::enable_if_t<is_map_v<Q>, bool> = true>
2204 auto
2205 try_emplace(Key &&key, Args &&...args) -> std::pair<iterator, bool>
2206 {
2207 return do_try_emplace(std::move(key), std::forward<Args>(args)...);
2208 }
2209
2210 template <class... Args,
2211 typename Q = T,
2212 std::enable_if_t<is_map_v<Q>, bool> = true>
2213 auto
2214 try_emplace(const_iterator /*hint*/, Key const &key, Args &&...args)
2215 -> iterator
2216 {
2217 return do_try_emplace(key, std::forward<Args>(args)...).first;
2218 }
2219
2220 template <class... Args,
2221 typename Q = T,
2222 std::enable_if_t<is_map_v<Q>, bool> = true>
2223 auto
2224 try_emplace(const_iterator /*hint*/, Key &&key, Args &&...args)
2225 -> iterator
2226 {
2227 return do_try_emplace(std::move(key), std::forward<Args>(args)...)
2228 .first;
2229 }
2230
2231 template <typename K,
2232 typename... Args,
2233 typename Q = T,
2234 typename H = Hash,
2235 typename KE = KeyEqual,
2236 std::enable_if_t<
2237 is_map_v<Q> && is_transparent_v<H, KE> &&
2238 is_neither_convertible_v<K &&, iterator, const_iterator>,
2239 bool> = true>
2240 auto
2241 try_emplace(K &&key, Args &&...args) -> std::pair<iterator, bool>
2242 {
2243 return do_try_emplace(std::forward<K>(key),
2244 std::forward<Args>(args)...);
2245 }
2246
2247 template <typename K,
2248 typename... Args,
2249 typename Q = T,
2250 typename H = Hash,
2251 typename KE = KeyEqual,
2252 std::enable_if_t<
2253 is_map_v<Q> && is_transparent_v<H, KE> &&
2254 is_neither_convertible_v<K &&, iterator, const_iterator>,
2255 bool> = true>
2256 auto
2257 try_emplace(const_iterator /*hint*/, K &&key, Args &&...args)
2258 -> iterator
2259 {
2260 return do_try_emplace(std::forward<K>(key),
2261 std::forward<Args>(args)...)
2262 .first;
2263 }
2264
2265 auto
2266 erase(iterator it) -> iterator
2267 {
2268 auto hash = mixed_hash(get_key(*it));
2269 auto bucket_idx = bucket_idx_from_hash(hash);
2270
2271 auto const value_idx_to_remove =
2272 static_cast<value_idx_type>(it - cbegin());
2273 while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove)
2274 {
2275 bucket_idx = next(bucket_idx);
2276 }
2277
2278 do_erase(bucket_idx, [](value_type && /*unused*/) {});
2279 return begin() + static_cast<difference_type>(value_idx_to_remove);
2280 }
2281
2282 auto
2283 extract(iterator it) -> value_type
2284 {
2285 auto hash = mixed_hash(get_key(*it));
2286 auto bucket_idx = bucket_idx_from_hash(hash);
2287
2288 auto const value_idx_to_remove =
2289 static_cast<value_idx_type>(it - cbegin());
2290 while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove)
2291 {
2292 bucket_idx = next(bucket_idx);
2293 }
2294
2295 auto tmp = std::optional<value_type>{};
2296 do_erase(bucket_idx,
2297 [&tmp](value_type &&val) { tmp = std::move(val); });
2298 return std::move(tmp).value();
2299 }
2300
2301 template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
2302 auto
2303 erase(const_iterator it) -> iterator
2304 {
2305 return erase(begin() + (it - cbegin()));
2306 }
2307
2308 template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
2309 auto
2310 extract(const_iterator it) -> value_type
2311 {
2312 return extract(begin() + (it - cbegin()));
2313 }
2314
2315 auto
2316 erase(const_iterator first, const_iterator last) -> iterator
2317 {
2318 auto const idx_first = first - cbegin();
2319 auto const idx_last = last - cbegin();
2320 auto const first_to_last = std::distance(first, last);
2321 auto const last_to_end = std::distance(last, cend());
2322
2323 // remove elements from left to right which moves elements from the
2324 // end back
2325 auto const mid = idx_first + (std::min)(first_to_last, last_to_end);
2326 auto idx = idx_first;
2327 while (idx != mid)
2328 {
2329 erase(begin() + idx);
2330 ++idx;
2331 }
2332
2333 // all elements from the right are moved, now remove the last element
2334 // until all done
2335 idx = idx_last;
2336 while (idx != mid)
2337 {
2338 --idx;
2339 erase(begin() + idx);
2340 }
2341
2342 return begin() + idx_first;
2343 }
2344
2345 auto
2346 erase(Key const &key) -> size_t
2347 {
2348 return do_erase_key(key, [](value_type && /*unused*/) {});
2349 }
2350
2351 auto
2352 extract(Key const &key) -> std::optional<value_type>
2353 {
2354 auto tmp = std::optional<value_type>{};
2355 do_erase_key(key, [&tmp](value_type &&val) { tmp = std::move(val); });
2356 return tmp;
2357 }
2358
2359 template <class K,
2360 class H = Hash,
2361 class KE = KeyEqual,
2362 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2363 auto
2364 erase(K &&key) -> size_t
2365 {
2366 return do_erase_key(std::forward<K>(key),
2367 [](value_type && /*unused*/) {});
2368 }
2369
2370 template <class K,
2371 class H = Hash,
2372 class KE = KeyEqual,
2373 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2374 auto
2375 extract(K &&key) -> std::optional<value_type>
2376 {
2377 auto tmp = std::optional<value_type>{};
2378 do_erase_key(std::forward<K>(key),
2379 [&tmp](value_type &&val) { tmp = std::move(val); });
2380 return tmp;
2381 }
2382
2383 void
2384 swap(table &other) noexcept(
2385 noexcept(std::is_nothrow_swappable_v<value_container_type>
2386 &&std::is_nothrow_swappable_v<Hash>
2387 &&std::is_nothrow_swappable_v<KeyEqual>))
2388 {
2389 using std::swap;
2390 swap(other, *this);
2391 }
2392
2393 // lookup
2394 // /////////////////////////////////////////////////////////////////
2395
2396 template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
2397 auto
2398 at(key_type const &key) -> Q &
2399 {
2400 return do_at(key);
2401 }
2402
2403 template <
2404 typename K,
2405 typename Q = T,
2406 typename H = Hash,
2407 typename KE = KeyEqual,
2408 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
2409 auto
2410 at(K const &key) -> Q &
2411 {
2412 return do_at(key);
2413 }
2414
2415 template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
2416 auto
2417 at(key_type const &key) const -> Q const &
2418 {
2419 return do_at(key);
2420 }
2421
2422 template <
2423 typename K,
2424 typename Q = T,
2425 typename H = Hash,
2426 typename KE = KeyEqual,
2427 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
2428 auto
2429 at(K const &key) const -> Q const &
2430 {
2431 return do_at(key);
2432 }
2433
2434 template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
2435 auto
2436 operator[](Key const &key) -> Q &
2437 {
2438 return try_emplace(key).first->second;
2439 }
2440
2441 template <typename Q = T, std::enable_if_t<is_map_v<Q>, bool> = true>
2442 auto
2443 operator[](Key &&key) -> Q &
2444 {
2445 return try_emplace(std::move(key)).first->second;
2446 }
2447
2448 template <
2449 typename K,
2450 typename Q = T,
2451 typename H = Hash,
2452 typename KE = KeyEqual,
2453 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>, bool> = true>
2454 auto
2455 operator[](K &&key) -> Q &
2456 {
2457 return try_emplace(std::forward<K>(key)).first->second;
2458 }
2459
2460 auto
2461 count(Key const &key) const -> size_t
2462 {
2463 return find(key) == end() ? 0 : 1;
2464 }
2465
2466 template <class K,
2467 class H = Hash,
2468 class KE = KeyEqual,
2469 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2470 auto
2471 count(K const &key) const -> size_t
2472 {
2473 return find(key) == end() ? 0 : 1;
2474 }
2475
2476 auto
2477 find(Key const &key) -> iterator
2478 {
2479 return do_find(key);
2480 }
2481
2482 auto
2483 find(Key const &key) const -> const_iterator
2484 {
2485 return do_find(key);
2486 }
2487
2488 template <class K,
2489 class H = Hash,
2490 class KE = KeyEqual,
2491 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2492 auto
2493 find(K const &key) -> iterator
2494 {
2495 return do_find(key);
2496 }
2497
2498 template <class K,
2499 class H = Hash,
2500 class KE = KeyEqual,
2501 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2502 auto
2503 find(K const &key) const -> const_iterator
2504 {
2505 return do_find(key);
2506 }
2507
2508 auto
2509 contains(Key const &key) const -> bool
2510 {
2511 return find(key) != end();
2512 }
2513
2514 template <class K,
2515 class H = Hash,
2516 class KE = KeyEqual,
2517 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2518 auto
2519 contains(K const &key) const -> bool
2520 {
2521 return find(key) != end();
2522 }
2523
2524 auto
2525 equal_range(Key const &key) -> std::pair<iterator, iterator>
2526 {
2527 auto it = do_find(key);
2528 return {it, it == end() ? end() : it + 1};
2529 }
2530
2531 auto
2532 equal_range(const Key &key) const
2533 -> std::pair<const_iterator, const_iterator>
2534 {
2535 auto it = do_find(key);
2536 return {it, it == end() ? end() : it + 1};
2537 }
2538
2539 template <class K,
2540 class H = Hash,
2541 class KE = KeyEqual,
2542 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2543 auto
2544 equal_range(K const &key) -> std::pair<iterator, iterator>
2545 {
2546 auto it = do_find(key);
2547 return {it, it == end() ? end() : it + 1};
2548 }
2549
2550 template <class K,
2551 class H = Hash,
2552 class KE = KeyEqual,
2553 std::enable_if_t<is_transparent_v<H, KE>, bool> = true>
2554 auto
2555 equal_range(K const &key) const
2556 -> std::pair<const_iterator, const_iterator>
2557 {
2558 auto it = do_find(key);
2559 return {it, it == end() ? end() : it + 1};
2560 }
2561
2562 // bucket interface
2563 // ///////////////////////////////////////////////////////
2564
2565 auto
2566 bucket_count() const noexcept -> size_t
2567 { // NOLINT(modernize-use-nodiscard)
2568 return m_num_buckets;
2569 }
2570
2571 static constexpr auto
2572 max_bucket_count() noexcept -> size_t
2573 { // NOLINT(modernize-use-nodiscard)
2574 return max_size();
2575 }
2576
2577 // hash policy
2578 // ////////////////////////////////////////////////////////////
2579
2580 [[nodiscard]] auto
2581 load_factor() const -> float
2582 {
2583 return bucket_count() ? static_cast<float>(size()) /
2584 static_cast<float>(bucket_count()) :
2585 0.0F;
2586 }
2587
2588 [[nodiscard]] auto
2589 max_load_factor() const -> float
2590 {
2591 return m_max_load_factor;
2592 }
2593
2594 void
2595 max_load_factor(float ml)
2596 {
2597 m_max_load_factor = ml;
2598 if (m_num_buckets != max_bucket_count())
2599 {
2600 m_max_bucket_capacity = static_cast<value_idx_type>(
2601 static_cast<float>(bucket_count()) * max_load_factor());
2602 }
2603 }
2604
2605 void
2606 rehash(size_t count)
2607 {
2608 count = (std::min)(count, max_size());
2609 auto shifts = calc_shifts_for_size((std::max)(count, size()));
2610 if (shifts != m_shifts)
2611 {
2612 m_shifts = shifts;
2613 deallocate_buckets();
2614 m_values.shrink_to_fit();
2615 allocate_buckets_from_shift();
2616 clear_and_fill_buckets_from_values();
2617 }
2618 }
2619
2620 void
2621 reserve(size_t capa)
2622 {
2623 capa = (std::min)(capa, max_size());
2624 if constexpr (has_reserve<value_container_type>)
2625 {
2626 // std::deque doesn't have reserve(). Make sure we only call when
2627 // available
2628 m_values.reserve(capa);
2629 }
2630 auto shifts = calc_shifts_for_size((std::max)(capa, size()));
2631 if (0 == m_num_buckets || shifts < m_shifts)
2632 {
2633 m_shifts = shifts;
2634 deallocate_buckets();
2635 allocate_buckets_from_shift();
2636 clear_and_fill_buckets_from_values();
2637 }
2638 }
2639
2640 // observers
2641 // //////////////////////////////////////////////////////////////
2642
2643 auto
2644 hash_function() const -> hasher
2645 {
2646 return m_hash;
2647 }
2648
2649 auto
2650 key_eq() const -> key_equal
2651 {
2652 return m_equal;
2653 }
2654
2655 // nonstandard API: expose the underlying values container
2656 [[nodiscard]] auto
2657 values() const noexcept -> value_container_type const &
2658 {
2659 return m_values;
2660 }
2661
2662 // non-member functions
2663 // ///////////////////////////////////////////////////
2664
2665 friend auto
2666 operator==(table const &a, table const &b) -> bool
2667 {
2668 if (&a == &b)
2669 {
2670 return true;
2671 }
2672 if (a.size() != b.size())
2673 {
2674 return false;
2675 }
2676 for (auto const &b_entry : b)
2677 {
2678 auto it = a.find(get_key(b_entry));
2679 if constexpr (is_map_v<T>)
2680 {
2681 // map: check that key is here, then also check that value is
2682 // the same
2683 if (a.end() == it || !(b_entry.second == it->second))
2684 {
2685 return false;
2686 }
2687 }
2688 else
2689 {
2690 // set: only check that the key is here
2691 if (a.end() == it)
2692 {
2693 return false;
2694 }
2695 }
2696 }
2697 return true;
2698 }
2699
2700 friend auto
2701 operator!=(table const &a, table const &b) -> bool
2702 {
2703 return !(a == b);
2704 }
2705 };
2706
2707 } // namespace detail
2708
2710 class Key,
2711 class T,
2712 class Hash = hash<Key>,
2713 class KeyEqual = std::equal_to<Key>,
2714 class AllocatorOrContainer = std::allocator<std::pair<Key, T>>,
2715 class Bucket = bucket_type::standard>
2716 using map = detail::
2717 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, false>;
2718
2720 class Key,
2721 class T,
2722 class Hash = hash<Key>,
2723 class KeyEqual = std::equal_to<Key>,
2724 class AllocatorOrContainer = std::allocator<std::pair<Key, T>>,
2725 class Bucket = bucket_type::standard>
2726 using segmented_map =
2727 detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, true>;
2728
2730 class Key,
2731 class Hash = hash<Key>,
2732 class KeyEqual = std::equal_to<Key>,
2733 class AllocatorOrContainer = std::allocator<Key>,
2734 class Bucket = bucket_type::standard>
2735 using set = detail::
2736 table<Key, void, Hash, KeyEqual, AllocatorOrContainer, Bucket, false>;
2737
2739 class Key,
2740 class Hash = hash<Key>,
2741 class KeyEqual = std::equal_to<Key>,
2742 class AllocatorOrContainer = std::allocator<Key>,
2743 class Bucket = bucket_type::standard>
2744 using segmented_set = detail::
2745 table<Key, void, Hash, KeyEqual, AllocatorOrContainer, Bucket, true>;
2746
2747# if defined(ANKERL_UNORDERED_DENSE_PMR)
2748
2749 namespace pmr
2750 {
2751
2753 class Key,
2754 class T,
2755 class Hash = hash<Key>,
2756 class KeyEqual = std::equal_to<Key>,
2757 class Bucket = bucket_type::standard>
2758 using map = detail::table<
2759 Key,
2760 T,
2761 Hash,
2762 KeyEqual,
2763 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<std::pair<Key, T>>,
2764 Bucket,
2765 false>;
2766
2768 class Key,
2769 class T,
2770 class Hash = hash<Key>,
2771 class KeyEqual = std::equal_to<Key>,
2772 class Bucket = bucket_type::standard>
2773 using segmented_map = detail::table<
2774 Key,
2775 T,
2776 Hash,
2777 KeyEqual,
2778 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<std::pair<Key, T>>,
2779 Bucket,
2780 true>;
2781
2783 class Key,
2784 class Hash = hash<Key>,
2785 class KeyEqual = std::equal_to<Key>,
2786 class Bucket = bucket_type::standard>
2787 using set =
2788 detail::table<Key,
2789 void,
2790 Hash,
2791 KeyEqual,
2792 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<Key>,
2793 Bucket,
2794 false>;
2795
2797 class Key,
2798 class Hash = hash<Key>,
2799 class KeyEqual = std::equal_to<Key>,
2800 class Bucket = bucket_type::standard>
2801 using segmented_set =
2802 detail::table<Key,
2803 void,
2804 Hash,
2805 KeyEqual,
2806 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<Key>,
2807 Bucket,
2808 true>;
2809
2810 } // namespace pmr
2811
2812# endif
2813
2814 // deduction guides
2815 // ///////////////////////////////////////////////////////////
2816
2817 // deduction guides for alias templates are only possible since C++20
2818 // see
2819 // https://en.cppreference.com/w/cpp/language/class_template_argument_deduction
2820
2821 } // namespace ANKERL_UNORDERED_DENSE_NAMESPACE
2822} // namespace ankerl::unordered_dense
2823
2824// std extensions /////////////////////////////////////////////////////////////
2825
2826namespace std
2827{ // NOLINT(cert-dcl58-cpp)
2828
2829 ANKERL_UNORDERED_DENSE_EXPORT template <class Key,
2830 class T,
2831 class Hash,
2832 class KeyEqual,
2833 class AllocatorOrContainer,
2834 class Bucket,
2835 class Pred,
2836 bool IsSegmented>
2837 // NOLINTNEXTLINE(cert-dcl58-cpp)
2838 auto
2839 erase_if(
2840 ankerl::unordered_dense::detail::
2841 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, IsSegmented>
2842 &map,
2843 Pred pred) -> size_t
2844 {
2845 using map_t = ankerl::unordered_dense::detail::
2846 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, IsSegmented>;
2847
2848 // going back to front because erase() invalidates the end iterator
2849 auto const old_size = map.size();
2850 auto idx = old_size;
2851 while (idx)
2852 {
2853 --idx;
2854 auto it =
2855 map.begin() + static_cast<typename map_t::difference_type>(idx);
2856 if (pred(*it))
2857 {
2858 map.erase(it);
2859 }
2860 }
2861
2862 return old_size - map.size();
2863 }
2864
2865} // namespace std
2866
2867#endif
2868#endif
@ standard
Standard Navier-Stokes equations.
@ T
Particle temperature.
#define ANKERL_UNORDERED_DENSE_NAMESPACE
#define ANKERL_UNORDERED_DENSE_NOINLINE
#define ANKERL_UNORDERED_DENSE_EXPORT