Line data Source code
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.
34 : struct RopeRefCountString {
35 : unsigned RefCount;
36 : char Data[1]; // Variable sized.
37 :
38 : void Retain() { ++RefCount; }
39 :
40 : void Release() {
41 24 : assert(RefCount > 0 && "Reference count is already zero.");
42 12 : if (--RefCount == 0)
43 0 : delete [] (char*)this;
44 12 : }
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 {
60 : llvm::IntrusiveRefCntPtr<RopeRefCountString> StrData;
61 : unsigned StartOffs;
62 : unsigned EndOffs;
63 :
64 : RopePiece() : StrData(nullptr), StartOffs(0), EndOffs(0) {}
65 :
66 : RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,
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.
88 : class RopePieceBTreeIterator :
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
101 : RopePieceBTreeIterator()
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 :
137 : class RopePieceBTree {
138 : void /*RopePieceBTreeNode*/ *Root;
139 : void operator=(const RopePieceBTree &) = delete;
140 : public:
141 : RopePieceBTree();
142 : RopePieceBTree(const RopePieceBTree &RHS);
143 : ~RopePieceBTree();
144 :
145 : typedef RopePieceBTreeIterator iterator;
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 12 : 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.
170 : llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer;
171 : unsigned AllocOffs;
172 : enum { AllocChunkSize = 4080 };
173 :
174 : public:
175 : RewriteRope() : AllocBuffer(nullptr), AllocOffs(AllocChunkSize) {}
176 : RewriteRope(const RewriteRope &RHS)
177 : : Chunks(RHS.Chunks), AllocBuffer(nullptr), AllocOffs(AllocChunkSize) {
178 : }
179 :
180 : typedef RopePieceBTree::iterator iterator;
181 : typedef RopePieceBTree::iterator const_iterator;
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
|
