// Copyright 2018 The Abseil Authors.

//

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

//

//      https://www.apache.org/licenses/LICENSE-2.0

//

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

//

// An open-addressing

// hashtable with quadratic probing.

//

// This is a low level hashtable on top of which different interfaces can be

// implemented, like flat_hash_set, node_hash_set, string_hash_set, etc.

//

// The table interface is similar to that of std::unordered_set. Notable

// differences are that most member functions support heterogeneous keys when

// BOTH the hash and eq functions are marked as transparent. They do so by

// providing a typedef called `is_transparent`.

//

// When heterogeneous lookup is enabled, functions that take key_type act as if

// they have an overload set like:

//

//   iterator find(const key_type& key);

//   template <class K>

//   iterator find(const K& key);

//

//   size_type erase(const key_type& key);

//   template <class K>

//   size_type erase(const K& key);

//

//   std::pair<iterator, iterator> equal_range(const key_type& key);

//   template <class K>

//   std::pair<iterator, iterator> equal_range(const K& key);

//

// When heterogeneous lookup is disabled, only the explicit `key_type` overloads

// exist.

//

// find() also supports passing the hash explicitly:

//

//   iterator find(const key_type& key, size_t hash);

//   template <class U>

//   iterator find(const U& key, size_t hash);

//

// In addition the pointer to element and iterator stability guarantees are

// weaker: all iterators and pointers are invalidated after a new element is

// inserted.

//

// IMPLEMENTATION DETAILS

//

// # Table Layout

//

// A raw_hash_set's backing array consists of control bytes followed by slots

// that may or may not contain objects.

//

// The layout of the backing array, for `capacity` slots, is thus, as a

// pseudo-struct:

//

//   struct BackingArray {

//     // Sampling handler. This field isn't present when the sampling is

//     // disabled or this allocation hasn't been selected for sampling.

//     HashtablezInfoHandle infoz_;

//     // The number of elements we can insert before growing the capacity.

//     size_t growth_left;

//     // Control bytes for the "real" slots.

//     ctrl_t ctrl[capacity];

//     // Always `ctrl_t::kSentinel`. This is used by iterators to find when to

//     // stop and serves no other purpose.

//     ctrl_t sentinel;

//     // A copy of the first `kWidth - 1` elements of `ctrl`. This is used so

//     // that if a probe sequence picks a value near the end of `ctrl`,

//     // `Group` will have valid control bytes to look at.

//     ctrl_t clones[kWidth - 1];

//     // The actual slot data.

//     slot_type slots[capacity];

//   };

//

// The length of this array is computed by `AllocSize()` below.

//

// Control bytes (`ctrl_t`) are bytes (collected into groups of a

// platform-specific size) that define the state of the corresponding slot in

// the slot array. Group manipulation is tightly optimized to be as efficient

// as possible: SSE and friends on x86, clever bit operations on other arches.

//

//      Group 1         Group 2        Group 3

// +---------------+---------------+---------------+

// | | | | | | | | | | | | | | | | | | | | | | | | |

// +---------------+---------------+---------------+

//

// Each control byte is either a special value for empty slots, deleted slots

// (sometimes called *tombstones*), and a special end-of-table marker used by

// iterators, or, if occupied, seven bits (H2) from the hash of the value in the

// corresponding slot.

//

// Storing control bytes in a separate array also has beneficial cache effects,

// since more logical slots will fit into a cache line.

//

// # Hashing

//

// We compute two separate hashes, `H1` and `H2`, from the hash of an object.

// `H1(hash(x))` is an index into `slots`, and essentially the starting point

// for the probe sequence. `H2(hash(x))` is a 7-bit value used to filter out

// objects that cannot possibly be the one we are looking for.

//

// # Table operations.

//

// The key operations are `insert`, `find`, and `erase`.

//

// Since `insert` and `erase` are implemented in terms of `find`, we describe

// `find` first. To `find` a value `x`, we compute `hash(x)`. From

// `H1(hash(x))` and the capacity, we construct a `probe_seq` that visits every

// group of slots in some interesting order.

//

// We now walk through these indices. At each index, we select the entire group

// starting with that index and extract potential candidates: occupied slots

// with a control byte equal to `H2(hash(x))`. If we find an empty slot in the

// group, we stop and return an error. Each candidate slot `y` is compared with

// `x`; if `x == y`, we are done and return `&y`; otherwise we continue to the

// next probe index. Tombstones effectively behave like full slots that never

// match the value we're looking for.

//

// The `H2` bits ensure when we compare a slot to an object with `==`, we are

// likely to have actually found the object.  That is, the chance is low that

// `==` is called and returns `false`.  Thus, when we search for an object, we

// are unlikely to call `==` many times.  This likelyhood can be analyzed as

// follows (assuming that H2 is a random enough hash function).

//

// Let's assume that there are `k` "wrong" objects that must be examined in a

// probe sequence.  For example, when doing a `find` on an object that is in the

// table, `k` is the number of objects between the start of the probe sequence

// and the final found object (not including the final found object).  The

// expected number of objects with an H2 match is then `k/128`.  Measurements

// and analysis indicate that even at high load factors, `k` is less than 32,

// meaning that the number of "false positive" comparisons we must perform is

// less than 1/8 per `find`.

// `insert` is implemented in terms of `unchecked_insert`, which inserts a

// value presumed to not be in the table (violating this requirement will cause

// the table to behave erratically). Given `x` and its hash `hash(x)`, to insert

// it, we construct a `probe_seq` once again, and use it to find the first

// group with an unoccupied (empty *or* deleted) slot. We place `x` into the

// first such slot in the group and mark it as full with `x`'s H2.

//

// To `insert`, we compose `unchecked_insert` with `find`. We compute `h(x)` and

// perform a `find` to see if it's already present; if it is, we're done. If

// it's not, we may decide the table is getting overcrowded (i.e. the load

// factor is greater than 7/8 for big tables; `is_small()` tables use a max load

// factor of 1); in this case, we allocate a bigger array, `unchecked_insert`

// each element of the table into the new array (we know that no insertion here

// will insert an already-present value), and discard the old backing array. At

// this point, we may `unchecked_insert` the value `x`.

//

// Below, `unchecked_insert` is partly implemented by `prepare_insert`, which

// presents a viable, initialized slot pointee to the caller.

//

// `erase` is implemented in terms of `erase_at`, which takes an index to a

// slot. Given an offset, we simply create a tombstone and destroy its contents.

// If we can prove that the slot would not appear in a probe sequence, we can

// make the slot as empty, instead. We can prove this by observing that if a

// group has any empty slots, it has never been full (assuming we never create

// an empty slot in a group with no empties, which this heuristic guarantees we

// never do) and find would stop at this group anyways (since it does not probe

// beyond groups with empties).

//

// `erase` is `erase_at` composed with `find`: if we

// have a value `x`, we can perform a `find`, and then `erase_at` the resulting

// slot.

//

// To iterate, we simply traverse the array, skipping empty and deleted slots

// and stopping when we hit a `kSentinel`.

#ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_

#define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_

#include <algorithm>

#include <cassert>

#include <cmath>

#include <cstddef>

#include <cstdint>

#include <cstring>

#include <initializer_list>

#include <iterator>

#include <limits>

#include <memory>

#include <string>

#include <tuple>

#include <type_traits>

#include <utility>

#include "absl/base/attributes.h"

#include "absl/base/config.h"

#include "absl/base/internal/endian.h"

#include "absl/base/internal/raw_logging.h"

#include "absl/base/macros.h"

#include "absl/base/optimization.h"

#include "absl/base/options.h"

#include "absl/base/port.h"

#include "absl/base/prefetch.h"

#include "absl/container/internal/common.h"

#include "absl/container/internal/compressed_tuple.h"

#include "absl/container/internal/container_memory.h"

#include "absl/container/internal/hash_policy_traits.h"

#include "absl/container/internal/hashtable_debug_hooks.h"

#include "absl/container/internal/hashtablez_sampler.h"

#include "absl/memory/memory.h"

#include "absl/meta/type_traits.h"

#include "absl/numeric/bits.h"

#include "absl/utility/utility.h"

#ifdef ABSL_INTERNAL_HAVE_SSE2

#include <emmintrin.h>

#endif

#ifdef ABSL_INTERNAL_HAVE_SSSE3

#include <tmmintrin.h>

#endif

#ifdef _MSC_VER

#include <intrin.h>

#endif

#ifdef ABSL_INTERNAL_HAVE_ARM_NEON

#include <arm_neon.h>

#endif

namespace absl {

ABSL_NAMESPACE_BEGIN

namespace container_internal {

#ifdef ABSL_SWISSTABLE_ENABLE_GENERATIONS

#error ABSL_SWISSTABLE_ENABLE_GENERATIONS cannot be directly set

#elif defined(ABSL_HAVE_ADDRESS_SANITIZER) || \

    defined(ABSL_HAVE_MEMORY_SANITIZER)

// When compiled in sanitizer mode, we add generation integers to the backing

// array and iterators. In the backing array, we store the generation between

// the control bytes and the slots. When iterators are dereferenced, we assert

// that the container has not been mutated in a way that could cause iterator

// invalidation since the iterator was initialized.

#define ABSL_SWISSTABLE_ENABLE_GENERATIONS

#endif

// We use uint8_t so we don't need to worry about padding.

using GenerationType = uint8_t;

// A sentinel value for empty generations. Using 0 makes it easy to constexpr

// initialize an array of this value.

constexpr GenerationType SentinelEmptyGeneration() { return 0; }

constexpr GenerationType NextGeneration(GenerationType generation) {

  return ++generation == SentinelEmptyGeneration() ? ++generation : generation;

}

#ifdef ABSL_SWISSTABLE_ENABLE_GENERATIONS

constexpr bool SwisstableGenerationsEnabled() { return true; }

constexpr size_t NumGenerationBytes() { return sizeof(GenerationType); }

#else

constexpr bool SwisstableGenerationsEnabled() { return false; }

constexpr size_t NumGenerationBytes() { return 0; }

#endif

template <typename AllocType>

void SwapAlloc(AllocType& lhs, AllocType& rhs,

               std::true_type /* propagate_on_container_swap */) {

  using std::swap;

  swap(lhs, rhs);

}

template <typename AllocType>

void SwapAlloc(AllocType& /*lhs*/, AllocType& /*rhs*/,

               std::false_type /* propagate_on_container_swap */) {}

// The state for a probe sequence.

//

// Currently, the sequence is a triangular progression of the form

//

//   p(i) := Width * (i^2 + i)/2 + hash (mod mask + 1)

//

// The use of `Width` ensures that each probe step does not overlap groups;

// the sequence effectively outputs the addresses of *groups* (although not

// necessarily aligned to any boundary). The `Group` machinery allows us

// to check an entire group with minimal branching.

//

// Wrapping around at `mask + 1` is important, but not for the obvious reason.

// As described above, the first few entries of the control byte array

// are mirrored at the end of the array, which `Group` will find and use

// for selecting candidates. However, when those candidates' slots are

// actually inspected, there are no corresponding slots for the cloned bytes,

// so we need to make sure we've treated those offsets as "wrapping around".

//

// It turns out that this probe sequence visits every group exactly once if the

// number of groups is a power of two, since (i^2+i)/2 is a bijection in

// Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probing

template <size_t Width>

class probe_seq {

 public:

  // Creates a new probe sequence using `hash` as the initial value of the

  // sequence and `mask` (usually the capacity of the table) as the mask to

  // apply to each value in the progression.

  probe_seq(size_t hash, size_t mask) {

    assert(((mask + 1) & mask) == 0 && "not a mask");

    mask_ = mask;

    offset_ = hash & mask_;

  }

  // The offset within the table, i.e., the value `p(i)` above.

  size_t offset() const { return offset_; }

  size_t offset(size_t i) const { return (offset_ + i) & mask_; }

  void next() {

    index_ += Width;

    offset_ += index_;

    offset_ &= mask_;

  }

  // 0-based probe index, a multiple of `Width`.

  size_t index() const { return index_; }

 private:

  size_t mask_;

  size_t offset_;

  size_t index_ = 0;

};

template <class ContainerKey, class Hash, class Eq>

struct RequireUsableKey {

  template <class PassedKey, class... Args>

  std::pair<

      decltype(std::declval<const Hash&>()(std::declval<const PassedKey&>())),

      decltype(std::declval<const Eq&>()(std::declval<const ContainerKey&>(),

                                         std::declval<const PassedKey&>()))>*

  operator()(const PassedKey&, const Args&...) const;

};

template <class E, class Policy, class Hash, class Eq, class... Ts>

struct IsDecomposable : std::false_type {};

template <class Policy, class Hash, class Eq, class... Ts>

struct IsDecomposable<

    absl::void_t<decltype(Policy::apply(

        RequireUsableKey<typename Policy::key_type, Hash, Eq>(),

        std::declval<Ts>()...))>,

    Policy, Hash, Eq, Ts...> : std::true_type {};

// TODO(alkis): Switch to std::is_nothrow_swappable when gcc/clang supports it.

template <class T>

constexpr bool IsNoThrowSwappable(std::true_type = {} /* is_swappable */) {

  using std::swap;

  return noexcept(swap(std::declval<T&>(), std::declval<T&>()));

}

template <class T>

constexpr bool IsNoThrowSwappable(std::false_type /* is_swappable */) {

  return false;

}

template <typename T>

uint32_t TrailingZeros(T x) {

  ABSL_ASSUME(x != 0);

  return static_cast<uint32_t>(countr_zero(x));

}

// An abstract bitmask, such as that emitted by a SIMD instruction.

//

// Specifically, this type implements a simple bitset whose representation is

// controlled by `SignificantBits` and `Shift`. `SignificantBits` is the number

// of abstract bits in the bitset, while `Shift` is the log-base-two of the

// width of an abstract bit in the representation.

// This mask provides operations for any number of real bits set in an abstract

// bit. To add iteration on top of that, implementation must guarantee no more

// than the most significant real bit is set in a set abstract bit.

template <class T, int SignificantBits, int Shift = 0>

class NonIterableBitMask {

 public:

  explicit NonIterableBitMask(T mask) : mask_(mask) {}

  explicit operator bool() const { return this->mask_ != 0; }

  // Returns the index of the lowest *abstract* bit set in `self`.

  uint32_t LowestBitSet() const {

    return container_internal::TrailingZeros(mask_) >> Shift;

  }

  // Returns the index of the highest *abstract* bit set in `self`.

  uint32_t HighestBitSet() const {

    return static_cast<uint32_t>((bit_width(mask_) - 1) >> Shift);

  }

  // Returns the number of trailing zero *abstract* bits.

  uint32_t TrailingZeros() const {

    return container_internal::TrailingZeros(mask_) >> Shift;

  }

  // Returns the number of leading zero *abstract* bits.

  uint32_t LeadingZeros() const {

    constexpr int total_significant_bits = SignificantBits << Shift;

    constexpr int extra_bits = sizeof(T) * 8 - total_significant_bits;

    return static_cast<uint32_t>(countl_zero(mask_ << extra_bits)) >> Shift;

  }

  T mask_;

};

// Mask that can be iterable

//

// For example, when `SignificantBits` is 16 and `Shift` is zero, this is just

// an ordinary 16-bit bitset occupying the low 16 bits of `mask`. When

// `SignificantBits` is 8 and `Shift` is 3, abstract bits are represented as

// the bytes `0x00` and `0x80`, and it occupies all 64 bits of the bitmask.

//

// For example:

//   for (int i : BitMask<uint32_t, 16>(0b101)) -> yields 0, 2

//   for (int i : BitMask<uint64_t, 8, 3>(0x0000000080800000)) -> yields 2, 3

template <class T, int SignificantBits, int Shift = 0>

class BitMask : public NonIterableBitMask<T, SignificantBits, Shift> {

  using Base = NonIterableBitMask<T, SignificantBits, Shift>;

  static_assert(std::is_unsigned<T>::value, "");

  static_assert(Shift == 0 || Shift == 3, "");

 public:

  explicit BitMask(T mask) : Base(mask) {}

  // BitMask is an iterator over the indices of its abstract bits.

  using value_type = int;

  using iterator = BitMask;

  using const_iterator = BitMask;

  BitMask& operator++() {

    if (Shift == 3) {

      constexpr uint64_t msbs = 0x8080808080808080ULL;

      this->mask_ &= msbs;

    }

    this->mask_ &= (this->mask_ - 1);

    return *this;

  }

  uint32_t operator*() const { return Base::LowestBitSet(); }

  BitMask begin() const { return *this; }

  BitMask end() const { return BitMask(0); }

 private:

  friend bool operator==(const BitMask& a, const BitMask& b) {

    return a.mask_ == b.mask_;

  }

  friend bool operator!=(const BitMask& a, const BitMask& b) {

    return a.mask_ != b.mask_;

  }

};

using h2_t = uint8_t;

// The values here are selected for maximum performance. See the static asserts

// below for details.

// A `ctrl_t` is a single control byte, which can have one of four

// states: empty, deleted, full (which has an associated seven-bit h2_t value)

// and the sentinel. They have the following bit patterns:

//

//      empty: 1 0 0 0 0 0 0 0

//    deleted: 1 1 1 1 1 1 1 0

//       full: 0 h h h h h h h  // h represents the hash bits.

//   sentinel: 1 1 1 1 1 1 1 1

//

// These values are specifically tuned for SSE-flavored SIMD.

// The static_asserts below detail the source of these choices.

//

// We use an enum class so that when strict aliasing is enabled, the compiler

// knows ctrl_t doesn't alias other types.

enum class ctrl_t : int8_t {

  kEmpty = -128,   // 0b10000000

  kDeleted = -2,   // 0b11111110

  kSentinel = -1,  // 0b11111111

};

static_assert(

    (static_cast<int8_t>(ctrl_t::kEmpty) &

     static_cast<int8_t>(ctrl_t::kDeleted) &

     static_cast<int8_t>(ctrl_t::kSentinel) & 0x80) != 0,

    "Special markers need to have the MSB to make checking for them efficient");

static_assert(

    ctrl_t::kEmpty < ctrl_t::kSentinel && ctrl_t::kDeleted < ctrl_t::kSentinel,

    "ctrl_t::kEmpty and ctrl_t::kDeleted must be smaller than "

    "ctrl_t::kSentinel to make the SIMD test of IsEmptyOrDeleted() efficient");

static_assert(

    ctrl_t::kSentinel == static_cast<ctrl_t>(-1),

    "ctrl_t::kSentinel must be -1 to elide loading it from memory into SIMD "

    "registers (pcmpeqd xmm, xmm)");

static_assert(ctrl_t::kEmpty == static_cast<ctrl_t>(-128),

              "ctrl_t::kEmpty must be -128 to make the SIMD check for its "

              "existence efficient (psignb xmm, xmm)");

static_assert(

    (~static_cast<int8_t>(ctrl_t::kEmpty) &

     ~static_cast<int8_t>(ctrl_t::kDeleted) &

     static_cast<int8_t>(ctrl_t::kSentinel) & 0x7F) != 0,

    "ctrl_t::kEmpty and ctrl_t::kDeleted must share an unset bit that is not "

    "shared by ctrl_t::kSentinel to make the scalar test for "

    "MaskEmptyOrDeleted() efficient");

static_assert(ctrl_t::kDeleted == static_cast<ctrl_t>(-2),

              "ctrl_t::kDeleted must be -2 to make the implementation of "

              "ConvertSpecialToEmptyAndFullToDeleted efficient");

// See definition comment for why this is size 32.

ABSL_DLL extern const ctrl_t kEmptyGroup[32];

// Returns a pointer to a control byte group that can be used by empty tables.

inline ctrl_t* EmptyGroup() {

  // Const must be cast away here; no uses of this function will actually write

  // to it, because it is only used for empty tables.

  return const_cast<ctrl_t*>(kEmptyGroup + 16);

}

// Returns a pointer to a generation to use for an empty hashtable.

GenerationType* EmptyGeneration();

// Returns whether `generation` is a generation for an empty hashtable that

// could be returned by EmptyGeneration().

inline bool IsEmptyGeneration(const GenerationType* generation) {

  return *generation == SentinelEmptyGeneration();

}

// Mixes a randomly generated per-process seed with `hash` and `ctrl` to

// randomize insertion order within groups.

bool ShouldInsertBackwards(size_t hash, const ctrl_t* ctrl);

// Returns a per-table, hash salt, which changes on resize. This gets mixed into

// H1 to randomize iteration order per-table.

//

// The seed consists of the ctrl_ pointer, which adds enough entropy to ensure

// non-determinism of iteration order in most cases.

inline size_t PerTableSalt(const ctrl_t* ctrl) {

  // The low bits of the pointer have little or no entropy because of

  // alignment. We shift the pointer to try to use higher entropy bits. A

  // good number seems to be 12 bits, because that aligns with page size.

  return reinterpret_cast<uintptr_t>(ctrl) >> 12;

}

// Extracts the H1 portion of a hash: 57 bits mixed with a per-table salt.

inline size_t H1(size_t hash, const ctrl_t* ctrl) {

  return (hash >> 7) ^ PerTableSalt(ctrl);

}

// Extracts the H2 portion of a hash: the 7 bits not used for H1.

//

// These are used as an occupied control byte.

inline h2_t H2(size_t hash) { return hash & 0x7F; }

// Helpers for checking the state of a control byte.

inline bool IsEmpty(ctrl_t c) { return c == ctrl_t::kEmpty; }

inline bool IsFull(ctrl_t c) { return c >= static_cast<ctrl_t>(0); }

inline bool IsDeleted(ctrl_t c) { return c == ctrl_t::kDeleted; }

inline bool IsEmptyOrDeleted(ctrl_t c) { return c < ctrl_t::kSentinel; }

#ifdef ABSL_INTERNAL_HAVE_SSE2

// Quick reference guide for intrinsics used below:

//

// * __m128i: An XMM (128-bit) word.

//

// * _mm_setzero_si128: Returns a zero vector.

// * _mm_set1_epi8:     Returns a vector with the same i8 in each lane.

//

// * _mm_subs_epi8:    Saturating-subtracts two i8 vectors.

// * _mm_and_si128:    Ands two i128s together.

// * _mm_or_si128:     Ors two i128s together.

// * _mm_andnot_si128: And-nots two i128s together.

//

// * _mm_cmpeq_epi8: Component-wise compares two i8 vectors for equality,

//                   filling each lane with 0x00 or 0xff.

// * _mm_cmpgt_epi8: Same as above, but using > rather than ==.

//

// * _mm_loadu_si128:  Performs an unaligned load of an i128.

// * _mm_storeu_si128: Performs an unaligned store of an i128.

//

// * _mm_sign_epi8:     Retains, negates, or zeroes each i8 lane of the first

//                      argument if the corresponding lane of the second

//                      argument is positive, negative, or zero, respectively.

// * _mm_movemask_epi8: Selects the sign bit out of each i8 lane and produces a

//                      bitmask consisting of those bits.

// * _mm_shuffle_epi8:  Selects i8s from the first argument, using the low

//                      four bits of each i8 lane in the second argument as

//                      indices.

// https://github.com/abseil/abseil-cpp/issues/209

// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87853

// _mm_cmpgt_epi8 is broken under GCC with -funsigned-char

// Work around this by using the portable implementation of Group

// when using -funsigned-char under GCC.

inline __m128i _mm_cmpgt_epi8_fixed(__m128i a, __m128i b) {

#if defined(__GNUC__) && !defined(__clang__)

  if (std::is_unsigned<char>::value) {

    const __m128i mask = _mm_set1_epi8(0x80);

    const __m128i diff = _mm_subs_epi8(b, a);

    return _mm_cmpeq_epi8(_mm_and_si128(diff, mask), mask);

  }

#endif

  return _mm_cmpgt_epi8(a, b);

}

struct GroupSse2Impl {

  static constexpr size_t kWidth = 16;  // the number of slots per group

  explicit GroupSse2Impl(const ctrl_t* pos) {

    ctrl = _mm_loadu_si128(reinterpret_cast<const __m128i*>(pos));

  }

  // Returns a bitmask representing the positions of slots that match hash.

  BitMask<uint32_t, kWidth> Match(h2_t hash) const {

    auto match = _mm_set1_epi8(static_cast<char>(hash));

    return BitMask<uint32_t, kWidth>(

        static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(match, ctrl))));

  }

  // Returns a bitmask representing the positions of empty slots.

  NonIterableBitMask<uint32_t, kWidth> MaskEmpty() const {

#ifdef ABSL_INTERNAL_HAVE_SSSE3

    // This only works because ctrl_t::kEmpty is -128.

    return NonIterableBitMask<uint32_t, kWidth>(

        static_cast<uint32_t>(_mm_movemask_epi8(_mm_sign_epi8(ctrl, ctrl))));

#else

    auto match = _mm_set1_epi8(static_cast<char>(ctrl_t::kEmpty));

    return NonIterableBitMask<uint32_t, kWidth>(

        static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(match, ctrl))));

#endif

  }

  // Returns a bitmask representing the positions of empty or deleted slots.

  NonIterableBitMask<uint32_t, kWidth> MaskEmptyOrDeleted() const {

    auto special = _mm_set1_epi8(static_cast<char>(ctrl_t::kSentinel));

    return NonIterableBitMask<uint32_t, kWidth>(static_cast<uint32_t>(

        _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl))));

  }

  // Returns the number of trailing empty or deleted elements in the group.

  uint32_t CountLeadingEmptyOrDeleted() const {

    auto special = _mm_set1_epi8(static_cast<char>(ctrl_t::kSentinel));

    return TrailingZeros(static_cast<uint32_t>(

        _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1));

  }

  void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {

    auto msbs = _mm_set1_epi8(static_cast<char>(-128));

    auto x126 = _mm_set1_epi8(126);

#ifdef ABSL_INTERNAL_HAVE_SSSE3

    auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs);

#else

    auto zero = _mm_setzero_si128();

    auto special_mask = _mm_cmpgt_epi8_fixed(zero, ctrl);

    auto res = _mm_or_si128(msbs, _mm_andnot_si128(special_mask, x126));

#endif

    _mm_storeu_si128(reinterpret_cast<__m128i*>(dst), res);

  }

  __m128i ctrl;

};

#endif  // ABSL_INTERNAL_RAW_HASH_SET_HAVE_SSE2

#if defined(ABSL_INTERNAL_HAVE_ARM_NEON) && defined(ABSL_IS_LITTLE_ENDIAN)

struct GroupAArch64Impl {

  static constexpr size_t kWidth = 8;

  explicit GroupAArch64Impl(const ctrl_t* pos) {

    ctrl = vld1_u8(reinterpret_cast<const uint8_t*>(pos));

  }

  BitMask<uint64_t, kWidth, 3> Match(h2_t hash) const {

    uint8x8_t dup = vdup_n_u8(hash);

    auto mask = vceq_u8(ctrl, dup);

    return BitMask<uint64_t, kWidth, 3>(

        vget_lane_u64(vreinterpret_u64_u8(mask), 0));

  }

  NonIterableBitMask<uint64_t, kWidth, 3> MaskEmpty() const {

    uint64_t mask =

        vget_lane_u64(vreinterpret_u64_u8(vceq_s8(

                          vdup_n_s8(static_cast<int8_t>(ctrl_t::kEmpty)),

                          vreinterpret_s8_u8(ctrl))),

                      0);

    return NonIterableBitMask<uint64_t, kWidth, 3>(mask);

  }

  NonIterableBitMask<uint64_t, kWidth, 3> MaskEmptyOrDeleted() const {

    uint64_t mask =

        vget_lane_u64(vreinterpret_u64_u8(vcgt_s8(

                          vdup_n_s8(static_cast<int8_t>(ctrl_t::kSentinel)),

                          vreinterpret_s8_u8(ctrl))),

                      0);

    return NonIterableBitMask<uint64_t, kWidth, 3>(mask);

  }

  uint32_t CountLeadingEmptyOrDeleted() const {

    uint64_t mask =

        vget_lane_u64(vreinterpret_u64_u8(vcle_s8(

                          vdup_n_s8(static_cast<int8_t>(ctrl_t::kSentinel)),

                          vreinterpret_s8_u8(ctrl))),

                      0);

    // Similar to MaskEmptyorDeleted() but we invert the logic to invert the

    // produced bitfield. We then count number of trailing zeros.

    // Clang and GCC optimize countr_zero to rbit+clz without any check for 0,

    // so we should be fine.

    return static_cast<uint32_t>(countr_zero(mask)) >> 3;

  }

  void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {

    uint64_t mask = vget_lane_u64(vreinterpret_u64_u8(ctrl), 0);

    constexpr uint64_t msbs = 0x8080808080808080ULL;

    constexpr uint64_t slsbs = 0x0202020202020202ULL;

    constexpr uint64_t midbs = 0x7e7e7e7e7e7e7e7eULL;

    auto x = slsbs & (mask >> 6);

    auto res = (x + midbs) | msbs;

    little_endian::Store64(dst, res);

  }

  uint8x8_t ctrl;

};

#endif  // ABSL_INTERNAL_HAVE_ARM_NEON && ABSL_IS_LITTLE_ENDIAN

struct GroupPortableImpl {

  static constexpr size_t kWidth = 8;

  explicit GroupPortableImpl(const ctrl_t* pos)

      : ctrl(little_endian::Load64(pos)) {}

  BitMask<uint64_t, kWidth, 3> Match(h2_t hash) const {

    // For the technique, see:

    // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord

    // (Determine if a word has a byte equal to n).

    //

    // Caveat: there are false positives but:

    // - they only occur if there is a real match

    // - they never occur on ctrl_t::kEmpty, ctrl_t::kDeleted, ctrl_t::kSentinel

    // - they will be handled gracefully by subsequent checks in code

    //

    // Example:

    //   v = 0x1716151413121110

    //   hash = 0x12

    //   retval = (v - lsbs) & ~v & msbs = 0x0000000080800000

    constexpr uint64_t msbs = 0x8080808080808080ULL;

    constexpr uint64_t lsbs = 0x0101010101010101ULL;

    auto x = ctrl ^ (lsbs * hash);

    return BitMask<uint64_t, kWidth, 3>((x - lsbs) & ~x & msbs);

  }

  NonIterableBitMask<uint64_t, kWidth, 3> MaskEmpty() const {

    constexpr uint64_t msbs = 0x8080808080808080ULL;

    return NonIterableBitMask<uint64_t, kWidth, 3>((ctrl & ~(ctrl << 6)) &

                                                   msbs);

  }

  NonIterableBitMask<uint64_t, kWidth, 3> MaskEmptyOrDeleted() const {

    constexpr uint64_t msbs = 0x8080808080808080ULL;

    return NonIterableBitMask<uint64_t, kWidth, 3>((ctrl & ~(ctrl << 7)) &

                                                   msbs);

  }

  uint32_t CountLeadingEmptyOrDeleted() const {

    // ctrl | ~(ctrl >> 7) will have the lowest bit set to zero for kEmpty and

    // kDeleted. We lower all other bits and count number of trailing zeros.

    constexpr uint64_t bits = 0x0101010101010101ULL;

    return static_cast<uint32_t>(countr_zero((ctrl | ~(ctrl >> 7)) & bits) >>

                                 3);

  }

  void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {

    constexpr uint64_t msbs = 0x8080808080808080ULL;

    constexpr uint64_t lsbs = 0x0101010101010101ULL;

    auto x = ctrl & msbs;

    auto res = (~x + (x >> 7)) & ~lsbs;

    little_endian::Store64(dst, res);

  }

  uint64_t ctrl;

};

#ifdef ABSL_INTERNAL_HAVE_SSE2

using Group = GroupSse2Impl;

using GroupEmptyOrDeleted = GroupSse2Impl;

#elif defined(ABSL_INTERNAL_HAVE_ARM_NEON) && defined(ABSL_IS_LITTLE_ENDIAN)

using Group = GroupAArch64Impl;

// For Aarch64, we use the portable implementation for counting and masking

// empty or deleted group elements. This is to avoid the latency of moving

// between data GPRs and Neon registers when it does not provide a benefit.

// Using Neon is profitable when we call Match(), but is not when we don't,

// which is the case when we do *EmptyOrDeleted operations. It is difficult to

// make a similar approach beneficial on other architectures such as x86 since

// they have much lower GPR <-> vector register transfer latency and 16-wide

// Groups.

using GroupEmptyOrDeleted = GroupPortableImpl;

#else

using Group = GroupPortableImpl;

using GroupEmptyOrDeleted = GroupPortableImpl;

#endif

// When there is an insertion with no reserved growth, we rehash with

// probability `min(1, RehashProbabilityConstant() / capacity())`. Using a

// constant divided by capacity ensures that inserting N elements is still O(N)

// in the average case. Using the constant 16 means that we expect to rehash ~8

// times more often than when generations are disabled. We are adding expected

// rehash_probability * #insertions/capacity_growth = 16/capacity * ((7/8 -

// 7/16) * capacity)/capacity_growth = ~7 extra rehashes per capacity growth.

inline size_t RehashProbabilityConstant() { return 16; }

class CommonFieldsGenerationInfoEnabled {

  // A sentinel value for reserved_growth_ indicating that we just ran out of

  // reserved growth on the last insertion. When reserve is called and then

  // insertions take place, reserved_growth_'s state machine is N, ..., 1,

  // kReservedGrowthJustRanOut, 0.

  static constexpr size_t kReservedGrowthJustRanOut =

      (std::numeric_limits<size_t>::max)();

 public:

  CommonFieldsGenerationInfoEnabled() = default;

  CommonFieldsGenerationInfoEnabled(CommonFieldsGenerationInfoEnabled&& that)

      : reserved_growth_(that.reserved_growth_),

        reservation_size_(that.reservation_size_),

        generation_(that.generation_) {

    that.reserved_growth_ = 0;

    that.reservation_size_ = 0;

    that.generation_ = EmptyGeneration();

  }

  CommonFieldsGenerationInfoEnabled& operator=(

      CommonFieldsGenerationInfoEnabled&&) = default;

  // Whether we should rehash on insert in order to detect bugs of using invalid

  // references. We rehash on the first insertion after reserved_growth_ reaches

  // 0 after a call to reserve. We also do a rehash with low probability

  // whenever reserved_growth_ is zero.

  bool should_rehash_for_bug_detection_on_insert(const ctrl_t* ctrl,

                                                 size_t capacity) const;

  void maybe_increment_generation_on_insert() {

    if (reserved_growth_ == kReservedGrowthJustRanOut) reserved_growth_ = 0;

    if (reserved_growth_ > 0) {

      if (--reserved_growth_ == 0) reserved_growth_ = kReservedGrowthJustRanOut;

    } else {

      *generation_ = NextGeneration(*generation_);

    }

  }

  void reset_reserved_growth(size_t reservation, size_t size) {

    reserved_growth_ = reservation - size;

  }

  size_t reserved_growth() const { return reserved_growth_; }

  void set_reserved_growth(size_t r) { reserved_growth_ = r; }

  size_t reservation_size() const { return reservation_size_; }

  void set_reservation_size(size_t r) { reservation_size_ = r; }

  GenerationType generation() const { return *generation_; }

  void set_generation(GenerationType g) { *generation_ = g; }

  GenerationType* generation_ptr() const { return generation_; }

  void set_generation_ptr(GenerationType* g) { generation_ = g; }

 private:

  // The number of insertions remaining that are guaranteed to not rehash due to

  // a prior call to reserve. Note: we store reserved growth in addition to

  // reservation size because calls to erase() decrease size_ but don't decrease

  // reserved growth.

  size_t reserved_growth_ = 0;

  // The maximum argument to reserve() since the container was cleared. We need

  // to keep track of this, in addition to reserved growth, because we reset

  // reserved growth to this when erase(begin(), end()) is called.

  size_t reservation_size_ = 0;

  // Pointer to the generation counter, which is used to validate iterators and

  // is stored in the backing array between the control bytes and the slots.

  // Note that we can't store the generation inside the container itself and

  // keep a pointer to the container in the iterators because iterators must

  // remain valid when the container is moved.

  // Note: we could derive this pointer from the control pointer, but it makes

  // the code more complicated, and there's a benefit in having the sizes of

  // raw_hash_set in sanitizer mode and non-sanitizer mode a bit more different,

  // which is that tests are less likely to rely on the size remaining the same.

  GenerationType* generation_ = EmptyGeneration();

};

class CommonFieldsGenerationInfoDisabled {

 public:

  CommonFieldsGenerationInfoDisabled() = default;

  CommonFieldsGenerationInfoDisabled(CommonFieldsGenerationInfoDisabled&&) =

      default;

  CommonFieldsGenerationInfoDisabled& operator=(

      CommonFieldsGenerationInfoDisabled&&) = default;

  bool should_rehash_for_bug_detection_on_insert(const ctrl_t*, size_t) const {

    return false;

  }

  void maybe_increment_generation_on_insert() {}

  void reset_reserved_growth(size_t, size_t) {}

  size_t reserved_growth() const { return 0; }

  void set_reserved_growth(size_t) {}

  size_t reservation_size() const { return 0; }

  void set_reservation_size(size_t) {}

  GenerationType generation() const { return 0; }

  void set_generation(GenerationType) {}

  GenerationType* generation_ptr() const { return nullptr; }

  void set_generation_ptr(GenerationType*) {}

};

class HashSetIteratorGenerationInfoEnabled {

 public:

  HashSetIteratorGenerationInfoEnabled() = default;

  explicit HashSetIteratorGenerationInfoEnabled(

      const GenerationType* generation_ptr)

      : generation_ptr_(generation_ptr), generation_(*generation_ptr) {}

  GenerationType generation() const { return generation_; }

  void reset_generation() { generation_ = *generation_ptr_; }

  const GenerationType* generation_ptr() const { return generation_ptr_; }

  void set_generation_ptr(const GenerationType* ptr) { generation_ptr_ = ptr; }

 private:

  const GenerationType* generation_ptr_ = EmptyGeneration();

  GenerationType generation_ = *generation_ptr_;

};

class HashSetIteratorGenerationInfoDisabled {

 public:

  HashSetIteratorGenerationInfoDisabled() = default;

  explicit HashSetIteratorGenerationInfoDisabled(const GenerationType*) {}

  GenerationType generation() const { return 0; }

  void reset_generation() {}

  const GenerationType* generation_ptr() const { return nullptr; }

  void set_generation_ptr(const GenerationType*) {}

};

#ifdef ABSL_SWISSTABLE_ENABLE_GENERATIONS

using CommonFieldsGenerationInfo = CommonFieldsGenerationInfoEnabled;

using HashSetIteratorGenerationInfo = HashSetIteratorGenerationInfoEnabled;

#else

using CommonFieldsGenerationInfo = CommonFieldsGenerationInfoDisabled;

using HashSetIteratorGenerationInfo = HashSetIteratorGenerationInfoDisabled;

#endif

// Returns whether `n` is a valid capacity (i.e., number of slots).

//

// A valid capacity is a non-zero integer `2^m - 1`.

inline bool IsValidCapacity(size_t n) { return ((n + 1) & n) == 0 && n > 0; }

// Computes the offset from the start of the backing allocation of control.

// infoz and growth_left are stored at the beginning of the backing array.

inline size_t ControlOffset(bool has_infoz) {

  return (has_infoz ? sizeof(HashtablezInfoHandle) : 0) + sizeof(size_t);

}

// Returns the number of "cloned control bytes".

//

// This is the number of control bytes that are present both at the beginning

// of the control byte array and at the end, such that we can create a

// `Group::kWidth`-width probe window starting from any control byte.

constexpr size_t NumClonedBytes() { return Group::kWidth - 1; }

// Given the capacity of a table, computes the offset (from the start of the

// backing allocation) of the generation counter (if it exists).

inline size_t GenerationOffset(size_t capacity, bool has_infoz) {

  assert(IsValidCapacity(capacity));

  const size_t num_control_bytes = capacity + 1 + NumClonedBytes();

  return ControlOffset(has_infoz) + num_control_bytes;

}

// Given the capacity of a table, computes the offset (from the start of the

// backing allocation) at which the slots begin.

inline size_t SlotOffset(size_t capacity, size_t slot_align, bool has_infoz) {

  assert(IsValidCapacity(capacity));

  return (GenerationOffset(capacity, has_infoz) + NumGenerationBytes() +

          slot_align - 1) &

         (~slot_align + 1);

}

// Given the capacity of a table, computes the total size of the backing

// array.

inline size_t AllocSize(size_t capacity, size_t slot_size, size_t slot_align,

                        bool has_infoz) {

  return SlotOffset(capacity, slot_align, has_infoz) + capacity * slot_size;

}

// CommonFields hold the fields in raw_hash_set that do not depend

// on template parameters. This allows us to conveniently pass all

// of this state to helper functions as a single argument.

class CommonFields : public CommonFieldsGenerationInfo {

 public:

  CommonFields() = default;

  // Not copyable

  CommonFields(const CommonFields&) = delete;

  CommonFields& operator=(const CommonFields&) = delete;

  // Movable

  CommonFields(CommonFields&& that)

      : CommonFieldsGenerationInfo(

            std::move(static_cast<CommonFieldsGenerationInfo&&>(that))),

        // Explicitly copying fields into "this" and then resetting "that"

        // fields generates less code then calling absl::exchange per field.

        control_(that.control()),

        slots_(that.slot_array()),

        capacity_(that.capacity()),

        size_(that.size_) {

    that.set_control(EmptyGroup());

    that.set_slots(nullptr);

    that.set_capacity(0);

    that.size_ = 0;

  }

  CommonFields& operator=(CommonFields&&) = default;

  ctrl_t* control() const { return control_; }

  void set_control(ctrl_t* c) { control_ = c; }

  void* backing_array_start() const {

    // growth_left (and maybe infoz) is stored before control bytes.

    assert(reinterpret_cast<uintptr_t>(control()) % alignof(size_t) == 0);

    return control() - ControlOffset(has_infoz());

  }

  // Note: we can't use slots() because Qt defines "slots" as a macro.

  void* slot_array() const { return slots_; }

  void set_slots(void* s) { slots_ = s; }

  // The number of filled slots.

  size_t size() const { return size_ >> HasInfozShift(); }

  void set_size(size_t s) {

    size_ = (s << HasInfozShift()) | (size_ & HasInfozMask());

  }

  void increment_size() {

    assert(size() < capacity());

    size_ += size_t{1} << HasInfozShift();

  }

  void decrement_size() {

    assert(size() > 0);

    size_ -= size_t{1} << HasInfozShift();

  }

  // The total number of available slots.

  size_t capacity() const { return capacity_; }

  void set_capacity(size_t c) {

    assert(c == 0 || IsValidCapacity(c));

    capacity_ = c;

  }

  // The number of slots we can still fill without needing to rehash.

  // This is stored in the heap allocation before the control bytes.

  size_t growth_left() const {

    const size_t* gl_ptr = reinterpret_cast<size_t*>(control()) - 1;

    assert(reinterpret_cast<uintptr_t>(gl_ptr) % alignof(size_t) == 0);

    return *gl_ptr;

  }

  void set_growth_left(size_t gl) {

    size_t* gl_ptr = reinterpret_cast<size_t*>(control()) - 1;

    assert(reinterpret_cast<uintptr_t>(gl_ptr) % alignof(size_t) == 0);

    *gl_ptr = gl;

  }

  bool has_infoz() const {

    return ABSL_PREDICT_FALSE((size_ & HasInfozMask()) != 0);

  }

  void set_has_infoz(bool has_infoz) {

    size_ = (size() << HasInfozShift()) | static_cast<size_t>(has_infoz);

  }

  HashtablezInfoHandle infoz() {

    return has_infoz()

               ? *reinterpret_cast<HashtablezInfoHandle*>(backing_array_start())

               : HashtablezInfoHandle();

  }

  void set_infoz(HashtablezInfoHandle infoz) {

    assert(has_infoz());

    *reinterpret_cast<HashtablezInfoHandle*>(backing_array_start()) = infoz;

  }

  bool should_rehash_for_bug_detection_on_insert() const {

    return CommonFieldsGenerationInfo::

        should_rehash_for_bug_detection_on_insert(control(), capacity());

  }

  void reset_reserved_growth(size_t reservation) {

    CommonFieldsGenerationInfo::reset_reserved_growth(reservation, size());

  }

  // The size of the backing array allocation.

  size_t alloc_size(size_t slot_size, size_t slot_align) const {

    return AllocSize(capacity(), slot_size, slot_align, has_infoz());

  }

  // Returns the number of control bytes set to kDeleted. For testing only.

  size_t TombstonesCount() const {

    return static_cast<size_t>(