Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/mash/robin_hood.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
rev   line source
jpayne@69 1 // ______ _____ ______ _________
jpayne@69 2 // ______________ ___ /_ ___(_)_______ ___ /_ ______ ______ ______ /
jpayne@69 3 // __ ___/_ __ \__ __ \__ / __ __ \ __ __ \_ __ \_ __ \_ __ /
jpayne@69 4 // _ / / /_/ /_ /_/ /_ / _ / / / _ / / // /_/ // /_/ // /_/ /
jpayne@69 5 // /_/ \____/ /_.___/ /_/ /_/ /_/ ________/_/ /_/ \____/ \____/ \__,_/
jpayne@69 6 // _/_____/
jpayne@69 7 //
jpayne@69 8 // Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
jpayne@69 9 // https://github.com/martinus/robin-hood-hashing
jpayne@69 10 //
jpayne@69 11 // Licensed under the MIT License <http://opensource.org/licenses/MIT>.
jpayne@69 12 // SPDX-License-Identifier: MIT
jpayne@69 13 // Copyright (c) 2018-2020 Martin Ankerl <http://martin.ankerl.com>
jpayne@69 14 //
jpayne@69 15 // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69 16 // of this software and associated documentation files (the "Software"), to deal
jpayne@69 17 // in the Software without restriction, including without limitation the rights
jpayne@69 18 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69 19 // copies of the Software, and to permit persons to whom the Software is
jpayne@69 20 // furnished to do so, subject to the following conditions:
jpayne@69 21 //
jpayne@69 22 // The above copyright notice and this permission notice shall be included in all
jpayne@69 23 // copies or substantial portions of the Software.
jpayne@69 24 //
jpayne@69 25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69 26 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69 27 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69 28 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69 29 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69 30 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
jpayne@69 31 // SOFTWARE.
jpayne@69 32
jpayne@69 33 #ifndef ROBIN_HOOD_H_INCLUDED
jpayne@69 34 #define ROBIN_HOOD_H_INCLUDED
jpayne@69 35
jpayne@69 36 // see https://semver.org/
jpayne@69 37 #define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes
jpayne@69 38 #define ROBIN_HOOD_VERSION_MINOR 9 // for adding functionality in a backwards-compatible manner
jpayne@69 39 #define ROBIN_HOOD_VERSION_PATCH 1 // for backwards-compatible bug fixes
jpayne@69 40
jpayne@69 41 #include <algorithm>
jpayne@69 42 #include <cstdlib>
jpayne@69 43 #include <cstring>
jpayne@69 44 #include <functional>
jpayne@69 45 #include <memory> // only to support hash of smart pointers
jpayne@69 46 #include <stdexcept>
jpayne@69 47 #include <string>
jpayne@69 48 #include <type_traits>
jpayne@69 49 #include <utility>
jpayne@69 50 #if __cplusplus >= 201703L
jpayne@69 51 # include <string_view>
jpayne@69 52 #endif
jpayne@69 53
jpayne@69 54 // #define ROBIN_HOOD_LOG_ENABLED
jpayne@69 55 #ifdef ROBIN_HOOD_LOG_ENABLED
jpayne@69 56 # include <iostream>
jpayne@69 57 # define ROBIN_HOOD_LOG(...) \
jpayne@69 58 std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl;
jpayne@69 59 #else
jpayne@69 60 # define ROBIN_HOOD_LOG(x)
jpayne@69 61 #endif
jpayne@69 62
jpayne@69 63 // #define ROBIN_HOOD_TRACE_ENABLED
jpayne@69 64 #ifdef ROBIN_HOOD_TRACE_ENABLED
jpayne@69 65 # include <iostream>
jpayne@69 66 # define ROBIN_HOOD_TRACE(...) \
jpayne@69 67 std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl;
jpayne@69 68 #else
jpayne@69 69 # define ROBIN_HOOD_TRACE(x)
jpayne@69 70 #endif
jpayne@69 71
jpayne@69 72 // #define ROBIN_HOOD_COUNT_ENABLED
jpayne@69 73 #ifdef ROBIN_HOOD_COUNT_ENABLED
jpayne@69 74 # include <iostream>
jpayne@69 75 # define ROBIN_HOOD_COUNT(x) ++counts().x;
jpayne@69 76 namespace robin_hood {
jpayne@69 77 struct Counts {
jpayne@69 78 uint64_t shiftUp{};
jpayne@69 79 uint64_t shiftDown{};
jpayne@69 80 };
jpayne@69 81 inline std::ostream& operator<<(std::ostream& os, Counts const& c) {
jpayne@69 82 return os << c.shiftUp << " shiftUp" << std::endl << c.shiftDown << " shiftDown" << std::endl;
jpayne@69 83 }
jpayne@69 84
jpayne@69 85 static Counts& counts() {
jpayne@69 86 static Counts counts{};
jpayne@69 87 return counts;
jpayne@69 88 }
jpayne@69 89 } // namespace robin_hood
jpayne@69 90 #else
jpayne@69 91 # define ROBIN_HOOD_COUNT(x)
jpayne@69 92 #endif
jpayne@69 93
jpayne@69 94 // all non-argument macros should use this facility. See
jpayne@69 95 // https://www.fluentcpp.com/2019/05/28/better-macros-better-flags/
jpayne@69 96 #define ROBIN_HOOD(x) ROBIN_HOOD_PRIVATE_DEFINITION_##x()
jpayne@69 97
jpayne@69 98 // mark unused members with this macro
jpayne@69 99 #define ROBIN_HOOD_UNUSED(identifier)
jpayne@69 100
jpayne@69 101 // bitness
jpayne@69 102 #if SIZE_MAX == UINT32_MAX
jpayne@69 103 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 32
jpayne@69 104 #elif SIZE_MAX == UINT64_MAX
jpayne@69 105 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 64
jpayne@69 106 #else
jpayne@69 107 # error Unsupported bitness
jpayne@69 108 #endif
jpayne@69 109
jpayne@69 110 // endianess
jpayne@69 111 #ifdef _MSC_VER
jpayne@69 112 # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() 1
jpayne@69 113 # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() 0
jpayne@69 114 #else
jpayne@69 115 # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() \
jpayne@69 116 (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
jpayne@69 117 # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
jpayne@69 118 #endif
jpayne@69 119
jpayne@69 120 // inline
jpayne@69 121 #ifdef _MSC_VER
jpayne@69 122 # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __declspec(noinline)
jpayne@69 123 #else
jpayne@69 124 # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __attribute__((noinline))
jpayne@69 125 #endif
jpayne@69 126
jpayne@69 127 // exceptions
jpayne@69 128 #if !defined(__cpp_exceptions) && !defined(__EXCEPTIONS) && !defined(_CPPUNWIND)
jpayne@69 129 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 0
jpayne@69 130 #else
jpayne@69 131 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 1
jpayne@69 132 #endif
jpayne@69 133
jpayne@69 134 // count leading/trailing bits
jpayne@69 135 #if !defined(ROBIN_HOOD_DISABLE_INTRINSICS)
jpayne@69 136 # ifdef _MSC_VER
jpayne@69 137 # if ROBIN_HOOD(BITNESS) == 32
jpayne@69 138 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward
jpayne@69 139 # else
jpayne@69 140 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward64
jpayne@69 141 # endif
jpayne@69 142 # include <intrin.h>
jpayne@69 143 # pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD))
jpayne@69 144 # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \
jpayne@69 145 [](size_t mask) noexcept -> int { \
jpayne@69 146 unsigned long index; \
jpayne@69 147 return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast<int>(index) \
jpayne@69 148 : ROBIN_HOOD(BITNESS); \
jpayne@69 149 }(x)
jpayne@69 150 # else
jpayne@69 151 # if ROBIN_HOOD(BITNESS) == 32
jpayne@69 152 # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl
jpayne@69 153 # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl
jpayne@69 154 # else
jpayne@69 155 # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll
jpayne@69 156 # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll
jpayne@69 157 # endif
jpayne@69 158 # define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS))
jpayne@69 159 # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS))
jpayne@69 160 # endif
jpayne@69 161 #endif
jpayne@69 162
jpayne@69 163 // fallthrough
jpayne@69 164 #ifndef __has_cpp_attribute // For backwards compatibility
jpayne@69 165 # define __has_cpp_attribute(x) 0
jpayne@69 166 #endif
jpayne@69 167 #if __has_cpp_attribute(clang::fallthrough)
jpayne@69 168 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[clang::fallthrough]]
jpayne@69 169 #elif __has_cpp_attribute(gnu::fallthrough)
jpayne@69 170 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[gnu::fallthrough]]
jpayne@69 171 #else
jpayne@69 172 # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH()
jpayne@69 173 #endif
jpayne@69 174
jpayne@69 175 // likely/unlikely
jpayne@69 176 #ifdef _MSC_VER
jpayne@69 177 # define ROBIN_HOOD_LIKELY(condition) condition
jpayne@69 178 # define ROBIN_HOOD_UNLIKELY(condition) condition
jpayne@69 179 #else
jpayne@69 180 # define ROBIN_HOOD_LIKELY(condition) __builtin_expect(condition, 1)
jpayne@69 181 # define ROBIN_HOOD_UNLIKELY(condition) __builtin_expect(condition, 0)
jpayne@69 182 #endif
jpayne@69 183
jpayne@69 184 // detect if native wchar_t type is availiable in MSVC
jpayne@69 185 #ifdef _MSC_VER
jpayne@69 186 # ifdef _NATIVE_WCHAR_T_DEFINED
jpayne@69 187 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1
jpayne@69 188 # else
jpayne@69 189 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 0
jpayne@69 190 # endif
jpayne@69 191 #else
jpayne@69 192 # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1
jpayne@69 193 #endif
jpayne@69 194
jpayne@69 195 // workaround missing "is_trivially_copyable" in g++ < 5.0
jpayne@69 196 // See https://stackoverflow.com/a/31798726/48181
jpayne@69 197 #if defined(__GNUC__) && __GNUC__ < 5
jpayne@69 198 # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__)
jpayne@69 199 #else
jpayne@69 200 # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value
jpayne@69 201 #endif
jpayne@69 202
jpayne@69 203 // helpers for C++ versions, see https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html
jpayne@69 204 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX() __cplusplus
jpayne@69 205 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX98() 199711L
jpayne@69 206 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX11() 201103L
jpayne@69 207 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX14() 201402L
jpayne@69 208 #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX17() 201703L
jpayne@69 209
jpayne@69 210 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17)
jpayne@69 211 # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() [[nodiscard]]
jpayne@69 212 #else
jpayne@69 213 # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD()
jpayne@69 214 #endif
jpayne@69 215
jpayne@69 216 namespace robin_hood {
jpayne@69 217
jpayne@69 218 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14)
jpayne@69 219 # define ROBIN_HOOD_STD std
jpayne@69 220 #else
jpayne@69 221
jpayne@69 222 // c++11 compatibility layer
jpayne@69 223 namespace ROBIN_HOOD_STD {
jpayne@69 224 template <class T>
jpayne@69 225 struct alignment_of
jpayne@69 226 : std::integral_constant<std::size_t, alignof(typename std::remove_all_extents<T>::type)> {};
jpayne@69 227
jpayne@69 228 template <class T, T... Ints>
jpayne@69 229 class integer_sequence {
jpayne@69 230 public:
jpayne@69 231 using value_type = T;
jpayne@69 232 static_assert(std::is_integral<value_type>::value, "not integral type");
jpayne@69 233 static constexpr std::size_t size() noexcept {
jpayne@69 234 return sizeof...(Ints);
jpayne@69 235 }
jpayne@69 236 };
jpayne@69 237 template <std::size_t... Inds>
jpayne@69 238 using index_sequence = integer_sequence<std::size_t, Inds...>;
jpayne@69 239
jpayne@69 240 namespace detail_ {
jpayne@69 241 template <class T, T Begin, T End, bool>
jpayne@69 242 struct IntSeqImpl {
jpayne@69 243 using TValue = T;
jpayne@69 244 static_assert(std::is_integral<TValue>::value, "not integral type");
jpayne@69 245 static_assert(Begin >= 0 && Begin < End, "unexpected argument (Begin<0 || Begin<=End)");
jpayne@69 246
jpayne@69 247 template <class, class>
jpayne@69 248 struct IntSeqCombiner;
jpayne@69 249
jpayne@69 250 template <TValue... Inds0, TValue... Inds1>
jpayne@69 251 struct IntSeqCombiner<integer_sequence<TValue, Inds0...>, integer_sequence<TValue, Inds1...>> {
jpayne@69 252 using TResult = integer_sequence<TValue, Inds0..., Inds1...>;
jpayne@69 253 };
jpayne@69 254
jpayne@69 255 using TResult =
jpayne@69 256 typename IntSeqCombiner<typename IntSeqImpl<TValue, Begin, Begin + (End - Begin) / 2,
jpayne@69 257 (End - Begin) / 2 == 1>::TResult,
jpayne@69 258 typename IntSeqImpl<TValue, Begin + (End - Begin) / 2, End,
jpayne@69 259 (End - Begin + 1) / 2 == 1>::TResult>::TResult;
jpayne@69 260 };
jpayne@69 261
jpayne@69 262 template <class T, T Begin>
jpayne@69 263 struct IntSeqImpl<T, Begin, Begin, false> {
jpayne@69 264 using TValue = T;
jpayne@69 265 static_assert(std::is_integral<TValue>::value, "not integral type");
jpayne@69 266 static_assert(Begin >= 0, "unexpected argument (Begin<0)");
jpayne@69 267 using TResult = integer_sequence<TValue>;
jpayne@69 268 };
jpayne@69 269
jpayne@69 270 template <class T, T Begin, T End>
jpayne@69 271 struct IntSeqImpl<T, Begin, End, true> {
jpayne@69 272 using TValue = T;
jpayne@69 273 static_assert(std::is_integral<TValue>::value, "not integral type");
jpayne@69 274 static_assert(Begin >= 0, "unexpected argument (Begin<0)");
jpayne@69 275 using TResult = integer_sequence<TValue, Begin>;
jpayne@69 276 };
jpayne@69 277 } // namespace detail_
jpayne@69 278
jpayne@69 279 template <class T, T N>
jpayne@69 280 using make_integer_sequence = typename detail_::IntSeqImpl<T, 0, N, (N - 0) == 1>::TResult;
jpayne@69 281
jpayne@69 282 template <std::size_t N>
jpayne@69 283 using make_index_sequence = make_integer_sequence<std::size_t, N>;
jpayne@69 284
jpayne@69 285 template <class... T>
jpayne@69 286 using index_sequence_for = make_index_sequence<sizeof...(T)>;
jpayne@69 287
jpayne@69 288 } // namespace ROBIN_HOOD_STD
jpayne@69 289
jpayne@69 290 #endif
jpayne@69 291
jpayne@69 292 namespace detail {
jpayne@69 293
jpayne@69 294 // make sure we static_cast to the correct type for hash_int
jpayne@69 295 #if ROBIN_HOOD(BITNESS) == 64
jpayne@69 296 using SizeT = uint64_t;
jpayne@69 297 #else
jpayne@69 298 using SizeT = uint32_t;
jpayne@69 299 #endif
jpayne@69 300
jpayne@69 301 template <typename T>
jpayne@69 302 T rotr(T x, unsigned k) {
jpayne@69 303 return (x >> k) | (x << (8U * sizeof(T) - k));
jpayne@69 304 }
jpayne@69 305
jpayne@69 306 // This cast gets rid of warnings like "cast from 'uint8_t*' {aka 'unsigned char*'} to
jpayne@69 307 // 'uint64_t*' {aka 'long unsigned int*'} increases required alignment of target type". Use with
jpayne@69 308 // care!
jpayne@69 309 template <typename T>
jpayne@69 310 inline T reinterpret_cast_no_cast_align_warning(void* ptr) noexcept {
jpayne@69 311 return reinterpret_cast<T>(ptr);
jpayne@69 312 }
jpayne@69 313
jpayne@69 314 template <typename T>
jpayne@69 315 inline T reinterpret_cast_no_cast_align_warning(void const* ptr) noexcept {
jpayne@69 316 return reinterpret_cast<T>(ptr);
jpayne@69 317 }
jpayne@69 318
jpayne@69 319 // make sure this is not inlined as it is slow and dramatically enlarges code, thus making other
jpayne@69 320 // inlinings more difficult. Throws are also generally the slow path.
jpayne@69 321 template <typename E, typename... Args>
jpayne@69 322 [[noreturn]] ROBIN_HOOD(NOINLINE)
jpayne@69 323 #if ROBIN_HOOD(HAS_EXCEPTIONS)
jpayne@69 324 void doThrow(Args&&... args) {
jpayne@69 325 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-array-to-pointer-decay)
jpayne@69 326 throw E(std::forward<Args>(args)...);
jpayne@69 327 }
jpayne@69 328 #else
jpayne@69 329 void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) /*unused*/) {
jpayne@69 330 abort();
jpayne@69 331 }
jpayne@69 332 #endif
jpayne@69 333
jpayne@69 334 template <typename E, typename T, typename... Args>
jpayne@69 335 T* assertNotNull(T* t, Args&&... args) {
jpayne@69 336 if (ROBIN_HOOD_UNLIKELY(nullptr == t)) {
jpayne@69 337 doThrow<E>(std::forward<Args>(args)...);
jpayne@69 338 }
jpayne@69 339 return t;
jpayne@69 340 }
jpayne@69 341
jpayne@69 342 template <typename T>
jpayne@69 343 inline T unaligned_load(void const* ptr) noexcept {
jpayne@69 344 // using memcpy so we don't get into unaligned load problems.
jpayne@69 345 // compiler should optimize this very well anyways.
jpayne@69 346 T t;
jpayne@69 347 std::memcpy(&t, ptr, sizeof(T));
jpayne@69 348 return t;
jpayne@69 349 }
jpayne@69 350
jpayne@69 351 // Allocates bulks of memory for objects of type T. This deallocates the memory in the destructor,
jpayne@69 352 // and keeps a linked list of the allocated memory around. Overhead per allocation is the size of a
jpayne@69 353 // pointer.
jpayne@69 354 template <typename T, size_t MinNumAllocs = 4, size_t MaxNumAllocs = 256>
jpayne@69 355 class BulkPoolAllocator {
jpayne@69 356 public:
jpayne@69 357 BulkPoolAllocator() noexcept = default;
jpayne@69 358
jpayne@69 359 // does not copy anything, just creates a new allocator.
jpayne@69 360 BulkPoolAllocator(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept
jpayne@69 361 : mHead(nullptr)
jpayne@69 362 , mListForFree(nullptr) {}
jpayne@69 363
jpayne@69 364 BulkPoolAllocator(BulkPoolAllocator&& o) noexcept
jpayne@69 365 : mHead(o.mHead)
jpayne@69 366 , mListForFree(o.mListForFree) {
jpayne@69 367 o.mListForFree = nullptr;
jpayne@69 368 o.mHead = nullptr;
jpayne@69 369 }
jpayne@69 370
jpayne@69 371 BulkPoolAllocator& operator=(BulkPoolAllocator&& o) noexcept {
jpayne@69 372 reset();
jpayne@69 373 mHead = o.mHead;
jpayne@69 374 mListForFree = o.mListForFree;
jpayne@69 375 o.mListForFree = nullptr;
jpayne@69 376 o.mHead = nullptr;
jpayne@69 377 return *this;
jpayne@69 378 }
jpayne@69 379
jpayne@69 380 BulkPoolAllocator&
jpayne@69 381 // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp)
jpayne@69 382 operator=(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept {
jpayne@69 383 // does not do anything
jpayne@69 384 return *this;
jpayne@69 385 }
jpayne@69 386
jpayne@69 387 ~BulkPoolAllocator() noexcept {
jpayne@69 388 reset();
jpayne@69 389 }
jpayne@69 390
jpayne@69 391 // Deallocates all allocated memory.
jpayne@69 392 void reset() noexcept {
jpayne@69 393 while (mListForFree) {
jpayne@69 394 T* tmp = *mListForFree;
jpayne@69 395 ROBIN_HOOD_LOG("std::free")
jpayne@69 396 std::free(mListForFree);
jpayne@69 397 mListForFree = reinterpret_cast_no_cast_align_warning<T**>(tmp);
jpayne@69 398 }
jpayne@69 399 mHead = nullptr;
jpayne@69 400 }
jpayne@69 401
jpayne@69 402 // allocates, but does NOT initialize. Use in-place new constructor, e.g.
jpayne@69 403 // T* obj = pool.allocate();
jpayne@69 404 // ::new (static_cast<void*>(obj)) T();
jpayne@69 405 T* allocate() {
jpayne@69 406 T* tmp = mHead;
jpayne@69 407 if (!tmp) {
jpayne@69 408 tmp = performAllocation();
jpayne@69 409 }
jpayne@69 410
jpayne@69 411 mHead = *reinterpret_cast_no_cast_align_warning<T**>(tmp);
jpayne@69 412 return tmp;
jpayne@69 413 }
jpayne@69 414
jpayne@69 415 // does not actually deallocate but puts it in store.
jpayne@69 416 // make sure you have already called the destructor! e.g. with
jpayne@69 417 // obj->~T();
jpayne@69 418 // pool.deallocate(obj);
jpayne@69 419 void deallocate(T* obj) noexcept {
jpayne@69 420 *reinterpret_cast_no_cast_align_warning<T**>(obj) = mHead;
jpayne@69 421 mHead = obj;
jpayne@69 422 }
jpayne@69 423
jpayne@69 424 // Adds an already allocated block of memory to the allocator. This allocator is from now on
jpayne@69 425 // responsible for freeing the data (with free()). If the provided data is not large enough to
jpayne@69 426 // make use of, it is immediately freed. Otherwise it is reused and freed in the destructor.
jpayne@69 427 void addOrFree(void* ptr, const size_t numBytes) noexcept {
jpayne@69 428 // calculate number of available elements in ptr
jpayne@69 429 if (numBytes < ALIGNMENT + ALIGNED_SIZE) {
jpayne@69 430 // not enough data for at least one element. Free and return.
jpayne@69 431 ROBIN_HOOD_LOG("std::free")
jpayne@69 432 std::free(ptr);
jpayne@69 433 } else {
jpayne@69 434 ROBIN_HOOD_LOG("add to buffer")
jpayne@69 435 add(ptr, numBytes);
jpayne@69 436 }
jpayne@69 437 }
jpayne@69 438
jpayne@69 439 void swap(BulkPoolAllocator<T, MinNumAllocs, MaxNumAllocs>& other) noexcept {
jpayne@69 440 using std::swap;
jpayne@69 441 swap(mHead, other.mHead);
jpayne@69 442 swap(mListForFree, other.mListForFree);
jpayne@69 443 }
jpayne@69 444
jpayne@69 445 private:
jpayne@69 446 // iterates the list of allocated memory to calculate how many to alloc next.
jpayne@69 447 // Recalculating this each time saves us a size_t member.
jpayne@69 448 // This ignores the fact that memory blocks might have been added manually with addOrFree. In
jpayne@69 449 // practice, this should not matter much.
jpayne@69 450 ROBIN_HOOD(NODISCARD) size_t calcNumElementsToAlloc() const noexcept {
jpayne@69 451 auto tmp = mListForFree;
jpayne@69 452 size_t numAllocs = MinNumAllocs;
jpayne@69 453
jpayne@69 454 while (numAllocs * 2 <= MaxNumAllocs && tmp) {
jpayne@69 455 auto x = reinterpret_cast<T***>(tmp);
jpayne@69 456 tmp = *x;
jpayne@69 457 numAllocs *= 2;
jpayne@69 458 }
jpayne@69 459
jpayne@69 460 return numAllocs;
jpayne@69 461 }
jpayne@69 462
jpayne@69 463 // WARNING: Underflow if numBytes < ALIGNMENT! This is guarded in addOrFree().
jpayne@69 464 void add(void* ptr, const size_t numBytes) noexcept {
jpayne@69 465 const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE;
jpayne@69 466
jpayne@69 467 auto data = reinterpret_cast<T**>(ptr);
jpayne@69 468
jpayne@69 469 // link free list
jpayne@69 470 auto x = reinterpret_cast<T***>(data);
jpayne@69 471 *x = mListForFree;
jpayne@69 472 mListForFree = data;
jpayne@69 473
jpayne@69 474 // create linked list for newly allocated data
jpayne@69 475 auto* const headT =
jpayne@69 476 reinterpret_cast_no_cast_align_warning<T*>(reinterpret_cast<char*>(ptr) + ALIGNMENT);
jpayne@69 477
jpayne@69 478 auto* const head = reinterpret_cast<char*>(headT);
jpayne@69 479
jpayne@69 480 // Visual Studio compiler automatically unrolls this loop, which is pretty cool
jpayne@69 481 for (size_t i = 0; i < numElements; ++i) {
jpayne@69 482 *reinterpret_cast_no_cast_align_warning<char**>(head + i * ALIGNED_SIZE) =
jpayne@69 483 head + (i + 1) * ALIGNED_SIZE;
jpayne@69 484 }
jpayne@69 485
jpayne@69 486 // last one points to 0
jpayne@69 487 *reinterpret_cast_no_cast_align_warning<T**>(head + (numElements - 1) * ALIGNED_SIZE) =
jpayne@69 488 mHead;
jpayne@69 489 mHead = headT;
jpayne@69 490 }
jpayne@69 491
jpayne@69 492 // Called when no memory is available (mHead == 0).
jpayne@69 493 // Don't inline this slow path.
jpayne@69 494 ROBIN_HOOD(NOINLINE) T* performAllocation() {
jpayne@69 495 size_t const numElementsToAlloc = calcNumElementsToAlloc();
jpayne@69 496
jpayne@69 497 // alloc new memory: [prev |T, T, ... T]
jpayne@69 498 size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc;
jpayne@69 499 ROBIN_HOOD_LOG("std::malloc " << bytes << " = " << ALIGNMENT << " + " << ALIGNED_SIZE
jpayne@69 500 << " * " << numElementsToAlloc)
jpayne@69 501 add(assertNotNull<std::bad_alloc>(std::malloc(bytes)), bytes);
jpayne@69 502 return mHead;
jpayne@69 503 }
jpayne@69 504
jpayne@69 505 // enforce byte alignment of the T's
jpayne@69 506 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14)
jpayne@69 507 static constexpr size_t ALIGNMENT =
jpayne@69 508 (std::max)(std::alignment_of<T>::value, std::alignment_of<T*>::value);
jpayne@69 509 #else
jpayne@69 510 static const size_t ALIGNMENT =
jpayne@69 511 (ROBIN_HOOD_STD::alignment_of<T>::value > ROBIN_HOOD_STD::alignment_of<T*>::value)
jpayne@69 512 ? ROBIN_HOOD_STD::alignment_of<T>::value
jpayne@69 513 : +ROBIN_HOOD_STD::alignment_of<T*>::value; // the + is for walkarround
jpayne@69 514 #endif
jpayne@69 515
jpayne@69 516 static constexpr size_t ALIGNED_SIZE = ((sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT;
jpayne@69 517
jpayne@69 518 static_assert(MinNumAllocs >= 1, "MinNumAllocs");
jpayne@69 519 static_assert(MaxNumAllocs >= MinNumAllocs, "MaxNumAllocs");
jpayne@69 520 static_assert(ALIGNED_SIZE >= sizeof(T*), "ALIGNED_SIZE");
jpayne@69 521 static_assert(0 == (ALIGNED_SIZE % sizeof(T*)), "ALIGNED_SIZE mod");
jpayne@69 522 static_assert(ALIGNMENT >= sizeof(T*), "ALIGNMENT");
jpayne@69 523
jpayne@69 524 T* mHead{nullptr};
jpayne@69 525 T** mListForFree{nullptr};
jpayne@69 526 };
jpayne@69 527
jpayne@69 528 template <typename T, size_t MinSize, size_t MaxSize, bool IsFlat>
jpayne@69 529 struct NodeAllocator;
jpayne@69 530
jpayne@69 531 // dummy allocator that does nothing
jpayne@69 532 template <typename T, size_t MinSize, size_t MaxSize>
jpayne@69 533 struct NodeAllocator<T, MinSize, MaxSize, true> {
jpayne@69 534
jpayne@69 535 // we are not using the data, so just free it.
jpayne@69 536 void addOrFree(void* ptr, size_t ROBIN_HOOD_UNUSED(numBytes) /*unused*/) noexcept {
jpayne@69 537 ROBIN_HOOD_LOG("std::free")
jpayne@69 538 std::free(ptr);
jpayne@69 539 }
jpayne@69 540 };
jpayne@69 541
jpayne@69 542 template <typename T, size_t MinSize, size_t MaxSize>
jpayne@69 543 struct NodeAllocator<T, MinSize, MaxSize, false> : public BulkPoolAllocator<T, MinSize, MaxSize> {};
jpayne@69 544
jpayne@69 545 // dummy hash, unsed as mixer when robin_hood::hash is already used
jpayne@69 546 template <typename T>
jpayne@69 547 struct identity_hash {
jpayne@69 548 constexpr size_t operator()(T const& obj) const noexcept {
jpayne@69 549 return static_cast<size_t>(obj);
jpayne@69 550 }
jpayne@69 551 };
jpayne@69 552
jpayne@69 553 // c++14 doesn't have is_nothrow_swappable, and clang++ 6.0.1 doesn't like it either, so I'm making
jpayne@69 554 // my own here.
jpayne@69 555 namespace swappable {
jpayne@69 556 #if ROBIN_HOOD(CXX) < ROBIN_HOOD(CXX17)
jpayne@69 557 using std::swap;
jpayne@69 558 template <typename T>
jpayne@69 559 struct nothrow {
jpayne@69 560 static const bool value = noexcept(swap(std::declval<T&>(), std::declval<T&>()));
jpayne@69 561 };
jpayne@69 562 #else
jpayne@69 563 template <typename T>
jpayne@69 564 struct nothrow {
jpayne@69 565 static const bool value = std::is_nothrow_swappable<T>::value;
jpayne@69 566 };
jpayne@69 567 #endif
jpayne@69 568 } // namespace swappable
jpayne@69 569
jpayne@69 570 } // namespace detail
jpayne@69 571
jpayne@69 572 struct is_transparent_tag {};
jpayne@69 573
jpayne@69 574 // A custom pair implementation is used in the map because std::pair is not is_trivially_copyable,
jpayne@69 575 // which means it would not be allowed to be used in std::memcpy. This struct is copyable, which is
jpayne@69 576 // also tested.
jpayne@69 577 template <typename T1, typename T2>
jpayne@69 578 struct pair {
jpayne@69 579 using first_type = T1;
jpayne@69 580 using second_type = T2;
jpayne@69 581
jpayne@69 582 template <typename U1 = T1, typename U2 = T2,
jpayne@69 583 typename = typename std::enable_if<std::is_default_constructible<U1>::value &&
jpayne@69 584 std::is_default_constructible<U2>::value>::type>
jpayne@69 585 constexpr pair() noexcept(noexcept(U1()) && noexcept(U2()))
jpayne@69 586 : first()
jpayne@69 587 , second() {}
jpayne@69 588
jpayne@69 589 // pair constructors are explicit so we don't accidentally call this ctor when we don't have to.
jpayne@69 590 explicit constexpr pair(std::pair<T1, T2> const& o) noexcept(
jpayne@69 591 noexcept(T1(std::declval<T1 const&>())) && noexcept(T2(std::declval<T2 const&>())))
jpayne@69 592 : first(o.first)
jpayne@69 593 , second(o.second) {}
jpayne@69 594
jpayne@69 595 // pair constructors are explicit so we don't accidentally call this ctor when we don't have to.
jpayne@69 596 explicit constexpr pair(std::pair<T1, T2>&& o) noexcept(noexcept(
jpayne@69 597 T1(std::move(std::declval<T1&&>()))) && noexcept(T2(std::move(std::declval<T2&&>()))))
jpayne@69 598 : first(std::move(o.first))
jpayne@69 599 , second(std::move(o.second)) {}
jpayne@69 600
jpayne@69 601 constexpr pair(T1&& a, T2&& b) noexcept(noexcept(
jpayne@69 602 T1(std::move(std::declval<T1&&>()))) && noexcept(T2(std::move(std::declval<T2&&>()))))
jpayne@69 603 : first(std::move(a))
jpayne@69 604 , second(std::move(b)) {}
jpayne@69 605
jpayne@69 606 template <typename U1, typename U2>
jpayne@69 607 constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward<U1>(
jpayne@69 608 std::declval<U1&&>()))) && noexcept(T2(std::forward<U2>(std::declval<U2&&>()))))
jpayne@69 609 : first(std::forward<U1>(a))
jpayne@69 610 , second(std::forward<U2>(b)) {}
jpayne@69 611
jpayne@69 612 template <typename... U1, typename... U2>
jpayne@69 613 constexpr pair(
jpayne@69 614 std::piecewise_construct_t /*unused*/, std::tuple<U1...> a,
jpayne@69 615 std::tuple<U2...> b) noexcept(noexcept(pair(std::declval<std::tuple<U1...>&>(),
jpayne@69 616 std::declval<std::tuple<U2...>&>(),
jpayne@69 617 ROBIN_HOOD_STD::index_sequence_for<U1...>(),
jpayne@69 618 ROBIN_HOOD_STD::index_sequence_for<U2...>())))
jpayne@69 619 : pair(a, b, ROBIN_HOOD_STD::index_sequence_for<U1...>(),
jpayne@69 620 ROBIN_HOOD_STD::index_sequence_for<U2...>()) {}
jpayne@69 621
jpayne@69 622 // constructor called from the std::piecewise_construct_t ctor
jpayne@69 623 template <typename... U1, size_t... I1, typename... U2, size_t... I2>
jpayne@69 624 pair(std::tuple<U1...>& a, std::tuple<U2...>& b, ROBIN_HOOD_STD::index_sequence<I1...> /*unused*/, ROBIN_HOOD_STD::index_sequence<I2...> /*unused*/) noexcept(
jpayne@69 625 noexcept(T1(std::forward<U1>(std::get<I1>(
jpayne@69 626 std::declval<std::tuple<
jpayne@69 627 U1...>&>()))...)) && noexcept(T2(std::
jpayne@69 628 forward<U2>(std::get<I2>(
jpayne@69 629 std::declval<std::tuple<U2...>&>()))...)))
jpayne@69 630 : first(std::forward<U1>(std::get<I1>(a))...)
jpayne@69 631 , second(std::forward<U2>(std::get<I2>(b))...) {
jpayne@69 632 // make visual studio compiler happy about warning about unused a & b.
jpayne@69 633 // Visual studio's pair implementation disables warning 4100.
jpayne@69 634 (void)a;
jpayne@69 635 (void)b;
jpayne@69 636 }
jpayne@69 637
jpayne@69 638 void swap(pair<T1, T2>& o) noexcept((detail::swappable::nothrow<T1>::value) &&
jpayne@69 639 (detail::swappable::nothrow<T2>::value)) {
jpayne@69 640 using std::swap;
jpayne@69 641 swap(first, o.first);
jpayne@69 642 swap(second, o.second);
jpayne@69 643 }
jpayne@69 644
jpayne@69 645 T1 first; // NOLINT(misc-non-private-member-variables-in-classes)
jpayne@69 646 T2 second; // NOLINT(misc-non-private-member-variables-in-classes)
jpayne@69 647 };
jpayne@69 648
jpayne@69 649 template <typename A, typename B>
jpayne@69 650 inline void swap(pair<A, B>& a, pair<A, B>& b) noexcept(
jpayne@69 651 noexcept(std::declval<pair<A, B>&>().swap(std::declval<pair<A, B>&>()))) {
jpayne@69 652 a.swap(b);
jpayne@69 653 }
jpayne@69 654
jpayne@69 655 template <typename A, typename B>
jpayne@69 656 inline constexpr bool operator==(pair<A, B> const& x, pair<A, B> const& y) {
jpayne@69 657 return (x.first == y.first) && (x.second == y.second);
jpayne@69 658 }
jpayne@69 659 template <typename A, typename B>
jpayne@69 660 inline constexpr bool operator!=(pair<A, B> const& x, pair<A, B> const& y) {
jpayne@69 661 return !(x == y);
jpayne@69 662 }
jpayne@69 663 template <typename A, typename B>
jpayne@69 664 inline constexpr bool operator<(pair<A, B> const& x, pair<A, B> const& y) noexcept(noexcept(
jpayne@69 665 std::declval<A const&>() < std::declval<A const&>()) && noexcept(std::declval<B const&>() <
jpayne@69 666 std::declval<B const&>())) {
jpayne@69 667 return x.first < y.first || (!(y.first < x.first) && x.second < y.second);
jpayne@69 668 }
jpayne@69 669 template <typename A, typename B>
jpayne@69 670 inline constexpr bool operator>(pair<A, B> const& x, pair<A, B> const& y) {
jpayne@69 671 return y < x;
jpayne@69 672 }
jpayne@69 673 template <typename A, typename B>
jpayne@69 674 inline constexpr bool operator<=(pair<A, B> const& x, pair<A, B> const& y) {
jpayne@69 675 return !(x > y);
jpayne@69 676 }
jpayne@69 677 template <typename A, typename B>
jpayne@69 678 inline constexpr bool operator>=(pair<A, B> const& x, pair<A, B> const& y) {
jpayne@69 679 return !(x < y);
jpayne@69 680 }
jpayne@69 681
jpayne@69 682 inline size_t hash_bytes(void const* ptr, size_t len) noexcept {
jpayne@69 683 static constexpr uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
jpayne@69 684 static constexpr uint64_t seed = UINT64_C(0xe17a1465);
jpayne@69 685 static constexpr unsigned int r = 47;
jpayne@69 686
jpayne@69 687 auto const* const data64 = static_cast<uint64_t const*>(ptr);
jpayne@69 688 uint64_t h = seed ^ (len * m);
jpayne@69 689
jpayne@69 690 size_t const n_blocks = len / 8;
jpayne@69 691 for (size_t i = 0; i < n_blocks; ++i) {
jpayne@69 692 auto k = detail::unaligned_load<uint64_t>(data64 + i);
jpayne@69 693
jpayne@69 694 k *= m;
jpayne@69 695 k ^= k >> r;
jpayne@69 696 k *= m;
jpayne@69 697
jpayne@69 698 h ^= k;
jpayne@69 699 h *= m;
jpayne@69 700 }
jpayne@69 701
jpayne@69 702 auto const* const data8 = reinterpret_cast<uint8_t const*>(data64 + n_blocks);
jpayne@69 703 switch (len & 7U) {
jpayne@69 704 case 7:
jpayne@69 705 h ^= static_cast<uint64_t>(data8[6]) << 48U;
jpayne@69 706 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 707 case 6:
jpayne@69 708 h ^= static_cast<uint64_t>(data8[5]) << 40U;
jpayne@69 709 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 710 case 5:
jpayne@69 711 h ^= static_cast<uint64_t>(data8[4]) << 32U;
jpayne@69 712 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 713 case 4:
jpayne@69 714 h ^= static_cast<uint64_t>(data8[3]) << 24U;
jpayne@69 715 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 716 case 3:
jpayne@69 717 h ^= static_cast<uint64_t>(data8[2]) << 16U;
jpayne@69 718 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 719 case 2:
jpayne@69 720 h ^= static_cast<uint64_t>(data8[1]) << 8U;
jpayne@69 721 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 722 case 1:
jpayne@69 723 h ^= static_cast<uint64_t>(data8[0]);
jpayne@69 724 h *= m;
jpayne@69 725 ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
jpayne@69 726 default:
jpayne@69 727 break;
jpayne@69 728 }
jpayne@69 729
jpayne@69 730 h ^= h >> r;
jpayne@69 731 h *= m;
jpayne@69 732 h ^= h >> r;
jpayne@69 733 return static_cast<size_t>(h);
jpayne@69 734 }
jpayne@69 735
jpayne@69 736 inline size_t hash_int(uint64_t x) noexcept {
jpayne@69 737 // inspired by lemire's strongly universal hashing
jpayne@69 738 // https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/
jpayne@69 739 //
jpayne@69 740 // Instead of shifts, we use rotations so we don't lose any bits.
jpayne@69 741 //
jpayne@69 742 // Added a final multiplcation with a constant for more mixing. It is most important that
jpayne@69 743 // the lower bits are well mixed.
jpayne@69 744 auto h1 = x * UINT64_C(0xA24BAED4963EE407);
jpayne@69 745 auto h2 = detail::rotr(x, 32U) * UINT64_C(0x9FB21C651E98DF25);
jpayne@69 746 auto h = detail::rotr(h1 + h2, 32U);
jpayne@69 747 return static_cast<size_t>(h);
jpayne@69 748 }
jpayne@69 749
jpayne@69 750 // A thin wrapper around std::hash, performing an additional simple mixing step of the result.
jpayne@69 751 template <typename T, typename Enable = void>
jpayne@69 752 struct hash : public std::hash<T> {
jpayne@69 753 size_t operator()(T const& obj) const
jpayne@69 754 noexcept(noexcept(std::declval<std::hash<T>>().operator()(std::declval<T const&>()))) {
jpayne@69 755 // call base hash
jpayne@69 756 auto result = std::hash<T>::operator()(obj);
jpayne@69 757 // return mixed of that, to be save against identity has
jpayne@69 758 return hash_int(static_cast<detail::SizeT>(result));
jpayne@69 759 }
jpayne@69 760 };
jpayne@69 761
jpayne@69 762 template <typename CharT>
jpayne@69 763 struct hash<std::basic_string<CharT>> {
jpayne@69 764 size_t operator()(std::basic_string<CharT> const& str) const noexcept {
jpayne@69 765 return hash_bytes(str.data(), sizeof(CharT) * str.size());
jpayne@69 766 }
jpayne@69 767 };
jpayne@69 768
jpayne@69 769 #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17)
jpayne@69 770 template <typename CharT>
jpayne@69 771 struct hash<std::basic_string_view<CharT>> {
jpayne@69 772 size_t operator()(std::basic_string_view<CharT> const& sv) const noexcept {
jpayne@69 773 return hash_bytes(sv.data(), sizeof(CharT) * sv.size());
jpayne@69 774 }
jpayne@69 775 };
jpayne@69 776 #endif
jpayne@69 777
jpayne@69 778 template <class T>
jpayne@69 779 struct hash<T*> {
jpayne@69 780 size_t operator()(T* ptr) const noexcept {
jpayne@69 781 return hash_int(reinterpret_cast<detail::SizeT>(ptr));
jpayne@69 782 }
jpayne@69 783 };
jpayne@69 784
jpayne@69 785 template <class T>
jpayne@69 786 struct hash<std::unique_ptr<T>> {
jpayne@69 787 size_t operator()(std::unique_ptr<T> const& ptr) const noexcept {
jpayne@69 788 return hash_int(reinterpret_cast<detail::SizeT>(ptr.get()));
jpayne@69 789 }
jpayne@69 790 };
jpayne@69 791
jpayne@69 792 template <class T>
jpayne@69 793 struct hash<std::shared_ptr<T>> {
jpayne@69 794 size_t operator()(std::shared_ptr<T> const& ptr) const noexcept {
jpayne@69 795 return hash_int(reinterpret_cast<detail::SizeT>(ptr.get()));
jpayne@69 796 }
jpayne@69 797 };
jpayne@69 798
jpayne@69 799 template <typename Enum>
jpayne@69 800 struct hash<Enum, typename std::enable_if<std::is_enum<Enum>::value>::type> {
jpayne@69 801 size_t operator()(Enum e) const noexcept {
jpayne@69 802 using Underlying = typename std::underlying_type<Enum>::type;
jpayne@69 803 return hash<Underlying>{}(static_cast<Underlying>(e));
jpayne@69 804 }
jpayne@69 805 };
jpayne@69 806
jpayne@69 807 #define ROBIN_HOOD_HASH_INT(T) \
jpayne@69 808 template <> \
jpayne@69 809 struct hash<T> { \
jpayne@69 810 size_t operator()(T const& obj) const noexcept { \
jpayne@69 811 return hash_int(static_cast<uint64_t>(obj)); \
jpayne@69 812 } \
jpayne@69 813 }
jpayne@69 814
jpayne@69 815 #if defined(__GNUC__) && !defined(__clang__)
jpayne@69 816 # pragma GCC diagnostic push
jpayne@69 817 # pragma GCC diagnostic ignored "-Wuseless-cast"
jpayne@69 818 #endif
jpayne@69 819 // see https://en.cppreference.com/w/cpp/utility/hash
jpayne@69 820 ROBIN_HOOD_HASH_INT(bool);
jpayne@69 821 ROBIN_HOOD_HASH_INT(char);
jpayne@69 822 ROBIN_HOOD_HASH_INT(signed char);
jpayne@69 823 ROBIN_HOOD_HASH_INT(unsigned char);
jpayne@69 824 ROBIN_HOOD_HASH_INT(char16_t);
jpayne@69 825 ROBIN_HOOD_HASH_INT(char32_t);
jpayne@69 826 #if ROBIN_HOOD(HAS_NATIVE_WCHART)
jpayne@69 827 ROBIN_HOOD_HASH_INT(wchar_t);
jpayne@69 828 #endif
jpayne@69 829 ROBIN_HOOD_HASH_INT(short);
jpayne@69 830 ROBIN_HOOD_HASH_INT(unsigned short);
jpayne@69 831 ROBIN_HOOD_HASH_INT(int);
jpayne@69 832 ROBIN_HOOD_HASH_INT(unsigned int);
jpayne@69 833 ROBIN_HOOD_HASH_INT(long);
jpayne@69 834 ROBIN_HOOD_HASH_INT(long long);
jpayne@69 835 ROBIN_HOOD_HASH_INT(unsigned long);
jpayne@69 836 ROBIN_HOOD_HASH_INT(unsigned long long);
jpayne@69 837 #if defined(__GNUC__) && !defined(__clang__)
jpayne@69 838 # pragma GCC diagnostic pop
jpayne@69 839 #endif
jpayne@69 840 namespace detail {
jpayne@69 841
jpayne@69 842 template <typename T>
jpayne@69 843 struct void_type {
jpayne@69 844 using type = void;
jpayne@69 845 };
jpayne@69 846
jpayne@69 847 template <typename T, typename = void>
jpayne@69 848 struct has_is_transparent : public std::false_type {};
jpayne@69 849
jpayne@69 850 template <typename T>
jpayne@69 851 struct has_is_transparent<T, typename void_type<typename T::is_transparent>::type>
jpayne@69 852 : public std::true_type {};
jpayne@69 853
jpayne@69 854 // using wrapper classes for hash and key_equal prevents the diamond problem when the same type
jpayne@69 855 // is used. see https://stackoverflow.com/a/28771920/48181
jpayne@69 856 template <typename T>
jpayne@69 857 struct WrapHash : public T {
jpayne@69 858 WrapHash() = default;
jpayne@69 859 explicit WrapHash(T const& o) noexcept(noexcept(T(std::declval<T const&>())))
jpayne@69 860 : T(o) {}
jpayne@69 861 };
jpayne@69 862
jpayne@69 863 template <typename T>
jpayne@69 864 struct WrapKeyEqual : public T {
jpayne@69 865 WrapKeyEqual() = default;
jpayne@69 866 explicit WrapKeyEqual(T const& o) noexcept(noexcept(T(std::declval<T const&>())))
jpayne@69 867 : T(o) {}
jpayne@69 868 };
jpayne@69 869
jpayne@69 870 // A highly optimized hashmap implementation, using the Robin Hood algorithm.
jpayne@69 871 //
jpayne@69 872 // In most cases, this map should be usable as a drop-in replacement for std::unordered_map, but
jpayne@69 873 // be about 2x faster in most cases and require much less allocations.
jpayne@69 874 //
jpayne@69 875 // This implementation uses the following memory layout:
jpayne@69 876 //
jpayne@69 877 // [Node, Node, ... Node | info, info, ... infoSentinel ]
jpayne@69 878 //
jpayne@69 879 // * Node: either a DataNode that directly has the std::pair<key, val> as member,
jpayne@69 880 // or a DataNode with a pointer to std::pair<key,val>. Which DataNode representation to use
jpayne@69 881 // depends on how fast the swap() operation is. Heuristically, this is automatically choosen
jpayne@69 882 // based on sizeof(). there are always 2^n Nodes.
jpayne@69 883 //
jpayne@69 884 // * info: Each Node in the map has a corresponding info byte, so there are 2^n info bytes.
jpayne@69 885 // Each byte is initialized to 0, meaning the corresponding Node is empty. Set to 1 means the
jpayne@69 886 // corresponding node contains data. Set to 2 means the corresponding Node is filled, but it
jpayne@69 887 // actually belongs to the previous position and was pushed out because that place is already
jpayne@69 888 // taken.
jpayne@69 889 //
jpayne@69 890 // * infoSentinel: Sentinel byte set to 1, so that iterator's ++ can stop at end() without the
jpayne@69 891 // need for a idx variable.
jpayne@69 892 //
jpayne@69 893 // According to STL, order of templates has effect on throughput. That's why I've moved the
jpayne@69 894 // boolean to the front.
jpayne@69 895 // https://www.reddit.com/r/cpp/comments/ahp6iu/compile_time_binary_size_reductions_and_cs_future/eeguck4/
jpayne@69 896 template <bool IsFlat, size_t MaxLoadFactor100, typename Key, typename T, typename Hash,
jpayne@69 897 typename KeyEqual>
jpayne@69 898 class Table
jpayne@69 899 : public WrapHash<Hash>,
jpayne@69 900 public WrapKeyEqual<KeyEqual>,
jpayne@69 901 detail::NodeAllocator<
jpayne@69 902 typename std::conditional<
jpayne@69 903 std::is_void<T>::value, Key,
jpayne@69 904 robin_hood::pair<typename std::conditional<IsFlat, Key, Key const>::type, T>>::type,
jpayne@69 905 4, 16384, IsFlat> {
jpayne@69 906 public:
jpayne@69 907 static constexpr bool is_flat = IsFlat;
jpayne@69 908 static constexpr bool is_map = !std::is_void<T>::value;
jpayne@69 909 static constexpr bool is_set = !is_map;
jpayne@69 910 static constexpr bool is_transparent =
jpayne@69 911 has_is_transparent<Hash>::value && has_is_transparent<KeyEqual>::value;
jpayne@69 912
jpayne@69 913 using key_type = Key;
jpayne@69 914 using mapped_type = T;
jpayne@69 915 using value_type = typename std::conditional<
jpayne@69 916 is_set, Key,
jpayne@69 917 robin_hood::pair<typename std::conditional<is_flat, Key, Key const>::type, T>>::type;
jpayne@69 918 using size_type = size_t;
jpayne@69 919 using hasher = Hash;
jpayne@69 920 using key_equal = KeyEqual;
jpayne@69 921 using Self = Table<IsFlat, MaxLoadFactor100, key_type, mapped_type, hasher, key_equal>;
jpayne@69 922
jpayne@69 923 private:
jpayne@69 924 static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100,
jpayne@69 925 "MaxLoadFactor100 needs to be >10 && < 100");
jpayne@69 926
jpayne@69 927 using WHash = WrapHash<Hash>;
jpayne@69 928 using WKeyEqual = WrapKeyEqual<KeyEqual>;
jpayne@69 929
jpayne@69 930 // configuration defaults
jpayne@69 931
jpayne@69 932 // make sure we have 8 elements, needed to quickly rehash mInfo
jpayne@69 933 static constexpr size_t InitialNumElements = sizeof(uint64_t);
jpayne@69 934 static constexpr uint32_t InitialInfoNumBits = 5;
jpayne@69 935 static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits;
jpayne@69 936 static constexpr size_t InfoMask = InitialInfoInc - 1U;
jpayne@69 937 static constexpr uint8_t InitialInfoHashShift = 0;
jpayne@69 938 using DataPool = detail::NodeAllocator<value_type, 4, 16384, IsFlat>;
jpayne@69 939
jpayne@69 940 // type needs to be wider than uint8_t.
jpayne@69 941 using InfoType = uint32_t;
jpayne@69 942
jpayne@69 943 // DataNode ////////////////////////////////////////////////////////
jpayne@69 944
jpayne@69 945 // Primary template for the data node. We have special implementations for small and big
jpayne@69 946 // objects. For large objects it is assumed that swap() is fairly slow, so we allocate these
jpayne@69 947 // on the heap so swap merely swaps a pointer.
jpayne@69 948 template <typename M, bool>
jpayne@69 949 class DataNode {};
jpayne@69 950
jpayne@69 951 // Small: just allocate on the stack.
jpayne@69 952 template <typename M>
jpayne@69 953 class DataNode<M, true> final {
jpayne@69 954 public:
jpayne@69 955 template <typename... Args>
jpayne@69 956 explicit DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, Args&&... args) noexcept(
jpayne@69 957 noexcept(value_type(std::forward<Args>(args)...)))
jpayne@69 958 : mData(std::forward<Args>(args)...) {}
jpayne@69 959
jpayne@69 960 DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode<M, true>&& n) noexcept(
jpayne@69 961 std::is_nothrow_move_constructible<value_type>::value)
jpayne@69 962 : mData(std::move(n.mData)) {}
jpayne@69 963
jpayne@69 964 // doesn't do anything
jpayne@69 965 void destroy(M& ROBIN_HOOD_UNUSED(map) /*unused*/) noexcept {}
jpayne@69 966 void destroyDoNotDeallocate() noexcept {}
jpayne@69 967
jpayne@69 968 value_type const* operator->() const noexcept {
jpayne@69 969 return &mData;
jpayne@69 970 }
jpayne@69 971 value_type* operator->() noexcept {
jpayne@69 972 return &mData;
jpayne@69 973 }
jpayne@69 974
jpayne@69 975 const value_type& operator*() const noexcept {
jpayne@69 976 return mData;
jpayne@69 977 }
jpayne@69 978
jpayne@69 979 value_type& operator*() noexcept {
jpayne@69 980 return mData;
jpayne@69 981 }
jpayne@69 982
jpayne@69 983 template <typename VT = value_type>
jpayne@69 984 ROBIN_HOOD(NODISCARD)
jpayne@69 985 typename std::enable_if<is_map, typename VT::first_type&>::type getFirst() noexcept {
jpayne@69 986 return mData.first;
jpayne@69 987 }
jpayne@69 988 template <typename VT = value_type>
jpayne@69 989 ROBIN_HOOD(NODISCARD)
jpayne@69 990 typename std::enable_if<is_set, VT&>::type getFirst() noexcept {
jpayne@69 991 return mData;
jpayne@69 992 }
jpayne@69 993
jpayne@69 994 template <typename VT = value_type>
jpayne@69 995 ROBIN_HOOD(NODISCARD)
jpayne@69 996 typename std::enable_if<is_map, typename VT::first_type const&>::type
jpayne@69 997 getFirst() const noexcept {
jpayne@69 998 return mData.first;
jpayne@69 999 }
jpayne@69 1000 template <typename VT = value_type>
jpayne@69 1001 ROBIN_HOOD(NODISCARD)
jpayne@69 1002 typename std::enable_if<is_set, VT const&>::type getFirst() const noexcept {
jpayne@69 1003 return mData;
jpayne@69 1004 }
jpayne@69 1005
jpayne@69 1006 template <typename MT = mapped_type>
jpayne@69 1007 ROBIN_HOOD(NODISCARD)
jpayne@69 1008 typename std::enable_if<is_map, MT&>::type getSecond() noexcept {
jpayne@69 1009 return mData.second;
jpayne@69 1010 }
jpayne@69 1011
jpayne@69 1012 template <typename MT = mapped_type>
jpayne@69 1013 ROBIN_HOOD(NODISCARD)
jpayne@69 1014 typename std::enable_if<is_set, MT const&>::type getSecond() const noexcept {
jpayne@69 1015 return mData.second;
jpayne@69 1016 }
jpayne@69 1017
jpayne@69 1018 void swap(DataNode<M, true>& o) noexcept(
jpayne@69 1019 noexcept(std::declval<value_type>().swap(std::declval<value_type>()))) {
jpayne@69 1020 mData.swap(o.mData);
jpayne@69 1021 }
jpayne@69 1022
jpayne@69 1023 private:
jpayne@69 1024 value_type mData;
jpayne@69 1025 };
jpayne@69 1026
jpayne@69 1027 // big object: allocate on heap.
jpayne@69 1028 template <typename M>
jpayne@69 1029 class DataNode<M, false> {
jpayne@69 1030 public:
jpayne@69 1031 template <typename... Args>
jpayne@69 1032 explicit DataNode(M& map, Args&&... args)
jpayne@69 1033 : mData(map.allocate()) {
jpayne@69 1034 ::new (static_cast<void*>(mData)) value_type(std::forward<Args>(args)...);
jpayne@69 1035 }
jpayne@69 1036
jpayne@69 1037 DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode<M, false>&& n) noexcept
jpayne@69 1038 : mData(std::move(n.mData)) {}
jpayne@69 1039
jpayne@69 1040 void destroy(M& map) noexcept {
jpayne@69 1041 // don't deallocate, just put it into list of datapool.
jpayne@69 1042 mData->~value_type();
jpayne@69 1043 map.deallocate(mData);
jpayne@69 1044 }
jpayne@69 1045
jpayne@69 1046 void destroyDoNotDeallocate() noexcept {
jpayne@69 1047 mData->~value_type();
jpayne@69 1048 }
jpayne@69 1049
jpayne@69 1050 value_type const* operator->() const noexcept {
jpayne@69 1051 return mData;
jpayne@69 1052 }
jpayne@69 1053
jpayne@69 1054 value_type* operator->() noexcept {
jpayne@69 1055 return mData;
jpayne@69 1056 }
jpayne@69 1057
jpayne@69 1058 const value_type& operator*() const {
jpayne@69 1059 return *mData;
jpayne@69 1060 }
jpayne@69 1061
jpayne@69 1062 value_type& operator*() {
jpayne@69 1063 return *mData;
jpayne@69 1064 }
jpayne@69 1065
jpayne@69 1066 template <typename VT = value_type>
jpayne@69 1067 ROBIN_HOOD(NODISCARD)
jpayne@69 1068 typename std::enable_if<is_map, typename VT::first_type&>::type getFirst() noexcept {
jpayne@69 1069 return mData->first;
jpayne@69 1070 }
jpayne@69 1071 template <typename VT = value_type>
jpayne@69 1072 ROBIN_HOOD(NODISCARD)
jpayne@69 1073 typename std::enable_if<is_set, VT&>::type getFirst() noexcept {
jpayne@69 1074 return *mData;
jpayne@69 1075 }
jpayne@69 1076
jpayne@69 1077 template <typename VT = value_type>
jpayne@69 1078 ROBIN_HOOD(NODISCARD)
jpayne@69 1079 typename std::enable_if<is_map, typename VT::first_type const&>::type
jpayne@69 1080 getFirst() const noexcept {
jpayne@69 1081 return mData->first;
jpayne@69 1082 }
jpayne@69 1083 template <typename VT = value_type>
jpayne@69 1084 ROBIN_HOOD(NODISCARD)
jpayne@69 1085 typename std::enable_if<is_set, VT const&>::type getFirst() const noexcept {
jpayne@69 1086 return *mData;
jpayne@69 1087 }
jpayne@69 1088
jpayne@69 1089 template <typename MT = mapped_type>
jpayne@69 1090 ROBIN_HOOD(NODISCARD)
jpayne@69 1091 typename std::enable_if<is_map, MT&>::type getSecond() noexcept {
jpayne@69 1092 return mData->second;
jpayne@69 1093 }
jpayne@69 1094
jpayne@69 1095 template <typename MT = mapped_type>
jpayne@69 1096 ROBIN_HOOD(NODISCARD)
jpayne@69 1097 typename std::enable_if<is_map, MT const&>::type getSecond() const noexcept {
jpayne@69 1098 return mData->second;
jpayne@69 1099 }
jpayne@69 1100
jpayne@69 1101 void swap(DataNode<M, false>& o) noexcept {
jpayne@69 1102 using std::swap;
jpayne@69 1103 swap(mData, o.mData);
jpayne@69 1104 }
jpayne@69 1105
jpayne@69 1106 private:
jpayne@69 1107 value_type* mData;
jpayne@69 1108 };
jpayne@69 1109
jpayne@69 1110 using Node = DataNode<Self, IsFlat>;
jpayne@69 1111
jpayne@69 1112 // helpers for doInsert: extract first entry (only const required)
jpayne@69 1113 ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(Node const& n) const noexcept {
jpayne@69 1114 return n.getFirst();
jpayne@69 1115 }
jpayne@69 1116
jpayne@69 1117 // in case we have void mapped_type, we are not using a pair, thus we just route k through.
jpayne@69 1118 // No need to disable this because it's just not used if not applicable.
jpayne@69 1119 ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(key_type const& k) const noexcept {
jpayne@69 1120 return k;
jpayne@69 1121 }
jpayne@69 1122
jpayne@69 1123 // in case we have non-void mapped_type, we have a standard robin_hood::pair
jpayne@69 1124 template <typename Q = mapped_type>
jpayne@69 1125 ROBIN_HOOD(NODISCARD)
jpayne@69 1126 typename std::enable_if<!std::is_void<Q>::value, key_type const&>::type
jpayne@69 1127 getFirstConst(value_type const& vt) const noexcept {
jpayne@69 1128 return vt.first;
jpayne@69 1129 }
jpayne@69 1130
jpayne@69 1131 // Cloner //////////////////////////////////////////////////////////
jpayne@69 1132
jpayne@69 1133 template <typename M, bool UseMemcpy>
jpayne@69 1134 struct Cloner;
jpayne@69 1135
jpayne@69 1136 // fast path: Just copy data, without allocating anything.
jpayne@69 1137 template <typename M>
jpayne@69 1138 struct Cloner<M, true> {
jpayne@69 1139 void operator()(M const& source, M& target) const {
jpayne@69 1140 auto const* const src = reinterpret_cast<char const*>(source.mKeyVals);
jpayne@69 1141 auto* tgt = reinterpret_cast<char*>(target.mKeyVals);
jpayne@69 1142 auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1);
jpayne@69 1143 std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt);
jpayne@69 1144 }
jpayne@69 1145 };
jpayne@69 1146
jpayne@69 1147 template <typename M>
jpayne@69 1148 struct Cloner<M, false> {
jpayne@69 1149 void operator()(M const& s, M& t) const {
jpayne@69 1150 auto const numElementsWithBuffer = t.calcNumElementsWithBuffer(t.mMask + 1);
jpayne@69 1151 std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(numElementsWithBuffer), t.mInfo);
jpayne@69 1152
jpayne@69 1153 for (size_t i = 0; i < numElementsWithBuffer; ++i) {
jpayne@69 1154 if (t.mInfo[i]) {
jpayne@69 1155 ::new (static_cast<void*>(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]);
jpayne@69 1156 }
jpayne@69 1157 }
jpayne@69 1158 }
jpayne@69 1159 };
jpayne@69 1160
jpayne@69 1161 // Destroyer ///////////////////////////////////////////////////////
jpayne@69 1162
jpayne@69 1163 template <typename M, bool IsFlatAndTrivial>
jpayne@69 1164 struct Destroyer {};
jpayne@69 1165
jpayne@69 1166 template <typename M>
jpayne@69 1167 struct Destroyer<M, true> {
jpayne@69 1168 void nodes(M& m) const noexcept {
jpayne@69 1169 m.mNumElements = 0;
jpayne@69 1170 }
jpayne@69 1171
jpayne@69 1172 void nodesDoNotDeallocate(M& m) const noexcept {
jpayne@69 1173 m.mNumElements = 0;
jpayne@69 1174 }
jpayne@69 1175 };
jpayne@69 1176
jpayne@69 1177 template <typename M>
jpayne@69 1178 struct Destroyer<M, false> {
jpayne@69 1179 void nodes(M& m) const noexcept {
jpayne@69 1180 m.mNumElements = 0;
jpayne@69 1181 // clear also resets mInfo to 0, that's sometimes not necessary.
jpayne@69 1182 auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1);
jpayne@69 1183
jpayne@69 1184 for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) {
jpayne@69 1185 if (0 != m.mInfo[idx]) {
jpayne@69 1186 Node& n = m.mKeyVals[idx];
jpayne@69 1187 n.destroy(m);
jpayne@69 1188 n.~Node();
jpayne@69 1189 }
jpayne@69 1190 }
jpayne@69 1191 }
jpayne@69 1192
jpayne@69 1193 void nodesDoNotDeallocate(M& m) const noexcept {
jpayne@69 1194 m.mNumElements = 0;
jpayne@69 1195 // clear also resets mInfo to 0, that's sometimes not necessary.
jpayne@69 1196 auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1);
jpayne@69 1197 for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) {
jpayne@69 1198 if (0 != m.mInfo[idx]) {
jpayne@69 1199 Node& n = m.mKeyVals[idx];
jpayne@69 1200 n.destroyDoNotDeallocate();
jpayne@69 1201 n.~Node();
jpayne@69 1202 }
jpayne@69 1203 }
jpayne@69 1204 }
jpayne@69 1205 };
jpayne@69 1206
jpayne@69 1207 // Iter ////////////////////////////////////////////////////////////
jpayne@69 1208
jpayne@69 1209 struct fast_forward_tag {};
jpayne@69 1210
jpayne@69 1211 // generic iterator for both const_iterator and iterator.
jpayne@69 1212 template <bool IsConst>
jpayne@69 1213 // NOLINTNEXTLINE(hicpp-special-member-functions,cppcoreguidelines-special-member-functions)
jpayne@69 1214 class Iter {
jpayne@69 1215 private:
jpayne@69 1216 using NodePtr = typename std::conditional<IsConst, Node const*, Node*>::type;
jpayne@69 1217
jpayne@69 1218 public:
jpayne@69 1219 using difference_type = std::ptrdiff_t;
jpayne@69 1220 using value_type = typename Self::value_type;
jpayne@69 1221 using reference = typename std::conditional<IsConst, value_type const&, value_type&>::type;
jpayne@69 1222 using pointer = typename std::conditional<IsConst, value_type const*, value_type*>::type;
jpayne@69 1223 using iterator_category = std::forward_iterator_tag;
jpayne@69 1224
jpayne@69 1225 // default constructed iterator can be compared to itself, but WON'T return true when
jpayne@69 1226 // compared to end().
jpayne@69 1227 Iter() = default;
jpayne@69 1228
jpayne@69 1229 // Rule of zero: nothing specified. The conversion constructor is only enabled for
jpayne@69 1230 // iterator to const_iterator, so it doesn't accidentally work as a copy ctor.
jpayne@69 1231
jpayne@69 1232 // Conversion constructor from iterator to const_iterator.
jpayne@69 1233 template <bool OtherIsConst,
jpayne@69 1234 typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
jpayne@69 1235 // NOLINTNEXTLINE(hicpp-explicit-conversions)
jpayne@69 1236 Iter(Iter<OtherIsConst> const& other) noexcept
jpayne@69 1237 : mKeyVals(other.mKeyVals)
jpayne@69 1238 , mInfo(other.mInfo) {}
jpayne@69 1239
jpayne@69 1240 Iter(NodePtr valPtr, uint8_t const* infoPtr) noexcept
jpayne@69 1241 : mKeyVals(valPtr)
jpayne@69 1242 , mInfo(infoPtr) {}
jpayne@69 1243
jpayne@69 1244 Iter(NodePtr valPtr, uint8_t const* infoPtr,
jpayne@69 1245 fast_forward_tag ROBIN_HOOD_UNUSED(tag) /*unused*/) noexcept
jpayne@69 1246 : mKeyVals(valPtr)
jpayne@69 1247 , mInfo(infoPtr) {
jpayne@69 1248 fastForward();
jpayne@69 1249 }
jpayne@69 1250
jpayne@69 1251 template <bool OtherIsConst,
jpayne@69 1252 typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
jpayne@69 1253 Iter& operator=(Iter<OtherIsConst> const& other) noexcept {
jpayne@69 1254 mKeyVals = other.mKeyVals;
jpayne@69 1255 mInfo = other.mInfo;
jpayne@69 1256 return *this;
jpayne@69 1257 }
jpayne@69 1258
jpayne@69 1259 // prefix increment. Undefined behavior if we are at end()!
jpayne@69 1260 Iter& operator++() noexcept {
jpayne@69 1261 mInfo++;
jpayne@69 1262 mKeyVals++;
jpayne@69 1263 fastForward();
jpayne@69 1264 return *this;
jpayne@69 1265 }
jpayne@69 1266
jpayne@69 1267 Iter operator++(int) noexcept {
jpayne@69 1268 Iter tmp = *this;
jpayne@69 1269 ++(*this);
jpayne@69 1270 return tmp;
jpayne@69 1271 }
jpayne@69 1272
jpayne@69 1273 reference operator*() const {
jpayne@69 1274 return **mKeyVals;
jpayne@69 1275 }
jpayne@69 1276
jpayne@69 1277 pointer operator->() const {
jpayne@69 1278 return &**mKeyVals;
jpayne@69 1279 }
jpayne@69 1280
jpayne@69 1281 template <bool O>
jpayne@69 1282 bool operator==(Iter<O> const& o) const noexcept {
jpayne@69 1283 return mKeyVals == o.mKeyVals;
jpayne@69 1284 }
jpayne@69 1285
jpayne@69 1286 template <bool O>
jpayne@69 1287 bool operator!=(Iter<O> const& o) const noexcept {
jpayne@69 1288 return mKeyVals != o.mKeyVals;
jpayne@69 1289 }
jpayne@69 1290
jpayne@69 1291 private:
jpayne@69 1292 // fast forward to the next non-free info byte
jpayne@69 1293 // I've tried a few variants that don't depend on intrinsics, but unfortunately they are
jpayne@69 1294 // quite a bit slower than this one. So I've reverted that change again. See map_benchmark.
jpayne@69 1295 void fastForward() noexcept {
jpayne@69 1296 size_t n = 0;
jpayne@69 1297 while (0U == (n = detail::unaligned_load<size_t>(mInfo))) {
jpayne@69 1298 mInfo += sizeof(size_t);
jpayne@69 1299 mKeyVals += sizeof(size_t);
jpayne@69 1300 }
jpayne@69 1301 #if defined(ROBIN_HOOD_DISABLE_INTRINSICS)
jpayne@69 1302 // we know for certain that within the next 8 bytes we'll find a non-zero one.
jpayne@69 1303 if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load<uint32_t>(mInfo))) {
jpayne@69 1304 mInfo += 4;
jpayne@69 1305 mKeyVals += 4;
jpayne@69 1306 }
jpayne@69 1307 if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load<uint16_t>(mInfo))) {
jpayne@69 1308 mInfo += 2;
jpayne@69 1309 mKeyVals += 2;
jpayne@69 1310 }
jpayne@69 1311 if (ROBIN_HOOD_UNLIKELY(0U == *mInfo)) {
jpayne@69 1312 mInfo += 1;
jpayne@69 1313 mKeyVals += 1;
jpayne@69 1314 }
jpayne@69 1315 #else
jpayne@69 1316 # if ROBIN_HOOD(LITTLE_ENDIAN)
jpayne@69 1317 auto inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8;
jpayne@69 1318 # else
jpayne@69 1319 auto inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8;
jpayne@69 1320 # endif
jpayne@69 1321 mInfo += inc;
jpayne@69 1322 mKeyVals += inc;
jpayne@69 1323 #endif
jpayne@69 1324 }
jpayne@69 1325
jpayne@69 1326 friend class Table<IsFlat, MaxLoadFactor100, key_type, mapped_type, hasher, key_equal>;
jpayne@69 1327 NodePtr mKeyVals{nullptr};
jpayne@69 1328 uint8_t const* mInfo{nullptr};
jpayne@69 1329 };
jpayne@69 1330
jpayne@69 1331 ////////////////////////////////////////////////////////////////////
jpayne@69 1332
jpayne@69 1333 // highly performance relevant code.
jpayne@69 1334 // Lower bits are used for indexing into the array (2^n size)
jpayne@69 1335 // The upper 1-5 bits need to be a reasonable good hash, to save comparisons.
jpayne@69 1336 template <typename HashKey>
jpayne@69 1337 void keyToIdx(HashKey&& key, size_t* idx, InfoType* info) const {
jpayne@69 1338 // for a user-specified hash that is *not* robin_hood::hash, apply robin_hood::hash as
jpayne@69 1339 // an additional mixing step. This serves as a bad hash prevention, if the given data is
jpayne@69 1340 // badly mixed.
jpayne@69 1341 using Mix =
jpayne@69 1342 typename std::conditional<std::is_same<::robin_hood::hash<key_type>, hasher>::value,
jpayne@69 1343 ::robin_hood::detail::identity_hash<size_t>,
jpayne@69 1344 ::robin_hood::hash<size_t>>::type;
jpayne@69 1345
jpayne@69 1346 // the lower InitialInfoNumBits are reserved for info.
jpayne@69 1347 auto h = Mix{}(WHash::operator()(key));
jpayne@69 1348 *info = mInfoInc + static_cast<InfoType>((h & InfoMask) >> mInfoHashShift);
jpayne@69 1349 *idx = (h >> InitialInfoNumBits) & mMask;
jpayne@69 1350 }
jpayne@69 1351
jpayne@69 1352 // forwards the index by one, wrapping around at the end
jpayne@69 1353 void next(InfoType* info, size_t* idx) const noexcept {
jpayne@69 1354 *idx = *idx + 1;
jpayne@69 1355 *info += mInfoInc;
jpayne@69 1356 }
jpayne@69 1357
jpayne@69 1358 void nextWhileLess(InfoType* info, size_t* idx) const noexcept {
jpayne@69 1359 // unrolling this by hand did not bring any speedups.
jpayne@69 1360 while (*info < mInfo[*idx]) {
jpayne@69 1361 next(info, idx);
jpayne@69 1362 }
jpayne@69 1363 }
jpayne@69 1364
jpayne@69 1365 // Shift everything up by one element. Tries to move stuff around.
jpayne@69 1366 void
jpayne@69 1367 shiftUp(size_t startIdx,
jpayne@69 1368 size_t const insertion_idx) noexcept(std::is_nothrow_move_assignable<Node>::value) {
jpayne@69 1369 auto idx = startIdx;
jpayne@69 1370 ::new (static_cast<void*>(mKeyVals + idx)) Node(std::move(mKeyVals[idx - 1]));
jpayne@69 1371 while (--idx != insertion_idx) {
jpayne@69 1372 mKeyVals[idx] = std::move(mKeyVals[idx - 1]);
jpayne@69 1373 }
jpayne@69 1374
jpayne@69 1375 idx = startIdx;
jpayne@69 1376 while (idx != insertion_idx) {
jpayne@69 1377 ROBIN_HOOD_COUNT(shiftUp)
jpayne@69 1378 mInfo[idx] = static_cast<uint8_t>(mInfo[idx - 1] + mInfoInc);
jpayne@69 1379 if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) {
jpayne@69 1380 mMaxNumElementsAllowed = 0;
jpayne@69 1381 }
jpayne@69 1382 --idx;
jpayne@69 1383 }
jpayne@69 1384 }
jpayne@69 1385
jpayne@69 1386 void shiftDown(size_t idx) noexcept(std::is_nothrow_move_assignable<Node>::value) {
jpayne@69 1387 // until we find one that is either empty or has zero offset.
jpayne@69 1388 // TODO(martinus) we don't need to move everything, just the last one for the same
jpayne@69 1389 // bucket.
jpayne@69 1390 mKeyVals[idx].destroy(*this);
jpayne@69 1391
jpayne@69 1392 // until we find one that is either empty or has zero offset.
jpayne@69 1393 while (mInfo[idx + 1] >= 2 * mInfoInc) {
jpayne@69 1394 ROBIN_HOOD_COUNT(shiftDown)
jpayne@69 1395 mInfo[idx] = static_cast<uint8_t>(mInfo[idx + 1] - mInfoInc);
jpayne@69 1396 mKeyVals[idx] = std::move(mKeyVals[idx + 1]);
jpayne@69 1397 ++idx;
jpayne@69 1398 }
jpayne@69 1399
jpayne@69 1400 mInfo[idx] = 0;
jpayne@69 1401 // don't destroy, we've moved it
jpayne@69 1402 // mKeyVals[idx].destroy(*this);
jpayne@69 1403 mKeyVals[idx].~Node();
jpayne@69 1404 }
jpayne@69 1405
jpayne@69 1406 // copy of find(), except that it returns iterator instead of const_iterator.
jpayne@69 1407 template <typename Other>
jpayne@69 1408 ROBIN_HOOD(NODISCARD)
jpayne@69 1409 size_t findIdx(Other const& key) const {
jpayne@69 1410 size_t idx{};
jpayne@69 1411 InfoType info{};
jpayne@69 1412 keyToIdx(key, &idx, &info);
jpayne@69 1413
jpayne@69 1414 do {
jpayne@69 1415 // unrolling this twice gives a bit of a speedup. More unrolling did not help.
jpayne@69 1416 if (info == mInfo[idx] &&
jpayne@69 1417 ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) {
jpayne@69 1418 return idx;
jpayne@69 1419 }
jpayne@69 1420 next(&info, &idx);
jpayne@69 1421 if (info == mInfo[idx] &&
jpayne@69 1422 ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) {
jpayne@69 1423 return idx;
jpayne@69 1424 }
jpayne@69 1425 next(&info, &idx);
jpayne@69 1426 } while (info <= mInfo[idx]);
jpayne@69 1427
jpayne@69 1428 // nothing found!
jpayne@69 1429 return mMask == 0 ? 0
jpayne@69 1430 : static_cast<size_t>(std::distance(
jpayne@69 1431 mKeyVals, reinterpret_cast_no_cast_align_warning<Node*>(mInfo)));
jpayne@69 1432 }
jpayne@69 1433
jpayne@69 1434 void cloneData(const Table& o) {
jpayne@69 1435 Cloner<Table, IsFlat && ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(Node)>()(o, *this);
jpayne@69 1436 }
jpayne@69 1437
jpayne@69 1438 // inserts a keyval that is guaranteed to be new, e.g. when the hashmap is resized.
jpayne@69 1439 // @return index where the element was created
jpayne@69 1440 size_t insert_move(Node&& keyval) {
jpayne@69 1441 // we don't retry, fail if overflowing
jpayne@69 1442 // don't need to check max num elements
jpayne@69 1443 if (0 == mMaxNumElementsAllowed && !try_increase_info()) {
jpayne@69 1444 throwOverflowError(); // impossible to reach LCOV_EXCL_LINE
jpayne@69 1445 }
jpayne@69 1446
jpayne@69 1447 size_t idx{};
jpayne@69 1448 InfoType info{};
jpayne@69 1449 keyToIdx(keyval.getFirst(), &idx, &info);
jpayne@69 1450
jpayne@69 1451 // skip forward. Use <= because we are certain that the element is not there.
jpayne@69 1452 while (info <= mInfo[idx]) {
jpayne@69 1453 idx = idx + 1;
jpayne@69 1454 info += mInfoInc;
jpayne@69 1455 }
jpayne@69 1456
jpayne@69 1457 // key not found, so we are now exactly where we want to insert it.
jpayne@69 1458 auto const insertion_idx = idx;
jpayne@69 1459 auto const insertion_info = static_cast<uint8_t>(info);
jpayne@69 1460 if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
jpayne@69 1461 mMaxNumElementsAllowed = 0;
jpayne@69 1462 }
jpayne@69 1463
jpayne@69 1464 // find an empty spot
jpayne@69 1465 while (0 != mInfo[idx]) {
jpayne@69 1466 next(&info, &idx);
jpayne@69 1467 }
jpayne@69 1468
jpayne@69 1469 auto& l = mKeyVals[insertion_idx];
jpayne@69 1470 if (idx == insertion_idx) {
jpayne@69 1471 ::new (static_cast<void*>(&l)) Node(std::move(keyval));
jpayne@69 1472 } else {
jpayne@69 1473 shiftUp(idx, insertion_idx);
jpayne@69 1474 l = std::move(keyval);
jpayne@69 1475 }
jpayne@69 1476
jpayne@69 1477 // put at empty spot
jpayne@69 1478 mInfo[insertion_idx] = insertion_info;
jpayne@69 1479
jpayne@69 1480 ++mNumElements;
jpayne@69 1481 return insertion_idx;
jpayne@69 1482 }
jpayne@69 1483
jpayne@69 1484 public:
jpayne@69 1485 using iterator = Iter<false>;
jpayne@69 1486 using const_iterator = Iter<true>;
jpayne@69 1487
jpayne@69 1488 Table() noexcept(noexcept(Hash()) && noexcept(KeyEqual()))
jpayne@69 1489 : WHash()
jpayne@69 1490 , WKeyEqual() {
jpayne@69 1491 ROBIN_HOOD_TRACE(this)
jpayne@69 1492 }
jpayne@69 1493
jpayne@69 1494 // Creates an empty hash map. Nothing is allocated yet, this happens at the first insert.
jpayne@69 1495 // This tremendously speeds up ctor & dtor of a map that never receives an element. The
jpayne@69 1496 // penalty is payed at the first insert, and not before. Lookup of this empty map works
jpayne@69 1497 // because everybody points to DummyInfoByte::b. parameter bucket_count is dictated by the
jpayne@69 1498 // standard, but we can ignore it.
jpayne@69 1499 explicit Table(
jpayne@69 1500 size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/, const Hash& h = Hash{},
jpayne@69 1501 const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && noexcept(KeyEqual(equal)))
jpayne@69 1502 : WHash(h)
jpayne@69 1503 , WKeyEqual(equal) {
jpayne@69 1504 ROBIN_HOOD_TRACE(this)
jpayne@69 1505 }
jpayne@69 1506
jpayne@69 1507 template <typename Iter>
jpayne@69 1508 Table(Iter first, Iter last, size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0,
jpayne@69 1509 const Hash& h = Hash{}, const KeyEqual& equal = KeyEqual{})
jpayne@69 1510 : WHash(h)
jpayne@69 1511 , WKeyEqual(equal) {
jpayne@69 1512 ROBIN_HOOD_TRACE(this)
jpayne@69 1513 insert(first, last);
jpayne@69 1514 }
jpayne@69 1515
jpayne@69 1516 Table(std::initializer_list<value_type> initlist,
jpayne@69 1517 size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, const Hash& h = Hash{},
jpayne@69 1518 const KeyEqual& equal = KeyEqual{})
jpayne@69 1519 : WHash(h)
jpayne@69 1520 , WKeyEqual(equal) {
jpayne@69 1521 ROBIN_HOOD_TRACE(this)
jpayne@69 1522 insert(initlist.begin(), initlist.end());
jpayne@69 1523 }
jpayne@69 1524
jpayne@69 1525 Table(Table&& o) noexcept
jpayne@69 1526 : WHash(std::move(static_cast<WHash&>(o)))
jpayne@69 1527 , WKeyEqual(std::move(static_cast<WKeyEqual&>(o)))
jpayne@69 1528 , DataPool(std::move(static_cast<DataPool&>(o))) {
jpayne@69 1529 ROBIN_HOOD_TRACE(this)
jpayne@69 1530 if (o.mMask) {
jpayne@69 1531 mKeyVals = std::move(o.mKeyVals);
jpayne@69 1532 mInfo = std::move(o.mInfo);
jpayne@69 1533 mNumElements = std::move(o.mNumElements);
jpayne@69 1534 mMask = std::move(o.mMask);
jpayne@69 1535 mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed);
jpayne@69 1536 mInfoInc = std::move(o.mInfoInc);
jpayne@69 1537 mInfoHashShift = std::move(o.mInfoHashShift);
jpayne@69 1538 // set other's mask to 0 so its destructor won't do anything
jpayne@69 1539 o.init();
jpayne@69 1540 }
jpayne@69 1541 }
jpayne@69 1542
jpayne@69 1543 Table& operator=(Table&& o) noexcept {
jpayne@69 1544 ROBIN_HOOD_TRACE(this)
jpayne@69 1545 if (&o != this) {
jpayne@69 1546 if (o.mMask) {
jpayne@69 1547 // only move stuff if the other map actually has some data
jpayne@69 1548 destroy();
jpayne@69 1549 mKeyVals = std::move(o.mKeyVals);
jpayne@69 1550 mInfo = std::move(o.mInfo);
jpayne@69 1551 mNumElements = std::move(o.mNumElements);
jpayne@69 1552 mMask = std::move(o.mMask);
jpayne@69 1553 mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed);
jpayne@69 1554 mInfoInc = std::move(o.mInfoInc);
jpayne@69 1555 mInfoHashShift = std::move(o.mInfoHashShift);
jpayne@69 1556 WHash::operator=(std::move(static_cast<WHash&>(o)));
jpayne@69 1557 WKeyEqual::operator=(std::move(static_cast<WKeyEqual&>(o)));
jpayne@69 1558 DataPool::operator=(std::move(static_cast<DataPool&>(o)));
jpayne@69 1559
jpayne@69 1560 o.init();
jpayne@69 1561
jpayne@69 1562 } else {
jpayne@69 1563 // nothing in the other map => just clear us.
jpayne@69 1564 clear();
jpayne@69 1565 }
jpayne@69 1566 }
jpayne@69 1567 return *this;
jpayne@69 1568 }
jpayne@69 1569
jpayne@69 1570 Table(const Table& o)
jpayne@69 1571 : WHash(static_cast<const WHash&>(o))
jpayne@69 1572 , WKeyEqual(static_cast<const WKeyEqual&>(o))
jpayne@69 1573 , DataPool(static_cast<const DataPool&>(o)) {
jpayne@69 1574 ROBIN_HOOD_TRACE(this)
jpayne@69 1575 if (!o.empty()) {
jpayne@69 1576 // not empty: create an exact copy. it is also possible to just iterate through all
jpayne@69 1577 // elements and insert them, but copying is probably faster.
jpayne@69 1578
jpayne@69 1579 auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1);
jpayne@69 1580 auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer);
jpayne@69 1581
jpayne@69 1582 ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal("
jpayne@69 1583 << numElementsWithBuffer << ")")
jpayne@69 1584 mKeyVals = static_cast<Node*>(
jpayne@69 1585 detail::assertNotNull<std::bad_alloc>(std::malloc(numBytesTotal)));
jpayne@69 1586 // no need for calloc because clonData does memcpy
jpayne@69 1587 mInfo = reinterpret_cast<uint8_t*>(mKeyVals + numElementsWithBuffer);
jpayne@69 1588 mNumElements = o.mNumElements;
jpayne@69 1589 mMask = o.mMask;
jpayne@69 1590 mMaxNumElementsAllowed = o.mMaxNumElementsAllowed;
jpayne@69 1591 mInfoInc = o.mInfoInc;
jpayne@69 1592 mInfoHashShift = o.mInfoHashShift;
jpayne@69 1593 cloneData(o);
jpayne@69 1594 }
jpayne@69 1595 }
jpayne@69 1596
jpayne@69 1597 // Creates a copy of the given map. Copy constructor of each entry is used.
jpayne@69 1598 // Not sure why clang-tidy thinks this doesn't handle self assignment, it does
jpayne@69 1599 // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp)
jpayne@69 1600 Table& operator=(Table const& o) {
jpayne@69 1601 ROBIN_HOOD_TRACE(this)
jpayne@69 1602 if (&o == this) {
jpayne@69 1603 // prevent assigning of itself
jpayne@69 1604 return *this;
jpayne@69 1605 }
jpayne@69 1606
jpayne@69 1607 // we keep using the old allocator and not assign the new one, because we want to keep
jpayne@69 1608 // the memory available. when it is the same size.
jpayne@69 1609 if (o.empty()) {
jpayne@69 1610 if (0 == mMask) {
jpayne@69 1611 // nothing to do, we are empty too
jpayne@69 1612 return *this;
jpayne@69 1613 }
jpayne@69 1614
jpayne@69 1615 // not empty: destroy what we have there
jpayne@69 1616 // clear also resets mInfo to 0, that's sometimes not necessary.
jpayne@69 1617 destroy();
jpayne@69 1618 init();
jpayne@69 1619 WHash::operator=(static_cast<const WHash&>(o));
jpayne@69 1620 WKeyEqual::operator=(static_cast<const WKeyEqual&>(o));
jpayne@69 1621 DataPool::operator=(static_cast<DataPool const&>(o));
jpayne@69 1622
jpayne@69 1623 return *this;
jpayne@69 1624 }
jpayne@69 1625
jpayne@69 1626 // clean up old stuff
jpayne@69 1627 Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::value>{}.nodes(*this);
jpayne@69 1628
jpayne@69 1629 if (mMask != o.mMask) {
jpayne@69 1630 // no luck: we don't have the same array size allocated, so we need to realloc.
jpayne@69 1631 if (0 != mMask) {
jpayne@69 1632 // only deallocate if we actually have data!
jpayne@69 1633 ROBIN_HOOD_LOG("std::free")
jpayne@69 1634 std::free(mKeyVals);
jpayne@69 1635 }
jpayne@69 1636
jpayne@69 1637 auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1);
jpayne@69 1638 auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer);
jpayne@69 1639 ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal("
jpayne@69 1640 << numElementsWithBuffer << ")")
jpayne@69 1641 mKeyVals = static_cast<Node*>(
jpayne@69 1642 detail::assertNotNull<std::bad_alloc>(std::malloc(numBytesTotal)));
jpayne@69 1643
jpayne@69 1644 // no need for calloc here because cloneData performs a memcpy.
jpayne@69 1645 mInfo = reinterpret_cast<uint8_t*>(mKeyVals + numElementsWithBuffer);
jpayne@69 1646 // sentinel is set in cloneData
jpayne@69 1647 }
jpayne@69 1648 WHash::operator=(static_cast<const WHash&>(o));
jpayne@69 1649 WKeyEqual::operator=(static_cast<const WKeyEqual&>(o));
jpayne@69 1650 DataPool::operator=(static_cast<DataPool const&>(o));
jpayne@69 1651 mNumElements = o.mNumElements;
jpayne@69 1652 mMask = o.mMask;
jpayne@69 1653 mMaxNumElementsAllowed = o.mMaxNumElementsAllowed;
jpayne@69 1654 mInfoInc = o.mInfoInc;
jpayne@69 1655 mInfoHashShift = o.mInfoHashShift;
jpayne@69 1656 cloneData(o);
jpayne@69 1657
jpayne@69 1658 return *this;
jpayne@69 1659 }
jpayne@69 1660
jpayne@69 1661 // Swaps everything between the two maps.
jpayne@69 1662 void swap(Table& o) {
jpayne@69 1663 ROBIN_HOOD_TRACE(this)
jpayne@69 1664 using std::swap;
jpayne@69 1665 swap(o, *this);
jpayne@69 1666 }
jpayne@69 1667
jpayne@69 1668 // Clears all data, without resizing.
jpayne@69 1669 void clear() {
jpayne@69 1670 ROBIN_HOOD_TRACE(this)
jpayne@69 1671 if (empty()) {
jpayne@69 1672 // don't do anything! also important because we don't want to write to
jpayne@69 1673 // DummyInfoByte::b, even though we would just write 0 to it.
jpayne@69 1674 return;
jpayne@69 1675 }
jpayne@69 1676
jpayne@69 1677 Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::value>{}.nodes(*this);
jpayne@69 1678
jpayne@69 1679 auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1);
jpayne@69 1680 // clear everything, then set the sentinel again
jpayne@69 1681 uint8_t const z = 0;
jpayne@69 1682 std::fill(mInfo, mInfo + calcNumBytesInfo(numElementsWithBuffer), z);
jpayne@69 1683 mInfo[numElementsWithBuffer] = 1;
jpayne@69 1684
jpayne@69 1685 mInfoInc = InitialInfoInc;
jpayne@69 1686 mInfoHashShift = InitialInfoHashShift;
jpayne@69 1687 }
jpayne@69 1688
jpayne@69 1689 // Destroys the map and all it's contents.
jpayne@69 1690 ~Table() {
jpayne@69 1691 ROBIN_HOOD_TRACE(this)
jpayne@69 1692 destroy();
jpayne@69 1693 }
jpayne@69 1694
jpayne@69 1695 // Checks if both tables contain the same entries. Order is irrelevant.
jpayne@69 1696 bool operator==(const Table& other) const {
jpayne@69 1697 ROBIN_HOOD_TRACE(this)
jpayne@69 1698 if (other.size() != size()) {
jpayne@69 1699 return false;
jpayne@69 1700 }
jpayne@69 1701 for (auto const& otherEntry : other) {
jpayne@69 1702 if (!has(otherEntry)) {
jpayne@69 1703 return false;
jpayne@69 1704 }
jpayne@69 1705 }
jpayne@69 1706
jpayne@69 1707 return true;
jpayne@69 1708 }
jpayne@69 1709
jpayne@69 1710 bool operator!=(const Table& other) const {
jpayne@69 1711 ROBIN_HOOD_TRACE(this)
jpayne@69 1712 return !operator==(other);
jpayne@69 1713 }
jpayne@69 1714
jpayne@69 1715 template <typename Q = mapped_type>
jpayne@69 1716 typename std::enable_if<!std::is_void<Q>::value, Q&>::type operator[](const key_type& key) {
jpayne@69 1717 ROBIN_HOOD_TRACE(this)
jpayne@69 1718 return doCreateByKey(key);
jpayne@69 1719 }
jpayne@69 1720
jpayne@69 1721 template <typename Q = mapped_type>
jpayne@69 1722 typename std::enable_if<!std::is_void<Q>::value, Q&>::type operator[](key_type&& key) {
jpayne@69 1723 ROBIN_HOOD_TRACE(this)
jpayne@69 1724 return doCreateByKey(std::move(key));
jpayne@69 1725 }
jpayne@69 1726
jpayne@69 1727 template <typename Iter>
jpayne@69 1728 void insert(Iter first, Iter last) {
jpayne@69 1729 for (; first != last; ++first) {
jpayne@69 1730 // value_type ctor needed because this might be called with std::pair's
jpayne@69 1731 insert(value_type(*first));
jpayne@69 1732 }
jpayne@69 1733 }
jpayne@69 1734
jpayne@69 1735 template <typename... Args>
jpayne@69 1736 std::pair<iterator, bool> emplace(Args&&... args) {
jpayne@69 1737 ROBIN_HOOD_TRACE(this)
jpayne@69 1738 Node n{*this, std::forward<Args>(args)...};
jpayne@69 1739 auto r = doInsert(std::move(n));
jpayne@69 1740 if (!r.second) {
jpayne@69 1741 // insertion not possible: destroy node
jpayne@69 1742 // NOLINTNEXTLINE(bugprone-use-after-move)
jpayne@69 1743 n.destroy(*this);
jpayne@69 1744 }
jpayne@69 1745 return r;
jpayne@69 1746 }
jpayne@69 1747
jpayne@69 1748 template <typename... Args>
jpayne@69 1749 std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) {
jpayne@69 1750 return try_emplace_impl(key, std::forward<Args>(args)...);
jpayne@69 1751 }
jpayne@69 1752
jpayne@69 1753 template <typename... Args>
jpayne@69 1754 std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args) {
jpayne@69 1755 return try_emplace_impl(std::move(key), std::forward<Args>(args)...);
jpayne@69 1756 }
jpayne@69 1757
jpayne@69 1758 template <typename... Args>
jpayne@69 1759 std::pair<iterator, bool> try_emplace(const_iterator hint, const key_type& key,
jpayne@69 1760 Args&&... args) {
jpayne@69 1761 (void)hint;
jpayne@69 1762 return try_emplace_impl(key, std::forward<Args>(args)...);
jpayne@69 1763 }
jpayne@69 1764
jpayne@69 1765 template <typename... Args>
jpayne@69 1766 std::pair<iterator, bool> try_emplace(const_iterator hint, key_type&& key, Args&&... args) {
jpayne@69 1767 (void)hint;
jpayne@69 1768 return try_emplace_impl(std::move(key), std::forward<Args>(args)...);
jpayne@69 1769 }
jpayne@69 1770
jpayne@69 1771 template <typename Mapped>
jpayne@69 1772 std::pair<iterator, bool> insert_or_assign(const key_type& key, Mapped&& obj) {
jpayne@69 1773 return insert_or_assign_impl(key, std::forward<Mapped>(obj));
jpayne@69 1774 }
jpayne@69 1775
jpayne@69 1776 template <typename Mapped>
jpayne@69 1777 std::pair<iterator, bool> insert_or_assign(key_type&& key, Mapped&& obj) {
jpayne@69 1778 return insert_or_assign_impl(std::move(key), std::forward<Mapped>(obj));
jpayne@69 1779 }
jpayne@69 1780
jpayne@69 1781 template <typename Mapped>
jpayne@69 1782 std::pair<iterator, bool> insert_or_assign(const_iterator hint, const key_type& key,
jpayne@69 1783 Mapped&& obj) {
jpayne@69 1784 (void)hint;
jpayne@69 1785 return insert_or_assign_impl(key, std::forward<Mapped>(obj));
jpayne@69 1786 }
jpayne@69 1787
jpayne@69 1788 template <typename Mapped>
jpayne@69 1789 std::pair<iterator, bool> insert_or_assign(const_iterator hint, key_type&& key, Mapped&& obj) {
jpayne@69 1790 (void)hint;
jpayne@69 1791 return insert_or_assign_impl(std::move(key), std::forward<Mapped>(obj));
jpayne@69 1792 }
jpayne@69 1793
jpayne@69 1794 std::pair<iterator, bool> insert(const value_type& keyval) {
jpayne@69 1795 ROBIN_HOOD_TRACE(this)
jpayne@69 1796 return doInsert(keyval);
jpayne@69 1797 }
jpayne@69 1798
jpayne@69 1799 std::pair<iterator, bool> insert(value_type&& keyval) {
jpayne@69 1800 return doInsert(std::move(keyval));
jpayne@69 1801 }
jpayne@69 1802
jpayne@69 1803 // Returns 1 if key is found, 0 otherwise.
jpayne@69 1804 size_t count(const key_type& key) const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1805 ROBIN_HOOD_TRACE(this)
jpayne@69 1806 auto kv = mKeyVals + findIdx(key);
jpayne@69 1807 if (kv != reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
jpayne@69 1808 return 1;
jpayne@69 1809 }
jpayne@69 1810 return 0;
jpayne@69 1811 }
jpayne@69 1812
jpayne@69 1813 template <typename OtherKey, typename Self_ = Self>
jpayne@69 1814 // NOLINTNEXTLINE(modernize-use-nodiscard)
jpayne@69 1815 typename std::enable_if<Self_::is_transparent, size_t>::type count(const OtherKey& key) const {
jpayne@69 1816 ROBIN_HOOD_TRACE(this)
jpayne@69 1817 auto kv = mKeyVals + findIdx(key);
jpayne@69 1818 if (kv != reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
jpayne@69 1819 return 1;
jpayne@69 1820 }
jpayne@69 1821 return 0;
jpayne@69 1822 }
jpayne@69 1823
jpayne@69 1824 bool contains(const key_type& key) const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1825 return 1U == count(key);
jpayne@69 1826 }
jpayne@69 1827
jpayne@69 1828 template <typename OtherKey, typename Self_ = Self>
jpayne@69 1829 // NOLINTNEXTLINE(modernize-use-nodiscard)
jpayne@69 1830 typename std::enable_if<Self_::is_transparent, bool>::type contains(const OtherKey& key) const {
jpayne@69 1831 return 1U == count(key);
jpayne@69 1832 }
jpayne@69 1833
jpayne@69 1834 // Returns a reference to the value found for key.
jpayne@69 1835 // Throws std::out_of_range if element cannot be found
jpayne@69 1836 template <typename Q = mapped_type>
jpayne@69 1837 // NOLINTNEXTLINE(modernize-use-nodiscard)
jpayne@69 1838 typename std::enable_if<!std::is_void<Q>::value, Q&>::type at(key_type const& key) {
jpayne@69 1839 ROBIN_HOOD_TRACE(this)
jpayne@69 1840 auto kv = mKeyVals + findIdx(key);
jpayne@69 1841 if (kv == reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
jpayne@69 1842 doThrow<std::out_of_range>("key not found");
jpayne@69 1843 }
jpayne@69 1844 return kv->getSecond();
jpayne@69 1845 }
jpayne@69 1846
jpayne@69 1847 // Returns a reference to the value found for key.
jpayne@69 1848 // Throws std::out_of_range if element cannot be found
jpayne@69 1849 template <typename Q = mapped_type>
jpayne@69 1850 // NOLINTNEXTLINE(modernize-use-nodiscard)
jpayne@69 1851 typename std::enable_if<!std::is_void<Q>::value, Q const&>::type at(key_type const& key) const {
jpayne@69 1852 ROBIN_HOOD_TRACE(this)
jpayne@69 1853 auto kv = mKeyVals + findIdx(key);
jpayne@69 1854 if (kv == reinterpret_cast_no_cast_align_warning<Node*>(mInfo)) {
jpayne@69 1855 doThrow<std::out_of_range>("key not found");
jpayne@69 1856 }
jpayne@69 1857 return kv->getSecond();
jpayne@69 1858 }
jpayne@69 1859
jpayne@69 1860 const_iterator find(const key_type& key) const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1861 ROBIN_HOOD_TRACE(this)
jpayne@69 1862 const size_t idx = findIdx(key);
jpayne@69 1863 return const_iterator{mKeyVals + idx, mInfo + idx};
jpayne@69 1864 }
jpayne@69 1865
jpayne@69 1866 template <typename OtherKey>
jpayne@69 1867 const_iterator find(const OtherKey& key, is_transparent_tag /*unused*/) const {
jpayne@69 1868 ROBIN_HOOD_TRACE(this)
jpayne@69 1869 const size_t idx = findIdx(key);
jpayne@69 1870 return const_iterator{mKeyVals + idx, mInfo + idx};
jpayne@69 1871 }
jpayne@69 1872
jpayne@69 1873 template <typename OtherKey, typename Self_ = Self>
jpayne@69 1874 typename std::enable_if<Self_::is_transparent, // NOLINT(modernize-use-nodiscard)
jpayne@69 1875 const_iterator>::type // NOLINT(modernize-use-nodiscard)
jpayne@69 1876 find(const OtherKey& key) const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1877 ROBIN_HOOD_TRACE(this)
jpayne@69 1878 const size_t idx = findIdx(key);
jpayne@69 1879 return const_iterator{mKeyVals + idx, mInfo + idx};
jpayne@69 1880 }
jpayne@69 1881
jpayne@69 1882 iterator find(const key_type& key) {
jpayne@69 1883 ROBIN_HOOD_TRACE(this)
jpayne@69 1884 const size_t idx = findIdx(key);
jpayne@69 1885 return iterator{mKeyVals + idx, mInfo + idx};
jpayne@69 1886 }
jpayne@69 1887
jpayne@69 1888 template <typename OtherKey>
jpayne@69 1889 iterator find(const OtherKey& key, is_transparent_tag /*unused*/) {
jpayne@69 1890 ROBIN_HOOD_TRACE(this)
jpayne@69 1891 const size_t idx = findIdx(key);
jpayne@69 1892 return iterator{mKeyVals + idx, mInfo + idx};
jpayne@69 1893 }
jpayne@69 1894
jpayne@69 1895 template <typename OtherKey, typename Self_ = Self>
jpayne@69 1896 typename std::enable_if<Self_::is_transparent, iterator>::type find(const OtherKey& key) {
jpayne@69 1897 ROBIN_HOOD_TRACE(this)
jpayne@69 1898 const size_t idx = findIdx(key);
jpayne@69 1899 return iterator{mKeyVals + idx, mInfo + idx};
jpayne@69 1900 }
jpayne@69 1901
jpayne@69 1902 iterator begin() {
jpayne@69 1903 ROBIN_HOOD_TRACE(this)
jpayne@69 1904 if (empty()) {
jpayne@69 1905 return end();
jpayne@69 1906 }
jpayne@69 1907 return iterator(mKeyVals, mInfo, fast_forward_tag{});
jpayne@69 1908 }
jpayne@69 1909 const_iterator begin() const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1910 ROBIN_HOOD_TRACE(this)
jpayne@69 1911 return cbegin();
jpayne@69 1912 }
jpayne@69 1913 const_iterator cbegin() const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1914 ROBIN_HOOD_TRACE(this)
jpayne@69 1915 if (empty()) {
jpayne@69 1916 return cend();
jpayne@69 1917 }
jpayne@69 1918 return const_iterator(mKeyVals, mInfo, fast_forward_tag{});
jpayne@69 1919 }
jpayne@69 1920
jpayne@69 1921 iterator end() {
jpayne@69 1922 ROBIN_HOOD_TRACE(this)
jpayne@69 1923 // no need to supply valid info pointer: end() must not be dereferenced, and only node
jpayne@69 1924 // pointer is compared.
jpayne@69 1925 return iterator{reinterpret_cast_no_cast_align_warning<Node*>(mInfo), nullptr};
jpayne@69 1926 }
jpayne@69 1927 const_iterator end() const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1928 ROBIN_HOOD_TRACE(this)
jpayne@69 1929 return cend();
jpayne@69 1930 }
jpayne@69 1931 const_iterator cend() const { // NOLINT(modernize-use-nodiscard)
jpayne@69 1932 ROBIN_HOOD_TRACE(this)
jpayne@69 1933 return const_iterator{reinterpret_cast_no_cast_align_warning<Node*>(mInfo), nullptr};
jpayne@69 1934 }
jpayne@69 1935
jpayne@69 1936 iterator erase(const_iterator pos) {
jpayne@69 1937 ROBIN_HOOD_TRACE(this)
jpayne@69 1938 // its safe to perform const cast here
jpayne@69 1939 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
jpayne@69 1940 return erase(iterator{const_cast<Node*>(pos.mKeyVals), const_cast<uint8_t*>(pos.mInfo)});
jpayne@69 1941 }
jpayne@69 1942
jpayne@69 1943 // Erases element at pos, returns iterator to the next element.
jpayne@69 1944 iterator erase(iterator pos) {
jpayne@69 1945 ROBIN_HOOD_TRACE(this)
jpayne@69 1946 // we assume that pos always points to a valid entry, and not end().
jpayne@69 1947 auto const idx = static_cast<size_t>(pos.mKeyVals - mKeyVals);
jpayne@69 1948
jpayne@69 1949 shiftDown(idx);
jpayne@69 1950 --mNumElements;
jpayne@69 1951
jpayne@69 1952 if (*pos.mInfo) {
jpayne@69 1953 // we've backward shifted, return this again
jpayne@69 1954 return pos;
jpayne@69 1955 }
jpayne@69 1956
jpayne@69 1957 // no backward shift, return next element
jpayne@69 1958 return ++pos;
jpayne@69 1959 }
jpayne@69 1960
jpayne@69 1961 size_t erase(const key_type& key) {
jpayne@69 1962 ROBIN_HOOD_TRACE(this)
jpayne@69 1963 size_t idx{};
jpayne@69 1964 InfoType info{};
jpayne@69 1965 keyToIdx(key, &idx, &info);
jpayne@69 1966
jpayne@69 1967 // check while info matches with the source idx
jpayne@69 1968 do {
jpayne@69 1969 if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
jpayne@69 1970 shiftDown(idx);
jpayne@69 1971 --mNumElements;
jpayne@69 1972 return 1;
jpayne@69 1973 }
jpayne@69 1974 next(&info, &idx);
jpayne@69 1975 } while (info <= mInfo[idx]);
jpayne@69 1976
jpayne@69 1977 // nothing found to delete
jpayne@69 1978 return 0;
jpayne@69 1979 }
jpayne@69 1980
jpayne@69 1981 // reserves space for the specified number of elements. Makes sure the old data fits.
jpayne@69 1982 // exactly the same as reserve(c).
jpayne@69 1983 void rehash(size_t c) {
jpayne@69 1984 // forces a reserve
jpayne@69 1985 reserve(c, true);
jpayne@69 1986 }
jpayne@69 1987
jpayne@69 1988 // reserves space for the specified number of elements. Makes sure the old data fits.
jpayne@69 1989 // Exactly the same as rehash(c). Use rehash(0) to shrink to fit.
jpayne@69 1990 void reserve(size_t c) {
jpayne@69 1991 // reserve, but don't force rehash
jpayne@69 1992 reserve(c, false);
jpayne@69 1993 }
jpayne@69 1994
jpayne@69 1995 size_type size() const noexcept { // NOLINT(modernize-use-nodiscard)
jpayne@69 1996 ROBIN_HOOD_TRACE(this)
jpayne@69 1997 return mNumElements;
jpayne@69 1998 }
jpayne@69 1999
jpayne@69 2000 size_type max_size() const noexcept { // NOLINT(modernize-use-nodiscard)
jpayne@69 2001 ROBIN_HOOD_TRACE(this)
jpayne@69 2002 return static_cast<size_type>(-1);
jpayne@69 2003 }
jpayne@69 2004
jpayne@69 2005 ROBIN_HOOD(NODISCARD) bool empty() const noexcept {
jpayne@69 2006 ROBIN_HOOD_TRACE(this)
jpayne@69 2007 return 0 == mNumElements;
jpayne@69 2008 }
jpayne@69 2009
jpayne@69 2010 float max_load_factor() const noexcept { // NOLINT(modernize-use-nodiscard)
jpayne@69 2011 ROBIN_HOOD_TRACE(this)
jpayne@69 2012 return MaxLoadFactor100 / 100.0F;
jpayne@69 2013 }
jpayne@69 2014
jpayne@69 2015 // Average number of elements per bucket. Since we allow only 1 per bucket
jpayne@69 2016 float load_factor() const noexcept { // NOLINT(modernize-use-nodiscard)
jpayne@69 2017 ROBIN_HOOD_TRACE(this)
jpayne@69 2018 return static_cast<float>(size()) / static_cast<float>(mMask + 1);
jpayne@69 2019 }
jpayne@69 2020
jpayne@69 2021 ROBIN_HOOD(NODISCARD) size_t mask() const noexcept {
jpayne@69 2022 ROBIN_HOOD_TRACE(this)
jpayne@69 2023 return mMask;
jpayne@69 2024 }
jpayne@69 2025
jpayne@69 2026 ROBIN_HOOD(NODISCARD) size_t calcMaxNumElementsAllowed(size_t maxElements) const noexcept {
jpayne@69 2027 if (ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits<size_t>::max)() / 100)) {
jpayne@69 2028 return maxElements * MaxLoadFactor100 / 100;
jpayne@69 2029 }
jpayne@69 2030
jpayne@69 2031 // we might be a bit inprecise, but since maxElements is quite large that doesn't matter
jpayne@69 2032 return (maxElements / 100) * MaxLoadFactor100;
jpayne@69 2033 }
jpayne@69 2034
jpayne@69 2035 ROBIN_HOOD(NODISCARD) size_t calcNumBytesInfo(size_t numElements) const noexcept {
jpayne@69 2036 // we add a uint64_t, which houses the sentinel (first byte) and padding so we can load
jpayne@69 2037 // 64bit types.
jpayne@69 2038 return numElements + sizeof(uint64_t);
jpayne@69 2039 }
jpayne@69 2040
jpayne@69 2041 ROBIN_HOOD(NODISCARD)
jpayne@69 2042 size_t calcNumElementsWithBuffer(size_t numElements) const noexcept {
jpayne@69 2043 auto maxNumElementsAllowed = calcMaxNumElementsAllowed(numElements);
jpayne@69 2044 return numElements + (std::min)(maxNumElementsAllowed, (static_cast<size_t>(0xFF)));
jpayne@69 2045 }
jpayne@69 2046
jpayne@69 2047 // calculation only allowed for 2^n values
jpayne@69 2048 ROBIN_HOOD(NODISCARD) size_t calcNumBytesTotal(size_t numElements) const {
jpayne@69 2049 #if ROBIN_HOOD(BITNESS) == 64
jpayne@69 2050 return numElements * sizeof(Node) + calcNumBytesInfo(numElements);
jpayne@69 2051 #else
jpayne@69 2052 // make sure we're doing 64bit operations, so we are at least safe against 32bit overflows.
jpayne@69 2053 auto const ne = static_cast<uint64_t>(numElements);
jpayne@69 2054 auto const s = static_cast<uint64_t>(sizeof(Node));
jpayne@69 2055 auto const infos = static_cast<uint64_t>(calcNumBytesInfo(numElements));
jpayne@69 2056
jpayne@69 2057 auto const total64 = ne * s + infos;
jpayne@69 2058 auto const total = static_cast<size_t>(total64);
jpayne@69 2059
jpayne@69 2060 if (ROBIN_HOOD_UNLIKELY(static_cast<uint64_t>(total) != total64)) {
jpayne@69 2061 throwOverflowError();
jpayne@69 2062 }
jpayne@69 2063 return total;
jpayne@69 2064 #endif
jpayne@69 2065 }
jpayne@69 2066
jpayne@69 2067 private:
jpayne@69 2068 template <typename Q = mapped_type>
jpayne@69 2069 ROBIN_HOOD(NODISCARD)
jpayne@69 2070 typename std::enable_if<!std::is_void<Q>::value, bool>::type has(const value_type& e) const {
jpayne@69 2071 ROBIN_HOOD_TRACE(this)
jpayne@69 2072 auto it = find(e.first);
jpayne@69 2073 return it != end() && it->second == e.second;
jpayne@69 2074 }
jpayne@69 2075
jpayne@69 2076 template <typename Q = mapped_type>
jpayne@69 2077 ROBIN_HOOD(NODISCARD)
jpayne@69 2078 typename std::enable_if<std::is_void<Q>::value, bool>::type has(const value_type& e) const {
jpayne@69 2079 ROBIN_HOOD_TRACE(this)
jpayne@69 2080 return find(e) != end();
jpayne@69 2081 }
jpayne@69 2082
jpayne@69 2083 void reserve(size_t c, bool forceRehash) {
jpayne@69 2084 ROBIN_HOOD_TRACE(this)
jpayne@69 2085 auto const minElementsAllowed = (std::max)(c, mNumElements);
jpayne@69 2086 auto newSize = InitialNumElements;
jpayne@69 2087 while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) {
jpayne@69 2088 newSize *= 2;
jpayne@69 2089 }
jpayne@69 2090 if (ROBIN_HOOD_UNLIKELY(newSize == 0)) {
jpayne@69 2091 throwOverflowError();
jpayne@69 2092 }
jpayne@69 2093
jpayne@69 2094 ROBIN_HOOD_LOG("newSize > mMask + 1: " << newSize << " > " << mMask << " + 1")
jpayne@69 2095
jpayne@69 2096 // only actually do anything when the new size is bigger than the old one. This prevents to
jpayne@69 2097 // continuously allocate for each reserve() call.
jpayne@69 2098 if (forceRehash || newSize > mMask + 1) {
jpayne@69 2099 rehashPowerOfTwo(newSize);
jpayne@69 2100 }
jpayne@69 2101 }
jpayne@69 2102
jpayne@69 2103 // reserves space for at least the specified number of elements.
jpayne@69 2104 // only works if numBuckets if power of two
jpayne@69 2105 void rehashPowerOfTwo(size_t numBuckets) {
jpayne@69 2106 ROBIN_HOOD_TRACE(this)
jpayne@69 2107
jpayne@69 2108 Node* const oldKeyVals = mKeyVals;
jpayne@69 2109 uint8_t const* const oldInfo = mInfo;
jpayne@69 2110
jpayne@69 2111 const size_t oldMaxElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1);
jpayne@69 2112
jpayne@69 2113 // resize operation: move stuff
jpayne@69 2114 init_data(numBuckets);
jpayne@69 2115 if (oldMaxElementsWithBuffer > 1) {
jpayne@69 2116 for (size_t i = 0; i < oldMaxElementsWithBuffer; ++i) {
jpayne@69 2117 if (oldInfo[i] != 0) {
jpayne@69 2118 insert_move(std::move(oldKeyVals[i]));
jpayne@69 2119 // destroy the node but DON'T destroy the data.
jpayne@69 2120 oldKeyVals[i].~Node();
jpayne@69 2121 }
jpayne@69 2122 }
jpayne@69 2123
jpayne@69 2124 // this check is not necessary as it's guarded by the previous if, but it helps silence
jpayne@69 2125 // g++'s overeager "attempt to free a non-heap object 'map'
jpayne@69 2126 // [-Werror=free-nonheap-object]" warning.
jpayne@69 2127 if (oldKeyVals != reinterpret_cast_no_cast_align_warning<Node*>(&mMask)) {
jpayne@69 2128 // don't destroy old data: put it into the pool instead
jpayne@69 2129 DataPool::addOrFree(oldKeyVals, calcNumBytesTotal(oldMaxElementsWithBuffer));
jpayne@69 2130 }
jpayne@69 2131 }
jpayne@69 2132 }
jpayne@69 2133
jpayne@69 2134 ROBIN_HOOD(NOINLINE) void throwOverflowError() const {
jpayne@69 2135 #if ROBIN_HOOD(HAS_EXCEPTIONS)
jpayne@69 2136 throw std::overflow_error("robin_hood::map overflow");
jpayne@69 2137 #else
jpayne@69 2138 abort();
jpayne@69 2139 #endif
jpayne@69 2140 }
jpayne@69 2141
jpayne@69 2142 template <typename OtherKey, typename... Args>
jpayne@69 2143 std::pair<iterator, bool> try_emplace_impl(OtherKey&& key, Args&&... args) {
jpayne@69 2144 ROBIN_HOOD_TRACE(this)
jpayne@69 2145 auto it = find(key);
jpayne@69 2146 if (it == end()) {
jpayne@69 2147 return emplace(std::piecewise_construct,
jpayne@69 2148 std::forward_as_tuple(std::forward<OtherKey>(key)),
jpayne@69 2149 std::forward_as_tuple(std::forward<Args>(args)...));
jpayne@69 2150 }
jpayne@69 2151 return {it, false};
jpayne@69 2152 }
jpayne@69 2153
jpayne@69 2154 template <typename OtherKey, typename Mapped>
jpayne@69 2155 std::pair<iterator, bool> insert_or_assign_impl(OtherKey&& key, Mapped&& obj) {
jpayne@69 2156 ROBIN_HOOD_TRACE(this)
jpayne@69 2157 auto it = find(key);
jpayne@69 2158 if (it == end()) {
jpayne@69 2159 return emplace(std::forward<OtherKey>(key), std::forward<Mapped>(obj));
jpayne@69 2160 }
jpayne@69 2161 it->second = std::forward<Mapped>(obj);
jpayne@69 2162 return {it, false};
jpayne@69 2163 }
jpayne@69 2164
jpayne@69 2165 void init_data(size_t max_elements) {
jpayne@69 2166 mNumElements = 0;
jpayne@69 2167 mMask = max_elements - 1;
jpayne@69 2168 mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements);
jpayne@69 2169
jpayne@69 2170 auto const numElementsWithBuffer = calcNumElementsWithBuffer(max_elements);
jpayne@69 2171
jpayne@69 2172 // calloc also zeroes everything
jpayne@69 2173 auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer);
jpayne@69 2174 ROBIN_HOOD_LOG("std::calloc " << numBytesTotal << " = calcNumBytesTotal("
jpayne@69 2175 << numElementsWithBuffer << ")")
jpayne@69 2176 mKeyVals = reinterpret_cast<Node*>(
jpayne@69 2177 detail::assertNotNull<std::bad_alloc>(std::calloc(1, numBytesTotal)));
jpayne@69 2178 mInfo = reinterpret_cast<uint8_t*>(mKeyVals + numElementsWithBuffer);
jpayne@69 2179
jpayne@69 2180 // set sentinel
jpayne@69 2181 mInfo[numElementsWithBuffer] = 1;
jpayne@69 2182
jpayne@69 2183 mInfoInc = InitialInfoInc;
jpayne@69 2184 mInfoHashShift = InitialInfoHashShift;
jpayne@69 2185 }
jpayne@69 2186
jpayne@69 2187 template <typename Arg, typename Q = mapped_type>
jpayne@69 2188 typename std::enable_if<!std::is_void<Q>::value, Q&>::type doCreateByKey(Arg&& key) {
jpayne@69 2189 while (true) {
jpayne@69 2190 size_t idx{};
jpayne@69 2191 InfoType info{};
jpayne@69 2192 keyToIdx(key, &idx, &info);
jpayne@69 2193 nextWhileLess(&info, &idx);
jpayne@69 2194
jpayne@69 2195 // while we potentially have a match. Can't do a do-while here because when mInfo is
jpayne@69 2196 // 0 we don't want to skip forward
jpayne@69 2197 while (info == mInfo[idx]) {
jpayne@69 2198 if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
jpayne@69 2199 // key already exists, do not insert.
jpayne@69 2200 return mKeyVals[idx].getSecond();
jpayne@69 2201 }
jpayne@69 2202 next(&info, &idx);
jpayne@69 2203 }
jpayne@69 2204
jpayne@69 2205 // unlikely that this evaluates to true
jpayne@69 2206 if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
jpayne@69 2207 increase_size();
jpayne@69 2208 continue;
jpayne@69 2209 }
jpayne@69 2210
jpayne@69 2211 // key not found, so we are now exactly where we want to insert it.
jpayne@69 2212 auto const insertion_idx = idx;
jpayne@69 2213 auto const insertion_info = info;
jpayne@69 2214 if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
jpayne@69 2215 mMaxNumElementsAllowed = 0;
jpayne@69 2216 }
jpayne@69 2217
jpayne@69 2218 // find an empty spot
jpayne@69 2219 while (0 != mInfo[idx]) {
jpayne@69 2220 next(&info, &idx);
jpayne@69 2221 }
jpayne@69 2222
jpayne@69 2223 auto& l = mKeyVals[insertion_idx];
jpayne@69 2224 if (idx == insertion_idx) {
jpayne@69 2225 // put at empty spot. This forwards all arguments into the node where the object
jpayne@69 2226 // is constructed exactly where it is needed.
jpayne@69 2227 ::new (static_cast<void*>(&l))
jpayne@69 2228 Node(*this, std::piecewise_construct,
jpayne@69 2229 std::forward_as_tuple(std::forward<Arg>(key)), std::forward_as_tuple());
jpayne@69 2230 } else {
jpayne@69 2231 shiftUp(idx, insertion_idx);
jpayne@69 2232 l = Node(*this, std::piecewise_construct,
jpayne@69 2233 std::forward_as_tuple(std::forward<Arg>(key)), std::forward_as_tuple());
jpayne@69 2234 }
jpayne@69 2235
jpayne@69 2236 // mKeyVals[idx].getFirst() = std::move(key);
jpayne@69 2237 mInfo[insertion_idx] = static_cast<uint8_t>(insertion_info);
jpayne@69 2238
jpayne@69 2239 ++mNumElements;
jpayne@69 2240 return mKeyVals[insertion_idx].getSecond();
jpayne@69 2241 }
jpayne@69 2242 }
jpayne@69 2243
jpayne@69 2244 // This is exactly the same code as operator[], except for the return values
jpayne@69 2245 template <typename Arg>
jpayne@69 2246 std::pair<iterator, bool> doInsert(Arg&& keyval) {
jpayne@69 2247 while (true) {
jpayne@69 2248 size_t idx{};
jpayne@69 2249 InfoType info{};
jpayne@69 2250 keyToIdx(getFirstConst(keyval), &idx, &info);
jpayne@69 2251 nextWhileLess(&info, &idx);
jpayne@69 2252
jpayne@69 2253 // while we potentially have a match
jpayne@69 2254 while (info == mInfo[idx]) {
jpayne@69 2255 if (WKeyEqual::operator()(getFirstConst(keyval), mKeyVals[idx].getFirst())) {
jpayne@69 2256 // key already exists, do NOT insert.
jpayne@69 2257 // see http://en.cppreference.com/w/cpp/container/unordered_map/insert
jpayne@69 2258 return std::make_pair<iterator, bool>(iterator(mKeyVals + idx, mInfo + idx),
jpayne@69 2259 false);
jpayne@69 2260 }
jpayne@69 2261 next(&info, &idx);
jpayne@69 2262 }
jpayne@69 2263
jpayne@69 2264 // unlikely that this evaluates to true
jpayne@69 2265 if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
jpayne@69 2266 increase_size();
jpayne@69 2267 continue;
jpayne@69 2268 }
jpayne@69 2269
jpayne@69 2270 // key not found, so we are now exactly where we want to insert it.
jpayne@69 2271 auto const insertion_idx = idx;
jpayne@69 2272 auto const insertion_info = info;
jpayne@69 2273 if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) {
jpayne@69 2274 mMaxNumElementsAllowed = 0;
jpayne@69 2275 }
jpayne@69 2276
jpayne@69 2277 // find an empty spot
jpayne@69 2278 while (0 != mInfo[idx]) {
jpayne@69 2279 next(&info, &idx);
jpayne@69 2280 }
jpayne@69 2281
jpayne@69 2282 auto& l = mKeyVals[insertion_idx];
jpayne@69 2283 if (idx == insertion_idx) {
jpayne@69 2284 ::new (static_cast<void*>(&l)) Node(*this, std::forward<Arg>(keyval));
jpayne@69 2285 } else {
jpayne@69 2286 shiftUp(idx, insertion_idx);
jpayne@69 2287 l = Node(*this, std::forward<Arg>(keyval));
jpayne@69 2288 }
jpayne@69 2289
jpayne@69 2290 // put at empty spot
jpayne@69 2291 mInfo[insertion_idx] = static_cast<uint8_t>(insertion_info);
jpayne@69 2292
jpayne@69 2293 ++mNumElements;
jpayne@69 2294 return std::make_pair(iterator(mKeyVals + insertion_idx, mInfo + insertion_idx), true);
jpayne@69 2295 }
jpayne@69 2296 }
jpayne@69 2297
jpayne@69 2298 bool try_increase_info() {
jpayne@69 2299 ROBIN_HOOD_LOG("mInfoInc=" << mInfoInc << ", numElements=" << mNumElements
jpayne@69 2300 << ", maxNumElementsAllowed="
jpayne@69 2301 << calcMaxNumElementsAllowed(mMask + 1))
jpayne@69 2302 if (mInfoInc <= 2) {
jpayne@69 2303 // need to be > 2 so that shift works (otherwise undefined behavior!)
jpayne@69 2304 return false;
jpayne@69 2305 }
jpayne@69 2306 // we got space left, try to make info smaller
jpayne@69 2307 mInfoInc = static_cast<uint8_t>(mInfoInc >> 1U);
jpayne@69 2308
jpayne@69 2309 // remove one bit of the hash, leaving more space for the distance info.
jpayne@69 2310 // This is extremely fast because we can operate on 8 bytes at once.
jpayne@69 2311 ++mInfoHashShift;
jpayne@69 2312 auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1);
jpayne@69 2313
jpayne@69 2314 for (size_t i = 0; i < numElementsWithBuffer; i += 8) {
jpayne@69 2315 auto val = unaligned_load<uint64_t>(mInfo + i);
jpayne@69 2316 val = (val >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f);
jpayne@69 2317 std::memcpy(mInfo + i, &val, sizeof(val));
jpayne@69 2318 }
jpayne@69 2319 // update sentinel, which might have been cleared out!
jpayne@69 2320 mInfo[numElementsWithBuffer] = 1;
jpayne@69 2321
jpayne@69 2322 mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
jpayne@69 2323 return true;
jpayne@69 2324 }
jpayne@69 2325
jpayne@69 2326 void increase_size() {
jpayne@69 2327 // nothing allocated yet? just allocate InitialNumElements
jpayne@69 2328 if (0 == mMask) {
jpayne@69 2329 init_data(InitialNumElements);
jpayne@69 2330 return;
jpayne@69 2331 }
jpayne@69 2332
jpayne@69 2333 auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
jpayne@69 2334 if (mNumElements < maxNumElementsAllowed && try_increase_info()) {
jpayne@69 2335 return;
jpayne@69 2336 }
jpayne@69 2337
jpayne@69 2338 ROBIN_HOOD_LOG("mNumElements=" << mNumElements << ", maxNumElementsAllowed="
jpayne@69 2339 << maxNumElementsAllowed << ", load="
jpayne@69 2340 << (static_cast<double>(mNumElements) * 100.0 /
jpayne@69 2341 (static_cast<double>(mMask) + 1)))
jpayne@69 2342 // it seems we have a really bad hash function! don't try to resize again
jpayne@69 2343 if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) {
jpayne@69 2344 throwOverflowError();
jpayne@69 2345 }
jpayne@69 2346
jpayne@69 2347 rehashPowerOfTwo((mMask + 1) * 2);
jpayne@69 2348 }
jpayne@69 2349
jpayne@69 2350 void destroy() {
jpayne@69 2351 if (0 == mMask) {
jpayne@69 2352 // don't deallocate!
jpayne@69 2353 return;
jpayne@69 2354 }
jpayne@69 2355
jpayne@69 2356 Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::value>{}
jpayne@69 2357 .nodesDoNotDeallocate(*this);
jpayne@69 2358
jpayne@69 2359 // This protection against not deleting mMask shouldn't be needed as it's sufficiently
jpayne@69 2360 // protected with the 0==mMask check, but I have this anyways because g++ 7 otherwise
jpayne@69 2361 // reports a compile error: attempt to free a non-heap object 'fm'
jpayne@69 2362 // [-Werror=free-nonheap-object]
jpayne@69 2363 if (mKeyVals != reinterpret_cast_no_cast_align_warning<Node*>(&mMask)) {
jpayne@69 2364 ROBIN_HOOD_LOG("std::free")
jpayne@69 2365 std::free(mKeyVals);
jpayne@69 2366 }
jpayne@69 2367 }
jpayne@69 2368
jpayne@69 2369 void init() noexcept {
jpayne@69 2370 mKeyVals = reinterpret_cast_no_cast_align_warning<Node*>(&mMask);
jpayne@69 2371 mInfo = reinterpret_cast<uint8_t*>(&mMask);
jpayne@69 2372 mNumElements = 0;
jpayne@69 2373 mMask = 0;
jpayne@69 2374 mMaxNumElementsAllowed = 0;
jpayne@69 2375 mInfoInc = InitialInfoInc;
jpayne@69 2376 mInfoHashShift = InitialInfoHashShift;
jpayne@69 2377 }
jpayne@69 2378
jpayne@69 2379 // members are sorted so no padding occurs
jpayne@69 2380 Node* mKeyVals = reinterpret_cast_no_cast_align_warning<Node*>(&mMask); // 8 byte 8
jpayne@69 2381 uint8_t* mInfo = reinterpret_cast<uint8_t*>(&mMask); // 8 byte 16
jpayne@69 2382 size_t mNumElements = 0; // 8 byte 24
jpayne@69 2383 size_t mMask = 0; // 8 byte 32
jpayne@69 2384 size_t mMaxNumElementsAllowed = 0; // 8 byte 40
jpayne@69 2385 InfoType mInfoInc = InitialInfoInc; // 4 byte 44
jpayne@69 2386 InfoType mInfoHashShift = InitialInfoHashShift; // 4 byte 48
jpayne@69 2387 // 16 byte 56 if NodeAllocator
jpayne@69 2388 };
jpayne@69 2389
jpayne@69 2390 } // namespace detail
jpayne@69 2391
jpayne@69 2392 // map
jpayne@69 2393
jpayne@69 2394 template <typename Key, typename T, typename Hash = hash<Key>,
jpayne@69 2395 typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
jpayne@69 2396 using unordered_flat_map = detail::Table<true, MaxLoadFactor100, Key, T, Hash, KeyEqual>;
jpayne@69 2397
jpayne@69 2398 template <typename Key, typename T, typename Hash = hash<Key>,
jpayne@69 2399 typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
jpayne@69 2400 using unordered_node_map = detail::Table<false, MaxLoadFactor100, Key, T, Hash, KeyEqual>;
jpayne@69 2401
jpayne@69 2402 template <typename Key, typename T, typename Hash = hash<Key>,
jpayne@69 2403 typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
jpayne@69 2404 using unordered_map =
jpayne@69 2405 detail::Table<sizeof(robin_hood::pair<Key, T>) <= sizeof(size_t) * 6 &&
jpayne@69 2406 std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
jpayne@69 2407 std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
jpayne@69 2408 MaxLoadFactor100, Key, T, Hash, KeyEqual>;
jpayne@69 2409
jpayne@69 2410 // set
jpayne@69 2411
jpayne@69 2412 template <typename Key, typename Hash = hash<Key>, typename KeyEqual = std::equal_to<Key>,
jpayne@69 2413 size_t MaxLoadFactor100 = 80>
jpayne@69 2414 using unordered_flat_set = detail::Table<true, MaxLoadFactor100, Key, void, Hash, KeyEqual>;
jpayne@69 2415
jpayne@69 2416 template <typename Key, typename Hash = hash<Key>, typename KeyEqual = std::equal_to<Key>,
jpayne@69 2417 size_t MaxLoadFactor100 = 80>
jpayne@69 2418 using unordered_node_set = detail::Table<false, MaxLoadFactor100, Key, void, Hash, KeyEqual>;
jpayne@69 2419
jpayne@69 2420 template <typename Key, typename Hash = hash<Key>, typename KeyEqual = std::equal_to<Key>,
jpayne@69 2421 size_t MaxLoadFactor100 = 80>
jpayne@69 2422 using unordered_set = detail::Table<sizeof(Key) <= sizeof(size_t) * 6 &&
jpayne@69 2423 std::is_nothrow_move_constructible<Key>::value &&
jpayne@69 2424 std::is_nothrow_move_assignable<Key>::value,
jpayne@69 2425 MaxLoadFactor100, Key, void, Hash, KeyEqual>;
jpayne@69 2426
jpayne@69 2427 } // namespace robin_hood
jpayne@69 2428
jpayne@69 2429 #endif