From b94170eefce899d0b236804681d77fe026956fd9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 6 Jul 2022 22:26:53 +0200 Subject: Version 3.7. Make sure to check NEWS/Changes in README.md for a few code-breaking API changes. --- README.md | 14 +- benchmarks/build_all.sh | 2 +- benchmarks/external/ankerl/robin_hood.h | 2544 ++++++++++++++++++++++++++++++ benchmarks/external/robin_hood.h | 2544 ------------------------------ benchmarks/external/tsl/robin_hash.h | 1 + benchmarks/external/update.sh | 43 +- benchmarks/misc/rust_cmap.c | 6 +- benchmarks/misc/string_bench_STC.cpp | 16 +- benchmarks/picobench/picobench_cmap.cpp | 51 +- benchmarks/picobench/picobench_csmap.cpp | 10 +- benchmarks/plotbench/cdeq_benchmark.cpp | 6 +- benchmarks/plotbench/cmap_benchmark.cpp | 4 +- benchmarks/plotbench/csmap_benchmark.cpp | 4 +- benchmarks/plotbench/cvec_benchmark.cpp | 4 +- benchmarks/shootout_hashmaps.cpp | 78 +- docs/carc_api.md | 2 +- docs/carray_api.md | 8 +- docs/cbox_api.md | 2 +- docs/cdeq_api.md | 8 +- docs/clist_api.md | 2 +- docs/cmap_api.md | 10 +- docs/cpque_api.md | 6 +- docs/cqueue_api.md | 2 +- docs/cset_api.md | 10 +- docs/csmap_api.md | 7 +- docs/csset_api.md | 2 +- docs/cstack_api.md | 8 +- docs/cstr_api.md | 1 - docs/cvec_api.md | 8 +- examples/astar.c | 2 +- examples/bits2.c | 2 +- examples/books.c | 2 +- examples/complex.c | 2 +- examples/convert.c | 2 +- examples/cpque.c | 2 +- examples/csmap_erase.c | 2 +- examples/csmap_find.c | 10 +- examples/demos.c | 8 +- examples/inits.c | 2 +- examples/new_arr.c | 4 +- examples/new_pque.c | 4 +- examples/new_queue.c | 4 +- examples/queue.c | 2 +- examples/stack.c | 1 + include/stc/alt/csmap.h | 6 +- include/stc/carc.h | 2 +- include/stc/carr2.h | 18 +- include/stc/carr3.h | 20 +- include/stc/cbits.h | 26 +- include/stc/cbox.h | 6 +- include/stc/cdeq.h | 32 +- include/stc/clist.h | 11 +- include/stc/cmap.h | 26 +- include/stc/cpque.h | 23 +- include/stc/cqueue.h | 4 +- include/stc/csmap.h | 26 +- include/stc/cstack.h | 75 +- include/stc/cstr.h | 3 - include/stc/cvec.h | 43 +- include/stc/forward.h | 8 + include/stc/template.h | 1 + 61 files changed, 2918 insertions(+), 2864 deletions(-) create mode 100644 benchmarks/external/ankerl/robin_hood.h delete mode 100644 benchmarks/external/robin_hood.h diff --git a/README.md b/README.md index ef896068..f74888d8 100644 --- a/README.md +++ b/README.md @@ -3,9 +3,9 @@ STC - Smart Template Containers for C ===================================== -News: Version 3.6 released (April 2022) +News: Version 3.7 released (July 2022) --------------------------------------- -- See [Changes version 3.6](#changes-version-36) +- [See changes version 3](#version-3). Note some code-breaking API changes! Introduction ------------ @@ -457,6 +457,16 @@ Memory efficiency # Version 3 +## Changes version 3.7 +- NB! Changed self argument from value to const pointer on containers (does not apply to **cstr**): + - `CNT_size(const CNT *self)` + - `CNT_capacity(const CNT *self)` + - `CNT_empty(const CNT *self)` +- Now both **cstack** and **cbits** can be used with template `i_cap` parameter: `#define i_cap `. They then use fixed sized arrays, and no heap allocated memory. +- Renamed *cstr_rename_n()* => *cstr_rename_with_n()* as it could be confused with replacing n instances instead of n bytes. +- Renamed macro *c_apply_arr()* => *c_apply_array()* +- Fixed bug in `csmap.h`: begin() on empty map was not fully initialized. + ## Changes version 3.6 - Swapped to new **cstr** (*short string optimized*, aka SSO). Note that `cstr_str(&s)` must be used, `s.str` is no longer usable. - Removed *redundant* size argument to `i_hash` template parameter and `c_default_hash`. Please update your code. diff --git a/benchmarks/build_all.sh b/benchmarks/build_all.sh index 348a79dd..1093807c 100644 --- a/benchmarks/build_all.sh +++ b/benchmarks/build_all.sh @@ -1,5 +1,5 @@ #!/bin/bash -cc='g++ -std=c++17' +cc='g++ -std=c++20' #cc='clang' #cc='clang -c -DSTC_HEADER' #cc='cl -nologo' diff --git a/benchmarks/external/ankerl/robin_hood.h b/benchmarks/external/ankerl/robin_hood.h new file mode 100644 index 00000000..0af031f5 --- /dev/null +++ b/benchmarks/external/ankerl/robin_hood.h @@ -0,0 +1,2544 @@ +// ______ _____ ______ _________ +// ______________ ___ /_ ___(_)_______ ___ /_ ______ ______ ______ / +// __ ___/_ __ \__ __ \__ / __ __ \ __ __ \_ __ \_ __ \_ __ / +// _ / / /_/ /_ /_/ /_ / _ / / / _ / / // /_/ // /_/ // /_/ / +// /_/ \____/ /_.___/ /_/ /_/ /_/ ________/_/ /_/ \____/ \____/ \__,_/ +// _/_____/ +// +// Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20 +// https://github.com/martinus/robin-hood-hashing +// +// Licensed under the MIT License . +// SPDX-License-Identifier: MIT +// Copyright (c) 2018-2021 Martin Ankerl +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to deal +// in the Software without restriction, including without limitation the rights +// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all +// copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +// SOFTWARE. + +#ifndef ROBIN_HOOD_H_INCLUDED +#define ROBIN_HOOD_H_INCLUDED + +// see https://semver.org/ +#define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes +#define ROBIN_HOOD_VERSION_MINOR 11 // for adding functionality in a backwards-compatible manner +#define ROBIN_HOOD_VERSION_PATCH 5 // for backwards-compatible bug fixes + +#include +#include +#include +#include +#include +#include // only to support hash of smart pointers +#include +#include +#include +#include +#if __cplusplus >= 201703L +# include +#endif + +// #define ROBIN_HOOD_LOG_ENABLED +#ifdef ROBIN_HOOD_LOG_ENABLED +# include +# define ROBIN_HOOD_LOG(...) \ + std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl; +#else +# define ROBIN_HOOD_LOG(x) +#endif + +// #define ROBIN_HOOD_TRACE_ENABLED +#ifdef ROBIN_HOOD_TRACE_ENABLED +# include +# define ROBIN_HOOD_TRACE(...) \ + std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl; +#else +# define ROBIN_HOOD_TRACE(x) +#endif + +// #define ROBIN_HOOD_COUNT_ENABLED +#ifdef ROBIN_HOOD_COUNT_ENABLED +# include +# define ROBIN_HOOD_COUNT(x) ++counts().x; +namespace robin_hood { +struct Counts { + uint64_t shiftUp{}; + uint64_t shiftDown{}; +}; +inline std::ostream& operator<<(std::ostream& os, Counts const& c) { + return os << c.shiftUp << " shiftUp" << std::endl << c.shiftDown << " shiftDown" << std::endl; +} + +static Counts& counts() { + static Counts counts{}; + return counts; +} +} // namespace robin_hood +#else +# define ROBIN_HOOD_COUNT(x) +#endif + +// all non-argument macros should use this facility. See +// https://www.fluentcpp.com/2019/05/28/better-macros-better-flags/ +#define ROBIN_HOOD(x) ROBIN_HOOD_PRIVATE_DEFINITION_##x() + +// mark unused members with this macro +#define ROBIN_HOOD_UNUSED(identifier) + +// bitness +#if SIZE_MAX == UINT32_MAX +# define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 32 +#elif SIZE_MAX == UINT64_MAX +# define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 64 +#else +# error Unsupported bitness +#endif + +// endianess +#ifdef _MSC_VER +# define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() 1 +# define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() 0 +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() \ + (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) +# define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) +#endif + +// inline +#ifdef _MSC_VER +# define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __declspec(noinline) +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __attribute__((noinline)) +#endif + +// exceptions +#if !defined(__cpp_exceptions) && !defined(__EXCEPTIONS) && !defined(_CPPUNWIND) +# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 0 +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 1 +#endif + +// count leading/trailing bits +#if !defined(ROBIN_HOOD_DISABLE_INTRINSICS) +# ifdef _MSC_VER +# if ROBIN_HOOD(BITNESS) == 32 +# define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward +# else +# define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward64 +# endif +# include +# pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD)) +# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \ + [](size_t mask) noexcept -> int { \ + unsigned long index; \ + return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast(index) \ + : ROBIN_HOOD(BITNESS); \ + }(x) +# else +# if ROBIN_HOOD(BITNESS) == 32 +# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl +# define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl +# else +# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll +# define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll +# endif +# define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS)) +# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS)) +# endif +#endif + +// fallthrough +#ifndef __has_cpp_attribute // For backwards compatibility +# define __has_cpp_attribute(x) 0 +#endif +#if __has_cpp_attribute(clang::fallthrough) +# define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[clang::fallthrough]] +#elif __has_cpp_attribute(gnu::fallthrough) +# define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[gnu::fallthrough]] +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() +#endif + +// likely/unlikely +#ifdef _MSC_VER +# define ROBIN_HOOD_LIKELY(condition) condition +# define ROBIN_HOOD_UNLIKELY(condition) condition +#else +# define ROBIN_HOOD_LIKELY(condition) __builtin_expect(condition, 1) +# define ROBIN_HOOD_UNLIKELY(condition) __builtin_expect(condition, 0) +#endif + +// detect if native wchar_t type is availiable in MSVC +#ifdef _MSC_VER +# ifdef _NATIVE_WCHAR_T_DEFINED +# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1 +# else +# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 0 +# endif +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1 +#endif + +// detect if MSVC supports the pair(std::piecewise_construct_t,...) consructor being constexpr +#ifdef _MSC_VER +# if _MSC_VER <= 1900 +# define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 1 +# else +# define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 0 +# endif +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 0 +#endif + +// workaround missing "is_trivially_copyable" in g++ < 5.0 +// See https://stackoverflow.com/a/31798726/48181 +#if defined(__GNUC__) && __GNUC__ < 5 +# define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__) +#else +# define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value +#endif + +// helpers for C++ versions, see https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html +#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX() __cplusplus +#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX98() 199711L +#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX11() 201103L +#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX14() 201402L +#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX17() 201703L + +#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17) +# define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() [[nodiscard]] +#else +# define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() +#endif + +namespace robin_hood { + +#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) +# define ROBIN_HOOD_STD std +#else + +// c++11 compatibility layer +namespace ROBIN_HOOD_STD { +template +struct alignment_of + : std::integral_constant::type)> {}; + +template +class integer_sequence { +public: + using value_type = T; + static_assert(std::is_integral::value, "not integral type"); + static constexpr std::size_t size() noexcept { + return sizeof...(Ints); + } +}; +template +using index_sequence = integer_sequence; + +namespace detail_ { +template +struct IntSeqImpl { + using TValue = T; + static_assert(std::is_integral::value, "not integral type"); + static_assert(Begin >= 0 && Begin < End, "unexpected argument (Begin<0 || Begin<=End)"); + + template + struct IntSeqCombiner; + + template + struct IntSeqCombiner, integer_sequence> { + using TResult = integer_sequence; + }; + + using TResult = + typename IntSeqCombiner::TResult, + typename IntSeqImpl::TResult>::TResult; +}; + +template +struct IntSeqImpl { + using TValue = T; + static_assert(std::is_integral::value, "not integral type"); + static_assert(Begin >= 0, "unexpected argument (Begin<0)"); + using TResult = integer_sequence; +}; + +template +struct IntSeqImpl { + using TValue = T; + static_assert(std::is_integral::value, "not integral type"); + static_assert(Begin >= 0, "unexpected argument (Begin<0)"); + using TResult = integer_sequence; +}; +} // namespace detail_ + +template +using make_integer_sequence = typename detail_::IntSeqImpl::TResult; + +template +using make_index_sequence = make_integer_sequence; + +template +using index_sequence_for = make_index_sequence; + +} // namespace ROBIN_HOOD_STD + +#endif + +namespace detail { + +// make sure we static_cast to the correct type for hash_int +#if ROBIN_HOOD(BITNESS) == 64 +using SizeT = uint64_t; +#else +using SizeT = uint32_t; +#endif + +template +T rotr(T x, unsigned k) { + return (x >> k) | (x << (8U * sizeof(T) - k)); +} + +// This cast gets rid of warnings like "cast from 'uint8_t*' {aka 'unsigned char*'} to +// 'uint64_t*' {aka 'long unsigned int*'} increases required alignment of target type". Use with +// care! +template +inline T reinterpret_cast_no_cast_align_warning(void* ptr) noexcept { + return reinterpret_cast(ptr); +} + +template +inline T reinterpret_cast_no_cast_align_warning(void const* ptr) noexcept { + return reinterpret_cast(ptr); +} + +// make sure this is not inlined as it is slow and dramatically enlarges code, thus making other +// inlinings more difficult. Throws are also generally the slow path. +template +[[noreturn]] ROBIN_HOOD(NOINLINE) +#if ROBIN_HOOD(HAS_EXCEPTIONS) + void doThrow(Args&&... args) { + // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-array-to-pointer-decay) + throw E(std::forward(args)...); +} +#else + void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) /*unused*/) { + abort(); +} +#endif + +template +T* assertNotNull(T* t, Args&&... args) { + if (ROBIN_HOOD_UNLIKELY(nullptr == t)) { + doThrow(std::forward(args)...); + } + return t; +} + +template +inline T unaligned_load(void const* ptr) noexcept { + // using memcpy so we don't get into unaligned load problems. + // compiler should optimize this very well anyways. + T t; + std::memcpy(&t, ptr, sizeof(T)); + return t; +} + +// Allocates bulks of memory for objects of type T. This deallocates the memory in the destructor, +// and keeps a linked list of the allocated memory around. Overhead per allocation is the size of a +// pointer. +template +class BulkPoolAllocator { +public: + BulkPoolAllocator() noexcept = default; + + // does not copy anything, just creates a new allocator. + BulkPoolAllocator(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept + : mHead(nullptr) + , mListForFree(nullptr) {} + + BulkPoolAllocator(BulkPoolAllocator&& o) noexcept + : mHead(o.mHead) + , mListForFree(o.mListForFree) { + o.mListForFree = nullptr; + o.mHead = nullptr; + } + + BulkPoolAllocator& operator=(BulkPoolAllocator&& o) noexcept { + reset(); + mHead = o.mHead; + mListForFree = o.mListForFree; + o.mListForFree = nullptr; + o.mHead = nullptr; + return *this; + } + + BulkPoolAllocator& + // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) + operator=(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept { + // does not do anything + return *this; + } + + ~BulkPoolAllocator() noexcept { + reset(); + } + + // Deallocates all allocated memory. + void reset() noexcept { + while (mListForFree) { + T* tmp = *mListForFree; + ROBIN_HOOD_LOG("std::free") + std::free(mListForFree); + mListForFree = reinterpret_cast_no_cast_align_warning(tmp); + } + mHead = nullptr; + } + + // allocates, but does NOT initialize. Use in-place new constructor, e.g. + // T* obj = pool.allocate(); + // ::new (static_cast(obj)) T(); + T* allocate() { + T* tmp = mHead; + if (!tmp) { + tmp = performAllocation(); + } + + mHead = *reinterpret_cast_no_cast_align_warning(tmp); + return tmp; + } + + // does not actually deallocate but puts it in store. + // make sure you have already called the destructor! e.g. with + // obj->~T(); + // pool.deallocate(obj); + void deallocate(T* obj) noexcept { + *reinterpret_cast_no_cast_align_warning(obj) = mHead; + mHead = obj; + } + + // Adds an already allocated block of memory to the allocator. This allocator is from now on + // responsible for freeing the data (with free()). If the provided data is not large enough to + // make use of, it is immediately freed. Otherwise it is reused and freed in the destructor. + void addOrFree(void* ptr, const size_t numBytes) noexcept { + // calculate number of available elements in ptr + if (numBytes < ALIGNMENT + ALIGNED_SIZE) { + // not enough data for at least one element. Free and return. + ROBIN_HOOD_LOG("std::free") + std::free(ptr); + } else { + ROBIN_HOOD_LOG("add to buffer") + add(ptr, numBytes); + } + } + + void swap(BulkPoolAllocator& other) noexcept { + using std::swap; + swap(mHead, other.mHead); + swap(mListForFree, other.mListForFree); + } + +private: + // iterates the list of allocated memory to calculate how many to alloc next. + // Recalculating this each time saves us a size_t member. + // This ignores the fact that memory blocks might have been added manually with addOrFree. In + // practice, this should not matter much. + ROBIN_HOOD(NODISCARD) size_t calcNumElementsToAlloc() const noexcept { + auto tmp = mListForFree; + size_t numAllocs = MinNumAllocs; + + while (numAllocs * 2 <= MaxNumAllocs && tmp) { + auto x = reinterpret_cast(tmp); + tmp = *x; + numAllocs *= 2; + } + + return numAllocs; + } + + // WARNING: Underflow if numBytes < ALIGNMENT! This is guarded in addOrFree(). + void add(void* ptr, const size_t numBytes) noexcept { + const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE; + + auto data = reinterpret_cast(ptr); + + // link free list + auto x = reinterpret_cast(data); + *x = mListForFree; + mListForFree = data; + + // create linked list for newly allocated data + auto* const headT = + reinterpret_cast_no_cast_align_warning(reinterpret_cast(ptr) + ALIGNMENT); + + auto* const head = reinterpret_cast(headT); + + // Visual Studio compiler automatically unrolls this loop, which is pretty cool + for (size_t i = 0; i < numElements; ++i) { + *reinterpret_cast_no_cast_align_warning(head + i * ALIGNED_SIZE) = + head + (i + 1) * ALIGNED_SIZE; + } + + // last one points to 0 + *reinterpret_cast_no_cast_align_warning(head + (numElements - 1) * ALIGNED_SIZE) = + mHead; + mHead = headT; + } + + // Called when no memory is available (mHead == 0). + // Don't inline this slow path. + ROBIN_HOOD(NOINLINE) T* performAllocation() { + size_t const numElementsToAlloc = calcNumElementsToAlloc(); + + // alloc new memory: [prev |T, T, ... T] + size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc; + ROBIN_HOOD_LOG("std::malloc " << bytes << " = " << ALIGNMENT << " + " << ALIGNED_SIZE + << " * " << numElementsToAlloc) + add(assertNotNull(std::malloc(bytes)), bytes); + return mHead; + } + + // enforce byte alignment of the T's +#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) + static constexpr size_t ALIGNMENT = + (std::max)(std::alignment_of::value, std::alignment_of::value); +#else + static const size_t ALIGNMENT = + (ROBIN_HOOD_STD::alignment_of::value > ROBIN_HOOD_STD::alignment_of::value) + ? ROBIN_HOOD_STD::alignment_of::value + : +ROBIN_HOOD_STD::alignment_of::value; // the + is for walkarround +#endif + + static constexpr size_t ALIGNED_SIZE = ((sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT; + + static_assert(MinNumAllocs >= 1, "MinNumAllocs"); + static_assert(MaxNumAllocs >= MinNumAllocs, "MaxNumAllocs"); + static_assert(ALIGNED_SIZE >= sizeof(T*), "ALIGNED_SIZE"); + static_assert(0 == (ALIGNED_SIZE % sizeof(T*)), "ALIGNED_SIZE mod"); + static_assert(ALIGNMENT >= sizeof(T*), "ALIGNMENT"); + + T* mHead{nullptr}; + T** mListForFree{nullptr}; +}; + +template +struct NodeAllocator; + +// dummy allocator that does nothing +template +struct NodeAllocator { + + // we are not using the data, so just free it. + void addOrFree(void* ptr, size_t ROBIN_HOOD_UNUSED(numBytes) /*unused*/) noexcept { + ROBIN_HOOD_LOG("std::free") + std::free(ptr); + } +}; + +template +struct NodeAllocator : public BulkPoolAllocator {}; + +// c++14 doesn't have is_nothrow_swappable, and clang++ 6.0.1 doesn't like it either, so I'm making +// my own here. +namespace swappable { +#if ROBIN_HOOD(CXX) < ROBIN_HOOD(CXX17) +using std::swap; +template +struct nothrow { + static const bool value = noexcept(swap(std::declval(), std::declval())); +}; +#else +template +struct nothrow { + static const bool value = std::is_nothrow_swappable::value; +}; +#endif +} // namespace swappable + +} // namespace detail + +struct is_transparent_tag {}; + +// A custom pair implementation is used in the map because std::pair is not is_trivially_copyable, +// which means it would not be allowed to be used in std::memcpy. This struct is copyable, which is +// also tested. +template +struct pair { + using first_type = T1; + using second_type = T2; + + template ::value && + std::is_default_constructible::value>::type> + constexpr pair() noexcept(noexcept(U1()) && noexcept(U2())) + : first() + , second() {} + + // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. + explicit constexpr pair(std::pair const& o) noexcept( + noexcept(T1(std::declval())) && noexcept(T2(std::declval()))) + : first(o.first) + , second(o.second) {} + + // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. + explicit constexpr pair(std::pair&& o) noexcept(noexcept( + T1(std::move(std::declval()))) && noexcept(T2(std::move(std::declval())))) + : first(std::move(o.first)) + , second(std::move(o.second)) {} + + constexpr pair(T1&& a, T2&& b) noexcept(noexcept( + T1(std::move(std::declval()))) && noexcept(T2(std::move(std::declval())))) + : first(std::move(a)) + , second(std::move(b)) {} + + template + constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward( + std::declval()))) && noexcept(T2(std::forward(std::declval())))) + : first(std::forward(a)) + , second(std::forward(b)) {} + + template + // MSVC 2015 produces error "C2476: ‘constexpr’ constructor does not initialize all members" + // if this constructor is constexpr +#if !ROBIN_HOOD(BROKEN_CONSTEXPR) + constexpr +#endif + pair(std::piecewise_construct_t /*unused*/, std::tuple a, + std::tuple + b) noexcept(noexcept(pair(std::declval&>(), + std::declval&>(), + ROBIN_HOOD_STD::index_sequence_for(), + ROBIN_HOOD_STD::index_sequence_for()))) + : pair(a, b, ROBIN_HOOD_STD::index_sequence_for(), + ROBIN_HOOD_STD::index_sequence_for()) { + } + + // constructor called from the std::piecewise_construct_t ctor + template + pair(std::tuple& a, std::tuple& b, ROBIN_HOOD_STD::index_sequence /*unused*/, ROBIN_HOOD_STD::index_sequence /*unused*/) noexcept( + noexcept(T1(std::forward(std::get( + std::declval&>()))...)) && noexcept(T2(std:: + forward(std::get( + std::declval&>()))...))) + : first(std::forward(std::get(a))...) + , second(std::forward(std::get(b))...) { + // make visual studio compiler happy about warning about unused a & b. + // Visual studio's pair implementation disables warning 4100. + (void)a; + (void)b; + } + + void swap(pair& o) noexcept((detail::swappable::nothrow::value) && + (detail::swappable::nothrow::value)) { + using std::swap; + swap(first, o.first); + swap(second, o.second); + } + + T1 first; // NOLINT(misc-non-private-member-variables-in-classes) + T2 second; // NOLINT(misc-non-private-member-variables-in-classes) +}; + +template +inline void swap(pair& a, pair& b) noexcept( + noexcept(std::declval&>().swap(std::declval&>()))) { + a.swap(b); +} + +template +inline constexpr bool operator==(pair const& x, pair const& y) { + return (x.first == y.first) && (x.second == y.second); +} +template +inline constexpr bool operator!=(pair const& x, pair const& y) { + return !(x == y); +} +template +inline constexpr bool operator<(pair const& x, pair const& y) noexcept(noexcept( + std::declval() < std::declval()) && noexcept(std::declval() < + std::declval())) { + return x.first < y.first || (!(y.first < x.first) && x.second < y.second); +} +template +inline constexpr bool operator>(pair const& x, pair const& y) { + return y < x; +} +template +inline constexpr bool operator<=(pair const& x, pair const& y) { + return !(x > y); +} +template +inline constexpr bool operator>=(pair const& x, pair const& y) { + return !(x < y); +} + +inline size_t hash_bytes(void const* ptr, size_t len) noexcept { + static constexpr uint64_t m = UINT64_C(0xc6a4a7935bd1e995); + static constexpr uint64_t seed = UINT64_C(0xe17a1465); + static constexpr unsigned int r = 47; + + auto const* const data64 = static_cast(ptr); + uint64_t h = seed ^ (len * m); + + size_t const n_blocks = len / 8; + for (size_t i = 0; i < n_blocks; ++i) { + auto k = detail::unaligned_load(data64 + i); + + k *= m; + k ^= k >> r; + k *= m; + + h ^= k; + h *= m; + } + + auto const* const data8 = reinterpret_cast(data64 + n_blocks); + switch (len & 7U) { + case 7: + h ^= static_cast(data8[6]) << 48U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 6: + h ^= static_cast(data8[5]) << 40U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 5: + h ^= static_cast(data8[4]) << 32U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 4: + h ^= static_cast(data8[3]) << 24U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 3: + h ^= static_cast(data8[2]) << 16U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 2: + h ^= static_cast(data8[1]) << 8U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 1: + h ^= static_cast(data8[0]); + h *= m; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + default: + break; + } + + h ^= h >> r; + + // not doing the final step here, because this will be done by keyToIdx anyways + // h *= m; + // h ^= h >> r; + return static_cast(h); +} + +inline size_t hash_int(uint64_t x) noexcept { + // tried lots of different hashes, let's stick with murmurhash3. It's simple, fast, well tested, + // and doesn't need any special 128bit operations. + x ^= x >> 33U; + x *= UINT64_C(0xff51afd7ed558ccd); + x ^= x >> 33U; + + // not doing the final step here, because this will be done by keyToIdx anyways + // x *= UINT64_C(0xc4ceb9fe1a85ec53); + // x ^= x >> 33U; + return static_cast(x); +} + +// A thin wrapper around std::hash, performing an additional simple mixing step of the result. +template +struct hash : public std::hash { + size_t operator()(T const& obj) const + noexcept(noexcept(std::declval>().operator()(std::declval()))) { + // call base hash + auto result = std::hash::operator()(obj); + // return mixed of that, to be save against identity has + return hash_int(static_cast(result)); + } +}; + +template +struct hash> { + size_t operator()(std::basic_string const& str) const noexcept { + return hash_bytes(str.data(), sizeof(CharT) * str.size()); + } +}; + +#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17) +template +struct hash> { + size_t operator()(std::basic_string_view const& sv) const noexcept { + return hash_bytes(sv.data(), sizeof(CharT) * sv.size()); + } +}; +#endif + +template +struct hash { + size_t operator()(T* ptr) const noexcept { + return hash_int(reinterpret_cast(ptr)); + } +}; + +template +struct hash> { + size_t operator()(std::unique_ptr const& ptr) const noexcept { + return hash_int(reinterpret_cast(ptr.get())); + } +}; + +template +struct hash> { + size_t operator()(std::shared_ptr const& ptr) const noexcept { + return hash_int(reinterpret_cast(ptr.get())); + } +}; + +template +struct hash::value>::type> { + size_t operator()(Enum e) const noexcept { + using Underlying = typename std::underlying_type::type; + return hash{}(static_cast(e)); + } +}; + +#define ROBIN_HOOD_HASH_INT(T) \ + template <> \ + struct hash { \ + size_t operator()(T const& obj) const noexcept { \ + return hash_int(static_cast(obj)); \ + } \ + } + +#if defined(__GNUC__) && !defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wuseless-cast" +#endif +// see https://en.cppreference.com/w/cpp/utility/hash +ROBIN_HOOD_HASH_INT(bool); +ROBIN_HOOD_HASH_INT(char); +ROBIN_HOOD_HASH_INT(signed char); +ROBIN_HOOD_HASH_INT(unsigned char); +ROBIN_HOOD_HASH_INT(char16_t); +ROBIN_HOOD_HASH_INT(char32_t); +#if ROBIN_HOOD(HAS_NATIVE_WCHART) +ROBIN_HOOD_HASH_INT(wchar_t); +#endif +ROBIN_HOOD_HASH_INT(short); +ROBIN_HOOD_HASH_INT(unsigned short); +ROBIN_HOOD_HASH_INT(int); +ROBIN_HOOD_HASH_INT(unsigned int); +ROBIN_HOOD_HASH_INT(long); +ROBIN_HOOD_HASH_INT(long long); +ROBIN_HOOD_HASH_INT(unsigned long); +ROBIN_HOOD_HASH_INT(unsigned long long); +#if defined(__GNUC__) && !defined(__clang__) +# pragma GCC diagnostic pop +#endif +namespace detail { + +template +struct void_type { + using type = void; +}; + +template +struct has_is_transparent : public std::false_type {}; + +template +struct has_is_transparent::type> + : public std::true_type {}; + +// using wrapper classes for hash and key_equal prevents the diamond problem when the same type +// is used. see https://stackoverflow.com/a/28771920/48181 +template +struct WrapHash : public T { + WrapHash() = default; + explicit WrapHash(T const& o) noexcept(noexcept(T(std::declval()))) + : T(o) {} +}; + +template +struct WrapKeyEqual : public T { + WrapKeyEqual() = default; + explicit WrapKeyEqual(T const& o) noexcept(noexcept(T(std::declval()))) + : T(o) {} +}; + +// A highly optimized hashmap implementation, using the Robin Hood algorithm. +// +// In most cases, this map should be usable as a drop-in replacement for std::unordered_map, but +// be about 2x faster in most cases and require much less allocations. +// +// This implementation uses the following memory layout: +// +// [Node, Node, ... Node | info, info, ... infoSentinel ] +// +// * Node: either a DataNode that directly has the std::pair as member, +// or a DataNode with a pointer to std::pair. Which DataNode representation to use +// depends on how fast the swap() operation is. Heuristically, this is automatically choosen +// based on sizeof(). there are always 2^n Nodes. +// +// * info: Each Node in the map has a corresponding info byte, so there are 2^n info bytes. +// Each byte is initialized to 0, meaning the corresponding Node is empty. Set to 1 means the +// corresponding node contains data. Set to 2 means the corresponding Node is filled, but it +// actually belongs to the previous position and was pushed out because that place is already +// taken. +// +// * infoSentinel: Sentinel byte set to 1, so that iterator's ++ can stop at end() without the +// need for a idx variable. +// +// According to STL, order of templates has effect on throughput. That's why I've moved the +// boolean to the front. +// https://www.reddit.com/r/cpp/comments/ahp6iu/compile_time_binary_size_reductions_and_cs_future/eeguck4/ +template +class Table + : public WrapHash, + public WrapKeyEqual, + detail::NodeAllocator< + typename std::conditional< + std::is_void::value, Key, + robin_hood::pair::type, T>>::type, + 4, 16384, IsFlat> { +public: + static constexpr bool is_flat = IsFlat; + static constexpr bool is_map = !std::is_void::value; + static constexpr bool is_set = !is_map; + static constexpr bool is_transparent = + has_is_transparent::value && has_is_transparent::value; + + using key_type = Key; + using mapped_type = T; + using value_type = typename std::conditional< + is_set, Key, + robin_hood::pair::type, T>>::type; + using size_type = size_t; + using hasher = Hash; + using key_equal = KeyEqual; + using Self = Table; + +private: + static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100, + "MaxLoadFactor100 needs to be >10 && < 100"); + + using WHash = WrapHash; + using WKeyEqual = WrapKeyEqual; + + // configuration defaults + + // make sure we have 8 elements, needed to quickly rehash mInfo + static constexpr size_t InitialNumElements = sizeof(uint64_t); + static constexpr uint32_t InitialInfoNumBits = 5; + static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits; + static constexpr size_t InfoMask = InitialInfoInc - 1U; + static constexpr uint8_t InitialInfoHashShift = 0; + using DataPool = detail::NodeAllocator; + + // type needs to be wider than uint8_t. + using InfoType = uint32_t; + + // DataNode //////////////////////////////////////////////////////// + + // Primary template for the data node. We have special implementations for small and big + // objects. For large objects it is assumed that swap() is fairly slow, so we allocate these + // on the heap so swap merely swaps a pointer. + template + class DataNode {}; + + // Small: just allocate on the stack. + template + class DataNode final { + public: + template + explicit DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, Args&&... args) noexcept( + noexcept(value_type(std::forward(args)...))) + : mData(std::forward(args)...) {} + + DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept( + std::is_nothrow_move_constructible::value) + : mData(std::move(n.mData)) {} + + // doesn't do anything + void destroy(M& ROBIN_HOOD_UNUSED(map) /*unused*/) noexcept {} + void destroyDoNotDeallocate() noexcept {} + + value_type const* operator->() const noexcept { + return &mData; + } + value_type* operator->() noexcept { + return &mData; + } + + const value_type& operator*() const noexcept { + return mData; + } + + value_type& operator*() noexcept { + return mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return mData.first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type + getFirst() const noexcept { + return mData.first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() const noexcept { + return mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() noexcept { + return mData.second; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() const noexcept { + return mData.second; + } + + void swap(DataNode& o) noexcept( + noexcept(std::declval().swap(std::declval()))) { + mData.swap(o.mData); + } + + private: + value_type mData; + }; + + // big object: allocate on heap. + template + class DataNode { + public: + template + explicit DataNode(M& map, Args&&... args) + : mData(map.allocate()) { + ::new (static_cast(mData)) value_type(std::forward(args)...); + } + + DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept + : mData(std::move(n.mData)) {} + + void destroy(M& map) noexcept { + // don't deallocate, just put it into list of datapool. + mData->~value_type(); + map.deallocate(mData); + } + + void destroyDoNotDeallocate() noexcept { + mData->~value_type(); + } + + value_type const* operator->() const noexcept { + return mData; + } + + value_type* operator->() noexcept { + return mData; + } + + const value_type& operator*() const { + return *mData; + } + + value_type& operator*() { + return *mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return mData->first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return *mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type + getFirst() const noexcept { + return mData->first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() const noexcept { + return *mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() noexcept { + return mData->second; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() const noexcept { + return mData->second; + } + + void swap(DataNode& o) noexcept { + using std::swap; + swap(mData, o.mData); + } + + private: + value_type* mData; + }; + + using Node = DataNode; + + // helpers for insertKeyPrepareEmptySpot: extract first entry (only const required) + ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(Node const& n) const noexcept { + return n.getFirst(); + } + + // in case we have void mapped_type, we are not using a pair, thus we just route k through. + // No need to disable this because it's just not used if not applicable. + ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(key_type const& k) const noexcept { + return k; + } + + // in case we have non-void mapped_type, we have a standard robin_hood::pair + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::value, key_type const&>::type + getFirstConst(value_type const& vt) const noexcept { + return vt.first; + } + + // Cloner ////////////////////////////////////////////////////////// + + template + struct Cloner; + + // fast path: Just copy data, without allocating anything. + template + struct Cloner { + void operator()(M const& source, M& target) const { + auto const* const src = reinterpret_cast(source.mKeyVals); + auto* tgt = reinterpret_cast(target.mKeyVals); + auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1); + std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt); + } + }; + + template + struct Cloner { + void operator()(M const& s, M& t) const { + auto const numElementsWithBuffer = t.calcNumElementsWithBuffer(t.mMask + 1); + std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(numElementsWithBuffer), t.mInfo); + + for (size_t i = 0; i < numElementsWithBuffer; ++i) { + if (t.mInfo[i]) { + ::new (static_cast(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]); + } + } + } + }; + + // Destroyer /////////////////////////////////////////////////////// + + template + struct Destroyer {}; + + template + struct Destroyer { + void nodes(M& m) const noexcept { + m.mNumElements = 0; + } + + void nodesDoNotDeallocate(M& m) const noexcept { + m.mNumElements = 0; + } + }; + + template + struct Destroyer { + void nodes(M& m) const noexcept { + m.mNumElements = 0; + // clear also resets mInfo to 0, that's sometimes not necessary. + auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); + + for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { + if (0 != m.mInfo[idx]) { + Node& n = m.mKeyVals[idx]; + n.destroy(m); + n.~Node(); + } + } + } + + void nodesDoNotDeallocate(M& m) const noexcept { + m.mNumElements = 0; + // clear also resets mInfo to 0, that's sometimes not necessary. + auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); + for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { + if (0 != m.mInfo[idx]) { + Node& n = m.mKeyVals[idx]; + n.destroyDoNotDeallocate(); + n.~Node(); + } + } + } + }; + + // Iter //////////////////////////////////////////////////////////// + + struct fast_forward_tag {}; + + // generic iterator for both const_iterator and iterator. + template + // NOLINTNEXTLINE(hicpp-special-member-functions,cppcoreguidelines-special-member-functions) + class Iter { + private: + using NodePtr = typename std::conditional::type; + + public: + using difference_type = std::ptrdiff_t; + using value_type = typename Self::value_type; + using reference = typename std::conditional::type; + using pointer = typename std::conditional::type; + using iterator_category = std::forward_iterator_tag; + + // default constructed iterator can be compared to itself, but WON'T return true when + // compared to end(). + Iter() = default; + + // Rule of zero: nothing specified. The conversion constructor is only enabled for + // iterator to const_iterator, so it doesn't accidentally work as a copy ctor. + + // Conversion constructor from iterator to const_iterator. + template ::type> + // NOLINTNEXTLINE(hicpp-explicit-conversions) + Iter(Iter const& other) noexcept + : mKeyVals(other.mKeyVals) + , mInfo(other.mInfo) {} + + Iter(NodePtr valPtr, uint8_t const* infoPtr) noexcept + : mKeyVals(valPtr) + , mInfo(infoPtr) {} + + Iter(NodePtr valPtr, uint8_t const* infoPtr, + fast_forward_tag ROBIN_HOOD_UNUSED(tag) /*unused*/) noexcept + : mKeyVals(valPtr) + , mInfo(infoPtr) { + fastForward(); + } + + template ::type> + Iter& operator=(Iter const& other) noexcept { + mKeyVals = other.mKeyVals; + mInfo = other.mInfo; + return *this; + } + + // prefix increment. Undefined behavior if we are at end()! + Iter& operator++() noexcept { + mInfo++; + mKeyVals++; + fastForward(); + return *this; + } + + Iter operator++(int) noexcept { + Iter tmp = *this; + ++(*this); + return tmp; + } + + reference operator*() const { + return **mKeyVals; + } + + pointer operator->() const { + return &**mKeyVals; + } + + template + bool operator==(Iter const& o) const noexcept { + return mKeyVals == o.mKeyVals; + } + + template + bool operator!=(Iter const& o) const noexcept { + return mKeyVals != o.mKeyVals; + } + + private: + // fast forward to the next non-free info byte + // I've tried a few variants that don't depend on intrinsics, but unfortunately they are + // quite a bit slower than this one. So I've reverted that change again. See map_benchmark. + void fastForward() noexcept { + size_t n = 0; + while (0U == (n = detail::unaligned_load(mInfo))) { + mInfo += sizeof(size_t); + mKeyVals += sizeof(size_t); + } +#if defined(ROBIN_HOOD_DISABLE_INTRINSICS) + // we know for certain that within the next 8 bytes we'll find a non-zero one. + if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load(mInfo))) { + mInfo += 4; + mKeyVals += 4; + } + if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load(mInfo))) { + mInfo += 2; + mKeyVals += 2; + } + if (ROBIN_HOOD_UNLIKELY(0U == *mInfo)) { + mInfo += 1; + mKeyVals += 1; + } +#else +# if ROBIN_HOOD(LITTLE_ENDIAN) + auto inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8; +# else + auto inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8; +# endif + mInfo += inc; + mKeyVals += inc; +#endif + } + + friend class Table; + NodePtr mKeyVals{nullptr}; + uint8_t const* mInfo{nullptr}; + }; + + //////////////////////////////////////////////////////////////////// + + // highly performance relevant code. + // Lower bits are used for indexing into the array (2^n size) + // The upper 1-5 bits need to be a reasonable good hash, to save comparisons. + template + void keyToIdx(HashKey&& key, size_t* idx, InfoType* info) const { + // In addition to whatever hash is used, add another mul & shift so we get better hashing. + // This serves as a bad hash prevention, if the given data is + // badly mixed. + auto h = static_cast(WHash::operator()(key)); + + h *= mHashMultiplier; + h ^= h >> 33U; + + // the lower InitialInfoNumBits are reserved for info. + *info = mInfoInc + static_cast((h & InfoMask) >> mInfoHashShift); + *idx = (static_cast(h) >> InitialInfoNumBits) & mMask; + } + + // forwards the index by one, wrapping around at the end + void next(InfoType* info, size_t* idx) const noexcept { + *idx = *idx + 1; + *info += mInfoInc; + } + + void nextWhileLess(InfoType* info, size_t* idx) const noexcept { + // unrolling this by hand did not bring any speedups. + while (*info < mInfo[*idx]) { + next(info, idx); + } + } + + // Shift everything up by one element. Tries to move stuff around. + void + shiftUp(size_t startIdx, + size_t const insertion_idx) noexcept(std::is_nothrow_move_assignable::value) { + auto idx = startIdx; + ::new (static_cast(mKeyVals + idx)) Node(std::move(mKeyVals[idx - 1])); + while (--idx != insertion_idx) { + mKeyVals[idx] = std::move(mKeyVals[idx - 1]); + } + + idx = startIdx; + while (idx != insertion_idx) { + ROBIN_HOOD_COUNT(shiftUp) + mInfo[idx] = static_cast(mInfo[idx - 1] + mInfoInc); + if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) { + mMaxNumElementsAllowed = 0; + } + --idx; + } + } + + void shiftDown(size_t idx) noexcept(std::is_nothrow_move_assignable::value) { + // until we find one that is either empty or has zero offset. + // TODO(martinus) we don't need to move everything, just the last one for the same + // bucket. + mKeyVals[idx].destroy(*this); + + // until we find one that is either empty or has zero offset. + while (mInfo[idx + 1] >= 2 * mInfoInc) { + ROBIN_HOOD_COUNT(shiftDown) + mInfo[idx] = static_cast(mInfo[idx + 1] - mInfoInc); + mKeyVals[idx] = std::move(mKeyVals[idx + 1]); + ++idx; + } + + mInfo[idx] = 0; + // don't destroy, we've moved it + // mKeyVals[idx].destroy(*this); + mKeyVals[idx].~Node(); + } + + // copy of find(), except that it returns iterator instead of const_iterator. + template + ROBIN_HOOD(NODISCARD) + size_t findIdx(Other const& key) const { + size_t idx{}; + InfoType info{}; + keyToIdx(key, &idx, &info); + + do { + // unrolling this twice gives a bit of a speedup. More unrolling did not help. + if (info == mInfo[idx] && + ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { + return idx; + } + next(&info, &idx); + if (info == mInfo[idx] && + ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { + return idx; + } + next(&info, &idx); + } while (info <= mInfo[idx]); + + // nothing found! + return mMask == 0 ? 0 + : static_cast(std::distance( + mKeyVals, reinterpret_cast_no_cast_align_warning(mInfo))); + } + + void cloneData(const Table& o) { + Cloner()(o, *this); + } + + // inserts a keyval that is guaranteed to be new, e.g. when the hashmap is resized. + // @return True on success, false if something went wrong + void insert_move(Node&& keyval) { + // we don't retry, fail if overflowing + // don't need to check max num elements + if (0 == mMaxNumElementsAllowed && !try_increase_info()) { + throwOverflowError(); + } + + size_t idx{}; + InfoType info{}; + keyToIdx(keyval.getFirst(), &idx, &info); + + // skip forward. Use <= because we are certain that the element is not there. + while (info <= mInfo[idx]) { + idx = idx + 1; + info += mInfoInc; + } + + // key not found, so we are now exactly where we want to insert it. + auto const insertion_idx = idx; + auto const insertion_info = static_cast(info); + if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { + mMaxNumElementsAllowed = 0; + } + + // find an empty spot + while (0 != mInfo[idx]) { + next(&info, &idx); + } + + auto& l = mKeyVals[insertion_idx]; + if (idx == insertion_idx) { + ::new (static_cast(&l)) Node(std::move(keyval)); + } else { + shiftUp(idx, insertion_idx); + l = std::move(keyval); + } + + // put at empty spot + mInfo[insertion_idx] = insertion_info; + + ++mNumElements; + } + +public: + using iterator = Iter; + using const_iterator = Iter; + + Table() noexcept(noexcept(Hash()) && noexcept(KeyEqual())) + : WHash() + , WKeyEqual() { + ROBIN_HOOD_TRACE(this) + } + + // Creates an empty hash map. Nothing is allocated yet, this happens at the first insert. + // This tremendously speeds up ctor & dtor of a map that never receives an element. The + // penalty is payed at the first insert, and not before. Lookup of this empty map works + // because everybody points to DummyInfoByte::b. parameter bucket_count is dictated by the + // standard, but we can ignore it. + explicit Table( + size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/, const Hash& h = Hash{}, + const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && noexcept(KeyEqual(equal))) + : WHash(h) + , WKeyEqual(equal) { + ROBIN_HOOD_TRACE(this) + } + + template + Table(Iter first, Iter last, size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, + const Hash& h = Hash{}, const KeyEqual& equal = KeyEqual{}) + : WHash(h) + , WKeyEqual(equal) { + ROBIN_HOOD_TRACE(this) + insert(first, last); + } + + Table(std::initializer_list initlist, + size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, const Hash& h = Hash{}, + const KeyEqual& equal = KeyEqual{}) + : WHash(h) + , WKeyEqual(equal) { + ROBIN_HOOD_TRACE(this) + insert(initlist.begin(), initlist.end()); + } + + Table(Table&& o) noexcept + : WHash(std::move(static_cast(o))) + , WKeyEqual(std::move(static_cast(o))) + , DataPool(std::move(static_cast(o))) { + ROBIN_HOOD_TRACE(this) + if (o.mMask) { + mHashMultiplier = std::move(o.mHashMultiplier); + mKeyVals = std::move(o.mKeyVals); + mInfo = std::move(o.mInfo); + mNumElements = std::move(o.mNumElements); + mMask = std::move(o.mMask); + mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed); + mInfoInc = std::move(o.mInfoInc); + mInfoHashShift = std::move(o.mInfoHashShift); + // set other's mask to 0 so its destructor won't do anything + o.init(); + } + } + + Table& operator=(Table&& o) noexcept { + ROBIN_HOOD_TRACE(this) + if (&o != this) { + if (o.mMask) { + // only move stuff if the other map actually has some data + destroy(); + mHashMultiplier = std::move(o.mHashMultiplier); + mKeyVals = std::move(o.mKeyVals); + mInfo = std::move(o.mInfo); + mNumElements = std::move(o.mNumElements); + mMask = std::move(o.mMask); + mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed); + mInfoInc = std::move(o.mInfoInc); + mInfoHashShift = std::move(o.mInfoHashShift); + WHash::operator=(std::move(static_cast(o))); + WKeyEqual::operator=(std::move(static_cast(o))); + DataPool::operator=(std::move(static_cast(o))); + + o.init(); + + } else { + // nothing in the other map => just clear us. + clear(); + } + } + return *this; + } + + Table(const Table& o) + : WHash(static_cast(o)) + , WKeyEqual(static_cast(o)) + , DataPool(static_cast(o)) { + ROBIN_HOOD_TRACE(this) + if (!o.empty()) { + // not empty: create an exact copy. it is also possible to just iterate through all + // elements and insert them, but copying is probably faster. + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); + auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); + + ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal(" + << numElementsWithBuffer << ")") + mHashMultiplier = o.mHashMultiplier; + mKeyVals = static_cast( + detail::assertNotNull(std::malloc(numBytesTotal))); + // no need for calloc because clonData does memcpy + mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); + mNumElements = o.mNumElements; + mMask = o.mMask; + mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; + mInfoInc = o.mInfoInc; + mInfoHashShift = o.mInfoHashShift; + cloneData(o); + } + } + + // Creates a copy of the given map. Copy constructor of each entry is used. + // Not sure why clang-tidy thinks this doesn't handle self assignment, it does + // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) + Table& operator=(Table const& o) { + ROBIN_HOOD_TRACE(this) + if (&o == this) { + // prevent assigning of itself + return *this; + } + + // we keep using the old allocator and not assign the new one, because we want to keep + // the memory available. when it is the same size. + if (o.empty()) { + if (0 == mMask) { + // nothing to do, we are empty too + return *this; + } + + // not empty: destroy what we have there + // clear also resets mInfo to 0, that's sometimes not necessary. + destroy(); + init(); + WHash::operator=(static_cast(o)); + WKeyEqual::operator=(static_cast(o)); + DataPool::operator=(static_cast(o)); + + return *this; + } + + // clean up old stuff + Destroyer::value>{}.nodes(*this); + + if (mMask != o.mMask) { + // no luck: we don't have the same array size allocated, so we need to realloc. + if (0 != mMask) { + // only deallocate if we actually have data! + ROBIN_HOOD_LOG("std::free") + std::free(mKeyVals); + } + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); + auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); + ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal(" + << numElementsWithBuffer << ")") + mKeyVals = static_cast( + detail::assertNotNull(std::malloc(numBytesTotal))); + + // no need for calloc here because cloneData performs a memcpy. + mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); + // sentinel is set in cloneData + } + WHash::operator=(static_cast(o)); + WKeyEqual::operator=(static_cast(o)); + DataPool::operator=(static_cast(o)); + mHashMultiplier = o.mHashMultiplier; + mNumElements = o.mNumElements; + mMask = o.mMask; + mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; + mInfoInc = o.mInfoInc; + mInfoHashShift = o.mInfoHashShift; + cloneData(o); + + return *this; + } + + // Swaps everything between the two maps. + void swap(Table& o) { + ROBIN_HOOD_TRACE(this) + using std::swap; + swap(o, *this); + } + + // Clears all data, without resizing. + void clear() { + ROBIN_HOOD_TRACE(this) + if (empty()) { + // don't do anything! also important because we don't want to write to + // DummyInfoByte::b, even though we would just write 0 to it. + return; + } + + Destroyer::value>{}.nodes(*this); + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); + // clear everything, then set the sentinel again + uint8_t const z = 0; + std::fill(mInfo, mInfo + calcNumBytesInfo(numElementsWithBuffer), z); + mInfo[numElementsWithBuffer] = 1; + + mInfoInc = InitialInfoInc; + mInfoHashShift = InitialInfoHashShift; + } + + // Destroys the map and all it's contents. + ~Table() { + ROBIN_HOOD_TRACE(this) + destroy(); + } + + // Checks if both tables contain the same entries. Order is irrelevant. + bool operator==(const Table& other) const { + ROBIN_HOOD_TRACE(this) + if (other.size() != size()) { + return false; + } + for (auto const& otherEntry : other) { + if (!has(otherEntry)) { + return false; + } + } + + return true; + } + + bool operator!=(const Table& other) const { + ROBIN_HOOD_TRACE(this) + return !operator==(other); + } + + template + typename std::enable_if::value, Q&>::type operator[](const key_type& key) { + ROBIN_HOOD_TRACE(this) + auto idxAndState = insertKeyPrepareEmptySpot(key); + switch (idxAndState.second) { + case InsertionState::key_found: + break; + + case InsertionState::new_node: + ::new (static_cast(&mKeyVals[idxAndState.first])) + Node(*this, std::piecewise_construct, std::forward_as_tuple(key), + std::forward_as_tuple()); + break; + + case InsertionState::overwrite_node: + mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct, + std::forward_as_tuple(key), std::forward_as_tuple()); + break; + + case InsertionState::overflow_error: + throwOverflowError(); + } + + return mKeyVals[idxAndState.first].getSecond(); + } + + template + typename std::enable_if::value, Q&>::type operator[](key_type&& key) { + ROBIN_HOOD_TRACE(this) + auto idxAndState = insertKeyPrepareEmptySpot(key); + switch (idxAndState.second) { + case InsertionState::key_found: + break; + + case InsertionState::new_node: + ::new (static_cast(&mKeyVals[idxAndState.first])) + Node(*this, std::piecewise_construct, std::forward_as_tuple(std::move(key)), + std::forward_as_tuple()); + break; + + case InsertionState::overwrite_node: + mKeyVals[idxAndState.first] = + Node(*this, std::piecewise_construct, std::forward_as_tuple(std::move(key)), + std::forward_as_tuple()); + break; + + case InsertionState::overflow_error: + throwOverflowError(); + } + + return mKeyVals[idxAndState.first].getSecond(); + } + + template + void insert(Iter first, Iter last) { + for (; first != last; ++first) { + // value_type ctor needed because this might be called with std::pair's + insert(value_type(*first)); + } + } + + void insert(std::initializer_list ilist) { + for (auto&& vt : ilist) { + insert(std::move(vt)); + } + } + + template + std::pair emplace(Args&&... args) { + ROBIN_HOOD_TRACE(this) + Node n{*this, std::forward(args)...}; + auto idxAndState = insertKeyPrepareEmptySpot(getFirstConst(n)); + switch (idxAndState.second) { + case InsertionState::key_found: + n.destroy(*this); + break; + + case InsertionState::new_node: + ::new (static_cast(&mKeyVals[idxAndState.first])) Node(*this, std::move(n)); + break; + + case InsertionState::overwrite_node: + mKeyVals[idxAndState.first] = std::move(n); + break; + + case InsertionState::overflow_error: + n.destroy(*this); + throwOverflowError(); + break; + } + + return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first), + InsertionState::key_found != idxAndState.second); + } + + template + iterator emplace_hint(const_iterator position, Args&&... args) { + (void)position; + return emplace(std::forward(args)...).first; + } + + template + std::pair try_emplace(const key_type& key, Args&&... args) { + return try_emplace_impl(key, std::forward(args)...); + } + + template + std::pair try_emplace(key_type&& key, Args&&... args) { + return try_emplace_impl(std::move(key), std::forward(args)...); + } + + template + iterator try_emplace(const_iterator hint, const key_type& key, Args&&... args) { + (void)hint; + return try_emplace_impl(key, std::forward(args)...).first; + } + + template + iterator try_emplace(const_iterator hint, key_type&& key, Args&&... args) { + (void)hint; + return try_emplace_impl(std::move(key), std::forward(args)...).first; + } + + template + std::pair insert_or_assign(const key_type& key, Mapped&& obj) { + return insertOrAssignImpl(key, std::forward(obj)); + } + + template + std::pair insert_or_assign(key_type&& key, Mapped&& obj) { + return insertOrAssignImpl(std::move(key), std::forward(obj)); + } + + template + iterator insert_or_assign(const_iterator hint, const key_type& key, Mapped&& obj) { + (void)hint; + return insertOrAssignImpl(key, std::forward(obj)).first; + } + + template + iterator insert_or_assign(const_iterator hint, key_type&& key, Mapped&& obj) { + (void)hint; + return insertOrAssignImpl(std::move(key), std::forward(obj)).first; + } + + std::pair insert(const value_type& keyval) { + ROBIN_HOOD_TRACE(this) + return emplace(keyval); + } + + iterator insert(const_iterator hint, const value_type& keyval) { + (void)hint; + return emplace(keyval).first; + } + + std::pair insert(value_type&& keyval) { + return emplace(std::move(keyval)); + } + + iterator insert(const_iterator hint, value_type&& keyval) { + (void)hint; + return emplace(std::move(keyval)).first; + } + + // Returns 1 if key is found, 0 otherwise. + size_t count(const key_type& key) const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + auto kv = mKeyVals + findIdx(key); + if (kv != reinterpret_cast_no_cast_align_warning(mInfo)) { + return 1; + } + return 0; + } + + template + // NOLINTNEXTLINE(modernize-use-nodiscard) + typename std::enable_if::type count(const OtherKey& key) const { + ROBIN_HOOD_TRACE(this) + auto kv = mKeyVals + findIdx(key); + if (kv != reinterpret_cast_no_cast_align_warning(mInfo)) { + return 1; + } + return 0; + } + + bool contains(const key_type& key) const { // NOLINT(modernize-use-nodiscard) + return 1U == count(key); + } + + template + // NOLINTNEXTLINE(modernize-use-nodiscard) + typename std::enable_if::type contains(const OtherKey& key) const { + return 1U == count(key); + } + + // Returns a reference to the value found for key. + // Throws std::out_of_range if element cannot be found + template + // NOLINTNEXTLINE(modernize-use-nodiscard) + typename std::enable_if::value, Q&>::type at(key_type const& key) { + ROBIN_HOOD_TRACE(this) + auto kv = mKeyVals + findIdx(key); + if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { + doThrow("key not found"); + } + return kv->getSecond(); + } + + // Returns a reference to the value found for key. + // Throws std::out_of_range if element cannot be found + template + // NOLINTNEXTLINE(modernize-use-nodiscard) + typename std::enable_if::value, Q const&>::type at(key_type const& key) const { + ROBIN_HOOD_TRACE(this) + auto kv = mKeyVals + findIdx(key); + if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { + doThrow("key not found"); + } + return kv->getSecond(); + } + + const_iterator find(const key_type& key) const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + const size_t idx = findIdx(key); + return const_iterator{mKeyVals + idx, mInfo + idx}; + } + + template + const_iterator find(const OtherKey& key, is_transparent_tag /*unused*/) const { + ROBIN_HOOD_TRACE(this) + const size_t idx = findIdx(key); + return const_iterator{mKeyVals + idx, mInfo + idx}; + } + + template + typename std::enable_if::type // NOLINT(modernize-use-nodiscard) + find(const OtherKey& key) const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + const size_t idx = findIdx(key); + return const_iterator{mKeyVals + idx, mInfo + idx}; + } + + iterator find(const key_type& key) { + ROBIN_HOOD_TRACE(this) + const size_t idx = findIdx(key); + return iterator{mKeyVals + idx, mInfo + idx}; + } + + template + iterator find(const OtherKey& key, is_transparent_tag /*unused*/) { + ROBIN_HOOD_TRACE(this) + const size_t idx = findIdx(key); + return iterator{mKeyVals + idx, mInfo + idx}; + } + + template + typename std::enable_if::type find(const OtherKey& key) { + ROBIN_HOOD_TRACE(this) + const size_t idx = findIdx(key); + return iterator{mKeyVals + idx, mInfo + idx}; + } + + iterator begin() { + ROBIN_HOOD_TRACE(this) + if (empty()) { + return end(); + } + return iterator(mKeyVals, mInfo, fast_forward_tag{}); + } + const_iterator begin() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return cbegin(); + } + const_iterator cbegin() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + if (empty()) { + return cend(); + } + return const_iterator(mKeyVals, mInfo, fast_forward_tag{}); + } + + iterator end() { + ROBIN_HOOD_TRACE(this) + // no need to supply valid info pointer: end() must not be dereferenced, and only node + // pointer is compared. + return iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; + } + const_iterator end() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return cend(); + } + const_iterator cend() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return const_iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; + } + + iterator erase(const_iterator pos) { + ROBIN_HOOD_TRACE(this) + // its safe to perform const cast here + // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) + return erase(iterator{const_cast(pos.mKeyVals), const_cast(pos.mInfo)}); + } + + // Erases element at pos, returns iterator to the next element. + iterator erase(iterator pos) { + ROBIN_HOOD_TRACE(this) + // we assume that pos always points to a valid entry, and not end(). + auto const idx = static_cast(pos.mKeyVals - mKeyVals); + + shiftDown(idx); + --mNumElements; + + if (*pos.mInfo) { + // we've backward shifted, return this again + return pos; + } + + // no backward shift, return next element + return ++pos; + } + + size_t erase(const key_type& key) { + ROBIN_HOOD_TRACE(this) + size_t idx{}; + InfoType info{}; + keyToIdx(key, &idx, &info); + + // check while info matches with the source idx + do { + if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { + shiftDown(idx); + --mNumElements; + return 1; + } + next(&info, &idx); + } while (info <= mInfo[idx]); + + // nothing found to delete + return 0; + } + + // reserves space for the specified number of elements. Makes sure the old data fits. + // exactly the same as reserve(c). + void rehash(size_t c) { + // forces a reserve + reserve(c, true); + } + + // reserves space for the specified number of elements. Makes sure the old data fits. + // Exactly the same as rehash(c). Use rehash(0) to shrink to fit. + void reserve(size_t c) { + // reserve, but don't force rehash + reserve(c, false); + } + + // If possible reallocates the map to a smaller one. This frees the underlying table. + // Does not do anything if load_factor is too large for decreasing the table's size. + void compact() { + ROBIN_HOOD_TRACE(this) + auto newSize = InitialNumElements; + while (calcMaxNumElementsAllowed(newSize) < mNumElements && newSize != 0) { + newSize *= 2; + } + if (ROBIN_HOOD_UNLIKELY(newSize == 0)) { + throwOverflowError(); + } + + ROBIN_HOOD_LOG("newSize > mMask + 1: " << newSize << " > " << mMask << " + 1") + + // only actually do anything when the new size is bigger than the old one. This prevents to + // continuously allocate for each reserve() call. + if (newSize < mMask + 1) { + rehashPowerOfTwo(newSize, true); + } + } + + size_type size() const noexcept { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return mNumElements; + } + + size_type max_size() const noexcept { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return static_cast(-1); + } + + ROBIN_HOOD(NODISCARD) bool empty() const noexcept { + ROBIN_HOOD_TRACE(this) + return 0 == mNumElements; + } + + float max_load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return MaxLoadFactor100 / 100.0F; + } + + // Average number of elements per bucket. Since we allow only 1 per bucket + float load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this) + return static_cast(size()) / static_cast(mMask + 1); + } + + ROBIN_HOOD(NODISCARD) size_t mask() const noexcept { + ROBIN_HOOD_TRACE(this) + return mMask; + } + + ROBIN_HOOD(NODISCARD) size_t calcMaxNumElementsAllowed(size_t maxElements) const noexcept { + if (ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits::max)() / 100)) { + return maxElements * MaxLoadFactor100 / 100; + } + + // we might be a bit inprecise, but since maxElements is quite large that doesn't matter + return (maxElements / 100) * MaxLoadFactor100; + } + + ROBIN_HOOD(NODISCARD) size_t calcNumBytesInfo(size_t numElements) const noexcept { + // we add a uint64_t, which houses the sentinel (first byte) and padding so we can load + // 64bit types. + return numElements + sizeof(uint64_t); + } + + ROBIN_HOOD(NODISCARD) + size_t calcNumElementsWithBuffer(size_t numElements) const noexcept { + auto maxNumElementsAllowed = calcMaxNumElementsAllowed(numElements); + return numElements + (std::min)(maxNumElementsAllowed, (static_cast(0xFF))); + } + + // calculation only allowed for 2^n values + ROBIN_HOOD(NODISCARD) size_t calcNumBytesTotal(size_t numElements) const { +#if ROBIN_HOOD(BITNESS) == 64 + return numElements * sizeof(Node) + calcNumBytesInfo(numElements); +#else + // make sure we're doing 64bit operations, so we are at least safe against 32bit overflows. + auto const ne = static_cast(numElements); + auto const s = static_cast(sizeof(Node)); + auto const infos = static_cast(calcNumBytesInfo(numElements)); + + auto const total64 = ne * s + infos; + auto const total = static_cast(total64); + + if (ROBIN_HOOD_UNLIKELY(static_cast(total) != total64)) { + throwOverflowError(); + } + return total; +#endif + } + +private: + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::value, bool>::type has(const value_type& e) const { + ROBIN_HOOD_TRACE(this) + auto it = find(e.first); + return it != end() && it->second == e.second; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::value, bool>::type has(const value_type& e) const { + ROBIN_HOOD_TRACE(this) + return find(e) != end(); + } + + void reserve(size_t c, bool forceRehash) { + ROBIN_HOOD_TRACE(this) + auto const minElementsAllowed = (std::max)(c, mNumElements); + auto newSize = InitialNumElements; + while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) { + newSize *= 2; + } + if (ROBIN_HOOD_UNLIKELY(newSize == 0)) { + throwOverflowError(); + } + + ROBIN_HOOD_LOG("newSize > mMask + 1: " << newSize << " > " << mMask << " + 1") + + // only actually do anything when the new size is bigger than the old one. This prevents to + // continuously allocate for each reserve() call. + if (forceRehash || newSize > mMask + 1) { + rehashPowerOfTwo(newSize, false); + } + } + + // reserves space for at least the specified number of elements. + // only works if numBuckets if power of two + // True on success, false otherwise + void rehashPowerOfTwo(size_t numBuckets, bool forceFree) { + ROBIN_HOOD_TRACE(this) + + Node* const oldKeyVals = mKeyVals; + uint8_t const* const oldInfo = mInfo; + + const size_t oldMaxElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); + + // resize operation: move stuff + initData(numBuckets); + if (oldMaxElementsWithBuffer > 1) { + for (size_t i = 0; i < oldMaxElementsWithBuffer; ++i) { + if (oldInfo[i] != 0) { + // might throw an exception, which is really bad since we are in the middle of + // moving stuff. + insert_move(std::move(oldKeyVals[i])); + // destroy the node but DON'T destroy the data. + oldKeyVals[i].~Node(); + } + } + + // this check is not necessary as it's guarded by the previous if, but it helps + // silence g++'s overeager "attempt to free a non-heap object 'map' + // [-Werror=free-nonheap-object]" warning. + if (oldKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { + // don't destroy old data: put it into the pool instead + if (forceFree) { + std::free(oldKeyVals); + } else { + DataPool::addOrFree(oldKeyVals, calcNumBytesTotal(oldMaxElementsWithBuffer)); + } + } + } + } + + ROBIN_HOOD(NOINLINE) void throwOverflowError() const { +#if ROBIN_HOOD(HAS_EXCEPTIONS) + throw std::overflow_error("robin_hood::map overflow"); +#else + abort(); +#endif + } + + template + std::pair try_emplace_impl(OtherKey&& key, Args&&... args) { + ROBIN_HOOD_TRACE(this) + auto idxAndState = insertKeyPrepareEmptySpot(key); + switch (idxAndState.second) { + case InsertionState::key_found: + break; + + case InsertionState::new_node: + ::new (static_cast(&mKeyVals[idxAndState.first])) Node( + *this, std::piecewise_construct, std::forward_as_tuple(std::forward(key)), + std::forward_as_tuple(std::forward(args)...)); + break; + + case InsertionState::overwrite_node: + mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct, + std::forward_as_tuple(std::forward(key)), + std::forward_as_tuple(std::forward(args)...)); + break; + + case InsertionState::overflow_error: + throwOverflowError(); + break; + } + + return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first), + InsertionState::key_found != idxAndState.second); + } + + template + std::pair insertOrAssignImpl(OtherKey&& key, Mapped&& obj) { + ROBIN_HOOD_TRACE(this) + auto idxAndState = insertKeyPrepareEmptySpot(key); + switch (idxAndState.second) { + case InsertionState::key_found: + mKeyVals[idxAndState.first].getSecond() = std::forward(obj); + break; + + case InsertionState::new_node: + ::new (static_cast(&mKeyVals[idxAndState.first])) Node( + *this, std::piecewise_construct, std::forward_as_tuple(std::forward(key)), + std::forward_as_tuple(std::forward(obj))); + break; + + case InsertionState::overwrite_node: + mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct, + std::forward_as_tuple(std::forward(key)), + std::forward_as_tuple(std::forward(obj))); + break; + + case InsertionState::overflow_error: + throwOverflowError(); + break; + } + + return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first), + InsertionState::key_found != idxAndState.second); + } + + void initData(size_t max_elements) { + mNumElements = 0; + mMask = max_elements - 1; + mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements); + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(max_elements); + + // malloc & zero mInfo. Faster than calloc everything. + auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); + ROBIN_HOOD_LOG("std::calloc " << numBytesTotal << " = calcNumBytesTotal(" + << numElementsWithBuffer << ")") + mKeyVals = reinterpret_cast( + detail::assertNotNull(std::malloc(numBytesTotal))); + mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); + std::memset(mInfo, 0, numBytesTotal - numElementsWithBuffer * sizeof(Node)); + + // set sentinel + mInfo[numElementsWithBuffer] = 1; + + mInfoInc = InitialInfoInc; + mInfoHashShift = InitialInfoHashShift; + } + + enum class InsertionState { overflow_error, key_found, new_node, overwrite_node }; + + // Finds key, and if not already present prepares a spot where to pot the key & value. + // This potentially shifts nodes out of the way, updates mInfo and number of inserted + // elements, so the only operation left to do is create/assign a new node at that spot. + template + std::pair insertKeyPrepareEmptySpot(OtherKey&& key) { + for (int i = 0; i < 256; ++i) { + size_t idx{}; + InfoType info{}; + keyToIdx(key, &idx, &info); + nextWhileLess(&info, &idx); + + // while we potentially have a match + while (info == mInfo[idx]) { + if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { + // key already exists, do NOT insert. + // see http://en.cppreference.com/w/cpp/container/unordered_map/insert + return std::make_pair(idx, InsertionState::key_found); + } + next(&info, &idx); + } + + // unlikely that this evaluates to true + if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) { + if (!increase_size()) { + return std::make_pair(size_t(0), InsertionState::overflow_error); + } + continue; + } + + // key not found, so we are now exactly where we want to insert it. + auto const insertion_idx = idx; + auto const insertion_info = info; + if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { + mMaxNumElementsAllowed = 0; + } + + // find an empty spot + while (0 != mInfo[idx]) { + next(&info, &idx); + } + + if (idx != insertion_idx) { + shiftUp(idx, insertion_idx); + } + // put at empty spot + mInfo[insertion_idx] = static_cast(insertion_info); + ++mNumElements; + return std::make_pair(insertion_idx, idx == insertion_idx + ? InsertionState::new_node + : InsertionState::overwrite_node); + } + + // enough attempts failed, so finally give up. + return std::make_pair(size_t(0), InsertionState::overflow_error); + } + + bool try_increase_info() { + ROBIN_HOOD_LOG("mInfoInc=" << mInfoInc << ", numElements=" << mNumElements + << ", maxNumElementsAllowed=" + << calcMaxNumElementsAllowed(mMask + 1)) + if (mInfoInc <= 2) { + // need to be > 2 so that shift works (otherwise undefined behavior!) + return false; + } + // we got space left, try to make info smaller + mInfoInc = static_cast(mInfoInc >> 1U); + + // remove one bit of the hash, leaving more space for the distance info. + // This is extremely fast because we can operate on 8 bytes at once. + ++mInfoHashShift; + auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); + + for (size_t i = 0; i < numElementsWithBuffer; i += 8) { + auto val = unaligned_load(mInfo + i); + val = (val >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f); + std::memcpy(mInfo + i, &val, sizeof(val)); + } + // update sentinel, which might have been cleared out! + mInfo[numElementsWithBuffer] = 1; + + mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); + return true; + } + + // True if resize was possible, false otherwise + bool increase_size() { + // nothing allocated yet? just allocate InitialNumElements + if (0 == mMask) { + initData(InitialNumElements); + return true; + } + + auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); + if (mNumElements < maxNumElementsAllowed && try_increase_info()) { + return true; + } + + ROBIN_HOOD_LOG("mNumElements=" << mNumElements << ", maxNumElementsAllowed=" + << maxNumElementsAllowed << ", load=" + << (static_cast(mNumElements) * 100.0 / + (static_cast(mMask) + 1))) + + if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) { + // we have to resize, even though there would still be plenty of space left! + // Try to rehash instead. Delete freed memory so we don't steadyily increase mem in case + // we have to rehash a few times + nextHashMultiplier(); + rehashPowerOfTwo(mMask + 1, true); + } else { + // we've reached the capacity of the map, so the hash seems to work nice. Keep using it. + rehashPowerOfTwo((mMask + 1) * 2, false); + } + return true; + } + + void nextHashMultiplier() { + // adding an *even* number, so that the multiplier will always stay odd. This is necessary + // so that the hash stays a mixing function (and thus doesn't have any information loss). + mHashMultiplier += UINT64_C(0xc4ceb9fe1a85ec54); + } + + void destroy() { + if (0 == mMask) { + // don't deallocate! + return; + } + + Destroyer::value>{} + .nodesDoNotDeallocate(*this); + + // This protection against not deleting mMask shouldn't be needed as it's sufficiently + // protected with the 0==mMask check, but I have this anyways because g++ 7 otherwise + // reports a compile error: attempt to free a non-heap object 'fm' + // [-Werror=free-nonheap-object] + if (mKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { + ROBIN_HOOD_LOG("std::free") + std::free(mKeyVals); + } + } + + void init() noexcept { + mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); + mInfo = reinterpret_cast(&mMask); + mNumElements = 0; + mMask = 0; + mMaxNumElementsAllowed = 0; + mInfoInc = InitialInfoInc; + mInfoHashShift = InitialInfoHashShift; + } + + // members are sorted so no padding occurs + uint64_t mHashMultiplier = UINT64_C(0xc4ceb9fe1a85ec53); // 8 byte 8 + Node* mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); // 8 byte 16 + uint8_t* mInfo = reinterpret_cast(&mMask); // 8 byte 24 + size_t mNumElements = 0; // 8 byte 32 + size_t mMask = 0; // 8 byte 40 + size_t mMaxNumElementsAllowed = 0; // 8 byte 48 + InfoType mInfoInc = InitialInfoInc; // 4 byte 52 + InfoType mInfoHashShift = InitialInfoHashShift; // 4 byte 56 + // 16 byte 56 if NodeAllocator +}; + +} // namespace detail + +// map + +template , + typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> +using unordered_flat_map = detail::Table; + +template , + typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> +using unordered_node_map = detail::Table; + +template , + typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> +using unordered_map = + detail::Table) <= sizeof(size_t) * 6 && + std::is_nothrow_move_constructible>::value && + std::is_nothrow_move_assignable>::value, + MaxLoadFactor100, Key, T, Hash, KeyEqual>; + +// set + +template , typename KeyEqual = std::equal_to, + size_t MaxLoadFactor100 = 80> +using unordered_flat_set = detail::Table; + +template , typename KeyEqual = std::equal_to, + size_t MaxLoadFactor100 = 80> +using unordered_node_set = detail::Table; + +template , typename KeyEqual = std::equal_to, + size_t MaxLoadFactor100 = 80> +using unordered_set = detail::Table::value && + std::is_nothrow_move_assignable::value, + MaxLoadFactor100, Key, void, Hash, KeyEqual>; + +} // namespace robin_hood + +#endif diff --git a/benchmarks/external/robin_hood.h b/benchmarks/external/robin_hood.h deleted file mode 100644 index 0af031f5..00000000 --- a/benchmarks/external/robin_hood.h +++ /dev/null @@ -1,2544 +0,0 @@ -// ______ _____ ______ _________ -// ______________ ___ /_ ___(_)_______ ___ /_ ______ ______ ______ / -// __ ___/_ __ \__ __ \__ / __ __ \ __ __ \_ __ \_ __ \_ __ / -// _ / / /_/ /_ /_/ /_ / _ / / / _ / / // /_/ // /_/ // /_/ / -// /_/ \____/ /_.___/ /_/ /_/ /_/ ________/_/ /_/ \____/ \____/ \__,_/ -// _/_____/ -// -// Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20 -// https://github.com/martinus/robin-hood-hashing -// -// Licensed under the MIT License . -// SPDX-License-Identifier: MIT -// Copyright (c) 2018-2021 Martin Ankerl -// -// Permission is hereby granted, free of charge, to any person obtaining a copy -// of this software and associated documentation files (the "Software"), to deal -// in the Software without restriction, including without limitation the rights -// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -// copies of the Software, and to permit persons to whom the Software is -// furnished to do so, subject to the following conditions: -// -// The above copyright notice and this permission notice shall be included in all -// copies or substantial portions of the Software. -// -// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -// SOFTWARE. - -#ifndef ROBIN_HOOD_H_INCLUDED -#define ROBIN_HOOD_H_INCLUDED - -// see https://semver.org/ -#define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes -#define ROBIN_HOOD_VERSION_MINOR 11 // for adding functionality in a backwards-compatible manner -#define ROBIN_HOOD_VERSION_PATCH 5 // for backwards-compatible bug fixes - -#include -#include -#include -#include -#include -#include // only to support hash of smart pointers -#include -#include -#include -#include -#if __cplusplus >= 201703L -# include -#endif - -// #define ROBIN_HOOD_LOG_ENABLED -#ifdef ROBIN_HOOD_LOG_ENABLED -# include -# define ROBIN_HOOD_LOG(...) \ - std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl; -#else -# define ROBIN_HOOD_LOG(x) -#endif - -// #define ROBIN_HOOD_TRACE_ENABLED -#ifdef ROBIN_HOOD_TRACE_ENABLED -# include -# define ROBIN_HOOD_TRACE(...) \ - std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << __VA_ARGS__ << std::endl; -#else -# define ROBIN_HOOD_TRACE(x) -#endif - -// #define ROBIN_HOOD_COUNT_ENABLED -#ifdef ROBIN_HOOD_COUNT_ENABLED -# include -# define ROBIN_HOOD_COUNT(x) ++counts().x; -namespace robin_hood { -struct Counts { - uint64_t shiftUp{}; - uint64_t shiftDown{}; -}; -inline std::ostream& operator<<(std::ostream& os, Counts const& c) { - return os << c.shiftUp << " shiftUp" << std::endl << c.shiftDown << " shiftDown" << std::endl; -} - -static Counts& counts() { - static Counts counts{}; - return counts; -} -} // namespace robin_hood -#else -# define ROBIN_HOOD_COUNT(x) -#endif - -// all non-argument macros should use this facility. See -// https://www.fluentcpp.com/2019/05/28/better-macros-better-flags/ -#define ROBIN_HOOD(x) ROBIN_HOOD_PRIVATE_DEFINITION_##x() - -// mark unused members with this macro -#define ROBIN_HOOD_UNUSED(identifier) - -// bitness -#if SIZE_MAX == UINT32_MAX -# define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 32 -#elif SIZE_MAX == UINT64_MAX -# define ROBIN_HOOD_PRIVATE_DEFINITION_BITNESS() 64 -#else -# error Unsupported bitness -#endif - -// endianess -#ifdef _MSC_VER -# define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() 1 -# define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() 0 -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_LITTLE_ENDIAN() \ - (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) -# define ROBIN_HOOD_PRIVATE_DEFINITION_BIG_ENDIAN() (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) -#endif - -// inline -#ifdef _MSC_VER -# define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __declspec(noinline) -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_NOINLINE() __attribute__((noinline)) -#endif - -// exceptions -#if !defined(__cpp_exceptions) && !defined(__EXCEPTIONS) && !defined(_CPPUNWIND) -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 0 -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_EXCEPTIONS() 1 -#endif - -// count leading/trailing bits -#if !defined(ROBIN_HOOD_DISABLE_INTRINSICS) -# ifdef _MSC_VER -# if ROBIN_HOOD(BITNESS) == 32 -# define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward -# else -# define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward64 -# endif -# include -# pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD)) -# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \ - [](size_t mask) noexcept -> int { \ - unsigned long index; \ - return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast(index) \ - : ROBIN_HOOD(BITNESS); \ - }(x) -# else -# if ROBIN_HOOD(BITNESS) == 32 -# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl -# define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl -# else -# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll -# define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll -# endif -# define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS)) -# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS)) -# endif -#endif - -// fallthrough -#ifndef __has_cpp_attribute // For backwards compatibility -# define __has_cpp_attribute(x) 0 -#endif -#if __has_cpp_attribute(clang::fallthrough) -# define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[clang::fallthrough]] -#elif __has_cpp_attribute(gnu::fallthrough) -# define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() [[gnu::fallthrough]] -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_FALLTHROUGH() -#endif - -// likely/unlikely -#ifdef _MSC_VER -# define ROBIN_HOOD_LIKELY(condition) condition -# define ROBIN_HOOD_UNLIKELY(condition) condition -#else -# define ROBIN_HOOD_LIKELY(condition) __builtin_expect(condition, 1) -# define ROBIN_HOOD_UNLIKELY(condition) __builtin_expect(condition, 0) -#endif - -// detect if native wchar_t type is availiable in MSVC -#ifdef _MSC_VER -# ifdef _NATIVE_WCHAR_T_DEFINED -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1 -# else -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 0 -# endif -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_NATIVE_WCHART() 1 -#endif - -// detect if MSVC supports the pair(std::piecewise_construct_t,...) consructor being constexpr -#ifdef _MSC_VER -# if _MSC_VER <= 1900 -# define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 1 -# else -# define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 0 -# endif -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_BROKEN_CONSTEXPR() 0 -#endif - -// workaround missing "is_trivially_copyable" in g++ < 5.0 -// See https://stackoverflow.com/a/31798726/48181 -#if defined(__GNUC__) && __GNUC__ < 5 -# define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) __has_trivial_copy(__VA_ARGS__) -#else -# define ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(...) std::is_trivially_copyable<__VA_ARGS__>::value -#endif - -// helpers for C++ versions, see https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html -#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX() __cplusplus -#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX98() 199711L -#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX11() 201103L -#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX14() 201402L -#define ROBIN_HOOD_PRIVATE_DEFINITION_CXX17() 201703L - -#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17) -# define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() [[nodiscard]] -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_NODISCARD() -#endif - -namespace robin_hood { - -#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) -# define ROBIN_HOOD_STD std -#else - -// c++11 compatibility layer -namespace ROBIN_HOOD_STD { -template -struct alignment_of - : std::integral_constant::type)> {}; - -template -class integer_sequence { -public: - using value_type = T; - static_assert(std::is_integral::value, "not integral type"); - static constexpr std::size_t size() noexcept { - return sizeof...(Ints); - } -}; -template -using index_sequence = integer_sequence; - -namespace detail_ { -template -struct IntSeqImpl { - using TValue = T; - static_assert(std::is_integral::value, "not integral type"); - static_assert(Begin >= 0 && Begin < End, "unexpected argument (Begin<0 || Begin<=End)"); - - template - struct IntSeqCombiner; - - template - struct IntSeqCombiner, integer_sequence> { - using TResult = integer_sequence; - }; - - using TResult = - typename IntSeqCombiner::TResult, - typename IntSeqImpl::TResult>::TResult; -}; - -template -struct IntSeqImpl { - using TValue = T; - static_assert(std::is_integral::value, "not integral type"); - static_assert(Begin >= 0, "unexpected argument (Begin<0)"); - using TResult = integer_sequence; -}; - -template -struct IntSeqImpl { - using TValue = T; - static_assert(std::is_integral::value, "not integral type"); - static_assert(Begin >= 0, "unexpected argument (Begin<0)"); - using TResult = integer_sequence; -}; -} // namespace detail_ - -template -using make_integer_sequence = typename detail_::IntSeqImpl::TResult; - -template -using make_index_sequence = make_integer_sequence; - -template -using index_sequence_for = make_index_sequence; - -} // namespace ROBIN_HOOD_STD - -#endif - -namespace detail { - -// make sure we static_cast to the correct type for hash_int -#if ROBIN_HOOD(BITNESS) == 64 -using SizeT = uint64_t; -#else -using SizeT = uint32_t; -#endif - -template -T rotr(T x, unsigned k) { - return (x >> k) | (x << (8U * sizeof(T) - k)); -} - -// This cast gets rid of warnings like "cast from 'uint8_t*' {aka 'unsigned char*'} to -// 'uint64_t*' {aka 'long unsigned int*'} increases required alignment of target type". Use with -// care! -template -inline T reinterpret_cast_no_cast_align_warning(void* ptr) noexcept { - return reinterpret_cast(ptr); -} - -template -inline T reinterpret_cast_no_cast_align_warning(void const* ptr) noexcept { - return reinterpret_cast(ptr); -} - -// make sure this is not inlined as it is slow and dramatically enlarges code, thus making other -// inlinings more difficult. Throws are also generally the slow path. -template -[[noreturn]] ROBIN_HOOD(NOINLINE) -#if ROBIN_HOOD(HAS_EXCEPTIONS) - void doThrow(Args&&... args) { - // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-array-to-pointer-decay) - throw E(std::forward(args)...); -} -#else - void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) /*unused*/) { - abort(); -} -#endif - -template -T* assertNotNull(T* t, Args&&... args) { - if (ROBIN_HOOD_UNLIKELY(nullptr == t)) { - doThrow(std::forward(args)...); - } - return t; -} - -template -inline T unaligned_load(void const* ptr) noexcept { - // using memcpy so we don't get into unaligned load problems. - // compiler should optimize this very well anyways. - T t; - std::memcpy(&t, ptr, sizeof(T)); - return t; -} - -// Allocates bulks of memory for objects of type T. This deallocates the memory in the destructor, -// and keeps a linked list of the allocated memory around. Overhead per allocation is the size of a -// pointer. -template -class BulkPoolAllocator { -public: - BulkPoolAllocator() noexcept = default; - - // does not copy anything, just creates a new allocator. - BulkPoolAllocator(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept - : mHead(nullptr) - , mListForFree(nullptr) {} - - BulkPoolAllocator(BulkPoolAllocator&& o) noexcept - : mHead(o.mHead) - , mListForFree(o.mListForFree) { - o.mListForFree = nullptr; - o.mHead = nullptr; - } - - BulkPoolAllocator& operator=(BulkPoolAllocator&& o) noexcept { - reset(); - mHead = o.mHead; - mListForFree = o.mListForFree; - o.mListForFree = nullptr; - o.mHead = nullptr; - return *this; - } - - BulkPoolAllocator& - // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) - operator=(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept { - // does not do anything - return *this; - } - - ~BulkPoolAllocator() noexcept { - reset(); - } - - // Deallocates all allocated memory. - void reset() noexcept { - while (mListForFree) { - T* tmp = *mListForFree; - ROBIN_HOOD_LOG("std::free") - std::free(mListForFree); - mListForFree = reinterpret_cast_no_cast_align_warning(tmp); - } - mHead = nullptr; - } - - // allocates, but does NOT initialize. Use in-place new constructor, e.g. - // T* obj = pool.allocate(); - // ::new (static_cast(obj)) T(); - T* allocate() { - T* tmp = mHead; - if (!tmp) { - tmp = performAllocation(); - } - - mHead = *reinterpret_cast_no_cast_align_warning(tmp); - return tmp; - } - - // does not actually deallocate but puts it in store. - // make sure you have already called the destructor! e.g. with - // obj->~T(); - // pool.deallocate(obj); - void deallocate(T* obj) noexcept { - *reinterpret_cast_no_cast_align_warning(obj) = mHead; - mHead = obj; - } - - // Adds an already allocated block of memory to the allocator. This allocator is from now on - // responsible for freeing the data (with free()). If the provided data is not large enough to - // make use of, it is immediately freed. Otherwise it is reused and freed in the destructor. - void addOrFree(void* ptr, const size_t numBytes) noexcept { - // calculate number of available elements in ptr - if (numBytes < ALIGNMENT + ALIGNED_SIZE) { - // not enough data for at least one element. Free and return. - ROBIN_HOOD_LOG("std::free") - std::free(ptr); - } else { - ROBIN_HOOD_LOG("add to buffer") - add(ptr, numBytes); - } - } - - void swap(BulkPoolAllocator& other) noexcept { - using std::swap; - swap(mHead, other.mHead); - swap(mListForFree, other.mListForFree); - } - -private: - // iterates the list of allocated memory to calculate how many to alloc next. - // Recalculating this each time saves us a size_t member. - // This ignores the fact that memory blocks might have been added manually with addOrFree. In - // practice, this should not matter much. - ROBIN_HOOD(NODISCARD) size_t calcNumElementsToAlloc() const noexcept { - auto tmp = mListForFree; - size_t numAllocs = MinNumAllocs; - - while (numAllocs * 2 <= MaxNumAllocs && tmp) { - auto x = reinterpret_cast(tmp); - tmp = *x; - numAllocs *= 2; - } - - return numAllocs; - } - - // WARNING: Underflow if numBytes < ALIGNMENT! This is guarded in addOrFree(). - void add(void* ptr, const size_t numBytes) noexcept { - const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE; - - auto data = reinterpret_cast(ptr); - - // link free list - auto x = reinterpret_cast(data); - *x = mListForFree; - mListForFree = data; - - // create linked list for newly allocated data - auto* const headT = - reinterpret_cast_no_cast_align_warning(reinterpret_cast(ptr) + ALIGNMENT); - - auto* const head = reinterpret_cast(headT); - - // Visual Studio compiler automatically unrolls this loop, which is pretty cool - for (size_t i = 0; i < numElements; ++i) { - *reinterpret_cast_no_cast_align_warning(head + i * ALIGNED_SIZE) = - head + (i + 1) * ALIGNED_SIZE; - } - - // last one points to 0 - *reinterpret_cast_no_cast_align_warning(head + (numElements - 1) * ALIGNED_SIZE) = - mHead; - mHead = headT; - } - - // Called when no memory is available (mHead == 0). - // Don't inline this slow path. - ROBIN_HOOD(NOINLINE) T* performAllocation() { - size_t const numElementsToAlloc = calcNumElementsToAlloc(); - - // alloc new memory: [prev |T, T, ... T] - size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc; - ROBIN_HOOD_LOG("std::malloc " << bytes << " = " << ALIGNMENT << " + " << ALIGNED_SIZE - << " * " << numElementsToAlloc) - add(assertNotNull(std::malloc(bytes)), bytes); - return mHead; - } - - // enforce byte alignment of the T's -#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) - static constexpr size_t ALIGNMENT = - (std::max)(std::alignment_of::value, std::alignment_of::value); -#else - static const size_t ALIGNMENT = - (ROBIN_HOOD_STD::alignment_of::value > ROBIN_HOOD_STD::alignment_of::value) - ? ROBIN_HOOD_STD::alignment_of::value - : +ROBIN_HOOD_STD::alignment_of::value; // the + is for walkarround -#endif - - static constexpr size_t ALIGNED_SIZE = ((sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT; - - static_assert(MinNumAllocs >= 1, "MinNumAllocs"); - static_assert(MaxNumAllocs >= MinNumAllocs, "MaxNumAllocs"); - static_assert(ALIGNED_SIZE >= sizeof(T*), "ALIGNED_SIZE"); - static_assert(0 == (ALIGNED_SIZE % sizeof(T*)), "ALIGNED_SIZE mod"); - static_assert(ALIGNMENT >= sizeof(T*), "ALIGNMENT"); - - T* mHead{nullptr}; - T** mListForFree{nullptr}; -}; - -template -struct NodeAllocator; - -// dummy allocator that does nothing -template -struct NodeAllocator { - - // we are not using the data, so just free it. - void addOrFree(void* ptr, size_t ROBIN_HOOD_UNUSED(numBytes) /*unused*/) noexcept { - ROBIN_HOOD_LOG("std::free") - std::free(ptr); - } -}; - -template -struct NodeAllocator : public BulkPoolAllocator {}; - -// c++14 doesn't have is_nothrow_swappable, and clang++ 6.0.1 doesn't like it either, so I'm making -// my own here. -namespace swappable { -#if ROBIN_HOOD(CXX) < ROBIN_HOOD(CXX17) -using std::swap; -template -struct nothrow { - static const bool value = noexcept(swap(std::declval(), std::declval())); -}; -#else -template -struct nothrow { - static const bool value = std::is_nothrow_swappable::value; -}; -#endif -} // namespace swappable - -} // namespace detail - -struct is_transparent_tag {}; - -// A custom pair implementation is used in the map because std::pair is not is_trivially_copyable, -// which means it would not be allowed to be used in std::memcpy. This struct is copyable, which is -// also tested. -template -struct pair { - using first_type = T1; - using second_type = T2; - - template ::value && - std::is_default_constructible::value>::type> - constexpr pair() noexcept(noexcept(U1()) && noexcept(U2())) - : first() - , second() {} - - // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. - explicit constexpr pair(std::pair const& o) noexcept( - noexcept(T1(std::declval())) && noexcept(T2(std::declval()))) - : first(o.first) - , second(o.second) {} - - // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. - explicit constexpr pair(std::pair&& o) noexcept(noexcept( - T1(std::move(std::declval()))) && noexcept(T2(std::move(std::declval())))) - : first(std::move(o.first)) - , second(std::move(o.second)) {} - - constexpr pair(T1&& a, T2&& b) noexcept(noexcept( - T1(std::move(std::declval()))) && noexcept(T2(std::move(std::declval())))) - : first(std::move(a)) - , second(std::move(b)) {} - - template - constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward( - std::declval()))) && noexcept(T2(std::forward(std::declval())))) - : first(std::forward(a)) - , second(std::forward(b)) {} - - template - // MSVC 2015 produces error "C2476: ‘constexpr’ constructor does not initialize all members" - // if this constructor is constexpr -#if !ROBIN_HOOD(BROKEN_CONSTEXPR) - constexpr -#endif - pair(std::piecewise_construct_t /*unused*/, std::tuple a, - std::tuple - b) noexcept(noexcept(pair(std::declval&>(), - std::declval&>(), - ROBIN_HOOD_STD::index_sequence_for(), - ROBIN_HOOD_STD::index_sequence_for()))) - : pair(a, b, ROBIN_HOOD_STD::index_sequence_for(), - ROBIN_HOOD_STD::index_sequence_for()) { - } - - // constructor called from the std::piecewise_construct_t ctor - template - pair(std::tuple& a, std::tuple& b, ROBIN_HOOD_STD::index_sequence /*unused*/, ROBIN_HOOD_STD::index_sequence /*unused*/) noexcept( - noexcept(T1(std::forward(std::get( - std::declval&>()))...)) && noexcept(T2(std:: - forward(std::get( - std::declval&>()))...))) - : first(std::forward(std::get(a))...) - , second(std::forward(std::get(b))...) { - // make visual studio compiler happy about warning about unused a & b. - // Visual studio's pair implementation disables warning 4100. - (void)a; - (void)b; - } - - void swap(pair& o) noexcept((detail::swappable::nothrow::value) && - (detail::swappable::nothrow::value)) { - using std::swap; - swap(first, o.first); - swap(second, o.second); - } - - T1 first; // NOLINT(misc-non-private-member-variables-in-classes) - T2 second; // NOLINT(misc-non-private-member-variables-in-classes) -}; - -template -inline void swap(pair& a, pair& b) noexcept( - noexcept(std::declval&>().swap(std::declval&>()))) { - a.swap(b); -} - -template -inline constexpr bool operator==(pair const& x, pair const& y) { - return (x.first == y.first) && (x.second == y.second); -} -template -inline constexpr bool operator!=(pair const& x, pair const& y) { - return !(x == y); -} -template -inline constexpr bool operator<(pair const& x, pair const& y) noexcept(noexcept( - std::declval() < std::declval()) && noexcept(std::declval() < - std::declval())) { - return x.first < y.first || (!(y.first < x.first) && x.second < y.second); -} -template -inline constexpr bool operator>(pair const& x, pair const& y) { - return y < x; -} -template -inline constexpr bool operator<=(pair const& x, pair const& y) { - return !(x > y); -} -template -inline constexpr bool operator>=(pair const& x, pair const& y) { - return !(x < y); -} - -inline size_t hash_bytes(void const* ptr, size_t len) noexcept { - static constexpr uint64_t m = UINT64_C(0xc6a4a7935bd1e995); - static constexpr uint64_t seed = UINT64_C(0xe17a1465); - static constexpr unsigned int r = 47; - - auto const* const data64 = static_cast(ptr); - uint64_t h = seed ^ (len * m); - - size_t const n_blocks = len / 8; - for (size_t i = 0; i < n_blocks; ++i) { - auto k = detail::unaligned_load(data64 + i); - - k *= m; - k ^= k >> r; - k *= m; - - h ^= k; - h *= m; - } - - auto const* const data8 = reinterpret_cast(data64 + n_blocks); - switch (len & 7U) { - case 7: - h ^= static_cast(data8[6]) << 48U; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - case 6: - h ^= static_cast(data8[5]) << 40U; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - case 5: - h ^= static_cast(data8[4]) << 32U; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - case 4: - h ^= static_cast(data8[3]) << 24U; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - case 3: - h ^= static_cast(data8[2]) << 16U; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - case 2: - h ^= static_cast(data8[1]) << 8U; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - case 1: - h ^= static_cast(data8[0]); - h *= m; - ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH - default: - break; - } - - h ^= h >> r; - - // not doing the final step here, because this will be done by keyToIdx anyways - // h *= m; - // h ^= h >> r; - return static_cast(h); -} - -inline size_t hash_int(uint64_t x) noexcept { - // tried lots of different hashes, let's stick with murmurhash3. It's simple, fast, well tested, - // and doesn't need any special 128bit operations. - x ^= x >> 33U; - x *= UINT64_C(0xff51afd7ed558ccd); - x ^= x >> 33U; - - // not doing the final step here, because this will be done by keyToIdx anyways - // x *= UINT64_C(0xc4ceb9fe1a85ec53); - // x ^= x >> 33U; - return static_cast(x); -} - -// A thin wrapper around std::hash, performing an additional simple mixing step of the result. -template -struct hash : public std::hash { - size_t operator()(T const& obj) const - noexcept(noexcept(std::declval>().operator()(std::declval()))) { - // call base hash - auto result = std::hash::operator()(obj); - // return mixed of that, to be save against identity has - return hash_int(static_cast(result)); - } -}; - -template -struct hash> { - size_t operator()(std::basic_string const& str) const noexcept { - return hash_bytes(str.data(), sizeof(CharT) * str.size()); - } -}; - -#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX17) -template -struct hash> { - size_t operator()(std::basic_string_view const& sv) const noexcept { - return hash_bytes(sv.data(), sizeof(CharT) * sv.size()); - } -}; -#endif - -template -struct hash { - size_t operator()(T* ptr) const noexcept { - return hash_int(reinterpret_cast(ptr)); - } -}; - -template -struct hash> { - size_t operator()(std::unique_ptr const& ptr) const noexcept { - return hash_int(reinterpret_cast(ptr.get())); - } -}; - -template -struct hash> { - size_t operator()(std::shared_ptr const& ptr) const noexcept { - return hash_int(reinterpret_cast(ptr.get())); - } -}; - -template -struct hash::value>::type> { - size_t operator()(Enum e) const noexcept { - using Underlying = typename std::underlying_type::type; - return hash{}(static_cast(e)); - } -}; - -#define ROBIN_HOOD_HASH_INT(T) \ - template <> \ - struct hash { \ - size_t operator()(T const& obj) const noexcept { \ - return hash_int(static_cast(obj)); \ - } \ - } - -#if defined(__GNUC__) && !defined(__clang__) -# pragma GCC diagnostic push -# pragma GCC diagnostic ignored "-Wuseless-cast" -#endif -// see https://en.cppreference.com/w/cpp/utility/hash -ROBIN_HOOD_HASH_INT(bool); -ROBIN_HOOD_HASH_INT(char); -ROBIN_HOOD_HASH_INT(signed char); -ROBIN_HOOD_HASH_INT(unsigned char); -ROBIN_HOOD_HASH_INT(char16_t); -ROBIN_HOOD_HASH_INT(char32_t); -#if ROBIN_HOOD(HAS_NATIVE_WCHART) -ROBIN_HOOD_HASH_INT(wchar_t); -#endif -ROBIN_HOOD_HASH_INT(short); -ROBIN_HOOD_HASH_INT(unsigned short); -ROBIN_HOOD_HASH_INT(int); -ROBIN_HOOD_HASH_INT(unsigned int); -ROBIN_HOOD_HASH_INT(long); -ROBIN_HOOD_HASH_INT(long long); -ROBIN_HOOD_HASH_INT(unsigned long); -ROBIN_HOOD_HASH_INT(unsigned long long); -#if defined(__GNUC__) && !defined(__clang__) -# pragma GCC diagnostic pop -#endif -namespace detail { - -template -struct void_type { - using type = void; -}; - -template -struct has_is_transparent : public std::false_type {}; - -template -struct has_is_transparent::type> - : public std::true_type {}; - -// using wrapper classes for hash and key_equal prevents the diamond problem when the same type -// is used. see https://stackoverflow.com/a/28771920/48181 -template -struct WrapHash : public T { - WrapHash() = default; - explicit WrapHash(T const& o) noexcept(noexcept(T(std::declval()))) - : T(o) {} -}; - -template -struct WrapKeyEqual : public T { - WrapKeyEqual() = default; - explicit WrapKeyEqual(T const& o) noexcept(noexcept(T(std::declval()))) - : T(o) {} -}; - -// A highly optimized hashmap implementation, using the Robin Hood algorithm. -// -// In most cases, this map should be usable as a drop-in replacement for std::unordered_map, but -// be about 2x faster in most cases and require much less allocations. -// -// This implementation uses the following memory layout: -// -// [Node, Node, ... Node | info, info, ... infoSentinel ] -// -// * Node: either a DataNode that directly has the std::pair as member, -// or a DataNode with a pointer to std::pair. Which DataNode representation to use -// depends on how fast the swap() operation is. Heuristically, this is automatically choosen -// based on sizeof(). there are always 2^n Nodes. -// -// * info: Each Node in the map has a corresponding info byte, so there are 2^n info bytes. -// Each byte is initialized to 0, meaning the corresponding Node is empty. Set to 1 means the -// corresponding node contains data. Set to 2 means the corresponding Node is filled, but it -// actually belongs to the previous position and was pushed out because that place is already -// taken. -// -// * infoSentinel: Sentinel byte set to 1, so that iterator's ++ can stop at end() without the -// need for a idx variable. -// -// According to STL, order of templates has effect on throughput. That's why I've moved the -// boolean to the front. -// https://www.reddit.com/r/cpp/comments/ahp6iu/compile_time_binary_size_reductions_and_cs_future/eeguck4/ -template -class Table - : public WrapHash, - public WrapKeyEqual, - detail::NodeAllocator< - typename std::conditional< - std::is_void::value, Key, - robin_hood::pair::type, T>>::type, - 4, 16384, IsFlat> { -public: - static constexpr bool is_flat = IsFlat; - static constexpr bool is_map = !std::is_void::value; - static constexpr bool is_set = !is_map; - static constexpr bool is_transparent = - has_is_transparent::value && has_is_transparent::value; - - using key_type = Key; - using mapped_type = T; - using value_type = typename std::conditional< - is_set, Key, - robin_hood::pair::type, T>>::type; - using size_type = size_t; - using hasher = Hash; - using key_equal = KeyEqual; - using Self = Table; - -private: - static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100, - "MaxLoadFactor100 needs to be >10 && < 100"); - - using WHash = WrapHash; - using WKeyEqual = WrapKeyEqual; - - // configuration defaults - - // make sure we have 8 elements, needed to quickly rehash mInfo - static constexpr size_t InitialNumElements = sizeof(uint64_t); - static constexpr uint32_t InitialInfoNumBits = 5; - static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits; - static constexpr size_t InfoMask = InitialInfoInc - 1U; - static constexpr uint8_t InitialInfoHashShift = 0; - using DataPool = detail::NodeAllocator; - - // type needs to be wider than uint8_t. - using InfoType = uint32_t; - - // DataNode //////////////////////////////////////////////////////// - - // Primary template for the data node. We have special implementations for small and big - // objects. For large objects it is assumed that swap() is fairly slow, so we allocate these - // on the heap so swap merely swaps a pointer. - template - class DataNode {}; - - // Small: just allocate on the stack. - template - class DataNode final { - public: - template - explicit DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, Args&&... args) noexcept( - noexcept(value_type(std::forward(args)...))) - : mData(std::forward(args)...) {} - - DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept( - std::is_nothrow_move_constructible::value) - : mData(std::move(n.mData)) {} - - // doesn't do anything - void destroy(M& ROBIN_HOOD_UNUSED(map) /*unused*/) noexcept {} - void destroyDoNotDeallocate() noexcept {} - - value_type const* operator->() const noexcept { - return &mData; - } - value_type* operator->() noexcept { - return &mData; - } - - const value_type& operator*() const noexcept { - return mData; - } - - value_type& operator*() noexcept { - return mData; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() noexcept { - return mData.first; - } - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() noexcept { - return mData; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type - getFirst() const noexcept { - return mData.first; - } - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() const noexcept { - return mData; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getSecond() noexcept { - return mData.second; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getSecond() const noexcept { - return mData.second; - } - - void swap(DataNode& o) noexcept( - noexcept(std::declval().swap(std::declval()))) { - mData.swap(o.mData); - } - - private: - value_type mData; - }; - - // big object: allocate on heap. - template - class DataNode { - public: - template - explicit DataNode(M& map, Args&&... args) - : mData(map.allocate()) { - ::new (static_cast(mData)) value_type(std::forward(args)...); - } - - DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept - : mData(std::move(n.mData)) {} - - void destroy(M& map) noexcept { - // don't deallocate, just put it into list of datapool. - mData->~value_type(); - map.deallocate(mData); - } - - void destroyDoNotDeallocate() noexcept { - mData->~value_type(); - } - - value_type const* operator->() const noexcept { - return mData; - } - - value_type* operator->() noexcept { - return mData; - } - - const value_type& operator*() const { - return *mData; - } - - value_type& operator*() { - return *mData; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() noexcept { - return mData->first; - } - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() noexcept { - return *mData; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type - getFirst() const noexcept { - return mData->first; - } - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() const noexcept { - return *mData; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getSecond() noexcept { - return mData->second; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getSecond() const noexcept { - return mData->second; - } - - void swap(DataNode& o) noexcept { - using std::swap; - swap(mData, o.mData); - } - - private: - value_type* mData; - }; - - using Node = DataNode; - - // helpers for insertKeyPrepareEmptySpot: extract first entry (only const required) - ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(Node const& n) const noexcept { - return n.getFirst(); - } - - // in case we have void mapped_type, we are not using a pair, thus we just route k through. - // No need to disable this because it's just not used if not applicable. - ROBIN_HOOD(NODISCARD) key_type const& getFirstConst(key_type const& k) const noexcept { - return k; - } - - // in case we have non-void mapped_type, we have a standard robin_hood::pair - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::value, key_type const&>::type - getFirstConst(value_type const& vt) const noexcept { - return vt.first; - } - - // Cloner ////////////////////////////////////////////////////////// - - template - struct Cloner; - - // fast path: Just copy data, without allocating anything. - template - struct Cloner { - void operator()(M const& source, M& target) const { - auto const* const src = reinterpret_cast(source.mKeyVals); - auto* tgt = reinterpret_cast(target.mKeyVals); - auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1); - std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt); - } - }; - - template - struct Cloner { - void operator()(M const& s, M& t) const { - auto const numElementsWithBuffer = t.calcNumElementsWithBuffer(t.mMask + 1); - std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(numElementsWithBuffer), t.mInfo); - - for (size_t i = 0; i < numElementsWithBuffer; ++i) { - if (t.mInfo[i]) { - ::new (static_cast(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]); - } - } - } - }; - - // Destroyer /////////////////////////////////////////////////////// - - template - struct Destroyer {}; - - template - struct Destroyer { - void nodes(M& m) const noexcept { - m.mNumElements = 0; - } - - void nodesDoNotDeallocate(M& m) const noexcept { - m.mNumElements = 0; - } - }; - - template - struct Destroyer { - void nodes(M& m) const noexcept { - m.mNumElements = 0; - // clear also resets mInfo to 0, that's sometimes not necessary. - auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); - - for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { - if (0 != m.mInfo[idx]) { - Node& n = m.mKeyVals[idx]; - n.destroy(m); - n.~Node(); - } - } - } - - void nodesDoNotDeallocate(M& m) const noexcept { - m.mNumElements = 0; - // clear also resets mInfo to 0, that's sometimes not necessary. - auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); - for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { - if (0 != m.mInfo[idx]) { - Node& n = m.mKeyVals[idx]; - n.destroyDoNotDeallocate(); - n.~Node(); - } - } - } - }; - - // Iter //////////////////////////////////////////////////////////// - - struct fast_forward_tag {}; - - // generic iterator for both const_iterator and iterator. - template - // NOLINTNEXTLINE(hicpp-special-member-functions,cppcoreguidelines-special-member-functions) - class Iter { - private: - using NodePtr = typename std::conditional::type; - - public: - using difference_type = std::ptrdiff_t; - using value_type = typename Self::value_type; - using reference = typename std::conditional::type; - using pointer = typename std::conditional::type; - using iterator_category = std::forward_iterator_tag; - - // default constructed iterator can be compared to itself, but WON'T return true when - // compared to end(). - Iter() = default; - - // Rule of zero: nothing specified. The conversion constructor is only enabled for - // iterator to const_iterator, so it doesn't accidentally work as a copy ctor. - - // Conversion constructor from iterator to const_iterator. - template ::type> - // NOLINTNEXTLINE(hicpp-explicit-conversions) - Iter(Iter const& other) noexcept - : mKeyVals(other.mKeyVals) - , mInfo(other.mInfo) {} - - Iter(NodePtr valPtr, uint8_t const* infoPtr) noexcept - : mKeyVals(valPtr) - , mInfo(infoPtr) {} - - Iter(NodePtr valPtr, uint8_t const* infoPtr, - fast_forward_tag ROBIN_HOOD_UNUSED(tag) /*unused*/) noexcept - : mKeyVals(valPtr) - , mInfo(infoPtr) { - fastForward(); - } - - template ::type> - Iter& operator=(Iter const& other) noexcept { - mKeyVals = other.mKeyVals; - mInfo = other.mInfo; - return *this; - } - - // prefix increment. Undefined behavior if we are at end()! - Iter& operator++() noexcept { - mInfo++; - mKeyVals++; - fastForward(); - return *this; - } - - Iter operator++(int) noexcept { - Iter tmp = *this; - ++(*this); - return tmp; - } - - reference operator*() const { - return **mKeyVals; - } - - pointer operator->() const { - return &**mKeyVals; - } - - template - bool operator==(Iter const& o) const noexcept { - return mKeyVals == o.mKeyVals; - } - - template - bool operator!=(Iter const& o) const noexcept { - return mKeyVals != o.mKeyVals; - } - - private: - // fast forward to the next non-free info byte - // I've tried a few variants that don't depend on intrinsics, but unfortunately they are - // quite a bit slower than this one. So I've reverted that change again. See map_benchmark. - void fastForward() noexcept { - size_t n = 0; - while (0U == (n = detail::unaligned_load(mInfo))) { - mInfo += sizeof(size_t); - mKeyVals += sizeof(size_t); - } -#if defined(ROBIN_HOOD_DISABLE_INTRINSICS) - // we know for certain that within the next 8 bytes we'll find a non-zero one. - if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load(mInfo))) { - mInfo += 4; - mKeyVals += 4; - } - if (ROBIN_HOOD_UNLIKELY(0U == detail::unaligned_load(mInfo))) { - mInfo += 2; - mKeyVals += 2; - } - if (ROBIN_HOOD_UNLIKELY(0U == *mInfo)) { - mInfo += 1; - mKeyVals += 1; - } -#else -# if ROBIN_HOOD(LITTLE_ENDIAN) - auto inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8; -# else - auto inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8; -# endif - mInfo += inc; - mKeyVals += inc; -#endif - } - - friend class Table; - NodePtr mKeyVals{nullptr}; - uint8_t const* mInfo{nullptr}; - }; - - //////////////////////////////////////////////////////////////////// - - // highly performance relevant code. - // Lower bits are used for indexing into the array (2^n size) - // The upper 1-5 bits need to be a reasonable good hash, to save comparisons. - template - void keyToIdx(HashKey&& key, size_t* idx, InfoType* info) const { - // In addition to whatever hash is used, add another mul & shift so we get better hashing. - // This serves as a bad hash prevention, if the given data is - // badly mixed. - auto h = static_cast(WHash::operator()(key)); - - h *= mHashMultiplier; - h ^= h >> 33U; - - // the lower InitialInfoNumBits are reserved for info. - *info = mInfoInc + static_cast((h & InfoMask) >> mInfoHashShift); - *idx = (static_cast(h) >> InitialInfoNumBits) & mMask; - } - - // forwards the index by one, wrapping around at the end - void next(InfoType* info, size_t* idx) const noexcept { - *idx = *idx + 1; - *info += mInfoInc; - } - - void nextWhileLess(InfoType* info, size_t* idx) const noexcept { - // unrolling this by hand did not bring any speedups. - while (*info < mInfo[*idx]) { - next(info, idx); - } - } - - // Shift everything up by one element. Tries to move stuff around. - void - shiftUp(size_t startIdx, - size_t const insertion_idx) noexcept(std::is_nothrow_move_assignable::value) { - auto idx = startIdx; - ::new (static_cast(mKeyVals + idx)) Node(std::move(mKeyVals[idx - 1])); - while (--idx != insertion_idx) { - mKeyVals[idx] = std::move(mKeyVals[idx - 1]); - } - - idx = startIdx; - while (idx != insertion_idx) { - ROBIN_HOOD_COUNT(shiftUp) - mInfo[idx] = static_cast(mInfo[idx - 1] + mInfoInc); - if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) { - mMaxNumElementsAllowed = 0; - } - --idx; - } - } - - void shiftDown(size_t idx) noexcept(std::is_nothrow_move_assignable::value) { - // until we find one that is either empty or has zero offset. - // TODO(martinus) we don't need to move everything, just the last one for the same - // bucket. - mKeyVals[idx].destroy(*this); - - // until we find one that is either empty or has zero offset. - while (mInfo[idx + 1] >= 2 * mInfoInc) { - ROBIN_HOOD_COUNT(shiftDown) - mInfo[idx] = static_cast(mInfo[idx + 1] - mInfoInc); - mKeyVals[idx] = std::move(mKeyVals[idx + 1]); - ++idx; - } - - mInfo[idx] = 0; - // don't destroy, we've moved it - // mKeyVals[idx].destroy(*this); - mKeyVals[idx].~Node(); - } - - // copy of find(), except that it returns iterator instead of const_iterator. - template - ROBIN_HOOD(NODISCARD) - size_t findIdx(Other const& key) const { - size_t idx{}; - InfoType info{}; - keyToIdx(key, &idx, &info); - - do { - // unrolling this twice gives a bit of a speedup. More unrolling did not help. - if (info == mInfo[idx] && - ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { - return idx; - } - next(&info, &idx); - if (info == mInfo[idx] && - ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { - return idx; - } - next(&info, &idx); - } while (info <= mInfo[idx]); - - // nothing found! - return mMask == 0 ? 0 - : static_cast(std::distance( - mKeyVals, reinterpret_cast_no_cast_align_warning(mInfo))); - } - - void cloneData(const Table& o) { - Cloner()(o, *this); - } - - // inserts a keyval that is guaranteed to be new, e.g. when the hashmap is resized. - // @return True on success, false if something went wrong - void insert_move(Node&& keyval) { - // we don't retry, fail if overflowing - // don't need to check max num elements - if (0 == mMaxNumElementsAllowed && !try_increase_info()) { - throwOverflowError(); - } - - size_t idx{}; - InfoType info{}; - keyToIdx(keyval.getFirst(), &idx, &info); - - // skip forward. Use <= because we are certain that the element is not there. - while (info <= mInfo[idx]) { - idx = idx + 1; - info += mInfoInc; - } - - // key not found, so we are now exactly where we want to insert it. - auto const insertion_idx = idx; - auto const insertion_info = static_cast(info); - if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { - mMaxNumElementsAllowed = 0; - } - - // find an empty spot - while (0 != mInfo[idx]) { - next(&info, &idx); - } - - auto& l = mKeyVals[insertion_idx]; - if (idx == insertion_idx) { - ::new (static_cast(&l)) Node(std::move(keyval)); - } else { - shiftUp(idx, insertion_idx); - l = std::move(keyval); - } - - // put at empty spot - mInfo[insertion_idx] = insertion_info; - - ++mNumElements; - } - -public: - using iterator = Iter; - using const_iterator = Iter; - - Table() noexcept(noexcept(Hash()) && noexcept(KeyEqual())) - : WHash() - , WKeyEqual() { - ROBIN_HOOD_TRACE(this) - } - - // Creates an empty hash map. Nothing is allocated yet, this happens at the first insert. - // This tremendously speeds up ctor & dtor of a map that never receives an element. The - // penalty is payed at the first insert, and not before. Lookup of this empty map works - // because everybody points to DummyInfoByte::b. parameter bucket_count is dictated by the - // standard, but we can ignore it. - explicit Table( - size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/, const Hash& h = Hash{}, - const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && noexcept(KeyEqual(equal))) - : WHash(h) - , WKeyEqual(equal) { - ROBIN_HOOD_TRACE(this) - } - - template - Table(Iter first, Iter last, size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, - const Hash& h = Hash{}, const KeyEqual& equal = KeyEqual{}) - : WHash(h) - , WKeyEqual(equal) { - ROBIN_HOOD_TRACE(this) - insert(first, last); - } - - Table(std::initializer_list initlist, - size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, const Hash& h = Hash{}, - const KeyEqual& equal = KeyEqual{}) - : WHash(h) - , WKeyEqual(equal) { - ROBIN_HOOD_TRACE(this) - insert(initlist.begin(), initlist.end()); - } - - Table(Table&& o) noexcept - : WHash(std::move(static_cast(o))) - , WKeyEqual(std::move(static_cast(o))) - , DataPool(std::move(static_cast(o))) { - ROBIN_HOOD_TRACE(this) - if (o.mMask) { - mHashMultiplier = std::move(o.mHashMultiplier); - mKeyVals = std::move(o.mKeyVals); - mInfo = std::move(o.mInfo); - mNumElements = std::move(o.mNumElements); - mMask = std::move(o.mMask); - mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed); - mInfoInc = std::move(o.mInfoInc); - mInfoHashShift = std::move(o.mInfoHashShift); - // set other's mask to 0 so its destructor won't do anything - o.init(); - } - } - - Table& operator=(Table&& o) noexcept { - ROBIN_HOOD_TRACE(this) - if (&o != this) { - if (o.mMask) { - // only move stuff if the other map actually has some data - destroy(); - mHashMultiplier = std::move(o.mHashMultiplier); - mKeyVals = std::move(o.mKeyVals); - mInfo = std::move(o.mInfo); - mNumElements = std::move(o.mNumElements); - mMask = std::move(o.mMask); - mMaxNumElementsAllowed = std::move(o.mMaxNumElementsAllowed); - mInfoInc = std::move(o.mInfoInc); - mInfoHashShift = std::move(o.mInfoHashShift); - WHash::operator=(std::move(static_cast(o))); - WKeyEqual::operator=(std::move(static_cast(o))); - DataPool::operator=(std::move(static_cast(o))); - - o.init(); - - } else { - // nothing in the other map => just clear us. - clear(); - } - } - return *this; - } - - Table(const Table& o) - : WHash(static_cast(o)) - , WKeyEqual(static_cast(o)) - , DataPool(static_cast(o)) { - ROBIN_HOOD_TRACE(this) - if (!o.empty()) { - // not empty: create an exact copy. it is also possible to just iterate through all - // elements and insert them, but copying is probably faster. - - auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); - auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); - - ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal(" - << numElementsWithBuffer << ")") - mHashMultiplier = o.mHashMultiplier; - mKeyVals = static_cast( - detail::assertNotNull(std::malloc(numBytesTotal))); - // no need for calloc because clonData does memcpy - mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); - mNumElements = o.mNumElements; - mMask = o.mMask; - mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; - mInfoInc = o.mInfoInc; - mInfoHashShift = o.mInfoHashShift; - cloneData(o); - } - } - - // Creates a copy of the given map. Copy constructor of each entry is used. - // Not sure why clang-tidy thinks this doesn't handle self assignment, it does - // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) - Table& operator=(Table const& o) { - ROBIN_HOOD_TRACE(this) - if (&o == this) { - // prevent assigning of itself - return *this; - } - - // we keep using the old allocator and not assign the new one, because we want to keep - // the memory available. when it is the same size. - if (o.empty()) { - if (0 == mMask) { - // nothing to do, we are empty too - return *this; - } - - // not empty: destroy what we have there - // clear also resets mInfo to 0, that's sometimes not necessary. - destroy(); - init(); - WHash::operator=(static_cast(o)); - WKeyEqual::operator=(static_cast(o)); - DataPool::operator=(static_cast(o)); - - return *this; - } - - // clean up old stuff - Destroyer::value>{}.nodes(*this); - - if (mMask != o.mMask) { - // no luck: we don't have the same array size allocated, so we need to realloc. - if (0 != mMask) { - // only deallocate if we actually have data! - ROBIN_HOOD_LOG("std::free") - std::free(mKeyVals); - } - - auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); - auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); - ROBIN_HOOD_LOG("std::malloc " << numBytesTotal << " = calcNumBytesTotal(" - << numElementsWithBuffer << ")") - mKeyVals = static_cast( - detail::assertNotNull(std::malloc(numBytesTotal))); - - // no need for calloc here because cloneData performs a memcpy. - mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); - // sentinel is set in cloneData - } - WHash::operator=(static_cast(o)); - WKeyEqual::operator=(static_cast(o)); - DataPool::operator=(static_cast(o)); - mHashMultiplier = o.mHashMultiplier; - mNumElements = o.mNumElements; - mMask = o.mMask; - mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; - mInfoInc = o.mInfoInc; - mInfoHashShift = o.mInfoHashShift; - cloneData(o); - - return *this; - } - - // Swaps everything between the two maps. - void swap(Table& o) { - ROBIN_HOOD_TRACE(this) - using std::swap; - swap(o, *this); - } - - // Clears all data, without resizing. - void clear() { - ROBIN_HOOD_TRACE(this) - if (empty()) { - // don't do anything! also important because we don't want to write to - // DummyInfoByte::b, even though we would just write 0 to it. - return; - } - - Destroyer::value>{}.nodes(*this); - - auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); - // clear everything, then set the sentinel again - uint8_t const z = 0; - std::fill(mInfo, mInfo + calcNumBytesInfo(numElementsWithBuffer), z); - mInfo[numElementsWithBuffer] = 1; - - mInfoInc = InitialInfoInc; - mInfoHashShift = InitialInfoHashShift; - } - - // Destroys the map and all it's contents. - ~Table() { - ROBIN_HOOD_TRACE(this) - destroy(); - } - - // Checks if both tables contain the same entries. Order is irrelevant. - bool operator==(const Table& other) const { - ROBIN_HOOD_TRACE(this) - if (other.size() != size()) { - return false; - } - for (auto const& otherEntry : other) { - if (!has(otherEntry)) { - return false; - } - } - - return true; - } - - bool operator!=(const Table& other) const { - ROBIN_HOOD_TRACE(this) - return !operator==(other); - } - - template - typename std::enable_if::value, Q&>::type operator[](const key_type& key) { - ROBIN_HOOD_TRACE(this) - auto idxAndState = insertKeyPrepareEmptySpot(key); - switch (idxAndState.second) { - case InsertionState::key_found: - break; - - case InsertionState::new_node: - ::new (static_cast(&mKeyVals[idxAndState.first])) - Node(*this, std::piecewise_construct, std::forward_as_tuple(key), - std::forward_as_tuple()); - break; - - case InsertionState::overwrite_node: - mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct, - std::forward_as_tuple(key), std::forward_as_tuple()); - break; - - case InsertionState::overflow_error: - throwOverflowError(); - } - - return mKeyVals[idxAndState.first].getSecond(); - } - - template - typename std::enable_if::value, Q&>::type operator[](key_type&& key) { - ROBIN_HOOD_TRACE(this) - auto idxAndState = insertKeyPrepareEmptySpot(key); - switch (idxAndState.second) { - case InsertionState::key_found: - break; - - case InsertionState::new_node: - ::new (static_cast(&mKeyVals[idxAndState.first])) - Node(*this, std::piecewise_construct, std::forward_as_tuple(std::move(key)), - std::forward_as_tuple()); - break; - - case InsertionState::overwrite_node: - mKeyVals[idxAndState.first] = - Node(*this, std::piecewise_construct, std::forward_as_tuple(std::move(key)), - std::forward_as_tuple()); - break; - - case InsertionState::overflow_error: - throwOverflowError(); - } - - return mKeyVals[idxAndState.first].getSecond(); - } - - template - void insert(Iter first, Iter last) { - for (; first != last; ++first) { - // value_type ctor needed because this might be called with std::pair's - insert(value_type(*first)); - } - } - - void insert(std::initializer_list ilist) { - for (auto&& vt : ilist) { - insert(std::move(vt)); - } - } - - template - std::pair emplace(Args&&... args) { - ROBIN_HOOD_TRACE(this) - Node n{*this, std::forward(args)...}; - auto idxAndState = insertKeyPrepareEmptySpot(getFirstConst(n)); - switch (idxAndState.second) { - case InsertionState::key_found: - n.destroy(*this); - break; - - case InsertionState::new_node: - ::new (static_cast(&mKeyVals[idxAndState.first])) Node(*this, std::move(n)); - break; - - case InsertionState::overwrite_node: - mKeyVals[idxAndState.first] = std::move(n); - break; - - case InsertionState::overflow_error: - n.destroy(*this); - throwOverflowError(); - break; - } - - return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first), - InsertionState::key_found != idxAndState.second); - } - - template - iterator emplace_hint(const_iterator position, Args&&... args) { - (void)position; - return emplace(std::forward(args)...).first; - } - - template - std::pair try_emplace(const key_type& key, Args&&... args) { - return try_emplace_impl(key, std::forward(args)...); - } - - template - std::pair try_emplace(key_type&& key, Args&&... args) { - return try_emplace_impl(std::move(key), std::forward(args)...); - } - - template - iterator try_emplace(const_iterator hint, const key_type& key, Args&&... args) { - (void)hint; - return try_emplace_impl(key, std::forward(args)...).first; - } - - template - iterator try_emplace(const_iterator hint, key_type&& key, Args&&... args) { - (void)hint; - return try_emplace_impl(std::move(key), std::forward(args)...).first; - } - - template - std::pair insert_or_assign(const key_type& key, Mapped&& obj) { - return insertOrAssignImpl(key, std::forward(obj)); - } - - template - std::pair insert_or_assign(key_type&& key, Mapped&& obj) { - return insertOrAssignImpl(std::move(key), std::forward(obj)); - } - - template - iterator insert_or_assign(const_iterator hint, const key_type& key, Mapped&& obj) { - (void)hint; - return insertOrAssignImpl(key, std::forward(obj)).first; - } - - template - iterator insert_or_assign(const_iterator hint, key_type&& key, Mapped&& obj) { - (void)hint; - return insertOrAssignImpl(std::move(key), std::forward(obj)).first; - } - - std::pair insert(const value_type& keyval) { - ROBIN_HOOD_TRACE(this) - return emplace(keyval); - } - - iterator insert(const_iterator hint, const value_type& keyval) { - (void)hint; - return emplace(keyval).first; - } - - std::pair insert(value_type&& keyval) { - return emplace(std::move(keyval)); - } - - iterator insert(const_iterator hint, value_type&& keyval) { - (void)hint; - return emplace(std::move(keyval)).first; - } - - // Returns 1 if key is found, 0 otherwise. - size_t count(const key_type& key) const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - auto kv = mKeyVals + findIdx(key); - if (kv != reinterpret_cast_no_cast_align_warning(mInfo)) { - return 1; - } - return 0; - } - - template - // NOLINTNEXTLINE(modernize-use-nodiscard) - typename std::enable_if::type count(const OtherKey& key) const { - ROBIN_HOOD_TRACE(this) - auto kv = mKeyVals + findIdx(key); - if (kv != reinterpret_cast_no_cast_align_warning(mInfo)) { - return 1; - } - return 0; - } - - bool contains(const key_type& key) const { // NOLINT(modernize-use-nodiscard) - return 1U == count(key); - } - - template - // NOLINTNEXTLINE(modernize-use-nodiscard) - typename std::enable_if::type contains(const OtherKey& key) const { - return 1U == count(key); - } - - // Returns a reference to the value found for key. - // Throws std::out_of_range if element cannot be found - template - // NOLINTNEXTLINE(modernize-use-nodiscard) - typename std::enable_if::value, Q&>::type at(key_type const& key) { - ROBIN_HOOD_TRACE(this) - auto kv = mKeyVals + findIdx(key); - if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { - doThrow("key not found"); - } - return kv->getSecond(); - } - - // Returns a reference to the value found for key. - // Throws std::out_of_range if element cannot be found - template - // NOLINTNEXTLINE(modernize-use-nodiscard) - typename std::enable_if::value, Q const&>::type at(key_type const& key) const { - ROBIN_HOOD_TRACE(this) - auto kv = mKeyVals + findIdx(key); - if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { - doThrow("key not found"); - } - return kv->getSecond(); - } - - const_iterator find(const key_type& key) const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - const size_t idx = findIdx(key); - return const_iterator{mKeyVals + idx, mInfo + idx}; - } - - template - const_iterator find(const OtherKey& key, is_transparent_tag /*unused*/) const { - ROBIN_HOOD_TRACE(this) - const size_t idx = findIdx(key); - return const_iterator{mKeyVals + idx, mInfo + idx}; - } - - template - typename std::enable_if::type // NOLINT(modernize-use-nodiscard) - find(const OtherKey& key) const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - const size_t idx = findIdx(key); - return const_iterator{mKeyVals + idx, mInfo + idx}; - } - - iterator find(const key_type& key) { - ROBIN_HOOD_TRACE(this) - const size_t idx = findIdx(key); - return iterator{mKeyVals + idx, mInfo + idx}; - } - - template - iterator find(const OtherKey& key, is_transparent_tag /*unused*/) { - ROBIN_HOOD_TRACE(this) - const size_t idx = findIdx(key); - return iterator{mKeyVals + idx, mInfo + idx}; - } - - template - typename std::enable_if::type find(const OtherKey& key) { - ROBIN_HOOD_TRACE(this) - const size_t idx = findIdx(key); - return iterator{mKeyVals + idx, mInfo + idx}; - } - - iterator begin() { - ROBIN_HOOD_TRACE(this) - if (empty()) { - return end(); - } - return iterator(mKeyVals, mInfo, fast_forward_tag{}); - } - const_iterator begin() const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return cbegin(); - } - const_iterator cbegin() const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - if (empty()) { - return cend(); - } - return const_iterator(mKeyVals, mInfo, fast_forward_tag{}); - } - - iterator end() { - ROBIN_HOOD_TRACE(this) - // no need to supply valid info pointer: end() must not be dereferenced, and only node - // pointer is compared. - return iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; - } - const_iterator end() const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return cend(); - } - const_iterator cend() const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return const_iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; - } - - iterator erase(const_iterator pos) { - ROBIN_HOOD_TRACE(this) - // its safe to perform const cast here - // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) - return erase(iterator{const_cast(pos.mKeyVals), const_cast(pos.mInfo)}); - } - - // Erases element at pos, returns iterator to the next element. - iterator erase(iterator pos) { - ROBIN_HOOD_TRACE(this) - // we assume that pos always points to a valid entry, and not end(). - auto const idx = static_cast(pos.mKeyVals - mKeyVals); - - shiftDown(idx); - --mNumElements; - - if (*pos.mInfo) { - // we've backward shifted, return this again - return pos; - } - - // no backward shift, return next element - return ++pos; - } - - size_t erase(const key_type& key) { - ROBIN_HOOD_TRACE(this) - size_t idx{}; - InfoType info{}; - keyToIdx(key, &idx, &info); - - // check while info matches with the source idx - do { - if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { - shiftDown(idx); - --mNumElements; - return 1; - } - next(&info, &idx); - } while (info <= mInfo[idx]); - - // nothing found to delete - return 0; - } - - // reserves space for the specified number of elements. Makes sure the old data fits. - // exactly the same as reserve(c). - void rehash(size_t c) { - // forces a reserve - reserve(c, true); - } - - // reserves space for the specified number of elements. Makes sure the old data fits. - // Exactly the same as rehash(c). Use rehash(0) to shrink to fit. - void reserve(size_t c) { - // reserve, but don't force rehash - reserve(c, false); - } - - // If possible reallocates the map to a smaller one. This frees the underlying table. - // Does not do anything if load_factor is too large for decreasing the table's size. - void compact() { - ROBIN_HOOD_TRACE(this) - auto newSize = InitialNumElements; - while (calcMaxNumElementsAllowed(newSize) < mNumElements && newSize != 0) { - newSize *= 2; - } - if (ROBIN_HOOD_UNLIKELY(newSize == 0)) { - throwOverflowError(); - } - - ROBIN_HOOD_LOG("newSize > mMask + 1: " << newSize << " > " << mMask << " + 1") - - // only actually do anything when the new size is bigger than the old one. This prevents to - // continuously allocate for each reserve() call. - if (newSize < mMask + 1) { - rehashPowerOfTwo(newSize, true); - } - } - - size_type size() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return mNumElements; - } - - size_type max_size() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return static_cast(-1); - } - - ROBIN_HOOD(NODISCARD) bool empty() const noexcept { - ROBIN_HOOD_TRACE(this) - return 0 == mNumElements; - } - - float max_load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return MaxLoadFactor100 / 100.0F; - } - - // Average number of elements per bucket. Since we allow only 1 per bucket - float load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this) - return static_cast(size()) / static_cast(mMask + 1); - } - - ROBIN_HOOD(NODISCARD) size_t mask() const noexcept { - ROBIN_HOOD_TRACE(this) - return mMask; - } - - ROBIN_HOOD(NODISCARD) size_t calcMaxNumElementsAllowed(size_t maxElements) const noexcept { - if (ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits::max)() / 100)) { - return maxElements * MaxLoadFactor100 / 100; - } - - // we might be a bit inprecise, but since maxElements is quite large that doesn't matter - return (maxElements / 100) * MaxLoadFactor100; - } - - ROBIN_HOOD(NODISCARD) size_t calcNumBytesInfo(size_t numElements) const noexcept { - // we add a uint64_t, which houses the sentinel (first byte) and padding so we can load - // 64bit types. - return numElements + sizeof(uint64_t); - } - - ROBIN_HOOD(NODISCARD) - size_t calcNumElementsWithBuffer(size_t numElements) const noexcept { - auto maxNumElementsAllowed = calcMaxNumElementsAllowed(numElements); - return numElements + (std::min)(maxNumElementsAllowed, (static_cast(0xFF))); - } - - // calculation only allowed for 2^n values - ROBIN_HOOD(NODISCARD) size_t calcNumBytesTotal(size_t numElements) const { -#if ROBIN_HOOD(BITNESS) == 64 - return numElements * sizeof(Node) + calcNumBytesInfo(numElements); -#else - // make sure we're doing 64bit operations, so we are at least safe against 32bit overflows. - auto const ne = static_cast(numElements); - auto const s = static_cast(sizeof(Node)); - auto const infos = static_cast(calcNumBytesInfo(numElements)); - - auto const total64 = ne * s + infos; - auto const total = static_cast(total64); - - if (ROBIN_HOOD_UNLIKELY(static_cast(total) != total64)) { - throwOverflowError(); - } - return total; -#endif - } - -private: - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::value, bool>::type has(const value_type& e) const { - ROBIN_HOOD_TRACE(this) - auto it = find(e.first); - return it != end() && it->second == e.second; - } - - template - ROBIN_HOOD(NODISCARD) - typename std::enable_if::value, bool>::type has(const value_type& e) const { - ROBIN_HOOD_TRACE(this) - return find(e) != end(); - } - - void reserve(size_t c, bool forceRehash) { - ROBIN_HOOD_TRACE(this) - auto const minElementsAllowed = (std::max)(c, mNumElements); - auto newSize = InitialNumElements; - while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) { - newSize *= 2; - } - if (ROBIN_HOOD_UNLIKELY(newSize == 0)) { - throwOverflowError(); - } - - ROBIN_HOOD_LOG("newSize > mMask + 1: " << newSize << " > " << mMask << " + 1") - - // only actually do anything when the new size is bigger than the old one. This prevents to - // continuously allocate for each reserve() call. - if (forceRehash || newSize > mMask + 1) { - rehashPowerOfTwo(newSize, false); - } - } - - // reserves space for at least the specified number of elements. - // only works if numBuckets if power of two - // True on success, false otherwise - void rehashPowerOfTwo(size_t numBuckets, bool forceFree) { - ROBIN_HOOD_TRACE(this) - - Node* const oldKeyVals = mKeyVals; - uint8_t const* const oldInfo = mInfo; - - const size_t oldMaxElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); - - // resize operation: move stuff - initData(numBuckets); - if (oldMaxElementsWithBuffer > 1) { - for (size_t i = 0; i < oldMaxElementsWithBuffer; ++i) { - if (oldInfo[i] != 0) { - // might throw an exception, which is really bad since we are in the middle of - // moving stuff. - insert_move(std::move(oldKeyVals[i])); - // destroy the node but DON'T destroy the data. - oldKeyVals[i].~Node(); - } - } - - // this check is not necessary as it's guarded by the previous if, but it helps - // silence g++'s overeager "attempt to free a non-heap object 'map' - // [-Werror=free-nonheap-object]" warning. - if (oldKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { - // don't destroy old data: put it into the pool instead - if (forceFree) { - std::free(oldKeyVals); - } else { - DataPool::addOrFree(oldKeyVals, calcNumBytesTotal(oldMaxElementsWithBuffer)); - } - } - } - } - - ROBIN_HOOD(NOINLINE) void throwOverflowError() const { -#if ROBIN_HOOD(HAS_EXCEPTIONS) - throw std::overflow_error("robin_hood::map overflow"); -#else - abort(); -#endif - } - - template - std::pair try_emplace_impl(OtherKey&& key, Args&&... args) { - ROBIN_HOOD_TRACE(this) - auto idxAndState = insertKeyPrepareEmptySpot(key); - switch (idxAndState.second) { - case InsertionState::key_found: - break; - - case InsertionState::new_node: - ::new (static_cast(&mKeyVals[idxAndState.first])) Node( - *this, std::piecewise_construct, std::forward_as_tuple(std::forward(key)), - std::forward_as_tuple(std::forward(args)...)); - break; - - case InsertionState::overwrite_node: - mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct, - std::forward_as_tuple(std::forward(key)), - std::forward_as_tuple(std::forward(args)...)); - break; - - case InsertionState::overflow_error: - throwOverflowError(); - break; - } - - return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first), - InsertionState::key_found != idxAndState.second); - } - - template - std::pair insertOrAssignImpl(OtherKey&& key, Mapped&& obj) { - ROBIN_HOOD_TRACE(this) - auto idxAndState = insertKeyPrepareEmptySpot(key); - switch (idxAndState.second) { - case InsertionState::key_found: - mKeyVals[idxAndState.first].getSecond() = std::forward(obj); - break; - - case InsertionState::new_node: - ::new (static_cast(&mKeyVals[idxAndState.first])) Node( - *this, std::piecewise_construct, std::forward_as_tuple(std::forward(key)), - std::forward_as_tuple(std::forward(obj))); - break; - - case InsertionState::overwrite_node: - mKeyVals[idxAndState.first] = Node(*this, std::piecewise_construct, - std::forward_as_tuple(std::forward(key)), - std::forward_as_tuple(std::forward(obj))); - break; - - case InsertionState::overflow_error: - throwOverflowError(); - break; - } - - return std::make_pair(iterator(mKeyVals + idxAndState.first, mInfo + idxAndState.first), - InsertionState::key_found != idxAndState.second); - } - - void initData(size_t max_elements) { - mNumElements = 0; - mMask = max_elements - 1; - mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements); - - auto const numElementsWithBuffer = calcNumElementsWithBuffer(max_elements); - - // malloc & zero mInfo. Faster than calloc everything. - auto const numBytesTotal = calcNumBytesTotal(numElementsWithBuffer); - ROBIN_HOOD_LOG("std::calloc " << numBytesTotal << " = calcNumBytesTotal(" - << numElementsWithBuffer << ")") - mKeyVals = reinterpret_cast( - detail::assertNotNull(std::malloc(numBytesTotal))); - mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); - std::memset(mInfo, 0, numBytesTotal - numElementsWithBuffer * sizeof(Node)); - - // set sentinel - mInfo[numElementsWithBuffer] = 1; - - mInfoInc = InitialInfoInc; - mInfoHashShift = InitialInfoHashShift; - } - - enum class InsertionState { overflow_error, key_found, new_node, overwrite_node }; - - // Finds key, and if not already present prepares a spot where to pot the key & value. - // This potentially shifts nodes out of the way, updates mInfo and number of inserted - // elements, so the only operation left to do is create/assign a new node at that spot. - template - std::pair insertKeyPrepareEmptySpot(OtherKey&& key) { - for (int i = 0; i < 256; ++i) { - size_t idx{}; - InfoType info{}; - keyToIdx(key, &idx, &info); - nextWhileLess(&info, &idx); - - // while we potentially have a match - while (info == mInfo[idx]) { - if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { - // key already exists, do NOT insert. - // see http://en.cppreference.com/w/cpp/container/unordered_map/insert - return std::make_pair(idx, InsertionState::key_found); - } - next(&info, &idx); - } - - // unlikely that this evaluates to true - if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) { - if (!increase_size()) { - return std::make_pair(size_t(0), InsertionState::overflow_error); - } - continue; - } - - // key not found, so we are now exactly where we want to insert it. - auto const insertion_idx = idx; - auto const insertion_info = info; - if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { - mMaxNumElementsAllowed = 0; - } - - // find an empty spot - while (0 != mInfo[idx]) { - next(&info, &idx); - } - - if (idx != insertion_idx) { - shiftUp(idx, insertion_idx); - } - // put at empty spot - mInfo[insertion_idx] = static_cast(insertion_info); - ++mNumElements; - return std::make_pair(insertion_idx, idx == insertion_idx - ? InsertionState::new_node - : InsertionState::overwrite_node); - } - - // enough attempts failed, so finally give up. - return std::make_pair(size_t(0), InsertionState::overflow_error); - } - - bool try_increase_info() { - ROBIN_HOOD_LOG("mInfoInc=" << mInfoInc << ", numElements=" << mNumElements - << ", maxNumElementsAllowed=" - << calcMaxNumElementsAllowed(mMask + 1)) - if (mInfoInc <= 2) { - // need to be > 2 so that shift works (otherwise undefined behavior!) - return false; - } - // we got space left, try to make info smaller - mInfoInc = static_cast(mInfoInc >> 1U); - - // remove one bit of the hash, leaving more space for the distance info. - // This is extremely fast because we can operate on 8 bytes at once. - ++mInfoHashShift; - auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); - - for (size_t i = 0; i < numElementsWithBuffer; i += 8) { - auto val = unaligned_load(mInfo + i); - val = (val >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f); - std::memcpy(mInfo + i, &val, sizeof(val)); - } - // update sentinel, which might have been cleared out! - mInfo[numElementsWithBuffer] = 1; - - mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); - return true; - } - - // True if resize was possible, false otherwise - bool increase_size() { - // nothing allocated yet? just allocate InitialNumElements - if (0 == mMask) { - initData(InitialNumElements); - return true; - } - - auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); - if (mNumElements < maxNumElementsAllowed && try_increase_info()) { - return true; - } - - ROBIN_HOOD_LOG("mNumElements=" << mNumElements << ", maxNumElementsAllowed=" - << maxNumElementsAllowed << ", load=" - << (static_cast(mNumElements) * 100.0 / - (static_cast(mMask) + 1))) - - if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) { - // we have to resize, even though there would still be plenty of space left! - // Try to rehash instead. Delete freed memory so we don't steadyily increase mem in case - // we have to rehash a few times - nextHashMultiplier(); - rehashPowerOfTwo(mMask + 1, true); - } else { - // we've reached the capacity of the map, so the hash seems to work nice. Keep using it. - rehashPowerOfTwo((mMask + 1) * 2, false); - } - return true; - } - - void nextHashMultiplier() { - // adding an *even* number, so that the multiplier will always stay odd. This is necessary - // so that the hash stays a mixing function (and thus doesn't have any information loss). - mHashMultiplier += UINT64_C(0xc4ceb9fe1a85ec54); - } - - void destroy() { - if (0 == mMask) { - // don't deallocate! - return; - } - - Destroyer::value>{} - .nodesDoNotDeallocate(*this); - - // This protection against not deleting mMask shouldn't be needed as it's sufficiently - // protected with the 0==mMask check, but I have this anyways because g++ 7 otherwise - // reports a compile error: attempt to free a non-heap object 'fm' - // [-Werror=free-nonheap-object] - if (mKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { - ROBIN_HOOD_LOG("std::free") - std::free(mKeyVals); - } - } - - void init() noexcept { - mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); - mInfo = reinterpret_cast(&mMask); - mNumElements = 0; - mMask = 0; - mMaxNumElementsAllowed = 0; - mInfoInc = InitialInfoInc; - mInfoHashShift = InitialInfoHashShift; - } - - // members are sorted so no padding occurs - uint64_t mHashMultiplier = UINT64_C(0xc4ceb9fe1a85ec53); // 8 byte 8 - Node* mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); // 8 byte 16 - uint8_t* mInfo = reinterpret_cast(&mMask); // 8 byte 24 - size_t mNumElements = 0; // 8 byte 32 - size_t mMask = 0; // 8 byte 40 - size_t mMaxNumElementsAllowed = 0; // 8 byte 48 - InfoType mInfoInc = InitialInfoInc; // 4 byte 52 - InfoType mInfoHashShift = InitialInfoHashShift; // 4 byte 56 - // 16 byte 56 if NodeAllocator -}; - -} // namespace detail - -// map - -template , - typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> -using unordered_flat_map = detail::Table; - -template , - typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> -using unordered_node_map = detail::Table; - -template , - typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> -using unordered_map = - detail::Table) <= sizeof(size_t) * 6 && - std::is_nothrow_move_constructible>::value && - std::is_nothrow_move_assignable>::value, - MaxLoadFactor100, Key, T, Hash, KeyEqual>; - -// set - -template , typename KeyEqual = std::equal_to, - size_t MaxLoadFactor100 = 80> -using unordered_flat_set = detail::Table; - -template , typename KeyEqual = std::equal_to, - size_t MaxLoadFactor100 = 80> -using unordered_node_set = detail::Table; - -template , typename KeyEqual = std::equal_to, - size_t MaxLoadFactor100 = 80> -using unordered_set = detail::Table::value && - std::is_nothrow_move_assignable::value, - MaxLoadFactor100, Key, void, Hash, KeyEqual>; - -} // namespace robin_hood - -#endif diff --git a/benchmarks/external/tsl/robin_hash.h b/benchmarks/external/tsl/robin_hash.h index f9fb9e76..89c7c96f 100644 --- a/benchmarks/external/tsl/robin_hash.h +++ b/benchmarks/external/tsl/robin_hash.h @@ -1589,6 +1589,7 @@ class robin_hash : private Hash, private KeyEqual, private GrowthPolicy { */ bucket_entry* static_empty_bucket_ptr() noexcept { static bucket_entry empty_bucket(true); + tsl_rh_assert(empty_bucket.empty()); return &empty_bucket; } diff --git a/benchmarks/external/update.sh b/benchmarks/external/update.sh index c0169fab..00b587cb 100644 --- a/benchmarks/external/update.sh +++ b/benchmarks/external/update.sh @@ -1,35 +1,32 @@ tsl_h="https://raw.github.com/Tessil/hopscotch-map/master/include/tsl/" tsl_r="https://raw.github.com/Tessil/robin-map/master/include/tsl/" -tsl_s="https://raw.github.com/Tessil/sparse-map/master/include/tsl/" -greg="https://raw.github.com/greg7mdp/sparsepp/master/sparsepp/" -martinus="https://raw.github.com/martinus/robin-hood-hashing/master/src/include/" +smap="https://raw.github.com/greg7mdp/sparsepp/master/sparsepp/" +pmap="https://raw.github.com/greg7mdp/parallel-hashmap/" +martinus_r="https://raw.github.com/martinus/robin-hood-hashing/master/src/include/" +martinus_d="https://raw.github.com/martinus/unordered_dense/master/include/ankerl/" skarupke="https://raw.github.com/skarupke/flat_hash_map/master/" -mkdir -p tsl sparsepp skarupke +mkdir -p ankerl skarupke sparsepp tsl -wget $martinus"robin_hood.h" -O "robin_hood.h" +wget $martinus_r"robin_hood.h" -O "ankerl/robin_hood.h" +wget $martinus_d"unordered_dense.h" -O "ankerl/unordered_dense.h" -wget $skarupke"bytell_hash_map.hpp" -O "skarupke/bytell_hash_map.hpp" +#wget $skarupke"bytell_hash_map.hpp" -O "skarupke/bytell_hash_map.hpp" wget $skarupke"flat_hash_map.hpp" -O "skarupke/flat_hash_map.hpp" -wget $greg"spp.h" -O "sparsepp/spp.h" -wget $greg"spp_config.h" -O "sparsepp/spp_config.h" -wget $greg"spp_dlalloc.h" -O "sparsepp/spp_dlalloc.h" -wget $greg"spp_memory.h" -O "sparsepp/spp_memory.h" -wget $greg"spp_smartptr.h" -O "sparsepp/spp_smartptr.h" -wget $greg"spp_stdint.h" -O "sparsepp/spp_stdint.h" -wget $greg"spp_timer.h" -O "sparsepp/spp_timer.h" -wget $greg"spp_traits.h" -O "sparsepp/spp_traits.h" -wget $greg"spp_utils.h" -O "sparsepp/spp_utils.h" - -wget $tsl_h"hopscotch_growth_policy.h" -O "tsl/hopscotch_growth_policy.h" -wget $tsl_h"hopscotch_hash.h" -O "tsl/hopscotch_hash.h" -wget $tsl_h"hopscotch_map.h" -O "tsl/hopscotch_map.h" +#wget $smap"spp.h" -O "sparsepp/spp.h" +#wget $smap"spp_config.h" -O "sparsepp/spp_config.h" +#wget $smap"spp_dlalloc.h" -O "sparsepp/spp_dlalloc.h" +#wget $smap"spp_memory.h" -O "sparsepp/spp_memory.h" +#wget $smap"spp_smartptr.h" -O "sparsepp/spp_smartptr.h" +#wget $smap"spp_stdint.h" -O "sparsepp/spp_stdint.h" +#wget $smap"spp_timer.h" -O "sparsepp/spp_timer.h" +#wget $smap"spp_traits.h" -O "sparsepp/spp_traits.h" +#wget $smap"spp_utils.h" -O "sparsepp/spp_utils.h" +#wget $tsl_h"hopscotch_growth_policy.h" -O "tsl/hopscotch_growth_policy.h" +#wget $tsl_h"hopscotch_hash.h" -O "tsl/hopscotch_hash.h" +#wget $tsl_h"hopscotch_map.h" -O "tsl/hopscotch_map.h" wget $tsl_r"robin_growth_policy.h" -O "tsl/robin_growth_policy.h" wget $tsl_r"robin_hash.h" -O "tsl/robin_hash.h" wget $tsl_r"robin_map.h" -O "tsl/robin_map.h" - -#wget $tsl_s"sparse_growth_policy.h" -O "tsl/sparse_growth_policy.h" -#wget $tsl_s"sparse_hash.h" -O "tsl/sparse_hash.h" -#wget $tsl_s"sparse_map.h" -O "tsl/sparse_map.h" diff --git a/benchmarks/misc/rust_cmap.c b/benchmarks/misc/rust_cmap.c index 1e763bde..933910cb 100644 --- a/benchmarks/misc/rust_cmap.c +++ b/benchmarks/misc/rust_cmap.c @@ -37,7 +37,7 @@ int main() uint64_t key = romu_trio(rng) & mask; cmap_u64_insert(&m, key, 0).ref->second += 1; } - printf("insert : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(m)); + printf("insert : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(&m)); now = clock(); sum = 0; @@ -55,7 +55,7 @@ int main() uint64_t key = romu_trio(rng2) & mask; cmap_u64_erase(&m, key); } - printf("remove : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(m)); + printf("remove : %zums \tsize : %" PRIuMAX "\n", (clock() - now)/ms, cmap_u64_size(&m)); printf("press a key:\n"); getchar(); } -} \ No newline at end of file +} diff --git a/benchmarks/misc/string_bench_STC.cpp b/benchmarks/misc/string_bench_STC.cpp index 2e05dae3..9fc861ea 100644 --- a/benchmarks/misc/string_bench_STC.cpp +++ b/benchmarks/misc/string_bench_STC.cpp @@ -68,10 +68,10 @@ private: void initShortStringVec(cvec_str* vs, cvec_sv* vsv) { - cvec_str_clear(vs); + cvec_str_drop(vs); cvec_sv_clear(vsv); - cvec_str_copy(vs, read_file("names.txt")); + *vs = read_file("names.txt"); /* cvec_str_emplace_back(vs, "Susan"); cvec_str_emplace_back(vs, "Jason"); @@ -103,16 +103,16 @@ void initShortStringVec(cvec_str* vs, cvec_sv* vsv) cvec_sv_push_back(vsv, csview_from_s(i.ref)); num += cstr_size(*i.ref); } - std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl; - std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl; + std::cout << "num strings: " << cvec_sv_size(vsv) << std::endl; + std::cout << "avg str len: " << num / (float)cvec_sv_size(vsv) << std::endl; } void initLongStringVec(cvec_str* vs, cvec_sv* vsv) { - cvec_str_clear(vs); + cvec_str_drop(vs); cvec_sv_clear(vsv); - cvec_str_copy(vs, read_file("names.txt")); + *vs = read_file("names.txt"); c_foreach (i, cvec_str, *vs) { cstr_append_s(i.ref, *i.ref); cstr_append_s(i.ref, *i.ref); @@ -149,8 +149,8 @@ void initLongStringVec(cvec_str* vs, cvec_sv* vsv) cvec_sv_push_back(vsv, csview_from_s(i.ref)); num += cstr_size(*i.ref); } - std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl; - std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl; + std::cout << "num strings: " << cvec_sv_size(vsv) << std::endl; + std::cout << "avg str len: " << num / (float)cvec_sv_size(vsv) << std::endl; } void initMaps(const cvec_str* vs, csmap_str* mapTrans, csmap_ssv* mapSview, diff --git a/benchmarks/picobench/picobench_cmap.cpp b/benchmarks/picobench/picobench_cmap.cpp index 4a330019..f4551aa1 100644 --- a/benchmarks/picobench/picobench_cmap.cpp +++ b/benchmarks/picobench/picobench_cmap.cpp @@ -6,10 +6,9 @@ #include #include #include -#include "../external/robin_hood.h" -#include "../external/skarupke/bytell_hash_map.hpp" -#include "../external/tsl/hopscotch_map.h" -#include "../external/parallel_hashmap/phmap.h" +#include "../external/ankerl/unordered_dense.h" +#include "../external/skarupke/flat_hash_map.hpp" +#include "../external/tsl/robin_map.h" #define PICOBENCH_IMPLEMENT_WITH_MAIN #include "picobench.hpp" @@ -18,20 +17,14 @@ enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80}; uint64_t seed = time(NULL); template using umap = std::unordered_map; -template using bmap = ska::bytell_hash_map; template using fmap = ska::flat_hash_map; -template using hmap = tsl::hopscotch_map; -template using pmap = phmap::flat_hash_map; -template using rmap = robin_hood::unordered_flat_map, std::equal_to, MaxLoadFactor100>; +template using tmap = tsl::robin_map; +template using dmap = ankerl::unordered_dense::map; #define DEFMAP(map, ...) \ using u##map = umap __VA_ARGS__; \ - using b##map = bmap __VA_ARGS__; \ using f##map = fmap __VA_ARGS__; \ - using h##map = hmap __VA_ARGS__; \ - using p##map = pmap __VA_ARGS__; \ - using r##map = rmap __VA_ARGS__ - + using t##map = tmap __VA_ARGS__; \ + using d##map = dmap __VA_ARGS__ DEFMAP(map_i, ); DEFMAP(map_x, ); @@ -90,7 +83,7 @@ static void ins_and_erase_cmap_i(picobench::state& s) csrandom(seed); c_forrange (s.iterations()) cmap_i_erase(&map, crandom()); - s.set_result(cmap_i_size(map)); + s.set_result(cmap_i_size(&map)); cmap_i_drop(&map); } @@ -110,17 +103,15 @@ static void ins_and_erase_cmap_x(picobench::state& s) csrandom(seed); c_forrange (s.iterations()) cmap_x_erase(&map, crandom()); - s.set_result(cmap_x_size(map)); + s.set_result(cmap_x_size(&map)); cmap_x_drop(&map); } #define P samples(S1).iterations({N1/4}) PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; -PICOBENCH(ins_and_erase_i).P; +PICOBENCH(ins_and_erase_i).P; PICOBENCH(ins_and_erase_cmap_x).P; #undef P @@ -158,11 +149,9 @@ static void ins_and_access_cmap_i(picobench::state& s) #define P samples(S1).iterations({N1, N1, N1, N1}).args({18, 23, 25, 31}) PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; -PICOBENCH(ins_and_access_i).P; +PICOBENCH(ins_and_access_i).P; PICOBENCH(ins_and_access_cmap_i).P; #undef P @@ -213,18 +202,16 @@ static void ins_and_access_cmap_s(picobench::state& s) randomize(buf, s.arg()); result += cmap_str_erase(&map, buf); } - s.set_result(result + cmap_str_size(map)); + s.set_result(result + cmap_str_size(&map)); cstr_drop(&str); cmap_str_drop(&map); } #define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000}) PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; -PICOBENCH(ins_and_access_s).P; +PICOBENCH(ins_and_access_s).P; PICOBENCH(ins_and_access_cmap_s).P; #undef P @@ -293,10 +280,8 @@ static void iterate_cmap_x(picobench::state& s) #define P samples(S1).iterations({N1/20}).args({12}) PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; -PICOBENCH(iterate_x).P; +PICOBENCH(iterate_x).P; PICOBENCH(iterate_cmap_x).P; #undef P diff --git a/benchmarks/picobench/picobench_csmap.cpp b/benchmarks/picobench/picobench_csmap.cpp index ea2174fa..312b38c5 100644 --- a/benchmarks/picobench/picobench_csmap.cpp +++ b/benchmarks/picobench/picobench_csmap.cpp @@ -53,7 +53,7 @@ static void ctor_and_ins_one_csmap_i(picobench::state& s) c_forrange (n, s.iterations()) { csmap_i map = csmap_i_init(); csmap_i_insert(&map, n, 0); - result += csmap_i_size(map); + result += csmap_i_size(&map); csmap_i_drop(&map); } s.set_result(result); @@ -87,7 +87,7 @@ static void insert_csmap_i(picobench::state& s) picobench::scope scope(s); c_forrange (n, s.iterations()) csmap_i_insert(&map, crandom() & 0xfffffff, n); - s.set_result(csmap_i_size(map)); + s.set_result(csmap_i_size(&map)); csmap_i_drop(&map); } @@ -133,7 +133,7 @@ static void ins_and_erase_csmap_i(picobench::state& s) picobench::scope scope(s); c_forrange (i, s.iterations()) csmap_i_insert(&map, crandom() & mask, i); - result = csmap_i_size(map); + result = csmap_i_size(&map); csmap_i_clear(&map); csrandom(seed); @@ -184,7 +184,7 @@ static void ins_and_access_csmap_i(picobench::state& s) const csmap_i_value* val = csmap_i_get(&map, crandom() & mask); if (val) csmap_i_erase(&map, val->first); } - s.set_result(result + csmap_i_size(map)); + s.set_result(result + csmap_i_size(&map)); csmap_i_drop(&map); } @@ -245,7 +245,7 @@ static void ins_and_access_csmap_s(picobench::state& s) csmap_str_erase(&map, cstr_str(&it.ref->first)); }*/ } - s.set_result(result + csmap_str_size(map)); + s.set_result(result + csmap_str_size(&map)); cstr_drop(&str); csmap_str_drop(&map); } diff --git a/benchmarks/plotbench/cdeq_benchmark.cpp b/benchmarks/plotbench/cdeq_benchmark.cpp index d938450a..72884e78 100644 --- a/benchmarks/plotbench/cdeq_benchmark.cpp +++ b/benchmarks/plotbench/cdeq_benchmark.cpp @@ -77,11 +77,11 @@ Sample test_stc_deque() { c_forrange (N/3) {cdeq_x_push_back(&con, crandom() & mask1); cdeq_x_pop_front(&con);} c_forrange (N/3) cdeq_x_push_back(&con, crandom() & mask1); s.test[INSERT].t2 = clock(); - s.test[INSERT].sum = cdeq_x_size(con); + s.test[INSERT].sum = cdeq_x_size(&con); s.test[ERASE].t1 = clock(); - c_forrange (cdeq_x_size(con)/2) { cdeq_x_pop_front(&con); cdeq_x_pop_back(&con); } + c_forrange (cdeq_x_size(&con)/2) { cdeq_x_pop_front(&con); cdeq_x_pop_back(&con); } s.test[ERASE].t2 = clock(); - s.test[ERASE].sum = cdeq_x_size(con); + s.test[ERASE].sum = cdeq_x_size(&con); cdeq_x_drop(&con); }{ csrandom(seed); diff --git a/benchmarks/plotbench/cmap_benchmark.cpp b/benchmarks/plotbench/cmap_benchmark.cpp index 781ad720..4304db52 100644 --- a/benchmarks/plotbench/cmap_benchmark.cpp +++ b/benchmarks/plotbench/cmap_benchmark.cpp @@ -76,12 +76,12 @@ Sample test_stc_unordered_map() { c_forrange (i, N/2) cmap_x_insert(&con, crandom() & mask1, i); c_forrange (i, N/2) cmap_x_insert(&con, i, i); s.test[INSERT].t2 = clock(); - s.test[INSERT].sum = cmap_x_size(con); + s.test[INSERT].sum = cmap_x_size(&con); csrandom(seed); s.test[ERASE].t1 = clock(); c_forrange (N) cmap_x_erase(&con, crandom() & mask1); s.test[ERASE].t2 = clock(); - s.test[ERASE].sum = cmap_x_size(con); + s.test[ERASE].sum = cmap_x_size(&con); cmap_x_drop(&con); }{ container con = cmap_x_init(); diff --git a/benchmarks/plotbench/csmap_benchmark.cpp b/benchmarks/plotbench/csmap_benchmark.cpp index 3fb8a0a4..b319006f 100644 --- a/benchmarks/plotbench/csmap_benchmark.cpp +++ b/benchmarks/plotbench/csmap_benchmark.cpp @@ -77,12 +77,12 @@ Sample test_stc_map() { c_forrange (i, N/2) csmap_x_insert(&con, crandom() & mask1, i); c_forrange (i, N/2) csmap_x_insert(&con, i, i); s.test[INSERT].t2 = clock(); - s.test[INSERT].sum = csmap_x_size(con); + s.test[INSERT].sum = csmap_x_size(&con); csrandom(seed); s.test[ERASE].t1 = clock(); c_forrange (N) csmap_x_erase(&con, crandom() & mask1); s.test[ERASE].t2 = clock(); - s.test[ERASE].sum = csmap_x_size(con); + s.test[ERASE].sum = csmap_x_size(&con); csmap_x_drop(&con); }{ container con = csmap_x_init(); diff --git a/benchmarks/plotbench/cvec_benchmark.cpp b/benchmarks/plotbench/cvec_benchmark.cpp index 9ba95f31..44dcee2f 100644 --- a/benchmarks/plotbench/cvec_benchmark.cpp +++ b/benchmarks/plotbench/cvec_benchmark.cpp @@ -73,11 +73,11 @@ Sample test_stc_vector() { csrandom(seed); c_forrange (N) cvec_x_push_back(&con, crandom() & mask1); s.test[INSERT].t2 = clock(); - s.test[INSERT].sum = cvec_x_size(con); + s.test[INSERT].sum = cvec_x_size(&con); s.test[ERASE].t1 = clock(); c_forrange (N) { cvec_x_pop_back(&con); } s.test[ERASE].t2 = clock(); - s.test[ERASE].sum = cvec_x_size(con); + s.test[ERASE].sum = cvec_x_size(&con); cvec_x_drop(&con); }{ csrandom(seed); diff --git a/benchmarks/shootout_hashmaps.cpp b/benchmarks/shootout_hashmaps.cpp index 0cf29ab7..9f5315c0 100644 --- a/benchmarks/shootout_hashmaps.cpp +++ b/benchmarks/shootout_hashmaps.cpp @@ -5,47 +5,47 @@ #include #include "external/khash.h" -enum {max_load_factor = 77}; +#define MAX_LOAD_FACTOR 77 #ifdef __cplusplus #include #include -#include "external/robin_hood.h" -#include "external/skarupke/bytell_hash_map.hpp" -#include "external/parallel_hashmap/phmap.h" -#include "external/tsl/hopscotch_map.h" +#include "external/ankerl/robin_hood.h" +#include "external/ankerl/unordered_dense.h" +#include "external/skarupke/flat_hash_map.hpp" +//#include "external/skarupke/bytell_hash_map.hpp" +//#include "external/parallel_hashmap/phmap.h" +//#include "external/tsl/hopscotch_map.h" #include "external/tsl/robin_map.h" template inline void std_destroy(C& c) { C().swap(c); } template using robin_hood_flat_map = robin_hood::unordered_flat_map< - K, V, robin_hood::hash, std::equal_to, max_load_factor>; + K, V, robin_hood::hash, std::equal_to, MAX_LOAD_FACTOR>; #endif +// khash template expansion KHASH_MAP_INIT_INT64(ii, int64_t) -// cmap and khash template expansion +// cmap template expansion #define i_key int64_t #define i_val int64_t #define i_tag ii #include -stc64_t rng; -size_t seed; -#define SEED(s) rng = stc64_new(seed) +#define SEED(s) rng = stc64_new(s) #define RAND(N) (stc64_rand(&rng) & (((uint64_t)1 << N) - 1)) - #define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \ - ; cmap_##X##_max_load_factor(&map, max_load_factor/100.0f) + ; cmap_##X##_max_load_factor(&map, MAX_LOAD_FACTOR/100.0f) #define CMAP_PUT(X, key, val) cmap_##X##_insert_or_assign(&map, key, val).ref->second #define CMAP_EMPLACE(X, key, val) cmap_##X##_insert(&map, key, val).ref->second #define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key) #define CMAP_FIND(X, key) cmap_##X##_contains(&map, key) #define CMAP_FOR(X, i) c_foreach (i, cmap_##X, map) #define CMAP_ITEM(X, i) i.ref->second -#define CMAP_SIZE(X) cmap_##X##_size(map) -#define CMAP_BUCKETS(X) cmap_##X##_bucket_count(map) +#define CMAP_SIZE(X) cmap_##X##_size(&map) +#define CMAP_BUCKETS(X) cmap_##X##_bucket_count(&map) #define CMAP_CLEAR(X) cmap_##X##_clear(&map) #define CMAP_DTOR(X) cmap_##X##_drop(&map) @@ -61,7 +61,7 @@ size_t seed; #define KMAP_CLEAR(X) kh_clear(X, map) #define KMAP_DTOR(X) kh_destroy(X, map) -#define UMAP_SETUP(X, Key, Value) std::unordered_map map; map.max_load_factor(max_load_factor/100.0f) +#define UMAP_SETUP(X, Key, Value) std::unordered_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define UMAP_PUT(X, key, val) (map[key] = val) #define UMAP_EMPLACE(X, key, val) map.emplace(key, val).first->second #define UMAP_FIND(X, key) int(map.find(key) != map.end()) @@ -73,7 +73,7 @@ size_t seed; #define UMAP_CLEAR(X) map.clear() #define UMAP_DTOR(X) std_destroy(map) -#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map map; map.max_load_factor(max_load_factor/100.0f) +#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define FMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define FMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) #define FMAP_FIND(X, key) UMAP_FIND(X, key) @@ -85,7 +85,7 @@ size_t seed; #define FMAP_CLEAR(X) UMAP_CLEAR(X) #define FMAP_DTOR(X) UMAP_DTOR(X) -#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map map; map.max_load_factor(max_load_factor/100.0f) +#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define HMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define HMAP_EMPLACE(X, key, val) map.emplace(key, val).first.value() #define HMAP_FIND(X, key) UMAP_FIND(X, key) @@ -97,7 +97,7 @@ size_t seed; #define HMAP_CLEAR(X) UMAP_CLEAR(X) #define HMAP_DTOR(X) UMAP_DTOR(X) -#define TMAP_SETUP(X, Key, Value) tsl::robin_map map; map.max_load_factor(max_load_factor/100.0f) +#define TMAP_SETUP(X, Key, Value) tsl::robin_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define TMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define TMAP_EMPLACE(X, key, val) map.emplace(key, val).first.value() #define TMAP_FIND(X, key) UMAP_FIND(X, key) @@ -122,7 +122,19 @@ size_t seed; #define RMAP_CLEAR(X) UMAP_CLEAR(X) #define RMAP_DTOR(X) UMAP_DTOR(X) -#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map map; map.max_load_factor(max_load_factor/100.0f) +#define DMAP_SETUP(X, Key, Value) ankerl::unordered_dense::map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) +#define DMAP_PUT(X, key, val) UMAP_PUT(X, key, val) +#define DMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) +#define DMAP_FIND(X, key) UMAP_FIND(X, key) +#define DMAP_ERASE(X, key) UMAP_ERASE(X, key) +#define DMAP_FOR(X, i) UMAP_FOR(X, i) +#define DMAP_ITEM(X, i) UMAP_ITEM(X, i) +#define DMAP_SIZE(X) UMAP_SIZE(X) +#define DMAP_BUCKETS(X) UMAP_BUCKETS(X) +#define DMAP_CLEAR(X) UMAP_CLEAR(X) +#define DMAP_DTOR(X) UMAP_DTOR(X) + +#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map map; map.max_load_factor(MAX_LOAD_FACTOR/100.0f) #define PMAP_PUT(X, key, val) UMAP_PUT(X, key, val) #define PMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val) #define PMAP_FIND(X, key) UMAP_FIND(X, key) @@ -191,7 +203,7 @@ size_t seed; SEED(seed); \ for (size_t i = 0; i < m; ++i) \ M##_PUT(X, RAND(keybits), i); \ - size_t x = 200000000/M##_SIZE(X); \ + size_t x = 100000000/M##_SIZE(X); \ clock_t difference, before = clock(); \ for (size_t k=0; k < x; k++) M##_FOR (X, it) \ sum += M##_ITEM(X, it); \ @@ -211,7 +223,7 @@ size_t seed; for (size_t i = 0; i < m; ++i) \ M##_PUT(X, RAND(keybits), i); \ before = clock(); \ - size_t x = m * 10000000/M##_SIZE(X); \ + size_t x = m * 8000000/M##_SIZE(X); \ for (size_t i = 0; i < x; ++i) \ found += M##_FIND(X, RAND(keybits)); \ SEED(seed); \ @@ -226,16 +238,16 @@ size_t seed; #ifdef __cplusplus #define RUN_TEST(n) MAP_TEST##n(KMAP, ii, N##n) MAP_TEST##n(CMAP, ii, N##n) \ - MAP_TEST##n(PMAP, ii, N##n) MAP_TEST##n(FMAP, ii, N##n) \ - MAP_TEST##n(RMAP, ii, N##n) MAP_TEST##n(HMAP, ii, N##n) \ - MAP_TEST##n(TMAP, ii, N##n) MAP_TEST##n(UMAP, ii, N##n) + MAP_TEST##n(FMAP, ii, N##n) MAP_TEST##n(TMAP, ii, N##n) \ + MAP_TEST##n(RMAP, ii, N##n) MAP_TEST##n(DMAP, ii, N##n) \ + MAP_TEST##n(UMAP, ii, N##n) #else #define RUN_TEST(n) MAP_TEST##n(KMAP, ii, N##n) MAP_TEST##n(CMAP, ii, N##n) #endif enum { - DEFAULT_N_MILL = 40, - DEFAULT_KEYBITS = 25, + DEFAULT_N_MILL = 10, + DEFAULT_KEYBITS = 22, }; int main(int argc, char* argv[]) @@ -244,16 +256,18 @@ int main(int argc, char* argv[]) unsigned keybits = argc >= 3 ? atoi(argv[2]) : DEFAULT_KEYBITS; unsigned n = n_mill * 1000000; unsigned N0 = n, N1 = n/2, N2 = n/2, N3 = n, N4 = n, N5 = n; - seed = time(NULL); // 1636306010; + stc64_t rng; + size_t seed = time(NULL); printf("\nUnordered hash map shootout\n"); - printf("CMAP = https://github.com/tylov/STC\n" - "KMAP = https://github.com/attractivechaos/klib\n" - "PMAP = https://github.com/greg7mdp/parallel-hashmap\n" + printf("KMAP = https://github.com/attractivechaos/klib\n" + "CMAP = https://github.com/tylov/STC (**)\n" + //"PMAP = https://github.com/greg7mdp/parallel-hashmap\n" "FMAP = https://github.com/skarupke/flat_hash_map\n" - "RMAP = https://github.com/martinus/robin-hood-hashing\n" - "HMAP = https://github.com/Tessil/hopscotch-map\n" "TMAP = https://github.com/Tessil/robin-map\n" + //"HMAP = https://github.com/Tessil/hopscotch-map\n" + "RMAP = https://github.com/martinus/robin-hood-hashing\n" + "DMAP = https://github.com/martinus/unordered_dense\n" "UMAP = std::unordered_map\n\n"); printf("Usage %s [n-million=%d key-bits=%d]\n", argv[0], DEFAULT_N_MILL, DEFAULT_KEYBITS); diff --git a/docs/carc_api.md b/docs/carc_api.md index bdab2533..534e3da3 100644 --- a/docs/carc_api.md +++ b/docs/carc_api.md @@ -39,7 +39,7 @@ carc_X carc_X_from_ptr(i_val* p); // create a carc carc_X carc_X_clone(carc_X other); // return other with increased use count carc_X carc_X_move(carc_X* self); // transfer ownership to another carc. void carc_X_take(carc_X* self, carc_X other); // take ownership of other. -void carc_X_copy(carc_X* self, carc_X other); // copy shared (increase use count) +void carc_X_assign(carc_X* self, carc_X other); // copy shared (increase use count) void carc_X_drop(carc_X* self); // destruct (decrease use count, free at 0) long carc_X_use_count(carc_X ptr); diff --git a/docs/carray_api.md b/docs/carray_api.md index fba152c6..579bf119 100644 --- a/docs/carray_api.md +++ b/docs/carray_api.md @@ -26,11 +26,11 @@ carr2_X carr2_X_with_size(size_t xdim, size_t ydim, i_val val); carr2_X carr2_X_with_data(size_t xdim, size_t ydim, i_val* array); carr2_X carr2_X_new_uninit(size_t xdim, size_t ydim); carr2_X carr2_X_clone(carr2_X arr); -void carr2_X_copy(carr2_X* self, carr2_X other); +void carr2_X_copy(carr2_X* self, const carr2_X* other); i_val* carr2_X_release(carr2_X* self); // release storage (not freed) void carr2_X_drop(carr2_X* self); -size_t carr2_X_size(carr2_X arr); +size_t carr2_X_size(const carr2_X* self); i_val* carr2_X_data(carr2_X* self); // access storage data const i_val* carr2_X_at(const carr2_X* self, size_t x, size_t y); size_t carr2_X_idx(const carr2_X* self, size_t x, size_t y); @@ -47,11 +47,11 @@ carr3_X carr3_X_with_size(size_t xdim, size_t ydim, size_t zdim, i_v carr3_X carr3_X_with_data(size_t xdim, size_t ydim, size_t zdim, i_val* array); carr3_X carr3_X_new_uninit(size_t xdim, size_t ydim, size_t zdim); carr3_X carr3_X_clone(carr3_X arr); -void carr3_X_copy(carr3_X* self, carr3_X other); +void carr3_X_copy(carr3_X* self, const carr3_X* other); i_val* carr3_X_release(carr3_X* self); // release storage (not freed) void carr3_X_drop(carr3_X* self); -size_t carr3_X_size(carr3_X arr); +size_t carr3_X_size(const carr3_X* self); i_val* carr3_X_data(carr3_X* self); // storage data const i_val* carr3_X_at(const carr3_X* self, size_t x, size_t y, size_t z); size_t carr3_X_idx(const carr3_X* self, size_t x, size_t y, size_t z); diff --git a/docs/cbox_api.md b/docs/cbox_api.md index 8709548a..4087ffa3 100644 --- a/docs/cbox_api.md +++ b/docs/cbox_api.md @@ -38,7 +38,7 @@ cbox_X cbox_X_from_ptr(i_val* p); // create a cbox f cbox_X cbox_X_clone(cbox_X other); // return deep copied clone cbox_X cbox_X_move(cbox_X* self); // transfer ownership to another cbox. void cbox_X_take(cbox_X* self, cbox_X other); // take ownership of other. -void cbox_X_copy(cbox_X* self, cbox_X other); // deep copy to self +void cbox_X_assign(cbox_X* self, cbox_X other); // deep copy to self void cbox_X_drop(cbox_X* self); // destruct the contained object and free's it. void cbox_X_reset(cbox_X* self); diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index a1f1228f..1840468c 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -28,15 +28,15 @@ cdeq_X cdeq_X_with_capacity(size_t size); cdeq_X cdeq_X_clone(cdeq_X deq); void cdeq_X_clear(cdeq_X* self); -void cdeq_X_copy(cdeq_X* self, cdeq_X other); +void cdeq_X_copy(cdeq_X* self, const cdeq_X* other); bool cdeq_X_reserve(cdeq_X* self, size_t cap); void cdeq_X_shrink_to_fit(cdeq_X* self); void cdeq_X_swap(cdeq_X* a, cdeq_X* b); void cdeq_X_drop(cdeq_X* self); // destructor -bool cdeq_X_empty(cdeq_X deq); -size_t cdeq_X_size(cdeq_X deq); -size_t cdeq_X_capacity(cdeq_X deq); +bool cdeq_X_empty(const cdeq_X* self); +size_t cdeq_X_size(const cdeq_X* self); +size_t cdeq_X_capacity(const cdeq_X* self); const cdeq_X_value* cdeq_X_at(const cdeq_X* self, size_t idx); const cdeq_X_value* cdeq_X_get(const cdeq_X* self, i_valraw raw); // return NULL if not found diff --git a/docs/clist_api.md b/docs/clist_api.md index 58970a19..9cd950bb 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -42,7 +42,7 @@ clist_X clist_X_init(void); clist_X clist_X_clone(clist_X list); void clist_X_clear(clist_X* self); -void clist_X_copy(clist_X* self, clist_X other); +void clist_X_copy(clist_X* self, const clist_X* other); void clist_X_drop(clist_X* self); // destructor bool clist_X_empty(clist_X list); diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 58d33534..5804112f 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -48,17 +48,17 @@ cmap_X cmap_X_with_capacity(size_t cap); cmap_X cmap_X_clone(cmap_x map); void cmap_X_clear(cmap_X* self); -void cmap_X_copy(cmap_X* self, cmap_X other); +void cmap_X_copy(cmap_X* self, const cmap_X* other); void cmap_X_max_load_factor(cmap_X* self, float max_load); // default: 0.85 bool cmap_X_reserve(cmap_X* self, size_t size); void cmap_X_shrink_to_fit(cmap_X* self); void cmap_X_swap(cmap_X* a, cmap_X* b); void cmap_X_drop(cmap_X* self); // destructor -size_t cmap_X_size(cmap_X map); -size_t cmap_X_capacity(cmap_X map); // buckets * max_load_factor -bool cmap_X_empty(cmap_X map); -size_t cmap_X_bucket_count(cmap_X map); // num. of allocated buckets +size_t cmap_X_size(const cmap_X* self); +size_t cmap_X_capacity(const cmap_X self); // buckets * max_load_factor +bool cmap_X_empty(const cmap_X* self ); +size_t cmap_X_bucket_count(const cmap_X* self); // num. of allocated buckets const cmap_X_mapped* cmap_X_at(const cmap_X* self, i_keyraw rkey); // rkey must be in map cmap_X_mapped* cmap_X_at_mut(cmap_X* self, i_keyraw rkey); // mutable at diff --git a/docs/cpque_api.md b/docs/cpque_api.md index d9a381cc..12f5c3bc 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -32,11 +32,11 @@ cpque_X cpque_X_clone(cpque_X pq); void cpque_X_clear(cpque_X* self); bool cpque_X_reserve(cpque_X* self, size_t n); void cpque_X_shrink_to_fit(cpque_X* self); -void cpque_X_copy(cpque_X* self, cpque_X other); +void cpque_X_copy(cpque_X* self, const cpque_X* other); void cpque_X_drop(cpque_X* self); // destructor -size_t cpque_X_size(cpque_X pq); -bool cpque_X_empty(cpque_X pq); +size_t cpque_X_size(const cpque_X* self); +bool cpque_X_empty(const cpque_X* self); i_val* cpque_X_top(const cpque_X* self); void cpque_X_make_heap(cpque_X* self); // heapify the vector. diff --git a/docs/cqueue_api.md b/docs/cqueue_api.md index ffb75216..1f5469d6 100644 --- a/docs/cqueue_api.md +++ b/docs/cqueue_api.md @@ -27,7 +27,7 @@ cqueue_X cqueue_X_init(void); cqueue_X cqueue_X_clone(cqueue_X q); void cqueue_X_clear(cqueue_X* self); -void cqueue_X_copy(cqueue_X* self, cqueue_X other); +void cqueue_X_copy(cqueue_X* self, const cqueue_X* other); void cqueue_X_drop(cqueue_X* self); // destructor size_t cqueue_X_size(cqueue_X q); diff --git a/docs/cset_api.md b/docs/cset_api.md index b325eaca..95a236b1 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -28,17 +28,17 @@ cset_X cset_X_with_capacity(size_t cap); cset_X cset_X_clone(cset_x set); void cset_X_clear(cset_X* self); -void cset_X_copy(cset_X* self, cset_X other); +void cset_X_copy(cset_X* self, const cset_X* other); void cset_X_max_load_factor(cset_X* self, float max_load); // default: 0.85 bool cset_X_reserve(cset_X* self, size_t size); void cset_X_shrink_to_fit(cset_X* self); void cset_X_swap(cset_X* a, cset_X* b); void cset_X_drop(cset_X* self); // destructor -size_t cset_X_size(cset_X set); // num. of allocated buckets -size_t cset_X_capacity(cset_X set); // buckets * max_load_factor -bool cset_X_empty(cset_X set); -size_t cset_X_bucket_count(cset_X set); +size_t cset_X_size(const cset_X* self); // num. of allocated buckets +size_t cset_X_capacity(const cset_X* self); // buckets * max_load_factor +bool cset_X_empty(const cset_X* self); +size_t cset_X_bucket_count(const cset_X* self); bool cset_X_contains(const cset_X* self, i_keyraw rkey); const cset_X_value* cset_X_get(const cset_X* self, i_keyraw rkey); // return NULL if not found diff --git a/docs/csmap_api.md b/docs/csmap_api.md index a797e3cd..b3cf668b 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -47,12 +47,13 @@ void csmap_X_shrink_to_fit(csmap_X* self); csmap_X csmap_X_clone(csmap_x map); void csmap_X_clear(csmap_X* self); -void csmap_X_copy(csmap_X* self, csmap_X other); +void csmap_X_copy(csmap_X* self, const csmap_X* other); void csmap_X_swap(csmap_X* a, csmap_X* b); void csmap_X_drop(csmap_X* self); // destructor -size_t csmap_X_size(csmap_X map); -bool csmap_X_empty(csmap_X map); +size_t csmap_X_size(const csmap_X self); +bool csmap_X_empty(const csmap_X* self); +bool csmap_X_capacity(const csmap_X* self); const csmap_X_mapped* csmap_X_at(const csmap_X* self, i_keyraw rkey); // rkey must be in map csmap_X_mapped* csmap_X_at_mut(csmap_X* self, i_keyraw rkey); // mutable at diff --git a/docs/csset_api.md b/docs/csset_api.md index 5106a791..66ce8505 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -30,7 +30,7 @@ void csset_X_shrink_to_fit(csset_X* self); csset_X csset_X_clone(csset_x set); void csset_X_clear(csset_X* self); -void csset_X_copy(csset_X* self, csset_X other); +void csset_X_copy(csset_X* self, const csset_X* other); void csset_X_swap(csset_X* a, csset_X* b); void csset_X_drop(csset_X* self); // destructor diff --git a/docs/cstack_api.md b/docs/cstack_api.md index a72153e1..f148df38 100644 --- a/docs/cstack_api.md +++ b/docs/cstack_api.md @@ -32,12 +32,12 @@ void cstack_X_clear(cstack_X* self); bool cstack_X_reserve(cstack_X* self, size_t n); void cstack_X_shrink_to_fit(cstack_X* self); i_val* cstack_X_append_uninit(cstack_X* self, size_t n); -void cstack_X_copy(cstack_X* self, cstack_X other); +void cstack_X_copy(cstack_X* self, const cstack_X* other); void cstack_X_drop(cstack_X* self); // destructor -size_t cstack_X_size(cstack_X st); -size_t cstack_X_capacity(cstack_X st); -bool cstack_X_empty(cstack_X st); +size_t cstack_X_size(const cstack_X* self); +size_t cstack_X_capacity(const cstack_X* self); +bool cstack_X_empty(const cstack_X* self); i_val* cstack_X_top(const cstack_X* self); const i_val* cstack_X_at(const cstack_X* self, size_t idx); diff --git a/docs/cstr_api.md b/docs/cstr_api.md index 071da20a..7afdcf77 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -49,7 +49,6 @@ void cstr_clear(cstr* self); char* cstr_assign(cstr* self, const char* str); char* cstr_assign_s(cstr* self, cstr s); char* cstr_assign_n(cstr* self, const char* str, size_t len); // assign n first chars of str -void cstr_copy(cstr* self, cstr s); // like cstr_assign_s() int cstr_printf(cstr* self, const char* fmt, ...); // printf() formatting char* cstr_append(cstr* self, const char* app); diff --git a/docs/cvec_api.md b/docs/cvec_api.md index e504954c..db2bd8ce 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -33,7 +33,7 @@ cvec_X cvec_X_with_capacity(size_t size); cvec_X cvec_X_clone(cvec_X vec); void cvec_X_clear(cvec_X* self); -void cvec_X_copy(cvec_X* self, cvec_X other); +void cvec_X_copy(cvec_X* self, const cvec_X* other); bool cvec_X_reserve(cvec_X* self, size_t cap); bool cvec_X_resize(cvec_X* self, size_t size, i_val null); cvec_X_value* cvec_X_append_uninit(cvec_X* self, size_t n); // return start of uninit @@ -41,9 +41,9 @@ void cvec_X_shrink_to_fit(cvec_X* self); void cvec_X_swap(cvec_X* a, cvec_X* b); void cvec_X_drop(cvec_X* self); // destructor -bool cvec_X_empty(cvec_X vec); -size_t cvec_X_size(cvec_X vec); -size_t cvec_X_capacity(cvec_X vec); +bool cvec_X_empty(const cvec_X* self); +size_t cvec_X_size(const cvec_X* self); +size_t cvec_X_capacity(const cvec_X* self); const cvec_X_value* cvec_X_at(const cvec_X* self, size_t idx); const cvec_X_value* cvec_X_get(const cvec_X* self, i_valraw raw); // return NULL if not found diff --git a/examples/astar.c b/examples/astar.c index 4b86df9e..7d90bf35 100644 --- a/examples/astar.c +++ b/examples/astar.c @@ -88,7 +88,7 @@ astar(cstr* maze, int width) point goal = point_from(maze, "!", width); csmap_pcost_insert(&costs, start, 0); cpque_point_push(&front, start); - while (!cpque_point_empty(front)) + while (!cpque_point_empty(&front)) { point current = *cpque_point_top(&front); cpque_point_pop(&front); diff --git a/examples/bits2.c b/examples/bits2.c index bb3324e3..73c18351 100644 --- a/examples/bits2.c +++ b/examples/bits2.c @@ -2,7 +2,7 @@ // Example of static sized (stack allocated) bitsets #define i_type Bits -#define i_len 80 // enable fixed bitset on the stack +#define i_cap 80 // enable fixed bitset on the stack #include int main() diff --git a/examples/books.c b/examples/books.c index b2015208..fb9e4564 100644 --- a/examples/books.c +++ b/examples/books.c @@ -33,7 +33,7 @@ int main() // queried using references (&str). if (cmap_str_contains(&book_reviews, "Les Misérables")) { printf("We've got %" PRIuMAX " reviews, but Les Misérables ain't one.", - cmap_str_size(book_reviews)); + cmap_str_size(&book_reviews)); } // oops, this review has a lot of spelling mistakes, let's delete it. diff --git a/examples/complex.c b/examples/complex.c index 79a34a6a..c15d3bc7 100644 --- a/examples/complex.c +++ b/examples/complex.c @@ -42,7 +42,7 @@ int main() { // Put in some data in stack array stack.data[x] = 3.1415927f; - printf("stack size: %" PRIuMAX "\n", FloatStack_size(stack)); + printf("stack size: %" PRIuMAX "\n", FloatStack_size(&stack)); StackList list = StackList_init(); StackList_push_back(&list, stack); diff --git a/examples/convert.c b/examples/convert.c index c1380c94..56cd1eca 100644 --- a/examples/convert.c +++ b/examples/convert.c @@ -36,7 +36,7 @@ int main() cvec_str_emplace_back(&keys, cstr_str(&i.ref->first)); cvec_str_emplace_back(&values, cstr_str(&i.ref->second)); } - c_forrange (i, cvec_str_size(keys)) + c_forrange (i, cvec_str_size(&keys)) printf(" %s: %s\n", cstr_str(keys.data + i), cstr_str(values.data + i)); puts("\nCOPY VEC TO LIST:"); diff --git a/examples/cpque.c b/examples/cpque.c index 2c08f796..00d2697e 100644 --- a/examples/cpque.c +++ b/examples/cpque.c @@ -13,7 +13,7 @@ static bool (*less_fn)(const int* x, const int* y); void print_queue(ipque q) { ipque copy = ipque_clone(q); - while (!ipque_empty(copy)) { + while (!ipque_empty(©)) { printf("%d ", *ipque_top(©)); ipque_pop(©); } diff --git a/examples/csmap_erase.c b/examples/csmap_erase.c index 09d28d78..37d25f37 100644 --- a/examples/csmap_erase.c +++ b/examples/csmap_erase.c @@ -12,7 +12,7 @@ void printmap(mymap m) { c_foreach (elem, mymap, m) printf(" [%d, %s]", elem.ref->first, cstr_str(&elem.ref->second)); - printf("\nsize() == %" PRIuMAX "\n\n", mymap_size(m)); + printf("\nsize() == %" PRIuMAX "\n\n", mymap_size(&m)); } int main() diff --git a/examples/csmap_find.c b/examples/csmap_find.c index c3047110..f74f7fb9 100644 --- a/examples/csmap_find.c +++ b/examples/csmap_find.c @@ -17,10 +17,10 @@ void print_elem(csmap_istr_raw p) { } #define using_print_collection(CX) \ - void print_collection_##CX(CX t) { \ + void print_collection_##CX(const CX* t) { \ printf("%" PRIuMAX " elements: ", CX##_size(t)); \ \ - c_foreach (p, CX, t) { \ + c_foreach (p, CX, *t) { \ print_elem(CX##_value_toraw(p.ref)); \ } \ puts(""); \ @@ -48,7 +48,7 @@ int main() c_apply(v, csmap_istr_emplace(&m1, c_pair(v)), csmap_istr_raw, {{40, "Zr"}, {45, "Rh"}}); puts("The starting map m1 is (key, value):"); - print_collection_csmap_istr(m1); + print_collection_csmap_istr(&m1); typedef cvec_istr_value pair; cvec_istr_push_back(&v, (pair){43, "Tc"}); @@ -59,13 +59,13 @@ int main() cvec_istr_push_back(&v, (pair){44, "Ru"}); // attempt a duplicate puts("Inserting the following vector data into m1:"); - print_collection_cvec_istr(v); + print_collection_cvec_istr(&v); c_foreach (i, cvec_istr, cvec_istr_begin(&v), cvec_istr_end(&v)) csmap_istr_emplace(&m1, c_pair(i.ref)); puts("The modified map m1 is (key, value):"); - print_collection_csmap_istr(m1); + print_collection_csmap_istr(&m1); puts(""); findit(m1, 45); findit(m1, 6); diff --git a/examples/demos.c b/examples/demos.c index 7c5b9a4b..4cb50082 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -47,7 +47,7 @@ void vectordemo1() cvec_ix_pop_back(&bignums); // erase the last cvec_ix_erase_n(&bignums, 0, 1); // erase the first - for (size_t i = 0; i < cvec_ix_size(bignums); ++i) { + for (size_t i = 0; i < cvec_ix_size(&bignums); ++i) { printf("%" PRIuMAX ": %" PRIuMAX "\n", i, bignums.data[i]); } } @@ -175,11 +175,11 @@ void mapdemo3() cmap_str_iter it = cmap_str_find(&table, "Make"); c_foreach (i, cmap_str, table) printf("entry: %s: %s\n", cstr_str(&i.ref->first), cstr_str(&i.ref->second)); - printf("size %" PRIuMAX ": remove: Make: %s\n", cmap_str_size(table), cstr_str(&it.ref->second)); + printf("size %" PRIuMAX ": remove: Make: %s\n", cmap_str_size(&table), cstr_str(&it.ref->second)); //cmap_str_erase(&table, "Make"); cmap_str_erase_at(&table, it); - printf("size %" PRIuMAX "\n", cmap_str_size(table)); + printf("size %" PRIuMAX "\n", cmap_str_size(&table)); c_foreach (i, cmap_str, table) printf("entry: %s: %s\n", cstr_str(&i.ref->first), cstr_str(&i.ref->second)); cmap_str_drop(&table); // frees key and value cstrs, and hash table. @@ -200,7 +200,7 @@ void arraydemo1() float *arr1 = arr3.data[5][4]; printf("arr3: %" PRIuMAX ": (%" PRIuMAX ", %" PRIuMAX ", %" PRIuMAX ") = %" PRIuMAX "\n", sizeof(arr3), - arr3.xdim, arr3.ydim, arr3.zdim, carr3_f_size(arr3)); + arr3.xdim, arr3.ydim, arr3.zdim, carr3_f_size(&arr3)); printf("%g\n", arr1[3]); // = 10.2 printf("%g\n", arr2[4][3]); // = 10.2 diff --git a/examples/inits.c b/examples/inits.c index dc67075c..608dd146 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -44,7 +44,7 @@ int main(void) c_apply_array(v, cpque_f_push(&floats, *v), const float, nums, c_arraylen(nums)); puts("\npop and show high priorites first:"); - while (! cpque_f_empty(floats)) { + while (! cpque_f_empty(&floats)) { printf("%.1f ", *cpque_f_top(&floats)); cpque_f_pop(&floats); } diff --git a/examples/new_arr.c b/examples/new_arr.c index 8ccc62fa..17a96062 100644 --- a/examples/new_arr.c +++ b/examples/new_arr.c @@ -17,7 +17,7 @@ int main() carr2_int_drop(&volume)) { int *dat = carr2_int_data(&volume); - for (size_t i = 0; i < carr2_int_size(volume); ++i) + for (size_t i = 0; i < carr2_int_size(&volume); ++i) dat[i] = i; for (size_t x = 0; x < volume.xdim; ++x) @@ -34,7 +34,7 @@ int main() carr3_int_drop(&volume)) { int *dat = carr3_int_data(&volume); - for (size_t i = 0; i < carr3_int_size(volume); ++i) + for (size_t i = 0; i < carr3_int_size(&volume); ++i) dat[i] = i; for (size_t x = 0; x < volume.xdim; ++x) diff --git a/examples/new_pque.c b/examples/new_pque.c index 2e5cf9ca..1f968f4c 100644 --- a/examples/new_pque.c +++ b/examples/new_pque.c @@ -46,7 +46,7 @@ int main() cpque_pnt_push(&pque, (Point){54, 74}); cpque_pnt_push(&pque, (Point){12, 62}); // print - while (!cpque_pnt_empty(pque)) { + while (!cpque_pnt_empty(&pque)) { cpque_pnt_value *v = cpque_pnt_top(&pque); printf(" (%d,%d)", v->x, v->y); cpque_pnt_pop(&pque); @@ -58,7 +58,7 @@ int main() cpque_int_push(&ique, 123); cpque_int_push(&ique, 321); // print - for (size_t i=0; i0; --i) { int r = stc64_uniform(&rng, &dist); if (r & 1) @@ -39,6 +39,6 @@ int main() { else cqueue_int_pop(&Q); } - printf("after: size %" PRIuMAX ", capacity %" PRIuMAX "\n", cqueue_int_size(Q), cqueue_int_capacity(Q)); + printf("after: size %" PRIuMAX ", capacity %" PRIuMAX "\n", cqueue_int_size(&Q), cqueue_int_capacity(&Q)); } } diff --git a/examples/queue.c b/examples/queue.c index cfc8d988..cc6f8302 100644 --- a/examples/queue.c +++ b/examples/queue.c @@ -26,6 +26,6 @@ int main() { else --n, cqueue_i_pop(&queue); } - printf("%d, %" PRIuMAX "\n", n, cqueue_i_size(queue)); + printf("%d, %" PRIuMAX "\n", n, cqueue_i_size(&queue)); } } diff --git a/examples/stack.c b/examples/stack.c index ca809c97..1991e269 100644 --- a/examples/stack.c +++ b/examples/stack.c @@ -2,6 +2,7 @@ #include #define i_tag i +#define i_cap 100 #define i_val int #include diff --git a/include/stc/alt/csmap.h b/include/stc/alt/csmap.h index 168cf480..60a1b72a 100644 --- a/include/stc/alt/csmap.h +++ b/include/stc/alt/csmap.h @@ -155,11 +155,11 @@ _cx_memb(_value_clone)(_cx_value _val) { } STC_INLINE void -_cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->root == other.root) +_cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->root == other->root) return; _cx_memb(_drop)(self); - *self = _cx_memb(_clone)(other); + *self = _cx_memb(_clone)(*other); } #endif // !_i_no_clone diff --git a/include/stc/carc.h b/include/stc/carc.h index 73ccc5bf..57f00899 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -155,7 +155,7 @@ STC_INLINE _cx_self _cx_memb(_clone)(_cx_self ptr) { return ptr; } -STC_INLINE void _cx_memb(_copy)(_cx_self* self, _cx_self ptr) { +STC_INLINE void _cx_memb(_assign)(_cx_self* self, _cx_self ptr) { if (ptr.use_count) _i_atomic_inc(ptr.use_count); _cx_memb(_drop)(self); diff --git a/include/stc/carr2.h b/include/stc/carr2.h index dc35893a..66a98f58 100644 --- a/include/stc/carr2.h +++ b/include/stc/carr2.h @@ -38,7 +38,7 @@ int main() { c_autovar (carr2_int image = carr2_int_new_uninit(w, h), carr2_int_drop(&image)) { int *dat = carr2_int_data(&image); - for (int i = 0; i < carr2_int_size(image); ++i) + for (int i = 0; i < carr2_int_size(&image); ++i) dat[i] = i; for (int x = 0; x < image.xdim; ++x) @@ -67,14 +67,14 @@ STC_API _cx_value* _cx_memb(_release)(_cx_self* self); STC_API void _cx_memb(_drop)(_cx_self* self); #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self src); -STC_API void _cx_memb(_copy)(_cx_self *self, _cx_self other); +STC_API void _cx_memb(_copy)(_cx_self *self, const _cx_self* other); #endif STC_INLINE _cx_self _cx_memb(_new_uninit)(size_t xdim, size_t ydim) { return _cx_memb(_with_data)(xdim, ydim, c_alloc_n(_cx_value, xdim*ydim)); } -STC_INLINE size_t _cx_memb(_size)(_cx_self arr) - { return arr.xdim*arr.ydim; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* self) + { return self->xdim*self->ydim; } STC_INLINE _cx_value *_cx_memb(_data)(_cx_self* self) { return *self->data; } @@ -118,14 +118,14 @@ STC_DEF _cx_self _cx_memb(_with_size)(size_t xdim, size_t ydim, i_key null) { STC_DEF _cx_self _cx_memb(_clone)(_cx_self src) { _cx_self _arr = _cx_memb(_new_uninit)(src.xdim, src.ydim); - for (_cx_value* p = _arr.data[0], *q = src.data[0], *e = p + _cx_memb(_size)(src); p != e; ++p, ++q) + for (_cx_value* p = _arr.data[0], *q = src.data[0], *e = p + _cx_memb(_size)(&src); p != e; ++p, ++q) *p = i_keyclone((*q)); return _arr; } -STC_DEF void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->data == other.data) return; - _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); +STC_DEF void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); *self = _cx_memb(_clone)(*other); } #endif @@ -138,7 +138,7 @@ STC_DEF _cx_value *_cx_memb(_release)(_cx_self* self) { STC_DEF void _cx_memb(_drop)(_cx_self* self) { if (!self->data) return; - for (_cx_value* p = self->data[0], *q = p + _cx_memb(_size)(*self); p != q; ) { + for (_cx_value* p = self->data[0], *q = p + _cx_memb(_size)(self); p != q; ) { --q; i_keydrop(q); } c_free(self->data[0]); /* values */ diff --git a/include/stc/carr3.h b/include/stc/carr3.h index bbd3a065..8ff1670e 100644 --- a/include/stc/carr3.h +++ b/include/stc/carr3.h @@ -38,7 +38,7 @@ int main() { c_autovar (carr3_int image = carr3_int_new_uninit(w, h, d), carr3_int_drop(&image)) { int *dat = carr3_int_data(&image); - for (int i = 0; i < carr3_int_size(image); ++i) + for (int i = 0; i < carr3_int_size(&image); ++i) dat[i] = i; for (int x = 0; x < image.xdim; ++x) @@ -69,15 +69,15 @@ STC_API _cx_value* _cx_memb(_release)(_cx_self* self); STC_API void _cx_memb(_drop)(_cx_self* self); #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self src); -STC_API void _cx_memb(_copy)(_cx_self *self, _cx_self other); +STC_API void _cx_memb(_copy)(_cx_self *self, const _cx_self* other); #endif STC_INLINE _cx_self _cx_memb(_new_uninit)(size_t xdim, size_t ydim, size_t zdim) { return _cx_memb(_with_data)(xdim, ydim, zdim, c_alloc_n(_cx_value, xdim*ydim*zdim)); } -STC_INLINE size_t _cx_memb(_size)(_cx_self arr) - { return arr.xdim*arr.ydim*arr.zdim; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* self) + { return self->xdim*self->ydim*self->zdim; } STC_INLINE _cx_value* _cx_memb(_data)(_cx_self* self) { return **self->data; } @@ -95,7 +95,7 @@ STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) { return c_make(_cx_iter){**self->data}; } STC_INLINE _cx_iter _cx_memb(_end)(const _cx_self* self) - { return c_make(_cx_iter){**self->data + _cx_memb(_size)(*self)}; } + { return c_make(_cx_iter){**self->data + _cx_memb(_size)(self)}; } STC_INLINE void _cx_memb(_next)(_cx_iter* it) { ++it->ref; } @@ -123,14 +123,14 @@ STC_DEF _cx_self _cx_memb(_with_size)(size_t xdim, size_t ydim, size_t zdim, i_k STC_DEF _cx_self _cx_memb(_clone)(_cx_self src) { _cx_self _arr = _cx_memb(_new_uninit)(src.xdim, src.ydim, src.zdim); - for (_cx_value* p = **_arr.data, *q = **src.data, *e = p + _cx_memb(_size)(src); p != e; ++p, ++q) + for (_cx_value* p = **_arr.data, *q = **src.data, *e = p + _cx_memb(_size)(&src); p != e; ++p, ++q) *p = i_keyclone((*q)); return _arr; } -STC_DEF void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->data == other.data) return; - _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); +STC_DEF void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); *self = _cx_memb(_clone)(*other); } #endif @@ -143,7 +143,7 @@ STC_DEF _cx_value* _cx_memb(_release)(_cx_self* self) { STC_DEF void _cx_memb(_drop)(_cx_self* self) { if (!self->data) return; - for (_cx_value* p = **self->data, *q = p + _cx_memb(_size)(*self); p != q; ) { + for (_cx_value* p = **self->data, *q = p + _cx_memb(_size)(self); p != q; ) { --q; i_keydrop(q); } c_free(self->data[0][0]); /* data */ diff --git a/include/stc/cbits.h b/include/stc/cbits.h index f7ce2368..dccd5fb3 100644 --- a/include/stc/cbits.h +++ b/include/stc/cbits.h @@ -82,7 +82,7 @@ STC_API char* _cbits_to_str(const uint64_t* set, const size_t sz, #define _i_memb(name) c_paste(i_type, name) -#if !defined i_len +#if !defined i_cap #define _i_assert(x) assert(x) #define i_type cbits @@ -90,6 +90,7 @@ STC_API char* _cbits_to_str(const uint64_t* set, const size_t sz, struct { uint64_t *data64; size_t _size; } typedef i_type; STC_INLINE cbits cbits_init(void) { return c_make(cbits){NULL}; } +STC_INLINE void cbits_inits(cbits* self) { self->data64 = NULL; self->_size = 0; } STC_INLINE void cbits_drop(cbits* self) { c_free(self->data64); } STC_INLINE size_t cbits_size(const cbits* self) { return self->_size; } STC_API void cbits_resize(cbits* self, size_t size, bool value); @@ -131,18 +132,19 @@ STC_INLINE cbits cbits_with_pattern(const size_t size, const uint64_t pattern) { return set; } -#else // i_len +#else // i_cap #define _i_assert(x) (void)0 #if !defined i_type - #define i_type c_paste(cbits, i_len) + #define i_type c_paste(cbits, i_cap) #endif -struct { uint64_t data64[(i_len - 1)/64 + 1]; } typedef i_type; +struct { uint64_t data64[(i_cap - 1)/64 + 1]; } typedef i_type; STC_INLINE i_type _i_memb(_init)(void) { return c_make(i_type){0}; } +STC_INLINE void _i_memb(_inits)(i_type* self) {} STC_INLINE void _i_memb(_drop)(i_type* self) {} -STC_INLINE size_t _i_memb(_size)(const i_type* self) { return i_len; } +STC_INLINE size_t _i_memb(_size)(const i_type* self) { return i_cap; } STC_INLINE i_type _i_memb(_move)(i_type* self) { return *self; } STC_INLINE i_type* _i_memb(_take)(i_type* self, i_type other) @@ -151,24 +153,24 @@ STC_INLINE i_type* _i_memb(_take)(i_type* self, i_type other) STC_INLINE i_type _i_memb(_clone)(i_type other) { return other; } -STC_INLINE i_type* _i_memb(_copy)(i_type* self, i_type other) - { *self = other; return self; } +STC_INLINE i_type* _i_memb(_copy)(i_type* self, const i_type* other) + { *self = *other; return self; } STC_INLINE void _i_memb(_set_all)(i_type *self, const bool value); STC_INLINE void _i_memb(_set_pattern)(i_type *self, const uint64_t pattern); STC_INLINE i_type _i_memb(_with_size)(const size_t size, const bool value) { - assert(size <= i_len); + assert(size <= i_cap); i_type set; _i_memb(_set_all)(&set, value); return set; } STC_INLINE i_type _i_memb(_with_pattern)(const size_t size, const uint64_t pattern) { - assert(size <= i_len); + assert(size <= i_cap); i_type set; _i_memb(_set_pattern)(&set, pattern); return set; } -#endif // i_len +#endif // i_cap STC_INLINE void _i_memb(_set_all)(i_type *self, const bool value) @@ -248,7 +250,7 @@ STC_INLINE bool _i_memb(_disjoint)(const i_type* self, const i_type* other) { /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(i_implement) || defined(i_extern) -#if !defined i_len +#if !defined i_cap STC_DEF cbits* cbits_copy(cbits* self, const cbits* other) { if (self->data64 == other->data64) return self; @@ -318,7 +320,7 @@ STC_DEF bool _cbits_disjoint(const uint64_t* set, const uint64_t* other, const s #define CBITS_H_INCLUDED #undef _i_memb #undef _i_assert -#undef i_len +#undef i_cap #undef i_type #undef i_opt #undef i_header diff --git a/include/stc/cbox.h b/include/stc/cbox.h index f1e410b1..c3a9dd02 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -139,11 +139,11 @@ STC_INLINE void _cx_memb(_reset_to)(_cx_self* self, _cx_value* p) { return out; } - STC_INLINE void _cx_memb(_copy)(_cx_self* self, _cx_self other) { - if (self->get == other.get) + STC_INLINE void _cx_memb(_assign)(_cx_self* self, const _cx_self ptr) { + if (self->get == ptr.get) return; _cx_memb(_drop)(self); - *self = _cx_memb(_clone)(other); + *self = _cx_memb(_clone)(ptr); } #endif // !_i_no_clone diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index 9c706e52..c5e08393 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -49,13 +49,13 @@ STC_API void _cx_memb(_drop)(_cx_self* self); STC_API _cx_value* _cx_memb(_push)(_cx_self* self, i_key value); STC_API void _cx_memb(_shrink_to_fit)(_cx_self *self); #if !defined _i_queue -#if !defined _i_no_clone -STC_API _cx_value* _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2); #if !defined _i_no_emplace STC_API _cx_value* _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, const _cx_raw* p2); #endif // _i_no_emplace +#if !defined _i_no_clone +STC_API _cx_value* _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, + const _cx_value* p1, const _cx_value* p2); #endif // !_i_no_clone #if !c_option(c_no_cmp) @@ -76,15 +76,16 @@ STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) #endif STC_INLINE i_key _cx_memb(_value_clone)(i_key val) { return i_keyclone(val); } -STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->data == other.data) return; - _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); +STC_INLINE void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); + *self = _cx_memb(_clone)(*other); } #endif // !_i_no_clone -STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return cdeq_rep_(&cx)->size; } -STC_INLINE size_t _cx_memb(_capacity)(_cx_self cx) { return cdeq_rep_(&cx)->cap; } -STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return !cdeq_rep_(&cx)->size; } -STC_INLINE _cx_raw _cx_memb(_value_toraw)(_cx_value* pval) { return i_keyto(pval); } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* cx) { return cdeq_rep_(cx)->size; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* cx) { return cdeq_rep_(cx)->cap; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* cx) { return !cdeq_rep_(cx)->size; } +STC_INLINE _cx_raw _cx_memb(_value_toraw)(const _cx_value* pval) { return i_keyto(pval); } STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); } STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return self->data; } STC_INLINE _cx_value* _cx_memb(_back)(const _cx_self* self) @@ -142,12 +143,13 @@ _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2) { return _cx_memb(_erase_range_p)(self, it1.ref, it2.ref); } -#if !defined _i_no_clone && !defined _i_no_emplace +#if !defined _i_no_clone STC_INLINE _cx_value* _cx_memb(_emplace_range)(_cx_self* self, _cx_iter it, _cx_iter it1, _cx_iter it2) { return _cx_memb(_clone_range_p)(self, it.ref, it1.ref, it2.ref); } - +#endif // !_i_no_clone +#if !defined _i_no_emplace STC_INLINE _cx_value* _cx_memb(_emplace_front)(_cx_self* self, _cx_raw raw) { return _cx_memb(_push_front)(self, i_keyfrom(raw)); @@ -165,7 +167,7 @@ STC_INLINE _cx_value* _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, _cx_raw raw) { return _cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); } -#endif // !_i_no_clone && !_i_no_emplace +#endif // !_i_no_emplace #if !c_option(c_no_cmp) @@ -225,7 +227,7 @@ _cx_memb(_clear)(_cx_self* self) { STC_DEF void _cx_memb(_shrink_to_fit)(_cx_self *self) { - if (_cx_memb(_size)(*self) != _cx_memb(_capacity)(*self)) { + if (_cx_memb(_size)(self) != _cx_memb(_capacity)(self)) { struct cdeq_rep* rep = cdeq_rep_(self); const size_t sz = rep->size; memmove(self->_base, self->data, sz*sizeof(i_key)); @@ -389,7 +391,6 @@ _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2) { return c_make(_cx_iter){p1}; } -#if !defined _i_no_clone #if !defined _i_no_emplace STC_DEF _cx_value* _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, const _cx_raw* p2) { @@ -401,6 +402,7 @@ _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, co } #endif // !_i_no_emplace +#if !defined _i_no_clone STC_DEF _cx_value* _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, const _cx_value* p1, const _cx_value* p2) { diff --git a/include/stc/clist.h b/include/stc/clist.h index 29bf56f3..0fbf01ae 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -116,10 +116,12 @@ STC_API _cx_self _cx_memb(_clone)(_cx_self cx); STC_INLINE i_key _cx_memb(_value_clone)(i_key val) { return i_keyclone(val); } STC_INLINE void -_cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->last == other.last) return; - _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); +_cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->last == other->last) return; + _cx_memb(_drop)(self); *self = _cx_memb(_clone)(*other); } +#endif // !_i_no_clone + #if !defined _i_no_emplace STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, _cx_raw raw) { return _cx_memb(_push_back)(self, i_keyfrom(raw)); } @@ -130,11 +132,10 @@ STC_INLINE _cx_iter _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, _cx_r STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) { return _cx_memb(_push_back)(self, i_keyfrom(raw)); } #endif // !_i_no_emplace -#endif // !_i_no_clone STC_INLINE _cx_self _cx_memb(_init)(void) { return c_make(_cx_self){NULL}; } STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { return true; } -STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return cx.last == NULL; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* self) { return self->last == NULL; } STC_INLINE void _cx_memb(_clear)(_cx_self* self) { _cx_memb(_drop)(self); } STC_INLINE _cx_value* _cx_memb(_push)(_cx_self* self, i_key value) { return _cx_memb(_push_back)(self, value); } diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 3cc08cde..cfff214b 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -102,18 +102,18 @@ STC_API void _cx_memb(_erase_entry)(_cx_self* self, _cx_value* val); STC_INLINE _cx_self _cx_memb(_init)(void) { return c_make(_cx_self)_cmap_inits; } STC_INLINE void _cx_memb(_shrink_to_fit)(_cx_self* self) { _cx_memb(_reserve)(self, self->size); } STC_INLINE void _cx_memb(_max_load_factor)(_cx_self* self, float ml) {self->max_load_factor = ml; } -STC_INLINE bool _cx_memb(_empty)(_cx_self m) { return m.size == 0; } -STC_INLINE size_t _cx_memb(_size)(_cx_self m) { return m.size; } -STC_INLINE size_t _cx_memb(_bucket_count)(_cx_self map) { return map.bucket_count; } -STC_INLINE size_t _cx_memb(_capacity)(_cx_self map) - { return (size_t)(map.bucket_count*map.max_load_factor); } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* map) { return !map->size; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* map) { return map->size; } +STC_INLINE size_t _cx_memb(_bucket_count)(_cx_self* map) { return map->bucket_count; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* map) + { return (size_t)(map->bucket_count*map->max_load_factor); } STC_INLINE void _cx_memb(_swap)(_cx_self *map1, _cx_self *map2) {c_swap(_cx_self, *map1, *map2); } STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_rawkey rkey) { return self->size && self->_hashx[_cx_memb(_bucket_)(self, &rkey).idx]; } #ifndef _i_isset STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key _key, i_val _mapped); - #if !defined _i_no_clone && !defined _i_no_emplace + #if !defined _i_no_emplace STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped); #endif @@ -129,11 +129,11 @@ STC_INLINE bool _cx_memb(_contains)(const _cx_self* self, _cx_rawkey rke #endif // !_i_isset #if !defined _i_no_clone -STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->table == other.table) +STC_INLINE void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->table == other->table) return; _cx_memb(_drop)(self); - *self = _cx_memb(_clone)(other); + *self = _cx_memb(_clone)(*other); } STC_INLINE _cx_value @@ -142,6 +142,7 @@ _cx_memb(_value_clone)(_cx_value _val) { _i_MAP_ONLY( _val.second = i_valclone(_val.second); ) return _val; } +#endif // !_i_no_clone #if !defined _i_no_emplace STC_INLINE _cx_result @@ -154,10 +155,9 @@ _cx_memb(_emplace)(_cx_self* self, _cx_rawkey rkey _i_MAP_ONLY(, i_valraw rmappe return _res; } #endif // !_i_no_emplace -#endif // !_i_no_clone STC_INLINE _cx_raw -_cx_memb(_value_toraw)(_cx_value* val) { +_cx_memb(_value_toraw)(const _cx_value* val) { return _i_SET_ONLY( i_keyto(val) ) _i_MAP_ONLY( c_make(_cx_raw){i_keyto((&val->first)), i_valto((&val->second))} ); } @@ -299,7 +299,7 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { return _res; } - #if !defined _i_no_clone && !defined _i_no_emplace + #if !defined _i_no_emplace STC_DEF _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped) { _cx_result _res = _cx_memb(_insert_entry_)(self, rkey); @@ -310,7 +310,7 @@ STC_DEF void _cx_memb(_clear)(_cx_self* self) { _res.ref->second = i_valfrom(rmapped); return _res; } - #endif // !_i_no_clone && !_i_no_emplace + #endif // !_i_no_emplace #endif // !_i_isset STC_DEF chash_bucket_t diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 3a7cc0a1..bb7c207e 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -73,14 +73,14 @@ STC_INLINE void _cx_memb(_clear)(_cx_self* self) { STC_INLINE void _cx_memb(_drop)(_cx_self* self) { _cx_memb(_clear)(self); c_free(self->data); } -STC_INLINE size_t _cx_memb(_size)(_cx_self q) - { return q.size; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* q) + { return q->size; } -STC_INLINE bool _cx_memb(_empty)(_cx_self q) - { return !q.size; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* q) + { return !q->size; } -STC_INLINE size_t _cx_memb(_capacity)(_cx_self q) - { return q.capacity; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* q) + { return q->capacity; } STC_INLINE _cx_value* _cx_memb(_top)(const _cx_self* self) { return &self->data[0]; } @@ -91,18 +91,19 @@ STC_INLINE void _cx_memb(_pop)(_cx_self* self) #if !defined _i_no_clone STC_API _cx_self _cx_memb(_clone)(_cx_self q); -STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->data == other.data) return; - _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); +STC_INLINE void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); + *self = _cx_memb(_clone)(*other); } STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) { return i_keyclone(val); } +#endif // !_i_no_clone #if !defined _i_no_emplace STC_INLINE void _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) { _cx_memb(_push)(self, i_keyfrom(raw)); } #endif // !_i_no_emplace -#endif // !_i_no_clone /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(i_implement) @@ -118,7 +119,7 @@ _cx_memb(_sift_down_)(_cx_value* arr, const size_t idx, const size_t n) { STC_DEF void _cx_memb(_make_heap)(_cx_self* self) { - size_t n = _cx_memb(_size)(*self); + size_t n = self->size; _cx_value *arr = self->data - 1; for (size_t k = n >> 1; k != 0; --k) _cx_memb(_sift_down_)(arr, k, n); diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 00874f35..0c0df063 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -40,7 +40,7 @@ int main() { cqueue_int_push(&Q, stc64_uniform(&rng, &dist)); // Push or pop on the queue ten million times - printf("before: size, capacity: %d, %d\n", n, cqueue_int_size(Q), cqueue_int_capacity(Q)); + printf("before: size, capacity: %d, %d\n", n, cqueue_int_size(&Q), cqueue_int_capacity(&Q)); for (int i=n; i>0; --i) { int r = stc64_uniform(&rng, &dist); if (r & 1) @@ -48,7 +48,7 @@ int main() { else --n, cqueue_int_pop(&Q); } - printf("after: size, capacity: %d, %d\n", n, cqueue_int_size(Q), cqueue_int_capacity(Q)); + printf("after: size, capacity: %d, %d\n", n, cqueue_int_size(&Q), cqueue_int_capacity(&Q)); } } */ diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 5af28830..97f1fce1 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -97,11 +97,11 @@ typedef _i_SET_ONLY( i_keyraw ) _i_MAP_ONLY( struct { i_keyraw first; i_valraw second; } ) _cx_raw; -#if !defined _i_no_clone -STC_API _cx_self _cx_memb(_clone)(_cx_self tree); #if !defined _i_no_emplace STC_API _cx_result _cx_memb(_emplace)(_cx_self* self, _cx_rawkey rkey _i_MAP_ONLY(, i_valraw rmapped)); #endif // !_i_no_emplace +#if !defined _i_no_clone +STC_API _cx_self _cx_memb(_clone)(_cx_self tree); #endif // !_i_no_clone STC_API _cx_self _cx_memb(_init)(void); STC_API _cx_result _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)); @@ -117,9 +117,9 @@ STC_API _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it); STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2); STC_API void _cx_memb(_next)(_cx_iter* it); -STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return _csmap_rep(&cx)->size == 0; } -STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return _csmap_rep(&cx)->size; } -STC_INLINE size_t _cx_memb(_capacity)(_cx_self cx) { return _csmap_rep(&cx)->cap; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* cx) { return _csmap_rep(cx)->size == 0; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* cx) { return _csmap_rep(cx)->size; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* cx) { return _csmap_rep(cx)->cap; } STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); } STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, _cx_rawkey rkey) { _cx_iter it; _cx_memb(_find_it)(self, rkey, &it); return it; } @@ -142,7 +142,7 @@ _cx_memb(_clear)(_cx_self* self) { _cx_memb(_drop)(self); *self = _cx_memb(_init)(); } STC_INLINE _cx_raw -_cx_memb(_value_toraw)(_cx_value* val) { +_cx_memb(_value_toraw)(const _cx_value* val) { return _i_SET_ONLY( i_keyto(val) ) _i_MAP_ONLY( c_make(_cx_raw){i_keyto((&val->first)), i_valto((&val->second))} ); @@ -169,11 +169,11 @@ _cx_memb(_value_clone)(_cx_value _val) { } STC_INLINE void -_cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->nodes == other.nodes) +_cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->nodes == other->nodes) return; _cx_memb(_drop)(self); - *self = _cx_memb(_clone)(other); + *self = _cx_memb(_clone)(*other); } STC_INLINE void @@ -184,7 +184,7 @@ _cx_memb(_shrink_to_fit)(_cx_self *self) { #endif // !_i_no_clone #ifndef _i_isset - #if !defined _i_no_clone && !defined _i_no_emplace + #if !defined _i_no_emplace STC_API _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped); #endif STC_API _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped); @@ -275,7 +275,7 @@ static i_size _cx_memb(_new_node_)(_cx_self* self, int level) { i_size tn; struct csmap_rep *rep = _csmap_rep(self); if (rep->disp) { - tn = rep->disp; + tn = (i_size)rep->disp; rep->disp = self->nodes[tn].link[1]; } else { if (rep->head == rep->cap) @@ -324,7 +324,7 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { return res; } - #if !defined _i_no_clone && !defined _i_no_emplace + #if !defined _i_no_emplace STC_DEF _cx_result _cx_memb(_emplace_or_assign)(_cx_self* self, _cx_rawkey rkey, i_valraw rmapped) { _cx_result res = _cx_memb(_insert_entry_)(self, rkey); @@ -337,7 +337,7 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { } return res; } - #endif // !_i_no_clone && !_i_no_emplace + #endif // !_i_no_emplace #endif // !_i_isset STC_DEF _cx_value* diff --git a/include/stc/cstack.h b/include/stc/cstack.h index b9cff196..46d209ca 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -34,12 +34,29 @@ #include "template.h" #if !c_option(c_is_fwd) -_cx_deftypes(_c_cstack_types, _cx_self, i_key); +#ifdef i_cap + #define _i_no_clone + _cx_deftypes(_c_cstack_fixed, _cx_self, i_key, i_cap); +#else + _cx_deftypes(_c_cstack_types, _cx_self, i_key); +#endif #endif typedef i_keyraw _cx_raw; -STC_INLINE _cx_self _cx_memb(_init)(void) - { return c_make(_cx_self){0, 0, 0}; } +STC_INLINE _cx_self _cx_memb(_init)(void) { + _cx_self s; s.size = 0; +#ifndef i_cap + s.capacity = 0; s.data = NULL; +#endif + return s; +} + +#ifdef i_cap +STC_INLINE void _cx_memb(_inits)(_cx_self* self) + { self->size = 0; } +#else +STC_INLINE void _cx_memb(_inits)(_cx_self* self) + { self->size = 0; self->capacity = 0; self->data = NULL; } STC_INLINE _cx_self _cx_memb(_with_capacity)(size_t cap) { _cx_self out = {(_cx_value *) c_malloc(cap*sizeof(i_key)), 0, cap}; @@ -51,6 +68,7 @@ STC_INLINE _cx_self _cx_memb(_with_size)(size_t size, i_key null) { while (size) out.data[--size] = null; return out; } +#endif STC_INLINE void _cx_memb(_clear)(_cx_self* self) { _cx_value *p = self->data + self->size; @@ -58,22 +76,33 @@ STC_INLINE void _cx_memb(_clear)(_cx_self* self) { self->size = 0; } -STC_INLINE void _cx_memb(_drop)(_cx_self* self) - { _cx_memb(_clear)(self); c_free(self->data); } +STC_INLINE void _cx_memb(_drop)(_cx_self* self) { + _cx_memb(_clear)(self); +#ifndef i_cap + c_free(self->data); +#endif +} -STC_INLINE size_t _cx_memb(_size)(_cx_self v) - { return v.size; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* self) + { return self->size; } -STC_INLINE bool _cx_memb(_empty)(_cx_self v) - { return !v.size; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* self) + { return !self->size; } -STC_INLINE size_t _cx_memb(_capacity)(_cx_self v) - { return v.capacity; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* self) { +#ifndef i_cap + return self->capacity; +#else + return i_cap; +#endif +} STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { if (n < self->size) return true; +#ifndef i_cap _cx_value *t = (_cx_value *)c_realloc(self->data, n*sizeof *t); if (t) { self->capacity = n, self->data = t; return true; } +#endif return false; } @@ -88,11 +117,11 @@ _cx_memb(_append_uninit)(_cx_self *self, size_t n) { STC_INLINE void _cx_memb(_shrink_to_fit)(_cx_self* self) { _cx_memb(_reserve)(self, self->size); } -STC_INLINE _cx_value* _cx_memb(_top)(const _cx_self* self) +STC_INLINE const _cx_value* _cx_memb(_top)(const _cx_self* self) { return &self->data[self->size - 1]; } STC_INLINE _cx_value* _cx_memb(_push)(_cx_self* self, _cx_value val) { - if (self->size == self->capacity) + if (self->size == _cx_memb(_capacity)(self)) if (!_cx_memb(_reserve)(self, self->size*3/2 + 4)) return NULL; _cx_value* vp = self->data + self->size++; @@ -111,7 +140,6 @@ STC_INLINE const _cx_value* _cx_memb(_at)(const _cx_self* self, size_t idx) STC_INLINE _cx_value* _cx_memb(_at_mut)(_cx_self* self, size_t idx) { assert(idx < self->size); return self->data + idx; } -#if !defined _i_no_clone #if !defined _i_no_emplace STC_INLINE _cx_value* _cx_memb(_emplace)(_cx_self* self, _cx_raw raw) { return _cx_memb(_push)(self, i_keyfrom(raw)); } @@ -119,31 +147,36 @@ STC_INLINE _cx_value* _cx_memb(_emplace_back)(_cx_self* self, _cx_raw raw) { return _cx_memb(_push)(self, i_keyfrom(raw)); } #endif // !_i_no_emplace +#if !defined _i_no_clone STC_INLINE _cx_self _cx_memb(_clone)(_cx_self v) { - _cx_self out = {(_cx_value *) c_malloc(v.size*sizeof(_cx_value)), v.size, v.size}; + _cx_self out = {(_cx_value *)c_malloc(v.size*sizeof(_cx_value)), v.size, v.size}; if (!out.data) out.capacity = 0; else for (size_t i = 0; i < v.size; ++v.data) out.data[i++] = i_keyclone((*v.data)); return out; } -STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->data == other.data) return; - _cx_memb(_drop)(self); *self = _cx_memb(_clone)(other); +STC_INLINE void _cx_memb(_copy)(_cx_self *self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); + *self = _cx_memb(_clone)(*other); } STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) { return i_keyclone(val); } -STC_INLINE i_keyraw _cx_memb(_value_toraw)(_cx_value* val) +STC_INLINE i_keyraw _cx_memb(_value_toraw)(const _cx_value* val) { return i_keyto(val); } #endif // !_i_no_clone STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) - { return c_make(_cx_iter){self->data}; } + { return c_make(_cx_iter){(_cx_value*)self->data}; } + STC_INLINE _cx_iter _cx_memb(_end)(const _cx_self* self) - { return c_make(_cx_iter){self->data + self->size}; } + { return c_make(_cx_iter){(_cx_value*)self->data + self->size}; } + STC_INLINE void _cx_memb(_next)(_cx_iter* it) { ++it->ref; } + STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t offs) { it.ref += offs; return it; } diff --git a/include/stc/cstr.h b/include/stc/cstr.h index ed533064..441fe94a 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -300,9 +300,6 @@ STC_INLINE char* cstr_assign_s(cstr* self, cstr s) { return cstr_assign_n(self, sv.str, sv.size); } -STC_INLINE void cstr_copy(cstr* self, cstr s) - { cstr_assign_s(self, s); } - STC_INLINE char* cstr_append(cstr* self, const char* str) { return cstr_append_n(self, str, strlen(str)); } diff --git a/include/stc/cvec.h b/include/stc/cvec.h index 77462a30..19303125 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -93,17 +93,6 @@ STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, _cx_raw r STC_API _cx_iter _cx_memb(_binary_search_in)(_cx_iter it1, _cx_iter it2, _cx_raw raw, _cx_iter* lower_bound); #endif -#if !defined _i_no_clone -STC_API _cx_self _cx_memb(_clone)(_cx_self cx); -STC_API _cx_value* _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, - const _cx_value* p1, const _cx_value* p2); -STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) - { return i_keyclone(val); } -STC_INLINE void _cx_memb(_copy)(_cx_self *self, _cx_self other) { - if (self->data == other.data) return; - _cx_memb(_drop)(self); - *self = _cx_memb(_clone)(other); - } #if !defined _i_no_emplace STC_API _cx_value* _cx_memb(_emplace_range_p)(_cx_self* self, _cx_value* pos, const _cx_raw* p1, const _cx_raw* p2); @@ -119,17 +108,29 @@ STC_INLINE _cx_value* _cx_memb(_emplace_at)(_cx_self* self, _cx_iter it, _cx_raw raw) { return _cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); } +#endif // !_i_no_emplace + +#if !defined _i_no_clone +STC_API _cx_self _cx_memb(_clone)(_cx_self cx); +STC_API _cx_value* _cx_memb(_clone_range_p)(_cx_self* self, _cx_value* pos, + const _cx_value* p1, const _cx_value* p2); +STC_INLINE i_key _cx_memb(_value_clone)(_cx_value val) + { return i_keyclone(val); } +STC_INLINE void _cx_memb(_copy)(_cx_self* self, const _cx_self* other) { + if (self->data == other->data) return; + _cx_memb(_drop)(self); + *self = _cx_memb(_clone)(*other); + } STC_INLINE _cx_value* _cx_memb(_emplace_range)(_cx_self* self, _cx_iter it, _cx_iter it1, _cx_iter it2) { return _cx_memb(_clone_range_p)(self, it.ref, it1.ref, it2.ref); } -#endif // !_i_no_emplace #endif // !_i_no_clone -STC_INLINE size_t _cx_memb(_size)(_cx_self cx) { return cvec_rep_(&cx)->size; } -STC_INLINE size_t _cx_memb(_capacity)(_cx_self cx) { return cvec_rep_(&cx)->cap; } -STC_INLINE bool _cx_memb(_empty)(_cx_self cx) { return !cvec_rep_(&cx)->size; } -STC_INLINE _cx_raw _cx_memb(_value_toraw)(_cx_value* val) { return i_keyto(val); } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* cx) { return cvec_rep_(cx)->size; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* cx) { return cvec_rep_(cx)->cap; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* cx) { return !cvec_rep_(cx)->size; } +STC_INLINE _cx_raw _cx_memb(_value_toraw)(const _cx_value* val) { return i_keyto(val); } STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); } STC_INLINE _cx_value* _cx_memb(_front)(const _cx_self* self) { return self->data; } STC_INLINE _cx_value* _cx_memb(_back)(const _cx_self* self) @@ -146,7 +147,7 @@ STC_INLINE _cx_iter _cx_memb(_end)(const _cx_self* self) STC_INLINE void _cx_memb(_next)(_cx_iter* it) { ++it->ref; } STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t offs) { it.ref += offs; return it; } -STC_INLINE size_t _cx_memb(_index)(_cx_self cx, _cx_iter it) { return it.ref - cx.data; } +STC_INLINE size_t _cx_memb(_index)(const _cx_self* cx, _cx_iter it) { return it.ref - cx->data; } STC_INLINE _cx_self _cx_memb(_with_size)(const size_t size, i_key null) { @@ -163,13 +164,13 @@ _cx_memb(_with_capacity)(const size_t cap) { } STC_INLINE void -_cx_memb(_shrink_to_fit)(_cx_self *self) { - _cx_memb(_reserve)(self, _cx_memb(_size)(*self)); +_cx_memb(_shrink_to_fit)(_cx_self* self) { + _cx_memb(_reserve)(self, _cx_memb(_size)(self)); } STC_INLINE _cx_value* -_cx_memb(_append_uninit)(_cx_self *self, const size_t n) { - return _cx_memb(_insert_uninit_p)(self, self->data + _cx_memb(_size)(*self), n); +_cx_memb(_append_uninit)(_cx_self* self, const size_t n) { + return _cx_memb(_insert_uninit_p)(self, self->data + _cx_memb(_size)(self), n); } STC_INLINE _cx_value* diff --git a/include/stc/forward.h b/include/stc/forward.h index 18c3d7b0..9c462b8e 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -192,6 +192,14 @@ typedef union { size_t size, capacity; \ } SELF +#define _c_cstack_fixed(SELF, VAL, CAP) \ + typedef VAL SELF##_value; \ + typedef struct { SELF##_value *ref; } SELF##_iter; \ + typedef struct SELF { \ + SELF##_value data[CAP]; \ + size_t size; \ + } SELF + #define _c_cpque_types(SELF, VAL) \ typedef VAL SELF##_value; \ typedef struct SELF { \ diff --git a/include/stc/template.h b/include/stc/template.h index 217b29d3..93f5e4c2 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -259,6 +259,7 @@ #undef i_cmp #undef i_eq #undef i_hash +#undef i_cap #undef i_size #undef i_val -- cgit v1.2.3