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.cc180
1 files changed, 96 insertions, 84 deletions
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index f5aa6e47..ecbd2dbd 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -36,8 +36,8 @@
#include "absl/container/inlined_vector.h"
#include "absl/strings/escaping.h"
#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_btree.h"
#include "absl/strings/internal/cord_rep_flat.h"
-#include "absl/strings/internal/cord_rep_ring.h"
#include "absl/strings/internal/cordz_statistics.h"
#include "absl/strings/internal/cordz_update_scope.h"
#include "absl/strings/internal/cordz_update_tracker.h"
@@ -51,20 +51,20 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
using ::absl::cord_internal::CordRep;
+using ::absl::cord_internal::CordRepBtree;
using ::absl::cord_internal::CordRepConcat;
using ::absl::cord_internal::CordRepExternal;
using ::absl::cord_internal::CordRepFlat;
-using ::absl::cord_internal::CordRepRing;
using ::absl::cord_internal::CordRepSubstring;
using ::absl::cord_internal::CordzUpdateTracker;
using ::absl::cord_internal::InlineData;
using ::absl::cord_internal::kMaxFlatLength;
using ::absl::cord_internal::kMinFlatLength;
+using ::absl::cord_internal::BTREE;
using ::absl::cord_internal::CONCAT;
using ::absl::cord_internal::EXTERNAL;
using ::absl::cord_internal::FLAT;
-using ::absl::cord_internal::RING;
using ::absl::cord_internal::SUBSTRING;
using ::absl::cord_internal::kInlinedVectorSize;
@@ -100,8 +100,8 @@ static constexpr uint64_t min_length[] = {
static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length);
-static inline bool cord_ring_enabled() {
- return cord_internal::cord_ring_buffer_enabled.load(
+static inline bool btree_enabled() {
+ return cord_internal::cord_btree_enabled.load(
std::memory_order_relaxed);
}
@@ -218,27 +218,25 @@ static CordRepFlat* CreateFlat(const char* data, size_t length,
return flat;
}
-// Creates a new flat or ringbuffer out of the specified array.
+// Creates a new flat or Btree out of the specified array.
// The returned node has a refcount of 1.
-static CordRep* RingNewTree(const char* data, size_t length,
- size_t alloc_hint) {
+static CordRep* NewBtree(const char* data, size_t length, size_t alloc_hint) {
if (length <= kMaxFlatLength) {
return CreateFlat(data, length, alloc_hint);
}
CordRepFlat* flat = CreateFlat(data, kMaxFlatLength, 0);
data += kMaxFlatLength;
length -= kMaxFlatLength;
- size_t extra = (length - 1) / kMaxFlatLength + 1;
- auto* root = CordRepRing::Create(flat, extra);
- return CordRepRing::Append(root, {data, length}, alloc_hint);
+ auto* root = CordRepBtree::Create(flat);
+ return CordRepBtree::Append(root, {data, length}, alloc_hint);
}
// 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) {
if (length == 0) return nullptr;
- if (cord_ring_enabled()) {
- return RingNewTree(data, length, alloc_hint);
+ if (btree_enabled()) {
+ return NewBtree(data, length, alloc_hint);
}
absl::FixedArray<CordRep*> reps((length - 1) / kMaxFlatLength + 1);
size_t n = 0;
@@ -346,10 +344,10 @@ inline void Cord::InlineRep::remove_prefix(size_t n) {
reduce_size(n);
}
-// Returns `rep` converted into a CordRepRing.
-// Directly returns `rep` if `rep` is already a CordRepRing.
-static CordRepRing* ForceRing(CordRep* rep, size_t extra) {
- return (rep->tag == RING) ? rep->ring() : CordRepRing::Create(rep, extra);
+// Returns `rep` converted into a CordRepBtree.
+// Directly returns `rep` if `rep` is already a CordRepBtree.
+static CordRepBtree* ForceBtree(CordRep* rep) {
+ return rep->tag == BTREE ? rep->btree() : CordRepBtree::Create(rep);
}
void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
@@ -357,8 +355,8 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
assert(!is_tree());
if (!data_.is_empty()) {
CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
- if (cord_ring_enabled()) {
- tree = CordRepRing::Append(CordRepRing::Create(flat, 1), tree);
+ if (btree_enabled()) {
+ tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
} else {
tree = Concat(flat, tree);
}
@@ -369,8 +367,8 @@ 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 (cord_ring_enabled()) {
- tree = CordRepRing::Append(ForceRing(data_.as_tree(), 1), tree);
+ if (btree_enabled()) {
+ tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
} else {
tree = Concat(data_.as_tree(), tree);
}
@@ -391,8 +389,8 @@ void Cord::InlineRep::PrependTreeToInlined(CordRep* tree,
assert(!is_tree());
if (!data_.is_empty()) {
CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
- if (cord_ring_enabled()) {
- tree = CordRepRing::Prepend(CordRepRing::Create(flat, 1), tree);
+ if (btree_enabled()) {
+ tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
} else {
tree = Concat(tree, flat);
}
@@ -404,8 +402,8 @@ 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);
+ if (btree_enabled()) {
+ tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
} else {
tree = Concat(tree, data_.as_tree());
}
@@ -427,8 +425,8 @@ void Cord::InlineRep::PrependTree(CordRep* tree, MethodIdentifier method) {
// written to region and the actual size increase will be written to size.
static inline bool PrepareAppendRegion(CordRep* root, char** region,
size_t* size, size_t max_length) {
- if (root->tag == RING && root->refcount.IsOne()) {
- Span<char> span = root->ring()->GetAppendBuffer(max_length);
+ if (root->tag == BTREE && root->refcount.IsOne()) {
+ Span<char> span = root->btree()->GetAppendBuffer(max_length);
if (!span.empty()) {
*region = span.data();
*size = span.size();
@@ -500,8 +498,8 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size,
*region = new_node->Data();
*size = new_node->length;
- if (cord_ring_enabled()) {
- rep = CordRepRing::Append(ForceRing(rep, 1), new_node);
+ if (btree_enabled()) {
+ rep = CordRepBtree::Append(ForceBtree(rep), new_node);
} else {
rep = Concat(rep, new_node);
}
@@ -511,8 +509,13 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size,
// If the rep is a leaf, this will increment the value at total_mem_usage and
// will return true.
static bool RepMemoryUsageLeaf(const CordRep* rep, size_t* total_mem_usage) {
+ size_t maybe_sub_size = 0;
+ if (rep->tag == SUBSTRING) {
+ maybe_sub_size = sizeof(cord_internal::CordRepSubstring);
+ rep = rep->substring()->child;
+ }
if (rep->tag >= FLAT) {
- *total_mem_usage += rep->flat()->AllocatedSize();
+ *total_mem_usage += maybe_sub_size + rep->flat()->AllocatedSize();
return true;
}
if (rep->tag == EXTERNAL) {
@@ -520,8 +523,9 @@ static bool RepMemoryUsageLeaf(const CordRep* rep, size_t* total_mem_usage) {
// assume it is 'at least' a word / pointer to data. In the future we may
// choose to use the 'data' byte as a tag to identify the types of some
// well-known externals, such as a std::string instance.
- *total_mem_usage +=
- sizeof(cord_internal::CordRepExternalImpl<intptr_t>) + rep->length;
+ *total_mem_usage += maybe_sub_size +
+ sizeof(cord_internal::CordRepExternalImpl<intptr_t>) +
+ rep->length;
return true;
}
return false;
@@ -690,9 +694,11 @@ void Cord::InlineRep::AppendArray(absl::string_view src,
return;
}
- if (cord_ring_enabled()) {
- rep = ForceRing(rep, (src.size() - 1) / kMaxFlatLength + 1);
- rep = CordRepRing::Append(rep->ring(), src);
+ if (btree_enabled()) {
+ // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
+ rep = ForceBtree(rep);
+ const size_t alloc_hint = (std::min)(kMaxFlatLength, rep->length / 10);
+ rep = CordRepBtree::Append(rep->btree(), src, alloc_hint);
} 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
@@ -769,9 +775,13 @@ inline void Cord::AppendImpl(C&& src) {
contents_.AppendTree(rep, CordzUpdateTracker::kAppendCord);
}
-void Cord::Append(const Cord& src) { AppendImpl(src); }
+void Cord::Append(const Cord& src) {
+ AppendImpl(src);
+}
-void Cord::Append(Cord&& src) { AppendImpl(std::move(src)); }
+void Cord::Append(Cord&& src) {
+ AppendImpl(std::move(src));
+}
template <typename T, Cord::EnableIfString<T>>
void Cord::Append(T&& src) {
@@ -923,8 +933,10 @@ void Cord::RemovePrefix(size_t n) {
} else {
auto constexpr method = CordzUpdateTracker::kRemovePrefix;
CordzUpdateScope scope(contents_.cordz_info(), method);
- if (tree->tag == RING) {
- tree = CordRepRing::RemovePrefix(tree->ring(), n);
+ if (tree->tag == BTREE) {
+ CordRep* old = tree;
+ tree = tree->btree()->SubTree(n, tree->length - n);
+ CordRep::Unref(old);
} else {
CordRep* newrep = RemovePrefixFrom(tree, n);
CordRep::Unref(tree);
@@ -944,8 +956,10 @@ void Cord::RemoveSuffix(size_t n) {
} else {
auto constexpr method = CordzUpdateTracker::kRemoveSuffix;
CordzUpdateScope scope(contents_.cordz_info(), method);
- if (tree->tag == RING) {
- tree = CordRepRing::RemoveSuffix(tree->ring(), n);
+ if (tree->tag == BTREE) {
+ CordRep* old = tree;
+ tree = tree->btree()->SubTree(0, tree->length - n);
+ CordRep::Unref(old);
} else {
CordRep* newrep = RemoveSuffixFrom(tree, n);
CordRep::Unref(tree);
@@ -1037,9 +1051,8 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
return sub_cord;
}
- if (tree->tag == RING) {
- CordRepRing* ring = CordRep::Ref(tree)->ring();
- tree = CordRepRing::SubRing(ring, pos, new_size);
+ if (tree->tag == BTREE) {
+ tree = tree->btree()->SubTree(pos, new_size);
} else {
tree = NewSubRange(tree, pos, new_size);
}
@@ -1227,8 +1240,8 @@ bool ComputeCompareResult<bool>(int memcmp_res) {
} // namespace
-// Helper routine. Locates the first flat chunk of the Cord without
-// initializing the iterator.
+// Helper routine. Locates the first flat or external chunk of the Cord without
+// initializing the iterator, and returns a string_view referencing the data.
inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
if (!is_tree()) {
return absl::string_view(data_.as_chars(), data_.inline_size());
@@ -1243,8 +1256,13 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
return absl::string_view(node->external()->base, node->length);
}
- if (node->tag == RING) {
- return node->ring()->entry_data(node->ring()->head());
+ if (node->tag == BTREE) {
+ CordRepBtree* tree = node->btree();
+ int height = tree->height();
+ while (--height >= 0) {
+ tree = tree->Edge(CordRepBtree::kFront)->btree();
+ }
+ return tree->Data(tree->begin());
}
// Walk down the left branches until we hit a non-CONCAT node.
@@ -1506,22 +1524,21 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
return subcord;
}
- if (ring_reader_) {
+ if (btree_reader_) {
size_t chunk_size = current_chunk_.size();
if (n <= chunk_size && n <= kMaxBytesToCopy) {
subcord = Cord(current_chunk_.substr(0, n), method);
+ if (n < chunk_size) {
+ current_chunk_.remove_prefix(n);
+ } else {
+ current_chunk_ = btree_reader_.Next();
+ }
} else {
- auto* ring = CordRep::Ref(ring_reader_.ring())->ring();
- size_t offset = ring_reader_.length() - bytes_remaining_;
- CordRep* rep = CordRepRing::SubRing(ring, offset, n);
+ CordRep* rep;
+ current_chunk_ = btree_reader_.Read(n, chunk_size, rep);
subcord.contents_.EmplaceTree(rep, method);
}
- if (n < chunk_size) {
- bytes_remaining_ -= n;
- current_chunk_.remove_prefix(n);
- } else {
- AdvanceBytesRing(n);
- }
+ bytes_remaining_ -= n;
return subcord;
}
@@ -1698,8 +1715,8 @@ char Cord::operator[](size_t i) const {
if (rep->tag >= FLAT) {
// Get the "i"th character directly from the flat array.
return rep->flat()->Data()[offset];
- } else if (rep->tag == RING) {
- return rep->ring()->GetCharacter(offset);
+ } else if (rep->tag == BTREE) {
+ return rep->btree()->GetCharacter(offset);
} else if (rep->tag == EXTERNAL) {
// Get the "i"th character from the external array.
return rep->external()->base[offset];
@@ -1758,8 +1775,8 @@ absl::string_view Cord::FlattenSlowPath() {
} else if (rep->tag == EXTERNAL) {
*fragment = absl::string_view(rep->external()->base, rep->length);
return true;
- } else if (rep->tag == RING) {
- return rep->ring()->IsFlat(fragment);
+ } else if (rep->tag == BTREE) {
+ return rep->btree()->IsFlat(fragment);
} else if (rep->tag == SUBSTRING) {
CordRep* child = rep->substring()->child;
if (child->tag >= FLAT) {
@@ -1770,9 +1787,9 @@ absl::string_view Cord::FlattenSlowPath() {
*fragment = absl::string_view(
child->external()->base + rep->substring()->start, rep->length);
return true;
- } else if (child->tag == RING) {
- return child->ring()->IsFlat(rep->substring()->start, rep->length,
- fragment);
+ } else if (child->tag == BTREE) {
+ return child->btree()->IsFlat(rep->substring()->start, rep->length,
+ fragment);
}
}
return false;
@@ -1781,7 +1798,7 @@ absl::string_view Cord::FlattenSlowPath() {
/* static */ void Cord::ForEachChunkAux(
absl::cord_internal::CordRep* rep,
absl::FunctionRef<void(absl::string_view)> callback) {
- if (rep->tag == RING) {
+ if (rep->tag == BTREE) {
ChunkIterator it(rep), end;
while (it != end) {
callback(*it);
@@ -1866,15 +1883,7 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
*os << absl::CEscape(std::string(rep->flat()->Data(), rep->length));
*os << "]\n";
} else {
- assert(rep->tag == RING);
- auto* ring = rep->ring();
- *os << "RING, entries = " << ring->entries() << "\n";
- CordRepRing::index_type head = ring->head();
- do {
- DumpNode(ring->entry_child(head), include_data, os,
- indent + kIndentStep);
- head = ring->advance(head);
- } while (head != ring->tail());
+ CordRepBtree::Dump(rep, /*label=*/ "", include_data, *os);
}
if (stack.empty()) break;
rep = stack.back();
@@ -1967,15 +1976,18 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
}
next_node = right;
}
- } else if (cur_node->tag == RING) {
- total_mem_usage += CordRepRing::AllocSize(cur_node->ring()->capacity());
- const CordRepRing* ring = cur_node->ring();
- CordRepRing::index_type pos = ring->head(), tail = ring->tail();
- do {
- CordRep* node = ring->entry_child(pos);
- assert(node->tag >= FLAT || node->tag == EXTERNAL);
- RepMemoryUsageLeaf(node, &total_mem_usage);
- } while ((pos = ring->advance(pos)) != tail);
+ } else if (cur_node->tag == BTREE) {
+ total_mem_usage += sizeof(CordRepBtree);
+ const CordRepBtree* node = cur_node->btree();
+ if (node->height() == 0) {
+ for (const CordRep* edge : node->Edges()) {
+ RepMemoryUsageLeaf(edge, &total_mem_usage);
+ }
+ } else {
+ for (const CordRep* edge : node->Edges()) {
+ tree_stack.push_back(edge);
+ }
+ }
} else {
// Since cur_node is not a leaf or a concat node it must be a substring.
assert(cur_node->tag == SUBSTRING);
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-12 20:52:28 +0000