Bug Summary

File:src/gnu/usr.bin/clang/libclangRewrite/../../../llvm/clang/lib/Rewrite/RewriteRope.cpp
Warning:line 429, column 7
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

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