/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Rewrite/RewriteRope.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | |
20 | | using 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 | | |
65 | | namespace { |
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 | 82.0k | RopePieceBTreeNode(bool isLeaf) : IsLeaf(isLeaf) {} |
95 | | ~RopePieceBTreeNode() = default; |
96 | | |
97 | | public: |
98 | 1.44M | bool isLeaf() const { return IsLeaf; } |
99 | 6.84M | 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 | 79.0k | RopePieceBTreeLeaf() : RopePieceBTreeNode(true) {} |
150 | | |
151 | 79.0k | ~RopePieceBTreeLeaf() { |
152 | 79.0k | if (PrevLeaf || NextLeaf79.0k ) |
153 | 16.4k | removeFromLeafInOrder(); |
154 | 79.0k | clear(); |
155 | 79.0k | } |
156 | | |
157 | 318k | bool isFull() const { return NumPieces == 2*WidthFactor; } |
158 | | |
159 | | /// clear - Remove all rope pieces from this leaf. |
160 | 99.8k | void clear() { |
161 | 399k | while (NumPieces) |
162 | 299k | Pieces[--NumPieces] = RopePiece(); |
163 | 99.8k | Size = 0; |
164 | 99.8k | } |
165 | | |
166 | 2.67M | unsigned getNumPieces() const { return NumPieces; } |
167 | | |
168 | 1.98M | const RopePiece &getPiece(unsigned i) const { |
169 | 1.98M | assert(i < getNumPieces() && "Invalid piece ID"); |
170 | 0 | return Pieces[i]; |
171 | 1.98M | } |
172 | | |
173 | 38.4k | const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; } |
174 | | |
175 | 16.4k | void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) { |
176 | 16.4k | assert(!PrevLeaf && !NextLeaf && "Already in ordering"); |
177 | | |
178 | 0 | NextLeaf = Node->NextLeaf; |
179 | 16.4k | if (NextLeaf) |
180 | 13.1k | NextLeaf->PrevLeaf = &NextLeaf; |
181 | 16.4k | PrevLeaf = &Node->NextLeaf; |
182 | 16.4k | Node->NextLeaf = this; |
183 | 16.4k | } |
184 | | |
185 | 16.4k | void removeFromLeafInOrder() { |
186 | 16.4k | if (PrevLeaf) { |
187 | 1 | *PrevLeaf = NextLeaf; |
188 | 1 | if (NextLeaf) |
189 | 1 | NextLeaf->PrevLeaf = PrevLeaf; |
190 | 16.4k | } else if (NextLeaf) { |
191 | 16.4k | NextLeaf->PrevLeaf = nullptr; |
192 | 16.4k | } |
193 | 16.4k | } |
194 | | |
195 | | /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by |
196 | | /// summing the size of all RopePieces. |
197 | 32.8k | void FullRecomputeSizeLocally() { |
198 | 32.8k | Size = 0; |
199 | 295k | for (unsigned i = 0, e = getNumPieces(); i != e; ++i262k ) |
200 | 262k | Size += getPiece(i).size(); |
201 | 32.8k | } |
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 | 1.00M | static bool classof(const RopePieceBTreeNode *N) { |
224 | 1.00M | return N->isLeaf(); |
225 | 1.00M | } |
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. |
236 | 233k | RopePieceBTreeNode *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 | 233k | if (Offset == 0 || Offset == size()210k ) { |
240 | | // Fastpath for a common case. There is already a splitpoint at the end. |
241 | 24.3k | return nullptr; |
242 | 24.3k | } |
243 | | |
244 | | // Find the piece that this offset lands in. |
245 | 209k | unsigned PieceOffs = 0; |
246 | 209k | unsigned i = 0; |
247 | 938k | while (Offset >= PieceOffs+Pieces[i].size()) { |
248 | 729k | PieceOffs += Pieces[i].size(); |
249 | 729k | ++i; |
250 | 729k | } |
251 | | |
252 | | // If there is already a split point at the specified offset, just return |
253 | | // success. |
254 | 209k | if (PieceOffs == Offset) |
255 | 76.7k | return nullptr; |
256 | | |
257 | | // Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset |
258 | | // to being Piece relative. |
259 | 132k | unsigned IntraPieceOffset = Offset-PieceOffs; |
260 | | |
261 | | // We do this by shrinking the RopePiece and then doing an insert of the tail. |
262 | 132k | RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset, |
263 | 132k | Pieces[i].EndOffs); |
264 | 132k | Size -= Pieces[i].size(); |
265 | 132k | Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset; |
266 | 132k | Size += Pieces[i].size(); |
267 | | |
268 | 132k | return insert(Offset, Tail); |
269 | 209k | } |
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. |
276 | | RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset, |
277 | 318k | const RopePiece &R) { |
278 | | // If this node is not full, insert the piece. |
279 | 318k | if (!isFull()) { |
280 | | // Find the insertion point. We are guaranteed that there is a split at the |
281 | | // specified offset so find it. |
282 | 301k | unsigned i = 0, e = getNumPieces(); |
283 | 301k | if (Offset == size()) { |
284 | | // Fastpath for a common case. |
285 | 58.9k | i = e; |
286 | 242k | } else { |
287 | 242k | unsigned SlotOffs = 0; |
288 | 1.28M | for (; Offset > SlotOffs; ++i1.03M ) |
289 | 1.03M | SlotOffs += getPiece(i).size(); |
290 | 242k | assert(SlotOffs == Offset && "Split didn't occur before insertion!"); |
291 | 242k | } |
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 | 1.43M | for (; i != e; --e1.13M ) |
296 | 1.13M | Pieces[e] = Pieces[e-1]; |
297 | 301k | Pieces[i] = R; |
298 | 301k | ++NumPieces; |
299 | 301k | Size += R.size(); |
300 | 301k | return nullptr; |
301 | 301k | } |
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 | 16.4k | RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf(); |
310 | | |
311 | | // Move over the last 'WidthFactor' values from here to NewNode. |
312 | 16.4k | std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor], |
313 | 16.4k | &NewNode->Pieces[0]); |
314 | | // Replace old pieces with null RopePieces to drop refcounts. |
315 | 16.4k | std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece()); |
316 | | |
317 | | // Decrease the number of values in the two nodes. |
318 | 16.4k | NewNode->NumPieces = NumPieces = WidthFactor; |
319 | | |
320 | | // Recompute the two nodes' size. |
321 | 16.4k | NewNode->FullRecomputeSizeLocally(); |
322 | 16.4k | FullRecomputeSizeLocally(); |
323 | | |
324 | | // Update the list of leaves. |
325 | 16.4k | NewNode->insertAfterLeafInOrder(this); |
326 | | |
327 | | // These insertions can't fail. |
328 | 16.4k | if (this->size() >= Offset) |
329 | 3.64k | this->insert(Offset, R); |
330 | 12.7k | else |
331 | 12.7k | NewNode->insert(Offset - this->size(), R); |
332 | 16.4k | return NewNode; |
333 | 318k | } |
334 | | |
335 | | /// erase - Remove NumBytes from this node at the specified offset. We are |
336 | | /// guaranteed that there is a split at Offset. |
337 | 67.5k | void 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 | 67.5k | unsigned PieceOffs = 0; |
341 | 67.5k | unsigned i = 0; |
342 | 188k | for (; Offset > PieceOffs; ++i120k ) |
343 | 120k | PieceOffs += getPiece(i).size(); |
344 | 67.5k | assert(PieceOffs == Offset && "Split didn't occur before erase!"); |
345 | | |
346 | 0 | unsigned StartPiece = i; |
347 | | |
348 | | // Figure out how many pieces completely cover 'NumBytes'. We want to remove |
349 | | // all of them. |
350 | 68.1k | for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i564 ) |
351 | 564 | PieceOffs += getPiece(i).size(); |
352 | | |
353 | | // If we exactly include the last one, include it in the region to delete. |
354 | 67.5k | if (Offset+NumBytes == PieceOffs+getPiece(i).size()) { |
355 | 1.10k | PieceOffs += getPiece(i).size(); |
356 | 1.10k | ++i; |
357 | 1.10k | } |
358 | | |
359 | | // If we completely cover some RopePieces, erase them now. |
360 | 67.5k | if (i != StartPiece) { |
361 | 1.34k | unsigned NumDeleted = i-StartPiece; |
362 | 5.73k | for (; i != getNumPieces(); ++i4.39k ) |
363 | 4.39k | Pieces[i-NumDeleted] = Pieces[i]; |
364 | | |
365 | | // Drop references to dead rope pieces. |
366 | 1.34k | std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()], |
367 | 1.34k | RopePiece()); |
368 | 1.34k | NumPieces -= NumDeleted; |
369 | | |
370 | 1.34k | unsigned CoverBytes = PieceOffs-Offset; |
371 | 1.34k | NumBytes -= CoverBytes; |
372 | 1.34k | Size -= CoverBytes; |
373 | 1.34k | } |
374 | | |
375 | | // If we completely removed some stuff, we could be done. |
376 | 67.5k | if (NumBytes == 0) return1.10k ; |
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 | 66.4k | assert(getPiece(StartPiece).size() > NumBytes); |
381 | 0 | Pieces[StartPiece].StartOffs += NumBytes; |
382 | | |
383 | | // The size of this node just shrunk by NumBytes. |
384 | 66.4k | Size -= NumBytes; |
385 | 66.4k | } |
386 | | |
387 | | //===----------------------------------------------------------------------===// |
388 | | // RopePieceBTreeInterior Class |
389 | | //===----------------------------------------------------------------------===// |
390 | | |
391 | | namespace { |
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 | 1.26k | RopePieceBTreeInterior() : RopePieceBTreeNode(false) {} |
404 | | |
405 | | RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS) |
406 | 1.78k | : RopePieceBTreeNode(false) { |
407 | 1.78k | Children[0] = LHS; |
408 | 1.78k | Children[1] = RHS; |
409 | 1.78k | NumChildren = 2; |
410 | 1.78k | Size = LHS->size() + RHS->size(); |
411 | 1.78k | } |
412 | | |
413 | 3.05k | ~RopePieceBTreeInterior() { |
414 | 22.5k | for (unsigned i = 0, e = getNumChildren(); i != e; ++i19.4k ) |
415 | 19.4k | Children[i]->Destroy(); |
416 | 3.05k | } |
417 | | |
418 | 17.1k | bool isFull() const { return NumChildren == 2*WidthFactor; } |
419 | | |
420 | 228k | unsigned getNumChildren() const { return NumChildren; } |
421 | | |
422 | 2.35k | const RopePieceBTreeNode *getChild(unsigned i) const { |
423 | 2.35k | assert(i < NumChildren && "invalid child #"); |
424 | 0 | return Children[i]; |
425 | 2.35k | } |
426 | | |
427 | 5.15M | RopePieceBTreeNode *getChild(unsigned i) { |
428 | 5.15M | assert(i < NumChildren && "invalid child #"); |
429 | 0 | return Children[i]; |
430 | 5.15M | } |
431 | | |
432 | | /// FullRecomputeSizeLocally - Recompute the Size field of this node by |
433 | | /// summing up the sizes of the child nodes. |
434 | 2.53k | void FullRecomputeSizeLocally() { |
435 | 2.53k | Size = 0; |
436 | 24.0k | for (unsigned i = 0, e = getNumChildren(); i != e; ++i21.5k ) |
437 | 21.5k | Size += getChild(i)->size(); |
438 | 2.53k | } |
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 | 439k | static bool classof(const RopePieceBTreeNode *N) { |
465 | 439k | return !N->isLeaf(); |
466 | 439k | } |
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. |
477 | 205k | RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) { |
478 | | // Figure out which child to split. |
479 | 205k | if (Offset == 0 || Offset == size()204k ) |
480 | 1.48k | return nullptr; // If we have an exact offset, we're already split. |
481 | | |
482 | 203k | unsigned ChildOffset = 0; |
483 | 203k | unsigned i = 0; |
484 | 1.28M | for (; Offset >= ChildOffset+getChild(i)->size(); ++i1.07M ) |
485 | 1.07M | ChildOffset += getChild(i)->size(); |
486 | | |
487 | | // If already split there, we're done. |
488 | 203k | if (ChildOffset == Offset) |
489 | 1.28k | return nullptr; |
490 | | |
491 | | // Otherwise, recursively split the child. |
492 | 202k | if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset)) |
493 | 9.89k | return HandleChildPiece(i, RHS); |
494 | 192k | return nullptr; // Done! |
495 | 202k | } |
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. |
503 | | RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset, |
504 | 194k | 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 | 194k | unsigned i = 0, e = getNumChildren(); |
508 | | |
509 | 194k | unsigned ChildOffs = 0; |
510 | 194k | if (Offset == size()) { |
511 | | // Fastpath for a common case. Insert at end of last child. |
512 | 538 | i = e-1; |
513 | 538 | ChildOffs = size()-getChild(i)->size(); |
514 | 193k | } else { |
515 | 1.23M | for (; Offset > ChildOffs+getChild(i)->size(); ++i1.04M ) |
516 | 1.04M | ChildOffs += getChild(i)->size(); |
517 | 193k | } |
518 | | |
519 | 194k | Size += R.size(); |
520 | | |
521 | | // Insert at the end of this child. |
522 | 194k | if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R)) |
523 | 6.00k | return HandleChildPiece(i, RHS); |
524 | | |
525 | 188k | return nullptr; |
526 | 194k | } |
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. |
530 | | RopePieceBTreeNode * |
531 | 17.1k | RopePieceBTreeInterior::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 | 17.1k | if (!isFull()) { |
535 | | // Insert RHS after child 'i'. |
536 | 15.9k | if (i + 1 != getNumChildren()) |
537 | 12.7k | memmove(&Children[i+2], &Children[i+1], |
538 | 12.7k | (getNumChildren()-i-1)*sizeof(Children[0])); |
539 | 15.9k | Children[i+1] = RHS; |
540 | 15.9k | ++NumChildren; |
541 | 15.9k | return nullptr; |
542 | 15.9k | } |
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 | 1.26k | RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior(); |
549 | | |
550 | | // Move over the last 'WidthFactor' values from here to NewNode. |
551 | 1.26k | memcpy(&NewNode->Children[0], &Children[WidthFactor], |
552 | 1.26k | WidthFactor*sizeof(Children[0])); |
553 | | |
554 | | // Decrease the number of values in the two nodes. |
555 | 1.26k | 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 | 1.26k | if (i < WidthFactor) |
560 | 38 | this->HandleChildPiece(i, RHS); |
561 | 1.23k | else |
562 | 1.23k | NewNode->HandleChildPiece(i-WidthFactor, RHS); |
563 | | |
564 | | // Recompute the two nodes' size. |
565 | 1.26k | NewNode->FullRecomputeSizeLocally(); |
566 | 1.26k | FullRecomputeSizeLocally(); |
567 | 1.26k | return NewNode; |
568 | 17.1k | } |
569 | | |
570 | | /// erase - Remove NumBytes from this node at the specified offset. We are |
571 | | /// guaranteed that there is a split at Offset. |
572 | 12.8k | void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) { |
573 | | // This will shrink this node by NumBytes. |
574 | 12.8k | Size -= NumBytes; |
575 | | |
576 | | // Find the first child that overlaps with Offset. |
577 | 12.8k | unsigned i = 0; |
578 | 50.3k | for (; Offset >= getChild(i)->size(); ++i37.5k ) |
579 | 37.5k | Offset -= getChild(i)->size(); |
580 | | |
581 | | // Propagate the delete request into overlapping children, or completely |
582 | | // delete the children as appropriate. |
583 | 12.8k | while (NumBytes) { |
584 | 12.8k | RopePieceBTreeNode *CurChild = getChild(i); |
585 | | |
586 | | // If we are deleting something contained entirely in the child, pass on the |
587 | | // request. |
588 | 12.8k | if (Offset+NumBytes < CurChild->size()) { |
589 | 12.8k | CurChild->erase(Offset, NumBytes); |
590 | 12.8k | return; |
591 | 12.8k | } |
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 | 11 | if (Offset) { |
596 | 10 | unsigned BytesFromChild = CurChild->size()-Offset; |
597 | 10 | CurChild->erase(Offset, BytesFromChild); |
598 | 10 | NumBytes -= BytesFromChild; |
599 | | // Start at the beginning of the next child. |
600 | 10 | Offset = 0; |
601 | 10 | ++i; |
602 | 10 | continue; |
603 | 10 | } |
604 | | |
605 | | // If the deletion request completely covers the child, delete it and move |
606 | | // the rest down. |
607 | 1 | NumBytes -= CurChild->size(); |
608 | 1 | CurChild->Destroy(); |
609 | 1 | --NumChildren; |
610 | 1 | if (i != getNumChildren()) |
611 | 1 | memmove(&Children[i], &Children[i+1], |
612 | 1 | (getNumChildren()-i)*sizeof(Children[0])); |
613 | 1 | } |
614 | 12.8k | } |
615 | | |
616 | | //===----------------------------------------------------------------------===// |
617 | | // RopePieceBTreeNode Implementation |
618 | | //===----------------------------------------------------------------------===// |
619 | | |
620 | 82.0k | void RopePieceBTreeNode::Destroy() { |
621 | 82.0k | if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) |
622 | 79.0k | delete Leaf; |
623 | 3.05k | else |
624 | 3.05k | delete cast<RopePieceBTreeInterior>(this); |
625 | 82.0k | } |
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. |
633 | 439k | RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) { |
634 | 439k | assert(Offset <= size() && "Invalid offset to split!"); |
635 | 439k | if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) |
636 | 233k | return Leaf->split(Offset); |
637 | 205k | return cast<RopePieceBTreeInterior>(this)->split(Offset); |
638 | 439k | } |
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. |
646 | | RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset, |
647 | 363k | const RopePiece &R) { |
648 | 363k | assert(Offset <= size() && "Invalid offset to insert!"); |
649 | 363k | if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) |
650 | 168k | return Leaf->insert(Offset, R); |
651 | 194k | return cast<RopePieceBTreeInterior>(this)->insert(Offset, R); |
652 | 363k | } |
653 | | |
654 | | /// erase - Remove NumBytes from this node at the specified offset. We are |
655 | | /// guaranteed that there is a split at Offset. |
656 | 80.4k | void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) { |
657 | 80.4k | assert(Offset+NumBytes <= size() && "Invalid offset to erase!"); |
658 | 80.4k | if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) |
659 | 67.5k | return Leaf->erase(Offset, NumBytes); |
660 | 12.8k | return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes); |
661 | 80.4k | } |
662 | | |
663 | | //===----------------------------------------------------------------------===// |
664 | | // RopePieceBTreeIterator Implementation |
665 | | //===----------------------------------------------------------------------===// |
666 | | |
667 | 748k | static const RopePieceBTreeLeaf *getCN(const void *P) { |
668 | 748k | return static_cast<const RopePieceBTreeLeaf*>(P); |
669 | 748k | } |
670 | | |
671 | | // begin iterator. |
672 | 21.5k | RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) { |
673 | 21.5k | 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 | 23.9k | while (const auto *IN = dyn_cast<RopePieceBTreeInterior>(N)) |
677 | 2.35k | N = IN->getChild(0); |
678 | | |
679 | | // We must have at least one leaf. |
680 | 21.5k | 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 | 21.6k | while (CurNode && getCN(CurNode)->getNumPieces() == 021.5k ) |
685 | 8 | CurNode = getCN(CurNode)->getNextLeafInOrder(); |
686 | | |
687 | 21.5k | if (CurNode) |
688 | 21.5k | CurPiece = &getCN(CurNode)->getPiece(0); |
689 | 8 | else // Empty tree, this is an end() iterator. |
690 | 8 | CurPiece = nullptr; |
691 | 21.5k | CurChar = 0; |
692 | 21.5k | } |
693 | | |
694 | 316k | void RopePieceBTreeIterator::MoveToNextPiece() { |
695 | 316k | if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) { |
696 | 277k | CurChar = 0; |
697 | 277k | ++CurPiece; |
698 | 277k | return; |
699 | 277k | } |
700 | | |
701 | | // Find the next non-empty leaf node. |
702 | 38.3k | do |
703 | 38.3k | CurNode = getCN(CurNode)->getNextLeafInOrder(); |
704 | 38.3k | while (CurNode && getCN(CurNode)->getNumPieces() == 017.6k ); |
705 | | |
706 | 38.3k | if (CurNode) |
707 | 17.6k | CurPiece = &getCN(CurNode)->getPiece(0); |
708 | 20.7k | else // Hit end(). |
709 | 20.7k | CurPiece = nullptr; |
710 | 38.3k | CurChar = 0; |
711 | 38.3k | } |
712 | | |
713 | | //===----------------------------------------------------------------------===// |
714 | | // RopePieceBTree Implementation |
715 | | //===----------------------------------------------------------------------===// |
716 | | |
717 | 824k | static RopePieceBTreeNode *getRoot(void *P) { |
718 | 824k | return static_cast<RopePieceBTreeNode*>(P); |
719 | 824k | } |
720 | | |
721 | 20.8k | RopePieceBTree::RopePieceBTree() { |
722 | 20.8k | Root = new RopePieceBTreeLeaf(); |
723 | 20.8k | } |
724 | | |
725 | 41.7k | RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) { |
726 | 41.7k | assert(RHS.empty() && "Can't copy non-empty tree yet"); |
727 | 0 | Root = new RopePieceBTreeLeaf(); |
728 | 41.7k | } |
729 | | |
730 | 62.5k | RopePieceBTree::~RopePieceBTree() { |
731 | 62.5k | getRoot(Root)->Destroy(); |
732 | 62.5k | } |
733 | | |
734 | 265k | unsigned RopePieceBTree::size() const { |
735 | 265k | return getRoot(Root)->size(); |
736 | 265k | } |
737 | | |
738 | 20.8k | void RopePieceBTree::clear() { |
739 | 20.8k | if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root))) |
740 | 20.8k | Leaf->clear(); |
741 | 0 | else { |
742 | 0 | getRoot(Root)->Destroy(); |
743 | 0 | Root = new RopePieceBTreeLeaf(); |
744 | 0 | } |
745 | 20.8k | } |
746 | | |
747 | 168k | void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) { |
748 | | // #1. Split at Offset. |
749 | 168k | if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) |
750 | 123 | Root = new RopePieceBTreeInterior(getRoot(Root), RHS); |
751 | | |
752 | | // #2. Do the insertion. |
753 | 168k | if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R)) |
754 | 1.44k | Root = new RopePieceBTreeInterior(getRoot(Root), RHS); |
755 | 168k | } |
756 | | |
757 | 67.5k | void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) { |
758 | | // #1. Split at Offset. |
759 | 67.5k | if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) |
760 | 220 | Root = new RopePieceBTreeInterior(getRoot(Root), RHS); |
761 | | |
762 | | // #2. Do the erasing. |
763 | 67.5k | getRoot(Root)->erase(Offset, NumBytes); |
764 | 67.5k | } |
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. |
774 | 168k | RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) { |
775 | 168k | unsigned Len = End-Start; |
776 | 168k | assert(Len && "Zero length RopePiece is invalid!"); |
777 | | |
778 | | // If we have space for this string in the current alloc buffer, use it. |
779 | 168k | if (AllocOffs+Len <= AllocChunkSize) { |
780 | 146k | memcpy(AllocBuffer->Data+AllocOffs, Start, Len); |
781 | 146k | AllocOffs += Len; |
782 | 146k | return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs); |
783 | 146k | } |
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 | 22.3k | if (Len > AllocChunkSize) { |
788 | 386 | unsigned Size = End-Start+sizeof(RopeRefCountString)-1; |
789 | 386 | auto *Res = reinterpret_cast<RopeRefCountString *>(new char[Size]); |
790 | 386 | Res->RefCount = 0; |
791 | 386 | memcpy(Res->Data, Start, End-Start); |
792 | 386 | return RopePiece(Res, 0, End-Start); |
793 | 386 | } |
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 | 21.9k | unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize; |
799 | 21.9k | auto *Res = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]); |
800 | 21.9k | Res->RefCount = 0; |
801 | 21.9k | memcpy(Res->Data, Start, Len); |
802 | 21.9k | AllocBuffer = Res; |
803 | 21.9k | AllocOffs = Len; |
804 | | |
805 | 21.9k | return RopePiece(AllocBuffer, 0, Len); |
806 | 22.3k | } |