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