From 1aa7b8ff0952800ee26832f17dadf8a1a24d3848 Mon Sep 17 00:00:00 2001 From: tylo Date: Wed, 12 Aug 2020 09:57:52 +0200 Subject: Updated robin_hood hash. --- examples/benchmark.c | 4 +- examples/others/robin_hood.hpp | 549 +++++++++++++++++++++++++---------------- stc/cbitset.h | 6 +- 3 files changed, 347 insertions(+), 212 deletions(-) diff --git a/examples/benchmark.c b/examples/benchmark.c index af696692..42eb57ca 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -34,7 +34,7 @@ crandom_eng64_t rng; ; cmap_##tag##_set_load_factors(&map, max_load_factor, 0.0) #define CMAP_PUT(tag, key, val) cmap_##tag##_put(&map, key, val)->value #define CMAP_ERASE(tag, key) cmap_##tag##_erase(&map, key) -#define CMAP_FIND(tag, key) (cmap_##tag##_find(map, key) != c_nullptr) +#define CMAP_FIND(tag, key) (cmap_##tag##_find(map, key) != NULL) #define CMAP_SIZE(tag) cmap_size(map) #define CMAP_BUCKETS(tag) (map).bucket_count #define CMAP_CLEAR(tag) cmap_##tag##_destroy(&map) @@ -76,7 +76,7 @@ crandom_eng64_t rng; #define RMAP_FIND(tag, key) (map.find(key) != map.end()) #define RMAP_ERASE(tag, key) map.erase(key) #define RMAP_SIZE(tag) map.size() -#define RMAP_BUCKETS(tag) map.bucket_count() +#define RMAP_BUCKETS(tag) map.mask() #define RMAP_CLEAR(tag) map.clear() const size_t N1 = 10000000 * 5; diff --git a/examples/others/robin_hood.hpp b/examples/others/robin_hood.hpp index 48b21f21..2cf9e029 100644 --- a/examples/others/robin_hood.hpp +++ b/examples/others/robin_hood.hpp @@ -6,7 +6,7 @@ // _/_____/ // // Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20 -// version 3.6.0 +// version 3.8.1 // https://github.com/martinus/robin-hood-hashing // // Licensed under the MIT License . @@ -36,17 +36,21 @@ // see https://semver.org/ #define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes -#define ROBIN_HOOD_VERSION_MINOR 6 // for adding functionality in a backwards-compatible manner -#define ROBIN_HOOD_VERSION_PATCH 0 // for backwards-compatible bug fixes +#define ROBIN_HOOD_VERSION_MINOR 8 // for adding functionality in a backwards-compatible manner +#define ROBIN_HOOD_VERSION_PATCH 1 // for backwards-compatible bug fixes #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 @@ -128,7 +132,19 @@ static Counts& counts() { #endif // count leading/trailing bits -#ifdef _MSC_VER +#if ((defined __i386 || defined __x86_64__) && defined __BMI__) || defined _M_IX86 || defined _M_X64 +# ifdef _MSC_VER +# include +# else +# include +# endif +# if ROBIN_HOOD(BITNESS) == 32 +# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() _tzcnt_u32 +# else +# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() _tzcnt_u64 +# endif +# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ROBIN_HOOD(CTZ)(x) +#elif defined _MSC_VER # if ROBIN_HOOD(BITNESS) == 32 # define ROBIN_HOOD_PRIVATE_DEFINITION_BITSCANFORWARD() _BitScanForward # else @@ -175,6 +191,17 @@ static Counts& counts() { # 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 + // workaround missing "is_trivially_copyable" in g++ < 5.0 // See https://stackoverflow.com/a/31798726/48181 #if defined(__GNUC__) && __GNUC__ < 5 @@ -274,38 +301,10 @@ using index_sequence_for = make_index_sequence; namespace detail { -// umul -#if defined(__SIZEOF_INT128__) -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 1 -# if defined(__GNUC__) || defined(__clang__) -# pragma GCC diagnostic push -# pragma GCC diagnostic ignored "-Wpedantic" -using uint128_t = unsigned __int128; -# pragma GCC diagnostic pop -# endif -inline uint64_t umul128(uint64_t a, uint64_t b, uint64_t* high) noexcept { - auto result = static_cast(a) * static_cast(b); - *high = static_cast(result >> 64U); - return static_cast(result); -} -#elif (defined(_MSC_VER) && ROBIN_HOOD(BITNESS) == 64) -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 1 -# include // for __umulh -# pragma intrinsic(__umulh) -# ifndef _M_ARM64 -# pragma intrinsic(_umul128) -# endif -inline uint64_t umul128(uint64_t a, uint64_t b, uint64_t* high) noexcept { -# ifdef _M_ARM64 - *high = __umulh(a, b); - return ((uint64_t)(a)) * (b); -# else - return _umul128(a, b, high); -# endif +template +T rotr(T x, unsigned k) { + return (x >> k) | (x << (8U * sizeof(T) - k)); } -#else -# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 0 -#endif // 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 @@ -473,10 +472,10 @@ private: mListForFree = data; // create linked list for newly allocated data - auto const headT = + auto* const headT = reinterpret_cast_no_cast_align_warning(reinterpret_cast(ptr) + ALIGNMENT); - auto const head = reinterpret_cast(headT); + 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) { @@ -552,12 +551,18 @@ struct identity_hash { // 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 @@ -586,20 +591,19 @@ struct pair { , 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())))) + 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())))) + 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())))) + 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)) {} @@ -615,15 +619,12 @@ struct pair { // 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< - I2...> /*unused*/) noexcept(noexcept(T1(std:: - forward(std::get( - std::declval< - std::tuple&>()))...)) && - noexcept(T2(std::forward( - std::get(std::declval&>()))...))) + 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. @@ -658,7 +659,9 @@ inline constexpr bool operator!=(pair const& x, pair const& y) { return !(x == y); } template -inline constexpr bool operator<(pair const& x, pair const& y) { +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 @@ -674,14 +677,12 @@ inline constexpr bool operator>=(pair const& x, pair const& y) { return !(x < y); } -// Hash an arbitrary amount of bytes. This is basically Murmur2 hash without caring about big -// endianness. TODO(martinus) add a fallback for very large strings? -static size_t hash_bytes(void const* ptr, size_t const len) noexcept { +inline size_t hash_bytes(void const* ptr, size_t const 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 data64 = static_cast(ptr); + auto const* const data64 = static_cast(ptr); uint64_t h = seed ^ (len * m); size_t const n_blocks = len / 8; @@ -696,7 +697,7 @@ static size_t hash_bytes(void const* ptr, size_t const len) noexcept { h *= m; } - auto const data8 = reinterpret_cast(data64 + n_blocks); + auto const* const data8 = reinterpret_cast(data64 + n_blocks); switch (len & 7U) { case 7: h ^= static_cast(data8[6]) << 48U; @@ -730,28 +731,18 @@ static size_t hash_bytes(void const* ptr, size_t const len) noexcept { return static_cast(h); } -inline size_t hash_int(uint64_t obj) noexcept { -#if ROBIN_HOOD(HAS_UMUL128) - // 167079903232 masksum, 120428523 ops best: 0xde5fb9d2630458e9 - static constexpr uint64_t k = UINT64_C(0xde5fb9d2630458e9); - uint64_t h; - uint64_t l = detail::umul128(obj, k, &h); - return h + l; -#elif ROBIN_HOOD(BITNESS) == 32 - uint64_t const r = obj * UINT64_C(0xca4bcaa75ec3f625); - auto h = static_cast(r >> 32U); - auto l = static_cast(r); - return h + l; -#else - // murmurhash 3 finalizer - uint64_t h = obj; - h ^= h >> 33; - h *= 0xff51afd7ed558ccd; - h ^= h >> 33; - h *= 0xc4ceb9fe1a85ec53; - h ^= h >> 33; +inline size_t hash_int(uint64_t x) noexcept { + // inspired by lemire's strongly universal hashing + // https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/ + // + // Instead of shifts, we use rotations so we don't lose any bits. + // + // Added a final multiplcation with a constant for more mixing. It is most important that the + // lower bits are well mixed. + auto h1 = x * UINT64_C(0xA24BAED4963EE407); + auto h2 = detail::rotr(x, 32U) * UINT64_C(0x9FB21C651E98DF25); + auto h = detail::rotr(h1 + h2, 32U); return static_cast(h); -#endif } // A thin wrapper around std::hash, performing an additional simple mixing step of the result. @@ -766,13 +757,22 @@ struct hash : public std::hash { } }; -template <> -struct hash { - size_t operator()(std::string const& str) const noexcept { - return hash_bytes(str.data(), str.size()); +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 { @@ -780,10 +780,24 @@ struct hash { } }; +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())); + } +}; + #define ROBIN_HOOD_HASH_INT(T) \ template <> \ struct hash { \ - size_t operator()(T obj) const noexcept { \ + size_t operator()(T const& obj) const noexcept { \ return hash_int(static_cast(obj)); \ } \ } @@ -799,7 +813,9 @@ 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); @@ -813,8 +829,20 @@ ROBIN_HOOD_HASH_INT(unsigned long long); #endif namespace detail { -// 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 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; @@ -831,8 +859,8 @@ struct WrapKeyEqual : public T { // 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. +// 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: // @@ -840,8 +868,8 @@ struct WrapKeyEqual : public T { // // * 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. +// 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 @@ -849,12 +877,11 @@ struct WrapKeyEqual : public T { // 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. +// * 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. +// 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 @@ -870,6 +897,8 @@ 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; @@ -903,8 +932,8 @@ private: // 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. + // 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 {}; @@ -953,8 +982,8 @@ private: template ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() const - noexcept { + typename std::enable_if::type + getFirst() const noexcept { return mData.first; } template @@ -1036,8 +1065,8 @@ private: template ROBIN_HOOD(NODISCARD) - typename std::enable_if::type getFirst() const - noexcept { + typename std::enable_if::type + getFirst() const noexcept { return mData->first; } template @@ -1097,8 +1126,8 @@ private: template struct Cloner { void operator()(M const& source, M& target) const { - auto src = reinterpret_cast(source.mKeyVals); - auto tgt = reinterpret_cast(target.mKeyVals); + 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); } @@ -1186,8 +1215,8 @@ private: // 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. + // 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 (mInfo); + size_t n = 0; + while (0U == (n = detail::unaligned_load(mInfo))) { + mInfo += sizeof(size_t); + mKeyVals += sizeof(size_t); + } #if ROBIN_HOOD(LITTLE_ENDIAN) - inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8; + auto inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8; #else - inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8; + auto inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8; #endif - mInfo += inc; - mKeyVals += inc; - } while (inc == static_cast(sizeof(size_t))); + mInfo += inc; + mKeyVals += inc; } friend class Table; @@ -1270,9 +1308,9 @@ private: // 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 { - // for a user-specified hash that is *not* robin_hood::hash, apply robin_hood::hash as an - // additional mixing step. This serves as a bad hash prevention, if the given data is badly - // mixed. + // for a user-specified hash that is *not* robin_hood::hash, apply robin_hood::hash as + // an additional mixing step. This serves as a bad hash prevention, if the given data is + // badly mixed. using Mix = typename std::conditional, hasher>::value, ::robin_hood::detail::identity_hash, @@ -1308,7 +1346,7 @@ private: idx = startIdx; while (idx != insertion_idx) { - ROBIN_HOOD_COUNT(shiftUp); + ROBIN_HOOD_COUNT(shiftUp) mInfo[idx] = static_cast(mInfo[idx - 1] + mInfoInc); if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) { mMaxNumElementsAllowed = 0; @@ -1319,12 +1357,13 @@ private: 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. + // 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); + ROBIN_HOOD_COUNT(shiftDown) mInfo[idx] = static_cast(mInfo[idx + 1] - mInfoInc); mKeyVals[idx] = std::move(mKeyVals[idx + 1]); ++idx; @@ -1340,8 +1379,8 @@ private: template ROBIN_HOOD(NODISCARD) size_t findIdx(Other const& key) const { - size_t idx; - InfoType info; + size_t idx{}; + InfoType info{}; keyToIdx(key, &idx, &info); do { @@ -1377,8 +1416,8 @@ private: throwOverflowError(); // impossible to reach LCOV_EXCL_LINE } - size_t idx; - InfoType info; + size_t idx{}; + InfoType info{}; keyToIdx(keyval.getFirst(), &idx, &info); // skip forward. Use <= because we are certain that the element is not there. @@ -1418,17 +1457,17 @@ public: using iterator = Iter; using const_iterator = Iter; - // 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*/ = 0, const Hash& h = Hash{}, - const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && - noexcept(KeyEqual(equal))) + // 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*/ = 0, const Hash& h = Hash{}, + const KeyEqual& equal = KeyEqual{}) noexcept(noexcept(Hash(h)) && noexcept(KeyEqual(equal))) : WHash(h) , WKeyEqual(equal) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) } template @@ -1436,7 +1475,7 @@ public: const Hash& h = Hash{}, const KeyEqual& equal = KeyEqual{}) : WHash(h) , WKeyEqual(equal) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) insert(first, last); } @@ -1445,7 +1484,7 @@ public: const KeyEqual& equal = KeyEqual{}) : WHash(h) , WKeyEqual(equal) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) insert(initlist.begin(), initlist.end()); } @@ -1453,7 +1492,7 @@ public: : WHash(std::move(static_cast(o))) , WKeyEqual(std::move(static_cast(o))) , DataPool(std::move(static_cast(o))) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) if (o.mMask) { mKeyVals = std::move(o.mKeyVals); mInfo = std::move(o.mInfo); @@ -1468,7 +1507,7 @@ public: } Table& operator=(Table&& o) noexcept { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) if (&o != this) { if (o.mMask) { // only move stuff if the other map actually has some data @@ -1498,7 +1537,7 @@ public: : WHash(static_cast(o)) , WKeyEqual(static_cast(o)) , DataPool(static_cast(o)) { - ROBIN_HOOD_TRACE(this); + 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. @@ -1521,14 +1560,14 @@ public: // 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); + 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. + // 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 @@ -1579,17 +1618,17 @@ public: // Swaps everything between the two maps. void swap(Table& o) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) using std::swap; swap(o, *this); } // Clears all data, without resizing. void clear() { - ROBIN_HOOD_TRACE(this); + 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. + // 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; } @@ -1607,13 +1646,13 @@ public: // Destroys the map and all it's contents. ~Table() { - ROBIN_HOOD_TRACE(this); + 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); + ROBIN_HOOD_TRACE(this) if (other.size() != size()) { return false; } @@ -1627,19 +1666,19 @@ public: } bool operator!=(const Table& other) const { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return !operator==(other); } template typename std::enable_if::value, Q&>::type operator[](const key_type& key) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return doCreateByKey(key); } template typename std::enable_if::value, Q&>::type operator[](key_type&& key) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return doCreateByKey(std::move(key)); } @@ -1653,7 +1692,7 @@ public: template std::pair emplace(Args&&... args) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) Node n{*this, std::forward(args)...}; auto r = doInsert(std::move(n)); if (!r.second) { @@ -1664,8 +1703,54 @@ public: return r; } + 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 + std::pair try_emplace(const_iterator hint, const key_type& key, + Args&&... args) { + (void)hint; + return try_emplace_impl(key, std::forward(args)...); + } + + template + std::pair try_emplace(const_iterator hint, key_type&& key, Args&&... args) { + (void)hint; + return try_emplace_impl(std::move(key), std::forward(args)...); + } + + template + std::pair insert_or_assign(const key_type& key, Mapped&& obj) { + return insert_or_assign_impl(key, std::forward(obj)); + } + + template + std::pair insert_or_assign(key_type&& key, Mapped&& obj) { + return insert_or_assign_impl(std::move(key), std::forward(obj)); + } + + template + std::pair insert_or_assign(const_iterator hint, const key_type& key, + Mapped&& obj) { + (void)hint; + return insert_or_assign_impl(key, std::forward(obj)); + } + + template + std::pair insert_or_assign(const_iterator hint, key_type&& key, Mapped&& obj) { + (void)hint; + return insert_or_assign_impl(std::move(key), std::forward(obj)); + } + std::pair insert(const value_type& keyval) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return doInsert(keyval); } @@ -1675,7 +1760,18 @@ public: // Returns 1 if key is found, 0 otherwise. size_t count(const key_type& key) const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + 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; @@ -1687,12 +1783,18 @@ public: 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); + ROBIN_HOOD_TRACE(this) auto kv = mKeyVals + findIdx(key); if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { doThrow("key not found"); @@ -1705,7 +1807,7 @@ public: template // NOLINTNEXTLINE(modernize-use-nodiscard) typename std::enable_if::value, Q const&>::type at(key_type const& key) const { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) auto kv = mKeyVals + findIdx(key); if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { doThrow("key not found"); @@ -1714,44 +1816,60 @@ public: } const_iterator find(const key_type& key) const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + 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); + 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); + 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); + 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); + 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); + ROBIN_HOOD_TRACE(this) return cbegin(); } const_iterator cbegin() const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) if (empty()) { return cend(); } @@ -1759,22 +1877,22 @@ public: } iterator end() { - ROBIN_HOOD_TRACE(this); + 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); + ROBIN_HOOD_TRACE(this) return cend(); } const_iterator cend() const { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return const_iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; } iterator erase(const_iterator pos) { - ROBIN_HOOD_TRACE(this); + 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)}); @@ -1782,7 +1900,7 @@ public: // Erases element at pos, returns iterator to the next element. iterator erase(iterator pos) { - ROBIN_HOOD_TRACE(this); + 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); @@ -1799,9 +1917,9 @@ public: } size_t erase(const key_type& key) { - ROBIN_HOOD_TRACE(this); - size_t idx; - InfoType info; + ROBIN_HOOD_TRACE(this) + size_t idx{}; + InfoType info{}; keyToIdx(key, &idx, &info); // check while info matches with the source idx @@ -1827,7 +1945,7 @@ public: // reserves space for the specified number of elements. Makes sure the old data fits. // Exactly the same as resize(c). Use resize(0) to shrink to fit. void reserve(size_t c) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) auto const minElementsAllowed = (std::max)(c, mNumElements); auto newSize = InitialNumElements; while (calcMaxNumElementsAllowed(newSize) < minElementsAllowed && newSize != 0) { @@ -1841,39 +1959,33 @@ public: } size_type size() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return mNumElements; } - size_type bucket_count() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); - return mMaxNumElementsAllowed; - } - - size_type max_size() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return static_cast(-1); } ROBIN_HOOD(NODISCARD) bool empty() const noexcept { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return 0 == mNumElements; } float max_load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) - ROBIN_HOOD_TRACE(this); + 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); + ROBIN_HOOD_TRACE(this) return static_cast(size()) / static_cast(mMask + 1); } ROBIN_HOOD(NODISCARD) size_t mask() const noexcept { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return mMask; } @@ -1922,7 +2034,7 @@ private: template ROBIN_HOOD(NODISCARD) typename std::enable_if::value, bool>::type has(const value_type& e) const { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) auto it = find(e.first); return it != end() && it->second == e.second; } @@ -1930,14 +2042,14 @@ private: template ROBIN_HOOD(NODISCARD) typename std::enable_if::value, bool>::type has(const value_type& e) const { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) return find(e) != end(); } // reserves space for at least the specified number of elements. // only works if numBuckets if power of two void rehashPowerOfTwo(size_t numBuckets) { - ROBIN_HOOD_TRACE(this); + ROBIN_HOOD_TRACE(this) Node* const oldKeyVals = mKeyVals; uint8_t const* const oldInfo = mInfo; @@ -1968,6 +2080,29 @@ private: #endif } + template + std::pair try_emplace_impl(OtherKey&& key, Args&&... args) { + ROBIN_HOOD_TRACE(this) + auto it = find(key); + if (it == end()) { + return emplace(std::piecewise_construct, + std::forward_as_tuple(std::forward(key)), + std::forward_as_tuple(std::forward(args)...)); + } + return {it, false}; + } + + template + std::pair insert_or_assign_impl(OtherKey&& key, Mapped&& obj) { + ROBIN_HOOD_TRACE(this) + auto it = find(key); + if (it == end()) { + return emplace(std::forward(key), std::forward(obj)); + } + it->second = std::forward(obj); + return {it, false}; + } + void init_data(size_t max_elements) { mNumElements = 0; mMask = max_elements - 1; @@ -1990,13 +2125,13 @@ private: template typename std::enable_if::value, Q&>::type doCreateByKey(Arg&& key) { while (true) { - size_t idx; - InfoType info; + size_t idx{}; + InfoType info{}; keyToIdx(key, &idx, &info); nextWhileLess(&info, &idx); - // while we potentially have a match. Can't do a do-while here because when mInfo is 0 - // we don't want to skip forward + // while we potentially have a match. Can't do a do-while here because when mInfo is + // 0 we don't want to skip forward while (info == mInfo[idx]) { if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { // key already exists, do not insert. @@ -2025,8 +2160,8 @@ private: auto& l = mKeyVals[insertion_idx]; if (idx == insertion_idx) { - // put at empty spot. This forwards all arguments into the node where the object is - // constructed exactly where it is needed. + // put at empty spot. This forwards all arguments into the node where the object + // is constructed exactly where it is needed. ::new (static_cast(&l)) Node(*this, std::piecewise_construct, std::forward_as_tuple(std::forward(key)), std::forward_as_tuple()); @@ -2048,8 +2183,8 @@ private: template std::pair doInsert(Arg&& keyval) { while (true) { - size_t idx; - InfoType info; + size_t idx{}; + InfoType info{}; keyToIdx(getFirstConst(keyval), &idx, &info); nextWhileLess(&info, &idx); @@ -2101,7 +2236,7 @@ private: bool try_increase_info() { ROBIN_HOOD_LOG("mInfoInc=" << mInfoInc << ", numElements=" << mNumElements << ", maxNumElementsAllowed=" - << calcMaxNumElementsAllowed(mMask + 1)); + << calcMaxNumElementsAllowed(mMask + 1)) if (mInfoInc <= 2) { // need to be > 2 so that shift works (otherwise undefined behavior!) return false; @@ -2141,7 +2276,7 @@ private: ROBIN_HOOD_LOG("mNumElements=" << mNumElements << ", maxNumElementsAllowed=" << maxNumElementsAllowed << ", load=" << (static_cast(mNumElements) * 100.0 / - (static_cast(mMask) + 1))); + (static_cast(mMask) + 1))) // it seems we have a really bad hash function! don't try to resize again if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) { throwOverflowError(); @@ -2163,13 +2298,13 @@ private: // 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(&mMask)) { + if (mKeyVals != reinterpret_cast_no_cast_align_warning(&mMask)) { free(mKeyVals); } } void init() noexcept { - mKeyVals = reinterpret_cast(&mMask); + mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); mInfo = reinterpret_cast(&mMask); mNumElements = 0; mMask = 0; @@ -2179,14 +2314,14 @@ private: } // members are sorted so no padding occurs - Node* mKeyVals = reinterpret_cast(&mMask); // 8 byte 8 - uint8_t* mInfo = reinterpret_cast(&mMask); // 8 byte 16 - size_t mNumElements = 0; // 8 byte 24 - size_t mMask = 0; // 8 byte 32 - size_t mMaxNumElementsAllowed = 0; // 8 byte 40 - InfoType mInfoInc = InitialInfoInc; // 4 byte 44 - InfoType mInfoHashShift = InitialInfoHashShift; // 4 byte 48 - // 16 byte 56 if NodeAllocator + Node* mKeyVals = reinterpret_cast_no_cast_align_warning(&mMask); // 8 byte 8 + uint8_t* mInfo = reinterpret_cast(&mMask); // 8 byte 16 + size_t mNumElements = 0; // 8 byte 24 + size_t mMask = 0; // 8 byte 32 + size_t mMaxNumElementsAllowed = 0; // 8 byte 40 + InfoType mInfoInc = InitialInfoInc; // 4 byte 44 + InfoType mInfoHashShift = InitialInfoHashShift; // 4 byte 48 + // 16 byte 56 if NodeAllocator }; } // namespace detail diff --git a/stc/cbitset.h b/stc/cbitset.h index e021281c..8af4bfcb 100644 --- a/stc/cbitset.h +++ b/stc/cbitset.h @@ -165,9 +165,9 @@ STC_API void cbitset_resize(cbitset_t* self, size_t size, bool value) { #if defined(__GNUC__) || defined(__clang__) #define c_popcount64(x) __builtin_popcountll(x) -#elif defined(_MSC_VER) - #include - #define c_popcount64(x) _mm_popcnt_u64(x) +#elif defined(_MSC_VER) && defined(_WIN64) + #include + #define c_popcount64(x) __popcnt64(x) #else /* http://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation */ static inline uint64_t c_popcount64(uint64_t x) { -- cgit v1.2.3