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/type_traits.h"
  24 #include <algorithm>
  25 #include <cstring>
  26 #include <memory>
  27
  28 namespace clang {
  29   class ASTContext;
  30
  31 template<typename T>
  32 class ASTVector {
  33 private:
  34   T *Begin, *End;
  35   llvm::PointerIntPair<T*, 1, bool> Capacity;
  36
  37   void setEnd(T *P) { this->End = P; }
  38
  39 protected:
  40   // Make a tag bit available to users of this class.
  41   // FIXME: This is a horrible hack.
  42   bool getTag() const { return Capacity.getInt(); }
  43   void setTag(bool B) { Capacity.setInt(B); }
  44
  45 public:
  46   // Default ctor - Initialize to empty.
  47   ASTVector() : Begin(nullptr), End(nullptr), Capacity(nullptr, false) {}
  48
  49   ASTVector(ASTVector &&O) : Begin(O.Begin), End(O.End), Capacity(O.Capacity) {
  50     O.Begin = O.End = nullptr;
  51     O.Capacity.setPointer(nullptr);
  52     O.Capacity.setInt(false);
  53   }
  54
  55   ASTVector(const ASTContext &C, unsigned N)
  56       : Begin(nullptr), End(nullptr), Capacity(nullptr, false) {
  57     reserve(C, N);
  58   }
  59
  60   ASTVector &operator=(ASTVector &&RHS) {
  61     ASTVector O(std::move(RHS));
  62     using std::swap;
  63     swap(Begin, O.Begin);
  64     swap(End, O.End);
  65     swap(Capacity, O.Capacity);
  66     return *this;
  67   }
  68
  69   ~ASTVector() {
  70     if (std::is_class<T>::value) {
  71       // Destroy the constructed elements in the vector.
  72       destroy_range(Begin, End);
  73     }
  74   }
  75
  76   typedef size_t size_type;
  77   typedef ptrdiff_t difference_type;
  78   typedef T value_type;
  79   typedef T* iterator;
  80   typedef const T* const_iterator;
  81
  82   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  83   typedef std::reverse_iterator<iterator>  reverse_iterator;
  84
  85   typedef T& reference;
  86   typedef const T& const_reference;
  87   typedef T* pointer;
  88   typedef const T* const_pointer;
  89
  90   // forward iterator creation methods.
  91   iterator begin() { return Begin; }
  92   const_iterator begin() const { return Begin; }
  93   iterator end() { return End; }
  94   const_iterator end() const { return End; }
  95
  96   // reverse iterator creation methods.
  97   reverse_iterator rbegin()            { return reverse_iterator(end()); }
  98   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
  99   reverse_iterator rend()              { return reverse_iterator(begin()); }
 100   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
 101
 102   bool empty() const { return Begin == End; }
 103   size_type size() const { return End-Begin; }
 104
 105   reference operator[](unsigned idx) {
 106     assert(Begin + idx < End);
 107     return Begin[idx];
 108   }
 109   const_reference operator[](unsigned idx) const {
 110     assert(Begin + idx < End);
 111     return Begin[idx];
 112   }
 113
 114   reference front() {
 115     return begin()[0];
 116   }
 117   const_reference front() const {
 118     return begin()[0];
 119   }
 120
 121   reference back() {
 122     return end()[-1];
 123   }
 124   const_reference back() const {
 125     return end()[-1];
 126   }
 127
 128   void pop_back() {
 129     --End;
 130     End->~T();
 131   }
 132
 133   T pop_back_val() {
 134     T Result = back();
 135     pop_back();
 136     return Result;
 137   }
 138
 139   void clear() {
 140     if (std::is_class<T>::value) {
 141       destroy_range(Begin, End);
 142     }
 143     End = Begin;
 144   }
 145
 146   /// data - Return a pointer to the vector's buffer, even if empty().
 147   pointer data() {
 148     return pointer(Begin);
 149   }
 150
 151   /// data - Return a pointer to the vector's buffer, even if empty().
 152   const_pointer data() const {
 153     return const_pointer(Begin);
 154   }
 155
 156   void push_back(const_reference Elt, const ASTContext &C) {
 157     if (End < this->capacity_ptr()) {
 158     Retry:
 159       new (End) T(Elt);
 160       ++End;
 161       return;
 162     }
 163     grow(C);
 164     goto Retry;
 165   }
 166
 167   void reserve(const ASTContext &C, unsigned N) {
 168     if (unsigned(this->capacity_ptr()-Begin) < N)
 169       grow(C, N);
 170   }
 171
 172   /// capacity - Return the total number of elements in the currently allocated
 173   /// buffer.
 174   size_t capacity() const { return this->capacity_ptr() - Begin; }
 175
 176   /// append - Add the specified range to the end of the SmallVector.
 177   ///
 178   template<typename in_iter>
 179   void append(const ASTContext &C, in_iter in_start, in_iter in_end) {
 180     size_type NumInputs = std::distance(in_start, in_end);
 181
 182     if (NumInputs == 0)
 183       return;
 184
 185     // Grow allocated space if needed.
 186     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
 187       this->grow(C, this->size()+NumInputs);
 188
 189     // Copy the new elements over.
 190     // TODO: NEED To compile time dispatch on whether in_iter is a random access
 191     // iterator to use the fast uninitialized_copy.
 192     std::uninitialized_copy(in_start, in_end, this->end());
 193     this->setEnd(this->end() + NumInputs);
 194   }
 195
 196   /// append - Add the specified range to the end of the SmallVector.
 197   ///
 198   void append(const ASTContext &C, size_type NumInputs, const T &Elt) {
 199     // Grow allocated space if needed.
 200     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
 201       this->grow(C, this->size()+NumInputs);
 202
 203     // Copy the new elements over.
 204     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
 205     this->setEnd(this->end() + NumInputs);
 206   }
 207
 208   /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
 209   /// starting with "Dest", constructing elements into it as needed.
 210   template<typename It1, typename It2>
 211   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
 212     std::uninitialized_copy(I, E, Dest);
 213   }
 214
 215   iterator insert(const ASTContext &C, iterator I, const T &Elt) {
 216     if (I == this->end()) {  // Important special case for empty vector.
 217       push_back(Elt, C);
 218       return this->end()-1;
 219     }
 220
 221     if (this->End < this->capacity_ptr()) {
 222     Retry:
 223       new (this->end()) T(this->back());
 224       this->setEnd(this->end()+1);
 225       // Push everything else over.
 226       std::copy_backward(I, this->end()-1, this->end());
 227       *I = Elt;
 228       return I;
 229     }
 230     size_t EltNo = I-this->begin();
 231     this->grow(C);
 232     I = this->begin()+EltNo;
 233     goto Retry;
 234   }
 235
 236   iterator insert(const ASTContext &C, iterator I, size_type NumToInsert,
 237                   const T &Elt) {
 238     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 239     size_t InsertElt = I - this->begin();
 240
 241     if (I == this->end()) { // Important special case for empty vector.
 242       append(C, NumToInsert, Elt);
 243       return this->begin() + InsertElt;
 244     }
 245
 246     // Ensure there is enough space.
 247     reserve(C, static_cast<unsigned>(this->size() + NumToInsert));
 248
 249     // Uninvalidate the iterator.
 250     I = this->begin()+InsertElt;
 251
 252     // If there are more elements between the insertion point and the end of the
 253     // range than there are being inserted, we can use a simple approach to
 254     // insertion.  Since we already reserved space, we know that this won't
 255     // reallocate the vector.
 256     if (size_t(this->end()-I) >= NumToInsert) {
 257       T *OldEnd = this->end();
 258       append(C, this->end()-NumToInsert, this->end());
 259
 260       // Copy the existing elements that get replaced.
 261       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
 262
 263       std::fill_n(I, NumToInsert, Elt);
 264       return I;
 265     }
 266
 267     // Otherwise, we're inserting more elements than exist already, and we're
 268     // not inserting at the end.
 269
 270     // Copy over the elements that we're about to overwrite.
 271     T *OldEnd = this->end();
 272     this->setEnd(this->end() + NumToInsert);
 273     size_t NumOverwritten = OldEnd-I;
 274     this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
 275
 276     // Replace the overwritten part.
 277     std::fill_n(I, NumOverwritten, Elt);
 278
 279     // Insert the non-overwritten middle part.
 280     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
 281     return I;
 282   }
 283
 284   template<typename ItTy>
 285   iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) {
 286     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 287     size_t InsertElt = I - this->begin();
 288
 289     if (I == this->end()) { // Important special case for empty vector.
 290       append(C, From, To);
 291       return this->begin() + InsertElt;
 292     }
 293
 294     size_t NumToInsert = std::distance(From, To);
 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, alignof(T)) T[NewCapacity];
 384
 385   // Copy the elements over.
 386   if (Begin != End) {
 387     if (std::is_class<T>::value) {
 388       std::uninitialized_copy(Begin, End, NewElts);
 389       // Destroy the original elements.
 390       destroy_range(Begin, End);
 391     } else {
 392       // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
 393       memcpy(NewElts, Begin, CurSize * sizeof(T));
 394     }
 395   }
 396
 397   // ASTContext never frees any memory.
 398   Begin = NewElts;
 399   End = NewElts+CurSize;
 400   Capacity.setPointer(Begin+NewCapacity);
 401 }
 402
 403 } // end: clang namespace
 404 #endif