/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Rewrite/Core/RewriteRope.h
Line | Count | Source (jump to first uncovered line) |
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. |
33 | | struct RopeRefCountString { |
34 | | unsigned RefCount; |
35 | | char Data[1]; // Variable sized. |
36 | | |
37 | 1.89M | void Retain() { ++RefCount; } |
38 | | |
39 | 1.89M | void Release() { |
40 | 1.89M | assert(RefCount > 0 && "Reference count is already zero."); |
41 | 1.89M | if (--RefCount == 0) |
42 | 22.3k | delete [] (char*)this; |
43 | 1.89M | } |
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 { |
59 | | llvm::IntrusiveRefCntPtr<RopeRefCountString> StrData; |
60 | | unsigned StartOffs = 0; |
61 | | unsigned EndOffs = 0; |
62 | | |
63 | 1.58M | RopePiece() = default; |
64 | | RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start, |
65 | | unsigned End) |
66 | 301k | : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {} |
67 | | |
68 | 7.36M | const char &operator[](unsigned Offset) const { |
69 | 7.36M | return StrData->Data[Offset+StartOffs]; |
70 | 7.36M | } |
71 | 0 | char &operator[](unsigned Offset) { |
72 | 0 | return StrData->Data[Offset+StartOffs]; |
73 | 0 | } |
74 | | |
75 | 13.0M | 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. |
86 | | class RopePieceBTreeIterator { |
87 | | /// CurNode - The current B+Tree node that we are inspecting. |
88 | | const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr; |
89 | | |
90 | | /// CurPiece - The current RopePiece in the B+Tree node that we're |
91 | | /// inspecting. |
92 | | const RopePiece *CurPiece = nullptr; |
93 | | |
94 | | /// CurChar - The current byte in the RopePiece we are pointing to. |
95 | | unsigned CurChar = 0; |
96 | | |
97 | | public: |
98 | | using iterator_category = std::forward_iterator_tag; |
99 | | using value_type = const char; |
100 | | using difference_type = std::ptrdiff_t; |
101 | | using pointer = value_type *; |
102 | | using reference = value_type &; |
103 | | |
104 | 22.3k | RopePieceBTreeIterator() = default; |
105 | | RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N); |
106 | | |
107 | 7.21M | char operator*() const { |
108 | 7.21M | return (*CurPiece)[CurChar]; |
109 | 7.21M | } |
110 | | |
111 | 8.16M | bool operator==(const RopePieceBTreeIterator &RHS) const { |
112 | 8.16M | return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar26.7k ; |
113 | 8.16M | } |
114 | 8.16M | bool operator!=(const RopePieceBTreeIterator &RHS) const { |
115 | 8.16M | return !operator==(RHS); |
116 | 8.16M | } |
117 | | |
118 | 8.81M | RopePieceBTreeIterator& operator++() { // Preincrement |
119 | 8.81M | if (CurChar+1 < CurPiece->size()) |
120 | 8.64M | ++CurChar; |
121 | 168k | else |
122 | 168k | MoveToNextPiece(); |
123 | 8.81M | return *this; |
124 | 8.81M | } |
125 | | |
126 | 0 | RopePieceBTreeIterator operator++(int) { // Postincrement |
127 | 0 | RopePieceBTreeIterator tmp = *this; ++*this; return tmp; |
128 | 0 | } |
129 | | |
130 | 147k | llvm::StringRef piece() const { |
131 | 147k | return llvm::StringRef(&(*CurPiece)[0], CurPiece->size()); |
132 | 147k | } |
133 | | |
134 | | void MoveToNextPiece(); |
135 | | }; |
136 | | |
137 | | //===--------------------------------------------------------------------===// |
138 | | // RopePieceBTree Class |
139 | | //===--------------------------------------------------------------------===// |
140 | | |
141 | | class RopePieceBTree { |
142 | | void /*RopePieceBTreeNode*/ *Root; |
143 | | |
144 | | public: |
145 | | RopePieceBTree(); |
146 | | RopePieceBTree(const RopePieceBTree &RHS); |
147 | | RopePieceBTree &operator=(const RopePieceBTree &) = delete; |
148 | | ~RopePieceBTree(); |
149 | | |
150 | | using iterator = RopePieceBTreeIterator; |
151 | | |
152 | 21.5k | iterator begin() const { return iterator(Root); } |
153 | 22.3k | iterator end() const { return iterator(); } |
154 | | unsigned size() const; |
155 | 41.7k | unsigned empty() const { return size() == 0; } |
156 | | |
157 | | void clear(); |
158 | | |
159 | | void insert(unsigned Offset, const RopePiece &R); |
160 | | |
161 | | void erase(unsigned Offset, unsigned NumBytes); |
162 | | }; |
163 | | |
164 | | //===--------------------------------------------------------------------===// |
165 | | // RewriteRope Class |
166 | | //===--------------------------------------------------------------------===// |
167 | | |
168 | | /// RewriteRope - A powerful string class. This class supports extremely |
169 | | /// efficient insertions and deletions into the middle of it, even for |
170 | | /// ridiculously long strings. |
171 | | class RewriteRope { |
172 | | RopePieceBTree Chunks; |
173 | | |
174 | | /// We allocate space for string data out of a buffer of size AllocChunkSize. |
175 | | /// This keeps track of how much space is left. |
176 | | llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer; |
177 | | enum { AllocChunkSize = 4080 }; |
178 | | unsigned AllocOffs = AllocChunkSize; |
179 | | |
180 | | public: |
181 | 20.8k | RewriteRope() = default; |
182 | 41.7k | RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {} |
183 | | |
184 | | using iterator = RopePieceBTree::iterator; |
185 | | using const_iterator = RopePieceBTree::iterator; |
186 | | |
187 | 21.5k | iterator begin() const { return Chunks.begin(); } |
188 | 22.3k | iterator end() const { return Chunks.end(); } |
189 | 224k | unsigned size() const { return Chunks.size(); } |
190 | | |
191 | 20.8k | void clear() { |
192 | 20.8k | Chunks.clear(); |
193 | 20.8k | } |
194 | | |
195 | 20.8k | void assign(const char *Start, const char *End) { |
196 | 20.8k | clear(); |
197 | 20.8k | if (Start != End) |
198 | 20.8k | Chunks.insert(0, MakeRopeString(Start, End)); |
199 | 20.8k | } |
200 | | |
201 | 151k | void insert(unsigned Offset, const char *Start, const char *End) { |
202 | 151k | assert(Offset <= size() && "Invalid position to insert!"); |
203 | 151k | if (Start == End) return3.19k ; |
204 | 148k | Chunks.insert(Offset, MakeRopeString(Start, End)); |
205 | 148k | } |
206 | | |
207 | 72.4k | void erase(unsigned Offset, unsigned NumBytes) { |
208 | 72.4k | assert(Offset+NumBytes <= size() && "Invalid region to erase!"); |
209 | 72.4k | if (NumBytes == 0) return4.85k ; |
210 | 67.5k | Chunks.erase(Offset, NumBytes); |
211 | 67.5k | } |
212 | | |
213 | | private: |
214 | | RopePiece MakeRopeString(const char *Start, const char *End); |
215 | | }; |
216 | | |
217 | | } // namespace clang |
218 | | |
219 | | #endif // LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H |