diff options
author | 2018-12-20 12:29:59 -0800 | |
---|---|---|
committer | 2018-12-21 14:43:20 -0500 | |
commit | 968a34ffdaadd7db062a9621dfbdf8b2d16e05af (patch) | |
tree | 6db3f5237087d2c51b264ecb33cd57f1e17b69b9 /absl/container/internal/raw_hash_set.h | |
parent | 3e2e9b5557e76d098de4b8a2a659125b98ca519b (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.h | 53 |
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{}}; |