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 "clang/AST/AttrIterator.h"
22 #include "llvm/ADT/PointerIntPair.h"
23 #include "llvm/Support/type_traits.h"
24 #include <algorithm>
25 #include <cstddef>
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 
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 
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;
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  bool empty() const { return Begin == End; }
104  size_type size() const { return End-Begin; }
105 
106  reference operator[](unsigned idx) {
107  assert(Begin + idx < End);
108  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 
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, 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
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:212
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:180
reverse_iterator rbegin()
Definition: ASTVector.h:98
StringRef P
iterator insert(const ASTContext &C, iterator I, const T &Elt)
Definition: ASTVector.h:216
const_reverse_iterator rbegin() const
Definition: ASTVector.h:99
ptrdiff_t difference_type
Definition: ASTVector.h:78
float __ovld __cnfn distance(float p0, float p1)
Returns the distance between p0 and p1.
const T & const_reference
Definition: ASTVector.h:87
const_iterator capacity_ptr() const
Definition: ASTVector.h:368
size_type size() const
Definition: ASTVector.h:104
const_iterator end() const
Definition: ASTVector.h:95
std::reverse_iterator< iterator > reverse_iterator
Definition: ASTVector.h:84
size_t capacity() const
capacity - Return the total number of elements in the currently allocated buffer. ...
Definition: ASTVector.h:175
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:128
bool empty() const
Definition: ASTVector.h:103
bool getTag() const
Definition: ASTVector.h:43
const T * const_pointer
Definition: ASTVector.h:89
void setTag(bool B)
Definition: ASTVector.h:44
reference back()
Definition: ASTVector.h:122
const_iterator begin() const
Definition: ASTVector.h:93
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: ASTVector.h:83
ASTVector(ASTVector &&O)
Definition: ASTVector.h:50
reference operator[](unsigned idx)
Definition: ASTVector.h:106
iterator end()
Definition: ASTVector.h:94
const FunctionProtoType * T
ASTVector & operator=(ASTVector &&RHS)
Definition: ASTVector.h:61
The result type of a method or function.
reverse_iterator rend()
Definition: ASTVector.h:100
size_t size_type
Definition: ASTVector.h:77
#define false
Definition: stdbool.h:33
ASTVector(const ASTContext &C, unsigned N)
Definition: ASTVector.h:56
pointer data()
data - Return a pointer to the vector&#39;s buffer, even if empty().
Definition: ASTVector.h:148
reference front()
Definition: ASTVector.h:115
iterator capacity_ptr()
Definition: ASTVector.h:371
__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.
const_reverse_iterator rend() const
Definition: ASTVector.h:101
void resize(const ASTContext &C, unsigned N, const T &NV)
Definition: ASTVector.h:338
const_reference front() const
Definition: ASTVector.h:118
const_reference back() const
Definition: ASTVector.h:125
iterator begin()
Definition: ASTVector.h:92
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:199
void reserve(const ASTContext &C, unsigned N)
Definition: ASTVector.h:168
const_pointer data() const
data - Return a pointer to the vector&#39;s buffer, even if empty().
Definition: ASTVector.h:153
void push_back(const_reference Elt, const ASTContext &C)
Definition: ASTVector.h:157
iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To)
Definition: ASTVector.h:286
const_reference operator[](unsigned idx) const
Definition: ASTVector.h:110
const T * const_iterator
Definition: ASTVector.h:81
iterator insert(const ASTContext &C, iterator I, size_type NumToInsert, const T &Elt)
Definition: ASTVector.h:237