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