Change the RewriteRope::Chunks data structure from an std::list into
a nice shiny B+ Tree variant. This fixes the last of the known algorithmic
issues with the rewriter, allowing a significant speedup. For example,
-emit-html on Ted's 500K .i file speeds up from 26.8s -> 0.64s in a
debug build (41x!) and 5.475s -> 0.132s (41x!) in an optimized build.
This code is functional but needs to be cleaned up, ifdefs removed, better
commented, and moved to a .cpp file. I plan to do this tomorrow.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@49635 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Rewrite/DeltaTree.cpp b/lib/Rewrite/DeltaTree.cpp
index dd096c2..f771531 100644
--- a/lib/Rewrite/DeltaTree.cpp
+++ b/lib/Rewrite/DeltaTree.cpp
@@ -58,10 +58,12 @@
} // end anonymous namespace
-struct InsertResult {
- DeltaTreeNode *LHS, *RHS;
- SourceDelta Split;
-};
+namespace {
+ struct InsertResult {
+ DeltaTreeNode *LHS, *RHS;
+ SourceDelta Split;
+ };
+} // end anonymous namespace
namespace {
@@ -72,8 +74,8 @@
/// WidthFactor - This controls the number of K/V slots held in the BTree:
/// how wide it is. Each level of the BTree is guaranteed to have at least
- /// WidthFactor-1 K/V pairs (unless the whole tree is less full than that)
- /// and may have at most 2*WidthFactor-1 K/V pairs.
+ /// WidthFactor-1 K/V pairs (except the root) and may have at most
+ /// 2*WidthFactor-1 K/V pairs.
enum { WidthFactor = 8 };
/// Values - This tracks the SourceDelta's currently in this node.