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.

llvm-svn: 49635

1 files changed, 8 insertions, 6 deletions

diff --git a/clang/lib/Rewrite/DeltaTree.cpp b/clang/lib/Rewrite/DeltaTree.cpp
index dd096c2613d..f7715312eb8 100644
--- a/clang/lib/Rewrite/DeltaTree.cpp
+++ b/clang/lib/Rewrite/DeltaTree.cpp
@@ -58,10 +58,12 @@ namespace {
 } // 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 @@ namespace {
     
     /// 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.