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