container_internal

Namespaces

Enumerations

enum class ctrl_t : int8_t

Name	Value	Comments
kEmpty	-128	0b10000000
kDeleted	-2	0b11111110
kSentinel	-1	0b11111111

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 InvalidCapacity : size_t

Name	Value	Comments
kAboveMaxValidCapacity	~size_t{} - 100	--
kReentrance	18446744073709551516	--
kDestroyed	18446744073709551517	--
kMovedFrom	18446744073709551518	These two must be last because we use `>= kMovedFrom` to mean moved-from.
kSelfMovedFrom	18446744073709551519	These two must be last because we use `>= kMovedFrom` to mean moved-from.

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

classes of bugs.

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

enum class MatchKind : uint8_t

Name	Value
kEq	0
kNe	1

Defined at line 463 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.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, absl::void_t<typename T::absl_container_eq>>

```
class HasAbslContainerHash
```

class HasAbslContainerHash<T, absl::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<absl::void_t<decltype(Policy::apply(
        RequireUsableKey<typename Policy::key_type, Hash, Eq>(),
        std::declval<Ts>()...))>, Policy, Hash, Eq, Ts...>

```
class IsTransparent
```

class IsTransparent<T, absl::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, absl::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, absl::void_t<typename Policy::mapped_type>>

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

```
class prefers_linear_node_search
```

class prefers_linear_node_search<T, absl::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
```
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 1181 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
void AssertSameContainer (const ctrl_t * ctrl_a, const ctrl_t * ctrl_b, const void *const & slot_a, const void *const & 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 1334 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 1495 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)
```
Note: we mark this function as ABSL_ATTRIBUTE_NOINLINE because we don't want

it to be inlined into e.g. the destructor to save code size.

Defined at line 1502 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
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.
```
GenerationType * EmptyGeneration ()
```
Returns a pointer to a generation to use for an empty hashtable.
```
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
```
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 94 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h
```
void RecordInsertHitSlow (HashtablezInfo * info)
```
This is inline to avoid calling convention overhead for an otherwise

lightweight operation.

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

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 169 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 179 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 199 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 201 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 206 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 211 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 215 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 220 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
bool IsFull (ctrl_t c)
```
Defined at line 221 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.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 224 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

```
bool IsDeleted (ctrl_t c)
```
Defined at line 227 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
bool IsEmptyOrDeleted (ctrl_t c)
```
Defined at line 228 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
bool operator== (const btree_container<Tree> & x, const btree_container<Tree> & y)
```
Defined at line 233 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.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 233 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 238 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 240 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 242 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 246 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 250 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
void SanitizerUnpoisonMemoryRegion (const void * m, size_t s)
```
Defined at line 251 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 254 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.h
```
GenerationType NextGeneration (GenerationType generation)
```
Defined at line 258 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void RecordRehashSlow (HashtablezInfo * info, size_t total_probe_length)

void RecordReservationSlow (HashtablezInfo * info, size_t target_capacity)

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)

```
template <typename T>
```
```
void SanitizerPoisonObject (const T * object)
```
Defined at line 263 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h
```
ctrl_t * SooControl ()
```
Returns a pointer to a full byte followed by a sentinel byte.

Defined at line 395 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool IsSooControl (const ctrl_t * ctrl)
```
Whether ctrl is from the SooControl array.

Defined at line 401 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 408 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.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 419 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t H1 (size_t hash)
```
H1 is just the low bits of the hash.

Defined at line 529 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 534 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 543 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 772 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 775 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 782 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 785 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t ControlOffset (bool has_infoz)
```
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.

Defined at line 791 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 797 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t MaxSooSlotSize ()
```
Returns the maximum size of the SOO slot.

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

`control`.

Defined at line 902 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 1145 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 1151 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 1167 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
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 1196 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <class InputIter>

size_t SelectBucketCountForIterRange (InputIter first, InputIter last, size_t bucket_count)

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

```
bool SwisstableDebugEnabled ()
```
Defined at line 1232 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void AssertIsFull (const ctrl_t * ctrl, GenerationType generation, const GenerationType * generation_ptr, const char * operation)

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

```
void AssertIsValidForComparison (const ctrl_t * ctrl, GenerationType generation, const GenerationType * generation_ptr)
```
Note that for comparisons, null/end iterators are valid.

Defined at line 1283 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
bool AreItersFromSameContainer (const ctrl_t * ctrl_a, const ctrl_t * ctrl_b, const void *const & slot_a, const void *const & 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.

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 1312 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

void UnsampleSlow (HashtablezInfo * info)

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

HashtablezSampler & GlobalHashtablezSampler ()

Returns a global Sampler.

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)

```
size_t GetHashtablezMaxSamples ()
```
Sets a soft max for the number of samples that will be kept.

void SetHashtablezMaxSamples (size_t max)

void SetHashtablezMaxSamplesInternal (size_t max)

```
bool AbslContainerInternalSampleEverything_lts_20260107 ()
```
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.
```
void swap (HashtablezInfoHandle & , HashtablezInfoHandle & )
```
Defined at line 230 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtablez_sampler.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 243 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtablez_sampler.h
```
GenerationType SentinelEmptyGeneration ()
```
A sentinel value for empty generations. Using 0 makes it easy to constexpr

initialize an array of this value.

Defined at line 256 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.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 264 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtable_control_bytes.h
```
bool SwisstableGenerationsEnabled ()
```
Defined at line 266 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t NumGenerationBytes ()
```
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 267 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree_container.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 267 of file ../../third_party/abseil-cpp/src/absl/container/internal/hashtablez_sampler.h
```
template <typename T>
```
```
void SanitizerUnpoisonObject (const T * object)
```
Defined at line 268 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.h

void SetHashtablezConfigListener (HashtablezConfigListener l)

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

void SetHashtablezEnabled (bool enabled)

```
bool SwisstableAssertAccessToDestroyedTable ()
```
Returns true if we should assert that the table is not accessed after it has

been destroyed or during the destruction of the table.

Defined at line 272 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 280 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 286 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 293 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 298 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 341 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h
```
ctrl_t * DefaultIterControl ()
```
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 387 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 542 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 550 of file ../../third_party/abseil-cpp/src/absl/container/internal/container_memory.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

```
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 1393 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
probe_seq<Group::kWidth> probe_h1 (size_t capacity, size_t h1)
```
Begins a probing operation on `common.control`, using `hash`.

Defined at line 1398 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
probe_seq<Group::kWidth> probe (size_t capacity, size_t hash)
```
Defined at line 1401 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 1404 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 1422 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
size_t BackingArrayAlignment (size_t align_of_slot)
```
growth_info (which is a size_t) is stored with the backing array.

Defined at line 1472 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 1484 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t kSizeOfSizeT = sizeof(size_t)>
```
```
size_t MaxValidSizeFor1ByteSlot ()
```
Returns the maximum valid size for a table with 1-byte slots.

This function is an utility shared by MaxValidSize and IsAboveValidSize.

Template parameter is only used to enable testing.

Defined at line 1570 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 slot_size)
```
Returns the maximum valid size for a table with provided slot size.

Template parameter is only used to enable testing.

Defined at line 1583 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
```
template <size_t kSizeOfSizeT = sizeof(size_t)>
```
```
bool IsAboveValidSize (size_t size, size_t slot_size)
```
Returns true if size is larger than the maximum valid size.

It is an optimization to avoid the division operation in the common case.

Template parameter is only used to enable testing.

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

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

Type erased version of raw_hash_set::rehash.

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

Type erased version of copy constructor.

template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy>

size_t 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 offset of the new element.

All possible template combinations are defined in cc file to improve

compilation time.

```
size_t 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 index 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.

size_t 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>
```
```
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 612 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>

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

Defined at line 619 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>

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

Defined at line 626 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 1618 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 1623 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 1655 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: `new_size > policy.soo_capacity`.

```
void ReserveEmptyNonAllocatedTableToFitBucketCount (CommonFields & common, const PolicyFunctions & policy, size_t bucket_count)
```
Resizes empty non-allocated table to the next valid capacity after

`bucket_count`. Requires:

1. `c.capacity() == policy.soo_capacity`.

2. `c.empty()`.

3. `new_size > policy.soo_capacity`.

The table will be attempted to be sampled.
```
std::pair<ctrl_t *, 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 control and 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, bool soo_enabled)
```
ClearBackingArray clears the backing array, either modifying it in place,

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

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, const ctrl_t * ctrl, size_t slot_size)

```
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 1721 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 1979 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 1986 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 2080 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 2083 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 2846 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 2867 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

template <typename H>

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

Defined at line 2872 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 2879 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 3662 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 3669 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 3673 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h

Variables

ctrl_t kDefaultIterControl

const ctrl_t[2] kSooControl