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 "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     if (I == this->end()) {  // Important special case for empty vector.
 240       append(C, NumToInsert, Elt);
 241       return this->end()-1;
 242     }
 243
 244     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 245     size_t InsertElt = I - this->begin();
 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     if (I == this->end()) {  // Important special case for empty vector.
 288       append(C, From, To);
 289       return this->end()-1;
 290     }
 291
 292     size_t NumToInsert = std::distance(From, To);
 293     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 294     size_t InsertElt = I - this->begin();
 295
 296     // Ensure there is enough space.
 297     reserve(C, static_cast<unsigned>(this->size() + NumToInsert));
 298
 299     // Uninvalidate the iterator.
 300     I = this->begin()+InsertElt;
 301
 302     // If there are more elements between the insertion point and the end of the
 303     // range than there are being inserted, we can use a simple approach to
 304     // insertion.  Since we already reserved space, we know that this won't
 305     // reallocate the vector.
 306     if (size_t(this->end()-I) >= NumToInsert) {
 307       T *OldEnd = this->end();
 308       append(C, this->end()-NumToInsert, this->end());
 309
 310       // Copy the existing elements that get replaced.
 311       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
 312
 313       std::copy(From, To, I);
 314       return I;
 315     }
 316
 317     // Otherwise, we're inserting more elements than exist already, and we're
 318     // not inserting at the end.
 319
 320     // Copy over the elements that we're about to overwrite.
 321     T *OldEnd = this->end();
 322     this->setEnd(this->end() + NumToInsert);
 323     size_t NumOverwritten = OldEnd-I;
 324     this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
 325
 326     // Replace the overwritten part.
 327     for (; NumOverwritten > 0; --NumOverwritten) {
 328       *I = *From;
 329       ++I; ++From;
 330     }
 331
 332     // Insert the non-overwritten middle part.
 333     this->uninitialized_copy(From, To, OldEnd);
 334     return I;
 335   }
 336
 337   void resize(const ASTContext &C, unsigned N, const T &NV) {
 338     if (N < this->size()) {
 339       this->destroy_range(this->begin()+N, this->end());
 340       this->setEnd(this->begin()+N);
 341     } else if (N > this->size()) {
 342       if (this->capacity() < N)
 343         this->grow(C, N);
 344       construct_range(this->end(), this->begin()+N, NV);
 345       this->setEnd(this->begin()+N);
 346     }
 347   }
 348
 349 private:
 350   /// grow - double the size of the allocated memory, guaranteeing space for at
 351   /// least one more element or MinSize if specified.
 352   void grow(const ASTContext &C, size_type MinSize = 1);
 353
 354   void construct_range(T *S, T *E, const T &Elt) {
 355     for (; S != E; ++S)
 356       new (S) T(Elt);
 357   }
 358
 359   void destroy_range(T *S, T *E) {
 360     while (S != E) {
 361       --E;
 362       E->~T();
 363     }
 364   }
 365
 366 protected:
 367   const_iterator capacity_ptr() const {
 368     return (iterator) Capacity.getPointer();
 369   }
 370   iterator capacity_ptr() { return (iterator)Capacity.getPointer(); }
 371 };
 372
 373 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 374 template <typename T>
 375 void ASTVector<T>::grow(const ASTContext &C, size_t MinSize) {
 376   size_t CurCapacity = this->capacity();
 377   size_t CurSize = size();
 378   size_t NewCapacity = 2*CurCapacity;
 379   if (NewCapacity < MinSize)
 380     NewCapacity = MinSize;
 381
 382   // Allocate the memory from the ASTContext.
 383   T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity];
 384
 385   // Copy the elements over.
 386   if (std::is_class<T>::value) {
 387     std::uninitialized_copy(Begin, End, NewElts);
 388     // Destroy the original elements.
 389     destroy_range(Begin, End);
 390   }
 391   else {
 392     // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
 393     memcpy(NewElts, Begin, CurSize * sizeof(T));
 394   }
 395
 396   // ASTContext never frees any memory.
 397   Begin = NewElts;
 398   End = NewElts+CurSize;
 399   Capacity.setPointer(Begin+NewCapacity);
 400 }
 401
 402 } // end: clang namespace
 403 #endif