summaryrefslogtreecommitdiff
path: root/absl/strings
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-03-12 09:41:33 -0700
committerGravatar Derek Mauro <dmauro@google.com>2020-03-12 12:46:00 -0400
commitc6954897f7ece5011f0126db9117361dc1a6ff36 (patch)
tree77751f0d6868522e891c8dd816fbc4a01448bc18 /absl/strings
parentb92f35f65fa5298d430eab49c1831b5f3e9594c8 (diff)
Export of internal Abseil changes
-- 66a0a46462692378f77518f9db766a218bfac40b by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 300565981 -- 2a1ad67662b2e22beec7d3be019e6bba23c41c7f by Derek Mauro <dmauro@google.com>: Fix CompressedTuple move constructor on MSVC Imports GitHub #637 PiperOrigin-RevId: 300545840 -- a3ee3ad036bbb6b0031121fd58299e5c59a243e1 by Derek Mauro <dmauro@google.com>: Disable LLVM's XRay instrumentation on Android Fixes #626 PiperOrigin-RevId: 300540906 -- 87999244b1f825e585ec12a431086cb60daeb24f by Gennadiy Rozental <rogeeff@google.com>: Increase max cord depth by 2. After reviewing of the paper we can prove that the algorithm in fact can lead to slightly larger max depth. PiperOrigin-RevId: 300422376 -- 98de175ee8ad33290ef883c167c2de4414a11007 by Abseil Team <absl-team@google.com>: Use *opt/opt-> instead of opt.value() in an example, after checking the optional has a value. PiperOrigin-RevId: 300253502 -- 1107aa0acf0fe743ef50173e02e48f0d4eb572ef by Derek Mauro <dmauro@google.com>: Stop overriding the default system C++ dialect in CMake CMake on MacOS has some very strange defaults, like Wno-c++11-extensions, and doesn't seem to respect CMAKE_CXX_STANDARD, so use CMAKE_CXX_FLAGS instead. PiperOrigin-RevId: 300180753 GitOrigin-RevId: 66a0a46462692378f77518f9db766a218bfac40b Change-Id: Icd7b84c49306441b012cb87f244cc92a11697db8
Diffstat (limited to 'absl/strings')
-rw-r--r--absl/strings/cord.cc21
-rw-r--r--absl/strings/cord.h38
-rw-r--r--absl/strings/cord_test.cc10
3 files changed, 28 insertions, 41 deletions
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 9b32b3cc..415b239b 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -187,19 +187,20 @@ static constexpr size_t TagToLength(uint8_t tag) {
// Enforce that kMaxFlatSize maps to a well-known exact tag value.
static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic");
-constexpr uint64_t Fibonacci(uint8_t n, uint64_t a = 0, uint64_t b = 1) {
- return n == 0 ? a : n == 1 ? b : Fibonacci(n - 1, b, a + b);
+constexpr size_t Fibonacci(uint8_t n, const size_t a = 0, const size_t b = 1) {
+ return n == 0
+ ? a
+ : n == 1 ? b
+ : Fibonacci(n - 1, b,
+ (a > (size_t(-1) - b)) ? size_t(-1) : a + b);
}
-static_assert(Fibonacci(63) == 6557470319842,
- "Fibonacci values computed incorrectly");
-
// Minimum length required for a given depth tree -- a tree is considered
// balanced if
// length(t) >= kMinLength[depth(t)]
// The node depth is allowed to become larger to reduce rebalancing
// for larger strings (see ShouldRebalance).
-constexpr uint64_t kMinLength[] = {
+constexpr size_t kMinLength[] = {
Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5), Fibonacci(6),
Fibonacci(7), Fibonacci(8), Fibonacci(9), Fibonacci(10), Fibonacci(11),
Fibonacci(12), Fibonacci(13), Fibonacci(14), Fibonacci(15), Fibonacci(16),
@@ -218,9 +219,9 @@ constexpr uint64_t kMinLength[] = {
Fibonacci(77), Fibonacci(78), Fibonacci(79), Fibonacci(80), Fibonacci(81),
Fibonacci(82), Fibonacci(83), Fibonacci(84), Fibonacci(85), Fibonacci(86),
Fibonacci(87), Fibonacci(88), Fibonacci(89), Fibonacci(90), Fibonacci(91),
- Fibonacci(92), Fibonacci(93)};
+ Fibonacci(92), Fibonacci(93), Fibonacci(94), Fibonacci(95)};
-static_assert(sizeof(kMinLength) / sizeof(uint64_t) ==
+static_assert(sizeof(kMinLength) / sizeof(size_t) >=
(cord_internal::MaxCordDepth() + 1),
"Not enough elements in kMinLength array to cover all the "
"supported Cord depth(s)");
@@ -1169,9 +1170,9 @@ class CordForest {
void AddNode(CordRep* node) {
CordRep* sum = nullptr;
- // Collect together everything with which we will merge node
+ // Collect together everything with which we will merge with node
int i = 0;
- for (; node->length > kMinLength[i + 1]; ++i) {
+ for (; node->length >= kMinLength[i + 1]; ++i) {
auto& tree_at_i = trees_[i];
if (tree_at_i == nullptr) continue;
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 3941f19c..eb236e50 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -72,39 +72,21 @@ namespace cord_internal {
// It's expensive to keep a tree perfectly balanced, so instead we keep trees
// approximately balanced. A tree node N of depth D(N) that contains a string
// of L(N) characters is considered balanced if L >= Fibonacci(D + 2).
-// The "+ 2" is used to ensure that every leaf node contains at least one
-// character. Here we presume that
+// The "+ 2" is used to ensure that every balanced leaf node contains at least
+// one character. Here we presume that
// Fibonacci(0) = 0
// Fibonacci(1) = 1
// Fibonacci(2) = 1
// Fibonacci(3) = 2
// ...
-//
-// Fibonacci numbers are convenient because it means when two balanced trees of
-// the same depth are made the children of a new node, the resulting tree is
-// guaranteed to also be balanced:
-//
-//
-// L(left) >= Fibonacci(D(left) + 2)
-// L(right) >= Fibonacci(D(right) + 2)
-//
-// L(left) + L(right) >= Fibonacci(D(left) + 2) + Fibonacci(D(right) + 2)
-// L(left) + L(right) == L(new_tree)
-//
-// L(new_tree) >= 2 * Fibonacci(D(child) + 2)
-// D(child) == D(new_tree) - 1
-//
-// L(new_tree) >= 2 * Fibonacci(D(new_tree) + 1)
-// 2 * Fibonacci(N) >= Fibonacci(N + 1)
-//
-// L(new_tree) >= Fibonacci(D(new_tree) + 2)
-//
-//
-// The 93rd Fibonacci number is the largest Fibonacci number that can be
-// represented in 64 bits, so the size of a balanced Cord of depth 92 is too big
-// for an unsigned 64 bit integer to hold. Therefore we can safely assume that
-// the maximum depth of a Cord is 91.
-constexpr size_t MaxCordDepth() { return 91; }
+// The algorithm is based on paper by Hans Boehm et al:
+// https://www.cs.rit.edu/usr/local/pub/jeh/courses/QUARTERS/FP/Labs/CedarRope/rope-paper.pdf
+// In this paper authors shows that rebalancing based on cord forest of already
+// balanced subtrees can be proven to never produce tree of depth larger than
+// largest Fibonacci number representable in the same integral type as cord size
+// For 64 bit integers this is the 93rd Fibonacci number. For 32 bit integrals
+// this is 47th Fibonacci number.
+constexpr size_t MaxCordDepth() { return sizeof(size_t) == 8 ? 93 : 47; }
// This class models fixed max size stack of CordRep pointers.
// The elements are being pushed back and popped from the back.
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc
index d6e091f8..f2d81d4c 100644
--- a/absl/strings/cord_test.cc
+++ b/absl/strings/cord_test.cc
@@ -1403,12 +1403,16 @@ TEST(CordChunkIterator, Operations) {
}
TEST(CordChunkIterator, MaxLengthFullTree) {
+ // Start with a 1-byte cord, and then double its length in a loop. We should
+ // be able to do this until the point where we would overflow size_t.
+
absl::Cord cord;
size_t size = 1;
AddExternalMemory("x", &cord);
EXPECT_EQ(cord.size(), size);
- for (int i = 0; i < 63; ++i) {
+ const int kCordLengthDoublingLimit = std::numeric_limits<size_t>::digits - 1;
+ for (int i = 0; i < kCordLengthDoublingLimit; ++i) {
cord.Prepend(absl::Cord(cord));
size <<= 1;
@@ -1431,7 +1435,7 @@ TEST(CordChunkIterator, MaxDepth) {
AddExternalMemory("x", &left_child);
absl::Cord root = left_child;
- for (int i = 0; i < 91; ++i) {
+ for (int i = 0; i < absl::cord_internal::MaxCordDepth() - 2; ++i) {
size_t new_size = left_child.size() + root.size();
root.Prepend(left_child);
EXPECT_EQ(root.size(), new_size);
@@ -1442,7 +1446,7 @@ TEST(CordChunkIterator, MaxDepth) {
std::swap(left_child, root);
}
- EXPECT_DEATH_IF_SUPPORTED(root.Prepend(left_child), "Cord depth exceeds max");
+ EXPECT_DEATH_IF_SUPPORTED(root.Prepend(left_child), "Cord is too long");
}
TEST(CordCharIterator, Traits) {