Export of internal Abseil changes.

--
3d20ce6cd6541579abecaba169d4b8716d511272 by Jon Cohen <cohenjon@google.com>:

Only use LSAN for clang version >= 3.5.  This should fix https://github.com/abseil/abseil-cpp/issues/244

PiperOrigin-RevId: 234675129

--
e15bd4ec7a81aa95cc3d09fa1e0e81d58ae478fb by Conrad Parker <conradparker@google.com>:

Fix errors in apply() sample code

The following changes are made:
 * Make the example method public.
 * Give the two user functions different names to avoid confusion about
   whether apply() can select the correct overload of a function based
   on its tuple argument (it can't).
 * Pass tuple2 to the second example apply() invocation, instead of
   passing its contents individually.
 * Fix a s/tuple/tuple3/ typo in the third example apply() invocation.

PiperOrigin-RevId: 234223407

--
de0ed71e21bc76ddf9fe715fdbaef74cd0df95c7 by Abseil Team <absl-team@google.com>:

First test if a macro is defined to avoid -Wundef.

ABSL clients may need to compile their code with the -Wundef warning
flag. It will be helpful if ABSL header files can be compiled without
the -Wundef warning.

How to avoid the -Wundef warning: If a macro may be undefined, we need
to first test whether the macro is defined before testing its value. We
can't rely on the C preprocessor rule that an undefined macro has the
value 0L.

PiperOrigin-RevId: 234201123

--
fa484ad7dae0cac21140a96662809ecb0ec8eb5d by Abseil Team <absl-team@google.com>:

Internal change.

PiperOrigin-RevId: 234185697

--
d69b1baef681e27954b065375ecf9c2320463b2b by Samuel Benzaquen <sbenza@google.com>:

Mix pointers more thoroughly.
Some pointer alignments interact badly with the mixing constant. By mixing twice we reduce this problem.

PiperOrigin-RevId: 234178401

--
1041d0e474610f3a8fea0db90958857327d6da1c by Samuel Benzaquen <sbenza@google.com>:

Record rehashes in the hashtablez struct.
Only recording the probe length on insertion causes a huge overestimation of
the total probe length at any given time.

With natural growth, elements are inserted when the load factor is between
(max load/2, max load). However, after a rehash the majority of elements are
actually inserted when the load factor is less than max/2 and have a much lower
average probe length.

Also reset some values when the table is cleared.

PiperOrigin-RevId: 234013580

--
299205caf3c89c47339f7409bc831746602cea84 by Mark Barolak <mbar@google.com>:

Fix a sample code snippet that assumes `absl::string_view::const_iterator` is `const char*`.  This is generally true, however in C++17 builds, absl::string_view is an alias for std::string_view and on MSVC, the std::string_view::const_iterator is an object instead of just a pointer.

PiperOrigin-RevId: 233844595

--
af6c6370cf51a1e6c1469c79dfb2a486a4009136 by Abseil Team <absl-team@google.com>:

Internal change.

PiperOrigin-RevId: 233773470

--
6e59e4b8e2bb6101b448f0f32b0bea81fe399ccf by Abseil Team <absl-team@google.com>:

fix typo in {Starts|Ends}WithIgnoreCase comment in match.h

PiperOrigin-RevId: 233662951
GitOrigin-RevId: 3d20ce6cd6541579abecaba169d4b8716d511272
Change-Id: Ib9a29b1c38c6aedf5d9f3f7f00596e8d30e864dd

1 files changed, 12 insertions, 4 deletions

diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index a5d0cae0..33f8f8fa 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -936,7 +936,7 @@ class raw_hash_set {
       reset_growth_left();
     }
     assert(empty());
-    infoz_.RecordStorageChanged(size_, capacity_);
+    infoz_.RecordStorageChanged(0, capacity_);
   }
 
   // This overload kicks in when the argument is an rvalue of insertable and
@@ -1226,7 +1226,7 @@ class raw_hash_set {
     if (n == 0 && capacity_ == 0) return;
     if (n == 0 && size_ == 0) {
       destroy_slots();
-      infoz_.RecordStorageChanged(size_, capacity_);
+      infoz_.RecordStorageChanged(0, 0);
       return;
     }
     // bitor is a faster way of doing `max` here. We will round up to the next
@@ -1483,11 +1483,14 @@ class raw_hash_set {
     capacity_ = new_capacity;
     initialize_slots();
 
+    size_t total_probe_length = 0;
     for (size_t i = 0; i != old_capacity; ++i) {
       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).offset;
+        auto target = find_first_non_full(hash);
+        size_t new_i = target.offset;
+        total_probe_length += target.probe_length;
         set_ctrl(new_i, H2(hash));
         PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, old_slots + i);
       }
@@ -1499,6 +1502,7 @@ class raw_hash_set {
       Deallocate<Layout::Alignment()>(&alloc_ref(), old_ctrl,
                                       layout.AllocSize());
     }
+    infoz_.RecordRehash(total_probe_length);
   }
 
   void drop_deletes_without_resize() ABSL_ATTRIBUTE_NOINLINE {
@@ -1522,12 +1526,15 @@ class raw_hash_set {
     ConvertDeletedToEmptyAndFullToDeleted(ctrl_, capacity_);
     typename std::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type
         raw;
+    size_t total_probe_length = 0;
     slot_type* slot = reinterpret_cast<slot_type*>(&raw);
     for (size_t i = 0; i != capacity_; ++i) {
       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).offset;
+      auto target = find_first_non_full(hash);
+      size_t new_i = target.offset;
+      total_probe_length += target.probe_length;
 
       // 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
@@ -1560,6 +1567,7 @@ class raw_hash_set {
       }
     }
     reset_growth_left();
+    infoz_.RecordRehash(total_probe_length);
   }
 
   void rehash_and_grow_if_necessary() {