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

//     uint64_t growth_left_overflow;  // optional

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

#include <cassert>

#include <cmath>

#include <cstddef>

#include <cstdint>

#include <cstring>

#include <functional>

#include <initializer_list>

#include <iterator>

#include <limits>

#include <memory>

#include <optional>

#include <tuple>

#include <type_traits>

#include <typeindex>

#include <utility>

#include <variant>

#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/internal/unaligned_access.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/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/strings/string_view.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

// ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b)

//

// Informs the compiler that the two pointer arguments point into separately

// allocated storage (either different variable definitions or different dynamic

// storage allocations), allowing the compiler to assume they do not alias for

// optimization purposes. Differences from __restrict:

//  - __restrict only applies to the pointer itself, not the pointed-to object.

//  - This macro allows the compiler to optimize caller code, not just the

//    pointer dereferences of a function argument within that function.

//

// WARNING: If the arguments point into the same storage, the program has

// undefined behavior. Note that the definition of "storage" here refers to the

// outermost enclosing allocation of any particular object (for example, it is

// never correct to call this macro passing the addresses of fields in the same

// struct, elements of the same array, objects on the same arena block, etc.).

// Note that in the example below, the annotation will affect callers of

// SetFirstAndGetSize as well (they may be mis-compiled if the arguments are not

// from separate allocations).

//

// See

// https://clang.llvm.org/docs/LanguageExtensions.html#builtin-assume-separate-storage

//

// Example:

//

//   class Buffer {

//    public:

//     size_t* data() {

//       // Safe because `data_` is allocated via `::operator new`, so it is

//       // guaranteed to be in a separate allocation from `*this`.

//       ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(data_, this);

//       return data_;

//     }

//     size_t size() const { return size_; }

//

//    private:

//     size_t* data_ = new size_t[10];

//     size_t size_ = 10;

//   };

//

//   size_t SetFirstAndGetSize(Buffer& buf) {

//     size_t n = buf.size();

//     buf.data()[0] = n;

//     // After inlining, the compiler knows storing to `buf.data()[0]` cannot

//     // clobber `buf.size_`, and can return `n` without reloading `buf.size_`.

//     return buf.size();

//   }

#if ABSL_HAVE_BUILTIN(__builtin_assume_separate_storage)

#define ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) \

  __builtin_assume_separate_storage(a, b)

#elif ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L

#define ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) \

  (decltype((void)(a), (void)(b))())

#else

#define ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) \

  (false ? ((void)(a), (void)(b)) : void())

#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 NDEBUG

inline constexpr bool kIsDebug = false;

#else

inline constexpr bool kIsDebug = true;

#endif

constexpr bool SwisstableDebugEnabled() {

#if defined(ABSL_SWISSTABLE_ENABLE_GENERATIONS) || ABSL_OPTION_HARDENED == 1

  return true;

#else

  return kIsDebug;

#endif

}

#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() {

  if constexpr (kIsDebug) {

    return true;

  } else {

    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 {};

template <typename T, template <typename...> class Template>

struct is_instance_of : std::false_type {};

template <template <typename...> class Template, typename... Args>

struct is_instance_of<Template<Args...>, Template> : 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 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.

class HashtableCapacity {

 public:

  static constexpr HashtableCapacity CreateDestroyed() {

    return HashtableCapacity(kDestroyed);

  }

  static constexpr HashtableCapacity CreateReentrance() {

    return HashtableCapacity(kReentrance);

  }

  static constexpr HashtableCapacity CreateMovedFrom() {

    return HashtableCapacity(kMovedFrom);

  }

  static constexpr HashtableCapacity CreateSelfMovedFrom() {

    return HashtableCapacity(kSelfMovedFrom);

  }

  explicit HashtableCapacity(uninitialized_tag_t) {}

  explicit constexpr HashtableCapacity(size_t capacity)

      : capacity_data_(static_cast<uint8_t>(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 HashtableCapacity FromRawData(uint64_t capacity) {

    auto cap = HashtableCapacity(uninitialized_tag_t{});

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

    return cap;

  }

  uint8_t 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 (size_t{1} << capacity_data_) - 1;

  }

  constexpr bool is_small() const {

    // Small tables have capacity 0 or 1.

    // 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 : uint8_t {

    kAboveMaxValidCapacity = 64 - 10,

    kReentrance,

    kDestroyed,

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

    kMovedFrom,

    kSelfMovedFrom,

  };

  explicit constexpr HashtableCapacity(InvalidCapacity capacity)

      : capacity_data_(capacity) {

    ABSL_SWISSTABLE_ASSERT(capacity_data_ > kAboveMaxValidCapacity);

  }

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

  uint8_t capacity_data_;

};

// Returns next per-table seed.

uint8_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.

class PerTableSeed {

 public:

  // Returns the seed for the table.

  size_t seed() const { return seed_; }

 private:

  friend class HashtableInlineData;

  explicit PerTableSeed(uint64_t seed)

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

  const uint16_t 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_;

};

// 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()`.

//

// GrowthInfoLowerBound is stored as 8 bits in HashtableInlineData.

// For capacity > kMaxGrowthLeftLowerBound we additionally store 8 bytes

// at the beginning of the backing array. Storing GrowthInfoLowerBound in

// HashtableInlineData 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. GrowthInfo

// overflow for capacity > kMaxGrowthLeftLowerBound is stored as unaligned

// uint64_t.

// 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 size_t kMaxGrowthLeftLowerBound = 127;

  static_assert(kMaxGrowthLeftLowerBound == kGrowthLeftMask);

  explicit constexpr GrowthInfoLowerBound(uint8_t growth_left)

      : growth_left_(growth_left) {}

  // Returns the raw one byte encoded value of the GrowthInfoLowerBound.

  uint8_t ToRawData() const { return 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_;

};

// 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) kSeedBitCount bits for the seed. (For SOO tables, the lowest bit of the

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

class HashtableInlineData {

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

  static constexpr size_t kSeedBitCount = 5;

 public:

  static constexpr size_t kGrowthInfoLowerBoundBitCount = 8;

  static constexpr size_t kBlockedElementBitCount = 3;

  static constexpr size_t kMaxBlockedElementCount =

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

  static constexpr size_t kCapacityBitCount = 6;

  static constexpr size_t kHasInfozShift = kCapacityBitCount;

  // We have one unused bit so that the seed is within a single byte of `data_`.

  // This allows `gbswap_64` in `absl::Hash` to simplify to a single shift.

  static constexpr size_t kSeedShift =

      kHasInfozShift + /*has_infoz*/ 1 + /*unused*/ 1;

  static constexpr size_t kSizeBitCount =

      64 -

      (kBlockedElementBitCount + kSeedBitCount + kGrowthInfoLowerBoundBitCount +

       /*unused*/ 1 + /*has_infoz*/ 1 + kCapacityBitCount);

  explicit HashtableInlineData(uninitialized_tag_t) {}

  explicit HashtableInlineData(HashtableCapacity capacity, no_seed_empty_tag_t)

      : data_(CapacityBits(capacity)) {}

  HashtableInlineData(HashtableCapacity capacity, full_soo_tag_t,

                      bool has_tried_sampling)

      : data_(CapacityBits(capacity) | kSizeOneNoMetadata |

              (has_tried_sampling ? kSooHasTriedSamplingMask : 0)) {}

  HashtableCapacity capacity() const {

    return HashtableCapacity::FromRawData(

        static_cast<uint8_t>(data_ & kCapacityMask));

  }

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

  void set_capacity(HashtableCapacity c) {

    data_ = (data_ & ~kCapacityMask) | CapacityBits(c);

  }

  // Allow for preventing the compiler from optimizing away the store.

  void set_capacity(HashtableCapacity c) volatile {

    data_ = (data_ & ~kCapacityMask) | CapacityBits(c);

  }

  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 a small table (capacity <= 1) is empty.

  bool empty_when_small() const {

    ABSL_SWISSTABLE_ASSERT(is_small());

    ABSL_SWISSTABLE_ASSERT(size() <= 1);

    return (data_ & kSizeOneNoMetadata) == 0;

  }

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

  bool is_sampled_seed() const { return seed().seed() == kSeedMask; }

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

  GrowthInfoLowerBound growth_info_lower_bound() const {

    ABSL_SWISSTABLE_ASSERT(!is_small() &&

                           "we do not track growth for small tables");

    return GrowthInfoLowerBound(static_cast<uint8_t>(

        (data_ & kGrowthInfoLowerBoundMask) >> kGrowthInfoLowerBoundShift));

  }

  void set_growth_info_lower_bound(

      GrowthInfoLowerBound growth_info_lower_bound) {

    data_ = (data_ & ~kGrowthInfoLowerBoundMask) |

            (uint64_t{growth_info_lower_bound.ToRawData()}

             << kGrowthInfoLowerBoundShift);

  }

  // Overwrites single empty slot with a full slot.

  // Must be called when growth left lower bound is positive.

  void overwrite_empty_as_full() {

    ABSL_SWISSTABLE_ASSERT(growth_info_lower_bound().GetGrowthLeft() > 0);

    data_ -= kGrowthInfoLowerBoundOne;

  }

  // Overwrites single full slot with an empty slot.

  // Must be called when growth left lower bound is less than

  // kMaxGrowthLeftLowerBound.

  void overwrite_full_as_empty_in_lower_bound() {

    increment_growth_info_lower_bound(1);

  }

  // Increments the growth left lower bound by the given increment.

  // Must be called when the growth left lower bound + increment does not exceed

  // kMaxGrowthLeftLowerBound.

  void increment_growth_info_lower_bound(size_t increment) {

    ABSL_SWISSTABLE_ASSERT(growth_info_lower_bound().GetGrowthLeft() +

                               increment <=

                           GrowthInfoLowerBound::kMaxGrowthLeftLowerBound);

    data_ += increment << kGrowthInfoLowerBoundShift;

  }

  // Overwrites specified control element with full slot.

  // Must be called when growth left lower bound is >= IsEmpty(ctrl).

  void overwrite_control_as_full(ctrl_t ctrl) {

    ABSL_SWISSTABLE_ASSERT(growth_info_lower_bound().GetGrowthLeft() >=

                           static_cast<size_t>(IsEmpty(ctrl)));

    data_ -= static_cast<size_t>(IsEmpty(ctrl)) << kGrowthInfoLowerBoundShift;

  }

  // Overwrites single full slot with a deleted slot.

  void overwrite_full_as_deleted() {

    data_ |= (GrowthInfoLowerBound::kDeletedBit << kGrowthInfoLowerBoundShift);

  }

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

 private:

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

  // (40 bits)      : size

  // (8 bits)       : growth_info_lower_bound

  // (3 bits)       : blocked_element_count

  // (5 bits)       : seed

  // (1 bit)        : unused

  // (1 bit)        : has_infoz

  // (6 bits)       : capacity (the low 6 bits of the first byte)

  // Note: for size to overflow would require ~2^43 bytes of RAM, which is

  // impractical. We don't split these components of `data_` into separate bit

  // field elements because we get worse generated code that way.

  // TODO(ezb): if we have 41 bits for size, then on ARM, we will be able to use

  // a single instruction for size increase/decrease.

  static constexpr size_t kSizeShift = 64 - kSizeBitCount;

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

  static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1;

  static constexpr uint64_t kCapacityMask = (1 << kCapacityBitCount) - 1;

  static constexpr uint64_t kHasInfozMask = uint64_t{1} << kHasInfozShift;

  static constexpr uint64_t kSeedMask = ((uint64_t{1} << kSeedBitCount) - 1)

                                        << kSeedShift;

  static constexpr uint64_t kBlockedElementsShift = kSeedShift + kSeedBitCount;

  static constexpr uint64_t kBlockedElementMask = kMaxBlockedElementCount

                                                  << kBlockedElementsShift;

  static constexpr uint64_t kGrowthInfoLowerBoundShift =

      kBlockedElementsShift + kBlockedElementBitCount;

  static constexpr uint64_t kGrowthInfoLowerBoundOne =

      uint64_t{1} << kGrowthInfoLowerBoundShift;

  static constexpr uint64_t kGrowthInfoLowerBoundMask =

      uint64_t{0xff} << kGrowthInfoLowerBoundShift;

  static_assert(kGrowthInfoLowerBoundShift + kGrowthInfoLowerBoundBitCount ==

                kSizeShift);

  // For SOO tables, the seed is unused, and its lowest bit is repurposed to

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

  static constexpr uint64_t kSooHasTriedSamplingMask = uint64_t{1}

                                                       << kSeedShift;

  // 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 uint8_t kSampledSeed = (1 << kSeedBitCount) - 1;

  // Keep the seed within the second byte of `data_` so that `gbswap_64` on

  // `data_ & kSeedMask` in `absl::Hash` simplifies to a single shift.

  static_assert(kSeedShift == 8);

  static_assert(kSeedShift + kSeedBitCount <= 16);

  // Returns the bits of `data_` that encode `capacity`.

  static uint64_t CapacityBits(HashtableCapacity capacity) {

    return uint64_t{capacity.ToRawData()};

  }

  void set_seed(uint8_t seed) {

    data_ = (data_ & ~kSeedMask) | ((uint64_t{seed} << kSeedShift) & kSeedMask);

  }

  uint64_t data_;

};

static_assert(sizeof(HashtableCapacity) == 1);

static_assert(sizeof(HashtableInlineData) == 8);

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