summaryrefslogtreecommitdiff
path: root/absl/container/internal/raw_hash_set.h
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2018-12-20 12:29:59 -0800
committerGravatar Xiaoyi Zhang <zhangxy988@gmail.com>2018-12-21 14:43:20 -0500
commit968a34ffdaadd7db062a9621dfbdf8b2d16e05af (patch)
tree6db3f5237087d2c51b264ecb33cd57f1e17b69b9 /absl/container/internal/raw_hash_set.h
parent3e2e9b5557e76d098de4b8a2a659125b98ca519b (diff)
Export of internal Abseil changes.
-- 7fa1107161a03dac53fb84c2b06d8092616c7b13 by Abseil Team <absl-team@google.com>: Harden the generic stacktrace implementation for use during early program execution PiperOrigin-RevId: 226375950 -- 079f9969329f5eb66f647dd3c44b17541b1bf217 by Matt Kulukundis <kfm@google.com>: Workaround platforms that have over-aggressive warnings on -Wexit-time-destructors PiperOrigin-RevId: 226362948 -- 1447943f509be681ca5495add0162c750ef237f1 by Matt Kulukundis <kfm@google.com>: Switch from 64 to size_t atomics so they work on embedded platforms that do not have 64 bit atomics. PiperOrigin-RevId: 226210704 -- d14d49837ae2bcde74051e0c79c18ee0f43866b9 by Tom Manshreck <shreck@google.com>: Develop initial documentation for API breaking changes process: PiperOrigin-RevId: 226210021 -- 7ea3d7fe0e86979dab83a5fc9cc3bf1d6cb3bd53 by Abseil Team <absl-team@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 226195522 -- 7de873e880d7f016a4fa1e08d626f0535cc470af by Abseil Team <absl-team@google.com>: Make Abseil LICENSE files newline terminated, with a single trailing blank line. Also remove line-ending whitespace. PiperOrigin-RevId: 226182949 -- 7d00643fadfad7f0d992c68bd9d2ed2e5bc960b0 by Matt Kulukundis <kfm@google.com>: Internal cleanup PiperOrigin-RevId: 226045282 -- c4a0a11c0ce2875271191e477f3d36eaaeca4613 by Matt Kulukundis <kfm@google.com>: Internal cleanup PiperOrigin-RevId: 226038273 -- 8ee4ebbb1ae5cda119e436e5ff7e3aa966608c10 by Matt Kulukundis <kfm@google.com>: Adds a global sampler which tracks a fraction of live tables for collecting telemetry data. PiperOrigin-RevId: 226032080 -- d576446f050518cd1b0ae447d682d8552f0e7e30 by Mark Barolak <mbar@google.com>: Replace an internal CaseEqual function with calls to the identical absl::EqualsIgnoreCase. This closes out a rather old TODO. PiperOrigin-RevId: 226024779 -- 6b23f1ee028a5ffa608c920424f1220a117a8f3d by Abseil Team <absl-team@google.com>: Add December 2018 LTS branch to list of LTS branches. PiperOrigin-RevId: 226011333 -- bb0833a43bdaef4c8c059b17bcd27ba9a085a114 by Mark Barolak <mbar@google.com>: Explicitly state that when the SimpleAtoi family of functions encounter an error, the value of their output parameter is unspecified. Also standardize the name of the output parameter to be `out`. PiperOrigin-RevId: 225997035 -- 46c1876b1a248eabda7545daa61a74a4cdfe9077 by Abseil Team <absl-team@google.com>: Remove deprecated CMake function absl_test, absl_library and absl_header_library PiperOrigin-RevId: 225950041 GitOrigin-RevId: 7fa1107161a03dac53fb84c2b06d8092616c7b13 Change-Id: I2ca9d3aada9292614527d1339a7557494139b806
Diffstat (limited to 'absl/container/internal/raw_hash_set.h')
-rw-r--r--absl/container/internal/raw_hash_set.h53
1 files changed, 38 insertions, 15 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index b7b5ef8c..34d69d7a 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -109,6 +109,7 @@
#include "absl/container/internal/container_memory.h"
#include "absl/container/internal/hash_policy_traits.h"
#include "absl/container/internal/hashtable_debug_hooks.h"
+#include "absl/container/internal/hashtablez_sampler.h"
#include "absl/container/internal/have_sse.h"
#include "absl/container/internal/layout.h"
#include "absl/memory/memory.h"
@@ -943,9 +944,10 @@ class raw_hash_set {
// than a full `insert`.
for (const auto& v : that) {
const size_t hash = PolicyTraits::apply(HashElement{hash_ref()}, v);
- const size_t i = find_first_non_full(hash);
- set_ctrl(i, H2(hash));
- emplace_at(i, v);
+ auto target = find_first_non_full(hash);
+ set_ctrl(target.offset, H2(hash));
+ emplace_at(target.offset, v);
+ infoz_.RecordInsert(hash, target.probe_length);
}
size_ = that.size();
growth_left() -= that.size();
@@ -959,6 +961,7 @@ 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.
@@ -979,6 +982,7 @@ class raw_hash_set {
std::swap(size_, that.size_);
std::swap(capacity_, that.capacity_);
std::swap(growth_left(), that.growth_left());
+ std::swap(infoz_, that.infoz_);
} else {
reserve(that.size());
// Note: this will copy elements of dense_set and unordered_set instead of
@@ -1049,6 +1053,7 @@ class raw_hash_set {
growth_left() = static_cast<size_t>(capacity_ * kMaxLoadFactor);
}
assert(empty());
+ infoz_.RecordStorageChanged(size_, capacity_);
}
// This overload kicks in when the argument is an rvalue of insertable and
@@ -1323,6 +1328,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_);
if (AllocTraits::propagate_on_container_swap::value) {
swap(alloc_ref(), that.alloc_ref());
} else {
@@ -1333,7 +1339,11 @@ class raw_hash_set {
void rehash(size_t n) {
if (n == 0 && capacity_ == 0) return;
- if (n == 0 && size_ == 0) return destroy_slots();
+ if (n == 0 && size_ == 0) {
+ destroy_slots();
+ infoz_.RecordStorageChanged(size_, capacity_);
+ return;
+ }
auto m = NormalizeCapacity((std::max)(n, NumSlotsFast(size())));
// n == 0 unconditionally rehashes as per the standard.
if (n == 0 || m > capacity_) {
@@ -1550,10 +1560,15 @@ class raw_hash_set {
set_ctrl(index, was_never_full ? kEmpty : kDeleted);
growth_left() += was_never_full;
+ infoz_.RecordErase();
}
void initialize_slots() {
assert(capacity_);
+ if (slots_ == nullptr) {
+ infoz_ = Sample();
+ }
+
auto layout = MakeLayout(capacity_);
char* mem = static_cast<char*>(
Allocate<Layout::Alignment()>(&alloc_ref(), layout.AllocSize()));
@@ -1561,6 +1576,7 @@ class raw_hash_set {
slots_ = layout.template Pointer<1>(mem);
reset_ctrl();
growth_left() = static_cast<size_t>(capacity_ * kMaxLoadFactor) - size_;
+ infoz_.RecordStorageChanged(size_, capacity_);
}
void destroy_slots() {
@@ -1593,7 +1609,7 @@ class raw_hash_set {
if (IsFull(old_ctrl[i])) {
size_t hash = PolicyTraits::apply(HashElement{hash_ref()},
PolicyTraits::element(old_slots + i));
- size_t new_i = find_first_non_full(hash);
+ size_t new_i = find_first_non_full(hash).offset;
set_ctrl(new_i, H2(hash));
PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, old_slots + i);
}
@@ -1633,7 +1649,7 @@ class raw_hash_set {
if (!IsDeleted(ctrl_[i])) continue;
size_t hash = PolicyTraits::apply(HashElement{hash_ref()},
PolicyTraits::element(slots_ + i));
- size_t new_i = find_first_non_full(hash);
+ size_t new_i = find_first_non_full(hash).offset;
// Verify if the old and new i fall within the same group wrt the hash.
// If they do, we don't need to move the object as it falls already in the
@@ -1706,7 +1722,11 @@ class raw_hash_set {
// - the input is already a set
// - there are enough slots
// - the element with the hash is not in the table
- size_t find_first_non_full(size_t hash) {
+ struct FindInfo {
+ size_t offset;
+ size_t probe_length;
+ };
+ FindInfo find_first_non_full(size_t hash) {
auto seq = probe(hash);
while (true) {
Group g{ctrl_ + seq.offset()};
@@ -1718,11 +1738,11 @@ class raw_hash_set {
// the group.
// TODO(kfm,sbenza): revisit after we do unconditional mixing
if (ShouldInsertBackwards(hash, ctrl_))
- return seq.offset(mask.HighestBitSet());
+ return {seq.offset(mask.HighestBitSet()), seq.index()};
else
- return seq.offset(mask.LowestBitSet());
+ return {seq.offset(mask.LowestBitSet()), seq.index()};
#else
- return seq.offset(mask.LowestBitSet());
+ return {seq.offset(mask.LowestBitSet()), seq.index()};
#endif
}
assert(seq.index() < capacity_ && "full table!");
@@ -1762,15 +1782,17 @@ class raw_hash_set {
}
size_t prepare_insert(size_t hash) ABSL_ATTRIBUTE_NOINLINE {
- size_t target = find_first_non_full(hash);
- if (ABSL_PREDICT_FALSE(growth_left() == 0 && !IsDeleted(ctrl_[target]))) {
+ auto target = find_first_non_full(hash);
+ if (ABSL_PREDICT_FALSE(growth_left() == 0 &&
+ !IsDeleted(ctrl_[target.offset]))) {
rehash_and_grow_if_necessary();
target = find_first_non_full(hash);
}
++size_;
- growth_left() -= IsEmpty(ctrl_[target]);
- set_ctrl(target, H2(hash));
- return target;
+ growth_left() -= IsEmpty(ctrl_[target.offset]);
+ set_ctrl(target.offset, H2(hash));
+ infoz_.RecordInsert(hash, target.probe_length);
+ return target.offset;
}
// Constructs the value in the space pointed by the iterator. This only works
@@ -1847,6 +1869,7 @@ class raw_hash_set {
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,
key_equal, allocator_type>
settings_{0, hasher{}, key_equal{}, allocator_type{}};