contrib/llvm/tools/clang/include/clang/Analysis/Support/BumpVector.h

   1 //===-- BumpVector.h - Vector-like ADT that uses bump 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 BumpVector, a vector-like ADT whose contents are
  11 //  allocated from a BumpPtrAllocator.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 // FIXME: Most of this is copy-and-paste from SmallVector.h.  We can
  16 // refactor this core logic into something common that is shared between
  17 // the two.  The main thing that is different is the allocation strategy.
  18
  19 #ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
  20 #define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
  21
  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 <iterator>
  28 #include <memory>
  29
  30 namespace clang {
  31
  32 class BumpVectorContext {
  33   llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
  34 public:
  35   /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator
  36   /// and destroys it when the BumpVectorContext object is destroyed.
  37   BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {}
  38
  39   BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) {
  40     Other.Alloc.setInt(false);
  41     Other.Alloc.setPointer(nullptr);
  42   }
  43
  44   /// Construct a new BumpVectorContext that reuses an existing
  45   /// BumpPtrAllocator.  This BumpPtrAllocator is not destroyed when the
  46   /// BumpVectorContext object is destroyed.
  47   BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {}
  48
  49   ~BumpVectorContext() {
  50     if (Alloc.getInt())
  51       delete Alloc.getPointer();
  52   }
  53
  54   llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
  55 };
  56
  57 template<typename T>
  58 class BumpVector {
  59   T *Begin, *End, *Capacity;
  60 public:
  61   // Default ctor - Initialize to empty.
  62   explicit BumpVector(BumpVectorContext &C, unsigned N)
  63   : Begin(nullptr), End(nullptr), Capacity(nullptr) {
  64     reserve(C, N);
  65   }
  66
  67   ~BumpVector() {
  68     if (std::is_class<T>::value) {
  69       // Destroy the constructed elements in the vector.
  70       destroy_range(Begin, End);
  71     }
  72   }
  73
  74   typedef size_t size_type;
  75   typedef ptrdiff_t difference_type;
  76   typedef T value_type;
  77   typedef T* iterator;
  78   typedef const T* const_iterator;
  79
  80   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  81   typedef std::reverse_iterator<iterator>  reverse_iterator;
  82
  83   typedef T& reference;
  84   typedef const T& const_reference;
  85   typedef T* pointer;
  86   typedef const T* const_pointer;
  87
  88   // forward iterator creation methods.
  89   iterator begin() { return Begin; }
  90   const_iterator begin() const { return Begin; }
  91   iterator end() { return End; }
  92   const_iterator end() const { return End; }
  93
  94   // reverse iterator creation methods.
  95   reverse_iterator rbegin()            { return reverse_iterator(end()); }
  96   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
  97   reverse_iterator rend()              { return reverse_iterator(begin()); }
  98   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
  99
 100   bool empty() const { return Begin == End; }
 101   size_type size() const { return End-Begin; }
 102
 103   reference operator[](unsigned idx) {
 104     assert(Begin + idx < End);
 105     return Begin[idx];
 106   }
 107   const_reference operator[](unsigned idx) const {
 108     assert(Begin + idx < End);
 109     return Begin[idx];
 110   }
 111
 112   reference front() {
 113     return begin()[0];
 114   }
 115   const_reference front() const {
 116     return begin()[0];
 117   }
 118
 119   reference back() {
 120     return end()[-1];
 121   }
 122   const_reference back() const {
 123     return end()[-1];
 124   }
 125
 126   void pop_back() {
 127     --End;
 128     End->~T();
 129   }
 130
 131   T pop_back_val() {
 132     T Result = back();
 133     pop_back();
 134     return Result;
 135   }
 136
 137   void clear() {
 138     if (std::is_class<T>::value) {
 139       destroy_range(Begin, End);
 140     }
 141     End = Begin;
 142   }
 143
 144   /// data - Return a pointer to the vector's buffer, even if empty().
 145   pointer data() {
 146     return pointer(Begin);
 147   }
 148
 149   /// data - Return a pointer to the vector's buffer, even if empty().
 150   const_pointer data() const {
 151     return const_pointer(Begin);
 152   }
 153
 154   void push_back(const_reference Elt, BumpVectorContext &C) {
 155     if (End < Capacity) {
 156     Retry:
 157       new (End) T(Elt);
 158       ++End;
 159       return;
 160     }
 161     grow(C);
 162     goto Retry;
 163   }
 164
 165   /// insert - Insert some number of copies of element into a position. Return
 166   /// iterator to position after last inserted copy.
 167   iterator insert(iterator I, size_t Cnt, const_reference E,
 168       BumpVectorContext &C) {
 169     assert (I >= Begin && I <= End && "Iterator out of bounds.");
 170     if (End + Cnt <= Capacity) {
 171     Retry:
 172       move_range_right(I, End, Cnt);
 173       construct_range(I, I + Cnt, E);
 174       End += Cnt;
 175       return I + Cnt;
 176     }
 177     ptrdiff_t D = I - Begin;
 178     grow(C, size() + Cnt);
 179     I = Begin + D;
 180     goto Retry;
 181   }
 182
 183   void reserve(BumpVectorContext &C, unsigned N) {
 184     if (unsigned(Capacity-Begin) < N)
 185       grow(C, N);
 186   }
 187
 188   /// capacity - Return the total number of elements in the currently allocated
 189   /// buffer.
 190   size_t capacity() const { return Capacity - Begin; }
 191
 192 private:
 193   /// grow - double the size of the allocated memory, guaranteeing space for at
 194   /// least one more element or MinSize if specified.
 195   void grow(BumpVectorContext &C, size_type MinSize = 1);
 196
 197   void construct_range(T *S, T *E, const T &Elt) {
 198     for (; S != E; ++S)
 199       new (S) T(Elt);
 200   }
 201
 202   void destroy_range(T *S, T *E) {
 203     while (S != E) {
 204       --E;
 205       E->~T();
 206     }
 207   }
 208
 209   void move_range_right(T *S, T *E, size_t D) {
 210     for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) {
 211       --E;
 212       new (I) T(*E);
 213       E->~T();
 214     }
 215   }
 216 };
 217
 218 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 219 template <typename T>
 220 void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) {
 221   size_t CurCapacity = Capacity-Begin;
 222   size_t CurSize = size();
 223   size_t NewCapacity = 2*CurCapacity;
 224   if (NewCapacity < MinSize)
 225     NewCapacity = MinSize;
 226
 227   // Allocate the memory from the BumpPtrAllocator.
 228   T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
 229
 230   // Copy the elements over.
 231   if (Begin != End) {
 232     if (std::is_class<T>::value) {
 233       std::uninitialized_copy(Begin, End, NewElts);
 234       // Destroy the original elements.
 235       destroy_range(Begin, End);
 236     } else {
 237       // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
 238       memcpy(NewElts, Begin, CurSize * sizeof(T));
 239     }
 240   }
 241
 242   // For now, leak 'Begin'.  We can add it back to a freelist in
 243   // BumpVectorContext.
 244   Begin = NewElts;
 245   End = NewElts+CurSize;
 246   Capacity = Begin+NewCapacity;
 247 }
 248
 249 } // end: clang namespace
 250 #endif