clang  9.0.0svn
RewriteRope.h
Go to the documentation of this file.
1 //===- RewriteRope.h - Rope specialized for rewriter ------------*- C++ -*-===//
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 defines the RewriteRope class, which is a powerful string class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
14 #define LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
15 
16 #include "llvm/ADT/IntrusiveRefCntPtr.h"
17 #include "llvm/ADT/StringRef.h"
18 #include <cassert>
19 #include <cstddef>
20 #include <iterator>
21 #include <utility>
22 
23 namespace clang {
24 
25  //===--------------------------------------------------------------------===//
26  // RopeRefCountString Class
27  //===--------------------------------------------------------------------===//
28 
29  /// RopeRefCountString - This struct is allocated with 'new char[]' from the
30  /// heap, and represents a reference counted chunk of string data. When its
31  /// ref count drops to zero, it is delete[]'d. This is primarily managed
32  /// through the RopePiece class below.
34  unsigned RefCount;
35  char Data[1]; // Variable sized.
36 
37  void Retain() { ++RefCount; }
38 
39  void Release() {
40  assert(RefCount > 0 && "Reference count is already zero.");
41  if (--RefCount == 0)
42  delete [] (char*)this;
43  }
44  };
45 
46  //===--------------------------------------------------------------------===//
47  // RopePiece Class
48  //===--------------------------------------------------------------------===//
49 
50  /// RopePiece - This class represents a view into a RopeRefCountString object.
51  /// This allows references to string data to be efficiently chopped up and
52  /// moved around without having to push around the string data itself.
53  ///
54  /// For example, we could have a 1M RopePiece and want to insert something
55  /// into the middle of it. To do this, we split it into two RopePiece objects
56  /// that both refer to the same underlying RopeRefCountString (just with
57  /// different offsets) which is a nice constant time operation.
58  struct RopePiece {
60  unsigned StartOffs = 0;
61  unsigned EndOffs = 0;
62 
63  RopePiece() = default;
65  unsigned End)
66  : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
67 
68  const char &operator[](unsigned Offset) const {
69  return StrData->Data[Offset+StartOffs];
70  }
71  char &operator[](unsigned Offset) {
72  return StrData->Data[Offset+StartOffs];
73  }
74 
75  unsigned size() const { return EndOffs-StartOffs; }
76  };
77 
78  //===--------------------------------------------------------------------===//
79  // RopePieceBTreeIterator Class
80  //===--------------------------------------------------------------------===//
81 
82  /// RopePieceBTreeIterator - This class provides read-only forward iteration
83  /// over bytes that are in a RopePieceBTree. This first iterates over bytes
84  /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
85  /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
87  public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> {
88  /// CurNode - The current B+Tree node that we are inspecting.
89  const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr;
90 
91  /// CurPiece - The current RopePiece in the B+Tree node that we're
92  /// inspecting.
93  const RopePiece *CurPiece = nullptr;
94 
95  /// CurChar - The current byte in the RopePiece we are pointing to.
96  unsigned CurChar = 0;
97 
98  public:
99  RopePieceBTreeIterator() = default;
100  RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
101 
102  char operator*() const {
103  return (*CurPiece)[CurChar];
104  }
105 
106  bool operator==(const RopePieceBTreeIterator &RHS) const {
107  return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
108  }
109  bool operator!=(const RopePieceBTreeIterator &RHS) const {
110  return !operator==(RHS);
111  }
112 
113  RopePieceBTreeIterator& operator++() { // Preincrement
114  if (CurChar+1 < CurPiece->size())
115  ++CurChar;
116  else
117  MoveToNextPiece();
118  return *this;
119  }
120 
121  RopePieceBTreeIterator operator++(int) { // Postincrement
122  RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
123  }
124 
125  llvm::StringRef piece() const {
126  return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
127  }
128 
129  void MoveToNextPiece();
130  };
131 
132  //===--------------------------------------------------------------------===//
133  // RopePieceBTree Class
134  //===--------------------------------------------------------------------===//
135 
137  void /*RopePieceBTreeNode*/ *Root;
138 
139  public:
140  RopePieceBTree();
141  RopePieceBTree(const RopePieceBTree &RHS);
142  RopePieceBTree &operator=(const RopePieceBTree &) = delete;
143  ~RopePieceBTree();
144 
146 
147  iterator begin() const { return iterator(Root); }
148  iterator end() const { return iterator(); }
149  unsigned size() const;
150  unsigned empty() const { return size() == 0; }
151 
152  void clear();
153 
154  void insert(unsigned Offset, const RopePiece &R);
155 
156  void erase(unsigned Offset, unsigned NumBytes);
157  };
158 
159  //===--------------------------------------------------------------------===//
160  // RewriteRope Class
161  //===--------------------------------------------------------------------===//
162 
163 /// RewriteRope - A powerful string class. This class supports extremely
164 /// efficient insertions and deletions into the middle of it, even for
165 /// ridiculously long strings.
166 class RewriteRope {
167  RopePieceBTree Chunks;
168 
169  /// We allocate space for string data out of a buffer of size AllocChunkSize.
170  /// This keeps track of how much space is left.
172  enum { AllocChunkSize = 4080 };
173  unsigned AllocOffs = AllocChunkSize;
174 
175 public:
176  RewriteRope() = default;
177  RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}
178 
181 
182  iterator begin() const { return Chunks.begin(); }
183  iterator end() const { return Chunks.end(); }
184  unsigned size() const { return Chunks.size(); }
185 
186  void clear() {
187  Chunks.clear();
188  }
189 
190  void assign(const char *Start, const char *End) {
191  clear();
192  if (Start != End)
193  Chunks.insert(0, MakeRopeString(Start, End));
194  }
195 
196  void insert(unsigned Offset, const char *Start, const char *End) {
197  assert(Offset <= size() && "Invalid position to insert!");
198  if (Start == End) return;
199  Chunks.insert(Offset, MakeRopeString(Start, End));
200  }
201 
202  void erase(unsigned Offset, unsigned NumBytes) {
203  assert(Offset+NumBytes <= size() && "Invalid region to erase!");
204  if (NumBytes == 0) return;
205  Chunks.erase(Offset, NumBytes);
206  }
207 
208 private:
209  RopePiece MakeRopeString(const char *Start, const char *End);
210 };
211 
212 } // namespace clang
213 
214 #endif // LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
void insert(unsigned Offset, const char *Start, const char *End)
Definition: RewriteRope.h:196
bool operator==(CanQual< T > x, CanQual< U > y)
void insert(unsigned Offset, const RopePiece &R)
RewriteRope - A powerful string class.
Definition: RewriteRope.h:166
virtual void clear()
llvm::StringRef piece() const
Definition: RewriteRope.h:125
void erase(unsigned Offset, unsigned NumBytes)
Definition: RewriteRope.h:202
RopePieceBTreeIterator & operator++()
Definition: RewriteRope.h:113
RopeRefCountString - This struct is allocated with &#39;new char[]&#39; from the heap, and represents a refer...
Definition: RewriteRope.h:33
Definition: Format.h:2222
const char & operator[](unsigned Offset) const
Definition: RewriteRope.h:68
RopePiece - This class represents a view into a RopeRefCountString object.
Definition: RewriteRope.h:58
iterator end() const
Definition: RewriteRope.h:183
llvm::IntrusiveRefCntPtr< RopeRefCountString > StrData
Definition: RewriteRope.h:59
void erase(unsigned Offset, unsigned NumBytes)
iterator begin() const
Definition: RewriteRope.h:182
unsigned empty() const
Definition: RewriteRope.h:150
unsigned Offset
Definition: Format.cpp:1709
SourceLocation End
RewriteRope(const RewriteRope &RHS)
Definition: RewriteRope.h:177
unsigned size() const
Definition: RewriteRope.h:184
RopePieceBTreeIterator iterator
Definition: RewriteRope.h:145
unsigned size() const
Definition: RewriteRope.h:75
RopePiece(llvm::IntrusiveRefCntPtr< RopeRefCountString > Str, unsigned Start, unsigned End)
Definition: RewriteRope.h:64
Dataflow Directional Tag Classes.
RopePieceBTreeIterator - This class provides read-only forward iteration over bytes that are in a Rop...
Definition: RewriteRope.h:86
bool operator==(const RopePieceBTreeIterator &RHS) const
Definition: RewriteRope.h:106
void assign(const char *Start, const char *End)
Definition: RewriteRope.h:190
unsigned size() const
iterator begin() const
Definition: RewriteRope.h:147
iterator end() const
Definition: RewriteRope.h:148
char & operator[](unsigned Offset)
Definition: RewriteRope.h:71
RopePieceBTreeIterator operator++(int)
Definition: RewriteRope.h:121
bool operator!=(const RopePieceBTreeIterator &RHS) const
Definition: RewriteRope.h:109