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