diff options
Diffstat (limited to 'absl/strings/internal')
| -rw-r--r-- | absl/strings/internal/cord_internal.h | 60 | ||||
| -rw-r--r-- | absl/strings/internal/cord_internal_test.cc | 116 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree.cc | 119 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree.h | 46 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_btree_test.cc | 129 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_concat.cc | 63 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_concat_test.cc | 143 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_crc.h | 9 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_ring.cc | 20 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info.cc | 9 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info_statistics_test.cc | 22 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_statistics.h | 1 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_update_tracker.h | 1 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_update_tracker_test.cc | 1 |
14 files changed, 551 insertions, 188 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 { diff --git a/absl/strings/internal/cord_internal_test.cc b/absl/strings/internal/cord_internal_test.cc deleted file mode 100644 index 0758dfef..00000000 --- a/absl/strings/internal/cord_internal_test.cc +++ /dev/null @@ -1,116 +0,0 @@ -// Copyright 2021 The Abseil Authors -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/strings/internal/cord_internal.h" - -#include "gmock/gmock.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -TEST(RefcountAndFlags, NormalRefcount) { - for (bool expect_high_refcount : {false, true}) { - SCOPED_TRACE(expect_high_refcount); - RefcountAndFlags refcount; - // count = 1 - - EXPECT_FALSE(refcount.HasCrc()); - EXPECT_TRUE(refcount.IsMutable()); - EXPECT_TRUE(refcount.IsOne()); - - refcount.Increment(); - // count = 2 - - EXPECT_FALSE(refcount.HasCrc()); - EXPECT_FALSE(refcount.IsMutable()); - EXPECT_FALSE(refcount.IsOne()); - - // Decrementing should return true, since a reference is outstanding. - if (expect_high_refcount) { - EXPECT_TRUE(refcount.DecrementExpectHighRefcount()); - } else { - EXPECT_TRUE(refcount.Decrement()); - } - // count = 1 - - EXPECT_FALSE(refcount.HasCrc()); - EXPECT_TRUE(refcount.IsMutable()); - EXPECT_TRUE(refcount.IsOne()); - - // One more decremnt will return false, as no references remain. - if (expect_high_refcount) { - EXPECT_FALSE(refcount.DecrementExpectHighRefcount()); - } else { - EXPECT_FALSE(refcount.Decrement()); - } - } -} - -TEST(RefcountAndFlags, CrcRefcount) { - for (bool expect_high_refcount : {false, true}) { - SCOPED_TRACE(expect_high_refcount); - RefcountAndFlags refcount(RefcountAndFlags::WithCrc{}); - // count = 1 - - // A CRC-carrying node is never mutable, but can be unshared - EXPECT_TRUE(refcount.HasCrc()); - EXPECT_FALSE(refcount.IsMutable()); - EXPECT_TRUE(refcount.IsOne()); - - refcount.Increment(); - // count = 2 - - EXPECT_TRUE(refcount.HasCrc()); - EXPECT_FALSE(refcount.IsMutable()); - EXPECT_FALSE(refcount.IsOne()); - - // Decrementing should return true, since a reference is outstanding. - if (expect_high_refcount) { - EXPECT_TRUE(refcount.DecrementExpectHighRefcount()); - } else { - EXPECT_TRUE(refcount.Decrement()); - } - // count = 1 - - EXPECT_TRUE(refcount.HasCrc()); - EXPECT_FALSE(refcount.IsMutable()); - EXPECT_TRUE(refcount.IsOne()); - - // One more decremnt will return false, as no references remain. - if (expect_high_refcount) { - EXPECT_FALSE(refcount.DecrementExpectHighRefcount()); - } else { - EXPECT_FALSE(refcount.Decrement()); - } - } -} - -TEST(RefcountAndFlags, ImmortalRefcount) { - RefcountAndFlags immortal_refcount(RefcountAndFlags::Immortal{}); - - for (int i = 0; i < 100; ++i) { - // An immortal refcount is never unshared, and decrementing never causes - // a collection. - EXPECT_FALSE(immortal_refcount.HasCrc()); - EXPECT_FALSE(immortal_refcount.IsMutable()); - EXPECT_FALSE(immortal_refcount.IsOne()); - EXPECT_TRUE(immortal_refcount.Decrement()); - EXPECT_TRUE(immortal_refcount.DecrementExpectHighRefcount()); - } -} - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/strings/internal/cord_rep_btree.cc b/absl/strings/internal/cord_rep_btree.cc index 4404f33a..7cefcc52 100644 --- a/absl/strings/internal/cord_rep_btree.cc +++ b/absl/strings/internal/cord_rep_btree.cc @@ -216,8 +216,8 @@ void DeleteLeafEdge(CordRep* rep) { // propagate node changes up the stack. template <EdgeType edge_type> struct StackOperations { - // Returns true if the node at 'depth' is mutable, i.e. has a refcount - // of one, carries no CRC, and all of its parent nodes have a refcount of one. + // Returns true if the node at 'depth' is not shared, i.e. has a refcount + // of one and all of its parent nodes have a refcount of one. inline bool owned(int depth) const { return depth < share_depth; } // Returns the node at 'depth'. @@ -228,11 +228,11 @@ struct StackOperations { inline CordRepBtree* BuildStack(CordRepBtree* tree, int depth) { assert(depth <= tree->height()); int current_depth = 0; - while (current_depth < depth && tree->refcount.IsMutable()) { + while (current_depth < depth && tree->refcount.IsOne()) { stack[current_depth++] = tree; tree = tree->Edge(edge_type)->btree(); } - share_depth = current_depth + (tree->refcount.IsMutable() ? 1 : 0); + share_depth = current_depth + (tree->refcount.IsOne() ? 1 : 0); while (current_depth < depth) { stack[current_depth++] = tree; tree = tree->Edge(edge_type)->btree(); @@ -241,17 +241,17 @@ struct StackOperations { } // Builds a stack with the invariant that all nodes are private owned / not - // shared and carry no CRC data. This is used in iterative updates where a - // previous propagation guaranteed all nodes have this property. + // shared. This is used in iterative updates where a previous propagation + // guaranteed all nodes are owned / private. inline void BuildOwnedStack(CordRepBtree* tree, int height) { assert(height <= CordRepBtree::kMaxHeight); int depth = 0; while (depth < height) { - assert(tree->refcount.IsMutable()); + assert(tree->refcount.IsOne()); stack[depth++] = tree; tree = tree->Edge(edge_type)->btree(); } - assert(tree->refcount.IsMutable()); + assert(tree->refcount.IsOne()); share_depth = depth + 1; } @@ -336,12 +336,12 @@ struct StackOperations { return Unwind</*propagate=*/true>(tree, depth, length, result); } - // `share_depth` contains the depth at which the nodes in the stack cannot - // be mutated. I.e., if the top most level is shared (i.e.: - // `!refcount.IsMutable()`), then `share_depth` is 0. If the 2nd node - // is shared (and implicitly all nodes below that) then `share_depth` is 1, - // etc. A `share_depth` greater than the depth of the stack indicates that - // none of the nodes in the stack are shared. + // `share_depth` contains the depth at which the nodes in the stack become + // shared. I.e., if the top most level is shared (i.e.: `!refcount.IsOne()`), + // then `share_depth` is 0. If the 2nd node is shared (and implicitly all + // nodes below that) then `share_depth` is 1, etc. A `share_depth` greater + // than the depth of the stack indicates that none of the nodes in the stack + // are shared. int share_depth; NodeStack stack; @@ -773,7 +773,7 @@ CopyResult CordRepBtree::CopyPrefix(size_t n, bool allow_folding) { CordRep* CordRepBtree::ExtractFront(CordRepBtree* tree) { CordRep* front = tree->Edge(tree->begin()); - if (tree->refcount.IsMutable()) { + if (tree->refcount.IsOne()) { Unref(tree->Edges(tree->begin() + 1, tree->end())); CordRepBtree::Delete(tree); } else { @@ -786,7 +786,7 @@ CordRep* CordRepBtree::ExtractFront(CordRepBtree* tree) { CordRepBtree* CordRepBtree::ConsumeBeginTo(CordRepBtree* tree, size_t end, size_t new_length) { assert(end <= tree->end()); - if (tree->refcount.IsMutable()) { + if (tree->refcount.IsOne()) { Unref(tree->Edges(end, tree->end())); tree->set_end(end); tree->length = new_length; @@ -813,13 +813,13 @@ CordRep* CordRepBtree::RemoveSuffix(CordRepBtree* tree, size_t n) { size_t length = len - n; int height = tree->height(); - bool is_mutable = tree->refcount.IsMutable(); + bool is_mutable = tree->refcount.IsOne(); // Extract all top nodes which are reduced to size = 1 Position pos = tree->IndexOfLength(length); while (pos.index == tree->begin()) { CordRep* edge = ExtractFront(tree); - is_mutable &= edge->refcount.IsMutable(); + is_mutable &= edge->refcount.IsOne(); if (height-- == 0) return ResizeEdge(edge, length, is_mutable); tree = edge->btree(); pos = tree->IndexOfLength(length); @@ -835,8 +835,8 @@ CordRep* CordRepBtree::RemoveSuffix(CordRepBtree* tree, size_t n) { length = pos.n; while (length != edge->length) { // ConsumeBeginTo guarantees `tree` is a clean, privately owned copy. - assert(tree->refcount.IsMutable()); - const bool edge_is_mutable = edge->refcount.IsMutable(); + assert(tree->refcount.IsOne()); + const bool edge_is_mutable = edge->refcount.IsOne(); if (height-- == 0) { tree->edges_[pos.index] = ResizeEdge(edge, length, edge_is_mutable); @@ -973,7 +973,7 @@ char CordRepBtree::GetCharacter(size_t offset) const { Span<char> CordRepBtree::GetAppendBufferSlow(size_t size) { // The inlined version in `GetAppendBuffer()` deals with all heights <= 3. assert(height() >= 4); - assert(refcount.IsMutable()); + assert(refcount.IsOne()); // Build a stack of nodes we may potentially need to update if we find a // non-shared FLAT with capacity at the leaf level. @@ -982,13 +982,13 @@ Span<char> CordRepBtree::GetAppendBufferSlow(size_t size) { CordRepBtree* stack[kMaxDepth]; for (int i = 0; i < depth; ++i) { node = node->Edge(kBack)->btree(); - if (!node->refcount.IsMutable()) return {}; + if (!node->refcount.IsOne()) return {}; stack[i] = node; } // Must be a privately owned, mutable flat. CordRep* const edge = node->Edge(kBack); - if (!edge->refcount.IsMutable() || edge->tag < FLAT) return {}; + if (!edge->refcount.IsOne() || edge->tag < FLAT) return {}; // Must have capacity. const size_t avail = edge->flat()->Capacity() - edge->length; @@ -1123,6 +1123,79 @@ CordRepBtree* CordRepBtree::Rebuild(CordRepBtree* tree) { return nullptr; } +CordRepBtree::ExtractResult CordRepBtree::ExtractAppendBuffer( + CordRepBtree* tree, size_t extra_capacity) { + int depth = 0; + NodeStack stack; + + // Set up default 'no success' result which is {tree, nullptr}. + ExtractResult result; + result.tree = tree; + result.extracted = nullptr; + + // Dive down the right side of the tree, making sure no edges are shared. + while (tree->height() > 0) { + if (!tree->refcount.IsOne()) return result; + stack[depth++] = tree; + tree = tree->Edge(kBack)->btree(); + } + if (!tree->refcount.IsOne()) return result; + + // Validate we ended on a non shared flat. + CordRep* rep = tree->Edge(kBack); + if (!(rep->IsFlat() && rep->refcount.IsOne())) return result; + + // Verify it has at least the requested extra capacity. + CordRepFlat* flat = rep->flat(); + const size_t length = flat->length; + const size_t avail = flat->Capacity() - flat->length; + if (extra_capacity > avail) return result; + + // Set the extracted flat in the result. + result.extracted = flat; + + // Cascading delete all nodes that become empty. + while (tree->size() == 1) { + CordRepBtree::Delete(tree); + if (--depth < 0) { + // We consumed the entire tree: return nullptr for new tree. + result.tree = nullptr; + return result; + } + rep = tree; + tree = stack[depth]; + } + + // Remove the edge or cascaded up parent node. + tree->set_end(tree->end() - 1); + tree->length -= length; + + // Adjust lengths up the tree. + while (depth > 0) { + tree = stack[--depth]; + tree->length -= length; + } + + // Remove unnecessary top nodes with size = 1. This may iterate all the way + // down to the leaf node in which case we simply return the remaining last + // edge in that node and the extracted flat. + while (tree->size() == 1) { + int height = tree->height(); + rep = tree->Edge(kBack); + Delete(tree); + if (height == 0) { + // We consumed the leaf: return the sole data edge as the new tree. + result.tree = rep; + return result; + } + tree = rep->btree(); + } + + // Done: return the (new) top level node and extracted flat. + result.tree = tree; + return result; +} + } // namespace cord_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/strings/internal/cord_rep_btree.h b/absl/strings/internal/cord_rep_btree.h index bb38f0c3..0b44509e 100644 --- a/absl/strings/internal/cord_rep_btree.h +++ b/absl/strings/internal/cord_rep_btree.h @@ -240,11 +240,41 @@ class CordRepBtree : public CordRep { // length of the flat node and involved tree nodes have been increased by // `span.length()`. The caller is responsible for immediately assigning values // to all uninitialized data reference by the returned span. - // Requires `this->refcount.IsMutable()`: this function forces the - // caller to do this fast path check on the top level node, as this is the - // most commonly shared node of a cord tree. + // Requires `this->refcount.IsOne()`: this function forces the caller to do + // this fast path check on the top level node, as this is the most commonly + // shared node of a cord tree. Span<char> GetAppendBuffer(size_t size); + // Extracts the right-most data edge from this tree iff: + // - the tree and all internal edges to the right-most node are not shared. + // - the right-most node is a FLAT node and not shared. + // - the right-most node has at least the desired extra capacity. + // + // Returns {tree, nullptr} if any of the above conditions are not met. + // This method effectively removes data from the tree. The intent of this + // method is to allow applications appending small string data to use + // pre-existing capacity, and add the modified rep back to the tree. + // + // Simplified such code would look similar to this: + // void MyTreeBuilder::Append(string_view data) { + // ExtractResult result = CordRepBtree::ExtractAppendBuffer(tree_, 1); + // if (CordRep* rep = result.extracted) { + // size_t available = rep->Capacity() - rep->length; + // size_t n = std::min(data.size(), n); + // memcpy(rep->Data(), data.data(), n); + // rep->length += n; + // data.remove_prefix(n); + // if (!result.tree->IsBtree()) { + // tree_ = CordRepBtree::Create(result.tree); + // } + // tree_ = CordRepBtree::Append(tree_, rep); + // } + // ... + // // Remaining edge in `result.tree`. + // } + static ExtractResult ExtractAppendBuffer(CordRepBtree* tree, + size_t extra_capacity = 1); + // Returns the `height` of the tree. The height of a tree is limited to // kMaxHeight. `height` is implemented as an `int` as in some places we // use negative (-1) values for 'data edges'. @@ -849,7 +879,7 @@ inline CordRepBtree* CordRepBtree::Create(CordRep* rep) { } inline Span<char> CordRepBtree::GetAppendBuffer(size_t size) { - assert(refcount.IsMutable()); + assert(refcount.IsOne()); CordRepBtree* tree = this; const int height = this->height(); CordRepBtree* n1 = tree; @@ -858,21 +888,21 @@ inline Span<char> CordRepBtree::GetAppendBuffer(size_t size) { switch (height) { case 3: tree = tree->Edge(kBack)->btree(); - if (!tree->refcount.IsMutable()) return {}; + if (!tree->refcount.IsOne()) return {}; n2 = tree; ABSL_FALLTHROUGH_INTENDED; case 2: tree = tree->Edge(kBack)->btree(); - if (!tree->refcount.IsMutable()) return {}; + if (!tree->refcount.IsOne()) return {}; n1 = tree; ABSL_FALLTHROUGH_INTENDED; case 1: tree = tree->Edge(kBack)->btree(); - if (!tree->refcount.IsMutable()) return {}; + if (!tree->refcount.IsOne()) return {}; ABSL_FALLTHROUGH_INTENDED; case 0: CordRep* edge = tree->Edge(kBack); - if (!edge->refcount.IsMutable()) return {}; + if (!edge->refcount.IsOne()) return {}; if (edge->tag < FLAT) return {}; size_t avail = edge->flat()->Capacity() - edge->length; if (avail == 0) return {}; diff --git a/absl/strings/internal/cord_rep_btree_test.cc b/absl/strings/internal/cord_rep_btree_test.cc index be9473d4..1d0c68b2 100644 --- a/absl/strings/internal/cord_rep_btree_test.cc +++ b/absl/strings/internal/cord_rep_btree_test.cc @@ -128,6 +128,16 @@ MATCHER_P2(IsSubstring, start, length, return true; } +MATCHER_P2(EqExtractResult, tree, rep, "Equals ExtractResult") { + if (arg.tree != tree || arg.extracted != rep) { + *result_listener << "Expected {" << static_cast<const void*>(tree) << ", " + << static_cast<const void*>(rep) << "}, got {" << arg.tree + << ", " << arg.extracted << "}"; + return false; + } + return true; +} + // DataConsumer is a simple helper class used by tests to 'consume' string // fragments from the provided input in forward or backward direction. class DataConsumer { @@ -1483,6 +1493,125 @@ TEST_P(CordRepBtreeTest, Rebuild) { } } +// Convenience helper for CordRepBtree::ExtractAppendBuffer +CordRepBtree::ExtractResult ExtractLast(CordRepBtree* input, size_t cap = 1) { + return CordRepBtree::ExtractAppendBuffer(input, cap); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferLeafSingleFlat) { + CordRep* flat = MakeFlat("Abc"); + CordRepBtree* leaf = CordRepBtree::Create(flat); + EXPECT_THAT(ExtractLast(leaf), EqExtractResult(nullptr, flat)); + CordRep::Unref(flat); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNodeSingleFlat) { + CordRep* flat = MakeFlat("Abc"); + CordRepBtree* leaf = CordRepBtree::Create(flat); + CordRepBtree* node = CordRepBtree::New(leaf); + EXPECT_THAT(ExtractLast(node), EqExtractResult(nullptr, flat)); + CordRep::Unref(flat); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferLeafTwoFlats) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3); + CordRepBtree* leaf = CreateTree(flats); + EXPECT_THAT(ExtractLast(leaf), EqExtractResult(flats[0], flats[1])); + CordRep::Unref(flats[0]); + CordRep::Unref(flats[1]); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNodeTwoFlats) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3); + CordRepBtree* leaf = CreateTree(flats); + CordRepBtree* node = CordRepBtree::New(leaf); + EXPECT_THAT(ExtractLast(node), EqExtractResult(flats[0], flats[1])); + CordRep::Unref(flats[0]); + CordRep::Unref(flats[1]); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNodeTwoFlatsInTwoLeafs) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3); + CordRepBtree* leaf1 = CordRepBtree::Create(flats[0]); + CordRepBtree* leaf2 = CordRepBtree::Create(flats[1]); + CordRepBtree* node = CordRepBtree::New(leaf1, leaf2); + EXPECT_THAT(ExtractLast(node), EqExtractResult(flats[0], flats[1])); + CordRep::Unref(flats[0]); + CordRep::Unref(flats[1]); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferLeafThreeFlats) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdefghi", 3); + CordRepBtree* leaf = CreateTree(flats); + EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, flats[2])); + CordRep::Unref(flats[2]); + CordRep::Unref(leaf); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNodeThreeFlatsRightNoFolding) { + CordRep* flat = MakeFlat("Abc"); + std::vector<CordRep*> flats = CreateFlatsFromString("defghi", 3); + CordRepBtree* leaf1 = CordRepBtree::Create(flat); + CordRepBtree* leaf2 = CreateTree(flats); + CordRepBtree* node = CordRepBtree::New(leaf1, leaf2); + EXPECT_THAT(ExtractLast(node), EqExtractResult(node, flats[1])); + EXPECT_THAT(node->Edges(), ElementsAre(leaf1, leaf2)); + EXPECT_THAT(leaf1->Edges(), ElementsAre(flat)); + EXPECT_THAT(leaf2->Edges(), ElementsAre(flats[0])); + CordRep::Unref(node); + CordRep::Unref(flats[1]); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNodeThreeFlatsRightLeafFolding) { + CordRep* flat = MakeFlat("Abc"); + std::vector<CordRep*> flats = CreateFlatsFromString("defghi", 3); + CordRepBtree* leaf1 = CreateTree(flats); + CordRepBtree* leaf2 = CordRepBtree::Create(flat); + CordRepBtree* node = CordRepBtree::New(leaf1, leaf2); + EXPECT_THAT(ExtractLast(node), EqExtractResult(leaf1, flat)); + EXPECT_THAT(leaf1->Edges(), ElementsAreArray(flats)); + CordRep::Unref(leaf1); + CordRep::Unref(flat); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNoCapacity) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3); + CordRepBtree* leaf = CreateTree(flats); + size_t avail = flats[1]->flat()->Capacity() - flats[1]->length; + EXPECT_THAT(ExtractLast(leaf, avail + 1), EqExtractResult(leaf, nullptr)); + EXPECT_THAT(ExtractLast(leaf, avail), EqExtractResult(flats[0], flats[1])); + CordRep::Unref(flats[0]); + CordRep::Unref(flats[1]); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferNotFlat) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3); + auto substr = MakeSubstring(1, 2, flats[1]); + CordRepBtree* leaf = CreateTree({flats[0], substr}); + EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, nullptr)); + CordRep::Unref(leaf); +} + +TEST(CordRepBtreeTest, ExtractAppendBufferShared) { + std::vector<CordRep*> flats = CreateFlatsFromString("abcdef", 3); + CordRepBtree* leaf = CreateTree(flats); + + CordRep::Ref(flats[1]); + EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, nullptr)); + CordRep::Unref(flats[1]); + + CordRep::Ref(leaf); + EXPECT_THAT(ExtractLast(leaf), EqExtractResult(leaf, nullptr)); + CordRep::Unref(leaf); + + CordRepBtree* node = CordRepBtree::New(leaf); + CordRep::Ref(node); + EXPECT_THAT(ExtractLast(node), EqExtractResult(node, nullptr)); + CordRep::Unref(node); + + CordRep::Unref(node); +} + } // namespace } // namespace cord_internal ABSL_NAMESPACE_END diff --git a/absl/strings/internal/cord_rep_concat.cc b/absl/strings/internal/cord_rep_concat.cc new file mode 100644 index 00000000..3457b55c --- /dev/null +++ b/absl/strings/internal/cord_rep_concat.cc @@ -0,0 +1,63 @@ +// Copyright 2021 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <cstdint> + +#include "absl/base/config.h" +#include "absl/container/inlined_vector.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_flat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +CordRepConcat::ExtractResult CordRepConcat::ExtractAppendBuffer( + CordRepConcat* tree, size_t extra_capacity) { + absl::InlinedVector<CordRepConcat*, kInlinedVectorSize> stack; + CordRepConcat* concat = tree; + CordRep* rep = concat->right; + + // Dive down the tree, making sure no edges are shared + while (concat->refcount.IsOne() && rep->IsConcat()) { + stack.push_back(concat); + concat = rep->concat(); + rep = concat->right; + } + // Validate we ended on a non shared flat. + if (concat->refcount.IsOne() && rep->IsFlat() && + rep->refcount.IsOne()) { + // Verify it has at least the requested extra capacity + CordRepFlat* flat = rep->flat(); + size_t remaining = flat->Capacity() - flat->length; + if (extra_capacity > remaining) return {tree, nullptr}; + + // Check if we have a parent to adjust, or if we must return the left node. + rep = concat->left; + if (!stack.empty()) { + stack.back()->right = rep; + for (CordRepConcat* parent : stack) { + parent->length -= flat->length; + } + rep = tree; + } + delete concat; + return {rep, flat}; + } + return {tree, nullptr}; +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_rep_concat_test.cc b/absl/strings/internal/cord_rep_concat_test.cc new file mode 100644 index 00000000..32bab975 --- /dev/null +++ b/absl/strings/internal/cord_rep_concat_test.cc @@ -0,0 +1,143 @@ +// Copyright 2021 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <cstdint> +#include <utility> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_test_util.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +using ::absl::cordrep_testing::MakeFlat; +using ::absl::cordrep_testing::MakeSubstring; +using ::testing::Eq; + +MATCHER_P2(EqExtractResult, tree, rep, "Equals ExtractResult") { + if (arg.tree != tree || arg.extracted != rep) { + *result_listener << "Expected {" << static_cast<const void*>(tree) << ", " + << static_cast<const void*>(rep) << "}, got {" << arg.tree + << ", " << arg.extracted << "}"; + return false; + } + return true; +} + +CordRepConcat* MakeConcat(CordRep* left, CordRep* right, int depth) { + CordRepConcat* concat = new CordRepConcat; + concat->tag = CONCAT; + concat->set_depth(depth); + concat->length = left->length + right->length; + concat->left = left; + concat->right = right; + return concat; +} + +CordRepConcat::ExtractResult ExtractLast(CordRepConcat* concat, + size_t extra_capacity = 1) { + return CordRepConcat::ExtractAppendBuffer(concat, extra_capacity); +} + +TEST(CordRepConcatTest, ExtractAppendBufferTwoFlats) { + CordRepFlat* flat1 = MakeFlat("abc"); + CordRepFlat* flat2 = MakeFlat("defg"); + CordRepConcat* concat = MakeConcat(flat1, flat2, 0); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(flat1, flat2)); + CordRep::Unref(flat1); + CordRep::Unref(flat2); +} + +TEST(CordRepConcatTest, ExtractAppendBufferThreeFlatsOne) { + CordRepFlat* flat1 = MakeFlat("abc"); + CordRepFlat* flat2 = MakeFlat("defg"); + CordRepFlat* flat3 = MakeFlat("hijkl"); + CordRepConcat* lconcat = MakeConcat(flat1, flat2, 0); + CordRepConcat* concat = MakeConcat(lconcat, flat3, 1); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(lconcat, flat3)); + ASSERT_THAT(lconcat->length, Eq(7)); + CordRep::Unref(lconcat); + CordRep::Unref(flat3); +} + +TEST(CordRepConcatTest, ExtractAppendBufferThreeFlatsTwo) { + CordRepFlat* flat1 = MakeFlat("hijkl"); + CordRepFlat* flat2 = MakeFlat("abc"); + CordRepFlat* flat3 = MakeFlat("defg"); + CordRepConcat* rconcat = MakeConcat(flat2, flat3, 0); + CordRepConcat* concat = MakeConcat(flat1, rconcat, 1); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(concat, flat3)); + ASSERT_THAT(concat->length, Eq(8)); + CordRep::Unref(concat); + CordRep::Unref(flat3); +} + +TEST(CordRepConcatTest, ExtractAppendBufferShared) { + CordRepFlat* flat1 = MakeFlat("hijkl"); + CordRepFlat* flat2 = MakeFlat("abc"); + CordRepFlat* flat3 = MakeFlat("defg"); + CordRepConcat* rconcat = MakeConcat(flat2, flat3, 0); + CordRepConcat* concat = MakeConcat(flat1, rconcat, 1); + + CordRep::Ref(concat); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(concat, nullptr)); + CordRep::Unref(concat); + + CordRep::Ref(rconcat); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(concat, nullptr)); + CordRep::Unref(rconcat); + + CordRep::Ref(flat3); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(concat, nullptr)); + CordRep::Unref(flat3); + + CordRep::Unref(concat); +} + +TEST(CordRepConcatTest, ExtractAppendBufferNotFlat) { + CordRepFlat* flat1 = MakeFlat("hijkl"); + CordRepFlat* flat2 = MakeFlat("abc"); + CordRepFlat* flat3 = MakeFlat("defg"); + auto substr = MakeSubstring(1, 2, flat3); + CordRepConcat* rconcat = MakeConcat(flat2, substr, 0); + CordRepConcat* concat = MakeConcat(flat1, rconcat, 1); + EXPECT_THAT(ExtractLast(concat), EqExtractResult(concat, nullptr)); + CordRep::Unref(concat); +} + +TEST(CordRepConcatTest, ExtractAppendBufferNoCapacity) { + CordRepFlat* flat1 = MakeFlat("hijkl"); + CordRepFlat* flat2 = MakeFlat("abc"); + CordRepFlat* flat3 = MakeFlat("defg"); + size_t avail = flat3->Capacity() - flat3->length; + CordRepConcat* rconcat = MakeConcat(flat2, flat3, 0); + CordRepConcat* concat = MakeConcat(flat1, rconcat, 1); + + // Should fail if 1 byte over, success if exactly matching + EXPECT_THAT(ExtractLast(concat, avail + 1), EqExtractResult(concat, nullptr)); + EXPECT_THAT(ExtractLast(concat, avail), EqExtractResult(concat, flat3)); + + CordRep::Unref(concat); + CordRep::Unref(flat3); +} + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_rep_crc.h b/absl/strings/internal/cord_rep_crc.h index 3ead94a1..5294b0d1 100644 --- a/absl/strings/internal/cord_rep_crc.h +++ b/absl/strings/internal/cord_rep_crc.h @@ -76,6 +76,15 @@ inline CordRep* SkipCrcNode(CordRep* rep) { } } +inline const CordRep* SkipCrcNode(const CordRep* rep) { + assert(rep != nullptr); + if (ABSL_PREDICT_FALSE(rep->IsCrc())) { + return rep->crc()->child; + } else { + return rep; + } +} + inline CordRepCrc* CordRep::crc() { assert(IsCrc()); return static_cast<CordRepCrc*>(this); diff --git a/absl/strings/internal/cord_rep_ring.cc b/absl/strings/internal/cord_rep_ring.cc index 07c77eb3..db1f63fa 100644 --- a/absl/strings/internal/cord_rep_ring.cc +++ b/absl/strings/internal/cord_rep_ring.cc @@ -277,7 +277,7 @@ CordRepRing* CordRepRing::Mutable(CordRepRing* rep, size_t extra) { // Get current number of entries, and check for max capacity. size_t entries = rep->entries(); - if (!rep->refcount.IsMutable()) { + if (!rep->refcount.IsOne()) { return Copy(rep, rep->head(), rep->tail(), extra); } else if (entries + extra > rep->capacity()) { const size_t min_grow = rep->capacity() + rep->capacity() / 2; @@ -292,10 +292,10 @@ CordRepRing* CordRepRing::Mutable(CordRepRing* rep, size_t extra) { } Span<char> CordRepRing::GetAppendBuffer(size_t size) { - assert(refcount.IsMutable()); + assert(refcount.IsOne()); index_type back = retreat(tail_); CordRep* child = entry_child(back); - if (child->tag >= FLAT && child->refcount.IsMutable()) { + if (child->tag >= FLAT && child->refcount.IsOne()) { size_t capacity = child->flat()->Capacity(); pos_type end_pos = entry_end_pos(back); size_t data_offset = entry_data_offset(back); @@ -312,10 +312,10 @@ Span<char> CordRepRing::GetAppendBuffer(size_t size) { } Span<char> CordRepRing::GetPrependBuffer(size_t size) { - assert(refcount.IsMutable()); + assert(refcount.IsOne()); CordRep* child = entry_child(head_); size_t data_offset = entry_data_offset(head_); - if (data_offset && child->refcount.IsMutable() && child->tag >= FLAT) { + if (data_offset && child->refcount.IsOne() && child->tag >= FLAT) { size_t n = (std::min)(data_offset, size); this->length += n; begin_pos_ -= n; @@ -504,7 +504,7 @@ CordRepRing* CordRepRing::Prepend(CordRepRing* rep, CordRep* child) { CordRepRing* CordRepRing::Append(CordRepRing* rep, absl::string_view data, size_t extra) { - if (rep->refcount.IsMutable()) { + if (rep->refcount.IsOne()) { Span<char> avail = rep->GetAppendBuffer(data.length()); if (!avail.empty()) { memcpy(avail.data(), data.data(), avail.length()); @@ -538,7 +538,7 @@ CordRepRing* CordRepRing::Append(CordRepRing* rep, absl::string_view data, CordRepRing* CordRepRing::Prepend(CordRepRing* rep, absl::string_view data, size_t extra) { - if (rep->refcount.IsMutable()) { + if (rep->refcount.IsOne()) { Span<char> avail = rep->GetPrependBuffer(data.length()); if (!avail.empty()) { const char* tail = data.data() + data.length() - avail.length(); @@ -678,7 +678,7 @@ CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset, Position tail = rep->FindTail(head.index, offset + len); const size_t new_entries = rep->entries(head.index, tail.index); - if (rep->refcount.IsMutable() && extra <= (rep->capacity() - new_entries)) { + if (rep->refcount.IsOne() && extra <= (rep->capacity() - new_entries)) { // We adopt a privately owned rep and no extra entries needed. if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); @@ -715,7 +715,7 @@ CordRepRing* CordRepRing::RemovePrefix(CordRepRing* rep, size_t len, } Position head = rep->Find(len); - if (rep->refcount.IsMutable()) { + if (rep->refcount.IsOne()) { if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); rep->head_ = head.index; } else { @@ -745,7 +745,7 @@ CordRepRing* CordRepRing::RemoveSuffix(CordRepRing* rep, size_t len, } Position tail = rep->FindTail(rep->length - len); - if (rep->refcount.IsMutable()) { + if (rep->refcount.IsOne()) { // We adopt a privately owned rep, scrub. if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); rep->tail_ = tail.index; diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc index 5c18bbc5..4d52a802 100644 --- a/absl/strings/internal/cordz_info.cc +++ b/absl/strings/internal/cordz_info.cc @@ -20,6 +20,7 @@ #include "absl/debugging/stacktrace.h" #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.h" +#include "absl/strings/internal/cord_rep_crc.h" #include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cordz_handle.h" #include "absl/strings/internal/cordz_statistics.h" @@ -81,6 +82,14 @@ class CordRepAnalyzer { size_t refcount = rep->refcount.Get(); RepRef repref{rep, (refcount > 1) ? refcount - 1 : 1}; + // Process the top level CRC node, if present. + if (repref.rep->tag == CRC) { + statistics_.node_count++; + statistics_.node_counts.crc++; + memory_usage_.Add(sizeof(CordRepCrc), repref.refcount); + repref = repref.Child(repref.rep->crc()->child); + } + // Process all top level linear nodes (substrings and flats). repref = CountLinearReps(repref, memory_usage_); diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc index 7430d281..5277c3c1 100644 --- a/absl/strings/internal/cordz_info_statistics_test.cc +++ b/absl/strings/internal/cordz_info_statistics_test.cc @@ -22,6 +22,7 @@ #include "absl/strings/cord.h" #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.h" +#include "absl/strings/internal/cord_rep_crc.h" #include "absl/strings/internal/cord_rep_flat.h" #include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cordz_info.h" @@ -535,6 +536,27 @@ TEST(CordzInfoStatisticsTest, BtreeNodeShared) { EXPECT_THAT(SampleCord(tree), EqStatistics(expected)); } +TEST(CordzInfoStatisticsTest, Crc) { + RefHelper ref; + auto* left = Flat(1000); + auto* right = Flat(1000); + auto* concat = Concat(left, right); + auto* crc = ref.NeedsUnref(CordRepCrc::New(concat, 12345)); + + CordzStatistics expected; + expected.size = concat->length; + expected.estimated_memory_usage = + SizeOf(crc) + SizeOf(concat) + SizeOf(left) + SizeOf(right); + expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage; + expected.node_count = 4; + expected.node_counts.flat = 2; + expected.node_counts.flat_1k = 2; + expected.node_counts.concat = 1; + expected.node_counts.crc = 1; + + EXPECT_THAT(SampleCord(crc), EqStatistics(expected)); +} + TEST(CordzInfoStatisticsTest, ThreadSafety) { Notification stop; static constexpr int kNumThreads = 8; diff --git a/absl/strings/internal/cordz_statistics.h b/absl/strings/internal/cordz_statistics.h index da4c7dbb..57071905 100644 --- a/absl/strings/internal/cordz_statistics.h +++ b/absl/strings/internal/cordz_statistics.h @@ -41,6 +41,7 @@ struct CordzStatistics { size_t concat = 0; // #concat reps size_t ring = 0; // #ring buffer reps size_t btree = 0; // #btree reps + size_t crc = 0; // #crc reps }; // The size of the cord in bytes. This matches the result of Cord::size(). diff --git a/absl/strings/internal/cordz_update_tracker.h b/absl/strings/internal/cordz_update_tracker.h index 1f764486..7a41c180 100644 --- a/absl/strings/internal/cordz_update_tracker.h +++ b/absl/strings/internal/cordz_update_tracker.h @@ -60,6 +60,7 @@ class CordzUpdateTracker { kPrependString, kRemovePrefix, kRemoveSuffix, + kSetExpectedChecksum, kSubCord, // kNumMethods defines the number of entries: must be the last entry. diff --git a/absl/strings/internal/cordz_update_tracker_test.cc b/absl/strings/internal/cordz_update_tracker_test.cc index 2348a175..8eda529e 100644 --- a/absl/strings/internal/cordz_update_tracker_test.cc +++ b/absl/strings/internal/cordz_update_tracker_test.cc @@ -58,6 +58,7 @@ Methods AllMethods() { Method::kPrependString, Method::kRemovePrefix, Method::kRemoveSuffix, + Method::kSetExpectedChecksum, Method::kSubCord}; } |