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

1 files changed, 10 insertions, 28 deletions

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.