summaryrefslogtreecommitdiff
path: root/absl/strings
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings')
-rw-r--r--absl/strings/BUILD.bazel16
-rw-r--r--absl/strings/CMakeLists.txt16
-rw-r--r--absl/strings/cord.cc20
-rw-r--r--absl/strings/internal/cord_internal.cc4
-rw-r--r--absl/strings/internal/cord_internal.h17
-rw-r--r--absl/strings/internal/cord_rep_crc.cc54
-rw-r--r--absl/strings/internal/cord_rep_crc.h93
-rw-r--r--absl/strings/internal/cord_rep_crc_test.cc115
-rw-r--r--absl/strings/internal/cord_rep_flat.h10
9 files changed, 333 insertions, 12 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 090fc58a..1948fe32 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -272,6 +272,7 @@ cc_library(
"internal/cord_rep_btree_navigator.cc",
"internal/cord_rep_btree_reader.cc",
"internal/cord_rep_consume.cc",
+ "internal/cord_rep_crc.cc",
"internal/cord_rep_ring.cc",
],
hdrs = [
@@ -280,6 +281,7 @@ cc_library(
"internal/cord_rep_btree_navigator.h",
"internal/cord_rep_btree_reader.h",
"internal/cord_rep_consume.h",
+ "internal/cord_rep_crc.h",
"internal/cord_rep_flat.h",
"internal/cord_rep_ring.h",
"internal/cord_rep_ring_reader.h",
@@ -366,6 +368,20 @@ cc_test(
],
)
+cc_test(
+ name = "cord_rep_crc_test",
+ size = "small",
+ srcs = ["internal/cord_rep_crc_test.cc"],
+ copts = ABSL_TEST_COPTS,
+ visibility = ["//visibility:private"],
+ deps = [
+ ":cord_internal",
+ ":cord_rep_test_util",
+ "//absl/base:config",
+ "@com_google_googletest//:gtest_main",
+ ],
+)
+
cc_library(
name = "cordz_update_tracker",
hdrs = ["internal/cordz_update_tracker.h"],
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index d6801fe6..1ef3332c 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -558,6 +558,7 @@ absl_cc_library(
"internal/cord_rep_btree.h"
"internal/cord_rep_btree_navigator.h"
"internal/cord_rep_btree_reader.h"
+ "internal/cord_rep_crc.h"
"internal/cord_rep_consume.h"
"internal/cord_rep_flat.h"
"internal/cord_rep_ring.h"
@@ -567,6 +568,7 @@ absl_cc_library(
"internal/cord_rep_btree.cc"
"internal/cord_rep_btree_navigator.cc"
"internal/cord_rep_btree_reader.cc"
+ "internal/cord_rep_crc.cc"
"internal/cord_rep_consume.cc"
"internal/cord_rep_ring.cc"
COPTS
@@ -1013,6 +1015,20 @@ absl_cc_test(
absl_cc_test(
NAME
+ cord_rep_crc_test
+ SRCS
+ "internal/cord_rep_crc_test.cc"
+ COPTS
+ ${ABSL_TEST_COPTS}
+ DEPS
+ absl::config
+ absl::cord_internal
+ absl::cord_rep_test_util
+ GTest::gmock_main
+)
+
+absl_cc_test(
+ NAME
cord_ring_test
SRCS
"cord_ring_test.cc"
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 854047ca..63a82133 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -37,6 +37,7 @@
#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_crc.h"
#include "absl/strings/internal/cord_rep_flat.h"
#include "absl/strings/internal/cordz_statistics.h"
#include "absl/strings/internal/cordz_update_scope.h"
@@ -53,6 +54,7 @@ ABSL_NAMESPACE_BEGIN
using ::absl::cord_internal::CordRep;
using ::absl::cord_internal::CordRepBtree;
using ::absl::cord_internal::CordRepConcat;
+using ::absl::cord_internal::CordRepCrc;
using ::absl::cord_internal::CordRepExternal;
using ::absl::cord_internal::CordRepFlat;
using ::absl::cord_internal::CordRepSubstring;
@@ -1870,7 +1872,11 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
*os << "]";
*os << " " << (IsRootBalanced(rep) ? 'b' : 'u');
*os << " " << std::setw(indent) << "";
- if (rep->IsConcat()) {
+ if (rep->IsCrc()) {
+ *os << "CRC crc=" << rep->crc()->crc << "\n";
+ indent += kIndentStep;
+ rep = rep->crc()->child;
+ } else if (rep->IsConcat()) {
*os << "CONCAT depth=" << Depth(rep) << "\n";
indent += kIndentStep;
indents.push_back(indent);
@@ -1922,6 +1928,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
ABSL_INTERNAL_CHECK(node != nullptr, ReportError(root, node));
if (node != root) {
ABSL_INTERNAL_CHECK(node->length != 0, ReportError(root, node));
+ ABSL_INTERNAL_CHECK(!node->IsCrc(), ReportError(root, node));
}
if (node->IsConcat()) {
@@ -1949,6 +1956,12 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
ABSL_INTERNAL_CHECK(node->substring()->start + node->length <=
node->substring()->child->length,
ReportError(root, node));
+ } else if (node->IsCrc()) {
+ ABSL_INTERNAL_CHECK(node->crc()->child != nullptr,
+ ReportError(root, node));
+ ABSL_INTERNAL_CHECK(node->crc()->length == node->crc()->child->length,
+ ReportError(root, node));
+ worklist.push_back(node->crc()->child);
}
} while (!worklist.empty());
return true;
@@ -1958,6 +1971,11 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
/* static */ size_t Cord::MemoryUsageAux(const CordRep* rep) {
size_t total_mem_usage = 0;
+ if (rep->IsCrc()) {
+ total_mem_usage += sizeof(CordRepCrc);
+ rep = rep->crc()->child;
+ }
+
// Allow a quick exit for the common case that the root is a leaf.
if (RepMemoryUsageLeaf(rep, &total_mem_usage)) {
return total_mem_usage;
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 1767e6fc..c9ceac90 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -19,6 +19,7 @@
#include "absl/container/inlined_vector.h"
#include "absl/strings/internal/cord_rep_btree.h"
+#include "absl/strings/internal/cord_rep_crc.h"
#include "absl/strings/internal/cord_rep_flat.h"
#include "absl/strings/internal/cord_rep_ring.h"
@@ -70,6 +71,9 @@ void CordRep::Destroy(CordRep* rep) {
rep = child;
continue;
}
+ } else if (rep->tag == CRC) {
+ CordRepCrc::Destroy(rep->crc());
+ rep = nullptr;
} else {
CordRepFlat::Delete(rep);
rep = nullptr;
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index bfe5564e..bf135ae2 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -192,6 +192,7 @@ struct CordRepConcat;
struct CordRepExternal;
struct CordRepFlat;
struct CordRepSubstring;
+struct CordRepCrc;
class CordRepRing;
class CordRepBtree;
@@ -199,18 +200,19 @@ class CordRepBtree;
enum CordRepKind {
CONCAT = 0,
SUBSTRING = 1,
- BTREE = 2,
- RING = 3,
- EXTERNAL = 4,
+ CRC = 2,
+ BTREE = 3,
+ RING = 4,
+ EXTERNAL = 5,
// We have different tags for different sized flat arrays,
- // starting with FLAT, and limited to MAX_FLAT_TAG. The 225 value is based on
+ // starting with FLAT, and limited to MAX_FLAT_TAG. The 226 value is based on
// the current 'size to tag' encoding of 8 / 32 bytes. If a new tag is needed
// in the future, then 'FLAT' and 'MAX_FLAT_TAG' should be adjusted as well
// as the Tag <---> Size logic so that FLAT stil represents the minimum flat
// allocation size. (32 bytes as of now).
- FLAT = 5,
- MAX_FLAT_TAG = 225
+ FLAT = 6,
+ MAX_FLAT_TAG = 226
};
// There are various locations where we want to check if some rep is a 'plain'
@@ -251,6 +253,7 @@ struct CordRep {
constexpr bool IsRing() const { return tag == RING; }
constexpr bool IsConcat() const { return tag == CONCAT; }
constexpr bool IsSubstring() const { return tag == SUBSTRING; }
+ constexpr bool IsCrc() const { return tag == CRC; }
constexpr bool IsExternal() const { return tag == EXTERNAL; }
constexpr bool IsFlat() const { return tag >= FLAT; }
constexpr bool IsBtree() const { return tag == BTREE; }
@@ -261,6 +264,8 @@ struct CordRep {
inline const CordRepConcat* concat() const;
inline CordRepSubstring* substring();
inline const CordRepSubstring* substring() const;
+ inline CordRepCrc* crc();
+ inline const CordRepCrc* crc() const;
inline CordRepExternal* external();
inline const CordRepExternal* external() const;
inline CordRepFlat* flat();
diff --git a/absl/strings/internal/cord_rep_crc.cc b/absl/strings/internal/cord_rep_crc.cc
new file mode 100644
index 00000000..ee140354
--- /dev/null
+++ b/absl/strings/internal/cord_rep_crc.cc
@@ -0,0 +1,54 @@
+// 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.
+
+#include "absl/strings/internal/cord_rep_crc.h"
+
+#include <cassert>
+#include <cstdint>
+
+#include "absl/base/config.h"
+#include "absl/strings/internal/cord_internal.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+
+CordRepCrc* CordRepCrc::New(CordRep* child, uint32_t crc) {
+ assert(child != nullptr);
+ if (child->IsCrc()) {
+ if (child->refcount.IsOne()) {
+ child->crc()->crc = crc;
+ return child->crc();
+ }
+ CordRep* old = child;
+ child = old->crc()->child;
+ CordRep::Ref(child);
+ CordRep::Unref(old);
+ }
+ auto* new_cordrep = new CordRepCrc;
+ new_cordrep->length = child->length;
+ new_cordrep->tag = cord_internal::CRC;
+ new_cordrep->child = child;
+ new_cordrep->crc = crc;
+ return new_cordrep;
+}
+
+void CordRepCrc::Destroy(CordRepCrc* node) {
+ CordRep::Unref(node->child);
+ delete node;
+}
+
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/strings/internal/cord_rep_crc.h b/absl/strings/internal/cord_rep_crc.h
new file mode 100644
index 00000000..3ead94a1
--- /dev/null
+++ b/absl/strings/internal/cord_rep_crc.h
@@ -0,0 +1,93 @@
+// 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_CRC_H_
+#define ABSL_STRINGS_INTERNAL_CORD_REP_CRC_H_
+
+#include <cassert>
+#include <cstdint>
+
+#include "absl/base/config.h"
+#include "absl/base/optimization.h"
+#include "absl/strings/internal/cord_internal.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+
+// CordRepCrc is a CordRep node intended only to appear at the top level of a
+// cord tree. It associates an "expected CRC" with the contained data, to allow
+// for easy passage of checksum data in Cord data flows.
+//
+// From Cord's perspective, the crc value has no semantics; any validation of
+// the contained checksum is the user's responsibility.
+struct CordRepCrc : public CordRep {
+ CordRep* child;
+ uint32_t crc;
+
+ // Consumes `child` and returns a CordRepCrc prefixed tree containing `child`.
+ // If the specified `child` is itself a CordRepCrc node, then this method
+ // either replaces the existing node, or directly updates the crc value in it
+ // depending on the node being shared or not, i.e.: refcount.IsOne().
+ // `child` must not be null. Never returns null.
+ static CordRepCrc* New(CordRep* child, uint32_t crc);
+
+ // Destroys (deletes) the provided node. `node` must not be null.
+ static void Destroy(CordRepCrc* node);
+};
+
+// Consumes `rep` and returns a CordRep* with any outer CordRepCrc wrapper
+// removed. This is usually a no-op (returning `rep`), but this will remove and
+// unref an outer CordRepCrc node.
+inline CordRep* RemoveCrcNode(CordRep* rep) {
+ assert(rep != nullptr);
+ if (ABSL_PREDICT_FALSE(rep->IsCrc())) {
+ CordRep* child = rep->crc()->child;
+ if (rep->refcount.IsOne()) {
+ delete rep->crc();
+ } else {
+ CordRep::Ref(child);
+ CordRep::Unref(rep);
+ }
+ return child;
+ }
+ return rep;
+}
+
+// Returns `rep` if it is not a CordRepCrc node, or its child if it is.
+// Does not consume or create a reference on `rep` or the returned value.
+inline CordRep* SkipCrcNode(CordRep* rep) {
+ assert(rep != nullptr);
+ if (ABSL_PREDICT_FALSE(rep->IsCrc())) {
+ return rep->crc()->child;
+ } else {
+ return rep;
+ }
+}
+
+inline CordRepCrc* CordRep::crc() {
+ assert(IsCrc());
+ return static_cast<CordRepCrc*>(this);
+}
+
+inline const CordRepCrc* CordRep::crc() const {
+ assert(IsCrc());
+ return static_cast<const CordRepCrc*>(this);
+}
+
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif // ABSL_STRINGS_INTERNAL_CORD_REP_CRC_H_
diff --git a/absl/strings/internal/cord_rep_crc_test.cc b/absl/strings/internal/cord_rep_crc_test.cc
new file mode 100644
index 00000000..80f53485
--- /dev/null
+++ b/absl/strings/internal/cord_rep_crc_test.cc
@@ -0,0 +1,115 @@
+// 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.
+
+#include "absl/strings/internal/cord_rep_crc.h"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/config.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::MakeFlat;
+using ::testing::Eq;
+using ::testing::Ne;
+
+#if !defined(NDEBUG) && GTEST_HAS_DEATH_TEST
+
+TEST(CordRepCrc, NewWithNullPtr) {
+ EXPECT_DEATH(CordRepCrc::New(nullptr, 0), "");
+}
+
+TEST(CordRepCrc, RemoveCrcWithNullptr) {
+ EXPECT_DEATH(RemoveCrcNode(nullptr), "");
+}
+
+#endif // !NDEBUG && GTEST_HAS_DEATH_TEST
+
+TEST(CordRepCrc, NewDestroy) {
+ CordRep* rep = cordrep_testing::MakeFlat("Hello world");
+ CordRepCrc* crc = CordRepCrc::New(rep, 12345);
+ EXPECT_TRUE(crc->refcount.IsOne());
+ EXPECT_THAT(crc->child, Eq(rep));
+ EXPECT_THAT(crc->crc, Eq(12345));
+ EXPECT_TRUE(rep->refcount.IsOne());
+ CordRepCrc::Destroy(crc);
+}
+
+TEST(CordRepCrc, NewExistingCrcNotShared) {
+ CordRep* rep = cordrep_testing::MakeFlat("Hello world");
+ CordRepCrc* crc = CordRepCrc::New(rep, 12345);
+ CordRepCrc* new_crc = CordRepCrc::New(crc, 54321);
+ EXPECT_THAT(new_crc, Eq(crc));
+ EXPECT_TRUE(new_crc->refcount.IsOne());
+ EXPECT_THAT(new_crc->child, Eq(rep));
+ EXPECT_THAT(new_crc->crc, Eq(54321));
+ EXPECT_TRUE(rep->refcount.IsOne());
+ CordRepCrc::Destroy(new_crc);
+}
+
+TEST(CordRepCrc, NewExistingCrcShared) {
+ CordRep* rep = cordrep_testing::MakeFlat("Hello world");
+ CordRepCrc* crc = CordRepCrc::New(rep, 12345);
+ CordRep::Ref(crc);
+ CordRepCrc* new_crc = CordRepCrc::New(crc, 54321);
+
+ EXPECT_THAT(new_crc, Ne(crc));
+ EXPECT_TRUE(new_crc->refcount.IsOne());
+ EXPECT_TRUE(crc->refcount.IsOne());
+ EXPECT_FALSE(rep->refcount.IsOne());
+ EXPECT_THAT(crc->child, Eq(rep));
+ EXPECT_THAT(new_crc->child, Eq(rep));
+ EXPECT_THAT(crc->crc, Eq(12345));
+ EXPECT_THAT(new_crc->crc, Eq(54321));
+
+ CordRep::Unref(crc);
+ CordRep::Unref(new_crc);
+}
+
+TEST(CordRepCrc, RemoveCrcNotCrc) {
+ CordRep* rep = cordrep_testing::MakeFlat("Hello world");
+ CordRep* nocrc = RemoveCrcNode(rep);
+ EXPECT_THAT(nocrc, Eq(rep));
+ CordRep::Unref(nocrc);
+}
+
+TEST(CordRepCrc, RemoveCrcNotShared) {
+ CordRep* rep = cordrep_testing::MakeFlat("Hello world");
+ CordRepCrc* crc = CordRepCrc::New(rep, 12345);
+ CordRep* nocrc = RemoveCrcNode(crc);
+ EXPECT_THAT(nocrc, Eq(rep));
+ EXPECT_TRUE(rep->refcount.IsOne());
+ CordRep::Unref(nocrc);
+}
+
+TEST(CordRepCrc, RemoveCrcShared) {
+ CordRep* rep = cordrep_testing::MakeFlat("Hello world");
+ CordRepCrc* crc = CordRepCrc::New(rep, 12345);
+ CordRep::Ref(crc);
+ CordRep* nocrc = RemoveCrcNode(crc);
+ EXPECT_THAT(nocrc, Eq(rep));
+ EXPECT_FALSE(rep->refcount.IsOne());
+ CordRep::Unref(nocrc);
+ CordRep::Unref(crc);
+}
+
+} // namespace
+} // namespace cord_internal
+ABSL_NAMESPACE_END
+} // namespace absl
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h
index 4d0f9886..62cf5840 100644
--- a/absl/strings/internal/cord_rep_flat.h
+++ b/absl/strings/internal/cord_rep_flat.h
@@ -44,11 +44,11 @@ static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead;
static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead;
constexpr uint8_t AllocatedSizeToTagUnchecked(size_t size) {
- return static_cast<uint8_t>((size <= 1024) ? size / 8 + 1
- : 129 + size / 32 - 1024 / 32);
+ return static_cast<uint8_t>((size <= 1024) ? size / 8 + 2
+ : 130 + size / 32 - 1024 / 32);
}
-static_assert(kMinFlatSize / 8 + 1 >= FLAT, "");
+static_assert(kMinFlatSize / 8 + 2 >= FLAT, "");
static_assert(AllocatedSizeToTagUnchecked(kMaxFlatSize) <= MAX_FLAT_TAG, "");
// Helper functions for rounded div, and rounding to exact sizes.
@@ -73,7 +73,7 @@ inline uint8_t AllocatedSizeToTag(size_t size) {
// Converts the provided tag to the corresponding allocated size
constexpr size_t TagToAllocatedSize(uint8_t tag) {
- return (tag <= 129) ? ((tag - 1) * 8) : (1024 + (tag - 129) * 32);
+ return (tag <= 130) ? ((tag - 2) * 8) : (1024 + (tag - 130) * 32);
}
// Converts the provided tag to the corresponding available data length
@@ -82,7 +82,7 @@ constexpr size_t TagToLength(uint8_t tag) {
}
// Enforce that kMaxFlatSize maps to a well-known exact tag value.
-static_assert(TagToAllocatedSize(225) == kMaxFlatSize, "Bad tag logic");
+static_assert(TagToAllocatedSize(226) == kMaxFlatSize, "Bad tag logic");
struct CordRepFlat : public CordRep {
// Creates a new flat node.
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-22 07:30:58 +0000