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 "llvm/Support/Casting.h"
  16 #include <algorithm>
  17 using namespace clang;
  18 using llvm::dyn_cast;
  19 using llvm::cast;
  20
  21 /// RewriteRope is a "strong" string class, designed to make insertions and
  22 /// deletions in the middle of the string nearly constant time (really, they are
  23 /// O(log N), but with a very low constant factor).
  24 ///
  25 /// The implementation of this datastructure is a conceptual linear sequence of
  26 /// RopePiece elements.  Each RopePiece represents a view on a separately
  27 /// allocated and reference counted string.  This means that splitting a very
  28 /// long string can be done in constant time by splitting a RopePiece that
  29 /// references the whole string into two rope pieces that reference each half.
  30 /// Once split, another string can be inserted in between the two halves by
  31 /// inserting a RopePiece in between the two others.  All of this is very
  32 /// inexpensive: it takes time proportional to the number of RopePieces, not the
  33 /// length of the strings they represent.
  34 ///
  35 /// While a linear sequences of RopePieces is the conceptual model, the actual
  36 /// implementation captures them in an adapted B+ Tree.  Using a B+ tree (which
  37 /// is a tree that keeps the values in the leaves and has where each node
  38 /// contains a reasonable number of pointers to children/values) allows us to
  39 /// maintain efficient operation when the RewriteRope contains a *huge* number
  40 /// of RopePieces.  The basic idea of the B+ Tree is that it allows us to find
  41 /// the RopePiece corresponding to some offset very efficiently, and it
  42 /// automatically balances itself on insertions of RopePieces (which can happen
  43 /// for both insertions and erases of string ranges).
  44 ///
  45 /// The one wrinkle on the theory is that we don't attempt to keep the tree
  46 /// properly balanced when erases happen.  Erases of string data can both insert
  47 /// new RopePieces (e.g. when the middle of some other rope piece is deleted,
  48 /// which results in two rope pieces, which is just like an insert) or it can
  49 /// reduce the number of RopePieces maintained by the B+Tree.  In the case when
  50 /// the number of RopePieces is reduced, we don't attempt to maintain the
  51 /// standard 'invariant' that each node in the tree contains at least
  52 /// 'WidthFactor' children/values.  For our use cases, this doesn't seem to
  53 /// matter.
  54 ///
  55 /// The implementation below is primarily implemented in terms of three classes:
  56 ///   RopePieceBTreeNode - Common base class for:
  57 ///
  58 ///     RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
  59 ///          nodes.  This directly represents a chunk of the string with those
  60 ///          RopePieces contatenated.
  61 ///     RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
  62 ///          up to '2*WidthFactor' other nodes in the tree.
  63
  64
  65 //===----------------------------------------------------------------------===//
  66 // RopePieceBTreeNode Class
  67 //===----------------------------------------------------------------------===//
  68
  69 namespace {
  70   /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
  71   /// RopePieceBTreeInterior.  This provides some 'virtual' dispatching methods
  72   /// and a flag that determines which subclass the instance is.  Also
  73   /// important, this node knows the full extend of the node, including any
  74   /// children that it has.  This allows efficient skipping over entire subtrees
  75   /// when looking for an offset in the BTree.
  76   class RopePieceBTreeNode {
  77   protected:
  78     /// WidthFactor - This controls the number of K/V slots held in the BTree:
  79     /// how wide it is.  Each level of the BTree is guaranteed to have at least
  80     /// 'WidthFactor' elements in it (either ropepieces or children), (except
  81     /// the root, which may have less) and may have at most 2*WidthFactor
  82     /// elements.
  83     enum { WidthFactor = 8 };
  84
  85     /// Size - This is the number of bytes of file this node (including any
  86     /// potential children) covers.
  87     unsigned Size;
  88
  89     /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
  90     /// is an instance of RopePieceBTreeInterior.
  91     bool IsLeaf;
  92
  93     RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {}
  94     ~RopePieceBTreeNode() {}
  95   public:
  96
  97     bool isLeaf() const { return IsLeaf; }
  98     unsigned size() const { return Size; }
  99
 100     void Destroy();
 101
 102     /// split - Split the range containing the specified offset so that we are
 103     /// guaranteed that there is a place to do an insertion at the specified
 104     /// offset.  The offset is relative, so "0" is the start of the node.
 105     ///
 106     /// If there is no space in this subtree for the extra piece, the extra tree
 107     /// node is returned and must be inserted into a parent.
 108     RopePieceBTreeNode *split(unsigned Offset);
 109
 110     /// insert - Insert the specified ropepiece into this tree node at the
 111     /// specified offset.  The offset is relative, so "0" is the start of the
 112     /// node.
 113     ///
 114     /// If there is no space in this subtree for the extra piece, the extra tree
 115     /// node is returned and must be inserted into a parent.
 116     RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
 117
 118     /// erase - Remove NumBytes from this node at the specified offset.  We are
 119     /// guaranteed that there is a split at Offset.
 120     void erase(unsigned Offset, unsigned NumBytes);
 121
 122     //static inline bool classof(const RopePieceBTreeNode *) { return true; }
 123
 124   };
 125 } // end anonymous namespace
 126
 127 //===----------------------------------------------------------------------===//
 128 // RopePieceBTreeLeaf Class
 129 //===----------------------------------------------------------------------===//
 130
 131 namespace {
 132   /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
 133   /// nodes.  This directly represents a chunk of the string with those
 134   /// RopePieces contatenated.  Since this is a B+Tree, all values (in this case
 135   /// instances of RopePiece) are stored in leaves like this.  To make iteration
 136   /// over the leaves efficient, they maintain a singly linked list through the
 137   /// NextLeaf field.  This allows the B+Tree forward iterator to be constant
 138   /// time for all increments.
 139   class RopePieceBTreeLeaf : public RopePieceBTreeNode {
 140     /// NumPieces - This holds the number of rope pieces currently active in the
 141     /// Pieces array.
 142     unsigned char NumPieces;
 143
 144     /// Pieces - This tracks the file chunks currently in this leaf.
 145     ///
 146     RopePiece Pieces[2*WidthFactor];
 147
 148     /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
 149     /// efficient in-order forward iteration of the tree without traversal.
 150     RopePieceBTreeLeaf **PrevLeaf, *NextLeaf;
 151   public:
 152     RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0),
 153                            PrevLeaf(0), NextLeaf(0) {}
 154     ~RopePieceBTreeLeaf() {
 155       if (PrevLeaf || NextLeaf)
 156         removeFromLeafInOrder();
 157       clear();
 158     }
 159
 160     bool isFull() const { return NumPieces == 2*WidthFactor; }
 161
 162     /// clear - Remove all rope pieces from this leaf.
 163     void clear() {
 164       while (NumPieces)
 165         Pieces[--NumPieces] = RopePiece();
 166       Size = 0;
 167     }
 168
 169     unsigned getNumPieces() const { return NumPieces; }
 170
 171     const RopePiece &getPiece(unsigned i) const {
 172       assert(i < getNumPieces() && "Invalid piece ID");
 173       return Pieces[i];
 174     }
 175
 176     const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
 177     void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
 178       assert(PrevLeaf == 0 && NextLeaf == 0 && "Already in ordering");
 179
 180       NextLeaf = Node->NextLeaf;
 181       if (NextLeaf)
 182         NextLeaf->PrevLeaf = &NextLeaf;
 183       PrevLeaf = &Node->NextLeaf;
 184       Node->NextLeaf = this;
 185     }
 186
 187     void removeFromLeafInOrder() {
 188       if (PrevLeaf) {
 189         *PrevLeaf = NextLeaf;
 190         if (NextLeaf)
 191           NextLeaf->PrevLeaf = PrevLeaf;
 192       } else if (NextLeaf) {
 193         NextLeaf->PrevLeaf = 0;
 194       }
 195     }
 196
 197     /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
 198     /// summing the size of all RopePieces.
 199     void FullRecomputeSizeLocally() {
 200       Size = 0;
 201       for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
 202         Size += getPiece(i).size();
 203     }
 204
 205     /// split - Split the range containing the specified offset so that we are
 206     /// guaranteed that there is a place to do an insertion at the specified
 207     /// offset.  The offset is relative, so "0" is the start of the node.
 208     ///
 209     /// If there is no space in this subtree for the extra piece, the extra tree
 210     /// node is returned and must be inserted into a parent.
 211     RopePieceBTreeNode *split(unsigned Offset);
 212
 213     /// insert - Insert the specified ropepiece into this tree node at the
 214     /// specified offset.  The offset is relative, so "0" is the start of the
 215     /// node.
 216     ///
 217     /// If there is no space in this subtree for the extra piece, the extra tree
 218     /// node is returned and must be inserted into a parent.
 219     RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
 220
 221
 222     /// erase - Remove NumBytes from this node at the specified offset.  We are
 223     /// guaranteed that there is a split at Offset.
 224     void erase(unsigned Offset, unsigned NumBytes);
 225
 226     //static inline bool classof(const RopePieceBTreeLeaf *) { return true; }
 227     static inline bool classof(const RopePieceBTreeNode *N) {
 228       return N->isLeaf();
 229     }
 230   };
 231 } // end anonymous namespace
 232
 233 /// split - Split the range containing the specified offset so that we are
 234 /// guaranteed that there is a place to do an insertion at the specified
 235 /// offset.  The offset is relative, so "0" is the start of the node.
 236 ///
 237 /// If there is no space in this subtree for the extra piece, the extra tree
 238 /// node is returned and must be inserted into a parent.
 239 RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {
 240   // Find the insertion point.  We are guaranteed that there is a split at the
 241   // specified offset so find it.
 242   if (Offset == 0 || Offset == size()) {
 243     // Fastpath for a common case.  There is already a splitpoint at the end.
 244     return 0;
 245   }
 246
 247   // Find the piece that this offset lands in.
 248   unsigned PieceOffs = 0;
 249   unsigned i = 0;
 250   while (Offset >= PieceOffs+Pieces[i].size()) {
 251     PieceOffs += Pieces[i].size();
 252     ++i;
 253   }
 254
 255   // If there is already a split point at the specified offset, just return
 256   // success.
 257   if (PieceOffs == Offset)
 258     return 0;
 259
 260   // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset
 261   // to being Piece relative.
 262   unsigned IntraPieceOffset = Offset-PieceOffs;
 263
 264   // We do this by shrinking the RopePiece and then doing an insert of the tail.
 265   RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
 266                  Pieces[i].EndOffs);
 267   Size -= Pieces[i].size();
 268   Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
 269   Size += Pieces[i].size();
 270
 271   return insert(Offset, Tail);
 272 }
 273
 274
 275 /// insert - Insert the specified RopePiece into this tree node at the
 276 /// specified offset.  The offset is relative, so "0" is the start of the node.
 277 ///
 278 /// If there is no space in this subtree for the extra piece, the extra tree
 279 /// node is returned and must be inserted into a parent.
 280 RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,
 281                                                const RopePiece &R) {
 282   // If this node is not full, insert the piece.
 283   if (!isFull()) {
 284     // Find the insertion point.  We are guaranteed that there is a split at the
 285     // specified offset so find it.
 286     unsigned i = 0, e = getNumPieces();
 287     if (Offset == size()) {
 288       // Fastpath for a common case.
 289       i = e;
 290     } else {
 291       unsigned SlotOffs = 0;
 292       for (; Offset > SlotOffs; ++i)
 293         SlotOffs += getPiece(i).size();
 294       assert(SlotOffs == Offset && "Split didn't occur before insertion!");
 295     }
 296
 297     // For an insertion into a non-full leaf node, just insert the value in
 298     // its sorted position.  This requires moving later values over.
 299     for (; i != e; --e)
 300       Pieces[e] = Pieces[e-1];
 301     Pieces[i] = R;
 302     ++NumPieces;
 303     Size += R.size();
 304     return 0;
 305   }
 306
 307   // Otherwise, if this is leaf is full, split it in two halves.  Since this
 308   // node is full, it contains 2*WidthFactor values.  We move the first
 309   // 'WidthFactor' values to the LHS child (which we leave in this node) and
 310   // move the last 'WidthFactor' values into the RHS child.
 311
 312   // Create the new node.
 313   RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
 314
 315   // Move over the last 'WidthFactor' values from here to NewNode.
 316   std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
 317             &NewNode->Pieces[0]);
 318   // Replace old pieces with null RopePieces to drop refcounts.
 319   std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
 320
 321   // Decrease the number of values in the two nodes.
 322   NewNode->NumPieces = NumPieces = WidthFactor;
 323
 324   // Recompute the two nodes' size.
 325   NewNode->FullRecomputeSizeLocally();
 326   FullRecomputeSizeLocally();
 327
 328   // Update the list of leaves.
 329   NewNode->insertAfterLeafInOrder(this);
 330
 331   // These insertions can't fail.
 332   if (this->size() >= Offset)
 333     this->insert(Offset, R);
 334   else
 335     NewNode->insert(Offset - this->size(), R);
 336   return NewNode;
 337 }
 338
 339 /// erase - Remove NumBytes from this node at the specified offset.  We are
 340 /// guaranteed that there is a split at Offset.
 341 void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
 342   // Since we are guaranteed that there is a split at Offset, we start by
 343   // finding the Piece that starts there.
 344   unsigned PieceOffs = 0;
 345   unsigned i = 0;
 346   for (; Offset > PieceOffs; ++i)
 347     PieceOffs += getPiece(i).size();
 348   assert(PieceOffs == Offset && "Split didn't occur before erase!");
 349
 350   unsigned StartPiece = i;
 351
 352   // Figure out how many pieces completely cover 'NumBytes'.  We want to remove
 353   // all of them.
 354   for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
 355     PieceOffs += getPiece(i).size();
 356
 357   // If we exactly include the last one, include it in the region to delete.
 358   if (Offset+NumBytes == PieceOffs+getPiece(i).size())
 359     PieceOffs += getPiece(i).size(), ++i;
 360
 361   // If we completely cover some RopePieces, erase them now.
 362   if (i != StartPiece) {
 363     unsigned NumDeleted = i-StartPiece;
 364     for (; i != getNumPieces(); ++i)
 365       Pieces[i-NumDeleted] = Pieces[i];
 366
 367     // Drop references to dead rope pieces.
 368     std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
 369               RopePiece());
 370     NumPieces -= NumDeleted;
 371
 372     unsigned CoverBytes = PieceOffs-Offset;
 373     NumBytes -= CoverBytes;
 374     Size -= CoverBytes;
 375   }
 376
 377   // If we completely removed some stuff, we could be done.
 378   if (NumBytes == 0) return;
 379
 380   // Okay, now might be erasing part of some Piece.  If this is the case, then
 381   // move the start point of the piece.
 382   assert(getPiece(StartPiece).size() > NumBytes);
 383   Pieces[StartPiece].StartOffs += NumBytes;
 384
 385   // The size of this node just shrunk by NumBytes.
 386   Size -= NumBytes;
 387 }
 388
 389 //===----------------------------------------------------------------------===//
 390 // RopePieceBTreeInterior Class
 391 //===----------------------------------------------------------------------===//
 392
 393 namespace {
 394   /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
 395   /// which holds up to 2*WidthFactor pointers to child nodes.
 396   class RopePieceBTreeInterior : public RopePieceBTreeNode {
 397     /// NumChildren - This holds the number of children currently active in the
 398     /// Children array.
 399     unsigned char NumChildren;
 400     RopePieceBTreeNode *Children[2*WidthFactor];
 401   public:
 402     RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {}
 403
 404     RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
 405     : RopePieceBTreeNode(false) {
 406       Children[0] = LHS;
 407       Children[1] = RHS;
 408       NumChildren = 2;
 409       Size = LHS->size() + RHS->size();
 410     }
 411
 412     bool isFull() const { return NumChildren == 2*WidthFactor; }
 413
 414     unsigned getNumChildren() const { return NumChildren; }
 415     const RopePieceBTreeNode *getChild(unsigned i) const {
 416       assert(i < NumChildren && "invalid child #");
 417       return Children[i];
 418     }
 419     RopePieceBTreeNode *getChild(unsigned i) {
 420       assert(i < NumChildren && "invalid child #");
 421       return Children[i];
 422     }
 423
 424     /// FullRecomputeSizeLocally - Recompute the Size field of this node by
 425     /// summing up the sizes of the child nodes.
 426     void FullRecomputeSizeLocally() {
 427       Size = 0;
 428       for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
 429         Size += getChild(i)->size();
 430     }
 431
 432
 433     /// split - Split the range containing the specified offset so that we are
 434     /// guaranteed that there is a place to do an insertion at the specified
 435     /// offset.  The offset is relative, so "0" is the start of the node.
 436     ///
 437     /// If there is no space in this subtree for the extra piece, the extra tree
 438     /// node is returned and must be inserted into a parent.
 439     RopePieceBTreeNode *split(unsigned Offset);
 440
 441
 442     /// insert - Insert the specified ropepiece into this tree node at the
 443     /// specified offset.  The offset is relative, so "0" is the start of the
 444     /// node.
 445     ///
 446     /// If there is no space in this subtree for the extra piece, the extra tree
 447     /// node is returned and must be inserted into a parent.
 448     RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
 449
 450     /// HandleChildPiece - A child propagated an insertion result up to us.
 451     /// Insert the new child, and/or propagate the result further up the tree.
 452     RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
 453
 454     /// erase - Remove NumBytes from this node at the specified offset.  We are
 455     /// guaranteed that there is a split at Offset.
 456     void erase(unsigned Offset, unsigned NumBytes);
 457
 458     //static inline bool classof(const RopePieceBTreeInterior *) { return true; }
 459     static inline bool classof(const RopePieceBTreeNode *N) {
 460       return !N->isLeaf();
 461     }
 462   };
 463 } // end anonymous namespace
 464
 465 /// split - Split the range containing the specified offset so that we are
 466 /// guaranteed that there is a place to do an insertion at the specified
 467 /// offset.  The offset is relative, so "0" is the start of the node.
 468 ///
 469 /// If there is no space in this subtree for the extra piece, the extra tree
 470 /// node is returned and must be inserted into a parent.
 471 RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
 472   // Figure out which child to split.
 473   if (Offset == 0 || Offset == size())
 474     return 0;  // If we have an exact offset, we're already split.
 475
 476   unsigned ChildOffset = 0;
 477   unsigned i = 0;
 478   for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
 479     ChildOffset += getChild(i)->size();
 480
 481   // If already split there, we're done.
 482   if (ChildOffset == Offset)
 483     return 0;
 484
 485   // Otherwise, recursively split the child.
 486   if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
 487     return HandleChildPiece(i, RHS);
 488   return 0;  // Done!
 489 }
 490
 491 /// insert - Insert the specified ropepiece into this tree node at the
 492 /// specified offset.  The offset is relative, so "0" is the start of the
 493 /// node.
 494 ///
 495 /// If there is no space in this subtree for the extra piece, the extra tree
 496 /// node is returned and must be inserted into a parent.
 497 RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
 498                                                    const RopePiece &R) {
 499   // Find the insertion point.  We are guaranteed that there is a split at the
 500   // specified offset so find it.
 501   unsigned i = 0, e = getNumChildren();
 502
 503   unsigned ChildOffs = 0;
 504   if (Offset == size()) {
 505     // Fastpath for a common case.  Insert at end of last child.
 506     i = e-1;
 507     ChildOffs = size()-getChild(i)->size();
 508   } else {
 509     for (; Offset > ChildOffs+getChild(i)->size(); ++i)
 510       ChildOffs += getChild(i)->size();
 511   }
 512
 513   Size += R.size();
 514
 515   // Insert at the end of this child.
 516   if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
 517     return HandleChildPiece(i, RHS);
 518
 519   return 0;
 520 }
 521
 522 /// HandleChildPiece - A child propagated an insertion result up to us.
 523 /// Insert the new child, and/or propagate the result further up the tree.
 524 RopePieceBTreeNode *
 525 RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
 526   // Otherwise the child propagated a subtree up to us as a new child.  See if
 527   // we have space for it here.
 528   if (!isFull()) {
 529     // Insert RHS after child 'i'.
 530     if (i + 1 != getNumChildren())
 531       memmove(&Children[i+2], &Children[i+1],
 532               (getNumChildren()-i-1)*sizeof(Children[0]));
 533     Children[i+1] = RHS;
 534     ++NumChildren;
 535     return 0;
 536   }
 537
 538   // Okay, this node is full.  Split it in half, moving WidthFactor children to
 539   // a newly allocated interior node.
 540
 541   // Create the new node.
 542   RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
 543
 544   // Move over the last 'WidthFactor' values from here to NewNode.
 545   memcpy(&NewNode->Children[0], &Children[WidthFactor],
 546          WidthFactor*sizeof(Children[0]));
 547
 548   // Decrease the number of values in the two nodes.
 549   NewNode->NumChildren = NumChildren = WidthFactor;
 550
 551   // Finally, insert the two new children in the side the can (now) hold them.
 552   // These insertions can't fail.
 553   if (i < WidthFactor)
 554     this->HandleChildPiece(i, RHS);
 555   else
 556     NewNode->HandleChildPiece(i-WidthFactor, RHS);
 557
 558   // Recompute the two nodes' size.
 559   NewNode->FullRecomputeSizeLocally();
 560   FullRecomputeSizeLocally();
 561   return NewNode;
 562 }
 563
 564 /// erase - Remove NumBytes from this node at the specified offset.  We are
 565 /// guaranteed that there is a split at Offset.
 566 void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
 567   // This will shrink this node by NumBytes.
 568   Size -= NumBytes;
 569
 570   // Find the first child that overlaps with Offset.
 571   unsigned i = 0;
 572   for (; Offset >= getChild(i)->size(); ++i)
 573     Offset -= getChild(i)->size();
 574
 575   // Propagate the delete request into overlapping children, or completely
 576   // delete the children as appropriate.
 577   while (NumBytes) {
 578     RopePieceBTreeNode *CurChild = getChild(i);
 579
 580     // If we are deleting something contained entirely in the child, pass on the
 581     // request.
 582     if (Offset+NumBytes < CurChild->size()) {
 583       CurChild->erase(Offset, NumBytes);
 584       return;
 585     }
 586
 587     // If this deletion request starts somewhere in the middle of the child, it
 588     // must be deleting to the end of the child.
 589     if (Offset) {
 590       unsigned BytesFromChild = CurChild->size()-Offset;
 591       CurChild->erase(Offset, BytesFromChild);
 592       NumBytes -= BytesFromChild;
 593       // Start at the beginning of the next child.
 594       Offset = 0;
 595       ++i;
 596       continue;
 597     }
 598
 599     // If the deletion request completely covers the child, delete it and move
 600     // the rest down.
 601     NumBytes -= CurChild->size();
 602     CurChild->Destroy();
 603     --NumChildren;
 604     if (i != getNumChildren())
 605       memmove(&Children[i], &Children[i+1],
 606               (getNumChildren()-i)*sizeof(Children[0]));
 607   }
 608 }
 609
 610 //===----------------------------------------------------------------------===//
 611 // RopePieceBTreeNode Implementation
 612 //===----------------------------------------------------------------------===//
 613
 614 void RopePieceBTreeNode::Destroy() {
 615   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 616     delete Leaf;
 617   else
 618     delete cast<RopePieceBTreeInterior>(this);
 619 }
 620
 621 /// split - Split the range containing the specified offset so that we are
 622 /// guaranteed that there is a place to do an insertion at the specified
 623 /// offset.  The offset is relative, so "0" is the start of the node.
 624 ///
 625 /// If there is no space in this subtree for the extra piece, the extra tree
 626 /// node is returned and must be inserted into a parent.
 627 RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
 628   assert(Offset <= size() && "Invalid offset to split!");
 629   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 630     return Leaf->split(Offset);
 631   return cast<RopePieceBTreeInterior>(this)->split(Offset);
 632 }
 633
 634 /// insert - Insert the specified ropepiece into this tree node at the
 635 /// specified offset.  The offset is relative, so "0" is the start of the
 636 /// node.
 637 ///
 638 /// If there is no space in this subtree for the extra piece, the extra tree
 639 /// node is returned and must be inserted into a parent.
 640 RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
 641                                                const RopePiece &R) {
 642   assert(Offset <= size() && "Invalid offset to insert!");
 643   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 644     return Leaf->insert(Offset, R);
 645   return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
 646 }
 647
 648 /// erase - Remove NumBytes from this node at the specified offset.  We are
 649 /// guaranteed that there is a split at Offset.
 650 void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
 651   assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
 652   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
 653     return Leaf->erase(Offset, NumBytes);
 654   return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
 655 }
 656
 657
 658 //===----------------------------------------------------------------------===//
 659 // RopePieceBTreeIterator Implementation
 660 //===----------------------------------------------------------------------===//
 661
 662 static const RopePieceBTreeLeaf *getCN(const void *P) {
 663   return static_cast<const RopePieceBTreeLeaf*>(P);
 664 }
 665
 666 // begin iterator.
 667 RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
 668   const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n);
 669
 670   // Walk down the left side of the tree until we get to a leaf.
 671   while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N))
 672     N = IN->getChild(0);
 673
 674   // We must have at least one leaf.
 675   CurNode = cast<RopePieceBTreeLeaf>(N);
 676
 677   // If we found a leaf that happens to be empty, skip over it until we get
 678   // to something full.
 679   while (CurNode && getCN(CurNode)->getNumPieces() == 0)
 680     CurNode = getCN(CurNode)->getNextLeafInOrder();
 681
 682   if (CurNode != 0)
 683     CurPiece = &getCN(CurNode)->getPiece(0);
 684   else  // Empty tree, this is an end() iterator.
 685     CurPiece = 0;
 686   CurChar = 0;
 687 }
 688
 689 void RopePieceBTreeIterator::MoveToNextPiece() {
 690   if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
 691     CurChar = 0;
 692     ++CurPiece;
 693     return;
 694   }
 695
 696   // Find the next non-empty leaf node.
 697   do
 698     CurNode = getCN(CurNode)->getNextLeafInOrder();
 699   while (CurNode && getCN(CurNode)->getNumPieces() == 0);
 700
 701   if (CurNode != 0)
 702     CurPiece = &getCN(CurNode)->getPiece(0);
 703   else // Hit end().
 704     CurPiece = 0;
 705   CurChar = 0;
 706 }
 707
 708 //===----------------------------------------------------------------------===//
 709 // RopePieceBTree Implementation
 710 //===----------------------------------------------------------------------===//
 711
 712 static RopePieceBTreeNode *getRoot(void *P) {
 713   return static_cast<RopePieceBTreeNode*>(P);
 714 }
 715
 716 RopePieceBTree::RopePieceBTree() {
 717   Root = new RopePieceBTreeLeaf();
 718 }
 719 RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
 720   assert(RHS.empty() && "Can't copy non-empty tree yet");
 721   Root = new RopePieceBTreeLeaf();
 722 }
 723 RopePieceBTree::~RopePieceBTree() {
 724   getRoot(Root)->Destroy();
 725 }
 726
 727 unsigned RopePieceBTree::size() const {
 728   return getRoot(Root)->size();
 729 }
 730
 731 void RopePieceBTree::clear() {
 732   if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
 733     Leaf->clear();
 734   else {
 735     getRoot(Root)->Destroy();
 736     Root = new RopePieceBTreeLeaf();
 737   }
 738 }
 739
 740 void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
 741   // #1. Split at Offset.
 742   if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
 743     Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
 744
 745   // #2. Do the insertion.
 746   if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
 747     Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
 748 }
 749
 750 void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
 751   // #1. Split at Offset.
 752   if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
 753     Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
 754
 755   // #2. Do the erasing.
 756   getRoot(Root)->erase(Offset, NumBytes);
 757 }
 758
 759 //===----------------------------------------------------------------------===//
 760 // RewriteRope Implementation
 761 //===----------------------------------------------------------------------===//
 762
 763 /// MakeRopeString - This copies the specified byte range into some instance of
 764 /// RopeRefCountString, and return a RopePiece that represents it.  This uses
 765 /// the AllocBuffer object to aggregate requests for small strings into one
 766 /// allocation instead of doing tons of tiny allocations.
 767 RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
 768   unsigned Len = End-Start;
 769   assert(Len && "Zero length RopePiece is invalid!");
 770
 771   // If we have space for this string in the current alloc buffer, use it.
 772   if (AllocOffs+Len <= AllocChunkSize) {
 773     memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
 774     AllocOffs += Len;
 775     return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
 776   }
 777
 778   // If we don't have enough room because this specific allocation is huge,
 779   // just allocate a new rope piece for it alone.
 780   if (Len > AllocChunkSize) {
 781     unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
 782     RopeRefCountString *Res =
 783       reinterpret_cast<RopeRefCountString *>(new char[Size]);
 784     Res->RefCount = 0;
 785     memcpy(Res->Data, Start, End-Start);
 786     return RopePiece(Res, 0, End-Start);
 787   }
 788
 789   // Otherwise, this was a small request but we just don't have space for it
 790   // Make a new chunk and share it with later allocations.
 791
 792   // If we had an old allocation, drop our reference to it.
 793   if (AllocBuffer && --AllocBuffer->RefCount == 0)
 794     delete [] (char*)AllocBuffer;
 795
 796   unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
 797   AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
 798   AllocBuffer->RefCount = 0;
 799   memcpy(AllocBuffer->Data, Start, Len);
 800   AllocOffs = Len;
 801
 802   // Start out the new allocation with a refcount of 1, since we have an
 803   // internal reference to it.
 804   AllocBuffer->addRef();
 805   return RopePiece(AllocBuffer, 0, Len);
 806 }
 807
 808