about summary refs log tree commit diff
path: root/absl/container/internal/raw_hash_set.h
diff options
context:
space:
mode:
authorAbseil Team <absl-team@google.com>2018-12-20T20·29-0800
committerXiaoyi Zhang <zhangxy988@gmail.com>2018-12-21T19·43-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 b7b5ef8c7b44..34d69d7af2fc 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{}};