1 files changed, 53 insertions, 53 deletions

diff --git a/lib/Rewrite/DeltaTree.cpp b/lib/Rewrite/DeltaTree.cpp
index 5d51ddae0896..a94444b50c77 100644
--- a/lib/Rewrite/DeltaTree.cpp
+++ b/lib/Rewrite/DeltaTree.cpp
@@ -39,7 +39,7 @@ namespace {
 /// former and adds children pointers.  Each node knows the full delta of all
 /// entries (recursively) contained inside of it, which allows us to get the
 /// full delta implied by a whole subtree in constant time.
-  
+
 namespace {
   /// SourceDelta - As code in the original input buffer is added and deleted,
   /// SourceDelta records are used to keep track of how the input SourceLocation
@@ -47,7 +47,7 @@ namespace {
   struct SourceDelta {
     unsigned FileLoc;
     int Delta;
-    
+
     static SourceDelta get(unsigned Loc, int D) {
       SourceDelta Delta;
       Delta.FileLoc = Loc;
@@ -71,36 +71,36 @@ namespace {
   ///
   class DeltaTreeNode {
     friend class DeltaTreeInteriorNode;
-    
+
     /// 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 (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.
     ///
     SourceDelta Values[2*WidthFactor-1];
-    
+
     /// NumValuesUsed - This tracks the number of values this node currently
     /// holds.
     unsigned char NumValuesUsed;
-    
+
     /// IsLeaf - This is true if this is a leaf of the btree.  If false, this is
     /// an interior node, and is actually an instance of DeltaTreeInteriorNode.
     bool IsLeaf;
-    
+
     /// FullDelta - This is the full delta of all the values in this node and
     /// all children nodes.
     int FullDelta;
   public:
     DeltaTreeNode(bool isLeaf = true)
       : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {}
-    
+
     bool isLeaf() const { return IsLeaf; }
     int getFullDelta() const { return FullDelta; }
     bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; }
-    
+
     unsigned getNumValuesUsed() const { return NumValuesUsed; }
     const SourceDelta &getValue(unsigned i) const {
       assert(i < NumValuesUsed && "Invalid value #");
@@ -110,7 +110,7 @@ namespace {
       assert(i < NumValuesUsed && "Invalid value #");
       return Values[i];
     }
-    
+
     /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into
     /// this node.  If insertion is easy, do it and return false.  Otherwise,
     /// split the node, populate InsertRes with info about the split, and return
@@ -118,14 +118,14 @@ namespace {
     bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes);
 
     void DoSplit(InsertResult &InsertRes);
-    
-    
+
+
     /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a
     /// local walk over our contained deltas.
     void RecomputeFullDeltaLocally();
-    
+
     void Destroy();
-    
+
     static inline bool classof(const DeltaTreeNode *) { return true; }
   };
 } // end anonymous namespace
@@ -142,14 +142,14 @@ namespace {
     friend class DeltaTreeNode;
   public:
     DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {}
-    
+
     DeltaTreeInteriorNode(DeltaTreeNode *FirstChild)
     : DeltaTreeNode(false /*nonleaf*/) {
       FullDelta = FirstChild->FullDelta;
       Children[0] = FirstChild;
     }
-    
-    DeltaTreeInteriorNode(const InsertResult &IR) 
+
+    DeltaTreeInteriorNode(const InsertResult &IR)
       : DeltaTreeNode(false /*nonleaf*/) {
       Children[0] = IR.LHS;
       Children[1] = IR.RHS;
@@ -157,7 +157,7 @@ namespace {
       FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta;
       NumValuesUsed = 1;
     }
-    
+
     const DeltaTreeNode *getChild(unsigned i) const {
       assert(i < getNumValuesUsed()+1 && "Invalid child");
       return Children[i];
@@ -166,7 +166,7 @@ namespace {
       assert(i < getNumValuesUsed()+1 && "Invalid child");
       return Children[i];
     }
-    
+
     static inline bool classof(const DeltaTreeInteriorNode *) { return true; }
     static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); }
   };
@@ -197,16 +197,16 @@ void DeltaTreeNode::RecomputeFullDeltaLocally() {
 /// this node.  If insertion is easy, do it and return false.  Otherwise,
 /// split the node, populate InsertRes with info about the split, and return
 /// true.
-bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, 
+bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
                                 InsertResult *InsertRes) {
   // Maintain full delta for this node.
   FullDelta += Delta;
-  
+
   // Find the insertion point, the first delta whose index is >= FileIndex.
   unsigned i = 0, e = getNumValuesUsed();
   while (i != e && FileIndex > getValue(i).FileLoc)
     ++i;
-  
+
   // If we found an a record for exactly this file index, just merge this
   // value into the pre-existing record and finish early.
   if (i != e && getValue(i).FileLoc == FileIndex) {
@@ -230,19 +230,19 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
       ++NumValuesUsed;
       return false;
     }
-    
+
     // Otherwise, if this is leaf is full, split the node at its median, insert
     // the value into one of the children, and return the result.
     assert(InsertRes && "No result location specified");
     DoSplit(*InsertRes);
-    
+
     if (InsertRes->Split.FileLoc > FileIndex)
       InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
     else
       InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/);
     return true;
   }
- 
+
   // Otherwise, this is an interior node.  Send the request down the tree.
   DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this);
   if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes))
@@ -259,21 +259,21 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
               (e-i)*sizeof(IN->Children[0]));
     IN->Children[i] = InsertRes->LHS;
     IN->Children[i+1] = InsertRes->RHS;
-    
+
     if (e != i)
       memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0]));
     Values[i] = InsertRes->Split;
     ++NumValuesUsed;
     return false;
   }
-  
+
   // Finally, if this interior node was full and a node is percolated up, split
   // ourself and return that up the chain.  Start by saving all our info to
   // avoid having the split clobber it.
   IN->Children[i] = InsertRes->LHS;
   DeltaTreeNode *SubRHS = InsertRes->RHS;
   SourceDelta SubSplit = InsertRes->Split;
-  
+
   // Do the split.
   DoSplit(*InsertRes);
 
@@ -283,22 +283,22 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
     InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS);
   else
     InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS);
-  
-  // We now have a non-empty interior node 'InsertSide' to insert 
+
+  // We now have a non-empty interior node 'InsertSide' to insert
   // SubRHS/SubSplit into.  Find out where to insert SubSplit.
-  
+
   // Find the insertion point, the first delta whose index is >SubSplit.FileLoc.
   i = 0; e = InsertSide->getNumValuesUsed();
   while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc)
     ++i;
-  
+
   // Now we know that i is the place to insert the split value into.  Insert it
   // and the child right after it.
   if (i != e)
     memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1],
             (e-i)*sizeof(IN->Children[0]));
   InsertSide->Children[i+1] = SubRHS;
-  
+
   if (e != i)
     memmove(&InsertSide->Values[i+1], &InsertSide->Values[i],
             (e-i)*sizeof(Values[0]));
@@ -313,12 +313,12 @@ bool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta,
 /// Return the pieces in InsertRes.
 void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
   assert(isFull() && "Why split a non-full node?");
-  
+
   // Since this node is full, it contains 2*WidthFactor-1 values.  We move
   // the first 'WidthFactor-1' values to the LHS child (which we leave in this
   // node), propagate one value up, and move the last 'WidthFactor-1' values
   // into the RHS child.
-  
+
   // Create the new child node.
   DeltaTreeNode *NewNode;
   if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) {
@@ -332,18 +332,18 @@ void DeltaTreeNode::DoSplit(InsertResult &InsertRes) {
     // Just create the new leaf node.
     NewNode = new DeltaTreeNode();
   }
-  
+
   // Move over the last 'WidthFactor-1' values from here to NewNode.
   memcpy(&NewNode->Values[0], &Values[WidthFactor],
          (WidthFactor-1)*sizeof(Values[0]));
-  
+
   // Decrease the number of values in the two nodes.
   NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1;
-  
+
   // Recompute the two nodes' full delta.
   NewNode->RecomputeFullDeltaLocally();
   RecomputeFullDeltaLocally();
-  
+
   InsertRes.LHS = this;
   InsertRes.RHS = NewNode;
   InsertRes.Split = Values[WidthFactor-1];
@@ -374,7 +374,7 @@ static void VerifyTree(const DeltaTreeNode *N) {
     assert(FullDelta == N->getFullDelta());
     return;
   }
-  
+
   // Verify interior nodes: Ensure that FullDelta matches up and the
   // elements are in proper order and the children are in proper order.
   int FullDelta = 0;
@@ -385,18 +385,18 @@ static void VerifyTree(const DeltaTreeNode *N) {
       assert(IN->getValue(i-1).FileLoc < IVal.FileLoc);
     FullDelta += IVal.Delta;
     FullDelta += IChild->getFullDelta();
-    
+
     // The largest value in child #i should be smaller than FileLoc.
     assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc <
            IVal.FileLoc);
-    
+
     // The smallest value in child #i+1 should be larger than FileLoc.
     assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc);
     VerifyTree(IChild);
   }
-  
+
   FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta();
-  
+
   assert(FullDelta == N->getFullDelta());
 }
 #endif  // VERIFY_TREE
@@ -424,9 +424,9 @@ DeltaTree::~DeltaTree() {
 /// specified file index.
 int DeltaTree::getDeltaAt(unsigned FileIndex) const {
   const DeltaTreeNode *Node = getRoot(Root);
-  
+
   int Result = 0;
-  
+
   // Walk down the tree.
   while (1) {
     // For all nodes, include any local deltas before the specified file
@@ -436,29 +436,29 @@ int DeltaTree::getDeltaAt(unsigned FileIndex) const {
     for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e;
          ++NumValsGreater) {
       const SourceDelta &Val = Node->getValue(NumValsGreater);
-      
+
       if (Val.FileLoc >= FileIndex)
         break;
       Result += Val.Delta;
     }
-    
+
     // If we have an interior node, include information about children and
     // recurse.  Otherwise, if we have a leaf, we're done.
     const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node);
     if (!IN) return Result;
-    
+
     // Include any children to the left of the values we skipped, all of
     // their deltas should be included as well.
     for (unsigned i = 0; i != NumValsGreater; ++i)
       Result += IN->getChild(i)->getFullDelta();
-    
+
     // If we found exactly the value we were looking for, break off the
     // search early.  There is no need to search the RHS of the value for
     // partial results.
     if (NumValsGreater != Node->getNumValuesUsed() &&
         Node->getValue(NumValsGreater).FileLoc == FileIndex)
       return Result+IN->getChild(NumValsGreater)->getFullDelta();
-    
+
     // Otherwise, traverse down the tree.  The selected subtree may be
     // partially included in the range.
     Node = IN->getChild(NumValsGreater);
@@ -472,12 +472,12 @@ int DeltaTree::getDeltaAt(unsigned FileIndex) const {
 void DeltaTree::AddDelta(unsigned FileIndex, int Delta) {
   assert(Delta && "Adding a noop?");
   DeltaTreeNode *MyRoot = getRoot(Root);
-  
+
   InsertResult InsertRes;
   if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) {
     Root = MyRoot = new DeltaTreeInteriorNode(InsertRes);
   }
-  
+
 #ifdef VERIFY_TREE
   VerifyTree(MyRoot);
 #endif