===================================================================
@@ -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,16 @@
#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 +102,15 @@
This change is the start of a rewrite of unordered_set and unordered_map. (By the way, I am new to GCC and do not have SVN write access.) SUMMARY OF MOTIVATION FOR THE CHANGE 1. Speed. Linked lists are slow. Without them, we save memory, allowing us to default to a lower load factor; or, the savings could be RAM, if desired. Initial tests are showing a 20%ish improvement on several basic benchmarks (with FDO, on x86-64). 2. Defense to hash flooding. This benefit is harder to analyze, but I think I'm making a reasonable proposal. PLAN I plan to spread the changs out over multiple patches. This first patch has no effect USE_HYBRID_WILD_CUCKOO_FOR_UNORDERED_SET is defined to 1 (or similar). The patch isn't ready yet to turn that on by default; I intend to suggest flipping the default after this and other to-be-written patches are submitted. That said, I would love to get feedback, so I can understand any substantial flaws sooner rather than later. DETAILS "Hash flooding" is an attempt by an adversary to flood a hash table with keys that cause an unusual amount of time (or RAM or ...) to be consumed. For example, an adversary might present many keys with the same hash code. Here are several common ideas to combat hash flooding, and counter arguments to each: 1. A traditional hash table with a "great" hash function. Counter argument: no matter what hash function is selected, there is still a timing attack that can force O(n^1.5) computational steps by the attackee via only n steps by the adversary. Also, "great" hash functions aren't cheap. 2. A hash table that uses linked lists in lightly-occupied buckets and balanced binary trees in heavily-occupied buckets. Counter argument: Worst case O(n log n) time with perhaps a lot of wasted RAM as well. Also, this introduces the need for an ordering on the elements. 3. De-amortized Cuckoo with "great" hash functions. Counter argument: when hash-flooded, the "queue" or "stash" in de-amortized Cuckoo can become long enough that a lot of basic operations that much longer than normal. Also, "great" hash functions aren't cheap. On general principles, it would be nice to avoid a performance penalty in the happy, common cases where no hash flooding is in progress. Furthermore, if hash flooding is in progress, access to keys not provided by the adversary should still be (mostly) fast. My belief is we can overcome all these issues and still be backward compatible with the requirements of C++'s unordered_set and unordered_map. I haven't decided exactly how to tackle unordered_multi{map,set} yet, but I don't forsee any huge problems there. Another key feature of the scheme I've begun implementing is that, while it's preferable to let it work with a family of hash functions (like Cuckoo does), if only one is available, as will be the case in a lot of existing code, then it still works. When offered a single hash function to use, the code creates a family of hash functions by using a random post-processing step, i.e., the output of the given hash function is rehashed by a randomly-selected hash-code-to-hash-code function. This isn't great for avoiding hash flooding, but I suspect it's better than nothing. Comments in the patch contain additional algorithmic details etc. KNOWN ISSUES o The C++ standard says very little about what local iterators are supposed to do. What it seems to require: begin(bucket_number) takes O(1) time, and if two elements have the same hash code then a single local iteration should contain both. The current patch takes that at face value, and simply makes begin(0) yield a local iterator that contains everything (like begin()) and begin(n) == end(n) for n != 0. Unfortunately, although the standard doesn't say one may assume it, there may be existing code that assumes that begin(n) has something to do with the elements whose hash code is n mod bucket_count(). If my shortcut isn't acceptable then I'll have to switch to a more complex, slower scheme. That'll hurt a bit, but I don't think it'll destroy the value of what I'm proposing. Luckily, local iterators are an obscure, seldom-used feature. o Allocators need to be addressed (currently the prototype just uses new and delete for everything). o Other details need to be addressed, notably: swapping exactly what should be swapped in the swap method, making begin() take O(1) time, and properly handling exceptions thrown by the hasher and other code that we call. o Portability needs to be addressed. o I'm still working on switching everything over to GCC coding style o Some optimizations (notably caching hash codes) need to be investigated/added. o Performance gains without FDO aren't nearly as impressive. I haven't yet looked into this discrepancy. 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 +155,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 +181,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 +243,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 +774,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 }; /**