container_internal

Namespaces

Enumerations

enum class ctrl_t : int8_t

Name	Value	Comments
kEmpty	-128	0b10000000
kDeleted	-2	0b11111110
kSentinel	-1	0b11111111
kMarkedForSlowTransfer	-3	Special value used in the slow path of resizing.

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

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

and the sentinel. They have the following bit patterns:

empty: 1 0 0 0 0 0 0 0

deleted: 1 1 1 1 1 1 1 0

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

sentinel: 1 1 1 1 1 1 1 1

These values are specifically tuned for SSE-flavored SIMD.

The static_asserts below detail the source of these choices.

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

knows ctrl_t doesn't alias other types.

Defined at line 184 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h

enum class MatchKind : uint8_t

Name	Value
kEq	0
kNe	1

Defined at line 465 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

enum HashtableCapacityStorageMode

Name	Value	Comments
kCapacityByValue	0	Capacity stored as size_t as a full number.
kCapacityByLog	1	Capacity stored as uint8_t as log2, i.e. capacity = 2^capacity_ - 1.

The mode we store capacity in the table.

Defined at line 480 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

Records

```
class AbslContainerEq
```

class AbslContainerEq<T, typename std::enable_if_t<HasAbslContainerEq<T>::value>>

```
class AbslContainerHash
```

class AbslContainerHash<T, typename std::enable_if_t<HasAbslContainerHash<T>::value>>

class ApplyWithoutDefaultSuffix<Template, TypeList<D, Ds...>, TypeList<T, Ts...>, TypeList<L...>, std::enable_if_t<!std::is_same_v<TypeList<D, Ds...>, TypeList<T, Ts...>>>>

class BtreeTestOnlyCheckedCompareOptOutBase

class CommonFieldsGenerationInfoDisabled

class HasAbslContainerEq<T, std::void_t<typename T::absl_container_eq>>

```
class HasAbslContainerHash
```

class HasAbslContainerHash<T, std::void_t<typename T::absl_container_hash>>

class HashEq<T, typename std::enable_if_t<HasAbslContainerHash<T>::value>>

```
class HashKey
```

class HashSetIteratorGenerationInfoDisabled

class HashSetIteratorGenerationInfoEnabled

class IsDecomposable<std::void_t<decltype(Policy::apply(
        RequireUsableKey<typename Policy::key_type, Hash, Eq>(),
        std::declval<Ts>()...))>, Policy, Hash, Eq, Ts...>

```
class IsTransparent
```

class IsTransparent<T, std::void_t<typename T::is_transparent>>

class btree_iterator_generation_info_disabled

class btree_iterator_generation_info_enabled

class checked_compare_base<Compare, false>

class has_linear_node_search_preference<T, std::void_t<typename T::absl_btree_prefer_linear_node_search>>

class key_compare_adapter<std::less<std::string>, std::string>

class key_compare_adapter<std::greater<std::string>, std::string>

class key_compare_adapter<std::less<std::string_view>, std::string_view>

class key_compare_adapter<std::greater<std::string_view>, std::string_view>

class key_compare_adapter<std::less<absl::Cord>, absl::Cord>

class key_compare_adapter<std::greater<absl::Cord>, absl::Cord>

class node_handle<Policy, PolicyTraits, Alloc, std::void_t<typename Policy::mapped_type>>

class policy_trait_element_is_owner<Policy, std::enable_if_t<!std::is_void_v<typename Policy::element_is_owner>>>

```
class prefers_linear_node_search
```

class prefers_linear_node_search<T, std::void_t<typename T::absl_btree_prefer_linear_node_search>>

Functions

```
template <size_t Alignment, class Alloc>
```
```
void * Allocate (Alloc * alloc, size_t n)
```
Allocates at least n bytes aligned to the specified alignment.

Alignment must be a power of 2. It must be positive.

Note that many allocators don't honor alignment requirements above certain

threshold (usually either alignof(std::max_align_t) or alignof(void*)).

Allocate() doesn't apply alignment corrections. If the underlying allocator

returns insufficiently alignment pointer, that's what you are going to get.

Defined at line 62 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

void RecordClearedReservationSlow (HashtablezInfo * info)

void RecordStorageChangedSlow (HashtablezInfo * info, size_t size, size_t capacity)

void RecordInsertMissSlow (HashtablezInfo * info, size_t hash, size_t distance_from_desired)

void RecordEraseSlow (HashtablezInfo * info)

HashtablezInfo * SampleSlow (SamplingState & next_sample, size_t inline_element_size, size_t key_size, size_t value_size, uint16_t soo_capacity)

```
void ConvertDeletedToEmptyAndFullToDeleted (ctrl_t * ctrl, size_t capacity)
```
Applies the following mapping to every byte in the control array:

* kDeleted -> kEmpty

* kEmpty -> kEmpty

* _ -> kDeleted

PRECONDITION:

IsValidCapacity(capacity)

ctrl[capacity] == ctrl_t::kSentinel

ctrl[i] != ctrl_t::kSentinel for all i

<

capacity

template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy>

void * GrowSooTableToNextCapacityAndPrepareInsert (CommonFields & common, const PolicyFunctions & policy, absl::FunctionRef<size_t (size_t)> get_hash, bool force_sampling)

Resizes SOO table to the NextCapacity(SooCapacity()) and prepares insert for

the given new_hash. Returns the new slot.

All possible template combinations are defined in cc file to improve

compilation time.

```
void DestroySlots (CommonFields & c, size_t slot_size, DestroySlotFn destroy_slot)
```
Destroys all full slots in the backing array.

REQUIRES: !is_small(c.capacity()).

REQUIRES: destroy_slot != nullptr.

void DeallocBackingArray (CommonFields & c, size_t slot_size, size_t slot_align, DeallocBackingArrayFn dealloc, void * alloc)

Deallocates the backing array and unregister infoz if necessary.

REQUIRES: c.capacity > raw_hash_set::DefaultCapacity().

template <bool kSooEnabled>

void Clear (CommonFields & c, const PolicyFunctions & policy, DestroySlotFn destroy_slot, void * alloc)

Type erased version of raw_hash_set::clear.

void DestructSoo (CommonFields & c, size_t slot_size, size_t slot_align, DestroySlotFn destroy_slot, DeallocBackingArrayFn dealloc, void * alloc)

Destructs all elements and deallocates the backing array for SOO tables.

REQUIRES: !c.is_small || !c.empty()

REQUIRES: !c.is_small || destroy_slot != nullptr

void DestructNonSoo (CommonFields & c, size_t slot_size, size_t slot_align, DestroySlotFn destroy_slot, DeallocBackingArrayFn dealloc, void * alloc)

Destructs all elements and deallocates the backing array for non-SOO tables.

REQUIRES: c.capacity > 0.

void EraseMetaOnlySmall (CommonFields & c, bool soo_enabled, size_t slot_size)

Type-erased versions of raw_hash_set::erase_meta_only_{small,large}.

void EraseMetaOnlyLarge (CommonFields & c, size_t index, size_t slot_size)

```
void * GetRefForEmptyClass (CommonFields & common)
```
Returns a pointer to `common`. This is used to implement type erased

raw_hash_set::get_hash_ref_fn and raw_hash_set::get_alloc_ref_fn for the

empty class cases.
```
template <typename T>
```
```
uint32_t TrailingZeros (T x)
```
Defined at line 63 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
template <class Allocator, class ValueType>
```
```
auto IsDestructionTrivial ()
```
Returns true if the destruction of the value with given Allocator will be

trivial.

Defined at line 81 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
template <size_t Alignment, class Alloc>
```
```
void Deallocate (Alloc * alloc, void * p, size_t n)
```
The pointer must have been previously obtained by calling

Allocate

<Alignment

>(alloc, n).

Defined at line 93 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
bool BtreeGenerationsEnabled ()
```
Defined at line 96 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h
```
size_t SooCapacity ()
```
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.

Defined at line 378 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool IsValidCapacity (size_t n)
```
Returns whether `n` is a valid capacity (i.e., number of slots).

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

Defined at line 395 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool IsSmallCapacity (size_t capacity)
```
Whether a table is small enough that we don't need to hash any keys.

Defined at line 398 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void UnsampleSlow (HashtablezInfo * info)

```
HashtablezInfoHandle ForcedTrySample (size_t inline_element_size, size_t key_size, size_t value_size, uint16_t soo_capacity)
```
Returns a sampling handle.

Must be called only if HashSetShouldBeSampled() returned true.

Returned handle still can be unsampled if sampling is not possible.

HashtablezSampler & GlobalHashtablezSampler ()

Returns a global Sampler.

```
size_t GetHashtablezMaxSamples ()
```
Sets a soft max for the number of samples that will be kept.
```
GenerationType * EmptyGeneration ()
```
Returns a pointer to a generation to use for an empty hashtable.

bool operator== (const BitMask<T, SignificantBits, Shift, NullifyBitsOnIteration> & a, const BitMask<T, SignificantBits, Shift, NullifyBitsOnIteration> & b)

Defined at line 157 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h

bool operator!= (const BitMask<T, SignificantBits, Shift, NullifyBitsOnIteration> & a, const BitMask<T, SignificantBits, Shift, NullifyBitsOnIteration> & b)

Defined at line 160 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h

```
template <class Alloc, class T, class Tuple>
```
```
void ConstructFromTuple (Alloc * alloc, T * ptr, Tuple && t)
```
Constructs T into uninitialized storage pointed by `ptr` using the args

specified in the tuple.

Defined at line 167 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
template <class T, class Tuple, class F>
```
```
decltype(std::declval<F>()(std::declval<T>())) WithConstructed (Tuple && t, F && f)
```
Constructs T using the args specified in the tuple and calls F with the

constructed value.

Defined at line 176 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
std::pair<std::tuple<>, std::tuple<>> PairArgs ()
```
Given arguments of an std::pair's constructor, PairArgs() returns a pair of

tuples with references to the passed arguments. The tuples contain

constructor arguments for the first and the second elements of the pair.

The following two snippets are equivalent.

1. std::pair

<F

, S> p(args...);

2. auto a = PairArgs(args...);

std::pair

<F

, S> p(std::piecewise_construct,

std::move(a.first), std::move(a.second));

Defined at line 195 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
template <class F, class S>
```
```
std::pair<std::tuple<F &&>, std::tuple<S &&>> PairArgs (F && f, S && s)
```
Defined at line 197 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

template <class F, class S>

std::pair<std::tuple<const F &>, std::tuple<const S &>> PairArgs (const std::pair<F, S> & p)

Defined at line 202 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

template <class F, class S>

std::pair<std::tuple<F &&>, std::tuple<S &&>> PairArgs (std::pair<F, S> && p)

Defined at line 207 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

template <class F, class S>

decltype(std::make_pair(memory_internal::TupleRef(std::forward<F>(f)), memory_internal::TupleRef(std::forward<S>(s)))) PairArgs (std::piecewise_construct_t , F && f, S && s)

Defined at line 211 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

```
void swap (HashtablezInfoHandle & , HashtablezInfoHandle & )
```
Defined at line 213 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtablez_sampler.h

template <class F, class... Args>

decltype(memory_internal::DecomposePairImpl(std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) DecomposePair (F && f, Args &&... args)

A helper function for implementing apply() in map policies.

Defined at line 220 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

```
bool IsEmpty (ctrl_t c)
```
Helpers for checking the state of a control byte.

Defined at line 222 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
bool IsFull (ctrl_t c)
```
Defined at line 223 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
bool ShouldSampleNextTable ()
```
Returns true if the next table should be sampled.

This function updates the global state.

If the function returns true, actual sampling should be done by calling

ForcedTrySample().

Defined at line 226 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtablez_sampler.h
```
bool IsDeleted (ctrl_t c)
```
Defined at line 229 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
template <class F, class Arg>
```
```
decltype(std::declval<F>()(std::declval<const Arg &>(), std::declval<Arg>())) DecomposeValue (F && f, Arg && arg)
```
A helper function for implementing apply() in set policies.

Defined at line 229 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
bool IsEmptyOrDeleted (ctrl_t c)
```
Defined at line 230 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h

void RecordRehashSlow (HashtablezInfo * info, size_t total_probe_length)

void RecordReservationSlow (HashtablezInfo * info, size_t target_capacity)

```
bool operator== (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 234 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
void SanitizerPoisonMemoryRegion (const void * m, size_t s)
```
Helper functions for asan and msan.

Defined at line 236 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
bool operator!= (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 239 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
bool operator< (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 243 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
bool operator> (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 247 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
void SanitizerUnpoisonMemoryRegion (const void * m, size_t s)
```
Defined at line 247 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
HashtablezInfoHandle Sample (size_t inline_element_size, size_t key_size, size_t value_size, uint16_t soo_capacity)
```
Returns a sampling handle.

Defined at line 250 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtablez_sampler.h
```
bool operator<= (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 251 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
bool operator>= (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 255 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
template <typename T>
```
```
void SanitizerPoisonObject (const T * object)
```
Defined at line 259 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
template <typename T>
```
```
void SanitizerUnpoisonObject (const T * object)
```
Defined at line 264 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
__m128i _mm_cmpgt_epi8_fixed (__m128i a, __m128i b)
```
https://github.com/abseil/abseil-cpp/issues/209

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

_mm_cmpgt_epi8 is broken under GCC with -funsigned-char

Work around this by using the portable implementation of Group

when using -funsigned-char under GCC.

Defined at line 266 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
GenerationType NextGeneration (GenerationType generation)
```
Defined at line 267 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <typename State>
```
```
State AbslHashValue (State h, const btree_container<Tree> & b)
```
Support absl::Hash.

Defined at line 268 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
void TestOnlyRefreshSamplingStateForCurrentThread ()
```
In case sampling needs to be disabled and re-enabled in tests, this function

can be used to reset the sampling state for the current thread.

It is useful to avoid sampling attempts and sampling delays in tests.

void SetHashtablezConfigListener (HashtablezConfigListener l)

```
bool IsHashtablezEnabled ()
```
Enables or disables sampling for Swiss tables.

void SetHashtablezEnabled (bool enabled)

void SetHashtablezEnabledInternal (bool enabled)

```
int32_t GetHashtablezSampleParameter ()
```
Sets the rate at which Swiss tables will be sampled.

void SetHashtablezSampleParameter (int32_t rate)

void SetHashtablezSampleParameterInternal (int32_t rate)

void SetHashtablezMaxSamples (size_t max)

void SetHashtablezMaxSamplesInternal (size_t max)

```
bool AbslContainerInternalSampleEverything ()
```
Configuration override.

This allows process-wide sampling without depending on order of

initialization of static storage duration objects.

The definition of this constant is weak, which allows us to inject a

different value for it at link time.
```
GenerationType SentinelEmptyGeneration ()
```
A sentinel value for empty generations. Using 0 makes it easy to constexpr

initialize an array of this value.

Defined at line 265 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool SwisstableGenerationsEnabled ()
```
Defined at line 275 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t NumGenerationBytes ()
```
Defined at line 276 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool SwisstableGenerationsOrDebugEnabled ()
```
Defined at line 279 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename AllocType>

void SwapAlloc (AllocType & lhs, AllocType & rhs, std::true_type )

Defined at line 287 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename AllocType>

void SwapAlloc (AllocType & lhs, AllocType & rhs, std::false_type )

Defined at line 293 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename AllocType>

void CopyAlloc (AllocType & lhs, AllocType & rhs, std::true_type )

Defined at line 300 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

```
template <typename AllocType>
```
```
void CopyAlloc (AllocType & , AllocType & , std::false_type )
```
Defined at line 305 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
void * DefaultIterSlot ()
```
Returns a pointer to a control byte that can be used by default-constructed

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

Defined at line 331 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
ctrl_t * SooControl ()
```
Returns a pointer to a full byte followed by a sentinel byte.

Defined at line 339 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <typename Compare, typename Key>
```
```
bool compare_has_valid_result_type ()
```
Defined at line 343 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h
```
bool IsSooControl (const ctrl_t * ctrl)
```
Whether ctrl is from the SooControl array.

Defined at line 345 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
ctrl_t * InsertIteratorControl ()
```
Returns a pointer to a full byte followed by a sentinel byte.

Defined at line 351 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool IsInsertIteratorControl (const ctrl_t * ctrl)
```
Whether ctrl is special value for iterators returned by `insert` and similar.

Defined at line 358 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool IsEmptyGeneration (const GenerationType * generation)
```
Returns whether `generation` is a generation for an empty hashtable that

could be returned by EmptyGeneration().

Defined at line 367 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool is_single_group (size_t capacity)
```
Whether a table fits entirely into a probing group.

Arbitrary order of elements in such tables is correct.

Defined at line 404 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool IsCapacityValidForBlockedElements (size_t cap)
```
Whether `cap` is a valid capacity for a table that can store blocked

elements.

Defined at line 410 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t NormalizeCapacity (size_t n)
```
Converts `n` into the next valid capacity, per `IsValidCapacity`.

Defined at line 415 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t NextCapacity (size_t n)
```
Returns the next valid capacity after `n`.

Defined at line 420 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t PreviousCapacity (size_t n)
```
Returns the previous valid capacity before `n`.

Defined at line 426 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t CapacityToGrowth (size_t capacity)
```
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.

Defined at line 441 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <class Fn, class T, bool kIsDefault>
```
```
size_t TypeErasedApplyToSlotFn (const void * fn, void * slot, size_t seed)
```
Type erased function to apply `Fn` to data inside of the `slot`.

The data is expected to have type `T`.

Defined at line 538 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
template <class Fn, class T, bool kIsDefault>
```
```
size_t TypeErasedDerefAndApplyToSlotFn (const void * fn, void * slot_ptr, size_t seed)
```
Type erased function to apply `Fn` to data inside of the `*slot_ptr`.

The data is expected to have type `T`.

Defined at line 546 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
template <class Fn, class T, bool kIsDefault>
```
```
size_t TypeErasedDerefAndApplyToSlotFirstFn (const void * fn, void * slot_ptr, size_t seed)
```
Type erased function to apply `Fn` to data inside of the `slot_ptr->first`.

The data is expected to have type `T`.

Defined at line 556 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
size_t H1 (size_t hash)
```
H1 is just the low bits of the hash.

Defined at line 783 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
h2_t H2 (size_t hash)
```
Extracts the H2 portion of a hash: the 7 most significant bits.

These are used as an occupied control byte.

Defined at line 788 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename Node>

bool AreNodesFromSameContainer (const Node * node_a, const Node * node_b)

Defined at line 1052 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

```
size_t MaxSooSlotSize ()
```
Returns the maximum size of the SOO slot.

Defined at line 1206 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
GrowthInfoAccessor GetGrowthInfoFromControl (ctrl_t * control)
```
Returns a reference to the GrowthInfo object stored immediately before

`control`.

Defined at line 1230 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t MaxStorableSize ()
```
Defined at line 1939 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t kSizeOfSizeT = sizeof(size_t)>
```
```
size_t MaxValidSizeForKeySize (size_t key_size)
```
There are no more than 2^sizeof(key_type) unique key_types (and hashtable

keys must be unique) so we can't have a hashtable with more than

2^sizeof(key_type) elements.

Defined at line 1949 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t kSizeOfSizeT = sizeof(size_t)>
```
```
size_t MaxValidSizeForSlotSize (size_t slot_size)
```
Defined at line 1955 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t kSizeOfSizeT = sizeof(size_t)>
```
```
size_t MaxValidSize (size_t key_size, size_t slot_size)
```
Returns the maximum valid size for a table, given the key size and slot size.

Template parameter is only used to enable testing.

Defined at line 1968 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
uint16_t NextHashTableSeed ()
```
Returns next per-table seed.
```
size_t SizeToCapacity (size_t size)
```
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)`.

Defined at line 456 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t RehashProbabilityConstant ()
```
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.

Defined at line 797 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t NumClonedBytes ()
```
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.

Defined at line 1100 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t NumControlBytes (size_t capacity)
```
Returns the number of control bytes including cloned.

Defined at line 1103 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t GrowthInfoSizeForCapacity (size_t capacity)
```
Returns the size in bytes table with given capacity use to store GrowthInfo.

Returns 0 for small tables that doesn't store GrowthInfo.

Defined at line 1109 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t MetadataBeforeControlSize (bool has_infoz, size_t capacity)
```
Computes the size of the metadata before the control bytes. infoz,

growth_info and generation are stored at the beginning of the backing array.

Defined at line 1120 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t AlignUpTo (size_t offset, size_t align)
```
Returns the offset of the next item after `offset` that is aligned to `align`

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

Defined at line 1132 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIter>

size_t SelectReservationSizeForIterRange (InputIter first, InputIter last, size_t reservation_size)

Defined at line 1492 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

```
bool SwisstableDebugEnabled ()
```
Defined at line 1504 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <typename T>
```
```
T CrashIfIteratorIsInvalid (const T * ptr)
```
Dereferences `ptr`. The function is named in order to provide a helpful error

message when users see crashing stack traces. Note that this function is not

guaranteed to crash when `ptr` is invalid if sanitizer mode is not enabled.

Defined at line 1517 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
void AssertIsFull (const ctrl_t *const & ctrl, const void * slot, GenerationType generation, const GenerationType * generation_ptr, const char * operation)
```
Note: we take control pointers by reference in a few Assert* functions below

so that it's not UB if they're uninitialized as long as we don't read them

(when slot is null).

Defined at line 1537 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
void AssertIsValidForComparison (const ctrl_t *const & ctrl, const void * slot, GenerationType generation, const GenerationType * generation_ptr)
```
Note that for comparisons, null/end iterators are valid.

Defined at line 1581 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool AreItersFromSameContainer (const ctrl_t *const & ctrl_a, const ctrl_t *const & ctrl_b, const void * slot_a, const void * slot_b)
```
If the two iterators come from the same container, then their pointers will

interleave such that ctrl_a

<

= ctrl_b

<

slot_a

<

= slot_b or vice/versa.

Defined at line 1616 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
void AssertSameContainer (const ctrl_t *const & ctrl_a, const ctrl_t *const & ctrl_b, const void * slot_a, const void * slot_b, const GenerationType * generation_ptr_a, const GenerationType * generation_ptr_b)
```
Asserts that two iterators come from the same container.

Note: we take slots by reference so that it's not UB if they're uninitialized

as long as we don't read them (when ctrl is null).

Defined at line 1641 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
probe_seq<Group::kWidth> probe_h1 (ProbeCapacity capacity, size_t h1)
```
Begins a probing operation on `common.control`, using `hash`.

Defined at line 1751 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
probe_seq<Group::kWidth> probe (ProbeCapacity capacity, size_t hash)
```
Defined at line 1754 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
probe_seq<Group::kWidth> probe (const CommonFields & common, size_t hash)
```
Defined at line 1757 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <typename = void>
```
```
size_t TryFindNewIndexWithoutProbing (size_t h1, size_t old_index, size_t old_capacity, ctrl_t * new_ctrl, size_t new_capacity)
```
Implementation detail of transfer_unprobed_elements_to_next_capacity_fn.

Tries to find the new index for an element whose hash corresponds to

`h1` for growth to the next capacity.

Returns kProbedElementIndexSentinel if full probing is required.

If element is located in the first probing group in the table before growth,

returns one of two positions: `old_index` or `old_index + old_capacity + 1`.

Otherwise, we will try to insert it into the first probe group of the new

table. We only attempt to do so if the first probe group is already

initialized.

Defined at line 1775 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t BackingArrayAlignment (size_t align_of_slot)
```
The HashtablezInfoHandle is stored before the control bytes.

NOTE: The growth_info is also stored before the backing array, but it doesn't

have alignment requirements. For small tables it is 1 byte, for larger tables

it is 8 bytes, but we use unaligned load.

Defined at line 1828 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t AlignOfBackingArray, typename Alloc>
```
```
void * AllocateBackingArray (void * alloc, size_t n)
```
Allocates `n` bytes for a backing array.

Defined at line 1851 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <size_t AlignOfBackingArray, typename Alloc>

void DeallocateBackingArray (void * alloc, size_t capacity, ctrl_t * ctrl, size_t slot_size, size_t slot_align, bool had_infoz, size_t blocked_element_count)

Defined at line 1856 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

```
void IterateOverFullSlots (const CommonFields & c, size_t slot_size, absl::FunctionRef<void (const ctrl_t *, void *)> cb)
```
Iterates over all full slots and calls `cb(const ctrl_t*, void*)`.

No insertion to the table is allowed during `cb` call.

Erasure is allowed only for the element passed to the callback.

The table must not be in SOO mode.
```
template <typename CharAlloc>
```
```
bool ShouldSampleHashtablezInfoForAlloc ()
```
Defined at line 1840 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t kSizeOfSizeT = sizeof(size_t)>
```
```
size_t MaxSizeAtMaxValidCapacity (size_t slot_size)
```
The following functions are used for calculating the max valid size of the

table. This is important for security to avoid overflowing size_t when

calculating the allocation size of the backing array

(https://nvd.nist.gov/vuln/detail/CVE-2025-0838). We also limit the max valid

size based on the size of the key_type, and this is an optimization because

we ABSL_ASSUME that the size is less than MaxValidSize, which can enable

other optimizations for tables with small keys.

Defined at line 1932 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t OptimalMemcpySizeForSooSlotTransfer (size_t slot_size, size_t max_soo_slot_size)
```
Returns the optimal size for memcpy when transferring SOO slot.

Otherwise, returns the optimal size for memcpy SOO slot transfer

to SooSlotIndex().

At the destination we are allowed to copy upto twice more bytes,

because there is at least one more slot after SooSlotIndex().

The result must not exceed MaxSooSlotSize().

Some of the cases are merged to minimize the number of function

instantiations.

Defined at line 2008 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
void ReserveTableToFitNewSize (CommonFields & common, const PolicyFunctions & policy, size_t new_size)
```
Type erased version of raw_hash_set::reserve. Requires:

1. `new_size > policy.soo_capacity`.

2. `new_size

<

= kMaxValidSize`.

void Rehash (CommonFields & common, const PolicyFunctions & policy, size_t n)

Type erased version of raw_hash_set::rehash.

Requires: `n

= MaxValidCapacity()`.

void Copy (CommonFields & common, const PolicyFunctions & policy, const CommonFields & other, absl::FunctionRef<void (void *, const void *)> copy_fn)

Type erased version of copy constructor.

```
void * PrepareInsertSmallNonSoo (CommonFields & common, const PolicyFunctions & policy, absl::FunctionRef<size_t (size_t)> get_hash)
```
PrepareInsert for small tables (is_small()==true).

Returns the new slot.

Hash is only computed if the table is sampled or grew to large size

(is_small()==false).
```
void ResizeAllocatedTableWithSeedChange (CommonFields & common, const PolicyFunctions & policy, size_t new_capacity)
```
Resizes table with allocated slots and change the table seed.

Tables with SOO enabled must have capacity > policy.soo_capacity.

No sampling will be performed since table is already allocated.
```
void ClearBackingArray (CommonFields & c, const PolicyFunctions & policy, void * alloc, bool reuse)
```
ClearBackingArray clears the backing array, either modifying it in place,

or creating a new one based on the value of "reuse".

REQUIRES: c.capacity > MaxSmallCapacity().
```
void * PrepareInsertLarge (CommonFields & common, const PolicyFunctions & policy, size_t hash, Group::NonIterableBitMaskType mask_empty, FindInfo target_group)
```
Given the hash of a value not currently in the table and the first group with

an empty slot in the probe sequence, finds a viable slot to insert it at.

In case there's no space left, the table can be resized or rehashed

(for tables with deleted slots, see FindInsertPositionWithGrowthOrRehash).

In the case of absence of deleted slots and positive growth_left, the element

can be inserted in one of the empty slots in the provided `target_group`.

When the table has deleted slots (according to GrowthInfo), the target

position will be searched one more time using `find_first_non_full`.

REQUIRES: `!common.is_small()`.

REQUIRES: At least one non-full slot available.

REQUIRES: `mask_empty` is a mask containing empty slots for the

`target_group`.

REQUIRES: `target_group` is a starting position for the group that has

at least one empty slot.

void * PrepareInsertLargeGenerationsEnabled (CommonFields & common, const PolicyFunctions & policy, size_t hash, Group::NonIterableBitMaskType mask_empty, FindInfo target_group, absl::FunctionRef<size_t (size_t)> recompute_hash)

Same as above, but with generations enabled, we may end up changing the seed,

which means we need to be able to recompute the hash.

```
template <typename K, typename V, typename H, typename E, typename A, typename Function>
```
```
std::decay_t<Function> c_for_each_fast (const flat_hash_map<K, V, H, E, A> & c, Function && f)
```
c_for_each_fast(flat_hash_map

<

>, Function)

Container-based version of the

<algorithm

> `std::for_each()` function to

apply a function to a container's elements.

There is no guarantees on the order of the function calls.

Erasure and/or insertion of elements in the function is not allowed.

Defined at line 633 of file ../../third_party/abseil-cpp/src/absl/container/flat_hash_map.h

template <typename K, typename V, typename H, typename E, typename A, typename Function>

std::decay_t<Function> c_for_each_fast (flat_hash_map<K, V, H, E, A> & c, Function && f)

Defined at line 640 of file ../../third_party/abseil-cpp/src/absl/container/flat_hash_map.h

template <typename K, typename V, typename H, typename E, typename A, typename Function>

std::decay_t<Function> c_for_each_fast (flat_hash_map<K, V, H, E, A> && c, Function && f)

Defined at line 647 of file ../../third_party/abseil-cpp/src/absl/container/flat_hash_map.h

```
size_t SooSlotIndex ()
```
Returns the index of the SOO slot when growing from SOO to non-SOO in a

single group. See also InitializeSmallControlBytesAfterSoo(). It's important

to use index 1 so that when resizing from capacity 1 to 3, we can still have

random iteration order between the first two inserted elements.

I.e. it allows inserting the second element at either index 0 or 2.

Defined at line 1978 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t MaxSmallAfterSooCapacity ()
```
Maximum capacity for the algorithm for small table after SOO.

Note that typical size after SOO is 3, but we allow up to 7.

Allowing till 16 would require additional store that can be avoided.

Defined at line 1983 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t SizeOfSlot>
```
```
void TransferNRelocatable (void * , void * dst, void * src, size_t count)
```
For trivially relocatable types we use memcpy directly. This allows us to

share the same function body for raw_hash_set instantiations that have the

same slot size as long as they are relocatable.

Separate function for relocating single slot cause significant binary bloat.

Defined at line 2101 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool operator== (const iterator & a, const iterator & b)
```
Defined at line 2369 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool operator!= (const iterator & a, const iterator & b)
```
Defined at line 2378 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool operator== (const const_iterator & a, const const_iterator & b)
```
Defined at line 2456 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool operator!= (const const_iterator & a, const const_iterator & b)
```
Defined at line 2459 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

bool operator== (const raw_hash_set<Policy, Params...> & a, const raw_hash_set<Policy, Params...> & b)

Defined at line 3234 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

bool operator!= (const raw_hash_set<Policy, Params...> & a, const raw_hash_set<Policy, Params...> & b)

Defined at line 3255 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename H>

std::enable_if_t<H::template is_hashable<value_type>::value, H> AbslHashValue (H h, const raw_hash_set<Policy, Params...> & s)

Defined at line 3260 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

```
void swap (raw_hash_set<Policy, Params...> & a, raw_hash_set<Policy, Params...> & b)
```
Defined at line 3266 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <typename P, typename... Params, typename Predicate>
```
```
typename raw_hash_set<P, Params...>::size_type EraseIf (Predicate & pred, raw_hash_set<P, Params...> * c)
```
Erases all elements that satisfy the predicate `pred` from the container `c`.

Defined at line 4045 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <typename P, typename... Params, typename Callback>
```
```
void ForEach (Callback & cb, raw_hash_set<P, Params...> * c)
```
Calls `cb` for all elements in the container `c`.

Defined at line 4052 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename Ptypename... Paramstypename Callback>

void ForEach (Callback & cb, const raw_hash_set<P, Params...> * c)

Defined at line 4056 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

Variables

char kDefaultIterSlot

const ctrl_t[2] kInsertIteratorControl

const size_t kMaxSmallCapacity

Defined at line 380 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

const ctrl_t[2] kSooControl