include/llvm/ADT/SmallVector.h

   1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the SmallVector class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SMALLVECTOR_H
  15 #define LLVM_ADT_SMALLVECTOR_H
  16
  17 #include <cassert>
  18 #include <memory>
  19
  20 namespace llvm {
  21
  22 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
  23 /// for the case when the array is small.  It contains some number of elements
  24 /// in-place, which allows it to avoid heap allocation when the actual number of
  25 /// elements is below that threshold.  This allows normal "small" cases to be
  26 /// fast without losing generality for large inputs.
  27 ///
  28 /// Note that this does not attempt to be exception safe.
  29 ///
  30 template <typename T, unsigned N>
  31 class SmallVector {
  32   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
  33   // don't want it to be automatically run, so we need to represent the space as
  34   // something else.  An array of char would work great, but might not be
  35   // aligned sufficiently.  Instead, we either use GCC extensions, or some
  36   // number of union instances for the space, which guarantee maximal alignment.
  37   union U {
  38     double D;
  39     long double LD;
  40     long long L;
  41     void *P;
  42   };
  43
  44   /// InlineElts - These are the 'N' elements that are stored inline in the body
  45   /// of the vector
  46   U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U)];
  47   T *Begin, *End, *Capacity;
  48 public:
  49   // Default ctor - Initialize to empty.
  50   SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) {
  51   }
  52
  53   SmallVector(const SmallVector &RHS) {
  54     unsigned RHSSize = RHS.size();
  55     Begin = (T*)InlineElts;
  56
  57     // Doesn't fit in the small case?  Allocate space.
  58     if (RHSSize > N) {
  59       End = Capacity = Begin;
  60       grow(RHSSize);
  61     }
  62     End = Begin+RHSSize;
  63     Capacity = Begin+N;
  64     std::uninitialized_copy(RHS.begin(), RHS.end(), Begin);
  65   }
  66   ~SmallVector() {
  67     // If this wasn't grown from the inline copy, deallocate the old space.
  68     if ((void*)Begin != (void*)InlineElts)
  69       delete[] (char*)Begin;
  70   }
  71
  72   typedef size_t size_type;
  73   typedef T* iterator;
  74   typedef const T* const_iterator;
  75   typedef T& reference;
  76   typedef const T& const_reference;
  77
  78   bool empty() const { return Begin == End; }
  79   size_type size() const { return End-Begin; }
  80
  81   iterator begin() { return Begin; }
  82   const_iterator begin() const { return Begin; }
  83
  84   iterator end() { return End; }
  85   const_iterator end() const { return End; }
  86
  87   reference operator[](unsigned idx) {
  88     assert(idx < size() && "out of range reference!");
  89     return Begin[idx];
  90   }
  91   const_reference operator[](unsigned idx) const {
  92     assert(idx < size() && "out of range reference!");
  93     return Begin[idx];
  94   }
  95
  96   reference back() {
  97     assert(!empty() && "SmallVector is empty!");
  98     return end()[-1];
  99   }
 100   const_reference back() const {
 101     assert(!empty() && "SmallVector is empty!");
 102     return end()[-1];
 103   }
 104
 105   void push_back(const_reference Elt) {
 106     if (End < Capacity) {
 107   Retry:
 108       new (End) T(Elt);
 109       ++End;
 110       return;
 111     }
 112     grow();
 113     goto Retry;
 114   }
 115
 116   const SmallVector &operator=(const SmallVector &RHS) {
 117     // Avoid self-assignment.
 118     if (this == &RHS) return *this;
 119
 120     // If we already have sufficient space, assign the common elements, then
 121     // destroy any excess.
 122     unsigned RHSSize = RHS.size();
 123     unsigned CurSize = size();
 124     if (CurSize >= RHSSize) {
 125       // Assign common elements.
 126       for (unsigned i = 0; i != RHSSize; ++i)
 127         Begin[i] = RHS.Begin[i];
 128
 129       // Destroy excess elements.
 130       for (unsigned i = RHSSize; i != CurSize; ++i)
 131         Begin[i].~T();
 132
 133       // Trim.
 134       End = Begin + RHSSize;
 135       return *this;
 136     }
 137
 138     // If we have to grow to have enough elements, destroy the current elements.
 139     // This allows us to avoid copying them during the grow.
 140     if (Capacity-Begin < RHSSize) {
 141       // Destroy current elements.
 142       for (T *I = Begin, E = End; I != E; ++I)
 143         I->~T();
 144       End = Begin;
 145       CurSize = 0;
 146       grow(RHSSize);
 147     } else {
 148       // Otherwise, use assignment for the already-constructed elements.
 149       for (unsigned i = 0; i != CurSize; ++i)
 150         Begin[i] = RHS.Begin[i];
 151     }
 152
 153     // Copy construct the new elements in place.
 154     std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
 155
 156     // Set end.
 157     End = Begin+RHSSize;
 158   }
 159
 160 private:
 161   /// isSmall - Return true if this is a smallvector which has not had dynamic
 162   /// memory allocated for it.
 163   bool isSmall() const {
 164     return (void*)Begin == (void*)InlineElts;
 165   }
 166
 167   /// grow - double the size of the allocated memory, guaranteeing space for at
 168   /// least one more element or MinSize if specified.
 169   void grow(unsigned MinSize = 0) {
 170     unsigned CurCapacity = Capacity-Begin;
 171     unsigned CurSize = size();
 172     unsigned NewCapacity = 2*CurCapacity;
 173     if (NewCapacity < MinSize)
 174       NewCapacity = MinSize;
 175     T *NewElts = reinterpret_cast<T*>(new char[NewCapacity*sizeof(T)]);
 176
 177     // Copy the elements over.
 178     std::uninitialized_copy(Begin, End, NewElts);
 179
 180     // Destroy the original elements.
 181     for (T *I = Begin, *E = End; I != E; ++I)
 182       I->~T();
 183
 184     // If this wasn't grown from the inline copy, deallocate the old space.
 185     if (!isSmall())
 186       delete[] (char*)Begin;
 187
 188     Begin = NewElts;
 189     End = NewElts+CurSize;
 190     Capacity = Begin+NewCapacity*2;
 191   }
 192 };
 193
 194 } // End llvm namespace
 195
 196 #endif