summaryrefslogtreecommitdiff
path: root/absl/strings
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings')
-rw-r--r--absl/strings/BUILD.bazel1
-rw-r--r--absl/strings/CMakeLists.txt1
-rw-r--r--absl/strings/cord.cc472
-rw-r--r--absl/strings/cord.h1
-rw-r--r--absl/strings/cord_analysis.cc41
-rw-r--r--absl/strings/internal/cord_internal.cc42
-rw-r--r--absl/strings/internal/cord_internal.h30
-rw-r--r--absl/strings/internal/cord_rep_concat.cc63
-rw-r--r--absl/strings/internal/cord_rep_consume.cc81
-rw-r--r--absl/strings/internal/cord_rep_flat.h8
-rw-r--r--absl/strings/internal/cord_rep_test_util.h3
-rw-r--r--absl/strings/internal/cordz_info.cc38
-rw-r--r--absl/strings/internal/cordz_info_statistics_test.cc4
13 files changed, 45 insertions, 740 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 617577cd..129affec 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -271,7 +271,6 @@ cc_library(
"internal/cord_rep_btree.cc",
"internal/cord_rep_btree_navigator.cc",
"internal/cord_rep_btree_reader.cc",
- "internal/cord_rep_concat.cc",
"internal/cord_rep_consume.cc",
"internal/cord_rep_crc.cc",
"internal/cord_rep_ring.cc",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index e73a1ea0..f31eef4d 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -568,7 +568,6 @@ absl_cc_library(
"internal/cord_rep_btree.cc"
"internal/cord_rep_btree_navigator.cc"
"internal/cord_rep_btree_reader.cc"
- "internal/cord_rep_concat.cc"
"internal/cord_rep_crc.cc"
"internal/cord_rep_consume.cc"
"internal/cord_rep_ring.cc"
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 59722107..4ee722da 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -53,7 +53,6 @@ ABSL_NAMESPACE_BEGIN
using ::absl::cord_internal::CordRep;
using ::absl::cord_internal::CordRepBtree;
-using ::absl::cord_internal::CordRepConcat;
using ::absl::cord_internal::CordRepCrc;
using ::absl::cord_internal::CordRepExternal;
using ::absl::cord_internal::CordRepFlat;
@@ -66,53 +65,6 @@ using ::absl::cord_internal::kMinFlatLength;
using ::absl::cord_internal::kInlinedVectorSize;
using ::absl::cord_internal::kMaxBytesToCopy;
-constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) {
- return n == 0 ? a : Fibonacci(n - 1, b, a + b);
-}
-
-static_assert(Fibonacci(63) == 6557470319842,
- "Fibonacci values computed incorrectly");
-
-// Minimum length required for a given depth tree -- a tree is considered
-// balanced if
-// length(t) >= min_length[depth(t)]
-// The root node depth is allowed to become twice as large to reduce rebalancing
-// for larger strings (see IsRootBalanced).
-static constexpr uint64_t min_length[] = {
- Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5),
- Fibonacci(6), Fibonacci(7), Fibonacci(8), Fibonacci(9),
- Fibonacci(10), Fibonacci(11), Fibonacci(12), Fibonacci(13),
- Fibonacci(14), Fibonacci(15), Fibonacci(16), Fibonacci(17),
- Fibonacci(18), Fibonacci(19), Fibonacci(20), Fibonacci(21),
- Fibonacci(22), Fibonacci(23), Fibonacci(24), Fibonacci(25),
- Fibonacci(26), Fibonacci(27), Fibonacci(28), Fibonacci(29),
- Fibonacci(30), Fibonacci(31), Fibonacci(32), Fibonacci(33),
- Fibonacci(34), Fibonacci(35), Fibonacci(36), Fibonacci(37),
- Fibonacci(38), Fibonacci(39), Fibonacci(40), Fibonacci(41),
- Fibonacci(42), Fibonacci(43), Fibonacci(44), Fibonacci(45),
- Fibonacci(46), Fibonacci(47),
- 0xffffffffffffffffull, // Avoid overflow
-};
-
-static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length);
-
-static inline constexpr bool btree_enabled() { return true; }
-
-static inline bool IsRootBalanced(CordRep* node) {
- if (!node->IsConcat()) {
- return true;
- } else if (node->concat()->depth() <= 15) {
- return true;
- } else if (node->concat()->depth() > kMinLengthSize) {
- return false;
- } else {
- // Allow depth to become twice as large as implied by fibonacci rule to
- // reduce rebalancing for larger strings.
- return (node->length >= min_length[node->concat()->depth() / 2]);
- }
-}
-
-static CordRep* Rebalance(CordRep* node);
static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
int indent = 0);
static bool VerifyNode(CordRep* root, CordRep* start_node,
@@ -134,24 +86,6 @@ static inline CordRep* VerifyTree(CordRep* node) {
return node;
}
-// Return the depth of a node
-static int Depth(const CordRep* rep) {
- if (rep->IsConcat()) {
- return rep->concat()->depth();
- } else {
- return 0;
- }
-}
-
-static void SetConcatChildren(CordRepConcat* concat, CordRep* left,
- CordRep* right) {
- concat->left = left;
- concat->right = right;
-
- concat->length = left->length + right->length;
- concat->set_depth(1 + std::max(Depth(left), Depth(right)));
-}
-
// Create a concatenation of the specified nodes.
// Does not change the refcounts of "left" and "right".
// The returned node has a refcount of 1.
@@ -167,42 +101,15 @@ static CordRep* RawConcat(CordRep* left, CordRep* right) {
CordRep::Unref(right);
return left;
}
-
- CordRepConcat* rep = new CordRepConcat();
- rep->tag = cord_internal::CONCAT;
- SetConcatChildren(rep, left, right);
-
- return rep;
+ ABSL_INTERNAL_LOG(FATAL, "CordRepConcat is no longer supported");
+ return nullptr;
}
static CordRep* Concat(CordRep* left, CordRep* right) {
CordRep* rep = RawConcat(left, right);
- if (rep != nullptr && !IsRootBalanced(rep)) {
- rep = Rebalance(rep);
- }
return VerifyTree(rep);
}
-// Make a balanced tree out of an array of leaf nodes.
-static CordRep* MakeBalancedTree(CordRep** reps, size_t n) {
- // Make repeated passes over the array, merging adjacent pairs
- // until we are left with just a single node.
- while (n > 1) {
- size_t dst = 0;
- for (size_t src = 0; src < n; src += 2) {
- if (src + 1 < n) {
- reps[dst] = Concat(reps[src], reps[src + 1]);
- } else {
- reps[dst] = reps[src];
- }
- dst++;
- }
- n = dst;
- }
-
- return reps[0];
-}
-
static CordRepFlat* CreateFlat(const char* data, size_t length,
size_t alloc_hint) {
CordRepFlat* flat = CordRepFlat::New(length + alloc_hint);
@@ -228,21 +135,7 @@ static CordRep* NewBtree(const char* data, size_t length, size_t alloc_hint) {
// The returned node has a refcount of 1.
static CordRep* NewTree(const char* data, size_t length, size_t alloc_hint) {
if (length == 0) return nullptr;
- if (btree_enabled()) {
- return NewBtree(data, length, alloc_hint);
- }
- absl::FixedArray<CordRep*> reps((length - 1) / kMaxFlatLength + 1);
- size_t n = 0;
- do {
- const size_t len = std::min(length, kMaxFlatLength);
- CordRepFlat* rep = CordRepFlat::New(len + alloc_hint);
- rep->length = len;
- memcpy(rep->Data(), data, len);
- reps[n++] = VerifyTree(rep);
- data += len;
- length -= len;
- } while (length != 0);
- return MakeBalancedTree(reps.data(), n);
+ return NewBtree(data, length, alloc_hint);
}
namespace cord_internal {
@@ -350,11 +243,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
assert(!is_tree());
if (!data_.is_empty()) {
CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
- if (btree_enabled()) {
- tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
- } else {
- tree = Concat(flat, tree);
- }
+ tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
}
EmplaceTree(tree, method);
}
@@ -362,11 +251,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
void Cord::InlineRep::AppendTreeToTree(CordRep* tree, MethodIdentifier method) {
assert(is_tree());
const CordzUpdateScope scope(data_.cordz_info(), method);
- if (btree_enabled()) {
- tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
- } else {
- tree = Concat(cord_internal::RemoveCrcNode(data_.as_tree()), tree);
- }
+ tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
SetTree(tree, scope);
}
@@ -386,11 +271,7 @@ void Cord::InlineRep::PrependTreeToInlined(CordRep* tree,
assert(!is_tree());
if (!data_.is_empty()) {
CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
- if (btree_enabled()) {
- tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
- } else {
- tree = Concat(tree, flat);
- }
+ tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
}
EmplaceTree(tree, method);
}
@@ -399,11 +280,7 @@ void Cord::InlineRep::PrependTreeToTree(CordRep* tree,
MethodIdentifier method) {
assert(is_tree());
const CordzUpdateScope scope(data_.cordz_info(), method);
- if (btree_enabled()) {
- tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
- } else {
- tree = Concat(tree, cord_internal::RemoveCrcNode(data_.as_tree()));
- }
+ tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
SetTree(tree, scope);
}
@@ -433,12 +310,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
}
}
- // Search down the right-hand path for a non-full FLAT node.
CordRep* dst = root;
- while (dst->IsConcat() && dst->refcount.IsOne()) {
- dst = dst->concat()->right;
- }
-
if (!dst->IsFlat() || !dst->refcount.IsOne()) {
*region = nullptr;
*size = 0;
@@ -453,12 +325,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
return false;
}
- size_t size_increase = std::min(capacity - in_use, max_length);
-
- // We need to update the length fields for all nodes, including the leaf node.
- for (CordRep* rep = root; rep != dst; rep = rep->concat()->right) {
- rep->length += size_increase;
- }
+ const size_t size_increase = std::min(capacity - in_use, max_length);
dst->length += size_increase;
*region = dst->flat()->Data() + in_use;
@@ -627,27 +494,11 @@ void Cord::InlineRep::AppendArray(absl::string_view src,
return;
}
- if (btree_enabled()) {
- // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
- rep = ForceBtree(rep);
- const size_t min_growth = std::max<size_t>(rep->length / 10, src.size());
- rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size());
- } else {
- // Use new block(s) for any remaining bytes that were not handled above.
- // Alloc extra memory only if the right child of the root of the new tree
- // is going to be a FLAT node, which will permit further inplace appends.
- size_t length = src.size();
- if (src.size() < kMaxFlatLength) {
- // The new length is either
- // - old size + 10%
- // - old_size + src.size()
- // This will cause a reasonable conservative step-up in size that is
- // still large enough to avoid excessive amounts of small fragments
- // being added.
- length = std::max<size_t>(rep->length / 10, src.size());
- }
- rep = Concat(rep, NewTree(src.data(), src.size(), length - src.size()));
- }
+ // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
+ rep = ForceBtree(rep);
+ const size_t min_growth = std::max<size_t>(rep->length / 10, src.size());
+ rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size());
+
CommitTree(root, rep, scope, method);
}
@@ -779,18 +630,6 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
absl::InlinedVector<CordRep*, kInlinedVectorSize> rhs_stack;
assert(!node->IsCrc());
- while (node->IsConcat()) {
- assert(n <= node->length);
- if (n < node->concat()->left->length) {
- // Push right to stack, descend left.
- rhs_stack.push_back(node->concat()->right);
- node = node->concat()->left;
- } else {
- // Drop left, descend right.
- n -= node->concat()->left->length;
- node = node->concat()->right;
- }
- }
assert(n <= node->length);
if (n == 0) {
@@ -822,19 +661,6 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
bool inplace_ok = node->refcount.IsOne();
assert(!node->IsCrc());
- while (node->IsConcat()) {
- assert(n <= node->length);
- if (n < node->concat()->right->length) {
- // Push left to stack, descend right.
- lhs_stack.push_back(node->concat()->left);
- node = node->concat()->right;
- } else {
- // Drop right, descend left.
- n -= node->concat()->right->length;
- node = node->concat()->left;
- }
- inplace_ok = inplace_ok && node->refcount.IsOne();
- }
assert(n <= node->length);
if (n == 0) {
@@ -936,22 +762,12 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
results.push_back(Concat(left, right));
} else if (pos == 0 && n == node->length) {
results.push_back(CordRep::Ref(node));
- } else if (!node->IsConcat()) {
+ } else {
if (node->IsSubstring()) {
pos += node->substring()->start;
node = node->substring()->child;
}
results.push_back(NewSubstring(CordRep::Ref(node), pos, n));
- } else if (pos + n <= node->concat()->left->length) {
- todo.push_back(SubRange(node->concat()->left, pos, n));
- } else if (pos >= node->concat()->left->length) {
- pos -= node->concat()->left->length;
- todo.push_back(SubRange(node->concat()->right, pos, n));
- } else {
- size_t left_n = node->concat()->left->length - pos;
- todo.push_back(SubRange(nullptr, 0, 0)); // Concat()
- todo.push_back(SubRange(node->concat()->right, 0, n - left_n));
- todo.push_back(SubRange(node->concat()->left, pos, left_n));
}
} while (!todo.empty());
assert(results.size() == 1);
@@ -999,147 +815,6 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
}
// --------------------------------------------------------------------
-// Balancing
-
-class CordForest {
- public:
- explicit CordForest(size_t length)
- : root_length_(length), trees_(kMinLengthSize, nullptr) {}
-
- void Build(CordRep* cord_root) {
- std::vector<CordRep*> pending = {cord_root};
- assert(cord_root->IsConcat());
-
- while (!pending.empty()) {
- CordRep* node = pending.back();
- pending.pop_back();
- CheckNode(node);
- if (ABSL_PREDICT_FALSE(!node->IsConcat())) {
- AddNode(node);
- continue;
- }
-
- CordRepConcat* concat_node = node->concat();
- if (concat_node->depth() >= kMinLengthSize ||
- concat_node->length < min_length[concat_node->depth()]) {
- pending.push_back(concat_node->right);
- pending.push_back(concat_node->left);
-
- if (concat_node->refcount.IsOne()) {
- concat_node->left = concat_freelist_;
- concat_freelist_ = concat_node;
- } else {
- CordRep::Ref(concat_node->right);
- CordRep::Ref(concat_node->left);
- CordRep::Unref(concat_node);
- }
- } else {
- AddNode(node);
- }
- }
- }
-
- CordRep* ConcatNodes() {
- CordRep* sum = nullptr;
- for (auto* node : trees_) {
- if (node == nullptr) continue;
-
- sum = PrependNode(node, sum);
- root_length_ -= node->length;
- if (root_length_ == 0) break;
- }
- ABSL_INTERNAL_CHECK(sum != nullptr, "Failed to locate sum node");
- return VerifyTree(sum);
- }
-
- private:
- CordRep* AppendNode(CordRep* node, CordRep* sum) {
- return (sum == nullptr) ? node : MakeConcat(sum, node);
- }
-
- CordRep* PrependNode(CordRep* node, CordRep* sum) {
- return (sum == nullptr) ? node : MakeConcat(node, sum);
- }
-
- void AddNode(CordRep* node) {
- CordRep* sum = nullptr;
-
- // Collect together everything with which we will merge with node
- int i = 0;
- for (; node->length > min_length[i + 1]; ++i) {
- auto& tree_at_i = trees_[i];
-
- if (tree_at_i == nullptr) continue;
- sum = PrependNode(tree_at_i, sum);
- tree_at_i = nullptr;
- }
-
- sum = AppendNode(node, sum);
-
- // Insert sum into appropriate place in the forest
- for (; sum->length >= min_length[i]; ++i) {
- auto& tree_at_i = trees_[i];
- if (tree_at_i == nullptr) continue;
-
- sum = MakeConcat(tree_at_i, sum);
- tree_at_i = nullptr;
- }
-
- // min_length[0] == 1, which means sum->length >= min_length[0]
- assert(i > 0);
- trees_[i - 1] = sum;
- }
-
- // Make concat node trying to resue existing CordRepConcat nodes we
- // already collected in the concat_freelist_.
- CordRep* MakeConcat(CordRep* left, CordRep* right) {
- if (concat_freelist_ == nullptr) return RawConcat(left, right);
-
- CordRepConcat* rep = concat_freelist_;
- if (concat_freelist_->left == nullptr) {
- concat_freelist_ = nullptr;
- } else {
- concat_freelist_ = concat_freelist_->left->concat();
- }
- SetConcatChildren(rep, left, right);
-
- return rep;
- }
-
- static void CheckNode(CordRep* node) {
- ABSL_INTERNAL_CHECK(node->length != 0u, "");
- if (node->IsConcat()) {
- ABSL_INTERNAL_CHECK(node->concat()->left != nullptr, "");
- ABSL_INTERNAL_CHECK(node->concat()->right != nullptr, "");
- ABSL_INTERNAL_CHECK(node->length == (node->concat()->left->length +
- node->concat()->right->length),
- "");
- }
- }
-
- size_t root_length_;
-
- // use an inlined vector instead of a flat array to get bounds checking
- absl::InlinedVector<CordRep*, kInlinedVectorSize> trees_;
-
- // List of concat nodes we can re-use for Cord balancing.
- CordRepConcat* concat_freelist_ = nullptr;
-};
-
-static CordRep* Rebalance(CordRep* node) {
- VerifyTree(node);
- assert(node->IsConcat());
-
- if (node->length == 0) {
- return nullptr;
- }
-
- CordForest forest(node->length);
- forest.Build(node);
- return forest.ConcatNodes();
-}
-
-// --------------------------------------------------------------------
// Comparators
namespace {
@@ -1203,11 +878,6 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
return tree->Data(tree->begin());
}
- // Walk down the left branches until we hit a non-CONCAT node.
- while (node->IsConcat()) {
- node = node->concat()->left;
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1436,13 +1106,6 @@ Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() {
CordRep* node = stack_of_right_children.back();
stack_of_right_children.pop_back();
- // Walk down the left branches until we hit a non-CONCAT node. Save the
- // right children to the stack for subsequent traversal.
- while (node->IsConcat()) {
- stack_of_right_children.push_back(node->concat()->right);
- node = node->concat()->left;
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1557,22 +1220,6 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
return subcord;
}
- // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
- // right children to the stack for subsequent traversal.
- while (node->IsConcat()) {
- if (node->concat()->left->length > n) {
- // Push right, descend left.
- stack_of_right_children.push_back(node->concat()->right);
- node = node->concat()->left;
- } else {
- // Read left, descend right.
- subnode = Concat(subnode, CordRep::Ref(node->concat()->left));
- n -= node->concat()->left->length;
- bytes_remaining_ -= node->concat()->left->length;
- node = node->concat()->right;
- }
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1630,21 +1277,6 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
return;
}
- // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
- // right children to the stack for subsequent traversal.
- while (node->IsConcat()) {
- if (node->concat()->left->length > n) {
- // Push right, descend left.
- stack_of_right_children.push_back(node->concat()->right);
- node = node->concat()->left;
- } else {
- // Skip left, descend right.
- n -= node->concat()->left->length;
- bytes_remaining_ -= node->concat()->left->length;
- node = node->concat()->right;
- }
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1681,16 +1313,6 @@ char Cord::operator[](size_t i) const {
} else if (rep->IsExternal()) {
// Get the "i"th character from the external array.
return rep->external()->base[offset];
- } else if (rep->IsConcat()) {
- // Recursively branch to the side of the concatenation that the "i"th
- // character is on.
- size_t left_length = rep->concat()->left->length;
- if (offset < left_length) {
- rep = rep->concat()->left;
- } else {
- offset -= left_length;
- rep = rep->concat()->right;
- }
} else {
// This must be a substring a node, so bypass it to get to the child.
assert(rep->IsSubstring());
@@ -1772,43 +1394,13 @@ absl::string_view Cord::FlattenSlowPath() {
return;
}
- int stack_pos = 0;
- constexpr int stack_max = 128;
- // Stack of right branches for tree traversal
- absl::cord_internal::CordRep* stack[stack_max];
+ // This is a leaf node, so invoke our callback.
absl::cord_internal::CordRep* current_node = cord_internal::SkipCrcNode(rep);
- while (true) {
- if (current_node->IsConcat()) {
- if (stack_pos == stack_max) {
- // There's no more room on our stack array to add another right branch,
- // and the idea is to avoid allocations, so call this function
- // recursively to navigate this subtree further. (This is not something
- // we expect to happen in practice).
- ForEachChunkAux(current_node, callback);
-
- // Pop the next right branch and iterate.
- current_node = stack[--stack_pos];
- continue;
- } else {
- // Save the right branch for later traversal and continue down the left
- // branch.
- stack[stack_pos++] = current_node->concat()->right;
- current_node = current_node->concat()->left;
- continue;
- }
- }
- // This is a leaf node, so invoke our callback.
- absl::string_view chunk;
- bool success = GetFlatAux(current_node, &chunk);
- assert(success);
- if (success) {
- callback(chunk);
- }
- if (stack_pos == 0) {
- // end of traversal
- return;
- }
- current_node = stack[--stack_pos];
+ absl::string_view chunk;
+ bool success = GetFlatAux(current_node, &chunk);
+ assert(success);
+ if (success) {
+ callback(chunk);
}
}
@@ -1823,18 +1415,11 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
*os << " [";
if (include_data) *os << static_cast<void*>(rep);
*os << "]";
- *os << " " << (IsRootBalanced(rep) ? 'b' : 'u');
*os << " " << std::setw(indent) << "";
if (rep->IsCrc()) {
*os << "CRC crc=" << rep->crc()->crc << "\n";
indent += kIndentStep;
rep = rep->crc()->child;
- } else if (rep->IsConcat()) {
- *os << "CONCAT depth=" << Depth(rep) << "\n";
- indent += kIndentStep;
- indents.push_back(indent);
- stack.push_back(rep->concat()->right);
- rep = rep->concat()->left;
} else if (rep->IsSubstring()) {
*os << "SUBSTRING @ " << rep->substring()->start << "\n";
indent += kIndentStep;
@@ -1871,7 +1456,7 @@ static std::string ReportError(CordRep* root, CordRep* node) {
}
static bool VerifyNode(CordRep* root, CordRep* start_node,
- bool full_validation) {
+ bool /* full_validation */) {
absl::InlinedVector<CordRep*, 2> worklist;
worklist.push_back(start_node);
do {
@@ -1884,19 +1469,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
ABSL_INTERNAL_CHECK(!node->IsCrc(), ReportError(root, node));
}
- if (node->IsConcat()) {
- ABSL_INTERNAL_CHECK(node->concat()->left != nullptr,
- ReportError(root, node));
- ABSL_INTERNAL_CHECK(node->concat()->right != nullptr,
- ReportError(root, node));
- ABSL_INTERNAL_CHECK((node->length == node->concat()->left->length +
- node->concat()->right->length),
- ReportError(root, node));
- if (full_validation) {
- worklist.push_back(node->concat()->right);
- worklist.push_back(node->concat()->left);
- }
- } else if (node->IsFlat()) {
+ if (node->IsFlat()) {
ABSL_INTERNAL_CHECK(node->length <= node->flat()->Capacity(),
ReportError(root, node));
} else if (node->IsExternal()) {
@@ -1937,7 +1510,6 @@ uint8_t CordTestAccess::LengthToTag(size_t s) {
ABSL_INTERNAL_CHECK(s <= kMaxFlatLength, absl::StrCat("Invalid length ", s));
return cord_internal::AllocatedSizeToTag(s + cord_internal::kFlatOverhead);
}
-size_t CordTestAccess::SizeofCordRepConcat() { return sizeof(CordRepConcat); }
size_t CordTestAccess::SizeofCordRepExternal() {
return sizeof(CordRepExternal);
}
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 49d51da2..7f34ef48 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -1553,7 +1553,6 @@ class CordTestAccess {
public:
static size_t FlatOverhead();
static size_t MaxFlatLength();
- static size_t SizeofCordRepConcat();
static size_t SizeofCordRepExternal();
static size_t SizeofCordRepSubstring();
static size_t FlatTagToLength(uint8_t tag);
diff --git a/absl/strings/cord_analysis.cc b/absl/strings/cord_analysis.cc
index c0d9ea79..3fa15b01 100644
--- a/absl/strings/cord_analysis.cc
+++ b/absl/strings/cord_analysis.cc
@@ -128,45 +128,6 @@ void AnalyzeDataEdge(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
raw_usage.Add(size, rep);
}
-// Computes the memory size of the provided Concat tree.
-template <Mode mode>
-void AnalyzeConcat(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
- absl::InlinedVector<CordRepRef<mode>, 47> pending;
-
- while (rep.rep != nullptr) {
- const CordRepConcat* concat = rep.rep->concat();
- CordRepRef<mode> left = rep.Child(concat->left);
- CordRepRef<mode> right = rep.Child(concat->right);
-
- raw_usage.Add(sizeof(CordRepConcat), rep);
-
- switch ((IsDataEdge(left.rep) ? 1 : 0) | (IsDataEdge(right.rep) ? 2 : 0)) {
- case 0: // neither left or right are data edges
- rep = left;
- pending.push_back(right);
- break;
- case 1: // only left is a data edge
- AnalyzeDataEdge(left, raw_usage);
- rep = right;
- break;
- case 2: // only right is a data edge
- AnalyzeDataEdge(right, raw_usage);
- rep = left;
- break;
- case 3: // left and right are data edges
- AnalyzeDataEdge(right, raw_usage);
- AnalyzeDataEdge(left, raw_usage);
- if (!pending.empty()) {
- rep = pending.back();
- pending.pop_back();
- } else {
- rep.rep = nullptr;
- }
- break;
- }
- }
-}
-
// Computes the memory size of the provided Ring tree.
template <Mode mode>
void AnalyzeRing(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
@@ -211,8 +172,6 @@ size_t GetEstimatedUsage(const CordRep* rep) {
AnalyzeDataEdge(repref, raw_usage);
} else if (repref.rep->tag == BTREE) {
AnalyzeBtree(repref, raw_usage);
- } else if (repref.rep->IsConcat()) {
- AnalyzeConcat(repref, raw_usage);
} else if (repref.rep->tag == RING) {
AnalyzeRing(repref, raw_usage);
} else {
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 75544191..06119350 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -36,53 +36,31 @@ ABSL_CONST_INIT std::atomic<bool> cord_btree_exhaustive_validation(false);
void CordRep::Destroy(CordRep* rep) {
assert(rep != nullptr);
- absl::InlinedVector<CordRep*, Constants::kInlinedVectorSize> pending;
while (true) {
assert(!rep->refcount.IsImmortal());
- if (rep->IsConcat()) {
- CordRepConcat* rep_concat = rep->concat();
- CordRep* right = rep_concat->right;
- if (!right->refcount.Decrement()) {
- pending.push_back(right);
- }
- CordRep* left = rep_concat->left;
- delete rep_concat;
- rep = nullptr;
- if (!left->refcount.Decrement()) {
- rep = left;
- continue;
- }
- } else if (rep->tag == BTREE) {
+ if (rep->tag == BTREE) {
CordRepBtree::Destroy(rep->btree());
- rep = nullptr;
+ return;
} else if (rep->tag == RING) {
CordRepRing::Destroy(rep->ring());
- rep = nullptr;
+ return;
} else if (rep->tag == EXTERNAL) {
CordRepExternal::Delete(rep);
- rep = nullptr;
+ return;
} else if (rep->tag == SUBSTRING) {
CordRepSubstring* rep_substring = rep->substring();
- CordRep* child = rep_substring->child;
+ rep = rep_substring->child;
delete rep_substring;
- rep = nullptr;
- if (!child->refcount.Decrement()) {
- rep = child;
- continue;
+ if (rep->refcount.Decrement()) {
+ return;
}
} else if (rep->tag == CRC) {
CordRepCrc::Destroy(rep->crc());
- rep = nullptr;
+ return;
} else {
+ assert(rep->IsFlat());
CordRepFlat::Delete(rep);
- rep = nullptr;
- }
-
- if (!pending.empty()) {
- rep = pending.back();
- pending.pop_back();
- } else {
- break;
+ return;
}
}
}
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index b9ecbba6..8db6aa6d 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -171,7 +171,7 @@ class CordRepBtree;
// Various representations that we allow
enum CordRepKind {
- CONCAT = 0,
+ UNUSED_0 = 0,
SUBSTRING = 1,
CRC = 2,
BTREE = 3,
@@ -239,7 +239,6 @@ struct CordRep {
// Returns true if this instance's tag matches the requested type.
constexpr bool IsRing() const { return tag == RING; }
- constexpr bool IsConcat() const { return tag == CONCAT; }
constexpr bool IsSubstring() const { return tag == SUBSTRING; }
constexpr bool IsCrc() const { return tag == CRC; }
constexpr bool IsExternal() const { return tag == EXTERNAL; }
@@ -248,8 +247,6 @@ struct CordRep {
inline CordRepRing* ring();
inline const CordRepRing* ring() const;
- inline CordRepConcat* concat();
- inline const CordRepConcat* concat() const;
inline CordRepSubstring* substring();
inline const CordRepSubstring* substring() const;
inline CordRepCrc* crc();
@@ -276,21 +273,6 @@ struct CordRep {
static inline void Unref(CordRep* rep);
};
-struct CordRepConcat : public CordRep {
- CordRep* left;
- CordRep* right;
-
- 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 {
size_t start; // Starting offset of substring in child
CordRep* child;
@@ -569,16 +551,6 @@ class InlineData {
static_assert(sizeof(InlineData) == kMaxInline + 1, "");
-inline CordRepConcat* CordRep::concat() {
- assert(IsConcat());
- return static_cast<CordRepConcat*>(this);
-}
-
-inline const CordRepConcat* CordRep::concat() const {
- assert(IsConcat());
- return static_cast<const CordRepConcat*>(this);
-}
-
inline CordRepSubstring* CordRep::substring() {
assert(IsSubstring());
return static_cast<CordRepSubstring*>(this);
diff --git a/absl/strings/internal/cord_rep_concat.cc b/absl/strings/internal/cord_rep_concat.cc
deleted file mode 100644
index 3457b55c..00000000
--- a/absl/strings/internal/cord_rep_concat.cc
+++ /dev/null
@@ -1,63 +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 <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_consume.cc b/absl/strings/internal/cord_rep_consume.cc
index 253339be..20a55797 100644
--- a/absl/strings/internal/cord_rep_consume.cc
+++ b/absl/strings/internal/cord_rep_consume.cc
@@ -40,88 +40,21 @@ CordRep* ClipSubstring(CordRepSubstring* substring) {
return child;
}
-// Unrefs the provided `concat`, and returns `{concat->left, concat->right}`
-// Adds or assumes a reference on `concat->left` and `concat->right`.
-// Returns an array of 2 elements containing the left and right nodes.
-std::array<CordRep*, 2> ClipConcat(CordRepConcat* concat) {
- std::array<CordRep*, 2> result{concat->left, concat->right};
- if (concat->refcount.IsOne()) {
- delete concat;
- } else {
- CordRep::Ref(result[0]);
- CordRep::Ref(result[1]);
- CordRep::Unref(concat);
- }
- return result;
-}
+} // namespace
-void Consume(bool forward, CordRep* rep, ConsumeFn consume_fn) {
+void Consume(CordRep* rep, ConsumeFn consume_fn) {
size_t offset = 0;
size_t length = rep->length;
- struct Entry {
- CordRep* rep;
- size_t offset;
- size_t length;
- };
- absl::InlinedVector<Entry, 40> stack;
-
- for (;;) {
- if (rep->IsConcat()) {
- std::array<CordRep*, 2> res = ClipConcat(rep->concat());
- CordRep* left = res[0];
- CordRep* right = res[1];
-
- if (left->length <= offset) {
- // Don't need left node
- offset -= left->length;
- CordRep::Unref(left);
- rep = right;
- continue;
- }
- size_t length_left = left->length - offset;
- if (length_left >= length) {
- // Don't need right node
- CordRep::Unref(right);
- rep = left;
- continue;
- }
-
- // Need both nodes
- size_t length_right = length - length_left;
- if (forward) {
- stack.push_back({right, 0, length_right});
- rep = left;
- length = length_left;
- } else {
- stack.push_back({left, offset, length_left});
- rep = right;
- offset = 0;
- length = length_right;
- }
- } else if (rep->tag == SUBSTRING) {
- offset += rep->substring()->start;
- rep = ClipSubstring(rep->substring());
- } else {
- consume_fn(rep, offset, length);
- if (stack.empty()) return;
-
- rep = stack.back().rep;
- offset = stack.back().offset;
- length = stack.back().length;
- stack.pop_back();
- }
+ if (rep->tag == SUBSTRING) {
+ offset += rep->substring()->start;
+ rep = ClipSubstring(rep->substring());
}
-}
-
-} // namespace
-
-void Consume(CordRep* rep, ConsumeFn consume_fn) {
- return Consume(true, rep, std::move(consume_fn));
+ consume_fn(rep, offset, length);
}
void ReverseConsume(CordRep* rep, ConsumeFn consume_fn) {
- return Consume(false, rep, std::move(consume_fn));
+ return Consume(rep, std::move(consume_fn));
}
} // namespace cord_internal
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h
index ae8b3a2a..e3e27fcd 100644
--- a/absl/strings/internal/cord_rep_flat.h
+++ b/absl/strings/internal/cord_rep_flat.h
@@ -73,9 +73,11 @@ static_assert(AllocatedSizeToTagUnchecked(kMinFlatSize) == FLAT, "");
static_assert(AllocatedSizeToTagUnchecked(kMaxLargeFlatSize) == MAX_FLAT_TAG,
"");
-// Helper functions for rounded div, and rounding to exact sizes.
-constexpr size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; }
-constexpr size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; }
+// RoundUp logically performs `((n + m - 1) / m) * m` to round up to the nearest
+// multiple of `m`, optimized for the invariant that `m` is a power of 2.
+constexpr size_t RoundUp(size_t n, size_t m) {
+ return (n + m - 1) & (0 - m);
+}
// Returns the size to the nearest equal or larger value that can be
// expressed exactly as a tag value.
diff --git a/absl/strings/internal/cord_rep_test_util.h b/absl/strings/internal/cord_rep_test_util.h
index 692d7db5..18a0a195 100644
--- a/absl/strings/internal/cord_rep_test_util.h
+++ b/absl/strings/internal/cord_rep_test_util.h
@@ -114,9 +114,6 @@ inline void CordVisitReps(cord_internal::CordRep* rep, Fn&& fn) {
for (cord_internal::CordRep* edge : rep->btree()->Edges()) {
CordVisitReps(edge, fn);
}
- } else if (rep->IsConcat()) {
- CordVisitReps(rep->concat()->left, fn);
- CordVisitReps(rep->concat()->right, fn);
}
}
diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc
index 24605260..c891d0ed 100644
--- a/absl/strings/internal/cordz_info.cc
+++ b/absl/strings/internal/cordz_info.cc
@@ -98,8 +98,6 @@ class CordRepAnalyzer {
AnalyzeRing(repref);
} else if (repref.rep->tag == BTREE) {
AnalyzeBtree(repref);
- } else if (repref.rep->IsConcat()) {
- AnalyzeConcat(repref);
} else {
// We should have either a concat, btree, or ring node if not null.
assert(false);
@@ -141,14 +139,6 @@ class CordRepAnalyzer {
}
};
- // Returns `rr` if `rr.rep` is not null and a CONCAT type.
- // Asserts that `rr.rep` is a concat node or null.
- static RepRef AssertConcat(RepRef repref) {
- const CordRep* rep = repref.rep;
- assert(rep == nullptr || rep->IsConcat());
- return (rep != nullptr && rep->IsConcat()) ? repref : RepRef{nullptr, 0};
- }
-
// Counts a flat of the provide allocated size
void CountFlat(size_t size) {
statistics_.node_count++;
@@ -201,34 +191,6 @@ class CordRepAnalyzer {
return rep;
}
- // Analyzes the provided concat node in a flattened recursive way.
- void AnalyzeConcat(RepRef rep) {
- absl::InlinedVector<RepRef, 47> pending;
-
- while (rep.rep != nullptr) {
- const CordRepConcat* concat = rep.rep->concat();
- RepRef left = rep.Child(concat->left);
- RepRef right = rep.Child(concat->right);
-
- statistics_.node_count++;
- statistics_.node_counts.concat++;
- memory_usage_.Add(sizeof(CordRepConcat), rep.refcount);
-
- right = AssertConcat(CountLinearReps(right, memory_usage_));
- rep = AssertConcat(CountLinearReps(left, memory_usage_));
- if (rep.rep != nullptr) {
- if (right.rep != nullptr) {
- pending.push_back(right);
- }
- } else if (right.rep != nullptr) {
- rep = right;
- } else if (!pending.empty()) {
- rep = pending.back();
- pending.pop_back();
- }
- }
- }
-
// Analyzes the provided ring.
void AnalyzeRing(RepRef rep) {
statistics_.node_count++;
diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc
index 40f93dd3..476c38d2 100644
--- a/absl/strings/internal/cordz_info_statistics_test.cc
+++ b/absl/strings/internal/cordz_info_statistics_test.cc
@@ -148,10 +148,6 @@ double FairShareImpl(CordRep* rep, size_t ref) {
rep->ring()->ForEach([&](CordRepRing::index_type i) {
self += FairShareImpl(rep->ring()->entry_child(i), 1);
});
- } else if (rep->IsConcat()) {
- self = SizeOf(rep->concat());
- children = FairShareImpl(rep->concat()->left, ref) +
- FairShareImpl(rep->concat()->right, ref);
} else {
assert(false);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-07 11:46:40 +0000