clang  9.0.0svn
RewriteRope.cpp
Go to the documentation of this file.
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 
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  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");
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");
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.
236 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  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.
276 RopePieceBTreeNode *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!");
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.
337 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  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!");
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);
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 
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  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 #");
424  return Children[i];
425  }
426 
427  RopePieceBTreeNode *getChild(unsigned i) {
428  assert(i < NumChildren && "invalid child #");
429  return Children[i];
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.
477 RopePieceBTreeNode *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.
503 RopePieceBTreeNode *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.
530 RopePieceBTreeNode *
531 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  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.
572 void 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)
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) {
584  RopePieceBTreeNode *CurChild = getChild(i);
585 
586  // If we are deleting something contained entirely in the child, pass on the
587  // request.
588  if (Offset+NumBytes < CurChild->size()) {
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) {
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();
609  --NumChildren;
610  if (i != getNumChildren())
611  memmove(&Children[i], &Children[i+1],
612  (getNumChildren()-i)*sizeof(Children[0]));
613  }
614 }
615 
616 //===----------------------------------------------------------------------===//
617 // RopePieceBTreeNode Implementation
618 //===----------------------------------------------------------------------===//
619 
620 void RopePieceBTreeNode::Destroy() {
621  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
622  delete Leaf;
623  else
624  delete cast<RopePieceBTreeInterior>(this);
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.
633 RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
634  assert(Offset <= size() && "Invalid offset to split!");
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.
646 RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
647  const RopePiece &R) {
648  assert(Offset <= size() && "Invalid offset to insert!");
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.
656 void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
657  assert(Offset+NumBytes <= size() && "Invalid offset to erase!");
658  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(this))
659  return Leaf->erase(Offset, NumBytes);
660  return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes);
661 }
662 
663 //===----------------------------------------------------------------------===//
664 // RopePieceBTreeIterator Implementation
665 //===----------------------------------------------------------------------===//
666 
667 static const RopePieceBTreeLeaf *getCN(const void *P) {
668  return static_cast<const RopePieceBTreeLeaf*>(P);
669 }
670 
671 // begin iterator.
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 
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 
717 static RopePieceBTreeNode *getRoot(void *P) {
718  return static_cast<RopePieceBTreeNode*>(P);
719 }
720 
722  Root = new RopePieceBTreeLeaf();
723 }
724 
726  assert(RHS.empty() && "Can't copy non-empty tree yet");
727  Root = new RopePieceBTreeLeaf();
728 }
729 
731  getRoot(Root)->Destroy();
732 }
733 
734 unsigned RopePieceBTree::size() const {
735  return getRoot(Root)->size();
736 }
737 
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 
747 void 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 
757 void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
758  // #1. Split at Offset.
759  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
760  Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
761 
762  // #2. Do the erasing.
763  getRoot(Root)->erase(Offset, NumBytes);
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.
774 RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
775  unsigned Len = End-Start;
776  assert(Len && "Zero length RopePiece is invalid!");
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) + 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 }
void insert(unsigned Offset, const RopePiece &R)
StringRef P
virtual void clear()
RopeRefCountString - This struct is allocated with &#39;new char[]&#39; from the heap, and represents a refer...
Definition: RewriteRope.h:33
RopePiece - This class represents a view into a RopeRefCountString object.
Definition: RewriteRope.h:58
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
void erase(unsigned Offset, unsigned NumBytes)
unsigned EndOffs
Definition: RewriteRope.h:61
unsigned empty() const
Definition: RewriteRope.h:150
unsigned Offset
Definition: Format.cpp:1709
SourceLocation End
#define offsetof(t, d)
Definition: stddef.h:104
#define false
Definition: stdbool.h:17
unsigned size() const
Definition: RewriteRope.h:75
__DEVICE__ void * memcpy(void *__a, const void *__b, size_t __c)
static RopePieceBTreeNode * getRoot(void *P)
ast_type_traits::DynTypedNode Node
Dataflow Directional Tag Classes.
unsigned size() const
static bool classof(const OMPClause *T)
static const RopePieceBTreeLeaf * getCN(const void *P)
unsigned StartOffs
Definition: RewriteRope.h:60
#define true
Definition: stdbool.h:16