class GrowthInfoAccessor
Defined at line 1022 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
Stored the information regarding number of slots we can still fill
without needing to rehash.
We want to ensure sufficient number of empty slots in the table in order
to keep probe sequences relatively short. Empty slot in the probe group
is required to stop probing.
Tombstones (kDeleted slots) are not included in the growth capacity,
because we'd like to rehash when the table is filled with tombstones and/or
full slots.
GrowthInfo also stores a bit that encodes whether table may have any
deleted slots.
Most of the tables (>95%) have no deleted slots, so some functions can
be more efficient with this information.
Callers can also force a rehash via the standard `rehash(0)`,
which will recompute this value as a side-effect.
See also `CapacityToGrowth()`.
GrowthInfo is stored as 1 or 8 bytes at the beginning of the backing array.
For capacity
<
= kMaxGrowthLeftLowerBound we store single byte, otherwise we
store 8 bytes. Byte before the first control byte for all tables is always
used to store GrowthInfoLowerBound. That helps to avoid any branching in the
hottest code accessing GrowthInfo. GrowthInfoLowerBound has 7 bits to store
the growth left and 1 bit to store whether the table has any deleted slots.
For capacity > kMaxGrowthLeftLowerBound we use another 7 bytes to store the
full GrowthInfo. GrowthInfo for capacity > kMaxGrowthLeftLowerBound is stored
as uint64_t in little endian encoding. Most significant 8 bits (last byte in
little endian encoding) contains GrowthInfoLowerBound.
Public Members
static const uint64_t kLowerBoundShiftPublic Methods
void GrowthInfoAccessor (void * control)Defined at line 1028 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
void InitGrowthLeftNoDeleted (size_t growth_left, size_t capacity)Initializes the GrowthInfo assuming we can grow `growth_left` elements
and there are no kDeleted slots in the table.
void OverwriteEmptyAsFull ()Overwrites single empty slot with a full slot.
Must be called when GetGrowthLeftLowerBound() > 0.
Defined at line 1047 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
void OverwriteControlAsFull (ctrl_t ctrl)Overwrites specified control element with full slot.
Must be called when GetGrowthLeftLowerBound() >= IsEmpty(ctrl).
Defined at line 1054 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
void OverwriteFullAsDeleted ()Overwrites single full slot with a deleted slot.
Defined at line 1061 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
GrowthInfoLowerBound GetGrowthInfoLowerBound ()Returns a GrowthInfoLowerBound object containing the information
about minimum growth left.
Defined at line 1067 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
size_t GetGrowthLeftLowerBound ()Returns the minimum number of elements left to grow.
Defined at line 1072 of file ../../third_party/abseil-cpp/src/absl/container/internal/raw_hash_set.h
GrowthInfoLowerBound RebalanceGrowthLeftLowerBound (size_t capacity)Returns a GrowthInfoLowerBound object containing the information
about minimum growth left.
It guarantees that GetGrowthLeft() will be > 0 if GetGrowthLeftTotal() > 0.
It may optionally borrow some growth left from the full_growth_info.
void OverwriteFullAsEmpty ()Overwrites single full slot with an empty slot.
size_t GetGrowthLeftTotalSlow (size_t capacity)The number of slots we can still fill without needing to rehash.
Hot code paths should try to work with
growth_info().GetGrowthLeftLowerBound() instead.