Clang Project

clang_source_code/lib/Rewrite/RewriteRope.cpp
1//===- RewriteRope.cpp - Rope specialized for rewriter --------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9//  This file implements the RewriteRope class, which is a powerful string.
10//
11//===----------------------------------------------------------------------===//
12
13#include "clang/Rewrite/Core/RewriteRope.h"
14#include "clang/Basic/LLVM.h"
15#include "llvm/Support/Casting.h"
16#include <algorithm>
17#include <cassert>
18#include <cstring>
19
20using namespace clang;
21
22/// RewriteRope is a "strong" string class, designed to make insertions and
23/// deletions in the middle of the string nearly constant time (really, they are
24/// O(log N), but with a very low constant factor).
25///
26/// The implementation of this datastructure is a conceptual linear sequence of
27/// RopePiece elements.  Each RopePiece represents a view on a separately
28/// allocated and reference counted string.  This means that splitting a very
29/// long string can be done in constant time by splitting a RopePiece that
30/// references the whole string into two rope pieces that reference each half.
31/// Once split, another string can be inserted in between the two halves by
32/// inserting a RopePiece in between the two others.  All of this is very
33/// inexpensive: it takes time proportional to the number of RopePieces, not the
34/// length of the strings they represent.
35///
36/// While a linear sequences of RopePieces is the conceptual model, the actual
37/// implementation captures them in an adapted B+ Tree.  Using a B+ tree (which
38/// is a tree that keeps the values in the leaves and has where each node
39/// contains a reasonable number of pointers to children/values) allows us to
40/// maintain efficient operation when the RewriteRope contains a *huge* number
41/// of RopePieces.  The basic idea of the B+ Tree is that it allows us to find
42/// the RopePiece corresponding to some offset very efficiently, and it
43/// automatically balances itself on insertions of RopePieces (which can happen
44/// for both insertions and erases of string ranges).
45///
46/// The one wrinkle on the theory is that we don't attempt to keep the tree
47/// properly balanced when erases happen.  Erases of string data can both insert
48/// new RopePieces (e.g. when the middle of some other rope piece is deleted,
49/// which results in two rope pieces, which is just like an insert) or it can
50/// reduce the number of RopePieces maintained by the B+Tree.  In the case when
51/// the number of RopePieces is reduced, we don't attempt to maintain the
52/// standard 'invariant' that each node in the tree contains at least
53/// 'WidthFactor' children/values.  For our use cases, this doesn't seem to
54/// matter.
55///
56/// The implementation below is primarily implemented in terms of three classes:
57///   RopePieceBTreeNode - Common base class for:
58///
59///     RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
60///          nodes.  This directly represents a chunk of the string with those
61///          RopePieces concatenated.
62///     RopePieceBTreeInterior - An interior node in the B+ Tree, which manages
63///          up to '2*WidthFactor' other nodes in the tree.
64
65namespace {
66
67//===----------------------------------------------------------------------===//
68// RopePieceBTreeNode Class
69//===----------------------------------------------------------------------===//
70
71  /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and
72  /// RopePieceBTreeInterior.  This provides some 'virtual' dispatching methods
73  /// and a flag that determines which subclass the instance is.  Also
74  /// important, this node knows the full extend of the node, including any
75  /// children that it has.  This allows efficient skipping over entire subtrees
76  /// when looking for an offset in the BTree.
77  class RopePieceBTreeNode {
78  protected:
79    /// WidthFactor - This controls the number of K/V slots held in the BTree:
80    /// how wide it is.  Each level of the BTree is guaranteed to have at least
81    /// 'WidthFactor' elements in it (either ropepieces or children), (except
82    /// the root, which may have less) and may have at most 2*WidthFactor
83    /// elements.
84    enum { WidthFactor = 8 };
85
86    /// Size - This is the number of bytes of file this node (including any
87    /// potential children) covers.
88    unsigned Size = 0;
89
90    /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it
91    /// is an instance of RopePieceBTreeInterior.
92    bool IsLeaf;
93
94    RopePieceBTreeNode(bool isLeaf) : IsLeaf(isLeaf) {}
95    ~RopePieceBTreeNode() = default;
96
97  public:
98    bool isLeaf() const { return IsLeaf; }
99    unsigned size() const { return Size; }
100
101    void Destroy();
102
103    /// split - Split the range containing the specified offset so that we are
104    /// guaranteed that there is a place to do an insertion at the specified
105    /// offset.  The offset is relative, so "0" is the start of the node.
106    ///
107    /// If there is no space in this subtree for the extra piece, the extra tree
108    /// node is returned and must be inserted into a parent.
109    RopePieceBTreeNode *split(unsigned Offset);
110
111    /// insert - Insert the specified ropepiece into this tree node at the
112    /// specified offset.  The offset is relative, so "0" is the start of the
113    /// node.
114    ///
115    /// If there is no space in this subtree for the extra piece, the extra tree
116    /// node is returned and must be inserted into a parent.
117    RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);
118
119    /// erase - Remove NumBytes from this node at the specified offset.  We are
120    /// guaranteed that there is a split at Offset.
121    void erase(unsigned Offset, unsigned NumBytes);
122  };
123
124//===----------------------------------------------------------------------===//
125// RopePieceBTreeLeaf Class
126//===----------------------------------------------------------------------===//
127
128  /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece
129  /// nodes.  This directly represents a chunk of the string with those
130  /// RopePieces concatenated.  Since this is a B+Tree, all values (in this case
131  /// instances of RopePiece) are stored in leaves like this.  To make iteration
132  /// over the leaves efficient, they maintain a singly linked list through the
133  /// NextLeaf field.  This allows the B+Tree forward iterator to be constant
134  /// time for all increments.
135  class RopePieceBTreeLeaf : public RopePieceBTreeNode {
136    /// NumPieces - This holds the number of rope pieces currently active in the
137    /// Pieces array.
138    unsigned char NumPieces = 0;
139
140    /// Pieces - This tracks the file chunks currently in this leaf.
141    RopePiece Pieces[2*WidthFactor];
142
143    /// NextLeaf - This is a pointer to the next leaf in the tree, allowing
144    /// efficient in-order forward iteration of the tree without traversal.
145    RopePieceBTreeLeaf **PrevLeaf = nullptr;
146    RopePieceBTreeLeaf *NextLeaf = nullptr;
147
148  public:
149    RopePieceBTreeLeaf() : RopePieceBTreeNode(true) {}
150
151    ~RopePieceBTreeLeaf() {
152      if (PrevLeaf || NextLeaf)
153        removeFromLeafInOrder();
154      clear();
155    }
156
157    bool isFull() const { return NumPieces == 2*WidthFactor; }
158
159    /// clear - Remove all rope pieces from this leaf.
160    void clear() {
161      while (NumPieces)
162        Pieces[--NumPieces] = RopePiece();
163      Size = 0;
164    }
165
166    unsigned getNumPieces() const { return NumPieces; }
167
168    const RopePiece &getPiece(unsigned i) const {
169       (0) . __assert_fail ("i < getNumPieces() && \"Invalid piece ID\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 169, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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       (0) . __assert_fail ("!PrevLeaf && !NextLeaf && \"Already in ordering\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 176, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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.
236RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {
237  // Find the insertion point.  We are guaranteed that there is a split at the
238  // specified offset so find it.
239  if (Offset == 0 || Offset == size()) {
240    // Fastpath for a common case.  There is already a splitpoint at the end.
241    return nullptr;
242  }
243
244  // Find the piece that this offset lands in.
245  unsigned PieceOffs = 0;
246  unsigned i = 0;
247  while (Offset >= PieceOffs+Pieces[i].size()) {
248    PieceOffs += Pieces[i].size();
249    ++i;
250  }
251
252  // If there is already a split point at the specified offset, just return
253  // success.
254  if (PieceOffs == Offset)
255    return nullptr;
256
257  // Otherwise, we need to split piece 'i' at Offset-PieceOffs.  Convert Offset
258  // to being Piece relative.
259  unsigned IntraPieceOffset = Offset-PieceOffs;
260
261  // We do this by shrinking the RopePiece and then doing an insert of the tail.
262  RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset,
263                 Pieces[i].EndOffs);
264  Size -= Pieces[i].size();
265  Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset;
266  Size += Pieces[i].size();
267
268  return insert(Offset, Tail);
269}
270
271/// insert - Insert the specified RopePiece into this tree node at the
272/// specified offset.  The offset is relative, so "0" is the start of the node.
273///
274/// If there is no space in this subtree for the extra piece, the extra tree
275/// node is returned and must be inserted into a parent.
276RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,
277                                               const RopePiece &R) {
278  // If this node is not full, insert the piece.
279  if (!isFull()) {
280    // Find the insertion point.  We are guaranteed that there is a split at the
281    // specified offset so find it.
282    unsigned i = 0, e = getNumPieces();
283    if (Offset == size()) {
284      // Fastpath for a common case.
285      i = e;
286    } else {
287      unsigned SlotOffs = 0;
288      for (; Offset > SlotOffs; ++i)
289        SlotOffs += getPiece(i).size();
290       (0) . __assert_fail ("SlotOffs == Offset && \"Split didn't occur before insertion!\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 290, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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.
337void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {
338  // Since we are guaranteed that there is a split at Offset, we start by
339  // finding the Piece that starts there.
340  unsigned PieceOffs = 0;
341  unsigned i = 0;
342  for (; Offset > PieceOffs; ++i)
343    PieceOffs += getPiece(i).size();
344   (0) . __assert_fail ("PieceOffs == Offset && \"Split didn't occur before erase!\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 344, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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   NumBytes", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 380, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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
391namespace {
392
393  /// RopePieceBTreeInterior - This represents an interior node in the B+Tree,
394  /// which holds up to 2*WidthFactor pointers to child nodes.
395  class RopePieceBTreeInterior : public RopePieceBTreeNode {
396    /// NumChildren - This holds the number of children currently active in the
397    /// Children array.
398    unsigned char NumChildren = 0;
399
400    RopePieceBTreeNode *Children[2*WidthFactor];
401
402  public:
403    RopePieceBTreeInterior() : RopePieceBTreeNode(false) {}
404
405    RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)
406        : RopePieceBTreeNode(false) {
407      Children[0] = LHS;
408      Children[1] = RHS;
409      NumChildren = 2;
410      Size = LHS->size() + RHS->size();
411    }
412
413    ~RopePieceBTreeInterior() {
414      for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
415        Children[i]->Destroy();
416    }
417
418    bool isFull() const { return NumChildren == 2*WidthFactor; }
419
420    unsigned getNumChildren() const { return NumChildren; }
421
422    const RopePieceBTreeNode *getChild(unsigned i) const {
423       (0) . __assert_fail ("i < NumChildren && \"invalid child #\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 423, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(i < NumChildren && "invalid child #");
424      return Children[i];
425    }
426
427    RopePieceBTreeNode *getChild(unsigned i) {
428       (0) . __assert_fail ("i < NumChildren && \"invalid child #\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 428, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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.
477RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {
478  // Figure out which child to split.
479  if (Offset == 0 || Offset == size())
480    return nullptr; // If we have an exact offset, we're already split.
481
482  unsigned ChildOffset = 0;
483  unsigned i = 0;
484  for (; Offset >= ChildOffset+getChild(i)->size(); ++i)
485    ChildOffset += getChild(i)->size();
486
487  // If already split there, we're done.
488  if (ChildOffset == Offset)
489    return nullptr;
490
491  // Otherwise, recursively split the child.
492  if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset))
493    return HandleChildPiece(i, RHS);
494  return nullptr; // Done!
495}
496
497/// insert - Insert the specified ropepiece into this tree node at the
498/// specified offset.  The offset is relative, so "0" is the start of the
499/// node.
500///
501/// If there is no space in this subtree for the extra piece, the extra tree
502/// node is returned and must be inserted into a parent.
503RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,
504                                                   const RopePiece &R) {
505  // Find the insertion point.  We are guaranteed that there is a split at the
506  // specified offset so find it.
507  unsigned i = 0, e = getNumChildren();
508
509  unsigned ChildOffs = 0;
510  if (Offset == size()) {
511    // Fastpath for a common case.  Insert at end of last child.
512    i = e-1;
513    ChildOffs = size()-getChild(i)->size();
514  } else {
515    for (; Offset > ChildOffs+getChild(i)->size(); ++i)
516      ChildOffs += getChild(i)->size();
517  }
518
519  Size += R.size();
520
521  // Insert at the end of this child.
522  if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R))
523    return HandleChildPiece(i, RHS);
524
525  return nullptr;
526}
527
528/// HandleChildPiece - A child propagated an insertion result up to us.
529/// Insert the new child, and/or propagate the result further up the tree.
530RopePieceBTreeNode *
531RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {
532  // Otherwise the child propagated a subtree up to us as a new child.  See if
533  // we have space for it here.
534  if (!isFull()) {
535    // Insert RHS after child 'i'.
536    if (i + 1 != getNumChildren())
537      memmove(&Children[i+2], &Children[i+1],
538              (getNumChildren()-i-1)*sizeof(Children[0]));
539    Children[i+1] = RHS;
540    ++NumChildren;
541    return nullptr;
542  }
543
544  // Okay, this node is full.  Split it in half, moving WidthFactor children to
545  // a newly allocated interior node.
546
547  // Create the new node.
548  RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();
549
550  // Move over the last 'WidthFactor' values from here to NewNode.
551  memcpy(&NewNode->Children[0], &Children[WidthFactor],
552         WidthFactor*sizeof(Children[0]));
553
554  // Decrease the number of values in the two nodes.
555  NewNode->NumChildren = NumChildren = WidthFactor;
556
557  // Finally, insert the two new children in the side the can (now) hold them.
558  // These insertions can't fail.
559  if (i < WidthFactor)
560    this->HandleChildPiece(i, RHS);
561  else
562    NewNode->HandleChildPiece(i-WidthFactor, RHS);
563
564  // Recompute the two nodes' size.
565  NewNode->FullRecomputeSizeLocally();
566  FullRecomputeSizeLocally();
567  return NewNode;
568}
569
570/// erase - Remove NumBytes from this node at the specified offset.  We are
571/// guaranteed that there is a split at Offset.
572void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {
573  // This will shrink this node by NumBytes.
574  Size -= NumBytes;
575
576  // Find the first child that overlaps with Offset.
577  unsigned i = 0;
578  for (; Offset >= getChild(i)->size(); ++i)
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
620void 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.
633RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {
634   (0) . __assert_fail ("Offset <= size() && \"Invalid offset to split!\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 634, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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.
646RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,
647                                               const RopePiece &R) {
648   (0) . __assert_fail ("Offset <= size() && \"Invalid offset to insert!\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 648, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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.
656void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {
657   (0) . __assert_fail ("Offset+NumBytes <= size() && \"Invalid offset to erase!\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 657, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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
667static const RopePieceBTreeLeaf *getCN(const void *P) {
668  return static_cast<const RopePieceBTreeLeaf*>(P);
669}
670
671// begin iterator.
672RopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) {
673  const auto *N = static_cast<const RopePieceBTreeNode *>(n);
674
675  // Walk down the left side of the tree until we get to a leaf.
676  while (const auto *IN = dyn_cast<RopePieceBTreeInterior>(N))
677    N = IN->getChild(0);
678
679  // We must have at least one leaf.
680  CurNode = cast<RopePieceBTreeLeaf>(N);
681
682  // If we found a leaf that happens to be empty, skip over it until we get
683  // to something full.
684  while (CurNode && getCN(CurNode)->getNumPieces() == 0)
685    CurNode = getCN(CurNode)->getNextLeafInOrder();
686
687  if (CurNode)
688    CurPiece = &getCN(CurNode)->getPiece(0);
689  else  // Empty tree, this is an end() iterator.
690    CurPiece = nullptr;
691  CurChar = 0;
692}
693
694void RopePieceBTreeIterator::MoveToNextPiece() {
695  if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) {
696    CurChar = 0;
697    ++CurPiece;
698    return;
699  }
700
701  // Find the next non-empty leaf node.
702  do
703    CurNode = getCN(CurNode)->getNextLeafInOrder();
704  while (CurNode && getCN(CurNode)->getNumPieces() == 0);
705
706  if (CurNode)
707    CurPiece = &getCN(CurNode)->getPiece(0);
708  else // Hit end().
709    CurPiece = nullptr;
710  CurChar = 0;
711}
712
713//===----------------------------------------------------------------------===//
714// RopePieceBTree Implementation
715//===----------------------------------------------------------------------===//
716
717static RopePieceBTreeNode *getRoot(void *P) {
718  return static_cast<RopePieceBTreeNode*>(P);
719}
720
721RopePieceBTree::RopePieceBTree() {
722  Root = new RopePieceBTreeLeaf();
723}
724
725RopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) {
726   (0) . __assert_fail ("RHS.empty() && \"Can't copy non-empty tree yet\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 726, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(RHS.empty() && "Can't copy non-empty tree yet");
727  Root = new RopePieceBTreeLeaf();
728}
729
730RopePieceBTree::~RopePieceBTree() {
731  getRoot(Root)->Destroy();
732}
733
734unsigned RopePieceBTree::size() const {
735  return getRoot(Root)->size();
736}
737
738void RopePieceBTree::clear() {
739  if (auto *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root)))
740    Leaf->clear();
741  else {
742    getRoot(Root)->Destroy();
743    Root = new RopePieceBTreeLeaf();
744  }
745}
746
747void RopePieceBTree::insert(unsigned Offset, const RopePiece &R) {
748  // #1. Split at Offset.
749  if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset))
750    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
751
752  // #2. Do the insertion.
753  if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R))
754    Root = new RopePieceBTreeInterior(getRoot(Root), RHS);
755}
756
757void RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) {
758  // #1. Split at Offset.
759  if (RopePieceBTreeNode *RHS = 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.
774RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {
775  unsigned Len = End-Start;
776   (0) . __assert_fail ("Len && \"Zero length RopePiece is invalid!\"", "/home/seafit/code_projects/clang_source/clang/lib/Rewrite/RewriteRope.cpp", 776, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">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}
807
clang::RopePieceBTreeIterator::MoveToNextPiece
clang::RopePieceBTree::size
clang::RopePieceBTree::clear
clang::RopePieceBTree::insert
clang::RopePieceBTree::erase
clang::RewriteRope::MakeRopeString
CodeThinker, Enjoy your reading code