Line data Source code
1 : //===- ASTVector.h - Vector that uses ASTContext for allocation --*- 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 provides ASTVector, a vector ADT whose contents are
11 : // allocated using the allocator associated with an ASTContext..
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : // FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h.
16 : // We can refactor this core logic into something common.
17 :
18 : #ifndef LLVM_CLANG_AST_ASTVECTOR_H
19 : #define LLVM_CLANG_AST_ASTVECTOR_H
20 :
21 : #include "clang/AST/AttrIterator.h"
22 : #include "llvm/ADT/PointerIntPair.h"
23 : #include "llvm/Support/Allocator.h"
24 : #include "llvm/Support/type_traits.h"
25 : #include <algorithm>
26 : #include <cstring>
27 : #include <memory>
28 :
29 : namespace clang {
30 : class ASTContext;
31 :
32 : template<typename T>
33 : class ASTVector {
34 : private:
35 : T *Begin, *End;
36 : llvm::PointerIntPair<T*, 1, bool> Capacity;
37 :
38 : void setEnd(T *P) { this->End = P; }
39 :
40 : protected:
41 : // Make a tag bit available to users of this class.
42 : // FIXME: This is a horrible hack.
43 : bool getTag() const { return Capacity.getInt(); }
44 : void setTag(bool B) { Capacity.setInt(B); }
45 :
46 : public:
47 : // Default ctor - Initialize to empty.
48 : ASTVector() : Begin(nullptr), End(nullptr), Capacity(nullptr, false) {}
49 :
50 : ASTVector(ASTVector &&O) : Begin(O.Begin), End(O.End), Capacity(O.Capacity) {
51 : O.Begin = O.End = nullptr;
52 : O.Capacity.setPointer(nullptr);
53 : O.Capacity.setInt(false);
54 : }
55 :
56 : ASTVector(const ASTContext &C, unsigned N)
57 : : Begin(nullptr), End(nullptr), Capacity(nullptr, false) {
58 : reserve(C, N);
59 : }
60 :
61 : ASTVector &operator=(ASTVector &&RHS) {
62 : ASTVector O(std::move(RHS));
63 : using std::swap;
64 : swap(Begin, O.Begin);
65 : swap(End, O.End);
66 : swap(Capacity, O.Capacity);
67 : return *this;
68 : }
69 :
70 : ~ASTVector() {
71 : if (std::is_class<T>::value) {
72 : // Destroy the constructed elements in the vector.
73 : destroy_range(Begin, End);
74 : }
75 : }
76 :
77 : typedef size_t size_type;
78 : typedef ptrdiff_t difference_type;
79 : typedef T value_type;
80 : typedef T* iterator;
81 : typedef const T* const_iterator;
82 :
83 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
84 : typedef std::reverse_iterator<iterator> reverse_iterator;
85 :
86 : typedef T& reference;
87 : typedef const T& const_reference;
88 : typedef T* pointer;
89 : typedef const T* const_pointer;
90 :
91 : // forward iterator creation methods.
92 : iterator begin() { return Begin; }
93 : const_iterator begin() const { return Begin; }
94 : iterator end() { return End; }
95 : const_iterator end() const { return End; }
96 :
97 : // reverse iterator creation methods.
98 : reverse_iterator rbegin() { return reverse_iterator(end()); }
99 : const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
100 : reverse_iterator rend() { return reverse_iterator(begin()); }
101 : const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
102 :
103 0 : bool empty() const { return Begin == End; }
104 0 : size_type size() const { return End-Begin; }
105 :
106 : reference operator[](unsigned idx) {
107 0 : assert(Begin + idx < End);
108 0 : return Begin[idx];
109 : }
110 : const_reference operator[](unsigned idx) const {
111 : assert(Begin + idx < End);
112 : return Begin[idx];
113 : }
114 :
115 : reference front() {
116 : return begin()[0];
117 : }
118 : const_reference front() const {
119 : return begin()[0];
120 : }
121 :
122 : reference back() {
123 : return end()[-1];
124 : }
125 : const_reference back() const {
126 : return end()[-1];
127 : }
128 :
129 : void pop_back() {
130 : --End;
131 : End->~T();
132 : }
133 :
134 : T pop_back_val() {
135 : T Result = back();
136 : pop_back();
137 : return Result;
138 : }
139 :
140 : void clear() {
141 : if (std::is_class<T>::value) {
142 : destroy_range(Begin, End);
143 : }
144 : End = Begin;
145 : }
146 :
147 : /// data - Return a pointer to the vector's buffer, even if empty().
148 : pointer data() {
149 : return pointer(Begin);
150 : }
151 :
152 : /// data - Return a pointer to the vector's buffer, even if empty().
153 : const_pointer data() const {
154 : return const_pointer(Begin);
155 : }
156 :
157 : void push_back(const_reference Elt, const ASTContext &C) {
158 : if (End < this->capacity_ptr()) {
159 : Retry:
160 : new (End) T(Elt);
161 : ++End;
162 : return;
163 : }
164 : grow(C);
165 : goto Retry;
166 : }
167 :
168 : void reserve(const ASTContext &C, unsigned N) {
169 : if (unsigned(this->capacity_ptr()-Begin) < N)
170 : grow(C, N);
171 : }
172 :
173 : /// capacity - Return the total number of elements in the currently allocated
174 : /// buffer.
175 : size_t capacity() const { return this->capacity_ptr() - Begin; }
176 :
177 : /// append - Add the specified range to the end of the SmallVector.
178 : ///
179 : template<typename in_iter>
180 : void append(const ASTContext &C, in_iter in_start, in_iter in_end) {
181 : size_type NumInputs = std::distance(in_start, in_end);
182 :
183 : if (NumInputs == 0)
184 : return;
185 :
186 : // Grow allocated space if needed.
187 : if (NumInputs > size_type(this->capacity_ptr()-this->end()))
188 : this->grow(C, this->size()+NumInputs);
189 :
190 : // Copy the new elements over.
191 : // TODO: NEED To compile time dispatch on whether in_iter is a random access
192 : // iterator to use the fast uninitialized_copy.
193 : std::uninitialized_copy(in_start, in_end, this->end());
194 : this->setEnd(this->end() + NumInputs);
195 : }
196 :
197 : /// append - Add the specified range to the end of the SmallVector.
198 : ///
199 : void append(const ASTContext &C, size_type NumInputs, const T &Elt) {
200 : // Grow allocated space if needed.
201 : if (NumInputs > size_type(this->capacity_ptr()-this->end()))
202 : this->grow(C, this->size()+NumInputs);
203 :
204 : // Copy the new elements over.
205 : std::uninitialized_fill_n(this->end(), NumInputs, Elt);
206 : this->setEnd(this->end() + NumInputs);
207 : }
208 :
209 : /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
210 : /// starting with "Dest", constructing elements into it as needed.
211 : template<typename It1, typename It2>
212 : static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
213 : std::uninitialized_copy(I, E, Dest);
214 : }
215 :
216 : iterator insert(const ASTContext &C, iterator I, const T &Elt) {
217 : if (I == this->end()) { // Important special case for empty vector.
218 : push_back(Elt, C);
219 : return this->end()-1;
220 : }
221 :
222 : if (this->End < this->capacity_ptr()) {
223 : Retry:
224 : new (this->end()) T(this->back());
225 : this->setEnd(this->end()+1);
226 : // Push everything else over.
227 : std::copy_backward(I, this->end()-1, this->end());
228 : *I = Elt;
229 : return I;
230 : }
231 : size_t EltNo = I-this->begin();
232 : this->grow(C);
233 : I = this->begin()+EltNo;
234 : goto Retry;
235 : }
236 :
237 : iterator insert(const ASTContext &C, iterator I, size_type NumToInsert,
238 : const T &Elt) {
239 : // Convert iterator to elt# to avoid invalidating iterator when we reserve()
240 : size_t InsertElt = I - this->begin();
241 :
242 : if (I == this->end()) { // Important special case for empty vector.
243 : append(C, NumToInsert, Elt);
244 : return this->begin() + InsertElt;
245 : }
246 :
247 : // Ensure there is enough space.
248 : reserve(C, static_cast<unsigned>(this->size() + NumToInsert));
249 :
250 : // Uninvalidate the iterator.
251 : I = this->begin()+InsertElt;
252 :
253 : // If there are more elements between the insertion point and the end of the
254 : // range than there are being inserted, we can use a simple approach to
255 : // insertion. Since we already reserved space, we know that this won't
256 : // reallocate the vector.
257 : if (size_t(this->end()-I) >= NumToInsert) {
258 : T *OldEnd = this->end();
259 : append(C, this->end()-NumToInsert, this->end());
260 :
261 : // Copy the existing elements that get replaced.
262 : std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
263 :
264 : std::fill_n(I, NumToInsert, Elt);
265 : return I;
266 : }
267 :
268 : // Otherwise, we're inserting more elements than exist already, and we're
269 : // not inserting at the end.
270 :
271 : // Copy over the elements that we're about to overwrite.
272 : T *OldEnd = this->end();
273 : this->setEnd(this->end() + NumToInsert);
274 : size_t NumOverwritten = OldEnd-I;
275 : this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
276 :
277 : // Replace the overwritten part.
278 : std::fill_n(I, NumOverwritten, Elt);
279 :
280 : // Insert the non-overwritten middle part.
281 : std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
282 : return I;
283 : }
284 :
285 : template<typename ItTy>
286 : iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) {
287 : // Convert iterator to elt# to avoid invalidating iterator when we reserve()
288 : size_t InsertElt = I - this->begin();
289 :
290 : if (I == this->end()) { // Important special case for empty vector.
291 : append(C, From, To);
292 : return this->begin() + InsertElt;
293 : }
294 :
295 : size_t NumToInsert = std::distance(From, To);
296 :
297 : // Ensure there is enough space.
298 : reserve(C, static_cast<unsigned>(this->size() + NumToInsert));
299 :
300 : // Uninvalidate the iterator.
301 : I = this->begin()+InsertElt;
302 :
303 : // If there are more elements between the insertion point and the end of the
304 : // range than there are being inserted, we can use a simple approach to
305 : // insertion. Since we already reserved space, we know that this won't
306 : // reallocate the vector.
307 : if (size_t(this->end()-I) >= NumToInsert) {
308 : T *OldEnd = this->end();
309 : append(C, this->end()-NumToInsert, this->end());
310 :
311 : // Copy the existing elements that get replaced.
312 : std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
313 :
314 : std::copy(From, To, I);
315 : return I;
316 : }
317 :
318 : // Otherwise, we're inserting more elements than exist already, and we're
319 : // not inserting at the end.
320 :
321 : // Copy over the elements that we're about to overwrite.
322 : T *OldEnd = this->end();
323 : this->setEnd(this->end() + NumToInsert);
324 : size_t NumOverwritten = OldEnd-I;
325 : this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
326 :
327 : // Replace the overwritten part.
328 : for (; NumOverwritten > 0; --NumOverwritten) {
329 : *I = *From;
330 : ++I; ++From;
331 : }
332 :
333 : // Insert the non-overwritten middle part.
334 : this->uninitialized_copy(From, To, OldEnd);
335 : return I;
336 : }
337 :
338 : void resize(const ASTContext &C, unsigned N, const T &NV) {
339 : if (N < this->size()) {
340 : this->destroy_range(this->begin()+N, this->end());
341 : this->setEnd(this->begin()+N);
342 : } else if (N > this->size()) {
343 : if (this->capacity() < N)
344 : this->grow(C, N);
345 : construct_range(this->end(), this->begin()+N, NV);
346 : this->setEnd(this->begin()+N);
347 : }
348 : }
349 :
350 : private:
351 : /// grow - double the size of the allocated memory, guaranteeing space for at
352 : /// least one more element or MinSize if specified.
353 : void grow(const ASTContext &C, size_type MinSize = 1);
354 :
355 : void construct_range(T *S, T *E, const T &Elt) {
356 : for (; S != E; ++S)
357 : new (S) T(Elt);
358 : }
359 :
360 : void destroy_range(T *S, T *E) {
361 : while (S != E) {
362 : --E;
363 : E->~T();
364 : }
365 : }
366 :
367 : protected:
368 : const_iterator capacity_ptr() const {
369 : return (iterator) Capacity.getPointer();
370 : }
371 : iterator capacity_ptr() { return (iterator)Capacity.getPointer(); }
372 : };
373 :
374 : // Define this out-of-line to dissuade the C++ compiler from inlining it.
375 : template <typename T>
376 : void ASTVector<T>::grow(const ASTContext &C, size_t MinSize) {
377 : size_t CurCapacity = this->capacity();
378 : size_t CurSize = size();
379 : size_t NewCapacity = 2*CurCapacity;
380 : if (NewCapacity < MinSize)
381 : NewCapacity = MinSize;
382 :
383 : // Allocate the memory from the ASTContext.
384 : T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity];
385 :
386 : // Copy the elements over.
387 : if (Begin != End) {
388 : if (std::is_class<T>::value) {
389 : std::uninitialized_copy(Begin, End, NewElts);
390 : // Destroy the original elements.
391 : destroy_range(Begin, End);
392 : } else {
393 : // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
394 : memcpy(NewElts, Begin, CurSize * sizeof(T));
395 : }
396 : }
397 :
398 : // ASTContext never frees any memory.
399 : Begin = NewElts;
400 : End = NewElts+CurSize;
401 : Capacity.setPointer(Begin+NewCapacity);
402 : }
403 :
404 : } // end: clang namespace
405 : #endif
|
