 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
73.3% |
132 / 180 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
88.9% |
160 / 180 |
| |
|
Line Coverage: |
92.5% |
273 / 295 |
| |
 |
|
 |
1 : //===--- RewriteRope.cpp - Rope specialized for rewriter --------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the RewriteRope class, which is a powerful string.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "clang/Rewrite/RewriteRope.h"
15 : #include "llvm/Support/Casting.h"
16 : #include <algorithm>
17 : using namespace clang;
18 : using llvm::dyn_cast;
19 : using llvm::cast;
20 :
21 : /// RewriteRope is a "strong" string class, designed to make insertions and
22 : /// deletions in the middle of the string nearly constant time (really, they are
23 : /// O(log N), but with a very low constant factor).
24 : ///
25 : /// The implementation of this datastructure is a conceptual linear sequence of
26 : /// RopePiece elements. Each RopePiece represents a view on a separately
27 : /// allocated and reference counted string. This means that splitting a very
28 : /// long string can be done in constant time by splitting a RopePiece that
29 : /// references the whole string into two rope pieces that reference each half.
30 : /// Once split, another string can be inserted in between the two halves by
31 : /// inserting a RopePiece in between the two others. All of this is very
32 : /// inexpensive: it takes time proportional to the number of RopePieces, not the
33 : /// length of the strings they represent.
34 : ///
35 : /// While a linear sequences of RopePieces is the conceptual model, the actual
36 : /// implementation captures them in an adapted B+ Tree. Using a B+ tree (which
37 : /// is a tree that keeps the values in the leaves and has where each node
38 : /// contains a reasonable number of pointers to children/values) allows us to
39 : /// maintain efficient operation when the RewriteRope contains a *huge* number
40 : /// of RopePieces. The basic idea of the B+ Tree is that it allows us to find
41 : /// the RopePiece corresponding to some offset very efficiently, and it
42 : /// automatically balances itself on insertions of RopePieces (which can happen
43 : /// for both insertions and erases of string ranges).
44 : ///
45 : /// The one wrinkle on the theory is that we don't attempt to keep the tree
46 : /// properly balanced when erases happen. Erases of string data can both insert
47 : /// new RopePieces (e.g. when the middle of some other rope piece is deleted,
48 : /// which results in two rope pieces, which is just like an insert) or it can
49 : /// reduce the number of RopePieces maintained by the B+Tree. In the case when
50 : /// the number of RopePieces is reduced, we don't attempt to maintain the
51 : /// standard 'invariant' that each node in the tree contains at least
52 : /// 'WidthFactor' children/values. For our use cases, this doesn't seem to
53 : /// matter.
54 : ///
55 : /// The implementation below is primarily implemented in terms of three classes:
56 : /// RopePieceBTreeNode - Common base class for:
57 : ///
58 : /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
59 : /// nodes. This directly represents a chunk of the string with those
60 : /// RopePieces contatenated.
61 : /// RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
62 : /// up to '2*WidthFactor' other nodes in the tree.
63 :
64 :
65 : //===----------------------------------------------------------------------===//
66 : // RopePieceBTreeNode Class
67 : //===----------------------------------------------------------------------===//
68 :
69 : namespace {
70 : /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
71 : /// RopePieceBTreeInterior. This provides some 'virtual' dispatching methods
72 : /// and a flag that determines which subclass the instance is. Also
73 : /// important, this node knows the full extend of the node, including any
74 : /// children that it has. This allows efficient skipping over entire subtrees
75 : /// when looking for an offset in the BTree.
76 : class RopePieceBTreeNode {
77 : protected:
78 : /// WidthFactor - This controls the number of K/V slots held in the BTree:
79 : /// how wide it is. Each level of the BTree is guaranteed to have at least
80 : /// 'WidthFactor' elements in it (either ropepieces or children), (except
81 : /// the root, which may have less) and may have at most 2*WidthFactor
82 : /// elements.
83 : enum { WidthFactor = 8 };
84 :
85 : /// Size - This is the number of bytes of file this node (including any
86 : /// potential children) covers.
87 : unsigned Size;
88 :
89 : /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
90 : /// is an instance of RopePieceBTreeInterior.
91 : bool IsLeaf;
92 :
93 459: RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {}
94 269: ~RopePieceBTreeNode() {}
95 : public:
96 :
97 11276: bool isLeaf() const { return IsLeaf; }
98 23603: unsigned size() const { return Size; }
99 :
100 : void Destroy();
101 :
102 : /// split - Split the range containing the specified offset so that we are
103 : /// guaranteed that there is a place to do an insertion at the specified
104 : /// offset. The offset is relative, so "0" is the start of the node.
105 : ///
106 : /// If there is no space in this subtree for the extra piece, the extra tree
107 : /// node is returned and must be inserted into a parent.
108 : RopePieceBTreeNode *split(unsigned Offset);
109 :
110 : /// insert - Insert the specified ropepiece into this tree node at the
111 : /// specified offset. The offset is relative, so "0" is the start of the
112 : /// node.
113 : ///
114 : /// If there is no space in this subtree for the extra piece, the extra tree
115 : /// node is returned and must be inserted into a parent.
116 : RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
117 :
118 : /// erase - Remove NumBytes from this node at the specified offset. We are
119 : /// guaranteed that there is a split at Offset.
120 : void erase(unsigned Offset, unsigned NumBytes);
121 :
122 : static inline bool classof(const RopePieceBTreeNode *) { return true; }
123 :
124 : };
125 : } // end anonymous namespace
126 :
127 : //===----------------------------------------------------------------------===//
128 : // RopePieceBTreeLeaf Class
129 : //===----------------------------------------------------------------------===//
130 :
131 : namespace {
132 : /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
133 : /// nodes. This directly represents a chunk of the string with those
134 : /// RopePieces contatenated. Since this is a B+Tree, all values (in this case
135 : /// instances of RopePiece) are stored in leaves like this. To make iteration
136 : /// over the leaves efficient, they maintain a singly linked list through the
137 : /// NextLeaf field. This allows the B+Tree forward iterator to be constant
138 : /// time for all increments.
139 : class RopePieceBTreeLeaf : public RopePieceBTreeNode {
140 : /// NumPieces - This holds the number of rope pieces currently active in the
141 : /// Pieces array.
142 : unsigned char NumPieces;
143 :
144 : /// Pieces - This tracks the file chunks currently in this leaf.
145 : ///
146 : RopePiece Pieces[2*WidthFactor];
147 :
148 : /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
149 : /// efficient in-order forward iteration of the tree without traversal.
150 : RopePieceBTreeLeaf **PrevLeaf, *NextLeaf;
151 : public:
152 413: RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0),
6608: branch 2 taken
413: branch 3 taken
153 413: PrevLeaf(0), NextLeaf(0) {}
154 223: ~RopePieceBTreeLeaf() {
222: branch 0 taken
1: branch 1 taken
0: branch 2 not taken
222: branch 3 taken
155 223: if (PrevLeaf || NextLeaf)
156 1: removeFromLeafInOrder();
157 223: clear();
223: branch 0 taken
0: branch 1 not taken
3568: branch 2 taken
223: branch 3 taken
158 223: }
159 :
160 2324: bool isFull() const { return NumPieces == 2*WidthFactor; }
161 :
162 : /// clear - Remove all rope pieces from this leaf.
163 290: void clear() {
215: branch 0 taken
290: branch 1 taken
164 795: while (NumPieces)
165 215: Pieces[--NumPieces] = RopePiece();
166 290: Size = 0;
167 290: }
168 :
169 30577: unsigned getNumPieces() const { return NumPieces; }
170 :
171 22589: const RopePiece &getPiece(unsigned i) const {
22589: branch 1 taken
0: branch 2 not taken
172 22589: assert(i < getNumPieces() && "Invalid piece ID");
173 22589: return Pieces[i];
174 : }
175 :
176 470: const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }
177 145: void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {
145: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
145: branch 3 taken
178 145: assert(PrevLeaf == 0 && NextLeaf == 0 && "Already in ordering");
179 :
180 145: NextLeaf = Node->NextLeaf;
21: branch 0 taken
124: branch 1 taken
181 145: if (NextLeaf)
182 21: NextLeaf->PrevLeaf = &NextLeaf;
183 145: PrevLeaf = &Node->NextLeaf;
184 145: Node->NextLeaf = this;
185 145: }
186 :
187 1: void removeFromLeafInOrder() {
1: branch 0 taken
0: branch 1 not taken
188 1: if (PrevLeaf) {
189 1: *PrevLeaf = NextLeaf;
1: branch 0 taken
0: branch 1 not taken
190 1: if (NextLeaf)
191 1: NextLeaf->PrevLeaf = PrevLeaf;
0: branch 0 not taken
0: branch 1 not taken
192 0: } else if (NextLeaf) {
193 0: NextLeaf->PrevLeaf = 0;
194 : }
195 1: }
196 :
197 : /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by
198 : /// summing the size of all RopePieces.
199 290: void FullRecomputeSizeLocally() {
200 290: Size = 0;
2320: branch 1 taken
290: branch 2 taken
201 2610: for (unsigned i = 0, e = getNumPieces(); i != e; ++i)
202 2320: Size += getPiece(i).size();
203 290: }
204 :
205 : /// split - Split the range containing the specified offset so that we are
206 : /// guaranteed that there is a place to do an insertion at the specified
207 : /// offset. The offset is relative, so "0" is the start of the node.
208 : ///
209 : /// If there is no space in this subtree for the extra piece, the extra tree
210 : /// node is returned and must be inserted into a parent.
211 : RopePieceBTreeNode *split(unsigned Offset);
212 :
213 : /// insert - Insert the specified ropepiece into this tree node at the
214 : /// specified offset. The offset is relative, so "0" is the start of the
215 : /// node.
216 : ///
217 : /// If there is no space in this subtree for the extra piece, the extra tree
218 : /// node is returned and must be inserted into a parent.
219 : RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
220 :
221 :
222 : /// erase - Remove NumBytes from this node at the specified offset. We are
223 : /// guaranteed that there is a split at Offset.
224 : void erase(unsigned Offset, unsigned NumBytes);
225 :
226 : static inline bool classof(const RopePieceBTreeLeaf *) { return true; }
227 9149: static inline bool classof(const RopePieceBTreeNode *N) {
228 9149: return N->isLeaf();
229 : }
230 : };
231 : } // end anonymous namespace
232 :
233 : /// split - Split the range containing the specified offset so that we are
234 : /// guaranteed that there is a place to do an insertion at the specified
235 : /// offset. The offset is relative, so "0" is the start of the node.
236 : ///
237 : /// If there is no space in this subtree for the extra piece, the extra tree
238 : /// node is returned and must be inserted into a parent.
239 1611: RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {
240 : // Find the insertion point. We are guaranteed that there is a split at the
241 : // specified offset so find it.
1519: branch 0 taken
92: branch 1 taken
3: branch 3 taken
1516: branch 4 taken
95: branch 5 taken
1516: branch 6 taken
242 1611: if (Offset == 0 || Offset == size()) {
243 : // Fastpath for a common case. There is already a splitpoint at the end.
244 95: return 0;
245 : }
246 :
247 : // Find the piece that this offset lands in.
248 1516: unsigned PieceOffs = 0;
249 1516: unsigned i = 0;
11825: branch 1 taken
1516: branch 2 taken
250 14857: while (Offset >= PieceOffs+Pieces[i].size()) {
251 11825: PieceOffs += Pieces[i].size();
252 11825: ++i;
253 : }
254 :
255 : // If there is already a split point at the specified offset, just return
256 : // success.
583: branch 0 taken
933: branch 1 taken
257 1516: if (PieceOffs == Offset)
258 583: return 0;
259 :
260 : // Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset
261 : // to being Piece relative.
262 933: unsigned IntraPieceOffset = Offset-PieceOffs;
263 :
264 : // We do this by shrinking the RopePiece and then doing an insert of the tail.
265 : RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
266 933: Pieces[i].EndOffs);
267 933: Size -= Pieces[i].size();
268 933: Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
269 933: Size += Pieces[i].size();
270 :
271 933: return insert(Offset, Tail);
272 : }
273 :
274 :
275 : /// insert - Insert the specified RopePiece into this tree node at the
276 : /// specified offset. The offset is relative, so "0" is the start of the node.
277 : ///
278 : /// If there is no space in this subtree for the extra piece, the extra tree
279 : /// node is returned and must be inserted into a parent.
280 : RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,
281 2324: const RopePiece &R) {
282 : // If this node is not full, insert the piece.
2179: branch 1 taken
145: branch 2 taken
283 2324: if (!isFull()) {
284 : // Find the insertion point. We are guaranteed that there is a split at the
285 : // specified offset so find it.
286 2179: unsigned i = 0, e = getNumPieces();
790: branch 1 taken
1389: branch 2 taken
287 2179: if (Offset == size()) {
288 : // Fastpath for a common case.
289 790: i = e;
290 : } else {
291 1389: unsigned SlotOffs = 0;
9783: branch 0 taken
1389: branch 1 taken
292 11172: for (; Offset > SlotOffs; ++i)
293 9783: SlotOffs += getPiece(i).size();
0: branch 0 not taken
1389: branch 1 taken
294 1389: assert(SlotOffs == Offset && "Split didn't occur before insertion!");
295 : }
296 :
297 : // For an insertion into a non-full leaf node, just insert the value in
298 : // its sorted position. This requires moving later values over.
3952: branch 0 taken
2179: branch 1 taken
299 6131: for (; i != e; --e)
300 3952: Pieces[e] = Pieces[e-1];
301 2179: Pieces[i] = R;
302 2179: ++NumPieces;
303 2179: Size += R.size();
304 2179: return 0;
305 : }
306 :
307 : // Otherwise, if this is leaf is full, split it in two halves. Since this
308 : // node is full, it contains 2*WidthFactor values. We move the first
309 : // 'WidthFactor' values to the LHS child (which we leave in this node) and
310 : // move the last 'WidthFactor' values into the RHS child.
311 :
312 : // Create the new node.
313 145: RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();
314 :
315 : // Move over the last 'WidthFactor' values from here to NewNode.
316 : std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor],
317 145: &NewNode->Pieces[0]);
318 : // Replace old pieces with null RopePieces to drop refcounts.
319 145: std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece());
320 :
321 : // Decrease the number of values in the two nodes.
322 145: NewNode->NumPieces = NumPieces = WidthFactor;
323 :
324 : // Recompute the two nodes' size.
325 145: NewNode->FullRecomputeSizeLocally();
326 145: FullRecomputeSizeLocally();
327 :
328 : // Update the list of leaves.
329 145: NewNode->insertAfterLeafInOrder(this);
330 :
331 : // These insertions can't fail.
12: branch 1 taken
133: branch 2 taken
332 145: if (this->size() >= Offset)
333 12: this->insert(Offset, R);
334 : else
335 133: NewNode->insert(Offset - this->size(), R);
336 145: return NewNode;
337 : }
338 :
339 : /// erase - Remove NumBytes from this node at the specified offset. We are
340 : /// guaranteed that there is a split at Offset.
341 430: void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
342 : // Since we are guaranteed that there is a split at Offset, we start by
343 : // finding the Piece that starts there.
344 430: unsigned PieceOffs = 0;
345 430: unsigned i = 0;
3621: branch 0 taken
430: branch 1 taken
346 4051: for (; Offset > PieceOffs; ++i)
347 3621: PieceOffs += getPiece(i).size();
0: branch 0 not taken
430: branch 1 taken
348 430: assert(PieceOffs == Offset && "Split didn't occur before erase!");
349 :
350 430: unsigned StartPiece = i;
351 :
352 : // Figure out how many pieces completely cover 'NumBytes'. We want to remove
353 : // all of them.
102: branch 2 taken
430: branch 3 taken
354 532: for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i)
355 102: PieceOffs += getPiece(i).size();
356 :
357 : // If we exactly include the last one, include it in the region to delete.
6: branch 2 taken
424: branch 3 taken
358 430: if (Offset+NumBytes == PieceOffs+getPiece(i).size())
359 6: PieceOffs += getPiece(i).size(), ++i;
360 :
361 : // If we completely cover some RopePieces, erase them now.
37: branch 0 taken
393: branch 1 taken
362 430: if (i != StartPiece) {
363 37: unsigned NumDeleted = i-StartPiece;
37: branch 1 taken
37: branch 2 taken
364 74: for (; i != getNumPieces(); ++i)
365 37: Pieces[i-NumDeleted] = Pieces[i];
366 :
367 : // Drop references to dead rope pieces.
368 : std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()],
369 37: RopePiece());
370 37: NumPieces -= NumDeleted;
371 :
372 37: unsigned CoverBytes = PieceOffs-Offset;
373 37: NumBytes -= CoverBytes;
374 37: Size -= CoverBytes;
375 : }
376 :
377 : // If we completely removed some stuff, we could be done.
424: branch 0 taken
6: branch 1 taken
378 430: if (NumBytes == 0) return;
379 :
380 : // Okay, now might be erasing part of some Piece. If this is the case, then
381 : // move the start point of the piece.
0: branch 2 not taken
424: branch 3 taken
382 424: assert(getPiece(StartPiece).size() > NumBytes);
383 424: Pieces[StartPiece].StartOffs += NumBytes;
384 :
385 : // The size of this node just shrunk by NumBytes.
386 424: Size -= NumBytes;
387 : }
388 :
389 : //===----------------------------------------------------------------------===//
390 : // RopePieceBTreeInterior Class
391 : //===----------------------------------------------------------------------===//
392 :
393 : namespace {
394 : /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
395 : /// which holds up to 2*WidthFactor pointers to child nodes.
396 46: class RopePieceBTreeInterior : public RopePieceBTreeNode {
397 : /// NumChildren - This holds the number of children currently active in the
398 : /// Children array.
399 : unsigned char NumChildren;
400 : RopePieceBTreeNode *Children[2*WidthFactor];
401 : public:
402 0: RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {}
403 :
404 46: RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
405 46: : RopePieceBTreeNode(false) {
406 46: Children[0] = LHS;
407 46: Children[1] = RHS;
408 46: NumChildren = 2;
409 46: Size = LHS->size() + RHS->size();
410 46: }
411 :
412 99: bool isFull() const { return NumChildren == 2*WidthFactor; }
413 :
414 814: unsigned getNumChildren() const { return NumChildren; }
415 66: const RopePieceBTreeNode *getChild(unsigned i) const {
0: branch 0 not taken
66: branch 1 taken
416 66: assert(i < NumChildren && "invalid child #");
417 66: return Children[i];
418 : }
419 12433: RopePieceBTreeNode *getChild(unsigned i) {
0: branch 0 not taken
12433: branch 1 taken
420 12433: assert(i < NumChildren && "invalid child #");
421 12433: return Children[i];
422 : }
423 :
424 : /// FullRecomputeSizeLocally - Recompute the Size field of this node by
425 : /// summing up the sizes of the child nodes.
426 0: void FullRecomputeSizeLocally() {
427 0: Size = 0;
0: branch 1 not taken
0: branch 2 not taken
428 0: for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
429 0: Size += getChild(i)->size();
430 0: }
431 :
432 :
433 : /// split - Split the range containing the specified offset so that we are
434 : /// guaranteed that there is a place to do an insertion at the specified
435 : /// offset. The offset is relative, so "0" is the start of the node.
436 : ///
437 : /// If there is no space in this subtree for the extra piece, the extra tree
438 : /// node is returned and must be inserted into a parent.
439 : RopePieceBTreeNode *split(unsigned Offset);
440 :
441 :
442 : /// insert - Insert the specified ropepiece into this tree node at the
443 : /// specified offset. The offset is relative, so "0" is the start of the
444 : /// node.
445 : ///
446 : /// If there is no space in this subtree for the extra piece, the extra tree
447 : /// node is returned and must be inserted into a parent.
448 : RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
449 :
450 : /// HandleChildPiece - A child propagated an insertion result up to us.
451 : /// Insert the new child, and/or propagate the result further up the tree.
452 : RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);
453 :
454 : /// erase - Remove NumBytes from this node at the specified offset. We are
455 : /// guaranteed that there is a split at Offset.
456 : void erase(unsigned Offset, unsigned NumBytes);
457 :
458 : static inline bool classof(const RopePieceBTreeInterior *) { return true; }
459 2127: static inline bool classof(const RopePieceBTreeNode *N) {
460 2127: return !N->isLeaf();
461 : }
462 : };
463 : } // end anonymous namespace
464 :
465 : /// split - Split the range containing the specified offset so that we are
466 : /// guaranteed that there is a place to do an insertion at the specified
467 : /// offset. The offset is relative, so "0" is the start of the node.
468 : ///
469 : /// If there is no space in this subtree for the extra piece, the extra tree
470 : /// node is returned and must be inserted into a parent.
471 924: RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
472 : // Figure out which child to split.
884: branch 0 taken
40: branch 1 taken
5: branch 3 taken
879: branch 4 taken
45: branch 5 taken
879: branch 6 taken
473 924: if (Offset == 0 || Offset == size())
474 45: return 0; // If we have an exact offset, we're already split.
475 :
476 879: unsigned ChildOffset = 0;
477 879: unsigned i = 0;
2203: branch 2 taken
879: branch 3 taken
478 3082: for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
479 2203: ChildOffset += getChild(i)->size();
480 :
481 : // If already split there, we're done.
19: branch 0 taken
860: branch 1 taken
482 879: if (ChildOffset == Offset)
483 19: return 0;
484 :
485 : // Otherwise, recursively split the child.
24: branch 2 taken
836: branch 3 taken
486 860: if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
487 24: return HandleChildPiece(i, RHS);
488 836: return 0; // Done!
489 : }
490 :
491 : /// insert - Insert the specified ropepiece into this tree node at the
492 : /// specified offset. The offset is relative, so "0" is the start of the
493 : /// node.
494 : ///
495 : /// If there is no space in this subtree for the extra piece, the extra tree
496 : /// node is returned and must be inserted into a parent.
497 : RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
498 692: const RopePiece &R) {
499 : // Find the insertion point. We are guaranteed that there is a split at the
500 : // specified offset so find it.
501 692: unsigned i = 0, e = getNumChildren();
502 :
503 692: unsigned ChildOffs = 0;
5: branch 1 taken
687: branch 2 taken
504 692: if (Offset == size()) {
505 : // Fastpath for a common case. Insert at end of last child.
506 5: i = e-1;
507 5: ChildOffs = size()-getChild(i)->size();
508 : } else {
1645: branch 2 taken
687: branch 3 taken
509 2332: for (; Offset > ChildOffs+getChild(i)->size(); ++i)
510 1645: ChildOffs += getChild(i)->size();
511 : }
512 :
513 692: Size += R.size();
514 :
515 : // Insert at the end of this child.
75: branch 2 taken
617: branch 3 taken
516 692: if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
517 75: return HandleChildPiece(i, RHS);
518 :
519 617: return 0;
520 : }
521 :
522 : /// HandleChildPiece - A child propagated an insertion result up to us.
523 : /// Insert the new child, and/or propagate the result further up the tree.
524 : RopePieceBTreeNode *
525 99: RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
526 : // Otherwise the child propagated a subtree up to us as a new child. See if
527 : // we have space for it here.
99: branch 1 taken
0: branch 2 not taken
528 99: if (!isFull()) {
529 : // Insert RHS after child 'i'.
21: branch 1 taken
78: branch 2 taken
530 99: if (i + 1 != getNumChildren())
531 : memmove(&Children[i+2], &Children[i+1],
532 21: (getNumChildren()-i-1)*sizeof(Children[0]));
533 99: Children[i+1] = RHS;
534 99: ++NumChildren;
535 99: return false;
536 : }
537 :
538 : // Okay, this node is full. Split it in half, moving WidthFactor children to
539 : // a newly allocated interior node.
540 :
541 : // Create the new node.
542 0: RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
543 :
544 : // Move over the last 'WidthFactor' values from here to NewNode.
545 : memcpy(&NewNode->Children[0], &Children[WidthFactor],
546 0: WidthFactor*sizeof(Children[0]));
547 :
548 : // Decrease the number of values in the two nodes.
549 0: NewNode->NumChildren = NumChildren = WidthFactor;
550 :
551 : // Finally, insert the two new children in the side the can (now) hold them.
552 : // These insertions can't fail.
0: branch 0 not taken
0: branch 1 not taken
553 0: if (i < WidthFactor)
554 0: this->HandleChildPiece(i, RHS);
555 : else
556 0: NewNode->HandleChildPiece(i-WidthFactor, RHS);
557 :
558 : // Recompute the two nodes' size.
559 0: NewNode->FullRecomputeSizeLocally();
560 0: FullRecomputeSizeLocally();
561 0: return NewNode;
562 : }
563 :
564 : /// erase - Remove NumBytes from this node at the specified offset. We are
565 : /// guaranteed that there is a split at Offset.
566 239: void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
567 : // This will shrink this node by NumBytes.
568 239: Size -= NumBytes;
569 :
570 : // Find the first child that overlaps with Offset.
571 239: unsigned i = 0;
567: branch 2 taken
239: branch 3 taken
572 806: for (; Offset >= getChild(i)->size(); ++i)
573 567: Offset -= getChild(i)->size();
574 :
575 : // Propagate the delete request into overlapping children, or completely
576 : // delete the children as appropriate.
241: branch 0 taken
1: branch 1 taken
577 481: while (NumBytes) {
578 241: RopePieceBTreeNode *CurChild = getChild(i);
579 :
580 : // If we are deleting something contained entirely in the child, pass on the
581 : // request.
238: branch 1 taken
3: branch 2 taken
582 241: if (Offset+NumBytes < CurChild->size()) {
583 238: CurChild->erase(Offset, NumBytes);
584 238: return;
585 : }
586 :
587 : // If this deletion request starts somewhere in the middle of the child, it
588 : // must be deleting to the end of the child.
2: branch 0 taken
1: branch 1 taken
589 3: if (Offset) {
590 2: unsigned BytesFromChild = CurChild->size()-Offset;
591 2: CurChild->erase(Offset, BytesFromChild);
592 2: NumBytes -= BytesFromChild;
593 : // Start at the beginning of the next child.
594 2: Offset = 0;
595 2: ++i;
596 2: continue;
597 : }
598 :
599 : // If the deletion request completely covers the child, delete it and move
600 : // the rest down.
601 1: NumBytes -= CurChild->size();
602 1: CurChild->Destroy();
603 1: --NumChildren;
1: branch 1 taken
0: branch 2 not taken
604 1: if (i != getNumChildren())
605 : memmove(&Children[i], &Children[i+1],
606 1: (getNumChildren()-i)*sizeof(Children[0]));
607 : }
608 : }
609 :
610 : //===----------------------------------------------------------------------===//
611 : // RopePieceBTreeNode Implementation
612 : //===----------------------------------------------------------------------===//
613 :
614 269: void RopePieceBTreeNode::Destroy() {
223: branch 1 taken
46: branch 2 taken
615 269: if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
223: branch 0 taken
0: branch 1 not taken
616 223: delete Leaf;
617 : else
46: branch 1 taken
0: branch 2 not taken
618 46: delete cast<RopePieceBTreeInterior>(this);
619 269: }
620 :
621 : /// split - Split the range containing the specified offset so that we are
622 : /// guaranteed that there is a place to do an insertion at the specified
623 : /// offset. The offset is relative, so "0" is the start of the node.
624 : ///
625 : /// If there is no space in this subtree for the extra piece, the extra tree
626 : /// node is returned and must be inserted into a parent.
627 2535: RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
2535: branch 1 taken
0: branch 2 not taken
628 2535: assert(Offset <= size() && "Invalid offset to split!");
1611: branch 1 taken
924: branch 2 taken
629 2535: if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
630 1611: return Leaf->split(Offset);
631 924: return cast<RopePieceBTreeInterior>(this)->split(Offset);
632 : }
633 :
634 : /// insert - Insert the specified ropepiece into this tree node at the
635 : /// specified offset. The offset is relative, so "0" is the start of the
636 : /// node.
637 : ///
638 : /// If there is no space in this subtree for the extra piece, the extra tree
639 : /// node is returned and must be inserted into a parent.
640 : RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
641 1938: const RopePiece &R) {
1938: branch 1 taken
0: branch 2 not taken
642 1938: assert(Offset <= size() && "Invalid offset to insert!");
1246: branch 1 taken
692: branch 2 taken
643 1938: if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
644 1246: return Leaf->insert(Offset, R);
645 692: return cast<RopePieceBTreeInterior>(this)->insert(Offset, R);
646 : }
647 :
648 : /// erase - Remove NumBytes from this node at the specified offset. We are
649 : /// guaranteed that there is a split at Offset.
650 669: void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
669: branch 1 taken
0: branch 2 not taken
651 669: assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
430: branch 1 taken
239: branch 2 taken
652 669: if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
653 430: return Leaf->erase(Offset, NumBytes);
654 239: return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
655 : }
656 :
657 :
658 : //===----------------------------------------------------------------------===//
659 : // RopePieceBTreeIterator Implementation
660 : //===----------------------------------------------------------------------===//
661 :
662 11212: static const RopePieceBTreeLeaf *getCN(const void *P) {
663 11212: return static_cast<const RopePieceBTreeLeaf*>(P);
664 : }
665 :
666 : // begin iterator.
667 94: RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
668 94: const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n);
669 :
670 : // Walk down the left side of the tree until we get to a leaf.
66: branch 1 taken
94: branch 2 taken
0: branch 4 not taken
0: branch 5 not taken
671 226: while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N))
672 66: N = IN->getChild(0);
673 :
674 : // We must have at least one leaf.
675 94: CurNode = cast<RopePieceBTreeLeaf>(N);
676 :
677 : // If we found a leaf that happens to be empty, skip over it until we get
678 : // to something full.
94: branch 0 taken
0: branch 1 not taken
0: branch 4 not taken
94: branch 5 taken
0: branch 6 not taken
94: branch 7 taken
94: branch 8 taken
94: branch 9 taken
0: branch 12 not taken
0: branch 13 not taken
0: branch 14 not taken
0: branch 15 not taken
679 188: while (CurNode && getCN(CurNode)->getNumPieces() == 0)
680 0: CurNode = getCN(CurNode)->getNextLeafInOrder();
681 :
94: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
682 94: if (CurNode != 0)
683 94: CurPiece = &getCN(CurNode)->getPiece(0);
684 : else // Empty tree, this is an end() iterator.
685 0: CurPiece = 0;
686 94: CurChar = 0;
687 94: }
688 :
689 4931: void RopePieceBTreeIterator::MoveToNextPiece() {
4461: branch 4 taken
470: branch 5 taken
690 4931: if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
691 4461: CurChar = 0;
692 4461: ++CurPiece;
693 4461: return;
694 : }
695 :
696 : // Find the next non-empty leaf node.
346: branch 0 taken
124: branch 1 taken
0: branch 4 not taken
346: branch 5 taken
0: branch 6 not taken
470: branch 7 taken
697 470: do
698 470: CurNode = getCN(CurNode)->getNextLeafInOrder();
699 : while (CurNode && getCN(CurNode)->getNumPieces() == 0);
700 :
346: branch 0 taken
124: branch 1 taken
701 470: if (CurNode != 0)
702 346: CurPiece = &getCN(CurNode)->getPiece(0);
703 : else // Hit end().
704 124: CurPiece = 0;
705 470: CurChar = 0;
706 : }
707 :
708 : //===----------------------------------------------------------------------===//
709 : // RopePieceBTree Implementation
710 : //===----------------------------------------------------------------------===//
711 :
712 5659: static RopePieceBTreeNode *getRoot(void *P) {
713 5659: return static_cast<RopePieceBTreeNode*>(P);
714 : }
715 :
716 67: RopePieceBTree::RopePieceBTree() {
717 67: Root = new RopePieceBTreeLeaf();
718 67: }
719 201: RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
201: branch 1 taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
720 201: assert(RHS.empty() && "Can't copy non-empty tree yet");
721 201: Root = new RopePieceBTreeLeaf();
722 201: }
723 268: RopePieceBTree::~RopePieceBTree() {
724 268: getRoot(Root)->Destroy();
725 268: }
726 :
727 1928: unsigned RopePieceBTree::size() const {
728 1928: return getRoot(Root)->size();
729 : }
730 :
731 67: void RopePieceBTree::clear() {
67: branch 2 taken
0: branch 3 not taken
732 67: if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
733 67: Leaf->clear();
734 : else {
735 0: getRoot(Root)->Destroy();
736 0: Root = new RopePieceBTreeLeaf();
737 : }
738 67: }
739 :
740 1246: void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
741 : // #1. Split at Offset.
5: branch 2 taken
1241: branch 3 taken
742 1246: if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
743 5: Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
744 :
745 : // #2. Do the insertion.
39: branch 2 taken
1207: branch 3 taken
746 1246: if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
747 39: Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
748 1246: }
749 :
750 429: void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
751 : // #1. Split at Offset.
2: branch 2 taken
427: branch 3 taken
752 429: if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
753 2: Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
754 :
755 : // #2. Do the erasing.
756 429: getRoot(Root)->erase(Offset, NumBytes);
757 429: }
758 :
759 : //===----------------------------------------------------------------------===//
760 : // RewriteRope Implementation
761 : //===----------------------------------------------------------------------===//
762 :
763 : /// MakeRopeString - This copies the specified byte range into some instance of
764 : /// RopeRefCountString, and return a RopePiece that represents it. This uses
765 : /// the AllocBuffer object to aggregate requests for small strings into one
766 : /// allocation instead of doing tons of tiny allocations.
767 1246: RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
768 1246: unsigned Len = End-Start;
0: branch 0 not taken
1246: branch 1 taken
769 1246: assert(Len && "Zero length RopePiece is invalid!");
770 :
771 : // If we have space for this string in the current alloc buffer, use it.
1138: branch 0 taken
108: branch 1 taken
772 1246: if (AllocOffs+Len <= AllocChunkSize) {
773 1138: memcpy(AllocBuffer->Data+AllocOffs, Start, Len);
774 1138: AllocOffs += Len;
775 1138: return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs);
776 : }
777 :
778 : // If we don't have enough room because this specific allocation is huge,
779 : // just allocate a new rope piece for it alone.
1: branch 0 taken
107: branch 1 taken
780 108: if (Len > AllocChunkSize) {
781 1: unsigned Size = End-Start+sizeof(RopeRefCountString)-1;
782 : RopeRefCountString *Res =
783 1: reinterpret_cast<RopeRefCountString *>(new char[Size]);
784 1: Res->RefCount = 0;
785 1: memcpy(Res->Data, Start, End-Start);
786 1: return RopePiece(Res, 0, End-Start);
787 : }
788 :
789 : // Otherwise, this was a small request but we just don't have space for it
790 : // Make a new chunk and share it with later allocations.
791 :
792 : // If we had an old allocation, drop our reference to it.
40: branch 0 taken
67: branch 1 taken
0: branch 2 not taken
40: branch 3 taken
0: branch 4 not taken
107: branch 5 taken
793 107: if (AllocBuffer && --AllocBuffer->RefCount == 0)
0: branch 0 not taken
0: branch 1 not taken
794 0: delete [] (char*)AllocBuffer;
795 :
796 107: unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;
797 107: AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);
798 107: AllocBuffer->RefCount = 0;
799 107: memcpy(AllocBuffer->Data, Start, Len);
800 107: AllocOffs = Len;
801 :
802 : // Start out the new allocation with a refcount of 1, since we have an
803 : // internal reference to it.
804 107: AllocBuffer->addRef();
805 107: return RopePiece(AllocBuffer, 0, Len);
806 : }
807 :
808 :
Generated: 2010-02-10 01:31 by zcov