 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
94.4% |
17 / 18 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
100.0% |
18 / 18 |
| |
|
Line Coverage: |
100.0% |
67 / 67 |
| |
 |
|
 |
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_REWRITEROPE_H
15 : #define LLVM_CLANG_REWRITEROPE_H
16 :
17 : #include <cstring>
18 : #include <cassert>
19 : #include <iterator>
20 :
21 : namespace clang {
22 : //===--------------------------------------------------------------------===//
23 : // RopeRefCountString Class
24 : //===--------------------------------------------------------------------===//
25 :
26 : /// RopeRefCountString - This struct is allocated with 'new char[]' from the
27 : /// heap, and represents a reference counted chunk of string data. When its
28 : /// ref count drops to zero, it is delete[]'d. This is primarily managed
29 : /// through the RopePiece class below.
30 : struct RopeRefCountString {
31 : unsigned RefCount;
32 : char Data[1]; // Variable sized.
33 :
34 7648: void addRef() {
6165: branch 0 taken
1483: branch 1 taken
35 7648: if (this) ++RefCount;
36 7648: }
37 :
38 11774: void dropRef() {
4269: branch 0 taken
7505: branch 1 taken
25: branch 2 taken
4244: branch 3 taken
25: branch 4 taken
11749: branch 5 taken
39 11774: if (this && --RefCount == 0)
25: branch 0 taken
0: branch 1 not taken
40 25: delete [] (char*)this;
41 11774: }
42 : };
43 :
44 : //===--------------------------------------------------------------------===//
45 : // RopePiece Class
46 : //===--------------------------------------------------------------------===//
47 :
48 : /// RopePiece - This class represents a view into a RopeRefCountString object.
49 : /// This allows references to string data to be efficiently chopped up and
50 : /// moved around without having to push around the string data itself.
51 : ///
52 : /// For example, we could have a 1M RopePiece and want to insert something
53 : /// into the middle of it. To do this, we split it into two RopePiece objects
54 : /// that both refer to the same underlying RopeRefCountString (just with
55 : /// different offsets) which is a nice constant time operation.
56 : struct RopePiece {
57 : RopeRefCountString *StrData;
58 : unsigned StartOffs;
59 : unsigned EndOffs;
60 :
61 7005: RopePiece() : StrData(0), StartOffs(0), EndOffs(0) {}
62 :
63 2179: RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End)
64 2179: : StrData(Str), StartOffs(Start), EndOffs(End) {
65 2179: StrData->addRef();
66 2179: }
67 : RopePiece(const RopePiece &RP)
68 : : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) {
69 : StrData->addRef();
70 : }
71 :
72 6144: ~RopePiece() {
73 6144: StrData->dropRef();
74 6144: }
75 :
76 8811: void operator=(const RopePiece &RHS) {
5362: branch 0 taken
3449: branch 1 taken
77 8811: if (StrData != RHS.StrData) {
78 5362: StrData->dropRef();
79 5362: StrData = RHS.StrData;
80 5362: StrData->addRef();
81 : }
82 8811: StartOffs = RHS.StartOffs;
83 8811: EndOffs = RHS.EndOffs;
84 8811: }
85 :
86 291498: const char &operator[](unsigned Offset) const {
87 291498: return StrData->Data[Offset+StartOffs];
88 : }
89 : char &operator[](unsigned Offset) {
90 : return StrData->Data[Offset+StartOffs];
91 : }
92 :
93 731744: unsigned size() const { return EndOffs-StartOffs; }
94 : };
95 :
96 : //===--------------------------------------------------------------------===//
97 : // RopePieceBTreeIterator Class
98 : //===--------------------------------------------------------------------===//
99 :
100 : /// RopePieceBTreeIterator - This class provides read-only forward iteration
101 : /// over bytes that are in a RopePieceBTree. This first iterates over bytes
102 : /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
103 : /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
104 : class RopePieceBTreeIterator :
105 : public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> {
106 : /// CurNode - The current B+Tree node that we are inspecting.
107 : const void /*RopePieceBTreeLeaf*/ *CurNode;
108 : /// CurPiece - The current RopePiece in the B+Tree node that we're
109 : /// inspecting.
110 : const RopePiece *CurPiece;
111 : /// CurChar - The current byte in the RopePiece we are pointing to.
112 : unsigned CurChar;
113 : public:
114 : // begin iterator.
115 : RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
116 : // end iterator
117 64: RopePieceBTreeIterator() : CurNode(0), CurPiece(0), CurChar(0) {}
118 :
119 291498: char operator*() const {
120 291498: return (*CurPiece)[CurChar];
121 : }
122 :
123 567253: bool operator==(const RopePieceBTreeIterator &RHS) const {
1353: branch 0 taken
565900: branch 1 taken
184: branch 2 taken
1169: branch 3 taken
124 567253: return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
125 : }
126 567163: bool operator!=(const RopePieceBTreeIterator &RHS) const {
127 567163: return !operator==(RHS);
128 : }
129 :
130 684623: RopePieceBTreeIterator& operator++() { // Preincrement
679692: branch 1 taken
4931: branch 2 taken
131 684623: if (CurChar+1 < CurPiece->size())
132 679692: ++CurChar;
133 : else
134 4931: MoveToNextPiece();
135 684623: return *this;
136 : }
137 : inline RopePieceBTreeIterator operator++(int) { // Postincrement
138 : RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
139 : }
140 : private:
141 : void MoveToNextPiece();
142 : };
143 :
144 : //===--------------------------------------------------------------------===//
145 : // RopePieceBTree Class
146 : //===--------------------------------------------------------------------===//
147 :
148 : class RopePieceBTree {
149 : void /*RopePieceBTreeNode*/ *Root;
150 : void operator=(const RopePieceBTree &); // DO NOT IMPLEMENT
151 : public:
152 : RopePieceBTree();
153 : RopePieceBTree(const RopePieceBTree &RHS);
154 : ~RopePieceBTree();
155 :
156 : typedef RopePieceBTreeIterator iterator;
157 94: iterator begin() const { return iterator(Root); }
158 64: iterator end() const { return iterator(); }
159 : unsigned size() const;
160 201: unsigned empty() const { return size() == 0; }
161 :
162 : void clear();
163 :
164 : void insert(unsigned Offset, const RopePiece &R);
165 :
166 : void erase(unsigned Offset, unsigned NumBytes);
167 : };
168 :
169 : //===--------------------------------------------------------------------===//
170 : // RewriteRope Class
171 : //===--------------------------------------------------------------------===//
172 :
173 : /// RewriteRope - A powerful string class. This class supports extremely
174 : /// efficient insertions and deletions into the middle of it, even for
175 : /// ridiculously long strings.
176 : class RewriteRope {
177 : RopePieceBTree Chunks;
178 :
179 : /// We allocate space for string data out of a buffer of size AllocChunkSize.
180 : /// This keeps track of how much space is left.
181 : RopeRefCountString *AllocBuffer;
182 : unsigned AllocOffs;
183 : enum { AllocChunkSize = 4080 };
184 :
185 : public:
186 67: RewriteRope() : AllocBuffer(0), AllocOffs(AllocChunkSize) {}
187 201: RewriteRope(const RewriteRope &RHS)
188 201: : Chunks(RHS.Chunks), AllocBuffer(0), AllocOffs(AllocChunkSize) {
189 201: }
190 :
191 268: ~RewriteRope() {
192 : // If we had an allocation buffer, drop our reference to it.
193 268: AllocBuffer->dropRef();
194 268: }
195 :
196 : typedef RopePieceBTree::iterator iterator;
197 : typedef RopePieceBTree::iterator const_iterator;
198 94: iterator begin() const { return Chunks.begin(); }
199 64: iterator end() const { return Chunks.end(); }
200 1727: unsigned size() const { return Chunks.size(); }
201 :
202 67: void clear() {
203 67: Chunks.clear();
204 67: }
205 :
206 67: void assign(const char *Start, const char *End) {
207 67: clear();
208 67: if (Start != End)
209 67: Chunks.insert(0, MakeRopeString(Start, End));
210 67: }
211 :
212 1179: void insert(unsigned Offset, const char *Start, const char *End) {
213 1179: assert(Offset <= size() && "Invalid position to insert!");
214 1179: if (Start == End) return;
215 1179: Chunks.insert(Offset, MakeRopeString(Start, End));
216 : }
217 :
218 536: void erase(unsigned Offset, unsigned NumBytes) {
219 536: assert(Offset+NumBytes <= size() && "Invalid region to erase!");
220 536: if (NumBytes == 0) return;
221 429: Chunks.erase(Offset, NumBytes);
222 : }
223 :
224 : private:
225 : RopePiece MakeRopeString(const char *Start, const char *End);
226 : };
227 :
228 : } // end namespace clang
229 :
230 : #endif
Generated: 2010-02-10 01:31 by zcov