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_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   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
 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