Export of internal Abseil changes

--
83e4cdf03a4d702b30e69204060de09e462e23c6 by Greg Falcon <gfalcon@google.com>:

Revert the crc addition to RefcountAndFlags, and restore related comments to their original state.

In development, the implementation of SetExpectedCrc() changed, and there is no longer a need to track the CRC status in the refcount.

Since the distinction between IsOne() and IsMutable() is subtle *and unused*, removing it now can help avoid subtle bugs in the future.  This distinction can always be added back later, if it proves necessary.

Keep the reserved bit for now; all it costs is one extra mask instruction in the refcount checks, and space for extra state in Cord is always hard to find.

PiperOrigin-RevId: 408647038

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

Implement Cord::SetExpectedChecksum() and Cord::ExpectedChecksum().

SetExpectedChecksum() will store a uint32_t out-of-band alongside a Cord's data.  This value persists through copies and assignments.  Mutating operations on a Cord cause the value to be forgotten.  ExpectedChecksum() retrieves the stored value, if present.

This API is intended for storing a CRC32C checksum alongside data, allowing checksums to be passed through dataflows and validated at the final step.  However, this API is agnostic to the meaning of the stored value.  No CRC32C validation is performed by these new APIs.

This implementation adds a new CordRep node, CordRepCrc.  A CordRepCrc may (currently) only live at the top of a tree.  This allows traversal logic to be agnostic to these nodes, instead putting the needed branches at the mutation level.    This also implements the property requested from API review, that any mutation is guaranteed to permanently forget the stored CRC.

PiperOrigin-RevId: 408611221

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

Move 'ExtractResult' into CordRep

The result of an extract operation is logically identical for any tree implementation, and having a single type makes 'tree independent' implementation in cord.cc more concise.

PiperOrigin-RevId: 408332408

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

Replace usages of `assert` macros with `ABSL_HARDENING_ASSERT`.

PiperOrigin-RevId: 408272133

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

Add CordRepBtree::ExtractAppendBuffer

PiperOrigin-RevId: 407944179

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

Add CordRepConcat::ExtractAppendBuffer

PiperOrigin-RevId: 407932968

--
9f520ba1600a93352c78f644a369c7c76195ee86 by Greg Falcon <gfalcon@google.com>:

Add cordz tracking for crc nodes.

This also adds a new kSetExpectedChecksum method to the list of tracked methods.  This is presently unused but will be used soon.

PiperOrigin-RevId: 407884120
GitOrigin-RevId: 83e4cdf03a4d702b30e69204060de09e462e23c6
Change-Id: I134ace2d87215813eaa60a282996a33884676c06

1 files changed, 29 insertions, 31 deletions

diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index bf135ae2..672bf178 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -87,9 +87,6 @@ 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() {
@@ -125,32 +122,14 @@ class RefcountAndFlags {
     return count_.load(std::memory_order_acquire) >> kNumFlags;
   }
 
-  // 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.
+  // 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.
   inline bool IsOne() {
     return (count_.load(std::memory_order_acquire) & kRefcountMask) ==
            kRefIncrement;
@@ -170,14 +149,14 @@ class RefcountAndFlags {
     kNumFlags = 2,
 
     kImmortalFlag = 0x1,
-    kCrcFlag = 0x2,
+    kReservedFlag = 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 = ~kCrcFlag,
+    kRefcountMask = ~kReservedFlag,
   };
 
   std::atomic<int32_t> count_;
@@ -227,6 +206,18 @@ static_assert(EXTERNAL == RING + 1, "BTREE and EXTERNAL not consecutive");
 static_assert(FLAT == EXTERNAL + 1, "EXTERNAL and FLAT not consecutive");
 
 struct CordRep {
+  // Result from an `extract edge` operation. Contains the (possibly changed)
+  // tree node as well as the extracted edge, or {tree, nullptr} if no edge
+  // could be extracted.
+  // On success, the returned `tree` value is null if `extracted` was the only
+  // data edge inside the tree, a data edge if there were only two data edges in
+  // the tree, or the (possibly new / smaller) remaining tree with the extracted
+  // data edge removed.
+  struct ExtractResult {
+    CordRep* tree;
+    CordRep* extracted;
+  };
+
   CordRep() = default;
   constexpr CordRep(RefcountAndFlags::Immortal immortal, size_t l)
       : length(l), refcount(immortal), tag(EXTERNAL), storage{} {}
@@ -294,6 +285,13 @@ struct CordRepConcat : public CordRep {
 
   uint8_t depth() const { return storage[0]; }
   void set_depth(uint8_t depth) { storage[0] = depth; }
+
+  // Extracts the right-most flat in the provided concat tree if the entire path
+  // to that flat is not shared, and the flat has the requested extra capacity.
+  // Returns the (potentially new) top level tree node and the extracted flat,
+  // or {tree, nullptr} if no flat was extracted.
+  static ExtractResult ExtractAppendBuffer(CordRepConcat* tree,
+                                           size_t extra_capacity);
 };
 
 struct CordRepSubstring : public CordRep {