contrib/llvm/tools/clang/lib/Rewrite/RewriteRope.cpp

   1 //===--- RewriteRope.cpp - Rope specialized for rewriter --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implements the RewriteRope class, which is a powerful string.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Rewrite/RewriteRope.h"
  15 #include "clang/Basic/LLVM.h"
  16 #include <algorithm>
  17 using namespace clang;
  18
  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).
  22 ///
  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.
  32 ///
  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).
  42 ///
  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
  51 /// matter.
  52 ///
  53 /// The implementation below is primarily implemented in terms of three classes:
  54 ///   RopePieceBTreeNode - Common base class for:
  55 ///
  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.
  61
  62
  63 //===----------------------------------------------------------------------===//
  64 // RopePieceBTreeNode Class
  65 //===----------------------------------------------------------------------===//
  66
  67 namespace {
  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 {
  75   protected:
  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
  80     /// elements.
  81     enum { WidthFactor = 8 };
  82
  83     /// Size - This is the number of bytes of file this node (including any
  84     /// potential children) covers.
  85     unsigned Size;
  86
  87     /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
  88     /// is an instance of RopePieceBTreeInterior.
  89     bool IsLeaf;
  90
  91     RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {}
  92     ~RopePieceBTreeNode() {}
  93   public:
  94
  95     bool isLeaf() const { return IsLeaf; }
  96     unsigned size() const { return Size; }
  97
  98     void Destroy();
  99
 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.
 103     ///
 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);
 107
 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
 110     /// node.
 111     ///
 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);
 115
 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);
 119
 120     //static inline bool classof(const RopePieceBTreeNode *) { return true; }
 121
 122   };
 123 } // end anonymous namespace
 124
 125 //===----------------------------------------------------------------------===//
 126 // RopePieceBTreeLeaf Class
 127 //===----------------------------------------------------------------------===//
 128
 129 namespace {
 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
 139     /// Pieces array.
 140     unsigned char NumPieces;
 141
 142     /// Pieces - This tracks the file chunks currently in this leaf.
 143     ///
 144     RopePiece Pieces[2*WidthFactor];
 145
 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;
 149   public:
 150     RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0),
 151                            PrevLeaf(0), NextLeaf(0) {}
 152     ~RopePieceBTreeLeaf() {
 153       if (PrevLeaf || NextLeaf)
 154         removeFromLeafInOrder();
 155       clear();
 156     }
 157
 158     bool isFull() const { return NumPieces == 2*WidthFactor; }
 159
 160     /// clear - Remove all rope pieces from this leaf.
 161     void clear() {
 162       while (NumPieces)
 163         Pieces[--NumPieces] = RopePiece();
 164       Size = 0;
 165     }
 166
 167     unsigned getNumPieces() const { return NumPieces; }
 168
 169     const RopePiece &getPiece(unsigned i) const {
 170       assert(i < getNumPieces() && "Invalid piece ID");
 171       return Pieces[i];
 172     }
 173
 174     const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
 175     void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
 176       assert(PrevLeaf == 0 && NextLeaf == 0 && "Already in ordering");
 177
 178       NextLeaf = Node->NextLeaf;
 179       if (NextLeaf)
 180         NextLeaf->PrevLeaf = &NextLeaf;
 181       PrevLeaf = &Node->NextLeaf;
 182       Node->NextLeaf = this;
 183     }
 184
 185     void removeFromLeafInOrder() {
 186       if (PrevLeaf) {
 187         *PrevLeaf = NextLeaf;
 188         if (NextLeaf)
 189           NextLeaf->PrevLeaf = PrevLeaf;
 190       } else if (NextLeaf) {
 191         NextLeaf->PrevLeaf = 0;
 192       }
 193     }
 194
 195     /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
 196     /// summing the size of all RopePieces.
 197     void FullRecomputeSizeLocally() {
 198       Size = 0;
 199       for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
 200         Size += getPiece(i).size();
 201     }
 202
 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.
 206     ///
 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);
 210
 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
 213     /// node.
 214     ///
 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);
 218
 219
 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);
 223
 224     //static inline bool classof(const RopePieceBTreeLeaf *) { return true; }
 225     static inline bool classof(const RopePieceBTreeNode *N) {
 226       return N->isLeaf();
 227     }
 228   };
 229 } // end anonymous namespace
 230
 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.
 234 ///
 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.
 242     return 0;
 243   }
 244
 245   // Find the piece that this offset lands in.
 246   unsigned PieceOffs = 0;
 247   unsigned i = 0;
 248   while (Offset >= PieceOffs+Pieces[i].size()) {
 249     PieceOffs += Pieces[i].size();
 250     ++i;
 251   }
 252
 253   // If there is already a split point at the specified offset, just return
 254   // success.
 255   if (PieceOffs == Offset)
 256     return 0;
 257
 258   // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset
 259   // to being Piece relative.
 260   unsigned IntraPieceOffset = Offset-PieceOffs;
 261
 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,
 264                  Pieces[i].EndOffs);
 265   Size -= Pieces[i].size();
 266   Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
 267   Size += Pieces[i].size();
 268
 269   return insert(Offset, Tail);
 270 }
 271
 272
 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.
 275 ///
 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.
 281   if (!isFull()) {
 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.
 287       i = e;
 288     } else {
 289       unsigned SlotOffs = 0;
 290       for (; Offset > SlotOffs; ++i)
 291         SlotOffs += getPiece(i).size();
 292       assert(SlotOffs == Offset && "Split didn't occur before insertion!");
 293     }
 294
 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.
 297     for (; i != e; --e)
 298       Pieces[e] = Pieces[e-1];
 299     Pieces[i] = R;
 300     ++NumPieces;
 301     Size += R.size();
 302     return 0;
 303   }
 304
 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.
 309
 310   // Create the new node.
 311   RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
 312
 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());
 318
 319   // Decrease the number of values in the two nodes.
 320   NewNode->NumPieces = NumPieces = WidthFactor;
 321
 322   // Recompute the two nodes' size.
 323   NewNode->FullRecomputeSizeLocally();
 324   FullRecomputeSizeLocally();
 325
 326   // Update the list of leaves.
 327   NewNode->insertAfterLeafInOrder(this);
 328
 329   // These insertions can't fail.
 330   if (this->size() >= Offset)
 331     this->insert(Offset, R);
 332   else
 333     NewNode->insert(Offset - this->size(), R);
 334   return NewNode;
 335 }
 336
 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;
 343   unsigned i = 0;
 344   for (; Offset > PieceOffs; ++i)
 345     PieceOffs += getPiece(i).size();
 346   assert(PieceOffs == Offset && "Split didn't occur before erase!");
 347
 348   unsigned StartPiece = i;
 349
 350   // Figure out how many pieces completely cover 'NumBytes'.  We want to remove
 351   // all of them.
 352   for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
 353     PieceOffs += getPiece(i).size();
 354
 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;
 358
 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];
 364
 365     // Drop references to dead rope pieces.
 366     std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
 367               RopePiece());
 368     NumPieces -= NumDeleted;
 369
 370     unsigned CoverBytes = PieceOffs-Offset;
 371     NumBytes -= CoverBytes;
 372     Size -= CoverBytes;
 373   }
 374
 375   // If we completely removed some stuff, we could be done.
 376   if (NumBytes == 0) return;
 377
 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;
 382
 383   // The size of this node just shrunk by NumBytes.
 384   Size -= NumBytes;
 385 }
 386
 387 //===----------------------------------------------------------------------===//
 388 // RopePieceBTreeInterior Class
 389 //===----------------------------------------------------------------------===//
 390
 391 namespace {
 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
 396     /// Children array.
 397     unsigned char NumChildren;
 398     RopePieceBTreeNode *Children[2*WidthFactor];
 399   public:
 400     RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {}
 401
 402     RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
 403     : RopePieceBTreeNode(false) {
 404       Children[0] = LHS;
 405       Children[1] = RHS;
 406       NumChildren = 2;
 407       Size = LHS->size() + RHS->size();
 408     }
 409
 410     bool isFull() const { return NumChildren == 2*WidthFactor; }
 411
 412     unsigned getNumChildren() const { return NumChildren; }
 413     const RopePieceBTreeNode *getChild(unsigned i) const {
 414       assert(i < NumChildren && "invalid child #");
 415       return Children[i];
 416     }
 417     RopePieceBTreeNode *getChild(unsigned i) {
 418       assert(i < NumChildren && "invalid child #");
 419       return Children[i];
 420     }
 421
 422     /// FullRecomputeSizeLocally - Recompute the Size field of this node by
 423     /// summing up the sizes of the child nodes.
 424     void FullRecomputeSizeLocally() {
 425       Size = 0;
 426       for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 427         Size += getChild(i)->size();
 428     }
 429
 430
 431     /// split - Split the range containing the specified offset so that we are
 432     /// guaranteed that there is a place to do an insertion at the specified
 433     /// offset.  The offset is relative, so "0" is the start of the node.
 434     ///
 435     /// If there is no space in this subtree for the extra piece, the extra tree
 436     /// node is returned and must be inserted into a parent.
 437     RopePieceBTreeNode *split(unsigned Offset);
 438
 439
 440     /// insert - Insert the specified ropepiece into this tree node at the
 441     /// specified offset.  The offset is relative, so "0" is the start of the
 442     /// node.
 443     ///
 444     /// If there is no space in this subtree for the extra piece, the extra tree
 445     /// node is returned and must be inserted into a parent.
 446     RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
 447
 448     /// HandleChildPiece - A child propagated an insertion result up to us.
 449     /// Insert the new child, and/or propagate the result further up the tree.
 450     RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
 451
 452     /// erase - Remove NumBytes from this node at the specified offset.  We are
 453     /// guaranteed that there is a split at Offset.
 454     void erase(unsigned Offset, unsigned NumBytes);
 455
 456     //static inline bool classof(const RopePieceBTreeInterior *) { return true; }
 457     static inline bool classof(const RopePieceBTreeNode *N) {
 458       return !N->isLeaf();
 459     }
 460   };
 461 } // end anonymous namespace
 462
 463 /// split - Split the range containing the specified offset so that we are
 464 /// guaranteed that there is a place to do an insertion at the specified
 465 /// offset.  The offset is relative, so "0" is the start of the node.
 466 ///
 467 /// If there is no space in this subtree for the extra piece, the extra tree
 468 /// node is returned and must be inserted into a parent.
 469 RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
 470   // Figure out which child to split.
 471   if (Offset == 0 || Offset == size())
 472     return 0;  // If we have an exact offset, we're already split.
 473
 474   unsigned ChildOffset = 0;
 475   unsigned i = 0;
 476   for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
 477     ChildOffset += getChild(i)->size();
 478
 479   // If already split there, we're done.
 480   if (ChildOffset == Offset)
 481     return 0;
 482
 483   // Otherwise, recursively split the child.
 484   if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
 485     return HandleChildPiece(i, RHS);
 486   return 0;  // Done!
 487 }
 488
 489 /// insert - Insert the specified ropepiece into this tree node at the
 490 /// specified offset.  The offset is relative, so "0" is the start of the
 491 /// node.
 492 ///
 493 /// If there is no space in this subtree for the extra piece, the extra tree
 494 /// node is returned and must be inserted into a parent.
 495 RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
 496                                                    const RopePiece &R) {
 497   // Find the insertion point.  We are guaranteed that there is a split at the
 498   // specified offset so find it.
 499   unsigned i = 0, e = getNumChildren();
 500
 501   unsigned ChildOffs = 0;
 502   if (Offset == size()) {
 503     // Fastpath for a common case.  Insert at end of last child.
 504     i = e-1;
 505     ChildOffs = size()-getChild(i)->size();
 506   } else {
 507     for (; Offset > ChildOffs+getChild(i)->size(); ++i)
 508       ChildOffs += getChild(i)->size();
 509   }
 510
 511   Size += R.size();
 512
 513   // Insert at the end of this child.
 514   if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
 515     return HandleChildPiece(i, RHS);
 516
 517   return 0;
 518 }
 519
 520 /// HandleChildPiece - A child propagated an insertion result up to us.
 521 /// Insert the new child, and/or propagate the result further up the tree.
 522 RopePieceBTreeNode *
 523 RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
 524   // Otherwise the child propagated a subtree up to us as a new child.  See if
 525   // we have space for it here.
 526   if (!isFull()) {
 527     // Insert RHS after child 'i'.
 528     if (i + 1 != getNumChildren())
 529       memmove(&Children[i+2], &Children[i+1],
 530               (getNumChildren()-i-1)*sizeof(Children[0]));
 531     Children[i+1] = RHS;
 532     ++NumChildren;
 533     return 0;
 534   }
 535
 536   // Okay, this node is full.  Split it in half, moving WidthFactor children to
 537   // a newly allocated interior node.
 538
 539   // Create the new node.
 540   RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
 541
 542   // Move over the last 'WidthFactor' values from here to NewNode.
 543   memcpy(&NewNode->Children[0], &Children[WidthFactor],
 544          WidthFactor*sizeof(Children[0]));
 545
 546   // Decrease the number of values in the two nodes.
 547   NewNode->NumChildren = NumChildren = WidthFactor;
 548
 549   // Finally, insert the two new children in the side the can (now) hold them.
 550   // These insertions can't fail.
 551   if (i < WidthFactor)
 552     this->HandleChildPiece(i, RHS);
 553   else
 554     NewNode->HandleChildPiece(i-WidthFactor, RHS);
 555
 556   // Recompute the two nodes' size.
 557   NewNode->FullRecomputeSizeLocally();
 558   FullRecomputeSizeLocally();
 559   return NewNode;
 560 }
 561
 562 /// erase - Remove NumBytes from this node at the specified offset.  We are
 563 /// guaranteed that there is a split at Offset.
 564 void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
 565   // This will shrink this node by NumBytes.
 566   Size -= NumBytes;
 567
 568   // Find the first child that overlaps with Offset.
 569   unsigned i = 0;
 570   for (; Offset >= getChild(i)->size(); ++i)
 571     Offset -= getChild(i)->size();
 572
 573   // Propagate the delete request into overlapping children, or completely
 574   // delete the children as appropriate.
 575   while (NumBytes) {
 576     RopePieceBTreeNode *CurChild = getChild(i);
 577
 578     // If we are deleting something contained entirely in the child, pass on the
 579     // request.
 580     if (Offset+NumBytes < CurChild->size()) {
 581       CurChild->erase(Offset, NumBytes);
 582       return;
 583     }
 584
 585     // If this deletion request starts somewhere in the middle of the child, it
 586     // must be deleting to the end of the child.
 587     if (Offset) {
 588       unsigned BytesFromChild = CurChild->size()-Offset;
 589       CurChild->erase(Offset, BytesFromChild);
 590       NumBytes -= BytesFromChild;
 591       // Start at the beginning of the next child.
 592       Offset = 0;
 593       ++i;
 594       continue;
 595     }
 596
 597     // If the deletion request completely covers the child, delete it and move
 598     // the rest down.
 599     NumBytes -= CurChild->size();
 600     CurChild->Destroy();
 601     --NumChildren;
 602     if (i != getNumChildren())
 603       memmove(&Children[i], &Children[i+1],
 604               (getNumChildren()-i)*sizeof(Children[0]));
 605   }
 606 }
 607
 608 //===----------------------------------------------------------------------===//
 609 // RopePieceBTreeNode Implementation
 610 //===----------------------------------------------------------------------===//
 611
 612 void RopePieceBTreeNode::Destroy() {
 613   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 614     delete Leaf;
 615   else
 616     delete cast<RopePieceBTreeInterior>(this);
 617 }
 618
 619 /// split - Split the range containing the specified offset so that we are
 620 /// guaranteed that there is a place to do an insertion at the specified
 621 /// offset.  The offset is relative, so "0" is the start of the node.
 622 ///
 623 /// If there is no space in this subtree for the extra piece, the extra tree
 624 /// node is returned and must be inserted into a parent.
 625 RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
 626   assert(Offset <= size() && "Invalid offset to split!");
 627   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 628     return Leaf->split(Offset);
 629   return cast<RopePieceBTreeInterior>(this)->split(Offset);
 630 }
 631
 632 /// insert - Insert the specified ropepiece into this tree node at the
 633 /// specified offset.  The offset is relative, so "0" is the start of the
 634 /// node.
 635 ///
 636 /// If there is no space in this subtree for the extra piece, the extra tree
 637 /// node is returned and must be inserted into a parent.
 638 RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
 639                                                const RopePiece &R) {
 640   assert(Offset <= size() && "Invalid offset to insert!");
 641   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 642     return Leaf->insert(Offset, R);
 643   return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
 644 }
 645
 646 /// erase - Remove NumBytes from this node at the specified offset.  We are
 647 /// guaranteed that there is a split at Offset.
 648 void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
 649   assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
 650   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 651     return Leaf->erase(Offset, NumBytes);
 652   return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
 653 }
 654
 655
 656 //===----------------------------------------------------------------------===//
 657 // RopePieceBTreeIterator Implementation
 658 //===----------------------------------------------------------------------===//
 659
 660 static const RopePieceBTreeLeaf *getCN(const void *P) {
 661   return static_cast<const RopePieceBTreeLeaf*>(P);
 662 }
 663
 664 // begin iterator.
 665 RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
 666   const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n);
 667
 668   // Walk down the left side of the tree until we get to a leaf.
 669   while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N))
 670     N = IN->getChild(0);
 671
 672   // We must have at least one leaf.
 673   CurNode = cast<RopePieceBTreeLeaf>(N);
 674
 675   // If we found a leaf that happens to be empty, skip over it until we get
 676   // to something full.
 677   while (CurNode && getCN(CurNode)->getNumPieces() == 0)
 678     CurNode = getCN(CurNode)->getNextLeafInOrder();
 679
 680   if (CurNode != 0)
 681     CurPiece = &getCN(CurNode)->getPiece(0);
 682   else  // Empty tree, this is an end() iterator.
 683     CurPiece = 0;
 684   CurChar = 0;
 685 }
 686
 687 void RopePieceBTreeIterator::MoveToNextPiece() {
 688   if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
 689     CurChar = 0;
 690     ++CurPiece;
 691     return;
 692   }
 693
 694   // Find the next non-empty leaf node.
 695   do
 696     CurNode = getCN(CurNode)->getNextLeafInOrder();
 697   while (CurNode && getCN(CurNode)->getNumPieces() == 0);
 698
 699   if (CurNode != 0)
 700     CurPiece = &getCN(CurNode)->getPiece(0);
 701   else // Hit end().
 702     CurPiece = 0;
 703   CurChar = 0;
 704 }
 705
 706 //===----------------------------------------------------------------------===//
 707 // RopePieceBTree Implementation
 708 //===----------------------------------------------------------------------===//
 709
 710 static RopePieceBTreeNode *getRoot(void *P) {
 711   return static_cast<RopePieceBTreeNode*>(P);
 712 }
 713
 714 RopePieceBTree::RopePieceBTree() {
 715   Root = new RopePieceBTreeLeaf();
 716 }
 717 RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
 718   assert(RHS.empty() && "Can't copy non-empty tree yet");
 719   Root = new RopePieceBTreeLeaf();
 720 }
 721 RopePieceBTree::~RopePieceBTree() {
 722   getRoot(Root)->Destroy();
 723 }
 724
 725 unsigned RopePieceBTree::size() const {
 726   return getRoot(Root)->size();
 727 }
 728
 729 void RopePieceBTree::clear() {
 730   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
 731     Leaf->clear();
 732   else {
 733     getRoot(Root)->Destroy();
 734     Root = new RopePieceBTreeLeaf();
 735   }
 736 }
 737
 738 void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
 739   // #1. Split at Offset.
 740   if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
 741     Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
 742
 743   // #2. Do the insertion.
 744   if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
 745     Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
 746 }
 747
 748 void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
 749   // #1. Split at Offset.
 750   if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
 751     Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
 752
 753   // #2. Do the erasing.
 754   getRoot(Root)->erase(Offset, NumBytes);
 755 }
 756
 757 //===----------------------------------------------------------------------===//
 758 // RewriteRope Implementation
 759 //===----------------------------------------------------------------------===//
 760
 761 /// MakeRopeString - This copies the specified byte range into some instance of
 762 /// RopeRefCountString, and return a RopePiece that represents it.  This uses
 763 /// the AllocBuffer object to aggregate requests for small strings into one
 764 /// allocation instead of doing tons of tiny allocations.
 765 RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
 766   unsigned Len = End-Start;
 767   assert(Len && "Zero length RopePiece is invalid!");
 768
 769   // If we have space for this string in the current alloc buffer, use it.
 770   if (AllocOffs+Len <= AllocChunkSize) {
 771     memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
 772     AllocOffs += Len;
 773     return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
 774   }
 775
 776   // If we don't have enough room because this specific allocation is huge,
 777   // just allocate a new rope piece for it alone.
 778   if (Len > AllocChunkSize) {
 779     unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
 780     RopeRefCountString *Res =
 781       reinterpret_cast<RopeRefCountString *>(new char[Size]);
 782     Res->RefCount = 0;
 783     memcpy(Res->Data, Start, End-Start);
 784     return RopePiece(Res, 0, End-Start);
 785   }
 786
 787   // Otherwise, this was a small request but we just don't have space for it
 788   // Make a new chunk and share it with later allocations.
 789
 790   // If we had an old allocation, drop our reference to it.
 791   if (AllocBuffer && --AllocBuffer->RefCount == 0)
 792     delete [] (char*)AllocBuffer;
 793
 794   unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
 795   AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
 796   AllocBuffer->RefCount = 0;
 797   memcpy(AllocBuffer->Data, Start, Len);
 798   AllocOffs = Len;
 799
 800   // Start out the new allocation with a refcount of 1, since we have an
 801   // internal reference to it.
 802   AllocBuffer->addRef();
 803   return RopePiece(AllocBuffer, 0, Len);
 804 }
 805
 806