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