34 #ifndef ROBIN_HOOD_H_INCLUDED
35 #define ROBIN_HOOD_H_INCLUDED
38 #define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes
39 #define ROBIN_HOOD_VERSION_MINOR 4 // for adding functionality in a backwards-compatible manner
40 #define ROBIN_HOOD_VERSION_PATCH 1 // for backwards-compatible bug fixes
48 #include <type_traits>
52 #ifdef ROBIN_HOOD_LOG_ENABLED
54 # define ROBIN_HOOD_LOG(x) std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << x << std::endl
56 # define ROBIN_HOOD_LOG(x)
60 #ifdef ROBIN_HOOD_TRACE_ENABLED
62 # define ROBIN_HOOD_TRACE(x) \
63 std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << x << std::endl
65 # define ROBIN_HOOD_TRACE(x)
70 #define ROBIN_HOOD(x) ROBIN_HOOD_PRIVATE_DEFINITION_##x()
73 #define ROBIN_HOOD_UNUSED(identifier)
76 #if SIZE_MAX == UINT32_MAX
77 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 32
78 #elif SIZE_MAX == UINT64_MAX
79 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 64
81 # error Unsupported bitness
86 # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() 1
87 # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() 0
89 # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() \
90 (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
91 # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
96 # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __declspec(noinline)
98 # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __attribute__((noinline))
102 #if !defined(__cpp_exceptions) && !defined(__EXCEPTIONS) && !defined(_CPPUNWIND)
103 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 0
105 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 1
110 # if ROBIN_HOOD(BITNESS) == 32
111 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward
113 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward64
116 # pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD))
117 # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \
118 [](size_t mask) noexcept->int { \
119 unsigned long index; \
120 return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast<int>(index) \
121 : ROBIN_HOOD(BITNESS); \
125 # if ROBIN_HOOD(BITNESS) == 32
126 # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl
127 # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl
129 # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll
130 # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll
132 # define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS))
133 # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS))
137 #ifndef __has_cpp_attribute // For backwards compatibility
138 # define __has_cpp_attribute(x) 0
140 #if __has_cpp_attribute(clang::fallthrough)
141 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[clang::fallthrough]]
142 #elif __has_cpp_attribute(gnu::fallthrough)
143 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[gnu::fallthrough]]
145 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH()
150 # define ROBIN_HOOD_LIKELY(condition) condition
151 # define ROBIN_HOOD_UNLIKELY(condition) condition
153 # define ROBIN_HOOD_LIKELY(condition) __builtin_expect(condition, 1)
154 # define ROBIN_HOOD_UNLIKELY(condition) __builtin_expect(condition, 0)
159 #if defined(__GNUC__) && __GNUC__ < 5
160 # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__)
162 # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value
166 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX() __cplusplus
167 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX98() 199711L
168 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX11() 201103L
169 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX14() 201402L
170 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX17() 201703L
172 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17)
173 # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() [[nodiscard]]
175 # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD()
178 namespace robin_hood {
180 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14)
181 # define ROBIN_HOOD_STD std
185 namespace ROBIN_HOOD_STD {
188 : std::integral_constant<std::size_t, alignof(typename std::remove_all_extents<T>::type)> {};
190 template <
class T, T... Ints>
191 class integer_sequence {
193 using value_type = T;
194 static_assert(std::is_integral<value_type>::value,
"not integral type");
195 static constexpr std::size_t size() noexcept {
196 return sizeof...(Ints);
199 template <std::size_t... Inds>
200 using index_sequence = integer_sequence<std::size_t, Inds...>;
203 template <
class T, T Begin, T End,
bool>
206 static_assert(std::is_integral<TValue>::value,
"not integral type");
207 static_assert(Begin >= 0 && Begin < End,
"unexpected argument (Begin<0 || Begin<=End)");
209 template <
class,
class>
210 struct IntSeqCombiner;
212 template <TValue... Inds0, TValue... Inds1>
213 struct IntSeqCombiner<integer_sequence<TValue, Inds0...>, integer_sequence<TValue, Inds1...>> {
214 using TResult = integer_sequence<TValue, Inds0..., Inds1...>;
218 typename IntSeqCombiner<
typename IntSeqImpl<TValue, Begin, Begin + (End - Begin) / 2,
219 (End - Begin) / 2 == 1>::TResult,
220 typename IntSeqImpl<TValue, Begin + (End - Begin) / 2, End,
221 (End - Begin + 1) / 2 == 1>::TResult>::TResult;
224 template <
class T, T Begin>
225 struct IntSeqImpl<T, Begin, Begin, false> {
227 static_assert(std::is_integral<TValue>::value,
"not integral type");
228 static_assert(Begin >= 0,
"unexpected argument (Begin<0)");
229 using TResult = integer_sequence<TValue>;
232 template <
class T, T Begin, T End>
233 struct IntSeqImpl<T, Begin, End, true> {
235 static_assert(std::is_integral<TValue>::value,
"not integral type");
236 static_assert(Begin >= 0,
"unexpected argument (Begin<0)");
237 using TResult = integer_sequence<TValue, Begin>;
241 template <
class T, T N>
242 using make_integer_sequence =
typename detail_::IntSeqImpl<T, 0, N, (N - 0) == 1>::TResult;
244 template <std::
size_t N>
245 using make_index_sequence = make_integer_sequence<std::size_t, N>;
247 template <
class... T>
248 using index_sequence_for = make_index_sequence<
sizeof...(T)>;
257 #if defined(__SIZEOF_INT128__)
258 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 1
259 # if defined(__GNUC__) || defined(__clang__)
260 # pragma GCC diagnostic push
261 # pragma GCC diagnostic ignored "-Wpedantic"
262 using uint128_t =
unsigned __int128;
263 # pragma GCC diagnostic pop
265 inline uint64_t umul128(uint64_t a, uint64_t b, uint64_t* high) noexcept {
266 auto result =
static_cast<uint128_t
>(a) *
static_cast<uint128_t
>(b);
267 *high =
static_cast<uint64_t
>(result >> 64U);
268 return static_cast<uint64_t
>(result);
270 #elif (defined(_WIN32) && ROBIN_HOOD(BITNESS) == 64)
271 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 1
273 # pragma intrinsic(__umulh)
275 # pragma intrinsic(_umul128)
277 inline uint64_t umul128(uint64_t a, uint64_t b, uint64_t* high) noexcept {
279 *high = __umulh(a, b);
280 return ((uint64_t)(a)) * (b);
282 return _umul128(a, b, high);
286 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 0
292 template <
typename T>
293 inline T reinterpret_cast_no_cast_align_warning(
void* ptr) noexcept {
294 return reinterpret_cast<T
>(ptr);
297 template <
typename T>
298 inline T reinterpret_cast_no_cast_align_warning(
void const* ptr) noexcept {
299 return reinterpret_cast<T
>(ptr);
304 template <
typename E,
typename... Args>
306 #if ROBIN_HOOD(HAS_EXCEPTIONS)
307 void doThrow(Args&&... args) {
309 throw E(std::forward<Args>(args)...);
312 void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) ) {
317 template <
typename E,
typename T,
typename... Args>
318 T* assertNotNull(T* t, Args&&... args) {
319 if (ROBIN_HOOD_UNLIKELY(
nullptr == t)) {
320 doThrow<E>(std::forward<Args>(args)...);
325 template <
typename T>
326 inline T unaligned_load(
void const* ptr) noexcept {
330 std::memcpy(&t, ptr,
sizeof(T));
337 template <
typename T,
size_t MinNumAllocs = 4,
size_t MaxNumAllocs = 256>
338 class BulkPoolAllocator {
340 BulkPoolAllocator() noexcept = default;
343 BulkPoolAllocator(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) ) noexcept
345 , mListForFree(
nullptr) {}
347 BulkPoolAllocator(BulkPoolAllocator&& o) noexcept
349 , mListForFree(o.mListForFree) {
350 o.mListForFree =
nullptr;
354 BulkPoolAllocator& operator=(BulkPoolAllocator&& o) noexcept {
357 mListForFree = o.mListForFree;
358 o.mListForFree =
nullptr;
364 operator=(
const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) ) noexcept {
369 ~BulkPoolAllocator() noexcept {
374 void reset() noexcept {
375 while (mListForFree) {
376 T* tmp = *mListForFree;
378 mListForFree = reinterpret_cast_no_cast_align_warning<T**>(tmp);
389 tmp = performAllocation();
392 mHead = *reinterpret_cast_no_cast_align_warning<T**>(tmp);
400 void deallocate(T* obj) noexcept {
401 *reinterpret_cast_no_cast_align_warning<T**>(obj) = mHead;
408 void addOrFree(
void* ptr,
const size_t numBytes) noexcept {
410 if (numBytes < ALIGNMENT + ALIGNED_SIZE) {
418 void swap(BulkPoolAllocator<T, MinNumAllocs, MaxNumAllocs>& other) noexcept {
420 swap(mHead, other.mHead);
421 swap(mListForFree, other.mListForFree);
429 ROBIN_HOOD(NODISCARD)
size_t calcNumElementsToAlloc() const noexcept {
430 auto tmp = mListForFree;
431 size_t numAllocs = MinNumAllocs;
433 while (numAllocs * 2 <= MaxNumAllocs && tmp) {
434 auto x =
reinterpret_cast<T***
>(tmp);
443 void add(
void* ptr,
const size_t numBytes) noexcept {
444 const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE;
446 auto data =
reinterpret_cast<T**
>(ptr);
449 auto x =
reinterpret_cast<T***
>(data);
455 reinterpret_cast_no_cast_align_warning<T*>(
reinterpret_cast<char*
>(ptr) + ALIGNMENT);
457 auto const head =
reinterpret_cast<char*
>(headT);
460 for (
size_t i = 0; i < numElements; ++i) {
461 *reinterpret_cast_no_cast_align_warning<char**>(head + i * ALIGNED_SIZE) =
462 head + (i + 1) * ALIGNED_SIZE;
466 *reinterpret_cast_no_cast_align_warning<T**>(head + (numElements - 1) * ALIGNED_SIZE) =
473 ROBIN_HOOD(NOINLINE) T* performAllocation() {
474 size_t const numElementsToAlloc = calcNumElementsToAlloc();
478 size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc;
479 add(assertNotNull<std::bad_alloc>(malloc(bytes)), bytes);
484 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14)
485 static constexpr
size_t ALIGNMENT =
486 (std::max)(std::alignment_of<T>::value, std::alignment_of<T*>::value);
488 static const size_t ALIGNMENT =
489 (ROBIN_HOOD_STD::alignment_of<T>::value > ROBIN_HOOD_STD::alignment_of<T*>::value)
490 ? ROBIN_HOOD_STD::alignment_of<T>::value
491 : +ROBIN_HOOD_STD::alignment_of<T*>::value;
494 static constexpr
size_t ALIGNED_SIZE = ((
sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT;
496 static_assert(MinNumAllocs >= 1,
"MinNumAllocs");
497 static_assert(MaxNumAllocs >= MinNumAllocs,
"MaxNumAllocs");
498 static_assert(ALIGNED_SIZE >=
sizeof(T*),
"ALIGNED_SIZE");
499 static_assert(0 == (ALIGNED_SIZE %
sizeof(T*)),
"ALIGNED_SIZE mod");
500 static_assert(ALIGNMENT >=
sizeof(T*),
"ALIGNMENT");
503 T** mListForFree{
nullptr};
506 template <
typename T,
size_t MinSize,
size_t MaxSize,
bool IsFlatMap>
507 struct NodeAllocator;
510 template <
typename T,
size_t MinSize,
size_t MaxSize>
511 struct NodeAllocator<T, MinSize, MaxSize, true> {
514 void addOrFree(
void* ptr,
size_t ROBIN_HOOD_UNUSED(numBytes) ) noexcept {
519 template <
typename T,
size_t MinSize,
size_t MaxSize>
520 struct NodeAllocator<T, MinSize, MaxSize, false> :
public BulkPoolAllocator<T, MinSize, MaxSize> {};
523 template <
typename T>
524 struct identity_hash {
525 constexpr
size_t operator()(T
const& obj)
const noexcept {
526 return static_cast<size_t>(obj);
532 namespace swappable {
534 template <
typename T>
536 static const bool value = noexcept(swap(std::declval<T&>(), std::declval<T&>()));
543 struct is_transparent_tag {};
548 template <
typename T1,
typename T2>
550 using first_type = T1;
551 using second_type = T2;
553 template <
typename U1 = T1,
typename U2 = T2,
554 typename =
typename std::enable_if<std::is_default_constructible<U1>::value &&
555 std::is_default_constructible<U2>::value>::type>
556 constexpr pair() noexcept(noexcept(U1()) && noexcept(U2()))
561 explicit constexpr pair(std::pair<T1, T2>
const& o) noexcept(
562 noexcept(T1(std::declval<T1 const&>())) && noexcept(T2(std::declval<T2 const&>())))
564 , second(o.second) {}
567 explicit constexpr pair(std::pair<T1, T2>&& o) noexcept(
568 noexcept(T1(std::move(std::declval<T1&&>()))) &&
569 noexcept(T2(std::move(std::declval<T2&&>()))))
570 : first(std::move(o.first))
571 , second(std::move(o.second)) {}
573 constexpr pair(T1&& a, T2&& b) noexcept(noexcept(T1(std::move(std::declval<T1&&>()))) &&
574 noexcept(T2(std::move(std::declval<T2&&>()))))
575 : first(std::move(a))
576 , second(std::move(b)) {}
578 template <
typename U1,
typename U2>
579 constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward<U1>(std::declval<U1&&>()))) &&
580 noexcept(T2(std::forward<U2>(std::declval<U2&&>()))))
581 : first(std::forward<U1>(a))
582 , second(std::forward<U2>(b)) {}
584 template <
typename... U1,
typename... U2>
586 std::piecewise_construct_t , std::tuple<U1...> a,
587 std::tuple<U2...> b) noexcept(noexcept(pair(std::declval<std::tuple<U1...>&>(),
588 std::declval<std::tuple<U2...>&>(),
589 ROBIN_HOOD_STD::index_sequence_for<U1...>(),
590 ROBIN_HOOD_STD::index_sequence_for<U2...>())))
591 : pair(a, b, ROBIN_HOOD_STD::index_sequence_for<U1...>(),
592 ROBIN_HOOD_STD::index_sequence_for<U2...>()) {}
595 template <
typename... U1,
size_t... I1,
typename... U2,
size_t... I2>
596 pair(std::tuple<U1...>& a, std::tuple<U2...>& b,
597 ROBIN_HOOD_STD::index_sequence<I1...> ,
598 ROBIN_HOOD_STD::index_sequence<
599 I2...> ) noexcept(noexcept(T1(std::
600 forward<U1>(std::get<I1>(
602 std::tuple<U1...>&>()))...)) &&
603 noexcept(T2(std::forward<U2>(
604 std::get<I2>(std::declval<std::tuple<U2...>&>()))...)))
605 : first(std::forward<U1>(std::get<I1>(a))...)
606 , second(std::forward<U2>(std::get<I2>(b))...) {
613 ROBIN_HOOD(NODISCARD) first_type& getFirst() noexcept {
616 ROBIN_HOOD(NODISCARD) first_type
const& getFirst() const noexcept {
619 ROBIN_HOOD(NODISCARD) second_type& getSecond() noexcept {
622 ROBIN_HOOD(NODISCARD) second_type
const& getSecond() const noexcept {
626 void swap(pair<T1, T2>& o) noexcept((detail::swappable::nothrow<T1>::value) &&
627 (detail::swappable::nothrow<T2>::value)) {
629 swap(first, o.first);
630 swap(second, o.second);
637 template <
typename A,
typename B>
638 void swap(pair<A, B>& a, pair<A, B>& b) noexcept(
639 noexcept(std::declval<pair<A, B>&>().swap(std::declval<pair<A, B>&>()))) {
645 static size_t hash_bytes(
void const* ptr,
size_t const len) noexcept {
646 static constexpr uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
647 static constexpr uint64_t seed = UINT64_C(0xe17a1465);
648 static constexpr
unsigned int r = 47;
650 auto const data64 =
static_cast<uint64_t const*
>(ptr);
651 uint64_t h = seed ^ (len * m);
653 size_t const n_blocks = len / 8;
654 for (
size_t i = 0; i < n_blocks; ++i) {
655 auto k = detail::unaligned_load<uint64_t>(data64 + i);
665 auto const data8 =
reinterpret_cast<uint8_t const*
>(data64 + n_blocks);
668 h ^=
static_cast<uint64_t
>(data8[6]) << 48U;
669 ROBIN_HOOD(FALLTHROUGH);
671 h ^=
static_cast<uint64_t
>(data8[5]) << 40U;
672 ROBIN_HOOD(FALLTHROUGH);
674 h ^=
static_cast<uint64_t
>(data8[4]) << 32U;
675 ROBIN_HOOD(FALLTHROUGH);
677 h ^=
static_cast<uint64_t
>(data8[3]) << 24U;
678 ROBIN_HOOD(FALLTHROUGH);
680 h ^=
static_cast<uint64_t
>(data8[2]) << 16U;
681 ROBIN_HOOD(FALLTHROUGH);
683 h ^=
static_cast<uint64_t
>(data8[1]) << 8U;
684 ROBIN_HOOD(FALLTHROUGH);
686 h ^=
static_cast<uint64_t
>(data8[0]);
688 ROBIN_HOOD(FALLTHROUGH);
696 return static_cast<size_t>(h);
699 inline size_t hash_int(uint64_t obj) noexcept {
700 #if ROBIN_HOOD(HAS_UMUL128)
702 static constexpr uint64_t k = UINT64_C(0xde5fb9d2630458e9);
704 uint64_t l = detail::umul128(obj, k, &h);
706 #elif ROBIN_HOOD(BITNESS) == 32
707 uint64_t
const r = obj * UINT64_C(0xca4bcaa75ec3f625);
708 auto h =
static_cast<uint32_t
>(r >> 32U);
709 auto l =
static_cast<uint32_t
>(r);
715 h *= 0xff51afd7ed558ccd;
717 h *= 0xc4ceb9fe1a85ec53;
719 return static_cast<size_t>(h);
724 template <
typename T>
725 struct hash :
public std::hash<T> {
726 size_t operator()(T
const& obj)
const
727 noexcept(noexcept(std::declval<std::hash<T>>().
operator()(std::declval<T const&>()))) {
729 auto result = std::hash<T>::operator()(obj);
731 return hash_int(
static_cast<uint64_t
>(result));
736 struct hash<std::string> {
737 size_t operator()(std::string
const& str)
const noexcept {
738 return hash_bytes(str.data(), str.size());
744 size_t operator()(T* ptr)
const noexcept {
745 return hash_int(
reinterpret_cast<size_t>(ptr));
749 #define ROBIN_HOOD_HASH_INT(T) \
752 size_t operator()(T obj) const noexcept { \
753 return hash_int(static_cast<uint64_t>(obj)); \
757 #if defined(__GNUC__) && !defined(__clang__)
758 # pragma GCC diagnostic push
759 # pragma GCC diagnostic ignored "-Wuseless-cast"
762 ROBIN_HOOD_HASH_INT(
bool);
763 ROBIN_HOOD_HASH_INT(
char);
764 ROBIN_HOOD_HASH_INT(
signed char);
765 ROBIN_HOOD_HASH_INT(
unsigned char);
766 ROBIN_HOOD_HASH_INT(char16_t);
767 ROBIN_HOOD_HASH_INT(char32_t);
768 ROBIN_HOOD_HASH_INT(
wchar_t);
769 ROBIN_HOOD_HASH_INT(
short);
770 ROBIN_HOOD_HASH_INT(
unsigned short);
771 ROBIN_HOOD_HASH_INT(
int);
772 ROBIN_HOOD_HASH_INT(
unsigned int);
773 ROBIN_HOOD_HASH_INT(
long);
774 ROBIN_HOOD_HASH_INT(
long long);
775 ROBIN_HOOD_HASH_INT(
unsigned long);
776 ROBIN_HOOD_HASH_INT(
unsigned long long);
777 #if defined(__GNUC__) && !defined(__clang__)
778 # pragma GCC diagnostic pop
784 template <
typename T>
785 struct WrapHash :
public T {
786 WrapHash() =
default;
787 explicit WrapHash(T
const& o) noexcept(noexcept(T(std::declval<T const&>())))
791 template <
typename T>
792 struct WrapKeyEqual :
public T {
793 WrapKeyEqual() =
default;
794 explicit WrapKeyEqual(T
const& o) noexcept(noexcept(T(std::declval<T const&>())))
825 template <
bool IsFlatMap,
size_t MaxLoadFactor100,
typename Key,
typename T,
typename Hash,
828 :
public WrapHash<Hash>,
829 public WrapKeyEqual<KeyEqual>,
830 detail::NodeAllocator<
831 robin_hood::pair<typename std::conditional<IsFlatMap, Key, Key const>::type, T>, 4, 16384,
834 using key_type = Key;
835 using mapped_type = T;
837 robin_hood::pair<typename std::conditional<IsFlatMap, Key, Key const>::type, T>;
838 using size_type = size_t;
840 using key_equal = KeyEqual;
842 unordered_map<IsFlatMap, MaxLoadFactor100, key_type, mapped_type, hasher, key_equal>;
843 static constexpr
bool is_flat_map = IsFlatMap;
846 static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100,
847 "MaxLoadFactor100 needs to be >10 && < 100");
849 using WHash = WrapHash<Hash>;
850 using WKeyEqual = WrapKeyEqual<KeyEqual>;
855 static constexpr
size_t InitialNumElements =
sizeof(uint64_t);
856 static constexpr uint32_t InitialInfoNumBits = 5;
857 static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits;
858 static constexpr uint8_t InitialInfoHashShift =
sizeof(size_t) * 8 - InitialInfoNumBits;
859 using DataPool = detail::NodeAllocator<value_type, 4, 16384, IsFlatMap>;
862 using InfoType = uint32_t;
869 template <
typename M,
bool>
873 template <
typename M>
874 class DataNode<M, true> final {
876 template <
typename... Args>
877 explicit DataNode(M& ROBIN_HOOD_UNUSED(map) , Args&&... args) noexcept(
878 noexcept(value_type(std::forward<Args>(args)...)))
879 : mData(std::forward<Args>(args)...) {}
881 DataNode(M& ROBIN_HOOD_UNUSED(map) , DataNode<M, true>&& n) noexcept(
882 std::is_nothrow_move_constructible<value_type>::value)
883 : mData(std::move(n.mData)) {}
886 void destroy(M& ROBIN_HOOD_UNUSED(map) ) noexcept {}
887 void destroyDoNotDeallocate() noexcept {}
889 value_type
const* operator->() const noexcept {
892 value_type* operator->() noexcept {
896 const value_type& operator*() const noexcept {
900 value_type& operator*() noexcept {
904 ROBIN_HOOD(NODISCARD)
typename value_type::first_type& getFirst() noexcept {
908 ROBIN_HOOD(NODISCARD)
typename value_type::first_type
const& getFirst() const noexcept {
912 ROBIN_HOOD(NODISCARD)
typename value_type::second_type& getSecond() noexcept {
916 ROBIN_HOOD(NODISCARD)
typename value_type::second_type
const& getSecond() const noexcept {
920 void swap(DataNode<M, true>& o) noexcept(
921 noexcept(std::declval<value_type>().swap(std::declval<value_type>()))) {
930 template <
typename M>
931 class DataNode<M, false> {
933 template <
typename... Args>
934 explicit DataNode(M& map, Args&&... args)
935 : mData(map.allocate()) {
936 ::new (
static_cast<void*
>(mData)) value_type(std::forward<Args>(args)...);
939 DataNode(M& ROBIN_HOOD_UNUSED(map) , DataNode<M, false>&& n) noexcept
940 : mData(std::move(n.mData)) {}
942 void destroy(M& map) noexcept {
944 mData->~value_type();
945 map.deallocate(mData);
948 void destroyDoNotDeallocate() noexcept {
949 mData->~value_type();
952 value_type
const* operator->() const noexcept {
956 value_type* operator->() noexcept {
960 const value_type& operator*()
const {
964 value_type& operator*() {
968 ROBIN_HOOD(NODISCARD)
typename value_type::first_type& getFirst() {
972 ROBIN_HOOD(NODISCARD)
typename value_type::first_type
const& getFirst()
const {
976 ROBIN_HOOD(NODISCARD)
typename value_type::second_type& getSecond() {
977 return mData->second;
980 ROBIN_HOOD(NODISCARD)
typename value_type::second_type
const& getSecond()
const {
981 return mData->second;
984 void swap(DataNode<M, false>& o) noexcept {
986 swap(mData, o.mData);
993 using Node = DataNode<Self, IsFlatMap>;
997 template <
typename M,
bool UseMemcpy>
1001 template <
typename M>
1002 struct Cloner<M, true> {
1003 void operator()(M
const& source, M& target)
const {
1006 auto src =
reinterpret_cast<char const*
>(source.mKeyVals);
1007 auto tgt =
reinterpret_cast<char*
>(target.mKeyVals);
1008 std::copy(src, src + target.calcNumBytesTotal(target.mMask + 1), tgt);
1012 template <
typename M>
1013 struct Cloner<M, false> {
1014 void operator()(M
const& s, M& t)
const {
1015 std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(t.mMask + 1), t.mInfo);
1017 for (
size_t i = 0; i < t.mMask + 1; ++i) {
1019 ::new (
static_cast<void*
>(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]);
1027 template <
typename M,
bool IsFlatMapAndTrivial>
1028 struct Destroyer {};
1030 template <
typename M>
1031 struct Destroyer<M, true> {
1032 void nodes(M& m)
const noexcept {
1036 void nodesDoNotDeallocate(M& m)
const noexcept {
1041 template <
typename M>
1042 struct Destroyer<M, false> {
1043 void nodes(M& m)
const noexcept {
1046 for (
size_t idx = 0; idx <= m.mMask; ++idx) {
1047 if (0 != m.mInfo[idx]) {
1048 Node& n = m.mKeyVals[idx];
1055 void nodesDoNotDeallocate(M& m)
const noexcept {
1058 for (
size_t idx = 0; idx <= m.mMask; ++idx) {
1059 if (0 != m.mInfo[idx]) {
1060 Node& n = m.mKeyVals[idx];
1061 n.destroyDoNotDeallocate();
1070 struct fast_forward_tag {};
1073 template <
bool IsConst>
1077 using NodePtr =
typename std::conditional<IsConst, Node const*, Node*>::type;
1080 using difference_type = std::ptrdiff_t;
1081 using value_type =
typename Self::value_type;
1082 using reference =
typename std::conditional<IsConst, value_type const&, value_type&>::type;
1083 using pointer =
typename std::conditional<IsConst, value_type const*, value_type*>::type;
1084 using iterator_category = std::forward_iterator_tag;
1094 template <
bool OtherIsConst,
1095 typename =
typename std::enable_if<IsConst && !OtherIsConst>::type>
1097 Iter(Iter<OtherIsConst>
const& other) noexcept
1098 : mKeyVals(other.mKeyVals)
1099 , mInfo(other.mInfo) {}
1101 Iter(NodePtr valPtr, uint8_t
const* infoPtr) noexcept
1105 Iter(NodePtr valPtr, uint8_t
const* infoPtr,
1106 fast_forward_tag ROBIN_HOOD_UNUSED(tag) ) noexcept
1112 template <
bool OtherIsConst,
1113 typename =
typename std::enable_if<IsConst && !OtherIsConst>::type>
1114 Iter& operator=(Iter<OtherIsConst>
const& other) noexcept {
1115 mKeyVals = other.mKeyVals;
1116 mInfo = other.mInfo;
1121 Iter& operator++() noexcept {
1128 reference operator*()
const {
1132 pointer operator->()
const {
1137 bool operator==(Iter<O>
const& o)
const noexcept {
1138 return mKeyVals == o.mKeyVals;
1142 bool operator!=(Iter<O>
const& o)
const noexcept {
1143 return mKeyVals != o.mKeyVals;
1148 void fastForward() noexcept {
1151 auto const n = detail::unaligned_load<size_t>(mInfo);
1152 #if ROBIN_HOOD(LITTLE_ENDIAN)
1153 inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8;
1155 inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8;
1159 }
while (inc ==
static_cast<int>(
sizeof(
size_t)));
1162 friend class unordered_map<IsFlatMap, MaxLoadFactor100, key_type, mapped_type, hasher,
1164 NodePtr mKeyVals{
nullptr};
1165 uint8_t
const* mInfo{
nullptr};
1173 template <
typename HashKey>
1174 void keyToIdx(HashKey&& key,
size_t* idx, InfoType* info)
const {
1179 typename std::conditional<std::is_same<::robin_hood::hash<key_type>, hasher>::value,
1180 ::robin_hood::detail::identity_hash<size_t>,
1181 ::robin_hood::hash<size_t>>::type;
1182 *idx = Mix{}(WHash::operator()(key));
1184 *info = mInfoInc +
static_cast<InfoType
>(*idx >> mInfoHashShift);
1189 void next(InfoType* info,
size_t* idx)
const noexcept {
1190 *idx = (*idx + 1) & mMask;
1194 void nextWhileLess(InfoType* info,
size_t* idx)
const noexcept {
1196 while (*info < mInfo[*idx]) {
1206 size_t const insertion_idx) noexcept(std::is_nothrow_move_assignable<Node>::value) {
1207 while (idx != insertion_idx) {
1208 size_t prev_idx = (idx - 1) & mMask;
1210 mKeyVals[idx] = std::move(mKeyVals[prev_idx]);
1212 ::new (
static_cast<void*
>(mKeyVals + idx)) Node(std::move(mKeyVals[prev_idx]));
1214 mInfo[idx] =
static_cast<uint8_t
>(mInfo[prev_idx] + mInfoInc);
1215 if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) {
1216 mMaxNumElementsAllowed = 0;
1222 void shiftDown(
size_t idx) noexcept(std::is_nothrow_move_assignable<Node>::value) {
1225 mKeyVals[idx].destroy(*
this);
1228 size_t nextIdx = (idx + 1) & mMask;
1229 while (mInfo[nextIdx] >= 2 * mInfoInc) {
1230 mInfo[idx] =
static_cast<uint8_t
>(mInfo[nextIdx] - mInfoInc);
1231 mKeyVals[idx] = std::move(mKeyVals[nextIdx]);
1233 nextIdx = (idx + 1) & mMask;
1239 mKeyVals[idx].~Node();
1243 template <
typename Other>
1244 ROBIN_HOOD(NODISCARD)
1245 size_t findIdx(Other
const& key)
const {
1248 keyToIdx(key, &idx, &info);
1252 if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
1256 if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
1260 }
while (info <= mInfo[idx]);
1263 return mMask == 0 ? 0 : mMask + 1;
1266 void cloneData(
const unordered_map& o) {
1267 Cloner<unordered_map, IsFlatMap && ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(Node)>()(o, *
this);
1272 size_t insert_move(Node&& keyval) {
1275 if (0 == mMaxNumElementsAllowed && !try_increase_info()) {
1276 throwOverflowError();
1281 keyToIdx(keyval.getFirst(), &idx, &info);
1284 while (info <= mInfo[idx]) {
1285 idx = (idx + 1) & mMask;
1290 auto const insertion_idx = idx;
1291 auto const insertion_info =
static_cast<uint8_t
>(info);
1292 if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
1293 mMaxNumElementsAllowed = 0;
1297 while (0 != mInfo[idx]) {
1301 auto& l = mKeyVals[insertion_idx];
1302 if (idx == insertion_idx) {
1303 ::new (
static_cast<void*
>(&l)) Node(std::move(keyval));
1305 shiftUp(idx, insertion_idx);
1306 l = std::move(keyval);
1310 mInfo[insertion_idx] = insertion_info;
1313 return insertion_idx;
1317 using iterator = Iter<false>;
1318 using const_iterator = Iter<true>;
1325 explicit unordered_map(
size_t ROBIN_HOOD_UNUSED(bucket_count) = 0,
1326 const Hash& h = Hash{},
1327 const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) &&
1328 noexcept(KeyEqual(equal)))
1330 , WKeyEqual(equal) {
1331 ROBIN_HOOD_TRACE(
this);
1334 template <
typename Iter>
1335 unordered_map(Iter first, Iter last,
size_t ROBIN_HOOD_UNUSED(bucket_count) = 0,
1336 const Hash& h = Hash{},
const KeyEqual& equal = KeyEqual{})
1338 , WKeyEqual(equal) {
1339 ROBIN_HOOD_TRACE(
this);
1340 insert(first, last);
1343 unordered_map(std::initializer_list<value_type> initlist,
1344 size_t ROBIN_HOOD_UNUSED(bucket_count) = 0,
const Hash& h = Hash{},
1345 const KeyEqual& equal = KeyEqual{})
1347 , WKeyEqual(equal) {
1348 ROBIN_HOOD_TRACE(
this);
1349 insert(initlist.begin(), initlist.end());
1352 unordered_map(unordered_map&& o) noexcept
1353 : WHash(std::move(
static_cast<WHash&
>(o)))
1354 , WKeyEqual(std::move(
static_cast<WKeyEqual&
>(o)))
1355 , DataPool(std::move(
static_cast<DataPool&
>(o))) {
1356 ROBIN_HOOD_TRACE(
this);
1358 mKeyVals = std::move(o.mKeyVals);
1359 mInfo = std::move(o.mInfo);
1360 mNumElements = std::move(o.mNumElements);
1361 mMask = std::move(o.mMask);
1362 mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed);
1363 mInfoInc = std::move(o.mInfoInc);
1364 mInfoHashShift = std::move(o.mInfoHashShift);
1370 unordered_map& operator=(unordered_map&& o) noexcept {
1371 ROBIN_HOOD_TRACE(
this);
1376 mKeyVals = std::move(o.mKeyVals);
1377 mInfo = std::move(o.mInfo);
1378 mNumElements = std::move(o.mNumElements);
1379 mMask = std::move(o.mMask);
1380 mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed);
1381 mInfoInc = std::move(o.mInfoInc);
1382 mInfoHashShift = std::move(o.mInfoHashShift);
1383 WHash::operator=(std::move(
static_cast<WHash&
>(o)));
1384 WKeyEqual::operator=(std::move(
static_cast<WKeyEqual&
>(o)));
1385 DataPool::operator=(std::move(
static_cast<DataPool&
>(o)));
1397 unordered_map(
const unordered_map& o)
1398 : WHash(static_cast<const WHash&>(o))
1399 , WKeyEqual(static_cast<const WKeyEqual&>(o))
1400 , DataPool(static_cast<const DataPool&>(o)) {
1401 ROBIN_HOOD_TRACE(
this);
1406 mKeyVals =
static_cast<Node*
>(
1407 detail::assertNotNull<std::bad_alloc>(malloc(calcNumBytesTotal(o.mMask + 1))));
1409 mInfo =
reinterpret_cast<uint8_t*
>(mKeyVals + o.mMask + 1);
1410 mNumElements = o.mNumElements;
1412 mMaxNumElementsAllowed = o.mMaxNumElementsAllowed;
1413 mInfoInc = o.mInfoInc;
1414 mInfoHashShift = o.mInfoHashShift;
1420 unordered_map& operator=(unordered_map
const& o) {
1421 ROBIN_HOOD_TRACE(
this);
1439 WHash::operator=(
static_cast<const WHash&
>(o));
1440 WKeyEqual::operator=(
static_cast<const WKeyEqual&
>(o));
1441 DataPool::operator=(
static_cast<DataPool const&
>(o));
1447 Destroyer<Self, IsFlatMap && std::is_trivially_destructible<Node>::value>{}.nodes(*
this);
1449 if (mMask != o.mMask) {
1456 mKeyVals =
static_cast<Node*
>(
1457 detail::assertNotNull<std::bad_alloc>(malloc(calcNumBytesTotal(o.mMask + 1))));
1460 mInfo =
reinterpret_cast<uint8_t*
>(mKeyVals + o.mMask + 1);
1463 WHash::operator=(
static_cast<const WHash&
>(o));
1464 WKeyEqual::operator=(
static_cast<const WKeyEqual&
>(o));
1465 DataPool::operator=(
static_cast<DataPool const&
>(o));
1466 mNumElements = o.mNumElements;
1468 mMaxNumElementsAllowed = o.mMaxNumElementsAllowed;
1469 mInfoInc = o.mInfoInc;
1470 mInfoHashShift = o.mInfoHashShift;
1477 void swap(unordered_map& o) {
1478 ROBIN_HOOD_TRACE(
this);
1485 ROBIN_HOOD_TRACE(
this);
1492 Destroyer<Self, IsFlatMap && std::is_trivially_destructible<Node>::value>{}.nodes(*
this);
1496 uint8_t
const z = 0;
1497 std::fill(mInfo, mInfo + (
sizeof(uint8_t) * (mMask + 1)), z);
1499 mInfoInc = InitialInfoInc;
1500 mInfoHashShift = InitialInfoHashShift;
1505 ROBIN_HOOD_TRACE(
this);
1510 bool operator==(
const unordered_map& other)
const {
1511 ROBIN_HOOD_TRACE(
this);
1512 if (other.size() != size()) {
1515 for (
auto const& otherEntry : other) {
1516 auto const myIt = find(otherEntry.first);
1517 if (myIt == end() || !(myIt->second == otherEntry.second)) {
1525 bool operator!=(
const unordered_map& other)
const {
1526 ROBIN_HOOD_TRACE(
this);
1527 return !operator==(other);
1530 mapped_type& operator[](
const key_type& key) {
1531 ROBIN_HOOD_TRACE(
this);
1532 return doCreateByKey(key);
1535 mapped_type& operator[](key_type&& key) {
1536 ROBIN_HOOD_TRACE(
this);
1537 return doCreateByKey(std::move(key));
1540 template <
typename Iter>
1541 void insert(Iter first, Iter last) {
1542 for (; first != last; ++first) {
1544 insert(value_type(*first));
1548 template <
typename... Args>
1549 std::pair<iterator, bool> emplace(Args&&... args) {
1550 ROBIN_HOOD_TRACE(
this);
1551 Node n{*
this, std::forward<Args>(args)...};
1552 auto r = doInsert(std::move(n));
1561 std::pair<iterator, bool> insert(
const value_type& keyval) {
1562 ROBIN_HOOD_TRACE(
this);
1563 return doInsert(keyval);
1566 std::pair<iterator, bool> insert(value_type&& keyval) {
1567 return doInsert(std::move(keyval));
1571 size_t count(
const key_type& key)
const {
1572 ROBIN_HOOD_TRACE(
this);
1573 auto kv = mKeyVals + findIdx(key);
1574 if (kv != reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1582 mapped_type& at(key_type
const& key) {
1583 ROBIN_HOOD_TRACE(
this);
1584 auto kv = mKeyVals + findIdx(key);
1585 if (kv == reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1586 doThrow<std::out_of_range>(
"key not found");
1588 return kv->getSecond();
1593 mapped_type
const& at(key_type
const& key)
const {
1594 ROBIN_HOOD_TRACE(
this);
1595 auto kv = mKeyVals + findIdx(key);
1596 if (kv == reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1597 doThrow<std::out_of_range>(
"key not found");
1599 return kv->getSecond();
1602 const_iterator find(
const key_type& key)
const {
1603 ROBIN_HOOD_TRACE(
this);
1604 const size_t idx = findIdx(key);
1605 return const_iterator{mKeyVals + idx, mInfo + idx};
1608 template <
typename OtherKey>
1609 const_iterator find(
const OtherKey& key, is_transparent_tag )
const {
1610 ROBIN_HOOD_TRACE(
this);
1611 const size_t idx = findIdx(key);
1612 return const_iterator{mKeyVals + idx, mInfo + idx};
1615 iterator find(
const key_type& key) {
1616 ROBIN_HOOD_TRACE(
this);
1617 const size_t idx = findIdx(key);
1618 return iterator{mKeyVals + idx, mInfo + idx};
1621 template <
typename OtherKey>
1622 iterator find(
const OtherKey& key, is_transparent_tag ) {
1623 ROBIN_HOOD_TRACE(
this);
1624 const size_t idx = findIdx(key);
1625 return iterator{mKeyVals + idx, mInfo + idx};
1629 ROBIN_HOOD_TRACE(
this);
1633 return iterator(mKeyVals, mInfo, fast_forward_tag{});
1635 const_iterator begin()
const {
1636 ROBIN_HOOD_TRACE(
this);
1639 const_iterator cbegin()
const {
1640 ROBIN_HOOD_TRACE(
this);
1644 return const_iterator(mKeyVals, mInfo, fast_forward_tag{});
1648 ROBIN_HOOD_TRACE(
this);
1651 return iterator{reinterpret_cast_no_cast_align_warning<Node*>(mInfo),
nullptr};
1653 const_iterator end()
const {
1654 ROBIN_HOOD_TRACE(
this);
1657 const_iterator cend()
const {
1658 ROBIN_HOOD_TRACE(
this);
1659 return const_iterator{reinterpret_cast_no_cast_align_warning<Node*>(mInfo),
nullptr};
1662 iterator erase(const_iterator pos) {
1663 ROBIN_HOOD_TRACE(
this);
1666 return erase(iterator{
const_cast<Node*
>(pos.mKeyVals),
const_cast<uint8_t*
>(pos.mInfo)});
1670 iterator erase(iterator pos) {
1671 ROBIN_HOOD_TRACE(
this);
1673 auto const idx =
static_cast<size_t>(pos.mKeyVals - mKeyVals);
1687 size_t erase(
const key_type& key) {
1688 ROBIN_HOOD_TRACE(
this);
1691 keyToIdx(key, &idx, &info);
1695 if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
1701 }
while (info <= mInfo[idx]);
1709 void rehash(
size_t c) {
1715 void reserve(
size_t c) {
1716 ROBIN_HOOD_TRACE(
this);
1717 auto const minElementsAllowed = (std::max)(c, mNumElements);
1718 auto newSize = InitialNumElements;
1719 while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) {
1722 if (ROBIN_HOOD_UNLIKELY(newSize == 0)) {
1723 throwOverflowError();
1726 rehashPowerOfTwo(newSize);
1729 size_type size() const noexcept {
1730 ROBIN_HOOD_TRACE(
this);
1731 return mNumElements;
1734 size_type max_size() const noexcept {
1735 ROBIN_HOOD_TRACE(
this);
1736 return static_cast<size_type
>(-1);
1739 ROBIN_HOOD(NODISCARD)
bool empty() const noexcept {
1740 ROBIN_HOOD_TRACE(
this);
1741 return 0 == mNumElements;
1744 float max_load_factor() const noexcept {
1745 ROBIN_HOOD_TRACE(
this);
1746 return MaxLoadFactor100 / 100.0F;
1750 float load_factor() const noexcept {
1751 ROBIN_HOOD_TRACE(
this);
1752 return static_cast<float>(size()) /
static_cast<float>(mMask + 1);
1755 ROBIN_HOOD(NODISCARD)
size_t mask() const noexcept {
1756 ROBIN_HOOD_TRACE(
this);
1760 ROBIN_HOOD(NODISCARD)
size_t calcMaxNumElementsAllowed(
size_t maxElements)
const noexcept {
1761 if (ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits<size_t>::max)() / 100)) {
1762 return maxElements * MaxLoadFactor100 / 100;
1766 return (maxElements / 100) * MaxLoadFactor100;
1769 ROBIN_HOOD(NODISCARD)
size_t calcNumBytesInfo(
size_t numElements)
const {
1770 return numElements +
sizeof(uint64_t);
1774 ROBIN_HOOD(NODISCARD)
size_t calcNumBytesTotal(
size_t numElements)
const {
1775 #if ROBIN_HOOD(BITNESS) == 64
1776 return numElements *
sizeof(Node) + calcNumBytesInfo(numElements);
1779 auto const ne =
static_cast<uint64_t
>(numElements);
1780 auto const s =
static_cast<uint64_t
>(
sizeof(Node));
1781 auto const infos =
static_cast<uint64_t
>(calcNumBytesInfo(numElements));
1783 auto const total64 = ne * s + infos;
1784 auto const total =
static_cast<size_t>(total64);
1786 if (ROBIN_HOOD_UNLIKELY(
static_cast<uint64_t
>(total) != total64)) {
1787 throwOverflowError();
1796 void rehashPowerOfTwo(
size_t numBuckets) {
1797 ROBIN_HOOD_TRACE(
this);
1799 Node*
const oldKeyVals = mKeyVals;
1800 uint8_t
const*
const oldInfo = mInfo;
1802 const size_t oldMaxElements = mMask + 1;
1805 init_data(numBuckets);
1806 if (oldMaxElements > 1) {
1807 for (
size_t i = 0; i < oldMaxElements; ++i) {
1808 if (oldInfo[i] != 0) {
1809 insert_move(std::move(oldKeyVals[i]));
1811 oldKeyVals[i].~Node();
1816 DataPool::addOrFree(oldKeyVals, calcNumBytesTotal(oldMaxElements));
1820 ROBIN_HOOD(NOINLINE)
void throwOverflowError()
const {
1821 #if ROBIN_HOOD(HAS_EXCEPTIONS)
1822 throw std::overflow_error(
"robin_hood::map overflow");
1828 void init_data(
size_t max_elements) {
1830 mMask = max_elements - 1;
1831 mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements);
1834 mKeyVals =
reinterpret_cast<Node*
>(
1835 detail::assertNotNull<std::bad_alloc>(calloc(1, calcNumBytesTotal(max_elements))));
1836 mInfo =
reinterpret_cast<uint8_t*
>(mKeyVals + max_elements);
1839 mInfo[max_elements] = 1;
1841 mInfoInc = InitialInfoInc;
1842 mInfoHashShift = InitialInfoHashShift;
1845 template <
typename Arg>
1846 mapped_type& doCreateByKey(Arg&& key) {
1850 keyToIdx(key, &idx, &info);
1851 nextWhileLess(&info, &idx);
1855 while (info == mInfo[idx]) {
1856 if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
1858 return mKeyVals[idx].getSecond();
1864 if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
1870 auto const insertion_idx = idx;
1871 auto const insertion_info = info;
1872 if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
1873 mMaxNumElementsAllowed = 0;
1877 while (0 != mInfo[idx]) {
1881 auto& l = mKeyVals[insertion_idx];
1882 if (idx == insertion_idx) {
1885 ::new (
static_cast<void*
>(&l))
1886 Node(*
this, std::piecewise_construct,
1887 std::forward_as_tuple(std::forward<Arg>(key)), std::forward_as_tuple());
1889 shiftUp(idx, insertion_idx);
1890 l = Node(*
this, std::piecewise_construct,
1891 std::forward_as_tuple(std::forward<Arg>(key)), std::forward_as_tuple());
1895 mInfo[insertion_idx] =
static_cast<uint8_t
>(insertion_info);
1898 return mKeyVals[insertion_idx].getSecond();
1903 template <
typename Arg>
1904 std::pair<iterator, bool> doInsert(Arg&& keyval) {
1908 keyToIdx(keyval.getFirst(), &idx, &info);
1909 nextWhileLess(&info, &idx);
1912 while (info == mInfo[idx]) {
1913 if (WKeyEqual::operator()(keyval.getFirst(), mKeyVals[idx].getFirst())) {
1916 return std::make_pair<iterator, bool>(iterator(mKeyVals + idx, mInfo + idx),
1923 if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
1929 auto const insertion_idx = idx;
1930 auto const insertion_info = info;
1931 if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
1932 mMaxNumElementsAllowed = 0;
1936 while (0 != mInfo[idx]) {
1940 auto& l = mKeyVals[insertion_idx];
1941 if (idx == insertion_idx) {
1942 ::new (
static_cast<void*
>(&l)) Node(*
this, std::forward<Arg>(keyval));
1944 shiftUp(idx, insertion_idx);
1945 l = Node(*
this, std::forward<Arg>(keyval));
1949 mInfo[insertion_idx] =
static_cast<uint8_t
>(insertion_info);
1952 return std::make_pair(iterator(mKeyVals + insertion_idx, mInfo + insertion_idx),
true);
1956 bool try_increase_info() {
1957 ROBIN_HOOD_LOG(
"mInfoInc=" << mInfoInc <<
", numElements=" << mNumElements
1958 <<
", maxNumElementsAllowed="
1959 << calcMaxNumElementsAllowed(mMask + 1));
1960 if (mInfoInc <= 2) {
1965 mInfoInc =
static_cast<uint8_t
>(mInfoInc >> 1U);
1970 auto const data = reinterpret_cast_no_cast_align_warning<uint64_t*>(mInfo);
1971 auto const numEntries = (mMask + 1) / 8;
1973 for (
size_t i = 0; i < numEntries; ++i) {
1974 data[i] = (data[i] >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f);
1976 mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
1980 void increase_size() {
1983 init_data(InitialNumElements);
1987 auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
1988 if (mNumElements < maxNumElementsAllowed && try_increase_info()) {
1992 ROBIN_HOOD_LOG(
"mNumElements=" << mNumElements <<
", maxNumElementsAllowed="
1993 << maxNumElementsAllowed <<
", load="
1994 << (
static_cast<double>(mNumElements) * 100.0 /
1995 (
static_cast<double>(mMask) + 1)));
1997 if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) {
1998 throwOverflowError();
2001 rehashPowerOfTwo((mMask + 1) * 2);
2010 Destroyer<Self, IsFlatMap && std::is_trivially_destructible<Node>::value>{}
2011 .nodesDoNotDeallocate(*
this);
2015 void init() noexcept {
2016 mKeyVals =
reinterpret_cast<Node*
>(&mMask);
2017 mInfo =
reinterpret_cast<uint8_t*
>(&mMask);
2020 mMaxNumElementsAllowed = 0;
2021 mInfoInc = InitialInfoInc;
2022 mInfoHashShift = InitialInfoHashShift;
2026 Node* mKeyVals =
reinterpret_cast<Node*
>(&mMask);
2027 uint8_t* mInfo =
reinterpret_cast<uint8_t*
>(&mMask);
2028 size_t mNumElements = 0;
2030 size_t mMaxNumElementsAllowed = 0;
2031 InfoType mInfoInc = InitialInfoInc;
2032 InfoType mInfoHashShift = InitialInfoHashShift;
2038 template <
typename Key,
typename T,
typename Hash = hash<Key>,
2039 typename KeyEqual = std::equal_to<Key>,
size_t MaxLoadFactor100 = 80>
2040 using unordered_flat_map = detail::unordered_map<true, MaxLoadFactor100, Key, T, Hash, KeyEqual>;
2042 template <
typename Key,
typename T,
typename Hash = hash<Key>,
2043 typename KeyEqual = std::equal_to<Key>,
size_t MaxLoadFactor100 = 80>
2044 using unordered_node_map = detail::unordered_map<false, MaxLoadFactor100, Key, T, Hash, KeyEqual>;
2046 template <
typename Key,
typename T,
typename Hash = hash<Key>,
2047 typename KeyEqual = std::equal_to<Key>,
size_t MaxLoadFactor100 = 80>
2048 using unordered_map =
2049 detail::unordered_map<
sizeof(robin_hood::pair<Key, T>) <=
sizeof(
size_t) * 6 &&
2050 std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
2051 std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
2052 MaxLoadFactor100, Key, T, Hash, KeyEqual>;