aboutsummaryrefslogtreecommitdiff
path: root/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/abseil-cpp/absl/container/internal/raw_hash_set.h')
-rw-r--r--third_party/abseil-cpp/absl/container/internal/raw_hash_set.h77
1 files changed, 41 insertions, 36 deletions
diff --git a/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h b/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h
index 80fc2cba3f..aa78265ca1 100644
--- a/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h
+++ b/third_party/abseil-cpp/absl/container/internal/raw_hash_set.h
@@ -628,7 +628,9 @@ class raw_hash_set {
static Layout MakeLayout(size_t capacity) {
assert(IsValidCapacity(capacity));
- return Layout(capacity + Group::kWidth + 1, capacity);
+ // The extra control bytes are for 1 sentinel byte followed by
+ // `Group::kWidth - 1` bytes that are cloned from the beginning.
+ return Layout(capacity + Group::kWidth, capacity);
}
using AllocTraits = absl::allocator_traits<allocator_type>;
@@ -792,7 +794,8 @@ class raw_hash_set {
explicit raw_hash_set(size_t bucket_count, const hasher& hash = hasher(),
const key_equal& eq = key_equal(),
const allocator_type& alloc = allocator_type())
- : ctrl_(EmptyGroup()), settings_(0, hash, eq, alloc) {
+ : ctrl_(EmptyGroup()),
+ settings_(0, HashtablezInfoHandle(), hash, eq, alloc) {
if (bucket_count) {
capacity_ = NormalizeCapacity(bucket_count);
initialize_slots();
@@ -903,7 +906,7 @@ class raw_hash_set {
auto target = find_first_non_full(ctrl_, hash, capacity_);
set_ctrl(target.offset, H2(hash));
emplace_at(target.offset, v);
- infoz_.RecordInsert(hash, target.probe_length);
+ infoz().RecordInsert(hash, target.probe_length);
}
size_ = that.size();
growth_left() -= that.size();
@@ -917,28 +920,27 @@ class raw_hash_set {
slots_(absl::exchange(that.slots_, nullptr)),
size_(absl::exchange(that.size_, 0)),
capacity_(absl::exchange(that.capacity_, 0)),
- infoz_(absl::exchange(that.infoz_, HashtablezInfoHandle())),
// Hash, equality and allocator are copied instead of moved because
// `that` must be left valid. If Hash is std::function<Key>, moving it
// would create a nullptr functor that cannot be called.
- settings_(that.settings_) {
- // growth_left was copied above, reset the one from `that`.
- that.growth_left() = 0;
- }
+ settings_(absl::exchange(that.growth_left(), 0),
+ absl::exchange(that.infoz(), HashtablezInfoHandle()),
+ that.hash_ref(), that.eq_ref(), that.alloc_ref()) {}
raw_hash_set(raw_hash_set&& that, const allocator_type& a)
: ctrl_(EmptyGroup()),
slots_(nullptr),
size_(0),
capacity_(0),
- settings_(0, that.hash_ref(), that.eq_ref(), a) {
+ settings_(0, HashtablezInfoHandle(), that.hash_ref(), that.eq_ref(),
+ a) {
if (a == that.alloc_ref()) {
std::swap(ctrl_, that.ctrl_);
std::swap(slots_, that.slots_);
std::swap(size_, that.size_);
std::swap(capacity_, that.capacity_);
std::swap(growth_left(), that.growth_left());
- std::swap(infoz_, that.infoz_);
+ std::swap(infoz(), that.infoz());
} else {
reserve(that.size());
// Note: this will copy elements of dense_set and unordered_set instead of
@@ -1009,7 +1011,7 @@ class raw_hash_set {
reset_growth_left();
}
assert(empty());
- infoz_.RecordStorageChanged(0, capacity_);
+ infoz().RecordStorageChanged(0, capacity_);
}
// This overload kicks in when the argument is an rvalue of insertable and
@@ -1301,7 +1303,7 @@ class raw_hash_set {
swap(growth_left(), that.growth_left());
swap(hash_ref(), that.hash_ref());
swap(eq_ref(), that.eq_ref());
- swap(infoz_, that.infoz_);
+ swap(infoz(), that.infoz());
SwapAlloc(alloc_ref(), that.alloc_ref(),
typename AllocTraits::propagate_on_container_swap{});
}
@@ -1310,7 +1312,7 @@ class raw_hash_set {
if (n == 0 && capacity_ == 0) return;
if (n == 0 && size_ == 0) {
destroy_slots();
- infoz_.RecordStorageChanged(0, 0);
+ infoz().RecordStorageChanged(0, 0);
return;
}
// bitor is a faster way of doing `max` here. We will round up to the next
@@ -1323,8 +1325,8 @@ class raw_hash_set {
}
void reserve(size_t n) {
- size_t m = GrowthToLowerboundCapacity(n);
- if (m > capacity_) {
+ if (n > size() + growth_left()) {
+ size_t m = GrowthToLowerboundCapacity(n);
resize(NormalizeCapacity(m));
}
}
@@ -1528,7 +1530,7 @@ class raw_hash_set {
set_ctrl(index, was_never_full ? kEmpty : kDeleted);
growth_left() += was_never_full;
- infoz_.RecordErase();
+ infoz().RecordErase();
}
void initialize_slots() {
@@ -1545,17 +1547,17 @@ class raw_hash_set {
// bound more carefully.
if (std::is_same<SlotAlloc, std::allocator<slot_type>>::value &&
slots_ == nullptr) {
- infoz_ = Sample();
+ infoz() = Sample();
}
auto layout = MakeLayout(capacity_);
char* mem = static_cast<char*>(
Allocate<Layout::Alignment()>(&alloc_ref(), layout.AllocSize()));
- ctrl_ = reinterpret_cast<ctrl_t*>(layout.template Pointer<0>(mem));
+ ctrl_ = layout.template Pointer<0>(mem);
slots_ = layout.template Pointer<1>(mem);
reset_ctrl();
reset_growth_left();
- infoz_.RecordStorageChanged(size_, capacity_);
+ infoz().RecordStorageChanged(size_, capacity_);
}
void destroy_slots() {
@@ -1603,7 +1605,7 @@ class raw_hash_set {
Deallocate<Layout::Alignment()>(&alloc_ref(), old_ctrl,
layout.AllocSize());
}
- infoz_.RecordRehash(total_probe_length);
+ infoz().RecordRehash(total_probe_length);
}
void drop_deletes_without_resize() ABSL_ATTRIBUTE_NOINLINE {
@@ -1669,7 +1671,7 @@ class raw_hash_set {
}
}
reset_growth_left();
- infoz_.RecordRehash(total_probe_length);
+ infoz().RecordRehash(total_probe_length);
}
void rehash_and_grow_if_necessary() {
@@ -1743,7 +1745,7 @@ class raw_hash_set {
++size_;
growth_left() -= IsEmpty(ctrl_[target.offset]);
set_ctrl(target.offset, H2(hash));
- infoz_.RecordInsert(hash, target.probe_length);
+ infoz().RecordInsert(hash, target.probe_length);
return target.offset;
}
@@ -1782,8 +1784,8 @@ class raw_hash_set {
growth_left() = CapacityToGrowth(capacity()) - size_;
}
- // Sets the control byte, and if `i < Group::kWidth`, set the cloned byte at
- // the end too.
+ // Sets the control byte, and if `i < Group::kWidth - 1`, set the cloned byte
+ // at the end too.
void set_ctrl(size_t i, ctrl_t h) {
assert(i < capacity_);
@@ -1794,32 +1796,35 @@ class raw_hash_set {
}
ctrl_[i] = h;
- ctrl_[((i - Group::kWidth) & capacity_) + 1 +
- ((Group::kWidth - 1) & capacity_)] = h;
+ constexpr size_t kClonedBytes = Group::kWidth - 1;
+ ctrl_[((i - kClonedBytes) & capacity_) + (kClonedBytes & capacity_)] = h;
}
size_t& growth_left() { return settings_.template get<0>(); }
- hasher& hash_ref() { return settings_.template get<1>(); }
- const hasher& hash_ref() const { return settings_.template get<1>(); }
- key_equal& eq_ref() { return settings_.template get<2>(); }
- const key_equal& eq_ref() const { return settings_.template get<2>(); }
- allocator_type& alloc_ref() { return settings_.template get<3>(); }
+ HashtablezInfoHandle& infoz() { return settings_.template get<1>(); }
+
+ hasher& hash_ref() { return settings_.template get<2>(); }
+ const hasher& hash_ref() const { return settings_.template get<2>(); }
+ key_equal& eq_ref() { return settings_.template get<3>(); }
+ const key_equal& eq_ref() const { return settings_.template get<3>(); }
+ allocator_type& alloc_ref() { return settings_.template get<4>(); }
const allocator_type& alloc_ref() const {
- return settings_.template get<3>();
+ return settings_.template get<4>();
}
// TODO(alkis): Investigate removing some of these fields:
// - ctrl/slots can be derived from each other
// - size can be moved into the slot array
- ctrl_t* ctrl_ = EmptyGroup(); // [(capacity + 1) * ctrl_t]
+ ctrl_t* ctrl_ = EmptyGroup(); // [(capacity + Group::kWidth) * ctrl_t]
slot_type* slots_ = nullptr; // [capacity * slot_type]
size_t size_ = 0; // number of full slots
size_t capacity_ = 0; // total number of slots
- HashtablezInfoHandle infoz_;
- absl::container_internal::CompressedTuple<size_t /* growth_left */, hasher,
+ absl::container_internal::CompressedTuple<size_t /* growth_left */,
+ HashtablezInfoHandle, hasher,
key_equal, allocator_type>
- settings_{0, hasher{}, key_equal{}, allocator_type{}};
+ settings_{0, HashtablezInfoHandle{}, hasher{}, key_equal{},
+ allocator_type{}};
};
// Erases all elements that satisfy the predicate `pred` from the container `c`.
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-23 19:34:21 +0000