summaryrefslogtreecommitdiff
path: root/absl/strings
diff options
context:
space:
mode:
Diffstat (limited to 'absl/strings')
-rw-r--r--absl/strings/cord_test.cc72
-rw-r--r--absl/strings/internal/cord_internal.h15
-rw-r--r--absl/strings/internal/cord_rep_btree.cc18
-rw-r--r--absl/strings/internal/cord_rep_flat.h54
4 files changed, 129 insertions, 30 deletions
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc
index 188fbc2e..8a311799 100644
--- a/absl/strings/cord_test.cc
+++ b/absl/strings/cord_test.cc
@@ -43,6 +43,10 @@
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
+// convenience local constants
+static constexpr auto FLAT = absl::cord_internal::FLAT;
+static constexpr auto MAX_FLAT_TAG = absl::cord_internal::MAX_FLAT_TAG;
+
typedef std::mt19937_64 RandomEngine;
static std::string RandomLowercaseString(RandomEngine* rng);
@@ -260,6 +264,74 @@ class CordTest : public testing::TestWithParam<int> {
INSTANTIATE_TEST_SUITE_P(WithParam, CordTest, testing::Values(0, 1, 2, 3),
CordTest::ToString);
+
+TEST(CordRepFlat, AllFlatCapacities) {
+ using absl::cord_internal::CordRep;
+ using absl::cord_internal::CordRepFlat;
+ using absl::cord_internal::kFlatOverhead;
+
+ // Explicitly and redundantly assert built-in min/max limits
+ static_assert(absl::cord_internal::kFlatOverhead < 32, "");
+ static_assert(absl::cord_internal::kMinFlatSize == 32, "");
+ static_assert(absl::cord_internal::kMaxLargeFlatSize == 256 << 10, "");
+ EXPECT_EQ(absl::cord_internal::TagToAllocatedSize(FLAT), 32);
+ EXPECT_EQ(absl::cord_internal::TagToAllocatedSize(MAX_FLAT_TAG), 256 << 10);
+
+ // Verify all tags to map perfectly back and forth, and
+ // that sizes are monotonically increasing.
+ size_t last_size = 0;
+ for (int tag = FLAT; tag <= MAX_FLAT_TAG; ++tag) {
+ size_t size = absl::cord_internal::TagToAllocatedSize(tag);
+ ASSERT_GT(size, last_size);
+ ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
+ last_size = size;
+ }
+
+ // All flat size from 32 - 512 are 8 byte granularity
+ for (size_t size = 32; size <= 512; size += 8) {
+ ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size);
+ uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size);
+ ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
+ }
+
+ // All flat sizes from 512 - 8192 are 64 byte granularity
+ for (size_t size = 512; size <= 8192; size += 64) {
+ ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size);
+ uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size);
+ ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
+ }
+
+ // All flat sizes from 8KB to 256KB are 4KB granularity
+ for (size_t size = 8192; size <= 256 * 1024; size += 4 * 1024) {
+ ASSERT_EQ(absl::cord_internal::RoundUpForTag(size), size);
+ uint8_t tag = absl::cord_internal::AllocatedSizeToTag(size);
+ ASSERT_EQ(absl::cord_internal::TagToAllocatedSize(tag), size);
+ }
+}
+
+TEST(CordRepFlat, MaxFlatSize) {
+ using absl::cord_internal::CordRep;
+ using absl::cord_internal::CordRepFlat;
+ using absl::cord_internal::kMaxFlatLength;
+ CordRepFlat* flat = CordRepFlat::New(kMaxFlatLength);
+ EXPECT_EQ(flat->Capacity(), kMaxFlatLength);
+ CordRep::Unref(flat);
+
+ flat = CordRepFlat::New(kMaxFlatLength * 4);
+ EXPECT_EQ(flat->Capacity(), kMaxFlatLength);
+ CordRep::Unref(flat);
+}
+
+TEST(CordRepFlat, MaxLargeFlatSize) {
+ using absl::cord_internal::CordRep;
+ using absl::cord_internal::CordRepFlat;
+ using absl::cord_internal::kFlatOverhead;
+ const size_t size = 256 * 1024 - kFlatOverhead;
+ CordRepFlat* flat = CordRepFlat::New(CordRepFlat::Large(), size);
+ EXPECT_GE(flat->Capacity(), size);
+ CordRep::Unref(flat);
+}
+
TEST_P(CordTest, AllFlatSizes) {
using absl::strings_internal::CordTestAccess;
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index 672bf178..b16c8fa5 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -185,13 +185,16 @@ enum CordRepKind {
EXTERNAL = 5,
// We have different tags for different sized flat arrays,
- // 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).
+ // starting with FLAT, and limited to MAX_FLAT_TAG. The below values map to an
+ // allocated range of 32 bytes to 256 KB. The current granularity is:
+ // - 8 byte granularity for flat sizes in [32 - 512]
+ // - 64 byte granularity for flat sizes in (512 - 8KiB]
+ // - 4KiB byte granularity for flat sizes in (8KiB, 256 KiB]
+ // If a new tag is needed in the future, then 'FLAT' and 'MAX_FLAT_TAG' should
+ // be adjusted as well as the Tag <---> Size mapping logic so that FLAT still
+ // represents the minimum flat allocation size. (32 bytes as of now).
FLAT = 6,
- MAX_FLAT_TAG = 226
+ MAX_FLAT_TAG = 248
};
// There are various locations where we want to check if some rep is a 'plain'
diff --git a/absl/strings/internal/cord_rep_btree.cc b/absl/strings/internal/cord_rep_btree.cc
index 83cdd5f4..f436bc17 100644
--- a/absl/strings/internal/cord_rep_btree.cc
+++ b/absl/strings/internal/cord_rep_btree.cc
@@ -380,18 +380,16 @@ void CordRepBtree::Dump(const CordRep* rep, std::ostream& stream) {
template <size_t size>
static void DestroyTree(CordRepBtree* tree) {
for (CordRep* node : tree->Edges()) {
- if (!node->refcount.Decrement()) {
- for (CordRep* edge : node->btree()->Edges()) {
- if (!edge->refcount.Decrement()) {
- if (size == 1) {
- DeleteLeafEdge(edge);
- } else {
- CordRepBtree::Destroy(edge->btree());
- }
- }
+ if (node->refcount.Decrement()) continue;
+ for (CordRep* edge : node->btree()->Edges()) {
+ if (edge->refcount.Decrement()) continue;
+ if (size == 1) {
+ DeleteLeafEdge(edge);
+ } else {
+ CordRepBtree::Destroy(edge->btree());
}
- CordRepBtree::Delete(node->btree());
}
+ CordRepBtree::Delete(node->btree());
}
CordRepBtree::Delete(tree);
}
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h
index 8c254273..a15c9acd 100644
--- a/absl/strings/internal/cord_rep_flat.h
+++ b/absl/strings/internal/cord_rep_flat.h
@@ -42,14 +42,34 @@ static constexpr size_t kMinFlatSize = 32;
static constexpr size_t kMaxFlatSize = 4096;
static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead;
static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead;
+static constexpr size_t kMaxLargeFlatSize = 256 * 1024;
+static constexpr size_t kMaxLargeFlatLength = kMaxLargeFlatSize - kFlatOverhead;
+// kTagBase should make the Size <--> Tag computation resilient
+// against changes to the value of FLAT when we add a new tag..
+static constexpr uint8_t kTagBase = FLAT - 4;
+
+// Converts the provided rounded size to the corresponding tag
constexpr uint8_t AllocatedSizeToTagUnchecked(size_t size) {
- return static_cast<uint8_t>((size <= 1024) ? size / 8 + 2
- : 130 + size / 32 - 1024 / 32);
+ return static_cast<uint8_t>(size <= 512 ? kTagBase + size / 8
+ : size <= 8192
+ ? kTagBase + 512 / 8 + size / 64 - 512 / 64
+ : kTagBase + 512 / 8 + ((8192 - 512) / 64) +
+ size / 4096 - 8192 / 4096);
}
-static_assert(kMinFlatSize / 8 + 2 >= FLAT, "");
-static_assert(AllocatedSizeToTagUnchecked(kMaxFlatSize) <= MAX_FLAT_TAG, "");
+// Converts the provided tag to the corresponding allocated size
+constexpr size_t TagToAllocatedSize(uint8_t tag) {
+ return (tag <= kTagBase + 512 / 8) ? tag * 8 - kTagBase * 8
+ : (tag <= kTagBase + (512 / 8) + ((8192 - 512) / 64))
+ ? 512 + tag * 64 - kTagBase * 64 - 512 / 8 * 64
+ : 8192 + tag * 4096 - kTagBase * 4096 -
+ ((512 / 8) + ((8192 - 512) / 64)) * 4096;
+}
+
+static_assert(AllocatedSizeToTagUnchecked(kMinFlatSize) == FLAT, "");
+static_assert(AllocatedSizeToTagUnchecked(kMaxLargeFlatSize) == MAX_FLAT_TAG,
+ "");
// Helper functions for rounded div, and rounding to exact sizes.
constexpr size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; }
@@ -58,7 +78,7 @@ constexpr size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; }
// Returns the size to the nearest equal or larger value that can be
// expressed exactly as a tag value.
inline size_t RoundUpForTag(size_t size) {
- return RoundUp(size, (size <= 1024) ? 8 : 32);
+ return RoundUp(size, (size <= 512) ? 8 : (size <= 8192 ? 64 : 4096));
}
// Converts the allocated size to a tag, rounding down if the size
@@ -71,26 +91,26 @@ inline uint8_t AllocatedSizeToTag(size_t size) {
return tag;
}
-// Converts the provided tag to the corresponding allocated size
-constexpr size_t TagToAllocatedSize(uint8_t tag) {
- return (tag <= 130) ? ((tag - 2) * 8) : (1024 + (tag - 130) * 32);
-}
-
// Converts the provided tag to the corresponding available data length
constexpr size_t TagToLength(uint8_t tag) {
return TagToAllocatedSize(tag) - kFlatOverhead;
}
// Enforce that kMaxFlatSize maps to a well-known exact tag value.
-static_assert(TagToAllocatedSize(226) == kMaxFlatSize, "Bad tag logic");
+static_assert(TagToAllocatedSize(MAX_FLAT_TAG) == kMaxLargeFlatSize,
+ "Bad tag logic");
struct CordRepFlat : public CordRep {
+ // Tag for explicit 'large flat' allocation
+ struct Large {};
+
// Creates a new flat node.
- static CordRepFlat* New(size_t len) {
+ template <size_t max_flat_size>
+ static CordRepFlat* NewImpl(size_t len) {
if (len <= kMinFlatLength) {
len = kMinFlatLength;
- } else if (len > kMaxFlatLength) {
- len = kMaxFlatLength;
+ } else if (len > max_flat_size - kFlatOverhead) {
+ len = max_flat_size - kFlatOverhead;
}
// Round size up so it matches a size we can exactly express in a tag.
@@ -101,6 +121,12 @@ struct CordRepFlat : public CordRep {
return rep;
}
+ static CordRepFlat* New(size_t len) { return NewImpl<kMaxFlatSize>(len); }
+
+ static CordRepFlat* New(Large, size_t len) {
+ return NewImpl<kMaxLargeFlatSize>(len);
+ }
+
// Deletes a CordRepFlat instance created previously through a call to New().
// Flat CordReps are allocated and constructed with raw ::operator new and
// placement new, and must be destructed and deallocated accordingly.
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-04 08:31:57 +0000