jpayne@69: // ______ _____ ______ _________ jpayne@69: // ______________ ___ /_ ___(_)_______ ___ /_ ______ ______ ______ / jpayne@69: // __ ___/_ __ \__ __ \__ / __ __ \ __ __ \_ __ \_ __ \_ __ / jpayne@69: // _ / / /_/ /_ /_/ /_ / _ / / / _ / / // /_/ // /_/ // /_/ / jpayne@69: // /_/ \____/ /_.___/ /_/ /_/ /_/ ________/_/ /_/ \____/ \____/ \__,_/ jpayne@69: // _/_____/ jpayne@69: // jpayne@69: // Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20 jpayne@69: // https://github.com/martinus/robin-hood-hashing jpayne@69: // jpayne@69: // Licensed under the MIT License . jpayne@69: // SPDX-License-Identifier: MIT jpayne@69: // Copyright (c) 2018-2020 Martin Ankerl jpayne@69: // jpayne@69: // Permission is hereby granted, free of charge, to any person obtaining a copy jpayne@69: // of this software and associated documentation files (the "Software"), to deal jpayne@69: // in the Software without restriction, including without limitation the rights jpayne@69: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell jpayne@69: // copies of the Software, and to permit persons to whom the Software is jpayne@69: // furnished to do so, subject to the following conditions: jpayne@69: // jpayne@69: // The above copyright notice and this permission notice shall be included in all jpayne@69: // copies or substantial portions of the Software. jpayne@69: // jpayne@69: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR jpayne@69: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, jpayne@69: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE jpayne@69: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER jpayne@69: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, jpayne@69: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE jpayne@69: // SOFTWARE. jpayne@69: jpayne@69: #ifndef ROBIN_HOOD_H_INCLUDED jpayne@69: #define ROBIN_HOOD_H_INCLUDED jpayne@69: jpayne@69: // see https://semver.org/ jpayne@69: #define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes jpayne@69: #define ROBIN_HOOD_VERSION_MINOR 9 // for adding functionality in a backwards-compatible manner jpayne@69: #define ROBIN_HOOD_VERSION_PATCH 1 // for backwards-compatible bug fixes jpayne@69: jpayne@69: #include jpayne@69: #include jpayne@69: #include jpayne@69: #include jpayne@69: #include // only to support hash of smart pointers jpayne@69: #include jpayne@69: #include jpayne@69: #include jpayne@69: #include jpayne@69: #if __cplusplus >= 201703L jpayne@69: # include jpayne@69: #endif jpayne@69: jpayne@69: // #define ROBIN_HOOD_LOG_ENABLED jpayne@69: #ifdef ROBIN_HOOD_LOG_ENABLED jpayne@69: # include jpayne@69: # define ROBIN_HOOD_LOG(...) \ jpayne@69: std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl; jpayne@69: #else jpayne@69: # define ROBIN_HOOD_LOG(x) jpayne@69: #endif jpayne@69: jpayne@69: // #define ROBIN_HOOD_TRACE_ENABLED jpayne@69: #ifdef ROBIN_HOOD_TRACE_ENABLED jpayne@69: # include jpayne@69: # define ROBIN_HOOD_TRACE(...) \ jpayne@69: std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl; jpayne@69: #else jpayne@69: # define ROBIN_HOOD_TRACE(x) jpayne@69: #endif jpayne@69: jpayne@69: // #define ROBIN_HOOD_COUNT_ENABLED jpayne@69: #ifdef ROBIN_HOOD_COUNT_ENABLED jpayne@69: # include jpayne@69: # define ROBIN_HOOD_COUNT(x) ++counts().x; jpayne@69: namespace robin_hood { jpayne@69: struct Counts { jpayne@69: uint64_t shiftUp{}; jpayne@69: uint64_t shiftDown{}; jpayne@69: }; jpayne@69: inline std::ostream& operator<<(std::ostream& os, Counts const& c) { jpayne@69: return os << c.shiftUp << " shiftUp" << std::endl << c.shiftDown << " shiftDown" << std::endl; jpayne@69: } jpayne@69: jpayne@69: static Counts& counts() { jpayne@69: static Counts counts{}; jpayne@69: return counts; jpayne@69: } jpayne@69: } // namespace robin_hood jpayne@69: #else jpayne@69: # define ROBIN_HOOD_COUNT(x) jpayne@69: #endif jpayne@69: jpayne@69: // all non-argument macros should use this facility. See jpayne@69: // https://www.fluentcpp.com/2019/05/28/better-macros-better-flags/ jpayne@69: #define ROBIN_HOOD(x) ROBIN_HOOD_PRIVATE_DEFINITION_##x() jpayne@69: jpayne@69: // mark unused members with this macro jpayne@69: #define ROBIN_HOOD_UNUSED(identifier) jpayne@69: jpayne@69: // bitness jpayne@69: #if SIZE_MAX == UINT32_MAX jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 32 jpayne@69: #elif SIZE_MAX == UINT64_MAX jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 64 jpayne@69: #else jpayne@69: # error Unsupported bitness jpayne@69: #endif jpayne@69: jpayne@69: // endianess jpayne@69: #ifdef _MSC_VER jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() 1 jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() 0 jpayne@69: #else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() \ jpayne@69: (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) jpayne@69: #endif jpayne@69: jpayne@69: // inline jpayne@69: #ifdef _MSC_VER jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __declspec(noinline) jpayne@69: #else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __attribute__((noinline)) jpayne@69: #endif jpayne@69: jpayne@69: // exceptions jpayne@69: #if !defined(__cpp_exceptions) && !defined(__EXCEPTIONS) && !defined(_CPPUNWIND) jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 0 jpayne@69: #else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 1 jpayne@69: #endif jpayne@69: jpayne@69: // count leading/trailing bits jpayne@69: #if !defined(ROBIN_HOOD_DISABLE_INTRINSICS) jpayne@69: # ifdef _MSC_VER jpayne@69: # if ROBIN_HOOD(BITNESS) == 32 jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward jpayne@69: # else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward64 jpayne@69: # endif jpayne@69: # include jpayne@69: # pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD)) jpayne@69: # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \ jpayne@69: [](size_t mask) noexcept -> int { \ jpayne@69: unsigned long index; \ jpayne@69: return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast(index) \ jpayne@69: : ROBIN_HOOD(BITNESS); \ jpayne@69: }(x) jpayne@69: # else jpayne@69: # if ROBIN_HOOD(BITNESS) == 32 jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl jpayne@69: # else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll jpayne@69: # endif jpayne@69: # define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS)) jpayne@69: # define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS)) jpayne@69: # endif jpayne@69: #endif jpayne@69: jpayne@69: // fallthrough jpayne@69: #ifndef __has_cpp_attribute // For backwards compatibility jpayne@69: # define __has_cpp_attribute(x) 0 jpayne@69: #endif jpayne@69: #if __has_cpp_attribute(clang::fallthrough) jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[clang::fallthrough]] jpayne@69: #elif __has_cpp_attribute(gnu::fallthrough) jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[gnu::fallthrough]] jpayne@69: #else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() jpayne@69: #endif jpayne@69: jpayne@69: // likely/unlikely jpayne@69: #ifdef _MSC_VER jpayne@69: # define ROBIN_HOOD_LIKELY(condition) condition jpayne@69: # define ROBIN_HOOD_UNLIKELY(condition) condition jpayne@69: #else jpayne@69: # define ROBIN_HOOD_LIKELY(condition) __builtin_expect(condition, 1) jpayne@69: # define ROBIN_HOOD_UNLIKELY(condition) __builtin_expect(condition, 0) jpayne@69: #endif jpayne@69: jpayne@69: // detect if native wchar_t type is availiable in MSVC jpayne@69: #ifdef _MSC_VER jpayne@69: # ifdef _NATIVE_WCHAR_T_DEFINED jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1 jpayne@69: # else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 0 jpayne@69: # endif jpayne@69: #else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1 jpayne@69: #endif jpayne@69: jpayne@69: // workaround missing "is_trivially_copyable" in g++ < 5.0 jpayne@69: // See https://stackoverflow.com/a/31798726/48181 jpayne@69: #if defined(__GNUC__) && __GNUC__ < 5 jpayne@69: # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__) jpayne@69: #else jpayne@69: # define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value jpayne@69: #endif jpayne@69: jpayne@69: // helpers for C++ versions, see https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html jpayne@69: #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX() __cplusplus jpayne@69: #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX98() 199711L jpayne@69: #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX11() 201103L jpayne@69: #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX14() 201402L jpayne@69: #define ROBIN_HOOD_PRIVATE_DEFINITION_CXX17() 201703L jpayne@69: jpayne@69: #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17) jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() [[nodiscard]] jpayne@69: #else jpayne@69: # define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() jpayne@69: #endif jpayne@69: jpayne@69: namespace robin_hood { jpayne@69: jpayne@69: #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) jpayne@69: # define ROBIN_HOOD_STD std jpayne@69: #else jpayne@69: jpayne@69: // c++11 compatibility layer jpayne@69: namespace ROBIN_HOOD_STD { jpayne@69: template jpayne@69: struct alignment_of jpayne@69: : std::integral_constant::type)> {}; jpayne@69: jpayne@69: template jpayne@69: class integer_sequence { jpayne@69: public: jpayne@69: using value_type = T; jpayne@69: static_assert(std::is_integral::value, "not integral type"); jpayne@69: static constexpr std::size_t size() noexcept { jpayne@69: return sizeof...(Ints); jpayne@69: } jpayne@69: }; jpayne@69: template jpayne@69: using index_sequence = integer_sequence; jpayne@69: jpayne@69: namespace detail_ { jpayne@69: template jpayne@69: struct IntSeqImpl { jpayne@69: using TValue = T; jpayne@69: static_assert(std::is_integral::value, "not integral type"); jpayne@69: static_assert(Begin >= 0 && Begin < End, "unexpected argument (Begin<0 || Begin<=End)"); jpayne@69: jpayne@69: template jpayne@69: struct IntSeqCombiner; jpayne@69: jpayne@69: template jpayne@69: struct IntSeqCombiner, integer_sequence> { jpayne@69: using TResult = integer_sequence; jpayne@69: }; jpayne@69: jpayne@69: using TResult = jpayne@69: typename IntSeqCombiner::TResult, jpayne@69: typename IntSeqImpl::TResult>::TResult; jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct IntSeqImpl { jpayne@69: using TValue = T; jpayne@69: static_assert(std::is_integral::value, "not integral type"); jpayne@69: static_assert(Begin >= 0, "unexpected argument (Begin<0)"); jpayne@69: using TResult = integer_sequence; jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct IntSeqImpl { jpayne@69: using TValue = T; jpayne@69: static_assert(std::is_integral::value, "not integral type"); jpayne@69: static_assert(Begin >= 0, "unexpected argument (Begin<0)"); jpayne@69: using TResult = integer_sequence; jpayne@69: }; jpayne@69: } // namespace detail_ jpayne@69: jpayne@69: template jpayne@69: using make_integer_sequence = typename detail_::IntSeqImpl::TResult; jpayne@69: jpayne@69: template jpayne@69: using make_index_sequence = make_integer_sequence; jpayne@69: jpayne@69: template jpayne@69: using index_sequence_for = make_index_sequence; jpayne@69: jpayne@69: } // namespace ROBIN_HOOD_STD jpayne@69: jpayne@69: #endif jpayne@69: jpayne@69: namespace detail { jpayne@69: jpayne@69: // make sure we static_cast to the correct type for hash_int jpayne@69: #if ROBIN_HOOD(BITNESS) == 64 jpayne@69: using SizeT = uint64_t; jpayne@69: #else jpayne@69: using SizeT = uint32_t; jpayne@69: #endif jpayne@69: jpayne@69: template jpayne@69: T rotr(T x, unsigned k) { jpayne@69: return (x >> k) | (x << (8U * sizeof(T) - k)); jpayne@69: } jpayne@69: jpayne@69: // This cast gets rid of warnings like "cast from 'uint8_t*' {aka 'unsigned char*'} to jpayne@69: // 'uint64_t*' {aka 'long unsigned int*'} increases required alignment of target type". Use with jpayne@69: // care! jpayne@69: template jpayne@69: inline T reinterpret_cast_no_cast_align_warning(void* ptr) noexcept { jpayne@69: return reinterpret_cast(ptr); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: inline T reinterpret_cast_no_cast_align_warning(void const* ptr) noexcept { jpayne@69: return reinterpret_cast(ptr); jpayne@69: } jpayne@69: jpayne@69: // make sure this is not inlined as it is slow and dramatically enlarges code, thus making other jpayne@69: // inlinings more difficult. Throws are also generally the slow path. jpayne@69: template jpayne@69: [[noreturn]] ROBIN_HOOD(NOINLINE) jpayne@69: #if ROBIN_HOOD(HAS_EXCEPTIONS) jpayne@69: void doThrow(Args&&... args) { jpayne@69: // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-array-to-pointer-decay) jpayne@69: throw E(std::forward(args)...); jpayne@69: } jpayne@69: #else jpayne@69: void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) /*unused*/) { jpayne@69: abort(); jpayne@69: } jpayne@69: #endif jpayne@69: jpayne@69: template jpayne@69: T* assertNotNull(T* t, Args&&... args) { jpayne@69: if (ROBIN_HOOD_UNLIKELY(nullptr == t)) { jpayne@69: doThrow(std::forward(args)...); jpayne@69: } jpayne@69: return t; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: inline T unaligned_load(void const* ptr) noexcept { jpayne@69: // using memcpy so we don't get into unaligned load problems. jpayne@69: // compiler should optimize this very well anyways. jpayne@69: T t; jpayne@69: std::memcpy(&t, ptr, sizeof(T)); jpayne@69: return t; jpayne@69: } jpayne@69: jpayne@69: // Allocates bulks of memory for objects of type T. This deallocates the memory in the destructor, jpayne@69: // and keeps a linked list of the allocated memory around. Overhead per allocation is the size of a jpayne@69: // pointer. jpayne@69: template jpayne@69: class BulkPoolAllocator { jpayne@69: public: jpayne@69: BulkPoolAllocator() noexcept = default; jpayne@69: jpayne@69: // does not copy anything, just creates a new allocator. jpayne@69: BulkPoolAllocator(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept jpayne@69: : mHead(nullptr) jpayne@69: , mListForFree(nullptr) {} jpayne@69: jpayne@69: BulkPoolAllocator(BulkPoolAllocator&& o) noexcept jpayne@69: : mHead(o.mHead) jpayne@69: , mListForFree(o.mListForFree) { jpayne@69: o.mListForFree = nullptr; jpayne@69: o.mHead = nullptr; jpayne@69: } jpayne@69: jpayne@69: BulkPoolAllocator& operator=(BulkPoolAllocator&& o) noexcept { jpayne@69: reset(); jpayne@69: mHead = o.mHead; jpayne@69: mListForFree = o.mListForFree; jpayne@69: o.mListForFree = nullptr; jpayne@69: o.mHead = nullptr; jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: BulkPoolAllocator& jpayne@69: // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) jpayne@69: operator=(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept { jpayne@69: // does not do anything jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: ~BulkPoolAllocator() noexcept { jpayne@69: reset(); jpayne@69: } jpayne@69: jpayne@69: // Deallocates all allocated memory. jpayne@69: void reset() noexcept { jpayne@69: while (mListForFree) { jpayne@69: T* tmp = *mListForFree; jpayne@69: ROBIN_HOOD_LOG("std::free") jpayne@69: std::free(mListForFree); jpayne@69: mListForFree = reinterpret_cast_no_cast_align_warning(tmp); jpayne@69: } jpayne@69: mHead = nullptr; jpayne@69: } jpayne@69: jpayne@69: // allocates, but does NOT initialize. Use in-place new constructor, e.g. jpayne@69: // T* obj = pool.allocate(); jpayne@69: // ::new (static_cast(obj)) T(); jpayne@69: T* allocate() { jpayne@69: T* tmp = mHead; jpayne@69: if (!tmp) { jpayne@69: tmp = performAllocation(); jpayne@69: } jpayne@69: jpayne@69: mHead = *reinterpret_cast_no_cast_align_warning(tmp); jpayne@69: return tmp; jpayne@69: } jpayne@69: jpayne@69: // does not actually deallocate but puts it in store. jpayne@69: // make sure you have already called the destructor! e.g. with jpayne@69: // obj->~T(); jpayne@69: // pool.deallocate(obj); jpayne@69: void deallocate(T* obj) noexcept { jpayne@69: *reinterpret_cast_no_cast_align_warning(obj) = mHead; jpayne@69: mHead = obj; jpayne@69: } jpayne@69: jpayne@69: // Adds an already allocated block of memory to the allocator. This allocator is from now on jpayne@69: // responsible for freeing the data (with free()). If the provided data is not large enough to jpayne@69: // make use of, it is immediately freed. Otherwise it is reused and freed in the destructor. jpayne@69: void addOrFree(void* ptr, const size_t numBytes) noexcept { jpayne@69: // calculate number of available elements in ptr jpayne@69: if (numBytes < ALIGNMENT + ALIGNED_SIZE) { jpayne@69: // not enough data for at least one element. Free and return. jpayne@69: ROBIN_HOOD_LOG("std::free") jpayne@69: std::free(ptr); jpayne@69: } else { jpayne@69: ROBIN_HOOD_LOG("add to buffer") jpayne@69: add(ptr, numBytes); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: void swap(BulkPoolAllocator& other) noexcept { jpayne@69: using std::swap; jpayne@69: swap(mHead, other.mHead); jpayne@69: swap(mListForFree, other.mListForFree); jpayne@69: } jpayne@69: jpayne@69: private: jpayne@69: // iterates the list of allocated memory to calculate how many to alloc next. jpayne@69: // Recalculating this each time saves us a size_t member. jpayne@69: // This ignores the fact that memory blocks might have been added manually with addOrFree. In jpayne@69: // practice, this should not matter much. jpayne@69: ROBIN_HOOD(NODISCARD) size_t calcNumElementsToAlloc() const noexcept { jpayne@69: auto tmp = mListForFree; jpayne@69: size_t numAllocs = MinNumAllocs; jpayne@69: jpayne@69: while (numAllocs * 2 <= MaxNumAllocs && tmp) { jpayne@69: auto x = reinterpret_cast(tmp); jpayne@69: tmp = *x; jpayne@69: numAllocs *= 2; jpayne@69: } jpayne@69: jpayne@69: return numAllocs; jpayne@69: } jpayne@69: jpayne@69: // WARNING: Underflow if numBytes < ALIGNMENT! This is guarded in addOrFree(). jpayne@69: void add(void* ptr, const size_t numBytes) noexcept { jpayne@69: const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE; jpayne@69: jpayne@69: auto data = reinterpret_cast(ptr); jpayne@69: jpayne@69: // link free list jpayne@69: auto x = reinterpret_cast(data); jpayne@69: *x = mListForFree; jpayne@69: mListForFree = data; jpayne@69: jpayne@69: // create linked list for newly allocated data jpayne@69: auto* const headT = jpayne@69: reinterpret_cast_no_cast_align_warning(reinterpret_cast(ptr) + ALIGNMENT); jpayne@69: jpayne@69: auto* const head = reinterpret_cast(headT); jpayne@69: jpayne@69: // Visual Studio compiler automatically unrolls this loop, which is pretty cool jpayne@69: for (size_t i = 0; i < numElements; ++i) { jpayne@69: *reinterpret_cast_no_cast_align_warning(head + i * ALIGNED_SIZE) = jpayne@69: head + (i + 1) * ALIGNED_SIZE; jpayne@69: } jpayne@69: jpayne@69: // last one points to 0 jpayne@69: *reinterpret_cast_no_cast_align_warning(head + (numElements - 1) * ALIGNED_SIZE) = jpayne@69: mHead; jpayne@69: mHead = headT; jpayne@69: } jpayne@69: jpayne@69: // Called when no memory is available (mHead == 0). jpayne@69: // Don't inline this slow path. jpayne@69: ROBIN_HOOD(NOINLINE) T* performAllocation() { jpayne@69: size_t const numElementsToAlloc = calcNumElementsToAlloc(); jpayne@69: jpayne@69: // alloc new memory: [prev |T, T, ... T] jpayne@69: size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc; jpayne@69: ROBIN_HOOD_LOG("std::malloc " << bytes << " = " << ALIGNMENT << " + " << ALIGNED_SIZE jpayne@69: << " * " << numElementsToAlloc) jpayne@69: add(assertNotNull(std::malloc(bytes)), bytes); jpayne@69: return mHead; jpayne@69: } jpayne@69: jpayne@69: // enforce byte alignment of the T's jpayne@69: #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) jpayne@69: static constexpr size_t ALIGNMENT = jpayne@69: (std::max)(std::alignment_of::value, std::alignment_of::value); jpayne@69: #else jpayne@69: static const size_t ALIGNMENT = jpayne@69: (ROBIN_HOOD_STD::alignment_of::value > ROBIN_HOOD_STD::alignment_of::value) jpayne@69: ? ROBIN_HOOD_STD::alignment_of::value jpayne@69: : +ROBIN_HOOD_STD::alignment_of::value; // the + is for walkarround jpayne@69: #endif jpayne@69: jpayne@69: static constexpr size_t ALIGNED_SIZE = ((sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT; jpayne@69: jpayne@69: static_assert(MinNumAllocs >= 1, "MinNumAllocs"); jpayne@69: static_assert(MaxNumAllocs >= MinNumAllocs, "MaxNumAllocs"); jpayne@69: static_assert(ALIGNED_SIZE >= sizeof(T*), "ALIGNED_SIZE"); jpayne@69: static_assert(0 == (ALIGNED_SIZE % sizeof(T*)), "ALIGNED_SIZE mod"); jpayne@69: static_assert(ALIGNMENT >= sizeof(T*), "ALIGNMENT"); jpayne@69: jpayne@69: T* mHead{nullptr}; jpayne@69: T** mListForFree{nullptr}; jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct NodeAllocator; jpayne@69: jpayne@69: // dummy allocator that does nothing jpayne@69: template jpayne@69: struct NodeAllocator { jpayne@69: jpayne@69: // we are not using the data, so just free it. jpayne@69: void addOrFree(void* ptr, size_t ROBIN_HOOD_UNUSED(numBytes) /*unused*/) noexcept { jpayne@69: ROBIN_HOOD_LOG("std::free") jpayne@69: std::free(ptr); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct NodeAllocator : public BulkPoolAllocator {}; jpayne@69: jpayne@69: // dummy hash, unsed as mixer when robin_hood::hash is already used jpayne@69: template jpayne@69: struct identity_hash { jpayne@69: constexpr size_t operator()(T const& obj) const noexcept { jpayne@69: return static_cast(obj); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: // c++14 doesn't have is_nothrow_swappable, and clang++ 6.0.1 doesn't like it either, so I'm making jpayne@69: // my own here. jpayne@69: namespace swappable { jpayne@69: #if ROBIN_HOOD(CXX) < ROBIN_HOOD(CXX17) jpayne@69: using std::swap; jpayne@69: template jpayne@69: struct nothrow { jpayne@69: static const bool value = noexcept(swap(std::declval(), std::declval())); jpayne@69: }; jpayne@69: #else jpayne@69: template jpayne@69: struct nothrow { jpayne@69: static const bool value = std::is_nothrow_swappable::value; jpayne@69: }; jpayne@69: #endif jpayne@69: } // namespace swappable jpayne@69: jpayne@69: } // namespace detail jpayne@69: jpayne@69: struct is_transparent_tag {}; jpayne@69: jpayne@69: // A custom pair implementation is used in the map because std::pair is not is_trivially_copyable, jpayne@69: // which means it would not be allowed to be used in std::memcpy. This struct is copyable, which is jpayne@69: // also tested. jpayne@69: template jpayne@69: struct pair { jpayne@69: using first_type = T1; jpayne@69: using second_type = T2; jpayne@69: jpayne@69: template ::value && jpayne@69: std::is_default_constructible::value>::type> jpayne@69: constexpr pair() noexcept(noexcept(U1()) && noexcept(U2())) jpayne@69: : first() jpayne@69: , second() {} jpayne@69: jpayne@69: // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. jpayne@69: explicit constexpr pair(std::pair const& o) noexcept( jpayne@69: noexcept(T1(std::declval())) && noexcept(T2(std::declval()))) jpayne@69: : first(o.first) jpayne@69: , second(o.second) {} jpayne@69: jpayne@69: // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. jpayne@69: explicit constexpr pair(std::pair&& o) noexcept(noexcept( jpayne@69: T1(std::move(std::declval()))) && noexcept(T2(std::move(std::declval())))) jpayne@69: : first(std::move(o.first)) jpayne@69: , second(std::move(o.second)) {} jpayne@69: jpayne@69: constexpr pair(T1&& a, T2&& b) noexcept(noexcept( jpayne@69: T1(std::move(std::declval()))) && noexcept(T2(std::move(std::declval())))) jpayne@69: : first(std::move(a)) jpayne@69: , second(std::move(b)) {} jpayne@69: jpayne@69: template jpayne@69: constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward( jpayne@69: std::declval()))) && noexcept(T2(std::forward(std::declval())))) jpayne@69: : first(std::forward(a)) jpayne@69: , second(std::forward(b)) {} jpayne@69: jpayne@69: template jpayne@69: constexpr pair( jpayne@69: std::piecewise_construct_t /*unused*/, std::tuple a, jpayne@69: std::tuple b) noexcept(noexcept(pair(std::declval&>(), jpayne@69: std::declval&>(), jpayne@69: ROBIN_HOOD_STD::index_sequence_for(), jpayne@69: ROBIN_HOOD_STD::index_sequence_for()))) jpayne@69: : pair(a, b, ROBIN_HOOD_STD::index_sequence_for(), jpayne@69: ROBIN_HOOD_STD::index_sequence_for()) {} jpayne@69: jpayne@69: // constructor called from the std::piecewise_construct_t ctor jpayne@69: template jpayne@69: pair(std::tuple& a, std::tuple& b, ROBIN_HOOD_STD::index_sequence /*unused*/, ROBIN_HOOD_STD::index_sequence /*unused*/) noexcept( jpayne@69: noexcept(T1(std::forward(std::get( jpayne@69: std::declval&>()))...)) && noexcept(T2(std:: jpayne@69: forward(std::get( jpayne@69: std::declval&>()))...))) jpayne@69: : first(std::forward(std::get(a))...) jpayne@69: , second(std::forward(std::get(b))...) { jpayne@69: // make visual studio compiler happy about warning about unused a & b. jpayne@69: // Visual studio's pair implementation disables warning 4100. jpayne@69: (void)a; jpayne@69: (void)b; jpayne@69: } jpayne@69: jpayne@69: void swap(pair& o) noexcept((detail::swappable::nothrow::value) && jpayne@69: (detail::swappable::nothrow::value)) { jpayne@69: using std::swap; jpayne@69: swap(first, o.first); jpayne@69: swap(second, o.second); jpayne@69: } jpayne@69: jpayne@69: T1 first; // NOLINT(misc-non-private-member-variables-in-classes) jpayne@69: T2 second; // NOLINT(misc-non-private-member-variables-in-classes) jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: inline void swap(pair& a, pair& b) noexcept( jpayne@69: noexcept(std::declval&>().swap(std::declval&>()))) { jpayne@69: a.swap(b); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: inline constexpr bool operator==(pair const& x, pair const& y) { jpayne@69: return (x.first == y.first) && (x.second == y.second); jpayne@69: } jpayne@69: template jpayne@69: inline constexpr bool operator!=(pair const& x, pair const& y) { jpayne@69: return !(x == y); jpayne@69: } jpayne@69: template jpayne@69: inline constexpr bool operator<(pair const& x, pair const& y) noexcept(noexcept( jpayne@69: std::declval() < std::declval ()) && noexcept(std::declval() < jpayne@69: std::declval())) { jpayne@69: return x.first < y.first || (!(y.first < x.first) && x.second < y.second); jpayne@69: } jpayne@69: template jpayne@69: inline constexpr bool operator>(pair const& x, pair const& y) { jpayne@69: return y < x; jpayne@69: } jpayne@69: template jpayne@69: inline constexpr bool operator<=(pair const& x, pair const& y) { jpayne@69: return !(x > y); jpayne@69: } jpayne@69: template jpayne@69: inline constexpr bool operator>=(pair const& x, pair const& y) { jpayne@69: return !(x < y); jpayne@69: } jpayne@69: jpayne@69: inline size_t hash_bytes(void const* ptr, size_t len) noexcept { jpayne@69: static constexpr uint64_t m = UINT64_C(0xc6a4a7935bd1e995); jpayne@69: static constexpr uint64_t seed = UINT64_C(0xe17a1465); jpayne@69: static constexpr unsigned int r = 47; jpayne@69: jpayne@69: auto const* const data64 = static_cast(ptr); jpayne@69: uint64_t h = seed ^ (len * m); jpayne@69: jpayne@69: size_t const n_blocks = len / 8; jpayne@69: for (size_t i = 0; i < n_blocks; ++i) { jpayne@69: auto k = detail::unaligned_load(data64 + i); jpayne@69: jpayne@69: k *= m; jpayne@69: k ^= k >> r; jpayne@69: k *= m; jpayne@69: jpayne@69: h ^= k; jpayne@69: h *= m; jpayne@69: } jpayne@69: jpayne@69: auto const* const data8 = reinterpret_cast(data64 + n_blocks); jpayne@69: switch (len & 7U) { jpayne@69: case 7: jpayne@69: h ^= static_cast(data8[6]) << 48U; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: case 6: jpayne@69: h ^= static_cast(data8[5]) << 40U; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: case 5: jpayne@69: h ^= static_cast(data8[4]) << 32U; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: case 4: jpayne@69: h ^= static_cast(data8[3]) << 24U; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: case 3: jpayne@69: h ^= static_cast(data8[2]) << 16U; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: case 2: jpayne@69: h ^= static_cast(data8[1]) << 8U; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: case 1: jpayne@69: h ^= static_cast(data8[0]); jpayne@69: h *= m; jpayne@69: ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH jpayne@69: default: jpayne@69: break; jpayne@69: } jpayne@69: jpayne@69: h ^= h >> r; jpayne@69: h *= m; jpayne@69: h ^= h >> r; jpayne@69: return static_cast(h); jpayne@69: } jpayne@69: jpayne@69: inline size_t hash_int(uint64_t x) noexcept { jpayne@69: // inspired by lemire's strongly universal hashing jpayne@69: // https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/ jpayne@69: // jpayne@69: // Instead of shifts, we use rotations so we don't lose any bits. jpayne@69: // jpayne@69: // Added a final multiplcation with a constant for more mixing. It is most important that jpayne@69: // the lower bits are well mixed. jpayne@69: auto h1 = x * UINT64_C(0xA24BAED4963EE407); jpayne@69: auto h2 = detail::rotr(x, 32U) * UINT64_C(0x9FB21C651E98DF25); jpayne@69: auto h = detail::rotr(h1 + h2, 32U); jpayne@69: return static_cast(h); jpayne@69: } jpayne@69: jpayne@69: // A thin wrapper around std::hash, performing an additional simple mixing step of the result. jpayne@69: template jpayne@69: struct hash : public std::hash { jpayne@69: size_t operator()(T const& obj) const jpayne@69: noexcept(noexcept(std::declval>().operator()(std::declval()))) { jpayne@69: // call base hash jpayne@69: auto result = std::hash::operator()(obj); jpayne@69: // return mixed of that, to be save against identity has jpayne@69: return hash_int(static_cast(result)); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct hash> { jpayne@69: size_t operator()(std::basic_string const& str) const noexcept { jpayne@69: return hash_bytes(str.data(), sizeof(CharT) * str.size()); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: #if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17) jpayne@69: template jpayne@69: struct hash> { jpayne@69: size_t operator()(std::basic_string_view const& sv) const noexcept { jpayne@69: return hash_bytes(sv.data(), sizeof(CharT) * sv.size()); jpayne@69: } jpayne@69: }; jpayne@69: #endif jpayne@69: jpayne@69: template jpayne@69: struct hash { jpayne@69: size_t operator()(T* ptr) const noexcept { jpayne@69: return hash_int(reinterpret_cast(ptr)); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct hash> { jpayne@69: size_t operator()(std::unique_ptr const& ptr) const noexcept { jpayne@69: return hash_int(reinterpret_cast(ptr.get())); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct hash> { jpayne@69: size_t operator()(std::shared_ptr const& ptr) const noexcept { jpayne@69: return hash_int(reinterpret_cast(ptr.get())); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct hash::value>::type> { jpayne@69: size_t operator()(Enum e) const noexcept { jpayne@69: using Underlying = typename std::underlying_type::type; jpayne@69: return hash{}(static_cast(e)); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: #define ROBIN_HOOD_HASH_INT(T) \ jpayne@69: template <> \ jpayne@69: struct hash { \ jpayne@69: size_t operator()(T const& obj) const noexcept { \ jpayne@69: return hash_int(static_cast(obj)); \ jpayne@69: } \ jpayne@69: } jpayne@69: jpayne@69: #if defined(__GNUC__) && !defined(__clang__) jpayne@69: # pragma GCC diagnostic push jpayne@69: # pragma GCC diagnostic ignored "-Wuseless-cast" jpayne@69: #endif jpayne@69: // see https://en.cppreference.com/w/cpp/utility/hash jpayne@69: ROBIN_HOOD_HASH_INT(bool); jpayne@69: ROBIN_HOOD_HASH_INT(char); jpayne@69: ROBIN_HOOD_HASH_INT(signed char); jpayne@69: ROBIN_HOOD_HASH_INT(unsigned char); jpayne@69: ROBIN_HOOD_HASH_INT(char16_t); jpayne@69: ROBIN_HOOD_HASH_INT(char32_t); jpayne@69: #if ROBIN_HOOD(HAS_NATIVE_WCHART) jpayne@69: ROBIN_HOOD_HASH_INT(wchar_t); jpayne@69: #endif jpayne@69: ROBIN_HOOD_HASH_INT(short); jpayne@69: ROBIN_HOOD_HASH_INT(unsigned short); jpayne@69: ROBIN_HOOD_HASH_INT(int); jpayne@69: ROBIN_HOOD_HASH_INT(unsigned int); jpayne@69: ROBIN_HOOD_HASH_INT(long); jpayne@69: ROBIN_HOOD_HASH_INT(long long); jpayne@69: ROBIN_HOOD_HASH_INT(unsigned long); jpayne@69: ROBIN_HOOD_HASH_INT(unsigned long long); jpayne@69: #if defined(__GNUC__) && !defined(__clang__) jpayne@69: # pragma GCC diagnostic pop jpayne@69: #endif jpayne@69: namespace detail { jpayne@69: jpayne@69: template jpayne@69: struct void_type { jpayne@69: using type = void; jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct has_is_transparent : public std::false_type {}; jpayne@69: jpayne@69: template jpayne@69: struct has_is_transparent::type> jpayne@69: : public std::true_type {}; jpayne@69: jpayne@69: // using wrapper classes for hash and key_equal prevents the diamond problem when the same type jpayne@69: // is used. see https://stackoverflow.com/a/28771920/48181 jpayne@69: template jpayne@69: struct WrapHash : public T { jpayne@69: WrapHash() = default; jpayne@69: explicit WrapHash(T const& o) noexcept(noexcept(T(std::declval()))) jpayne@69: : T(o) {} jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct WrapKeyEqual : public T { jpayne@69: WrapKeyEqual() = default; jpayne@69: explicit WrapKeyEqual(T const& o) noexcept(noexcept(T(std::declval()))) jpayne@69: : T(o) {} jpayne@69: }; jpayne@69: jpayne@69: // A highly optimized hashmap implementation, using the Robin Hood algorithm. jpayne@69: // jpayne@69: // In most cases, this map should be usable as a drop-in replacement for std::unordered_map, but jpayne@69: // be about 2x faster in most cases and require much less allocations. jpayne@69: // jpayne@69: // This implementation uses the following memory layout: jpayne@69: // jpayne@69: // [Node, Node, ... Node | info, info, ... infoSentinel ] jpayne@69: // jpayne@69: // * Node: either a DataNode that directly has the std::pair as member, jpayne@69: // or a DataNode with a pointer to std::pair. Which DataNode representation to use jpayne@69: // depends on how fast the swap() operation is. Heuristically, this is automatically choosen jpayne@69: // based on sizeof(). there are always 2^n Nodes. jpayne@69: // jpayne@69: // * info: Each Node in the map has a corresponding info byte, so there are 2^n info bytes. jpayne@69: // Each byte is initialized to 0, meaning the corresponding Node is empty. Set to 1 means the jpayne@69: // corresponding node contains data. Set to 2 means the corresponding Node is filled, but it jpayne@69: // actually belongs to the previous position and was pushed out because that place is already jpayne@69: // taken. jpayne@69: // jpayne@69: // * infoSentinel: Sentinel byte set to 1, so that iterator's ++ can stop at end() without the jpayne@69: // need for a idx variable. jpayne@69: // jpayne@69: // According to STL, order of templates has effect on throughput. That's why I've moved the jpayne@69: // boolean to the front. jpayne@69: // https://www.reddit.com/r/cpp/comments/ahp6iu/compile_time_binary_size_reductions_and_cs_future/eeguck4/ jpayne@69: template jpayne@69: class Table jpayne@69: : public WrapHash, jpayne@69: public WrapKeyEqual, jpayne@69: detail::NodeAllocator< jpayne@69: typename std::conditional< jpayne@69: std::is_void::value, Key, jpayne@69: robin_hood::pair::type, T>>::type, jpayne@69: 4, 16384, IsFlat> { jpayne@69: public: jpayne@69: static constexpr bool is_flat = IsFlat; jpayne@69: static constexpr bool is_map = !std::is_void::value; jpayne@69: static constexpr bool is_set = !is_map; jpayne@69: static constexpr bool is_transparent = jpayne@69: has_is_transparent::value && has_is_transparent::value; jpayne@69: jpayne@69: using key_type = Key; jpayne@69: using mapped_type = T; jpayne@69: using value_type = typename std::conditional< jpayne@69: is_set, Key, jpayne@69: robin_hood::pair::type, T>>::type; jpayne@69: using size_type = size_t; jpayne@69: using hasher = Hash; jpayne@69: using key_equal = KeyEqual; jpayne@69: using Self = Table; jpayne@69: jpayne@69: private: jpayne@69: static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100, jpayne@69: "MaxLoadFactor100 needs to be >10 && < 100"); jpayne@69: jpayne@69: using WHash = WrapHash; jpayne@69: using WKeyEqual = WrapKeyEqual; jpayne@69: jpayne@69: // configuration defaults jpayne@69: jpayne@69: // make sure we have 8 elements, needed to quickly rehash mInfo jpayne@69: static constexpr size_t InitialNumElements = sizeof(uint64_t); jpayne@69: static constexpr uint32_t InitialInfoNumBits = 5; jpayne@69: static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits; jpayne@69: static constexpr size_t InfoMask = InitialInfoInc - 1U; jpayne@69: static constexpr uint8_t InitialInfoHashShift = 0; jpayne@69: using DataPool = detail::NodeAllocator; jpayne@69: jpayne@69: // type needs to be wider than uint8_t. jpayne@69: using InfoType = uint32_t; jpayne@69: jpayne@69: // DataNode //////////////////////////////////////////////////////// jpayne@69: jpayne@69: // Primary template for the data node. We have special implementations for small and big jpayne@69: // objects. For large objects it is assumed that swap() is fairly slow, so we allocate these jpayne@69: // on the heap so swap merely swaps a pointer. jpayne@69: template jpayne@69: class DataNode {}; jpayne@69: jpayne@69: // Small: just allocate on the stack. jpayne@69: template jpayne@69: class DataNode final { jpayne@69: public: jpayne@69: template jpayne@69: explicit DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, Args&&... args) noexcept( jpayne@69: noexcept(value_type(std::forward(args)...))) jpayne@69: : mData(std::forward(args)...) {} jpayne@69: jpayne@69: DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept( jpayne@69: std::is_nothrow_move_constructible::value) jpayne@69: : mData(std::move(n.mData)) {} jpayne@69: jpayne@69: // doesn't do anything jpayne@69: void destroy(M& ROBIN_HOOD_UNUSED(map) /*unused*/) noexcept {} jpayne@69: void destroyDoNotDeallocate() noexcept {} jpayne@69: jpayne@69: value_type const* operator->() const noexcept { jpayne@69: return &mData; jpayne@69: } jpayne@69: value_type* operator->() noexcept { jpayne@69: return &mData; jpayne@69: } jpayne@69: jpayne@69: const value_type& operator*() const noexcept { jpayne@69: return mData; jpayne@69: } jpayne@69: jpayne@69: value_type& operator*() noexcept { jpayne@69: return mData; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getFirst() noexcept { jpayne@69: return mData.first; jpayne@69: } jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getFirst() noexcept { jpayne@69: return mData; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type jpayne@69: getFirst() const noexcept { jpayne@69: return mData.first; jpayne@69: } jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getFirst() const noexcept { jpayne@69: return mData; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getSecond() noexcept { jpayne@69: return mData.second; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getSecond() const noexcept { jpayne@69: return mData.second; jpayne@69: } jpayne@69: jpayne@69: void swap(DataNode& o) noexcept( jpayne@69: noexcept(std::declval().swap(std::declval()))) { jpayne@69: mData.swap(o.mData); jpayne@69: } jpayne@69: jpayne@69: private: jpayne@69: value_type mData; jpayne@69: }; jpayne@69: jpayne@69: // big object: allocate on heap. jpayne@69: template jpayne@69: class DataNode { jpayne@69: public: jpayne@69: template jpayne@69: explicit DataNode(M& map, Args&&... args) jpayne@69: : mData(map.allocate()) { jpayne@69: ::new (static_cast(mData)) value_type(std::forward(args)...); jpayne@69: } jpayne@69: jpayne@69: DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept jpayne@69: : mData(std::move(n.mData)) {} jpayne@69: jpayne@69: void destroy(M& map) noexcept { jpayne@69: // don't deallocate, just put it into list of datapool. jpayne@69: mData->~value_type(); jpayne@69: map.deallocate(mData); jpayne@69: } jpayne@69: jpayne@69: void destroyDoNotDeallocate() noexcept { jpayne@69: mData->~value_type(); jpayne@69: } jpayne@69: jpayne@69: value_type const* operator->() const noexcept { jpayne@69: return mData; jpayne@69: } jpayne@69: jpayne@69: value_type* operator->() noexcept { jpayne@69: return mData; jpayne@69: } jpayne@69: jpayne@69: const value_type& operator*() const { jpayne@69: return *mData; jpayne@69: } jpayne@69: jpayne@69: value_type& operator*() { jpayne@69: return *mData; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getFirst() noexcept { jpayne@69: return mData->first; jpayne@69: } jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getFirst() noexcept { jpayne@69: return *mData; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type jpayne@69: getFirst() const noexcept { jpayne@69: return mData->first; jpayne@69: } jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getFirst() const noexcept { jpayne@69: return *mData; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getSecond() noexcept { jpayne@69: return mData->second; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::type getSecond() const noexcept { jpayne@69: return mData->second; jpayne@69: } jpayne@69: jpayne@69: void swap(DataNode& o) noexcept { jpayne@69: using std::swap; jpayne@69: swap(mData, o.mData); jpayne@69: } jpayne@69: jpayne@69: private: jpayne@69: value_type* mData; jpayne@69: }; jpayne@69: jpayne@69: using Node = DataNode; jpayne@69: jpayne@69: // helpers for doInsert: extract first entry (only const required) jpayne@69: ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(Node const& n) const noexcept { jpayne@69: return n.getFirst(); jpayne@69: } jpayne@69: jpayne@69: // in case we have void mapped_type, we are not using a pair, thus we just route k through. jpayne@69: // No need to disable this because it's just not used if not applicable. jpayne@69: ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(key_type const& k) const noexcept { jpayne@69: return k; jpayne@69: } jpayne@69: jpayne@69: // in case we have non-void mapped_type, we have a standard robin_hood::pair jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::value, key_type const&>::type jpayne@69: getFirstConst(value_type const& vt) const noexcept { jpayne@69: return vt.first; jpayne@69: } jpayne@69: jpayne@69: // Cloner ////////////////////////////////////////////////////////// jpayne@69: jpayne@69: template jpayne@69: struct Cloner; jpayne@69: jpayne@69: // fast path: Just copy data, without allocating anything. jpayne@69: template jpayne@69: struct Cloner { jpayne@69: void operator()(M const& source, M& target) const { jpayne@69: auto const* const src = reinterpret_cast(source.mKeyVals); jpayne@69: auto* tgt = reinterpret_cast(target.mKeyVals); jpayne@69: auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1); jpayne@69: std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt); jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct Cloner { jpayne@69: void operator()(M const& s, M& t) const { jpayne@69: auto const numElementsWithBuffer = t.calcNumElementsWithBuffer(t.mMask + 1); jpayne@69: std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(numElementsWithBuffer), t.mInfo); jpayne@69: jpayne@69: for (size_t i = 0; i < numElementsWithBuffer; ++i) { jpayne@69: if (t.mInfo[i]) { jpayne@69: ::new (static_cast(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]); jpayne@69: } jpayne@69: } jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: // Destroyer /////////////////////////////////////////////////////// jpayne@69: jpayne@69: template jpayne@69: struct Destroyer {}; jpayne@69: jpayne@69: template jpayne@69: struct Destroyer { jpayne@69: void nodes(M& m) const noexcept { jpayne@69: m.mNumElements = 0; jpayne@69: } jpayne@69: jpayne@69: void nodesDoNotDeallocate(M& m) const noexcept { jpayne@69: m.mNumElements = 0; jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: struct Destroyer { jpayne@69: void nodes(M& m) const noexcept { jpayne@69: m.mNumElements = 0; jpayne@69: // clear also resets mInfo to 0, that's sometimes not necessary. jpayne@69: auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); jpayne@69: jpayne@69: for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { jpayne@69: if (0 != m.mInfo[idx]) { jpayne@69: Node& n = m.mKeyVals[idx]; jpayne@69: n.destroy(m); jpayne@69: n.~Node(); jpayne@69: } jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: void nodesDoNotDeallocate(M& m) const noexcept { jpayne@69: m.mNumElements = 0; jpayne@69: // clear also resets mInfo to 0, that's sometimes not necessary. jpayne@69: auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); jpayne@69: for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { jpayne@69: if (0 != m.mInfo[idx]) { jpayne@69: Node& n = m.mKeyVals[idx]; jpayne@69: n.destroyDoNotDeallocate(); jpayne@69: n.~Node(); jpayne@69: } jpayne@69: } jpayne@69: } jpayne@69: }; jpayne@69: jpayne@69: // Iter //////////////////////////////////////////////////////////// jpayne@69: jpayne@69: struct fast_forward_tag {}; jpayne@69: jpayne@69: // generic iterator for both const_iterator and iterator. jpayne@69: template jpayne@69: // NOLINTNEXTLINE(hicpp-special-member-functions,cppcoreguidelines-special-member-functions) jpayne@69: class Iter { jpayne@69: private: jpayne@69: using NodePtr = typename std::conditional::type; jpayne@69: jpayne@69: public: jpayne@69: using difference_type = std::ptrdiff_t; jpayne@69: using value_type = typename Self::value_type; jpayne@69: using reference = typename std::conditional::type; jpayne@69: using pointer = typename std::conditional::type; jpayne@69: using iterator_category = std::forward_iterator_tag; jpayne@69: jpayne@69: // default constructed iterator can be compared to itself, but WON'T return true when jpayne@69: // compared to end(). jpayne@69: Iter() = default; jpayne@69: jpayne@69: // Rule of zero: nothing specified. The conversion constructor is only enabled for jpayne@69: // iterator to const_iterator, so it doesn't accidentally work as a copy ctor. jpayne@69: jpayne@69: // Conversion constructor from iterator to const_iterator. jpayne@69: template ::type> jpayne@69: // NOLINTNEXTLINE(hicpp-explicit-conversions) jpayne@69: Iter(Iter const& other) noexcept jpayne@69: : mKeyVals(other.mKeyVals) jpayne@69: , mInfo(other.mInfo) {} jpayne@69: jpayne@69: Iter(NodePtr valPtr, uint8_t const* infoPtr) noexcept jpayne@69: : mKeyVals(valPtr) jpayne@69: , mInfo(infoPtr) {} jpayne@69: jpayne@69: Iter(NodePtr valPtr, uint8_t const* infoPtr, jpayne@69: fast_forward_tag ROBIN_HOOD_UNUSED(tag) /*unused*/) noexcept jpayne@69: : mKeyVals(valPtr) jpayne@69: , mInfo(infoPtr) { jpayne@69: fastForward(); jpayne@69: } jpayne@69: jpayne@69: template ::type> jpayne@69: Iter& operator=(Iter const& other) noexcept { jpayne@69: mKeyVals = other.mKeyVals; jpayne@69: mInfo = other.mInfo; jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: // prefix increment. Undefined behavior if we are at end()! jpayne@69: Iter& operator++() noexcept { jpayne@69: mInfo++; jpayne@69: mKeyVals++; jpayne@69: fastForward(); jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: Iter operator++(int) noexcept { jpayne@69: Iter tmp = *this; jpayne@69: ++(*this); jpayne@69: return tmp; jpayne@69: } jpayne@69: jpayne@69: reference operator*() const { jpayne@69: return **mKeyVals; jpayne@69: } jpayne@69: jpayne@69: pointer operator->() const { jpayne@69: return &**mKeyVals; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: bool operator==(Iter const& o) const noexcept { jpayne@69: return mKeyVals == o.mKeyVals; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: bool operator!=(Iter const& o) const noexcept { jpayne@69: return mKeyVals != o.mKeyVals; jpayne@69: } jpayne@69: jpayne@69: private: jpayne@69: // fast forward to the next non-free info byte jpayne@69: // I've tried a few variants that don't depend on intrinsics, but unfortunately they are jpayne@69: // quite a bit slower than this one. So I've reverted that change again. See map_benchmark. jpayne@69: void fastForward() noexcept { jpayne@69: size_t n = 0; jpayne@69: while (0U == (n = detail::unaligned_load(mInfo))) { jpayne@69: mInfo += sizeof(size_t); jpayne@69: mKeyVals += sizeof(size_t); jpayne@69: } jpayne@69: #if defined(ROBIN_HOOD_DISABLE_INTRINSICS) jpayne@69: // we know for certain that within the next 8 bytes we'll find a non-zero one. jpayne@69: if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load(mInfo))) { jpayne@69: mInfo += 4; jpayne@69: mKeyVals += 4; jpayne@69: } jpayne@69: if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load(mInfo))) { jpayne@69: mInfo += 2; jpayne@69: mKeyVals += 2; jpayne@69: } jpayne@69: if (ROBIN_HOOD_UNLIKELY(0U == *mInfo)) { jpayne@69: mInfo += 1; jpayne@69: mKeyVals += 1; jpayne@69: } jpayne@69: #else jpayne@69: # if ROBIN_HOOD(LITTLE_ENDIAN) jpayne@69: auto inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8; jpayne@69: # else jpayne@69: auto inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8; jpayne@69: # endif jpayne@69: mInfo += inc; jpayne@69: mKeyVals += inc; jpayne@69: #endif jpayne@69: } jpayne@69: jpayne@69: friend class Table; jpayne@69: NodePtr mKeyVals{nullptr}; jpayne@69: uint8_t const* mInfo{nullptr}; jpayne@69: }; jpayne@69: jpayne@69: //////////////////////////////////////////////////////////////////// jpayne@69: jpayne@69: // highly performance relevant code. jpayne@69: // Lower bits are used for indexing into the array (2^n size) jpayne@69: // The upper 1-5 bits need to be a reasonable good hash, to save comparisons. jpayne@69: template jpayne@69: void keyToIdx(HashKey&& key, size_t* idx, InfoType* info) const { jpayne@69: // for a user-specified hash that is *not* robin_hood::hash, apply robin_hood::hash as jpayne@69: // an additional mixing step. This serves as a bad hash prevention, if the given data is jpayne@69: // badly mixed. jpayne@69: using Mix = jpayne@69: typename std::conditional, hasher>::value, jpayne@69: ::robin_hood::detail::identity_hash, jpayne@69: ::robin_hood::hash>::type; jpayne@69: jpayne@69: // the lower InitialInfoNumBits are reserved for info. jpayne@69: auto h = Mix{}(WHash::operator()(key)); jpayne@69: *info = mInfoInc + static_cast((h & InfoMask) >> mInfoHashShift); jpayne@69: *idx = (h >> InitialInfoNumBits) & mMask; jpayne@69: } jpayne@69: jpayne@69: // forwards the index by one, wrapping around at the end jpayne@69: void next(InfoType* info, size_t* idx) const noexcept { jpayne@69: *idx = *idx + 1; jpayne@69: *info += mInfoInc; jpayne@69: } jpayne@69: jpayne@69: void nextWhileLess(InfoType* info, size_t* idx) const noexcept { jpayne@69: // unrolling this by hand did not bring any speedups. jpayne@69: while (*info < mInfo[*idx]) { jpayne@69: next(info, idx); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: // Shift everything up by one element. Tries to move stuff around. jpayne@69: void jpayne@69: shiftUp(size_t startIdx, jpayne@69: size_t const insertion_idx) noexcept(std::is_nothrow_move_assignable::value) { jpayne@69: auto idx = startIdx; jpayne@69: ::new (static_cast(mKeyVals + idx)) Node(std::move(mKeyVals[idx - 1])); jpayne@69: while (--idx != insertion_idx) { jpayne@69: mKeyVals[idx] = std::move(mKeyVals[idx - 1]); jpayne@69: } jpayne@69: jpayne@69: idx = startIdx; jpayne@69: while (idx != insertion_idx) { jpayne@69: ROBIN_HOOD_COUNT(shiftUp) jpayne@69: mInfo[idx] = static_cast(mInfo[idx - 1] + mInfoInc); jpayne@69: if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) { jpayne@69: mMaxNumElementsAllowed = 0; jpayne@69: } jpayne@69: --idx; jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: void shiftDown(size_t idx) noexcept(std::is_nothrow_move_assignable::value) { jpayne@69: // until we find one that is either empty or has zero offset. jpayne@69: // TODO(martinus) we don't need to move everything, just the last one for the same jpayne@69: // bucket. jpayne@69: mKeyVals[idx].destroy(*this); jpayne@69: jpayne@69: // until we find one that is either empty or has zero offset. jpayne@69: while (mInfo[idx + 1] >= 2 * mInfoInc) { jpayne@69: ROBIN_HOOD_COUNT(shiftDown) jpayne@69: mInfo[idx] = static_cast(mInfo[idx + 1] - mInfoInc); jpayne@69: mKeyVals[idx] = std::move(mKeyVals[idx + 1]); jpayne@69: ++idx; jpayne@69: } jpayne@69: jpayne@69: mInfo[idx] = 0; jpayne@69: // don't destroy, we've moved it jpayne@69: // mKeyVals[idx].destroy(*this); jpayne@69: mKeyVals[idx].~Node(); jpayne@69: } jpayne@69: jpayne@69: // copy of find(), except that it returns iterator instead of const_iterator. jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: size_t findIdx(Other const& key) const { jpayne@69: size_t idx{}; jpayne@69: InfoType info{}; jpayne@69: keyToIdx(key, &idx, &info); jpayne@69: jpayne@69: do { jpayne@69: // unrolling this twice gives a bit of a speedup. More unrolling did not help. jpayne@69: if (info == mInfo[idx] && jpayne@69: ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { jpayne@69: return idx; jpayne@69: } jpayne@69: next(&info, &idx); jpayne@69: if (info == mInfo[idx] && jpayne@69: ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { jpayne@69: return idx; jpayne@69: } jpayne@69: next(&info, &idx); jpayne@69: } while (info <= mInfo[idx]); jpayne@69: jpayne@69: // nothing found! jpayne@69: return mMask == 0 ? 0 jpayne@69: : static_cast(std::distance( jpayne@69: mKeyVals, reinterpret_cast_no_cast_align_warning(mInfo))); jpayne@69: } jpayne@69: jpayne@69: void cloneData(const Table& o) { jpayne@69: Cloner()(o, *this); jpayne@69: } jpayne@69: jpayne@69: // inserts a keyval that is guaranteed to be new, e.g. when the hashmap is resized. jpayne@69: // @return index where the element was created jpayne@69: size_t insert_move(Node&& keyval) { jpayne@69: // we don't retry, fail if overflowing jpayne@69: // don't need to check max num elements jpayne@69: if (0 == mMaxNumElementsAllowed && !try_increase_info()) { jpayne@69: throwOverflowError(); // impossible to reach LCOV_EXCL_LINE jpayne@69: } jpayne@69: jpayne@69: size_t idx{}; jpayne@69: InfoType info{}; jpayne@69: keyToIdx(keyval.getFirst(), &idx, &info); jpayne@69: jpayne@69: // skip forward. Use <= because we are certain that the element is not there. jpayne@69: while (info <= mInfo[idx]) { jpayne@69: idx = idx + 1; jpayne@69: info += mInfoInc; jpayne@69: } jpayne@69: jpayne@69: // key not found, so we are now exactly where we want to insert it. jpayne@69: auto const insertion_idx = idx; jpayne@69: auto const insertion_info = static_cast(info); jpayne@69: if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { jpayne@69: mMaxNumElementsAllowed = 0; jpayne@69: } jpayne@69: jpayne@69: // find an empty spot jpayne@69: while (0 != mInfo[idx]) { jpayne@69: next(&info, &idx); jpayne@69: } jpayne@69: jpayne@69: auto& l = mKeyVals[insertion_idx]; jpayne@69: if (idx == insertion_idx) { jpayne@69: ::new (static_cast(&l)) Node(std::move(keyval)); jpayne@69: } else { jpayne@69: shiftUp(idx, insertion_idx); jpayne@69: l = std::move(keyval); jpayne@69: } jpayne@69: jpayne@69: // put at empty spot jpayne@69: mInfo[insertion_idx] = insertion_info; jpayne@69: jpayne@69: ++mNumElements; jpayne@69: return insertion_idx; jpayne@69: } jpayne@69: jpayne@69: public: jpayne@69: using iterator = Iter; jpayne@69: using const_iterator = Iter; jpayne@69: jpayne@69: Table() noexcept(noexcept(Hash()) && noexcept(KeyEqual())) jpayne@69: : WHash() jpayne@69: , WKeyEqual() { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: } jpayne@69: jpayne@69: // Creates an empty hash map. Nothing is allocated yet, this happens at the first insert. jpayne@69: // This tremendously speeds up ctor & dtor of a map that never receives an element. The jpayne@69: // penalty is payed at the first insert, and not before. Lookup of this empty map works jpayne@69: // because everybody points to DummyInfoByte::b. parameter bucket_count is dictated by the jpayne@69: // standard, but we can ignore it. jpayne@69: explicit Table( jpayne@69: size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/, const Hash& h = Hash{}, jpayne@69: const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && noexcept(KeyEqual(equal))) jpayne@69: : WHash(h) jpayne@69: , WKeyEqual(equal) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: Table(Iter first, Iter last, size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, jpayne@69: const Hash& h = Hash{}, const KeyEqual& equal = KeyEqual{}) jpayne@69: : WHash(h) jpayne@69: , WKeyEqual(equal) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: insert(first, last); jpayne@69: } jpayne@69: jpayne@69: Table(std::initializer_list initlist, jpayne@69: size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, const Hash& h = Hash{}, jpayne@69: const KeyEqual& equal = KeyEqual{}) jpayne@69: : WHash(h) jpayne@69: , WKeyEqual(equal) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: insert(initlist.begin(), initlist.end()); jpayne@69: } jpayne@69: jpayne@69: Table(Table&& o) noexcept jpayne@69: : WHash(std::move(static_cast(o))) jpayne@69: , WKeyEqual(std::move(static_cast(o))) jpayne@69: , DataPool(std::move(static_cast(o))) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (o.mMask) { jpayne@69: mKeyVals = std::move(o.mKeyVals); jpayne@69: mInfo = std::move(o.mInfo); jpayne@69: mNumElements = std::move(o.mNumElements); jpayne@69: mMask = std::move(o.mMask); jpayne@69: mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed); jpayne@69: mInfoInc = std::move(o.mInfoInc); jpayne@69: mInfoHashShift = std::move(o.mInfoHashShift); jpayne@69: // set other's mask to 0 so its destructor won't do anything jpayne@69: o.init(); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: Table& operator=(Table&& o) noexcept { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (&o != this) { jpayne@69: if (o.mMask) { jpayne@69: // only move stuff if the other map actually has some data jpayne@69: destroy(); jpayne@69: mKeyVals = std::move(o.mKeyVals); jpayne@69: mInfo = std::move(o.mInfo); jpayne@69: mNumElements = std::move(o.mNumElements); jpayne@69: mMask = std::move(o.mMask); jpayne@69: mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed); jpayne@69: mInfoInc = std::move(o.mInfoInc); jpayne@69: mInfoHashShift = std::move(o.mInfoHashShift); jpayne@69: WHash::operator=(std::move(static_cast(o))); jpayne@69: WKeyEqual::operator=(std::move(static_cast(o))); jpayne@69: DataPool::operator=(std::move(static_cast(o))); jpayne@69: jpayne@69: o.init(); jpayne@69: jpayne@69: } else { jpayne@69: // nothing in the other map => just clear us. jpayne@69: clear(); jpayne@69: } jpayne@69: } jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: Table(const Table& o) jpayne@69: : WHash(static_cast(o)) jpayne@69: , WKeyEqual(static_cast(o)) jpayne@69: , DataPool(static_cast(o)) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (!o.empty()) { jpayne@69: // not empty: create an exact copy. it is also possible to just iterate through all jpayne@69: // elements and insert them, but copying is probably faster. jpayne@69: jpayne@69: auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); jpayne@69: auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); jpayne@69: jpayne@69: ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal(" jpayne@69: << numElementsWithBuffer << ")") jpayne@69: mKeyVals = static_cast( jpayne@69: detail::assertNotNull(std::malloc(numBytesTotal))); jpayne@69: // no need for calloc because clonData does memcpy jpayne@69: mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); jpayne@69: mNumElements = o.mNumElements; jpayne@69: mMask = o.mMask; jpayne@69: mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; jpayne@69: mInfoInc = o.mInfoInc; jpayne@69: mInfoHashShift = o.mInfoHashShift; jpayne@69: cloneData(o); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: // Creates a copy of the given map. Copy constructor of each entry is used. jpayne@69: // Not sure why clang-tidy thinks this doesn't handle self assignment, it does jpayne@69: // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) jpayne@69: Table& operator=(Table const& o) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (&o == this) { jpayne@69: // prevent assigning of itself jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: // we keep using the old allocator and not assign the new one, because we want to keep jpayne@69: // the memory available. when it is the same size. jpayne@69: if (o.empty()) { jpayne@69: if (0 == mMask) { jpayne@69: // nothing to do, we are empty too jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: // not empty: destroy what we have there jpayne@69: // clear also resets mInfo to 0, that's sometimes not necessary. jpayne@69: destroy(); jpayne@69: init(); jpayne@69: WHash::operator=(static_cast(o)); jpayne@69: WKeyEqual::operator=(static_cast(o)); jpayne@69: DataPool::operator=(static_cast(o)); jpayne@69: jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: // clean up old stuff jpayne@69: Destroyer::value>{}.nodes(*this); jpayne@69: jpayne@69: if (mMask != o.mMask) { jpayne@69: // no luck: we don't have the same array size allocated, so we need to realloc. jpayne@69: if (0 != mMask) { jpayne@69: // only deallocate if we actually have data! jpayne@69: ROBIN_HOOD_LOG("std::free") jpayne@69: std::free(mKeyVals); jpayne@69: } jpayne@69: jpayne@69: auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); jpayne@69: auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); jpayne@69: ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal(" jpayne@69: << numElementsWithBuffer << ")") jpayne@69: mKeyVals = static_cast( jpayne@69: detail::assertNotNull(std::malloc(numBytesTotal))); jpayne@69: jpayne@69: // no need for calloc here because cloneData performs a memcpy. jpayne@69: mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); jpayne@69: // sentinel is set in cloneData jpayne@69: } jpayne@69: WHash::operator=(static_cast(o)); jpayne@69: WKeyEqual::operator=(static_cast(o)); jpayne@69: DataPool::operator=(static_cast(o)); jpayne@69: mNumElements = o.mNumElements; jpayne@69: mMask = o.mMask; jpayne@69: mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; jpayne@69: mInfoInc = o.mInfoInc; jpayne@69: mInfoHashShift = o.mInfoHashShift; jpayne@69: cloneData(o); jpayne@69: jpayne@69: return *this; jpayne@69: } jpayne@69: jpayne@69: // Swaps everything between the two maps. jpayne@69: void swap(Table& o) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: using std::swap; jpayne@69: swap(o, *this); jpayne@69: } jpayne@69: jpayne@69: // Clears all data, without resizing. jpayne@69: void clear() { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (empty()) { jpayne@69: // don't do anything! also important because we don't want to write to jpayne@69: // DummyInfoByte::b, even though we would just write 0 to it. jpayne@69: return; jpayne@69: } jpayne@69: jpayne@69: Destroyer::value>{}.nodes(*this); jpayne@69: jpayne@69: auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); jpayne@69: // clear everything, then set the sentinel again jpayne@69: uint8_t const z = 0; jpayne@69: std::fill(mInfo, mInfo + calcNumBytesInfo(numElementsWithBuffer), z); jpayne@69: mInfo[numElementsWithBuffer] = 1; jpayne@69: jpayne@69: mInfoInc = InitialInfoInc; jpayne@69: mInfoHashShift = InitialInfoHashShift; jpayne@69: } jpayne@69: jpayne@69: // Destroys the map and all it's contents. jpayne@69: ~Table() { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: destroy(); jpayne@69: } jpayne@69: jpayne@69: // Checks if both tables contain the same entries. Order is irrelevant. jpayne@69: bool operator==(const Table& other) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (other.size() != size()) { jpayne@69: return false; jpayne@69: } jpayne@69: for (auto const& otherEntry : other) { jpayne@69: if (!has(otherEntry)) { jpayne@69: return false; jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: return true; jpayne@69: } jpayne@69: jpayne@69: bool operator!=(const Table& other) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return !operator==(other); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: typename std::enable_if::value, Q&>::type operator[](const key_type& key) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return doCreateByKey(key); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: typename std::enable_if::value, Q&>::type operator[](key_type&& key) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return doCreateByKey(std::move(key)); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: void insert(Iter first, Iter last) { jpayne@69: for (; first != last; ++first) { jpayne@69: // value_type ctor needed because this might be called with std::pair's jpayne@69: insert(value_type(*first)); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair emplace(Args&&... args) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: Node n{*this, std::forward(args)...}; jpayne@69: auto r = doInsert(std::move(n)); jpayne@69: if (!r.second) { jpayne@69: // insertion not possible: destroy node jpayne@69: // NOLINTNEXTLINE(bugprone-use-after-move) jpayne@69: n.destroy(*this); jpayne@69: } jpayne@69: return r; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair try_emplace(const key_type& key, Args&&... args) { jpayne@69: return try_emplace_impl(key, std::forward(args)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair try_emplace(key_type&& key, Args&&... args) { jpayne@69: return try_emplace_impl(std::move(key), std::forward(args)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair try_emplace(const_iterator hint, const key_type& key, jpayne@69: Args&&... args) { jpayne@69: (void)hint; jpayne@69: return try_emplace_impl(key, std::forward(args)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair try_emplace(const_iterator hint, key_type&& key, Args&&... args) { jpayne@69: (void)hint; jpayne@69: return try_emplace_impl(std::move(key), std::forward(args)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair insert_or_assign(const key_type& key, Mapped&& obj) { jpayne@69: return insert_or_assign_impl(key, std::forward(obj)); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair insert_or_assign(key_type&& key, Mapped&& obj) { jpayne@69: return insert_or_assign_impl(std::move(key), std::forward(obj)); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair insert_or_assign(const_iterator hint, const key_type& key, jpayne@69: Mapped&& obj) { jpayne@69: (void)hint; jpayne@69: return insert_or_assign_impl(key, std::forward(obj)); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair insert_or_assign(const_iterator hint, key_type&& key, Mapped&& obj) { jpayne@69: (void)hint; jpayne@69: return insert_or_assign_impl(std::move(key), std::forward(obj)); jpayne@69: } jpayne@69: jpayne@69: std::pair insert(const value_type& keyval) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return doInsert(keyval); jpayne@69: } jpayne@69: jpayne@69: std::pair insert(value_type&& keyval) { jpayne@69: return doInsert(std::move(keyval)); jpayne@69: } jpayne@69: jpayne@69: // Returns 1 if key is found, 0 otherwise. jpayne@69: size_t count(const key_type& key) const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto kv = mKeyVals + findIdx(key); jpayne@69: if (kv != reinterpret_cast_no_cast_align_warning(mInfo)) { jpayne@69: return 1; jpayne@69: } jpayne@69: return 0; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: // NOLINTNEXTLINE(modernize-use-nodiscard) jpayne@69: typename std::enable_if::type count(const OtherKey& key) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto kv = mKeyVals + findIdx(key); jpayne@69: if (kv != reinterpret_cast_no_cast_align_warning(mInfo)) { jpayne@69: return 1; jpayne@69: } jpayne@69: return 0; jpayne@69: } jpayne@69: jpayne@69: bool contains(const key_type& key) const { // NOLINT(modernize-use-nodiscard) jpayne@69: return 1U == count(key); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: // NOLINTNEXTLINE(modernize-use-nodiscard) jpayne@69: typename std::enable_if::type contains(const OtherKey& key) const { jpayne@69: return 1U == count(key); jpayne@69: } jpayne@69: jpayne@69: // Returns a reference to the value found for key. jpayne@69: // Throws std::out_of_range if element cannot be found jpayne@69: template jpayne@69: // NOLINTNEXTLINE(modernize-use-nodiscard) jpayne@69: typename std::enable_if::value, Q&>::type at(key_type const& key) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto kv = mKeyVals + findIdx(key); jpayne@69: if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { jpayne@69: doThrow("key not found"); jpayne@69: } jpayne@69: return kv->getSecond(); jpayne@69: } jpayne@69: jpayne@69: // Returns a reference to the value found for key. jpayne@69: // Throws std::out_of_range if element cannot be found jpayne@69: template jpayne@69: // NOLINTNEXTLINE(modernize-use-nodiscard) jpayne@69: typename std::enable_if::value, Q const&>::type at(key_type const& key) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto kv = mKeyVals + findIdx(key); jpayne@69: if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { jpayne@69: doThrow("key not found"); jpayne@69: } jpayne@69: return kv->getSecond(); jpayne@69: } jpayne@69: jpayne@69: const_iterator find(const key_type& key) const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: const size_t idx = findIdx(key); jpayne@69: return const_iterator{mKeyVals + idx, mInfo + idx}; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: const_iterator find(const OtherKey& key, is_transparent_tag /*unused*/) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: const size_t idx = findIdx(key); jpayne@69: return const_iterator{mKeyVals + idx, mInfo + idx}; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: typename std::enable_if::type // NOLINT(modernize-use-nodiscard) jpayne@69: find(const OtherKey& key) const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: const size_t idx = findIdx(key); jpayne@69: return const_iterator{mKeyVals + idx, mInfo + idx}; jpayne@69: } jpayne@69: jpayne@69: iterator find(const key_type& key) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: const size_t idx = findIdx(key); jpayne@69: return iterator{mKeyVals + idx, mInfo + idx}; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: iterator find(const OtherKey& key, is_transparent_tag /*unused*/) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: const size_t idx = findIdx(key); jpayne@69: return iterator{mKeyVals + idx, mInfo + idx}; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: typename std::enable_if::type find(const OtherKey& key) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: const size_t idx = findIdx(key); jpayne@69: return iterator{mKeyVals + idx, mInfo + idx}; jpayne@69: } jpayne@69: jpayne@69: iterator begin() { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (empty()) { jpayne@69: return end(); jpayne@69: } jpayne@69: return iterator(mKeyVals, mInfo, fast_forward_tag{}); jpayne@69: } jpayne@69: const_iterator begin() const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return cbegin(); jpayne@69: } jpayne@69: const_iterator cbegin() const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: if (empty()) { jpayne@69: return cend(); jpayne@69: } jpayne@69: return const_iterator(mKeyVals, mInfo, fast_forward_tag{}); jpayne@69: } jpayne@69: jpayne@69: iterator end() { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: // no need to supply valid info pointer: end() must not be dereferenced, and only node jpayne@69: // pointer is compared. jpayne@69: return iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; jpayne@69: } jpayne@69: const_iterator end() const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return cend(); jpayne@69: } jpayne@69: const_iterator cend() const { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return const_iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; jpayne@69: } jpayne@69: jpayne@69: iterator erase(const_iterator pos) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: // its safe to perform const cast here jpayne@69: // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) jpayne@69: return erase(iterator{const_cast(pos.mKeyVals), const_cast(pos.mInfo)}); jpayne@69: } jpayne@69: jpayne@69: // Erases element at pos, returns iterator to the next element. jpayne@69: iterator erase(iterator pos) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: // we assume that pos always points to a valid entry, and not end(). jpayne@69: auto const idx = static_cast(pos.mKeyVals - mKeyVals); jpayne@69: jpayne@69: shiftDown(idx); jpayne@69: --mNumElements; jpayne@69: jpayne@69: if (*pos.mInfo) { jpayne@69: // we've backward shifted, return this again jpayne@69: return pos; jpayne@69: } jpayne@69: jpayne@69: // no backward shift, return next element jpayne@69: return ++pos; jpayne@69: } jpayne@69: jpayne@69: size_t erase(const key_type& key) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: size_t idx{}; jpayne@69: InfoType info{}; jpayne@69: keyToIdx(key, &idx, &info); jpayne@69: jpayne@69: // check while info matches with the source idx jpayne@69: do { jpayne@69: if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { jpayne@69: shiftDown(idx); jpayne@69: --mNumElements; jpayne@69: return 1; jpayne@69: } jpayne@69: next(&info, &idx); jpayne@69: } while (info <= mInfo[idx]); jpayne@69: jpayne@69: // nothing found to delete jpayne@69: return 0; jpayne@69: } jpayne@69: jpayne@69: // reserves space for the specified number of elements. Makes sure the old data fits. jpayne@69: // exactly the same as reserve(c). jpayne@69: void rehash(size_t c) { jpayne@69: // forces a reserve jpayne@69: reserve(c, true); jpayne@69: } jpayne@69: jpayne@69: // reserves space for the specified number of elements. Makes sure the old data fits. jpayne@69: // Exactly the same as rehash(c). Use rehash(0) to shrink to fit. jpayne@69: void reserve(size_t c) { jpayne@69: // reserve, but don't force rehash jpayne@69: reserve(c, false); jpayne@69: } jpayne@69: jpayne@69: size_type size() const noexcept { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return mNumElements; jpayne@69: } jpayne@69: jpayne@69: size_type max_size() const noexcept { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return static_cast(-1); jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD(NODISCARD) bool empty() const noexcept { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return 0 == mNumElements; jpayne@69: } jpayne@69: jpayne@69: float max_load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return MaxLoadFactor100 / 100.0F; jpayne@69: } jpayne@69: jpayne@69: // Average number of elements per bucket. Since we allow only 1 per bucket jpayne@69: float load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return static_cast(size()) / static_cast(mMask + 1); jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD(NODISCARD) size_t mask() const noexcept { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return mMask; jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD(NODISCARD) size_t calcMaxNumElementsAllowed(size_t maxElements) const noexcept { jpayne@69: if (ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits::max)() / 100)) { jpayne@69: return maxElements * MaxLoadFactor100 / 100; jpayne@69: } jpayne@69: jpayne@69: // we might be a bit inprecise, but since maxElements is quite large that doesn't matter jpayne@69: return (maxElements / 100) * MaxLoadFactor100; jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD(NODISCARD) size_t calcNumBytesInfo(size_t numElements) const noexcept { jpayne@69: // we add a uint64_t, which houses the sentinel (first byte) and padding so we can load jpayne@69: // 64bit types. jpayne@69: return numElements + sizeof(uint64_t); jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: size_t calcNumElementsWithBuffer(size_t numElements) const noexcept { jpayne@69: auto maxNumElementsAllowed = calcMaxNumElementsAllowed(numElements); jpayne@69: return numElements + (std::min)(maxNumElementsAllowed, (static_cast(0xFF))); jpayne@69: } jpayne@69: jpayne@69: // calculation only allowed for 2^n values jpayne@69: ROBIN_HOOD(NODISCARD) size_t calcNumBytesTotal(size_t numElements) const { jpayne@69: #if ROBIN_HOOD(BITNESS) == 64 jpayne@69: return numElements * sizeof(Node) + calcNumBytesInfo(numElements); jpayne@69: #else jpayne@69: // make sure we're doing 64bit operations, so we are at least safe against 32bit overflows. jpayne@69: auto const ne = static_cast(numElements); jpayne@69: auto const s = static_cast(sizeof(Node)); jpayne@69: auto const infos = static_cast(calcNumBytesInfo(numElements)); jpayne@69: jpayne@69: auto const total64 = ne * s + infos; jpayne@69: auto const total = static_cast(total64); jpayne@69: jpayne@69: if (ROBIN_HOOD_UNLIKELY(static_cast(total) != total64)) { jpayne@69: throwOverflowError(); jpayne@69: } jpayne@69: return total; jpayne@69: #endif jpayne@69: } jpayne@69: jpayne@69: private: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::value, bool>::type has(const value_type& e) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto it = find(e.first); jpayne@69: return it != end() && it->second == e.second; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: ROBIN_HOOD(NODISCARD) jpayne@69: typename std::enable_if::value, bool>::type has(const value_type& e) const { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: return find(e) != end(); jpayne@69: } jpayne@69: jpayne@69: void reserve(size_t c, bool forceRehash) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto const minElementsAllowed = (std::max)(c, mNumElements); jpayne@69: auto newSize = InitialNumElements; jpayne@69: while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) { jpayne@69: newSize *= 2; jpayne@69: } jpayne@69: if (ROBIN_HOOD_UNLIKELY(newSize == 0)) { jpayne@69: throwOverflowError(); jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD_LOG("newSize > mMask + 1: " << newSize << " > " << mMask << " + 1") jpayne@69: jpayne@69: // only actually do anything when the new size is bigger than the old one. This prevents to jpayne@69: // continuously allocate for each reserve() call. jpayne@69: if (forceRehash || newSize > mMask + 1) { jpayne@69: rehashPowerOfTwo(newSize); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: // reserves space for at least the specified number of elements. jpayne@69: // only works if numBuckets if power of two jpayne@69: void rehashPowerOfTwo(size_t numBuckets) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: jpayne@69: Node* const oldKeyVals = mKeyVals; jpayne@69: uint8_t const* const oldInfo = mInfo; jpayne@69: jpayne@69: const size_t oldMaxElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); jpayne@69: jpayne@69: // resize operation: move stuff jpayne@69: init_data(numBuckets); jpayne@69: if (oldMaxElementsWithBuffer > 1) { jpayne@69: for (size_t i = 0; i < oldMaxElementsWithBuffer; ++i) { jpayne@69: if (oldInfo[i] != 0) { jpayne@69: insert_move(std::move(oldKeyVals[i])); jpayne@69: // destroy the node but DON'T destroy the data. jpayne@69: oldKeyVals[i].~Node(); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: // this check is not necessary as it's guarded by the previous if, but it helps silence jpayne@69: // g++'s overeager "attempt to free a non-heap object 'map' jpayne@69: // [-Werror=free-nonheap-object]" warning. jpayne@69: if (oldKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { jpayne@69: // don't destroy old data: put it into the pool instead jpayne@69: DataPool::addOrFree(oldKeyVals, calcNumBytesTotal(oldMaxElementsWithBuffer)); jpayne@69: } jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD(NOINLINE) void throwOverflowError() const { jpayne@69: #if ROBIN_HOOD(HAS_EXCEPTIONS) jpayne@69: throw std::overflow_error("robin_hood::map overflow"); jpayne@69: #else jpayne@69: abort(); jpayne@69: #endif jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair try_emplace_impl(OtherKey&& key, Args&&... args) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto it = find(key); jpayne@69: if (it == end()) { jpayne@69: return emplace(std::piecewise_construct, jpayne@69: std::forward_as_tuple(std::forward(key)), jpayne@69: std::forward_as_tuple(std::forward(args)...)); jpayne@69: } jpayne@69: return {it, false}; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: std::pair insert_or_assign_impl(OtherKey&& key, Mapped&& obj) { jpayne@69: ROBIN_HOOD_TRACE(this) jpayne@69: auto it = find(key); jpayne@69: if (it == end()) { jpayne@69: return emplace(std::forward(key), std::forward(obj)); jpayne@69: } jpayne@69: it->second = std::forward(obj); jpayne@69: return {it, false}; jpayne@69: } jpayne@69: jpayne@69: void init_data(size_t max_elements) { jpayne@69: mNumElements = 0; jpayne@69: mMask = max_elements - 1; jpayne@69: mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements); jpayne@69: jpayne@69: auto const numElementsWithBuffer = calcNumElementsWithBuffer(max_elements); jpayne@69: jpayne@69: // calloc also zeroes everything jpayne@69: auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); jpayne@69: ROBIN_HOOD_LOG("std::calloc " << numBytesTotal << " = calcNumBytesTotal(" jpayne@69: << numElementsWithBuffer << ")") jpayne@69: mKeyVals = reinterpret_cast( jpayne@69: detail::assertNotNull(std::calloc(1, numBytesTotal))); jpayne@69: mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); jpayne@69: jpayne@69: // set sentinel jpayne@69: mInfo[numElementsWithBuffer] = 1; jpayne@69: jpayne@69: mInfoInc = InitialInfoInc; jpayne@69: mInfoHashShift = InitialInfoHashShift; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: typename std::enable_if::value, Q&>::type doCreateByKey(Arg&& key) { jpayne@69: while (true) { jpayne@69: size_t idx{}; jpayne@69: InfoType info{}; jpayne@69: keyToIdx(key, &idx, &info); jpayne@69: nextWhileLess(&info, &idx); jpayne@69: jpayne@69: // while we potentially have a match. Can't do a do-while here because when mInfo is jpayne@69: // 0 we don't want to skip forward jpayne@69: while (info == mInfo[idx]) { jpayne@69: if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { jpayne@69: // key already exists, do not insert. jpayne@69: return mKeyVals[idx].getSecond(); jpayne@69: } jpayne@69: next(&info, &idx); jpayne@69: } jpayne@69: jpayne@69: // unlikely that this evaluates to true jpayne@69: if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) { jpayne@69: increase_size(); jpayne@69: continue; jpayne@69: } jpayne@69: jpayne@69: // key not found, so we are now exactly where we want to insert it. jpayne@69: auto const insertion_idx = idx; jpayne@69: auto const insertion_info = info; jpayne@69: if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { jpayne@69: mMaxNumElementsAllowed = 0; jpayne@69: } jpayne@69: jpayne@69: // find an empty spot jpayne@69: while (0 != mInfo[idx]) { jpayne@69: next(&info, &idx); jpayne@69: } jpayne@69: jpayne@69: auto& l = mKeyVals[insertion_idx]; jpayne@69: if (idx == insertion_idx) { jpayne@69: // put at empty spot. This forwards all arguments into the node where the object jpayne@69: // is constructed exactly where it is needed. jpayne@69: ::new (static_cast(&l)) jpayne@69: Node(*this, std::piecewise_construct, jpayne@69: std::forward_as_tuple(std::forward(key)), std::forward_as_tuple()); jpayne@69: } else { jpayne@69: shiftUp(idx, insertion_idx); jpayne@69: l = Node(*this, std::piecewise_construct, jpayne@69: std::forward_as_tuple(std::forward(key)), std::forward_as_tuple()); jpayne@69: } jpayne@69: jpayne@69: // mKeyVals[idx].getFirst() = std::move(key); jpayne@69: mInfo[insertion_idx] = static_cast(insertion_info); jpayne@69: jpayne@69: ++mNumElements; jpayne@69: return mKeyVals[insertion_idx].getSecond(); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: // This is exactly the same code as operator[], except for the return values jpayne@69: template jpayne@69: std::pair doInsert(Arg&& keyval) { jpayne@69: while (true) { jpayne@69: size_t idx{}; jpayne@69: InfoType info{}; jpayne@69: keyToIdx(getFirstConst(keyval), &idx, &info); jpayne@69: nextWhileLess(&info, &idx); jpayne@69: jpayne@69: // while we potentially have a match jpayne@69: while (info == mInfo[idx]) { jpayne@69: if (WKeyEqual::operator()(getFirstConst(keyval), mKeyVals[idx].getFirst())) { jpayne@69: // key already exists, do NOT insert. jpayne@69: // see http://en.cppreference.com/w/cpp/container/unordered_map/insert jpayne@69: return std::make_pair(iterator(mKeyVals + idx, mInfo + idx), jpayne@69: false); jpayne@69: } jpayne@69: next(&info, &idx); jpayne@69: } jpayne@69: jpayne@69: // unlikely that this evaluates to true jpayne@69: if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) { jpayne@69: increase_size(); jpayne@69: continue; jpayne@69: } jpayne@69: jpayne@69: // key not found, so we are now exactly where we want to insert it. jpayne@69: auto const insertion_idx = idx; jpayne@69: auto const insertion_info = info; jpayne@69: if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { jpayne@69: mMaxNumElementsAllowed = 0; jpayne@69: } jpayne@69: jpayne@69: // find an empty spot jpayne@69: while (0 != mInfo[idx]) { jpayne@69: next(&info, &idx); jpayne@69: } jpayne@69: jpayne@69: auto& l = mKeyVals[insertion_idx]; jpayne@69: if (idx == insertion_idx) { jpayne@69: ::new (static_cast(&l)) Node(*this, std::forward(keyval)); jpayne@69: } else { jpayne@69: shiftUp(idx, insertion_idx); jpayne@69: l = Node(*this, std::forward(keyval)); jpayne@69: } jpayne@69: jpayne@69: // put at empty spot jpayne@69: mInfo[insertion_idx] = static_cast(insertion_info); jpayne@69: jpayne@69: ++mNumElements; jpayne@69: return std::make_pair(iterator(mKeyVals + insertion_idx, mInfo + insertion_idx), true); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: bool try_increase_info() { jpayne@69: ROBIN_HOOD_LOG("mInfoInc=" << mInfoInc << ", numElements=" << mNumElements jpayne@69: << ", maxNumElementsAllowed=" jpayne@69: << calcMaxNumElementsAllowed(mMask + 1)) jpayne@69: if (mInfoInc <= 2) { jpayne@69: // need to be > 2 so that shift works (otherwise undefined behavior!) jpayne@69: return false; jpayne@69: } jpayne@69: // we got space left, try to make info smaller jpayne@69: mInfoInc = static_cast(mInfoInc >> 1U); jpayne@69: jpayne@69: // remove one bit of the hash, leaving more space for the distance info. jpayne@69: // This is extremely fast because we can operate on 8 bytes at once. jpayne@69: ++mInfoHashShift; jpayne@69: auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); jpayne@69: jpayne@69: for (size_t i = 0; i < numElementsWithBuffer; i += 8) { jpayne@69: auto val = unaligned_load(mInfo + i); jpayne@69: val = (val >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f); jpayne@69: std::memcpy(mInfo + i, &val, sizeof(val)); jpayne@69: } jpayne@69: // update sentinel, which might have been cleared out! jpayne@69: mInfo[numElementsWithBuffer] = 1; jpayne@69: jpayne@69: mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); jpayne@69: return true; jpayne@69: } jpayne@69: jpayne@69: void increase_size() { jpayne@69: // nothing allocated yet? just allocate InitialNumElements jpayne@69: if (0 == mMask) { jpayne@69: init_data(InitialNumElements); jpayne@69: return; jpayne@69: } jpayne@69: jpayne@69: auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); jpayne@69: if (mNumElements < maxNumElementsAllowed && try_increase_info()) { jpayne@69: return; jpayne@69: } jpayne@69: jpayne@69: ROBIN_HOOD_LOG("mNumElements=" << mNumElements << ", maxNumElementsAllowed=" jpayne@69: << maxNumElementsAllowed << ", load=" jpayne@69: << (static_cast(mNumElements) * 100.0 / jpayne@69: (static_cast(mMask) + 1))) jpayne@69: // it seems we have a really bad hash function! don't try to resize again jpayne@69: if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) { jpayne@69: throwOverflowError(); jpayne@69: } jpayne@69: jpayne@69: rehashPowerOfTwo((mMask + 1) * 2); jpayne@69: } jpayne@69: jpayne@69: void destroy() { jpayne@69: if (0 == mMask) { jpayne@69: // don't deallocate! jpayne@69: return; jpayne@69: } jpayne@69: jpayne@69: Destroyer::value>{} jpayne@69: .nodesDoNotDeallocate(*this); jpayne@69: jpayne@69: // This protection against not deleting mMask shouldn't be needed as it's sufficiently jpayne@69: // protected with the 0==mMask check, but I have this anyways because g++ 7 otherwise jpayne@69: // reports a compile error: attempt to free a non-heap object 'fm' jpayne@69: // [-Werror=free-nonheap-object] jpayne@69: if (mKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { jpayne@69: ROBIN_HOOD_LOG("std::free") jpayne@69: std::free(mKeyVals); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: void init() noexcept { jpayne@69: mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); jpayne@69: mInfo = reinterpret_cast(&mMask); jpayne@69: mNumElements = 0; jpayne@69: mMask = 0; jpayne@69: mMaxNumElementsAllowed = 0; jpayne@69: mInfoInc = InitialInfoInc; jpayne@69: mInfoHashShift = InitialInfoHashShift; jpayne@69: } jpayne@69: jpayne@69: // members are sorted so no padding occurs jpayne@69: Node* mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); // 8 byte 8 jpayne@69: uint8_t* mInfo = reinterpret_cast(&mMask); // 8 byte 16 jpayne@69: size_t mNumElements = 0; // 8 byte 24 jpayne@69: size_t mMask = 0; // 8 byte 32 jpayne@69: size_t mMaxNumElementsAllowed = 0; // 8 byte 40 jpayne@69: InfoType mInfoInc = InitialInfoInc; // 4 byte 44 jpayne@69: InfoType mInfoHashShift = InitialInfoHashShift; // 4 byte 48 jpayne@69: // 16 byte 56 if NodeAllocator jpayne@69: }; jpayne@69: jpayne@69: } // namespace detail jpayne@69: jpayne@69: // map jpayne@69: jpayne@69: template , jpayne@69: typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> jpayne@69: using unordered_flat_map = detail::Table; jpayne@69: jpayne@69: template , jpayne@69: typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> jpayne@69: using unordered_node_map = detail::Table; jpayne@69: jpayne@69: template , jpayne@69: typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> jpayne@69: using unordered_map = jpayne@69: detail::Table) <= sizeof(size_t) * 6 && jpayne@69: std::is_nothrow_move_constructible>::value && jpayne@69: std::is_nothrow_move_assignable>::value, jpayne@69: MaxLoadFactor100, Key, T, Hash, KeyEqual>; jpayne@69: jpayne@69: // set jpayne@69: jpayne@69: template , typename KeyEqual = std::equal_to, jpayne@69: size_t MaxLoadFactor100 = 80> jpayne@69: using unordered_flat_set = detail::Table; jpayne@69: jpayne@69: template , typename KeyEqual = std::equal_to, jpayne@69: size_t MaxLoadFactor100 = 80> jpayne@69: using unordered_node_set = detail::Table; jpayne@69: jpayne@69: template , typename KeyEqual = std::equal_to, jpayne@69: size_t MaxLoadFactor100 = 80> jpayne@69: using unordered_set = detail::Table::value && jpayne@69: std::is_nothrow_move_assignable::value, jpayne@69: MaxLoadFactor100, Key, void, Hash, KeyEqual>; jpayne@69: jpayne@69: } // namespace robin_hood jpayne@69: jpayne@69: #endif