summaryrefslogtreecommitdiff
path: root/absl/strings/cord.cc
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings/cord.cc')
-rw-r--r--absl/strings/cord.cc295
1 files changed, 130 insertions, 165 deletions
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 768106d4..15d17337 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -210,7 +210,7 @@ static CordRep* MakeBalancedTree(CordRep** reps, size_t n) {
}
static CordRepFlat* CreateFlat(const char* data, size_t length,
- size_t alloc_hint) {
+ size_t alloc_hint) {
CordRepFlat* flat = CordRepFlat::New(length + alloc_hint);
flat->length = length;
memcpy(flat->Data(), data, length);
@@ -234,9 +234,7 @@ static CordRep* RingNewTree(const char* data, size_t length,
// Create a new tree out of the specified array.
// The returned node has a refcount of 1.
-static CordRep* NewTree(const char* data,
- size_t length,
- size_t alloc_hint) {
+static CordRep* NewTree(const char* data, size_t length, size_t alloc_hint) {
if (length == 0) return nullptr;
if (cord_ring_enabled()) {
return RingNewTree(data, length, alloc_hint);
@@ -303,24 +301,6 @@ inline char* Cord::InlineRep::set_data(size_t n) {
return data_.as_chars();
}
-static inline CordRepFlat* MakeFlat(const InlineData& data, size_t extra = 0) {
- static_assert(kMinFlatLength >= sizeof(data), "");
- size_t len = data.inline_size();
- CordRepFlat* result = CordRepFlat::New(len + extra);
- result->length = len;
- memcpy(result->Data(), data.as_chars(), sizeof(data));
- return result;
-}
-
-inline CordRep* Cord::InlineRep::force_tree(size_t extra_hint) {
- if (data_.is_tree()) {
- return data_.as_tree();
- }
- CordRepFlat* result = MakeFlat(data_, extra_hint);
- set_tree(result);
- return result;
-}
-
inline void Cord::InlineRep::reduce_size(size_t n) {
size_t tag = inline_size();
assert(tag <= kMaxInline);
@@ -346,7 +326,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
MethodIdentifier method) {
assert(!is_tree());
if (!data_.is_empty()) {
- CordRepFlat* flat = MakeFlat(data_);
+ CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
if (cord_ring_enabled()) {
tree = CordRepRing::Append(CordRepRing::Create(flat, 1), tree);
} else {
@@ -376,14 +356,38 @@ void Cord::InlineRep::AppendTree(CordRep* tree, MethodIdentifier method) {
}
}
-void Cord::InlineRep::PrependTree(CordRep* tree) {
+void Cord::InlineRep::PrependTreeToInlined(CordRep* tree,
+ MethodIdentifier method) {
+ assert(!is_tree());
+ if (!data_.is_empty()) {
+ CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
+ if (cord_ring_enabled()) {
+ tree = CordRepRing::Prepend(CordRepRing::Create(flat, 1), tree);
+ } else {
+ tree = Concat(tree, flat);
+ }
+ }
+ EmplaceTree(tree, method);
+}
+
+void Cord::InlineRep::PrependTreeToTree(CordRep* tree,
+ MethodIdentifier method) {
+ assert(is_tree());
+ const CordzUpdateScope scope(data_.cordz_info(), method);
+ if (cord_ring_enabled()) {
+ tree = CordRepRing::Prepend(ForceRing(data_.as_tree(), 1), tree);
+ } else {
+ tree = Concat(tree, data_.as_tree());
+ }
+ SetTree(tree, scope);
+}
+
+void Cord::InlineRep::PrependTree(CordRep* tree, MethodIdentifier method) {
assert(tree != nullptr);
- if (data_.is_empty()) {
- set_tree(tree);
- } else if (cord_ring_enabled()) {
- set_tree(CordRepRing::Prepend(ForceRing(force_tree(0), 1), tree));
+ if (data_.is_tree()) {
+ PrependTreeToTree(tree, method);
} else {
- set_tree(Concat(tree, force_tree(0)));
+ PrependTreeToInlined(tree, method);
}
}
@@ -435,78 +439,43 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
return true;
}
+template <bool has_length>
void Cord::InlineRep::GetAppendRegion(char** region, size_t* size,
- size_t max_length) {
- if (max_length == 0) {
- *region = nullptr;
- *size = 0;
- return;
- }
-
- // Try to fit in the inline buffer if possible.
- if (!is_tree()) {
- size_t inline_length = inline_size();
- if (max_length <= kMaxInline - inline_length) {
- *region = data_.as_chars() + inline_length;
- *size = max_length;
- set_inline_size(inline_length + max_length);
+ size_t length) {
+ auto constexpr method = CordzUpdateTracker::kGetAppendRegion;
+
+ CordRep* root = tree();
+ size_t sz = root ? root->length : inline_size();
+ if (root == nullptr) {
+ size_t available = kMaxInline - sz;
+ if (available >= (has_length ? length : 1)) {
+ *region = data_.as_chars() + sz;
+ *size = has_length ? length : available;
+ set_inline_size(has_length ? sz + length : kMaxInline);
return;
}
}
- CordRep* root = force_tree(max_length);
-
- if (PrepareAppendRegion(root, region, size, max_length)) {
- UpdateCordzStatistics();
+ size_t extra = has_length ? length : (std::max)(sz, kMinFlatLength);
+ CordRep* rep = root ? root : MakeFlatWithExtraCapacity(extra);
+ CordzUpdateScope scope(root ? data_.cordz_info() : nullptr, method);
+ if (PrepareAppendRegion(rep, region, size, length)) {
+ CommitTree(root, rep, scope, method);
return;
}
// Allocate new node.
- CordRepFlat* new_node =
- CordRepFlat::New(std::max(static_cast<size_t>(root->length), max_length));
- new_node->length = std::min(new_node->Capacity(), max_length);
+ CordRepFlat* new_node = CordRepFlat::New(extra);
+ new_node->length = std::min(new_node->Capacity(), length);
*region = new_node->Data();
*size = new_node->length;
if (cord_ring_enabled()) {
- replace_tree(CordRepRing::Append(ForceRing(root, 1), new_node));
- return;
- }
- replace_tree(Concat(root, new_node));
-}
-
-void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) {
- const size_t max_length = std::numeric_limits<size_t>::max();
-
- // Try to fit in the inline buffer if possible.
- if (!data_.is_tree()) {
- size_t inline_length = inline_size();
- if (inline_length < kMaxInline) {
- *region = data_.as_chars() + inline_length;
- *size = kMaxInline - inline_length;
- set_inline_size(kMaxInline);
- return;
- }
- }
-
- CordRep* root = force_tree(max_length);
-
- if (PrepareAppendRegion(root, region, size, max_length)) {
- UpdateCordzStatistics();
- return;
- }
-
- // Allocate new node.
- CordRepFlat* new_node = CordRepFlat::New(root->length);
- new_node->length = new_node->Capacity();
- *region = new_node->Data();
- *size = new_node->length;
-
- if (cord_ring_enabled()) {
- replace_tree(CordRepRing::Append(ForceRing(root, 1), new_node));
- return;
+ rep = CordRepRing::Append(ForceRing(rep, 1), new_node);
+ } else {
+ rep = Concat(rep, new_node);
}
- replace_tree(Concat(root, new_node));
+ CommitTree(root, rep, scope, method);
}
// If the rep is a leaf, this will increment the value at total_mem_usage and
@@ -529,21 +498,26 @@ void Cord::InlineRep::UpdateCordzStatisticsSlow() {
}
void Cord::InlineRep::AssignSlow(const Cord::InlineRep& src) {
- UnrefTree();
-
- data_ = src.data_;
- if (is_tree()) {
- CordRep::Ref(tree());
- clear_cordz_info();
- CordzInfo::MaybeTrackCord(data_, CordzUpdateTracker::kAssignCord);
+ assert(&src != this);
+ assert(is_tree() || src.is_tree());
+ auto constexpr method = CordzUpdateTracker::kAssignCord;
+ if (CordRep* tree = this->tree()) {
+ CordzUpdateScope scope(data_.cordz_info(), method);
+ CordRep::Unref(tree);
+ if (CordRep* src_tree = src.tree()) {
+ SetTree(CordRep::Ref(src_tree), scope);
+ } else {
+ scope.SetCordRep(nullptr);
+ data_ = src.data_;
+ }
+ } else {
+ EmplaceTree(CordRep::Ref(src.as_tree()), method);
}
}
void Cord::InlineRep::UnrefTree() {
if (is_tree()) {
- if (ABSL_PREDICT_FALSE(is_profiled())) {
- absl::cord_internal::CordzInfo::UntrackCord(cordz_info());
- }
+ CordzInfo::MaybeUntrackCord(data_.cordz_info());
CordRep::Unref(tree());
}
}
@@ -595,12 +569,9 @@ template Cord::Cord(std::string&& src);
// The destruction code is separate so that the compiler can determine
// that it does not need to call the destructor on a moved-from Cord.
void Cord::DestroyCordSlow() {
- if (ABSL_PREDICT_FALSE(contents_.is_profiled())) {
- absl::cord_internal::CordzInfo::UntrackCord(contents_.cordz_info());
- }
- if (CordRep* tree = contents_.tree()) {
- CordRep::Unref(VerifyTree(tree));
- }
+ assert(contents_.is_tree());
+ CordzInfo::MaybeUntrackCord(contents_.cordz_info());
+ CordRep::Unref(VerifyTree(contents_.as_tree()));
}
// --------------------------------------------------------------------
@@ -613,23 +584,18 @@ void Cord::Clear() {
}
Cord& Cord::operator=(absl::string_view src) {
- if (ABSL_PREDICT_FALSE(contents_.is_profiled())) {
- absl::cord_internal::CordzInfo::UntrackCord(contents_.cordz_info());
- contents_.clear_cordz_info();
- }
-
const char* data = src.data();
size_t length = src.size();
CordRep* tree = contents_.tree();
if (length <= InlineRep::kMaxInline) {
// Embed into this->contents_
+ if (tree) CordzInfo::MaybeUntrackCord(contents_.cordz_info());
contents_.set_data(data, length, true);
if (tree) CordRep::Unref(tree);
return *this;
}
if (tree != nullptr && tree->tag >= FLAT &&
- tree->flat()->Capacity() >= length &&
- tree->refcount.IsOne()) {
+ tree->flat()->Capacity() >= length && tree->refcount.IsOne()) {
// Copy in place if the existing FLAT node is reusable.
memmove(tree->flat()->Data(), data, length);
tree->length = length;
@@ -655,71 +621,70 @@ template Cord& Cord::operator=(std::string&& src);
// TODO(sanjay): Move to Cord::InlineRep section of file. For now,
// we keep it here to make diffs easier.
-void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) {
- if (src_size == 0) return; // memcpy(_, nullptr, 0) is undefined.
+void Cord::InlineRep::AppendArray(absl::string_view src,
+ MethodIdentifier method) {
+ if (src.empty()) return; // memcpy(_, nullptr, 0) is undefined.
size_t appended = 0;
- CordRep* root = nullptr;
- if (is_tree()) {
- root = data_.as_tree();
+ CordRep* rep = tree();
+ const CordRep* const root = rep;
+ CordzUpdateScope scope(root ? cordz_info() : nullptr, method);
+ if (root != nullptr) {
char* region;
- if (PrepareAppendRegion(root, &region, &appended, src_size)) {
- memcpy(region, src_data, appended);
- UpdateCordzStatistics();
+ if (PrepareAppendRegion(rep, &region, &appended, src.size())) {
+ memcpy(region, src.data(), appended);
}
} else {
// Try to fit in the inline buffer if possible.
size_t inline_length = inline_size();
- if (src_size <= kMaxInline - inline_length) {
+ if (src.size() <= kMaxInline - inline_length) {
// Append new data to embedded array
- memcpy(data_.as_chars() + inline_length, src_data, src_size);
- set_inline_size(inline_length + src_size);
+ memcpy(data_.as_chars() + inline_length, src.data(), src.size());
+ set_inline_size(inline_length + src.size());
return;
}
- // It is possible that src_data == data_, but when we transition from an
+ // It is possible that src.data() == data_, but when we transition from an
// InlineRep to a tree we need to assign data_ = root via set_tree. To
// avoid corrupting the source data before we copy it, delay calling
// set_tree until after we've copied data.
// We are going from an inline size to beyond inline size. Make the new size
// either double the inlined size, or the added size + 10%.
- const size_t size1 = inline_length * 2 + src_size;
- const size_t size2 = inline_length + src_size / 10;
- root = CordRepFlat::New(std::max<size_t>(size1, size2));
- appended = std::min(
- src_size, root->flat()->Capacity() - inline_length);
- memcpy(root->flat()->Data(), data_.as_chars(), inline_length);
- memcpy(root->flat()->Data() + inline_length, src_data, appended);
- root->length = inline_length + appended;
- set_tree(root);
- }
-
- src_data += appended;
- src_size -= appended;
- if (src_size == 0) {
+ const size_t size1 = inline_length * 2 + src.size();
+ const size_t size2 = inline_length + src.size() / 10;
+ rep = CordRepFlat::New(std::max<size_t>(size1, size2));
+ appended = std::min(src.size(), rep->flat()->Capacity() - inline_length);
+ memcpy(rep->flat()->Data(), data_.as_chars(), inline_length);
+ memcpy(rep->flat()->Data() + inline_length, src.data(), appended);
+ rep->length = inline_length + appended;
+ }
+
+ src.remove_prefix(appended);
+ if (src.empty()) {
+ CommitTree(root, rep, scope, method);
return;
}
if (cord_ring_enabled()) {
- absl::string_view data(src_data, src_size);
- root = ForceRing(root, (data.size() - 1) / kMaxFlatLength + 1);
- replace_tree(CordRepRing::Append(root->ring(), data));
- return;
- }
-
- // 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>(root->length / 10, src_size);
+ rep = ForceRing(rep, (src.size() - 1) / kMaxFlatLength + 1);
+ rep = CordRepRing::Append(rep->ring(), src);
+ } 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()));
}
- set_tree(Concat(root, NewTree(src_data, src_size, length - src_size)));
+ CommitTree(root, rep, scope, method);
}
inline CordRep* Cord::TakeRep() const& {
@@ -734,12 +699,13 @@ inline CordRep* Cord::TakeRep() && {
template <typename C>
inline void Cord::AppendImpl(C&& src) {
+ auto constexpr method = CordzUpdateTracker::kAppendCord;
if (empty()) {
// Since destination is empty, we can avoid allocating a node,
if (src.contents_.is_tree()) {
// by taking the tree directly
CordRep* rep = std::forward<C>(src).TakeRep();
- contents_.EmplaceTree(rep, CordzUpdateTracker::kAppendCord);
+ contents_.EmplaceTree(rep, method);
} else {
// or copying over inline data
contents_.data_ = src.contents_.data_;
@@ -753,12 +719,12 @@ inline void Cord::AppendImpl(C&& src) {
CordRep* src_tree = src.contents_.tree();
if (src_tree == nullptr) {
// src has embedded data.
- contents_.AppendArray(src.contents_.data(), src_size);
+ contents_.AppendArray({src.contents_.data(), src_size}, method);
return;
}
if (src_tree->tag >= FLAT) {
// src tree just has one flat node.
- contents_.AppendArray(src_tree->flat()->Data(), src_size);
+ contents_.AppendArray({src_tree->flat()->Data(), src_size}, method);
return;
}
if (&src == this) {
@@ -797,7 +763,7 @@ void Cord::Prepend(const Cord& src) {
CordRep* src_tree = src.contents_.tree();
if (src_tree != nullptr) {
CordRep::Ref(src_tree);
- contents_.PrependTree(src_tree);
+ contents_.PrependTree(src_tree, CordzUpdateTracker::kPrependCord);
return;
}
@@ -820,7 +786,8 @@ void Cord::Prepend(absl::string_view src) {
return;
}
}
- contents_.PrependTree(NewTree(src.data(), src.size(), 0));
+ CordRep* rep = NewTree(src.data(), src.size(), 0);
+ contents_.PrependTree(rep, CordzUpdateTracker::kPrependString);
}
template <typename T, Cord::EnableIfString<T>>
@@ -1847,8 +1814,7 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
*os << absl::CEscape(std::string(rep->external()->base, rep->length));
*os << "]\n";
} else if (rep->tag >= FLAT) {
- *os << "FLAT cap=" << rep->flat()->Capacity()
- << " [";
+ *os << "FLAT cap=" << rep->flat()->Capacity() << " [";
if (include_data)
*os << absl::CEscape(std::string(rep->flat()->Data(), rep->length));
*os << "]\n";
@@ -1860,7 +1826,7 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
do {
DumpNode(ring->entry_child(head), include_data, os,
indent + kIndentStep);
- head = ring->advance(head);;
+ head = ring->advance(head);
} while (head != ring->tail());
}
if (stack.empty()) break;
@@ -1906,9 +1872,8 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
worklist.push_back(node->concat()->left);
}
} else if (node->tag >= FLAT) {
- ABSL_INTERNAL_CHECK(
- node->length <= node->flat()->Capacity(),
- ReportError(root, node));
+ ABSL_INTERNAL_CHECK(node->length <= node->flat()->Capacity(),
+ ReportError(root, node));
} else if (node->tag == EXTERNAL) {
ABSL_INTERNAL_CHECK(node->external()->base != nullptr,
ReportError(root, node));
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-30 11:06:23 +0000