summaryrefslogtreecommitdiff
path: root/absl/strings
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings')
-rw-r--r--absl/strings/CMakeLists.txt4
-rw-r--r--absl/strings/cord.cc45
-rw-r--r--absl/strings/cord.h30
-rw-r--r--absl/strings/internal/cord_internal.cc5
-rw-r--r--absl/strings/internal/cord_internal.h11
5 files changed, 70 insertions, 25 deletions
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index 54c10151..6cdab257 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -56,7 +56,7 @@ absl_cc_library(
DEPS
absl::strings_internal
absl::base
- absl::bits
+ absl::internal_bits
absl::config
absl::core_headers
absl::endian
@@ -406,7 +406,7 @@ absl_cc_library(
COPTS
${ABSL_DEFAULT_COPTS}
DEPS
- absl::bits
+ absl::internal_bits
absl::strings
absl::config
absl::core_headers
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index f475042c..f87f4882 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -1298,26 +1298,23 @@ void Cord::CopyToArraySlowPath(char* dst) const {
}
}
-Cord::ChunkIterator& Cord::ChunkIterator::operator++() {
- ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 &&
- "Attempted to iterate past `end()`");
- assert(bytes_remaining_ >= current_chunk_.size());
- bytes_remaining_ -= current_chunk_.size();
-
- if (stack_of_right_children_.empty()) {
+Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() {
+ assert(absl::holds_alternative<Stack>(context_));
+ auto& stack_of_right_children = absl::get<Stack>(context_);
+ if (stack_of_right_children.empty()) {
assert(!current_chunk_.empty()); // Called on invalid iterator.
// We have reached the end of the Cord.
return *this;
}
// Process the next node on the stack.
- CordRep* node = stack_of_right_children_.back();
- stack_of_right_children_.pop_back();
+ 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->tag == CONCAT) {
- stack_of_right_children_.push_back(node->concat()->right);
+ stack_of_right_children.push_back(node->concat()->right);
node = node->concat()->left;
}
@@ -1360,6 +1357,8 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
}
return subcord;
}
+ assert(absl::holds_alternative<Stack>(context_));
+ auto& stack_of_right_children = absl::get<Stack>(context_);
if (n < current_chunk_.size()) {
// Range to read is a proper subrange of the current chunk.
assert(current_leaf_ != nullptr);
@@ -1388,13 +1387,13 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
// Process the next node(s) on the stack, reading whole subtrees depending on
// their length and how many bytes we are advancing.
CordRep* node = nullptr;
- while (!stack_of_right_children_.empty()) {
- node = stack_of_right_children_.back();
- stack_of_right_children_.pop_back();
+ while (!stack_of_right_children.empty()) {
+ node = stack_of_right_children.back();
+ stack_of_right_children.pop_back();
if (node->length > n) break;
// TODO(qrczak): This might unnecessarily recreate existing concat nodes.
// Avoiding that would need pretty complicated logic (instead of
- // current_leaf_, keep current_subtree_ which points to the highest node
+ // current_leaf, keep current_subtree_ which points to the highest node
// such that the current leaf can be found on the path of left children
// starting from current_subtree_; delay creating subnode while node is
// below current_subtree_; find the proper node along the path of left
@@ -1419,7 +1418,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
while (node->tag == CONCAT) {
if (node->concat()->left->length > n) {
// Push right, descend left.
- stack_of_right_children_.push_back(node->concat()->right);
+ stack_of_right_children.push_back(node->concat()->right);
node = node->concat()->left;
} else {
// Read left, descend right.
@@ -1462,12 +1461,20 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
n -= current_chunk_.size();
bytes_remaining_ -= current_chunk_.size();
+ if (!absl::holds_alternative<Stack>(context_)) {
+ // We have reached the end of the Cord.
+ assert(bytes_remaining_ == 0);
+ return;
+ }
+
// Process the next node(s) on the stack, skipping whole subtrees depending on
// their length and how many bytes we are advancing.
CordRep* node = nullptr;
- while (!stack_of_right_children_.empty()) {
- node = stack_of_right_children_.back();
- stack_of_right_children_.pop_back();
+ assert(absl::holds_alternative<Stack>(context_));
+ auto& stack_of_right_children = absl::get<Stack>(context_);
+ while (!stack_of_right_children.empty()) {
+ node = stack_of_right_children.back();
+ stack_of_right_children.pop_back();
if (node->length > n) break;
n -= node->length;
bytes_remaining_ -= node->length;
@@ -1485,7 +1492,7 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
while (node->tag == CONCAT) {
if (node->concat()->left->length > n) {
// Push right, descend left.
- stack_of_right_children_.push_back(node->concat()->right);
+ stack_of_right_children.push_back(node->concat()->right);
node = node->concat()->left;
} else {
// Skip left, descend right.
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index b9cdc435..5fc61a73 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -362,6 +362,8 @@ class Cord {
friend class CharIterator;
private:
+ using Stack = absl::InlinedVector<absl::cord_internal::CordRep*, 4>;
+
// Constructs a `begin()` iterator from `cord`.
explicit ChunkIterator(const Cord* cord);
@@ -370,6 +372,10 @@ class Cord {
void RemoveChunkPrefix(size_t n);
Cord AdvanceAndReadBytes(size_t n);
void AdvanceBytes(size_t n);
+
+ // Stack specific operator++
+ ChunkIterator& AdvanceStack();
+
// Iterates `n` bytes, where `n` is expected to be greater than or equal to
// `current_chunk_.size()`.
void AdvanceBytesSlowPath(size_t n);
@@ -383,8 +389,10 @@ class Cord {
absl::cord_internal::CordRep* current_leaf_ = nullptr;
// The number of bytes left in the `Cord` over which we are iterating.
size_t bytes_remaining_ = 0;
- absl::InlinedVector<absl::cord_internal::CordRep*, 4>
- stack_of_right_children_;
+ // Context of this chunk iterator, can be one of:
+ // - monostate: iterator holds only one chunk or is empty.
+ // - Stack : iterator holds a concat / substring tree
+ absl::variant<absl::monostate, Stack> context_;
};
// Cord::ChunkIterator::chunk_begin()
@@ -1100,13 +1108,29 @@ inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
: bytes_remaining_(cord->size()) {
if (cord->empty()) return;
if (cord->contents_.is_tree()) {
- stack_of_right_children_.push_back(cord->contents_.tree());
+ Stack& stack_of_right_children = context_.emplace<Stack>();
+ stack_of_right_children.push_back(cord->contents_.tree());
operator++();
} else {
current_chunk_ = absl::string_view(cord->contents_.data(), cord->size());
}
}
+inline Cord::ChunkIterator& Cord::ChunkIterator::operator++() {
+ ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 &&
+ "Attempted to iterate past `end()`");
+ assert(bytes_remaining_ >= current_chunk_.size());
+ bytes_remaining_ -= current_chunk_.size();
+ if (bytes_remaining_ > 0) {
+ if (absl::holds_alternative<Stack>(context_)) {
+ return AdvanceStack();
+ }
+ } else {
+ current_chunk_ = {};
+ }
+ return *this;
+}
+
inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) {
ChunkIterator tmp(*this);
operator++();
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 35f4d235..59f2e4d9 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -24,7 +24,10 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {
-ABSL_CONST_INIT std::atomic<bool> cord_ring_buffer_enabled(false);
+ABSL_CONST_INIT std::atomic<bool> cord_ring_buffer_enabled(
+ kCordEnableRingBufferDefault);
+ABSL_CONST_INIT std::atomic<bool> shallow_subcords_enabled(
+ kCordShallowSubcordsDefault);
void CordRep::Destroy(CordRep* rep) {
assert(rep != nullptr);
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index f1af8e6e..57e7046a 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -31,12 +31,23 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {
+// Default feature enable states for cord ring buffers
+enum CordFeatureDefaults {
+ kCordEnableRingBufferDefault = false,
+ kCordShallowSubcordsDefault = false
+};
+
extern std::atomic<bool> cord_ring_buffer_enabled;
+extern std::atomic<bool> shallow_subcords_enabled;
inline void enable_cord_ring_buffer(bool enable) {
cord_ring_buffer_enabled.store(enable, std::memory_order_relaxed);
}
+inline void enable_shallow_subcords(bool enable) {
+ shallow_subcords_enabled.store(enable, std::memory_order_relaxed);
+}
+
enum Constants {
// The inlined size to use with absl::InlinedVector.
//