1 //===--- RewriteRope.cpp - Rope specialized for rewriter --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the RewriteRope class, which is a powerful string.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Rewrite/RewriteRope.h"
15 #include "clang/Basic/LLVM.h"
17 using namespace clang;
19 /// RewriteRope is a "strong" string class, designed to make insertions and
20 /// deletions in the middle of the string nearly constant time (really, they are
21 /// O(log N), but with a very low constant factor).
23 /// The implementation of this datastructure is a conceptual linear sequence of
24 /// RopePiece elements. Each RopePiece represents a view on a separately
25 /// allocated and reference counted string. This means that splitting a very
26 /// long string can be done in constant time by splitting a RopePiece that
27 /// references the whole string into two rope pieces that reference each half.
28 /// Once split, another string can be inserted in between the two halves by
29 /// inserting a RopePiece in between the two others. All of this is very
30 /// inexpensive: it takes time proportional to the number of RopePieces, not the
31 /// length of the strings they represent.
33 /// While a linear sequences of RopePieces is the conceptual model, the actual
34 /// implementation captures them in an adapted B+ Tree. Using a B+ tree (which
35 /// is a tree that keeps the values in the leaves and has where each node
36 /// contains a reasonable number of pointers to children/values) allows us to
37 /// maintain efficient operation when the RewriteRope contains a *huge* number
38 /// of RopePieces. The basic idea of the B+ Tree is that it allows us to find
39 /// the RopePiece corresponding to some offset very efficiently, and it
40 /// automatically balances itself on insertions of RopePieces (which can happen
41 /// for both insertions and erases of string ranges).
43 /// The one wrinkle on the theory is that we don't attempt to keep the tree
44 /// properly balanced when erases happen. Erases of string data can both insert
45 /// new RopePieces (e.g. when the middle of some other rope piece is deleted,
46 /// which results in two rope pieces, which is just like an insert) or it can
47 /// reduce the number of RopePieces maintained by the B+Tree. In the case when
48 /// the number of RopePieces is reduced, we don't attempt to maintain the
49 /// standard 'invariant' that each node in the tree contains at least
50 /// 'WidthFactor' children/values. For our use cases, this doesn't seem to
53 /// The implementation below is primarily implemented in terms of three classes:
54 /// RopePieceBTreeNode - Common base class for:
56 /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
57 /// nodes. This directly represents a chunk of the string with those
58 /// RopePieces contatenated.
59 /// RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
60 /// up to '2*WidthFactor' other nodes in the tree.
63 //===----------------------------------------------------------------------===//
64 // RopePieceBTreeNode Class
65 //===----------------------------------------------------------------------===//
68 /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
69 /// RopePieceBTreeInterior. This provides some 'virtual' dispatching methods
70 /// and a flag that determines which subclass the instance is. Also
71 /// important, this node knows the full extend of the node, including any
72 /// children that it has. This allows efficient skipping over entire subtrees
73 /// when looking for an offset in the BTree.
74 class RopePieceBTreeNode {
76 /// WidthFactor - This controls the number of K/V slots held in the BTree:
77 /// how wide it is. Each level of the BTree is guaranteed to have at least
78 /// 'WidthFactor' elements in it (either ropepieces or children), (except
79 /// the root, which may have less) and may have at most 2*WidthFactor
81 enum { WidthFactor = 8 };
83 /// Size - This is the number of bytes of file this node (including any
84 /// potential children) covers.
87 /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
88 /// is an instance of RopePieceBTreeInterior.
91 RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {}
92 ~RopePieceBTreeNode() {}
95 bool isLeaf() const { return IsLeaf; }
96 unsigned size() const { return Size; }
100 /// split - Split the range containing the specified offset so that we are
101 /// guaranteed that there is a place to do an insertion at the specified
102 /// offset. The offset is relative, so "0" is the start of the node.
104 /// If there is no space in this subtree for the extra piece, the extra tree
105 /// node is returned and must be inserted into a parent.
106 RopePieceBTreeNode *split(unsigned Offset);
108 /// insert - Insert the specified ropepiece into this tree node at the
109 /// specified offset. The offset is relative, so "0" is the start of the
112 /// If there is no space in this subtree for the extra piece, the extra tree
113 /// node is returned and must be inserted into a parent.
114 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
116 /// erase - Remove NumBytes from this node at the specified offset. We are
117 /// guaranteed that there is a split at Offset.
118 void erase(unsigned Offset, unsigned NumBytes);
120 //static inline bool classof(const RopePieceBTreeNode *) { return true; }
123 } // end anonymous namespace
125 //===----------------------------------------------------------------------===//
126 // RopePieceBTreeLeaf Class
127 //===----------------------------------------------------------------------===//
130 /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
131 /// nodes. This directly represents a chunk of the string with those
132 /// RopePieces contatenated. Since this is a B+Tree, all values (in this case
133 /// instances of RopePiece) are stored in leaves like this. To make iteration
134 /// over the leaves efficient, they maintain a singly linked list through the
135 /// NextLeaf field. This allows the B+Tree forward iterator to be constant
136 /// time for all increments.
137 class RopePieceBTreeLeaf : public RopePieceBTreeNode {
138 /// NumPieces - This holds the number of rope pieces currently active in the
140 unsigned char NumPieces;
142 /// Pieces - This tracks the file chunks currently in this leaf.
144 RopePiece Pieces[2*WidthFactor];
146 /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
147 /// efficient in-order forward iteration of the tree without traversal.
148 RopePieceBTreeLeaf **PrevLeaf, *NextLeaf;
150 RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0),
151 PrevLeaf(0), NextLeaf(0) {}
152 ~RopePieceBTreeLeaf() {
153 if (PrevLeaf || NextLeaf)
154 removeFromLeafInOrder();
158 bool isFull() const { return NumPieces == 2*WidthFactor; }
160 /// clear - Remove all rope pieces from this leaf.
163 Pieces[--NumPieces] = RopePiece();
167 unsigned getNumPieces() const { return NumPieces; }
169 const RopePiece &getPiece(unsigned i) const {
170 assert(i < getNumPieces() && "Invalid piece ID");
174 const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
175 void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
176 assert(PrevLeaf == 0 && NextLeaf == 0 && "Already in ordering");
178 NextLeaf = Node->NextLeaf;
180 NextLeaf->PrevLeaf = &NextLeaf;
181 PrevLeaf = &Node->NextLeaf;
182 Node->NextLeaf = this;
185 void removeFromLeafInOrder() {
187 *PrevLeaf = NextLeaf;
189 NextLeaf->PrevLeaf = PrevLeaf;
190 } else if (NextLeaf) {
191 NextLeaf->PrevLeaf = 0;
195 /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
196 /// summing the size of all RopePieces.
197 void FullRecomputeSizeLocally() {
199 for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
200 Size += getPiece(i).size();
203 /// split - Split the range containing the specified offset so that we are
204 /// guaranteed that there is a place to do an insertion at the specified
205 /// offset. The offset is relative, so "0" is the start of the node.
207 /// If there is no space in this subtree for the extra piece, the extra tree
208 /// node is returned and must be inserted into a parent.
209 RopePieceBTreeNode *split(unsigned Offset);
211 /// insert - Insert the specified ropepiece into this tree node at the
212 /// specified offset. The offset is relative, so "0" is the start of the
215 /// If there is no space in this subtree for the extra piece, the extra tree
216 /// node is returned and must be inserted into a parent.
217 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
220 /// erase - Remove NumBytes from this node at the specified offset. We are
221 /// guaranteed that there is a split at Offset.
222 void erase(unsigned Offset, unsigned NumBytes);
224 //static inline bool classof(const RopePieceBTreeLeaf *) { return true; }
225 static inline bool classof(const RopePieceBTreeNode *N) {
229 } // end anonymous namespace
231 /// split - Split the range containing the specified offset so that we are
232 /// guaranteed that there is a place to do an insertion at the specified
233 /// offset. The offset is relative, so "0" is the start of the node.
235 /// If there is no space in this subtree for the extra piece, the extra tree
236 /// node is returned and must be inserted into a parent.
237 RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {
238 // Find the insertion point. We are guaranteed that there is a split at the
239 // specified offset so find it.
240 if (Offset == 0 || Offset == size()) {
241 // Fastpath for a common case. There is already a splitpoint at the end.
245 // Find the piece that this offset lands in.
246 unsigned PieceOffs = 0;
248 while (Offset >= PieceOffs+Pieces[i].size()) {
249 PieceOffs += Pieces[i].size();
253 // If there is already a split point at the specified offset, just return
255 if (PieceOffs == Offset)
258 // Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset
259 // to being Piece relative.
260 unsigned IntraPieceOffset = Offset-PieceOffs;
262 // We do this by shrinking the RopePiece and then doing an insert of the tail.
263 RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
265 Size -= Pieces[i].size();
266 Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
267 Size += Pieces[i].size();
269 return insert(Offset, Tail);
273 /// insert - Insert the specified RopePiece into this tree node at the
274 /// specified offset. The offset is relative, so "0" is the start of the node.
276 /// If there is no space in this subtree for the extra piece, the extra tree
277 /// node is returned and must be inserted into a parent.
278 RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,
279 const RopePiece &R) {
280 // If this node is not full, insert the piece.
282 // Find the insertion point. We are guaranteed that there is a split at the
283 // specified offset so find it.
284 unsigned i = 0, e = getNumPieces();
285 if (Offset == size()) {
286 // Fastpath for a common case.
289 unsigned SlotOffs = 0;
290 for (; Offset > SlotOffs; ++i)
291 SlotOffs += getPiece(i).size();
292 assert(SlotOffs == Offset && "Split didn't occur before insertion!");
295 // For an insertion into a non-full leaf node, just insert the value in
296 // its sorted position. This requires moving later values over.
298 Pieces[e] = Pieces[e-1];
305 // Otherwise, if this is leaf is full, split it in two halves. Since this
306 // node is full, it contains 2*WidthFactor values. We move the first
307 // 'WidthFactor' values to the LHS child (which we leave in this node) and
308 // move the last 'WidthFactor' values into the RHS child.
310 // Create the new node.
311 RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
313 // Move over the last 'WidthFactor' values from here to NewNode.
314 std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
315 &NewNode->Pieces[0]);
316 // Replace old pieces with null RopePieces to drop refcounts.
317 std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
319 // Decrease the number of values in the two nodes.
320 NewNode->NumPieces = NumPieces = WidthFactor;
322 // Recompute the two nodes' size.
323 NewNode->FullRecomputeSizeLocally();
324 FullRecomputeSizeLocally();
326 // Update the list of leaves.
327 NewNode->insertAfterLeafInOrder(this);
329 // These insertions can't fail.
330 if (this->size() >= Offset)
331 this->insert(Offset, R);
333 NewNode->insert(Offset - this->size(), R);
337 /// erase - Remove NumBytes from this node at the specified offset. We are
338 /// guaranteed that there is a split at Offset.
339 void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
340 // Since we are guaranteed that there is a split at Offset, we start by
341 // finding the Piece that starts there.
342 unsigned PieceOffs = 0;
344 for (; Offset > PieceOffs; ++i)
345 PieceOffs += getPiece(i).size();
346 assert(PieceOffs == Offset && "Split didn't occur before erase!");
348 unsigned StartPiece = i;
350 // Figure out how many pieces completely cover 'NumBytes'. We want to remove
352 for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
353 PieceOffs += getPiece(i).size();
355 // If we exactly include the last one, include it in the region to delete.
356 if (Offset+NumBytes == PieceOffs+getPiece(i).size())
357 PieceOffs += getPiece(i).size(), ++i;
359 // If we completely cover some RopePieces, erase them now.
360 if (i != StartPiece) {
361 unsigned NumDeleted = i-StartPiece;
362 for (; i != getNumPieces(); ++i)
363 Pieces[i-NumDeleted] = Pieces[i];
365 // Drop references to dead rope pieces.
366 std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
368 NumPieces -= NumDeleted;
370 unsigned CoverBytes = PieceOffs-Offset;
371 NumBytes -= CoverBytes;
375 // If we completely removed some stuff, we could be done.
376 if (NumBytes == 0) return;
378 // Okay, now might be erasing part of some Piece. If this is the case, then
379 // move the start point of the piece.
380 assert(getPiece(StartPiece).size() > NumBytes);
381 Pieces[StartPiece].StartOffs += NumBytes;
383 // The size of this node just shrunk by NumBytes.
387 //===----------------------------------------------------------------------===//
388 // RopePieceBTreeInterior Class
389 //===----------------------------------------------------------------------===//
392 /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
393 /// which holds up to 2*WidthFactor pointers to child nodes.
394 class RopePieceBTreeInterior : public RopePieceBTreeNode {
395 /// NumChildren - This holds the number of children currently active in the
397 unsigned char NumChildren;
398 RopePieceBTreeNode *Children[2*WidthFactor];
400 RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {}
402 RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
403 : RopePieceBTreeNode(false) {
407 Size = LHS->size() + RHS->size();
410 ~RopePieceBTreeInterior() {
411 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
412 Children[i]->Destroy();
415 bool isFull() const { return NumChildren == 2*WidthFactor; }
417 unsigned getNumChildren() const { return NumChildren; }
418 const RopePieceBTreeNode *getChild(unsigned i) const {
419 assert(i < NumChildren && "invalid child #");
422 RopePieceBTreeNode *getChild(unsigned i) {
423 assert(i < NumChildren && "invalid child #");
427 /// FullRecomputeSizeLocally - Recompute the Size field of this node by
428 /// summing up the sizes of the child nodes.
429 void FullRecomputeSizeLocally() {
431 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
432 Size += getChild(i)->size();
436 /// split - Split the range containing the specified offset so that we are
437 /// guaranteed that there is a place to do an insertion at the specified
438 /// offset. The offset is relative, so "0" is the start of the node.
440 /// If there is no space in this subtree for the extra piece, the extra tree
441 /// node is returned and must be inserted into a parent.
442 RopePieceBTreeNode *split(unsigned Offset);
445 /// insert - Insert the specified ropepiece into this tree node at the
446 /// specified offset. The offset is relative, so "0" is the start of the
449 /// If there is no space in this subtree for the extra piece, the extra tree
450 /// node is returned and must be inserted into a parent.
451 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
453 /// HandleChildPiece - A child propagated an insertion result up to us.
454 /// Insert the new child, and/or propagate the result further up the tree.
455 RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
457 /// erase - Remove NumBytes from this node at the specified offset. We are
458 /// guaranteed that there is a split at Offset.
459 void erase(unsigned Offset, unsigned NumBytes);
461 //static inline bool classof(const RopePieceBTreeInterior *) { return true; }
462 static inline bool classof(const RopePieceBTreeNode *N) {
466 } // end anonymous namespace
468 /// split - Split the range containing the specified offset so that we are
469 /// guaranteed that there is a place to do an insertion at the specified
470 /// offset. The offset is relative, so "0" is the start of the node.
472 /// If there is no space in this subtree for the extra piece, the extra tree
473 /// node is returned and must be inserted into a parent.
474 RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
475 // Figure out which child to split.
476 if (Offset == 0 || Offset == size())
477 return 0; // If we have an exact offset, we're already split.
479 unsigned ChildOffset = 0;
481 for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
482 ChildOffset += getChild(i)->size();
484 // If already split there, we're done.
485 if (ChildOffset == Offset)
488 // Otherwise, recursively split the child.
489 if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
490 return HandleChildPiece(i, RHS);
494 /// insert - Insert the specified ropepiece into this tree node at the
495 /// specified offset. The offset is relative, so "0" is the start of the
498 /// If there is no space in this subtree for the extra piece, the extra tree
499 /// node is returned and must be inserted into a parent.
500 RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
501 const RopePiece &R) {
502 // Find the insertion point. We are guaranteed that there is a split at the
503 // specified offset so find it.
504 unsigned i = 0, e = getNumChildren();
506 unsigned ChildOffs = 0;
507 if (Offset == size()) {
508 // Fastpath for a common case. Insert at end of last child.
510 ChildOffs = size()-getChild(i)->size();
512 for (; Offset > ChildOffs+getChild(i)->size(); ++i)
513 ChildOffs += getChild(i)->size();
518 // Insert at the end of this child.
519 if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
520 return HandleChildPiece(i, RHS);
525 /// HandleChildPiece - A child propagated an insertion result up to us.
526 /// Insert the new child, and/or propagate the result further up the tree.
528 RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
529 // Otherwise the child propagated a subtree up to us as a new child. See if
530 // we have space for it here.
532 // Insert RHS after child 'i'.
533 if (i + 1 != getNumChildren())
534 memmove(&Children[i+2], &Children[i+1],
535 (getNumChildren()-i-1)*sizeof(Children[0]));
541 // Okay, this node is full. Split it in half, moving WidthFactor children to
542 // a newly allocated interior node.
544 // Create the new node.
545 RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
547 // Move over the last 'WidthFactor' values from here to NewNode.
548 memcpy(&NewNode->Children[0], &Children[WidthFactor],
549 WidthFactor*sizeof(Children[0]));
551 // Decrease the number of values in the two nodes.
552 NewNode->NumChildren = NumChildren = WidthFactor;
554 // Finally, insert the two new children in the side the can (now) hold them.
555 // These insertions can't fail.
557 this->HandleChildPiece(i, RHS);
559 NewNode->HandleChildPiece(i-WidthFactor, RHS);
561 // Recompute the two nodes' size.
562 NewNode->FullRecomputeSizeLocally();
563 FullRecomputeSizeLocally();
567 /// erase - Remove NumBytes from this node at the specified offset. We are
568 /// guaranteed that there is a split at Offset.
569 void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
570 // This will shrink this node by NumBytes.
573 // Find the first child that overlaps with Offset.
575 for (; Offset >= getChild(i)->size(); ++i)
576 Offset -= getChild(i)->size();
578 // Propagate the delete request into overlapping children, or completely
579 // delete the children as appropriate.
581 RopePieceBTreeNode *CurChild = getChild(i);
583 // If we are deleting something contained entirely in the child, pass on the
585 if (Offset+NumBytes < CurChild->size()) {
586 CurChild->erase(Offset, NumBytes);
590 // If this deletion request starts somewhere in the middle of the child, it
591 // must be deleting to the end of the child.
593 unsigned BytesFromChild = CurChild->size()-Offset;
594 CurChild->erase(Offset, BytesFromChild);
595 NumBytes -= BytesFromChild;
596 // Start at the beginning of the next child.
602 // If the deletion request completely covers the child, delete it and move
604 NumBytes -= CurChild->size();
607 if (i != getNumChildren())
608 memmove(&Children[i], &Children[i+1],
609 (getNumChildren()-i)*sizeof(Children[0]));
613 //===----------------------------------------------------------------------===//
614 // RopePieceBTreeNode Implementation
615 //===----------------------------------------------------------------------===//
617 void RopePieceBTreeNode::Destroy() {
618 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
621 delete cast<RopePieceBTreeInterior>(this);
624 /// split - Split the range containing the specified offset so that we are
625 /// guaranteed that there is a place to do an insertion at the specified
626 /// offset. The offset is relative, so "0" is the start of the node.
628 /// If there is no space in this subtree for the extra piece, the extra tree
629 /// node is returned and must be inserted into a parent.
630 RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
631 assert(Offset <= size() && "Invalid offset to split!");
632 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
633 return Leaf->split(Offset);
634 return cast<RopePieceBTreeInterior>(this)->split(Offset);
637 /// insert - Insert the specified ropepiece into this tree node at the
638 /// specified offset. The offset is relative, so "0" is the start of the
641 /// If there is no space in this subtree for the extra piece, the extra tree
642 /// node is returned and must be inserted into a parent.
643 RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
644 const RopePiece &R) {
645 assert(Offset <= size() && "Invalid offset to insert!");
646 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
647 return Leaf->insert(Offset, R);
648 return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
651 /// erase - Remove NumBytes from this node at the specified offset. We are
652 /// guaranteed that there is a split at Offset.
653 void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
654 assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
655 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
656 return Leaf->erase(Offset, NumBytes);
657 return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
661 //===----------------------------------------------------------------------===//
662 // RopePieceBTreeIterator Implementation
663 //===----------------------------------------------------------------------===//
665 static const RopePieceBTreeLeaf *getCN(const void *P) {
666 return static_cast<const RopePieceBTreeLeaf*>(P);
670 RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
671 const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n);
673 // Walk down the left side of the tree until we get to a leaf.
674 while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N))
677 // We must have at least one leaf.
678 CurNode = cast<RopePieceBTreeLeaf>(N);
680 // If we found a leaf that happens to be empty, skip over it until we get
681 // to something full.
682 while (CurNode && getCN(CurNode)->getNumPieces() == 0)
683 CurNode = getCN(CurNode)->getNextLeafInOrder();
686 CurPiece = &getCN(CurNode)->getPiece(0);
687 else // Empty tree, this is an end() iterator.
692 void RopePieceBTreeIterator::MoveToNextPiece() {
693 if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
699 // Find the next non-empty leaf node.
701 CurNode = getCN(CurNode)->getNextLeafInOrder();
702 while (CurNode && getCN(CurNode)->getNumPieces() == 0);
705 CurPiece = &getCN(CurNode)->getPiece(0);
711 //===----------------------------------------------------------------------===//
712 // RopePieceBTree Implementation
713 //===----------------------------------------------------------------------===//
715 static RopePieceBTreeNode *getRoot(void *P) {
716 return static_cast<RopePieceBTreeNode*>(P);
719 RopePieceBTree::RopePieceBTree() {
720 Root = new RopePieceBTreeLeaf();
722 RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
723 assert(RHS.empty() && "Can't copy non-empty tree yet");
724 Root = new RopePieceBTreeLeaf();
726 RopePieceBTree::~RopePieceBTree() {
727 getRoot(Root)->Destroy();
730 unsigned RopePieceBTree::size() const {
731 return getRoot(Root)->size();
734 void RopePieceBTree::clear() {
735 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
738 getRoot(Root)->Destroy();
739 Root = new RopePieceBTreeLeaf();
743 void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
744 // #1. Split at Offset.
745 if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
746 Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
748 // #2. Do the insertion.
749 if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
750 Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
753 void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
754 // #1. Split at Offset.
755 if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
756 Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
758 // #2. Do the erasing.
759 getRoot(Root)->erase(Offset, NumBytes);
762 //===----------------------------------------------------------------------===//
763 // RewriteRope Implementation
764 //===----------------------------------------------------------------------===//
766 /// MakeRopeString - This copies the specified byte range into some instance of
767 /// RopeRefCountString, and return a RopePiece that represents it. This uses
768 /// the AllocBuffer object to aggregate requests for small strings into one
769 /// allocation instead of doing tons of tiny allocations.
770 RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
771 unsigned Len = End-Start;
772 assert(Len && "Zero length RopePiece is invalid!");
774 // If we have space for this string in the current alloc buffer, use it.
775 if (AllocOffs+Len <= AllocChunkSize) {
776 memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
778 return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
781 // If we don't have enough room because this specific allocation is huge,
782 // just allocate a new rope piece for it alone.
783 if (Len > AllocChunkSize) {
784 unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
785 RopeRefCountString *Res =
786 reinterpret_cast<RopeRefCountString *>(new char[Size]);
788 memcpy(Res->Data, Start, End-Start);
789 return RopePiece(Res, 0, End-Start);
792 // Otherwise, this was a small request but we just don't have space for it
793 // Make a new chunk and share it with later allocations.
795 // If we had an old allocation, drop our reference to it.
796 if (AllocBuffer && --AllocBuffer->RefCount == 0)
797 delete [] (char*)AllocBuffer;
799 unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
800 AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
801 AllocBuffer->RefCount = 0;
802 memcpy(AllocBuffer->Data, Start, Len);
805 // Start out the new allocation with a refcount of 1, since we have an
806 // internal reference to it.
807 AllocBuffer->addRef();
808 return RopePiece(AllocBuffer, 0, Len);