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 <algorithm>
  18 #include <iterator>
  19 #include <memory>
  20
  21 namespace llvm {
  22
  23 /// SmallVectorImpl - This class consists of common code factored out of the
  24 /// SmallVector class to reduce code duplication based on the SmallVector 'N'
  25 /// template parameter.
  26 template <typename T>
  27 class SmallVectorImpl {
  28   T *Begin, *End, *Capacity;
  29
  30   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
  31   // don't want it to be automatically run, so we need to represent the space as
  32   // something else.  An array of char would work great, but might not be
  33   // aligned sufficiently.  Instead, we either use GCC extensions, or some
  34   // number of union instances for the space, which guarantee maximal alignment.
  35 protected:
  36 #ifdef __GNUC__
  37   typedef char U;
  38   U FirstEl __attribute__((aligned(__alignof__(double))));
  39 #else
  40   union U {
  41     double D;
  42     long double LD;
  43     long long L;
  44     void *P;
  45   } FirstEl;
  46 #endif
  47   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
  48 public:
  49   // Default ctor - Initialize to empty.
  50   SmallVectorImpl(unsigned N)
  51     : Begin((T*)&FirstEl), End((T*)&FirstEl), Capacity((T*)&FirstEl+N) {
  52   }
  53
  54   ~SmallVectorImpl() {
  55     // Destroy the constructed elements in the vector.
  56     destroy_range(Begin, End);
  57
  58     // If this wasn't grown from the inline copy, deallocate the old space.
  59     if (!isSmall())
  60       delete[] (char*)Begin;
  61   }
  62
  63   typedef size_t size_type;
  64   typedef T* iterator;
  65   typedef const T* const_iterator;
  66   typedef T& reference;
  67   typedef const T& const_reference;
  68
  69   bool empty() const { return Begin == End; }
  70   size_type size() const { return End-Begin; }
  71
  72   iterator begin() { return Begin; }
  73   const_iterator begin() const { return Begin; }
  74
  75   iterator end() { return End; }
  76   const_iterator end() const { return End; }
  77
  78   reference operator[](unsigned idx) {
  79     return Begin[idx];
  80   }
  81   const_reference operator[](unsigned idx) const {
  82     return Begin[idx];
  83   }
  84
  85   reference front() {
  86     return begin()[0];
  87   }
  88   const_reference front() const {
  89     return begin()[0];
  90   }
  91
  92   reference back() {
  93     return end()[-1];
  94   }
  95   const_reference back() const {
  96     return end()[-1];
  97   }
  98
  99   void push_back(const_reference Elt) {
 100     if (End < Capacity) {
 101   Retry:
 102       new (End) T(Elt);
 103       ++End;
 104       return;
 105     }
 106     grow();
 107     goto Retry;
 108   }
 109
 110   void pop_back() {
 111     --End;
 112     End->~T();
 113   }
 114
 115   void clear() {
 116     destroy_range(Begin, End);
 117     End = Begin;
 118   }
 119
 120   void resize(unsigned N) {
 121     if (N < size()) {
 122       destroy_range(Begin+N, End);
 123       End = Begin+N;
 124     } else if (N > size()) {
 125       if (Begin+N > Capacity)
 126         grow(N);
 127       construct_range(End, Begin+N, T());
 128       End = Begin+N;
 129     }
 130   }
 131
 132   void resize(unsigned N, const T &NV) {
 133     if (N < size()) {
 134       destroy_range(Begin+N, End);
 135       End = Begin+N;
 136     } else if (N > size()) {
 137       if (Begin+N > Capacity)
 138         grow(N);
 139       construct_range(End, Begin+N, NV);
 140       End = Begin+N;
 141     }
 142   }
 143
 144   void reserve(unsigned N) {
 145     if (unsigned(Capacity-Begin) < N)
 146       grow(N);
 147   }
 148
 149   void swap(SmallVectorImpl &RHS);
 150
 151   /// append - Add the specified range to the end of the SmallVector.
 152   ///
 153   template<typename in_iter>
 154   void append(in_iter in_start, in_iter in_end) {
 155     unsigned NumInputs = std::distance(in_start, in_end);
 156     // Grow allocated space if needed.
 157     if (End+NumInputs > Capacity)
 158       grow(size()+NumInputs);
 159
 160     // Copy the new elements over.
 161     std::uninitialized_copy(in_start, in_end, End);
 162     End += NumInputs;
 163   }
 164
 165   void assign(unsigned NumElts, const T &Elt) {
 166     clear();
 167     if (Begin+NumElts > Capacity)
 168       grow(NumElts);
 169     End = Begin+NumElts;
 170     construct_range(Begin, End, Elt);
 171   }
 172
 173   void erase(iterator I) {
 174     // Shift all elts down one.
 175     std::copy(I+1, End, I);
 176     // Drop the last elt.
 177     pop_back();
 178   }
 179
 180   void erase(iterator S, iterator E) {
 181     // Shift all elts down.
 182     iterator I = std::copy(E, End, S);
 183     // Drop the last elts.
 184     destroy_range(I, End);
 185     End = I;
 186   }
 187
 188   iterator insert(iterator I, const T &Elt) {
 189     if (I == End) {  // Important special case for empty vector.
 190       push_back(Elt);
 191       return end()-1;
 192     }
 193
 194     if (End < Capacity) {
 195   Retry:
 196       new (End) T(back());
 197       ++End;
 198       // Push everything else over.
 199       std::copy_backward(I, End-1, End);
 200       *I = Elt;
 201       return I;
 202     }
 203     unsigned EltNo = I-Begin;
 204     grow();
 205     I = Begin+EltNo;
 206     goto Retry;
 207   }
 208
 209   const SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
 210
 211 private:
 212   /// isSmall - Return true if this is a smallvector which has not had dynamic
 213   /// memory allocated for it.
 214   bool isSmall() const {
 215     return (void*)Begin == (void*)&FirstEl;
 216   }
 217
 218   /// grow - double the size of the allocated memory, guaranteeing space for at
 219   /// least one more element or MinSize if specified.
 220   void grow(unsigned MinSize = 0);
 221
 222   void construct_range(T *S, T *E, const T &Elt) {
 223     for (; S != E; ++S)
 224       new (S) T(Elt);
 225   }
 226
 227
 228   void destroy_range(T *S, T *E) {
 229     while (S != E) {
 230       E->~T();
 231       --E;
 232     }
 233   }
 234 };
 235
 236 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 237 template <typename T>
 238 void SmallVectorImpl<T>::grow(unsigned MinSize) {
 239   unsigned CurCapacity = Capacity-Begin;
 240   unsigned CurSize = size();
 241   unsigned NewCapacity = 2*CurCapacity;
 242   if (NewCapacity < MinSize)
 243     NewCapacity = MinSize;
 244   T *NewElts = reinterpret_cast<T*>(new char[NewCapacity*sizeof(T)]);
 245
 246   // Copy the elements over.
 247   std::uninitialized_copy(Begin, End, NewElts);
 248
 249   // Destroy the original elements.
 250   destroy_range(Begin, End);
 251
 252   // If this wasn't grown from the inline copy, deallocate the old space.
 253   if (!isSmall())
 254     delete[] (char*)Begin;
 255
 256   Begin = NewElts;
 257   End = NewElts+CurSize;
 258   Capacity = Begin+NewCapacity;
 259 }
 260
 261 template <typename T>
 262 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
 263   if (this == &RHS) return;
 264
 265   // We can only avoid copying elements if neither vector is small.
 266   if (!isSmall() && !RHS.isSmall()) {
 267     std::swap(Begin, RHS.Begin);
 268     std::swap(End, RHS.End);
 269     std::swap(Capacity, RHS.Capacity);
 270     return;
 271   }
 272   if (Begin+RHS.size() > Capacity)
 273     grow(RHS.size());
 274   if (RHS.begin()+size() > RHS.Capacity)
 275     RHS.grow(size());
 276
 277   // Swap the shared elements.
 278   unsigned NumShared = size();
 279   if (NumShared > RHS.size()) NumShared = RHS.size();
 280   for (unsigned i = 0; i != NumShared; ++i)
 281     std::swap(Begin[i], RHS[i]);
 282
 283   // Copy over the extra elts.
 284   if (size() > RHS.size()) {
 285     unsigned EltDiff = size() - RHS.size();
 286     std::uninitialized_copy(Begin+NumShared, End, RHS.End);
 287     RHS.End += EltDiff;
 288     destroy_range(Begin+NumShared, End);
 289     End = Begin+NumShared;
 290   } else if (RHS.size() > size()) {
 291     unsigned EltDiff = RHS.size() - size();
 292     std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End);
 293     End += EltDiff;
 294     destroy_range(RHS.Begin+NumShared, RHS.End);
 295     RHS.End = RHS.Begin+NumShared;
 296   }
 297 }
 298
 299 template <typename T>
 300 const SmallVectorImpl<T> &
 301 SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) {
 302   // Avoid self-assignment.
 303   if (this == &RHS) return *this;
 304
 305   // If we already have sufficient space, assign the common elements, then
 306   // destroy any excess.
 307   unsigned RHSSize = RHS.size();
 308   unsigned CurSize = size();
 309   if (CurSize >= RHSSize) {
 310     // Assign common elements.
 311     iterator NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
 312
 313     // Destroy excess elements.
 314     destroy_range(NewEnd, End);
 315
 316     // Trim.
 317     End = NewEnd;
 318     return *this;
 319   }
 320
 321   // If we have to grow to have enough elements, destroy the current elements.
 322   // This allows us to avoid copying them during the grow.
 323   if (unsigned(Capacity-Begin) < RHSSize) {
 324     // Destroy current elements.
 325     destroy_range(Begin, End);
 326     End = Begin;
 327     CurSize = 0;
 328     grow(RHSSize);
 329   } else if (CurSize) {
 330     // Otherwise, use assignment for the already-constructed elements.
 331     std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
 332   }
 333
 334   // Copy construct the new elements in place.
 335   std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
 336
 337   // Set end.
 338   End = Begin+RHSSize;
 339   return *this;
 340 }
 341
 342 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
 343 /// for the case when the array is small.  It contains some number of elements
 344 /// in-place, which allows it to avoid heap allocation when the actual number of
 345 /// elements is below that threshold.  This allows normal "small" cases to be
 346 /// fast without losing generality for large inputs.
 347 ///
 348 /// Note that this does not attempt to be exception safe.
 349 ///
 350 template <typename T, unsigned N>
 351 class SmallVector : public SmallVectorImpl<T> {
 352   /// InlineElts - These are 'N-1' elements that are stored inline in the body
 353   /// of the vector.  The extra '1' element is stored in SmallVectorImpl.
 354   typedef typename SmallVectorImpl<T>::U U;
 355   enum {
 356     // MinUs - The number of U's require to cover N T's.
 357     MinUs = (sizeof(T)*N+sizeof(U)-1)/sizeof(U),
 358
 359     // NumInlineEltsElts - The number of elements actually in this array.  There
 360     // is already one in the parent class, and we have to round up to avoid
 361     // having a zero-element array.
 362     NumInlineEltsElts = (MinUs - 1) > 0 ? (MinUs - 1) : 1,
 363
 364     // NumTsAvailable - The number of T's we actually have space for, which may
 365     // be more than N due to rounding.
 366     NumTsAvailable = (NumInlineEltsElts+1)*sizeof(U) / sizeof(T)
 367   };
 368   U InlineElts[NumInlineEltsElts];
 369 public:
 370   SmallVector() : SmallVectorImpl<T>(NumTsAvailable) {
 371   }
 372
 373   template<typename ItTy>
 374   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) {
 375     append(S, E);
 376   }
 377
 378   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) {
 379     operator=(RHS);
 380   }
 381
 382   const SmallVector &operator=(const SmallVector &RHS) {
 383     SmallVectorImpl<T>::operator=(RHS);
 384     return *this;
 385   }
 386 };
 387
 388 } // End llvm namespace
 389
 390 namespace std {
 391   /// Implement std::swap in terms of SmallVector swap.
 392   template<typename T>
 393   inline void
 394   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
 395     LHS.swap(RHS);
 396   }
 397
 398   /// Implement std::swap in terms of SmallVector swap.
 399   template<typename T, unsigned N>
 400   inline void
 401   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
 402     LHS.swap(RHS);
 403   }
 404 }
 405
 406 #endif