// Copyright 2018 The Abseil Authors.

//

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

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

// You may obtain a copy of the License at

//

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

//

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

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

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

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

// limitations under the License.

//

// An open-addressing

// hashtable with quadratic probing.

//

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

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

//

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

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

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

// providing a typedef called `is_transparent`.

//

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

// they have an overload set like:

//

//   iterator find(const key_type& key);

//   template <class K>

//   iterator find(const K& key);

//

//   size_type erase(const key_type& key);

//   template <class K>

//   size_type erase(const K& key);

//

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

//   template <class K>

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

//

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

// exist.

//

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

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

// inserted.

//

// IMPLEMENTATION DETAILS

//

// # Table Layout

//

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

// that may or may not contain objects.

//

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

// pseudo-struct:

//

//   struct BackingArray {

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

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

//     HashtablezInfoHandle infoz_;

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

//     size_t growth_left;

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

//     ctrl_t ctrl[capacity];

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

//     // stop and serves no other purpose.

//     ctrl_t sentinel;

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

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

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

//     ctrl_t clones[kWidth - 1];

//     // The actual slot data.

//     slot_type slots[capacity];

//   };

//

// The length of this array is computed by `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"

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

// Returns true if we should assert that the table is not accessed after it has

// been destroyed or during the destruction of the table.

constexpr bool SwisstableAssertAccessToDestroyedTable() {

#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 */) {}

// The state for a probe sequence.

//

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

//

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

//

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

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

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

// to check an entire group with minimal branching.

//

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

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

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

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

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

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

//

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

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

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

template <size_t Width>

class probe_seq {

 public:

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

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

  // apply to each value in the progression.

  probe_seq(size_t hash, size_t mask) {

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

    mask_ = mask;

    offset_ = hash & mask_;

  }

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

  size_t offset() const { return offset_; }

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

  void next() {

    index_ += Width;

    offset_ += index_;

    offset_ &= mask_;

  }

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

  size_t index() const { return index_; }

 private:

  size_t mask_;

  size_t offset_;

  size_t index_ = 0;

};

template <class ContainerKey, class Hash, class Eq>

struct RequireUsableKey {

  template <class PassedKey, class... Args>

  std::pair<

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

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

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

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

};

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

struct IsDecomposable : std::false_type {};

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

struct IsDecomposable<

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

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

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

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

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

template <class T>

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

  using std::swap;

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

}

template <class T>

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

  return false;

}

ABSL_DLL extern ctrl_t kDefaultIterControl;

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

// classes of bugs.

enum InvalidCapacity : size_t {

  kAboveMaxValidCapacity = ~size_t{} - 100,

  kReentrance,

  kDestroyed,

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

  kMovedFrom,

  kSelfMovedFrom,

};

// 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 ctrl_t* DefaultIterControl() { return &kDefaultIterControl; }

// 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[17];

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

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

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

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

  // 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 16 bits allows us to save one `and` instruction in H1 (we use

  // sign-extended move instead of mov+and).

  static constexpr size_t kBitCount = 16;

  static constexpr size_t kSignBit = uint64_t{1} << (kBitCount - 1);

  // Returns the seed for the table.

  size_t seed() const {

    // We use a sign-extended load to ensure high bits are non-zero.

    int16_t seed_signed = absl::bit_cast<int16_t>(seed_);

    auto seed_sign_extended =

        static_cast<std::make_signed_t<size_t>>(seed_signed);

    return absl::bit_cast<size_t>(seed_sign_extended);

  }

 private:

  friend class HashtableSize;

  explicit PerTableSeed(uint16_t seed) : seed_(seed) {

    ABSL_SWISSTABLE_ASSERT((seed & kSignBit) != 0 || seed == 0);

  }

  // The most significant bit of the seed is always 1 when there is a non-zero

  // seed. This way, when sign-extended the seed has non-zero high bits.

  const uint16_t seed_;

};

// Returns next per-table seed.

inline uint16_t NextSeed() {

  static_assert(PerTableSeed::kBitCount == 16);

  thread_local uint16_t seed =

      static_cast<uint16_t>(reinterpret_cast<uintptr_t>(&seed));

  seed += uint16_t{0xad53};

  return seed;

}

// The size and also has additionally

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

// 2) PerTableSeed::kBitCount bits for the seed.

class HashtableSize {

 public:

  static constexpr size_t kSizeBitCount = 64 - PerTableSeed::kBitCount - 1;

  explicit HashtableSize(uninitialized_tag_t) {}

  explicit HashtableSize(no_seed_empty_tag_t) : data_(0) {}

  explicit HashtableSize(full_soo_tag_t) : data_(kSizeOneNoMetadata) {}

  // 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) * kSizeOneNoMetadata;

  }

  void decrement_size() { data_ -= kSizeOneNoMetadata; }

  // Returns true if the table is empty.

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

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

  void set_size_to_zero_keep_metadata() { data_ = data_ & kMetadataMask; }

  PerTableSeed seed() const {

    return PerTableSeed(static_cast<size_t>(data_) & kSeedMask);

  }

  void generate_new_seed() { set_seed(NextSeed()); }

  // 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::kSignBit); }

  bool is_sampled_seed() const {

    return (data_ & kSeedMask) == PerTableSeed::kSignBit;

  }

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

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

 private:

  void set_seed(uint16_t seed) {

    data_ = (data_ & ~kSeedMask) | (seed | PerTableSeed::kSignBit);

  }

  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 kSeedMask =

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

  // The next bit after the seed.

  static constexpr uint64_t kHasInfozMask = kSeedMask + 1;

  uint64_t data_;

};

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

class GrowthInfo {

 public:

  // Leaves data member uninitialized.

  GrowthInfo() = default;

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

    growth_left_info_ = growth_left;

  }

  // Overwrites single full slot with an empty slot.

  void OverwriteFullAsEmpty() { ++growth_left_info_; }

  // Overwrites single empty slot with a full slot.

  void OverwriteEmptyAsFull() {

    ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() > 0);

    --growth_left_info_;

  }

  // Overwrites several empty slots with full slots.

  void OverwriteManyEmptyAsFull(size_t count) {

    ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() >= count);

    growth_left_info_ -= count;

  }

  // Overwrites specified control element with full slot.

  void OverwriteControlAsFull(ctrl_t ctrl) {

    ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() >=

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

    growth_left_info_ -= static_cast<size_t>(IsEmpty(ctrl));

  }

  // Overwrites single full slot with a deleted slot.

  void OverwriteFullAsDeleted() { growth_left_info_ |= kDeletedBit; }

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

  bool HasNoDeletedAndGrowthLeft() const {

    return static_cast<std::make_signed_t<size_t>>(growth_left_info_) > 0;

  }

  // Returns true if the table satisfies two properties:

  // 1. Guaranteed to have no kDeleted slots.

  // 2. There is no growth left.

  bool HasNoGrowthLeftAndNoDeleted() const { return growth_left_info_ == 0; }

  // Returns true if GetGrowthLeft() == 0, but must be called only if

  // HasNoDeleted() is false. It is slightly more efficient.

  bool HasNoGrowthLeftAssumingMayHaveDeleted() const {

    ABSL_SWISSTABLE_ASSERT(!HasNoDeleted());

    return growth_left_info_ == kDeletedBit;

  }

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

  bool HasNoDeleted() const {

    return static_cast<std::make_signed_t<size_t>>(growth_left_info_) >= 0;

  }

  // Returns the number of elements left to grow.

  size_t GetGrowthLeft() const { return growth_left_info_ & kGrowthLeftMask; }

 private:

  static constexpr size_t kGrowthLeftMask = ((~size_t{}) >> 1);

  static constexpr size_t kDeletedBit = ~kGrowthLeftMask;

  // Topmost bit signal whenever there are deleted slots.

  size_t growth_left_info_;

};

static_assert(sizeof(GrowthInfo) == sizeof(size_t), "");

static_assert(alignof(GrowthInfo) == alignof(size_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 <= 1; }

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

//

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

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

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

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

// Returns the number of control bytes including cloned.

constexpr size_t NumControlBytes(size_t capacity) {

  return IsSmallCapacity(capacity) ? 0 : capacity + 1 + NumClonedBytes();

}

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

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

constexpr size_t ControlOffset(bool has_infoz) {

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

}

// Returns the offset of the next item after `offset` that is aligned to `align`

// bytes. `align` must be a power of two.

constexpr size_t AlignUpTo(size_t offset, size_t align) {

  return (offset + align - 1) & (~align + 1);

}

// Helper class for computing offsets and allocation size of hash set fields.

class RawHashSetLayout {

 public:

  // TODO(b/413062340): maybe don't allocate growth info for capacity 1 tables.

  // Doing so may require additional branches/complexity so it might not be

  // worth it.

  explicit RawHashSetLayout(size_t capacity, size_t slot_size,

                            size_t slot_align, bool has_infoz)

      : control_offset_(ControlOffset(has_infoz)),

        generation_offset_(control_offset_ + NumControlBytes(capacity)),

        slot_offset_(

            AlignUpTo(generation_offset_ + NumGenerationBytes(), slot_align)),

        alloc_size_(slot_offset_ + capacity * slot_size) {

    ABSL_SWISSTABLE_ASSERT(IsValidCapacity(capacity));

    ABSL_SWISSTABLE_ASSERT(

        slot_size <=

        ((std::numeric_limits<size_t>::max)() - slot_offset_) / capacity);

  }

  // Returns precomputed offset from the start of the backing allocation of

  // control.

  size_t control_offset() const { return control_offset_; }

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

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

  size_t generation_offset() const { return generation_offset_; }

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

  // backing allocation) at which the slots begin.

  size_t slot_offset() const { return slot_offset_; }

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

  // array.

  size_t alloc_size() const { return alloc_size_; }

 private:

  size_t control_offset_;

  size_t generation_offset_;

  size_t slot_offset_;

  size_t alloc_size_;

};

struct HashtableFreeFunctionsAccess;

// This allows us to work around an uninitialized memory warning when

// constructing begin() iterators in empty hashtables.

template <typename T>

union MaybeInitializedPtr {

  T* get() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(p); }

absl::container_internal::MaybeInitializedPtr<absl::container_internal::ctrl_t>::get() const

Line

Count

Source

866

153M

  T* get() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(p); }

absl::container_internal::MaybeInitializedPtr<void>::get() const

Line

Count

Source

866

98.1M

  T* get() const { ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(p); }

  void set(T* ptr) { p = ptr; }

absl::container_internal::MaybeInitializedPtr<absl::container_internal::ctrl_t>::set(absl::container_internal::ctrl_t*)

Line

Count

Source

867

162k

  void set(T* ptr) { p = ptr; }

absl::container_internal::MaybeInitializedPtr<void>::set(void*)

Line

Count

Source

867

162k

  void set(T* ptr) { p = ptr; }

  T* p;

};

struct HeapPtrs {

  // The control bytes (and, also, a pointer near to the base of the backing

  // array).

  //

  // This contains `capacity + 1 + NumClonedBytes()` entries.

  //

  // Note that growth_info is stored immediately before this pointer.

  // May be uninitialized for small tables.

  MaybeInitializedPtr<ctrl_t> control;

  // The beginning of the slots, located at `SlotOffset()` bytes after

  // `control`. May be uninitialized for empty tables.

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

  MaybeInitializedPtr<void> slot_array;

};

// Returns the maximum size of the SOO slot.

constexpr size_t MaxSooSlotSize() { return sizeof(HeapPtrs); }

// Manages the backing array pointers or the SOO slot. When raw_hash_set::is_soo

// is true, the SOO slot is stored in `soo_data`. Otherwise, we use `heap`.

union HeapOrSoo {

  MaybeInitializedPtr<ctrl_t>& control() {

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control);

  }

  MaybeInitializedPtr<ctrl_t> control() const {

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.control);

  }

  MaybeInitializedPtr<void>& slot_array() {

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.slot_array);

  }

  MaybeInitializedPtr<void> slot_array() const {

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap.slot_array);

  }

  void* get_soo_data() {

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(soo_data);

  }

  const void* get_soo_data() const {

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(soo_data);

  }

  HeapPtrs heap;

  unsigned char soo_data[MaxSooSlotSize()];

};

// Returns a reference to the GrowthInfo object stored immediately before

// `control`.

inline GrowthInfo& GetGrowthInfoFromControl(ctrl_t* control) {

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

  ABSL_SWISSTABLE_ASSERT(

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

  return *gl_ptr;

}

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

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

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

class CommonFields : public CommonFieldsGenerationInfo {

 public:

  explicit CommonFields(soo_tag_t)

      : capacity_(SooCapacity()), size_(no_seed_empty_tag_t{}) {}

  explicit CommonFields(full_soo_tag_t)

      : capacity_(SooCapacity()), size_(full_soo_tag_t{}) {}

  explicit CommonFields(non_soo_tag_t)

      : capacity_(0), size_(no_seed_empty_tag_t{}) {}

  // For use in swapping.

  explicit CommonFields(uninitialized_tag_t) : size_(uninitialized_tag_t{}) {}

  // Not copyable

  CommonFields(const CommonFields&) = delete;

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

  // Copy with guarantee that it is not SOO.

  CommonFields(non_soo_tag_t, const CommonFields& that)

      : capacity_(that.capacity_),

        size_(that.size_),

        heap_or_soo_(that.heap_or_soo_) {

  }

  // Movable

  CommonFields(CommonFields&& that) = default;

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

  template <bool kSooEnabled>

  static CommonFields CreateDefault() {

    return kSooEnabled ? CommonFields{soo_tag_t{}}

                       : CommonFields{non_soo_tag_t{}};

  }

  // The inline data for SOO is written on top of control_/slots_.

  const void* soo_data() const { return heap_or_soo_.get_soo_data(); }

  void* soo_data() { return heap_or_soo_.get_soo_data(); }

  ctrl_t* control() const {

    ABSL_SWISSTABLE_ASSERT(capacity() > 0);

    // Assume that the control bytes don't alias `this`.

    ctrl_t* ctrl = heap_or_soo_.control().get();

    [[maybe_unused]] size_t num_control_bytes = NumControlBytes(capacity());

    ABSL_ASSUME(reinterpret_cast<uintptr_t>(ctrl + num_control_bytes) <=

                    reinterpret_cast<uintptr_t>(this) ||

                reinterpret_cast<uintptr_t>(this + 1) <=

                    reinterpret_cast<uintptr_t>(ctrl));

    ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(ctrl);

  }

  void set_control(ctrl_t* c) { heap_or_soo_.control().set(c); }

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

  void* slot_array() const { return heap_or_soo_.slot_array().get(); }

  MaybeInitializedPtr<void> slots_union() const {

    return heap_or_soo_.slot_array();

  }

  void set_slots(void* s) { heap_or_soo_.slot_array().set(s); }

  // The number of filled slots.

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

  // Sets the size to zero, but keeps hashinfoz bit and seed.

  void set_size_to_zero() { size_.set_size_to_zero_keep_metadata(); }

  void set_empty_soo() {

    AssertInSooMode();

    size_ = HashtableSize(no_seed_empty_tag_t{});

  }

  void set_full_soo() {

    AssertInSooMode();

    size_ = HashtableSize(full_soo_tag_t{});

  }

  void increment_size() {

    ABSL_SWISSTABLE_ASSERT(size() < capacity());

    size_.increment_size();

  }

  void increment_size(size_t n) {

    ABSL_SWISSTABLE_ASSERT(size() + n <= capacity());

    size_.increment_size(n);

  }

  void decrement_size() {

    ABSL_SWISSTABLE_ASSERT(!empty());

    size_.decrement_size();

  }

  bool empty() const { return size_.empty(); }

  // The seed used for the hash function.

  PerTableSeed seed() const { return size_.seed(); }

  // Generates a new seed the hash function.

  // The table will be invalidated if `!empty()` because hash is being changed.

  // In such cases, we will need to rehash the table.

  void generate_new_seed(bool has_infoz) {

    // Note: we can't use has_infoz() here because we set has_infoz later than

    // we generate the seed.

    if (ABSL_PREDICT_FALSE(has_infoz)) {

      size_.set_sampled_seed();

      return;

    }

    size_.generate_new_seed();

  }

  void set_no_seed_for_testing() { size_.set_no_seed_for_testing(); }

  // The total number of available slots.

  size_t capacity() const { return capacity_; }

  void set_capacity(size_t c) {

    // We allow setting above the max valid capacity for debugging purposes.

    ABSL_SWISSTABLE_ASSERT(c == 0 || IsValidCapacity(c) ||

                           c > kAboveMaxValidCapacity);

    capacity_ = c;

  }

  bool is_small() const { return IsSmallCapacity(capacity_); }

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

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

  // TODO(b/289225379): experiment with moving growth_info back inline to

  // increase room for SOO.

  size_t growth_left() const { return growth_info().GetGrowthLeft(); }

  GrowthInfo& growth_info() {

    ABSL_SWISSTABLE_ASSERT(!is_small());

    return GetGrowthInfoFromControl(control());

  }

  GrowthInfo growth_info() const {

    return const_cast<CommonFields*>(this)->growth_info();

  }

  bool has_infoz() const { return size_.has_infoz(); }

  void set_has_infoz() {

    ABSL_SWISSTABLE_ASSERT(size_.is_sampled_seed());

    size_.set_has_infoz();

  }

  HashtablezInfoHandle* infoz_ptr() const {

    // growth_info is stored before control bytes.

    ABSL_SWISSTABLE_ASSERT(

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

    ABSL_SWISSTABLE_ASSERT(has_infoz());

    return reinterpret_cast<HashtablezInfoHandle*>(

        control() - ControlOffset(/*has_infoz=*/true));

  }

  HashtablezInfoHandle infoz() {

    return has_infoz() ? *infoz_ptr() : HashtablezInfoHandle();

  }

  void set_infoz(HashtablezInfoHandle infoz) {