// 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

// [https://en.wikipedia.org/wiki/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.

//

// 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_;  // optional

//     // Additional number that can be added to growth_left_lower_bound.

//     // Only stored for tables with large capacities.

//     uint8_t growth_left_overflow[7];  // optional

//     // The minimum number of elements we can insert before growing the

//     // capacity.

//     uint8_t growth_left_lower_bound;

//     // 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 `RawHashSetLayout::alloc_size` 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.

//

// # Small Object Optimization (SOO)

//

// When the size/alignment of the value_type and the capacity of the table are

// small, we enable small object optimization and store the values inline in

// the raw_hash_set object. This optimization allows us to avoid

// allocation/deallocation as well as cache/dTLB misses.

//

// # 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; tables smaller than one probing

// group 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 <functional>

#include <initializer_list>

#include <iterator>

#include <limits>

#include <memory>

#include <tuple>

#include <type_traits>

#include <utility>

#include "absl/base/attributes.h"

#include "absl/base/casts.h"

#include "absl/base/config.h"

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

#include "absl/base/internal/iterator_traits.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"  // IWYU pragma: export // for node_handle

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

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

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

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

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

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

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

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

#include "absl/functional/function_ref.h"

#include "absl/hash/hash.h"

#include "absl/hash/internal/weakly_mixed_integer.h"

#include "absl/memory/memory.h"

#include "absl/meta/type_traits.h"

#include "absl/numeric/bits.h"

#include "absl/utility/utility.h"

#if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L

#include <ranges>  // NOLINT(build/c++20)

#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_HWADDRESS_SANITIZER) || \

       defined(ABSL_HAVE_MEMORY_SANITIZER)) &&   \

    !defined(NDEBUG_SANITIZER)  // If defined, performance is important.

// 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

#ifdef ABSL_SWISSTABLE_ASSERT

#error ABSL_SWISSTABLE_ASSERT cannot be directly set

#else

// We use this macro for assertions that users may see when the table is in an

// invalid state that sanitizers may help diagnose.

#define ABSL_SWISSTABLE_ASSERT(CONDITION) \

  assert((CONDITION) && "Try enabling sanitizers.")

#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

constexpr bool SwisstableGenerationsOrDebugEnabled() {

#ifndef NDEBUG

  return true;

#endif

  return SwisstableGenerationsEnabled();

}

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([[maybe_unused]] AllocType& lhs, [[maybe_unused]] AllocType& rhs,

               std::false_type /* propagate_on_container_swap */) {

  assert(lhs == rhs &&

         "It's UB to call swap with unequal non-propagating allocators.");

}

template <typename AllocType>

void CopyAlloc(AllocType& lhs, AllocType& rhs,

               std::true_type /* propagate_alloc */) {

  lhs = rhs;

}

template <typename AllocType>

void CopyAlloc(AllocType&, AllocType&, std::false_type /* propagate_alloc */) {}

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<

    std::void_t<decltype(Policy::apply(

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

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

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

ABSL_DLL extern char kDefaultIterSlot;

// Returns a pointer to a control byte that can be used by default-constructed

// iterators. We don't expect this pointer to be dereferenced.

inline void* DefaultIterSlot() { return &kDefaultIterSlot; }

// For use in SOO iterators.

// TODO(b/289225379): we could potentially get rid of this by adding an is_soo

// bit in iterators. This would add branches but reduce cache misses.

ABSL_DLL extern const ctrl_t kSooControl[2];

// Returns a pointer to a full byte followed by a sentinel byte.

inline ctrl_t* SooControl() {

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

  // to it because it is only used for SOO iterators.

  return const_cast<ctrl_t*>(kSooControl);

}

// Whether ctrl is from the SooControl array.

inline bool IsSooControl(const ctrl_t* ctrl) { return ctrl == SooControl(); }

// For use in iterators returned by `insert` and similar.

ABSL_DLL extern const ctrl_t kInsertIteratorControl[2];

// Returns a pointer to a full byte followed by a sentinel byte.

inline ctrl_t* InsertIteratorControl() {

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

  // to it because it is only used for iterators returned by `insert` and

  // similar.

  return const_cast<ctrl_t*>(kInsertIteratorControl);

}

// Whether ctrl is special value for iterators returned by `insert` and similar.

inline bool IsInsertIteratorControl(const ctrl_t* ctrl) {

  return ctrl == InsertIteratorControl();

}

// 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();

}

// We only allow a maximum of 1 SOO element, which makes the implementation

// much simpler. Complications with multiple SOO elements include:

// - Satisfying the guarantee that erasing one element doesn't invalidate

//   iterators to other elements means we would probably need actual SOO

//   control bytes.

// - In order to prevent user code from depending on iteration order for small

//   tables, we would need to randomize the iteration order somehow.

constexpr size_t SooCapacity() { return 1; }

// Maximum capacity of a table where we don't need to hash any keys.

inline constexpr size_t kMaxSmallCapacity = 1;

// Sentinel type to indicate SOO CommonFields construction.

struct soo_tag_t {};

// Sentinel type to indicate SOO CommonFields construction with full size.

struct full_soo_tag_t {};

// Sentinel type to indicate non-SOO CommonFields construction.

struct non_soo_tag_t {};

// Sentinel value to indicate an uninitialized value explicitly.

struct uninitialized_tag_t {};

// Sentinel value to indicate creation of an empty table without a seed.

struct no_seed_empty_tag_t {};

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

//

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

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

// Whether a table is small enough that we don't need to hash any keys.

constexpr bool IsSmallCapacity(size_t capacity) {

  return capacity <= kMaxSmallCapacity;

}

// Whether a table fits entirely into a probing group.

// Arbitrary order of elements in such tables is correct.

constexpr bool is_single_group(size_t capacity) {

  return capacity <= Group::kWidth;

}

// Whether `cap` is a valid capacity for a table that can store blocked

// elements.

constexpr bool IsCapacityValidForBlockedElements(size_t cap) {

  return !IsSmallCapacity(cap);

}

// Converts `n` into the next valid capacity, per `IsValidCapacity`.

constexpr size_t NormalizeCapacity(size_t n) {

  return n ? ~size_t{} >> countl_zero(n) : 1;

}

// Returns the next valid capacity after `n`.

constexpr size_t NextCapacity(size_t n) {

  ABSL_SWISSTABLE_ASSERT(IsValidCapacity(n) || n == 0);

  return n * 2 + 1;

}

// Returns the previous valid capacity before `n`.

constexpr size_t PreviousCapacity(size_t n) {

  ABSL_SWISSTABLE_ASSERT(IsValidCapacity(n));

  return n / 2;

}

// General notes on capacity/growth methods below:

// - We use 7/8th as maximum load factor. For 16-wide groups, that gives an

//   average of two empty slots per group.

// - For (capacity+1) < Group::kWidth, growth == capacity. In this case, we

//   never need to probe (the whole table fits in one group) so we don't need a

//   load factor less than 1.

// - For tables with capacity <= kMaxCapacityForLoadFactorOne, we leave one

//   empty slot.

// - For capacity > kMaxCapacityForLoadFactorOne, growth is 7/8*capacity.

constexpr inline size_t kMaxCapacityForLoadFactorOne = Group::kWidth * 4 - 1;

// Given `capacity`, applies the load factor; i.e., it returns the maximum

// number of values we should put into the table before a resizing rehash.

constexpr size_t CapacityToGrowth(size_t capacity) {

  ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity));

  // `capacity*7/8`

  if (capacity <= kMaxCapacityForLoadFactorOne) {

    // For small capacities we leave at most one empty slot.

    return capacity - (capacity >= Group::kWidth - 1);

  }

  return capacity - capacity / 8;

}

// Given `size`, "unapplies" the load factor to find how large the capacity

// should be to stay within the load factor.

//

// For size == 0, returns 0.

// For other values, returns the same as `NormalizeCapacity(size*8/7)`.

constexpr size_t SizeToCapacity(size_t size) {

  if (size == 0) {

    return 0;

  }

  // The minimum possible capacity is NormalizeCapacity(size).

  // Shifting right `~size_t{}` by `leading_zeros` yields

  // NormalizeCapacity(size).

  int leading_zeros = absl::countl_zero(

      size +

      // Tables larger than half a group require at least one empty slot.

      (size >= Group::kWidth / 2));

  if (size < kMaxCapacityForLoadFactorOne) {

    return (~size_t{}) >> leading_zeros;

  }

  constexpr size_t kLast3Bits = size_t{7} << (sizeof(size_t) * 8 - 3);

  // max_size_for_next_capacity = max_load_factor * next_capacity

  //                            = (7/8) * (~size_t{} >> leading_zeros)

  //                            = (7/8*~size_t{}) >> leading_zeros

  //                            = kLast3Bits >> leading_zeros

  size_t max_size_for_next_capacity = kLast3Bits >> leading_zeros;

  // Decrease shift if size is too big for the minimum capacity.

  leading_zeros -= static_cast<int>(size > max_size_for_next_capacity);

  return (~size_t{}) >> leading_zeros;

}

// The mode we store capacity in the table.

enum HashtableCapacityStorageMode {

  // Capacity stored as size_t as a full number.

  kCapacityByValue,

  // Capacity stored as uint8_t as log2, i.e. capacity = 2^capacity_ - 1.

  kCapacityByLog,

};

// The number of slots in the backing array. This is always 2^N-1 for an

// integer N.

// NOTE: this class exists to simplify experiments with different ways to store

// capacity within size.

// NOTE: we tried experimenting with compressing the capacity and storing it

// together with size_: (a) using 6 bits to store the corresponding power (N in

// 2^N-1), and (b) storing 2^N as the most significant bit of size_ and storing

// size in the low bits. Both of these experiments were regressions, presumably

// because we need capacity to do find operations.

template <HashtableCapacityStorageMode StorageMode>

class HashtableCapacityImpl {

  using IntType =

      std::conditional_t<StorageMode == kCapacityByValue, size_t, uint8_t>;

 public:

  static constexpr HashtableCapacityImpl CreateDestroyed() {

    return HashtableCapacityImpl(kDestroyed);

  }

  static constexpr HashtableCapacityImpl CreateReentrance() {

    return HashtableCapacityImpl(kReentrance);

  }

  static constexpr HashtableCapacityImpl CreateMovedFrom() {

    return HashtableCapacityImpl(kMovedFrom);

  }

  static constexpr HashtableCapacityImpl CreateSelfMovedFrom() {

    return HashtableCapacityImpl(kSelfMovedFrom);

  }

  explicit HashtableCapacityImpl(uninitialized_tag_t) {}

  explicit constexpr HashtableCapacityImpl(size_t capacity)

      : capacity_data_(static_cast<IntType>(

            StorageMode == kCapacityByValue ? capacity

                                            : TrailingZeros(capacity + 1))) {

    ABSL_SWISSTABLE_ASSERT(capacity == 0 || IsValidCapacity(capacity));

  }

  // Creates capacity from the value that was returned by `ToRawData()`.

  // This is needed to use bitfield for capacity.

  // At least on Windows combination uint8_t and uint64_t bitfield in one struct

  // is not optimized by compiler.

  static HashtableCapacityImpl FromRawData(uint64_t capacity) {

    auto cap = HashtableCapacityImpl(uninitialized_tag_t{});

    cap.capacity_data_ = static_cast<IntType>(capacity);

    return cap;

  }

  IntType ToRawData() const { return capacity_data_; }

  constexpr bool IsValid() const {

    return capacity_data_ <= kAboveMaxValidCapacity;

  }

  constexpr bool IsDestroyed() const { return capacity_data_ == kDestroyed; }

  constexpr bool IsReentrance() const { return capacity_data_ == kReentrance; }

  // Returns true if the table is moved-from including self moved-from.

  constexpr bool IsMovedFrom() const { return capacity_data_ >= kMovedFrom; }

  constexpr bool IsSelfMovedFrom() const {

    return capacity_data_ == kSelfMovedFrom;

  }

  constexpr size_t capacity() const {

    ABSL_SWISSTABLE_ASSERT(IsValid());

    return StorageMode == kCapacityByValue ? capacity_data_

                                           : (size_t{1} << capacity_data_) - 1;

  }

  constexpr bool is_small() const {

    // Small tables have capacity 0 or 1. This expression is valid for both

    // capacity storage modes.

    // Comparing capacity_data_ directly leads to a better generated code.

    // One byte comparison is used before computing the capacity in order to

    // detect small tables faster for critical path.

    static_assert(kMaxSmallCapacity == 1);

    return capacity_data_ <= 1;

  }

 private:

  // We use these sentinel capacity values in debug mode to indicate different

  // classes of bugs.

  enum InvalidCapacity : IntType {

    kAboveMaxValidCapacity = (std::numeric_limits<IntType>::max)() - 100,

    kReentrance,

    kDestroyed,

    // These two must be last because we use `>= kMovedFrom` to mean moved-from.

    kMovedFrom,

    kSelfMovedFrom,

  };

  explicit constexpr HashtableCapacityImpl(InvalidCapacity capacity)

      : capacity_data_(capacity) {

    ABSL_SWISSTABLE_ASSERT(capacity_data_ > kAboveMaxValidCapacity);

  }

  // Capacity is stored as a value or as a log2 depending on `StorageMode`.

  IntType capacity_data_;

};

template <HashtableCapacityStorageMode StorageMode>

class HashtableInlineDataImpl;

// Returns next per-table seed.

uint16_t NextHashTableSeed();

// Per table hash salt. This gets mixed into H1 to randomize iteration order

// per-table.

// The seed is needed to ensure non-determinism of iteration order.

template <typename StorageType>

class PerTableSeedImpl {

 public:

  using IntType = StorageType;

  // The number of bits in the seed.

  // It is big enough to ensure non-determinism of iteration order.

  // We store the seed inside a uint64_t together with size and other metadata.

  // Using 8 or 16 bits allows us to save one `and` instruction in H1 (we use

  // zero-extended move instead of mov+and). When absl::Hash is inlined, it can

  // also have lower latency knowing that the high bits of the seed are zero.

  static constexpr size_t kBitCount = sizeof(IntType) * 8;

  // We need to use a constant seed when the table is sampled so that sampled

  // hashes use the same seed and can e.g. identify stuck bits accurately.

  static constexpr IntType kSampledSeed = static_cast<IntType>(~IntType{0});

  // Returns the seed for the table.

  size_t seed() const { return seed_; }

 private:

  template <HashtableCapacityStorageMode StorageMode>

  friend class HashtableInlineDataImpl;

  explicit PerTableSeedImpl(uint64_t seed)

      : seed_(static_cast<IntType>(seed)) {}

  const IntType seed_;

};

// Represents blocked elements info: log2_period and tail_blocked.

// Every `2**log2_period` is a blocked slot. The first blocked slot is at

// index `2**log2_period-1`. E.g. if log2_period is 2, then every 4th slot

// is blocked: 0, 1, 2, X, 4, 5, 6, X, ...

//

// tail_blocked is the number of blocked slots at the end in addition.

// E.g., log2_period = 2 and tail_blocked = 3, then there are 6 blocked for

// capacity = 15.

// slots: 0, 1, 2, X, 4, 5, 6, X, 8, 9, 10, X, X, X, X, S. (S = sentinel)

class BlockedInfo {

 public:

  constexpr BlockedInfo(uint8_t log2_period, uint8_t tail_blocked)

      : log2_period_(log2_period), tail_blocked_(tail_blocked) {

    ABSL_ASSUME(log2_period < 64);

  }

  // Returns the log2 of the period for blocked elements.

  // Every `2**K` element is blocked starting from index `2**K - 1`.

  constexpr uint8_t log2_period() const { return log2_period_; }

  // Returns the number of blocked elements at the end of the table.

  constexpr uint8_t tail_blocked() const { return tail_blocked_; }

  // Returns the number of blocked elements before the given index.

  // Doesn't account for tail_blocked because there are no useful indices in

  // the blocked tail.

  constexpr size_t blocked_before(size_t index) const {

    return index >> log2_period();

  }

  // Returns the number of blocked elements in the table.

  constexpr size_t total_blocked_count(size_t capacity) const {

    return blocked_before(capacity) + tail_blocked();

  }

 private:

  uint8_t log2_period_;

  uint8_t tail_blocked_;

};

// Capacity, size and also has additionally

// 1) one bit that stores whether we have infoz.

// 2) kBlockedElementsBitCount bits that stores number of blocked elements in

//    the table.

// 3) PerTableSeed::kBitCount bits for the seed. (For SOO tables, the lowest

//    bit of the seed is repurposed to track if sampling has been tried).

template <HashtableCapacityStorageMode StorageMode>

class HashtableInlineDataImpl {

 public:

  static constexpr HashtableCapacityStorageMode kStorageMode = StorageMode;

  using PerTableSeed = PerTableSeedImpl<

      std::conditional_t<StorageMode == kCapacityByValue, uint16_t, uint8_t>>;

  using HashtableCapacity = HashtableCapacityImpl<StorageMode>;

  static constexpr size_t kBlockedElementBitCount = 3;

  static constexpr size_t kMaxBlockedElementCount =

      (uint64_t{1} << kBlockedElementBitCount) - 1;

  static constexpr size_t kSizeBitCount =

      64 -

      (kBlockedElementBitCount + PerTableSeed::kBitCount + /*has_infoz*/ 1 +

       (StorageMode == kCapacityByValue ? 0 : sizeof(HashtableCapacity) * 8));

  explicit HashtableInlineDataImpl(uninitialized_tag_t) {}

  explicit HashtableInlineDataImpl(HashtableCapacity capacity,

                                   no_seed_empty_tag_t)

      : capacity_internal_(capacity.ToRawData()), data_(0) {}

  HashtableInlineDataImpl(HashtableCapacity capacity, full_soo_tag_t,

                          bool has_tried_sampling)

      : capacity_internal_(capacity.ToRawData()),

        data_(kSizeOneNoMetadata |

              (has_tried_sampling ? kSooHasTriedSamplingMask : 0)) {}

  HashtableCapacity capacity() const {

    return HashtableCapacity::FromRawData(capacity_internal_);

  }

  bool is_small() const { return capacity().is_small(); }

  void set_capacity(HashtableCapacity c) { capacity_internal_ = c.ToRawData(); }

  void set_capacity(size_t c) { set_capacity(HashtableCapacity(c)); }

  // Returns actual size of the table.

  size_t size() const { return static_cast<size_t>(data_ >> kSizeShift); }

  void increment_size() { data_ += kSizeOneNoMetadata; }

  void increment_size(size_t size) {

    data_ += static_cast<uint64_t>(size) << kSizeShift;

  }

  void decrement_size() { data_ -= kSizeOneNoMetadata; }

  // Returns true if the table is empty.

  bool empty() const { return data_ < kSizeOneNoMetadata; }

  // Returns true if an empty SOO table has already queried should_sample_soo().

  bool soo_has_tried_sampling() const {

    return (data_ & kSooHasTriedSamplingMask) != 0;

  }

  // Records that an empty SOO table has tried sampling.

  void set_soo_has_tried_sampling() { data_ |= kSooHasTriedSamplingMask; }

  // Sets the size, but keeps all the metadata bits.

  void set_size(size_t size) {

    data_ =

        (data_ & kMetadataMask) | (static_cast<uint64_t>(size) << kSizeShift);

  }

  PerTableSeed seed() const { return PerTableSeed(data_ & kSeedMask); }

  void generate_new_seed() {

    set_seed(static_cast<typename PerTableSeed::IntType>(NextHashTableSeed()));

  }

  // We need to use a constant seed when the table is sampled so that sampled

  // hashes use the same seed and can e.g. identify stuck bits accurately.

  void set_sampled_seed() { set_seed(PerTableSeed::kSampledSeed); }

  bool is_sampled_seed() const {

    return seed().seed() == PerTableSeed::kSampledSeed;

  }

  // Returns true if the table has infoz.

  bool has_infoz() const {

    return ABSL_PREDICT_FALSE((data_ & kHasInfozMask) != 0);

  }

  // Sets the has_infoz bit.

  void set_has_infoz() { data_ |= kHasInfozMask; }

  // Returns the number of blocked elements in the table.

  size_t blocked_element_count() const {

    return (data_ & kBlockedElementMask) >> kBlockedElementsShift;

  }

  // Initializes the number of blocked elements in the table.

  // Requires:

  //   1. `blocked_element_count() == 0`.

  //   2. `count <= kMaxBlockedElementCount`.

  void init_blocked_element_count(uint64_t count) {

    ABSL_SWISSTABLE_ASSERT(blocked_element_count() == 0);

    ABSL_SWISSTABLE_ASSERT(count <= kMaxBlockedElementCount);

    data_ |= count << kBlockedElementsShift;

  }

  void set_blocked_element_count_to_zero() { data_ &= ~kBlockedElementMask; }

  void set_no_seed_for_testing() { data_ &= ~kSeedMask; }

 private:

  // Bit layout of `data_` from MSB to LSB:

  // (44 bits)      : size

  // (3 bits)       : blocked_element_count

  // (1 bit)        : has_infoz

  // (16 or 8 bits) : seed

  // We don't split these components of `data_` into separate bit field elements

  // because we get worse generated code that way.

  static constexpr size_t kDataBitCount =

      PerTableSeed::kBitCount + 1 + kSizeBitCount + kBlockedElementBitCount;

  static constexpr size_t kSizeShift = kDataBitCount - kSizeBitCount;

  static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift;

  static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1;

  static constexpr uint64_t kSeedMask =

      (uint64_t{1} << PerTableSeed::kBitCount) - 1;

  // The next bit after the seed.

  static constexpr uint64_t kHasInfozMask = kSeedMask + 1;

  static constexpr uint64_t kBlockedElementsShift = PerTableSeed::kBitCount + 1;

  static constexpr uint64_t kBlockedElementMask = kMaxBlockedElementCount

                                                  << kBlockedElementsShift;

  // For SOO tables, the seed is unused, and bit 0 is repurposed to track

  // whether the table has already queried should_sample_soo().

  static constexpr uint64_t kSooHasTriedSamplingMask = 1;

  void set_seed(typename PerTableSeed::IntType seed) {

    data_ = (data_ & ~kSeedMask) | seed;

  }

  uint64_t capacity_internal_ : sizeof(HashtableCapacity) * 8;

  uint64_t data_ : kDataBitCount;

};

static_assert(

    sizeof(HashtableInlineDataImpl<kCapacityByValue>::HashtableCapacity) ==

    sizeof(size_t));

// NOTE: some platforms have this size to be equal to 12 for two reasons:

// 1) alignof(uint64_t) == 4.

// 2) sizeof(size_t) == sizeof(HashtableCapacityImpl<kCapacityByValue>) == 4.

static_assert(sizeof(HashtableInlineDataImpl<kCapacityByValue>) <= 16);

static_assert(

    sizeof(HashtableInlineDataImpl<kCapacityByLog>::HashtableCapacity) == 1);

static_assert(sizeof(HashtableInlineDataImpl<kCapacityByLog>) == 8);

#ifndef ABSL_SWISSTABLE_INTERNAL_ENABLE_CAPACITY_BY_VALUE

using HashtableInlineData = HashtableInlineDataImpl<kCapacityByLog>;

#else

using HashtableInlineData = HashtableInlineDataImpl<kCapacityByValue>;

#endif  // ABSL_SWISSTABLE_INTERNAL_ENABLE_CAPACITY_BY_VALUE

using PerTableSeed = HashtableInlineData::PerTableSeed;

using HashtableCapacity = HashtableInlineData::HashtableCapacity;

// For large tables, we limit the number of blocked elements to maintain O(1)

// average case lookup complexity.

constexpr size_t kMaxBlockedElementsForLargeTables = 5;

static_assert(kMaxBlockedElementsForLargeTables <=

              HashtableInlineData::kMaxBlockedElementCount);

// H1 is just the low bits of the hash.

inline size_t H1(size_t hash) { return hash; }

// Extracts the H2 portion of a hash: the 7 most significant bits.

//

// These are used as an occupied control byte.

inline h2_t H2(size_t hash) { return hash >> (sizeof(size_t) * 8 - 7); }

// 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(size_t capacity) const;

  // Similar to above, except that we don't depend on reserved_growth_.

  bool should_rehash_for_bug_detection_on_move(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 {

      increment_generation();

    }

  }

  void increment_generation() { *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(size_t) const { return false; }

  bool should_rehash_for_bug_detection_on_move(size_t) const { return false; }

  void maybe_increment_generation_on_insert() {}

  void increment_generation() {}

  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

// Stored the information regarding number of slots we can still fill

// without needing to rehash.

//

// We want to ensure sufficient number of empty slots in the table in order

// to keep probe sequences relatively short. Empty slot in the probe group

// is required to stop probing.

//

// Tombstones (kDeleted slots) are not included in the growth capacity,

// because we'd like to rehash when the table is filled with tombstones and/or

// full slots.

//

// GrowthInfo also stores a bit that encodes whether table may have any

// deleted slots.

// Most of the tables (>95%) have no deleted slots, so some functions can

// be more efficient with this information.

//

// Callers can also force a rehash via the standard `rehash(0)`,

// which will recompute this value as a side-effect.

//

// See also `CapacityToGrowth()`.

//

// GrowthInfo is stored as 1 or 8 bytes at the beginning of the backing array.

// For capacity <= kMaxGrowthLeftLowerBound we store single byte, otherwise we

// store 8 bytes. Byte before the first control byte for all tables is always

// used to store GrowthInfoLowerBound. That helps to avoid any branching in the

// hottest code accessing GrowthInfo. GrowthInfoLowerBound has 7 bits to store

// the growth left and 1 bit to store whether the table has any deleted slots.

// For capacity > kMaxGrowthLeftLowerBound we use another 7 bytes to store the

// full GrowthInfo. GrowthInfo for capacity > kMaxGrowthLeftLowerBound is stored

// as uint64_t in little endian encoding. Most significant 8 bits (last byte in

// little endian encoding) contains GrowthInfoLowerBound.

class GrowthInfoAccessor;

// One byte encoding of lower bound GrowthInfo.

// It encodes number of growth left from 0 to kMaxGrowthLeftLowerBound and

// whether the table has any deleted slots.

class GrowthInfoLowerBound {

 public:

  static constexpr uint8_t kGrowthLeftMask = 0x7Fu;

  static constexpr uint8_t kDeletedBit = 0x80u;

  static constexpr uint64_t kMaxGrowthLeftLowerBound = 127;

  static_assert(kMaxGrowthLeftLowerBound == kGrowthLeftMask);

  explicit constexpr GrowthInfoLowerBound(uint8_t growth_left)

      : growth_left_(growth_left) {}

  // Returns true if table satisfies two properties:

  // 1. Guaranteed to have no kDeleted slots.

  // 2. There is a place for at least one element to grow.

  constexpr bool HasNoDeletedAndGrowthLeft() const {

    return static_cast<int8_t>(growth_left_) > 0;

  }

  // Returns true if table satisfies two properties:

  // 1. May have kDeleted slots (kDeletedBit == 1).

  // 2. There is a place for at least one element to grow.

  constexpr bool HasDeletedAndGrowthLeft() const {

    return growth_left_ > kDeletedBit;

  }

  // Returns true if the table satisfies two properties:

  // 1. Guaranteed to have no kDeleted slots.

  // 2. There is no growth left.

  constexpr bool HasNoGrowthLeftAndNoDeleted() const {

    return growth_left_ == 0;

  }

  // Returns true if GetGrowthLeft() == 0 and HasNoDeleted() is false.

  // It is slightly more efficient.

  constexpr bool HasNoGrowthLeftAndHaveDeleted() const {

    return growth_left_ == kDeletedBit;

  }

  // Returns true if table guaranteed to have no kDeleted slots.

  constexpr bool HasNoDeleted() const {

    return (growth_left_ & kDeletedBit) == 0;

  }

  // Returns the minimum number of elements left to grow.

  // Use GrowthInfoView::GetGrowthLeftTotal() to get the total number of

  // elements left to grow. For tables with capacity <=

  // kMaxGrowthLeftLowerBound, this is the same as GetGrowthLeftTotal().

  constexpr uint8_t GetGrowthLeft() const {

    return growth_left_ & kGrowthLeftMask;

  }

 private:

  uint8_t growth_left_;

};

// GrowthInfo is stored in the backing array, and this class provides a simple

// interface to access and modify it.

class GrowthInfoAccessor {

 public:

  // GrowthInfoLowerBound is stored in the most significant 8 bits of the

  // full growth info.

  static constexpr uint64_t kLowerBoundShift = 64 - 8;

  explicit GrowthInfoAccessor(void* control)

      : growth_info_lower_bound_(reinterpret_cast<uint8_t*>(control) - 1 -

                                 NumGenerationBytes()) {}

  // Initializes the GrowthInfo assuming we can grow `growth_left` elements

  // and there are no kDeleted slots in the table.

  void InitGrowthLeftNoDeleted(size_t growth_left, size_t capacity);