Remove tabs, and whitespace cleanups.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@81346 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Rewrite/DeltaTree.cpp b/lib/Rewrite/DeltaTree.cpp
index 5d51dda..a94444b 100644
--- a/lib/Rewrite/DeltaTree.cpp
+++ b/lib/Rewrite/DeltaTree.cpp
@@ -39,7 +39,7 @@
/// 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 @@
struct SourceDelta {
unsigned FileLoc;
int Delta;
-
+
static SourceDelta get(unsigned Loc, int D) {
SourceDelta Delta;
Delta.FileLoc = Loc;
@@ -71,36 +71,36 @@
///
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
/// 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 @@
++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 @@
(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 @@
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 @@
/// 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 @@
// 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 @@
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 @@
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 @@
/// 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 @@
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 @@
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