summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--CMake/AbseilDll.cmake1
-rw-r--r--absl/base/log_severity.h2
-rw-r--r--absl/strings/BUILD.bazel16
-rw-r--r--absl/strings/CMakeLists.txt16
-rw-r--r--absl/strings/cord.h20
-rw-r--r--absl/strings/cord_ring_reader_test.cc173
-rw-r--r--absl/strings/internal/cord_internal.h5
-rw-r--r--absl/strings/internal/cord_rep_ring_reader.h114
8 files changed, 344 insertions, 3 deletions
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake
index ac2f325c..b8c38d68 100644
--- a/CMake/AbseilDll.cmake
+++ b/CMake/AbseilDll.cmake
@@ -198,6 +198,7 @@ set(ABSL_INTERNAL_DLL_FILES
"strings/internal/cord_rep_flat.h"
"strings/internal/cord_rep_ring.cc"
"strings/internal/cord_rep_ring.h"
+ "strings/internal/cord_rep_ring_reader.h"
"strings/internal/charconv_bigint.cc"
"strings/internal/charconv_bigint.h"
"strings/internal/charconv_parse.cc"
diff --git a/absl/base/log_severity.h b/absl/base/log_severity.h
index 045f17f8..22364224 100644
--- a/absl/base/log_severity.h
+++ b/absl/base/log_severity.h
@@ -36,7 +36,7 @@ ABSL_NAMESPACE_BEGIN
// such values to a defined severity level, however in some cases values other
// than the defined levels are useful for comparison.
//
-// Exmaple:
+// Example:
//
// // Effectively disables all logging:
// SetMinLogLevel(static_cast<absl::LogSeverity>(100));
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index d7c322f6..794cf43a 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -275,6 +275,7 @@ cc_library(
"internal/cord_internal.h",
"internal/cord_rep_flat.h",
"internal/cord_rep_ring.h",
+ "internal/cord_rep_ring_reader.h",
],
copts = ABSL_DEFAULT_COPTS,
visibility = [
@@ -371,6 +372,21 @@ cc_test(
)
cc_test(
+ name = "cord_ring_reader_test",
+ size = "medium",
+ srcs = ["cord_ring_reader_test.cc"],
+ copts = ABSL_TEST_COPTS,
+ visibility = ["//visibility:private"],
+ deps = [
+ ":cord_internal",
+ ":strings",
+ "//absl/base:core_headers",
+ "//absl/debugging:leak_check",
+ "@com_google_googletest//:gtest_main",
+ ],
+)
+
+cc_test(
name = "substitute_test",
size = "small",
srcs = ["substitute_test.cc"],
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index a6204bf6..12f322a9 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -560,6 +560,7 @@ absl_cc_library(
"internal/cord_internal.h"
"internal/cord_rep_ring.h"
"internal/cord_rep_ring.cc"
+ "internal/cord_rep_ring_reader.h"
"internal/cord_rep_flat.h"
COPTS
${ABSL_DEFAULT_COPTS}
@@ -630,3 +631,18 @@ absl_cc_test(
absl::raw_logging_internal
gmock_main
)
+
+absl_cc_test(
+ NAME
+ cord_ring_reader_test
+ SRCS
+ "cord_ring_reader_test.cc"
+ COPTS
+ ${ABSL_TEST_COPTS}
+ DEPS
+ absl::cord
+ absl::strings
+ absl::base
+ absl::core_headers
+ gmock_main
+)
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 9d8764a0..abef98fe 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -367,9 +367,15 @@ class Cord {
// the inlined vector size (47 exists for backward compatibility).
using Stack = absl::InlinedVector<absl::cord_internal::CordRep*, 47>;
+ // Constructs a `begin()` iterator from `tree`. `tree` must not be null.
+ explicit ChunkIterator(cord_internal::CordRep* tree);
+
// Constructs a `begin()` iterator from `cord`.
explicit ChunkIterator(const Cord* cord);
+ // Initializes this instance from a tree. Invoked by constructors.
+ void InitTree(cord_internal::CordRep* tree);
+
// Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
// `current_chunk_.size()`.
void RemoveChunkPrefix(size_t n);
@@ -1100,11 +1106,20 @@ inline bool Cord::StartsWith(absl::string_view rhs) const {
return EqualsImpl(rhs, rhs_size);
}
+inline void Cord::ChunkIterator::InitTree(cord_internal::CordRep* tree) {
+ stack_of_right_children_.push_back(tree);
+ operator++();
+}
+
+inline Cord::ChunkIterator::ChunkIterator(cord_internal::CordRep* tree)
+ : bytes_remaining_(tree->length) {
+ InitTree(tree);
+}
+
inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
: bytes_remaining_(cord->size()) {
if (cord->contents_.is_tree()) {
- stack_of_right_children_.push_back(cord->contents_.as_tree());
- operator++();
+ InitTree(cord->contents_.as_tree());
} else {
current_chunk_ =
absl::string_view(cord->contents_.data(), bytes_remaining_);
@@ -1155,6 +1170,7 @@ inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
}
inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
+ assert(bytes_remaining_ >= n);
if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
RemoveChunkPrefix(n);
} else if (n != 0) {
diff --git a/absl/strings/cord_ring_reader_test.cc b/absl/strings/cord_ring_reader_test.cc
new file mode 100644
index 00000000..585616f3
--- /dev/null
+++ b/absl/strings/cord_ring_reader_test.cc
@@ -0,0 +1,173 @@
+// Copyright 2020 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 <cstdlib>
+#include <ctime>
+#include <memory>
+#include <random>
+#include <sstream>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/debugging/leak_check.h"
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_ring.h"
+#include "absl/strings/internal/cord_rep_ring_reader.h"
+#include "absl/strings/string_view.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+namespace {
+
+using testing::Eq;
+
+// Creates a flat for testing
+CordRep* MakeFlat(absl::string_view s) {
+ CordRepFlat* flat = CordRepFlat::New(s.length());
+ memcpy(flat->Data(), s.data(), s.length());
+ flat->length = s.length();
+ return flat;
+}
+
+CordRepRing* FromFlats(Span<absl::string_view const> flats) {
+ CordRepRing* ring = CordRepRing::Create(MakeFlat(flats[0]), flats.size() - 1);
+ for (int i = 1; i < flats.size(); ++i) {
+ ring = CordRepRing::Append(ring, MakeFlat(flats[i]));
+ }
+ return ring;
+}
+
+std::array<absl::string_view, 12> TestFlats() {
+ return {"abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ",
+ "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_",
+ "+-=", "[]\\{}|;':", ",/<>?", "."};
+}
+
+TEST(CordRingReaderTest, DefaultInstance) {
+ CordRepRingReader reader;
+ EXPECT_FALSE(static_cast<bool>(reader));
+ EXPECT_THAT(reader.ring(), Eq(nullptr));
+#ifndef NDEBUG
+ EXPECT_DEATH_IF_SUPPORTED(reader.length(), ".*");
+ EXPECT_DEATH_IF_SUPPORTED(reader.consumed(), ".*");
+ EXPECT_DEATH_IF_SUPPORTED(reader.remaining(), ".*");
+ EXPECT_DEATH_IF_SUPPORTED(reader.Next(), ".*");
+ EXPECT_DEATH_IF_SUPPORTED(reader.Seek(0), ".*");
+#endif
+}
+
+TEST(CordRingReaderTest, Reset) {
+ CordRepRingReader reader;
+ auto flats = TestFlats();
+ CordRepRing* ring = FromFlats(flats);
+
+ absl::string_view first = reader.Reset(ring);
+ EXPECT_THAT(first, Eq(flats[0]));
+ EXPECT_TRUE(static_cast<bool>(reader));
+ EXPECT_THAT(reader.ring(), Eq(ring));
+ EXPECT_THAT(reader.index(), Eq(ring->head()));
+ EXPECT_THAT(reader.length(), Eq(ring->length));
+ EXPECT_THAT(reader.consumed(), Eq(flats[0].length()));
+ EXPECT_THAT(reader.remaining(), Eq(ring->length - reader.consumed()));
+
+ reader.Reset();
+ EXPECT_FALSE(static_cast<bool>(reader));
+ EXPECT_THAT(reader.ring(), Eq(nullptr));
+
+ CordRep::Unref(ring);
+}
+
+TEST(CordRingReaderTest, Next) {
+ CordRepRingReader reader;
+ auto flats = TestFlats();
+ CordRepRing* ring = FromFlats(flats);
+ CordRepRing::index_type head = ring->head();
+
+ reader.Reset(ring);
+ size_t consumed = reader.consumed();
+ size_t remaining = reader.remaining();
+ for (int i = 1; i < flats.size(); ++i) {
+ consumed += flats[i].length();
+ remaining -= flats[i].length();
+ absl::string_view next = reader.Next();
+ ASSERT_THAT(next, Eq(flats[i]));
+ ASSERT_THAT(reader.index(), Eq(ring->advance(head, i)));
+ ASSERT_THAT(reader.consumed(), Eq(consumed));
+ ASSERT_THAT(reader.remaining(), Eq(remaining));
+ }
+
+#ifndef NDEBUG
+ EXPECT_DEATH_IF_SUPPORTED(reader.Next(), ".*");
+#endif
+
+ CordRep::Unref(ring);
+}
+
+TEST(CordRingReaderTest, SeekForward) {
+ CordRepRingReader reader;
+ auto flats = TestFlats();
+ CordRepRing* ring = FromFlats(flats);
+ CordRepRing::index_type head = ring->head();
+
+ reader.Reset(ring);
+ size_t consumed = 0;
+ size_t remaining = ring->length;;
+ for (int i = 0; i < flats.size(); ++i) {
+ size_t offset = consumed;
+ consumed += flats[i].length();
+ remaining -= flats[i].length();
+ for (int off = 0; off < flats[i].length(); ++off) {
+ absl::string_view chunk = reader.Seek(offset + off);
+ ASSERT_THAT(chunk, Eq(flats[i].substr(off)));
+ ASSERT_THAT(reader.index(), Eq(ring->advance(head, i)));
+ ASSERT_THAT(reader.consumed(), Eq(consumed));
+ ASSERT_THAT(reader.remaining(), Eq(remaining));
+ }
+ }
+
+ CordRep::Unref(ring);
+}
+
+TEST(CordRingReaderTest, SeekBackward) {
+ CordRepRingReader reader;
+ auto flats = TestFlats();
+ CordRepRing* ring = FromFlats(flats);
+ CordRepRing::index_type head = ring->head();
+
+ reader.Reset(ring);
+ size_t consumed = ring->length;
+ size_t remaining = 0;
+ for (int i = flats.size() - 1; i >= 0; --i) {
+ size_t offset = consumed - flats[i].length();
+ for (int off = 0; off < flats[i].length(); ++off) {
+ absl::string_view chunk = reader.Seek(offset + off);
+ ASSERT_THAT(chunk, Eq(flats[i].substr(off)));
+ ASSERT_THAT(reader.index(), Eq(ring->advance(head, i)));
+ ASSERT_THAT(reader.consumed(), Eq(consumed));
+ ASSERT_THAT(reader.remaining(), Eq(remaining));
+ }
+ consumed -= flats[i].length();
+ remaining += flats[i].length();
+ }
+#ifndef NDEBUG
+ EXPECT_DEATH_IF_SUPPORTED(reader.Seek(ring->length), ".*");
+#endif
+ CordRep::Unref(ring);
+}
+
+} // namespace
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index 011b49d3..7a1ef6b1 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -203,10 +203,15 @@ struct CordRep {
// platforms; we intentionally allow LLVM to ignore the attribute rather than
// attempting to hardcode the list of supported platforms.
#if defined(__clang__) && !defined(__i386__)
+#if !(defined(ABSL_HAVE_MEMORY_SANITIZER) || \
+ defined(ABSL_HAVE_THREAD_SANITIZER) || \
+ defined(ABSL_HAVE_ADDRESS_SANITIZER) || \
+ defined(UNDEFINED_BEHAVIOR_SANITIZER))
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wattributes"
__attribute__((preserve_most))
#pragma clang diagnostic pop
+#endif // *_SANITIZER
#endif
static void Destroy(CordRep* rep);
diff --git a/absl/strings/internal/cord_rep_ring_reader.h b/absl/strings/internal/cord_rep_ring_reader.h
new file mode 100644
index 00000000..396c0e2c
--- /dev/null
+++ b/absl/strings/internal/cord_rep_ring_reader.h
@@ -0,0 +1,114 @@
+// 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.
+
+#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_
+#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_
+
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_ring.h"
+#include "absl/strings/string_view.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+
+// CordRepRingReader provides basic navigation over CordRepRing data.
+class CordRepRingReader {
+ public:
+ // Returns true if this instance is not empty.
+ explicit operator bool() const { return ring_ != nullptr; }
+
+ // Returns the ring buffer reference for this instance, or nullptr if empty.
+ CordRepRing* ring() const { return ring_; }
+
+ // Returns the current node index inside the ring buffer for this instance.
+ // The returned value is undefined if this instance is empty.
+ CordRepRing::index_type index() const { return index_; }
+
+ // Returns the length of the referenced ring buffer.
+ // Requires the current instance to be non empty.
+ size_t length() const {
+ assert(ring_);
+ return ring_->length;
+ }
+
+ // Returns the end offset of the last navigated-to chunk, which represents the
+ // total bytes 'consumed' relative to the start of the ring. The returned
+ // value is never zero. For example, initializing a reader with a ring buffer
+ // with a first chunk of 19 bytes will return consumed() = 19.
+ // Requires the current instance to be non empty.
+ size_t consumed() const {
+ assert(ring_);
+ return ring_->entry_end_offset(index_);
+ }
+
+ // Returns the number of bytes remaining beyond the last navigated-to chunk.
+ // Requires the current instance to be non empty.
+ size_t remaining() const {
+ assert(ring_);
+ return length() - consumed();
+ }
+
+ // Resets this instance to an empty value
+ void Reset() { ring_ = nullptr; }
+
+ // Resets this instance to the start of `ring`. `ring` must not be null.
+ // Returns a reference into the first chunk of the provided ring.
+ absl::string_view Reset(CordRepRing* ring) {
+ assert(ring);
+ ring_ = ring;
+ index_ = ring_->head();
+ return ring_->entry_data(index_);
+ }
+
+ // Navigates to the next chunk inside the reference ring buffer.
+ // Returns a reference into the navigated-to chunk.
+ // Requires remaining() to be non zero.
+ absl::string_view Next() {
+ assert(remaining());
+ index_ = ring_->advance(index_);
+ return ring_->entry_data(index_);
+ }
+
+ // Navigates to the chunk at offset `offset`.
+ // Returns a reference into the navigated-to chunk, adjusted for the relative
+ // position of `offset` into that chunk. For example, calling Seek(13) on a
+ // ring buffer containing 2 chunks of 10 and 20 bytes respectively will return
+ // a string view into the second chunk starting at offset 3 with a size of 17.
+ // Requires `offset` to be less than `length()`
+ absl::string_view Seek(size_t offset) {
+ assert(offset < length());
+ size_t current = ring_->entry_end_offset(index_);
+ CordRepRing::index_type hint = (offset >= current) ? index_ : ring_->head();
+ const CordRepRing::Position head = ring_->Find(hint, offset);
+ index_ = head.index;
+ auto data = ring_->entry_data(head.index);
+ data.remove_prefix(head.offset);
+ return data;
+ }
+
+ private:
+ CordRepRing* ring_ = nullptr;
+ CordRepRing::index_type index_;
+};
+
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_