diff options
| author | Tyge Løvset <[email protected]> | 2020-03-20 15:11:35 +0100 |
|---|---|---|
| committer | GitHub <[email protected]> | 2020-03-20 15:11:35 +0100 |
| commit | a65478b5d96723134399ea2aa5de35ed265e0f1d (patch) | |
| tree | a058a9a655d56625276759962ae89f4a1b4cb5f5 | |
| parent | 789e029f849f2925614749dfb5dd2bc00510db42 (diff) | |
| download | STC-modified-a65478b5d96723134399ea2aa5de35ed265e0f1d.tar.gz STC-modified-a65478b5d96723134399ea2aa5de35ed265e0f1d.zip | |
Add files via upload
| -rw-r--r-- | others/khash.h | 507 | ||||
| -rw-r--r-- | others/robin_hood.h | 2231 |
2 files changed, 2738 insertions, 0 deletions
diff --git a/others/khash.h b/others/khash.h new file mode 100644 index 00000000..200c3fe0 --- /dev/null +++ b/others/khash.h @@ -0,0 +1,507 @@ +/* The MIT License
+
+ Copyright (c) 2008, 2009 by attractor <[email protected]>
+
+ 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.
+*/
+
+/*
+ An example:
+
+#include "khash.h"
+KHASH_MAP_INIT_INT(32, char)
+int main() {
+ int ret, is_missing;
+ khiter_t k;
+ khash_t(32) *h = kh_init(32);
+ k = kh_put(32, h, 5, &ret);
+ if (!ret) kh_del(32, h, k);
+ kh_value(h, k) = 10;
+ k = kh_get(32, h, 10);
+ is_missing = (k == kh_end(h));
+ k = kh_get(32, h, 5);
+ kh_del(32, h, k);
+ for (k = kh_begin(h); k != kh_end(h); ++k)
+ if (kh_exist(h, k)) kh_value(h, k) = 1;
+ kh_destroy(32, h);
+ return 0;
+}
+*/
+
+/*
+ 2009-09-26 (0.2.4):
+
+ * Improve portability
+
+ 2008-09-19 (0.2.3):
+
+ * Corrected the example
+ * Improved interfaces
+
+ 2008-09-11 (0.2.2):
+
+ * Improved speed a little in kh_put()
+
+ 2008-09-10 (0.2.1):
+
+ * Added kh_clear()
+ * Fixed a compiling error
+
+ 2008-09-02 (0.2.0):
+
+ * Changed to token concatenation which increases flexibility.
+
+ 2008-08-31 (0.1.2):
+
+ * Fixed a bug in kh_get(), which has not been tested previously.
+
+ 2008-08-31 (0.1.1):
+
+ * Added destructor
+*/
+
+
+#ifndef __AC_KHASH_H
+#define __AC_KHASH_H
+
+/*!
+ @header
+
+ Generic hash table library.
+
+ @copyright Heng Li
+ */
+
+#define AC_VERSION_KHASH_H "0.2.4"
+
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+
+/* compipler specific configuration */
+
+#if UINT_MAX == 0xffffffffu
+typedef unsigned int khint32_t;
+#elif ULONG_MAX == 0xffffffffu
+typedef unsigned long khint32_t;
+#endif
+
+#if ULONG_MAX == ULLONG_MAX
+typedef unsigned long khint64_t;
+#else
+typedef unsigned long long khint64_t;
+#endif
+
+#ifdef _MSC_VER
+#define inline __inline
+#endif
+
+typedef khint32_t khint_t;
+typedef khint_t khiter_t;
+
+#define __ac_HASH_PRIME_SIZE 32
+static const khint32_t __ac_prime_list[__ac_HASH_PRIME_SIZE] =
+{
+ 0ul, 3ul, 11ul, 23ul, 53ul,
+ 97ul, 193ul, 389ul, 769ul, 1543ul,
+ 3079ul, 6151ul, 12289ul, 24593ul, 49157ul,
+ 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul,
+ 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul,
+ 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul,
+ 3221225473ul, 4294967291ul
+};
+
+#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
+#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
+#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
+#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
+#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
+#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
+#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
+
+static const double __ac_HASH_UPPER = 0.77;
+
+#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
+ typedef struct { \
+ khint_t n_buckets, size, n_occupied, upper_bound; \
+ khint32_t *flags; \
+ khkey_t *keys; \
+ khval_t *vals; \
+ } kh_##name##_t; \
+ static inline kh_##name##_t *kh_init_##name() { \
+ return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t)); \
+ } \
+ static inline void kh_destroy_##name(kh_##name##_t *h) \
+ { \
+ if (h) { \
+ free(h->keys); free(h->flags); \
+ free(h->vals); \
+ free(h); \
+ } \
+ } \
+ static inline void kh_clear_##name(kh_##name##_t *h) \
+ { \
+ if (h && h->flags) { \
+ memset(h->flags, 0xaa, ((h->n_buckets>>4) + 1) * sizeof(khint32_t)); \
+ h->size = h->n_occupied = 0; \
+ } \
+ } \
+ static inline khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \
+ { \
+ if (h->n_buckets) { \
+ khint_t inc, k, i, last; \
+ k = __hash_func(key); i = k % h->n_buckets; \
+ inc = 1 + k % (h->n_buckets - 1); last = i; \
+ while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
+ if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
+ else i += inc; \
+ if (i == last) return h->n_buckets; \
+ } \
+ return __ac_iseither(h->flags, i)? h->n_buckets : i; \
+ } else return 0; \
+ } \
+ static inline void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
+ { \
+ khint32_t *new_flags = 0; \
+ khint_t j = 1; \
+ { \
+ khint_t t = __ac_HASH_PRIME_SIZE - 1; \
+ while (__ac_prime_list[t] > new_n_buckets) --t; \
+ new_n_buckets = __ac_prime_list[t+1]; \
+ if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; \
+ else { \
+ new_flags = (khint32_t*)malloc(((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \
+ memset(new_flags, 0xaa, ((new_n_buckets>>4) + 1) * sizeof(khint32_t)); \
+ if (h->n_buckets < new_n_buckets) { \
+ h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
+ if (kh_is_map) \
+ h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
+ } \
+ } \
+ } \
+ if (j) { \
+ for (j = 0; j != h->n_buckets; ++j) { \
+ if (__ac_iseither(h->flags, j) == 0) { \
+ khkey_t key = h->keys[j]; \
+ khval_t val; \
+ if (kh_is_map) val = h->vals[j]; \
+ __ac_set_isdel_true(h->flags, j); \
+ while (1) { \
+ khint_t inc, k, i; \
+ k = __hash_func(key); \
+ i = k % new_n_buckets; \
+ inc = 1 + k % (new_n_buckets - 1); \
+ while (!__ac_isempty(new_flags, i)) { \
+ if (i + inc >= new_n_buckets) i = i + inc - new_n_buckets; \
+ else i += inc; \
+ } \
+ __ac_set_isempty_false(new_flags, i); \
+ if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \
+ { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
+ if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
+ __ac_set_isdel_true(h->flags, i); \
+ } else { \
+ h->keys[i] = key; \
+ if (kh_is_map) h->vals[i] = val; \
+ break; \
+ } \
+ } \
+ } \
+ } \
+ if (h->n_buckets > new_n_buckets) { \
+ h->keys = (khkey_t*)realloc(h->keys, new_n_buckets * sizeof(khkey_t)); \
+ if (kh_is_map) \
+ h->vals = (khval_t*)realloc(h->vals, new_n_buckets * sizeof(khval_t)); \
+ } \
+ free(h->flags); \
+ h->flags = new_flags; \
+ h->n_buckets = new_n_buckets; \
+ h->n_occupied = h->size; \
+ h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
+ } \
+ } \
+ static inline khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
+ { \
+ khint_t x; \
+ if (h->n_occupied >= h->upper_bound) { \
+ if (h->n_buckets > (h->size<<1)) kh_resize_##name(h, h->n_buckets - 1); \
+ else kh_resize_##name(h, h->n_buckets + 1); \
+ } \
+ { \
+ khint_t inc, k, i, site, last; \
+ x = site = h->n_buckets; k = __hash_func(key); i = k % h->n_buckets; \
+ if (__ac_isempty(h->flags, i)) x = i; \
+ else { \
+ inc = 1 + k % (h->n_buckets - 1); last = i; \
+ while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
+ if (__ac_isdel(h->flags, i)) site = i; \
+ if (i + inc >= h->n_buckets) i = i + inc - h->n_buckets; \
+ else i += inc; \
+ if (i == last) { x = site; break; } \
+ } \
+ if (x == h->n_buckets) { \
+ if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
+ else x = i; \
+ } \
+ } \
+ } \
+ if (__ac_isempty(h->flags, x)) { \
+ h->keys[x] = key; \
+ __ac_set_isboth_false(h->flags, x); \
+ ++h->size; ++h->n_occupied; \
+ *ret = 1; \
+ } else if (__ac_isdel(h->flags, x)) { \
+ h->keys[x] = key; \
+ __ac_set_isboth_false(h->flags, x); \
+ ++h->size; \
+ *ret = 2; \
+ } else *ret = 0; \
+ return x; \
+ } \
+ static inline void kh_del_##name(kh_##name##_t *h, khint_t x) \
+ { \
+ if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \
+ __ac_set_isdel_true(h->flags, x); \
+ --h->size; \
+ } \
+ }
+
+/* --- BEGIN OF HASH FUNCTIONS --- */
+
+/*! @function
+ @abstract Integer hash function
+ @param key The integer [khint32_t]
+ @return The hash value [khint_t]
+ */
+#define kh_int_hash_func(key) (khint32_t)(key)
+/*! @function
+ @abstract Integer comparison function
+ */
+#define kh_int_hash_equal(a, b) ((a) == (b))
+/*! @function
+ @abstract 64-bit integer hash function
+ @param key The integer [khint64_t]
+ @return The hash value [khint_t]
+ */
+#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
+/*! @function
+ @abstract 64-bit integer comparison function
+ */
+#define kh_int64_hash_equal(a, b) ((a) == (b))
+/*! @function
+ @abstract const char* hash function
+ @param s Pointer to a null terminated string
+ @return The hash value
+ */
+static inline khint_t __ac_X31_hash_string(const char *s)
+{
+ khint_t h = *s;
+ if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
+ return h;
+}
+/*! @function
+ @abstract Another interface to const char* hash function
+ @param key Pointer to a null terminated string [const char*]
+ @return The hash value [khint_t]
+ */
+#define kh_str_hash_func(key) __ac_X31_hash_string(key)
+/*! @function
+ @abstract Const char* comparison function
+ */
+#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
+
+/* --- END OF HASH FUNCTIONS --- */
+
+/* Other necessary macros... */
+
+/*!
+ @abstract Type of the hash table.
+ @param name Name of the hash table [symbol]
+ */
+#define khash_t(name) kh_##name##_t
+
+/*! @function
+ @abstract Initiate a hash table.
+ @param name Name of the hash table [symbol]
+ @return Pointer to the hash table [khash_t(name)*]
+ */
+#define kh_init(name) kh_init_##name()
+
+/*! @function
+ @abstract Destroy a hash table.
+ @param name Name of the hash table [symbol]
+ @param h Pointer to the hash table [khash_t(name)*]
+ */
+#define kh_destroy(name, h) kh_destroy_##name(h)
+
+/*! @function
+ @abstract Reset a hash table without deallocating memory.
+ @param name Name of the hash table [symbol]
+ @param h Pointer to the hash table [khash_t(name)*]
+ */
+#define kh_clear(name, h) kh_clear_##name(h)
+
+/*! @function
+ @abstract Resize a hash table.
+ @param name Name of the hash table [symbol]
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param s New size [khint_t]
+ */
+#define kh_resize(name, h, s) kh_resize_##name(h, s)
+
+/*! @function
+ @abstract Insert a key to the hash table.
+ @param name Name of the hash table [symbol]
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param k Key [type of keys]
+ @param r Extra return code: 0 if the key is present in the hash table;
+ 1 if the bucket is empty (never used); 2 if the element in
+ the bucket has been deleted [int*]
+ @return Iterator to the inserted element [khint_t]
+ */
+#define kh_put(name, h, k, r) kh_put_##name(h, k, r)
+
+/*! @function
+ @abstract Retrieve a key from the hash table.
+ @param name Name of the hash table [symbol]
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param k Key [type of keys]
+ @return Iterator to the found element, or kh_end(h) is the element is absent [khint_t]
+ */
+#define kh_get(name, h, k) kh_get_##name(h, k)
+
+/*! @function
+ @abstract Remove a key from the hash table.
+ @param name Name of the hash table [symbol]
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param k Iterator to the element to be deleted [khint_t]
+ */
+#define kh_del(name, h, k) kh_del_##name(h, k)
+
+
+/*! @function
+ @abstract Test whether a bucket contains data.
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param x Iterator to the bucket [khint_t]
+ @return 1 if containing data; 0 otherwise [int]
+ */
+#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
+
+/*! @function
+ @abstract Get key given an iterator
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param x Iterator to the bucket [khint_t]
+ @return Key [type of keys]
+ */
+#define kh_key(h, x) ((h)->keys[x])
+
+/*! @function
+ @abstract Get value given an iterator
+ @param h Pointer to the hash table [khash_t(name)*]
+ @param x Iterator to the bucket [khint_t]
+ @return Value [type of values]
+ @discussion For hash sets, calling this results in segfault.
+ */
+#define kh_val(h, x) ((h)->vals[x])
+
+/*! @function
+ @abstract Alias of kh_val()
+ */
+#define kh_value(h, x) ((h)->vals[x])
+
+/*! @function
+ @abstract Get the start iterator
+ @param h Pointer to the hash table [khash_t(name)*]
+ @return The start iterator [khint_t]
+ */
+#define kh_begin(h) (khint_t)(0)
+
+/*! @function
+ @abstract Get the end iterator
+ @param h Pointer to the hash table [khash_t(name)*]
+ @return The end iterator [khint_t]
+ */
+#define kh_end(h) ((h)->n_buckets)
+
+/*! @function
+ @abstract Get the number of elements in the hash table
+ @param h Pointer to the hash table [khash_t(name)*]
+ @return Number of elements in the hash table [khint_t]
+ */
+#define kh_size(h) ((h)->size)
+
+/*! @function
+ @abstract Get the number of buckets in the hash table
+ @param h Pointer to the hash table [khash_t(name)*]
+ @return Number of buckets in the hash table [khint_t]
+ */
+#define kh_n_buckets(h) ((h)->n_buckets)
+
+/* More conenient interfaces */
+
+/*! @function
+ @abstract Instantiate a hash set containing integer keys
+ @param name Name of the hash table [symbol]
+ */
+#define KHASH_SET_INIT_INT(name) \
+ KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
+
+/*! @function
+ @abstract Instantiate a hash map containing integer keys
+ @param name Name of the hash table [symbol]
+ @param khval_t Type of values [type]
+ */
+#define KHASH_MAP_INIT_INT(name, khval_t) \
+ KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
+
+/*! @function
+ @abstract Instantiate a hash map containing 64-bit integer keys
+ @param name Name of the hash table [symbol]
+ */
+#define KHASH_SET_INIT_INT64(name) \
+ KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
+
+/*! @function
+ @abstract Instantiate a hash map containing 64-bit integer keys
+ @param name Name of the hash table [symbol]
+ @param khval_t Type of values [type]
+ */
+#define KHASH_MAP_INIT_INT64(name, khval_t) \
+ KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
+
+typedef const char *kh_cstr_t;
+/*! @function
+ @abstract Instantiate a hash map containing const char* keys
+ @param name Name of the hash table [symbol]
+ */
+#define KHASH_SET_INIT_STR(name) \
+ KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
+
+/*! @function
+ @abstract Instantiate a hash map containing const char* keys
+ @param name Name of the hash table [symbol]
+ @param khval_t Type of values [type]
+ */
+#define KHASH_MAP_INIT_STR(name, khval_t) \
+ KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
+
+#endif /* __AC_KHASH_H */
+
diff --git a/others/robin_hood.h b/others/robin_hood.h new file mode 100644 index 00000000..288864b6 --- /dev/null +++ b/others/robin_hood.h @@ -0,0 +1,2231 @@ +// ______ _____ ______ _________
+// ______________ ___ /_ ___(_)_______ ___ /_ ______ ______ ______ /
+// __ ___/_ __ \__ __ \__ / __ __ \ __ __ \_ __ \_ __ \_ __ /
+// _ / / /_/ /_ /_/ /_ / _ / / / _ / / // /_/ // /_/ // /_/ /
+// /_/ \____/ /_.___/ /_/ /_/ /_/ ________/_/ /_/ \____/ \____/ \__,_/
+// _/_____/
+//
+// Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
+// version 3.6.0
+// https://github.com/martinus/robin-hood-hashing
+//
+// Licensed under the MIT License <http://opensource.org/licenses/MIT>.
+// SPDX-License-Identifier: MIT
+// Copyright (c) 2018-2020 Martin Ankerl <http://martin.ankerl.com>
+//
+// 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 6 // for adding functionality in a backwards-compatible manner
+#define ROBIN_HOOD_VERSION_PATCH 0 // for backwards-compatible bug fixes
+
+#include <algorithm>
+#include <cstdlib>
+#include <cstring>
+#include <functional>
+#include <stdexcept>
+#include <string>
+#include <type_traits>
+#include <utility>
+
+// #define ROBIN_HOOD_LOG_ENABLED
+#ifdef ROBIN_HOOD_LOG_ENABLED
+# include <iostream>
+# define ROBIN_HOOD_LOG(x) std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << x << std::endl
+#else
+# define ROBIN_HOOD_LOG(x)
+#endif
+
+// #define ROBIN_HOOD_TRACE_ENABLED
+#ifdef ROBIN_HOOD_TRACE_ENABLED
+# include <iostream>
+# define ROBIN_HOOD_TRACE(x) \
+ std::cout << __FUNCTION__ << "@" << __LINE__ << ": " << x << std::endl
+#else
+# define ROBIN_HOOD_TRACE(x)
+#endif
+
+// #define ROBIN_HOOD_COUNT_ENABLED
+#ifdef ROBIN_HOOD_COUNT_ENABLED
+# include <iostream>
+# 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
+#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 <intrin.h>
+# 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<int>(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
+
+// 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
+
+// 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 <class T>
+struct alignment_of
+ : std::integral_constant<std::size_t, alignof(typename std::remove_all_extents<T>::type)> {};
+
+template <class T, T... Ints>
+class integer_sequence {
+public:
+ using value_type = T;
+ static_assert(std::is_integral<value_type>::value, "not integral type");
+ static constexpr std::size_t size() noexcept {
+ return sizeof...(Ints);
+ }
+};
+template <std::size_t... Inds>
+using index_sequence = integer_sequence<std::size_t, Inds...>;
+
+namespace detail_ {
+template <class T, T Begin, T End, bool>
+struct IntSeqImpl {
+ using TValue = T;
+ static_assert(std::is_integral<TValue>::value, "not integral type");
+ static_assert(Begin >= 0 && Begin < End, "unexpected argument (Begin<0 || Begin<=End)");
+
+ template <class, class>
+ struct IntSeqCombiner;
+
+ template <TValue... Inds0, TValue... Inds1>
+ struct IntSeqCombiner<integer_sequence<TValue, Inds0...>, integer_sequence<TValue, Inds1...>> {
+ using TResult = integer_sequence<TValue, Inds0..., Inds1...>;
+ };
+
+ using TResult =
+ typename IntSeqCombiner<typename IntSeqImpl<TValue, Begin, Begin + (End - Begin) / 2,
+ (End - Begin) / 2 == 1>::TResult,
+ typename IntSeqImpl<TValue, Begin + (End - Begin) / 2, End,
+ (End - Begin + 1) / 2 == 1>::TResult>::TResult;
+};
+
+template <class T, T Begin>
+struct IntSeqImpl<T, Begin, Begin, false> {
+ using TValue = T;
+ static_assert(std::is_integral<TValue>::value, "not integral type");
+ static_assert(Begin >= 0, "unexpected argument (Begin<0)");
+ using TResult = integer_sequence<TValue>;
+};
+
+template <class T, T Begin, T End>
+struct IntSeqImpl<T, Begin, End, true> {
+ using TValue = T;
+ static_assert(std::is_integral<TValue>::value, "not integral type");
+ static_assert(Begin >= 0, "unexpected argument (Begin<0)");
+ using TResult = integer_sequence<TValue, Begin>;
+};
+} // namespace detail_
+
+template <class T, T N>
+using make_integer_sequence = typename detail_::IntSeqImpl<T, 0, N, (N - 0) == 1>::TResult;
+
+template <std::size_t N>
+using make_index_sequence = make_integer_sequence<std::size_t, N>;
+
+template <class... T>
+using index_sequence_for = make_index_sequence<sizeof...(T)>;
+
+} // namespace ROBIN_HOOD_STD
+
+#endif
+
+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<uint128_t>(a) * static_cast<uint128_t>(b);
+ *high = static_cast<uint64_t>(result >> 64U);
+ return static_cast<uint64_t>(result);
+}
+#elif (defined(_MSC_VER) && ROBIN_HOOD(BITNESS) == 64)
+# define ROBIN_HOOD_PRIVATE_DEFINITION_HAS_UMUL128() 1
+# include <intrin.h> // 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
+}
+#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
+// care!
+template <typename T>
+inline T reinterpret_cast_no_cast_align_warning(void* ptr) noexcept {
+ return reinterpret_cast<T>(ptr);
+}
+
+template <typename T>
+inline T reinterpret_cast_no_cast_align_warning(void const* ptr) noexcept {
+ return reinterpret_cast<T>(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 <typename E, typename... Args>
+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>(args)...);
+}
+#else
+void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) /*unused*/) {
+ abort();
+}
+#endif
+
+template <typename E, typename T, typename... Args>
+T* assertNotNull(T* t, Args&&... args) {
+ if (ROBIN_HOOD_UNLIKELY(nullptr == t)) {
+ doThrow<E>(std::forward<Args>(args)...);
+ }
+ return t;
+}
+
+template <typename T>
+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 <typename T, size_t MinNumAllocs = 4, size_t MaxNumAllocs = 256>
+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;
+ free(mListForFree);
+ mListForFree = reinterpret_cast_no_cast_align_warning<T**>(tmp);
+ }
+ mHead = nullptr;
+ }
+
+ // allocates, but does NOT initialize. Use in-place new constructor, e.g.
+ // T* obj = pool.allocate();
+ // ::new (static_cast<void*>(obj)) T();
+ T* allocate() {
+ T* tmp = mHead;
+ if (!tmp) {
+ tmp = performAllocation();
+ }
+
+ mHead = *reinterpret_cast_no_cast_align_warning<T**>(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<T**>(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.
+ free(ptr);
+ } else {
+ add(ptr, numBytes);
+ }
+ }
+
+ void swap(BulkPoolAllocator<T, MinNumAllocs, MaxNumAllocs>& 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<T***>(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<T**>(ptr);
+
+ // link free list
+ auto x = reinterpret_cast<T***>(data);
+ *x = mListForFree;
+ mListForFree = data;
+
+ // create linked list for newly allocated data
+ auto const headT =
+ reinterpret_cast_no_cast_align_warning<T*>(reinterpret_cast<char*>(ptr) + ALIGNMENT);
+
+ auto const head = reinterpret_cast<char*>(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<char**>(head + i * ALIGNED_SIZE) =
+ head + (i + 1) * ALIGNED_SIZE;
+ }
+
+ // last one points to 0
+ *reinterpret_cast_no_cast_align_warning<T**>(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]
+ // std::cout << (sizeof(T*) + ALIGNED_SIZE * numElementsToAlloc) << " bytes" << std::endl;
+ size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc;
+ add(assertNotNull<std::bad_alloc>(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<T>::value, std::alignment_of<T*>::value);
+#else
+ static const size_t ALIGNMENT =
+ (ROBIN_HOOD_STD::alignment_of<T>::value > ROBIN_HOOD_STD::alignment_of<T*>::value)
+ ? ROBIN_HOOD_STD::alignment_of<T>::value
+ : +ROBIN_HOOD_STD::alignment_of<T*>::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 <typename T, size_t MinSize, size_t MaxSize, bool IsFlat>
+struct NodeAllocator;
+
+// dummy allocator that does nothing
+template <typename T, size_t MinSize, size_t MaxSize>
+struct NodeAllocator<T, MinSize, MaxSize, true> {
+
+ // we are not using the data, so just free it.
+ void addOrFree(void* ptr, size_t ROBIN_HOOD_UNUSED(numBytes) /*unused*/) noexcept {
+ free(ptr);
+ }
+};
+
+template <typename T, size_t MinSize, size_t MaxSize>
+struct NodeAllocator<T, MinSize, MaxSize, false> : public BulkPoolAllocator<T, MinSize, MaxSize> {};
+
+// dummy hash, unsed as mixer when robin_hood::hash is already used
+template <typename T>
+struct identity_hash {
+ constexpr size_t operator()(T const& obj) const noexcept {
+ return static_cast<size_t>(obj);
+ }
+};
+
+// 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 {
+using std::swap;
+template <typename T>
+struct nothrow {
+ static const bool value = noexcept(swap(std::declval<T&>(), std::declval<T&>()));
+};
+
+} // 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 <typename T1, typename T2>
+struct pair {
+ using first_type = T1;
+ using second_type = T2;
+
+ template <typename U1 = T1, typename U2 = T2,
+ typename = typename std::enable_if<std::is_default_constructible<U1>::value &&
+ std::is_default_constructible<U2>::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<T1, T2> const& o) noexcept(
+ noexcept(T1(std::declval<T1 const&>())) && noexcept(T2(std::declval<T2 const&>())))
+ : 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<T1, T2>&& o) noexcept(
+ noexcept(T1(std::move(std::declval<T1&&>()))) &&
+ noexcept(T2(std::move(std::declval<T2&&>()))))
+ : first(std::move(o.first))
+ , second(std::move(o.second)) {}
+
+ constexpr pair(T1&& a, T2&& b) noexcept(noexcept(T1(std::move(std::declval<T1&&>()))) &&
+ noexcept(T2(std::move(std::declval<T2&&>()))))
+ : first(std::move(a))
+ , second(std::move(b)) {}
+
+ template <typename U1, typename U2>
+ constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward<U1>(std::declval<U1&&>()))) &&
+ noexcept(T2(std::forward<U2>(std::declval<U2&&>()))))
+ : first(std::forward<U1>(a))
+ , second(std::forward<U2>(b)) {}
+
+ template <typename... U1, typename... U2>
+ constexpr pair(
+ std::piecewise_construct_t /*unused*/, std::tuple<U1...> a,
+ std::tuple<U2...> b) noexcept(noexcept(pair(std::declval<std::tuple<U1...>&>(),
+ std::declval<std::tuple<U2...>&>(),
+ ROBIN_HOOD_STD::index_sequence_for<U1...>(),
+ ROBIN_HOOD_STD::index_sequence_for<U2...>())))
+ : pair(a, b, ROBIN_HOOD_STD::index_sequence_for<U1...>(),
+ ROBIN_HOOD_STD::index_sequence_for<U2...>()) {}
+
+ // constructor called from the std::piecewise_construct_t ctor
+ template <typename... U1, size_t... I1, typename... U2, size_t... I2>
+ pair(std::tuple<U1...>& a, std::tuple<U2...>& b,
+ ROBIN_HOOD_STD::index_sequence<I1...> /*unused*/,
+ ROBIN_HOOD_STD::index_sequence<
+ I2...> /*unused*/) noexcept(noexcept(T1(std::
+ forward<U1>(std::get<I1>(
+ std::declval<
+ std::tuple<U1...>&>()))...)) &&
+ noexcept(T2(std::forward<U2>(
+ std::get<I2>(std::declval<std::tuple<U2...>&>()))...)))
+ : first(std::forward<U1>(std::get<I1>(a))...)
+ , second(std::forward<U2>(std::get<I2>(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<T1, T2>& o) noexcept((detail::swappable::nothrow<T1>::value) &&
+ (detail::swappable::nothrow<T2>::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 <typename A, typename B>
+inline void swap(pair<A, B>& a, pair<A, B>& b) noexcept(
+ noexcept(std::declval<pair<A, B>&>().swap(std::declval<pair<A, B>&>()))) {
+ a.swap(b);
+}
+
+template <typename A, typename B>
+inline constexpr bool operator==(pair<A, B> const& x, pair<A, B> const& y) {
+ return (x.first == y.first) && (x.second == y.second);
+}
+template <typename A, typename B>
+inline constexpr bool operator!=(pair<A, B> const& x, pair<A, B> const& y) {
+ return !(x == y);
+}
+template <typename A, typename B>
+inline constexpr bool operator<(pair<A, B> const& x, pair<A, B> const& y) {
+ return x.first < y.first || (!(y.first < x.first) && x.second < y.second);
+}
+template <typename A, typename B>
+inline constexpr bool operator>(pair<A, B> const& x, pair<A, B> const& y) {
+ return y < x;
+}
+template <typename A, typename B>
+inline constexpr bool operator<=(pair<A, B> const& x, pair<A, B> const& y) {
+ return !(x > y);
+}
+template <typename A, typename B>
+inline constexpr bool operator>=(pair<A, B> const& x, pair<A, B> 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 {
+ 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<uint64_t const*>(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<uint64_t>(data64 + i);
+
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+
+ h ^= k;
+ h *= m;
+ }
+
+ auto const data8 = reinterpret_cast<uint8_t const*>(data64 + n_blocks);
+ switch (len & 7U) {
+ case 7:
+ h ^= static_cast<uint64_t>(data8[6]) << 48U;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ case 6:
+ h ^= static_cast<uint64_t>(data8[5]) << 40U;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ case 5:
+ h ^= static_cast<uint64_t>(data8[4]) << 32U;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ case 4:
+ h ^= static_cast<uint64_t>(data8[3]) << 24U;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ case 3:
+ h ^= static_cast<uint64_t>(data8[2]) << 16U;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ case 2:
+ h ^= static_cast<uint64_t>(data8[1]) << 8U;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ case 1:
+ h ^= static_cast<uint64_t>(data8[0]);
+ h *= m;
+ ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH
+ default:
+ break;
+ }
+
+ h ^= h >> r;
+ h *= m;
+ h ^= h >> r;
+ return static_cast<size_t>(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<uint32_t>(r >> 32U);
+ auto l = static_cast<uint32_t>(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;
+ return static_cast<size_t>(h);
+#endif
+}
+
+// A thin wrapper around std::hash, performing an additional simple mixing step of the result.
+template <typename T>
+struct hash : public std::hash<T> {
+ size_t operator()(T const& obj) const
+ noexcept(noexcept(std::declval<std::hash<T>>().operator()(std::declval<T const&>()))) {
+ // call base hash
+ auto result = std::hash<T>::operator()(obj);
+ // return mixed of that, to be save against identity has
+ return hash_int(static_cast<uint64_t>(result));
+ }
+};
+
+template <>
+struct hash<std::string> {
+ size_t operator()(std::string const& str) const noexcept {
+ return hash_bytes(str.data(), str.size());
+ }
+};
+
+template <class T>
+struct hash<T*> {
+ size_t operator()(T* ptr) const noexcept {
+ return hash_int(reinterpret_cast<size_t>(ptr));
+ }
+};
+
+#define ROBIN_HOOD_HASH_INT(T) \
+ template <> \
+ struct hash<T> { \
+ size_t operator()(T obj) const noexcept { \
+ return hash_int(static_cast<uint64_t>(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);
+ROBIN_HOOD_HASH_INT(wchar_t);
+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 {
+
+// 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 <typename T>
+struct WrapHash : public T {
+ WrapHash() = default;
+ explicit WrapHash(T const& o) noexcept(noexcept(T(std::declval<T const&>())))
+ : T(o) {}
+};
+
+template <typename T>
+struct WrapKeyEqual : public T {
+ WrapKeyEqual() = default;
+ explicit WrapKeyEqual(T const& o) noexcept(noexcept(T(std::declval<T const&>())))
+ : 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<key, val> as member,
+// or a DataNode with a pointer to std::pair<key,val>. 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 <bool IsFlat, size_t MaxLoadFactor100, typename Key, typename T, typename Hash,
+ typename KeyEqual>
+class Table
+ : public WrapHash<Hash>,
+ public WrapKeyEqual<KeyEqual>,
+ detail::NodeAllocator<
+ typename std::conditional<
+ std::is_void<T>::value, Key,
+ robin_hood::pair<typename std::conditional<IsFlat, Key, Key const>::type, T>>::type,
+ 4, 16384, IsFlat> {
+public:
+ static constexpr bool is_flat = IsFlat;
+ static constexpr bool is_map = !std::is_void<T>::value;
+ static constexpr bool is_set = !is_map;
+
+ using key_type = Key;
+ using mapped_type = T;
+ using value_type = typename std::conditional<
+ is_set, Key,
+ robin_hood::pair<typename std::conditional<is_flat, Key, Key const>::type, T>>::type;
+ using size_type = size_t;
+ using hasher = Hash;
+ using key_equal = KeyEqual;
+ using Self = Table<IsFlat, MaxLoadFactor100, key_type, mapped_type, hasher, key_equal>;
+
+private:
+ static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100,
+ "MaxLoadFactor100 needs to be >10 && < 100");
+
+ using WHash = WrapHash<Hash>;
+ using WKeyEqual = WrapKeyEqual<KeyEqual>;
+
+ // 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 uint8_t InitialInfoHashShift = sizeof(size_t) * 8 - InitialInfoNumBits;
+ using DataPool = detail::NodeAllocator<value_type, 4, 16384, IsFlat>;
+
+ // 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 <typename M, bool>
+ class DataNode {};
+
+ // Small: just allocate on the stack.
+ template <typename M>
+ class DataNode<M, true> final {
+ public:
+ template <typename... Args>
+ explicit DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, Args&&... args) noexcept(
+ noexcept(value_type(std::forward<Args>(args)...)))
+ : mData(std::forward<Args>(args)...) {}
+
+ DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode<M, true>&& n) noexcept(
+ std::is_nothrow_move_constructible<value_type>::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 <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, typename VT::first_type&>::type getFirst() noexcept {
+ return mData.first;
+ }
+ template <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_set, VT&>::type getFirst() noexcept {
+ return mData;
+ }
+
+ template <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, typename VT::first_type const&>::type getFirst() const
+ noexcept {
+ return mData.first;
+ }
+ template <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_set, VT const&>::type getFirst() const noexcept {
+ return mData;
+ }
+
+ template <typename MT = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, MT&>::type getSecond() noexcept {
+ return mData.second;
+ }
+
+ template <typename MT = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_set, MT const&>::type getSecond() const noexcept {
+ return mData.second;
+ }
+
+ void swap(DataNode<M, true>& o) noexcept(
+ noexcept(std::declval<value_type>().swap(std::declval<value_type>()))) {
+ mData.swap(o.mData);
+ }
+
+ private:
+ value_type mData;
+ };
+
+ // big object: allocate on heap.
+ template <typename M>
+ class DataNode<M, false> {
+ public:
+ template <typename... Args>
+ explicit DataNode(M& map, Args&&... args)
+ : mData(map.allocate()) {
+ ::new (static_cast<void*>(mData)) value_type(std::forward<Args>(args)...);
+ }
+
+ DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode<M, false>&& 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 <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, typename VT::first_type&>::type getFirst() noexcept {
+ return mData->first;
+ }
+ template <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_set, VT&>::type getFirst() noexcept {
+ return *mData;
+ }
+
+ template <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, typename VT::first_type const&>::type getFirst() const
+ noexcept {
+ return mData->first;
+ }
+ template <typename VT = value_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_set, VT const&>::type getFirst() const noexcept {
+ return *mData;
+ }
+
+ template <typename MT = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, MT&>::type getSecond() noexcept {
+ return mData->second;
+ }
+
+ template <typename MT = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<is_map, MT const&>::type getSecond() const noexcept {
+ return mData->second;
+ }
+
+ void swap(DataNode<M, false>& o) noexcept {
+ using std::swap;
+ swap(mData, o.mData);
+ }
+
+ private:
+ value_type* mData;
+ };
+
+ using Node = DataNode<Self, IsFlat>;
+
+ // helpers for doInsert: 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 <typename Q = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<!std::is_void<Q>::value, key_type const&>::type
+ getFirstConst(value_type const& vt) const noexcept {
+ return vt.first;
+ }
+
+ // Cloner //////////////////////////////////////////////////////////
+
+ template <typename M, bool UseMemcpy>
+ struct Cloner;
+
+ // fast path: Just copy data, without allocating anything.
+ template <typename M>
+ struct Cloner<M, true> {
+ void operator()(M const& source, M& target) const {
+ auto src = reinterpret_cast<char const*>(source.mKeyVals);
+ auto tgt = reinterpret_cast<char*>(target.mKeyVals);
+ auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1);
+ std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt);
+ }
+ };
+
+ template <typename M>
+ struct Cloner<M, false> {
+ 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<void*>(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]);
+ }
+ }
+ }
+ };
+
+ // Destroyer ///////////////////////////////////////////////////////
+
+ template <typename M, bool IsFlatAndTrivial>
+ struct Destroyer {};
+
+ template <typename M>
+ struct Destroyer<M, true> {
+ void nodes(M& m) const noexcept {
+ m.mNumElements = 0;
+ }
+
+ void nodesDoNotDeallocate(M& m) const noexcept {
+ m.mNumElements = 0;
+ }
+ };
+
+ template <typename M>
+ struct Destroyer<M, false> {
+ 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 <bool IsConst>
+ // NOLINTNEXTLINE(hicpp-special-member-functions,cppcoreguidelines-special-member-functions)
+ class Iter {
+ private:
+ using NodePtr = typename std::conditional<IsConst, Node const*, Node*>::type;
+
+ public:
+ using difference_type = std::ptrdiff_t;
+ using value_type = typename Self::value_type;
+ using reference = typename std::conditional<IsConst, value_type const&, value_type&>::type;
+ using pointer = typename std::conditional<IsConst, value_type const*, value_type*>::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 <bool OtherIsConst,
+ typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
+ // NOLINTNEXTLINE(hicpp-explicit-conversions)
+ Iter(Iter<OtherIsConst> 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 <bool OtherIsConst,
+ typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
+ Iter& operator=(Iter<OtherIsConst> 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;
+ }
+
+ reference operator*() const {
+ return **mKeyVals;
+ }
+
+ pointer operator->() const {
+ return &**mKeyVals;
+ }
+
+ template <bool O>
+ bool operator==(Iter<O> const& o) const noexcept {
+ return mKeyVals == o.mKeyVals;
+ }
+
+ template <bool O>
+ bool operator!=(Iter<O> const& o) const noexcept {
+ return mKeyVals != o.mKeyVals;
+ }
+
+ private:
+ // fast forward to the next non-free info byte
+ void fastForward() noexcept {
+ int inc;
+ do {
+ auto const n = detail::unaligned_load<size_t>(mInfo);
+#if ROBIN_HOOD(LITTLE_ENDIAN)
+ inc = ROBIN_HOOD_COUNT_TRAILING_ZEROES(n) / 8;
+#else
+ inc = ROBIN_HOOD_COUNT_LEADING_ZEROES(n) / 8;
+#endif
+ mInfo += inc;
+ mKeyVals += inc;
+ } while (inc == static_cast<int>(sizeof(size_t)));
+ }
+
+ friend class Table<IsFlat, MaxLoadFactor100, key_type, mapped_type, hasher, key_equal>;
+ 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 <typename HashKey>
+ 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.
+ using Mix =
+ typename std::conditional<std::is_same<::robin_hood::hash<key_type>, hasher>::value,
+ ::robin_hood::detail::identity_hash<size_t>,
+ ::robin_hood::hash<size_t>>::type;
+ *idx = Mix{}(WHash::operator()(key));
+
+ *info = mInfoInc + static_cast<InfoType>(*idx >> mInfoHashShift);
+ *idx &= 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<Node>::value) {
+ auto idx = startIdx;
+ ::new (static_cast<void*>(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<uint8_t>(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<Node>::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<uint8_t>(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 <typename Other>
+ 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<size_t>(std::distance(
+ mKeyVals, reinterpret_cast_no_cast_align_warning<Node*>(mInfo)));
+ }
+
+ void cloneData(const Table& o) {
+ Cloner<Table, IsFlat && ROBIN_HOOD_IS_TRIVIALLY_COPYABLE(Node)>()(o, *this);
+ }
+
+ // inserts a keyval that is guaranteed to be new, e.g. when the hashmap is resized.
+ // @return index where the element was created
+ size_t 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(); // impossible to reach LCOV_EXCL_LINE
+ }
+
+ 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<uint8_t>(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<void*>(&l)) Node(std::move(keyval));
+ } else {
+ shiftUp(idx, insertion_idx);
+ l = std::move(keyval);
+ }
+
+ // put at empty spot
+ mInfo[insertion_idx] = insertion_info;
+
+ ++mNumElements;
+ return insertion_idx;
+ }
+
+public:
+ using iterator = Iter<false>;
+ using const_iterator = Iter<true>;
+
+ // 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);
+ }
+
+ template <typename Iter>
+ 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<value_type> 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<WHash&>(o)))
+ , WKeyEqual(std::move(static_cast<WKeyEqual&>(o)))
+ , DataPool(std::move(static_cast<DataPool&>(o))) {
+ ROBIN_HOOD_TRACE(this);
+ if (o.mMask) {
+ 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();
+ 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<WHash&>(o)));
+ WKeyEqual::operator=(std::move(static_cast<WKeyEqual&>(o)));
+ DataPool::operator=(std::move(static_cast<DataPool&>(o)));
+
+ o.init();
+
+ } else {
+ // nothing in the other map => just clear us.
+ clear();
+ }
+ }
+ return *this;
+ }
+
+ Table(const Table& o)
+ : WHash(static_cast<const WHash&>(o))
+ , WKeyEqual(static_cast<const WKeyEqual&>(o))
+ , DataPool(static_cast<const DataPool&>(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);
+ mKeyVals = static_cast<Node*>(detail::assertNotNull<std::bad_alloc>(
+ malloc(calcNumBytesTotal(numElementsWithBuffer))));
+ // no need for calloc because clonData does memcpy
+ mInfo = reinterpret_cast<uint8_t*>(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<const WHash&>(o));
+ WKeyEqual::operator=(static_cast<const WKeyEqual&>(o));
+ DataPool::operator=(static_cast<DataPool const&>(o));
+
+ return *this;
+ }
+
+ // clean up old stuff
+ Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::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!
+ free(mKeyVals);
+ }
+
+ auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1);
+ mKeyVals = static_cast<Node*>(detail::assertNotNull<std::bad_alloc>(
+ malloc(calcNumBytesTotal(numElementsWithBuffer))));
+
+ // no need for calloc here because cloneData performs a memcpy.
+ mInfo = reinterpret_cast<uint8_t*>(mKeyVals + numElementsWithBuffer);
+ // sentinel is set in cloneData
+ }
+ WHash::operator=(static_cast<const WHash&>(o));
+ WKeyEqual::operator=(static_cast<const WKeyEqual&>(o));
+ DataPool::operator=(static_cast<DataPool const&>(o));
+ 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<Self, IsFlat && std::is_trivially_destructible<Node>::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 Q = mapped_type>
+ typename std::enable_if<!std::is_void<Q>::value, Q&>::type operator[](const key_type& key) {
+ ROBIN_HOOD_TRACE(this);
+ return doCreateByKey(key);
+ }
+
+ template <typename Q = mapped_type>
+ typename std::enable_if<!std::is_void<Q>::value, Q&>::type operator[](key_type&& key) {
+ ROBIN_HOOD_TRACE(this);
+ return doCreateByKey(std::move(key));
+ }
+
+ template <typename Iter>
+ 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));
+ }
+ }
+
+ template <typename... Args>
+ std::pair<iterator, bool> emplace(Args&&... args) {
+ ROBIN_HOOD_TRACE(this);
+ Node n{*this, std::forward<Args>(args)...};
+ auto r = doInsert(std::move(n));
+ if (!r.second) {
+ // insertion not possible: destroy node
+ // NOLINTNEXTLINE(bugprone-use-after-move)
+ n.destroy(*this);
+ }
+ return r;
+ }
+
+ std::pair<iterator, bool> insert(const value_type& keyval) {
+ ROBIN_HOOD_TRACE(this);
+ return doInsert(keyval);
+ }
+
+ std::pair<iterator, bool> insert(value_type&& keyval) {
+ return doInsert(std::move(keyval));
+ }
+
+ // 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<Node*>(mInfo)) {
+ return 1;
+ }
+ return 0;
+ }
+
+ bool contains(const key_type& key) const { // NOLINT(modernize-use-nodiscard)
+ return 1U == count(key);
+ }
+
+ // Returns a reference to the value found for key.
+ // Throws std::out_of_range if element cannot be found
+ template <typename Q = mapped_type>
+ // NOLINTNEXTLINE(modernize-use-nodiscard)
+ typename std::enable_if<!std::is_void<Q>::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<Node*>(mInfo)) {
+ doThrow<std::out_of_range>("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 <typename Q = mapped_type>
+ // NOLINTNEXTLINE(modernize-use-nodiscard)
+ typename std::enable_if<!std::is_void<Q>::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<Node*>(mInfo)) {
+ doThrow<std::out_of_range>("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 <typename OtherKey>
+ 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};
+ }
+
+ iterator find(const key_type& key) {
+ ROBIN_HOOD_TRACE(this);
+ const size_t idx = findIdx(key);
+ return iterator{mKeyVals + idx, mInfo + idx};
+ }
+
+ template <typename OtherKey>
+ 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};
+ }
+
+ 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<Node*>(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<Node*>(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<Node*>(pos.mKeyVals), const_cast<uint8_t*>(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<size_t>(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) {
+ reserve(c);
+ }
+
+ // 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);
+ 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();
+ }
+
+ rehashPowerOfTwo(newSize);
+ }
+
+ size_type size() const noexcept { // NOLINT(modernize-use-nodiscard)
+ 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);
+ return static_cast<size_type>(-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<float>(size()) / static_cast<float>(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<size_t>::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<size_t>(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<uint64_t>(numElements);
+ auto const s = static_cast<uint64_t>(sizeof(Node));
+ auto const infos = static_cast<uint64_t>(calcNumBytesInfo(numElements));
+
+ auto const total64 = ne * s + infos;
+ auto const total = static_cast<size_t>(total64);
+
+ if (ROBIN_HOOD_UNLIKELY(static_cast<uint64_t>(total) != total64)) {
+ throwOverflowError();
+ }
+ return total;
+#endif
+ }
+
+private:
+ template <typename Q = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<!std::is_void<Q>::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 <typename Q = mapped_type>
+ ROBIN_HOOD(NODISCARD)
+ typename std::enable_if<std::is_void<Q>::value, bool>::type has(const value_type& e) const {
+ 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);
+
+ Node* const oldKeyVals = mKeyVals;
+ uint8_t const* const oldInfo = mInfo;
+
+ const size_t oldMaxElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1);
+
+ // resize operation: move stuff
+ init_data(numBuckets);
+ if (oldMaxElementsWithBuffer > 1) {
+ for (size_t i = 0; i < oldMaxElementsWithBuffer; ++i) {
+ if (oldInfo[i] != 0) {
+ insert_move(std::move(oldKeyVals[i]));
+ // destroy the node but DON'T destroy the data.
+ oldKeyVals[i].~Node();
+ }
+ }
+
+ // don't destroy old data: put it into the pool instead
+ 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
+ }
+
+ void init_data(size_t max_elements) {
+ mNumElements = 0;
+ mMask = max_elements - 1;
+ mMaxNumElementsAllowed = calcMaxNumElementsAllowed(max_elements);
+
+ auto const numElementsWithBuffer = calcNumElementsWithBuffer(max_elements);
+
+ // calloc also zeroes everything
+ mKeyVals = reinterpret_cast<Node*>(detail::assertNotNull<std::bad_alloc>(
+ calloc(1, calcNumBytesTotal(numElementsWithBuffer))));
+ mInfo = reinterpret_cast<uint8_t*>(mKeyVals + numElementsWithBuffer);
+
+ // set sentinel
+ mInfo[numElementsWithBuffer] = 1;
+
+ mInfoInc = InitialInfoInc;
+ mInfoHashShift = InitialInfoHashShift;
+ }
+
+ template <typename Arg, typename Q = mapped_type>
+ typename std::enable_if<!std::is_void<Q>::value, Q&>::type doCreateByKey(Arg&& key) {
+ while (true) {
+ 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 (info == mInfo[idx]) {
+ if (WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) {
+ // key already exists, do not insert.
+ return mKeyVals[idx].getSecond();
+ }
+ next(&info, &idx);
+ }
+
+ // unlikely that this evaluates to true
+ if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
+ increase_size();
+ 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);
+ }
+
+ 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.
+ ::new (static_cast<void*>(&l))
+ Node(*this, std::piecewise_construct,
+ std::forward_as_tuple(std::forward<Arg>(key)), std::forward_as_tuple());
+ } else {
+ shiftUp(idx, insertion_idx);
+ l = Node(*this, std::piecewise_construct,
+ std::forward_as_tuple(std::forward<Arg>(key)), std::forward_as_tuple());
+ }
+
+ // mKeyVals[idx].getFirst() = std::move(key);
+ mInfo[insertion_idx] = static_cast<uint8_t>(insertion_info);
+
+ ++mNumElements;
+ return mKeyVals[insertion_idx].getSecond();
+ }
+ }
+
+ // This is exactly the same code as operator[], except for the return values
+ template <typename Arg>
+ std::pair<iterator, bool> doInsert(Arg&& keyval) {
+ while (true) {
+ size_t idx;
+ InfoType info;
+ keyToIdx(getFirstConst(keyval), &idx, &info);
+ nextWhileLess(&info, &idx);
+
+ // while we potentially have a match
+ while (info == mInfo[idx]) {
+ if (WKeyEqual::operator()(getFirstConst(keyval), mKeyVals[idx].getFirst())) {
+ // key already exists, do NOT insert.
+ // see http://en.cppreference.com/w/cpp/container/unordered_map/insert
+ return std::make_pair<iterator, bool>(iterator(mKeyVals + idx, mInfo + idx),
+ false);
+ }
+ next(&info, &idx);
+ }
+
+ // unlikely that this evaluates to true
+ if (ROBIN_HOOD_UNLIKELY(mNumElements >= mMaxNumElementsAllowed)) {
+ increase_size();
+ 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);
+ }
+
+ auto& l = mKeyVals[insertion_idx];
+ if (idx == insertion_idx) {
+ ::new (static_cast<void*>(&l)) Node(*this, std::forward<Arg>(keyval));
+ } else {
+ shiftUp(idx, insertion_idx);
+ l = Node(*this, std::forward<Arg>(keyval));
+ }
+
+ // put at empty spot
+ mInfo[insertion_idx] = static_cast<uint8_t>(insertion_info);
+
+ ++mNumElements;
+ return std::make_pair(iterator(mKeyVals + insertion_idx, mInfo + insertion_idx), true);
+ }
+ }
+
+ 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<uint8_t>(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<uint64_t>(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;
+ }
+
+ void increase_size() {
+ // nothing allocated yet? just allocate InitialNumElements
+ if (0 == mMask) {
+ init_data(InitialNumElements);
+ return;
+ }
+
+ auto const maxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1);
+ if (mNumElements < maxNumElementsAllowed && try_increase_info()) {
+ return;
+ }
+
+ ROBIN_HOOD_LOG("mNumElements=" << mNumElements << ", maxNumElementsAllowed="
+ << maxNumElementsAllowed << ", load="
+ << (static_cast<double>(mNumElements) * 100.0 /
+ (static_cast<double>(mMask) + 1)));
+ // it seems we have a really bad hash function! don't try to resize again
+ if (mNumElements * 2 < calcMaxNumElementsAllowed(mMask + 1)) {
+ throwOverflowError();
+ }
+
+ rehashPowerOfTwo((mMask + 1) * 2);
+ }
+
+ void destroy() {
+ if (0 == mMask) {
+ // don't deallocate!
+ return;
+ }
+
+ Destroyer<Self, IsFlat && std::is_trivially_destructible<Node>::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<Node*>(&mMask)) {
+ free(mKeyVals);
+ }
+ }
+
+ void init() noexcept {
+ mKeyVals = reinterpret_cast<Node*>(&mMask);
+ mInfo = reinterpret_cast<uint8_t*>(&mMask);
+ mNumElements = 0;
+ mMask = 0;
+ mMaxNumElementsAllowed = 0;
+ mInfoInc = InitialInfoInc;
+ mInfoHashShift = InitialInfoHashShift;
+ }
+
+ // members are sorted so no padding occurs
+ Node* mKeyVals = reinterpret_cast<Node*>(&mMask); // 8 byte 8
+ uint8_t* mInfo = reinterpret_cast<uint8_t*>(&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
+
+// map
+
+template <typename Key, typename T, typename Hash = hash<Key>,
+ typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
+using unordered_flat_map = detail::Table<true, MaxLoadFactor100, Key, T, Hash, KeyEqual>;
+
+template <typename Key, typename T, typename Hash = hash<Key>,
+ typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
+using unordered_node_map = detail::Table<false, MaxLoadFactor100, Key, T, Hash, KeyEqual>;
+
+template <typename Key, typename T, typename Hash = hash<Key>,
+ typename KeyEqual = std::equal_to<Key>, size_t MaxLoadFactor100 = 80>
+using unordered_map =
+ detail::Table<sizeof(robin_hood::pair<Key, T>) <= sizeof(size_t) * 6 &&
+ std::is_nothrow_move_constructible<robin_hood::pair<Key, T>>::value &&
+ std::is_nothrow_move_assignable<robin_hood::pair<Key, T>>::value,
+ MaxLoadFactor100, Key, T, Hash, KeyEqual>;
+
+// set
+
+template <typename Key, typename Hash = hash<Key>, typename KeyEqual = std::equal_to<Key>,
+ size_t MaxLoadFactor100 = 80>
+using unordered_flat_set = detail::Table<true, MaxLoadFactor100, Key, void, Hash, KeyEqual>;
+
+template <typename Key, typename Hash = hash<Key>, typename KeyEqual = std::equal_to<Key>,
+ size_t MaxLoadFactor100 = 80>
+using unordered_node_set = detail::Table<false, MaxLoadFactor100, Key, void, Hash, KeyEqual>;
+
+template <typename Key, typename Hash = hash<Key>, typename KeyEqual = std::equal_to<Key>,
+ size_t MaxLoadFactor100 = 80>
+using unordered_set = detail::Table<sizeof(Key) <= sizeof(size_t) * 6 &&
+ std::is_nothrow_move_constructible<Key>::value &&
+ std::is_nothrow_move_assignable<Key>::value,
+ MaxLoadFactor100, Key, void, Hash, KeyEqual>;
+
+} // namespace robin_hood
+
+#endif
\ No newline at end of file |