summaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal/raw_hash_set.h')
-rw-r--r--absl/container/internal/raw_hash_set.h100
1 files changed, 52 insertions, 48 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 6da43026..5f89d8ef 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -909,6 +909,39 @@ using HashSetIteratorGenerationInfo = HashSetIteratorGenerationInfoDisabled;
// A valid capacity is a non-zero integer `2^m - 1`.
inline bool IsValidCapacity(size_t n) { return ((n + 1) & n) == 0 && n > 0; }
+// Computes the offset from the start of the backing allocation of the control
+// bytes. growth_left is stored at the beginning of the backing array.
+inline size_t ControlOffset() { return sizeof(size_t); }
+
+// 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; }
+
+// Given the capacity of a table, computes the offset (from the start of the
+// backing allocation) of the generation counter (if it exists).
+inline size_t GenerationOffset(size_t capacity) {
+ assert(IsValidCapacity(capacity));
+ const size_t num_control_bytes = capacity + 1 + NumClonedBytes();
+ return ControlOffset() + num_control_bytes;
+}
+
+// Given the capacity of a table, computes the offset (from the start of the
+// backing allocation) at which the slots begin.
+inline size_t SlotOffset(size_t capacity, size_t slot_align) {
+ assert(IsValidCapacity(capacity));
+ return (GenerationOffset(capacity) + NumGenerationBytes() + slot_align - 1) &
+ (~slot_align + 1);
+}
+
+// Given the capacity of a table, computes the total size of the backing
+// array.
+inline size_t AllocSize(size_t capacity, size_t slot_size, size_t slot_align) {
+ return SlotOffset(capacity, slot_align) + capacity * slot_size;
+}
+
// 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.
@@ -982,6 +1015,11 @@ class CommonFields : public CommonFieldsGenerationInfo {
CommonFieldsGenerationInfo::reset_reserved_growth(reservation, size());
}
+ // The size of the backing array allocation.
+ size_t alloc_size(size_t slot_size, size_t slot_align) const {
+ return AllocSize(capacity(), slot_size, slot_align);
+ }
+
// Returns the number of control bytes set to kDeleted. For testing only.
size_t TombstonesCount() const {
return static_cast<size_t>(
@@ -1014,13 +1052,6 @@ class CommonFields : public CommonFieldsGenerationInfo {
compressed_tuple_{0u, HashtablezInfoHandle{}};
};
-// 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; }
-
template <class Policy, class Hash, class Eq, class Alloc>
class raw_hash_set;
@@ -1355,32 +1386,6 @@ constexpr size_t BackingArrayAlignment(size_t align_of_slot) {
return (std::max)(align_of_slot, alignof(size_t));
}
-// Computes the offset from the start of the backing allocation of the control
-// bytes. growth_left is stored at the beginning of the backing array.
-inline size_t ControlOffset() { return sizeof(size_t); }
-
-// Given the capacity of a table, computes the offset (from the start of the
-// backing allocation) of the generation counter (if it exists).
-inline size_t GenerationOffset(size_t capacity) {
- assert(IsValidCapacity(capacity));
- const size_t num_control_bytes = capacity + 1 + NumClonedBytes();
- return ControlOffset() + num_control_bytes;
-}
-
-// Given the capacity of a table, computes the offset (from the start of the
-// backing allocation) at which the slots begin.
-inline size_t SlotOffset(size_t capacity, size_t slot_align) {
- assert(IsValidCapacity(capacity));
- return (GenerationOffset(capacity) + NumGenerationBytes() + slot_align - 1) &
- (~slot_align + 1);
-}
-
-// Given the capacity of a table, computes the total size of the backing
-// array.
-inline size_t AllocSize(size_t capacity, size_t slot_size, size_t slot_align) {
- return SlotOffset(capacity, slot_align) + capacity * slot_size;
-}
-
template <typename Alloc, size_t SizeOfSlot, size_t AlignOfSlot>
ABSL_ATTRIBUTE_NOINLINE void InitializeSlots(CommonFields& c, Alloc alloc) {
assert(c.capacity());
@@ -1426,9 +1431,8 @@ struct PolicyFunctions {
// Transfer the contents of src_slot to dst_slot.
void (*transfer)(void* set, void* dst_slot, void* src_slot);
- // Deallocate the specified backing store which is sized for n slots.
- void (*dealloc)(void* set, const PolicyFunctions& policy,
- void* backing_array_start, void* slot_array, size_t n);
+ // Deallocate the backing store from common.
+ void (*dealloc)(CommonFields& common, const PolicyFunctions& policy);
};
// ClearBackingArray clears the backing array, either modifying it in place,
@@ -1445,16 +1449,16 @@ void EraseMetaOnly(CommonFields& c, ctrl_t* it, size_t slot_size);
// function body for raw_hash_set instantiations that have the
// same slot alignment.
template <size_t AlignOfSlot>
-ABSL_ATTRIBUTE_NOINLINE void DeallocateStandard(void*,
- const PolicyFunctions& policy,
- void* backing_array_start,
- void* slot_array, size_t n) {
+ABSL_ATTRIBUTE_NOINLINE void DeallocateStandard(CommonFields& common,
+ const PolicyFunctions& policy) {
// Unpoison before returning the memory to the allocator.
- SanitizerUnpoisonMemoryRegion(slot_array, policy.slot_size * n);
+ SanitizerUnpoisonMemoryRegion(common.slot_array(),
+ policy.slot_size * common.capacity());
std::allocator<char> alloc;
Deallocate<BackingArrayAlignment(AlignOfSlot)>(
- &alloc, backing_array_start, AllocSize(n, policy.slot_size, AlignOfSlot));
+ &alloc, common.backing_array_start(),
+ common.alloc_size(policy.slot_size, AlignOfSlot));
}
// For trivially relocatable types we use memcpy directly. This allows us to
@@ -2763,16 +2767,16 @@ class raw_hash_set {
static_cast<slot_type*>(src));
}
// Note: dealloc_fn will only be used if we have a non-standard allocator.
- static void dealloc_fn(void* set, const PolicyFunctions&,
- void* backing_array_start, void* slot_mem, size_t n) {
- auto* h = static_cast<raw_hash_set*>(set);
+ static void dealloc_fn(CommonFields& common, const PolicyFunctions&) {
+ auto* set = reinterpret_cast<raw_hash_set*>(&common);
// Unpoison before returning the memory to the allocator.
- SanitizerUnpoisonMemoryRegion(slot_mem, sizeof(slot_type) * n);
+ SanitizerUnpoisonMemoryRegion(common.slot_array(),
+ sizeof(slot_type) * common.capacity());
Deallocate<BackingArrayAlignment(alignof(slot_type))>(
- &h->alloc_ref(), backing_array_start,
- AllocSize(n, sizeof(slot_type), alignof(slot_type)));
+ &set->alloc_ref(), common.backing_array_start(),
+ common.alloc_size(sizeof(slot_type), alignof(slot_type)));
}
static const PolicyFunctions& GetPolicyFunctions() {