From a44896e12d2fd51438b3620503e5db84d2f196e4 Mon Sep 17 00:00:00 2001 From: Tylo Date: Sun, 21 Jun 2020 23:04:27 +0200 Subject: Moved examples to examples folder. --- examples/advanced.c | 89 ++ examples/advanced.md | 90 ++ examples/benchmark.c | 175 +++ examples/demos.c | 182 +++ examples/others/bytell_hash_map.hpp | 1260 ++++++++++++++++++++ examples/others/flat_hash_map.hpp | 1496 +++++++++++++++++++++++ examples/others/khash.h | 595 ++++++++++ examples/others/khashl.h | 345 ++++++ examples/others/robin_hood.hpp | 2231 +++++++++++++++++++++++++++++++++++ examples/rngtest.c | 68 ++ 10 files changed, 6531 insertions(+) create mode 100644 examples/advanced.c create mode 100644 examples/advanced.md create mode 100644 examples/benchmark.c create mode 100644 examples/demos.c create mode 100644 examples/others/bytell_hash_map.hpp create mode 100644 examples/others/flat_hash_map.hpp create mode 100644 examples/others/khash.h create mode 100644 examples/others/khashl.h create mode 100644 examples/others/robin_hood.hpp create mode 100644 examples/rngtest.c (limited to 'examples') diff --git a/examples/advanced.c b/examples/advanced.c new file mode 100644 index 00000000..092e3f01 --- /dev/null +++ b/examples/advanced.c @@ -0,0 +1,89 @@ +/*To be able to use CHash with a user-defined key-type, you need to define two things: + +1. A hash function; this must be a function that calculates the hash value given an object of the key-type. + +2. A comparison function for equality; this is required because the hash cannot rely on the fact that the hash function will always provide a unique hash value for every distinct key (i.e., it needs to be able to deal with collisions), so it needs a way to compare two given keys for an exact match. + +The difficulty with the hash function is that if your key type consists of several members, you will usually have the hash function calculate hash values for the individual members, and then somehow combine them into one hash value for the entire object. For good performance (i.e., few collisions) you should think carefully about how to combine the individual hash values to ensure you avoid getting the same output for different objects too often. + +Assuming a key-type like this, and want string as value, we define the functions person_make(), person_destroy() and person_compare(): +```*/ +#include +#include "../stc/chash.h" +#include "../stc/cstring.h" + +struct Person { + CString name; + CString surname; + int age; +}; + +struct Person person_make(const char* name, const char* surname, int age) { + struct Person person = {cstring_make(name), cstring_make(surname), age}; + return person; +} + +void person_destroy(struct Person* p) { + cstring_destroy(&p->name); + cstring_destroy(&p->surname); +} +/*``` +In order to use Person as a map key, provide a "view" of your class that owns no resources (e.g. CString): +```*/ +struct PersonView { + const char* name; + const char* surname; + int age; +}; + +struct PersonView person_getView(struct Person* p) { + return (struct PersonView) {p->name.str, p->surname.str, p->age}; +} + +struct Person person_fromView(struct PersonView pv) { + return (struct Person) {cstring_make(pv.name), cstring_make(pv.surname), pv.age}; +} + +int personview_compare(const struct PersonView* x, const struct PersonView* y) { + int c; + c = strcmp(x->name, y->name); if (c != 0) return c; + c = strcmp(x->surname, y->surname); if (c != 0) return c; + return x->age - y->age; +} +/*``` +And a hash function that combines the three member's hashes: +```*/ +size_t personview_hash(const struct PersonView* pv, size_t ignore) { + // http://stackoverflow.com/a/1646913/126995 + size_t res = 17; + res = res * 31 + c_defaultHash(pv->name, strlen(pv->name)); + res = res * 31 + c_defaultHash(pv->surname, strlen(pv->surname)); + res = res * 31 + c_defaultHash(&pv->age, sizeof(pv->age)); + return res; +} +/*``` +With this in place, we can declare the map Person -> int: +```*/ +declare_CHash(ex, map, struct Person, int, c_emptyDestroy, personview_hash, personview_compare, + struct PersonView, person_destroy, person_getView, person_fromView); +/*``` +Note we use struct PersonView to put keys in the map, but keys are stored as struct Person with proper dynamically allocated CStrings to store name and surname. +```*/ +int main() +{ + CHash_ex m6 = chash_init; + chash_ex_put(&m6, (struct PersonView){"John", "Doe", 24}, 1001); + chash_ex_put(&m6, (struct PersonView){"Jane", "Doe", 21}, 1002); + chash_ex_put(&m6, (struct PersonView){"John", "Travolta", 66}, 1003); + + c_foreach (it, chash_ex, m6) { + if (cstring_equals(it.item->key.name, "John")) + printf("%s %s %d -> %d\n", it.item->key.name.str, it.item->key.surname.str, it.item->key.age, + it.item->value); + } + + chash_ex_destroy(&m6); +} +/*``` +CHash uses personview_hash() for hash value calculations, and the personview_compare() for equality checks. The chash_ex_destroy() function will free CStrings name, surname and the value for each item in the map, in addition to the CHash hash table itself. +*/ diff --git a/examples/advanced.md b/examples/advanced.md new file mode 100644 index 00000000..031db20d --- /dev/null +++ b/examples/advanced.md @@ -0,0 +1,90 @@ +To be able to use CMap with a user-defined key-type, you need to define two things: + +1. A hash function; this must be a function that calculates the hash value given an object of the key-type. + +2. A comparison function for equality; this is required because the hash cannot rely on the fact that the hash function will always provide a unique hash value for every distinct key (i.e., it needs to be able to deal with collisions), so it needs a way to compare two given keys for an exact match. + +The difficulty with the hash function is that if your key type consists of several members, you will usually have the hash function calculate hash values for the individual members, and then somehow combine them into one hash value for the entire object. For good performance (i.e., few collisions) you should think carefully about how to combine the individual hash values to ensure you avoid getting the same output for different objects too often. + +Assuming a key-type like this, and want string as value, we define the functions person_make(), person_destroy() and person_compare(): +``` +#include + +#include +#include + +struct Person { + CString name; + CString surname; + int age; +}; + +struct Person person_make(const char* name, const char* surname, int age) { + struct Person person = {cstring_make(name), cstring_make(surname), age}; + return person; +} + +void person_destroy(struct Person* p) { + cstring_destroy(&p->name); + cstring_destroy(&p->surname); +} +``` +In order to use Person as a map key, provide a "view" of your class that owns no resources (e.g. CString): +``` +struct PersonView { + const char* name; + const char* surname; + int age; +}; + +struct PersonView person_getView(struct Person* p) { + return (struct PersonView) {p->name.str, p->surname.str, p->age}; +} + +struct Person person_fromView(struct PersonView pv) { + return (struct Person) {cstring_make(pv.name), cstring_make(pv.surname), pv.age}; +} + +int personview_compare(const struct PersonView* x, const struct PersonView* y) { + int c; + c = strcmp(x->name, y->name); if (c != 0) return c; + c = strcmp(x->surname, y->surname); if (c != 0) return c; + return x->age - y->age; +} +``` +And a hash function that combines the three member's hashes: +``` +size_t personview_hash(const struct PersonView* pv, size_t ignore) { + // http://stackoverflow.com/a/1646913/126995 + size_t res = 17; + res = res * 31 + c_defaultHash(pv->name, strlen(pv->name)); + res = res * 31 + c_defaultHash(pv->surname, strlen(pv->surname)); + res = res * 31 + c_defaultHash(&pv->age, sizeof(pv->age)); + return res; +} +``` +With this in place, we can declare the map Person -> int: +``` +declare_CHash(ex, map, struct Person, int, c_emptyDestroy, personview_hash, personview_compare, + struct PersonView, person_destroy, person_getView, person_fromView); +``` +Note we use struct PersonView to put keys in the map, but keys are stored as struct Person with proper dynamically allocated CStrings to store name and surname. +``` +int main() +{ + CMap_ex m6 = chash_init; + chash_ex_put(&m6, (struct PersonView){"John", "Doe", 24}, 1001); + chash_ex_put(&m6, (struct PersonView){"Jane", "Doe", 21}, 1002); + chash_ex_put(&m6, (struct PersonView){"John", "Travolta", 66}, 1003); + + c_foreach (it, chash_ex, m6) { + if (cstring_equals(it.item->key.name, "John")) + printf("%s %s %d -> %d\n", it.item->key.name.str, it.item->key.surname.str, it.item->key.age, + it.item->value); + } + + chash_ex_destroy(&m6); +} +``` +CMap uses personview_hash() for hash value calculations, and the personview_compare() for equality checks. The chash_ex_destroy() function will free CStrings name, surname and the value for each item in the map, in addition to the CMap hash table itself. + diff --git a/examples/benchmark.c b/examples/benchmark.c new file mode 100644 index 00000000..bf516e28 --- /dev/null +++ b/examples/benchmark.c @@ -0,0 +1,175 @@ +#include "../stc/crandom.h" +#include "../stc/cstring.h" +#include "../stc/chash.h" +#include "others/khash.h" + +#include +#include + +#ifdef __cplusplus +#include +#include "others/bytell_hash_map.hpp" +#include "others/robin_hood.hpp" +#endif + +// Visual Studio: compile with -TP to force C++: cl -TP -EHsc -O2 benchmark.c + + +static inline uint32_t fibonacci_hash(const void* data, size_t len) { + const uint64_t key = *(const uint64_t *) data; + return (uint32_t) (key * 11400714819323198485llu); +} +declare_CHash(ii, map, int64_t, int64_t, c_emptyDestroy, fibonacci_hash); // c_lowbias32Hash); + +KHASH_MAP_INIT_INT64(ii, uint64_t) + +size_t seed = 1234; +static const double maxLoadFactor = 0.77; + +sfc64_t rng; +#define SEED(s) rng = sfc64_seed(seed) +#define RAND(N) (sfc64_rand(&rng) & ((1 << N) - 1)) +//mt19937_t rng; +//#define SEED(s) rng = mt19937_seed(s) +//#define RAND(N) (mt19937_rand(&rng) & ((1 << N) - 1)) + + +#define CMAP_SETUP(tag, Key, Value) CHash_##tag map = chash_init; \ + chash_##tag##_setMaxLoadFactor(&map, maxLoadFactor) +#define CMAP_PUT(tag, key, val) chash_##tag##_put(&map, key, val)->value +#define CMAP_ERASE(tag, key) chash_##tag##_erase(&map, key) +#define CMAP_FIND(tag, key) (chash_##tag##_get(map, key) != NULL) +#define CMAP_SIZE(tag) chash_size(map) +#define CMAP_BUCKETS(tag) chash_bucketCount(map) +#define CMAP_CLEAR(tag) chash_##tag##_destroy(&map) + +#define KMAP_SETUP(tag, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret +#define KMAP_PUT(tag, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, &map->vals[ki])) +#define KMAP_ERASE(tag, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0) +#define KMAP_FIND(tag, key) (kh_get(ii, map, key) != kh_end(map)) +#define KMAP_SIZE(tag) ((size_t) kh_size(map)) +#define KMAP_BUCKETS(tag) ((size_t) kh_n_buckets(map)) +#define KMAP_CLEAR(tag) kh_destroy(ii, map) + +#define UMAP_SETUP(tag, Key, Value) std::unordered_map map; map.max_load_factor(maxLoadFactor) +#define UMAP_PUT(tag, key, val) (map[key] = val) +#define UMAP_FIND(tag, key) (map.find(key) != map.end()) +#define UMAP_ERASE(tag, key) map.erase(key) +#define UMAP_SIZE(tag) map.size() +#define UMAP_BUCKETS(tag) map.bucket_count() +#define UMAP_CLEAR(tag) map.clear() + +#define BMAP_SETUP(tag, Key, Value) ska::bytell_hash_map map; map.max_load_factor(maxLoadFactor) +#define BMAP_PUT(tag, key, val) (map[key] = val) +#define BMAP_FIND(tag, key) (map.find(key) != map.end()) +#define BMAP_ERASE(tag, key) map.erase(key) +#define BMAP_SIZE(tag) map.size() +#define BMAP_BUCKETS(tag) map.bucket_count() +#define BMAP_CLEAR(tag) map.clear() + +#define FMAP_SETUP(tag, Key, Value) ska::flat_hash_map map; map.max_load_factor(maxLoadFactor) +#define FMAP_PUT(tag, key, val) (map[key] = val) +#define FMAP_FIND(tag, key) (map.find(key) != map.end()) +#define FMAP_ERASE(tag, key) map.erase(key) +#define FMAP_SIZE(tag) map.size() +#define FMAP_BUCKETS(tag) map.bucket_count() +#define FMAP_CLEAR(tag) map.clear() + +#define RMAP_SETUP(tag, Key, Value) robin_hood::unordered_map map +#define RMAP_PUT(tag, key, val) (map[key] = val) +#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_CLEAR(tag) map.clear() + +const size_t N1 = 7000000; +const size_t N2 = 10000000; +#define RR 20 +int rr = RR; + + +#define MAP_TEST1(M, tag) \ +{ \ + M##_SETUP(tag, int64_t, int64_t); \ + uint64_t checksum = 0, erased = 0; \ + SEED(seed); \ + clock_t difference, before = clock(); \ + for (size_t i = 0; i < N1; ++i) { \ + checksum += ++ M##_PUT(tag, RAND(rr), i); \ + erased += M##_ERASE(tag, RAND(rr)); \ + } \ + difference = clock() - before; \ + printf(#M "(" #tag "): sz: %zu, bucks: %zu, time: %.02f, sum: %zu, erase: %zu\n", \ + M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, checksum, erased); \ + M##_CLEAR(tag); \ +} + +#define MAP_TEST2(M, tag) \ +{ \ + M##_SETUP(tag, int64_t, int64_t); \ + size_t erased = 0; \ + clock_t difference, before = clock(); \ + for (size_t i = 0; i < N2; ++i) \ + M##_PUT(tag, i, i); \ + for (size_t i = 0; i < N2; ++i) \ + erased += M##_ERASE(tag, i); \ + difference = clock() - before; \ + printf(#M "(" #tag "): sz: %zu, bucks: %zu, time: %.02f, erase %zu\n", \ + M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ + M##_CLEAR(tag); \ +} + +#define MAP_TEST3(M, tag) \ +{ \ + M##_SETUP(tag, int64_t, int64_t); \ + size_t erased = 0; \ + clock_t difference, before = clock(); \ + SEED(seed); \ + for (size_t i = 0; i < N2; ++i) \ + M##_PUT(tag, RAND(rr), i); \ + SEED(seed); \ + for (size_t i = 0; i < N2; ++i) \ + erased += M##_ERASE(tag, RAND(rr)); \ + difference = clock() - before; \ + printf(#M "(" #tag "): sz: %zu, bucks: %zu, time: %.02f, erase %zu\n", \ + M##_SIZE(tag), M##_BUCKETS(tag), (float) difference / CLOCKS_PER_SEC, erased); \ + M##_CLEAR(tag); \ +} + + +int main(int argc, char* argv[]) +{ + rr = argc == 2 ? atoi(argv[1]) : RR; + seed = time(NULL); + printf("\nRandom keys are in range [0, 2^%d):\n", rr); + printf("\nmap: %zu repeats of Insert random key + remove a different random key:\n", N1); + MAP_TEST1(CMAP, ii) + MAP_TEST1(KMAP, ii) +#ifdef __cplusplus + MAP_TEST1(UMAP, ii) + MAP_TEST1(BMAP, ii) + MAP_TEST1(FMAP, ii) + MAP_TEST1(RMAP, ii) +#endif + + printf("\nmap: Insert %zu index keys, then remove them in same order:\n", N2); + MAP_TEST2(CMAP, ii) + MAP_TEST2(KMAP, ii) +#ifdef __cplusplus + MAP_TEST2(UMAP, ii) + MAP_TEST2(BMAP, ii) + MAP_TEST2(FMAP, ii) + MAP_TEST2(RMAP, ii) +#endif + + printf("\nmap: Insert %zu random keys, then remove them in same order:\n", N2); + MAP_TEST3(CMAP, ii) + MAP_TEST3(KMAP, ii) +#ifdef __cplusplus + MAP_TEST3(UMAP, ii) + MAP_TEST3(BMAP, ii) + MAP_TEST3(FMAP, ii) + MAP_TEST3(RMAP, ii) +#endif +} diff --git a/examples/demos.c b/examples/demos.c new file mode 100644 index 00000000..b2fa32ec --- /dev/null +++ b/examples/demos.c @@ -0,0 +1,182 @@ +#include "../stc/cvector.h" +#include "../stc/clist.h" +#include "../stc/chash.h" +#include "../stc/cstring.h" + + +void stringdemo1() +{ + printf("\nSTRINGDEMO1\n"); + CString cs = cstring_make("one-nine-three-seven-five"); + printf("%s.\n", cs.str); + + cstring_insert(&cs, 3, "-two"); + printf("%s.\n", cs.str); + + cstring_erase(&cs, 7, 5); // -nine + printf("%s.\n", cs.str); + + cstring_replace(&cs, 0, "seven", "four"); + printf("%s.\n", cs.str); + cstring_take(&cs, cstring_makeFmt("%s *** %s", cs.str, cs.str)); + printf("%s.\n", cs.str); + + printf("find: %s\n", cs.str + cstring_find(cs, 0, "four")); + + // reassign: + cstring_assign(&cs, "one two three four five six seven"); + cstring_append(&cs, " eight"); + printf("append: %s\n", cs.str); + + cstring_destroy(&cs); +} + + +declare_CVector(ix, int64_t); // ix is just an example tag name. + +void vectordemo1() +{ + printf("\nVECTORDEMO1\n"); + CVector_ix bignums = cvector_init; // = (CVector_ix) cvector_init; if initializing after declaration. + cvector_ix_reserve(&bignums, 100); + for (size_t i = 0; i<=100; ++i) + cvector_ix_pushBack(&bignums, i * i * i); + + printf("erase - %d: %zu\n", 100, bignums.data[100]); + cvector_ix_popBack(&bignums); // erase the last + + for (size_t i = 0; i < cvector_size(bignums); ++i) { + if (i >= 90) printf("%zu: %zu\n", i, bignums.data[i]); + } + cvector_ix_destroy(&bignums); +} + + + +declare_CVector(cs, CString, cstring_destroy, cstring_compare); // supply inline destructor of values + +void vectordemo2() +{ + printf("\nVECTORDEMO2\n"); + CVector_cs names = cvector_init; + cvector_cs_pushBack(&names, cstring_make("Mary")); + cvector_cs_pushBack(&names, cstring_make("Joe")); + cvector_cs_pushBack(&names, cstring_make("Chris")); + cstring_assign(&names.data[1], "Jane"); // replace Joe + printf("names[1]: %s\n", names.data[1].str); + + cvector_cs_sort(&names); // Sort the array + c_foreach (i, cvector_cs, names) + printf("sorted: %s\n", i.item->str); + cvector_cs_destroy(&names); +} + +declare_CList(ix, int); + +void listdemo1() +{ + printf("\nLISTDEMO1\n"); + CList_ix nums = clist_init, nums2 = clist_init; + for (int i = 0; i < 10; ++i) + clist_ix_pushBack(&nums, i); + for (int i = 100; i < 110; ++i) + clist_ix_pushBack(&nums2, i); + c_foreach (i, clist_ix, nums) + printf("value: %d\n", i.item->value); + /* merge/append nums2 to nums */ + clist_ix_spliceAfter(&nums, clist_ix_last(&nums), &nums2); + c_foreach (i, clist_ix, nums) + printf("spliced: %d\n", i.item->value); + + *clist_ix_find(&nums, 100) *= 10; + clist_ix_sort(&nums); // Sort the array + clist_ix_remove(&nums, 105); + clist_ix_popFront(&nums); + clist_ix_pushFront(&nums, -99); + c_foreach (i, clist_ix, nums) + printf("sorted: %d\n", i.item->value); + clist_ix_destroy(&nums); +} + +declare_CHash(i, set, int); + +void setdemo1() +{ + printf("\nSETDEMO1\n"); + CHash_i nums = chash_init; + chash_i_put(&nums, 8); + chash_i_put(&nums, 11); + + c_foreach (i, chash_i, nums) + printf("set: %d\n", i.item->key); + chash_i_destroy(&nums); +} + + +declare_CHash(ii, map, int, int); + +void mapdemo1() +{ + printf("\nMAPDEMO1\n"); + CHash_ii nums = chash_init; + chash_ii_put(&nums, 8, 64); + chash_ii_put(&nums, 11, 121); + + printf("get 8: %d\n", chash_ii_get(&nums, 8)->value); + chash_ii_destroy(&nums); +} + + +declare_CHash_string(si, map, int); // Shorthand macro for the general declare_CHash expansion. + +void mapdemo2() +{ + printf("\nMAPDEMO2\n"); + CHash_si nums = chash_init; + chash_si_put(&nums, "Hello", 64); + chash_si_put(&nums, "Groovy", 121); + chash_si_put(&nums, "Groovy", 200); // overwrite previous + + // iterate the map: + for (chash_si_iter_t i = chash_si_begin(&nums); i.item; i = chash_si_next(i)) + printf("long: %s: %d\n", i.item->key.str, i.item->value); + + // or rather use the short form: + c_foreach (i, chash_si, nums) + printf("short: %s: %d\n", i.item->key.str, i.item->value); + + chash_si_destroy(&nums); +} + + +declare_CHash_string(ss, map, CString, cstring_destroy); + +void mapdemo3() +{ + printf("\nMAPDEMO3\n"); + CHash_ss table = chash_init; + chash_ss_put(&table, "Map", cstring_make("test")); + chash_ss_put(&table, "Make", cstring_make("my")); + chash_ss_put(&table, "Sunny", cstring_make("day")); + printf("remove: Make: %s\n", chash_ss_get(&table, "Make")->value.str); + chash_ss_erase(&table, "Make"); + + printf("size %zu\n", chash_size(table)); + c_foreach (i, chash_ss, table) + printf("key: %s\n", i.item->key.str); + chash_ss_destroy(&table); // frees key and value CStrings, and hash table (CVector). +} + + + +int main() +{ + stringdemo1(); + vectordemo1(); + vectordemo2(); + listdemo1(); + setdemo1(); + mapdemo1(); + mapdemo2(); + mapdemo3(); +} diff --git a/examples/others/bytell_hash_map.hpp b/examples/others/bytell_hash_map.hpp new file mode 100644 index 00000000..2e348cdb --- /dev/null +++ b/examples/others/bytell_hash_map.hpp @@ -0,0 +1,1260 @@ +// Copyright Malte Skarupke 2017. +// Distributed under the Boost Software License, Version 1.0. +// (See http://www.boost.org/LICENSE_1_0.txt) + +#pragma once + +#include +#include +#include +#include +#include +#include +#include +#include "flat_hash_map.hpp" +#include +#include + +namespace ska +{ + +namespace detailv8 +{ +using ska::detailv3::functor_storage; +using ska::detailv3::KeyOrValueHasher; +using ska::detailv3::KeyOrValueEquality; +using ska::detailv3::AssignIfTrue; +using ska::detailv3::HashPolicySelector; + +template +struct sherwood_v8_constants +{ + static constexpr int8_t magic_for_empty = int8_t(0b11111111); + static constexpr int8_t magic_for_reserved = int8_t(0b11111110); + static constexpr int8_t bits_for_direct_hit = int8_t(0b10000000); + static constexpr int8_t magic_for_direct_hit = int8_t(0b00000000); + static constexpr int8_t magic_for_list_entry = int8_t(0b10000000); + + static constexpr int8_t bits_for_distance = int8_t(0b01111111); + inline static int distance_from_metadata(int8_t metadata) + { + return metadata & bits_for_distance; + } + + static constexpr int num_jump_distances = 126; + // jump distances chosen like this: + // 1. pick the first 16 integers to promote staying in the same block + // 2. add the next 66 triangular numbers to get even jumps when + // the hash table is a power of two + // 3. add 44 more triangular numbers at a much steeper growth rate + // to get a sequence that allows large jumps so that a table + // with 10000 sequential numbers doesn't endlessly re-allocate + static constexpr size_t jump_distances[num_jump_distances] + { + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, + + 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, + 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, + 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, + 1225, 1275, 1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770, 1830, + 1891, 1953, 2016, 2080, 2145, 2211, 2278, 2346, 2415, 2485, 2556, + + 3741, 8385, 18915, 42486, 95703, 215496, 485605, 1091503, 2456436, + 5529475, 12437578, 27986421, 62972253, 141700195, 318819126, 717314626, + 1614000520, 3631437253, 8170829695, 18384318876, 41364501751, + 93070021080, 209407709220, 471167588430, 1060127437995, 2385287281530, + 5366895564381, 12075513791265, 27169907873235, 61132301007778, + 137547673121001, 309482258302503, 696335090510256, 1566753939653640, + 3525196427195653, 7931691866727775, 17846306747368716, + 40154190394120111, 90346928493040500, 203280588949935750, + 457381324898247375, 1029107980662394500, 2315492957028380766, + 5209859150892887590, + }; +}; +template +constexpr int8_t sherwood_v8_constants::magic_for_empty; +template +constexpr int8_t sherwood_v8_constants::magic_for_reserved; +template +constexpr int8_t sherwood_v8_constants::bits_for_direct_hit; +template +constexpr int8_t sherwood_v8_constants::magic_for_direct_hit; +template +constexpr int8_t sherwood_v8_constants::magic_for_list_entry; + +template +constexpr int8_t sherwood_v8_constants::bits_for_distance; + +template +constexpr int sherwood_v8_constants::num_jump_distances; +template +constexpr size_t sherwood_v8_constants::jump_distances[num_jump_distances]; + +template +struct sherwood_v8_block +{ + sherwood_v8_block() + { + } + ~sherwood_v8_block() + { + } + int8_t control_bytes[BlockSize]; + union + { + T data[BlockSize]; + }; + + static sherwood_v8_block * empty_block() + { + static std::array empty_bytes = [] + { + std::array result; + result.fill(sherwood_v8_constants<>::magic_for_empty); + return result; + }(); + return reinterpret_cast(&empty_bytes); + } + + int first_empty_index() const + { + for (int i = 0; i < BlockSize; ++i) + { + if (control_bytes[i] == sherwood_v8_constants<>::magic_for_empty) + return i; + } + return -1; + } + + void fill_control_bytes(int8_t value) + { + std::fill(std::begin(control_bytes), std::end(control_bytes), value); + } +}; + +template +class sherwood_v8_table : private ByteAlloc, private Hasher, private Equal +{ + using AllocatorTraits = std::allocator_traits; + using BlockType = sherwood_v8_block; + using BlockPointer = BlockType *; + using BytePointer = typename AllocatorTraits::pointer; + struct convertible_to_iterator; + using Constants = sherwood_v8_constants<>; + +public: + + using value_type = T; + using size_type = size_t; + using difference_type = std::ptrdiff_t; + using hasher = ArgumentHash; + using key_equal = ArgumentEqual; + using allocator_type = ByteAlloc; + using reference = value_type &; + using const_reference = const value_type &; + using pointer = value_type *; + using const_pointer = const value_type *; + + sherwood_v8_table() + { + } + explicit sherwood_v8_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) + : ByteAlloc(alloc), Hasher(hash), Equal(equal) + { + if (bucket_count) + rehash(bucket_count); + } + sherwood_v8_table(size_type bucket_count, const ArgumentAlloc & alloc) + : sherwood_v8_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc) + { + } + sherwood_v8_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) + : sherwood_v8_table(bucket_count, hash, ArgumentEqual(), alloc) + { + } + explicit sherwood_v8_table(const ArgumentAlloc & alloc) + : ByteAlloc(alloc) + { + } + template + sherwood_v8_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) + : sherwood_v8_table(bucket_count, hash, equal, alloc) + { + insert(first, last); + } + template + sherwood_v8_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc) + : sherwood_v8_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc) + { + } + template + sherwood_v8_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) + : sherwood_v8_table(first, last, bucket_count, hash, ArgumentEqual(), alloc) + { + } + sherwood_v8_table(std::initializer_list il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) + : sherwood_v8_table(bucket_count, hash, equal, alloc) + { + if (bucket_count == 0) + rehash(il.size()); + insert(il.begin(), il.end()); + } + sherwood_v8_table(std::initializer_list il, size_type bucket_count, const ArgumentAlloc & alloc) + : sherwood_v8_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc) + { + } + sherwood_v8_table(std::initializer_list il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) + : sherwood_v8_table(il, bucket_count, hash, ArgumentEqual(), alloc) + { + } + sherwood_v8_table(const sherwood_v8_table & other) + : sherwood_v8_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator())) + { + } + sherwood_v8_table(const sherwood_v8_table & other, const ArgumentAlloc & alloc) + : ByteAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor) + { + rehash_for_other_container(other); + try + { + insert(other.begin(), other.end()); + } + catch(...) + { + clear(); + deallocate_data(entries, num_slots_minus_one); + throw; + } + } + sherwood_v8_table(sherwood_v8_table && other) noexcept + : ByteAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other)) + , _max_load_factor(other._max_load_factor) + { + swap_pointers(other); + } + sherwood_v8_table(sherwood_v8_table && other, const ArgumentAlloc & alloc) noexcept + : ByteAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other)) + , _max_load_factor(other._max_load_factor) + { + swap_pointers(other); + } + sherwood_v8_table & operator=(const sherwood_v8_table & other) + { + if (this == std::addressof(other)) + return *this; + + clear(); + if (AllocatorTraits::propagate_on_container_copy_assignment::value) + { + if (static_cast(*this) != static_cast(other)) + { + reset_to_empty_state(); + } + AssignIfTrue()(*this, other); + } + _max_load_factor = other._max_load_factor; + static_cast(*this) = other; + static_cast(*this) = other; + rehash_for_other_container(other); + insert(other.begin(), other.end()); + return *this; + } + sherwood_v8_table & operator=(sherwood_v8_table && other) noexcept + { + if (this == std::addressof(other)) + return *this; + else if (AllocatorTraits::propagate_on_container_move_assignment::value) + { + clear(); + reset_to_empty_state(); + AssignIfTrue()(*this, std::move(other)); + swap_pointers(other); + } + else if (static_cast(*this) == static_cast(other)) + { + swap_pointers(other); + } + else + { + clear(); + _max_load_factor = other._max_load_factor; + rehash_for_other_container(other); + for (T & elem : other) + emplace(std::move(elem)); + other.clear(); + } + static_cast(*this) = std::move(other); + static_cast(*this) = std::move(other); + return *this; + } + ~sherwood_v8_table() + { + clear(); + deallocate_data(entries, num_slots_minus_one); + } + + const allocator_type & get_allocator() const + { + return static_cast(*this); + } + const ArgumentEqual & key_eq() const + { + return static_cast(*this); + } + const ArgumentHash & hash_function() const + { + return static_cast(*this); + } + + template + struct templated_iterator + { + private: + friend class sherwood_v8_table; + BlockPointer current = BlockPointer(); + size_t index = 0; + + public: + templated_iterator() + { + } + templated_iterator(BlockPointer entries, size_t index) + : current(entries) + , index(index) + { + } + + using iterator_category = std::forward_iterator_tag; + using value_type = ValueType; + using difference_type = ptrdiff_t; + using pointer = ValueType *; + using reference = ValueType &; + + friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs) + { + return lhs.index == rhs.index; + } + friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs) + { + return !(lhs == rhs); + } + + templated_iterator & operator++() + { + do + { + if (index % BlockSize == 0) + --current; + if (index-- == 0) + break; + } + while(current->control_bytes[index % BlockSize] == Constants::magic_for_empty); + return *this; + } + templated_iterator operator++(int) + { + templated_iterator copy(*this); + ++*this; + return copy; + } + + ValueType & operator*() const + { + return current->data[index % BlockSize]; + } + ValueType * operator->() const + { + return current->data + index % BlockSize; + } + + operator templated_iterator() const + { + return { current, index }; + } + }; + using iterator = templated_iterator; + using const_iterator = templated_iterator; + + iterator begin() + { + size_t num_slots = num_slots_minus_one ? num_slots_minus_one + 1 : 0; + return ++iterator{ entries + num_slots / BlockSize, num_slots }; + } + const_iterator begin() const + { + size_t num_slots = num_slots_minus_one ? num_slots_minus_one + 1 : 0; + return ++iterator{ entries + num_slots / BlockSize, num_slots }; + } + const_iterator cbegin() const + { + return begin(); + } + iterator end() + { + return { entries - 1, std::numeric_limits::max() }; + } + const_iterator end() const + { + return { entries - 1, std::numeric_limits::max() }; + } + const_iterator cend() const + { + return end(); + } + + inline iterator find(const FindKey & key) + { + size_t index = hash_object(key); + size_t num_slots_minus_one = this->num_slots_minus_one; + BlockPointer entries = this->entries; + index = hash_policy.index_for_hash(index, num_slots_minus_one); + bool first = true; + for (;;) + { + size_t block_index = index / BlockSize; + int index_in_block = index % BlockSize; + BlockPointer block = entries + block_index; + int8_t metadata = block->control_bytes[index_in_block]; + if (first) + { + if ((metadata & Constants::bits_for_direct_hit) != Constants::magic_for_direct_hit) + return end(); + first = false; + } + if (compares_equal(key, block->data[index_in_block])) + return { block, index }; + int8_t to_next_index = metadata & Constants::bits_for_distance; + if (to_next_index == 0) + return end(); + index += Constants::jump_distances[to_next_index]; + index = hash_policy.keep_in_range(index, num_slots_minus_one); + } + } + inline const_iterator find(const FindKey & key) const + { + return const_cast(this)->find(key); + } + size_t count(const FindKey & key) const + { + return find(key) == end() ? 0 : 1; + } + std::pair equal_range(const FindKey & key) + { + iterator found = find(key); + if (found == end()) + return { found, found }; + else + return { found, std::next(found) }; + } + std::pair equal_range(const FindKey & key) const + { + const_iterator found = find(key); + if (found == end()) + return { found, found }; + else + return { found, std::next(found) }; + } + + + template + inline std::pair emplace(Key && key, Args &&... args) + { + size_t index = hash_object(key); + size_t num_slots_minus_one = this->num_slots_minus_one; + BlockPointer entries = this->entries; + index = hash_policy.index_for_hash(index, num_slots_minus_one); + bool first = true; + for (;;) + { + size_t block_index = index / BlockSize; + int index_in_block = index % BlockSize; + BlockPointer block = entries + block_index; + int8_t metadata = block->control_bytes[index_in_block]; + if (first) + { + if ((metadata & Constants::bits_for_direct_hit) != Constants::magic_for_direct_hit) + return emplace_direct_hit({ index, block }, std::forward(key), std::forward(args)...); + first = false; + } + if (compares_equal(key, block->data[index_in_block])) + return { { block, index }, false }; + int8_t to_next_index = metadata & Constants::bits_for_distance; + if (to_next_index == 0) + return emplace_new_key({ index, block }, std::forward(key), std::forward(args)...); + index += Constants::jump_distances[to_next_index]; + index = hash_policy.keep_in_range(index, num_slots_minus_one); + } + } + + std::pair insert(const value_type & value) + { + return emplace(value); + } + std::pair insert(value_type && value) + { + return emplace(std::move(value)); + } + template + iterator emplace_hint(const_iterator, Args &&... args) + { + return emplace(std::forward(args)...).first; + } + iterator insert(const_iterator, const value_type & value) + { + return emplace(value).first; + } + iterator insert(const_iterator, value_type && value) + { + return emplace(std::move(value)).first; + } + + template + void insert(It begin, It end) + { + for (; begin != end; ++begin) + { + emplace(*begin); + } + } + void insert(std::initializer_list il) + { + insert(il.begin(), il.end()); + } + + void rehash(size_t num_items) + { + num_items = std::max(num_items, static_cast(std::ceil(num_elements / static_cast(_max_load_factor)))); + if (num_items == 0) + { + reset_to_empty_state(); + return; + } + auto new_prime_index = hash_policy.next_size_over(num_items); + if (num_items == num_slots_minus_one + 1) + return; + size_t num_blocks = num_items / BlockSize; + if (num_items % BlockSize) + ++num_blocks; + size_t memory_requirement = calculate_memory_requirement(num_blocks); + unsigned char * new_memory = &*AllocatorTraits::allocate(*this, memory_requirement); + + BlockPointer new_buckets = reinterpret_cast(new_memory); + + BlockPointer special_end_item = new_buckets + num_blocks; + for (BlockPointer it = new_buckets; it <= special_end_item; ++it) + it->fill_control_bytes(Constants::magic_for_empty); + using std::swap; + swap(entries, new_buckets); + swap(num_slots_minus_one, num_items); + --num_slots_minus_one; + hash_policy.commit(new_prime_index); + num_elements = 0; + if (num_items) + ++num_items; + size_t old_num_blocks = num_items / BlockSize; + if (num_items % BlockSize) + ++old_num_blocks; + for (BlockPointer it = new_buckets, end = new_buckets + old_num_blocks; it != end; ++it) + { + for (int i = 0; i < BlockSize; ++i) + { + int8_t metadata = it->control_bytes[i]; + if (metadata != Constants::magic_for_empty && metadata != Constants::magic_for_reserved) + { + emplace(std::move(it->data[i])); + AllocatorTraits::destroy(*this, it->data + i); + } + } + } + deallocate_data(new_buckets, num_items - 1); + } + + void reserve(size_t num_elements) + { + size_t required_buckets = num_buckets_for_reserve(num_elements); + if (required_buckets > bucket_count()) + rehash(required_buckets); + } + + // the return value is a type that can be converted to an iterator + // the reason for doing this is that it's not free to find the + // iterator pointing at the next element. if you care about the + // next iterator, turn the return value into an iterator + convertible_to_iterator erase(const_iterator to_erase) + { + LinkedListIt current = { to_erase.index, to_erase.current }; + if (current.has_next()) + { + LinkedListIt previous = current; + LinkedListIt next = current.next(*this); + while (next.has_next()) + { + previous = next; + next = next.next(*this); + } + AllocatorTraits::destroy(*this, std::addressof(*current)); + AllocatorTraits::construct(*this, std::addressof(*current), std::move(*next)); + AllocatorTraits::destroy(*this, std::addressof(*next)); + next.set_metadata(Constants::magic_for_empty); + previous.clear_next(); + } + else + { + if (!current.is_direct_hit()) + find_parent_block(current).clear_next(); + AllocatorTraits::destroy(*this, std::addressof(*current)); + current.set_metadata(Constants::magic_for_empty); + } + --num_elements; + return { to_erase.current, to_erase.index }; + } + + iterator erase(const_iterator begin_it, const_iterator end_it) + { + if (begin_it == end_it) + return { begin_it.current, begin_it.index }; + if (std::next(begin_it) == end_it) + return erase(begin_it); + if (begin_it == begin() && end_it == end()) + { + clear(); + return { end_it.current, end_it.index }; + } + std::vector> depth_in_chain; + for (const_iterator it = begin_it; it != end_it; ++it) + { + LinkedListIt list_it(it.index, it.current); + if (list_it.is_direct_hit()) + depth_in_chain.emplace_back(0, list_it); + else + { + LinkedListIt root = find_direct_hit(list_it); + int distance = 1; + for (;;) + { + LinkedListIt next = root.next(*this); + if (next == list_it) + break; + ++distance; + root = next; + } + depth_in_chain.emplace_back(distance, list_it); + } + } + std::sort(depth_in_chain.begin(), depth_in_chain.end(), [](const auto & a, const auto & b) { return a.first < b.first; }); + for (auto it = depth_in_chain.rbegin(), end = depth_in_chain.rend(); it != end; ++it) + { + erase(it->second.it()); + } + + if (begin_it.current->control_bytes[begin_it.index % BlockSize] == Constants::magic_for_empty) + return ++iterator{ begin_it.current, begin_it.index }; + else + return { begin_it.current, begin_it.index }; + } + + size_t erase(const FindKey & key) + { + auto found = find(key); + if (found == end()) + return 0; + else + { + erase(found); + return 1; + } + } + + void clear() + { + if (!num_slots_minus_one) + return; + size_t num_slots = num_slots_minus_one + 1; + size_t num_blocks = num_slots / BlockSize; + if (num_slots % BlockSize) + ++num_blocks; + for (BlockPointer it = entries, end = it + num_blocks; it != end; ++it) + { + for (int i = 0; i < BlockSize; ++i) + { + if (it->control_bytes[i] != Constants::magic_for_empty) + { + AllocatorTraits::destroy(*this, std::addressof(it->data[i])); + it->control_bytes[i] = Constants::magic_for_empty; + } + } + } + num_elements = 0; + } + + void shrink_to_fit() + { + rehash_for_other_container(*this); + } + + void swap(sherwood_v8_table & other) + { + using std::swap; + swap_pointers(other); + swap(static_cast(*this), static_cast(other)); + swap(static_cast(*this), static_cast(other)); + if (AllocatorTraits::propagate_on_container_swap::value) + swap(static_cast(*this), static_cast(other)); + } + + size_t size() const + { + return num_elements; + } + size_t max_size() const + { + return (AllocatorTraits::max_size(*this)) / sizeof(T); + } + size_t bucket_count() const + { + return num_slots_minus_one ? num_slots_minus_one + 1 : 0; + } + size_type max_bucket_count() const + { + return (AllocatorTraits::max_size(*this)) / sizeof(T); + } + size_t bucket(const FindKey & key) const + { + return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); + } + float load_factor() const + { + return static_cast(num_elements) / (num_slots_minus_one + 1); + } + void max_load_factor(float value) + { + _max_load_factor = value; + } + float max_load_factor() const + { + return _max_load_factor; + } + + bool empty() const + { + return num_elements == 0; + } + +private: + BlockPointer entries = BlockType::empty_block(); + size_t num_slots_minus_one = 0; + typename HashPolicySelector::type hash_policy; + float _max_load_factor = 0.9375f; + size_t num_elements = 0; + + size_t num_buckets_for_reserve(size_t num_elements) const + { + return static_cast(std::ceil(num_elements / static_cast(_max_load_factor))); + } + void rehash_for_other_container(const sherwood_v8_table & other) + { + rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count())); + } + bool is_full() const + { + if (!num_slots_minus_one) + return true; + else + return num_elements + 1 > (num_slots_minus_one + 1) * static_cast(_max_load_factor); + } + + void swap_pointers(sherwood_v8_table & other) + { + using std::swap; + swap(hash_policy, other.hash_policy); + swap(entries, other.entries); + swap(num_slots_minus_one, other.num_slots_minus_one); + swap(num_elements, other.num_elements); + swap(_max_load_factor, other._max_load_factor); + } + + struct LinkedListIt + { + size_t index = 0; + BlockPointer block = nullptr; + + LinkedListIt() + { + } + LinkedListIt(size_t index, BlockPointer block) + : index(index), block(block) + { + } + + iterator it() const + { + return { block, index }; + } + int index_in_block() const + { + return index % BlockSize; + } + bool is_direct_hit() const + { + return (metadata() & Constants::bits_for_direct_hit) == Constants::magic_for_direct_hit; + } + bool is_empty() const + { + return metadata() == Constants::magic_for_empty; + } + bool has_next() const + { + return jump_index() != 0; + } + int8_t jump_index() const + { + return Constants::distance_from_metadata(metadata()); + } + int8_t metadata() const + { + return block->control_bytes[index_in_block()]; + } + void set_metadata(int8_t metadata) + { + block->control_bytes[index_in_block()] = metadata; + } + + LinkedListIt next(sherwood_v8_table & table) const + { + int8_t distance = jump_index(); + size_t next_index = table.hash_policy.keep_in_range(index + Constants::jump_distances[distance], table.num_slots_minus_one); + return { next_index, table.entries + next_index / BlockSize }; + } + void set_next(int8_t jump_index) + { + int8_t & metadata = block->control_bytes[index_in_block()]; + metadata = (metadata & ~Constants::bits_for_distance) | jump_index; + } + void clear_next() + { + set_next(0); + } + + value_type & operator*() const + { + return block->data[index_in_block()]; + } + bool operator!() const + { + return !block; + } + explicit operator bool() const + { + return block != nullptr; + } + bool operator==(const LinkedListIt & other) const + { + return index == other.index; + } + bool operator!=(const LinkedListIt & other) const + { + return !(*this == other); + } + }; + + template + SKA_NOINLINE(std::pair) emplace_direct_hit(LinkedListIt block, Args &&... args) + { + using std::swap; + if (is_full()) + { + grow(); + return emplace(std::forward(args)...); + } + if (block.metadata() == Constants::magic_for_empty) + { + AllocatorTraits::construct(*this, std::addressof(*block), std::forward(args)...); + block.set_metadata(Constants::magic_for_direct_hit); + ++num_elements; + return { block.it(), true }; + } + else + { + LinkedListIt parent_block = find_parent_block(block); + std::pair free_block = find_free_index(parent_block); + if (!free_block.first) + { + grow(); + return emplace(std::forward(args)...); + } + value_type new_value(std::forward(args)...); + for (LinkedListIt it = block;;) + { + AllocatorTraits::construct(*this, std::addressof(*free_block.second), std::move(*it)); + AllocatorTraits::destroy(*this, std::addressof(*it)); + parent_block.set_next(free_block.first); + free_block.second.set_metadata(Constants::magic_for_list_entry); + if (!it.has_next()) + { + it.set_metadata(Constants::magic_for_empty); + break; + } + LinkedListIt next = it.next(*this); + it.set_metadata(Constants::magic_for_empty); + block.set_metadata(Constants::magic_for_reserved); + it = next; + parent_block = free_block.second; + free_block = find_free_index(free_block.second); + if (!free_block.first) + { + grow(); + return emplace(std::move(new_value)); + } + } + AllocatorTraits::construct(*this, std::addressof(*block), std::move(new_value)); + block.set_metadata(Constants::magic_for_direct_hit); + ++num_elements; + return { block.it(), true }; + } + } + + template + SKA_NOINLINE(std::pair) emplace_new_key(LinkedListIt parent, Args &&... args) + { + if (is_full()) + { + grow(); + return emplace(std::forward(args)...); + } + std::pair free_block = find_free_index(parent); + if (!free_block.first) + { + grow(); + return emplace(std::forward(args)...); + } + AllocatorTraits::construct(*this, std::addressof(*free_block.second), std::forward(args)...); + free_block.second.set_metadata(Constants::magic_for_list_entry); + parent.set_next(free_block.first); + ++num_elements; + return { free_block.second.it(), true }; + } + + LinkedListIt find_direct_hit(LinkedListIt child) const + { + size_t to_move_hash = hash_object(*child); + size_t to_move_index = hash_policy.index_for_hash(to_move_hash, num_slots_minus_one); + return { to_move_index, entries + to_move_index / BlockSize }; + } + LinkedListIt find_parent_block(LinkedListIt child) + { + LinkedListIt parent_block = find_direct_hit(child); + for (;;) + { + LinkedListIt next = parent_block.next(*this); + if (next == child) + return parent_block; + parent_block = next; + } + } + + std::pair find_free_index(LinkedListIt parent) const + { + for (int8_t jump_index = 1; jump_index < Constants::num_jump_distances; ++jump_index) + { + size_t index = hash_policy.keep_in_range(parent.index + Constants::jump_distances[jump_index], num_slots_minus_one); + BlockPointer block = entries + index / BlockSize; + if (block->control_bytes[index % BlockSize] == Constants::magic_for_empty) + return { jump_index, { index, block } }; + } + return { 0, {} }; + } + + void grow() + { + rehash(std::max(size_t(10), 2 * bucket_count())); + } + + size_t calculate_memory_requirement(size_t num_blocks) + { + size_t memory_required = sizeof(BlockType) * num_blocks; + memory_required += BlockSize; // for metadata of past-the-end pointer + return memory_required; + } + + void deallocate_data(BlockPointer begin, size_t num_slots_minus_one) + { + if (begin == BlockType::empty_block()) + return; + + ++num_slots_minus_one; + size_t num_blocks = num_slots_minus_one / BlockSize; + if (num_slots_minus_one % BlockSize) + ++num_blocks; + size_t memory = calculate_memory_requirement(num_blocks); + unsigned char * as_byte_pointer = reinterpret_cast(begin); + AllocatorTraits::deallocate(*this, typename AllocatorTraits::pointer(as_byte_pointer), memory); + } + + void reset_to_empty_state() + { + deallocate_data(entries, num_slots_minus_one); + entries = BlockType::empty_block(); + num_slots_minus_one = 0; + hash_policy.reset(); + } + + template + size_t hash_object(const U & key) + { + return static_cast(*this)(key); + } + template + size_t hash_object(const U & key) const + { + return static_cast(*this)(key); + } + template + bool compares_equal(const L & lhs, const R & rhs) + { + return static_cast(*this)(lhs, rhs); + } + + struct convertible_to_iterator + { + BlockPointer it; + size_t index; + + operator iterator() + { + if (it->control_bytes[index % BlockSize] == Constants::magic_for_empty) + return ++iterator{it, index}; + else + return { it, index }; + } + operator const_iterator() + { + if (it->control_bytes[index % BlockSize] == Constants::magic_for_empty) + return ++iterator{it, index}; + else + return { it, index }; + } + }; +}; +template +struct AlignmentOr8Bytes +{ + static constexpr size_t value = 8; +}; +template +struct AlignmentOr8Bytes= 1>::type> +{ + static constexpr size_t value = alignof(T); +}; +template +struct CalculateBytellBlockSize; +template +struct CalculateBytellBlockSize +{ + static constexpr size_t this_value = AlignmentOr8Bytes::value; + static constexpr size_t base_value = CalculateBytellBlockSize::value; + static constexpr size_t value = this_value > base_value ? this_value : base_value; +}; +template<> +struct CalculateBytellBlockSize<> +{ + static constexpr size_t value = 8; +}; +} + +template, typename E = std::equal_to, typename A = std::allocator > > +class bytell_hash_map + : public detailv8::sherwood_v8_table + < + std::pair, + K, + H, + detailv8::KeyOrValueHasher, H>, + E, + detailv8::KeyOrValueEquality, E>, + A, + typename std::allocator_traits::template rebind_alloc, + detailv8::CalculateBytellBlockSize::value + > +{ + using Table = detailv8::sherwood_v8_table + < + std::pair, + K, + H, + detailv8::KeyOrValueHasher, H>, + E, + detailv8::KeyOrValueEquality, E>, + A, + typename std::allocator_traits::template rebind_alloc, + detailv8::CalculateBytellBlockSize::value + >; +public: + + using key_type = K; + using mapped_type = V; + + using Table::Table; + bytell_hash_map() + { + } + + inline V & operator[](const K & key) + { + return emplace(key, convertible_to_value()).first->second; + } + inline V & operator[](K && key) + { + return emplace(std::move(key), convertible_to_value()).first->second; + } + V & at(const K & key) + { + auto found = this->find(key); + if (found == this->end()) + throw std::out_of_range("Argument passed to at() was not in the map."); + return found->second; + } + const V & at(const K & key) const + { + auto found = this->find(key); + if (found == this->end()) + throw std::out_of_range("Argument passed to at() was not in the map."); + return found->second; + } + + using Table::emplace; + std::pair emplace() + { + return emplace(key_type(), convertible_to_value()); + } + template + std::pair insert_or_assign(const key_type & key, M && m) + { + auto emplace_result = emplace(key, std::forward(m)); + if (!emplace_result.second) + emplace_result.first->second = std::forward(m); + return emplace_result; + } + template + std::pair insert_or_assign(key_type && key, M && m) + { + auto emplace_result = emplace(std::move(key), std::forward(m)); + if (!emplace_result.second) + emplace_result.first->second = std::forward(m); + return emplace_result; + } + template + typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m) + { + return insert_or_assign(key, std::forward(m)).first; + } + template + typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m) + { + return insert_or_assign(std::move(key), std::forward(m)).first; + } + + friend bool operator==(const bytell_hash_map & lhs, const bytell_hash_map & rhs) + { + if (lhs.size() != rhs.size()) + return false; + for (const typename Table::value_type & value : lhs) + { + auto found = rhs.find(value.first); + if (found == rhs.end()) + return false; + else if (value.second != found->second) + return false; + } + return true; + } + friend bool operator!=(const bytell_hash_map & lhs, const bytell_hash_map & rhs) + { + return !(lhs == rhs); + } + +private: + struct convertible_to_value + { + operator V() const + { + return V(); + } + }; +}; + +template, typename E = std::equal_to, typename A = std::allocator > +class bytell_hash_set + : public detailv8::sherwood_v8_table + < + T, + T, + H, + detailv8::functor_storage, + E, + detailv8::functor_storage, + A, + typename std::allocator_traits::template rebind_alloc, + detailv8::CalculateBytellBlockSize::value + > +{ + using Table = detailv8::sherwood_v8_table + < + T, + T, + H, + detailv8::functor_storage, + E, + detailv8::functor_storage, + A, + typename std::allocator_traits::template rebind_alloc, + detailv8::CalculateBytellBlockSize::value + >; +public: + + using key_type = T; + + using Table::Table; + bytell_hash_set() + { + } + + template + std::pair emplace(Args &&... args) + { + return Table::emplace(T(std::forward(args)...)); + } + std::pair emplace(const key_type & arg) + { + return Table::emplace(arg); + } + std::pair emplace(key_type & arg) + { + return Table::emplace(arg); + } + std::pair emplace(const key_type && arg) + { + return Table::emplace(std::move(arg)); + } + std::pair emplace(key_type && arg) + { + return Table::emplace(std::move(arg)); + } + + friend bool operator==(const bytell_hash_set & lhs, const bytell_hash_set & rhs) + { + if (lhs.size() != rhs.size()) + return false; + for (const T & value : lhs) + { + if (rhs.find(value) == rhs.end()) + return false; + } + return true; + } + friend bool operator!=(const bytell_hash_set & lhs, const bytell_hash_set & rhs) + { + return !(lhs == rhs); + } +}; + +} // end namespace ska diff --git a/examples/others/flat_hash_map.hpp b/examples/others/flat_hash_map.hpp new file mode 100644 index 00000000..ea20af93 --- /dev/null +++ b/examples/others/flat_hash_map.hpp @@ -0,0 +1,1496 @@ +// Copyright Malte Skarupke 2017. +// Distributed under the Boost Software License, Version 1.0. +// (See http://www.boost.org/LICENSE_1_0.txt) + +#pragma once + +#include +#include +#include +#include +#include +#include +#include +#include + +#ifdef _MSC_VER +#define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__ +#else +#define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline)) +#endif + +namespace ska +{ +struct prime_number_hash_policy; +struct power_of_two_hash_policy; +struct fibonacci_hash_policy; + +namespace detailv3 +{ +template +struct functor_storage : Functor +{ + functor_storage() = default; + functor_storage(const Functor & functor) + : Functor(functor) + { + } + template + Result operator()(Args &&... args) + { + return static_cast(*this)(std::forward(args)...); + } + template + Result operator()(Args &&... args) const + { + return static_cast(*this)(std::forward(args)...); + } +}; +template +struct functor_storage +{ + typedef Result (*function_ptr)(Args...); + function_ptr function; + functor_storage(function_ptr function) + : function(function) + { + } + Result operator()(Args... args) const + { + return function(std::forward(args)...); + } + operator function_ptr &() + { + return function; + } + operator const function_ptr &() + { + return function; + } +}; +template +struct KeyOrValueHasher : functor_storage +{ + typedef functor_storage hasher_storage; + KeyOrValueHasher() = default; + KeyOrValueHasher(const hasher & hash) + : hasher_storage(hash) + { + } + size_t operator()(const key_type & key) + { + return static_cast(*this)(key); + } + size_t operator()(const key_type & key) const + { + return static_cast(*this)(key); + } + size_t operator()(const value_type & value) + { + return static_cast(*this)(value.first); + } + size_t operator()(const value_type & value) const + { + return static_cast(*this)(value.first); + } + template + size_t operator()(const std::pair & value) + { + return static_cast(*this)(value.first); + } + template + size_t operator()(const std::pair & value) const + { + return static_cast(*this)(value.first); + } +}; +template +struct KeyOrValueEquality : functor_storage +{ + typedef functor_storage equality_storage; + KeyOrValueEquality() = default; + KeyOrValueEquality(const key_equal & equality) + : equality_storage(equality) + { + } + bool operator()(const key_type & lhs, const key_type & rhs) + { + return static_cast(*this)(lhs, rhs); + } + bool operator()(const key_type & lhs, const value_type & rhs) + { + return static_cast(*this)(lhs, rhs.first); + } + bool operator()(const value_type & lhs, const key_type & rhs) + { + return static_cast(*this)(lhs.first, rhs); + } + bool operator()(const value_type & lhs, const value_type & rhs) + { + return static_cast(*this)(lhs.first, rhs.first); + } + template + bool operator()(const key_type & lhs, const std::pair & rhs) + { + return static_cast(*this)(lhs, rhs.first); + } + template + bool operator()(const std::pair & lhs, const key_type & rhs) + { + return static_cast(*this)(lhs.first, rhs); + } + template + bool operator()(const value_type & lhs, const std::pair & rhs) + { + return static_cast(*this)(lhs.first, rhs.first); + } + template + bool operator()(const std::pair & lhs, const value_type & rhs) + { + return static_cast(*this)(lhs.first, rhs.first); + } + template + bool operator()(const std::pair & lhs, const std::pair & rhs) + { + return static_cast(*this)(lhs.first, rhs.first); + } +}; +static constexpr int8_t min_lookups = 4; +template +struct sherwood_v3_entry +{ + sherwood_v3_entry() + { + } + sherwood_v3_entry(int8_t distance_from_desired) + : distance_from_desired(distance_from_desired) + { + } + ~sherwood_v3_entry() + { + } + static sherwood_v3_entry * empty_default_table() + { + static sherwood_v3_entry result[min_lookups] = { {}, {}, {}, {special_end_value} }; + return result; + } + + bool has_value() const + { + return distance_from_desired >= 0; + } + bool is_empty() const + { + return distance_from_desired < 0; + } + bool is_at_desired_position() const + { + return distance_from_desired <= 0; + } + template + void emplace(int8_t distance, Args &&... args) + { + new (std::addressof(value)) T(std::forward(args)...); + distance_from_desired = distance; + } + + void destroy_value() + { + value.~T(); + distance_from_desired = -1; + } + + int8_t distance_from_desired = -1; + static constexpr int8_t special_end_value = 0; + union { T value; }; +}; + +inline int8_t log2(size_t value) +{ + static constexpr int8_t table[64] = + { + 63, 0, 58, 1, 59, 47, 53, 2, + 60, 39, 48, 27, 54, 33, 42, 3, + 61, 51, 37, 40, 49, 18, 28, 20, + 55, 30, 34, 11, 43, 14, 22, 4, + 62, 57, 46, 52, 38, 26, 32, 41, + 50, 36, 17, 19, 29, 10, 13, 21, + 56, 45, 25, 31, 35, 16, 9, 12, + 44, 24, 15, 8, 23, 7, 6, 5 + }; + value |= value >> 1; + value |= value >> 2; + value |= value >> 4; + value |= value >> 8; + value |= value >> 16; + value |= value >> 32; + return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58]; +} + +template +struct AssignIfTrue +{ + void operator()(T & lhs, const T & rhs) + { + lhs = rhs; + } + void operator()(T & lhs, T && rhs) + { + lhs = std::move(rhs); + } +}; +template +struct AssignIfTrue +{ + void operator()(T &, const T &) + { + } + void operator()(T &, T &&) + { + } +}; + +inline size_t next_power_of_two(size_t i) +{ + --i; + i |= i >> 1; + i |= i >> 2; + i |= i >> 4; + i |= i >> 8; + i |= i >> 16; + i |= i >> 32; + ++i; + return i; +} + +template using void_t = void; + +template +struct HashPolicySelector +{ + typedef fibonacci_hash_policy type; +}; +template +struct HashPolicySelector> +{ + typedef typename T::hash_policy type; +}; + +template +class sherwood_v3_table : private EntryAlloc, private Hasher, private Equal +{ + using Entry = detailv3::sherwood_v3_entry; + using AllocatorTraits = std::allocator_traits; + using EntryPointer = typename AllocatorTraits::pointer; + struct convertible_to_iterator; + +public: + + using value_type = T; + using size_type = size_t; + using difference_type = std::ptrdiff_t; + using hasher = ArgumentHash; + using key_equal = ArgumentEqual; + using allocator_type = EntryAlloc; + using reference = value_type &; + using const_reference = const value_type &; + using pointer = value_type *; + using const_pointer = const value_type *; + + sherwood_v3_table() + { + } + explicit sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) + : EntryAlloc(alloc), Hasher(hash), Equal(equal) + { + rehash(bucket_count); + } + sherwood_v3_table(size_type bucket_count, const ArgumentAlloc & alloc) + : sherwood_v3_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc) + { + } + sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) + : sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc) + { + } + explicit sherwood_v3_table(const ArgumentAlloc & alloc) + : EntryAlloc(alloc) + { + } + template + sherwood_v3_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) + : sherwood_v3_table(bucket_count, hash, equal, alloc) + { + insert(first, last); + } + template + sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc) + : sherwood_v3_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc) + { + } + template + sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) + : sherwood_v3_table(first, last, bucket_count, hash, ArgumentEqual(), alloc) + { + } + sherwood_v3_table(std::initializer_list il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc()) + : sherwood_v3_table(bucket_count, hash, equal, alloc) + { + if (bucket_count == 0) + rehash(il.size()); + insert(il.begin(), il.end()); + } + sherwood_v3_table(std::initializer_list il, size_type bucket_count, const ArgumentAlloc & alloc) + : sherwood_v3_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc) + { + } + sherwood_v3_table(std::initializer_list il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc) + : sherwood_v3_table(il, bucket_count, hash, ArgumentEqual(), alloc) + { + } + sherwood_v3_table(const sherwood_v3_table & other) + : sherwood_v3_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator())) + { + } + sherwood_v3_table(const sherwood_v3_table & other, const ArgumentAlloc & alloc) + : EntryAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor) + { + rehash_for_other_container(other); + try + { + insert(other.begin(), other.end()); + } + catch(...) + { + clear(); + deallocate_data(entries, num_slots_minus_one, max_lookups); + throw; + } + } + sherwood_v3_table(sherwood_v3_table && other) noexcept + : EntryAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other)) + { + swap_pointers(other); + } + sherwood_v3_table(sherwood_v3_table && other, const ArgumentAlloc & alloc) noexcept + : EntryAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other)) + { + swap_pointers(other); + } + sherwood_v3_table & operator=(const sherwood_v3_table & other) + { + if (this == std::addressof(other)) + return *this; + + clear(); + if (AllocatorTraits::propagate_on_container_copy_assignment::value) + { + if (static_cast(*this) != static_cast(other)) + { + reset_to_empty_state(); + } + AssignIfTrue()(*this, other); + } + _max_load_factor = other._max_load_factor; + static_cast(*this) = other; + static_cast(*this) = other; + rehash_for_other_container(other); + insert(other.begin(), other.end()); + return *this; + } + sherwood_v3_table & operator=(sherwood_v3_table && other) noexcept + { + if (this == std::addressof(other)) + return *this; + else if (AllocatorTraits::propagate_on_container_move_assignment::value) + { + clear(); + reset_to_empty_state(); + AssignIfTrue()(*this, std::move(other)); + swap_pointers(other); + } + else if (static_cast(*this) == static_cast(other)) + { + swap_pointers(other); + } + else + { + clear(); + _max_load_factor = other._max_load_factor; + rehash_for_other_container(other); + for (T & elem : other) + emplace(std::move(elem)); + other.clear(); + } + static_cast(*this) = std::move(other); + static_cast(*this) = std::move(other); + return *this; + } + ~sherwood_v3_table() + { + clear(); + deallocate_data(entries, num_slots_minus_one, max_lookups); + } + + const allocator_type & get_allocator() const + { + return static_cast(*this); + } + const ArgumentEqual & key_eq() const + { + return static_cast(*this); + } + const ArgumentHash & hash_function() const + { + return static_cast(*this); + } + + template + struct templated_iterator + { + templated_iterator() = default; + templated_iterator(EntryPointer current) + : current(current) + { + } + EntryPointer current = EntryPointer(); + + using iterator_category = std::forward_iterator_tag; + using value_type = ValueType; + using difference_type = ptrdiff_t; + using pointer = ValueType *; + using reference = ValueType &; + + friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs) + { + return lhs.current == rhs.current; + } + friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs) + { + return !(lhs == rhs); + } + + templated_iterator & operator++() + { + do + { + ++current; + } + while(current->is_empty()); + return *this; + } + templated_iterator operator++(int) + { + templated_iterator copy(*this); + ++*this; + return copy; + } + + ValueType & operator*() const + { + return current->value; + } + ValueType * operator->() const + { + return std::addressof(current->value); + } + + operator templated_iterator() const + { + return { current }; + } + }; + using iterator = templated_iterator; + using const_iterator = templated_iterator; + + iterator begin() + { + for (EntryPointer it = entries;; ++it) + { + if (it->has_value()) + return { it }; + } + } + const_iterator begin() const + { + for (EntryPointer it = entries;; ++it) + { + if (it->has_value()) + return { it }; + } + } + const_iterator cbegin() const + { + return begin(); + } + iterator end() + { + return { entries + static_cast(num_slots_minus_one + max_lookups) }; + } + const_iterator end() const + { + return { entries + static_cast(num_slots_minus_one + max_lookups) }; + } + const_iterator cend() const + { + return end(); + } + + iterator find(const FindKey & key) + { + size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); + EntryPointer it = entries + ptrdiff_t(index); + for (int8_t distance = 0; it->distance_from_desired >= distance; ++distance, ++it) + { + if (compares_equal(key, it->value)) + return { it }; + } + return end(); + } + const_iterator find(const FindKey & key) const + { + return const_cast(this)->find(key); + } + size_t count(const FindKey & key) const + { + return find(key) == end() ? 0 : 1; + } + std::pair equal_range(const FindKey & key) + { + iterator found = find(key); + if (found == end()) + return { found, found }; + else + return { found, std::next(found) }; + } + std::pair equal_range(const FindKey & key) const + { + const_iterator found = find(key); + if (found == end()) + return { found, found }; + else + return { found, std::next(found) }; + } + + template + std::pair emplace(Key && key, Args &&... args) + { + size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); + EntryPointer current_entry = entries + ptrdiff_t(index); + int8_t distance_from_desired = 0; + for (; current_entry->distance_from_desired >= distance_from_desired; ++current_entry, ++distance_from_desired) + { + if (compares_equal(key, current_entry->value)) + return { { current_entry }, false }; + } + return emplace_new_key(distance_from_desired, current_entry, std::forward(key), std::forward(args)...); + } + + std::pair insert(const value_type & value) + { + return emplace(value); + } + std::pair insert(value_type && value) + { + return emplace(std::move(value)); + } + template + iterator emplace_hint(const_iterator, Args &&... args) + { + return emplace(std::forward(args)...).first; + } + iterator insert(const_iterator, const value_type & value) + { + return emplace(value).first; + } + iterator insert(const_iterator, value_type && value) + { + return emplace(std::move(value)).first; + } + + template + void insert(It begin, It end) + { + for (; begin != end; ++begin) + { + emplace(*begin); + } + } + void insert(std::initializer_list il) + { + insert(il.begin(), il.end()); + } + + void rehash(size_t num_buckets) + { + num_buckets = std::max(num_buckets, static_cast(std::ceil(num_elements / static_cast(_max_load_factor)))); + if (num_buckets == 0) + { + reset_to_empty_state(); + return; + } + auto new_prime_index = hash_policy.next_size_over(num_buckets); + if (num_buckets == bucket_count()) + return; + int8_t new_max_lookups = compute_max_lookups(num_buckets); + EntryPointer new_buckets(AllocatorTraits::allocate(*this, num_buckets + new_max_lookups)); + EntryPointer special_end_item = new_buckets + static_cast(num_buckets + new_max_lookups - 1); + for (EntryPointer it = new_buckets; it != special_end_item; ++it) + it->distance_from_desired = -1; + special_end_item->distance_from_desired = Entry::special_end_value; + std::swap(entries, new_buckets); + std::swap(num_slots_minus_one, num_buckets); + --num_slots_minus_one; + hash_policy.commit(new_prime_index); + int8_t old_max_lookups = max_lookups; + max_lookups = new_max_lookups; + num_elements = 0; + for (EntryPointer it = new_buckets, end = it + static_cast(num_buckets + old_max_lookups); it != end; ++it) + { + if (it->has_value()) + { + emplace(std::move(it->value)); + it->destroy_value(); + } + } + deallocate_data(new_buckets, num_buckets, old_max_lookups); + } + + void reserve(size_t num_elements) + { + size_t required_buckets = num_buckets_for_reserve(num_elements); + if (required_buckets > bucket_count()) + rehash(required_buckets); + } + + // the return value is a type that can be converted to an iterator + // the reason for doing this is that it's not free to find the + // iterator pointing at the next element. if you care about the + // next iterator, turn the return value into an iterator + convertible_to_iterator erase(const_iterator to_erase) + { + EntryPointer current = to_erase.current; + current->destroy_value(); + --num_elements; + for (EntryPointer next = current + ptrdiff_t(1); !next->is_at_desired_position(); ++current, ++next) + { + current->emplace(next->distance_from_desired - 1, std::move(next->value)); + next->destroy_value(); + } + return { to_erase.current }; + } + + iterator erase(const_iterator begin_it, const_iterator end_it) + { + if (begin_it == end_it) + return { begin_it.current }; + for (EntryPointer it = begin_it.current, end = end_it.current; it != end; ++it) + { + if (it->has_value()) + { + it->destroy_value(); + --num_elements; + } + } + if (end_it == this->end()) + return this->end(); + ptrdiff_t num_to_move = std::min(static_cast(end_it.current->distance_from_desired), end_it.current - begin_it.current); + EntryPointer to_return = end_it.current - num_to_move; + for (EntryPointer it = end_it.current; !it->is_at_desired_position();) + { + EntryPointer target = it - num_to_move; + target->emplace(it->distance_from_desired - num_to_move, std::move(it->value)); + it->destroy_value(); + ++it; + num_to_move = std::min(static_cast(it->distance_from_desired), num_to_move); + } + return { to_return }; + } + + size_t erase(const FindKey & key) + { + auto found = find(key); + if (found == end()) + return 0; + else + { + erase(found); + return 1; + } + } + + void clear() + { + for (EntryPointer it = entries, end = it + static_cast(num_slots_minus_one + max_lookups); it != end; ++it) + { + if (it->has_value()) + it->destroy_value(); + } + num_elements = 0; + } + + void shrink_to_fit() + { + rehash_for_other_container(*this); + } + + void swap(sherwood_v3_table & other) + { + using std::swap; + swap_pointers(other); + swap(static_cast(*this), static_cast(other)); + swap(static_cast(*this), static_cast(other)); + if (AllocatorTraits::propagate_on_container_swap::value) + swap(static_cast(*this), static_cast(other)); + } + + size_t size() const + { + return num_elements; + } + size_t max_size() const + { + return (AllocatorTraits::max_size(*this)) / sizeof(Entry); + } + size_t bucket_count() const + { + return num_slots_minus_one ? num_slots_minus_one + 1 : 0; + } + size_type max_bucket_count() const + { + return (AllocatorTraits::max_size(*this) - min_lookups) / sizeof(Entry); + } + size_t bucket(const FindKey & key) const + { + return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); + } + float load_factor() const + { + size_t buckets = bucket_count(); + if (buckets) + return static_cast(num_elements) / bucket_count(); + else + return 0; + } + void max_load_factor(float value) + { + _max_load_factor = value; + } + float max_load_factor() const + { + return _max_load_factor; + } + + bool empty() const + { + return num_elements == 0; + } + +private: + EntryPointer entries = Entry::empty_default_table(); + size_t num_slots_minus_one = 0; + typename HashPolicySelector::type hash_policy; + int8_t max_lookups = detailv3::min_lookups - 1; + float _max_load_factor = 0.5f; + size_t num_elements = 0; + + static int8_t compute_max_lookups(size_t num_buckets) + { + int8_t desired = detailv3::log2(num_buckets); + return std::max(detailv3::min_lookups, desired); + } + + size_t num_buckets_for_reserve(size_t num_elements) const + { + return static_cast(std::ceil(num_elements / std::min(0.5, static_cast(_max_load_factor)))); + } + void rehash_for_other_container(const sherwood_v3_table & other) + { + rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count())); + } + + void swap_pointers(sherwood_v3_table & other) + { + using std::swap; + swap(hash_policy, other.hash_policy); + swap(entries, other.entries); + swap(num_slots_minus_one, other.num_slots_minus_one); + swap(num_elements, other.num_elements); + swap(max_lookups, other.max_lookups); + swap(_max_load_factor, other._max_load_factor); + } + + template + SKA_NOINLINE(std::pair) emplace_new_key(int8_t distance_from_desired, EntryPointer current_entry, Key && key, Args &&... args) + { + using std::swap; + if (num_slots_minus_one == 0 || distance_from_desired == max_lookups || num_elements + 1 > (num_slots_minus_one + 1) * static_cast(_max_load_factor)) + { + grow(); + return emplace(std::forward(key), std::forward(args)...); + } + else if (current_entry->is_empty()) + { + current_entry->emplace(distance_from_desired, std::forward(key), std::forward(args)...); + ++num_elements; + return { { current_entry }, true }; + } + value_type to_insert(std::forward(key), std::forward(args)...); + swap(distance_from_desired, current_entry->distance_from_desired); + swap(to_insert, current_entry->value); + iterator result = { current_entry }; + for (++distance_from_desired, ++current_entry;; ++current_entry) + { + if (current_entry->is_empty()) + { + current_entry->emplace(distance_from_desired, std::move(to_insert)); + ++num_elements; + return { result, true }; + } + else if (current_entry->distance_from_desired < distance_from_desired) + { + swap(distance_from_desired, current_entry->distance_from_desired); + swap(to_insert, current_entry->value); + ++distance_from_desired; + } + else + { + ++distance_from_desired; + if (distance_from_desired == max_lookups) + { + swap(to_insert, result.current->value); + grow(); + return emplace(std::move(to_insert)); + } + } + } + } + + void grow() + { + rehash(std::max(size_t(4), 2 * bucket_count())); + } + + void deallocate_data(EntryPointer begin, size_t num_slots_minus_one, int8_t max_lookups) + { + if (begin != Entry::empty_default_table()) + { + AllocatorTraits::deallocate(*this, begin, num_slots_minus_one + max_lookups + 1); + } + } + + void reset_to_empty_state() + { + deallocate_data(entries, num_slots_minus_one, max_lookups); + entries = Entry::empty_default_table(); + num_slots_minus_one = 0; + hash_policy.reset(); + max_lookups = detailv3::min_lookups - 1; + } + + template + size_t hash_object(const U & key) + { + return static_cast(*this)(key); + } + template + size_t hash_object(const U & key) const + { + return static_cast(*this)(key); + } + template + bool compares_equal(const L & lhs, const R & rhs) + { + return static_cast(*this)(lhs, rhs); + } + + struct convertible_to_iterator + { + EntryPointer it; + + operator iterator() + { + if (it->has_value()) + return { it }; + else + return ++iterator{it}; + } + operator const_iterator() + { + if (it->has_value()) + return { it }; + else + return ++const_iterator{it}; + } + }; + +}; +} + +struct prime_number_hash_policy +{ + static size_t mod0(size_t) { return 0llu; } + static size_t mod2(size_t hash) { return hash % 2llu; } + static size_t mod3(size_t hash) { return hash % 3llu; } + static size_t mod5(size_t hash) { return hash % 5llu; } + static size_t mod7(size_t hash) { return hash % 7llu; } + static size_t mod11(size_t hash) { return hash % 11llu; } + static size_t mod13(size_t hash) { return hash % 13llu; } + static size_t mod17(size_t hash) { return hash % 17llu; } + static size_t mod23(size_t hash) { return hash % 23llu; } + static size_t mod29(size_t hash) { return hash % 29llu; } + static size_t mod37(size_t hash) { return hash % 37llu; } + static size_t mod47(size_t hash) { return hash % 47llu; } + static size_t mod59(size_t hash) { return hash % 59llu; } + static size_t mod73(size_t hash) { return hash % 73llu; } + static size_t mod97(size_t hash) { return hash % 97llu; } + static size_t mod127(size_t hash) { return hash % 127llu; } + static size_t mod151(size_t hash) { return hash % 151llu; } + static size_t mod197(size_t hash) { return hash % 197llu; } + static size_t mod251(size_t hash) { return hash % 251llu; } + static size_t mod313(size_t hash) { return hash % 313llu; } + static size_t mod397(size_t hash) { return hash % 397llu; } + static size_t mod499(size_t hash) { return hash % 499llu; } + static size_t mod631(size_t hash) { return hash % 631llu; } + static size_t mod797(size_t hash) { return hash % 797llu; } + static size_t mod1009(size_t hash) { return hash % 1009llu; } + static size_t mod1259(size_t hash) { return hash % 1259llu; } + static size_t mod1597(size_t hash) { return hash % 1597llu; } + static size_t mod2011(size_t hash) { return hash % 2011llu; } + static size_t mod2539(size_t hash) { return hash % 2539llu; } + static size_t mod3203(size_t hash) { return hash % 3203llu; } + static size_t mod4027(size_t hash) { return hash % 4027llu; } + static size_t mod5087(size_t hash) { return hash % 5087llu; } + static size_t mod6421(size_t hash) { return hash % 6421llu; } + static size_t mod8089(size_t hash) { return hash % 8089llu; } + static size_t mod10193(size_t hash) { return hash % 10193llu; } + static size_t mod12853(size_t hash) { return hash % 12853llu; } + static size_t mod16193(size_t hash) { return hash % 16193llu; } + static size_t mod20399(size_t hash) { return hash % 20399llu; } + static size_t mod25717(size_t hash) { return hash % 25717llu; } + static size_t mod32401(size_t hash) { return hash % 32401llu; } + static size_t mod40823(size_t hash) { return hash % 40823llu; } + static size_t mod51437(size_t hash) { return hash % 51437llu; } + static size_t mod64811(size_t hash) { return hash % 64811llu; } + static size_t mod81649(size_t hash) { return hash % 81649llu; } + static size_t mod102877(size_t hash) { return hash % 102877llu; } + static size_t mod129607(size_t hash) { return hash % 129607llu; } + static size_t mod163307(size_t hash) { return hash % 163307llu; } + static size_t mod205759(size_t hash) { return hash % 205759llu; } + static size_t mod259229(size_t hash) { return hash % 259229llu; } + static size_t mod326617(size_t hash) { return hash % 326617llu; } + static size_t mod411527(size_t hash) { return hash % 411527llu; } + static size_t mod518509(size_t hash) { return hash % 518509llu; } + static size_t mod653267(size_t hash) { return hash % 653267llu; } + static size_t mod823117(size_t hash) { return hash % 823117llu; } + static size_t mod1037059(size_t hash) { return hash % 1037059llu; } + static size_t mod1306601(size_t hash) { return hash % 1306601llu; } + static size_t mod1646237(size_t hash) { return hash % 1646237llu; } + static size_t mod2074129(size_t hash) { return hash % 2074129llu; } + static size_t mod2613229(size_t hash) { return hash % 2613229llu; } + static size_t mod3292489(size_t hash) { return hash % 3292489llu; } + static size_t mod4148279(size_t hash) { return hash % 4148279llu; } + static size_t mod5226491(size_t hash) { return hash % 5226491llu; } + static size_t mod6584983(size_t hash) { return hash % 6584983llu; } + static size_t mod8296553(size_t hash) { return hash % 8296553llu; } + static size_t mod10453007(size_t hash) { return hash % 10453007llu; } + static size_t mod13169977(size_t hash) { return hash % 13169977llu; } + static size_t mod16593127(size_t hash) { return hash % 16593127llu; } + static size_t mod20906033(size_t hash) { return hash % 20906033llu; } + static size_t mod26339969(size_t hash) { return hash % 26339969llu; } + static size_t mod33186281(size_t hash) { return hash % 33186281llu; } + static size_t mod41812097(size_t hash) { return hash % 41812097llu; } + static size_t mod52679969(size_t hash) { return hash % 52679969llu; } + static size_t mod66372617(size_t hash) { return hash % 66372617llu; } + static size_t mod83624237(size_t hash) { return hash % 83624237llu; } + static size_t mod105359939(size_t hash) { return hash % 105359939llu; } + static size_t mod132745199(size_t hash) { return hash % 132745199llu; } + static size_t mod167248483(size_t hash) { return hash % 167248483llu; } + static size_t mod210719881(size_t hash) { return hash % 210719881llu; } + static size_t mod265490441(size_t hash) { return hash % 265490441llu; } + static size_t mod334496971(size_t hash) { return hash % 334496971llu; } + static size_t mod421439783(size_t hash) { return hash % 421439783llu; } + static size_t mod530980861(size_t hash) { return hash % 530980861llu; } + static size_t mod668993977(size_t hash) { return hash % 668993977llu; } + static size_t mod842879579(size_t hash) { return hash % 842879579llu; } + static size_t mod1061961721(size_t hash) { return hash % 1061961721llu; } + static size_t mod1337987929(size_t hash) { return hash % 1337987929llu; } + static size_t mod1685759167(size_t hash) { return hash % 1685759167llu; } + static size_t mod2123923447(size_t hash) { return hash % 2123923447llu; } + static size_t mod2675975881(size_t hash) { return hash % 2675975881llu; } + static size_t mod3371518343(size_t hash) { return hash % 3371518343llu; } + static size_t mod4247846927(size_t hash) { return hash % 4247846927llu; } + static size_t mod5351951779(size_t hash) { return hash % 5351951779llu; } + static size_t mod6743036717(size_t hash) { return hash % 6743036717llu; } + static size_t mod8495693897(size_t hash) { return hash % 8495693897llu; } + static size_t mod10703903591(size_t hash) { return hash % 10703903591llu; } + static size_t mod13486073473(size_t hash) { return hash % 13486073473llu; } + static size_t mod16991387857(size_t hash) { return hash % 16991387857llu; } + static size_t mod21407807219(size_t hash) { return hash % 21407807219llu; } + static size_t mod26972146961(size_t hash) { return hash % 26972146961llu; } + static size_t mod33982775741(size_t hash) { return hash % 33982775741llu; } + static size_t mod42815614441(size_t hash) { return hash % 42815614441llu; } + static size_t mod53944293929(size_t hash) { return hash % 53944293929llu; } + static size_t mod67965551447(size_t hash) { return hash % 67965551447llu; } + static size_t mod85631228929(size_t hash) { return hash % 85631228929llu; } + static size_t mod107888587883(size_t hash) { return hash % 107888587883llu; } + static size_t mod135931102921(size_t hash) { return hash % 135931102921llu; } + static size_t mod171262457903(size_t hash) { return hash % 171262457903llu; } + static size_t mod215777175787(size_t hash) { return hash % 215777175787llu; } + static size_t mod271862205833(size_t hash) { return hash % 271862205833llu; } + static size_t mod342524915839(size_t hash) { return hash % 342524915839llu; } + static size_t mod431554351609(size_t hash) { return hash % 431554351609llu; } + static size_t mod543724411781(size_t hash) { return hash % 543724411781llu; } + static size_t mod685049831731(size_t hash) { return hash % 685049831731llu; } + static size_t mod863108703229(size_t hash) { return hash % 863108703229llu; } + static size_t mod1087448823553(size_t hash) { return hash % 1087448823553llu; } + static size_t mod1370099663459(size_t hash) { return hash % 1370099663459llu; } + static size_t mod1726217406467(size_t hash) { return hash % 1726217406467llu; } + static size_t mod2174897647073(size_t hash) { return hash % 2174897647073llu; } + static size_t mod2740199326961(size_t hash) { return hash % 2740199326961llu; } + static size_t mod3452434812973(size_t hash) { return hash % 3452434812973llu; } + static size_t mod4349795294267(size_t hash) { return hash % 4349795294267llu; } + static size_t mod5480398654009(size_t hash) { return hash % 5480398654009llu; } + static size_t mod6904869625999(size_t hash) { return hash % 6904869625999llu; } + static size_t mod8699590588571(size_t hash) { return hash % 8699590588571llu; } + static size_t mod10960797308051(size_t hash) { return hash % 10960797308051llu; } + static size_t mod13809739252051(size_t hash) { return hash % 13809739252051llu; } + static size_t mod17399181177241(size_t hash) { return hash % 17399181177241llu; } + static size_t mod21921594616111(size_t hash) { return hash % 21921594616111llu; } + static size_t mod27619478504183(size_t hash) { return hash % 27619478504183llu; } + static size_t mod34798362354533(size_t hash) { return hash % 34798362354533llu; } + static size_t mod43843189232363(size_t hash) { return hash % 43843189232363llu; } + static size_t mod55238957008387(size_t hash) { return hash % 55238957008387llu; } + static size_t mod69596724709081(size_t hash) { return hash % 69596724709081llu; } + static size_t mod87686378464759(size_t hash) { return hash % 87686378464759llu; } + static size_t mod110477914016779(size_t hash) { return hash % 110477914016779llu; } + static size_t mod139193449418173(size_t hash) { return hash % 139193449418173llu; } + static size_t mod175372756929481(size_t hash) { return hash % 175372756929481llu; } + static size_t mod220955828033581(size_t hash) { return hash % 220955828033581llu; } + static size_t mod278386898836457(size_t hash) { return hash % 278386898836457llu; } + static size_t mod350745513859007(size_t hash) { return hash % 350745513859007llu; } + static size_t mod441911656067171(size_t hash) { return hash % 441911656067171llu; } + static size_t mod556773797672909(size_t hash) { return hash % 556773797672909llu; } + static size_t mod701491027718027(size_t hash) { return hash % 701491027718027llu; } + static size_t mod883823312134381(size_t hash) { return hash % 883823312134381llu; } + static size_t mod1113547595345903(size_t hash) { return hash % 1113547595345903llu; } + static size_t mod1402982055436147(size_t hash) { return hash % 1402982055436147llu; } + static size_t mod1767646624268779(size_t hash) { return hash % 1767646624268779llu; } + static size_t mod2227095190691797(size_t hash) { return hash % 2227095190691797llu; } + static size_t mod2805964110872297(size_t hash) { return hash % 2805964110872297llu; } + static size_t mod3535293248537579(size_t hash) { return hash % 3535293248537579llu; } + static size_t mod4454190381383713(size_t hash) { return hash % 4454190381383713llu; } + static size_t mod5611928221744609(size_t hash) { return hash % 5611928221744609llu; } + static size_t mod7070586497075177(size_t hash) { return hash % 7070586497075177llu; } + static size_t mod8908380762767489(size_t hash) { return hash % 8908380762767489llu; } + static size_t mod11223856443489329(size_t hash) { return hash % 11223856443489329llu; } + static size_t mod14141172994150357(size_t hash) { return hash % 14141172994150357llu; } + static size_t mod17816761525534927(size_t hash) { return hash % 17816761525534927llu; } + static size_t mod22447712886978529(size_t hash) { return hash % 22447712886978529llu; } + static size_t mod28282345988300791(size_t hash) { return hash % 28282345988300791llu; } + static size_t mod35633523051069991(size_t hash) { return hash % 35633523051069991llu; } + static size_t mod44895425773957261(size_t hash) { return hash % 44895425773957261llu; } + static size_t mod56564691976601587(size_t hash) { return hash % 56564691976601587llu; } + static size_t mod71267046102139967(size_t hash) { return hash % 71267046102139967llu; } + static size_t mod89790851547914507(size_t hash) { return hash % 89790851547914507llu; } + static size_t mod113129383953203213(size_t hash) { return hash % 113129383953203213llu; } + static size_t mod142534092204280003(size_t hash) { return hash % 142534092204280003llu; } + static size_t mod179581703095829107(size_t hash) { return hash % 179581703095829107llu; } + static size_t mod226258767906406483(size_t hash) { return hash % 226258767906406483llu; } + static size_t mod285068184408560057(size_t hash) { return hash % 285068184408560057llu; } + static size_t mod359163406191658253(size_t hash) { return hash % 359163406191658253llu; } + static size_t mod452517535812813007(size_t hash) { return hash % 452517535812813007llu; } + static size_t mod570136368817120201(size_t hash) { return hash % 570136368817120201llu; } + static size_t mod718326812383316683(size_t hash) { return hash % 718326812383316683llu; } + static size_t mod905035071625626043(size_t hash) { return hash % 905035071625626043llu; } + static size_t mod1140272737634240411(size_t hash) { return hash % 1140272737634240411llu; } + static size_t mod1436653624766633509(size_t hash) { return hash % 1436653624766633509llu; } + static size_t mod1810070143251252131(size_t hash) { return hash % 1810070143251252131llu; } + static size_t mod2280545475268481167(size_t hash) { return hash % 2280545475268481167llu; } + static size_t mod2873307249533267101(size_t hash) { return hash % 2873307249533267101llu; } + static size_t mod3620140286502504283(size_t hash) { return hash % 3620140286502504283llu; } + static size_t mod4561090950536962147(size_t hash) { return hash % 4561090950536962147llu; } + static size_t mod5746614499066534157(size_t hash) { return hash % 5746614499066534157llu; } + static size_t mod7240280573005008577(size_t hash) { return hash % 7240280573005008577llu; } + static size_t mod9122181901073924329(size_t hash) { return hash % 9122181901073924329llu; } + static size_t mod11493228998133068689(size_t hash) { return hash % 11493228998133068689llu; } + static size_t mod14480561146010017169(size_t hash) { return hash % 14480561146010017169llu; } + static size_t mod18446744073709551557(size_t hash) { return hash % 18446744073709551557llu; } + + using mod_function = size_t (*)(size_t); + + mod_function next_size_over(size_t & size) const + { + // prime numbers generated by the following method: + // 1. start with a prime p = 2 + // 2. go to wolfram alpha and get p = NextPrime(2 * p) + // 3. repeat 2. until you overflow 64 bits + // you now have large gaps which you would hit if somebody called reserve() with an unlucky number. + // 4. to fill the gaps for every prime p go to wolfram alpha and get ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in the gaps + // 5. get PrevPrime(2^64) and put it at the end + static constexpr const size_t prime_list[] = + { + 2llu, 3llu, 5llu, 7llu, 11llu, 13llu, 17llu, 23llu, 29llu, 37llu, 47llu, + 59llu, 73llu, 97llu, 127llu, 151llu, 197llu, 251llu, 313llu, 397llu, + 499llu, 631llu, 797llu, 1009llu, 1259llu, 1597llu, 2011llu, 2539llu, + 3203llu, 4027llu, 5087llu, 6421llu, 8089llu, 10193llu, 12853llu, 16193llu, + 20399llu, 25717llu, 32401llu, 40823llu, 51437llu, 64811llu, 81649llu, + 102877llu, 129607llu, 163307llu, 205759llu, 259229llu, 326617llu, + 411527llu, 518509llu, 653267llu, 823117llu, 1037059llu, 1306601llu, + 1646237llu, 2074129llu, 2613229llu, 3292489llu, 4148279llu, 5226491llu, + 6584983llu, 8296553llu, 10453007llu, 13169977llu, 16593127llu, 20906033llu, + 26339969llu, 33186281llu, 41812097llu, 52679969llu, 66372617llu, + 83624237llu, 105359939llu, 132745199llu, 167248483llu, 210719881llu, + 265490441llu, 334496971llu, 421439783llu, 530980861llu, 668993977llu, + 842879579llu, 1061961721llu, 1337987929llu, 1685759167llu, 2123923447llu, + 2675975881llu, 3371518343llu, 4247846927llu, 5351951779llu, 6743036717llu, + 8495693897llu, 10703903591llu, 13486073473llu, 16991387857llu, + 21407807219llu, 26972146961llu, 33982775741llu, 42815614441llu, + 53944293929llu, 67965551447llu, 85631228929llu, 107888587883llu, + 135931102921llu, 171262457903llu, 215777175787llu, 271862205833llu, + 342524915839llu, 431554351609llu, 543724411781llu, 685049831731llu, + 863108703229llu, 1087448823553llu, 1370099663459llu, 1726217406467llu, + 2174897647073llu, 2740199326961llu, 3452434812973llu, 4349795294267llu, + 5480398654009llu, 6904869625999llu, 8699590588571llu, 10960797308051llu, + 13809739252051llu, 17399181177241llu, 21921594616111llu, 27619478504183llu, + 34798362354533llu, 43843189232363llu, 55238957008387llu, 69596724709081llu, + 87686378464759llu, 110477914016779llu, 139193449418173llu, + 175372756929481llu, 220955828033581llu, 278386898836457llu, + 350745513859007llu, 441911656067171llu, 556773797672909llu, + 701491027718027llu, 883823312134381llu, 1113547595345903llu, + 1402982055436147llu, 1767646624268779llu, 2227095190691797llu, + 2805964110872297llu, 3535293248537579llu, 4454190381383713llu, + 5611928221744609llu, 7070586497075177llu, 8908380762767489llu, + 11223856443489329llu, 14141172994150357llu, 17816761525534927llu, + 22447712886978529llu, 28282345988300791llu, 35633523051069991llu, + 44895425773957261llu, 56564691976601587llu, 71267046102139967llu, + 89790851547914507llu, 113129383953203213llu, 142534092204280003llu, + 179581703095829107llu, 226258767906406483llu, 285068184408560057llu, + 359163406191658253llu, 452517535812813007llu, 570136368817120201llu, + 718326812383316683llu, 905035071625626043llu, 1140272737634240411llu, + 1436653624766633509llu, 1810070143251252131llu, 2280545475268481167llu, + 2873307249533267101llu, 3620140286502504283llu, 4561090950536962147llu, + 5746614499066534157llu, 7240280573005008577llu, 9122181901073924329llu, + 11493228998133068689llu, 14480561146010017169llu, 18446744073709551557llu + }; + static constexpr size_t (* const mod_functions[])(size_t) = + { + &mod0, &mod2, &mod3, &mod5, &mod7, &mod11, &mod13, &mod17, &mod23, &mod29, &mod37, + &mod47, &mod59, &mod73, &mod97, &mod127, &mod151, &mod197, &mod251, &mod313, &mod397, + &mod499, &mod631, &mod797, &mod1009, &mod1259, &mod1597, &mod2011, &mod2539, &mod3203, + &mod4027, &mod5087, &mod6421, &mod8089, &mod10193, &mod12853, &mod16193, &mod20399, + &mod25717, &mod32401, &mod40823, &mod51437, &mod64811, &mod81649, &mod102877, + &mod129607, &mod163307, &mod205759, &mod259229, &mod326617, &mod411527, &mod518509, + &mod653267, &mod823117, &mod1037059, &mod1306601, &mod1646237, &mod2074129, + &mod2613229, &mod3292489, &mod4148279, &mod5226491, &mod6584983, &mod8296553, + &mod10453007, &mod13169977, &mod16593127, &mod20906033, &mod26339969, &mod33186281, + &mod41812097, &mod52679969, &mod66372617, &mod83624237, &mod105359939, &mod132745199, + &mod167248483, &mod210719881, &mod265490441, &mod334496971, &mod421439783, + &mod530980861, &mod668993977, &mod842879579, &mod1061961721, &mod1337987929, + &mod1685759167, &mod2123923447, &mod2675975881, &mod3371518343, &mod4247846927, + &mod5351951779, &mod6743036717, &mod8495693897, &mod10703903591, &mod13486073473, + &mod16991387857, &mod21407807219, &mod26972146961, &mod33982775741, &mod42815614441, + &mod53944293929, &mod67965551447, &mod85631228929, &mod107888587883, &mod135931102921, + &mod171262457903, &mod215777175787, &mod271862205833, &mod342524915839, + &mod431554351609, &mod543724411781, &mod685049831731, &mod863108703229, + &mod1087448823553, &mod1370099663459, &mod1726217406467, &mod2174897647073, + &mod2740199326961, &mod3452434812973, &mod4349795294267, &mod5480398654009, + &mod6904869625999, &mod8699590588571, &mod10960797308051, &mod13809739252051, + &mod17399181177241, &mod21921594616111, &mod27619478504183, &mod34798362354533, + &mod43843189232363, &mod55238957008387, &mod69596724709081, &mod87686378464759, + &mod110477914016779, &mod139193449418173, &mod175372756929481, &mod220955828033581, + &mod278386898836457, &mod350745513859007, &mod441911656067171, &mod556773797672909, + &mod701491027718027, &mod883823312134381, &mod1113547595345903, &mod1402982055436147, + &mod1767646624268779, &mod2227095190691797, &mod2805964110872297, &mod3535293248537579, + &mod4454190381383713, &mod5611928221744609, &mod7070586497075177, &mod8908380762767489, + &mod11223856443489329, &mod14141172994150357, &mod17816761525534927, + &mod22447712886978529, &mod28282345988300791, &mod35633523051069991, + &mod44895425773957261, &mod56564691976601587, &mod71267046102139967, + &mod89790851547914507, &mod113129383953203213, &mod142534092204280003, + &mod179581703095829107, &mod226258767906406483, &mod285068184408560057, + &mod359163406191658253, &mod452517535812813007, &mod570136368817120201, + &mod718326812383316683, &mod905035071625626043, &mod1140272737634240411, + &mod1436653624766633509, &mod1810070143251252131, &mod2280545475268481167, + &mod2873307249533267101, &mod3620140286502504283, &mod4561090950536962147, + &mod5746614499066534157, &mod7240280573005008577, &mod9122181901073924329, + &mod11493228998133068689, &mod14480561146010017169, &mod18446744073709551557 + }; + const size_t * found = std::lower_bound(std::begin(prime_list), std::end(prime_list) - 1, size); + size = *found; + return mod_functions[1 + found - prime_list]; + } + void commit(mod_function new_mod_function) + { + current_mod_function = new_mod_function; + } + void reset() + { + current_mod_function = &mod0; + } + + size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const + { + return current_mod_function(hash); + } + size_t keep_in_range(size_t index, size_t num_slots_minus_one) const + { + return index > num_slots_minus_one ? current_mod_function(index) : index; + } + +private: + mod_function current_mod_function = &mod0; +}; + +struct power_of_two_hash_policy +{ + size_t index_for_hash(size_t hash, size_t num_slots_minus_one) const + { + return hash & num_slots_minus_one; + } + size_t keep_in_range(size_t index, size_t num_slots_minus_one) const + { + return index_for_hash(index, num_slots_minus_one); + } + int8_t next_size_over(size_t & size) const + { + size = detailv3::next_power_of_two(size); + return 0; + } + void commit(int8_t) + { + } + void reset() + { + } + +}; + +struct fibonacci_hash_policy +{ + size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const + { + return (11400714819323198485ull * hash) >> shift; + } + size_t keep_in_range(size_t index, size_t num_slots_minus_one) const + { + return index & num_slots_minus_one; + } + + int8_t next_size_over(size_t & size) const + { + size = std::max(size_t(2), detailv3::next_power_of_two(size)); + return 64 - detailv3::log2(size); + } + void commit(int8_t shift) + { + this->shift = shift; + } + void reset() + { + shift = 63; + } + +private: + int8_t shift = 63; +}; + +template, typename E = std::equal_to, typename A = std::allocator > > +class flat_hash_map + : public detailv3::sherwood_v3_table + < + std::pair, + K, + H, + detailv3::KeyOrValueHasher, H>, + E, + detailv3::KeyOrValueEquality, E>, + A, + typename std::allocator_traits::template rebind_alloc>> + > +{ + using Table = detailv3::sherwood_v3_table + < + std::pair, + K, + H, + detailv3::KeyOrValueHasher, H>, + E, + detailv3::KeyOrValueEquality, E>, + A, + typename std::allocator_traits::template rebind_alloc>> + >; +public: + + using key_type = K; + using mapped_type = V; + + using Table::Table; + flat_hash_map() + { + } + + inline V & operator[](const K & key) + { + return emplace(key, convertible_to_value()).first->second; + } + inline V & operator[](K && key) + { + return emplace(std::move(key), convertible_to_value()).first->second; + } + V & at(const K & key) + { + auto found = this->find(key); + if (found == this->end()) + throw std::out_of_range("Argument passed to at() was not in the map."); + return found->second; + } + const V & at(const K & key) const + { + auto found = this->find(key); + if (found == this->end()) + throw std::out_of_range("Argument passed to at() was not in the map."); + return found->second; + } + + using Table::emplace; + std::pair emplace() + { + return emplace(key_type(), convertible_to_value()); + } + template + std::pair insert_or_assign(const key_type & key, M && m) + { + auto emplace_result = emplace(key, std::forward(m)); + if (!emplace_result.second) + emplace_result.first->second = std::forward(m); + return emplace_result; + } + template + std::pair insert_or_assign(key_type && key, M && m) + { + auto emplace_result = emplace(std::move(key), std::forward(m)); + if (!emplace_result.second) + emplace_result.first->second = std::forward(m); + return emplace_result; + } + template + typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m) + { + return insert_or_assign(key, std::forward(m)).first; + } + template + typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m) + { + return insert_or_assign(std::move(key), std::forward(m)).first; + } + + friend bool operator==(const flat_hash_map & lhs, const flat_hash_map & rhs) + { + if (lhs.size() != rhs.size()) + return false; + for (const typename Table::value_type & value : lhs) + { + auto found = rhs.find(value.first); + if (found == rhs.end()) + return false; + else if (value.second != found->second) + return false; + } + return true; + } + friend bool operator!=(const flat_hash_map & lhs, const flat_hash_map & rhs) + { + return !(lhs == rhs); + } + +private: + struct convertible_to_value + { + operator V() const + { + return V(); + } + }; +}; + +template, typename E = std::equal_to, typename A = std::allocator > +class flat_hash_set + : public detailv3::sherwood_v3_table + < + T, + T, + H, + detailv3::functor_storage, + E, + detailv3::functor_storage, + A, + typename std::allocator_traits::template rebind_alloc> + > +{ + using Table = detailv3::sherwood_v3_table + < + T, + T, + H, + detailv3::functor_storage, + E, + detailv3::functor_storage, + A, + typename std::allocator_traits::template rebind_alloc> + >; +public: + + using key_type = T; + + using Table::Table; + flat_hash_set() + { + } + + template + std::pair emplace(Args &&... args) + { + return Table::emplace(T(std::forward(args)...)); + } + std::pair emplace(const key_type & arg) + { + return Table::emplace(arg); + } + std::pair emplace(key_type & arg) + { + return Table::emplace(arg); + } + std::pair emplace(const key_type && arg) + { + return Table::emplace(std::move(arg)); + } + std::pair emplace(key_type && arg) + { + return Table::emplace(std::move(arg)); + } + + friend bool operator==(const flat_hash_set & lhs, const flat_hash_set & rhs) + { + if (lhs.size() != rhs.size()) + return false; + for (const T & value : lhs) + { + if (rhs.find(value) == rhs.end()) + return false; + } + return true; + } + friend bool operator!=(const flat_hash_set & lhs, const flat_hash_set & rhs) + { + return !(lhs == rhs); + } +}; + + +template +struct power_of_two_std_hash : std::hash +{ + typedef ska::power_of_two_hash_policy hash_policy; +}; + +} // end namespace ska \ No newline at end of file diff --git a/examples/others/khash.h b/examples/others/khash.h new file mode 100644 index 00000000..61dabc4d --- /dev/null +++ b/examples/others/khash.h @@ -0,0 +1,595 @@ +/* The MIT License + Copyright (c) 2008, 2009, 2011 by Attractive Chaos + 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); + 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; +} +*/ + +/* + 2013-05-02 (0.2.8): + * Use quadratic probing. When the capacity is power of 2, stepping function + i*(i+1)/2 guarantees to traverse each bucket. It is better than double + hashing on cache performance and is more robust than linear probing. + In theory, double hashing should be more robust than quadratic probing. + However, my implementation is probably not for large hash tables, because + the second hash function is closely tied to the first hash function, + which reduce the effectiveness of double hashing. + Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php + 2011-12-29 (0.2.7): + * Minor code clean up; no actual effect. + 2011-09-16 (0.2.6): + * The capacity is a power of 2. This seems to dramatically improve the + speed for simple keys. Thank Zilong Tan for the suggestion. Reference: + - http://code.google.com/p/ulib/ + - http://nothings.org/computer/judy/ + * Allow to optionally use linear probing which usually has better + performance for random input. Double hashing is still the default as it + is more robust to certain non-random input. + * Added Wang's integer hash function (not used by default). This hash + function is more robust to certain non-random input. + 2011-02-14 (0.2.5): + * Allow to declare global functions. + 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. + */ + +#define AC_VERSION_KHASH_H "0.2.8" + +#include +#include +#include + +/* compiler 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 + +#ifndef kh_inline +#ifdef _MSC_VER +#define kh_inline __inline +#else +#define kh_inline inline +#endif +#endif /* kh_inline */ + +#ifndef klib_unused +#if (defined __clang__ && __clang_major__ >= 3) || (defined __GNUC__ && __GNUC__ >= 3) +#define klib_unused __attribute__ ((__unused__)) +#else +#define klib_unused +#endif +#endif /* klib_unused */ + +typedef khint32_t khint_t; +typedef khint_t khiter_t; + +#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)) + +#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) + +#ifndef kroundup32 +#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) +#endif + +#ifndef kcalloc +#define kcalloc(N,Z) calloc(N,Z) +#endif +#ifndef kmalloc +#define kmalloc(Z) malloc(Z) +#endif +#ifndef krealloc +#define krealloc(P,Z) realloc(P,Z) +#endif +#ifndef kfree +#define kfree(P) free(P) +#endif + +static const double __ac_HASH_UPPER = 0.77; + +#define __KHASH_TYPE(name, khkey_t, khval_t) \ + typedef struct kh_##name##_s { \ + khint_t n_buckets, size, n_occupied, upper_bound; \ + khint32_t *flags; \ + khkey_t *keys; \ + khval_t *vals; \ + } kh_##name##_t; + +#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ + extern kh_##name##_t *kh_init_##name(void); \ + extern void kh_destroy_##name(kh_##name##_t *h); \ + extern void kh_clear_##name(kh_##name##_t *h); \ + extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ + extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ + extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ + extern void kh_del_##name(kh_##name##_t *h, khint_t x); + +#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + SCOPE kh_##name##_t *kh_init_##name(void) { \ + return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ + } \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + { \ + if (h) { \ + kfree((void *)h->keys); kfree(h->flags); \ + kfree((void *)h->vals); \ + kfree(h); \ + } \ + } \ + SCOPE void kh_clear_##name(kh_##name##_t *h) \ + { \ + if (h && h->flags) { \ + memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) { \ + khint_t k, i, last, mask, step = 0; \ + mask = h->n_buckets - 1; \ + k = __hash_func(key); i = k & mask; \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) return h->n_buckets; \ + } \ + return __ac_iseither(h->flags, i)? h->n_buckets : i; \ + } else return 0; \ + } \ + SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + kroundup32(new_n_buckets); \ + if (new_n_buckets < 4) new_n_buckets = 4; \ + if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ + else { /* hash table size to be changed (shrink or expand); rehash */ \ + new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (h->n_buckets < new_n_buckets) { /* expand */ \ + khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (!new_keys) { kfree(new_flags); return -1; } \ + h->keys = new_keys; \ + if (kh_is_map) { \ + khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + if (!new_vals) { kfree(new_flags); return -1; } \ + h->vals = new_vals; \ + } \ + } /* otherwise shrink */ \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != h->n_buckets; ++j) { \ + if (__ac_iseither(h->flags, j) == 0) { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + khint_t new_mask; \ + new_mask = new_n_buckets - 1; \ + if (kh_is_map) val = h->vals[j]; \ + __ac_set_isdel_true(h->flags, j); \ + while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ + khint_t k, i, step = 0; \ + k = __hash_func(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ + { 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); /* mark it as deleted in the old hash table */ \ + } else { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + if (kh_is_map) h->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + } \ + kfree(h->flags); /* free the working space */ \ + 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); \ + } \ + return 0; \ + } \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ + if (h->n_buckets > (h->size<<1)) { \ + if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ + *ret = -1; return h->n_buckets; \ + } \ + } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ + *ret = -1; return h->n_buckets; \ + } \ + } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ + { \ + khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ + x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ + if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ + else { \ + 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; \ + i = (i + (++step)) & mask; \ + 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)) { /* not present at all */ \ + 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)) { /* deleted */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; \ + *ret = 2; \ + } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ + return x; \ + } \ + SCOPE 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; \ + } \ + } + +#define KHASH_DECLARE(name, khkey_t, khval_t) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_PROTOTYPES(name, khkey_t, khval_t) + +#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + KHASH_INIT2(name, static kh_inline klib_unused, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +/* --- 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 kh_inline khint_t __ac_X31_hash_string(const char *s) +{ + khint_t h = (khint_t)*s; + if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*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) + +static kh_inline khint_t __ac_Wang_hash(khint_t key) +{ + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; +} +#define kh_int_hash_func2(key) __ac_Wang_hash((khint_t)key) + +/* --- END OF HASH FUNCTIONS --- */ + +/* Other convenient 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: -1 if the operation failed; + 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) if 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) + +/*! @function + @abstract Iterate over the entries in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which key will be assigned + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h,__i)) continue; \ + (kvar) = kh_key(h,__i); \ + (vvar) = kh_val(h,__i); \ + code; \ + } } + +/*! @function + @abstract Iterate over the values in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_value(h, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h,__i)) continue; \ + (vvar) = kh_val(h,__i); \ + code; \ + } } + +/* More convenient 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 set 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/examples/others/khashl.h b/examples/others/khashl.h new file mode 100644 index 00000000..3542ba98 --- /dev/null +++ b/examples/others/khashl.h @@ -0,0 +1,345 @@ +/* The MIT License + Copyright (c) 2019 by Attractive Chaos + 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 __AC_KHASHL_H +#define __AC_KHASHL_H + +#define AC_VERSION_KHASHL_H "0.1" + +#include +#include +#include + +/************************************ + * Compiler specific configurations * + ************************************/ + +#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 + +#ifndef kh_inline +#ifdef _MSC_VER +#define kh_inline __inline +#else +#define kh_inline inline +#endif +#endif /* kh_inline */ + +#ifndef klib_unused +#if (defined __clang__ && __clang_major__ >= 3) || (defined __GNUC__ && __GNUC__ >= 3) +#define klib_unused __attribute__ ((__unused__)) +#else +#define klib_unused +#endif +#endif /* klib_unused */ + +#define KH_LOCAL static kh_inline klib_unused + +typedef khint32_t khint_t; + +/****************** + * malloc aliases * + ******************/ + +#ifndef kcalloc +#define kcalloc(N,Z) calloc(N,Z) +#endif +#ifndef kmalloc +#define kmalloc(Z) malloc(Z) +#endif +#ifndef krealloc +#define krealloc(P,Z) realloc(P,Z) +#endif +#ifndef kfree +#define kfree(P) free(P) +#endif + +/**************************** + * Simple private functions * + ****************************/ + +#define __kh_used(flag, i) (flag[i>>5] >> (i&0x1fU) & 1U) +#define __kh_set_used(flag, i) (flag[i>>5] |= 1U<<(i&0x1fU)) +#define __kh_set_unused(flag, i) (flag[i>>5] &= ~(1U<<(i&0x1fU))) + +#define __kh_fsize(m) ((m) < 32? 1 : (m)>>5) + +static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 2654435769U >> (32 - bits); } + +/******************* + * Hash table base * + *******************/ + +#define __KHASHL_TYPE(HType, khkey_t) \ + typedef struct { \ + khint_t bits, count; \ + khint32_t *used; \ + khkey_t *keys; \ + } HType; + +#define __KHASHL_PROTOTYPES(HType, prefix, khkey_t) \ + extern HType *prefix##_init(void); \ + extern void prefix##_destroy(HType *h); \ + extern void prefix##_clear(HType *h); \ + extern khint_t prefix##_getp(const HType *h, const khkey_t *key); \ + extern int prefix##_resize(HType *h, khint_t new_n_buckets); \ + extern khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent); \ + extern void prefix##_del(HType *h, khint_t k); + +#define __KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \ + SCOPE HType *prefix##_init(void) { \ + return (HType*)kcalloc(1, sizeof(HType)); \ + } \ + SCOPE void prefix##_destroy(HType *h) { \ + if (!h) return; \ + kfree((void *)h->keys); kfree(h->used); \ + kfree(h); \ + } \ + SCOPE void prefix##_clear(HType *h) { \ + if (h && h->used) { \ + uint32_t n_buckets = 1U << h->bits; \ + memset(h->used, 0, __kh_fsize(n_buckets) * sizeof(khint32_t)); \ + h->count = 0; \ + } \ + } + +#define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE khint_t prefix##_getp(const HType *h, const khkey_t *key) { \ + khint_t i, last, n_buckets, mask; \ + if (h->keys == 0) return 0; \ + n_buckets = 1U << h->bits; \ + mask = n_buckets - 1U; \ + i = last = __kh_h2b(__hash_fn(*key), h->bits); \ + while (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \ + i = (i + 1U) & mask; \ + if (i == last) return n_buckets; \ + } \ + return !__kh_used(h->used, i)? n_buckets : i; \ + } \ + SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { return prefix##_getp(h, &key); } + +#define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE int prefix##_resize(HType *h, khint_t new_n_buckets) { \ + khint32_t *new_used = 0; \ + khint_t j = 0, x = new_n_buckets, n_buckets, new_bits, new_mask; \ + while ((x >>= 1) != 0) ++j; \ + if (new_n_buckets & (new_n_buckets - 1)) ++j; \ + new_bits = j > 2? j : 2; \ + new_n_buckets = 1U << new_bits; \ + if (h->count > (new_n_buckets>>1) + (new_n_buckets>>2)) return 0; /* requested size is too small */ \ + new_used = (khint32_t*)kmalloc(__kh_fsize(new_n_buckets) * sizeof(khint32_t)); \ + memset(new_used, 0, __kh_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (!new_used) return -1; /* not enough memory */ \ + n_buckets = h->keys? 1U<bits : 0U; \ + if (n_buckets < new_n_buckets) { /* expand */ \ + khkey_t *new_keys = (khkey_t*)krealloc((void*)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (!new_keys) { kfree(new_used); return -1; } \ + h->keys = new_keys; \ + } /* otherwise shrink */ \ + new_mask = new_n_buckets - 1; \ + for (j = 0; j != n_buckets; ++j) { \ + khkey_t key; \ + if (!__kh_used(h->used, j)) continue; \ + key = h->keys[j]; \ + __kh_set_unused(h->used, j); \ + while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ + khint_t i; \ + i = __kh_h2b(__hash_fn(key), new_bits); \ + while (__kh_used(new_used, i)) i = (i + 1) & new_mask; \ + __kh_set_used(new_used, i); \ + if (i < n_buckets && __kh_used(h->used, i)) { /* kick out the existing element */ \ + { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ + __kh_set_unused(h->used, i); /* mark it as deleted in the old hash table */ \ + } else { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + break; \ + } \ + } \ + } \ + if (n_buckets > new_n_buckets) /* shrink the hash table */ \ + h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + kfree(h->used); /* free the working space */ \ + h->used = new_used, h->bits = new_bits; \ + return 0; \ + } + +#define __KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + SCOPE khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent) { \ + khint_t n_buckets, i, last, mask; \ + n_buckets = h->keys? 1U<bits : 0U; \ + *absent = -1; \ + if (h->count >= (n_buckets>>1) + (n_buckets>>2)) { /* rehashing */ \ + if (prefix##_resize(h, n_buckets + 1U) < 0) \ + return n_buckets; \ + n_buckets = 1U<bits; \ + } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ + mask = n_buckets - 1; \ + i = last = __kh_h2b(__hash_fn(*key), h->bits); \ + while (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \ + i = (i + 1U) & mask; \ + if (i == last) break; \ + } \ + if (!__kh_used(h->used, i)) { /* not present at all */ \ + h->keys[i] = *key; \ + __kh_set_used(h->used, i); \ + ++h->count; \ + *absent = 1; \ + } else *absent = 0; /* Don't touch h->keys[i] if present */ \ + return i; \ + } \ + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { return prefix##_putp(h, &key, absent); } + +#define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \ + SCOPE int prefix##_del(HType *h, khint_t i) { \ + khint_t j = i, k, mask, n_buckets; \ + if (h->keys == 0) return 0; \ + n_buckets = 1U<bits; \ + mask = n_buckets - 1U; \ + while (1) { \ + j = (j + 1U) & mask; \ + if (j == i || !__kh_used(h->used, j)) break; /* j==i only when the table is completely full */ \ + k = __kh_h2b(__hash_fn(h->keys[j]), h->bits); \ + if ((j > i && (k <= i || k > j)) || (j < i && (k <= i && k > j))) \ + h->keys[i] = h->keys[j], i = j; \ + } \ + __kh_set_unused(h->used, i); \ + --h->count; \ + return 1; \ + } + +#define KHASHL_DECLARE(HType, prefix, khkey_t) \ + __KHASHL_TYPE(HType, khkey_t) \ + __KHASHL_PROTOTYPES(HType, prefix, khkey_t) + +#define KHASHL_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + __KHASHL_TYPE(HType, khkey_t) \ + __KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \ + __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + __KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) + +/***************************** + * More convenient interface * + *****************************/ + +#define __kh_packed __attribute__ ((__packed__)) +#define __kh_cached_hash(x) ((x).hash) + +#define KHASHL_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + typedef struct { khkey_t key; } __kh_packed HType##_s_bucket_t; \ + static kh_inline khint_t prefix##_s_hash(HType##_s_bucket_t x) { return __hash_fn(x.key); } \ + static kh_inline int prefix##_s_eq(HType##_s_bucket_t x, HType##_s_bucket_t y) { return __hash_eq(x.key, y.key); } \ + KHASHL_INIT(KH_LOCAL, HType, prefix##_s, HType##_s_bucket_t, prefix##_s_hash, prefix##_s_eq) \ + SCOPE HType *prefix##_init(void) { return prefix##_s_init(); } \ + SCOPE void prefix##_destroy(HType *h) { prefix##_s_destroy(h); } \ + SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \ + SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_s_del(h, k); } \ + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_s_bucket_t t; t.key = key; return prefix##_s_putp(h, &t, absent); } + +#define KHASHL_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ + typedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \ + static kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \ + static kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \ + KHASHL_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \ + SCOPE HType *prefix##_init(void) { return prefix##_m_init(); } \ + SCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \ + SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \ + SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_m_del(h, k); } \ + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); } + +#define KHASHL_CSET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + typedef struct { khkey_t key; khint_t hash; } __kh_packed HType##_cs_bucket_t; \ + static kh_inline int prefix##_cs_eq(HType##_cs_bucket_t x, HType##_cs_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \ + KHASHL_INIT(KH_LOCAL, HType, prefix##_cs, HType##_cs_bucket_t, __kh_cached_hash, prefix##_cs_eq) \ + SCOPE HType *prefix##_init(void) { return prefix##_cs_init(); } \ + SCOPE void prefix##_destroy(HType *h) { prefix##_cs_destroy(h); } \ + SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cs_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cs_getp(h, &t); } \ + SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cs_del(h, k); } \ + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cs_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cs_putp(h, &t, absent); } + +#define KHASHL_CMAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ + typedef struct { khkey_t key; kh_val_t val; khint_t hash; } __kh_packed HType##_cm_bucket_t; \ + static kh_inline int prefix##_cm_eq(HType##_cm_bucket_t x, HType##_cm_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \ + KHASHL_INIT(KH_LOCAL, HType, prefix##_cm, HType##_cm_bucket_t, __kh_cached_hash, prefix##_cm_eq) \ + SCOPE HType *prefix##_init(void) { return prefix##_cm_init(); } \ + SCOPE void prefix##_destroy(HType *h) { prefix##_cm_destroy(h); } \ + SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cm_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cm_getp(h, &t); } \ + SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cm_del(h, k); } \ + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cm_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cm_putp(h, &t, absent); } + +/************************** + * Public macro functions * + **************************/ + +#define kh_bucket(h, x) ((h)->keys[x]) +#define kh_size(h) ((h)->count) +#define kh_capacity(h) ((h)->keys? 1U<<(h)->bits : 0U) +#define kh_end(h) kh_capacity(h) + +#define kh_key(h, x) ((h)->keys[x].key) +#define kh_val(h, x) ((h)->keys[x].val) + +/************************************** + * Common hash and equality functions * + **************************************/ + +#define kh_eq_generic(a, b) ((a) == (b)) +#define kh_eq_str(a, b) (strcmp((a), (b)) == 0) +#define kh_hash_dummy(x) ((khint_t)(x)) + +static kh_inline khint_t kh_hash_uint32(khint_t key) { + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; +} + +static kh_inline khint_t kh_hash_uint64(khint64_t key) { + key = ~key + (key << 21); + key = key ^ key >> 24; + key = (key + (key << 3)) + (key << 8); + key = key ^ key >> 14; + key = (key + (key << 2)) + (key << 4); + key = key ^ key >> 28; + key = key + (key << 31); + return (khint_t)key; +} + +static kh_inline khint_t kh_hash_str(const char *s) { + khint_t h = (khint_t)*s; + if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; + return h; +} + +#endif /* __AC_KHASHL_H */ diff --git a/examples/others/robin_hood.hpp b/examples/others/robin_hood.hpp new file mode 100644 index 00000000..48b21f21 --- /dev/null +++ b/examples/others/robin_hood.hpp @@ -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 . +// SPDX-License-Identifier: MIT +// Copyright (c) 2018-2020 Martin Ankerl +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to deal +// in the Software without restriction, including without limitation the rights +// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in all +// copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +// SOFTWARE. + +#ifndef ROBIN_HOOD_H_INCLUDED +#define ROBIN_HOOD_H_INCLUDED + +// see https://semver.org/ +#define ROBIN_HOOD_VERSION_MAJOR 3 // for incompatible API changes +#define ROBIN_HOOD_VERSION_MINOR 6 // for adding functionality in a backwards-compatible manner +#define ROBIN_HOOD_VERSION_PATCH 0 // for backwards-compatible bug fixes + +#include +#include +#include +#include +#include +#include +#include +#include + +// #define ROBIN_HOOD_LOG_ENABLED +#ifdef ROBIN_HOOD_LOG_ENABLED +# include +# 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 +# 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 +# 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 +# pragma intrinsic(ROBIN_HOOD(BITSCANFORWARD)) +# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) \ + [](size_t mask) noexcept -> int { \ + unsigned long index; \ + return ROBIN_HOOD(BITSCANFORWARD)(&index, mask) ? static_cast(index) \ + : ROBIN_HOOD(BITNESS); \ + }(x) +#else +# if ROBIN_HOOD(BITNESS) == 32 +# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzl +# define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzl +# else +# define ROBIN_HOOD_PRIVATE_DEFINITION_CTZ() __builtin_ctzll +# define ROBIN_HOOD_PRIVATE_DEFINITION_CLZ() __builtin_clzll +# endif +# define ROBIN_HOOD_COUNT_LEADING_ZEROES(x) ((x) ? ROBIN_HOOD(CLZ)(x) : ROBIN_HOOD(BITNESS)) +# define ROBIN_HOOD_COUNT_TRAILING_ZEROES(x) ((x) ? ROBIN_HOOD(CTZ)(x) : ROBIN_HOOD(BITNESS)) +#endif + +// 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 +struct alignment_of + : std::integral_constant::type)> {}; + +template +class integer_sequence { +public: + using value_type = T; + static_assert(std::is_integral::value, "not integral type"); + static constexpr std::size_t size() noexcept { + return sizeof...(Ints); + } +}; +template +using index_sequence = integer_sequence; + +namespace detail_ { +template +struct IntSeqImpl { + using TValue = T; + static_assert(std::is_integral::value, "not integral type"); + static_assert(Begin >= 0 && Begin < End, "unexpected argument (Begin<0 || Begin<=End)"); + + template + struct IntSeqCombiner; + + template + struct IntSeqCombiner, integer_sequence> { + using TResult = integer_sequence; + }; + + using TResult = + typename IntSeqCombiner::TResult, + typename IntSeqImpl::TResult>::TResult; +}; + +template +struct IntSeqImpl { + using TValue = T; + static_assert(std::is_integral::value, "not integral type"); + static_assert(Begin >= 0, "unexpected argument (Begin<0)"); + using TResult = integer_sequence; +}; + +template +struct IntSeqImpl { + using TValue = T; + static_assert(std::is_integral::value, "not integral type"); + static_assert(Begin >= 0, "unexpected argument (Begin<0)"); + using TResult = integer_sequence; +}; +} // namespace detail_ + +template +using make_integer_sequence = typename detail_::IntSeqImpl::TResult; + +template +using make_index_sequence = make_integer_sequence; + +template +using index_sequence_for = make_index_sequence; + +} // namespace ROBIN_HOOD_STD + +#endif + +namespace detail { + +// 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 +} +#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 +inline T reinterpret_cast_no_cast_align_warning(void* ptr) noexcept { + return reinterpret_cast(ptr); +} + +template +inline T reinterpret_cast_no_cast_align_warning(void const* ptr) noexcept { + return reinterpret_cast(ptr); +} + +// make sure this is not inlined as it is slow and dramatically enlarges code, thus making other +// inlinings more difficult. Throws are also generally the slow path. +template +ROBIN_HOOD(NOINLINE) +#if ROBIN_HOOD(HAS_EXCEPTIONS) +void doThrow(Args&&... args) { + // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-array-to-pointer-decay) + throw E(std::forward(args)...); +} +#else +void doThrow(Args&&... ROBIN_HOOD_UNUSED(args) /*unused*/) { + abort(); +} +#endif + +template +T* assertNotNull(T* t, Args&&... args) { + if (ROBIN_HOOD_UNLIKELY(nullptr == t)) { + doThrow(std::forward(args)...); + } + return t; +} + +template +inline T unaligned_load(void const* ptr) noexcept { + // using memcpy so we don't get into unaligned load problems. + // compiler should optimize this very well anyways. + T t; + std::memcpy(&t, ptr, sizeof(T)); + return t; +} + +// Allocates bulks of memory for objects of type T. This deallocates the memory in the destructor, +// and keeps a linked list of the allocated memory around. Overhead per allocation is the size of a +// pointer. +template +class BulkPoolAllocator { +public: + BulkPoolAllocator() noexcept = default; + + // does not copy anything, just creates a new allocator. + BulkPoolAllocator(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept + : mHead(nullptr) + , mListForFree(nullptr) {} + + BulkPoolAllocator(BulkPoolAllocator&& o) noexcept + : mHead(o.mHead) + , mListForFree(o.mListForFree) { + o.mListForFree = nullptr; + o.mHead = nullptr; + } + + BulkPoolAllocator& operator=(BulkPoolAllocator&& o) noexcept { + reset(); + mHead = o.mHead; + mListForFree = o.mListForFree; + o.mListForFree = nullptr; + o.mHead = nullptr; + return *this; + } + + BulkPoolAllocator& + // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) + operator=(const BulkPoolAllocator& ROBIN_HOOD_UNUSED(o) /*unused*/) noexcept { + // does not do anything + return *this; + } + + ~BulkPoolAllocator() noexcept { + reset(); + } + + // Deallocates all allocated memory. + void reset() noexcept { + while (mListForFree) { + T* tmp = *mListForFree; + free(mListForFree); + mListForFree = reinterpret_cast_no_cast_align_warning(tmp); + } + mHead = nullptr; + } + + // allocates, but does NOT initialize. Use in-place new constructor, e.g. + // T* obj = pool.allocate(); + // ::new (static_cast(obj)) T(); + T* allocate() { + T* tmp = mHead; + if (!tmp) { + tmp = performAllocation(); + } + + mHead = *reinterpret_cast_no_cast_align_warning(tmp); + return tmp; + } + + // does not actually deallocate but puts it in store. + // make sure you have already called the destructor! e.g. with + // obj->~T(); + // pool.deallocate(obj); + void deallocate(T* obj) noexcept { + *reinterpret_cast_no_cast_align_warning(obj) = mHead; + mHead = obj; + } + + // Adds an already allocated block of memory to the allocator. This allocator is from now on + // responsible for freeing the data (with free()). If the provided data is not large enough to + // make use of, it is immediately freed. Otherwise it is reused and freed in the destructor. + void addOrFree(void* ptr, const size_t numBytes) noexcept { + // calculate number of available elements in ptr + if (numBytes < ALIGNMENT + ALIGNED_SIZE) { + // not enough data for at least one element. Free and return. + free(ptr); + } else { + add(ptr, numBytes); + } + } + + void swap(BulkPoolAllocator& other) noexcept { + using std::swap; + swap(mHead, other.mHead); + swap(mListForFree, other.mListForFree); + } + +private: + // iterates the list of allocated memory to calculate how many to alloc next. + // Recalculating this each time saves us a size_t member. + // This ignores the fact that memory blocks might have been added manually with addOrFree. In + // practice, this should not matter much. + ROBIN_HOOD(NODISCARD) size_t calcNumElementsToAlloc() const noexcept { + auto tmp = mListForFree; + size_t numAllocs = MinNumAllocs; + + while (numAllocs * 2 <= MaxNumAllocs && tmp) { + auto x = reinterpret_cast(tmp); + tmp = *x; + numAllocs *= 2; + } + + return numAllocs; + } + + // WARNING: Underflow if numBytes < ALIGNMENT! This is guarded in addOrFree(). + void add(void* ptr, const size_t numBytes) noexcept { + const size_t numElements = (numBytes - ALIGNMENT) / ALIGNED_SIZE; + + auto data = reinterpret_cast(ptr); + + // link free list + auto x = reinterpret_cast(data); + *x = mListForFree; + mListForFree = data; + + // create linked list for newly allocated data + auto const headT = + reinterpret_cast_no_cast_align_warning(reinterpret_cast(ptr) + ALIGNMENT); + + auto const head = reinterpret_cast(headT); + + // Visual Studio compiler automatically unrolls this loop, which is pretty cool + for (size_t i = 0; i < numElements; ++i) { + *reinterpret_cast_no_cast_align_warning(head + i * ALIGNED_SIZE) = + head + (i + 1) * ALIGNED_SIZE; + } + + // last one points to 0 + *reinterpret_cast_no_cast_align_warning(head + (numElements - 1) * ALIGNED_SIZE) = + mHead; + mHead = headT; + } + + // Called when no memory is available (mHead == 0). + // Don't inline this slow path. + ROBIN_HOOD(NOINLINE) T* performAllocation() { + size_t const numElementsToAlloc = calcNumElementsToAlloc(); + + // alloc new memory: [prev |T, T, ... T] + // std::cout << (sizeof(T*) + ALIGNED_SIZE * numElementsToAlloc) << " bytes" << std::endl; + size_t const bytes = ALIGNMENT + ALIGNED_SIZE * numElementsToAlloc; + add(assertNotNull(malloc(bytes)), bytes); + return mHead; + } + + // enforce byte alignment of the T's +#if ROBIN_HOOD(CXX) >= ROBIN_HOOD(CXX14) + static constexpr size_t ALIGNMENT = + (std::max)(std::alignment_of::value, std::alignment_of::value); +#else + static const size_t ALIGNMENT = + (ROBIN_HOOD_STD::alignment_of::value > ROBIN_HOOD_STD::alignment_of::value) + ? ROBIN_HOOD_STD::alignment_of::value + : +ROBIN_HOOD_STD::alignment_of::value; // the + is for walkarround +#endif + + static constexpr size_t ALIGNED_SIZE = ((sizeof(T) - 1) / ALIGNMENT + 1) * ALIGNMENT; + + static_assert(MinNumAllocs >= 1, "MinNumAllocs"); + static_assert(MaxNumAllocs >= MinNumAllocs, "MaxNumAllocs"); + static_assert(ALIGNED_SIZE >= sizeof(T*), "ALIGNED_SIZE"); + static_assert(0 == (ALIGNED_SIZE % sizeof(T*)), "ALIGNED_SIZE mod"); + static_assert(ALIGNMENT >= sizeof(T*), "ALIGNMENT"); + + T* mHead{nullptr}; + T** mListForFree{nullptr}; +}; + +template +struct NodeAllocator; + +// dummy allocator that does nothing +template +struct NodeAllocator { + + // we are not using the data, so just free it. + void addOrFree(void* ptr, size_t ROBIN_HOOD_UNUSED(numBytes) /*unused*/) noexcept { + free(ptr); + } +}; + +template +struct NodeAllocator : public BulkPoolAllocator {}; + +// dummy hash, unsed as mixer when robin_hood::hash is already used +template +struct identity_hash { + constexpr size_t operator()(T const& obj) const noexcept { + return static_cast(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 +struct nothrow { + static const bool value = noexcept(swap(std::declval(), std::declval())); +}; + +} // namespace swappable + +} // namespace detail + +struct is_transparent_tag {}; + +// A custom pair implementation is used in the map because std::pair is not is_trivially_copyable, +// which means it would not be allowed to be used in std::memcpy. This struct is copyable, which is +// also tested. +template +struct pair { + using first_type = T1; + using second_type = T2; + + template ::value && + std::is_default_constructible::value>::type> + constexpr pair() noexcept(noexcept(U1()) && noexcept(U2())) + : first() + , second() {} + + // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. + explicit constexpr pair(std::pair const& o) noexcept( + noexcept(T1(std::declval())) && noexcept(T2(std::declval()))) + : first(o.first) + , second(o.second) {} + + // pair constructors are explicit so we don't accidentally call this ctor when we don't have to. + explicit constexpr pair(std::pair&& o) noexcept( + noexcept(T1(std::move(std::declval()))) && + noexcept(T2(std::move(std::declval())))) + : first(std::move(o.first)) + , second(std::move(o.second)) {} + + constexpr pair(T1&& a, T2&& b) noexcept(noexcept(T1(std::move(std::declval()))) && + noexcept(T2(std::move(std::declval())))) + : first(std::move(a)) + , second(std::move(b)) {} + + template + constexpr pair(U1&& a, U2&& b) noexcept(noexcept(T1(std::forward(std::declval()))) && + noexcept(T2(std::forward(std::declval())))) + : first(std::forward(a)) + , second(std::forward(b)) {} + + template + constexpr pair( + std::piecewise_construct_t /*unused*/, std::tuple a, + std::tuple b) noexcept(noexcept(pair(std::declval&>(), + std::declval&>(), + ROBIN_HOOD_STD::index_sequence_for(), + ROBIN_HOOD_STD::index_sequence_for()))) + : pair(a, b, ROBIN_HOOD_STD::index_sequence_for(), + ROBIN_HOOD_STD::index_sequence_for()) {} + + // constructor called from the std::piecewise_construct_t ctor + template + pair(std::tuple& a, std::tuple& b, + ROBIN_HOOD_STD::index_sequence /*unused*/, + ROBIN_HOOD_STD::index_sequence< + I2...> /*unused*/) noexcept(noexcept(T1(std:: + forward(std::get( + std::declval< + std::tuple&>()))...)) && + noexcept(T2(std::forward( + std::get(std::declval&>()))...))) + : first(std::forward(std::get(a))...) + , second(std::forward(std::get(b))...) { + // make visual studio compiler happy about warning about unused a & b. + // Visual studio's pair implementation disables warning 4100. + (void)a; + (void)b; + } + + void swap(pair& o) noexcept((detail::swappable::nothrow::value) && + (detail::swappable::nothrow::value)) { + using std::swap; + swap(first, o.first); + swap(second, o.second); + } + + T1 first; // NOLINT(misc-non-private-member-variables-in-classes) + T2 second; // NOLINT(misc-non-private-member-variables-in-classes) +}; + +template +inline void swap(pair& a, pair& b) noexcept( + noexcept(std::declval&>().swap(std::declval&>()))) { + a.swap(b); +} + +template +inline constexpr bool operator==(pair const& x, pair const& y) { + return (x.first == y.first) && (x.second == y.second); +} +template +inline constexpr bool operator!=(pair const& x, pair const& y) { + return !(x == y); +} +template +inline constexpr bool operator<(pair const& x, pair const& y) { + return x.first < y.first || (!(y.first < x.first) && x.second < y.second); +} +template +inline constexpr bool operator>(pair const& x, pair const& y) { + return y < x; +} +template +inline constexpr bool operator<=(pair const& x, pair const& y) { + return !(x > y); +} +template +inline constexpr bool operator>=(pair const& x, pair const& y) { + return !(x < y); +} + +// 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(ptr); + uint64_t h = seed ^ (len * m); + + size_t const n_blocks = len / 8; + for (size_t i = 0; i < n_blocks; ++i) { + auto k = detail::unaligned_load(data64 + i); + + k *= m; + k ^= k >> r; + k *= m; + + h ^= k; + h *= m; + } + + auto const data8 = reinterpret_cast(data64 + n_blocks); + switch (len & 7U) { + case 7: + h ^= static_cast(data8[6]) << 48U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 6: + h ^= static_cast(data8[5]) << 40U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 5: + h ^= static_cast(data8[4]) << 32U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 4: + h ^= static_cast(data8[3]) << 24U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 3: + h ^= static_cast(data8[2]) << 16U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 2: + h ^= static_cast(data8[1]) << 8U; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + case 1: + h ^= static_cast(data8[0]); + h *= m; + ROBIN_HOOD(FALLTHROUGH); // FALLTHROUGH + default: + break; + } + + h ^= h >> r; + h *= m; + h ^= h >> r; + 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; + return static_cast(h); +#endif +} + +// A thin wrapper around std::hash, performing an additional simple mixing step of the result. +template +struct hash : public std::hash { + size_t operator()(T const& obj) const + noexcept(noexcept(std::declval>().operator()(std::declval()))) { + // call base hash + auto result = std::hash::operator()(obj); + // return mixed of that, to be save against identity has + return hash_int(static_cast(result)); + } +}; + +template <> +struct hash { + size_t operator()(std::string const& str) const noexcept { + return hash_bytes(str.data(), str.size()); + } +}; + +template +struct hash { + size_t operator()(T* ptr) const noexcept { + return hash_int(reinterpret_cast(ptr)); + } +}; + +#define ROBIN_HOOD_HASH_INT(T) \ + template <> \ + struct hash { \ + size_t operator()(T obj) const noexcept { \ + return hash_int(static_cast(obj)); \ + } \ + } + +#if defined(__GNUC__) && !defined(__clang__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wuseless-cast" +#endif +// see https://en.cppreference.com/w/cpp/utility/hash +ROBIN_HOOD_HASH_INT(bool); +ROBIN_HOOD_HASH_INT(char); +ROBIN_HOOD_HASH_INT(signed char); +ROBIN_HOOD_HASH_INT(unsigned char); +ROBIN_HOOD_HASH_INT(char16_t); +ROBIN_HOOD_HASH_INT(char32_t); +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 +struct WrapHash : public T { + WrapHash() = default; + explicit WrapHash(T const& o) noexcept(noexcept(T(std::declval()))) + : T(o) {} +}; + +template +struct WrapKeyEqual : public T { + WrapKeyEqual() = default; + explicit WrapKeyEqual(T const& o) noexcept(noexcept(T(std::declval()))) + : T(o) {} +}; + +// A highly optimized hashmap implementation, using the Robin Hood algorithm. +// +// In most cases, this map should be usable as a drop-in replacement for std::unordered_map, but be +// about 2x faster in most cases and require much less allocations. +// +// This implementation uses the following memory layout: +// +// [Node, Node, ... Node | info, info, ... infoSentinel ] +// +// * Node: either a DataNode that directly has the std::pair as member, +// or a DataNode with a pointer to std::pair. Which DataNode representation to use +// depends on how fast the swap() operation is. Heuristically, this is automatically choosen based +// on sizeof(). there are always 2^n Nodes. +// +// * info: Each Node in the map has a corresponding info byte, so there are 2^n info bytes. +// Each byte is initialized to 0, meaning the corresponding Node is empty. Set to 1 means the +// corresponding node contains data. Set to 2 means the corresponding Node is filled, but it +// actually belongs to the previous position and was pushed out because that place is already +// taken. +// +// * infoSentinel: Sentinel byte set to 1, so that iterator's ++ can stop at end() without the need +// for a idx +// variable. +// +// According to STL, order of templates has effect on throughput. That's why I've moved the boolean +// to the front. +// https://www.reddit.com/r/cpp/comments/ahp6iu/compile_time_binary_size_reductions_and_cs_future/eeguck4/ +template +class Table + : public WrapHash, + public WrapKeyEqual, + detail::NodeAllocator< + typename std::conditional< + std::is_void::value, Key, + robin_hood::pair::type, T>>::type, + 4, 16384, IsFlat> { +public: + static constexpr bool is_flat = IsFlat; + static constexpr bool is_map = !std::is_void::value; + static constexpr bool is_set = !is_map; + + using key_type = Key; + using mapped_type = T; + using value_type = typename std::conditional< + is_set, Key, + robin_hood::pair::type, T>>::type; + using size_type = size_t; + using hasher = Hash; + using key_equal = KeyEqual; + using Self = Table; + +private: + static_assert(MaxLoadFactor100 > 10 && MaxLoadFactor100 < 100, + "MaxLoadFactor100 needs to be >10 && < 100"); + + using WHash = WrapHash; + using WKeyEqual = WrapKeyEqual; + + // configuration defaults + + // make sure we have 8 elements, needed to quickly rehash mInfo + static constexpr size_t InitialNumElements = sizeof(uint64_t); + static constexpr uint32_t InitialInfoNumBits = 5; + static constexpr uint8_t InitialInfoInc = 1U << InitialInfoNumBits; + static constexpr uint8_t InitialInfoHashShift = sizeof(size_t) * 8 - InitialInfoNumBits; + using DataPool = detail::NodeAllocator; + + // type needs to be wider than uint8_t. + using InfoType = uint32_t; + + // DataNode //////////////////////////////////////////////////////// + + // Primary template for the data node. We have special implementations for small and big + // objects. For large objects it is assumed that swap() is fairly slow, so we allocate these on + // the heap so swap merely swaps a pointer. + template + class DataNode {}; + + // Small: just allocate on the stack. + template + class DataNode final { + public: + template + explicit DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, Args&&... args) noexcept( + noexcept(value_type(std::forward(args)...))) + : mData(std::forward(args)...) {} + + DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept( + std::is_nothrow_move_constructible::value) + : mData(std::move(n.mData)) {} + + // doesn't do anything + void destroy(M& ROBIN_HOOD_UNUSED(map) /*unused*/) noexcept {} + void destroyDoNotDeallocate() noexcept {} + + value_type const* operator->() const noexcept { + return &mData; + } + value_type* operator->() noexcept { + return &mData; + } + + const value_type& operator*() const noexcept { + return mData; + } + + value_type& operator*() noexcept { + return mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return mData.first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() const + noexcept { + return mData.first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() const noexcept { + return mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() noexcept { + return mData.second; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() const noexcept { + return mData.second; + } + + void swap(DataNode& o) noexcept( + noexcept(std::declval().swap(std::declval()))) { + mData.swap(o.mData); + } + + private: + value_type mData; + }; + + // big object: allocate on heap. + template + class DataNode { + public: + template + explicit DataNode(M& map, Args&&... args) + : mData(map.allocate()) { + ::new (static_cast(mData)) value_type(std::forward(args)...); + } + + DataNode(M& ROBIN_HOOD_UNUSED(map) /*unused*/, DataNode&& n) noexcept + : mData(std::move(n.mData)) {} + + void destroy(M& map) noexcept { + // don't deallocate, just put it into list of datapool. + mData->~value_type(); + map.deallocate(mData); + } + + void destroyDoNotDeallocate() noexcept { + mData->~value_type(); + } + + value_type const* operator->() const noexcept { + return mData; + } + + value_type* operator->() noexcept { + return mData; + } + + const value_type& operator*() const { + return *mData; + } + + value_type& operator*() { + return *mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return mData->first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() noexcept { + return *mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() const + noexcept { + return mData->first; + } + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getFirst() const noexcept { + return *mData; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() noexcept { + return mData->second; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::type getSecond() const noexcept { + return mData->second; + } + + void swap(DataNode& o) noexcept { + using std::swap; + swap(mData, o.mData); + } + + private: + value_type* mData; + }; + + using Node = DataNode; + + // helpers for 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 + ROBIN_HOOD(NODISCARD) + typename std::enable_if::value, key_type const&>::type + getFirstConst(value_type const& vt) const noexcept { + return vt.first; + } + + // Cloner ////////////////////////////////////////////////////////// + + template + struct Cloner; + + // fast path: Just copy data, without allocating anything. + template + struct Cloner { + void operator()(M const& source, M& target) const { + auto src = reinterpret_cast(source.mKeyVals); + auto tgt = reinterpret_cast(target.mKeyVals); + auto const numElementsWithBuffer = target.calcNumElementsWithBuffer(target.mMask + 1); + std::copy(src, src + target.calcNumBytesTotal(numElementsWithBuffer), tgt); + } + }; + + template + struct Cloner { + void operator()(M const& s, M& t) const { + auto const numElementsWithBuffer = t.calcNumElementsWithBuffer(t.mMask + 1); + std::copy(s.mInfo, s.mInfo + t.calcNumBytesInfo(numElementsWithBuffer), t.mInfo); + + for (size_t i = 0; i < numElementsWithBuffer; ++i) { + if (t.mInfo[i]) { + ::new (static_cast(t.mKeyVals + i)) Node(t, *s.mKeyVals[i]); + } + } + } + }; + + // Destroyer /////////////////////////////////////////////////////// + + template + struct Destroyer {}; + + template + struct Destroyer { + void nodes(M& m) const noexcept { + m.mNumElements = 0; + } + + void nodesDoNotDeallocate(M& m) const noexcept { + m.mNumElements = 0; + } + }; + + template + struct Destroyer { + void nodes(M& m) const noexcept { + m.mNumElements = 0; + // clear also resets mInfo to 0, that's sometimes not necessary. + auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); + + for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { + if (0 != m.mInfo[idx]) { + Node& n = m.mKeyVals[idx]; + n.destroy(m); + n.~Node(); + } + } + } + + void nodesDoNotDeallocate(M& m) const noexcept { + m.mNumElements = 0; + // clear also resets mInfo to 0, that's sometimes not necessary. + auto const numElementsWithBuffer = m.calcNumElementsWithBuffer(m.mMask + 1); + for (size_t idx = 0; idx < numElementsWithBuffer; ++idx) { + if (0 != m.mInfo[idx]) { + Node& n = m.mKeyVals[idx]; + n.destroyDoNotDeallocate(); + n.~Node(); + } + } + } + }; + + // Iter //////////////////////////////////////////////////////////// + + struct fast_forward_tag {}; + + // generic iterator for both const_iterator and iterator. + template + // NOLINTNEXTLINE(hicpp-special-member-functions,cppcoreguidelines-special-member-functions) + class Iter { + private: + using NodePtr = typename std::conditional::type; + + public: + using difference_type = std::ptrdiff_t; + using value_type = typename Self::value_type; + using reference = typename std::conditional::type; + using pointer = typename std::conditional::type; + using iterator_category = std::forward_iterator_tag; + + // default constructed iterator can be compared to itself, but WON'T return true when + // compared to end(). + Iter() = default; + + // Rule of zero: nothing specified. The conversion constructor is only enabled for iterator + // to const_iterator, so it doesn't accidentally work as a copy ctor. + + // Conversion constructor from iterator to const_iterator. + template ::type> + // NOLINTNEXTLINE(hicpp-explicit-conversions) + Iter(Iter const& other) noexcept + : mKeyVals(other.mKeyVals) + , mInfo(other.mInfo) {} + + Iter(NodePtr valPtr, uint8_t const* infoPtr) noexcept + : mKeyVals(valPtr) + , mInfo(infoPtr) {} + + Iter(NodePtr valPtr, uint8_t const* infoPtr, + fast_forward_tag ROBIN_HOOD_UNUSED(tag) /*unused*/) noexcept + : mKeyVals(valPtr) + , mInfo(infoPtr) { + fastForward(); + } + + template ::type> + Iter& operator=(Iter const& other) noexcept { + mKeyVals = other.mKeyVals; + mInfo = other.mInfo; + return *this; + } + + // prefix increment. Undefined behavior if we are at end()! + Iter& operator++() noexcept { + mInfo++; + mKeyVals++; + fastForward(); + return *this; + } + + reference operator*() const { + return **mKeyVals; + } + + pointer operator->() const { + return &**mKeyVals; + } + + template + bool operator==(Iter const& o) const noexcept { + return mKeyVals == o.mKeyVals; + } + + template + bool operator!=(Iter const& o) const noexcept { + return mKeyVals != o.mKeyVals; + } + + private: + // fast forward to the next non-free info byte + void fastForward() noexcept { + int inc; + do { + auto const n = detail::unaligned_load(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(sizeof(size_t))); + } + + friend class Table; + NodePtr mKeyVals{nullptr}; + uint8_t const* mInfo{nullptr}; + }; + + //////////////////////////////////////////////////////////////////// + + // highly performance relevant code. + // Lower bits are used for indexing into the array (2^n size) + // The upper 1-5 bits need to be a reasonable good hash, to save comparisons. + template + void keyToIdx(HashKey&& key, size_t* idx, InfoType* info) const { + // 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, + ::robin_hood::hash>::type; + *idx = Mix{}(WHash::operator()(key)); + + *info = mInfoInc + static_cast(*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::value) { + auto idx = startIdx; + ::new (static_cast(mKeyVals + idx)) Node(std::move(mKeyVals[idx - 1])); + while (--idx != insertion_idx) { + mKeyVals[idx] = std::move(mKeyVals[idx - 1]); + } + + idx = startIdx; + while (idx != insertion_idx) { + ROBIN_HOOD_COUNT(shiftUp); + mInfo[idx] = static_cast(mInfo[idx - 1] + mInfoInc); + if (ROBIN_HOOD_UNLIKELY(mInfo[idx] + mInfoInc > 0xFF)) { + mMaxNumElementsAllowed = 0; + } + --idx; + } + } + + void shiftDown(size_t idx) noexcept(std::is_nothrow_move_assignable::value) { + // until we find one that is either empty or has zero offset. + // TODO(martinus) we don't need to move everything, just the last one for the same bucket. + mKeyVals[idx].destroy(*this); + + // until we find one that is either empty or has zero offset. + while (mInfo[idx + 1] >= 2 * mInfoInc) { + ROBIN_HOOD_COUNT(shiftDown); + mInfo[idx] = static_cast(mInfo[idx + 1] - mInfoInc); + mKeyVals[idx] = std::move(mKeyVals[idx + 1]); + ++idx; + } + + mInfo[idx] = 0; + // don't destroy, we've moved it + // mKeyVals[idx].destroy(*this); + mKeyVals[idx].~Node(); + } + + // copy of find(), except that it returns iterator instead of const_iterator. + template + ROBIN_HOOD(NODISCARD) + size_t findIdx(Other const& key) const { + size_t idx; + InfoType info; + keyToIdx(key, &idx, &info); + + do { + // unrolling this twice gives a bit of a speedup. More unrolling did not help. + if (info == mInfo[idx] && + ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { + return idx; + } + next(&info, &idx); + if (info == mInfo[idx] && + ROBIN_HOOD_LIKELY(WKeyEqual::operator()(key, mKeyVals[idx].getFirst()))) { + return idx; + } + next(&info, &idx); + } while (info <= mInfo[idx]); + + // nothing found! + return mMask == 0 ? 0 + : static_cast(std::distance( + mKeyVals, reinterpret_cast_no_cast_align_warning(mInfo))); + } + + void cloneData(const Table& o) { + Cloner()(o, *this); + } + + // inserts a keyval that is guaranteed to be new, e.g. when the hashmap is resized. + // @return 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(info); + if (ROBIN_HOOD_UNLIKELY(insertion_info + mInfoInc > 0xFF)) { + mMaxNumElementsAllowed = 0; + } + + // find an empty spot + while (0 != mInfo[idx]) { + next(&info, &idx); + } + + auto& l = mKeyVals[insertion_idx]; + if (idx == insertion_idx) { + ::new (static_cast(&l)) Node(std::move(keyval)); + } else { + shiftUp(idx, insertion_idx); + l = std::move(keyval); + } + + // put at empty spot + mInfo[insertion_idx] = insertion_info; + + ++mNumElements; + return insertion_idx; + } + +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))) + : WHash(h) + , WKeyEqual(equal) { + ROBIN_HOOD_TRACE(this); + } + + template + Table(Iter first, Iter last, size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, + const Hash& h = Hash{}, const KeyEqual& equal = KeyEqual{}) + : WHash(h) + , WKeyEqual(equal) { + ROBIN_HOOD_TRACE(this); + insert(first, last); + } + + Table(std::initializer_list initlist, + size_t ROBIN_HOOD_UNUSED(bucket_count) /*unused*/ = 0, const Hash& h = Hash{}, + const KeyEqual& equal = KeyEqual{}) + : WHash(h) + , WKeyEqual(equal) { + ROBIN_HOOD_TRACE(this); + insert(initlist.begin(), initlist.end()); + } + + Table(Table&& o) noexcept + : WHash(std::move(static_cast(o))) + , WKeyEqual(std::move(static_cast(o))) + , DataPool(std::move(static_cast(o))) { + ROBIN_HOOD_TRACE(this); + if (o.mMask) { + 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(o))); + WKeyEqual::operator=(std::move(static_cast(o))); + DataPool::operator=(std::move(static_cast(o))); + + o.init(); + + } else { + // nothing in the other map => just clear us. + clear(); + } + } + return *this; + } + + Table(const Table& o) + : WHash(static_cast(o)) + , WKeyEqual(static_cast(o)) + , DataPool(static_cast(o)) { + ROBIN_HOOD_TRACE(this); + if (!o.empty()) { + // not empty: create an exact copy. it is also possible to just iterate through all + // elements and insert them, but copying is probably faster. + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); + mKeyVals = static_cast(detail::assertNotNull( + malloc(calcNumBytesTotal(numElementsWithBuffer)))); + // no need for calloc because clonData does memcpy + mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); + mNumElements = o.mNumElements; + mMask = o.mMask; + mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; + mInfoInc = o.mInfoInc; + mInfoHashShift = o.mInfoHashShift; + cloneData(o); + } + } + + // Creates a copy of the given map. Copy constructor of each entry is used. + // Not sure why clang-tidy thinks this doesn't handle self assignment, it does + // NOLINTNEXTLINE(bugprone-unhandled-self-assignment,cert-oop54-cpp) + Table& operator=(Table const& o) { + ROBIN_HOOD_TRACE(this); + if (&o == this) { + // prevent assigning of itself + return *this; + } + + // we keep using the old allocator and not assign the new one, because we want to keep the + // memory available. when it is the same size. + if (o.empty()) { + if (0 == mMask) { + // nothing to do, we are empty too + return *this; + } + + // not empty: destroy what we have there + // clear also resets mInfo to 0, that's sometimes not necessary. + destroy(); + init(); + WHash::operator=(static_cast(o)); + WKeyEqual::operator=(static_cast(o)); + DataPool::operator=(static_cast(o)); + + return *this; + } + + // clean up old stuff + Destroyer::value>{}.nodes(*this); + + if (mMask != o.mMask) { + // no luck: we don't have the same array size allocated, so we need to realloc. + if (0 != mMask) { + // only deallocate if we actually have data! + free(mKeyVals); + } + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(o.mMask + 1); + mKeyVals = static_cast(detail::assertNotNull( + malloc(calcNumBytesTotal(numElementsWithBuffer)))); + + // no need for calloc here because cloneData performs a memcpy. + mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); + // sentinel is set in cloneData + } + WHash::operator=(static_cast(o)); + WKeyEqual::operator=(static_cast(o)); + DataPool::operator=(static_cast(o)); + mNumElements = o.mNumElements; + mMask = o.mMask; + mMaxNumElementsAllowed = o.mMaxNumElementsAllowed; + mInfoInc = o.mInfoInc; + mInfoHashShift = o.mInfoHashShift; + cloneData(o); + + return *this; + } + + // Swaps everything between the two maps. + void swap(Table& o) { + ROBIN_HOOD_TRACE(this); + using std::swap; + swap(o, *this); + } + + // Clears all data, without resizing. + void clear() { + ROBIN_HOOD_TRACE(this); + if (empty()) { + // don't do anything! also important because we don't want to write to DummyInfoByte::b, + // even though we would just write 0 to it. + return; + } + + Destroyer::value>{}.nodes(*this); + + auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); + // clear everything, then set the sentinel again + uint8_t const z = 0; + std::fill(mInfo, mInfo + calcNumBytesInfo(numElementsWithBuffer), z); + mInfo[numElementsWithBuffer] = 1; + + mInfoInc = InitialInfoInc; + mInfoHashShift = InitialInfoHashShift; + } + + // Destroys the map and all it's contents. + ~Table() { + ROBIN_HOOD_TRACE(this); + destroy(); + } + + // Checks if both tables contain the same entries. Order is irrelevant. + bool operator==(const Table& other) const { + ROBIN_HOOD_TRACE(this); + if (other.size() != size()) { + return false; + } + for (auto const& otherEntry : other) { + if (!has(otherEntry)) { + return false; + } + } + + return true; + } + + bool operator!=(const Table& other) const { + ROBIN_HOOD_TRACE(this); + return !operator==(other); + } + + template + typename std::enable_if::value, Q&>::type operator[](const key_type& key) { + ROBIN_HOOD_TRACE(this); + return doCreateByKey(key); + } + + template + typename std::enable_if::value, Q&>::type operator[](key_type&& key) { + ROBIN_HOOD_TRACE(this); + return doCreateByKey(std::move(key)); + } + + template + void insert(Iter first, Iter last) { + for (; first != last; ++first) { + // value_type ctor needed because this might be called with std::pair's + insert(value_type(*first)); + } + } + + template + std::pair emplace(Args&&... args) { + ROBIN_HOOD_TRACE(this); + Node n{*this, std::forward(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 insert(const value_type& keyval) { + ROBIN_HOOD_TRACE(this); + return doInsert(keyval); + } + + std::pair 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(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 + // NOLINTNEXTLINE(modernize-use-nodiscard) + typename std::enable_if::value, Q&>::type at(key_type const& key) { + ROBIN_HOOD_TRACE(this); + auto kv = mKeyVals + findIdx(key); + if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { + doThrow("key not found"); + } + return kv->getSecond(); + } + + // Returns a reference to the value found for key. + // Throws std::out_of_range if element cannot be found + template + // NOLINTNEXTLINE(modernize-use-nodiscard) + typename std::enable_if::value, Q const&>::type at(key_type const& key) const { + ROBIN_HOOD_TRACE(this); + auto kv = mKeyVals + findIdx(key); + if (kv == reinterpret_cast_no_cast_align_warning(mInfo)) { + doThrow("key not found"); + } + return kv->getSecond(); + } + + const_iterator find(const key_type& key) const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + const size_t idx = findIdx(key); + return const_iterator{mKeyVals + idx, mInfo + idx}; + } + + template + const_iterator find(const OtherKey& key, is_transparent_tag /*unused*/) const { + ROBIN_HOOD_TRACE(this); + const size_t idx = findIdx(key); + return const_iterator{mKeyVals + idx, mInfo + idx}; + } + + iterator find(const key_type& key) { + ROBIN_HOOD_TRACE(this); + const size_t idx = findIdx(key); + return iterator{mKeyVals + idx, mInfo + idx}; + } + + template + iterator find(const OtherKey& key, is_transparent_tag /*unused*/) { + ROBIN_HOOD_TRACE(this); + const size_t idx = findIdx(key); + return iterator{mKeyVals + idx, mInfo + idx}; + } + + iterator begin() { + ROBIN_HOOD_TRACE(this); + if (empty()) { + return end(); + } + return iterator(mKeyVals, mInfo, fast_forward_tag{}); + } + const_iterator begin() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + return cbegin(); + } + const_iterator cbegin() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + if (empty()) { + return cend(); + } + return const_iterator(mKeyVals, mInfo, fast_forward_tag{}); + } + + iterator end() { + ROBIN_HOOD_TRACE(this); + // no need to supply valid info pointer: end() must not be dereferenced, and only node + // pointer is compared. + return iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; + } + const_iterator end() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + return cend(); + } + const_iterator cend() const { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + return const_iterator{reinterpret_cast_no_cast_align_warning(mInfo), nullptr}; + } + + iterator erase(const_iterator pos) { + ROBIN_HOOD_TRACE(this); + // its safe to perform const cast here + // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast) + return erase(iterator{const_cast(pos.mKeyVals), const_cast(pos.mInfo)}); + } + + // Erases element at pos, returns iterator to the next element. + iterator erase(iterator pos) { + ROBIN_HOOD_TRACE(this); + // we assume that pos always points to a valid entry, and not end(). + auto const idx = static_cast(pos.mKeyVals - mKeyVals); + + shiftDown(idx); + --mNumElements; + + if (*pos.mInfo) { + // we've backward shifted, return this again + return pos; + } + + // no backward shift, return next element + return ++pos; + } + + size_t erase(const key_type& key) { + ROBIN_HOOD_TRACE(this); + size_t idx; + InfoType info; + keyToIdx(key, &idx, &info); + + // check while info matches with the source idx + do { + if (info == mInfo[idx] && WKeyEqual::operator()(key, mKeyVals[idx].getFirst())) { + shiftDown(idx); + --mNumElements; + return 1; + } + next(&info, &idx); + } while (info <= mInfo[idx]); + + // nothing found to delete + return 0; + } + + // reserves space for the specified number of elements. Makes sure the old data fits. + // exactly the same as reserve(c). + void rehash(size_t c) { + 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(-1); + } + + ROBIN_HOOD(NODISCARD) bool empty() const noexcept { + ROBIN_HOOD_TRACE(this); + return 0 == mNumElements; + } + + float max_load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + return MaxLoadFactor100 / 100.0F; + } + + // Average number of elements per bucket. Since we allow only 1 per bucket + float load_factor() const noexcept { // NOLINT(modernize-use-nodiscard) + ROBIN_HOOD_TRACE(this); + return static_cast(size()) / static_cast(mMask + 1); + } + + ROBIN_HOOD(NODISCARD) size_t mask() const noexcept { + ROBIN_HOOD_TRACE(this); + return mMask; + } + + ROBIN_HOOD(NODISCARD) size_t calcMaxNumElementsAllowed(size_t maxElements) const noexcept { + if (ROBIN_HOOD_LIKELY(maxElements <= (std::numeric_limits::max)() / 100)) { + return maxElements * MaxLoadFactor100 / 100; + } + + // we might be a bit inprecise, but since maxElements is quite large that doesn't matter + return (maxElements / 100) * MaxLoadFactor100; + } + + ROBIN_HOOD(NODISCARD) size_t calcNumBytesInfo(size_t numElements) const noexcept { + // we add a uint64_t, which houses the sentinel (first byte) and padding so we can load + // 64bit types. + return numElements + sizeof(uint64_t); + } + + ROBIN_HOOD(NODISCARD) + size_t calcNumElementsWithBuffer(size_t numElements) const noexcept { + auto maxNumElementsAllowed = calcMaxNumElementsAllowed(numElements); + return numElements + (std::min)(maxNumElementsAllowed, (static_cast(0xFF))); + } + + // calculation only allowed for 2^n values + ROBIN_HOOD(NODISCARD) size_t calcNumBytesTotal(size_t numElements) const { +#if ROBIN_HOOD(BITNESS) == 64 + return numElements * sizeof(Node) + calcNumBytesInfo(numElements); +#else + // make sure we're doing 64bit operations, so we are at least safe against 32bit overflows. + auto const ne = static_cast(numElements); + auto const s = static_cast(sizeof(Node)); + auto const infos = static_cast(calcNumBytesInfo(numElements)); + + auto const total64 = ne * s + infos; + auto const total = static_cast(total64); + + if (ROBIN_HOOD_UNLIKELY(static_cast(total) != total64)) { + throwOverflowError(); + } + return total; +#endif + } + +private: + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::value, bool>::type has(const value_type& e) const { + ROBIN_HOOD_TRACE(this); + auto it = find(e.first); + return it != end() && it->second == e.second; + } + + template + ROBIN_HOOD(NODISCARD) + typename std::enable_if::value, bool>::type has(const value_type& e) const { + ROBIN_HOOD_TRACE(this); + return find(e) != end(); + } + + // 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(detail::assertNotNull( + calloc(1, calcNumBytesTotal(numElementsWithBuffer)))); + mInfo = reinterpret_cast(mKeyVals + numElementsWithBuffer); + + // set sentinel + mInfo[numElementsWithBuffer] = 1; + + mInfoInc = InitialInfoInc; + mInfoHashShift = InitialInfoHashShift; + } + + template + typename std::enable_if::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(&l)) + Node(*this, std::piecewise_construct, + std::forward_as_tuple(std::forward(key)), std::forward_as_tuple()); + } else { + shiftUp(idx, insertion_idx); + l = Node(*this, std::piecewise_construct, + std::forward_as_tuple(std::forward(key)), std::forward_as_tuple()); + } + + // mKeyVals[idx].getFirst() = std::move(key); + mInfo[insertion_idx] = static_cast(insertion_info); + + ++mNumElements; + return mKeyVals[insertion_idx].getSecond(); + } + } + + // This is exactly the same code as operator[], except for the return values + template + std::pair 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(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(&l)) Node(*this, std::forward(keyval)); + } else { + shiftUp(idx, insertion_idx); + l = Node(*this, std::forward(keyval)); + } + + // put at empty spot + mInfo[insertion_idx] = static_cast(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(mInfoInc >> 1U); + + // remove one bit of the hash, leaving more space for the distance info. + // This is extremely fast because we can operate on 8 bytes at once. + ++mInfoHashShift; + auto const numElementsWithBuffer = calcNumElementsWithBuffer(mMask + 1); + + for (size_t i = 0; i < numElementsWithBuffer; i += 8) { + auto val = unaligned_load(mInfo + i); + val = (val >> 1U) & UINT64_C(0x7f7f7f7f7f7f7f7f); + std::memcpy(mInfo + i, &val, sizeof(val)); + } + // update sentinel, which might have been cleared out! + mInfo[numElementsWithBuffer] = 1; + + mMaxNumElementsAllowed = calcMaxNumElementsAllowed(mMask + 1); + return true; + } + + 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(mNumElements) * 100.0 / + (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(); + } + + rehashPowerOfTwo((mMask + 1) * 2); + } + + void destroy() { + if (0 == mMask) { + // don't deallocate! + return; + } + + Destroyer::value>{} + .nodesDoNotDeallocate(*this); + + // This protection against not deleting mMask shouldn't be needed as it's sufficiently + // protected with the 0==mMask check, but I have this anyways because g++ 7 otherwise + // reports a compile error: attempt to free a non-heap object ‘fm’ + // [-Werror=free-nonheap-object] + if (mKeyVals != reinterpret_cast(&mMask)) { + free(mKeyVals); + } + } + + void init() noexcept { + mKeyVals = reinterpret_cast(&mMask); + mInfo = reinterpret_cast(&mMask); + mNumElements = 0; + mMask = 0; + mMaxNumElementsAllowed = 0; + mInfoInc = InitialInfoInc; + mInfoHashShift = InitialInfoHashShift; + } + + // 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 +}; + +} // namespace detail + +// map + +template , + typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> +using unordered_flat_map = detail::Table; + +template , + typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> +using unordered_node_map = detail::Table; + +template , + typename KeyEqual = std::equal_to, size_t MaxLoadFactor100 = 80> +using unordered_map = + detail::Table) <= sizeof(size_t) * 6 && + std::is_nothrow_move_constructible>::value && + std::is_nothrow_move_assignable>::value, + MaxLoadFactor100, Key, T, Hash, KeyEqual>; + +// set + +template , typename KeyEqual = std::equal_to, + size_t MaxLoadFactor100 = 80> +using unordered_flat_set = detail::Table; + +template , typename KeyEqual = std::equal_to, + size_t MaxLoadFactor100 = 80> +using unordered_node_set = detail::Table; + +template , typename KeyEqual = std::equal_to, + size_t MaxLoadFactor100 = 80> +using unordered_set = detail::Table::value && + std::is_nothrow_move_assignable::value, + MaxLoadFactor100, Key, void, Hash, KeyEqual>; + +} // namespace robin_hood + +#endif diff --git a/examples/rngtest.c b/examples/rngtest.c new file mode 100644 index 00000000..4a39c4e6 --- /dev/null +++ b/examples/rngtest.c @@ -0,0 +1,68 @@ +#include +#include +#include "../stc/crandom.h" +#ifdef __cplusplus +#include +#endif + + +#define NN 1000000000 + +int main(void) +{ + clock_t difference, before; + uint64_t v; + printf("start\n"); + + mt19937_t state = mt19937_default(); + uint32_t k = mt19937_rand(&state); + printf("%u - %g\n", k, c_randToFloat(k)); + + before = clock(); \ + v = 0; + for (size_t i=0; i