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