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