summaryrefslogtreecommitdiff
path: root/absl/strings/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings/internal')
-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
8 files changed, 23 insertions, 246 deletions
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-08-07 10:58:43 +0000