===================================================================
@@ -96,6 +96,7 @@
${bits_srcdir}/codecvt.h \
${bits_srcdir}/concept_check.h \
${bits_srcdir}/cpp_type_traits.h \
+ ${bits_srcdir}/cuckoo.h \
${bits_srcdir}/deque.tcc \
${bits_srcdir}/enable_special_members.h \
${bits_srcdir}/forward_list.h \
===================================================================
@@ -386,6 +386,7 @@
${bits_srcdir}/codecvt.h \
${bits_srcdir}/concept_check.h \
${bits_srcdir}/cpp_type_traits.h \
+ ${bits_srcdir}/cuckoo.h \
${bits_srcdir}/deque.tcc \
${bits_srcdir}/enable_special_members.h \
${bits_srcdir}/forward_list.h \
===================================================================
@@ -0,0 +1,3103 @@
+// hybrid wild cuckoo hashtable implementation -*- C++ -*-
+
+// Copyright (C) 2010-2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file bits/cuckoo.h
+ * This is an internal header file, included by other library headers.
+ * Do not attempt to use it directly. @headername{cuckoo}
+ * This file implements Hybrid Wild Cuckoo and Wild Cuckoo. The latter is used
+ * as a building block for Hybrid Wild Cuckoo when all the bells and whistles
+ * are required (as they are for a C++ standards-compliant unordered_{set,map}).
+ * It may also be interesting on its own.
+ *
+ * For simplicity we use one table (as is also done in some variants of Cuckoo).
+ * We also force the table size to be a power of 2 in this implementation,
+ * though there is no theoretical reason to do so. The number of elements in
+ * the table is _M_num_elements in the code, but called "n" here; the number of
+ * buckets is _M_num_buckets in the code, but called "b" here.
+ *
+ * As usual in such discussions, the big-O bounds stated below
+ * assume that hashing an element is O(1). We also ignore the bitset
+ * size and z, parameters typically set to small integers, when
+ * discussing big-O bounds. E.g., we never write O(z); we write O(1)
+ * for that.
+ *
+ * In Wild Cuckoo, the algorithm for inserting an item is similar to Cuckoo
+ * except that the set of possible "nests" for an item can grow dynamically.
+ * In particular, the algorithm for find-or-insert-if-not-present (often called
+ * "insert" among C++ programmers) is as follows:
+ * 1. Compute g1 = H1(key) and g2 = H2(key), where H1 and H2 are hash functions.
+ * 2. Let h1 = g1 % b and h2 = g2 % b
+ * 3. Look for the key in all its possible nests. Typically these are just
+ * h1, h1^1, h1^2, ..., h1^z, h2, h2^1, h2^2, ..., and h2^z. (Say, for z = 4.)
+ * However, we also keep a map of <g1, g2> pairs to information on additional
+ * possible nests, which can be anywhere in the table. Pairs with additional
+ * possible nests are called "extended." More details on this
+ * are below. A key point is that, unlike in all previous
+ * multiple-choice-hashing schemes, a key with any hash codes can appear
+ * anywhere in the table... Hence the "Wild" in Wild Cuckoo.
+ * 4. If the key is not found in any of its nests then it must be inserted,
+ * into a empty nest if possible. If no nest is free then we have two
+ * choices:
+ * o If the size of all extensions to <g1, g2> is below the "extension cap,"
+ * a constant, and either <g1, g2> is extended or a coin flip is heads,
+ * then (further) extend the set of possible set of nests for <g1, g2>.
+ * o Otherwise, bump an element in one of the relevant nests, put the new
+ * item in its place, and then re-insert the item that was bumped.
+ *
+ * When inserting an item known to be not present, we follow a substantially
+ * similar procedure. That's a bit of a departure from Cuckoo, which will
+ * prefer to bump immediately rather than compute H2(key). Whether this matters
+ * is an open question.
+ *
+ * In the variation of Wild Cuckoo implemented here, we use the concept of a
+ * sequence of buckets defined by an ordered pair of indices, i and j:
+ * The sequence is given by the values taken by y in this pseudocode (assume
+ * i != j and all math is mod b):
+ * y = i
+ * repeat for k in {0, ..., b-2}:
+ * if (j - i + k == 0) break; else y += j - i + k;
+ * y = i - (j - i - 1)
+ * repeat for l in {2, ..., b-1}:
+ * y -= j - i - l;
+ * We never use more than b values from such a sequence, and the first b values
+ * are unique if i != j and b is a power of 2. (Reasoning: it builds off the
+ * well-known fact that if b is a power of two then the first b elements of
+ * 0, 1, 3, 6, 10, ... are unique (mod b).)
+ *
+ * The first "extension" for a particular <g1, g2> pair is any one bucket, the
+ * second is any two buckets, the third is four buckets specified as the first
+ * four elements of a sequence defined by a pair of buckets, the fourth is the
+ * first eight buckets specified as the first eight elements of a sequence
+ * defined by a pair of buckets, etc.
+ *
+ * Conceptually there's a hash map for extensions, with keys being <g1, g2>
+ * pairs and values being the specification of a permutation of bucket indices
+ * and how much of that permutation to use. Unlike everything else, these
+ * key-value pairs are stored in "chaining" style, in the same table as our
+ * pointers to Values. A bucket's pointer can be NULL or point to one of these:
+ * 1. a single Value (and nothing else---these are not linked lists)
+ * 2. a linked list of Extension (chaining style, for our bookkeeping)
+ * A per-bucket "hint," one extra bit per bucket, distinguishes these cases.
+ * (It may be possible to "steal" a bit from pointers in buckets, thus
+ * eliminating the need to store hints separately.)
+ *
+ * Hybrid Wild Cuckoo is similar in spirit to Wild Cuckoo except that it starts
+ * with a more traditional and faster "hash the key once and hope for the best"
+ * strategy. We use H0 as the hash function. Only buckets that are "overfull"
+ * get the Wild Cuckoo treatment, using hash functions H1 and H2. In Hybrid
+ * Wild Cuckoo, hints are larger, because they have space to store a small
+ * bitset that in the best case records where to find all the keys for this
+ * bucket. If the small bitset is not sufficient to encode that information
+ * then the bucket is designated as "overfull" and Wild Cuckoo is enabled for
+ * that bucket.
+ *
+ * A few more details:
+ * o insert invalidates no iterators
+ * o erase invalidates no iterators except for those pointing to the erased key
+ * o Iterator "re-validation" can take O(1) time. Iterator "re-validation"
+ * occurs when the bucket number stored is stale, but we need an
+ * accurate bucket number, e.g., because we are iterating, or the
+ * iterator is passed to erase(). See Appendix for how it could be done.
+ * o erase(iterator) takes O(1 + time to re-validate the iterator) time. So, if
+ * iterator re-validation is O(1) then erase(iterator) is also. (But,
+ * erase(begin()) may be slower than that if we start to cache what begin()
+ * would return?)
+ *
+ * As before, conceptually a "bucket" is a list of items that all hash to the
+ * same value mod b. A "slot" is an entry in the hashtable. Conceptually, it
+ * is a pair of values, a hint and a pointer. These can be stored in two
+ * separate arrays, or in one array of uintptr_t. The latter is possible if we
+ * can "steal" bits from pointers because we know that certain values for
+ * pointers are unsupported.
+ *
+ * If hash collisions are rare then a lot of times the bucket for an
+ * item, x, will contain only x, and the slot it will use is
+ * ht_->_M_slots[H0(x) % b]. The hint in slot ht_->_M_slots[i] always contains
+ * information about the bucket of items that hash to i (mod b).
+ *
+ * In Hybrid Wild Cuckoo, a bucket's pointer points to one of two things:
+ * 1. a Value (and nothing else---these are not linked lists)
+ * 2. a linked list of Extension (chaining style, for our bookkeeping)
+ *
+ * Commit-or-Rollback Semantics
+ *
+ * We implement commit-or-rollback semantics for certain operations, as required
+ * by the C++ standard.
+ *
+ * A cuckoo hash insertion can rearrange items, though in practice it usually
+ * doesn't. We have "rollback state" to capture what we're changing. In the
+ * code, _M_get_rollback_state() is initially null, and we call this the "easy" state.
+ * For example, perhaps all we need to do is to copy an object and update
+ * _M_slots and _M_num_elements. In that case the copy requires allocation, but
+ * we've arranged the code to have nothing to rollback if that throws. The
+ * "hard" state, on the other hand, has non-null _M_get_rollback_state() that we
+ * update as we go, because there may more operations to come, and if those
+ * throw we have to roll back.
+ *
+ * Appendix 1: Things that will be added
+ *
+ * o Proper support for allocators
+ *
+ * o O(1) time for begin. The initial implementation will likely be to keep
+ * track of the lowest-numbered bucket that contains a Value.
+ *
+ * o Proper support for allocators
+ *
+ * Appendix: Things that might be added
+ *
+ * o Iteration through all n elements takes O(n) time (not O(b)):
+ * The easy way to deal with this is, I think, to have extra information
+ * that is maintained only when N/B < (some constant). So when N/B is really
+ * low we have this extra info, and when it is not, we know O(B) = O(N) so
+ * straightforward techniques are fine (e.g., skipping over as many empty
+ * buckets as necessary when advancing an iterator). We keep a doubly-linked
+ * list embedded in an array of length B when N/B is tiny. There's not much
+ * reason to complicate this. We simply encode the prev/next data in the
+ * extra array. The type of "prev" and "next" is _Bucket_number. When the
+ * number of elements grows beyond some threshold we can discard the extra
+ * array. The "discard" operation takes O(N) = O(B) time since N/B is very
+ * near some constant at the time it occurs. Similarly, if deletions cause
+ * N/B to get tiny again then we can revive the extra array and reconstruct
+ * the doubly-linked list at a cost of O(N) = O(B).
+ *
+ * O(1) iterator re-validation: Given an iterator, that is little more than a
+ * pointer to a Value, how do we find the bucket pointing to that Value? If
+ * the extension cap is finite then the number of possible nests for any
+ * key is bounded by a constant, so we can use find(). Unfortunately, in
+ * practice, there are contexts where using an infinite (or very large)
+ * extension cap makes sense. So, for only those keys with a large number
+ * of possible nests, we could store a separate hash map that allows relevant
+ * pointers to be mapped back to buckets in constant time. However, it
+ * seems like more trouble than its worth, so this isn't implemented.
+ *
+ * local iterators that approach the spirit of the C++ standard rather than just
+ * meeting the minimum requirements: this is a low priority because local
+ * iterators are an obscure, seldom-used feature. That said, it is certainly
+ * possible to do some work in this area.
+ *
+ * unordered_multiset and unordered_multimap: no decision has been made on how
+ * to implement these.
+ */
+
+#ifndef _CUCKOO_H
+#define _CUCKOO_H
+
+#include <algorithm>
+#include <bitset>
+#include <cassert>
+#include <climits>
+#include <functional>
+#include <iterator>
+#include <limits>
+#include <math.h>
+#include <memory>
+#include <random>
+#include <stddef.h>
+#if __cpp_exceptions
+#include <stdexcept>
+#endif
+#include <stdlib.h>
+#include <string>
+#include <string.h>
+#include <utility>
+#include <vector>
+
+
+namespace cuckoo_internal
+{
+ typedef size_t size_type;
+ typedef size_t _Bucket_number;
+
+ // _Cuckoos: either empty or a pair of hash function objects, depending on
+ // whether select_from_hash_function_family() is present in _V. _HasFamily
+ // is a helper whose purpose is to provide an _S_cuckoo.
+ template<typename _V>
+ struct _HasFamily
+ {
+ // SFINAE will make the first overload available if _V has a suitable
+ // select_from_hash_function_family() method.
+ template<typename _W>
+ static char
+ _S_func(_V (*)
+ [sizeof(((_W*)0)
+ ->select_from_hash_function_family((std::knuth_b*)0))]);
+
+ template<typename _W>
+ static int
+ _S_func(...);
+
+ enum
+ {
+ _S_cuckoo = sizeof(_S_func<_V>(0)) == sizeof(char)
+ };
+ };
+
+ template<typename _V, bool __cuckoo = _HasFamily<_V>::_S_cuckoo> struct _Cuckoos;
+
+ template<typename _V>
+ struct _Cuckoos<_V, true> : public _HasFamily<_V>
+ {
+ // TODO: invoke this from the appropriate places.
+ template<typename _Hasher, typename R>
+ void
+ _M_select_hash_functions(_Hasher* __h, R* __rng)
+ {
+ _M_hashers[0] = __h->select_from_hash_function_family(__rng);
+ _M_hashers[1] = __h->select_from_hash_function_family(__rng);
+ }
+
+ template<typename _Key>
+ size_type
+ _M_hash1(const _Key& __v, size_type) const
+ { return _M_hashers[0](__v); }
+
+ template<typename _Key>
+ size_type
+ _M_hash2(const _Key& __v, size_type) const
+ { return _M_hashers[1](__v); }
+
+ decltype(((_V*)0)->select_from_hash_function_family((std::knuth_b*)0)) _M_hashers[2];
+ };
+
+ template<typename _V>
+ struct _Cuckoos<_V, false> : public _HasFamily<_V>
+ {
+ // When the client hasn't provided us with select_from_hash_function_family,
+ // _M_hash1 and _M_hash2 fall back to rehashing the output of the one hash
+ // function that the client did provide.
+ template<typename __Hasher, typename _RNG>
+ void
+ _M_select_hash_functions(__Hasher*, _RNG* r)
+ {
+ _M_salt1 = _S_make_salt(r);
+ _M_salt2 = _S_make_salt(r);
+ while (_M_salt1 == _M_salt2)
+ {
+ _M_salt1 += (*r)() * 2;
+ }
+ assert(_M_salt1 % 2 == 1 && _M_salt2 % 2 == 1);
+ }
+
+ template<typename _RNG>
+ static size_type
+ _S_make_salt(_RNG* __r)
+ {
+ size_type __best_salt = 0;
+ size_type __best_score = 0;
+ int __tries = 2 + ((*__r)() & 0x7);
+ for (int __i = 0; __i < __tries; __i++)
+ {
+ size_type __salt = (*__r)() | 1;
+ size_type __q = _S_salt_score(__salt);
+ if (__q > __best_score) {
+ __best_score = __q;
+ __best_salt = __salt;
+ }
+ }
+ return __best_salt;
+ }
+
+ // Higher is better.
+ static size_type
+ _S_salt_score(size_type __salt)
+ {
+ const auto __bits = std::numeric_limits<size_type>::digits;
+ return (std::numeric_limits<size_type>::max()
+ - abs(popcnt(__salt) - __bits/2));
+ }
+
+ template<typename __I>
+ static int
+ popcnt(__I __n)
+ {
+ const int __shift = sizeof(__n) <= sizeof(unsigned int)
+ ? 0
+ : std::numeric_limits<unsigned int>::digits;
+ if (sizeof(__n) <= sizeof(unsigned int))
+ {
+ return std::bitset<std::numeric_limits<unsigned int>::digits>(__n).count();
+ }
+ else
+ {
+ int __count = 0;
+ while (__n != 0)
+ {
+ __count +=
+ std::bitset<std::numeric_limits<unsigned int>::digits>(__n).count();
+ __n >>= __shift;
+ }
+ return __count;
+ }
+ }
+
+ static size_type
+ _S_rehash(size_type __x, size_type __y)
+ {
+ const auto __bits = std::numeric_limits<size_type>::digits;
+ const int __shift = __bits * 30 / 32 - 13;
+ __x += __y >> 10;
+ __x *= __y;
+ __x ^= __x >> __shift;
+ __x *= __y;
+ __x ^= __x >> (__shift ^ 1);
+ return __x;
+ }
+
+ template<typename __Key>
+ size_type
+ _M_hash1(const __Key&, size_type g0) const
+ { return _S_rehash(g0, _M_salt1); }
+
+ template<typename __Key>
+ size_type
+ _M_hash2(const __Key&, size_type g0) const
+ { return _S_rehash(g0, _M_salt2); }
+
+ size_type _M_salt1;
+ size_type _M_salt2;
+ };
+
+ // _Settings contains parameters for growing and shrinking the table.
+ // It also packages a hasher that may have zero size.
+ template<typename _Key, typename _Hasher, int _S_min_buckets>
+ class _Cuckoo_settings : public _Hasher, public _Cuckoos<_Hasher>
+ {
+ public:
+ typedef _Key key_type;
+ typedef _Hasher hasher;
+
+ _Cuckoo_settings(const hasher& hf,
+ const float __enlarge,
+ const float __shrink)
+ : hasher(hf),
+ _M_enlarge_threshold(0),
+ _M_shrink_threshold(0),
+ _M_num_hashtable_copies(0)
+ {
+ set_enlarge_factor(__enlarge);
+ set_shrink_factor(__shrink);
+ }
+
+ size_type
+ _M_hash0(const key_type& __v) const
+ { return hasher::operator()(__v); }
+
+ void
+ set_enlarge_factor(float __f)
+ { _M_enlarge_factor = __f; }
+
+ void
+ set_shrink_factor(float __f)
+ { _M_shrink_factor = __f; }
+
+ void
+ set_enlarge_threshold(size_type __t)
+ { _M_enlarge_threshold = __t; }
+
+ void
+ set_shrink_threshold(size_type __t)
+ { _M_shrink_threshold = __t < _S_min_buckets ? 0 : __t; }
+
+ size_type
+ enlarge_size(size_type __x) const
+ { return static_cast<size_type>(__x * _M_enlarge_factor); }
+
+ size_type
+ shrink_size(size_type __x) const
+ { return static_cast<size_type>(__x * _M_shrink_factor); }
+
+ size_type
+ _M_num_copies() const
+ { return static_cast<size_type>(_M_num_hashtable_copies); }
+
+ void
+ _M_increment_num_copies()
+ { ++_M_num_hashtable_copies; }
+
+ // Reset the enlarge and shrink thresholds
+ void
+ _M_reset_thresholds(size_type __num_buckets)
+ {
+ set_enlarge_threshold(enlarge_size(__num_buckets));
+ set_shrink_threshold(shrink_size(__num_buckets));
+ }
+
+ // Caller is resposible for calling reset_threshold right after
+ // set_resizing_parameters.
+ void
+ set_resizing_parameters(float shrink, float grow)
+ {
+ assert(shrink >= 0.0);
+ grow = std::min(grow, 1.0f);
+ // Why 2.2 here? Would 2.0 or some other value be better?
+ // 2.2 should avoid thrashing the size, but is this well considered?
+ shrink = std::min(shrink, grow / 2.2f);
+ set_shrink_factor(shrink);
+ set_enlarge_factor(grow);
+ }
+
+ // Returns the smallest size a hashtable can be without being too crowded.
+ // Except, it will not return a value less than the second arg. Run time is
+ // O(lg(num_elts)): that's subpar theoretically, but reasonable in
+ // context, as rebuilding the table will take at least O(num_elts) time.
+ size_type
+ min_buckets(size_type __num_elts, size_type __min_buckets_wanted)
+ {
+ size_type __result = _S_min_buckets;
+ while (__result < __min_buckets_wanted
+ || (__num_elts
+ >= static_cast<size_type>(__result * _M_enlarge_factor)))
+ {
+ // Try to avoid overflowing size_type, since __result can exceed
+ // max_size() here.
+ if (static_cast<size_type>(__result * 2) < __result)
+ {
+#if __cpp_exceptions
+ throw std::length_error("resize overflow");
+#else
+ assert(0 && "resize overflow");
+#endif
+ }
+ __result *= 2;
+ }
+ return __result;
+ }
+
+ size_type _M_enlarge_threshold; // table.size() * enlarge_factor
+ size_type _M_shrink_threshold; // table.size() * shrink_factor
+ float _M_enlarge_factor; // how full before resize
+ float _M_shrink_factor; // how empty before resize
+
+ /* A counter incremented when we copy/move the table. */
+ unsigned int _M_num_hashtable_copies;
+ };
+
+ // Exception throwing utility.
+#ifdef ATTRIBUTE_NORETURN
+ template<typename _V>
+ inline void
+ ThrowException() ATTRIBUTE_NORETURN;
+#endif
+
+ template<typename _V>
+ inline void
+ ThrowException()
+ {
+#if __cpp_exceptions
+ throw _V();
+#endif
+ for (;;) assert(0 && "internal error: unreachable");
+ }
+
+ class _Permutation_iterator
+ {
+ public:
+ typedef cuckoo_internal::_Bucket_number _Bucket_number;
+ typedef cuckoo_internal::size_type size_type;
+ _Permutation_iterator(_Bucket_number __i, _Bucket_number __j,
+ size_type __b /* num_buckets */, size_type __len)
+ : _M_i(__i),
+ _M_j(__j),
+ _M_y(__i),
+ _M_delta(__j - __i),
+ _M_b(__b),
+ _M_len(__len) {
+ assert(0 <= __i && __i < __b && 0 <= __j && __j < __b && __i != __j);
+ assert((__b & (__b - 1)) == 0); // b must be a power of 2.
+ assert(__len <= __b);
+ }
+
+ bool
+ _M_done() const
+ { return _M_len == 0; }
+
+ _Bucket_number
+ _M_next()
+ {
+ assert(!_M_done());
+ --_M_len;
+ // Invariant: _M_y is the value we want. Store it and compute the next value.
+ _Bucket_number __result = _M_y;
+ if (_M_delta == 0)
+ {
+ _M_delta = _M_mod_b(-(_M_j - _M_i - 2));
+ _M_y = _M_mod_b(_M_i - (_M_j - _M_i - 1));
+ }
+ else
+ {
+ _M_y += _M_delta;
+ ++_M_delta;
+ }
+ _M_delta = _M_mod_b(_M_delta);
+ _M_y = _M_mod_b(_M_y);
+ return __result;
+ }
+
+ private:
+ _Bucket_number
+ _M_mod_b(_Bucket_number __x)
+ { return __x & (_M_b - 1); }
+
+ const _Bucket_number _M_i;
+ const _Bucket_number _M_j;
+ _Bucket_number _M_y;
+ _Bucket_number _M_delta;
+ const size_type _M_b;
+ size_type _M_len;
+ };
+
+ // Helpers for compile-time computation.
+
+ template<int _S_x, int _S_y>
+ struct _Max
+ { enum { _S_value = _S_x > _S_y ? _S_x : _S_y }; };
+
+ // ceil(lg(x)); requires x >= 1.
+ template<size_t _S_x>
+ struct _Ceil_log2
+ {
+ // The recursive case divides by 16, so that template depth
+ // is kept low. To avoid overflow, we never add anything to x.
+ enum
+ {
+ _S_is_power_of_two = (_S_x & (_S_x - 1)) == 0,
+ _S_value = _S_x == 2 ? 1
+ : _S_x <= 4 ? 2
+ : _S_x <= 8 ? 3
+ : _S_x <= 16 ? 4
+ : _S_x <= 32 ? 5
+ : (_Ceil_log2<(_S_x / 16) | 1>::_S_value
+ + (_S_is_power_of_two ? 3 : 4)) };
+ };
+
+ template<> struct _Ceil_log2<1> {
+ enum { _S_value = 0 };
+ };
+
+ template<size_t _S_x>
+ struct SmallestPowerOfTwoNotLessThan {
+ enum { _S_value = static_cast<size_t>(1) << _Ceil_log2<_S_x>::_S_value };
+ };
+
+ // Utilities related to random number generators (RNGs).
+
+ // We need random numbers for choosing hash functions from a family,
+ // deciding whether to bump or extend, deciding what to bump, and
+ // _M_random_odd_number. But, none of those matter for very small
+ // tables, so we initialize the RNG lazily, when it's first needed.
+ typedef std::minstd_rand _RNG; // Other choices here would likely be fine too.
+
+ class _RNGState
+ {
+ public:
+ typedef cuckoo_internal::size_type size_type;
+
+ explicit _RNGState(const std::seed_seq& seq)
+ { _M_reset(seq); }
+
+ void
+ _M_reset(const std::seed_seq& __seq)
+ {
+ std::vector<std::uint_least32_t> __v(__seq.size());
+ __seq.param(__v.begin());
+ std::seed_seq __tmp(__v.begin(), __v.end());
+ _M_rng.seed<std::seed_seq>(__tmp);
+ _M_random_odd_number =
+ _M_rand_at_most(std::numeric_limits<size_type>::max()) | 1;
+ }
+
+ uint64_t
+ _M_rand_uint64()
+ {
+ constexpr uint64_t __rngmax = _RNG::max();
+ constexpr uint64_t __rngmin = _RNG::min();
+ constexpr uint64_t __rngrange = __rngmax - __rngmin;
+ static_assert(__rngrange + _RNG::min() == _RNG::max(), "overflow");
+ uint64_t __result = static_cast<uint64_t>(_M_rng()) - __rngmin;
+ if (__rngrange == std::numeric_limits<uint64_t>::max()) return __result;
+ // One value is not enough.
+ const int __bits_per_random_number = _Ceil_log2<__rngrange>::_S_value;
+ for (int __done = __bits_per_random_number; __done < 64;
+ __done += __bits_per_random_number) {
+ __result <<= __bits_per_random_number;
+ __result += static_cast<uint64_t>(_M_rng()) - __rngmin;
+ }
+ return __result;
+ }
+
+ // Compute a random number.
+ size_type
+ _M_rand_at_most(size_type __max)
+ {
+ assert(sizeof(__max) <= 8 || __max <= std::numeric_limits<uint64_t>::max());
+ if (__max == _M_rng.max()) return _M_rng();
+ if (sizeof(__max) >= 8 && __max == std::numeric_limits<uint64_t>::max()) {
+ return _M_rand_uint64();
+ }
+ // Possible optimization: consume fewer random bits here.
+ return _M_rand_uint64() % (__max + 1);
+ }
+
+ size_type
+ _M_get_random_odd_number() const
+ { return _M_random_odd_number; }
+
+ private:
+ _RNG _M_rng;
+ size_type _M_random_odd_number; // This is modifed only when _M_rng is seeded.
+ };
+} // namespace cuckoo_internal
+
+// The _Cuckoo class for hashed associative containers.
+// _Value: what is stored in the table. E.g., for maps, this is a pair.
+// _Key: something in a 1-to-1 correspondence to a Value, that can be used
+// to search for a Value in the table (find() takes a Key).
+// _Hasher: hash function(s)
+// _Extract_key: given a Value, returns the unique Key associated with it.
+// Must have a result_type typedef indicating the return type
+// of operator().
+// _Equal_key: given two Keys, are they equal?
+// _Alloc: some memory allocations are performed via this.
+template<typename _Value, typename _Key, typename _Hasher,
+ typename _Extract_key, typename _Equal_key, typename _Alloc,
+ int _S_z = 4>
+ class _Cuckoo;
+
+template<class _Value, class _Key, class _Hasher, class _Extract_key,
+ class _Equal_key, class _Alloc, int _S_z>
+ class _Cuckoo_const_iterator;
+
+template<class _Value, class _Key, class _Hasher, class _Extract_key,
+ class _Equal_key, class _Alloc, int _S_z>
+ class _Cuckoo_iterator
+ {
+ private:
+ typedef typename _Alloc::template rebind<_Value>::other value_alloc_type;
+ typedef _Cuckoo<_Value, _Key, _Hasher, _Extract_key, _Equal_key, _Alloc,
+ _S_z> _Table;
+ typedef typename _Table::_Bucket_number _Bucket_number;
+ typedef typename _Table::_Slot _Slot;
+ friend class _Cuckoo<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>;
+ friend class _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>;
+
+ public:
+ typedef _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>
+ iterator;
+ typedef _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ const_iterator;
+
+ typedef std::forward_iterator_tag iterator_category;
+ typedef _Value value_type;
+ typedef typename value_alloc_type::difference_type difference_type;
+ typedef typename value_alloc_type::size_type size_type;
+ typedef typename value_alloc_type::const_reference reference;
+ typedef typename value_alloc_type::const_pointer pointer;
+
+ // Constructors
+ private:
+ _Cuckoo_iterator(const _Table* __h, _Bucket_number __pos, bool __advance)
+ {
+ _M_ht = const_cast<_Table*>(__h);
+ _M_b = __pos;
+ if (__advance)
+ {
+ _M_advance_past_empty();
+ }
+ else
+ {
+ assert(_M_b < _M_ht->bucket_count());
+ _M_val = const_cast<_Value*>(_M_ht->_M_slots[_M_b].get_ptr());
+ }
+ }
+
+ public:
+ _Cuckoo_iterator() : _M_val(nullptr), _M_ht(nullptr), _M_b(0) { }
+
+ // The default destructor is fine; we don't define one
+ // The default operator= is fine; we don't define one
+
+ // Dereference
+ reference
+ operator*() const
+ { return *_M_val; }
+
+ pointer
+ operator->() const
+ { return &(operator*()); }
+
+ // Move past empty slots and bookkeeping slots.
+ void
+ _M_advance_past_empty()
+ {
+ const _Bucket_number __n = _M_ht->bucket_count();
+ while (_M_b < __n && _M_ht->_M_slots[_M_b].has_no_element())
+ {
+ ++_M_b;
+ }
+ _M_val = const_cast<_Value*>(_M_b < __n ? _M_ht->_M_slots[_M_b].get_ptr()
+ : nullptr);
+ }
+
+ iterator&
+ operator++()
+ {
+ _M_update();
+ ++_M_b;
+ _M_advance_past_empty();
+ return *this;
+ }
+
+ iterator
+ operator++(int)
+ {
+ iterator __tmp(*this);
+ ++*this;
+ return __tmp;
+ }
+
+ // Comparison.
+ bool
+ operator==(const iterator& __it) const
+ { return _M_val == __it._M_val; }
+
+ bool
+ operator!=(const iterator& __it) const
+ { return _M_val != __it._M_val; }
+
+ private:
+ // Conversion of const_iterator to iterator. This is private because it is
+ // intended for internal use only.
+ _Cuckoo_iterator(const const_iterator& __it)
+ : _M_val(const_cast<_Value*>(__it._M_val)),
+ _M_ht(const_cast<_Table*>(__it._M_ht)),
+ _M_b(__it._M_b)
+ { }
+
+ void
+ _M_update()
+ {
+ _M_b = _M_ht->_M_mod_bucket_count(_M_b);
+ if (_M_ht->_M_slots[_M_b].get_ptr_raw()
+ != reinterpret_cast<uintptr_t>(_M_val))
+ {
+ // _M_b is stale. Use _M_val to find correct bucket number.
+ _M_b = _M_ht->find(_M_ht->get_key(*_M_val))._M_b;
+ assert(_M_val == _M_ht->_M_slots[_M_b].get_ptr());
+ }
+ }
+
+ _Value* _M_val;
+ _Table* _M_ht;
+ _Bucket_number _M_b;
+ };
+
+template<typename _Value, typename _Key, typename _Hasher,
+ typename _Extract_key, typename _Equal_key, typename _Alloc, int _S_z>
+ struct _Cuckoo_const_iterator
+ {
+ private:
+ typedef typename _Alloc::template rebind<_Value>::other value_alloc_type;
+ typedef _Cuckoo<_Value, _Key, _Hasher, _Extract_key, _Equal_key, _Alloc,
+ _S_z> _Table;
+ typedef typename _Table::_Bucket_number _Bucket_number;
+ typedef typename _Table::_Slot _Slot;
+ friend class _Cuckoo<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>;
+ friend class _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>;
+
+ public:
+ typedef _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>
+ iterator;
+ typedef _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ const_iterator;
+
+ typedef std::forward_iterator_tag iterator_category;
+ typedef _Value value_type;
+ typedef typename value_alloc_type::difference_type difference_type;
+ typedef typename value_alloc_type::size_type size_type;
+ typedef typename value_alloc_type::const_reference reference;
+ typedef typename value_alloc_type::const_pointer pointer;
+
+ private:
+ _Cuckoo_const_iterator(const _Table* __h,
+ _Bucket_number __pos,
+ bool __advance)
+ {
+ _M_ht = const_cast<_Table*>(__h);
+ _M_b = __pos;
+ if (__advance)
+ {
+ _M_advance_past_empty();
+ }
+ else
+ {
+ assert(_M_b < _M_ht->bucket_count());
+ _M_val = _M_ht->_M_slots[_M_b].get_ptr();
+ }
+ }
+
+ public:
+ _Cuckoo_const_iterator() : _M_val(nullptr), _M_ht(nullptr), _M_b(0) { }
+
+ // This lets us convert regular iterators to const iterators
+ _Cuckoo_const_iterator(const iterator& __it)
+ : _M_val(__it._M_val), _M_ht(__it._M_ht), _M_b(__it._M_b)
+ { }
+
+ reference
+ operator*() const
+ { return *_M_val; }
+
+ pointer
+ operator->() const
+ { return &(operator*()); }
+
+ // Advance _M_b zero or more times, if necessary. Set _M_val when done.
+ void
+ _M_advance_past_empty()
+ {
+ const _Bucket_number __n = _M_ht->bucket_count();
+ while (_M_b < __n && _M_ht->_M_slots[_M_b].has_no_element())
+ {
+ ++_M_b;
+ }
+ _M_val = _M_b < __n ? _M_ht->_M_slots[_M_b].get_ptr() : nullptr;
+ }
+
+ const_iterator&
+ operator++()
+ {
+ _M_update();
+ ++_M_b;
+ _M_advance_past_empty();
+ return *this;
+ }
+
+ const_iterator
+ operator++(int)
+ {
+ const_iterator __tmp(*this);
+ ++*this;
+ return __tmp;
+ }
+
+ // Comparison.
+ bool
+ operator==(const const_iterator& __it) const
+ { return _M_val == __it._M_val; }
+
+ bool
+ operator!=(const const_iterator& __it) const
+ { return _M_val != __it._M_val; }
+
+ private:
+ void
+ _M_update()
+ {
+ _M_b = _M_ht->_M_mod_bucket_count(_M_b);
+ if (_M_ht->_M_slots[_M_b].get_ptr_raw()
+ != reinterpret_cast<uintptr_t>(_M_val))
+ {
+ // _M_b is stale. Use _M_val to find correct bucket number.
+ _M_b = _M_ht->find(_M_ht->get_key(*_M_val))._M_b;
+ assert(_M_val == _M_ht->_M_slots[_M_b].get_ptr());
+ }
+ }
+
+ private:
+ const _Value* _M_val;
+ const _Table* _M_ht;
+ _Bucket_number _M_b;
+ };
+
+template<typename _Value, typename _Key, typename _Hasher,
+ typename _Extract_key, typename _Equal_key, typename _Alloc, int _S_z>
+ class _Cuckoo_const_local_iterator;
+
+template<typename _Value, typename _Key, typename _Hasher,
+ typename _Extract_key, typename _Equal_key, typename _Alloc, int _S_z>
+ class _Cuckoo_local_iterator
+ {
+ private:
+ typedef typename _Alloc::template rebind<_Value>::other value_alloc_type;
+ friend class _Cuckoo<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>;
+ friend class _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>;
+ friend class _Cuckoo_const_local_iterator<_Value, _Key, _Hasher,
+ _Extract_key, _Equal_key, _Alloc, _S_z>;
+
+ public:
+ typedef _Cuckoo_local_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ local_iterator;
+ typedef _Cuckoo_const_local_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ const_local_iterator;
+ typedef _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>
+ iterator;
+ typedef _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ const_iterator;
+
+ typedef std::forward_iterator_tag iterator_category;
+ typedef _Value value_type;
+ typedef typename value_alloc_type::difference_type difference_type;
+ typedef typename value_alloc_type::size_type size_type;
+ typedef typename value_alloc_type::const_reference reference;
+ typedef typename value_alloc_type::const_pointer pointer;
+
+ // Constructors
+ private:
+ explicit _Cuckoo_local_iterator(iterator __i) : _M_i(__i) { }
+
+ public:
+ _Cuckoo_local_iterator() { }
+
+ // Dereference
+ reference
+ operator*() const
+ { return *_M_i; }
+
+ pointer
+ operator->() const
+ { return &(operator*()); }
+
+ local_iterator&
+ operator++()
+ {
+ ++_M_i;
+ return *this;
+ }
+
+ local_iterator
+ operator++(int)
+ {
+ local_iterator __tmp(*this);
+ ++*this;
+ return __tmp;
+ }
+
+ // Comparison.
+ bool
+ operator==(const local_iterator& __it) const
+ { return _M_i == __it._M_i; }
+
+ bool
+ operator!=(const local_iterator& __it) const
+ { return _M_i != __it._M_i; }
+
+ private:
+ // Conversion of const_iterator to iterator. This is private because it is
+ // intended for internal use only.
+ _Cuckoo_local_iterator(const const_local_iterator& __it) : _M_i(__it._M_i)
+ { }
+
+ iterator _M_i;
+ };
+
+template<typename _Value, typename _Key, typename _Hasher,
+ typename _Extract_key, typename _Equal_key, typename _Alloc, int _S_z>
+ struct _Cuckoo_const_local_iterator
+ {
+ private:
+ typedef typename _Alloc::template rebind<_Value>::other value_alloc_type;
+ friend class _Cuckoo<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>;
+ friend class _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>;
+ friend class _Cuckoo_local_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>;
+
+ public:
+ typedef _Cuckoo_local_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ local_iterator;
+ typedef _Cuckoo_const_local_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ const_local_iterator;
+ typedef _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>
+ iterator;
+ typedef _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>
+ const_iterator;
+
+ typedef std::forward_iterator_tag iterator_category;
+ typedef _Value value_type;
+ typedef typename value_alloc_type::difference_type difference_type;
+ typedef typename value_alloc_type::size_type size_type;
+ typedef typename value_alloc_type::const_reference reference;
+ typedef typename value_alloc_type::const_pointer pointer;
+
+ private:
+ _Cuckoo_const_local_iterator(const iterator& __it) : _M_i(__it) { }
+
+ public:
+ _Cuckoo_const_local_iterator() { }
+
+ // This lets us convert regular local iterators to const local iterators
+ _Cuckoo_const_local_iterator(const local_iterator& __it) : _M_i(__it._M_i)
+ { }
+
+ reference
+ operator*() const
+ { return *_M_i; }
+
+ pointer
+ operator->() const
+ { return &(operator*()); }
+
+ const_local_iterator&
+ operator++()
+ {
+ ++_M_i;
+ return *this;
+ }
+
+ const_local_iterator
+ operator++(int)
+ {
+ const_local_iterator __tmp(*this);
+ ++*this;
+ return __tmp;
+ }
+
+ // Comparison.
+ bool
+ operator==(const const_local_iterator& __it) const
+ { return _M_i == __it._M_i; }
+
+ bool
+ operator!=(const const_local_iterator& __it) const
+ { return _M_i != __it._M_i; }
+
+ private:
+ const_iterator _M_i;
+ };
+
+template<class _Value, class _Key, class _Hasher,
+ class _Extract_key, class _Equal_key, class _Alloc, int _S_z>
+ class _Cuckoo
+ {
+ private:
+ enum
+ {
+ _S_random_hunt_max_iters = 10
+ };
+#ifndef NDEBUG
+ enum
+ {
+ _S_debug = true
+ };
+#else
+ enum
+ {
+ _S_debug = false
+ };
+#endif
+ enum
+ {
+ _S_easy = true,
+ _S_hard = false
+ };
+ enum
+ {
+ _S_copy = true,
+ _S_no_copy = false
+ };
+ enum
+ {
+ _S_delete = true,
+ _S_no_delete = false
+ };
+ enum
+ {
+ _S_advance = true,
+ _S_no_advance = false
+ };
+ enum
+ {
+ _S_did_insert = true,
+ _S_did_not_insert = false
+ };
+#if __cpp_exceptions
+ enum
+ {
+ _S_exceptions_enabled = true
+ };
+#else
+ enum
+ {
+ _S_exceptions_enabled = false
+ };
+#endif
+ enum
+ {
+ _S_hard_if_exceptions_enabled = _S_exceptions_enabled ? _S_hard : _S_easy
+ };
+
+ typedef typename _Alloc::template rebind<_Value>::other value_alloc_type;
+
+ public:
+ typedef _Key key_type;
+ typedef _Value value_type;
+ typedef _Hasher hasher;
+ typedef _Equal_key key_equal;
+ typedef _Alloc allocator_type;
+
+ typedef typename value_alloc_type::size_type size_type;
+ typedef typename value_alloc_type::difference_type difference_type;
+ typedef typename value_alloc_type::reference reference;
+ typedef typename value_alloc_type::const_reference const_reference;
+ typedef typename value_alloc_type::pointer pointer;
+ typedef typename value_alloc_type::const_pointer const_pointer;
+ typedef cuckoo_internal::_Bucket_number _Bucket_number;
+ typedef cuckoo_internal::_RNGState _RNGState;
+ typedef _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key, _Alloc, _S_z>
+ iterator;
+ typedef _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key, _Alloc,
+ _S_z> const_iterator;
+ typedef _Cuckoo_local_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key, _Alloc,
+ _S_z> local_iterator;
+ typedef _Cuckoo_const_local_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z> const_local_iterator;
+
+ private:
+ struct _Resize_request { }; // for "throw _Resize_request()"
+ typedef cuckoo_internal::_Permutation_iterator _Permutation_iterator;
+ typedef uintptr_t hint;
+ friend class _Cuckoo_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key, _Alloc,
+ _S_z>;
+ friend class _Cuckoo_const_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>;
+ friend class _Cuckoo_local_iterator<_Value, _Key, _Hasher, _Extract_key, _Equal_key,
+ _Alloc, _S_z>;
+ friend class _Cuckoo_const_local_iterator<_Value, _Key, _Hasher, _Extract_key,
+ _Equal_key, _Alloc, _S_z>;
+
+ // Helper to keep track of changes to _M_slots.
+ // Handy for implementing commit-or-rollback semantics.
+ struct _Rollback_state {
+ struct Record {
+ uintptr_t* ptr;
+ uintptr_t old_value;
+ };
+
+ // TODO: use allocator?
+ typedef std::vector<Record> Records;
+
+ void push_back(uintptr_t& u) { v_.push_back(Record{&u, u}); }
+ typename Records::size_type size() const { return v_.size(); }
+ Record& at(typename Records::size_type index) { return v_.at(index); }
+
+ Records v_;
+ std::vector<pointer> _M_vals_created;
+
+ template<typename _V> void _M_rollbackable_write(_V& ref, _V val) {
+ static_assert(sizeof(val) == sizeof(uintptr_t), "sizeof(val) assumption");
+ uintptr_t u;
+ memcpy(&u, &ref, sizeof(val));
+ v_.push_back(Record{reinterpret_cast<uintptr_t*>(&ref), u});
+ ref = val;
+ }
+
+ size_type _M_num_elements;
+ size_type _M_num_non_element_slots;
+ };
+
+ _Rollback_state* _M_get_rollback_state() {
+#if __cpp_exceptions
+ return _M_rollback_state;
+#else
+ return nullptr;
+#endif
+ }
+
+ void _M_clear_rollback_state() {
+#if __cpp_exceptions
+ _M_rollback_state = nullptr;
+#endif
+ }
+
+ template<typename _V> void _M_rollbackable_write(_V& ref, _V val) {
+ if (_M_get_rollback_state() != nullptr) {
+ _M_get_rollback_state()->_M_rollbackable_write(ref, val);
+ } else {
+ ref = val;
+ }
+ }
+
+ // Conceptually these are the key/value pairs for a map: g1 and g2
+ // are the "key" and the rest is the "value." See above for details.
+ struct _Extension
+ {
+ size_type g1;
+ size_type g2;
+ // To use i0 and i1 we need to create a _Permutation_iterator of a specific
+ // length; the length is determined by whether this is a first Extension
+ // for g1, g2, or a second, or a third, etc. The code traversing the chain
+ // keeps track, so we don't need to record that here.
+ _Bucket_number i0;
+ _Bucket_number i1;
+
+ bool Matches(size_type x1, size_type x2) const {
+ return x1 == g1 && x2 == g2;
+ }
+ };
+
+ // Extensions are linked into two separate linked lists. One is the
+ // list of all Extensions that we keep for bookkeeping purposes. The other is
+ // the list of Extensions for a particular bucket.
+ struct _Extension_list
+ {
+ _Extension_list* _M_next; // Bookkeeping list of all Extensions
+ _Extension_list* _M_next_in_chain; // Per-bucket list of Extensions
+ _Extension _M_extension;
+ };
+
+ struct _Slot
+ {
+ enum
+ {
+ _S_bitset_capacity = 7,
+ _S_max_bitset = (1 << _S_bitset_capacity) - 1,
+ _S_bits = _S_bitset_capacity + 3,
+ _S_width = sizeof(const_pointer) * 8, // Size of a pointer, in bits.
+ _S_top_mask = ((static_cast<uintptr_t>(1) << _S_bits) - 1) << (_S_width - _S_bits),
+ _S_bitset_mask = _S_top_mask << 3,
+ _S_ptr_mask = ~_S_top_mask,
+ // The next three masks are powers of two, i.e., all bits zero except one.
+ _S_contains_extension_list_mask = _S_top_mask ^ (_S_top_mask << 1),
+ _S_invalid_bitset_mask = _S_contains_extension_list_mask << 2,
+ // Which bits specify the type of pointer in the _Slot?
+ _S_pointer_type_mask = _S_contains_extension_list_mask
+ };
+
+ _Slot() : p_(0) { }
+
+ uintptr_t get_ptr_raw() const {
+#if defined(__x86_64__)
+ uintptr_t p = p_ << _S_bits;
+ asm("sar %1, %0"
+ : "+r"(p)
+ : "i"(_S_bits)
+ : "cc");
+ return p;
+#else
+ assert(0 && "not implemented");
+ return 0;
+#endif
+ }
+
+ const_pointer get_ptr() const {
+ assert(can_point_to_element());
+ return reinterpret_cast<const_pointer>(get_ptr_raw());
+ }
+
+ bool can_point_to_element() const { return (p_ & _S_pointer_type_mask) == 0; }
+ bool is_overfull() const { return !has_bitset(); }
+ bool contains_extension_list() const {
+ return (p_ & _S_contains_extension_list_mask) != 0;
+ }
+ bool has_bitset() const {
+ return (p_ & _S_invalid_bitset_mask) == 0;
+ }
+
+ hint get_bitset() const {
+ assert(has_bitset());
+ hint h = p_ >> (_S_width - _S_bitset_capacity);
+ return h;
+ }
+
+ void set_bitset(hint h) {
+ assert(has_bitset());
+ p_ <<= _S_bitset_capacity;
+ p_ |= h;
+ p_ = bitwise_right_rotate(p_, _S_bitset_capacity);
+ assert(get_bitset() == h);
+ }
+
+ void clear_bitset(bool easy, _Rollback_state* rs) {
+ assert(has_bitset());
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ p_ &= ~_S_bitset_mask;
+ assert(get_bitset() == 0);
+ }
+
+ void set_overfull(bool easy, _Rollback_state* rs) {
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ p_ |= _S_invalid_bitset_mask;
+ assert(is_overfull());
+ }
+
+ void xor_bitset(hint t, bool easy, _Rollback_state* rs) {
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ const hint old_bitset = get_bitset();
+ set_bitset(old_bitset ^ t);
+ assert(get_bitset() == old_bitset ^ t);
+ }
+
+ bool is_ptr_null() const {
+ bool result = (p_ & _S_ptr_mask) == 0;
+ assert(result == (get_ptr_raw() == 0));
+ return result;
+ }
+
+ bool is_available() const {
+ bool result = (p_ & (_S_ptr_mask | _S_pointer_type_mask)) == 0;
+ assert(result == (is_ptr_null() && can_point_to_element()));
+ return result;
+ }
+
+ bool has_element() const {
+ return can_point_to_element() && !is_ptr_null();
+ }
+
+ bool has_no_element() const {
+ return !has_element();
+ }
+
+ void set_ptr_that_was_null(const_pointer p, bool easy, _Rollback_state* rs) {
+ assert(get_ptr() == nullptr);
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ p_ |= reinterpret_cast<uintptr_t>(p) & _S_ptr_mask;
+ assert(get_ptr() == p);
+ }
+
+ void set_ptr_and_bitset(const_pointer p, hint bitset, bool easy,
+ _Rollback_state* rs) {
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ p_ = (reinterpret_cast<uintptr_t>(p) & _S_ptr_mask) |
+ (bitset << (_S_width - _S_bitset_capacity));
+ assert(get_bitset() == bitset && get_ptr() == p);
+ }
+
+ void set_ptr_and_mark_as_extension_list(_Extension_list* p, bool easy,
+ _Rollback_state* rs) {
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ p_ &= ~_S_ptr_mask;
+ p_ |= (reinterpret_cast<uintptr_t>(p) & _S_ptr_mask) |
+ _S_contains_extension_list_mask;
+ assert(get_extension_listptr() == p && !can_point_to_element());
+ }
+
+ void set_ptr_to_null(bool easy, _Rollback_state* rs) {
+ if (!easy) {
+ rs->push_back(p_);
+ }
+ p_ &= ~_S_ptr_mask;
+ assert(get_ptr() == nullptr);
+ }
+
+ _Extension_list* get_extension_listptr() const {
+ return reinterpret_cast<_Extension_list*>(get_ptr_raw());
+ }
+
+ private:
+ static uintptr_t bitwise_right_rotate(uintptr_t val, unsigned int shift) {
+ const int kNumBits = 8 * sizeof(val);
+ return (val >> shift) | (val << (kNumBits - shift));
+ }
+
+ uintptr_t p_;
+ };
+
+ // Utilities for singly-linked lists.
+ template<typename _V>
+ inline void
+ PopListUntilHeadIs(_V* __h, _V** __pointer_to_list)
+ {
+ while (*__pointer_to_list != __h)
+ {
+ auto __next = (*__pointer_to_list)->_M_next;
+ delete *__pointer_to_list;
+ *__pointer_to_list = __next;
+ }
+ }
+
+ template<typename _V>
+ inline void
+ PopAll(_V** __pointer_to_list)
+ { PopListUntilHeadIs(static_cast<_V*>(nullptr), __pointer_to_list); }
+
+ public:
+ // How full we let the table get before we resize, by default.
+ enum { _S_default_max_occupancy_percent = 60 };
+
+ // How empty we let the table get before we resize lower, by default.
+ // (0 means never resize lower.)
+ // It should be less than half of the corresponding upper bound, or
+ // we risk doing a lot of doubling/halving the table size for no good reason.
+ enum { _S_default_consider_shrink_occupancy =
+ _S_default_max_occupancy_percent * 2 / 5 };
+
+ // Minimum size we're willing to let hashtables be. Must be a power of two,
+ // and at least max(_S_z, _Slots::_S_bitset_capacity). Note, however, that for a
+ // given hashtable, the initial size is a function of the first constructor
+ // arg, and may be larger than _S_min_buckets.
+ static const size_type _S_min_buckets =
+ cuckoo_internal::SmallestPowerOfTwoNotLessThan<
+ cuckoo_internal::_Max<_S_z, _Slot::_S_bitset_capacity>::_S_value>::_S_value;
+
+ // By default, if you don't specify a hashtable size at
+ // construction-time, we use this size. Must be a power of two, and
+ // at least _S_min_buckets.
+ static const size_type _S_default_starting_buckets
+ = cuckoo_internal::_Max<32, _S_min_buckets>::_S_value;
+
+ // ITERATOR FUNCTIONS
+ // TODO: should we keep track of what begin() would return, so we don't have
+ // to iterate when begin() is invoked? It seems unhelpful on balance, but may
+ // be required by the C++ standard.
+ iterator begin() noexcept { return iterator(this, 0, _S_advance); }
+ iterator end() noexcept { return iterator(); }
+ const_iterator begin() const noexcept {
+ return const_iterator(this, 0, _S_advance);
+ }
+ const_iterator end() const noexcept { return const_iterator(); }
+ const_iterator cbegin() const noexcept { return begin(); }
+ const_iterator cend() const noexcept { return end(); }
+
+ // LOCAL ITERATORS / BUCKET INTERFACE
+ size_type bucket_size(size_type b) const noexcept {
+ return b == 0 ? size() : 0;
+ }
+ local_iterator begin(size_type b) noexcept {
+ return local_iterator(b == 0 ? begin() : end());
+ }
+ local_iterator end(size_type b) noexcept { return local_iterator(end()); }
+ const_local_iterator begin(size_type b) const noexcept {
+ return const_local_iterator(b == 0 ? begin() : end());
+ }
+ const_local_iterator end(size_type b) const noexcept { return const_local_iterator(end()); }
+ const_local_iterator cbegin(size_type n) const noexcept { return begin(n); }
+ const_local_iterator cend(size_type n) const noexcept { return end(n); }
+
+ // ACCESSOR FUNCTIONS for the things we templatize on, basically
+ hasher hash_function() const { return _M_settings; }
+ key_equal key_eq() const { return _M_key_info; }
+ allocator_type get_allocator() const { return allocator_type(_M_value_alloc); }
+
+ // Accessor function for statistics gathering.
+ int num_table_copies() const { return _M_settings._M_num_copies(); }
+
+ // FUNCTIONS CONCERNING SIZE
+ size_type size() const { return _M_num_elements; };
+ bool empty() const { return size() == 0; }
+ size_type bucket_count() const { return _M_num_buckets; }
+ size_type max_bucket_count() const { return max_size(); }
+ size_type max_size() const {
+ return std::min<size_type>(_M_value_alloc.max_size(),
+ std::numeric_limits<size_type>::max() / 8);
+ }
+
+ bool allow_rebucketing(bool new_state) {
+ std::swap(new_state, _M_allow_rebucketing);
+ return new_state;
+ }
+ bool allow_shrinking(bool new_state) {
+ std::swap(new_state, _M_allow_shrinking);
+ return new_state;
+ }
+
+ private:
+ enum { _S_impossible_bucket = ~(_Bucket_number)0 };
+
+ size_type _M_random_odd_number() const {
+ return _M_rng_state->_M_get_random_odd_number();
+ }
+ // In non-const context, create the RNG if need be.
+ size_type _M_random_odd_number() {
+ initialize_rng();
+ return _M_rng_state->_M_get_random_odd_number();
+ }
+
+ // "Make it big enough for delta more elements." Also, check if we've hit
+ // _M_work_threshold. If the table size is fine already then this does nothing.
+ // Returns whether a resize did occur.
+ bool _M_resize_delta(size_type delta) {
+ assert(bucket_count() >= _S_min_buckets);
+ if (!_M_allow_rebucketing) {
+ _M_work_since_last_rebuild =
+ std::min(_M_work_threshold, _M_work_since_last_rebuild);
+ return false;
+ }
+ if (_M_num_elements >=
+ (std::numeric_limits<size_type>::max)() - delta) {
+#if __cpp_exceptions
+ throw std::length_error("resize overflow");
+#else
+ assert(0 && "resize overflow");
+#endif
+ }
+
+ size_type min_size_to_consider = _S_min_buckets;
+ // Sometimes, we want to resize just to reduce the probability that
+ // a long sequence of inserts and erases has led to inopportune
+ // clustering of elements in the table. That's tracked by _M_work_threshold.
+ if (_M_work_since_last_rebuild < _M_work_threshold) {
+ if (_M_slots_in_use() + delta <= _M_settings._M_enlarge_threshold) {
+ return false;
+ } else {
+ // We passed the enlarge threshold. Doubling is probably a good idea.
+ min_size_to_consider = bucket_count() * 2;
+ }
+ }
+
+ if (!_M_allow_shrinking) {
+ min_size_to_consider = bucket_count();
+ }
+ size_type resize_to =
+ _M_settings.min_buckets(_M_num_elements + delta, min_size_to_consider);
+
+ force_resize(resize_to);
+ return true;
+ }
+
+ void force_resize(size_type resize_to) {
+ for (;;) {
+ __try {
+ _Cuckoo tmp(*this, resize_to);
+ swap(tmp);
+ return;
+ } __catch (_Resize_request&) {
+ lower_max_load_factor();
+ }
+ }
+ }
+
+ // According to the C++ standard, a load factor is just a suggestion, and
+ // the data structure is allowed to do whatever it likes. So, in certain
+ // unusual cases we unilaterally target a lower load factor.
+ float lower_max_load_factor() {
+ const float default_mlf = _S_default_max_occupancy_percent / 100.0f;
+ float mlf = _M_settings._M_enlarge_factor;
+ mlf = .97f * mlf + .03f * default_mlf;
+ set_resizing_parameters(_M_settings._M_shrink_factor, mlf);
+ _M_settings._M_reset_thresholds(bucket_count());
+ return mlf;
+ }
+
+
+ // Used to actually do the rehashing when we grow/shrink a hashtable.
+ // No new _Values are allocated; the existing ones are reused.
+ void move_from(_Cuckoo &ht, size_type min_buckets_wanted) {
+ clear_to_size(_M_settings.min_buckets(ht.size(), min_buckets_wanted),
+ ht._M_rng_state);
+ size_type num_buckets = bucket_count();
+ {
+ _Disallow_shrink_holder __dsh(&_M_allow_shrinking);
+ for (const_iterator it = ht.begin(); it != ht.end(); ++it) {
+ _M_insert_unique(*it, _S_easy);
+ assert(bucket_count() == num_buckets);
+ }
+ }
+ _Slot* start = ht._M_slots;
+ _Slot* end = start + ht._M_num_buckets;
+ memset(start, 0, (end - start) * sizeof(*start));
+ ht._M_num_elements = 0;
+ ht._M_num_non_element_slots = 0;
+ _M_settings._M_increment_num_copies();
+ }
+
+ void copy_from(const _Cuckoo &ht, size_type min_buckets_wanted) {
+ clear_to_size(_M_settings.min_buckets(ht.size(), min_buckets_wanted),
+ ht._M_rng_state);
+ size_type num_buckets = bucket_count();
+ {
+ _Disallow_shrink_holder __dsh(&_M_allow_shrinking);
+ for (const_iterator it = ht.begin(); it != ht.end(); ++it) {
+ _M_insert_unique(*new_value(*it, _S_easy), _S_easy);
+ assert(bucket_count() >= num_buckets);
+ }
+ }
+ _M_settings._M_increment_num_copies();
+ assert(size() == ht.size());
+ }
+
+ public:
+ // CONSTRUCTORS -- as required by the specs, we take a size,
+ // but also let you specify a hash function, key comparator,
+ // and key extractor. We also define a copy constructor and =.
+ // DESTRUCTOR -- needs to free the table
+ explicit _Cuckoo(size_type expected_max_items_in_table = 0,
+ const _Hasher& hf = _Hasher(), const _Equal_key& eql = _Equal_key(),
+ const _Extract_key& ext = _Extract_key(),
+ const _Alloc& alloc = _Alloc())
+ : _M_slots(nullptr),
+ _M_settings(hf),
+ _M_key_info(ext, eql),
+ _M_num_elements(0),
+ _M_num_non_element_slots(0),
+ _M_num_buckets(
+ expected_max_items_in_table == 0
+ ? _S_default_starting_buckets
+ : _M_settings.min_buckets(expected_max_items_in_table, 0)),
+ _M_value_alloc(alloc),
+ _M_allow_shrinking(true),
+ _M_allow_rebucketing(true),
+ _M_rng_state(nullptr) {
+ _M_clear_rollback_state();
+ clear_to_size(bucket_count());
+ }
+
+ _Cuckoo(const _Cuckoo& ht) : _Cuckoo() { *this = ht; }
+
+ explicit _Cuckoo(const _Alloc& alloc)
+ : _Cuckoo(0, _Hasher(), _Equal_key(), _Extract_key(), alloc)
+ { }
+
+ _Cuckoo(const _Cuckoo& ht, const _Alloc& alloc) : _Cuckoo(alloc) { *this = ht; }
+
+ // Move the elements to a new table. This is used by table resizing and
+ // the move constructor.
+ _Cuckoo(_Cuckoo& ht, size_type min_buckets_wanted = _S_default_starting_buckets)
+ : _M_slots(nullptr),
+ _M_settings(ht._M_settings),
+ _M_key_info(ht._M_key_info),
+ _M_num_elements(0),
+ _M_num_non_element_slots(0),
+ _M_num_buckets(0),
+ _M_value_alloc(ht._M_value_alloc),
+ _M_allow_shrinking(true),
+ _M_allow_rebucketing(true),
+ _M_rng_state(nullptr)
+ {
+ _M_clear_rollback_state();
+ __try
+ {
+ move_from(ht, min_buckets_wanted);
+ }
+ __catch (...)
+ {
+ cleanup(_S_no_delete);
+ __throw_exception_again;
+ }
+ }
+
+ _Cuckoo(_Cuckoo&& ht) : _Cuckoo(ht, ht.bucket_count()) { }
+
+ _Cuckoo&
+ operator=(const _Cuckoo& ht)
+ {
+ if (&ht == this) return *this; // Don't copy onto ourselves.
+ cleanup(_S_delete);
+ _M_slots = nullptr;
+ _M_settings = ht._M_settings;
+ _M_key_info = ht._M_key_info;
+ _M_num_elements = 0;
+ _M_num_non_element_slots = 0;
+ _M_work_since_last_rebuild = 0;
+ _M_work_threshold = 0;
+ assert(_M_get_rollback_state() == nullptr);
+ _M_extension_list = nullptr;
+ // TODO: copy the allocator if need be
+ _M_allow_shrinking = ht._M_allow_shrinking;
+ _M_allow_rebucketing = ht._M_allow_rebucketing;
+ _M_rng_state = nullptr;
+ copy_from(ht, _S_min_buckets);
+ return *this;
+ }
+
+ _Cuckoo&
+ operator=(std::initializer_list<value_type> il)
+ {
+ clear();
+ insert(il);
+ return *this;
+ }
+
+ ~_Cuckoo() { cleanup(_S_delete); }
+
+ private:
+ size_type
+ _M_slots_in_use() const
+ { return _M_num_elements + _M_num_non_element_slots; }
+
+ // This is intended for debug-mode sanity checks only.
+ size_type
+ count_non_element_slots() const
+ {
+ size_type __count = 0;
+ for (size_type __i = 0; __i < _M_num_buckets; __i++) {
+ if (_M_slots[__i].contains_extension_list()) {
+ assert(_M_slots[__i].get_extension_listptr() != nullptr);
+ ++__count;
+ }
+ }
+ return __count;
+ }
+
+ void cleanup(bool del) {
+ assert(_M_slots != nullptr);
+ //TODO: use allocator to delete _Values
+ //TODO: use allocator to delete _M_slots etc.
+ if (del) {
+ for (const_reference r : *this) {
+ _M_delete_value(r);
+ }
+ }
+ assert(_M_num_non_element_slots == count_non_element_slots());
+ delete[] _M_slots;
+ destroy_bookkeeping_data();
+ delete _M_rng_state;
+ }
+
+ public:
+ void swap(_Cuckoo& ht) noexcept {
+ if (this == &ht) return;
+ assert(_M_get_rollback_state() == nullptr);
+ assert(ht._M_get_rollback_state() == nullptr);
+ std::swap(_M_slots, ht._M_slots);
+ std::swap(_M_settings, ht._M_settings);
+ std::swap(_M_key_info, ht._M_key_info);
+ std::swap(_M_num_elements, ht._M_num_elements);
+ std::swap(_M_num_non_element_slots, ht._M_num_non_element_slots);
+ std::swap(_M_num_buckets, ht._M_num_buckets);
+ std::swap(_M_work_since_last_rebuild, ht._M_work_since_last_rebuild);
+ std::swap(_M_work_threshold, ht._M_work_threshold);
+ std::swap(_M_extension_list, ht._M_extension_list);
+ std::swap(_M_rng_state, ht._M_rng_state);
+ _M_settings._M_reset_thresholds(bucket_count());
+ ht._M_settings._M_reset_thresholds(ht.bucket_count());
+ // TODO: swap allocator if need be
+ }
+
+ // If hint > _M_num_buckets then force a resize, even if
+ // _M_allow_rebucketing is false.
+ void rehash(size_type hint) {
+ hint = std::min(hint, max_size());
+ if (hint <= _M_num_buckets) return;
+ size_type n = _M_num_buckets;
+ do {
+ n *= 2;
+ } while (n < hint);
+ force_resize(n);
+ }
+
+ void reserve(size_type hint) { rehash(ceil(hint / max_load_factor())); }
+
+ // Get and change the value of shrink_factor and enlarge_factor. The
+ // description at the beginning of this file explains how to choose
+ // the values. Setting the shrink parameter to 0.0 ensures that the
+ // table never shrinks.
+ void get_resizing_parameters(float* shrink, float* grow) const {
+ *shrink = _M_settings._M_shrink_factor;
+ *grow = _M_settings._M_enlarge_factor;
+ }
+ void set_resizing_parameters(float shrink, float grow) {
+ _M_settings.set_resizing_parameters(shrink, grow);
+ _M_settings._M_reset_thresholds(bucket_count());
+ }
+
+ /// Returns the average number of elements per bucket.
+ float
+ load_factor() const noexcept
+ { return size() * 1.0f / bucket_count(); }
+
+ /// Returns a positive number that the %_CuckooS tries to keep the
+ /// load factor less than or equal to.
+ float
+ max_load_factor() const noexcept
+ {
+ float shrink, grow;
+ get_resizing_parameters(&shrink, &grow);
+ return grow;
+ }
+
+ /**
+ * @brief Change the %_CuckooS maximum load factor.
+ * @param __z The new maximum load factor.
+ */
+ void
+ max_load_factor(float __z)
+ {
+ float shrink, grow;
+ get_resizing_parameters(&shrink, &grow);
+ set_resizing_parameters(shrink, __z);
+ }
+
+ void set_random_seed(const std::seed_seq& s) {
+ assert(empty());
+ if (_M_extension_list != nullptr) {
+ clear();
+ }
+ assert(_M_extension_list == nullptr);
+ if (_M_rng_state == nullptr) {
+ _M_rng_state = new _RNGState(s);
+ } else {
+ _M_rng_state->_M_reset(s);
+ }
+ }
+
+ private:
+ // There are 2 states:
+ // 1. we have not yet used a RNG, and we have no seed
+ // 2. we have a RNG
+ // Sometimes no seed is given so we need to come up with a seed
+ // somehow. This is done via std::random_device. Unfortunately,
+ // that can throw an exception. However, std::random_device is
+ // avoided if either this table is derived from one that already has
+ // an RNG or set_random_seed() was invoked.
+ void initialize_rng(_RNGState* r = nullptr) {
+ if (_M_rng_state != nullptr) return;
+ if (r != nullptr) {
+ _M_rng_state = new _RNGState(*r);
+ } else {
+ std::random_device rd;
+ _M_rng_state = new _RNGState(std::seed_seq{rd(), rd()});
+ }
+ }
+
+ size_type _M_rand_at_most(size_type max) {
+ initialize_rng();
+ return _M_rng_state->_M_rand_at_most(max);
+ }
+
+ void clear_to_size(size_type new_num_buckets, _RNGState* r = nullptr) {
+ init_bookkeeping_data();
+ assert(_M_slots == nullptr);
+ _M_num_buckets = new_num_buckets;
+ _M_slots = new _Slot[_M_num_buckets];
+ _M_num_elements = 0;
+ clear_with_existing_slots(false);
+ initialize_rng(r);
+ }
+
+ void clear_with_existing_slots(bool resize_to_minimum) {
+ assert(_M_slots != nullptr);
+ if (_M_num_elements > 0) {
+ for (const_reference r : *this) {
+ _M_delete_value(r);
+ }
+ _M_num_elements = 0;
+ }
+ destroy_bookkeeping_data();
+ if (_M_allow_shrinking && _M_allow_rebucketing && resize_to_minimum &&
+ _M_num_buckets != _S_min_buckets) {
+ delete[] _M_slots;
+ _M_num_buckets = _S_min_buckets;
+ _M_slots = new _Slot[_M_num_buckets];
+ }
+ fill_range_with_empty(_M_slots, _M_slots + _M_num_buckets);
+ _M_work_since_last_rebuild = 0;
+ _M_work_threshold = 5 * _M_num_buckets; // why 5?
+ _M_settings._M_reset_thresholds(bucket_count());
+ }
+
+ void fill_range_with_empty(_Slot* start, _Slot* end) {
+ memset(start, 0, (end - start) * sizeof(*start));
+ }
+
+ public:
+ void clear() {
+ clear_with_existing_slots(true);
+ }
+
+ void clear_no_resize() {
+ clear_with_existing_slots(false);
+ }
+
+ // LOOKUP ROUTINES
+ iterator find(const key_type& key) {
+ const_iterator it = const_cast<const _Cuckoo*>(this)->find(key);
+ return iterator(it);
+ }
+
+ const_iterator find(const key_type& __key) const {
+ _Find_result __fr = _M_find_if_present(__key);
+ return __fr._M_found ? const_iterator(this, __fr._M_b, _S_no_advance) : cend();
+ }
+
+ size_type bucket(const key_type&) const { return 0; }
+
+ // Counts how many elements match the given key: 0 or 1.
+ size_type count(const key_type &key) const {
+ return _M_find_if_present(key)._M_found ? 1 : 0;
+ }
+
+ std::pair<iterator, iterator> equal_range(const key_type& key) {
+ iterator pos = find(key);
+ if (pos == end()) {
+ return std::pair<iterator, iterator>(pos, pos);
+ } else {
+ const iterator startpos = pos++;
+ return std::pair<iterator, iterator>(startpos, pos);
+ }
+ }
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& key)
+ const {
+ const_iterator pos = find(key);
+ if (pos == end()) {
+ return std::pair<const_iterator, const_iterator>(pos, pos);
+ } else {
+ const const_iterator startpos = pos++;
+ return std::pair<const_iterator, const_iterator>(startpos, pos);
+ }
+ }
+
+ private:
+ // This struct is used only as the return type of _M_find_if_present().
+ struct _Find_result {
+ // If the key was found then:
+ // found is true, b is the bucket where it was found, and bitset is 0.
+ // Otherwise:
+ // found is false, b is the preferred bucket for the key, and bitset is the
+ // bitset for that bucket, or -1 if it's overfull.
+ static _Find_result _S_found(size_type __g0, _Bucket_number __b) {
+ return {__g0, __b, 0, true};
+ }
+ static _Find_result _S_not_found(size_type __g0, _Bucket_number __b, int __bitset) {
+ return {__g0, __b, __bitset, false};
+ }
+ static _Find_result _S_not_found_overfull(size_type __g0, _Bucket_number __b) {
+ return {__g0, __b, -1, false};
+ }
+
+ size_type _M_g0;
+ _Bucket_number _M_b;
+ int _M_bitset;
+ bool _M_found;
+ };
+
+ _Find_result _M_find_if_present(const key_type& key) const {
+ const size_type g0 = _M_hash0(key);
+ const _Bucket_number b = _M_mod_bucket_count(g0);
+ if (_M_slots[b].has_bitset()) {
+ // Common case. We have a bitset telling us where to look.
+ const int bitset = _M_slots[b].get_bitset();
+ for (int lg_t = 0, t = 1; t <= bitset; lg_t++, t *= 2) {
+ if ((bitset & t) != 0) {
+ const _Bucket_number q = b ^ lg_t;
+ if (!_M_slots[q].is_ptr_null()
+ && _M_equals(key, get_key(*_M_slots[q].get_ptr()))) {
+ // Found a match.
+ return _Find_result::_S_found(g0, q);
+ }
+ }
+ }
+ return _Find_result::_S_not_found(g0, b, bitset);
+ } else {
+ // Bucket b is overfull.
+ // Possible nests for obj include, for example, for _S_z=4,
+ // h1, h1 ^ 1, h1 ^ 2, h1 ^ 3, h2, h2 ^ 1, h2 ^ 2, and h2 ^ 3.
+ const size_type g1 = _M_hash1(key, g0);
+ const _Bucket_number h1 = _M_mod_bucket_count(g1);
+ for (_Bucket_number i = 0; i < _S_z; i++) {
+ const _Bucket_number q = h1 ^ i;
+ if (_M_slots[q].has_element()
+ && _M_equals(key, get_key(*_M_slots[q].get_ptr()))) {
+ return _Find_result::_S_found(g0, q);
+ }
+ }
+ const size_type g2 = _M_hash2(key, g0);
+ const _Bucket_number h2 = _M_mod_bucket_count(g2);
+ for (_Bucket_number i = 0; i < _S_z; i++) {
+ const _Bucket_number q = h2 ^ i;
+ if (_M_slots[q].has_element()
+ && _M_equals(key, get_key(*_M_slots[q].get_ptr()))) {
+ return _Find_result::_S_found(g0, q);
+ }
+ }
+ // Check Extensions, if any.
+ auto p = extensions_if_any(g1, g2);
+ if (p.found_any) { // There's at least one relevant extension.
+ const _Extension_list* el = p.el;
+ const _Extension* e = &el->_M_extension;
+ // The first one is a special case: only e->i0 is used.
+ assert(e->Matches(g1, g2));
+ const _Bucket_number q = e->i0;
+ if (_M_slots[q].has_element()
+ && _M_equals(key, get_key(*_M_slots[q].get_ptr()))) {
+ return _Find_result::_S_found(g0, q);
+ }
+ // Search subsequent extensions, if any.
+ size_type num_to_search_per_extension = 2;
+ while ((el = el->_M_next_in_chain) != nullptr) {
+ e = &el->_M_extension;
+ if (!e->Matches(g1, g2)) break;
+ _Permutation_iterator pi(e->i0, e->i1, _M_num_buckets,
+ num_to_search_per_extension);
+ do {
+ const _Bucket_number q = pi._M_next();
+ if (_M_slots[q].has_element()
+ && _M_equals(key, get_key(*_M_slots[q].get_ptr()))) {
+ return _Find_result::_S_found(g0, q);
+ }
+ } while (!pi._M_done());
+ num_to_search_per_extension *= 2;
+ }
+ }
+ // Done searching all possible nests.
+ return _Find_result::_S_not_found_overfull(g0, b);
+ }
+ }
+
+ // INSERTION ROUTINES
+
+ // Use new. TODO: Fix.
+ pointer new_value(const_reference obj, bool easy) {
+ // Make space in _M_get_rollback_state() first, because we only want to
+ // copy obj if that succeeds.
+ pointer* p = _M_extend_rollback_statefor_new_values();
+ pointer result = new _Value(obj);
+ if (_S_exceptions_enabled && !easy) {
+ *p = result;
+ }
+ return result;
+ }
+ void _M_delete_value(const_reference obj) {
+ delete &obj;
+ }
+
+ // The basic find-or-insert method. Requires _M_get_rollback_state() == nullptr.
+ template<typename _V>
+ std::pair<iterator, bool>
+ _M_find_or_insert(_V&& __t, bool __copy)
+ {
+ assert(_M_get_rollback_state() == nullptr);
+ _Find_result __fr = _M_find_if_present(get_key(__t));
+ if (__fr._M_found)
+ {
+ return std::make_pair(_M_iter_at(__fr._M_b), _S_did_not_insert);
+ }
+ const size_type __g0 = __fr._M_g0;
+ const _Bucket_number __b = __fr._M_b;
+ const int __bitset = __fr._M_bitset;
+ const_pointer __p = &__t;
+ if (__copy)
+ {
+ __p = new value_type(std::forward<_V>(__t));
+ }
+ __try
+ {
+ return __bitset >= 0
+ ? _M_insert_unique_with_bitset(*__p, __g0, __b, __bitset, _S_easy)
+ : _M_cuckoo_insert_unique(*__p, __g0, __b, _S_easy);
+ }
+ __catch (...)
+ {
+ if (__copy)
+ {
+ _M_delete_value(*__p);
+ }
+ __throw_exception_again;
+ }
+ }
+
+ // Returns true if it did resize, false otherwise.
+ // Can throw...
+ bool bump_work_count_and_maybe_resize(bool easy) {
+ ++_M_work_since_last_rebuild;
+ if (_M_work_since_last_rebuild >= _M_work_threshold) {
+ if (!_M_allow_rebucketing) {
+ _M_work_since_last_rebuild = _M_work_threshold;
+ return false;
+ }
+ if (easy) {
+ bool did_resize = _M_resize_delta(0);
+ assert(did_resize);
+ assert(_M_get_rollback_state() == nullptr);
+ return true;
+ } else {
+ cuckoo_internal::ThrowException<_Resize_request>();
+ }
+ }
+ return false;
+ }
+
+ std::pair<iterator, bool>
+ _M_insert_unique_with_bitset(const_reference obj,
+ size_type g0,
+ _Bucket_number b,
+ int bitset,
+ bool easy) {
+ if (bump_work_count_and_maybe_resize(easy)) {
+ return _M_insert_unique(obj, _S_easy);
+ }
+ for (int lg_t = 0, t = 1; t <= _Slot::_S_max_bitset; lg_t++, t *= 2) {
+ if ((bitset & t) == 0) {
+ const _Bucket_number q = b ^ lg_t;
+ if (_M_slots[q].is_ptr_null()) {
+ if (lg_t == 0) {
+ assert(q == b);
+ _M_slots[q].set_ptr_and_bitset(&obj, bitset | t,
+ easy, _M_get_rollback_state());
+ } else {
+ _M_slots[q].set_ptr_that_was_null(&obj, easy,
+ _M_get_rollback_state());
+ _M_slots[b].xor_bitset(t, easy, _M_get_rollback_state());
+ }
+ _M_increment_num_elements();
+ return std::make_pair(_M_iter_at(q), _S_did_insert);
+ }
+ }
+ }
+ // No good spot is available. We either need to bump something else to
+ // make space, or convert bucket b to overfull. Currently we take the
+ // simplest path: make bucket b overfull, though this policy is not
+ // necessarily optimal.
+ return _M_convert_bucket_to_overfull_and_insert_unique(obj, g0,
+ b, bitset);
+ }
+
+ // This is equivalent to _M_find_or_insert(), above, except that it requires
+ // that the thing we're inserting isn't already present.
+ // Requires count(get_key(obj)) == 0.
+ std::pair<iterator, bool>
+ _M_insert_unique(const_reference __obj, bool __easy)
+ {
+ const size_type __g0 = _M_hash0(get_key(__obj));
+ const _Bucket_number __b = _M_mod_bucket_count(__g0);
+ return _M_slots[__b].has_bitset()
+ ? _M_insert_unique_with_bitset(__obj, __g0, __b, _M_slots[__b].get_bitset(),
+ __easy)
+ : _M_cuckoo_insert_unique(__obj, __g0, __b, __easy);
+ }
+
+ void
+ _M_increment_num_elements()
+ {
+ ++_M_num_elements;
+ if (_M_num_elements >= _M_settings._M_enlarge_threshold)
+ {
+ // Bump up _M_work_since_last_rebuild to force a resize soon.
+ _M_work_since_last_rebuild = _M_work_threshold;
+ }
+ }
+
+ void
+ _M_decrement_num_elements()
+ {
+ --_M_num_elements;
+ if (_M_num_elements < _M_settings._M_shrink_threshold && _M_allow_shrinking)
+ {
+ // Bump up _M_work_since_last_rebuild to force a resize soon.
+ _M_work_since_last_rebuild = _M_work_threshold;
+ }
+ }
+
+ class _Disallow_shrink_holder
+ {
+ public:
+ explicit _Disallow_shrink_holder(bool* __p)
+ : _M_allow_shrinking_ptr(__p), _M_val(*__p)
+ { *__p = false; }
+
+ ~_Disallow_shrink_holder() { *_M_allow_shrinking_ptr = _M_val; }
+
+ private:
+ bool* const _M_allow_shrinking_ptr;
+ const bool _M_val;
+ };
+
+ class _Disallow_rebucket_holder {
+ public:
+ explicit _Disallow_rebucket_holder(bool* __p)
+ : _M_allow_rebucketing_ptr(__p), _M_val(*__p)
+ { *__p = false; }
+
+ ~_Disallow_rebucket_holder() { *_M_allow_rebucketing_ptr = _M_val; }
+
+ private:
+ bool* const _M_allow_rebucketing_ptr;
+ const bool _M_val;
+ };
+
+ std::pair<iterator, bool>
+ _M_convert_bucket_to_overfull_and_insert_unique(const_reference __obj,
+ size_type __g0,
+ _Bucket_number __b,
+ int __bitset)
+ {
+ assert(_M_slots[__b].get_bitset() == __bitset);
+ // The next two locals track the items we've temporarily removed.
+ size_type __bumped_count = 0;
+ const_pointer __bumped_items[_Slot::_S_bitset_capacity];
+ _Rollback_state __rs;
+ if (_S_exceptions_enabled && _M_get_rollback_state() == nullptr)
+ {
+ init_rollback_state(&__rs);
+ }
+ __try
+ {
+ _Disallow_shrink_holder dsh(&_M_allow_shrinking);
+ for (int __lg_t = 0, __t = 1; __t <= __bitset; __lg_t++, __t *= 2) {
+ if ((__bitset & __t) != 0) {
+ __bumped_items[__bumped_count++] = _M_slots[__b ^ __lg_t].get_ptr();
+ _M_slots[__b ^ __lg_t].set_ptr_to_null(_S_hard_if_exceptions_enabled,
+ _M_get_rollback_state());
+ }
+ }
+ _M_slots[__b].clear_bitset(_S_hard_if_exceptions_enabled,
+ _M_get_rollback_state());
+ _M_num_elements -= __bumped_count;
+ const auto __old_version = _M_settings._M_num_copies();
+ _M_slots[__b].set_overfull(_S_hard_if_exceptions_enabled,
+ _M_get_rollback_state());
+ while (__bumped_count != 0) {
+ const_reference __bumped_obj = *__bumped_items[--__bumped_count];
+ size_type __g0 = _M_hash0(get_key(__bumped_obj));
+ assert(__b == _S_impossible_bucket
+ || __b == _M_mod_bucket_count(__g0));
+ _M_likely__M_cuckoo_insert_unique(__bumped_obj, __g0, __b,
+ _S_hard_if_exceptions_enabled);
+ auto __version = _M_settings._M_num_copies();
+ __b = __version == __old_version ? __b : _S_impossible_bucket;
+ }
+ auto __result =
+ _M_likely__M_cuckoo_insert_unique(__obj,
+ __g0,
+ __b,
+ _S_hard_if_exceptions_enabled);
+ if (_S_exceptions_enabled && _M_get_rollback_state() == &__rs)
+ {
+ _M_clear_rollback_state();
+ }
+ return __result;
+ }
+ __catch (...)
+ {
+ _M_rollback();
+ __throw_exception_again;
+ }
+ }
+
+ void init_bookkeeping_data() {
+ _M_num_non_element_slots = 0;
+ _M_extension_list = nullptr;
+ }
+
+ void destroy_bookkeeping_data() {
+ PopAll(&_M_extension_list);
+ _M_num_non_element_slots = 0;
+ }
+
+ void init_rollback_state(_Rollback_state *rs) {
+ assert(_S_exceptions_enabled);
+#if __cpp_exceptions
+ assert(_M_get_rollback_state() == nullptr);
+ _M_rollback_state = rs;
+ rs->_M_num_elements = _M_num_elements;
+ rs->_M_num_non_element_slots = _M_num_non_element_slots;
+#endif
+ }
+
+ // Using cuckoo-style insertion, add __obj (or a copy of it) to the table.
+ // Unless __b == _S_impossible_bucket, in which case this routine is equivalent
+ // to _M_insert_unique().
+ // Requires count(get_key(__obj)) == 0 and either
+ // __b == _S_impossible_bucket or __b == _M_preferred_bucket(__obj).
+ std::pair<iterator, bool>
+ _M_likely__M_cuckoo_insert_unique(const_reference __obj,
+ size_type __g0,
+ _Bucket_number __b,
+ bool __easy)
+ {
+ return (__b == _S_impossible_bucket) ? _M_insert_unique(__obj, __easy)
+ : _M_cuckoo_insert_unique(__obj, __g0, __b, __easy);
+ }
+
+ // Using cuckoo-style insertion, add obj to the table.
+ // Requires count(get_key(obj)) == 0.
+ // Requires _M_hash0(get_key(obj)) = g0.
+ // Requires _M_preferred_bucket(obj) == b.
+ std::pair<iterator, bool> _M_cuckoo_insert_unique(const_reference obj,
+ size_type g0,
+ _Bucket_number b,
+ bool easy) {
+ if (bump_work_count_and_maybe_resize(easy)) {
+ return _M_insert_unique(obj, _S_easy);
+ }
+
+ // Possible nests for obj include, for example, for _S_z=4,
+ // h1, h1 ^ 1, h1 ^ 2, h1 ^ 3, h2, h2 ^ 1, h2 ^ 2, and h2 ^ 3.
+ const size_type g1 = _M_hash1(get_key(obj), g0);
+ const _Bucket_number h1 = _M_mod_bucket_count(g1);
+ for (_Bucket_number i = 0; i < _S_z; i++) {
+ if (_M_slots[h1 ^ i].is_available()) {
+ return _M_cuckoo_insert_to_slot(obj, b, h1 ^ i, easy);
+ }
+ }
+ const size_type g2 = _M_hash2(get_key(obj), g0);
+ const _Bucket_number h2 = _M_mod_bucket_count(g2);
+ for (_Bucket_number i = 0; i < _S_z; i++) {
+ if (_M_slots[h2 ^ i].is_available()) {
+ return _M_cuckoo_insert_to_slot(obj, b, h2 ^ i, easy);
+ }
+ }
+ auto p = extensions_if_any(g1, g2);
+ if (p.nodes_examined / 4 > sizeof(bucket_count()) * 8 ||
+ bucket_count() >> (p.nodes_examined / 4) == 0) {
+ // If we iterated through more than about 4 lg b extensions then the table
+ // is getting clogged. Substantially increase _M_work_since_last_rebuild.
+ _M_work_since_last_rebuild += (_M_work_since_last_rebuild >> 4) + 1;
+ }
+ if (p.found_any) {
+ // At least one relevant extension exists. Look for an empty nest.
+ _Extension_list* el = p.el;
+ _Extension* first_extension = &el->_M_extension;
+ const _Extension* e = first_extension;
+ // The first one is a special case: only e->i0 is used.
+ assert(e->Matches(g1, g2));
+ if (_M_slots[e->i0].is_available()) {
+ return _M_cuckoo_insert_to_slot(obj, b, e->i0, easy);
+ }
+ size_type num_to_search_per_extension = 2;
+ size_type _M_num_bucketssearched = 2 * _S_z + 1;
+ // Search subsequent extensions, if any.
+ _Extension_list* last_extension_list_visited = el;
+ while ((el = el->_M_next_in_chain) != nullptr) {
+ e = &el->_M_extension;
+ if (!e->Matches(g1, g2)) break;
+ _Permutation_iterator pi(e->i0, e->i1, _M_num_buckets,
+ num_to_search_per_extension);
+ do {
+ _Bucket_number q = pi._M_next();
+ if (_M_slots[q].is_available()) {
+ return _M_cuckoo_insert_to_slot(obj, b, q, easy);
+ }
+ ++_M_num_bucketssearched;
+ } while (!pi._M_done());
+ num_to_search_per_extension *= 2;
+ last_extension_list_visited = el;
+ if (num_to_search_per_extension == bucket_count()) {
+ // The whole table was just searched, and there is nowhere to put
+ // another item. Force a resize. But first, lower max_load_factor.
+ float mlf = lower_max_load_factor();
+ _M_work_since_last_rebuild = _M_work_threshold;
+ bool did_resize = bump_work_count_and_maybe_resize(easy);
+ assert(did_resize);
+ return _M_insert_unique(obj, _S_easy);
+ }
+ }
+ return _M_insert_by_creating_another_extension(
+ obj, last_extension_list_visited, g0, g1, g2, b);
+ }
+ static_assert(0 <= _S_z, "z cannot be negative"); // Usually 0 < _S_z < 10.
+ static_assert(_S_z < 1 << 30, "z is ridiculously large");
+ uint32_t r = _M_rand_at_most(_S_z * 4 - 1);
+ if ((r & 1) == 0) {
+ return _M_insert_by_creating_first_extension(obj, g0, g1, g2, b);
+ }
+ _Bucket_number victim = ((r & 2) == 0 ? h2 : h1) ^ (r >> 2);
+ // Rarely, we may find that _M_slots[victim] is pointing to
+ // something we cannot bump. If that happens, just start over.
+ if (!_M_slots[victim].can_point_to_element()) {
+ return _M_insert_unique(obj, easy);
+ }
+ const_pointer bumped_item = _M_slots[victim].get_ptr();
+ if (easy && _S_exceptions_enabled) {
+ // The caller has no _Rollback_state in progress, but we may need to
+ // handle an exception thrown during the "erase, insert, reinsert" here.
+ assert(_M_get_rollback_state() == nullptr);
+ _Rollback_state rs;
+ init_rollback_state(&rs);
+ __try {
+ _M_erase_known_key_no_rebucket(get_key(*bumped_item),
+ _S_hard_if_exceptions_enabled, _S_no_delete);
+ assert(_M_slots[victim].is_ptr_null());
+ auto result = _M_cuckoo_insert_to_slot(obj, b, victim, _S_hard);
+ _M_insert_unique(*bumped_item, _S_hard);
+ _M_clear_rollback_state();
+ return result;
+ } __catch (...) {
+ _M_rollback();
+ __throw_exception_again;
+ }
+ } else {
+ _M_erase_known_key_no_rebucket(get_key(*bumped_item), easy, _S_no_delete);
+ assert(_M_slots[victim].is_ptr_null());
+ auto result = _M_cuckoo_insert_to_slot(obj, b, victim, easy);
+ _M_insert_unique(*bumped_item, _S_hard_if_exceptions_enabled);
+ return result;
+ }
+ }
+
+ std::pair<_Bucket_number, _Bucket_number>
+ get_bucket_numbers_for_extensions(size_type g1, size_type g2) const {
+ // But, perhaps unnecessarily, we use multiple-choice chaining, so
+ // we return two distinct bucket numbers here. (See also the
+ // comment about 4 lg b, above.) The code assumes that the number of
+ // buckets is even, but it is easy to remove that assumption if it ever
+ // becomes necessary.
+ assert(_M_rng_state != nullptr);
+ _Bucket_number result0 = g1 * _M_random_odd_number() + g2;
+ result0 ^= result0 >> (sizeof(result0) == 8 ? 47 : 17);
+ result0 = _M_mod_bucket_count(result0 * _M_random_odd_number());
+ _Bucket_number result1 = g2 * _M_random_odd_number() + g1;
+ result1 ^= result1 >> (sizeof(result1) == 8 ? 46 : 16);
+ result1 = _M_mod_bucket_count((2 * result1 + 1) ^ result0);
+ assert(result0 != result1);
+ return {result0, result1};
+ }
+
+ struct ExtensionsIfAnyResult
+ {
+ // Whether any extensions for the <g1, g2> pair exist.
+ bool found_any;
+ // The first such extension (if any).
+ _Extension_list* el;
+ // Approximately how many _Extension_list nodes were examined.
+ size_type nodes_examined;
+ };
+
+ ExtensionsIfAnyResult extensions_if_any(size_type g1,
+ size_type g2) const {
+ if (_M_extension_list == nullptr) {
+ return {false, 0, 0};
+ }
+
+ const auto indices_to_examine = get_bucket_numbers_for_extensions(g1, g2);
+ _Extension_list *el = nullptr;
+ size_type iter_count = 0;
+ for (_Bucket_number index_to_examine :
+ {indices_to_examine.first, indices_to_examine.second}) {
+ if (_M_slots[index_to_examine].contains_extension_list()) {
+ el = _M_slots[index_to_examine].get_extension_listptr();
+ for (; el != nullptr; ++iter_count, el = el->_M_next_in_chain) {
+ if (el->_M_extension.Matches(g1, g2)) {
+ return {true, el, iter_count};
+ }
+ }
+ }
+ }
+ return {false, el, iter_count};
+ }
+
+ std::pair<iterator, bool>
+ _M_insert_by_creating_first_extension(const_reference obj, size_type g0,
+ size_type g1, size_type g2,
+ _Bucket_number b) {
+ const _Bucket_number bucket_for_extensions =
+ least_crowded_bucket(get_bucket_numbers_for_extensions(g1, g2));
+ _Rollback_state rs;
+ if (_S_exceptions_enabled && _M_get_rollback_state() == nullptr) {
+ init_rollback_state(&rs);
+ }
+ __try {
+ _Slot* s = &_M_slots[bucket_for_extensions];
+ const_pointer bumped_item = nullptr;
+ _Extension_list *el = nullptr;
+ if (s->can_point_to_element()) {
+ if (!s->is_ptr_null()) { // Need to bump an element
+ bumped_item = s->get_ptr();
+ _M_erase_known_key_no_rebucket(get_key(*bumped_item),
+ _S_hard_if_exceptions_enabled, _S_no_delete);
+ assert(s->is_ptr_null());
+ }
+ ++_M_num_non_element_slots;
+ } else {
+ el = s->get_extension_listptr();
+ }
+ // No element is in the bucket now. Insert at the front of the SLL of
+ // extensions.
+ std::pair<bool, _Bucket_number> p = _M_randomly_hunt_for_bucket();
+ el = new _Extension_list{_M_extension_list, el,
+ _Extension{g1, g2, p.second}};
+ _M_extension_list = el;
+ s->set_ptr_and_mark_as_extension_list(el, _S_hard_if_exceptions_enabled,
+ _M_get_rollback_state());
+ std::pair<iterator, bool> result;
+ if (p.first && p.second != bucket_for_extensions) {
+ assert(_M_slots[p.second].is_available());
+ result = _M_cuckoo_insert_to_slot(obj, b, p.second,
+ _S_hard_if_exceptions_enabled);
+ } else {
+ result = _M_cuckoo_insert_unique(obj, g0, b, _S_hard_if_exceptions_enabled);
+ }
+ // Almost done. Reinsert bumped item, if there is one.
+ if (bumped_item != nullptr) {
+ _M_insert_unique(*bumped_item, _S_hard_if_exceptions_enabled);
+ }
+ if (_S_exceptions_enabled && _M_get_rollback_state() == &rs)
+ _M_clear_rollback_state();
+ return result;
+ } __catch (...) {
+ _M_rollback();
+ __throw_exception_again;
+ }
+ }
+
+ // There are only two important cases: one of the buckets is
+ // available and the other isn't, or both buckets contain lists and
+ // the lists are different lengths. If we get both of those right
+ // we can hope to achieve the well-known O(ln ln n) bound for chain
+ // length when chaining with the choice of two buckets. In the
+ // unimportant cases, this method may return either p.first or p.second.
+ _Bucket_number
+ least_crowded_bucket(std::pair<_Bucket_number, _Bucket_number> __p) const
+ {
+ const _Slot& __s0 = _M_slots[__p.first];
+ const _Slot& __s1 = _M_slots[__p.second];
+ if (__s0.is_available()) return __p.first;
+ if (__s1.is_available()) return __p.second;
+ if (__s0.contains_extension_list() && __s1.contains_extension_list())
+ {
+ _Extension_list* __el0 = __s0.get_extension_listptr();
+ _Extension_list* __el1 = __s1.get_extension_listptr();
+ for (;;)
+ {
+ if ((__el0 = __el0->_M_next_in_chain) == nullptr) return __p.first;
+ if ((__el1 = __el1->_M_next_in_chain) == nullptr) return __p.second;
+ }
+ }
+ return __p.first;
+ }
+
+ std::pair<iterator, bool>
+ _M_insert_by_creating_another_extension(const_reference __obj,
+ _Extension_list* __last_extension_visited,
+ size_type __g0,
+ size_type __g1,
+ size_type __g2,
+ _Bucket_number __b) {
+ _Rollback_state __rs;
+ if (_S_exceptions_enabled && _M_get_rollback_state() == nullptr) {
+ init_rollback_state(&__rs);
+ }
+ __try
+ {
+ std::pair<bool, _Bucket_number> __p = _M_randomly_hunt_for_bucket();
+ std::pair<bool, _Bucket_number> __pp;
+ // Try to find two empty buckets, by probing at random.
+ // Whether or not two empty buckets are found, this loop will
+ // terminate in a reasonable amount of time, usually one iteration.
+ do {
+ __pp = _M_randomly_hunt_for_bucket();
+ } while (__p.second == __pp.second);
+ _Extension_list* __el = new _Extension_list{
+ _M_extension_list, __last_extension_visited->_M_next_in_chain,
+ _Extension{__g1, __g2, __p.second, __pp.second}};
+ // TODO: test if new returned nullptr(?)
+ _M_extension_list = __el;
+ _M_rollbackable_write(__last_extension_visited->_M_next_in_chain,
+ __el);
+ std::pair<iterator, bool> __result;
+ if (__p.first)
+ {
+ assert(_M_slots[__p.second].is_available());
+ __result =
+ _M_cuckoo_insert_to_slot(__obj, __b, __p.second,
+ _S_hard_if_exceptions_enabled);
+ }
+ else
+ {
+ __result = _M_cuckoo_insert_unique(__obj, __g0, __b,
+ _S_hard_if_exceptions_enabled);
+ }
+ if (_S_exceptions_enabled && (_M_get_rollback_state() == &__rs))
+ {
+ _M_clear_rollback_state();
+ }
+ return __result;
+ }
+ __catch (...)
+ {
+ _M_rollback();
+ __throw_exception_again;
+ }
+ }
+
+ std::pair<bool, _Bucket_number>
+ _M_randomly_hunt_for_bucket()
+ {
+ _Bucket_number __result = 0;
+ for (int __i = 0; __i < _S_random_hunt_max_iters; __i++)
+ {
+ __result = _M_rand_at_most(bucket_count() - 1);
+ if (_M_slots[__result].is_available())
+ {
+ return {true, __result};
+ }
+ }
+ return {false, __result};
+ }
+
+ // Put obj in one its possible nests, _M_slots[b].
+ // Requires _M_preferred_bucket(obj) == pref.
+ // Requires _M_slots[b] to be a possible nest for obj that is currently empty.
+ std::pair<iterator, bool> _M_cuckoo_insert_to_slot(const_reference __obj,
+ _Bucket_number __pref,
+ _Bucket_number __b,
+ bool __easy) {
+ _M_slots[__b].set_ptr_that_was_null(&__obj, __easy, _M_get_rollback_state());
+ _M_increment_num_elements();
+ return {_M_iter_at(__b), _S_did_insert};
+ }
+
+ void _M_rollback() {
+#if __cpp_exceptions
+ if (_M_rollback_state == nullptr) return;
+ // Undo everything in the log, starting with the most recent.
+ for (size_type i = _M_rollback_state->size(); i-- > 0; ) {
+ typename _Rollback_state::Record& r = _M_rollback_state->at(i);
+ memcpy(r.ptr, &r.old_value, sizeof(r.old_value));
+ }
+ // Undo allocation/construction of vals, if any.
+ for (const auto& v : _M_rollback_state->_M_vals_created) {
+ _M_delete_value(*v);
+ }
+
+ _M_num_elements = _M_rollback_state->_M_num_elements;
+ _M_num_non_element_slots = _M_rollback_state->_M_num_non_element_slots;
+ _M_rollback_state = nullptr;
+#endif
+ }
+
+ _Bucket_number
+ _M_preferred_bucket_for_key(const key_type& __key) const
+ { return _M_mod_bucket_count(_M_hash0(__key)); }
+
+ _Bucket_number
+ _M_preferred_bucket(const_reference __obj) const
+ { return _M_preferred_bucket_for_key(get_key(__obj)); }
+
+ iterator
+ _M_iter_at(_Bucket_number __b)
+ { return iterator(this, __b, _S_no_advance); }
+
+ // Specializations of insert(it, it) depending on the power of the iterator:
+ // (1) Iterator has multi-pass guarantee.
+ template<typename _ForwardIterator>
+ void insert(_ForwardIterator __f, _ForwardIterator __l,
+ std::forward_iterator_tag)
+ {
+ size_t __dist = std::distance(__f, __l);
+ if (__dist >= std::numeric_limits<size_type>::max()) {
+#if __cpp_exceptions
+ throw std::length_error("insert-range overflow");
+#else
+ assert(0 && "insert-range overflow");
+#endif
+ }
+ _M_resize_delta(static_cast<size_type>(__dist));
+ for ( ; __dist > 0; --__dist, ++__f) {
+ insert(*__f);
+ }
+ }
+
+ // (2) Arbitrary iterator, can't tell how much to resize
+ template<typename _InputIterator>
+ void insert(_InputIterator __f, _InputIterator __l,
+ std::input_iterator_tag) {
+ for ( ; __f != __l; ++__f) {
+ insert(*__f);
+ }
+ }
+
+ public:
+ // This is the normal insert routine, used by the outside world.
+ template<typename _V>
+ std::pair<iterator, bool>
+ insert(_V&& __v, bool __copy = _S_copy)
+ {
+ assert(_M_get_rollback_state() == nullptr);
+ for (;;) {
+ __try
+ {
+ return _M_find_or_insert(std::forward<_V>(__v), __copy);
+ }
+ __catch (_Resize_request&)
+ {
+ _M_resize_delta(1);
+ }
+ }
+ }
+
+ void
+ insert(std::initializer_list<value_type> __il)
+ { this->insert(__il.begin(), __il.end()); }
+
+ // When inserting a lot at a time, we specialize on the type of iterator
+ template<class _InputIterator>
+ void insert(_InputIterator __f, _InputIterator __l)
+ {
+ // specializes on iterator type
+ this->insert(__f, __l,
+ typename std::iterator_traits<_InputIterator>::iterator_category());
+ }
+
+ template<typename _V>
+ iterator
+ insert(const_iterator __hint, _V&& __v)
+ { return insert(std::forward<_V>(__v)).first; }
+
+ template<typename... _Args>
+ std::pair<iterator, bool>
+ emplace(_Args&&... __args)
+ {
+ // Create node and compute hash. If something goes wrong or no insertion
+ // was needed then we'll delete it.
+ const_pointer __p = new value_type(std::forward<_Args>(__args)...);
+ std::pair<iterator, bool> __result;
+ __try
+ {
+ __result = this->insert(*__p, _S_no_copy);
+ }
+ __catch (...)
+ {
+ _M_delete_value(*__p);
+ __throw_exception_again;
+ }
+ if (!__result.second)
+ {
+ _M_delete_value(*__p);
+ }
+ return __result;
+ }
+
+ template<typename... _Args>
+ iterator emplace_hint(const_iterator, _Args&&... __args)
+ {
+ // Create node and compute hash. If something goes wrong or no insertion
+ // was needed then we'll delete it.
+ const_pointer __p = new value_type(std::forward<_Args>(__args)...);
+ std::pair<iterator, bool> __result;
+ __try
+ {
+ __result = this->insert(*__p, _S_no_copy);
+ }
+ __catch (...)
+ {
+ _M_delete_value(*__p);
+ __throw_exception_again;
+ }
+ if (!__result.second)
+ {
+ _M_delete_value(*__p);
+ }
+ return __result.first;
+ }
+
+ // DELETION ROUTINES
+ size_type
+ erase(const key_type& __key)
+ { return _M_erase(__key, _S_easy, _S_delete); }
+
+ iterator
+ erase(iterator pos)
+ { return _M_erase_iter(pos); }
+
+ iterator
+ erase(const_iterator pos)
+ { return _M_erase_iter(pos); }
+
+ iterator
+ erase(const_iterator __f, const_iterator __l)
+ {
+ while (__f != __l) {
+ __f = this->erase(__f);
+ }
+ return __f;
+ }
+
+ private:
+ iterator
+ _M_erase_iter(iterator __pos)
+ {
+ _Disallow_rebucket_holder __dbh(&_M_allow_rebucketing);
+ assert(__pos != end());
+ iterator __result = std::next(__pos);
+ erase(*__pos);
+ return __result;
+ }
+
+ size_type
+ _M_erase(const key_type& __k, bool __easy, bool __del)
+ {
+ assert(__easy || !__del);
+ if (bump_work_count_and_maybe_resize(__easy))
+ {
+ return _M_erase(__k, _S_easy, __del);
+ }
+ const size_type __g0 = _M_hash0(__k);
+ const _Bucket_number __b = _M_mod_bucket_count(__g0);
+ if (_M_slots[__b].has_bitset())
+ {
+ // Common case. We have a bitset telling us where to look.
+ const int __bitset = _M_slots[__b].get_bitset();
+ for (int __lg_t = 0, __t = 1; __t <= __bitset; __lg_t++, __t *= 2)
+ {
+ if ((__bitset & __t) != 0)
+ {
+ const _Bucket_number __q = __b ^ __lg_t;
+ if (!_M_slots[__q].is_ptr_null()
+ && _M_equals(get_key(*_M_slots[__q].get_ptr()), __k))
+ {
+ // Found a match for __obj.
+ if (__del) _M_delete_value(*_M_slots[__q].get_ptr());
+ _M_slots[__q].set_ptr_to_null(__easy, _M_get_rollback_state());
+ _M_slots[__b].xor_bitset(__t, __easy, _M_get_rollback_state());
+ _M_decrement_num_elements();
+ return 1;
+ }
+ }
+ }
+ return 0;
+ }
+ else
+ {
+ // Uncommon case. Search an overfull bucket.
+ const size_type __g1 = _M_hash1(__k, __g0);
+ const _Bucket_number __h1 = _M_mod_bucket_count(__g1);
+ for (_Bucket_number __i = 0; __i < _S_z; __i++)
+ {
+ const _Bucket_number __q = __h1 ^ __i;
+ if (_M_slots[__q].has_element()
+ && _M_equals(get_key(*_M_slots[__q].get_ptr()), __k))
+ {
+ return _M_cuckoo_remove_from_slot(__q, __easy, __del);
+ }
+ }
+ const size_type __g2 = _M_hash2(__k, __g0);
+ const _Bucket_number __h2 = _M_mod_bucket_count(__g2);
+ for (_Bucket_number __i = 0; __i < _S_z; __i++)
+ {
+ const _Bucket_number __q = __h2 ^ __i;
+ if (_M_slots[__q].has_element()
+ && _M_equals(get_key(*_M_slots[__q].get_ptr()), __k))
+ {
+ return _M_cuckoo_remove_from_slot(__q, __easy, __del);
+ }
+ }
+ // Check for Extensions.
+ auto __p = extensions_if_any(__g1, __g2);
+ if (__p.found_any)
+ {
+ // At least one relevant extension exists.
+ _Extension_list* __el = __p.el;
+ const _Extension* __e = &__el->_M_extension;
+ // The first one is a special case: only e->i0 is used.
+ assert(__e->Matches(__g1, __g2));
+ const _Bucket_number __q = __e->i0;
+ if (_M_slots[__q].has_element()
+ && _M_equals(get_key(*_M_slots[__q].get_ptr()), __k))
+ {
+ return _M_cuckoo_remove_from_slot(__q, __easy, __del);
+ }
+ // Search subsequent extensions, if any.
+ size_type __num_to_search_per_extension = 2;
+ while ((__el = __el->_M_next_in_chain) != nullptr)
+ {
+ __e = &__el->_M_extension;
+ if (!(__e->Matches(__g1, __g2))) break;
+ _Permutation_iterator __pi(__e->i0, __e->i1, _M_num_buckets,
+ __num_to_search_per_extension);
+ do {
+ const _Bucket_number __q = __pi._M_next();
+ if (_M_slots[__q].has_element()
+ && _M_equals(get_key(*_M_slots[__q].get_ptr()), __k))
+ {
+ return _M_cuckoo_remove_from_slot(__q, __easy, __del);
+ }
+ } while (!__pi._M_done());
+ __num_to_search_per_extension *= 2;
+ }
+ }
+ return 0;
+ }
+ }
+
+ // Equivalent to erase(k, easy, del), but requires k to be present.
+ size_type
+ _M_erase_known_key(const key_type& __k, bool __easy, bool __del)
+ {
+ int __count = _M_erase(__k, __easy, __del);
+ assert(__count == 1);
+ return __count;
+ }
+
+ // The same, but do not allow rebucketing.
+ size_type
+ _M_erase_known_key_no_rebucket(const key_type& __k, bool __easy,
+ bool __del)
+ {
+ _Disallow_rebucket_holder __dbh(&_M_allow_rebucketing);
+ return _M_erase_known_key(__k, __easy, __del);
+ }
+
+ size_type
+ _M_cuckoo_remove_from_slot(_Bucket_number __b, bool __easy, bool __del)
+ {
+ if (__del) _M_delete_value(*_M_slots[__b].get_ptr());
+ _M_slots[__b].set_ptr_to_null(__easy, _M_get_rollback_state());
+ _M_decrement_num_elements();
+ return 1;
+ }
+
+ _Bucket_number
+ _M_mod_bucket_count(_Bucket_number __b) const
+ { return __b & (bucket_count() - 1); }
+
+ pointer*
+ _M_extend_rollback_statefor_new_values()
+ {
+ if (!_S_exceptions_enabled || _M_get_rollback_state() == nullptr)
+ {
+ return nullptr;
+ }
+ _M_get_rollback_state()->_M_vals_created
+ .resize(_M_get_rollback_state()->_M_vals_created.size() + 1);
+ return &_M_get_rollback_state()->_M_vals_created.back();
+ }
+
+ public:
+ // COMPARISON
+ bool
+ _M_equal(const _Cuckoo& ht) const
+ {
+ if (size() != ht.size())
+ {
+ return false;
+ }
+ else if (this == &ht)
+ {
+ return true;
+ }
+ else
+ {
+ for (const_reference r : *this)
+ {
+ if (ht.count(get_key(r)) != 1)
+ {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+
+ private:
+ // Package functors with another class to eliminate memory needed for
+ // zero-size functors. Since _Extract_key and hasher's operator() might
+ // have the same function signature, they must be packaged in
+ // different classes.
+ struct _Settings
+ : cuckoo_internal::_Cuckoo_settings<key_type, hasher, _S_min_buckets>
+ {
+ explicit _Settings(const hasher& __h)
+ : cuckoo_internal::_Cuckoo_settings<key_type, hasher,
+ _S_min_buckets>(
+ __h, _S_default_max_occupancy_percent / 100.0f,
+ _S_default_consider_shrink_occupancy / 100.0f)
+ { }
+ };
+
+ // Packages _Extract_key and _Equal_key functors.
+ class _KeyInfo : public _Extract_key, public _Equal_key {
+ public:
+ _KeyInfo(const _Extract_key& __ek, const _Equal_key& __eq)
+ : _Extract_key(__ek), _Equal_key(__eq) { }
+
+ // The return type of _Extract_key::operator(), e.g., _Key or const _Key&.
+ typedef decltype(_Extract_key()(*(const_pointer)0)) _Get_key_type;
+
+ _Get_key_type
+ get_key(const_reference __v) const
+ { return _Extract_key::operator()(__v); }
+
+ bool
+ _M_equals(const key_type& __a, const key_type& __b) const
+ { return _Equal_key::operator()(__a, __b); }
+ };
+
+ // Utility functions to access the templated operators.
+ size_type
+ _M_hash0(const key_type& __v) const
+ { return _M_settings._M_hash0(__v); }
+
+ size_type
+ _M_hash1(const key_type& __v, size_type __g0) const
+ { return _M_settings._M_hash1(__v, __g0); }
+
+ size_type
+ _M_hash2(const key_type& __v, size_type __g0) const
+ { return _M_settings._M_hash2(__v, __g0); }
+
+ bool
+ _M_equals(const key_type& __a, const key_type& __b) const
+ { return _M_key_info._M_equals(__a, __b); }
+
+ typename _KeyInfo::_Get_key_type
+ get_key(const_reference __v) const
+ { return _M_key_info.get_key(__v); }
+
+ void
+ set_key(pointer __v, const key_type& __k) const
+ { _M_key_info.set_key(__v, __k); }
+
+ ////////////////////////////////////////////////////////////////////////
+
+ /* array of _M_num_buckets slots */
+ _Slot* _M_slots;
+ _Settings _M_settings;
+ _KeyInfo _M_key_info;
+
+ size_type _M_num_elements;
+ size_type _M_num_non_element_slots; // ignores those with pointer == nullptr
+ size_type _M_num_buckets;
+ size_type _M_work_since_last_rebuild;
+ size_type _M_work_threshold;
+#if __cpp_exceptions
+ _Rollback_state* _M_rollback_state;
+#endif
+ // Linked list of all extensions. As new ones are created, they are
+ // pushed on the front of the list. This is just bookkeeping: the
+ // list is traversed only during rollbacks or our destructor.
+ _Extension_list* _M_extension_list;
+ value_alloc_type _M_value_alloc;
+ // If _M_allow_shrinking is false then disallow shrinking. This is used in
+ // situations where we know we are increasing the load but there may be
+ // a temporary dip in the load along the way, and it's best not to allow
+ // that to trigger a shrink.
+ bool _M_allow_shrinking;
+ // An even more extreme option: we can disallow rebucketing.
+ bool _M_allow_rebucketing;
+ // Count buckets consumed by bookkeeping data rather than const_pointers.
+ _RNGState* _M_rng_state;
+ };
+
+#endif /* _CUCKOO_H */
Property changes on: libstdc++-v3/include/bits/cuckoo.h
___________________________________________________________________
Added: svn:eol-style
## -0,0 +1 ##
+LF
\ No newline at end of property
===================================================================
@@ -30,6 +30,15 @@
#ifndef _UNORDERED_SET_H
#define _UNORDERED_SET_H
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET && \
+ defined(_GLIBCXX_DEBUG_UNORDERED_SET) || !defined(_LP64)
+#undef USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+#endif
+
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+#include <bits/cuckoo.h>
+#endif
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
@@ -92,7 +101,15 @@
class _Alloc = std::allocator<_Value> >
class unordered_set
{
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+ struct _Identity {
+ template <typename T>
+ T&& operator()(T&& t) const { return std::forward<T>(t); }
+ };
+ typedef _Cuckoo<_Value, _Value, _Hash, _Identity, _Pred, _Alloc> _Hashtable;
+#else
typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
+#endif
_Hashtable _M_h;
public:
@@ -137,7 +154,11 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+ : _M_h(__n, __hf, __eql, _Identity(), __a)
+#else
: _M_h(__n, __hf, __eql, __a)
+#endif
{ }
/**
@@ -159,8 +180,16 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+ : _M_h(__n, __hf, __eql, _Identity(), __a)
+ {
+ this->insert(__first, __last);
+ this->max_load_factor(1.0);
+ }
+#else
: _M_h(__first, __last, __n, __hf, __eql, __a)
{ }
+#endif
/// Copy constructor.
unordered_set(const unordered_set&) = default;
@@ -213,8 +242,13 @@
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal(),
const allocator_type& __a = allocator_type())
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+ : unordered_set(__n, __hf, __eql, __a)
+ { this->insert(__l); }
+#else
: _M_h(__l, __n, __hf, __eql, __a)
{ }
+#endif
unordered_set(size_type __n, const allocator_type& __a)
: unordered_set(__n, hasher(), key_equal(), __a)
@@ -739,6 +773,30 @@
friend bool
operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
+
+#if USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET
+ // Extras
+
+ // The seed can be set explicitly, e.g., to aid debugging. Requires: empty().
+ void set_random_seed(const std::seed_seq& __s) { _M_h.set_random_seed(__s); }
+
+ // Clear the set without rebucketing.
+ void clear_no_resize() { _M_h.clear_no_resize(); }
+
+ // New tables allow rebucketing, and that's the recommended state. But,
+ // we allow rebucketing to disabled or enabled manually. The return value
+ // is whether rebucketing was allowed immediately prior to the call.
+ bool allow_rebucketing(bool __new_state) {
+ return _M_h.allow_rebucketing(__new_state);
+ }
+
+ // Similarly, new tables allow shrinking. This allows shrinking
+ // to disabled or enabled manually. The return value is whether
+ // shrinking was allowed immediately prior to the call.
+ bool allow_shrinking(bool __new_state) {
+ return _M_h.allow_shrinking(__new_state);
+ }
+#endif
};
/**