Export of internal Abseil changes

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

Add common [container.requirements] type definitions to `CharRange` and `ChunkRange`

The presence of these allow these range classes to be used in various utility functions which require some minimum type of container. For example, this change allows tests to use `EXPECT_THAT(cord.Chunks(), ElementsAre(...))`

PiperOrigin-RevId: 406941278

--
0c195f073632e21d9a4bce158047b2ba8551c2d1 by Evan Brown <ezb@google.com>:

Use explicit exponential growth in SubstituteAndAppendArray.

PiperOrigin-RevId: 406931952

--
afb043bccd809a55cab78abadb7548a057d9eda0 by Jorg Brown <jorg@google.com>:

Use longer var names in macro to avoid clang-tidy warning

PiperOrigin-RevId: 406930978

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

Add future kAppendBuffer and kPrependBuffer API trackers for Cordz sampling

PiperOrigin-RevId: 406912759

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

Implement Prepend(string_view) in terms of PrependArray(string_view, MethodIdentifier).

PiperOrigin-RevId: 406891665

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

Add 'Rebuild' logic to CordRepBtree

There are btree hostile scenarios where an application could perform repeated split/insert/merge operations on a cord leading to a tree exceeding the maximum height. While this should be rare in practice, this change adds a Rebuild() method that will rebuild a tree with a 100% fill factor, and we will invoke this rebuild when a tree exceeds the maximum height. This basically follows the similar 'balance' logic in Concat trees (although the latter is common in Concat uses)

PiperOrigin-RevId: 406875739

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

Add 'in place' enabled RemoveSuffix

An in-place RemoveSuffix is more efficient than SubTree() as it can directly modify privately owned nodes and flats allowing easy re-use of free capacity in right-most flats that may turn into Substring edges when using SubTree.

PiperOrigin-RevId: 406431230

--
f09903c0a3d7344f59aaf1380a16ea10829217d4 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 406430373

--
9957af575c33bb18dc170572a4ee8cc5901df6b2 by Greg Falcon <gfalcon@google.com>:

Initial groundwork to allow storing checksum data inside CordRep instances.

This uses a RefcountAndFlags bit that was reserved for this purpose, and will be leveraged in a follow-up change to allow attaching checksums to a Cord's value.

This change splits RefcountAndFlags::IsOne() into two distinct operations:

* IsOne(): This returns true when the associated CordRep is not shared with other threads.  This is useful for functions that consume CordRep instances; for example, code that consumes an unshared CordRep can assume ownership of its children without modifying those refcounts.

* IsMutable(): This returns true when the associated CordRep reference is not shared with other threads, *and* does not store an associated checksum value.  This is useful for functions that modify a CordRep's contents: code may modify the bytes of a mutable-unshared CordRep without fear of races with other threads, or of invalidating a stored checksum.

The tricky part of this CL is ensuring that the correct choice between IsMutable() and IsOne() was made at each point.  An incorrect application of IsOne() could lead to correctness bugs in the future.  Code conditioned on IsOne() may delete the CordRep in question, or assume ownership of its children, but must not modify the CordRep's data without explicitly adjusting the CRC.

PiperOrigin-RevId: 406191103

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

Reduce the size in the LargeString test when running with Sanitizers

PiperOrigin-RevId: 406186945

--
735b4490bdb695c35731f06ce4b8de14ce2be6ed by Alex Strelnikov <strel@google.com>:

Release absl::SimpleHexAtoi.

PiperOrigin-RevId: 406143188
GitOrigin-RevId: f49e405201d2ffd5955503fa8ad0f08ec0cdfb2b
Change-Id: Ic6527ac40fa03ea02ca813e8bb7868a219544de4

1 files changed, 31 insertions, 10 deletions

diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index 0300ac40..bfe5564e 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -87,6 +87,9 @@ class RefcountAndFlags {
   constexpr RefcountAndFlags() : count_{kRefIncrement} {}
   struct Immortal {};
   explicit constexpr RefcountAndFlags(Immortal) : count_(kImmortalFlag) {}
+  struct WithCrc {};
+  explicit constexpr RefcountAndFlags(WithCrc)
+      : count_(kCrcFlag | kRefIncrement) {}
 
   // Increments the reference count. Imposes no memory ordering.
   inline void Increment() {
@@ -122,14 +125,32 @@ class RefcountAndFlags {
     return count_.load(std::memory_order_acquire) >> kNumFlags;
   }
 
-  // Returns whether the atomic integer is 1.
-  // If the reference count is used in the conventional way, a
-  // reference count of 1 implies that the current thread owns the
-  // reference and no other thread shares it.
-  // This call performs the test for a reference count of one, and
-  // performs the memory barrier needed for the owning thread
-  // to act on the object, knowing that it has exclusive access to the
-  // object.  Always returns false when the immortal bit is set.
+  // Returns true if the referenced object carries a CRC value.
+  bool HasCrc() const {
+    return (count_.load(std::memory_order_relaxed) & kCrcFlag) != 0;
+  }
+
+  // Returns true iff the atomic integer is 1 and this node does not store
+  // a CRC.  When both these conditions are met, the current thread owns
+  // the reference and no other thread shares it, so its contents may be
+  // safely mutated.
+  //
+  // If the referenced item is shared, carries a CRC, or is immortal,
+  // it should not be modified in-place, and this function returns false.
+  //
+  // This call performs the memory barrier needed for the owning thread
+  // to act on the object, so that if it returns true, it may safely
+  // assume exclusive access to the object.
+  inline bool IsMutable() {
+    return (count_.load(std::memory_order_acquire)) == kRefIncrement;
+  }
+
+  // Returns whether the atomic integer is 1.  Similar to IsMutable(),
+  // but does not check for a stored CRC.  (An unshared node with a CRC is not
+  // mutable, because changing its data would invalidate the CRC.)
+  //
+  // When this returns true, there are no other references, and data sinks
+  // may safely adopt the children of the CordRep.
   inline bool IsOne() {
     return (count_.load(std::memory_order_acquire) & kRefcountMask) ==
            kRefIncrement;
@@ -149,14 +170,14 @@ class RefcountAndFlags {
     kNumFlags = 2,
 
     kImmortalFlag = 0x1,
-    kReservedFlag = 0x2,
+    kCrcFlag = 0x2,
     kRefIncrement = (1 << kNumFlags),
 
     // Bitmask to use when checking refcount by equality.  This masks out
     // all flags except kImmortalFlag, which is part of the refcount for
     // purposes of equality.  (A refcount of 0 or 1 does not count as 0 or 1
     // if the immortal bit is set.)
-    kRefcountMask = ~kReservedFlag,
+    kRefcountMask = ~kCrcFlag,
   };
 
   std::atomic<int32_t> count_;