raw_hash_set.h
Go to the documentation of this file.
00001 // Copyright 2018 The Abseil Authors.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //      https://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 //
00015 // An open-addressing
00016 // hashtable with quadratic probing.
00017 //
00018 // This is a low level hashtable on top of which different interfaces can be
00019 // implemented, like flat_hash_set, node_hash_set, string_hash_set, etc.
00020 //
00021 // The table interface is similar to that of std::unordered_set. Notable
00022 // differences are that most member functions support heterogeneous keys when
00023 // BOTH the hash and eq functions are marked as transparent. They do so by
00024 // providing a typedef called `is_transparent`.
00025 //
00026 // When heterogeneous lookup is enabled, functions that take key_type act as if
00027 // they have an overload set like:
00028 //
00029 //   iterator find(const key_type& key);
00030 //   template <class K>
00031 //   iterator find(const K& key);
00032 //
00033 //   size_type erase(const key_type& key);
00034 //   template <class K>
00035 //   size_type erase(const K& key);
00036 //
00037 //   std::pair<iterator, iterator> equal_range(const key_type& key);
00038 //   template <class K>
00039 //   std::pair<iterator, iterator> equal_range(const K& key);
00040 //
00041 // When heterogeneous lookup is disabled, only the explicit `key_type` overloads
00042 // exist.
00043 //
00044 // find() also supports passing the hash explicitly:
00045 //
00046 //   iterator find(const key_type& key, size_t hash);
00047 //   template <class U>
00048 //   iterator find(const U& key, size_t hash);
00049 //
00050 // In addition the pointer to element and iterator stability guarantees are
00051 // weaker: all iterators and pointers are invalidated after a new element is
00052 // inserted.
00053 //
00054 // IMPLEMENTATION DETAILS
00055 //
00056 // The table stores elements inline in a slot array. In addition to the slot
00057 // array the table maintains some control state per slot. The extra state is one
00058 // byte per slot and stores empty or deleted marks, or alternatively 7 bits from
00059 // the hash of an occupied slot. The table is split into logical groups of
00060 // slots, like so:
00061 //
00062 //      Group 1         Group 2        Group 3
00063 // +---------------+---------------+---------------+
00064 // | | | | | | | | | | | | | | | | | | | | | | | | |
00065 // +---------------+---------------+---------------+
00066 //
00067 // On lookup the hash is split into two parts:
00068 // - H2: 7 bits (those stored in the control bytes)
00069 // - H1: the rest of the bits
00070 // The groups are probed using H1. For each group the slots are matched to H2 in
00071 // parallel. Because H2 is 7 bits (128 states) and the number of slots per group
00072 // is low (8 or 16) in almost all cases a match in H2 is also a lookup hit.
00073 //
00074 // On insert, once the right group is found (as in lookup), its slots are
00075 // filled in order.
00076 //
00077 // On erase a slot is cleared. In case the group did not have any empty slots
00078 // before the erase, the erased slot is marked as deleted.
00079 //
00080 // Groups without empty slots (but maybe with deleted slots) extend the probe
00081 // sequence. The probing algorithm is quadratic. Given N the number of groups,
00082 // the probing function for the i'th probe is:
00083 //
00084 //   P(0) = H1 % N
00085 //
00086 //   P(i) = (P(i - 1) + i) % N
00087 //
00088 // This probing function guarantees that after N probes, all the groups of the
00089 // table will be probed exactly once.
00090 
00091 #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
00092 #define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_
00093 
00094 #include <algorithm>
00095 #include <cmath>
00096 #include <cstdint>
00097 #include <cstring>
00098 #include <iterator>
00099 #include <limits>
00100 #include <memory>
00101 #include <tuple>
00102 #include <type_traits>
00103 #include <utility>
00104 
00105 #include "absl/base/internal/bits.h"
00106 #include "absl/base/internal/endian.h"
00107 #include "absl/base/port.h"
00108 #include "absl/container/internal/common.h"
00109 #include "absl/container/internal/compressed_tuple.h"
00110 #include "absl/container/internal/container_memory.h"
00111 #include "absl/container/internal/hash_policy_traits.h"
00112 #include "absl/container/internal/hashtable_debug_hooks.h"
00113 #include "absl/container/internal/hashtablez_sampler.h"
00114 #include "absl/container/internal/have_sse.h"
00115 #include "absl/container/internal/layout.h"
00116 #include "absl/memory/memory.h"
00117 #include "absl/meta/type_traits.h"
00118 #include "absl/utility/utility.h"
00119 
00120 namespace absl {
00121 namespace container_internal {
00122 
00123 template <size_t Width>
00124 class probe_seq {
00125  public:
00126   probe_seq(size_t hash, size_t mask) {
00127     assert(((mask + 1) & mask) == 0 && "not a mask");
00128     mask_ = mask;
00129     offset_ = hash & mask_;
00130   }
00131   size_t offset() const { return offset_; }
00132   size_t offset(size_t i) const { return (offset_ + i) & mask_; }
00133 
00134   void next() {
00135     index_ += Width;
00136     offset_ += index_;
00137     offset_ &= mask_;
00138   }
00139   // 0-based probe index. The i-th probe in the probe sequence.
00140   size_t index() const { return index_; }
00141 
00142  private:
00143   size_t mask_;
00144   size_t offset_;
00145   size_t index_ = 0;
00146 };
00147 
00148 template <class ContainerKey, class Hash, class Eq>
00149 struct RequireUsableKey {
00150   template <class PassedKey, class... Args>
00151   std::pair<
00152       decltype(std::declval<const Hash&>()(std::declval<const PassedKey&>())),
00153       decltype(std::declval<const Eq&>()(std::declval<const ContainerKey&>(),
00154                                          std::declval<const PassedKey&>()))>*
00155   operator()(const PassedKey&, const Args&...) const;
00156 };
00157 
00158 template <class E, class Policy, class Hash, class Eq, class... Ts>
00159 struct IsDecomposable : std::false_type {};
00160 
00161 template <class Policy, class Hash, class Eq, class... Ts>
00162 struct IsDecomposable<
00163     absl::void_t<decltype(
00164         Policy::apply(RequireUsableKey<typename Policy::key_type, Hash, Eq>(),
00165                       std::declval<Ts>()...))>,
00166     Policy, Hash, Eq, Ts...> : std::true_type {};
00167 
00168 // TODO(alkis): Switch to std::is_nothrow_swappable when gcc/clang supports it.
00169 template <class T>
00170 constexpr bool IsNoThrowSwappable() {
00171   using std::swap;
00172   return noexcept(swap(std::declval<T&>(), std::declval<T&>()));
00173 }
00174 
00175 template <typename T>
00176 int TrailingZeros(T x) {
00177   return sizeof(T) == 8 ? base_internal::CountTrailingZerosNonZero64(
00178                               static_cast<uint64_t>(x))
00179                         : base_internal::CountTrailingZerosNonZero32(
00180                               static_cast<uint32_t>(x));
00181 }
00182 
00183 template <typename T>
00184 int LeadingZeros(T x) {
00185   return sizeof(T) == 8
00186              ? base_internal::CountLeadingZeros64(static_cast<uint64_t>(x))
00187              : base_internal::CountLeadingZeros32(static_cast<uint32_t>(x));
00188 }
00189 
00190 // An abstraction over a bitmask. It provides an easy way to iterate through the
00191 // indexes of the set bits of a bitmask.  When Shift=0 (platforms with SSE),
00192 // this is a true bitmask.  On non-SSE, platforms the arithematic used to
00193 // emulate the SSE behavior works in bytes (Shift=3) and leaves each bytes as
00194 // either 0x00 or 0x80.
00195 //
00196 // For example:
00197 //   for (int i : BitMask<uint32_t, 16>(0x5)) -> yields 0, 2
00198 //   for (int i : BitMask<uint64_t, 8, 3>(0x0000000080800000)) -> yields 2, 3
00199 template <class T, int SignificantBits, int Shift = 0>
00200 class BitMask {
00201   static_assert(std::is_unsigned<T>::value, "");
00202   static_assert(Shift == 0 || Shift == 3, "");
00203 
00204  public:
00205   // These are useful for unit tests (gunit).
00206   using value_type = int;
00207   using iterator = BitMask;
00208   using const_iterator = BitMask;
00209 
00210   explicit BitMask(T mask) : mask_(mask) {}
00211   BitMask& operator++() {
00212     mask_ &= (mask_ - 1);
00213     return *this;
00214   }
00215   explicit operator bool() const { return mask_ != 0; }
00216   int operator*() const { return LowestBitSet(); }
00217   int LowestBitSet() const {
00218     return container_internal::TrailingZeros(mask_) >> Shift;
00219   }
00220   int HighestBitSet() const {
00221     return (sizeof(T) * CHAR_BIT - container_internal::LeadingZeros(mask_) -
00222             1) >>
00223            Shift;
00224   }
00225 
00226   BitMask begin() const { return *this; }
00227   BitMask end() const { return BitMask(0); }
00228 
00229   int TrailingZeros() const {
00230     return container_internal::TrailingZeros(mask_) >> Shift;
00231   }
00232 
00233   int LeadingZeros() const {
00234     constexpr int total_significant_bits = SignificantBits << Shift;
00235     constexpr int extra_bits = sizeof(T) * 8 - total_significant_bits;
00236     return container_internal::LeadingZeros(mask_ << extra_bits) >> Shift;
00237   }
00238 
00239  private:
00240   friend bool operator==(const BitMask& a, const BitMask& b) {
00241     return a.mask_ == b.mask_;
00242   }
00243   friend bool operator!=(const BitMask& a, const BitMask& b) {
00244     return a.mask_ != b.mask_;
00245   }
00246 
00247   T mask_;
00248 };
00249 
00250 using ctrl_t = signed char;
00251 using h2_t = uint8_t;
00252 
00253 // The values here are selected for maximum performance. See the static asserts
00254 // below for details.
00255 enum Ctrl : ctrl_t {
00256   kEmpty = -128,   // 0b10000000
00257   kDeleted = -2,   // 0b11111110
00258   kSentinel = -1,  // 0b11111111
00259 };
00260 static_assert(
00261     kEmpty & kDeleted & kSentinel & 0x80,
00262     "Special markers need to have the MSB to make checking for them efficient");
00263 static_assert(kEmpty < kSentinel && kDeleted < kSentinel,
00264               "kEmpty and kDeleted must be smaller than kSentinel to make the "
00265               "SIMD test of IsEmptyOrDeleted() efficient");
00266 static_assert(kSentinel == -1,
00267               "kSentinel must be -1 to elide loading it from memory into SIMD "
00268               "registers (pcmpeqd xmm, xmm)");
00269 static_assert(kEmpty == -128,
00270               "kEmpty must be -128 to make the SIMD check for its "
00271               "existence efficient (psignb xmm, xmm)");
00272 static_assert(~kEmpty & ~kDeleted & kSentinel & 0x7F,
00273               "kEmpty and kDeleted must share an unset bit that is not shared "
00274               "by kSentinel to make the scalar test for MatchEmptyOrDeleted() "
00275               "efficient");
00276 static_assert(kDeleted == -2,
00277               "kDeleted must be -2 to make the implementation of "
00278               "ConvertSpecialToEmptyAndFullToDeleted efficient");
00279 
00280 // A single block of empty control bytes for tables without any slots allocated.
00281 // This enables removing a branch in the hot path of find().
00282 inline ctrl_t* EmptyGroup() {
00283   alignas(16) static constexpr ctrl_t empty_group[] = {
00284       kSentinel, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty,
00285       kEmpty,    kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty};
00286   return const_cast<ctrl_t*>(empty_group);
00287 }
00288 
00289 // Mixes a randomly generated per-process seed with `hash` and `ctrl` to
00290 // randomize insertion order within groups.
00291 bool ShouldInsertBackwards(size_t hash, ctrl_t* ctrl);
00292 
00293 // Returns a hash seed.
00294 //
00295 // The seed consists of the ctrl_ pointer, which adds enough entropy to ensure
00296 // non-determinism of iteration order in most cases.
00297 inline size_t HashSeed(const ctrl_t* ctrl) {
00298   // The low bits of the pointer have little or no entropy because of
00299   // alignment. We shift the pointer to try to use higher entropy bits. A
00300   // good number seems to be 12 bits, because that aligns with page size.
00301   return reinterpret_cast<uintptr_t>(ctrl) >> 12;
00302 }
00303 
00304 inline size_t H1(size_t hash, const ctrl_t* ctrl) {
00305   return (hash >> 7) ^ HashSeed(ctrl);
00306 }
00307 inline ctrl_t H2(size_t hash) { return hash & 0x7F; }
00308 
00309 inline bool IsEmpty(ctrl_t c) { return c == kEmpty; }
00310 inline bool IsFull(ctrl_t c) { return c >= 0; }
00311 inline bool IsDeleted(ctrl_t c) { return c == kDeleted; }
00312 inline bool IsEmptyOrDeleted(ctrl_t c) { return c < kSentinel; }
00313 
00314 #if SWISSTABLE_HAVE_SSE2
00315 
00316 // https://github.com/abseil/abseil-cpp/issues/209
00317 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87853
00318 // _mm_cmpgt_epi8 is broken under GCC with -funsigned-char
00319 // Work around this by using the portable implementation of Group
00320 // when using -funsigned-char under GCC.
00321 inline __m128i _mm_cmpgt_epi8_fixed(__m128i a, __m128i b) {
00322 #if defined(__GNUC__) && !defined(__clang__)
00323   if (std::is_unsigned<char>::value) {
00324     const __m128i mask = _mm_set1_epi8(0x80);
00325     const __m128i diff = _mm_subs_epi8(b, a);
00326     return _mm_cmpeq_epi8(_mm_and_si128(diff, mask), mask);
00327   }
00328 #endif
00329   return _mm_cmpgt_epi8(a, b);
00330 }
00331 
00332 struct GroupSse2Impl {
00333   static constexpr size_t kWidth = 16;  // the number of slots per group
00334 
00335   explicit GroupSse2Impl(const ctrl_t* pos) {
00336     ctrl = _mm_loadu_si128(reinterpret_cast<const __m128i*>(pos));
00337   }
00338 
00339   // Returns a bitmask representing the positions of slots that match hash.
00340   BitMask<uint32_t, kWidth> Match(h2_t hash) const {
00341     auto match = _mm_set1_epi8(hash);
00342     return BitMask<uint32_t, kWidth>(
00343         _mm_movemask_epi8(_mm_cmpeq_epi8(match, ctrl)));
00344   }
00345 
00346   // Returns a bitmask representing the positions of empty slots.
00347   BitMask<uint32_t, kWidth> MatchEmpty() const {
00348 #if SWISSTABLE_HAVE_SSSE3
00349     // This only works because kEmpty is -128.
00350     return BitMask<uint32_t, kWidth>(
00351         _mm_movemask_epi8(_mm_sign_epi8(ctrl, ctrl)));
00352 #else
00353     return Match(kEmpty);
00354 #endif
00355   }
00356 
00357   // Returns a bitmask representing the positions of empty or deleted slots.
00358   BitMask<uint32_t, kWidth> MatchEmptyOrDeleted() const {
00359     auto special = _mm_set1_epi8(kSentinel);
00360     return BitMask<uint32_t, kWidth>(
00361         _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)));
00362   }
00363 
00364   // Returns the number of trailing empty or deleted elements in the group.
00365   uint32_t CountLeadingEmptyOrDeleted() const {
00366     auto special = _mm_set1_epi8(kSentinel);
00367     return TrailingZeros(
00368         _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1);
00369   }
00370 
00371   void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {
00372     auto msbs = _mm_set1_epi8(static_cast<char>(-128));
00373     auto x126 = _mm_set1_epi8(126);
00374 #if SWISSTABLE_HAVE_SSSE3
00375     auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs);
00376 #else
00377     auto zero = _mm_setzero_si128();
00378     auto special_mask = _mm_cmpgt_epi8_fixed(zero, ctrl);
00379     auto res = _mm_or_si128(msbs, _mm_andnot_si128(special_mask, x126));
00380 #endif
00381     _mm_storeu_si128(reinterpret_cast<__m128i*>(dst), res);
00382   }
00383 
00384   __m128i ctrl;
00385 };
00386 #endif  // SWISSTABLE_HAVE_SSE2
00387 
00388 struct GroupPortableImpl {
00389   static constexpr size_t kWidth = 8;
00390 
00391   explicit GroupPortableImpl(const ctrl_t* pos)
00392       : ctrl(little_endian::Load64(pos)) {}
00393 
00394   BitMask<uint64_t, kWidth, 3> Match(h2_t hash) const {
00395     // For the technique, see:
00396     // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
00397     // (Determine if a word has a byte equal to n).
00398     //
00399     // Caveat: there are false positives but:
00400     // - they only occur if there is a real match
00401     // - they never occur on kEmpty, kDeleted, kSentinel
00402     // - they will be handled gracefully by subsequent checks in code
00403     //
00404     // Example:
00405     //   v = 0x1716151413121110
00406     //   hash = 0x12
00407     //   retval = (v - lsbs) & ~v & msbs = 0x0000000080800000
00408     constexpr uint64_t msbs = 0x8080808080808080ULL;
00409     constexpr uint64_t lsbs = 0x0101010101010101ULL;
00410     auto x = ctrl ^ (lsbs * hash);
00411     return BitMask<uint64_t, kWidth, 3>((x - lsbs) & ~x & msbs);
00412   }
00413 
00414   BitMask<uint64_t, kWidth, 3> MatchEmpty() const {
00415     constexpr uint64_t msbs = 0x8080808080808080ULL;
00416     return BitMask<uint64_t, kWidth, 3>((ctrl & (~ctrl << 6)) & msbs);
00417   }
00418 
00419   BitMask<uint64_t, kWidth, 3> MatchEmptyOrDeleted() const {
00420     constexpr uint64_t msbs = 0x8080808080808080ULL;
00421     return BitMask<uint64_t, kWidth, 3>((ctrl & (~ctrl << 7)) & msbs);
00422   }
00423 
00424   uint32_t CountLeadingEmptyOrDeleted() const {
00425     constexpr uint64_t gaps = 0x00FEFEFEFEFEFEFEULL;
00426     return (TrailingZeros(((~ctrl & (ctrl >> 7)) | gaps) + 1) + 7) >> 3;
00427   }
00428 
00429   void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {
00430     constexpr uint64_t msbs = 0x8080808080808080ULL;
00431     constexpr uint64_t lsbs = 0x0101010101010101ULL;
00432     auto x = ctrl & msbs;
00433     auto res = (~x + (x >> 7)) & ~lsbs;
00434     little_endian::Store64(dst, res);
00435   }
00436 
00437   uint64_t ctrl;
00438 };
00439 
00440 #if SWISSTABLE_HAVE_SSE2
00441 using Group = GroupSse2Impl;
00442 #else
00443 using Group = GroupPortableImpl;
00444 #endif
00445 
00446 template <class Policy, class Hash, class Eq, class Alloc>
00447 class raw_hash_set;
00448 
00449 inline bool IsValidCapacity(size_t n) { return ((n + 1) & n) == 0 && n > 0; }
00450 
00451 // PRECONDITION:
00452 //   IsValidCapacity(capacity)
00453 //   ctrl[capacity] == kSentinel
00454 //   ctrl[i] != kSentinel for all i < capacity
00455 // Applies mapping for every byte in ctrl:
00456 //   DELETED -> EMPTY
00457 //   EMPTY -> EMPTY
00458 //   FULL -> DELETED
00459 inline void ConvertDeletedToEmptyAndFullToDeleted(
00460     ctrl_t* ctrl, size_t capacity) {
00461   assert(ctrl[capacity] == kSentinel);
00462   assert(IsValidCapacity(capacity));
00463   for (ctrl_t* pos = ctrl; pos != ctrl + capacity + 1; pos += Group::kWidth) {
00464     Group{pos}.ConvertSpecialToEmptyAndFullToDeleted(pos);
00465   }
00466   // Copy the cloned ctrl bytes.
00467   std::memcpy(ctrl + capacity + 1, ctrl, Group::kWidth);
00468   ctrl[capacity] = kSentinel;
00469 }
00470 
00471 // Rounds up the capacity to the next power of 2 minus 1, with a minimum of 1.
00472 inline size_t NormalizeCapacity(size_t n) {
00473   return n ? ~size_t{} >> LeadingZeros(n) : 1;
00474 }
00475 
00476 // We use 7/8th as maximum load factor.
00477 // For 16-wide groups, that gives an average of two empty slots per group.
00478 inline size_t CapacityToGrowth(size_t capacity) {
00479   assert(IsValidCapacity(capacity));
00480   // `capacity*7/8`
00481   if (Group::kWidth == 8 && capacity == 7) {
00482     // x-x/8 does not work when x==7.
00483     return 6;
00484   }
00485   return capacity - capacity / 8;
00486 }
00487 // From desired "growth" to a lowerbound of the necessary capacity.
00488 // Might not be a valid one and required NormalizeCapacity().
00489 inline size_t GrowthToLowerboundCapacity(size_t growth) {
00490   // `growth*8/7`
00491   if (Group::kWidth == 8 && growth == 7) {
00492     // x+(x-1)/7 does not work when x==7.
00493     return 8;
00494   }
00495   return growth + static_cast<size_t>((static_cast<int64_t>(growth) - 1) / 7);
00496 }
00497 
00498 // Policy: a policy defines how to perform different operations on
00499 // the slots of the hashtable (see hash_policy_traits.h for the full interface
00500 // of policy).
00501 //
00502 // Hash: a (possibly polymorphic) functor that hashes keys of the hashtable. The
00503 // functor should accept a key and return size_t as hash. For best performance
00504 // it is important that the hash function provides high entropy across all bits
00505 // of the hash.
00506 //
00507 // Eq: a (possibly polymorphic) functor that compares two keys for equality. It
00508 // should accept two (of possibly different type) keys and return a bool: true
00509 // if they are equal, false if they are not. If two keys compare equal, then
00510 // their hash values as defined by Hash MUST be equal.
00511 //
00512 // Allocator: an Allocator [https://devdocs.io/cpp/concept/allocator] with which
00513 // the storage of the hashtable will be allocated and the elements will be
00514 // constructed and destroyed.
00515 template <class Policy, class Hash, class Eq, class Alloc>
00516 class raw_hash_set {
00517   using PolicyTraits = hash_policy_traits<Policy>;
00518   using KeyArgImpl =
00519       KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
00520 
00521  public:
00522   using init_type = typename PolicyTraits::init_type;
00523   using key_type = typename PolicyTraits::key_type;
00524   // TODO(sbenza): Hide slot_type as it is an implementation detail. Needs user
00525   // code fixes!
00526   using slot_type = typename PolicyTraits::slot_type;
00527   using allocator_type = Alloc;
00528   using size_type = size_t;
00529   using difference_type = ptrdiff_t;
00530   using hasher = Hash;
00531   using key_equal = Eq;
00532   using policy_type = Policy;
00533   using value_type = typename PolicyTraits::value_type;
00534   using reference = value_type&;
00535   using const_reference = const value_type&;
00536   using pointer = typename absl::allocator_traits<
00537       allocator_type>::template rebind_traits<value_type>::pointer;
00538   using const_pointer = typename absl::allocator_traits<
00539       allocator_type>::template rebind_traits<value_type>::const_pointer;
00540 
00541   // Alias used for heterogeneous lookup functions.
00542   // `key_arg<K>` evaluates to `K` when the functors are transparent and to
00543   // `key_type` otherwise. It permits template argument deduction on `K` for the
00544   // transparent case.
00545   template <class K>
00546   using key_arg = typename KeyArgImpl::template type<K, key_type>;
00547 
00548  private:
00549   // Give an early error when key_type is not hashable/eq.
00550   auto KeyTypeCanBeHashed(const Hash& h, const key_type& k) -> decltype(h(k));
00551   auto KeyTypeCanBeEq(const Eq& eq, const key_type& k) -> decltype(eq(k, k));
00552 
00553   using Layout = absl::container_internal::Layout<ctrl_t, slot_type>;
00554 
00555   static Layout MakeLayout(size_t capacity) {
00556     assert(IsValidCapacity(capacity));
00557     return Layout(capacity + Group::kWidth + 1, capacity);
00558   }
00559 
00560   using AllocTraits = absl::allocator_traits<allocator_type>;
00561   using SlotAlloc = typename absl::allocator_traits<
00562       allocator_type>::template rebind_alloc<slot_type>;
00563   using SlotAllocTraits = typename absl::allocator_traits<
00564       allocator_type>::template rebind_traits<slot_type>;
00565 
00566   static_assert(std::is_lvalue_reference<reference>::value,
00567                 "Policy::element() must return a reference");
00568 
00569   template <typename T>
00570   struct SameAsElementReference
00571       : std::is_same<typename std::remove_cv<
00572                          typename std::remove_reference<reference>::type>::type,
00573                      typename std::remove_cv<
00574                          typename std::remove_reference<T>::type>::type> {};
00575 
00576   // An enabler for insert(T&&): T must be convertible to init_type or be the
00577   // same as [cv] value_type [ref].
00578   // Note: we separate SameAsElementReference into its own type to avoid using
00579   // reference unless we need to. MSVC doesn't seem to like it in some
00580   // cases.
00581   template <class T>
00582   using RequiresInsertable = typename std::enable_if<
00583       absl::disjunction<std::is_convertible<T, init_type>,
00584                         SameAsElementReference<T>>::value,
00585       int>::type;
00586 
00587   // RequiresNotInit is a workaround for gcc prior to 7.1.
00588   // See https://godbolt.org/g/Y4xsUh.
00589   template <class T>
00590   using RequiresNotInit =
00591       typename std::enable_if<!std::is_same<T, init_type>::value, int>::type;
00592 
00593   template <class... Ts>
00594   using IsDecomposable = IsDecomposable<void, PolicyTraits, Hash, Eq, Ts...>;
00595 
00596  public:
00597   static_assert(std::is_same<pointer, value_type*>::value,
00598                 "Allocators with custom pointer types are not supported");
00599   static_assert(std::is_same<const_pointer, const value_type*>::value,
00600                 "Allocators with custom pointer types are not supported");
00601 
00602   class iterator {
00603     friend class raw_hash_set;
00604 
00605    public:
00606     using iterator_category = std::forward_iterator_tag;
00607     using value_type = typename raw_hash_set::value_type;
00608     using reference =
00609         absl::conditional_t<PolicyTraits::constant_iterators::value,
00610                             const value_type&, value_type&>;
00611     using pointer = absl::remove_reference_t<reference>*;
00612     using difference_type = typename raw_hash_set::difference_type;
00613 
00614     iterator() {}
00615 
00616     // PRECONDITION: not an end() iterator.
00617     reference operator*() const { return PolicyTraits::element(slot_); }
00618 
00619     // PRECONDITION: not an end() iterator.
00620     pointer operator->() const { return &operator*(); }
00621 
00622     // PRECONDITION: not an end() iterator.
00623     iterator& operator++() {
00624       ++ctrl_;
00625       ++slot_;
00626       skip_empty_or_deleted();
00627       return *this;
00628     }
00629     // PRECONDITION: not an end() iterator.
00630     iterator operator++(int) {
00631       auto tmp = *this;
00632       ++*this;
00633       return tmp;
00634     }
00635 
00636     friend bool operator==(const iterator& a, const iterator& b) {
00637       return a.ctrl_ == b.ctrl_;
00638     }
00639     friend bool operator!=(const iterator& a, const iterator& b) {
00640       return !(a == b);
00641     }
00642 
00643    private:
00644     iterator(ctrl_t* ctrl) : ctrl_(ctrl) {}  // for end()
00645     iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {}
00646 
00647     void skip_empty_or_deleted() {
00648       while (IsEmptyOrDeleted(*ctrl_)) {
00649         // ctrl is not necessarily aligned to Group::kWidth. It is also likely
00650         // to read past the space for ctrl bytes and into slots. This is ok
00651         // because ctrl has sizeof() == 1 and slot has sizeof() >= 1 so there
00652         // is no way to read outside the combined slot array.
00653         uint32_t shift = Group{ctrl_}.CountLeadingEmptyOrDeleted();
00654         ctrl_ += shift;
00655         slot_ += shift;
00656       }
00657     }
00658 
00659     ctrl_t* ctrl_ = nullptr;
00660     // To avoid uninitialized member warnigs, put slot_ in an anonymous union.
00661     // The member is not initialized on singleton and end iterators.
00662     union {
00663       slot_type* slot_;
00664     };
00665   };
00666 
00667   class const_iterator {
00668     friend class raw_hash_set;
00669 
00670    public:
00671     using iterator_category = typename iterator::iterator_category;
00672     using value_type = typename raw_hash_set::value_type;
00673     using reference = typename raw_hash_set::const_reference;
00674     using pointer = typename raw_hash_set::const_pointer;
00675     using difference_type = typename raw_hash_set::difference_type;
00676 
00677     const_iterator() {}
00678     // Implicit construction from iterator.
00679     const_iterator(iterator i) : inner_(std::move(i)) {}
00680 
00681     reference operator*() const { return *inner_; }
00682     pointer operator->() const { return inner_.operator->(); }
00683 
00684     const_iterator& operator++() {
00685       ++inner_;
00686       return *this;
00687     }
00688     const_iterator operator++(int) { return inner_++; }
00689 
00690     friend bool operator==(const const_iterator& a, const const_iterator& b) {
00691       return a.inner_ == b.inner_;
00692     }
00693     friend bool operator!=(const const_iterator& a, const const_iterator& b) {
00694       return !(a == b);
00695     }
00696 
00697    private:
00698     const_iterator(const ctrl_t* ctrl, const slot_type* slot)
00699         : inner_(const_cast<ctrl_t*>(ctrl), const_cast<slot_type*>(slot)) {}
00700 
00701     iterator inner_;
00702   };
00703 
00704   using node_type = node_handle<Policy, hash_policy_traits<Policy>, Alloc>;
00705   using insert_return_type = InsertReturnType<iterator, node_type>;
00706 
00707   raw_hash_set() noexcept(
00708       std::is_nothrow_default_constructible<hasher>::value&&
00709           std::is_nothrow_default_constructible<key_equal>::value&&
00710               std::is_nothrow_default_constructible<allocator_type>::value) {}
00711 
00712   explicit raw_hash_set(size_t bucket_count, const hasher& hash = hasher(),
00713                         const key_equal& eq = key_equal(),
00714                         const allocator_type& alloc = allocator_type())
00715       : ctrl_(EmptyGroup()), settings_(0, hash, eq, alloc) {
00716     if (bucket_count) {
00717       capacity_ = NormalizeCapacity(bucket_count);
00718       reset_growth_left();
00719       initialize_slots();
00720     }
00721   }
00722 
00723   raw_hash_set(size_t bucket_count, const hasher& hash,
00724                const allocator_type& alloc)
00725       : raw_hash_set(bucket_count, hash, key_equal(), alloc) {}
00726 
00727   raw_hash_set(size_t bucket_count, const allocator_type& alloc)
00728       : raw_hash_set(bucket_count, hasher(), key_equal(), alloc) {}
00729 
00730   explicit raw_hash_set(const allocator_type& alloc)
00731       : raw_hash_set(0, hasher(), key_equal(), alloc) {}
00732 
00733   template <class InputIter>
00734   raw_hash_set(InputIter first, InputIter last, size_t bucket_count = 0,
00735                const hasher& hash = hasher(), const key_equal& eq = key_equal(),
00736                const allocator_type& alloc = allocator_type())
00737       : raw_hash_set(bucket_count, hash, eq, alloc) {
00738     insert(first, last);
00739   }
00740 
00741   template <class InputIter>
00742   raw_hash_set(InputIter first, InputIter last, size_t bucket_count,
00743                const hasher& hash, const allocator_type& alloc)
00744       : raw_hash_set(first, last, bucket_count, hash, key_equal(), alloc) {}
00745 
00746   template <class InputIter>
00747   raw_hash_set(InputIter first, InputIter last, size_t bucket_count,
00748                const allocator_type& alloc)
00749       : raw_hash_set(first, last, bucket_count, hasher(), key_equal(), alloc) {}
00750 
00751   template <class InputIter>
00752   raw_hash_set(InputIter first, InputIter last, const allocator_type& alloc)
00753       : raw_hash_set(first, last, 0, hasher(), key_equal(), alloc) {}
00754 
00755   // Instead of accepting std::initializer_list<value_type> as the first
00756   // argument like std::unordered_set<value_type> does, we have two overloads
00757   // that accept std::initializer_list<T> and std::initializer_list<init_type>.
00758   // This is advantageous for performance.
00759   //
00760   //   // Turns {"abc", "def"} into std::initializer_list<std::string>, then
00761   //   // copies the strings into the set.
00762   //   std::unordered_set<std::string> s = {"abc", "def"};
00763   //
00764   //   // Turns {"abc", "def"} into std::initializer_list<const char*>, then
00765   //   // copies the strings into the set.
00766   //   absl::flat_hash_set<std::string> s = {"abc", "def"};
00767   //
00768   // The same trick is used in insert().
00769   //
00770   // The enabler is necessary to prevent this constructor from triggering where
00771   // the copy constructor is meant to be called.
00772   //
00773   //   absl::flat_hash_set<int> a, b{a};
00774   //
00775   // RequiresNotInit<T> is a workaround for gcc prior to 7.1.
00776   template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
00777   raw_hash_set(std::initializer_list<T> init, size_t bucket_count = 0,
00778                const hasher& hash = hasher(), const key_equal& eq = key_equal(),
00779                const allocator_type& alloc = allocator_type())
00780       : raw_hash_set(init.begin(), init.end(), bucket_count, hash, eq, alloc) {}
00781 
00782   raw_hash_set(std::initializer_list<init_type> init, size_t bucket_count = 0,
00783                const hasher& hash = hasher(), const key_equal& eq = key_equal(),
00784                const allocator_type& alloc = allocator_type())
00785       : raw_hash_set(init.begin(), init.end(), bucket_count, hash, eq, alloc) {}
00786 
00787   template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
00788   raw_hash_set(std::initializer_list<T> init, size_t bucket_count,
00789                const hasher& hash, const allocator_type& alloc)
00790       : raw_hash_set(init, bucket_count, hash, key_equal(), alloc) {}
00791 
00792   raw_hash_set(std::initializer_list<init_type> init, size_t bucket_count,
00793                const hasher& hash, const allocator_type& alloc)
00794       : raw_hash_set(init, bucket_count, hash, key_equal(), alloc) {}
00795 
00796   template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
00797   raw_hash_set(std::initializer_list<T> init, size_t bucket_count,
00798                const allocator_type& alloc)
00799       : raw_hash_set(init, bucket_count, hasher(), key_equal(), alloc) {}
00800 
00801   raw_hash_set(std::initializer_list<init_type> init, size_t bucket_count,
00802                const allocator_type& alloc)
00803       : raw_hash_set(init, bucket_count, hasher(), key_equal(), alloc) {}
00804 
00805   template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
00806   raw_hash_set(std::initializer_list<T> init, const allocator_type& alloc)
00807       : raw_hash_set(init, 0, hasher(), key_equal(), alloc) {}
00808 
00809   raw_hash_set(std::initializer_list<init_type> init,
00810                const allocator_type& alloc)
00811       : raw_hash_set(init, 0, hasher(), key_equal(), alloc) {}
00812 
00813   raw_hash_set(const raw_hash_set& that)
00814       : raw_hash_set(that, AllocTraits::select_on_container_copy_construction(
00815                                that.alloc_ref())) {}
00816 
00817   raw_hash_set(const raw_hash_set& that, const allocator_type& a)
00818       : raw_hash_set(0, that.hash_ref(), that.eq_ref(), a) {
00819     reserve(that.size());
00820     // Because the table is guaranteed to be empty, we can do something faster
00821     // than a full `insert`.
00822     for (const auto& v : that) {
00823       const size_t hash = PolicyTraits::apply(HashElement{hash_ref()}, v);
00824       auto target = find_first_non_full(hash);
00825       set_ctrl(target.offset, H2(hash));
00826       emplace_at(target.offset, v);
00827       infoz_.RecordInsert(hash, target.probe_length);
00828     }
00829     size_ = that.size();
00830     growth_left() -= that.size();
00831   }
00832 
00833   raw_hash_set(raw_hash_set&& that) noexcept(
00834       std::is_nothrow_copy_constructible<hasher>::value&&
00835           std::is_nothrow_copy_constructible<key_equal>::value&&
00836               std::is_nothrow_copy_constructible<allocator_type>::value)
00837       : ctrl_(absl::exchange(that.ctrl_, EmptyGroup())),
00838         slots_(absl::exchange(that.slots_, nullptr)),
00839         size_(absl::exchange(that.size_, 0)),
00840         capacity_(absl::exchange(that.capacity_, 0)),
00841         infoz_(absl::exchange(that.infoz_, HashtablezInfoHandle())),
00842         // Hash, equality and allocator are copied instead of moved because
00843         // `that` must be left valid. If Hash is std::function<Key>, moving it
00844         // would create a nullptr functor that cannot be called.
00845         settings_(that.settings_) {
00846     // growth_left was copied above, reset the one from `that`.
00847     that.growth_left() = 0;
00848   }
00849 
00850   raw_hash_set(raw_hash_set&& that, const allocator_type& a)
00851       : ctrl_(EmptyGroup()),
00852         slots_(nullptr),
00853         size_(0),
00854         capacity_(0),
00855         settings_(0, that.hash_ref(), that.eq_ref(), a) {
00856     if (a == that.alloc_ref()) {
00857       std::swap(ctrl_, that.ctrl_);
00858       std::swap(slots_, that.slots_);
00859       std::swap(size_, that.size_);
00860       std::swap(capacity_, that.capacity_);
00861       std::swap(growth_left(), that.growth_left());
00862       std::swap(infoz_, that.infoz_);
00863     } else {
00864       reserve(that.size());
00865       // Note: this will copy elements of dense_set and unordered_set instead of
00866       // moving them. This can be fixed if it ever becomes an issue.
00867       for (auto& elem : that) insert(std::move(elem));
00868     }
00869   }
00870 
00871   raw_hash_set& operator=(const raw_hash_set& that) {
00872     raw_hash_set tmp(that,
00873                      AllocTraits::propagate_on_container_copy_assignment::value
00874                          ? that.alloc_ref()
00875                          : alloc_ref());
00876     swap(tmp);
00877     return *this;
00878   }
00879 
00880   raw_hash_set& operator=(raw_hash_set&& that) noexcept(
00881       absl::allocator_traits<allocator_type>::is_always_equal::value&&
00882           std::is_nothrow_move_assignable<hasher>::value&&
00883               std::is_nothrow_move_assignable<key_equal>::value) {
00884     // TODO(sbenza): We should only use the operations from the noexcept clause
00885     // to make sure we actually adhere to that contract.
00886     return move_assign(
00887         std::move(that),
00888         typename AllocTraits::propagate_on_container_move_assignment());
00889   }
00890 
00891   ~raw_hash_set() { destroy_slots(); }
00892 
00893   iterator begin() {
00894     auto it = iterator_at(0);
00895     it.skip_empty_or_deleted();
00896     return it;
00897   }
00898   iterator end() { return {ctrl_ + capacity_}; }
00899 
00900   const_iterator begin() const {
00901     return const_cast<raw_hash_set*>(this)->begin();
00902   }
00903   const_iterator end() const { return const_cast<raw_hash_set*>(this)->end(); }
00904   const_iterator cbegin() const { return begin(); }
00905   const_iterator cend() const { return end(); }
00906 
00907   bool empty() const { return !size(); }
00908   size_t size() const { return size_; }
00909   size_t capacity() const { return capacity_; }
00910   size_t max_size() const { return (std::numeric_limits<size_t>::max)(); }
00911 
00912   ABSL_ATTRIBUTE_REINITIALIZES void clear() {
00913     // Iterating over this container is O(bucket_count()). When bucket_count()
00914     // is much greater than size(), iteration becomes prohibitively expensive.
00915     // For clear() it is more important to reuse the allocated array when the
00916     // container is small because allocation takes comparatively long time
00917     // compared to destruction of the elements of the container. So we pick the
00918     // largest bucket_count() threshold for which iteration is still fast and
00919     // past that we simply deallocate the array.
00920     if (capacity_ > 127) {
00921       destroy_slots();
00922     } else if (capacity_) {
00923       for (size_t i = 0; i != capacity_; ++i) {
00924         if (IsFull(ctrl_[i])) {
00925           PolicyTraits::destroy(&alloc_ref(), slots_ + i);
00926         }
00927       }
00928       size_ = 0;
00929       reset_ctrl();
00930       reset_growth_left();
00931     }
00932     assert(empty());
00933     infoz_.RecordStorageChanged(0, capacity_);
00934   }
00935 
00936   // This overload kicks in when the argument is an rvalue of insertable and
00937   // decomposable type other than init_type.
00938   //
00939   //   flat_hash_map<std::string, int> m;
00940   //   m.insert(std::make_pair("abc", 42));
00941   template <class T, RequiresInsertable<T> = 0,
00942             typename std::enable_if<IsDecomposable<T>::value, int>::type = 0,
00943             T* = nullptr>
00944   std::pair<iterator, bool> insert(T&& value) {
00945     return emplace(std::forward<T>(value));
00946   }
00947 
00948   // This overload kicks in when the argument is a bitfield or an lvalue of
00949   // insertable and decomposable type.
00950   //
00951   //   union { int n : 1; };
00952   //   flat_hash_set<int> s;
00953   //   s.insert(n);
00954   //
00955   //   flat_hash_set<std::string> s;
00956   //   const char* p = "hello";
00957   //   s.insert(p);
00958   //
00959   // TODO(romanp): Once we stop supporting gcc 5.1 and below, replace
00960   // RequiresInsertable<T> with RequiresInsertable<const T&>.
00961   // We are hitting this bug: https://godbolt.org/g/1Vht4f.
00962   template <
00963       class T, RequiresInsertable<T> = 0,
00964       typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
00965   std::pair<iterator, bool> insert(const T& value) {
00966     return emplace(value);
00967   }
00968 
00969   // This overload kicks in when the argument is an rvalue of init_type. Its
00970   // purpose is to handle brace-init-list arguments.
00971   //
00972   //   flat_hash_map<std::string, int> s;
00973   //   s.insert({"abc", 42});
00974   std::pair<iterator, bool> insert(init_type&& value) {
00975     return emplace(std::move(value));
00976   }
00977 
00978   template <class T, RequiresInsertable<T> = 0,
00979             typename std::enable_if<IsDecomposable<T>::value, int>::type = 0,
00980             T* = nullptr>
00981   iterator insert(const_iterator, T&& value) {
00982     return insert(std::forward<T>(value)).first;
00983   }
00984 
00985   // TODO(romanp): Once we stop supporting gcc 5.1 and below, replace
00986   // RequiresInsertable<T> with RequiresInsertable<const T&>.
00987   // We are hitting this bug: https://godbolt.org/g/1Vht4f.
00988   template <
00989       class T, RequiresInsertable<T> = 0,
00990       typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
00991   iterator insert(const_iterator, const T& value) {
00992     return insert(value).first;
00993   }
00994 
00995   iterator insert(const_iterator, init_type&& value) {
00996     return insert(std::move(value)).first;
00997   }
00998 
00999   template <class InputIt>
01000   void insert(InputIt first, InputIt last) {
01001     for (; first != last; ++first) insert(*first);
01002   }
01003 
01004   template <class T, RequiresNotInit<T> = 0, RequiresInsertable<const T&> = 0>
01005   void insert(std::initializer_list<T> ilist) {
01006     insert(ilist.begin(), ilist.end());
01007   }
01008 
01009   void insert(std::initializer_list<init_type> ilist) {
01010     insert(ilist.begin(), ilist.end());
01011   }
01012 
01013   insert_return_type insert(node_type&& node) {
01014     if (!node) return {end(), false, node_type()};
01015     const auto& elem = PolicyTraits::element(CommonAccess::GetSlot(node));
01016     auto res = PolicyTraits::apply(
01017         InsertSlot<false>{*this, std::move(*CommonAccess::GetSlot(node))},
01018         elem);
01019     if (res.second) {
01020       CommonAccess::Reset(&node);
01021       return {res.first, true, node_type()};
01022     } else {
01023       return {res.first, false, std::move(node)};
01024     }
01025   }
01026 
01027   iterator insert(const_iterator, node_type&& node) {
01028     return insert(std::move(node)).first;
01029   }
01030 
01031   // This overload kicks in if we can deduce the key from args. This enables us
01032   // to avoid constructing value_type if an entry with the same key already
01033   // exists.
01034   //
01035   // For example:
01036   //
01037   //   flat_hash_map<std::string, std::string> m = {{"abc", "def"}};
01038   //   // Creates no std::string copies and makes no heap allocations.
01039   //   m.emplace("abc", "xyz");
01040   template <class... Args, typename std::enable_if<
01041                                IsDecomposable<Args...>::value, int>::type = 0>
01042   std::pair<iterator, bool> emplace(Args&&... args) {
01043     return PolicyTraits::apply(EmplaceDecomposable{*this},
01044                                std::forward<Args>(args)...);
01045   }
01046 
01047   // This overload kicks in if we cannot deduce the key from args. It constructs
01048   // value_type unconditionally and then either moves it into the table or
01049   // destroys.
01050   template <class... Args, typename std::enable_if<
01051                                !IsDecomposable<Args...>::value, int>::type = 0>
01052   std::pair<iterator, bool> emplace(Args&&... args) {
01053     typename std::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type
01054         raw;
01055     slot_type* slot = reinterpret_cast<slot_type*>(&raw);
01056 
01057     PolicyTraits::construct(&alloc_ref(), slot, std::forward<Args>(args)...);
01058     const auto& elem = PolicyTraits::element(slot);
01059     return PolicyTraits::apply(InsertSlot<true>{*this, std::move(*slot)}, elem);
01060   }
01061 
01062   template <class... Args>
01063   iterator emplace_hint(const_iterator, Args&&... args) {
01064     return emplace(std::forward<Args>(args)...).first;
01065   }
01066 
01067   // Extension API: support for lazy emplace.
01068   //
01069   // Looks up key in the table. If found, returns the iterator to the element.
01070   // Otherwise calls f with one argument of type raw_hash_set::constructor. f
01071   // MUST call raw_hash_set::constructor with arguments as if a
01072   // raw_hash_set::value_type is constructed, otherwise the behavior is
01073   // undefined.
01074   //
01075   // For example:
01076   //
01077   //   std::unordered_set<ArenaString> s;
01078   //   // Makes ArenaStr even if "abc" is in the map.
01079   //   s.insert(ArenaString(&arena, "abc"));
01080   //
01081   //   flat_hash_set<ArenaStr> s;
01082   //   // Makes ArenaStr only if "abc" is not in the map.
01083   //   s.lazy_emplace("abc", [&](const constructor& ctor) {
01084   //     ctor(&arena, "abc");
01085   //   });
01086   //
01087   // WARNING: This API is currently experimental. If there is a way to implement
01088   // the same thing with the rest of the API, prefer that.
01089   class constructor {
01090     friend class raw_hash_set;
01091 
01092    public:
01093     template <class... Args>
01094     void operator()(Args&&... args) const {
01095       assert(*slot_);
01096       PolicyTraits::construct(alloc_, *slot_, std::forward<Args>(args)...);
01097       *slot_ = nullptr;
01098     }
01099 
01100    private:
01101     constructor(allocator_type* a, slot_type** slot) : alloc_(a), slot_(slot) {}
01102 
01103     allocator_type* alloc_;
01104     slot_type** slot_;
01105   };
01106 
01107   template <class K = key_type, class F>
01108   iterator lazy_emplace(const key_arg<K>& key, F&& f) {
01109     auto res = find_or_prepare_insert(key);
01110     if (res.second) {
01111       slot_type* slot = slots_ + res.first;
01112       std::forward<F>(f)(constructor(&alloc_ref(), &slot));
01113       assert(!slot);
01114     }
01115     return iterator_at(res.first);
01116   }
01117 
01118   // Extension API: support for heterogeneous keys.
01119   //
01120   //   std::unordered_set<std::string> s;
01121   //   // Turns "abc" into std::string.
01122   //   s.erase("abc");
01123   //
01124   //   flat_hash_set<std::string> s;
01125   //   // Uses "abc" directly without copying it into std::string.
01126   //   s.erase("abc");
01127   template <class K = key_type>
01128   size_type erase(const key_arg<K>& key) {
01129     auto it = find(key);
01130     if (it == end()) return 0;
01131     erase(it);
01132     return 1;
01133   }
01134 
01135   // Erases the element pointed to by `it`.  Unlike `std::unordered_set::erase`,
01136   // this method returns void to reduce algorithmic complexity to O(1).  In
01137   // order to erase while iterating across a map, use the following idiom (which
01138   // also works for standard containers):
01139   //
01140   // for (auto it = m.begin(), end = m.end(); it != end;) {
01141   //   if (<pred>) {
01142   //     m.erase(it++);
01143   //   } else {
01144   //     ++it;
01145   //   }
01146   // }
01147   void erase(const_iterator cit) { erase(cit.inner_); }
01148 
01149   // This overload is necessary because otherwise erase<K>(const K&) would be
01150   // a better match if non-const iterator is passed as an argument.
01151   void erase(iterator it) {
01152     assert(it != end());
01153     PolicyTraits::destroy(&alloc_ref(), it.slot_);
01154     erase_meta_only(it);
01155   }
01156 
01157   iterator erase(const_iterator first, const_iterator last) {
01158     while (first != last) {
01159       erase(first++);
01160     }
01161     return last.inner_;
01162   }
01163 
01164   // Moves elements from `src` into `this`.
01165   // If the element already exists in `this`, it is left unmodified in `src`.
01166   template <typename H, typename E>
01167   void merge(raw_hash_set<Policy, H, E, Alloc>& src) {  // NOLINT
01168     assert(this != &src);
01169     for (auto it = src.begin(), e = src.end(); it != e; ++it) {
01170       if (PolicyTraits::apply(InsertSlot<false>{*this, std::move(*it.slot_)},
01171                               PolicyTraits::element(it.slot_))
01172               .second) {
01173         src.erase_meta_only(it);
01174       }
01175     }
01176   }
01177 
01178   template <typename H, typename E>
01179   void merge(raw_hash_set<Policy, H, E, Alloc>&& src) {
01180     merge(src);
01181   }
01182 
01183   node_type extract(const_iterator position) {
01184     auto node =
01185         CommonAccess::Make<node_type>(alloc_ref(), position.inner_.slot_);
01186     erase_meta_only(position);
01187     return node;
01188   }
01189 
01190   template <
01191       class K = key_type,
01192       typename std::enable_if<!std::is_same<K, iterator>::value, int>::type = 0>
01193   node_type extract(const key_arg<K>& key) {
01194     auto it = find(key);
01195     return it == end() ? node_type() : extract(const_iterator{it});
01196   }
01197 
01198   void swap(raw_hash_set& that) noexcept(
01199       IsNoThrowSwappable<hasher>() && IsNoThrowSwappable<key_equal>() &&
01200       (!AllocTraits::propagate_on_container_swap::value ||
01201        IsNoThrowSwappable<allocator_type>())) {
01202     using std::swap;
01203     swap(ctrl_, that.ctrl_);
01204     swap(slots_, that.slots_);
01205     swap(size_, that.size_);
01206     swap(capacity_, that.capacity_);
01207     swap(growth_left(), that.growth_left());
01208     swap(hash_ref(), that.hash_ref());
01209     swap(eq_ref(), that.eq_ref());
01210     swap(infoz_, that.infoz_);
01211     if (AllocTraits::propagate_on_container_swap::value) {
01212       swap(alloc_ref(), that.alloc_ref());
01213     } else {
01214       // If the allocators do not compare equal it is officially undefined
01215       // behavior. We choose to do nothing.
01216     }
01217   }
01218 
01219   void rehash(size_t n) {
01220     if (n == 0 && capacity_ == 0) return;
01221     if (n == 0 && size_ == 0) {
01222       destroy_slots();
01223       infoz_.RecordStorageChanged(0, 0);
01224       return;
01225     }
01226     // bitor is a faster way of doing `max` here. We will round up to the next
01227     // power-of-2-minus-1, so bitor is good enough.
01228     auto m = NormalizeCapacity(n | GrowthToLowerboundCapacity(size()));
01229     // n == 0 unconditionally rehashes as per the standard.
01230     if (n == 0 || m > capacity_) {
01231       resize(m);
01232     }
01233   }
01234 
01235   void reserve(size_t n) { rehash(GrowthToLowerboundCapacity(n)); }
01236 
01237   // Extension API: support for heterogeneous keys.
01238   //
01239   //   std::unordered_set<std::string> s;
01240   //   // Turns "abc" into std::string.
01241   //   s.count("abc");
01242   //
01243   //   ch_set<std::string> s;
01244   //   // Uses "abc" directly without copying it into std::string.
01245   //   s.count("abc");
01246   template <class K = key_type>
01247   size_t count(const key_arg<K>& key) const {
01248     return find(key) == end() ? 0 : 1;
01249   }
01250 
01251   // Issues CPU prefetch instructions for the memory needed to find or insert
01252   // a key.  Like all lookup functions, this support heterogeneous keys.
01253   //
01254   // NOTE: This is a very low level operation and should not be used without
01255   // specific benchmarks indicating its importance.
01256   template <class K = key_type>
01257   void prefetch(const key_arg<K>& key) const {
01258     (void)key;
01259 #if defined(__GNUC__)
01260     auto seq = probe(hash_ref()(key));
01261     __builtin_prefetch(static_cast<const void*>(ctrl_ + seq.offset()));
01262     __builtin_prefetch(static_cast<const void*>(slots_ + seq.offset()));
01263 #endif  // __GNUC__
01264   }
01265 
01266   // The API of find() has two extensions.
01267   //
01268   // 1. The hash can be passed by the user. It must be equal to the hash of the
01269   // key.
01270   //
01271   // 2. The type of the key argument doesn't have to be key_type. This is so
01272   // called heterogeneous key support.
01273   template <class K = key_type>
01274   iterator find(const key_arg<K>& key, size_t hash) {
01275     auto seq = probe(hash);
01276     while (true) {
01277       Group g{ctrl_ + seq.offset()};
01278       for (int i : g.Match(H2(hash))) {
01279         if (ABSL_PREDICT_TRUE(PolicyTraits::apply(
01280                 EqualElement<K>{key, eq_ref()},
01281                 PolicyTraits::element(slots_ + seq.offset(i)))))
01282           return iterator_at(seq.offset(i));
01283       }
01284       if (ABSL_PREDICT_TRUE(g.MatchEmpty())) return end();
01285       seq.next();
01286     }
01287   }
01288   template <class K = key_type>
01289   iterator find(const key_arg<K>& key) {
01290     return find(key, hash_ref()(key));
01291   }
01292 
01293   template <class K = key_type>
01294   const_iterator find(const key_arg<K>& key, size_t hash) const {
01295     return const_cast<raw_hash_set*>(this)->find(key, hash);
01296   }
01297   template <class K = key_type>
01298   const_iterator find(const key_arg<K>& key) const {
01299     return find(key, hash_ref()(key));
01300   }
01301 
01302   template <class K = key_type>
01303   bool contains(const key_arg<K>& key) const {
01304     return find(key) != end();
01305   }
01306 
01307   template <class K = key_type>
01308   std::pair<iterator, iterator> equal_range(const key_arg<K>& key) {
01309     auto it = find(key);
01310     if (it != end()) return {it, std::next(it)};
01311     return {it, it};
01312   }
01313   template <class K = key_type>
01314   std::pair<const_iterator, const_iterator> equal_range(
01315       const key_arg<K>& key) const {
01316     auto it = find(key);
01317     if (it != end()) return {it, std::next(it)};
01318     return {it, it};
01319   }
01320 
01321   size_t bucket_count() const { return capacity_; }
01322   float load_factor() const {
01323     return capacity_ ? static_cast<double>(size()) / capacity_ : 0.0;
01324   }
01325   float max_load_factor() const { return 1.0f; }
01326   void max_load_factor(float) {
01327     // Does nothing.
01328   }
01329 
01330   hasher hash_function() const { return hash_ref(); }
01331   key_equal key_eq() const { return eq_ref(); }
01332   allocator_type get_allocator() const { return alloc_ref(); }
01333 
01334   friend bool operator==(const raw_hash_set& a, const raw_hash_set& b) {
01335     if (a.size() != b.size()) return false;
01336     const raw_hash_set* outer = &a;
01337     const raw_hash_set* inner = &b;
01338     if (outer->capacity() > inner->capacity()) std::swap(outer, inner);
01339     for (const value_type& elem : *outer)
01340       if (!inner->has_element(elem)) return false;
01341     return true;
01342   }
01343 
01344   friend bool operator!=(const raw_hash_set& a, const raw_hash_set& b) {
01345     return !(a == b);
01346   }
01347 
01348   friend void swap(raw_hash_set& a,
01349                    raw_hash_set& b) noexcept(noexcept(a.swap(b))) {
01350     a.swap(b);
01351   }
01352 
01353  private:
01354   template <class Container, typename Enabler>
01355   friend struct absl::container_internal::hashtable_debug_internal::
01356       HashtableDebugAccess;
01357 
01358   struct FindElement {
01359     template <class K, class... Args>
01360     const_iterator operator()(const K& key, Args&&...) const {
01361       return s.find(key);
01362     }
01363     const raw_hash_set& s;
01364   };
01365 
01366   struct HashElement {
01367     template <class K, class... Args>
01368     size_t operator()(const K& key, Args&&...) const {
01369       return h(key);
01370     }
01371     const hasher& h;
01372   };
01373 
01374   template <class K1>
01375   struct EqualElement {
01376     template <class K2, class... Args>
01377     bool operator()(const K2& lhs, Args&&...) const {
01378       return eq(lhs, rhs);
01379     }
01380     const K1& rhs;
01381     const key_equal& eq;
01382   };
01383 
01384   struct EmplaceDecomposable {
01385     template <class K, class... Args>
01386     std::pair<iterator, bool> operator()(const K& key, Args&&... args) const {
01387       auto res = s.find_or_prepare_insert(key);
01388       if (res.second) {
01389         s.emplace_at(res.first, std::forward<Args>(args)...);
01390       }
01391       return {s.iterator_at(res.first), res.second};
01392     }
01393     raw_hash_set& s;
01394   };
01395 
01396   template <bool do_destroy>
01397   struct InsertSlot {
01398     template <class K, class... Args>
01399     std::pair<iterator, bool> operator()(const K& key, Args&&...) && {
01400       auto res = s.find_or_prepare_insert(key);
01401       if (res.second) {
01402         PolicyTraits::transfer(&s.alloc_ref(), s.slots_ + res.first, &slot);
01403       } else if (do_destroy) {
01404         PolicyTraits::destroy(&s.alloc_ref(), &slot);
01405       }
01406       return {s.iterator_at(res.first), res.second};
01407     }
01408     raw_hash_set& s;
01409     // Constructed slot. Either moved into place or destroyed.
01410     slot_type&& slot;
01411   };
01412 
01413   // "erases" the object from the container, except that it doesn't actually
01414   // destroy the object. It only updates all the metadata of the class.
01415   // This can be used in conjunction with Policy::transfer to move the object to
01416   // another place.
01417   void erase_meta_only(const_iterator it) {
01418     assert(IsFull(*it.inner_.ctrl_) && "erasing a dangling iterator");
01419     --size_;
01420     const size_t index = it.inner_.ctrl_ - ctrl_;
01421     const size_t index_before = (index - Group::kWidth) & capacity_;
01422     const auto empty_after = Group(it.inner_.ctrl_).MatchEmpty();
01423     const auto empty_before = Group(ctrl_ + index_before).MatchEmpty();
01424 
01425     // We count how many consecutive non empties we have to the right and to the
01426     // left of `it`. If the sum is >= kWidth then there is at least one probe
01427     // window that might have seen a full group.
01428     bool was_never_full =
01429         empty_before && empty_after &&
01430         static_cast<size_t>(empty_after.TrailingZeros() +
01431                             empty_before.LeadingZeros()) < Group::kWidth;
01432 
01433     set_ctrl(index, was_never_full ? kEmpty : kDeleted);
01434     growth_left() += was_never_full;
01435     infoz_.RecordErase();
01436   }
01437 
01438   void initialize_slots() {
01439     assert(capacity_);
01440     // Folks with custom allocators often make unwarranted assumptions about the
01441     // behavior of their classes vis-a-vis trivial destructability and what
01442     // calls they will or wont make.  Avoid sampling for people with custom
01443     // allocators to get us out of this mess.  This is not a hard guarantee but
01444     // a workaround while we plan the exact guarantee we want to provide.
01445     //
01446     // People are often sloppy with the exact type of their allocator (sometimes
01447     // it has an extra const or is missing the pair, but rebinds made it work
01448     // anyway).  To avoid the ambiguity, we work off SlotAlloc which we have
01449     // bound more carefully.
01450     if (std::is_same<SlotAlloc, std::allocator<slot_type>>::value &&
01451         slots_ == nullptr) {
01452       infoz_ = Sample();
01453     }
01454 
01455     auto layout = MakeLayout(capacity_);
01456     char* mem = static_cast<char*>(
01457         Allocate<Layout::Alignment()>(&alloc_ref(), layout.AllocSize()));
01458     ctrl_ = reinterpret_cast<ctrl_t*>(layout.template Pointer<0>(mem));
01459     slots_ = layout.template Pointer<1>(mem);
01460     reset_ctrl();
01461     reset_growth_left();
01462     infoz_.RecordStorageChanged(size_, capacity_);
01463   }
01464 
01465   void destroy_slots() {
01466     if (!capacity_) return;
01467     for (size_t i = 0; i != capacity_; ++i) {
01468       if (IsFull(ctrl_[i])) {
01469         PolicyTraits::destroy(&alloc_ref(), slots_ + i);
01470       }
01471     }
01472     auto layout = MakeLayout(capacity_);
01473     // Unpoison before returning the memory to the allocator.
01474     SanitizerUnpoisonMemoryRegion(slots_, sizeof(slot_type) * capacity_);
01475     Deallocate<Layout::Alignment()>(&alloc_ref(), ctrl_, layout.AllocSize());
01476     ctrl_ = EmptyGroup();
01477     slots_ = nullptr;
01478     size_ = 0;
01479     capacity_ = 0;
01480     growth_left() = 0;
01481   }
01482 
01483   void resize(size_t new_capacity) {
01484     assert(IsValidCapacity(new_capacity));
01485     auto* old_ctrl = ctrl_;
01486     auto* old_slots = slots_;
01487     const size_t old_capacity = capacity_;
01488     capacity_ = new_capacity;
01489     initialize_slots();
01490 
01491     size_t total_probe_length = 0;
01492     for (size_t i = 0; i != old_capacity; ++i) {
01493       if (IsFull(old_ctrl[i])) {
01494         size_t hash = PolicyTraits::apply(HashElement{hash_ref()},
01495                                           PolicyTraits::element(old_slots + i));
01496         auto target = find_first_non_full(hash);
01497         size_t new_i = target.offset;
01498         total_probe_length += target.probe_length;
01499         set_ctrl(new_i, H2(hash));
01500         PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, old_slots + i);
01501       }
01502     }
01503     if (old_capacity) {
01504       SanitizerUnpoisonMemoryRegion(old_slots,
01505                                     sizeof(slot_type) * old_capacity);
01506       auto layout = MakeLayout(old_capacity);
01507       Deallocate<Layout::Alignment()>(&alloc_ref(), old_ctrl,
01508                                       layout.AllocSize());
01509     }
01510     infoz_.RecordRehash(total_probe_length);
01511   }
01512 
01513   void drop_deletes_without_resize() ABSL_ATTRIBUTE_NOINLINE {
01514     assert(IsValidCapacity(capacity_));
01515     assert(!is_small());
01516     // Algorithm:
01517     // - mark all DELETED slots as EMPTY
01518     // - mark all FULL slots as DELETED
01519     // - for each slot marked as DELETED
01520     //     hash = Hash(element)
01521     //     target = find_first_non_full(hash)
01522     //     if target is in the same group
01523     //       mark slot as FULL
01524     //     else if target is EMPTY
01525     //       transfer element to target
01526     //       mark slot as EMPTY
01527     //       mark target as FULL
01528     //     else if target is DELETED
01529     //       swap current element with target element
01530     //       mark target as FULL
01531     //       repeat procedure for current slot with moved from element (target)
01532     ConvertDeletedToEmptyAndFullToDeleted(ctrl_, capacity_);
01533     typename std::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type
01534         raw;
01535     size_t total_probe_length = 0;
01536     slot_type* slot = reinterpret_cast<slot_type*>(&raw);
01537     for (size_t i = 0; i != capacity_; ++i) {
01538       if (!IsDeleted(ctrl_[i])) continue;
01539       size_t hash = PolicyTraits::apply(HashElement{hash_ref()},
01540                                         PolicyTraits::element(slots_ + i));
01541       auto target = find_first_non_full(hash);
01542       size_t new_i = target.offset;
01543       total_probe_length += target.probe_length;
01544 
01545       // Verify if the old and new i fall within the same group wrt the hash.
01546       // If they do, we don't need to move the object as it falls already in the
01547       // best probe we can.
01548       const auto probe_index = [&](size_t pos) {
01549         return ((pos - probe(hash).offset()) & capacity_) / Group::kWidth;
01550       };
01551 
01552       // Element doesn't move.
01553       if (ABSL_PREDICT_TRUE(probe_index(new_i) == probe_index(i))) {
01554         set_ctrl(i, H2(hash));
01555         continue;
01556       }
01557       if (IsEmpty(ctrl_[new_i])) {
01558         // Transfer element to the empty spot.
01559         // set_ctrl poisons/unpoisons the slots so we have to call it at the
01560         // right time.
01561         set_ctrl(new_i, H2(hash));
01562         PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, slots_ + i);
01563         set_ctrl(i, kEmpty);
01564       } else {
01565         assert(IsDeleted(ctrl_[new_i]));
01566         set_ctrl(new_i, H2(hash));
01567         // Until we are done rehashing, DELETED marks previously FULL slots.
01568         // Swap i and new_i elements.
01569         PolicyTraits::transfer(&alloc_ref(), slot, slots_ + i);
01570         PolicyTraits::transfer(&alloc_ref(), slots_ + i, slots_ + new_i);
01571         PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, slot);
01572         --i;  // repeat
01573       }
01574     }
01575     reset_growth_left();
01576     infoz_.RecordRehash(total_probe_length);
01577   }
01578 
01579   void rehash_and_grow_if_necessary() {
01580     if (capacity_ == 0) {
01581       resize(1);
01582     } else if (size() <= CapacityToGrowth(capacity()) / 2) {
01583       // Squash DELETED without growing if there is enough capacity.
01584       drop_deletes_without_resize();
01585     } else {
01586       // Otherwise grow the container.
01587       resize(capacity_ * 2 + 1);
01588     }
01589   }
01590 
01591   bool has_element(const value_type& elem) const {
01592     size_t hash = PolicyTraits::apply(HashElement{hash_ref()}, elem);
01593     auto seq = probe(hash);
01594     while (true) {
01595       Group g{ctrl_ + seq.offset()};
01596       for (int i : g.Match(H2(hash))) {
01597         if (ABSL_PREDICT_TRUE(PolicyTraits::element(slots_ + seq.offset(i)) ==
01598                               elem))
01599           return true;
01600       }
01601       if (ABSL_PREDICT_TRUE(g.MatchEmpty())) return false;
01602       seq.next();
01603       assert(seq.index() < capacity_ && "full table!");
01604     }
01605     return false;
01606   }
01607 
01608   // Probes the raw_hash_set with the probe sequence for hash and returns the
01609   // pointer to the first empty or deleted slot.
01610   // NOTE: this function must work with tables having both kEmpty and kDelete
01611   // in one group. Such tables appears during drop_deletes_without_resize.
01612   //
01613   // This function is very useful when insertions happen and:
01614   // - the input is already a set
01615   // - there are enough slots
01616   // - the element with the hash is not in the table
01617   struct FindInfo {
01618     size_t offset;
01619     size_t probe_length;
01620   };
01621   FindInfo find_first_non_full(size_t hash) {
01622     auto seq = probe(hash);
01623     while (true) {
01624       Group g{ctrl_ + seq.offset()};
01625       auto mask = g.MatchEmptyOrDeleted();
01626       if (mask) {
01627 #if !defined(NDEBUG)
01628         // We want to add entropy even when ASLR is not enabled.
01629         // In debug build we will randomly insert in either the front or back of
01630         // the group.
01631         // TODO(kfm,sbenza): revisit after we do unconditional mixing
01632         if (!is_small() && ShouldInsertBackwards(hash, ctrl_)) {
01633           return {seq.offset(mask.HighestBitSet()), seq.index()};
01634         }
01635 #endif
01636         return {seq.offset(mask.LowestBitSet()), seq.index()};
01637       }
01638       assert(seq.index() < capacity_ && "full table!");
01639       seq.next();
01640     }
01641   }
01642 
01643   // TODO(alkis): Optimize this assuming *this and that don't overlap.
01644   raw_hash_set& move_assign(raw_hash_set&& that, std::true_type) {
01645     raw_hash_set tmp(std::move(that));
01646     swap(tmp);
01647     return *this;
01648   }
01649   raw_hash_set& move_assign(raw_hash_set&& that, std::false_type) {
01650     raw_hash_set tmp(std::move(that), alloc_ref());
01651     swap(tmp);
01652     return *this;
01653   }
01654 
01655  protected:
01656   template <class K>
01657   std::pair<size_t, bool> find_or_prepare_insert(const K& key) {
01658     auto hash = hash_ref()(key);
01659     auto seq = probe(hash);
01660     while (true) {
01661       Group g{ctrl_ + seq.offset()};
01662       for (int i : g.Match(H2(hash))) {
01663         if (ABSL_PREDICT_TRUE(PolicyTraits::apply(
01664                 EqualElement<K>{key, eq_ref()},
01665                 PolicyTraits::element(slots_ + seq.offset(i)))))
01666           return {seq.offset(i), false};
01667       }
01668       if (ABSL_PREDICT_TRUE(g.MatchEmpty())) break;
01669       seq.next();
01670     }
01671     return {prepare_insert(hash), true};
01672   }
01673 
01674   size_t prepare_insert(size_t hash) ABSL_ATTRIBUTE_NOINLINE {
01675     auto target = find_first_non_full(hash);
01676     if (ABSL_PREDICT_FALSE(growth_left() == 0 &&
01677                            !IsDeleted(ctrl_[target.offset]))) {
01678       rehash_and_grow_if_necessary();
01679       target = find_first_non_full(hash);
01680     }
01681     ++size_;
01682     growth_left() -= IsEmpty(ctrl_[target.offset]);
01683     set_ctrl(target.offset, H2(hash));
01684     infoz_.RecordInsert(hash, target.probe_length);
01685     return target.offset;
01686   }
01687 
01688   // Constructs the value in the space pointed by the iterator. This only works
01689   // after an unsuccessful find_or_prepare_insert() and before any other
01690   // modifications happen in the raw_hash_set.
01691   //
01692   // PRECONDITION: i is an index returned from find_or_prepare_insert(k), where
01693   // k is the key decomposed from `forward<Args>(args)...`, and the bool
01694   // returned by find_or_prepare_insert(k) was true.
01695   // POSTCONDITION: *m.iterator_at(i) == value_type(forward<Args>(args)...).
01696   template <class... Args>
01697   void emplace_at(size_t i, Args&&... args) {
01698     PolicyTraits::construct(&alloc_ref(), slots_ + i,
01699                             std::forward<Args>(args)...);
01700 
01701     assert(PolicyTraits::apply(FindElement{*this}, *iterator_at(i)) ==
01702                iterator_at(i) &&
01703            "constructed value does not match the lookup key");
01704   }
01705 
01706   iterator iterator_at(size_t i) { return {ctrl_ + i, slots_ + i}; }
01707   const_iterator iterator_at(size_t i) const { return {ctrl_ + i, slots_ + i}; }
01708 
01709  private:
01710   friend struct RawHashSetTestOnlyAccess;
01711 
01712   probe_seq<Group::kWidth> probe(size_t hash) const {
01713     return probe_seq<Group::kWidth>(H1(hash, ctrl_), capacity_);
01714   }
01715 
01716   // Reset all ctrl bytes back to kEmpty, except the sentinel.
01717   void reset_ctrl() {
01718     std::memset(ctrl_, kEmpty, capacity_ + Group::kWidth);
01719     ctrl_[capacity_] = kSentinel;
01720     SanitizerPoisonMemoryRegion(slots_, sizeof(slot_type) * capacity_);
01721   }
01722 
01723   void reset_growth_left() {
01724     growth_left() = CapacityToGrowth(capacity()) - size_;
01725   }
01726 
01727   // Sets the control byte, and if `i < Group::kWidth`, set the cloned byte at
01728   // the end too.
01729   void set_ctrl(size_t i, ctrl_t h) {
01730     assert(i < capacity_);
01731 
01732     if (IsFull(h)) {
01733       SanitizerUnpoisonObject(slots_ + i);
01734     } else {
01735       SanitizerPoisonObject(slots_ + i);
01736     }
01737 
01738     ctrl_[i] = h;
01739     ctrl_[((i - Group::kWidth) & capacity_) + 1 +
01740           ((Group::kWidth - 1) & capacity_)] = h;
01741   }
01742 
01743   size_t& growth_left() { return settings_.template get<0>(); }
01744 
01745   // The representation of the object has two modes:
01746   //  - small: For capacities < kWidth-1
01747   //  - large: For the rest.
01748   //
01749   // Differences:
01750   //  - In small mode we are able to use the whole capacity. The extra control
01751   //  bytes give us at least one "empty" control byte to stop the iteration.
01752   //  This is important to make 1 a valid capacity.
01753   //
01754   //  - In small mode only the first `capacity()` control bytes after the
01755   //  sentinel are valid. The rest contain dummy kEmpty values that do not
01756   //  represent a real slot. This is important to take into account on
01757   //  find_first_non_full(), where we never try ShouldInsertBackwards() for
01758   //  small tables.
01759   bool is_small() const { return capacity_ < Group::kWidth - 1; }
01760 
01761   hasher& hash_ref() { return settings_.template get<1>(); }
01762   const hasher& hash_ref() const { return settings_.template get<1>(); }
01763   key_equal& eq_ref() { return settings_.template get<2>(); }
01764   const key_equal& eq_ref() const { return settings_.template get<2>(); }
01765   allocator_type& alloc_ref() { return settings_.template get<3>(); }
01766   const allocator_type& alloc_ref() const {
01767     return settings_.template get<3>();
01768   }
01769 
01770   // TODO(alkis): Investigate removing some of these fields:
01771   // - ctrl/slots can be derived from each other
01772   // - size can be moved into the slot array
01773   ctrl_t* ctrl_ = EmptyGroup();    // [(capacity + 1) * ctrl_t]
01774   slot_type* slots_ = nullptr;     // [capacity * slot_type]
01775   size_t size_ = 0;                // number of full slots
01776   size_t capacity_ = 0;            // total number of slots
01777   HashtablezInfoHandle infoz_;
01778   absl::container_internal::CompressedTuple<size_t /* growth_left */, hasher,
01779                                             key_equal, allocator_type>
01780       settings_{0, hasher{}, key_equal{}, allocator_type{}};
01781 };
01782 
01783 namespace hashtable_debug_internal {
01784 template <typename Set>
01785 struct HashtableDebugAccess<Set, absl::void_t<typename Set::raw_hash_set>> {
01786   using Traits = typename Set::PolicyTraits;
01787   using Slot = typename Traits::slot_type;
01788 
01789   static size_t GetNumProbes(const Set& set,
01790                              const typename Set::key_type& key) {
01791     size_t num_probes = 0;
01792     size_t hash = set.hash_ref()(key);
01793     auto seq = set.probe(hash);
01794     while (true) {
01795       container_internal::Group g{set.ctrl_ + seq.offset()};
01796       for (int i : g.Match(container_internal::H2(hash))) {
01797         if (Traits::apply(
01798                 typename Set::template EqualElement<typename Set::key_type>{
01799                     key, set.eq_ref()},
01800                 Traits::element(set.slots_ + seq.offset(i))))
01801           return num_probes;
01802         ++num_probes;
01803       }
01804       if (g.MatchEmpty()) return num_probes;
01805       seq.next();
01806       ++num_probes;
01807     }
01808   }
01809 
01810   static size_t AllocatedByteSize(const Set& c) {
01811     size_t capacity = c.capacity_;
01812     if (capacity == 0) return 0;
01813     auto layout = Set::MakeLayout(capacity);
01814     size_t m = layout.AllocSize();
01815 
01816     size_t per_slot = Traits::space_used(static_cast<const Slot*>(nullptr));
01817     if (per_slot != ~size_t{}) {
01818       m += per_slot * c.size();
01819     } else {
01820       for (size_t i = 0; i != capacity; ++i) {
01821         if (container_internal::IsFull(c.ctrl_[i])) {
01822           m += Traits::space_used(c.slots_ + i);
01823         }
01824       }
01825     }
01826     return m;
01827   }
01828 
01829   static size_t LowerBoundAllocatedByteSize(size_t size) {
01830     size_t capacity = GrowthToLowerboundCapacity(size);
01831     if (capacity == 0) return 0;
01832     auto layout = Set::MakeLayout(NormalizeCapacity(capacity));
01833     size_t m = layout.AllocSize();
01834     size_t per_slot = Traits::space_used(static_cast<const Slot*>(nullptr));
01835     if (per_slot != ~size_t{}) {
01836       m += per_slot * size;
01837     }
01838     return m;
01839   }
01840 };
01841 
01842 }  // namespace hashtable_debug_internal
01843 }  // namespace container_internal
01844 }  // namespace absl
01845 
01846 #endif  // ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:42:15