Export of internal Abseil changes

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

Fix typos in documentation.

PiperOrigin-RevId: 423376798

--
bf87e5de48a868f49a57d516be027e6e3a3cc3bd by Gennadiy Rozental <rogeeff@google.com>:

Correct WEAK attribute enabling condition.

ABSL_ATTRIBUTE_WEAK is present if:
    compiler has built-in attribute weak
  OR
    we are using gcc (and not clang)
AND
    we are not on windows
  OR
    we use windows clang version >= 9.0.0
AND
  we are not on MinGW

PiperOrigin-RevId: 423357629

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

There are magic numbers in the expected load factors and probe lengths, and they seem to be wrong especially under msvc.  Even under the linux tool chain, these tests fail occasionally.  Fix the magic numbers to make the tests succeed.

PiperOrigin-RevId: 423320829

--
fd109295a1425ca1cb2b69fe34a294b6189542c0 by Laramie Leavitt <lar@google.com>:

Manually align buffers in randen_engine.

In C++ it's implementation defined whether types with extended alignment are supported.

randen_engine uses vector intrinsics with 16-byte alignment requirements in
some instances, so internally we allocate an extra 8 bytes to manually align to 16.

No detectable performance impact.

PiperOrigin-RevId: 423109265
GitOrigin-RevId: 75504b9d2eb7560359b98b69136d071f980e04f2
Change-Id: I8c5ab2269ff6d9e89d3b4d0e95d36ddb6ce8096e

5 files changed, 74 insertions, 56 deletions

diff --git a/absl/base/attributes.h b/absl/base/attributes.h
index 00aad489..4ab6fa27 100644
--- a/absl/base/attributes.h
+++ b/absl/base/attributes.h
@@ -136,9 +136,9 @@
 // for further information.
 // The MinGW compiler doesn't complain about the weak attribute until the link
 // step, presumably because Windows doesn't use ELF binaries.
-#if (ABSL_HAVE_ATTRIBUTE(weak) ||                                        \
-     (defined(__GNUC__) && !defined(__clang__))) &&                      \
-    (!defined(_WIN32) || (defined(__clang__) && __clang_major__ < 9)) && \
+#if (ABSL_HAVE_ATTRIBUTE(weak) ||                                         \
+     (defined(__GNUC__) && !defined(__clang__))) &&                       \
+    (!defined(_WIN32) || (defined(__clang__) && __clang_major__ >= 9)) && \
     !defined(__MINGW32__)
 #undef ABSL_ATTRIBUTE_WEAK
 #define ABSL_ATTRIBUTE_WEAK __attribute__((weak))
@@ -312,7 +312,6 @@
   __attribute__((section(#name))) __attribute__((noinline))
 #endif
 
-
 // ABSL_ATTRIBUTE_SECTION_VARIABLE
 //
 // Tells the compiler/linker to put a given variable into a section and define
@@ -339,8 +338,8 @@
 // a no-op on ELF but not on Mach-O.
 //
 #ifndef ABSL_DECLARE_ATTRIBUTE_SECTION_VARS
-#define ABSL_DECLARE_ATTRIBUTE_SECTION_VARS(name) \
-  extern char __start_##name[] ABSL_ATTRIBUTE_WEAK;    \
+#define ABSL_DECLARE_ATTRIBUTE_SECTION_VARS(name)   \
+  extern char __start_##name[] ABSL_ATTRIBUTE_WEAK; \
   extern char __stop_##name[] ABSL_ATTRIBUTE_WEAK
 #endif
 #ifndef ABSL_DEFINE_ATTRIBUTE_SECTION_VARS
@@ -503,7 +502,7 @@
 #define ABSL_XRAY_NEVER_INSTRUMENT [[clang::xray_never_instrument]]
 #if ABSL_HAVE_CPP_ATTRIBUTE(clang::xray_log_args)
 #define ABSL_XRAY_LOG_ARGS(N) \
-    [[clang::xray_always_instrument, clang::xray_log_args(N)]]
+  [[clang::xray_always_instrument, clang::xray_log_args(N)]]
 #else
 #define ABSL_XRAY_LOG_ARGS(N) [[clang::xray_always_instrument]]
 #endif
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index f1c650cc..0fb2ae6f 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -67,7 +67,7 @@ struct FlatHashSetPolicy;
 //
 // By default, `flat_hash_set` uses the `absl::Hash` hashing framework. All
 // fundamental and Abseil types that support the `absl::Hash` framework have a
-// compatible equality operator for comparing insertions into `flat_hash_map`.
+// compatible equality operator for comparing insertions into `flat_hash_set`.
 // If your type is not yet supported by the `absl::Hash` framework, see
 // absl/hash/hash.h for information on extending Abseil hashing to user-defined
 // types.
@@ -106,7 +106,7 @@ class flat_hash_set
  public:
   // Constructors and Assignment Operators
   //
-  // A flat_hash_set supports the same overload set as `std::unordered_map`
+  // A flat_hash_set supports the same overload set as `std::unordered_set`
   // for construction and assignment:
   //
   // *  Default constructor
@@ -173,7 +173,7 @@ class flat_hash_set
   // available within the `flat_hash_set`.
   //
   // NOTE: this member function is particular to `absl::flat_hash_set` and is
-  // not provided in the `std::unordered_map` API.
+  // not provided in the `std::unordered_set` API.
   using Base::capacity;
 
   // flat_hash_set::empty()
@@ -332,7 +332,7 @@ class flat_hash_set
   // flat_hash_set::swap(flat_hash_set& other)
   //
   // Exchanges the contents of this `flat_hash_set` with those of the `other`
-  // flat hash map, avoiding invocation of any move, copy, or swap operations on
+  // flat hash set, avoiding invocation of any move, copy, or swap operations on
   // individual elements.
   //
   // All iterators and references on the `flat_hash_set` remain valid, excepting
@@ -340,7 +340,7 @@ class flat_hash_set
   //
   // `swap()` requires that the flat hash set's hashing and key equivalence
   // functions be Swappable, and are exchaged using unqualified calls to
-  // non-member `swap()`. If the map's allocator has
+  // non-member `swap()`. If the set's allocator has
   // `std::allocator_traits<allocator_type>::propagate_on_container_swap::value`
   // set to `true`, the allocators are also exchanged using an unqualified call
   // to non-member `swap()`; otherwise, the allocators are not swapped.
@@ -395,14 +395,14 @@ class flat_hash_set
   // flat_hash_set::bucket_count()
   //
   // Returns the number of "buckets" within the `flat_hash_set`. Note that
-  // because a flat hash map contains all elements within its internal storage,
+  // because a flat hash set contains all elements within its internal storage,
   // this value simply equals the current capacity of the `flat_hash_set`.
   using Base::bucket_count;
 
   // flat_hash_set::load_factor()
   //
   // Returns the current load factor of the `flat_hash_set` (the average number
-  // of slots occupied with a value within the hash map).
+  // of slots occupied with a value within the hash set).
   using Base::load_factor;
 
   // flat_hash_set::max_load_factor()
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 362b3cae..47015bcf 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1244,7 +1244,7 @@ ExpectedStats XorSeedExpectedStats() {
     case 16:
       if (kRandomizesInserts) {
         return {0.1,
-                1.0,
+                2.0,
                 {{0.95, 0.1}},
                 {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
       } else {
@@ -1258,7 +1258,7 @@ ExpectedStats XorSeedExpectedStats() {
   return {};
 }
 
-TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
+TEST(Table, EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
   ProbeStatsPerSize stats;
   std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
   for (size_t size : sizes) {
@@ -1330,17 +1330,17 @@ ExpectedStats LinearTransformExpectedStats() {
                 {{0.95, 0.3}},
                 {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
       } else {
-        return {0.15,
-                0.5,
-                {{0.95, 0.3}},
-                {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}};
+        return {0.4,
+                0.6,
+                {{0.95, 0.5}},
+                {{0.95, 1}, {0.99, 14}, {0.999, 23}, {0.9999, 26}}};
       }
     case 16:
       if (kRandomizesInserts) {
         return {0.1,
                 0.4,
                 {{0.95, 0.3}},
-                {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
+                {{0.95, 1}, {0.99, 2}, {0.999, 9}, {0.9999, 15}}};
       } else {
         return {0.05,
                 0.2,
@@ -1352,7 +1352,7 @@ ExpectedStats LinearTransformExpectedStats() {
   return {};
 }
 
-TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
+TEST(Table, EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
   ProbeStatsPerSize stats;
   std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
   for (size_t size : sizes) {
diff --git a/absl/random/internal/randen.h b/absl/random/internal/randen.h
index 9a3840b8..9ff4a7a5 100644
--- a/absl/random/internal/randen.h
+++ b/absl/random/internal/randen.h
@@ -43,10 +43,8 @@ class Randen {
 
   // Generate updates the randen sponge. The outer portion of the sponge
   // (kCapacityBytes .. kStateBytes) may be consumed as PRNG state.
-  template <typename T, size_t N>
-  void Generate(T (&state)[N]) const {
-    static_assert(N * sizeof(T) == kStateBytes,
-                  "Randen::Generate() requires kStateBytes of state");
+  // REQUIRES: state points to kStateBytes of state.
+  inline void Generate(void* state) const {
 #if ABSL_RANDOM_INTERNAL_AES_DISPATCH
     // HW AES Dispatch.
     if (has_crypto_) {
@@ -65,13 +63,9 @@ class Randen {
 
   // Absorb incorporates additional seed material into the randen sponge.  After
   // absorb returns, Generate must be called before the state may be consumed.
-  template <typename S, size_t M, typename T, size_t N>
-  void Absorb(const S (&seed)[M], T (&state)[N]) const {
-    static_assert(M * sizeof(S) == RandenTraits::kSeedBytes,
-                  "Randen::Absorb() requires kSeedBytes of seed");
-
-    static_assert(N * sizeof(T) == RandenTraits::kStateBytes,
-                  "Randen::Absorb() requires kStateBytes of state");
+  // REQUIRES: seed points to kSeedBytes of seed.
+  // REQUIRES: state points to kStateBytes of state.
+  inline void Absorb(const void* seed, void* state) const {
 #if ABSL_RANDOM_INTERNAL_AES_DISPATCH
     // HW AES Dispatch.
     if (has_crypto_) {
diff --git a/absl/random/internal/randen_engine.h b/absl/random/internal/randen_engine.h
index 372c3ac2..b4708664 100644
--- a/absl/random/internal/randen_engine.h
+++ b/absl/random/internal/randen_engine.h
@@ -42,7 +42,7 @@ namespace random_internal {
 // 'Strong' (well-distributed, unpredictable, backtracking-resistant) random
 // generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32.
 template <typename T>
-class alignas(16) randen_engine {
+class alignas(8) randen_engine {
  public:
   // C++11 URBG interface:
   using result_type = T;
@@ -58,7 +58,8 @@ class alignas(16) randen_engine {
     return (std::numeric_limits<result_type>::max)();
   }
 
-  explicit randen_engine(result_type seed_value = 0) { seed(seed_value); }
+  randen_engine() : randen_engine(0) {}
+  explicit randen_engine(result_type seed_value) { seed(seed_value); }
 
   template <class SeedSequence,
             typename = typename absl::enable_if_t<
@@ -67,17 +68,27 @@ class alignas(16) randen_engine {
     seed(seq);
   }
 
-  randen_engine(const randen_engine&) = default;
+  // alignment requirements dictate custom copy and move constructors.
+  randen_engine(const randen_engine& other)
+      : next_(other.next_), impl_(other.impl_) {
+    std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type));
+  }
+  randen_engine& operator=(const randen_engine& other) {
+    next_ = other.next_;
+    impl_ = other.impl_;
+    std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type));
+    return *this;
+  }
 
   // Returns random bits from the buffer in units of result_type.
   result_type operator()() {
     // Refill the buffer if needed (unlikely).
+    auto* begin = state();
     if (next_ >= kStateSizeT) {
       next_ = kCapacityT;
-      impl_.Generate(state_);
+      impl_.Generate(begin);
     }
-
-    return little_endian::ToHost(state_[next_++]);
+    return little_endian::ToHost(begin[next_++]);
   }
 
   template <class SeedSequence>
@@ -92,9 +103,10 @@ class alignas(16) randen_engine {
   void seed(result_type seed_value = 0) {
     next_ = kStateSizeT;
     // Zeroes the inner state and fills the outer state with seed_value to
-    // mimics behaviour of reseed
-    std::fill(std::begin(state_), std::begin(state_) + kCapacityT, 0);
-    std::fill(std::begin(state_) + kCapacityT, std::end(state_), seed_value);
+    // mimic the behaviour of reseed
+    auto* begin = state();
+    std::fill(begin, begin + kCapacityT, 0);
+    std::fill(begin + kCapacityT, begin + kStateSizeT, seed_value);
   }
 
   // Inserts entropy into (part of) the state. Calling this periodically with
@@ -105,7 +117,6 @@ class alignas(16) randen_engine {
     using sequence_result_type = typename SeedSequence::result_type;
     static_assert(sizeof(sequence_result_type) == 4,
                   "SeedSequence::result_type must be 32-bit");
-
     constexpr size_t kBufferSize =
         Randen::kSeedBytes / sizeof(sequence_result_type);
     alignas(16) sequence_result_type buffer[kBufferSize];
@@ -119,8 +130,8 @@ class alignas(16) randen_engine {
     if (entropy_size < kBufferSize) {
       // ... and only request that many values, or 256-bits, when unspecified.
       const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size;
-      std::fill(std::begin(buffer) + requested_entropy, std::end(buffer), 0);
-      seq.generate(std::begin(buffer), std::begin(buffer) + requested_entropy);
+      std::fill(buffer + requested_entropy, buffer + kBufferSize, 0);
+      seq.generate(buffer, buffer + requested_entropy);
 #ifdef ABSL_IS_BIG_ENDIAN
       // Randen expects the seed buffer to be in Little Endian; reverse it on
       // Big Endian platforms.
@@ -146,9 +157,9 @@ class alignas(16) randen_engine {
         std::swap(buffer[--dst], buffer[--src]);
       }
     } else {
-      seq.generate(std::begin(buffer), std::end(buffer));
+      seq.generate(buffer, buffer + kBufferSize);
     }
-    impl_.Absorb(buffer, state_);
+    impl_.Absorb(buffer, state());
 
     // Generate will be called when operator() is called
     next_ = kStateSizeT;
@@ -159,9 +170,10 @@ class alignas(16) randen_engine {
     count -= step;
 
     constexpr uint64_t kRateT = kStateSizeT - kCapacityT;
+    auto* begin = state();
     while (count > 0) {
       next_ = kCapacityT;
-      impl_.Generate(state_);
+      impl_.Generate(*reinterpret_cast<result_type(*)[kStateSizeT]>(begin));
       step = std::min<uint64_t>(kRateT, count);
       count -= step;
     }
@@ -169,9 +181,9 @@ class alignas(16) randen_engine {
   }
 
   bool operator==(const randen_engine& other) const {
+    const auto* begin = state();
     return next_ == other.next_ &&
-           std::equal(std::begin(state_), std::end(state_),
-                      std::begin(other.state_));
+           std::equal(begin, begin + kStateSizeT, other.state());
   }
 
   bool operator!=(const randen_engine& other) const {
@@ -185,11 +197,12 @@ class alignas(16) randen_engine {
     using numeric_type =
         typename random_internal::stream_format_type<result_type>::type;
     auto saver = random_internal::make_ostream_state_saver(os);
-    for (const auto& elem : engine.state_) {
+    auto* it = engine.state();
+    for (auto* end = it + kStateSizeT; it < end; ++it) {
       // In the case that `elem` is `uint8_t`, it must be cast to something
       // larger so that it prints as an integer rather than a character. For
       // simplicity, apply the cast all circumstances.
-      os << static_cast<numeric_type>(little_endian::FromHost(elem))
+      os << static_cast<numeric_type>(little_endian::FromHost(*it))
          << os.fill();
     }
     os << engine.next_;
@@ -215,7 +228,7 @@ class alignas(16) randen_engine {
     if (is.fail()) {
       return is;
     }
-    std::memcpy(engine.state_, state, sizeof(engine.state_));
+    std::memcpy(engine.state(), state, sizeof(state));
     engine.next_ = next;
     return is;
   }
@@ -226,9 +239,21 @@ class alignas(16) randen_engine {
   static constexpr size_t kCapacityT =
       Randen::kCapacityBytes / sizeof(result_type);
 
-  // First kCapacityT are `inner', the others are accessible random bits.
-  alignas(16) result_type state_[kStateSizeT];
-  size_t next_;  // index within state_
+  // Returns the state array pointer, which is aligned to 16 bytes.
+  // The first kCapacityT are the `inner' sponge; the remainder are available.
+  result_type* state() {
+    return reinterpret_cast<result_type*>(
+        (reinterpret_cast<uintptr_t>(&raw_state_) & 0xf) ? (raw_state_ + 8)
+                                                         : raw_state_);
+  }
+  const result_type* state() const {
+    return const_cast<randen_engine*>(this)->state();
+  }
+
+  // raw state array, manually aligned in state(). This overallocates
+  // by 8 bytes since C++ does not guarantee extended heap alignment.
+  alignas(8) char raw_state_[Randen::kStateBytes + 8];
+  size_t next_;  // index within state()
   Randen impl_;
 };