diff options
Diffstat (limited to 'absl/strings')
-rw-r--r-- | absl/strings/BUILD.bazel | 16 | ||||
-rw-r--r-- | absl/strings/CMakeLists.txt | 16 | ||||
-rw-r--r-- | absl/strings/cord.cc | 20 | ||||
-rw-r--r-- | absl/strings/internal/cord_internal.cc | 4 | ||||
-rw-r--r-- | absl/strings/internal/cord_internal.h | 17 | ||||
-rw-r--r-- | absl/strings/internal/cord_rep_crc.cc | 54 | ||||
-rw-r--r-- | absl/strings/internal/cord_rep_crc.h | 93 | ||||
-rw-r--r-- | absl/strings/internal/cord_rep_crc_test.cc | 115 | ||||
-rw-r--r-- | absl/strings/internal/cord_rep_flat.h | 10 |
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. |