Lines Matching +full:erase +full:- +full:size
1 //===- RewriteRope.cpp - Rope specialized for rewriter --------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
57 /// RopePieceBTreeNode - Common base class for:
59 /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
62 /// RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
67 //===----------------------------------------------------------------------===//
69 //===----------------------------------------------------------------------===//
71 /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
79 /// WidthFactor - This controls the number of K/V slots held in the BTree:
86 /// Size - This is the number of bytes of file this node (including any
88 unsigned Size = 0; member in __anon1975f3b50111::RopePieceBTreeNode
90 /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
99 unsigned size() const { return Size; } in size() function in __anon1975f3b50111::RopePieceBTreeNode
103 /// split - Split the range containing the specified offset so that we are
111 /// insert - Insert the specified ropepiece into this tree node at the
119 /// erase - Remove NumBytes from this node at the specified offset. We are
121 void erase(unsigned Offset, unsigned NumBytes);
124 //===----------------------------------------------------------------------===//
126 //===----------------------------------------------------------------------===//
128 /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
136 /// NumPieces - This holds the number of rope pieces currently active in the
140 /// Pieces - This tracks the file chunks currently in this leaf.
143 /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
144 /// efficient in-order forward iteration of the tree without traversal.
159 /// clear - Remove all rope pieces from this leaf.
162 Pieces[--NumPieces] = RopePiece(); in clear()
163 Size = 0; in clear()
178 NextLeaf = Node->NextLeaf; in insertAfterLeafInOrder()
180 NextLeaf->PrevLeaf = &NextLeaf; in insertAfterLeafInOrder()
181 PrevLeaf = &Node->NextLeaf; in insertAfterLeafInOrder()
182 Node->NextLeaf = this; in insertAfterLeafInOrder()
189 NextLeaf->PrevLeaf = PrevLeaf; in removeFromLeafInOrder()
191 NextLeaf->PrevLeaf = nullptr; in removeFromLeafInOrder()
195 /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
196 /// summing the size of all RopePieces.
198 Size = 0; in FullRecomputeSizeLocally()
200 Size += getPiece(i).size(); in FullRecomputeSizeLocally()
203 /// split - Split the range containing the specified offset so that we are
211 /// insert - Insert the specified ropepiece into this tree node at the
219 /// erase - Remove NumBytes from this node at the specified offset. We are
221 void erase(unsigned Offset, unsigned NumBytes);
224 return N->isLeaf(); in classof()
230 /// split - Split the range containing the specified offset so that we are
239 if (Offset == 0 || Offset == size()) { in split()
247 while (Offset >= PieceOffs+Pieces[i].size()) { in split()
248 PieceOffs += Pieces[i].size(); in split()
257 // Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset in split()
259 unsigned IntraPieceOffset = Offset-PieceOffs; in split()
264 Size -= Pieces[i].size(); in split()
266 Size += Pieces[i].size(); in split()
271 /// insert - Insert the specified RopePiece into this tree node at the
283 if (Offset == size()) { in insert()
289 SlotOffs += getPiece(i).size(); in insert()
293 // For an insertion into a non-full leaf node, just insert the value in in insert()
295 for (; i != e; --e) in insert()
296 Pieces[e] = Pieces[e-1]; in insert()
299 Size += R.size(); in insert()
313 &NewNode->Pieces[0]); in insert()
318 NewNode->NumPieces = NumPieces = WidthFactor; in insert()
320 // Recompute the two nodes' size. in insert()
321 NewNode->FullRecomputeSizeLocally(); in insert()
325 NewNode->insertAfterLeafInOrder(this); in insert()
328 if (this->size() >= Offset) in insert()
329 this->insert(Offset, R); in insert()
331 NewNode->insert(Offset - this->size(), R); in insert()
335 /// erase - Remove NumBytes from this node at the specified offset. We are
337 void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) { in erase() function in RopePieceBTreeLeaf
343 PieceOffs += getPiece(i).size(); in erase()
344 assert(PieceOffs == Offset && "Split didn't occur before erase!"); in erase()
350 for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i) in erase()
351 PieceOffs += getPiece(i).size(); in erase()
354 if (Offset+NumBytes == PieceOffs+getPiece(i).size()) { in erase()
355 PieceOffs += getPiece(i).size(); in erase()
359 // If we completely cover some RopePieces, erase them now. in erase()
361 unsigned NumDeleted = i-StartPiece; in erase()
363 Pieces[i-NumDeleted] = Pieces[i]; in erase()
366 std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()], in erase()
368 NumPieces -= NumDeleted; in erase()
370 unsigned CoverBytes = PieceOffs-Offset; in erase()
371 NumBytes -= CoverBytes; in erase()
372 Size -= CoverBytes; in erase()
380 assert(getPiece(StartPiece).size() > NumBytes); in erase()
383 // The size of this node just shrunk by NumBytes. in erase()
384 Size -= NumBytes; in erase()
387 //===----------------------------------------------------------------------===//
389 //===----------------------------------------------------------------------===//
393 /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
396 /// NumChildren - This holds the number of children currently active in the
410 Size = LHS->size() + RHS->size(); in RopePieceBTreeInterior()
415 Children[i]->Destroy(); in ~RopePieceBTreeInterior()
432 /// FullRecomputeSizeLocally - Recompute the Size field of this node by
435 Size = 0; in FullRecomputeSizeLocally()
437 Size += getChild(i)->size(); in FullRecomputeSizeLocally()
440 /// split - Split the range containing the specified offset so that we are
448 /// insert - Insert the specified ropepiece into this tree node at the
456 /// HandleChildPiece - A child propagated an insertion result up to us.
460 /// erase - Remove NumBytes from this node at the specified offset. We are
462 void erase(unsigned Offset, unsigned NumBytes);
465 return !N->isLeaf(); in classof()
471 /// split - Split the range containing the specified offset so that we are
479 if (Offset == 0 || Offset == size()) in split()
484 for (; Offset >= ChildOffset+getChild(i)->size(); ++i) in split()
485 ChildOffset += getChild(i)->size(); in split()
492 if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset)) in split()
497 /// insert - Insert the specified ropepiece into this tree node at the
510 if (Offset == size()) { in insert()
512 i = e-1; in insert()
513 ChildOffs = size()-getChild(i)->size(); in insert()
515 for (; Offset > ChildOffs+getChild(i)->size(); ++i) in insert()
516 ChildOffs += getChild(i)->size(); in insert()
519 Size += R.size(); in insert()
522 if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R)) in insert()
528 /// HandleChildPiece - A child propagated an insertion result up to us.
538 (getNumChildren()-i-1)*sizeof(Children[0])); in HandleChildPiece()
551 memcpy(&NewNode->Children[0], &Children[WidthFactor], in HandleChildPiece()
555 NewNode->NumChildren = NumChildren = WidthFactor; in HandleChildPiece()
560 this->HandleChildPiece(i, RHS); in HandleChildPiece()
562 NewNode->HandleChildPiece(i-WidthFactor, RHS); in HandleChildPiece()
564 // Recompute the two nodes' size. in HandleChildPiece()
565 NewNode->FullRecomputeSizeLocally(); in HandleChildPiece()
570 /// erase - Remove NumBytes from this node at the specified offset. We are
572 void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) { in erase() function in RopePieceBTreeInterior
574 Size -= NumBytes; in erase()
578 for (; Offset >= getChild(i)->size(); ++i) in erase()
579 Offset -= getChild(i)->size(); in erase()
588 if (Offset+NumBytes < CurChild->size()) { in erase()
589 CurChild->erase(Offset, NumBytes); in erase()
596 unsigned BytesFromChild = CurChild->size()-Offset; in erase()
597 CurChild->erase(Offset, BytesFromChild); in erase()
598 NumBytes -= BytesFromChild; in erase()
607 NumBytes -= CurChild->size(); in erase()
608 CurChild->Destroy(); in erase()
609 --NumChildren; in erase()
612 (getNumChildren()-i)*sizeof(Children[0])); in erase()
616 //===----------------------------------------------------------------------===//
618 //===----------------------------------------------------------------------===//
627 /// split - Split the range containing the specified offset so that we are
634 assert(Offset <= size() && "Invalid offset to split!"); in split()
636 return Leaf->split(Offset); in split()
637 return cast<RopePieceBTreeInterior>(this)->split(Offset); in split()
640 /// insert - Insert the specified ropepiece into this tree node at the
648 assert(Offset <= size() && "Invalid offset to insert!"); in insert()
650 return Leaf->insert(Offset, R); in insert()
651 return cast<RopePieceBTreeInterior>(this)->insert(Offset, R); in insert()
654 /// erase - Remove NumBytes from this node at the specified offset. We are
656 void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) { in erase() function in RopePieceBTreeNode
657 assert(Offset+NumBytes <= size() && "Invalid offset to erase!"); in erase()
659 return Leaf->erase(Offset, NumBytes); in erase()
660 return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes); in erase()
663 //===----------------------------------------------------------------------===//
665 //===----------------------------------------------------------------------===//
677 N = IN->getChild(0); in RopePieceBTreeIterator()
684 while (CurNode && getCN(CurNode)->getNumPieces() == 0) in RopePieceBTreeIterator()
685 CurNode = getCN(CurNode)->getNextLeafInOrder(); in RopePieceBTreeIterator()
688 CurPiece = &getCN(CurNode)->getPiece(0); in RopePieceBTreeIterator()
695 if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) { in MoveToNextPiece()
701 // Find the next non-empty leaf node. in MoveToNextPiece()
703 CurNode = getCN(CurNode)->getNextLeafInOrder(); in MoveToNextPiece()
704 while (CurNode && getCN(CurNode)->getNumPieces() == 0); in MoveToNextPiece()
707 CurPiece = &getCN(CurNode)->getPiece(0); in MoveToNextPiece()
713 //===----------------------------------------------------------------------===//
715 //===----------------------------------------------------------------------===//
726 assert(RHS.empty() && "Can't copy non-empty tree yet"); in RopePieceBTree()
731 getRoot(Root)->Destroy(); in ~RopePieceBTree()
734 unsigned RopePieceBTree::size() const { in size() function in RopePieceBTree
735 return getRoot(Root)->size(); in size()
740 Leaf->clear(); in clear()
742 getRoot(Root)->Destroy(); in clear()
749 if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) in insert()
753 if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R)) in insert()
757 void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) { in erase() function in RopePieceBTree
759 if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) in erase()
763 getRoot(Root)->erase(Offset, NumBytes); in erase()
766 //===----------------------------------------------------------------------===//
768 //===----------------------------------------------------------------------===//
770 /// MakeRopeString - This copies the specified byte range into some instance of
775 unsigned Len = End-Start; in MakeRopeString()
780 memcpy(AllocBuffer->Data+AllocOffs, Start, Len); in MakeRopeString()
782 return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs); in MakeRopeString()
788 unsigned Size = End-Start+sizeof(RopeRefCountString)-1; in MakeRopeString() local
789 auto *Res = reinterpret_cast<RopeRefCountString *>(new char[Size]); in MakeRopeString()
790 Res->RefCount = 0; in MakeRopeString()
791 memcpy(Res->Data, Start, End-Start); in MakeRopeString()
792 return RopePiece(Res, 0, End-Start); in MakeRopeString()
800 Res->RefCount = 0; in MakeRopeString()
801 memcpy(Res->Data, Start, Len); in MakeRopeString()