From 3374b039d943828871cda91d968109910fee8929 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 14 Apr 2008 07:17:29 +0000 Subject: 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 --- clang/lib/Rewrite/DeltaTree.cpp | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) (limited to 'clang/lib/Rewrite/DeltaTree.cpp') 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. -- cgit v1.2.3