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/RewriteRope.cpp b/lib/Rewrite/RewriteRope.cpp
index 61cb02b..30bbcfa 100644
--- a/lib/Rewrite/RewriteRope.cpp
+++ b/lib/Rewrite/RewriteRope.cpp
@@ -81,24 +81,24 @@
/// the root, which may have less) and may have at most 2*WidthFactor
/// elements.
enum { WidthFactor = 8 };
-
+
/// Size - This is the number of bytes of file this node (including any
/// potential children) covers.
unsigned Size;
-
+
/// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
/// is an instance of RopePieceBTreeInterior.
bool IsLeaf;
-
+
RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {}
~RopePieceBTreeNode() {}
public:
-
+
bool isLeaf() const { return IsLeaf; }
unsigned size() const { return Size; }
-
+
void Destroy();
-
+
/// split - Split the range containing the specified offset so that we are
/// guaranteed that there is a place to do an insertion at the specified
/// offset. The offset is relative, so "0" is the start of the node.
@@ -106,7 +106,7 @@
/// If there is no space in this subtree for the extra piece, the extra tree
/// node is returned and must be inserted into a parent.
RopePieceBTreeNode *split(unsigned Offset);
-
+
/// insert - Insert the specified ropepiece into this tree node at the
/// specified offset. The offset is relative, so "0" is the start of the
/// node.
@@ -114,13 +114,13 @@
/// If there is no space in this subtree for the extra piece, the extra tree
/// node is returned and must be inserted into a parent.
RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
-
+
/// erase - Remove NumBytes from this node at the specified offset. We are
/// guaranteed that there is a split at Offset.
void erase(unsigned Offset, unsigned NumBytes);
-
+
static inline bool classof(const RopePieceBTreeNode *) { return true; }
-
+
};
} // end anonymous namespace
@@ -140,11 +140,11 @@
/// NumPieces - This holds the number of rope pieces currently active in the
/// Pieces array.
unsigned char NumPieces;
-
+
/// Pieces - This tracks the file chunks currently in this leaf.
///
RopePiece Pieces[2*WidthFactor];
-
+
/// NextLeaf - This is a pointer to the next leaf in the tree, allowing
/// efficient in-order forward iteration of the tree without traversal.
RopePieceBTreeLeaf **PrevLeaf, *NextLeaf;
@@ -155,34 +155,34 @@
if (PrevLeaf || NextLeaf)
removeFromLeafInOrder();
}
-
+
bool isFull() const { return NumPieces == 2*WidthFactor; }
-
+
/// clear - Remove all rope pieces from this leaf.
void clear() {
while (NumPieces)
Pieces[--NumPieces] = RopePiece();
Size = 0;
}
-
+
unsigned getNumPieces() const { return NumPieces; }
-
+
const RopePiece &getPiece(unsigned i) const {
assert(i < getNumPieces() && "Invalid piece ID");
return Pieces[i];
}
-
+
const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
assert(PrevLeaf == 0 && NextLeaf == 0 && "Already in ordering");
-
+
NextLeaf = Node->NextLeaf;
if (NextLeaf)
NextLeaf->PrevLeaf = &NextLeaf;
PrevLeaf = &Node->NextLeaf;
Node->NextLeaf = this;
}
-
+
void removeFromLeafInOrder() {
if (PrevLeaf) {
*PrevLeaf = NextLeaf;
@@ -192,7 +192,7 @@
NextLeaf->PrevLeaf = 0;
}
}
-
+
/// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
/// summing the size of all RopePieces.
void FullRecomputeSizeLocally() {
@@ -200,7 +200,7 @@
for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
Size += getPiece(i).size();
}
-
+
/// split - Split the range containing the specified offset so that we are
/// guaranteed that there is a place to do an insertion at the specified
/// offset. The offset is relative, so "0" is the start of the node.
@@ -208,7 +208,7 @@
/// If there is no space in this subtree for the extra piece, the extra tree
/// node is returned and must be inserted into a parent.
RopePieceBTreeNode *split(unsigned Offset);
-
+
/// insert - Insert the specified ropepiece into this tree node at the
/// specified offset. The offset is relative, so "0" is the start of the
/// node.
@@ -216,12 +216,12 @@
/// If there is no space in this subtree for the extra piece, the extra tree
/// node is returned and must be inserted into a parent.
RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
-
-
+
+
/// erase - Remove NumBytes from this node at the specified offset. We are
/// guaranteed that there is a split at Offset.
void erase(unsigned Offset, unsigned NumBytes);
-
+
static inline bool classof(const RopePieceBTreeLeaf *) { return true; }
static inline bool classof(const RopePieceBTreeNode *N) {
return N->isLeaf();
@@ -242,7 +242,7 @@
// Fastpath for a common case. There is already a splitpoint at the end.
return 0;
}
-
+
// Find the piece that this offset lands in.
unsigned PieceOffs = 0;
unsigned i = 0;
@@ -250,23 +250,23 @@
PieceOffs += Pieces[i].size();
++i;
}
-
+
// If there is already a split point at the specified offset, just return
// success.
if (PieceOffs == Offset)
return 0;
-
+
// Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset
// to being Piece relative.
unsigned IntraPieceOffset = Offset-PieceOffs;
-
+
// We do this by shrinking the RopePiece and then doing an insert of the tail.
RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
Pieces[i].EndOffs);
Size -= Pieces[i].size();
Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
Size += Pieces[i].size();
-
+
return insert(Offset, Tail);
}
@@ -292,7 +292,7 @@
SlotOffs += getPiece(i).size();
assert(SlotOffs == Offset && "Split didn't occur before insertion!");
}
-
+
// For an insertion into a non-full leaf node, just insert the value in
// its sorted position. This requires moving later values over.
for (; i != e; --e)
@@ -302,31 +302,31 @@
Size += R.size();
return 0;
}
-
+
// Otherwise, if this is leaf is full, split it in two halves. Since this
// node is full, it contains 2*WidthFactor values. We move the first
// 'WidthFactor' values to the LHS child (which we leave in this node) and
// move the last 'WidthFactor' values into the RHS child.
-
+
// Create the new node.
RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
-
+
// Move over the last 'WidthFactor' values from here to NewNode.
std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
&NewNode->Pieces[0]);
// Replace old pieces with null RopePieces to drop refcounts.
std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
-
+
// Decrease the number of values in the two nodes.
NewNode->NumPieces = NumPieces = WidthFactor;
-
+
// Recompute the two nodes' size.
NewNode->FullRecomputeSizeLocally();
FullRecomputeSizeLocally();
-
+
// Update the list of leaves.
NewNode->insertAfterLeafInOrder(this);
-
+
// These insertions can't fail.
if (this->size() >= Offset)
this->insert(Offset, R);
@@ -345,42 +345,42 @@
for (; Offset > PieceOffs; ++i)
PieceOffs += getPiece(i).size();
assert(PieceOffs == Offset && "Split didn't occur before erase!");
-
+
unsigned StartPiece = i;
-
+
// Figure out how many pieces completely cover 'NumBytes'. We want to remove
// all of them.
for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
PieceOffs += getPiece(i).size();
-
+
// If we exactly include the last one, include it in the region to delete.
if (Offset+NumBytes == PieceOffs+getPiece(i).size())
PieceOffs += getPiece(i).size(), ++i;
-
+
// If we completely cover some RopePieces, erase them now.
if (i != StartPiece) {
unsigned NumDeleted = i-StartPiece;
for (; i != getNumPieces(); ++i)
Pieces[i-NumDeleted] = Pieces[i];
-
+
// Drop references to dead rope pieces.
std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
RopePiece());
NumPieces -= NumDeleted;
-
+
unsigned CoverBytes = PieceOffs-Offset;
NumBytes -= CoverBytes;
Size -= CoverBytes;
}
-
+
// If we completely removed some stuff, we could be done.
if (NumBytes == 0) return;
-
+
// Okay, now might be erasing part of some Piece. If this is the case, then
// move the start point of the piece.
assert(getPiece(StartPiece).size() > NumBytes);
Pieces[StartPiece].StartOffs += NumBytes;
-
+
// The size of this node just shrunk by NumBytes.
Size -= NumBytes;
}
@@ -399,7 +399,7 @@
RopePieceBTreeNode *Children[2*WidthFactor];
public:
RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {}
-
+
RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
: RopePieceBTreeNode(false) {
Children[0] = LHS;
@@ -407,9 +407,9 @@
NumChildren = 2;
Size = LHS->size() + RHS->size();
}
-
+
bool isFull() const { return NumChildren == 2*WidthFactor; }
-
+
unsigned getNumChildren() const { return NumChildren; }
const RopePieceBTreeNode *getChild(unsigned i) const {
assert(i < NumChildren && "invalid child #");
@@ -419,7 +419,7 @@
assert(i < NumChildren && "invalid child #");
return Children[i];
}
-
+
/// FullRecomputeSizeLocally - Recompute the Size field of this node by
/// summing up the sizes of the child nodes.
void FullRecomputeSizeLocally() {
@@ -427,8 +427,8 @@
for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
Size += getChild(i)->size();
}
-
-
+
+
/// split - Split the range containing the specified offset so that we are
/// guaranteed that there is a place to do an insertion at the specified
/// offset. The offset is relative, so "0" is the start of the node.
@@ -436,8 +436,8 @@
/// If there is no space in this subtree for the extra piece, the extra tree
/// node is returned and must be inserted into a parent.
RopePieceBTreeNode *split(unsigned Offset);
-
-
+
+
/// insert - Insert the specified ropepiece into this tree node at the
/// specified offset. The offset is relative, so "0" is the start of the
/// node.
@@ -445,18 +445,18 @@
/// If there is no space in this subtree for the extra piece, the extra tree
/// node is returned and must be inserted into a parent.
RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
-
+
/// HandleChildPiece - A child propagated an insertion result up to us.
/// Insert the new child, and/or propagate the result further up the tree.
RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
-
+
/// erase - Remove NumBytes from this node at the specified offset. We are
/// guaranteed that there is a split at Offset.
void erase(unsigned Offset, unsigned NumBytes);
-
+
static inline bool classof(const RopePieceBTreeInterior *) { return true; }
static inline bool classof(const RopePieceBTreeNode *N) {
- return !N->isLeaf();
+ return !N->isLeaf();
}
};
} // end anonymous namespace
@@ -471,18 +471,18 @@
// Figure out which child to split.
if (Offset == 0 || Offset == size())
return 0; // If we have an exact offset, we're already split.
-
+
unsigned ChildOffset = 0;
unsigned i = 0;
for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
ChildOffset += getChild(i)->size();
-
+
// If already split there, we're done.
if (ChildOffset == Offset)
return 0;
-
+
// Otherwise, recursively split the child.
- if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
+ if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
return HandleChildPiece(i, RHS);
return 0; // Done!
}
@@ -498,7 +498,7 @@
// Find the insertion point. We are guaranteed that there is a split at the
// specified offset so find it.
unsigned i = 0, e = getNumChildren();
-
+
unsigned ChildOffs = 0;
if (Offset == size()) {
// Fastpath for a common case. Insert at end of last child.
@@ -508,13 +508,13 @@
for (; Offset > ChildOffs+getChild(i)->size(); ++i)
ChildOffs += getChild(i)->size();
}
-
+
Size += R.size();
-
+
// Insert at the end of this child.
if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
return HandleChildPiece(i, RHS);
-
+
return 0;
}
@@ -533,27 +533,27 @@
++NumChildren;
return false;
}
-
+
// Okay, this node is full. Split it in half, moving WidthFactor children to
// a newly allocated interior node.
-
+
// Create the new node.
RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
-
+
// Move over the last 'WidthFactor' values from here to NewNode.
memcpy(&NewNode->Children[0], &Children[WidthFactor],
WidthFactor*sizeof(Children[0]));
-
+
// Decrease the number of values in the two nodes.
NewNode->NumChildren = NumChildren = WidthFactor;
-
+
// Finally, insert the two new children in the side the can (now) hold them.
// These insertions can't fail.
if (i < WidthFactor)
this->HandleChildPiece(i, RHS);
else
NewNode->HandleChildPiece(i-WidthFactor, RHS);
-
+
// Recompute the two nodes' size.
NewNode->FullRecomputeSizeLocally();
FullRecomputeSizeLocally();
@@ -565,24 +565,24 @@
void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
// This will shrink this node by NumBytes.
Size -= NumBytes;
-
+
// Find the first child that overlaps with Offset.
unsigned i = 0;
for (; Offset >= getChild(i)->size(); ++i)
Offset -= getChild(i)->size();
-
+
// Propagate the delete request into overlapping children, or completely
// delete the children as appropriate.
while (NumBytes) {
RopePieceBTreeNode *CurChild = getChild(i);
-
+
// If we are deleting something contained entirely in the child, pass on the
// request.
if (Offset+NumBytes < CurChild->size()) {
CurChild->erase(Offset, NumBytes);
return;
}
-
+
// If this deletion request starts somewhere in the middle of the child, it
// must be deleting to the end of the child.
if (Offset) {
@@ -665,19 +665,19 @@
// begin iterator.
RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n);
-
+
// Walk down the left side of the tree until we get to a leaf.
while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N))
N = IN->getChild(0);
-
+
// We must have at least one leaf.
CurNode = cast<RopePieceBTreeLeaf>(N);
-
+
// If we found a leaf that happens to be empty, skip over it until we get
// to something full.
while (CurNode && getCN(CurNode)->getNumPieces() == 0)
CurNode = getCN(CurNode)->getNextLeafInOrder();
-
+
if (CurNode != 0)
CurPiece = &getCN(CurNode)->getPiece(0);
else // Empty tree, this is an end() iterator.
@@ -691,12 +691,12 @@
++CurPiece;
return;
}
-
+
// Find the next non-empty leaf node.
do
CurNode = getCN(CurNode)->getNextLeafInOrder();
while (CurNode && getCN(CurNode)->getNumPieces() == 0);
-
+
if (CurNode != 0)
CurPiece = &getCN(CurNode)->getPiece(0);
else // Hit end().
@@ -740,7 +740,7 @@
// #1. Split at Offset.
if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
-
+
// #2. Do the insertion.
if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
@@ -750,7 +750,7 @@
// #1. Split at Offset.
if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
-
+
// #2. Do the erasing.
getRoot(Root)->erase(Offset, NumBytes);
}
@@ -766,38 +766,38 @@
RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
unsigned Len = End-Start;
assert(Len && "Zero length RopePiece is invalid!");
-
+
// If we have space for this string in the current alloc buffer, use it.
if (AllocOffs+Len <= AllocChunkSize) {
memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
AllocOffs += Len;
return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
}
-
+
// If we don't have enough room because this specific allocation is huge,
// just allocate a new rope piece for it alone.
if (Len > AllocChunkSize) {
unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
- RopeRefCountString *Res =
+ RopeRefCountString *Res =
reinterpret_cast<RopeRefCountString *>(new char[Size]);
Res->RefCount = 0;
memcpy(Res->Data, Start, End-Start);
return RopePiece(Res, 0, End-Start);
}
-
+
// Otherwise, this was a small request but we just don't have space for it
// Make a new chunk and share it with later allocations.
-
+
// If we had an old allocation, drop our reference to it.
if (AllocBuffer && --AllocBuffer->RefCount == 0)
delete [] (char*)AllocBuffer;
-
+
unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
AllocBuffer->RefCount = 0;
memcpy(AllocBuffer->Data, Start, Len);
AllocOffs = Len;
-
+
// Start out the new allocation with a refcount of 1, since we have an
// internal reference to it.
AllocBuffer->addRef();