RewriteRope.cpp revision b9b309481369196b64bbf73e540d0c9b487e56a5
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> 17using namespace clang; 18using llvm::dyn_cast; 19using 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 69namespace { 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 131namespace { 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 const RopePieceBTreeLeaf *NextLeaf; 151 public: 152 RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0), NextLeaf(0){} 153 154 bool isFull() const { return NumPieces == 2*WidthFactor; } 155 156 /// clear - Remove all rope pieces from this leaf. 157 void clear() { 158 while (NumPieces) 159 Pieces[--NumPieces] = RopePiece(); 160 Size = 0; 161 } 162 163 unsigned getNumPieces() const { return NumPieces; } 164 165 const RopePiece &getPiece(unsigned i) const { 166 assert(i < getNumPieces() && "Invalid piece ID"); 167 return Pieces[i]; 168 } 169 170 const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; } 171 void setNextLeafInOrder(const RopePieceBTreeLeaf *NL) { NextLeaf = NL; } 172 173 /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by 174 /// summing the size of all RopePieces. 175 void FullRecomputeSizeLocally() { 176 Size = 0; 177 for (unsigned i = 0, e = getNumPieces(); i != e; ++i) 178 Size += getPiece(i).size(); 179 } 180 181 /// split - Split the range containing the specified offset so that we are 182 /// guaranteed that there is a place to do an insertion at the specified 183 /// offset. The offset is relative, so "0" is the start of the node. 184 /// 185 /// If there is no space in this subtree for the extra piece, the extra tree 186 /// node is returned and must be inserted into a parent. 187 RopePieceBTreeNode *split(unsigned Offset); 188 189 /// insert - Insert the specified ropepiece into this tree node at the 190 /// specified offset. The offset is relative, so "0" is the start of the 191 /// node. 192 /// 193 /// If there is no space in this subtree for the extra piece, the extra tree 194 /// node is returned and must be inserted into a parent. 195 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R); 196 197 198 /// erase - Remove NumBytes from this node at the specified offset. We are 199 /// guaranteed that there is a split at Offset. 200 void erase(unsigned Offset, unsigned NumBytes); 201 202 static inline bool classof(const RopePieceBTreeLeaf *) { return true; } 203 static inline bool classof(const RopePieceBTreeNode *N) { 204 return N->isLeaf(); 205 } 206 }; 207} // end anonymous namespace 208 209/// split - Split the range containing the specified offset so that we are 210/// guaranteed that there is a place to do an insertion at the specified 211/// offset. The offset is relative, so "0" is the start of the node. 212/// 213/// If there is no space in this subtree for the extra piece, the extra tree 214/// node is returned and must be inserted into a parent. 215RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) { 216 // Find the insertion point. We are guaranteed that there is a split at the 217 // specified offset so find it. 218 if (Offset == 0 || Offset == size()) { 219 // Fastpath for a common case. There is already a splitpoint at the end. 220 return 0; 221 } 222 223 // Find the piece that this offset lands in. 224 unsigned PieceOffs = 0; 225 unsigned i = 0; 226 while (Offset >= PieceOffs+Pieces[i].size()) { 227 PieceOffs += Pieces[i].size(); 228 ++i; 229 } 230 231 // If there is already a split point at the specified offset, just return 232 // success. 233 if (PieceOffs == Offset) 234 return 0; 235 236 // Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset 237 // to being Piece relative. 238 unsigned IntraPieceOffset = Offset-PieceOffs; 239 240 // We do this by shrinking the RopePiece and then doing an insert of the tail. 241 RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset, 242 Pieces[i].EndOffs); 243 Size -= Pieces[i].size(); 244 Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset; 245 Size += Pieces[i].size(); 246 247 return insert(Offset, Tail); 248} 249 250 251/// insert - Insert the specified RopePiece into this tree node at the 252/// specified offset. The offset is relative, so "0" is the start of the node. 253/// 254/// If there is no space in this subtree for the extra piece, the extra tree 255/// node is returned and must be inserted into a parent. 256RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset, 257 const RopePiece &R) { 258 // If this node is not full, insert the piece. 259 if (!isFull()) { 260 // Find the insertion point. We are guaranteed that there is a split at the 261 // specified offset so find it. 262 unsigned i = 0, e = getNumPieces(); 263 if (Offset == size()) { 264 // Fastpath for a common case. 265 i = e; 266 } else { 267 unsigned SlotOffs = 0; 268 for (; Offset > SlotOffs; ++i) 269 SlotOffs += getPiece(i).size(); 270 assert(SlotOffs == Offset && "Split didn't occur before insertion!"); 271 } 272 273 // For an insertion into a non-full leaf node, just insert the value in 274 // its sorted position. This requires moving later values over. 275 for (; i != e; --e) 276 Pieces[e] = Pieces[e-1]; 277 Pieces[i] = R; 278 ++NumPieces; 279 Size += R.size(); 280 return 0; 281 } 282 283 // Otherwise, if this is leaf is full, split it in two halves. Since this 284 // node is full, it contains 2*WidthFactor values. We move the first 285 // 'WidthFactor' values to the LHS child (which we leave in this node) and 286 // move the last 'WidthFactor' values into the RHS child. 287 288 // Create the new node. 289 RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf(); 290 291 // Move over the last 'WidthFactor' values from here to NewNode. 292 std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor], 293 &NewNode->Pieces[0]); 294 // Replace old pieces with null RopePieces to drop refcounts. 295 std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece()); 296 297 // Decrease the number of values in the two nodes. 298 NewNode->NumPieces = NumPieces = WidthFactor; 299 300 // Recompute the two nodes' size. 301 NewNode->FullRecomputeSizeLocally(); 302 FullRecomputeSizeLocally(); 303 304 // Update the list of leaves. 305 NewNode->setNextLeafInOrder(this->getNextLeafInOrder()); 306 this->setNextLeafInOrder(NewNode); 307 308 // These insertions can't fail. 309 if (this->size() >= Offset) 310 this->insert(Offset, R); 311 else 312 NewNode->insert(Offset - this->size(), R); 313 return NewNode; 314} 315 316/// erase - Remove NumBytes from this node at the specified offset. We are 317/// guaranteed that there is a split at Offset. 318void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) { 319 // Since we are guaranteed that there is a split at Offset, we start by 320 // finding the Piece that starts there. 321 unsigned PieceOffs = 0; 322 unsigned i = 0; 323 for (; Offset > PieceOffs; ++i) 324 PieceOffs += getPiece(i).size(); 325 assert(PieceOffs == Offset && "Split didn't occur before erase!"); 326 327 unsigned StartPiece = i; 328 329 // Figure out how many pieces completely cover 'NumBytes'. We want to remove 330 // all of them. 331 for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i) 332 PieceOffs += getPiece(i).size(); 333 334 // If we exactly include the last one, include it in the region to delete. 335 if (Offset+NumBytes == PieceOffs+getPiece(i).size()) 336 PieceOffs += getPiece(i).size(), ++i; 337 338 // If we completely cover some RopePieces, erase them now. 339 if (i != StartPiece) { 340 unsigned NumDeleted = i-StartPiece; 341 for (; i != getNumPieces(); ++i) 342 Pieces[i-NumDeleted] = Pieces[i]; 343 344 // Drop references to dead rope pieces. 345 std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()], 346 RopePiece()); 347 NumPieces -= NumDeleted; 348 349 unsigned CoverBytes = PieceOffs-Offset; 350 NumBytes -= CoverBytes; 351 Size -= CoverBytes; 352 } 353 354 // If we completely removed some stuff, we could be done. 355 if (NumBytes == 0) return; 356 357 // Okay, now might be erasing part of some Piece. If this is the case, then 358 // move the start point of the piece. 359 assert(getPiece(StartPiece).size() > NumBytes); 360 Pieces[StartPiece].StartOffs += NumBytes; 361 362 // The size of this node just shrunk by NumBytes. 363 Size -= NumBytes; 364} 365 366//===----------------------------------------------------------------------===// 367// RopePieceBTreeInterior Class 368//===----------------------------------------------------------------------===// 369 370namespace { 371 /// RopePieceBTreeInterior - This represents an interior node in the B+Tree, 372 /// which holds up to 2*WidthFactor pointers to child nodes. 373 class RopePieceBTreeInterior : public RopePieceBTreeNode { 374 /// NumChildren - This holds the number of children currently active in the 375 /// Children array. 376 unsigned char NumChildren; 377 RopePieceBTreeNode *Children[2*WidthFactor]; 378 public: 379 RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {} 380 381 RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS) 382 : RopePieceBTreeNode(false) { 383 Children[0] = LHS; 384 Children[1] = RHS; 385 NumChildren = 2; 386 Size = LHS->size() + RHS->size(); 387 } 388 389 bool isFull() const { return NumChildren == 2*WidthFactor; } 390 391 unsigned getNumChildren() const { return NumChildren; } 392 const RopePieceBTreeNode *getChild(unsigned i) const { 393 assert(i < NumChildren && "invalid child #"); 394 return Children[i]; 395 } 396 RopePieceBTreeNode *getChild(unsigned i) { 397 assert(i < NumChildren && "invalid child #"); 398 return Children[i]; 399 } 400 401 /// FullRecomputeSizeLocally - Recompute the Size field of this node by 402 /// summing up the sizes of the child nodes. 403 void FullRecomputeSizeLocally() { 404 Size = 0; 405 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 406 Size += getChild(i)->size(); 407 } 408 409 410 /// split - Split the range containing the specified offset so that we are 411 /// guaranteed that there is a place to do an insertion at the specified 412 /// offset. The offset is relative, so "0" is the start of the node. 413 /// 414 /// If there is no space in this subtree for the extra piece, the extra tree 415 /// node is returned and must be inserted into a parent. 416 RopePieceBTreeNode *split(unsigned Offset); 417 418 419 /// insert - Insert the specified ropepiece into this tree node at the 420 /// specified offset. The offset is relative, so "0" is the start of the 421 /// node. 422 /// 423 /// If there is no space in this subtree for the extra piece, the extra tree 424 /// node is returned and must be inserted into a parent. 425 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R); 426 427 /// HandleChildPiece - A child propagated an insertion result up to us. 428 /// Insert the new child, and/or propagate the result further up the tree. 429 RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS); 430 431 /// erase - Remove NumBytes from this node at the specified offset. We are 432 /// guaranteed that there is a split at Offset. 433 void erase(unsigned Offset, unsigned NumBytes); 434 435 static inline bool classof(const RopePieceBTreeInterior *) { return true; } 436 static inline bool classof(const RopePieceBTreeNode *N) { 437 return !N->isLeaf(); 438 } 439 }; 440} // end anonymous namespace 441 442/// split - Split the range containing the specified offset so that we are 443/// guaranteed that there is a place to do an insertion at the specified 444/// offset. The offset is relative, so "0" is the start of the 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. 448RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) { 449 // Figure out which child to split. 450 if (Offset == 0 || Offset == size()) 451 return 0; // If we have an exact offset, we're already split. 452 453 unsigned ChildOffset = 0; 454 unsigned i = 0; 455 for (; Offset >= ChildOffset+getChild(i)->size(); ++i) 456 ChildOffset += getChild(i)->size(); 457 458 // If already split there, we're done. 459 if (ChildOffset == Offset) 460 return 0; 461 462 // Otherwise, recursively split the child. 463 if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset)) 464 return HandleChildPiece(i, RHS); 465 return 0; // Done! 466} 467 468/// insert - Insert the specified ropepiece into this tree node at the 469/// specified offset. The offset is relative, so "0" is the start of the 470/// node. 471/// 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. 474RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset, 475 const RopePiece &R) { 476 // Find the insertion point. We are guaranteed that there is a split at the 477 // specified offset so find it. 478 unsigned i = 0, e = getNumChildren(); 479 480 unsigned ChildOffs = 0; 481 if (Offset == size()) { 482 // Fastpath for a common case. Insert at end of last child. 483 i = e-1; 484 ChildOffs = size()-getChild(i)->size(); 485 } else { 486 for (; Offset > ChildOffs+getChild(i)->size(); ++i) 487 ChildOffs += getChild(i)->size(); 488 } 489 490 Size += R.size(); 491 492 // Insert at the end of this child. 493 if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R)) 494 return HandleChildPiece(i, RHS); 495 496 return 0; 497} 498 499/// HandleChildPiece - A child propagated an insertion result up to us. 500/// Insert the new child, and/or propagate the result further up the tree. 501RopePieceBTreeNode * 502RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) { 503 // Otherwise the child propagated a subtree up to us as a new child. See if 504 // we have space for it here. 505 if (!isFull()) { 506 // Insert RHS after child 'i'. 507 if (i + 1 != getNumChildren()) 508 memmove(&Children[i+2], &Children[i+1], 509 (getNumChildren()-i-1)*sizeof(Children[0])); 510 Children[i+1] = RHS; 511 ++NumChildren; 512 return false; 513 } 514 515 // Okay, this node is full. Split it in half, moving WidthFactor children to 516 // a newly allocated interior node. 517 518 // Create the new node. 519 RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior(); 520 521 // Move over the last 'WidthFactor' values from here to NewNode. 522 memcpy(&NewNode->Children[0], &Children[WidthFactor], 523 WidthFactor*sizeof(Children[0])); 524 525 // Decrease the number of values in the two nodes. 526 NewNode->NumChildren = NumChildren = WidthFactor; 527 528 // Finally, insert the two new children in the side the can (now) hold them. 529 // These insertions can't fail. 530 if (i < WidthFactor) 531 this->HandleChildPiece(i, RHS); 532 else 533 NewNode->HandleChildPiece(i-WidthFactor, RHS); 534 535 // Recompute the two nodes' size. 536 NewNode->FullRecomputeSizeLocally(); 537 FullRecomputeSizeLocally(); 538 return NewNode; 539} 540 541/// erase - Remove NumBytes from this node at the specified offset. We are 542/// guaranteed that there is a split at Offset. 543void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) { 544 // This will shrink this node by NumBytes. 545 Size -= NumBytes; 546 547 // Find the first child that overlaps with Offset. 548 unsigned i = 0; 549 for (; Offset >= getChild(i)->size(); ++i) 550 Offset -= getChild(i)->size(); 551 552 // Propagate the delete request into overlapping children, or completely 553 // delete the children as appropriate. 554 while (NumBytes) { 555 RopePieceBTreeNode *CurChild = getChild(i); 556 557 // If we are deleting something contained entirely in the child, pass on the 558 // request. 559 if (Offset+NumBytes < CurChild->size()) { 560 CurChild->erase(Offset, NumBytes); 561 return; 562 } 563 564 // If this deletion request starts somewhere in the middle of the child, it 565 // must be deleting to the end of the child. 566 if (Offset) { 567 unsigned BytesFromChild = CurChild->size()-Offset; 568 CurChild->erase(Offset, BytesFromChild); 569 NumBytes -= BytesFromChild; 570 ++i; 571 continue; 572 } 573 574 // If the deletion request completely covers the child, delete it and move 575 // the rest down. 576 NumBytes -= CurChild->size(); 577 CurChild->Destroy(); 578 --NumChildren; 579 if (i+1 != getNumChildren()) 580 memmove(&Children[i], &Children[i+1], 581 (getNumChildren()-i)*sizeof(Children[0])); 582 } 583} 584 585//===----------------------------------------------------------------------===// 586// RopePieceBTreeNode Implementation 587//===----------------------------------------------------------------------===// 588 589void RopePieceBTreeNode::Destroy() { 590 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 591 delete Leaf; 592 else 593 delete cast<RopePieceBTreeInterior>(this); 594} 595 596/// split - Split the range containing the specified offset so that we are 597/// guaranteed that there is a place to do an insertion at the specified 598/// offset. The offset is relative, so "0" is the start of the node. 599/// 600/// If there is no space in this subtree for the extra piece, the extra tree 601/// node is returned and must be inserted into a parent. 602RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) { 603 assert(Offset <= size() && "Invalid offset to split!"); 604 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 605 return Leaf->split(Offset); 606 return cast<RopePieceBTreeInterior>(this)->split(Offset); 607} 608 609/// insert - Insert the specified ropepiece into this tree node at the 610/// specified offset. The offset is relative, so "0" is the start of the 611/// node. 612/// 613/// If there is no space in this subtree for the extra piece, the extra tree 614/// node is returned and must be inserted into a parent. 615RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset, 616 const RopePiece &R) { 617 assert(Offset <= size() && "Invalid offset to insert!"); 618 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 619 return Leaf->insert(Offset, R); 620 return cast<RopePieceBTreeInterior>(this)->insert(Offset, R); 621} 622 623/// erase - Remove NumBytes from this node at the specified offset. We are 624/// guaranteed that there is a split at Offset. 625void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) { 626 assert(Offset+NumBytes <= size() && "Invalid offset to erase!"); 627 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 628 return Leaf->erase(Offset, NumBytes); 629 return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes); 630} 631 632 633//===----------------------------------------------------------------------===// 634// RopePieceBTreeIterator Implementation 635//===----------------------------------------------------------------------===// 636 637static const RopePieceBTreeLeaf *getCN(const void *P) { 638 return static_cast<const RopePieceBTreeLeaf*>(P); 639} 640 641// begin iterator. 642RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) { 643 const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n); 644 645 // Walk down the left side of the tree until we get to a leaf. 646 while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N)) 647 N = IN->getChild(0); 648 649 // We must have at least one leaf. 650 CurNode = cast<RopePieceBTreeLeaf>(N); 651 652 // If we found a leaf that happens to be empty, skip over it until we get 653 // to something full. 654 while (CurNode && getCN(CurNode)->getNumPieces() == 0) 655 CurNode = getCN(CurNode)->getNextLeafInOrder(); 656 657 if (CurNode != 0) 658 CurPiece = &getCN(CurNode)->getPiece(0); 659 else // Empty tree, this is an end() iterator. 660 CurPiece = 0; 661 CurChar = 0; 662} 663 664void RopePieceBTreeIterator::MoveToNextPiece() { 665 if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) { 666 CurChar = 0; 667 ++CurPiece; 668 return; 669 } 670 671 // Find the next non-empty leaf node. 672 do 673 CurNode = getCN(CurNode)->getNextLeafInOrder(); 674 while (CurNode && getCN(CurNode)->getNumPieces() == 0); 675 676 if (CurNode != 0) 677 CurPiece = &getCN(CurNode)->getPiece(0); 678 else // Hit end(). 679 CurPiece = 0; 680 CurChar = 0; 681} 682 683//===----------------------------------------------------------------------===// 684// RopePieceBTree Implementation 685//===----------------------------------------------------------------------===// 686 687static RopePieceBTreeNode *getRoot(void *P) { 688 return static_cast<RopePieceBTreeNode*>(P); 689} 690 691RopePieceBTree::RopePieceBTree() { 692 Root = new RopePieceBTreeLeaf(); 693} 694RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) { 695 assert(RHS.empty() && "Can't copy non-empty tree yet"); 696 Root = new RopePieceBTreeLeaf(); 697} 698RopePieceBTree::~RopePieceBTree() { 699 getRoot(Root)->Destroy(); 700} 701 702unsigned RopePieceBTree::size() const { 703 return getRoot(Root)->size(); 704} 705 706void RopePieceBTree::clear() { 707 if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root))) 708 Leaf->clear(); 709 else { 710 getRoot(Root)->Destroy(); 711 Root = new RopePieceBTreeLeaf(); 712 } 713} 714 715void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) { 716 // #1. Split at Offset. 717 if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) 718 Root = new RopePieceBTreeInterior(getRoot(Root), RHS); 719 720 // #2. Do the insertion. 721 if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R)) 722 Root = new RopePieceBTreeInterior(getRoot(Root), RHS); 723} 724 725void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) { 726 // #1. Split at Offset. 727 if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) 728 Root = new RopePieceBTreeInterior(getRoot(Root), RHS); 729 730 // #2. Do the erasing. 731 getRoot(Root)->erase(Offset, NumBytes); 732} 733 734//===----------------------------------------------------------------------===// 735// RewriteRope Implementation 736//===----------------------------------------------------------------------===// 737 738/// MakeRopeString - This copies the specified byte range into some instance of 739/// RopeRefCountString, and return a RopePiece that represents it. This uses 740/// the AllocBuffer object to aggregate requests for small strings into one 741/// allocation instead of doing tons of tiny allocations. 742RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) { 743 unsigned Len = End-Start; 744 745 // If we have space for this string in the current alloc buffer, use it. 746 if (AllocOffs+Len <= AllocChunkSize) { 747 memcpy(AllocBuffer->Data+AllocOffs, Start, Len); 748 AllocOffs += Len; 749 return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs); 750 } 751 752 // If we don't have enough room because this specific allocation is huge, 753 // just allocate a new rope piece for it alone. 754 if (Len > AllocChunkSize) { 755 unsigned Size = End-Start+sizeof(RopeRefCountString)-1; 756 RopeRefCountString *Res = 757 reinterpret_cast<RopeRefCountString *>(new char[Size]); 758 Res->RefCount = 0; 759 memcpy(Res->Data, Start, End-Start); 760 return RopePiece(Res, 0, End-Start); 761 } 762 763 // Otherwise, this was a small request but we just don't have space for it 764 // Make a new chunk and share it with later allocations. 765 766 // If we had an old allocation, drop our reference to it. 767 if (AllocBuffer && --AllocBuffer->RefCount == 0) 768 delete [] (char*)AllocBuffer; 769 770 unsigned AllocSize = sizeof(RopeRefCountString)-1+AllocChunkSize; 771 AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]); 772 AllocBuffer->RefCount = 0; 773 memcpy(AllocBuffer->Data, Start, Len); 774 AllocOffs = Len; 775 776 // Start out the new allocation with a refcount of 1, since we have an 777 // internal reference to it. 778 AllocBuffer->addRef(); 779 return RopePiece(AllocBuffer, 0, Len); 780} 781 782 783