Export of internal Abseil changes

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

Internal change

PiperOrigin-RevId: 373620391

--
d454f10549d27d7b025d1ce0ef90a0cdec42c361 by Martijn Vels <mvels@google.com>:

Add SetCordRepForTesting() helper to CordzInfo

PiperOrigin-RevId: 373602832

--
7a2d7bdd2e60fb51333e81cd71ebd0a4edb60704 by Evan Brown <ezb@google.com>:

For StrAppend, make sure to follow exponential growth like std::string::append.

PiperOrigin-RevId: 373589332

--
24397f19bce45133a42feaa7c883009ef9325095 by Greg Falcon <gfalcon@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 373569246
GitOrigin-RevId: 912c205cf80c4ed24a08000c04263403857b7f75
Change-Id: I5444f7ca2c0980685ca5c51596c259b845d69673

6 files changed, 57 insertions, 7 deletions

diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel
index 612b1505..90efe85a 100644
--- a/absl/random/internal/BUILD.bazel
+++ b/absl/random/internal/BUILD.bazel
@@ -717,7 +717,6 @@ cc_test(
 
 cc_test(
     name = "iostream_state_saver_test",
-    size = "small",
     srcs = ["iostream_state_saver_test.cc"],
     linkopts = ABSL_DEFAULT_LINKOPTS,
     deps = [
diff --git a/absl/strings/internal/cordz_info.h b/absl/strings/internal/cordz_info.h
index 13aaee17..026d5b99 100644
--- a/absl/strings/internal/cordz_info.h
+++ b/absl/strings/internal/cordz_info.h
@@ -158,6 +158,11 @@ class ABSL_LOCKABLE CordzInfo : public CordzHandle {
     return rep_;
   }
 
+  // Sets the current value of `rep_` for testing purposes only.
+  void SetCordRepForTesting(CordRep* rep) ABSL_NO_THREAD_SAFETY_ANALYSIS {
+    rep_ = rep;
+  }
+
   // Returns the stack trace for where the cord was first sampled. Cords are
   // potentially sampled when they promote from an inlined cord to a tree or
   // ring representation, which is not necessarily the location where the cord
diff --git a/absl/strings/internal/resize_uninitialized.h b/absl/strings/internal/resize_uninitialized.h
index e42628e3..749c66e7 100644
--- a/absl/strings/internal/resize_uninitialized.h
+++ b/absl/strings/internal/resize_uninitialized.h
@@ -17,6 +17,7 @@
 #ifndef ABSL_STRINGS_INTERNAL_RESIZE_UNINITIALIZED_H_
 #define ABSL_STRINGS_INTERNAL_RESIZE_UNINITIALIZED_H_
 
+#include <algorithm>
 #include <string>
 #include <type_traits>
 #include <utility>
@@ -66,6 +67,28 @@ inline void STLStringResizeUninitialized(string_type* s, size_t new_size) {
   ResizeUninitializedTraits<string_type>::Resize(s, new_size);
 }
 
+// Used to ensure exponential growth so that the amortized complexity of
+// increasing the string size by a small amount is O(1), in contrast to
+// O(str->size()) in the case of precise growth.
+template <typename string_type>
+void STLStringReserveAmortized(string_type* s, size_t new_size) {
+  const size_t cap = s->capacity();
+  if (new_size > cap) {
+    // Make sure to always grow by at least a factor of 2x.
+    s->reserve((std::max)(new_size, 2 * cap));
+  }
+}
+
+// Like STLStringResizeUninitialized(str, new_size), except guaranteed to use
+// exponential growth so that the amortized complexity of increasing the string
+// size by a small amount is O(1), in contrast to O(str->size()) in the case of
+// precise growth.
+template <typename string_type>
+void STLStringResizeUninitializedAmortized(string_type* s, size_t new_size) {
+  STLStringReserveAmortized(s, new_size);
+  STLStringResizeUninitialized(s, new_size);
+}
+
 }  // namespace strings_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
diff --git a/absl/strings/internal/resize_uninitialized_test.cc b/absl/strings/internal/resize_uninitialized_test.cc
index 0f8b3c2a..01ee476b 100644
--- a/absl/strings/internal/resize_uninitialized_test.cc
+++ b/absl/strings/internal/resize_uninitialized_test.cc
@@ -24,11 +24,13 @@ int resize_call_count = 0;
 // resize() method has been called.
 struct resizable_string {
   size_t size() const { return 0; }
+  size_t capacity() const { return 0; }
   char& operator[](size_t) {
     static char c = '\0';
     return c;
   }
   void resize(size_t) { resize_call_count += 1; }
+  void reserve(size_t) {}
 };
 
 int resize_default_init_call_count = 0;
@@ -37,12 +39,14 @@ int resize_default_init_call_count = 0;
 // resize() and __resize_default_init() methods have been called.
 struct resize_default_init_string {
   size_t size() const { return 0; }
+  size_t capacity() const { return 0; }
   char& operator[](size_t) {
     static char c = '\0';
     return c;
   }
   void resize(size_t) { resize_call_count += 1; }
   void __resize_default_init(size_t) { resize_default_init_call_count += 1; }
+  void reserve(size_t) {}
 };
 
 TEST(ResizeUninit, WithAndWithout) {
@@ -60,6 +64,9 @@ TEST(ResizeUninit, WithAndWithout) {
     absl::strings_internal::STLStringResizeUninitialized(&rs, 237);
     EXPECT_EQ(resize_call_count, 1);
     EXPECT_EQ(resize_default_init_call_count, 0);
+    absl::strings_internal::STLStringResizeUninitializedAmortized(&rs, 1000);
+    EXPECT_EQ(resize_call_count, 2);
+    EXPECT_EQ(resize_default_init_call_count, 0);
   }
 
   resize_call_count = 0;
@@ -76,7 +83,23 @@ TEST(ResizeUninit, WithAndWithout) {
     absl::strings_internal::STLStringResizeUninitialized(&rus, 237);
     EXPECT_EQ(resize_call_count, 0);
     EXPECT_EQ(resize_default_init_call_count, 1);
+    absl::strings_internal::STLStringResizeUninitializedAmortized(&rus, 1000);
+    EXPECT_EQ(resize_call_count, 0);
+    EXPECT_EQ(resize_default_init_call_count, 2);
+  }
+}
+
+TEST(ResizeUninit, Amortized) {
+  std::string str;
+  size_t prev_cap = str.capacity();
+  int cap_increase_count = 0;
+  for (int i = 0; i < 1000; ++i) {
+    absl::strings_internal::STLStringResizeUninitializedAmortized(&str, i);
+    size_t new_cap = str.capacity();
+    if (new_cap > prev_cap) ++cap_increase_count;
+    prev_cap = new_cap;
   }
+  EXPECT_LT(cap_increase_count, 50);
 }
 
 }  // namespace
diff --git a/absl/strings/str_cat.cc b/absl/strings/str_cat.cc
index dd5d25b0..f4a77493 100644
--- a/absl/strings/str_cat.cc
+++ b/absl/strings/str_cat.cc
@@ -174,7 +174,7 @@ void AppendPieces(std::string* dest,
     ASSERT_NO_OVERLAP(*dest, piece);
     total_size += piece.size();
   }
-  strings_internal::STLStringResizeUninitialized(dest, total_size);
+  strings_internal::STLStringResizeUninitializedAmortized(dest, total_size);
 
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -199,7 +199,7 @@ void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b) {
   ASSERT_NO_OVERLAP(*dest, a);
   ASSERT_NO_OVERLAP(*dest, b);
   std::string::size_type old_size = dest->size();
-  strings_internal::STLStringResizeUninitialized(
+  strings_internal::STLStringResizeUninitializedAmortized(
       dest, old_size + a.size() + b.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -214,7 +214,7 @@ void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b,
   ASSERT_NO_OVERLAP(*dest, b);
   ASSERT_NO_OVERLAP(*dest, c);
   std::string::size_type old_size = dest->size();
-  strings_internal::STLStringResizeUninitialized(
+  strings_internal::STLStringResizeUninitializedAmortized(
       dest, old_size + a.size() + b.size() + c.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -231,7 +231,7 @@ void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b,
   ASSERT_NO_OVERLAP(*dest, c);
   ASSERT_NO_OVERLAP(*dest, d);
   std::string::size_type old_size = dest->size();
-  strings_internal::STLStringResizeUninitialized(
+  strings_internal::STLStringResizeUninitializedAmortized(
       dest, old_size + a.size() + b.size() + c.size() + d.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
diff --git a/absl/time/internal/cctz/src/time_zone_format_test.cc b/absl/time/internal/cctz/src/time_zone_format_test.cc
index a11f93e2..294f2e22 100644
--- a/absl/time/internal/cctz/src/time_zone_format_test.cc
+++ b/absl/time/internal/cctz/src/time_zone_format_test.cc
@@ -1135,7 +1135,7 @@ TEST(Parse, ExtendedSeconds) {
   // All %E<prec>S cases are treated the same as %E*S on input.
   auto precisions = {"*", "0", "1",  "2",  "3",  "4",  "5",  "6", "7",
                      "8", "9", "10", "11", "12", "13", "14", "15"};
-  for (const std::string& prec : precisions) {
+  for (const std::string prec : precisions) {
     const std::string fmt = "%E" + prec + "S";
     SCOPED_TRACE(fmt);
     time_point<chrono::nanoseconds> tp = unix_epoch;
@@ -1217,7 +1217,7 @@ TEST(Parse, ExtendedSubeconds) {
   // All %E<prec>f cases are treated the same as %E*f on input.
   auto precisions = {"*", "0", "1",  "2",  "3",  "4",  "5",  "6", "7",
                      "8", "9", "10", "11", "12", "13", "14", "15"};
-  for (const std::string& prec : precisions) {
+  for (const std::string prec : precisions) {
     const std::string fmt = "%E" + prec + "f";
     SCOPED_TRACE(fmt);
     time_point<chrono::nanoseconds> tp = unix_epoch - chrono::seconds(1);