33 #ifndef ROBIN_HOOD_H_INCLUDED
34 #define ROBIN_HOOD_H_INCLUDED
37 #define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes
38 #define ROBIN_HOOD_VERSION_MINOR 11 // for adding functionality in a backwards-compatible manner
39 #define ROBIN_HOOD_VERSION_PATCH 1 // for backwards-compatible bug fixes
48 #include <type_traits>
50 #if __cplusplus >= 201703L
51 # include <string_view>
55 #ifdef ROBIN_HOOD_LOG_ENABLED
57 # define ROBIN_HOOD_LOG(...) \
58 std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl;
60 # define ROBIN_HOOD_LOG(x)
64 #ifdef ROBIN_HOOD_TRACE_ENABLED
66 # define ROBIN_HOOD_TRACE(...) \
67 std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl;
69 # define ROBIN_HOOD_TRACE(x)
73 #ifdef ROBIN_HOOD_COUNT_ENABLED
75 # define ROBIN_HOOD_COUNT(x) ++counts().x;
81 inline std::ostream& operator<<(std::ostream& os, Counts
const& c) {
82 return os << c.shiftUp <<
" shiftUp" << std::endl << c.shiftDown <<
" shiftDown" << std::endl;
85 static Counts& counts() {
86 static Counts counts{};
91 # define ROBIN_HOOD_COUNT(x)
96 #define ROBIN_HOOD(x) ROBIN_HOOD_PRIVATE_DEFINITION_##x()
99 #define ROBIN_HOOD_UNUSED(identifier)
102 #if SIZE_MAX == UINT32_MAX
103 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 32
104 #elif SIZE_MAX == UINT64_MAX
105 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 64
107 # error Unsupported bitness
112 # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() 1
113 # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() 0
115 # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() \
116 (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
117 # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
122 # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __declspec(noinline)
124 # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __attribute__((noinline))
128 #if !defined(__cpp_exceptions) && !defined(__EXCEPTIONS) && !defined(_CPPUNWIND)
129 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 0
131 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 1
135 #if !defined(ROBIN_HOOD_DISABLE_INTRINSICS)
137 # if ROBIN_HOOD(BITNESS) == 32
138 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward
140 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward64
143 # pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD))
144 # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \
145 [](size_t mask) noexcept -> int { \
146 unsigned long index; \
147 return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast<int>(index) \
148 : ROBIN_HOOD(BITNESS); \
151 # if ROBIN_HOOD(BITNESS) == 32
152 # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl
153 # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl
155 # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll
156 # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll
158 # define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS))
159 # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS))
164 #ifndef __has_cpp_attribute // For backwards compatibility
165 # define __has_cpp_attribute(x) 0
167 #if __has_cpp_attribute(clang::fallthrough)
168 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[clang::fallthrough]]
169 #elif __has_cpp_attribute(gnu::fallthrough)
170 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[gnu::fallthrough]]
172 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH()
177 # define ROBIN_HOOD_LIKELY(condition) condition
178 # define ROBIN_HOOD_UNLIKELY(condition) condition
180 # define ROBIN_HOOD_LIKELY(condition) __builtin_expect(condition, 1)
181 # define ROBIN_HOOD_UNLIKELY(condition) __builtin_expect(condition, 0)
186 # ifdef _NATIVE_WCHAR_T_DEFINED
187 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1
189 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 0
192 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1
197 # if _MSC_VER <= 1900
198 # define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 1
200 # define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 0
203 # define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 0
208 #if defined(__GNUC__) && __GNUC__ < 5
209 # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__)
211 # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value
215 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX() __cplusplus
216 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX98() 199711L
217 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX11() 201103L
218 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX14() 201402L
219 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX17() 201703L
221 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17)
222 # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() [[nodiscard]]
224 # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD()
229 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14)
230 # define ROBIN_HOOD_STD std
234 namespace ROBIN_HOOD_STD {
237 : std::integral_constant<std::size_t, alignof(typename std::remove_all_extents<T>::type)> {};
239 template <
class T, T... Ints>
243 static_assert(std::is_integral<value_type>::value,
"not integral type");
244 static constexpr std::size_t
size() noexcept {
245 return sizeof...(Ints);
248 template <std::size_t... Inds>
252 template <
class T, T Begin, T End,
bool>
255 static_assert(std::is_integral<TValue>::value,
"not integral type");
256 static_assert(Begin >= 0 && Begin < End,
"unexpected argument (Begin<0 || Begin<=End)");
258 template <
class,
class>
273 template <
class T, T Begin>
276 static_assert(std::is_integral<TValue>::value,
"not integral type");
277 static_assert(Begin >= 0,
"unexpected argument (Begin<0)");
281 template <
class T, T Begin, T End>
284 static_assert(std::is_integral<TValue>::value,
"not integral type");
285 static_assert(Begin >= 0,
"unexpected argument (Begin<0)");
290 template <
class T, T N>
293 template <std::
size_t N>
296 template <
class... T>
306 #if ROBIN_HOOD(BITNESS) == 64
307 using SizeT = uint64_t;
312 template <
typename T>
314 return (x >> k) | (x << (8U *
sizeof(T) - k));
320 template <
typename T>
322 return reinterpret_cast<T
>(ptr);
325 template <
typename T>
327 return reinterpret_cast<T
>(ptr);
332 template <
typename E,
typename... Args>
334 #if ROBIN_HOOD(HAS_EXCEPTIONS)
335 void doThrow(Args&&... args) {
337 throw E(std::forward<Args>(args)...);
345 template <
typename E,
typename T,
typename... Args>
348 doThrow<E>(std::forward<Args>(args)...);
353 template <
typename T>
358 std::memcpy(&t, ptr,
sizeof(T));
365 template <
typename T,
size_t MinNumAllocs = 4,
size_t MaxNumAllocs = 256>
373 , mListForFree(
nullptr) {}
377 , mListForFree(o.mListForFree) {
378 o.mListForFree =
nullptr;
385 mListForFree = o.mListForFree;
386 o.mListForFree =
nullptr;
404 while (mListForFree) {
405 T* tmp = *mListForFree;
407 std::free(mListForFree);
408 mListForFree = reinterpret_cast_no_cast_align_warning<T**>(tmp);
419 tmp = performAllocation();
422 mHead = *reinterpret_cast_no_cast_align_warning<T**>(tmp);
431 *reinterpret_cast_no_cast_align_warning<T**>(obj) = mHead;
438 void addOrFree(
void* ptr,
const size_t numBytes) noexcept {
440 if (numBytes < ALIGNMENT + ALIGNED_SIZE) {
452 swap(mHead, other.mHead);
453 swap(mListForFree, other.mListForFree);
461 ROBIN_HOOD(NODISCARD)
size_t calcNumElementsToAlloc() const noexcept {
462 auto tmp = mListForFree;
463 size_t numAllocs = MinNumAllocs;
465 while (numAllocs * 2 <= MaxNumAllocs && tmp) {
466 auto x =
reinterpret_cast<T***
>(tmp);
475 void add(
void* ptr,
const size_t numBytes) noexcept {
476 const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE;
478 auto data =
reinterpret_cast<T**
>(ptr);
481 auto x =
reinterpret_cast<T***
>(data);
487 reinterpret_cast_no_cast_align_warning<T*>(
reinterpret_cast<char*
>(ptr) + ALIGNMENT);
489 auto*
const head =
reinterpret_cast<char*
>(headT);
492 for (
size_t i = 0; i < numElements; ++i) {
493 *reinterpret_cast_no_cast_align_warning<char**>(head + i * ALIGNED_SIZE) =
494 head + (i + 1) * ALIGNED_SIZE;
498 *reinterpret_cast_no_cast_align_warning<T**>(head + (numElements - 1) * ALIGNED_SIZE) =
505 ROBIN_HOOD(NOINLINE) T* performAllocation() {
506 size_t const numElementsToAlloc = calcNumElementsToAlloc();
509 size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc;
510 ROBIN_HOOD_LOG(
"std::malloc " << bytes <<
" = " << ALIGNMENT <<
" + " << ALIGNED_SIZE
511 <<
" * " << numElementsToAlloc)
512 add(assertNotNull<std::bad_alloc>(std::malloc(bytes)), bytes);
517 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14)
518 static constexpr
size_t ALIGNMENT =
519 (std::max)(std::alignment_of<T>::value, std::alignment_of<T*>::value);
521 static const size_t ALIGNMENT =
522 (ROBIN_HOOD_STD::alignment_of<T>::value > ROBIN_HOOD_STD::alignment_of<T*>::value)
523 ? ROBIN_HOOD_STD::alignment_of<T>::value
524 : +ROBIN_HOOD_STD::alignment_of<T*>::value;
527 static constexpr
size_t ALIGNED_SIZE = ((
sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT;
529 static_assert(MinNumAllocs >= 1,
"MinNumAllocs");
530 static_assert(MaxNumAllocs >= MinNumAllocs,
"MaxNumAllocs");
531 static_assert(ALIGNED_SIZE >=
sizeof(T*),
"ALIGNED_SIZE");
532 static_assert(0 == (ALIGNED_SIZE %
sizeof(T*)),
"ALIGNED_SIZE mod");
533 static_assert(ALIGNMENT >=
sizeof(T*),
"ALIGNMENT");
536 T** mListForFree{
nullptr};
539 template <
typename T,
size_t MinSize,
size_t MaxSize,
bool IsFlat>
543 template <
typename T,
size_t MinSize,
size_t MaxSize>
553 template <
typename T,
size_t MinSize,
size_t MaxSize>
558 namespace swappable {
559 #if ROBIN_HOOD(CXX) < ROBIN_HOOD(CXX17)
561 template <
typename T>
563 static const bool value = noexcept(
swap(std::declval<T&>(), std::declval<T&>()));
566 template <
typename T>
568 static const bool value = std::is_nothrow_swappable<T>::value;
580 template <
typename T1,
typename T2>
585 template <
typename U1 = T1,
typename U2 = T2,
586 typename =
typename std::enable_if<std::is_default_constructible<U1>::value &&
587 std::is_default_constructible<U2>::value>::type>
588 constexpr
pair() noexcept(noexcept(U1()) && noexcept(U2()))
593 explicit constexpr
pair(std::pair<T1, T2>
const& o) noexcept(
594 noexcept(T1(std::declval<T1 const&>())) && noexcept(T2(std::declval<T2 const&>())))
599 explicit constexpr
pair(std::pair<T1, T2>&& o) noexcept(noexcept(
600 T1(std::move(std::declval<T1&&>()))) && noexcept(T2(std::move(std::declval<T2&&>()))))
604 constexpr
pair(T1&& a, T2&& b) noexcept(noexcept(
605 T1(std::move(std::declval<T1&&>()))) && noexcept(T2(std::move(std::declval<T2&&>()))))
606 :
first(std::move(a))
609 template <
typename U1,
typename U2>
610 constexpr
pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward<U1>(
611 std::declval<U1&&>()))) && noexcept(T2(std::forward<U2>(std::declval<U2&&>()))))
612 :
first(std::forward<U1>(a))
613 ,
second(std::forward<U2>(b)) {}
615 template <
typename... U1,
typename... U2>
618 #if !ROBIN_HOOD(BROKEN_CONSTEXPR)
621 pair(std::piecewise_construct_t , std::tuple<U1...> a,
623 b) noexcept(noexcept(
pair(std::declval<std::tuple<U1...>&>(),
624 std::declval<std::tuple<U2...>&>(),
632 template <
typename... U1,
size_t... I1,
typename... U2,
size_t... I2>
634 noexcept(T1(std::forward<U1>(std::get<I1>(
635 std::declval<std::tuple<
636 U1...>&>()))...)) && noexcept(T2(std::
637 forward<U2>(std::get<I2>(
638 std::declval<std::tuple<U2...>&>()))...)))
639 :
first(std::forward<U1>(std::get<I1>(a))...)
640 ,
second(std::forward<U2>(std::get<I2>(b))...) {
658 template <
typename A,
typename B>
664 template <
typename A,
typename B>
668 template <
typename A,
typename B>
672 template <
typename A,
typename B>
674 std::declval<A const&>() < std::declval<A const&>()) && noexcept(std::declval<B const&>() <
675 std::declval<B const&>())) {
676 return x.first < y.first || (!(y.first < x.first) && x.second < y.second);
678 template <
typename A,
typename B>
682 template <
typename A,
typename B>
686 template <
typename A,
typename B>
691 inline size_t hash_bytes(
void const* ptr,
size_t len) noexcept {
692 static constexpr uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
693 static constexpr uint64_t seed = UINT64_C(0xe17a1465);
694 static constexpr
unsigned int r = 47;
696 auto const*
const data64 =
static_cast<uint64_t const*
>(ptr);
697 uint64_t h = seed ^ (len * m);
699 size_t const n_blocks = len / 8;
700 for (
size_t i = 0; i < n_blocks; ++i) {
701 auto k = detail::unaligned_load<uint64_t>(data64 + i);
711 auto const*
const data8 =
reinterpret_cast<uint8_t const*
>(data64 + n_blocks);
714 h ^=
static_cast<uint64_t
>(data8[6]) << 48U;
717 h ^=
static_cast<uint64_t
>(data8[5]) << 40U;
720 h ^=
static_cast<uint64_t
>(data8[4]) << 32U;
723 h ^=
static_cast<uint64_t
>(data8[3]) << 24U;
726 h ^=
static_cast<uint64_t
>(data8[2]) << 16U;
729 h ^=
static_cast<uint64_t
>(data8[1]) << 8U;
732 h ^=
static_cast<uint64_t
>(data8[0]);
744 return static_cast<size_t>(h);
751 x *= UINT64_C(0xff51afd7ed558ccd);
757 return static_cast<size_t>(x);
761 template <
typename T,
typename Enable =
void>
762 struct hash :
public std::hash<T> {
764 noexcept(noexcept(std::declval<std::hash<T>>().
operator()(std::declval<T const&>()))) {
766 auto result = std::hash<T>::operator()(obj);
772 template <
typename CharT>
773 struct hash<std::basic_string<CharT>> {
774 size_t operator()(std::basic_string<CharT>
const& str)
const noexcept {
775 return hash_bytes(str.data(),
sizeof(CharT) * str.size());
779 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17)
780 template <
typename CharT>
781 struct hash<std::basic_string_view<CharT>> {
782 size_t operator()(std::basic_string_view<CharT>
const& sv)
const noexcept {
783 return hash_bytes(sv.data(),
sizeof(CharT) * sv.size());
796 struct hash<std::unique_ptr<T>> {
797 size_t operator()(std::unique_ptr<T>
const& ptr)
const noexcept {
803 struct hash<std::shared_ptr<T>> {
804 size_t operator()(std::shared_ptr<T>
const& ptr)
const noexcept {
809 template <
typename Enum>
810 struct hash<Enum, typename std::enable_if<std::is_enum<Enum>::value>::type> {
812 using Underlying =
typename std::underlying_type<Enum>::type;
817 #define ROBIN_HOOD_HASH_INT(T) \
820 size_t operator()(T const& obj) const noexcept { \
821 return hash_int(static_cast<uint64_t>(obj)); \
825 #if defined(__GNUC__) && !defined(__clang__)
826 # pragma GCC diagnostic push
827 # pragma GCC diagnostic ignored "-Wuseless-cast"
836 #if ROBIN_HOOD(HAS_NATIVE_WCHART)
847 #if defined(__GNUC__) && !defined(__clang__)
848 # pragma GCC diagnostic pop
852 template <
typename T>
857 template <
typename T,
typename =
void>
860 template <
typename T>
862 :
public std::true_type {};
866 template <
typename T>
869 explicit WrapHash(T
const& o) noexcept(noexcept(T(std::declval<T const&>())))
873 template <
typename T>
876 explicit WrapKeyEqual(T
const& o) noexcept(noexcept(T(std::declval<T const&>())))
906 template <
bool IsFlat,
size_t MaxLoadFactor100,
typename Key,
typename T,
typename Hash,
912 typename std::conditional<
913 std::is_void<T>::value, Key,
914 robin_hood::pair<typename std::conditional<IsFlat, Key, Key const>::type, T>>::type,
918 static constexpr
bool is_map = !std::is_void<T>::value;
934 static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100,
935 "MaxLoadFactor100 needs to be >10 && < 100");
943 static constexpr
size_t InitialNumElements =
sizeof(uint64_t);
944 static constexpr uint32_t InitialInfoNumBits = 5;
945 static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits;
946 static constexpr
size_t InfoMask = InitialInfoInc - 1U;
947 static constexpr uint8_t InitialInfoHashShift = 0;
951 using InfoType = uint32_t;
958 template <
typename M,
bool>
962 template <
typename M>
963 class DataNode<M, true> final {
965 template <
typename... Args>
967 noexcept(
value_type(std::forward<Args>(args)...)))
968 : mData(std::forward<Args>(args)...) {}
971 std::is_nothrow_move_constructible<value_type>::value)
972 : mData(std::move(n.mData)) {}
976 void destroyDoNotDeallocate() noexcept {}
978 value_type const* operator->() const noexcept {
985 const value_type& operator*() const noexcept {
993 template <
typename VT = value_type>
995 typename std::enable_if<is_map, typename VT::first_type&>::type getFirst() noexcept {
998 template <
typename VT = value_type>
1000 typename std::enable_if<is_set, VT&>::type getFirst() noexcept {
1004 template <
typename VT = value_type>
1006 typename std::enable_if<is_map, typename VT::first_type const&>::type
1007 getFirst() const noexcept {
1010 template <
typename VT = value_type>
1012 typename std::enable_if<is_set, VT const&>::type getFirst() const noexcept {
1016 template <
typename MT = mapped_type>
1018 typename std::enable_if<is_map, MT&>::type getSecond() noexcept {
1019 return mData.second;
1022 template <
typename MT = mapped_type>
1024 typename std::enable_if<is_set, MT const&>::type getSecond() const noexcept {
1025 return mData.second;
1028 void swap(DataNode<M, true>& o) noexcept(
1029 noexcept(std::declval<value_type>().
swap(std::declval<value_type>()))) {
1030 mData.swap(o.mData);
1038 template <
typename M>
1039 class DataNode<M, false> {
1041 template <
typename... Args>
1042 explicit DataNode(M& map, Args&&... args)
1043 : mData(map.allocate()) {
1044 ::new (
static_cast<void*
>(mData))
value_type(std::forward<Args>(args)...);
1048 : mData(std::move(n.mData)) {}
1050 void destroy(M& map) noexcept {
1052 mData->~value_type();
1053 map.deallocate(mData);
1056 void destroyDoNotDeallocate() noexcept {
1057 mData->~value_type();
1060 value_type const* operator->() const noexcept {
1076 template <
typename VT = value_type>
1078 typename std::enable_if<is_map, typename VT::first_type&>::type getFirst() noexcept {
1079 return mData->first;
1081 template <
typename VT = value_type>
1083 typename std::enable_if<is_set, VT&>::type getFirst() noexcept {
1087 template <
typename VT = value_type>
1089 typename std::enable_if<is_map, typename VT::first_type const&>::type
1090 getFirst() const noexcept {
1091 return mData->first;
1093 template <
typename VT = value_type>
1095 typename std::enable_if<is_set, VT const&>::type getFirst() const noexcept {
1099 template <
typename MT = mapped_type>
1101 typename std::enable_if<is_map, MT&>::type getSecond() noexcept {
1102 return mData->second;
1105 template <
typename MT = mapped_type>
1107 typename std::enable_if<is_map, MT const&>::type getSecond() const noexcept {
1108 return mData->second;
1111 void swap(DataNode<M, false>& o) noexcept {
1113 swap(mData, o.mData);
1120 using Node = DataNode<Self, IsFlat>;
1123 ROBIN_HOOD(NODISCARD)
key_type const& getFirstConst(Node
const& n)
const noexcept {
1124 return n.getFirst();
1129 ROBIN_HOOD(NODISCARD)
key_type const& getFirstConst(
key_type const& k)
const noexcept {
1134 template <
typename Q = mapped_type>
1135 ROBIN_HOOD(NODISCARD)
1136 typename std::enable_if<!std::is_void<Q>::value,
key_type const&>::type
1137 getFirstConst(
value_type const& vt)
const noexcept {
1143 template <
typename M,
bool UseMemcpy>
1147 template <
typename M>
1148 struct Cloner<M, true> {
1149 void operator()(M
const& source, M& target)
const {
1150 auto const*
const src =
reinterpret_cast<char const*
>(source.mKeyVals);
1151 auto* tgt =
reinterpret_cast<char*
>(target.mKeyVals);
1152 auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1);
1153 std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt);
1157 template <
typename M>
1158 struct Cloner<M, false> {
1159 void operator()(M
const& s, M& t)
const {
1160 auto const numElementsWithBuffer = t.calcNumElementsWithBuffer(t.mMask + 1);
1161 std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(numElementsWithBuffer), t.mInfo);
1163 for (
size_t i = 0; i < numElementsWithBuffer; ++i) {
1165 ::new (
static_cast<void*
>(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]);
1173 template <
typename M,
bool IsFlatAndTrivial>
1174 struct Destroyer {};
1176 template <
typename M>
1177 struct Destroyer<M, true> {
1178 void nodes(M& m)
const noexcept {
1182 void nodesDoNotDeallocate(M& m)
const noexcept {
1187 template <
typename M>
1188 struct Destroyer<M, false> {
1189 void nodes(M& m)
const noexcept {
1192 auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1);
1194 for (
size_t idx = 0; idx < numElementsWithBuffer; ++idx) {
1195 if (0 != m.mInfo[idx]) {
1196 Node& n = m.mKeyVals[idx];
1203 void nodesDoNotDeallocate(M& m)
const noexcept {
1206 auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1);
1207 for (
size_t idx = 0; idx < numElementsWithBuffer; ++idx) {
1208 if (0 != m.mInfo[idx]) {
1209 Node& n = m.mKeyVals[idx];
1210 n.destroyDoNotDeallocate();
1219 struct fast_forward_tag {};
1222 template <
bool IsConst>
1226 using NodePtr =
typename std::conditional<IsConst, Node const*, Node*>::type;
1229 using difference_type = std::ptrdiff_t;
1231 using reference =
typename std::conditional<IsConst, value_type const&, value_type&>::type;
1232 using pointer =
typename std::conditional<IsConst, value_type const*, value_type*>::type;
1233 using iterator_category = std::forward_iterator_tag;
1243 template <
bool OtherIsConst,
1244 typename =
typename std::enable_if<IsConst && !OtherIsConst>::type>
1246 Iter(Iter<OtherIsConst>
const& other) noexcept
1247 : mKeyVals(other.mKeyVals)
1248 , mInfo(other.mInfo) {}
1250 Iter(NodePtr valPtr, uint8_t
const* infoPtr) noexcept
1254 Iter(NodePtr valPtr, uint8_t
const* infoPtr,
1261 template <
bool OtherIsConst,
1262 typename =
typename std::enable_if<IsConst && !OtherIsConst>::type>
1263 Iter&
operator=(Iter<OtherIsConst>
const& other) noexcept {
1264 mKeyVals = other.mKeyVals;
1265 mInfo = other.mInfo;
1270 Iter& operator++() noexcept {
1277 Iter operator++(
int) noexcept {
1283 reference operator*()
const {
1287 pointer operator->()
const {
1292 bool operator==(Iter<O>
const& o)
const noexcept {
1293 return mKeyVals == o.mKeyVals;
1297 bool operator!=(Iter<O>
const& o)
const noexcept {
1298 return mKeyVals != o.mKeyVals;
1305 void fastForward() noexcept {
1307 while (0U == (n = detail::unaligned_load<size_t>(mInfo))) {
1308 mInfo +=
sizeof(size_t);
1309 mKeyVals +=
sizeof(size_t);
1311 #if defined(ROBIN_HOOD_DISABLE_INTRINSICS)
1326 # if ROBIN_HOOD(LITTLE_ENDIAN)
1337 NodePtr mKeyVals{
nullptr};
1338 uint8_t
const* mInfo{
nullptr};
1346 template <
typename HashKey>
1347 void keyToIdx(HashKey&& key,
size_t* idx, InfoType* info)
const {
1351 auto h =
static_cast<uint64_t
>(WHash::operator()(key));
1353 h *= mHashMultiplier;
1357 *info = mInfoInc +
static_cast<InfoType
>((h & InfoMask) >> mInfoHashShift);
1358 *idx = (
static_cast<size_t>(h) >> InitialInfoNumBits) & mMask;
1362 void next(InfoType* info,
size_t* idx)
const noexcept {
1367 void nextWhileLess(InfoType* info,
size_t* idx)
const noexcept {
1369 while (*info < mInfo[*idx]) {
1376 shiftUp(
size_t startIdx,
1377 size_t const insertion_idx) noexcept(std::is_nothrow_move_assignable<Node>::value) {
1378 auto idx = startIdx;
1379 ::new (
static_cast<void*
>(mKeyVals + idx)) Node(std::move(mKeyVals[idx - 1]));
1380 while (--idx != insertion_idx) {
1381 mKeyVals[idx] = std::move(mKeyVals[idx - 1]);
1385 while (idx != insertion_idx) {
1387 mInfo[idx] =
static_cast<uint8_t
>(mInfo[idx - 1] + mInfoInc);
1389 mMaxNumElementsAllowed = 0;
1395 void shiftDown(
size_t idx) noexcept(std::is_nothrow_move_assignable<Node>::value) {
1399 mKeyVals[idx].destroy(*
this);
1402 while (mInfo[idx + 1] >= 2 * mInfoInc) {
1404 mInfo[idx] =
static_cast<uint8_t
>(mInfo[idx + 1] - mInfoInc);
1405 mKeyVals[idx] = std::move(mKeyVals[idx + 1]);
1412 mKeyVals[idx].~Node();
1416 template <
typename Other>
1418 size_t findIdx(Other
const& key)
const {
1421 keyToIdx(key, &idx, &info);
1425 if (info == mInfo[idx] &&
1430 if (info == mInfo[idx] &&
1435 }
while (info <= mInfo[idx]);
1438 return mMask == 0 ? 0
1439 :
static_cast<size_t>(std::distance(
1440 mKeyVals, reinterpret_cast_no_cast_align_warning<Node*>(mInfo)));
1443 void cloneData(
const Table& o) {
1444 Cloner<Table, IsFlat && ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(Node)>()(o, *
this);
1449 void insert_move(Node&& keyval) {
1452 if (0 == mMaxNumElementsAllowed && !try_increase_info()) {
1453 throwOverflowError();
1458 keyToIdx(keyval.getFirst(), &idx, &info);
1461 while (info <= mInfo[idx]) {
1467 auto const insertion_idx = idx;
1468 auto const insertion_info =
static_cast<uint8_t
>(info);
1470 mMaxNumElementsAllowed = 0;
1474 while (0 != mInfo[idx]) {
1478 auto& l = mKeyVals[insertion_idx];
1479 if (idx == insertion_idx) {
1480 ::new (
static_cast<void*
>(&l)) Node(std::move(keyval));
1482 shiftUp(idx, insertion_idx);
1483 l = std::move(keyval);
1487 mInfo[insertion_idx] = insertion_info;
1496 Table() noexcept(noexcept(Hash()) && noexcept(KeyEqual()))
1509 const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && noexcept(KeyEqual(equal)))
1511 , WKeyEqual(equal) {
1515 template <
typename Iter>
1517 const Hash& h = Hash{},
const KeyEqual& equal = KeyEqual{})
1519 , WKeyEqual(equal) {
1526 const KeyEqual& equal = KeyEqual{})
1528 , WKeyEqual(equal) {
1539 mHashMultiplier = std::move(o.mHashMultiplier);
1540 mKeyVals = std::move(o.mKeyVals);
1541 mInfo = std::move(o.mInfo);
1542 mNumElements = std::move(o.mNumElements);
1543 mMask = std::move(o.mMask);
1544 mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed);
1545 mInfoInc = std::move(o.mInfoInc);
1546 mInfoHashShift = std::move(o.mInfoHashShift);
1558 mHashMultiplier = std::move(o.mHashMultiplier);
1559 mKeyVals = std::move(o.mKeyVals);
1560 mInfo = std::move(o.mInfo);
1561 mNumElements = std::move(o.mNumElements);
1562 mMask = std::move(o.mMask);
1563 mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed);
1564 mInfoInc = std::move(o.mInfoInc);
1565 mInfoHashShift = std::move(o.mInfoHashShift);
1566 WHash::operator=(std::move(
static_cast<WHash&
>(o)));
1567 WKeyEqual::operator=(std::move(
static_cast<WKeyEqual&
>(o)));
1568 DataPool::operator=(std::move(
static_cast<DataPool&
>(o)));
1590 auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer);
1592 ROBIN_HOOD_LOG(
"std::malloc " << numBytesTotal <<
" = calcNumBytesTotal("
1593 << numElementsWithBuffer <<
")")
1594 mHashMultiplier = o.mHashMultiplier;
1595 mKeyVals =
static_cast<Node*
>(
1596 detail::assertNotNull<std::bad_alloc>(std::malloc(numBytesTotal)));
1598 mInfo =
reinterpret_cast<uint8_t*
>(mKeyVals + numElementsWithBuffer);
1599 mNumElements = o.mNumElements;
1601 mMaxNumElementsAllowed = o.mMaxNumElementsAllowed;
1602 mInfoInc = o.mInfoInc;
1603 mInfoHashShift = o.mInfoHashShift;
1630 WHash::operator=(
static_cast<const WHash&
>(o));
1631 WKeyEqual::operator=(
static_cast<const WKeyEqual&
>(o));
1632 DataPool::operator=(
static_cast<DataPool const&
>(o));
1638 Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::value>{}.nodes(*
this);
1640 if (mMask != o.mMask) {
1645 std::free(mKeyVals);
1649 auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer);
1650 ROBIN_HOOD_LOG(
"std::malloc " << numBytesTotal <<
" = calcNumBytesTotal("
1651 << numElementsWithBuffer <<
")")
1652 mKeyVals =
static_cast<Node*
>(
1653 detail::assertNotNull<std::bad_alloc>(std::malloc(numBytesTotal)));
1656 mInfo =
reinterpret_cast<uint8_t*
>(mKeyVals + numElementsWithBuffer);
1659 WHash::operator=(
static_cast<const WHash&
>(o));
1660 WKeyEqual::operator=(
static_cast<const WKeyEqual&
>(o));
1661 DataPool::operator=(
static_cast<DataPool const&
>(o));
1662 mHashMultiplier = o.mHashMultiplier;
1663 mNumElements = o.mNumElements;
1665 mMaxNumElementsAllowed = o.mMaxNumElementsAllowed;
1666 mInfoInc = o.mInfoInc;
1667 mInfoHashShift = o.mInfoHashShift;
1689 Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::value>{}.nodes(*
this);
1693 uint8_t
const z = 0;
1694 std::fill(mInfo, mInfo + calcNumBytesInfo(numElementsWithBuffer), z);
1695 mInfo[numElementsWithBuffer] = 1;
1697 mInfoInc = InitialInfoInc;
1698 mInfoHashShift = InitialInfoHashShift;
1713 for (
auto const& otherEntry : other) {
1714 if (!has(otherEntry)) {
1727 template <
typename Q = mapped_type>
1730 auto idxAndState = insertKeyPrepareEmptySpot(key);
1731 switch (idxAndState.second) {
1732 case InsertionState::key_found:
1735 case InsertionState::new_node:
1736 ::new (
static_cast<void*
>(&mKeyVals[idxAndState.first]))
1737 Node(*
this, std::piecewise_construct, std::forward_as_tuple(key),
1738 std::forward_as_tuple());
1741 case InsertionState::overwrite_node:
1742 mKeyVals[idxAndState.first] = Node(*
this, std::piecewise_construct,
1743 std::forward_as_tuple(key), std::forward_as_tuple());
1746 case InsertionState::overflow_error:
1747 throwOverflowError();
1750 return mKeyVals[idxAndState.first].getSecond();
1753 template <
typename Q = mapped_type>
1756 auto idxAndState = insertKeyPrepareEmptySpot(key);
1757 switch (idxAndState.second) {
1758 case InsertionState::key_found:
1761 case InsertionState::new_node:
1762 ::new (
static_cast<void*
>(&mKeyVals[idxAndState.first]))
1763 Node(*
this, std::piecewise_construct, std::forward_as_tuple(std::move(key)),
1764 std::forward_as_tuple());
1767 case InsertionState::overwrite_node:
1768 mKeyVals[idxAndState.first] =
1769 Node(*
this, std::piecewise_construct, std::forward_as_tuple(std::move(key)),
1770 std::forward_as_tuple());
1773 case InsertionState::overflow_error:
1774 throwOverflowError();
1777 return mKeyVals[idxAndState.first].getSecond();
1780 template <
typename Iter>
1782 for (; first != last; ++first) {
1788 void insert(std::initializer_list<value_type> ilist) {
1789 for (
auto&& vt : ilist) {
1794 template <
typename... Args>
1795 std::pair<iterator, bool>
emplace(Args&&... args) {
1797 Node n{*
this, std::forward<Args>(args)...};
1798 auto idxAndState = insertKeyPrepareEmptySpot(getFirstConst(n));
1799 switch (idxAndState.second) {
1800 case InsertionState::key_found:
1804 case InsertionState::new_node:
1805 ::new (
static_cast<void*
>(&mKeyVals[idxAndState.first])) Node(*
this, std::move(n));
1808 case InsertionState::overwrite_node:
1809 mKeyVals[idxAndState.first] = std::move(n);
1812 case InsertionState::overflow_error:
1814 throwOverflowError();
1818 return std::make_pair(
iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first),
1819 InsertionState::key_found != idxAndState.second);
1822 template <
typename... Args>
1824 return try_emplace_impl(key, std::forward<Args>(args)...);
1827 template <
typename... Args>
1829 return try_emplace_impl(std::move(key), std::forward<Args>(args)...);
1832 template <
typename... Args>
1836 return try_emplace_impl(key, std::forward<Args>(args)...);
1839 template <
typename... Args>
1842 return try_emplace_impl(std::move(key), std::forward<Args>(args)...);
1845 template <
typename Mapped>
1847 return insertOrAssignImpl(key, std::forward<Mapped>(obj));
1850 template <
typename Mapped>
1852 return insertOrAssignImpl(std::move(key), std::forward<Mapped>(obj));
1855 template <
typename Mapped>
1859 return insertOrAssignImpl(key, std::forward<Mapped>(obj));
1862 template <
typename Mapped>
1865 return insertOrAssignImpl(std::move(key), std::forward<Mapped>(obj));
1874 return emplace(std::move(keyval));
1880 auto kv = mKeyVals + findIdx(key);
1881 if (kv != reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1887 template <
typename OtherKey,
typename Self_ = Self>
1889 typename std::enable_if<Self_::is_transparent, size_t>::type
count(
const OtherKey& key)
const {
1891 auto kv = mKeyVals + findIdx(key);
1892 if (kv != reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1899 return 1U ==
count(key);
1902 template <
typename OtherKey,
typename Self_ = Self>
1904 typename std::enable_if<Self_::is_transparent, bool>::type
contains(
const OtherKey& key)
const {
1905 return 1U ==
count(key);
1910 template <
typename Q = mapped_type>
1912 typename std::enable_if<!std::is_void<Q>::value, Q&>::type
at(
key_type const& key) {
1914 auto kv = mKeyVals + findIdx(key);
1915 if (kv == reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1916 doThrow<std::out_of_range>(
"key not found");
1918 return kv->getSecond();
1923 template <
typename Q = mapped_type>
1925 typename std::enable_if<!std::is_void<Q>::value, Q
const&>::type
at(
key_type const& key)
const {
1927 auto kv = mKeyVals + findIdx(key);
1928 if (kv == reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
1929 doThrow<std::out_of_range>(
"key not found");
1931 return kv->getSecond();
1936 const size_t idx = findIdx(key);
1940 template <
typename OtherKey>
1943 const size_t idx = findIdx(key);
1947 template <
typename OtherKey,
typename Self_ = Self>
1948 typename std::enable_if<Self_::is_transparent,
1952 const size_t idx = findIdx(key);
1958 const size_t idx = findIdx(key);
1959 return iterator{mKeyVals + idx, mInfo + idx};
1962 template <
typename OtherKey>
1965 const size_t idx = findIdx(key);
1966 return iterator{mKeyVals + idx, mInfo + idx};
1969 template <
typename OtherKey,
typename Self_ = Self>
1970 typename std::enable_if<Self_::is_transparent, iterator>::type
find(
const OtherKey& key) {
1972 const size_t idx = findIdx(key);
1973 return iterator{mKeyVals + idx, mInfo + idx};
1981 return iterator(mKeyVals, mInfo, fast_forward_tag{});
1999 return iterator{reinterpret_cast_no_cast_align_warning<Node*>(mInfo),
nullptr};
2007 return const_iterator{reinterpret_cast_no_cast_align_warning<Node*>(mInfo),
nullptr};
2014 return erase(
iterator{
const_cast<Node*
>(pos.mKeyVals),
const_cast<uint8_t*
>(pos.mInfo)});
2021 auto const idx =
static_cast<size_t>(pos.mKeyVals - mKeyVals);
2039 keyToIdx(key, &idx, &info);
2043 if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
2049 }
while (info <= mInfo[idx]);
2073 auto newSize = InitialNumElements;
2074 while (calcMaxNumElementsAllowed(newSize) < mNumElements && newSize != 0) {
2078 throwOverflowError();
2081 ROBIN_HOOD_LOG(
"newSize > mMask + 1: " << newSize <<
" > " << mMask <<
" + 1")
2085 if (newSize < mMask + 1) {
2086 rehashPowerOfTwo(newSize,
true);
2092 return mNumElements;
2102 return 0 == mNumElements;
2107 return MaxLoadFactor100 / 100.0F;
2113 return static_cast<float>(
size()) /
static_cast<float>(mMask + 1);
2121 ROBIN_HOOD(NODISCARD)
size_t calcMaxNumElementsAllowed(
size_t maxElements)
const noexcept {
2122 if (
ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits<size_t>::max)() / 100)) {
2123 return maxElements * MaxLoadFactor100 / 100;
2127 return (maxElements / 100) * MaxLoadFactor100;
2130 ROBIN_HOOD(NODISCARD)
size_t calcNumBytesInfo(
size_t numElements)
const noexcept {
2133 return numElements +
sizeof(uint64_t);
2138 auto maxNumElementsAllowed = calcMaxNumElementsAllowed(numElements);
2139 return numElements + (std::min)(maxNumElementsAllowed, (
static_cast<size_t>(0xFF)));
2143 ROBIN_HOOD(NODISCARD)
size_t calcNumBytesTotal(
size_t numElements)
const {
2144 #if ROBIN_HOOD(BITNESS) == 64
2145 return numElements *
sizeof(Node) + calcNumBytesInfo(numElements);
2148 auto const ne =
static_cast<uint64_t
>(numElements);
2149 auto const s =
static_cast<uint64_t
>(
sizeof(Node));
2150 auto const infos =
static_cast<uint64_t
>(calcNumBytesInfo(numElements));
2152 auto const total64 = ne * s + infos;
2153 auto const total =
static_cast<size_t>(total64);
2156 throwOverflowError();
2163 template <
typename Q = mapped_type>
2165 typename std::enable_if<!std::is_void<Q>::value,
bool>::type has(
const value_type& e)
const {
2167 auto it =
find(e.first);
2168 return it !=
end() && it->second == e.second;
2173 typename std::enable_if<std::is_void<Q>::value,
bool>::type has(const
value_type& e)
const {
2178 void reserve(
size_t c,
bool forceRehash) {
2180 auto const minElementsAllowed = (std::max)(c, mNumElements);
2181 auto newSize = InitialNumElements;
2182 while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) {
2186 throwOverflowError();
2189 ROBIN_HOOD_LOG(
"newSize > mMask + 1: " << newSize <<
" > " << mMask <<
" + 1")
2193 if (forceRehash || newSize > mMask + 1) {
2194 rehashPowerOfTwo(newSize,
false);
2201 void rehashPowerOfTwo(
size_t numBuckets,
bool forceFree) {
2204 Node* const oldKeyVals = mKeyVals;
2205 uint8_t const* const oldInfo = mInfo;
2210 initData(numBuckets);
2211 if (oldMaxElementsWithBuffer > 1) {
2212 for (
size_t i = 0; i < oldMaxElementsWithBuffer; ++i) {
2213 if (oldInfo[i] != 0) {
2216 insert_move(std::move(oldKeyVals[i]));
2218 oldKeyVals[i].~Node();
2225 if (oldKeyVals != reinterpret_cast_no_cast_align_warning<Node*>(&mMask)) {
2228 std::free(oldKeyVals);
2230 DataPool::addOrFree(oldKeyVals, calcNumBytesTotal(oldMaxElementsWithBuffer));
2236 ROBIN_HOOD(NOINLINE)
void throwOverflowError()
const {
2237 #if ROBIN_HOOD(HAS_EXCEPTIONS)
2238 throw std::overflow_error(
"robin_hood::map overflow");
2244 template <
typename OtherKey,
typename... Args>
2245 std::pair<iterator, bool> try_emplace_impl(OtherKey&& key, Args&&... args) {
2247 auto idxAndState = insertKeyPrepareEmptySpot(key);
2248 switch (idxAndState.second) {
2249 case InsertionState::key_found:
2252 case InsertionState::new_node:
2253 ::new (
static_cast<void*
>(&mKeyVals[idxAndState.first])) Node(
2254 *
this, std::piecewise_construct, std::forward_as_tuple(std::forward<OtherKey>(key)),
2255 std::forward_as_tuple(std::forward<Args>(args)...));
2258 case InsertionState::overwrite_node:
2259 mKeyVals[idxAndState.first] = Node(*
this, std::piecewise_construct,
2260 std::forward_as_tuple(std::forward<OtherKey>(key)),
2261 std::forward_as_tuple(std::forward<Args>(args)...));
2264 case InsertionState::overflow_error:
2265 throwOverflowError();
2269 return std::make_pair(
iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first),
2270 InsertionState::key_found != idxAndState.second);
2273 template <
typename OtherKey,
typename Mapped>
2274 std::pair<iterator, bool> insertOrAssignImpl(OtherKey&& key, Mapped&& obj) {
2276 auto idxAndState = insertKeyPrepareEmptySpot(key);
2277 switch (idxAndState.second) {
2278 case InsertionState::key_found:
2279 mKeyVals[idxAndState.first].getSecond() = std::forward<Mapped>(obj);
2282 case InsertionState::new_node:
2283 ::new (
static_cast<void*
>(&mKeyVals[idxAndState.first])) Node(
2284 *
this, std::piecewise_construct, std::forward_as_tuple(std::forward<OtherKey>(key)),
2285 std::forward_as_tuple(std::forward<Mapped>(obj)));
2288 case InsertionState::overwrite_node:
2289 mKeyVals[idxAndState.first] = Node(*
this, std::piecewise_construct,
2290 std::forward_as_tuple(std::forward<OtherKey>(key)),
2291 std::forward_as_tuple(std::forward<Mapped>(obj)));
2294 case InsertionState::overflow_error:
2295 throwOverflowError();
2299 return std::make_pair(
iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first),
2300 InsertionState::key_found != idxAndState.second);
2303 void initData(
size_t max_elements) {
2305 mMask = max_elements - 1;
2306 mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements);
2311 auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer);
2312 ROBIN_HOOD_LOG(
"std::calloc " << numBytesTotal <<
" = calcNumBytesTotal("
2313 << numElementsWithBuffer <<
")")
2314 mKeyVals = reinterpret_cast<Node*>(
2315 detail::
assertNotNull<std::bad_alloc>(std::calloc(1, numBytesTotal)));
2316 mInfo = reinterpret_cast<uint8_t*>(mKeyVals + numElementsWithBuffer);
2319 mInfo[numElementsWithBuffer] = 1;
2321 mInfoInc = InitialInfoInc;
2322 mInfoHashShift = InitialInfoHashShift;
2325 enum class InsertionState { overflow_error, key_found, new_node, overwrite_node };
2330 template <
typename OtherKey>
2331 std::pair<size_t, InsertionState> insertKeyPrepareEmptySpot(OtherKey&& key) {
2332 for (
int i = 0; i < 256; ++i) {
2335 keyToIdx(key, &idx, &info);
2336 nextWhileLess(&info, &idx);
2339 while (info == mInfo[idx]) {
2340 if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
2343 return std::make_pair(idx, InsertionState::key_found);
2350 if (!increase_size()) {
2351 return std::make_pair(
size_t(0), InsertionState::overflow_error);
2357 auto const insertion_idx = idx;
2358 auto const insertion_info = info;
2360 mMaxNumElementsAllowed = 0;
2364 while (0 != mInfo[idx]) {
2368 if (idx != insertion_idx) {
2369 shiftUp(idx, insertion_idx);
2372 mInfo[insertion_idx] =
static_cast<uint8_t
>(insertion_info);
2374 return std::make_pair(insertion_idx, idx == insertion_idx
2375 ? InsertionState::new_node
2376 : InsertionState::overwrite_node);
2380 return std::make_pair(
size_t(0), InsertionState::overflow_error);
2383 bool try_increase_info() {
2384 ROBIN_HOOD_LOG(
"mInfoInc=" << mInfoInc <<
", numElements=" << mNumElements
2385 <<
", maxNumElementsAllowed="
2386 << calcMaxNumElementsAllowed(mMask + 1))
2387 if (mInfoInc <= 2) {
2392 mInfoInc =
static_cast<uint8_t
>(mInfoInc >> 1U);
2399 for (
size_t i = 0; i < numElementsWithBuffer; i += 8) {
2400 auto val = unaligned_load<uint64_t>(mInfo + i);
2401 val = (val >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f);
2402 std::memcpy(mInfo + i, &val,
sizeof(val));
2405 mInfo[numElementsWithBuffer] = 1;
2407 mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
2412 bool increase_size() {
2415 initData(InitialNumElements);
2419 auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
2420 if (mNumElements < maxNumElementsAllowed && try_increase_info()) {
2424 ROBIN_HOOD_LOG(
"mNumElements=" << mNumElements <<
", maxNumElementsAllowed="
2425 << maxNumElementsAllowed <<
", load="
2426 << (
static_cast<double>(mNumElements) * 100.0 /
2427 (
static_cast<double>(mMask) + 1)))
2429 nextHashMultiplier();
2430 if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) {
2434 rehashPowerOfTwo(mMask + 1,
true);
2438 rehashPowerOfTwo((mMask + 1) * 2,
false);
2443 void nextHashMultiplier() {
2446 mHashMultiplier += UINT64_C(0xc4ceb9fe1a85ec54);
2455 Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::value>{}
2456 .nodesDoNotDeallocate(*
this);
2462 if (mKeyVals != reinterpret_cast_no_cast_align_warning<Node*>(&mMask)) {
2464 std::free(mKeyVals);
2468 void init() noexcept {
2469 mKeyVals = reinterpret_cast_no_cast_align_warning<Node*>(&mMask);
2470 mInfo =
reinterpret_cast<uint8_t*
>(&mMask);
2473 mMaxNumElementsAllowed = 0;
2474 mInfoInc = InitialInfoInc;
2475 mInfoHashShift = InitialInfoHashShift;
2479 uint64_t mHashMultiplier = UINT64_C(0xc4ceb9fe1a85ec53);
2480 Node* mKeyVals = reinterpret_cast_no_cast_align_warning<Node*>(&mMask);
2481 uint8_t* mInfo =
reinterpret_cast<uint8_t*
>(&mMask);
2482 size_t mNumElements = 0;
2484 size_t mMaxNumElementsAllowed = 0;
2485 InfoType mInfoInc = InitialInfoInc;
2486 InfoType mInfoHashShift = InitialInfoHashShift;
2494 template <
typename Key,
typename T,
typename Hash = hash<Key>,
2495 typename KeyEqual = std::equal_to<Key>,
size_t MaxLoadFactor100 = 80>
2498 template <
typename Key,
typename T,
typename Hash = hash<Key>,
2499 typename KeyEqual = std::equal_to<Key>,
size_t MaxLoadFactor100 = 80>
2502 template <
typename Key,
typename T,
typename Hash = hash<Key>,
2503 typename KeyEqual = std::equal_to<Key>,
size_t MaxLoadFactor100 = 80>
2506 std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
2507 std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
2508 MaxLoadFactor100, Key, T, Hash, KeyEqual>;
2512 template <
typename Key,
typename Hash = hash<Key>,
typename KeyEqual = std::equal_to<Key>,
2513 size_t MaxLoadFactor100 = 80>
2516 template <
typename Key,
typename Hash = hash<Key>,
typename KeyEqual = std::equal_to<Key>,
2517 size_t MaxLoadFactor100 = 80>
2520 template <
typename Key,
typename Hash = hash<Key>,
typename KeyEqual = std::equal_to<Key>,
2521 size_t MaxLoadFactor100 = 80>
2523 std::is_nothrow_move_constructible<Key>::value &&
2524 std::is_nothrow_move_assignable<Key>::value,
2525 MaxLoadFactor100, Key, void, Hash, KeyEqual>;