summaryrefslogtreecommitdiff
path: root/absl/strings/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings/internal')
-rw-r--r--absl/strings/internal/cord_data_edge.h63
-rw-r--r--absl/strings/internal/cord_data_edge_test.cc130
-rw-r--r--absl/strings/internal/cord_rep_btree.cc7
-rw-r--r--absl/strings/internal/cord_rep_btree.h31
-rw-r--r--absl/strings/internal/cord_rep_btree_navigator.cc3
-rw-r--r--absl/strings/internal/cord_rep_btree_reader.cc5
-rw-r--r--absl/strings/internal/cord_rep_btree_reader.h9
-rw-r--r--absl/strings/internal/cord_rep_btree_test.cc33
8 files changed, 223 insertions, 58 deletions
diff --git a/absl/strings/internal/cord_data_edge.h b/absl/strings/internal/cord_data_edge.h
new file mode 100644
index 00000000..e18b33e1
--- /dev/null
+++ b/absl/strings/internal/cord_data_edge.h
@@ -0,0 +1,63 @@
+// Copyright 2022 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_DATA_EDGE_H_
+#define ABSL_STRINGS_INTERNAL_CORD_DATA_EDGE_H_
+
+#include <cassert>
+#include <cstddef>
+
+#include "absl/base/config.h"
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_flat.h"
+#include "absl/strings/string_view.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+
+// Returns true if the provided rep is a FLAT, EXTERNAL or a SUBSTRING node
+// holding a FLAT or EXTERNAL child rep. Requires `rep != nullptr`.
+inline bool IsDataEdge(const CordRep* edge) {
+ assert(edge != nullptr);
+
+ // The fast path is that `edge` is an EXTERNAL or FLAT node, making the below
+ // if a single, well predicted branch. We then repeat the FLAT or EXTERNAL
+ // check in the slow path of the SUBSTRING check to optimize for the hot path.
+ if (edge->tag == EXTERNAL || edge->tag >= FLAT) return true;
+ if (edge->tag == SUBSTRING) edge = edge->substring()->child;
+ return edge->tag == EXTERNAL || edge->tag >= FLAT;
+}
+
+// Returns the `absl::string_view` data reference for the provided data edge.
+// Requires 'IsDataEdge(edge) == true`.
+inline absl::string_view EdgeData(const CordRep* edge) {
+ assert(IsDataEdge(edge));
+
+ size_t offset = 0;
+ const size_t length = edge->length;
+ if (edge->IsSubstring()) {
+ offset = edge->substring()->start;
+ edge = edge->substring()->child;
+ }
+ return edge->tag >= FLAT
+ ? absl::string_view{edge->flat()->Data() + offset, length}
+ : absl::string_view{edge->external()->base + offset, length};
+}
+
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_STRINGS_INTERNAL_CORD_DATA_EDGE_H_
diff --git a/absl/strings/internal/cord_data_edge_test.cc b/absl/strings/internal/cord_data_edge_test.cc
new file mode 100644
index 00000000..8fce3bc6
--- /dev/null
+++ b/absl/strings/internal/cord_data_edge_test.cc
@@ -0,0 +1,130 @@
+// Copyright 2022 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 "absl/strings/internal/cord_data_edge.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_test_util.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+namespace {
+
+using ::absl::cordrep_testing::MakeExternal;
+using ::absl::cordrep_testing::MakeFlat;
+using ::absl::cordrep_testing::MakeSubstring;
+
+TEST(CordDataEdgeTest, IsDataEdgeOnFlat) {
+ CordRep* rep = MakeFlat("Lorem ipsum dolor sit amet, consectetur ...");
+ EXPECT_TRUE(IsDataEdge(rep));
+ CordRep::Unref(rep);
+}
+
+TEST(CordDataEdgeTest, IsDataEdgeOnExternal) {
+ CordRep* rep = MakeExternal("Lorem ipsum dolor sit amet, consectetur ...");
+ EXPECT_TRUE(IsDataEdge(rep));
+ CordRep::Unref(rep);
+}
+
+TEST(CordDataEdgeTest, IsDataEdgeOnSubstringOfFlat) {
+ CordRep* rep = MakeFlat("Lorem ipsum dolor sit amet, consectetur ...");
+ CordRep* substr = MakeSubstring(1, 20, rep);
+ EXPECT_TRUE(IsDataEdge(substr));
+ CordRep::Unref(substr);
+}
+
+TEST(CordDataEdgeTest, IsDataEdgeOnSubstringOfExternal) {
+ CordRep* rep = MakeExternal("Lorem ipsum dolor sit amet, consectetur ...");
+ CordRep* substr = MakeSubstring(1, 20, rep);
+ EXPECT_TRUE(IsDataEdge(substr));
+ CordRep::Unref(substr);
+}
+
+TEST(CordDataEdgeTest, IsDataEdgeOnBtree) {
+ CordRep* rep = MakeFlat("Lorem ipsum dolor sit amet, consectetur ...");
+ CordRepBtree* tree = CordRepBtree::New(rep);
+ EXPECT_FALSE(IsDataEdge(tree));
+ CordRep::Unref(tree);
+}
+
+TEST(CordDataEdgeTest, IsDataEdgeOnBadSubstr) {
+ CordRep* rep = MakeFlat("Lorem ipsum dolor sit amet, consectetur ...");
+ CordRep* substr = MakeSubstring(1, 18, MakeSubstring(1, 20, rep));
+ EXPECT_FALSE(IsDataEdge(substr));
+ CordRep::Unref(substr);
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnFlat) {
+ absl::string_view value = "Lorem ipsum dolor sit amet, consectetur ...";
+ CordRep* rep = MakeFlat(value);
+ EXPECT_EQ(EdgeData(rep), value);
+ CordRep::Unref(rep);
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnExternal) {
+ absl::string_view value = "Lorem ipsum dolor sit amet, consectetur ...";
+ CordRep* rep = MakeExternal(value);
+ EXPECT_EQ(EdgeData(rep), value);
+ CordRep::Unref(rep);
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnSubstringOfFlat) {
+ absl::string_view value = "Lorem ipsum dolor sit amet, consectetur ...";
+ CordRep* rep = MakeFlat(value);
+ CordRep* substr = MakeSubstring(1, 20, rep);
+ EXPECT_EQ(EdgeData(substr), value.substr(1, 20));
+ CordRep::Unref(substr);
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnSubstringOfExternal) {
+ absl::string_view value = "Lorem ipsum dolor sit amet, consectetur ...";
+ CordRep* rep = MakeExternal(value);
+ CordRep* substr = MakeSubstring(1, 20, rep);
+ EXPECT_EQ(EdgeData(substr), value.substr(1, 20));
+ CordRep::Unref(substr);
+}
+
+#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
+
+TEST(CordDataEdgeTest, IsDataEdgeOnNullPtr) {
+ EXPECT_DEATH(IsDataEdge(nullptr), ".*");
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnNullPtr) {
+ EXPECT_DEATH(EdgeData(nullptr), ".*");
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnBtree) {
+ CordRep* rep = MakeFlat("Lorem ipsum dolor sit amet, consectetur ...");
+ CordRepBtree* tree = CordRepBtree::New(rep);
+ EXPECT_DEATH(EdgeData(tree), ".*");
+ CordRep::Unref(tree);
+}
+
+TEST(CordDataEdgeTest, EdgeDataOnBadSubstr) {
+ CordRep* rep = MakeFlat("Lorem ipsum dolor sit amet, consectetur ...");
+ CordRep* substr = MakeSubstring(1, 18, MakeSubstring(1, 20, rep));
+ EXPECT_DEATH(EdgeData(substr), ".*");
+ CordRep::Unref(substr);
+}
+
+#endif // GTEST_HAS_DEATH_TEST && !NDEBUG
+
+} // namespace
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/strings/internal/cord_rep_btree.cc b/absl/strings/internal/cord_rep_btree.cc
index 3ebd9f6d..2b592b47 100644
--- a/absl/strings/internal/cord_rep_btree.cc
+++ b/absl/strings/internal/cord_rep_btree.cc
@@ -22,6 +22,7 @@
#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
+#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_consume.h"
#include "absl/strings/internal/cord_rep_flat.h"
@@ -69,7 +70,7 @@ void DumpAll(const CordRep* rep, bool include_contents, std::ostream& stream,
// indentation and prefix / labels keeps us within roughly 80-100 wide.
constexpr size_t kMaxDataLength = 60;
stream << ", data = \""
- << CordRepBtree::EdgeData(r).substr(0, kMaxDataLength)
+ << EdgeData(r).substr(0, kMaxDataLength)
<< (r->length > kMaxDataLength ? "\"..." : "\"");
}
stream << '\n';
@@ -150,7 +151,7 @@ inline CordRep* MakeSubstring(CordRep* rep, size_t offset) {
CordRep* ResizeEdge(CordRep* edge, size_t length, bool is_mutable) {
assert(length > 0);
assert(length <= edge->length);
- assert(CordRepBtree::IsDataEdge(edge));
+ assert(IsDataEdge(edge));
if (length >= edge->length) return edge;
if (is_mutable && (edge->tag >= FLAT || edge->tag == SUBSTRING)) {
@@ -207,7 +208,7 @@ void DeleteSubstring(CordRepSubstring* substring) {
// Deletes a leaf node data edge. Requires `IsDataEdge(rep)`.
void DeleteLeafEdge(CordRep* rep) {
- assert(CordRepBtree::IsDataEdge(rep));
+ assert(IsDataEdge(rep));
if (rep->tag >= FLAT) {
CordRepFlat::Delete(rep->flat());
} else if (rep->tag == EXTERNAL) {
diff --git a/absl/strings/internal/cord_rep_btree.h b/absl/strings/internal/cord_rep_btree.h
index df5c994c..0e78e12c 100644
--- a/absl/strings/internal/cord_rep_btree.h
+++ b/absl/strings/internal/cord_rep_btree.h
@@ -22,6 +22,7 @@
#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/optimization.h"
+#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_flat.h"
#include "absl/strings/string_view.h"
@@ -310,13 +311,6 @@ class CordRepBtree : public CordRep {
// Requires this instance to be a leaf node, and `index` to be valid index.
inline absl::string_view Data(size_t index) const;
- static const char* EdgeDataPtr(const CordRep* r);
- static absl::string_view EdgeData(const CordRep* r);
-
- // Returns true if the provided rep is a FLAT, EXTERNAL or a SUBSTRING node
- // holding a FLAT or EXTERNAL child rep.
- static bool IsDataEdge(const CordRep* rep);
-
// Diagnostics: returns true if `tree` is valid and internally consistent.
// If `shallow` is false, then the provided top level node and all child nodes
// below it are recursively checked. If `shallow` is true, only the provided
@@ -631,34 +625,11 @@ inline absl::Span<CordRep* const> CordRepBtree::Edges(size_t begin,
return {edges_ + begin, static_cast<size_t>(end - begin)};
}
-inline const char* CordRepBtree::EdgeDataPtr(const CordRep* r) {
- assert(IsDataEdge(r));
- size_t offset = 0;
- if (r->tag == SUBSTRING) {
- offset = r->substring()->start;
- r = r->substring()->child;
- }
- return (r->tag >= FLAT ? r->flat()->Data() : r->external()->base) + offset;
-}
-
-inline absl::string_view CordRepBtree::EdgeData(const CordRep* r) {
- return absl::string_view(EdgeDataPtr(r), r->length);
-}
-
inline absl::string_view CordRepBtree::Data(size_t index) const {
assert(height() == 0);
return EdgeData(Edge(index));
}
-inline bool CordRepBtree::IsDataEdge(const CordRep* rep) {
- // The fast path is that `rep` is an EXTERNAL or FLAT node, making the below
- // if a single, well predicted branch. We then repeat the FLAT or EXTERNAL
- // check in the slow path the SUBSTRING check to optimize for the hot path.
- if (rep->tag == EXTERNAL || rep->tag >= FLAT) return true;
- if (rep->tag == SUBSTRING) rep = rep->substring()->child;
- return rep->tag == EXTERNAL || rep->tag >= FLAT;
-}
-
inline CordRepBtree* CordRepBtree::New(int height) {
CordRepBtree* tree = new CordRepBtree;
tree->length = 0;
diff --git a/absl/strings/internal/cord_rep_btree_navigator.cc b/absl/strings/internal/cord_rep_btree_navigator.cc
index 19afbe90..9b896a3d 100644
--- a/absl/strings/internal/cord_rep_btree_navigator.cc
+++ b/absl/strings/internal/cord_rep_btree_navigator.cc
@@ -16,6 +16,7 @@
#include <cassert>
+#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_btree.h"
@@ -39,7 +40,7 @@ inline CordRep* Substring(CordRep* rep, size_t offset, size_t n) {
assert(n <= rep->length);
assert(offset < rep->length);
assert(offset <= rep->length - n);
- assert(CordRepBtree::IsDataEdge(rep));
+ assert(IsDataEdge(rep));
if (n == 0) return nullptr;
if (n == rep->length) return CordRep::Ref(rep);
diff --git a/absl/strings/internal/cord_rep_btree_reader.cc b/absl/strings/internal/cord_rep_btree_reader.cc
index 5dc76966..0d0e8601 100644
--- a/absl/strings/internal/cord_rep_btree_reader.cc
+++ b/absl/strings/internal/cord_rep_btree_reader.cc
@@ -17,6 +17,7 @@
#include <cassert>
#include "absl/base/config.h"
+#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_btree.h"
#include "absl/strings/internal/cord_rep_btree_navigator.h"
@@ -44,7 +45,7 @@ absl::string_view CordRepBtreeReader::Read(size_t n, size_t chunk_size,
// can directly return the substring into the current data edge as the next
// chunk. We can easily establish from the above code that `navigator_.Next()`
// has not been called as that requires `chunk_size` to be zero.
- if (n < chunk_size) return CordRepBtree::EdgeData(edge).substr(result.n);
+ if (n < chunk_size) return EdgeData(edge).substr(result.n);
// The amount of data taken from the last edge is `chunk_size` and `result.n`
// contains the offset into the current edge trailing the read data (which can
@@ -60,7 +61,7 @@ absl::string_view CordRepBtreeReader::Read(size_t n, size_t chunk_size,
// We did not read all data, return remaining data from current edge.
edge = navigator_.Current();
remaining_ -= consumed_by_read + edge->length;
- return CordRepBtree::EdgeData(edge).substr(result.n);
+ return EdgeData(edge).substr(result.n);
}
} // namespace cord_internal
diff --git a/absl/strings/internal/cord_rep_btree_reader.h b/absl/strings/internal/cord_rep_btree_reader.h
index 7aa79dbf..8db8f8dd 100644
--- a/absl/strings/internal/cord_rep_btree_reader.h
+++ b/absl/strings/internal/cord_rep_btree_reader.h
@@ -18,6 +18,7 @@
#include <cassert>
#include "absl/base/config.h"
+#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_btree.h"
#include "absl/strings/internal/cord_rep_btree_navigator.h"
@@ -167,7 +168,7 @@ inline absl::string_view CordRepBtreeReader::Init(CordRepBtree* tree) {
assert(tree != nullptr);
const CordRep* edge = navigator_.InitFirst(tree);
remaining_ = tree->length - edge->length;
- return CordRepBtree::EdgeData(edge);
+ return EdgeData(edge);
}
inline absl::string_view CordRepBtreeReader::Next() {
@@ -175,7 +176,7 @@ inline absl::string_view CordRepBtreeReader::Next() {
const CordRep* edge = navigator_.Next();
assert(edge != nullptr);
remaining_ -= edge->length;
- return CordRepBtree::EdgeData(edge);
+ return EdgeData(edge);
}
inline absl::string_view CordRepBtreeReader::Skip(size_t skip) {
@@ -190,7 +191,7 @@ inline absl::string_view CordRepBtreeReader::Skip(size_t skip) {
// The combined length of all edges skipped before `pos.edge` is `skip -
// pos.offset`, all of which are 'consumed', as well as the current edge.
remaining_ -= skip - pos.offset + pos.edge->length;
- return CordRepBtree::EdgeData(pos.edge).substr(pos.offset);
+ return EdgeData(pos.edge).substr(pos.offset);
}
inline absl::string_view CordRepBtreeReader::Seek(size_t offset) {
@@ -199,7 +200,7 @@ inline absl::string_view CordRepBtreeReader::Seek(size_t offset) {
remaining_ = 0;
return {};
}
- absl::string_view chunk = CordRepBtree::EdgeData(pos.edge).substr(pos.offset);
+ absl::string_view chunk = EdgeData(pos.edge).substr(pos.offset);
remaining_ = length() - offset - chunk.length();
return chunk;
}
diff --git a/absl/strings/internal/cord_rep_btree_test.cc b/absl/strings/internal/cord_rep_btree_test.cc
index 1d56b252..51b90db1 100644
--- a/absl/strings/internal/cord_rep_btree_test.cc
+++ b/absl/strings/internal/cord_rep_btree_test.cc
@@ -25,6 +25,7 @@
#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/cleanup/cleanup.h"
+#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_test_util.h"
#include "absl/strings/str_cat.h"
@@ -323,30 +324,26 @@ TEST(CordRepBtreeTest, EdgeData) {
CordRep* substr2 = MakeSubstring(1, 6, CordRep::Ref(external));
CordRep* bad_substr = MakeSubstring(1, 2, CordRep::Ref(substr1));
- EXPECT_TRUE(CordRepBtree::IsDataEdge(flat));
- EXPECT_THAT(CordRepBtree::EdgeDataPtr(flat),
- TypedEq<const void*>(flat->Data()));
- EXPECT_THAT(CordRepBtree::EdgeData(flat), Eq("Hello world"));
+ EXPECT_TRUE(IsDataEdge(flat));
+ EXPECT_THAT(EdgeData(flat).data(), TypedEq<const void*>(flat->Data()));
+ EXPECT_THAT(EdgeData(flat), Eq("Hello world"));
- EXPECT_TRUE(CordRepBtree::IsDataEdge(external));
- EXPECT_THAT(CordRepBtree::EdgeDataPtr(external),
- TypedEq<const void*>(external->base));
- EXPECT_THAT(CordRepBtree::EdgeData(external), Eq("Hello external"));
+ EXPECT_TRUE(IsDataEdge(external));
+ EXPECT_THAT(EdgeData(external).data(), TypedEq<const void*>(external->base));
+ EXPECT_THAT(EdgeData(external), Eq("Hello external"));
- EXPECT_TRUE(CordRepBtree::IsDataEdge(substr1));
- EXPECT_THAT(CordRepBtree::EdgeDataPtr(substr1),
- TypedEq<const void*>(flat->Data() + 1));
- EXPECT_THAT(CordRepBtree::EdgeData(substr1), Eq("ello w"));
+ EXPECT_TRUE(IsDataEdge(substr1));
+ EXPECT_THAT(EdgeData(substr1).data(), TypedEq<const void*>(flat->Data() + 1));
+ EXPECT_THAT(EdgeData(substr1), Eq("ello w"));
- EXPECT_TRUE(CordRepBtree::IsDataEdge(substr2));
- EXPECT_THAT(CordRepBtree::EdgeDataPtr(substr2),
+ EXPECT_TRUE(IsDataEdge(substr2));
+ EXPECT_THAT(EdgeData(substr2).data(),
TypedEq<const void*>(external->base + 1));
- EXPECT_THAT(CordRepBtree::EdgeData(substr2), Eq("ello e"));
+ EXPECT_THAT(EdgeData(substr2), Eq("ello e"));
- EXPECT_FALSE(CordRepBtree::IsDataEdge(bad_substr));
+ EXPECT_FALSE(IsDataEdge(bad_substr));
#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG)
- EXPECT_DEATH(CordRepBtree::EdgeData(bad_substr), ".*");
- EXPECT_DEATH(CordRepBtree::EdgeDataPtr(bad_substr), ".*");
+ EXPECT_DEATH(EdgeData(bad_substr), ".*");
#endif
CordRep::Unref(bad_substr);
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-01 02:09:14 +0000