1 //===--- RewriteRope.h - Rope specialized for rewriter ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the RewriteRope class, which is a powerful string class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_REWRITEROPE_H
15 #define LLVM_CLANG_REWRITEROPE_H
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Support/Compiler.h"
25 //===--------------------------------------------------------------------===//
26 // RopeRefCountString Class
27 //===--------------------------------------------------------------------===//
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.
33 struct RopeRefCountString {
35 char Data[1]; // Variable sized.
43 delete [] (char*)this;
47 //===--------------------------------------------------------------------===//
49 //===--------------------------------------------------------------------===//
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.
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.
60 RopeRefCountString *StrData;
64 RopePiece() : StrData(nullptr), StartOffs(0), EndOffs(0) {}
66 RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End)
67 : StrData(Str), StartOffs(Start), EndOffs(End) {
71 RopePiece(const RopePiece &RP)
72 : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) {
82 void operator=(const RopePiece &RHS) {
83 if (StrData != RHS.StrData) {
86 StrData = RHS.StrData;
90 StartOffs = RHS.StartOffs;
91 EndOffs = RHS.EndOffs;
94 const char &operator[](unsigned Offset) const {
95 return StrData->Data[Offset+StartOffs];
97 char &operator[](unsigned Offset) {
98 return StrData->Data[Offset+StartOffs];
101 unsigned size() const { return EndOffs-StartOffs; }
104 //===--------------------------------------------------------------------===//
105 // RopePieceBTreeIterator Class
106 //===--------------------------------------------------------------------===//
108 /// RopePieceBTreeIterator - This class provides read-only forward iteration
109 /// over bytes that are in a RopePieceBTree. This first iterates over bytes
110 /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
111 /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
112 class RopePieceBTreeIterator :
113 public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> {
114 /// CurNode - The current B+Tree node that we are inspecting.
115 const void /*RopePieceBTreeLeaf*/ *CurNode;
116 /// CurPiece - The current RopePiece in the B+Tree node that we're
118 const RopePiece *CurPiece;
119 /// CurChar - The current byte in the RopePiece we are pointing to.
123 RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
125 RopePieceBTreeIterator()
126 : CurNode(nullptr), CurPiece(nullptr), CurChar(0) {}
128 char operator*() const {
129 return (*CurPiece)[CurChar];
132 bool operator==(const RopePieceBTreeIterator &RHS) const {
133 return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
135 bool operator!=(const RopePieceBTreeIterator &RHS) const {
136 return !operator==(RHS);
139 RopePieceBTreeIterator& operator++() { // Preincrement
140 if (CurChar+1 < CurPiece->size())
146 inline RopePieceBTreeIterator operator++(int) { // Postincrement
147 RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
150 llvm::StringRef piece() const {
151 return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
154 void MoveToNextPiece();
157 //===--------------------------------------------------------------------===//
158 // RopePieceBTree Class
159 //===--------------------------------------------------------------------===//
161 class RopePieceBTree {
162 void /*RopePieceBTreeNode*/ *Root;
163 void operator=(const RopePieceBTree &) LLVM_DELETED_FUNCTION;
166 RopePieceBTree(const RopePieceBTree &RHS);
169 typedef RopePieceBTreeIterator iterator;
170 iterator begin() const { return iterator(Root); }
171 iterator end() const { return iterator(); }
172 unsigned size() const;
173 unsigned empty() const { return size() == 0; }
177 void insert(unsigned Offset, const RopePiece &R);
179 void erase(unsigned Offset, unsigned NumBytes);
182 //===--------------------------------------------------------------------===//
184 //===--------------------------------------------------------------------===//
186 /// RewriteRope - A powerful string class. This class supports extremely
187 /// efficient insertions and deletions into the middle of it, even for
188 /// ridiculously long strings.
190 RopePieceBTree Chunks;
192 /// We allocate space for string data out of a buffer of size AllocChunkSize.
193 /// This keeps track of how much space is left.
194 RopeRefCountString *AllocBuffer;
196 enum { AllocChunkSize = 4080 };
199 RewriteRope() : AllocBuffer(nullptr), AllocOffs(AllocChunkSize) {}
200 RewriteRope(const RewriteRope &RHS)
201 : Chunks(RHS.Chunks), AllocBuffer(nullptr), AllocOffs(AllocChunkSize) {
205 // If we had an allocation buffer, drop our reference to it.
207 AllocBuffer->dropRef();
210 typedef RopePieceBTree::iterator iterator;
211 typedef RopePieceBTree::iterator const_iterator;
212 iterator begin() const { return Chunks.begin(); }
213 iterator end() const { return Chunks.end(); }
214 unsigned size() const { return Chunks.size(); }
220 void assign(const char *Start, const char *End) {
223 Chunks.insert(0, MakeRopeString(Start, End));
226 void insert(unsigned Offset, const char *Start, const char *End) {
227 assert(Offset <= size() && "Invalid position to insert!");
228 if (Start == End) return;
229 Chunks.insert(Offset, MakeRopeString(Start, End));
232 void erase(unsigned Offset, unsigned NumBytes) {
233 assert(Offset+NumBytes <= size() && "Invalid region to erase!");
234 if (NumBytes == 0) return;
235 Chunks.erase(Offset, NumBytes);
239 RopePiece MakeRopeString(const char *Start, const char *End);
242 } // end namespace clang