contrib/llvm/tools/clang/include/clang/AST/ASTVector.h

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