41 /// the RopePiece corresponding to some offset very efficiently, and it
75 /// when looking for an offset in the BTree.
102   /// split - Split the range containing the specified offset so that we are
104   /// offset.  The offset is relative, so "0" is the start of the node.
108   RopePieceBTreeNode *split(unsigned Offset);
111   /// specified offset.  The offset is relative, so "0" is the start of the
116   RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
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);
202   /// split - Split the range containing the specified offset so that we are
204   /// offset.  The offset is relative, so "0" is the start of the node.
208   RopePieceBTreeNode *split(unsigned Offset);
211   /// specified offset.  The offset is relative, so "0" is the start of the
216   RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
218   /// erase - Remove NumBytes from this node at the specified offset.  We are
219   /// guaranteed that there is a split at Offset.
220   void erase(unsigned Offset, unsigned NumBytes);
227 /// split - Split the range containing the specified offset so that we are
229 /// offset.  The offset is relative, so "0" is the start of the node.
233 RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {  in split()  argument
235   // specified offset so find it.  in split()
236   if (Offset == 0 || Offset == size()) {  in split()
241   // Find the piece that this offset lands in.  in split()
244   while (Offset >= PieceOffs + Pieces[i].size()) {  in split()
249   // If there is already a split point at the specified offset, just return  in split()
251   if (PieceOffs == Offset)  in split()
254   // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset  in split()
256   unsigned IntraPieceOffset = Offset - PieceOffs;  in split()
265   return insert(Offset, Tail);  in split()
269 /// specified offset.  The offset is relative, so "0" is the start of the node.
273 RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,  in insert()  argument
278     // specified offset so find it.  in insert()
280     if (Offset == size()) {  in insert()
285       for (; Offset > SlotOffs; ++i)  in insert()
287       assert(SlotOffs == Offset && "Split didn't occur before insertion!");  in insert()
325   if (this->size() >= Offset)  in insert()
326     this->insert(Offset, R);  in insert()
328     NewNode->insert(Offset - this->size(), R);  in insert()
332 /// erase - Remove NumBytes from this node at the specified offset.  We are
333 /// guaranteed that there is a split at Offset.
334 void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {  in erase()  argument
335   // Since we are guaranteed that there is a split at Offset, we start by  in erase()
339   for (; Offset > PieceOffs; ++i)  in erase()
341   assert(PieceOffs == Offset && "Split didn't occur before erase!");  in erase()
347   for (; Offset + NumBytes > PieceOffs + getPiece(i).size(); ++i)  in erase()
351   if (Offset + NumBytes == PieceOffs + getPiece(i).size()) {  in erase()
367     unsigned CoverBytes = PieceOffs - Offset;  in erase()
438   /// split - Split the range containing the specified offset so that we are
440   /// offset.  The offset is relative, so "0" is the start of the node.
444   RopePieceBTreeNode *split(unsigned Offset);
447   /// specified offset.  The offset is relative, so "0" is the start of the
452   RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
458   /// erase - Remove NumBytes from this node at the specified offset.  We are
459   /// guaranteed that there is a split at Offset.
460   void erase(unsigned Offset, unsigned NumBytes);
467 /// split - Split the range containing the specified offset so that we are
469 /// offset.  The offset is relative, so "0" is the start of the node.
473 RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {  in split()  argument
475   if (Offset == 0 || Offset == size())  in split()
476     return nullptr; // If we have an exact offset, we're already split.  in split()
480   for (; Offset >= ChildOffset + getChild(i)->size(); ++i)  in split()
484   if (ChildOffset == Offset)  in split()
488   if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset - ChildOffset))  in split()
494 /// specified offset.  The offset is relative, so "0" is the start of the
499 RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,  in insert()  argument
502   // specified offset so find it.  in insert()
506   if (Offset == size()) {  in insert()
511     for (; Offset > ChildOffs + getChild(i)->size(); ++i)  in insert()
518   if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset - ChildOffs, R))  in insert()
566 /// erase - Remove NumBytes from this node at the specified offset.  We are
567 /// guaranteed that there is a split at Offset.
568 void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {  in erase()  argument
572   // Find the first child that overlaps with Offset.  in erase()
574   for (; Offset >= getChild(i)->size(); ++i)  in erase()
575     Offset -= getChild(i)->size();  in erase()
584     if (Offset + NumBytes < CurChild->size()) {  in erase()
585       CurChild->erase(Offset, NumBytes);  in erase()
591     if (Offset) {  in erase()
592       unsigned BytesFromChild = CurChild->size() - Offset;  in erase()
593       CurChild->erase(Offset, BytesFromChild);  in erase()
596       Offset = 0;  in erase()
623 /// split - Split the range containing the specified offset so that we are
625 /// offset.  The offset is relative, so "0" is the start of the node.
629 RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {  in split()  argument
630   assert(Offset <= size() && "Invalid offset to split!");  in split()
632     return Leaf->split(Offset);  in split()
633   return cast<RopePieceBTreeInterior>(this)->split(Offset);  in split()
637 /// specified offset.  The offset is relative, so "0" is the start of the
642 RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,  in insert()  argument
644   assert(Offset <= size() && "Invalid offset to insert!");  in insert()
646     return Leaf->insert(Offset, R);  in insert()
647   return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);  in insert()
650 /// erase - Remove NumBytes from this node at the specified offset.  We are
651 /// guaranteed that there is a split at Offset.
652 void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {  in erase()  argument
653   assert(Offset + NumBytes <= size() && "Invalid offset to erase!");  in erase()
655     return Leaf->erase(Offset, NumBytes);  in erase()
656   return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);  in erase()
738 void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {  in insert()  argument
739   // #1. Split at Offset.  in insert()
740   if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))  in insert()
744   if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))  in insert()
748 void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {  in erase()  argument
749   // #1. Split at Offset.  in erase()
750   if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))  in erase()
754   getRoot(Root)->erase(Offset, NumBytes);  in erase()