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

2 files changed, 26 insertions, 9 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.
diff --git a/clang/lib/Rewrite/Rewriter.cpp b/clang/lib/Rewrite/Rewriter.cpp
index 1c1903cc40d..f7dcdd23fc2 100644
--- a/clang/lib/Rewrite/Rewriter.cpp
+++ b/clang/lib/Rewrite/Rewriter.cpp
@@ -27,8 +27,12 @@ void RewriteBuffer::RemoveText(unsigned OrigOffset, unsigned Size) {
   assert(RealOffset+Size < Buffer.size() && "Invalid location");
   
   // Remove the dead characters.
+#ifdef USE_ROPE_VECTOR
   RewriteRope::iterator I = Buffer.getAtOffset(RealOffset);
   Buffer.erase(I, I+Size);
+#else
+  Buffer.erase(RealOffset, Size);
+#endif
 
   // Add a delta so that future changes are offset correctly.
   AddDelta(OrigOffset, -Size);
@@ -40,23 +44,29 @@ void RewriteBuffer::InsertText(unsigned OrigOffset,
   
   // Nothing to insert, exit early.
   if (StrLen == 0) return;
-  
+
   unsigned RealOffset = getMappedOffset(OrigOffset, InsertAfter);
+
+#ifdef USE_ROPE_VECTOR
   assert(RealOffset <= Buffer.size() && "Invalid location");
 
   // Insert the new characters.
   Buffer.insert(Buffer.getAtOffset(RealOffset), StrData, StrData+StrLen);
+#else
+  Buffer.insert(RealOffset, StrData, StrData+StrLen);
+#endif
   
   // Add a delta so that future changes are offset correctly.
   AddDelta(OrigOffset, StrLen);
 }
 
 /// ReplaceText - This method replaces a range of characters in the input
-/// buffer with a new string.  This is effectively a combined "remove/insert"
+/// buffer with a new string.  This is effectively a combined "remove+insert"
 /// operation.
 void RewriteBuffer::ReplaceText(unsigned OrigOffset, unsigned OrigLength,
                                 const char *NewStr, unsigned NewLength) {
   unsigned RealOffset = getMappedOffset(OrigOffset, true);
+#ifdef USE_ROPE_VECTOR
   assert(RealOffset+OrigLength <= Buffer.size() && "Invalid location");
 
   // Overwrite the common piece.
@@ -76,7 +86,12 @@ void RewriteBuffer::ReplaceText(unsigned OrigOffset, unsigned OrigLength,
     RewriteRope::iterator I = Buffer.getAtOffset(RealOffset+NewLength);
     Buffer.erase(I, I+(OrigLength-NewLength));
   }
-  AddDelta(OrigOffset, NewLength-OrigLength);
+#else
+  Buffer.erase(RealOffset, OrigLength);
+  Buffer.insert(RealOffset, NewStr, NewStr+NewLength);
+#endif
+  if (OrigLength != NewLength)
+    AddDelta(OrigOffset, NewLength-OrigLength);
 }