include/llvm/ADT/SmallVector.h

   1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- 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 defines the SmallVector class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SMALLVECTOR_H
  15 #define LLVM_ADT_SMALLVECTOR_H
  16
  17 #include "llvm/ADT/iterator.h"
  18 #include "llvm/Support/type_traits.h"
  19 #include <algorithm>
  20 #include <cassert>
  21 #include <cstring>
  22 #include <memory>
  23
  24 #ifdef _MSC_VER
  25 namespace std {
  26 #if _MSC_VER <= 1310
  27   // Work around flawed VC++ implementation of std::uninitialized_copy.  Define
  28   // additional overloads so that elements with pointer types are recognized as
  29   // scalars and not objects, causing bizarre type conversion errors.
  30   template<class T1, class T2>
  31   inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) {
  32     _Scalar_ptr_iterator_tag _Cat;
  33     return _Cat;
  34   }
  35
  36   template<class T1, class T2>
  37   inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) {
  38     _Scalar_ptr_iterator_tag _Cat;
  39     return _Cat;
  40   }
  41 #else
  42 // FIXME: It is not clear if the problem is fixed in VS 2005.  What is clear
  43 // is that the above hack won't work if it wasn't fixed.
  44 #endif
  45 }
  46 #endif
  47
  48 namespace llvm {
  49
  50 /// SmallVectorImpl - This class consists of common code factored out of the
  51 /// SmallVector class to reduce code duplication based on the SmallVector 'N'
  52 /// template parameter.
  53 template <typename T>
  54 class SmallVectorImpl {
  55 protected:
  56   T *Begin, *End, *Capacity;
  57
  58   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
  59   // don't want it to be automatically run, so we need to represent the space as
  60   // something else.  An array of char would work great, but might not be
  61   // aligned sufficiently.  Instead, we either use GCC extensions, or some
  62   // number of union instances for the space, which guarantee maximal alignment.
  63 protected:
  64 #ifdef __GNUC__
  65   typedef char U;
  66   U FirstEl __attribute__((aligned));
  67 #else
  68   union U {
  69     double D;
  70     long double LD;
  71     long long L;
  72     void *P;
  73   } FirstEl;
  74 #endif
  75   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
  76 public:
  77   // Default ctor - Initialize to empty.
  78   explicit SmallVectorImpl(unsigned N)
  79     : Begin(reinterpret_cast<T*>(&FirstEl)),
  80       End(reinterpret_cast<T*>(&FirstEl)),
  81       Capacity(reinterpret_cast<T*>(&FirstEl)+N) {
  82   }
  83
  84   ~SmallVectorImpl() {
  85     // Destroy the constructed elements in the vector.
  86     destroy_range(Begin, End);
  87
  88     // If this wasn't grown from the inline copy, deallocate the old space.
  89     if (!isSmall())
  90       operator delete(Begin);
  91   }
  92
  93   typedef size_t size_type;
  94   typedef ptrdiff_t difference_type;
  95   typedef T value_type;
  96   typedef T* iterator;
  97   typedef const T* const_iterator;
  98
  99   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
 100   typedef std::reverse_iterator<iterator>  reverse_iterator;
 101
 102   typedef T& reference;
 103   typedef const T& const_reference;
 104   typedef T* pointer;
 105   typedef const T* const_pointer;
 106
 107   bool empty() const { return Begin == End; }
 108   size_type size() const { return End-Begin; }
 109   size_type max_size() const { return size_type(-1) / sizeof(T); }
 110
 111   // forward iterator creation methods.
 112   iterator begin() { return Begin; }
 113   const_iterator begin() const { return Begin; }
 114   iterator end() { return End; }
 115   const_iterator end() const { return End; }
 116
 117   // reverse iterator creation methods.
 118   reverse_iterator rbegin()            { return reverse_iterator(end()); }
 119   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
 120   reverse_iterator rend()              { return reverse_iterator(begin()); }
 121   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
 122
 123
 124   reference operator[](unsigned idx) {
 125     assert (Begin + idx < End);
 126     return Begin[idx];
 127   }
 128   const_reference operator[](unsigned idx) const {
 129     assert (Begin + idx < End);
 130     return Begin[idx];
 131   }
 132
 133   reference front() {
 134     return begin()[0];
 135   }
 136   const_reference front() const {
 137     return begin()[0];
 138   }
 139
 140   reference back() {
 141     return end()[-1];
 142   }
 143   const_reference back() const {
 144     return end()[-1];
 145   }
 146
 147   void push_back(const_reference Elt) {
 148     if (End < Capacity) {
 149   Retry:
 150       new (End) T(Elt);
 151       ++End;
 152       return;
 153     }
 154     grow();
 155     goto Retry;
 156   }
 157
 158   void pop_back() {
 159     --End;
 160     End->~T();
 161   }
 162
 163   T pop_back_val() {
 164     T Result = back();
 165     pop_back();
 166     return Result;
 167   }
 168
 169   void clear() {
 170     destroy_range(Begin, End);
 171     End = Begin;
 172   }
 173
 174   void resize(unsigned N) {
 175     if (N < size()) {
 176       destroy_range(Begin+N, End);
 177       End = Begin+N;
 178     } else if (N > size()) {
 179       if (unsigned(Capacity-Begin) < N)
 180         grow(N);
 181       construct_range(End, Begin+N, T());
 182       End = Begin+N;
 183     }
 184   }
 185
 186   void resize(unsigned N, const T &NV) {
 187     if (N < size()) {
 188       destroy_range(Begin+N, End);
 189       End = Begin+N;
 190     } else if (N > size()) {
 191       if (unsigned(Capacity-Begin) < N)
 192         grow(N);
 193       construct_range(End, Begin+N, NV);
 194       End = Begin+N;
 195     }
 196   }
 197
 198   void reserve(unsigned N) {
 199     if (unsigned(Capacity-Begin) < N)
 200       grow(N);
 201   }
 202
 203   void swap(SmallVectorImpl &RHS);
 204
 205   /// append - Add the specified range to the end of the SmallVector.
 206   ///
 207   template<typename in_iter>
 208   void append(in_iter in_start, in_iter in_end) {
 209     size_type NumInputs = std::distance(in_start, in_end);
 210     // Grow allocated space if needed.
 211     if (NumInputs > size_type(Capacity-End))
 212       grow(size()+NumInputs);
 213
 214     // Copy the new elements over.
 215     std::uninitialized_copy(in_start, in_end, End);
 216     End += NumInputs;
 217   }
 218
 219   /// append - Add the specified range to the end of the SmallVector.
 220   ///
 221   void append(size_type NumInputs, const T &Elt) {
 222     // Grow allocated space if needed.
 223     if (NumInputs > size_type(Capacity-End))
 224       grow(size()+NumInputs);
 225
 226     // Copy the new elements over.
 227     std::uninitialized_fill_n(End, NumInputs, Elt);
 228     End += NumInputs;
 229   }
 230
 231   void assign(unsigned NumElts, const T &Elt) {
 232     clear();
 233     if (unsigned(Capacity-Begin) < NumElts)
 234       grow(NumElts);
 235     End = Begin+NumElts;
 236     construct_range(Begin, End, Elt);
 237   }
 238
 239   iterator erase(iterator I) {
 240     iterator N = I;
 241     // Shift all elts down one.
 242     std::copy(I+1, End, I);
 243     // Drop the last elt.
 244     pop_back();
 245     return(N);
 246   }
 247
 248   iterator erase(iterator S, iterator E) {
 249     iterator N = S;
 250     // Shift all elts down.
 251     iterator I = std::copy(E, End, S);
 252     // Drop the last elts.
 253     destroy_range(I, End);
 254     End = I;
 255     return(N);
 256   }
 257
 258   iterator insert(iterator I, const T &Elt) {
 259     if (I == End) {  // Important special case for empty vector.
 260       push_back(Elt);
 261       return end()-1;
 262     }
 263
 264     if (End < Capacity) {
 265   Retry:
 266       new (End) T(back());
 267       ++End;
 268       // Push everything else over.
 269       std::copy_backward(I, End-1, End);
 270       *I = Elt;
 271       return I;
 272     }
 273     size_t EltNo = I-Begin;
 274     grow();
 275     I = Begin+EltNo;
 276     goto Retry;
 277   }
 278
 279   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
 280     if (I == End) {  // Important special case for empty vector.
 281       append(NumToInsert, Elt);
 282       return end()-1;
 283     }
 284
 285     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 286     size_t InsertElt = I-begin();
 287
 288     // Ensure there is enough space.
 289     reserve(static_cast<unsigned>(size() + NumToInsert));
 290
 291     // Uninvalidate the iterator.
 292     I = begin()+InsertElt;
 293
 294     // If there are more elements between the insertion point and the end of the
 295     // range than there are being inserted, we can use a simple approach to
 296     // insertion.  Since we already reserved space, we know that this won't
 297     // reallocate the vector.
 298     if (size_t(end()-I) >= NumToInsert) {
 299       T *OldEnd = End;
 300       append(End-NumToInsert, End);
 301
 302       // Copy the existing elements that get replaced.
 303       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
 304
 305       std::fill_n(I, NumToInsert, Elt);
 306       return I;
 307     }
 308
 309     // Otherwise, we're inserting more elements than exist already, and we're
 310     // not inserting at the end.
 311
 312     // Copy over the elements that we're about to overwrite.
 313     T *OldEnd = End;
 314     End += NumToInsert;
 315     size_t NumOverwritten = OldEnd-I;
 316     std::uninitialized_copy(I, OldEnd, End-NumOverwritten);
 317
 318     // Replace the overwritten part.
 319     std::fill_n(I, NumOverwritten, Elt);
 320
 321     // Insert the non-overwritten middle part.
 322     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
 323     return I;
 324   }
 325
 326   template<typename ItTy>
 327   iterator insert(iterator I, ItTy From, ItTy To) {
 328     if (I == End) {  // Important special case for empty vector.
 329       append(From, To);
 330       return end()-1;
 331     }
 332
 333     size_t NumToInsert = std::distance(From, To);
 334     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 335     size_t InsertElt = I-begin();
 336
 337     // Ensure there is enough space.
 338     reserve(static_cast<unsigned>(size() + NumToInsert));
 339
 340     // Uninvalidate the iterator.
 341     I = begin()+InsertElt;
 342
 343     // If there are more elements between the insertion point and the end of the
 344     // range than there are being inserted, we can use a simple approach to
 345     // insertion.  Since we already reserved space, we know that this won't
 346     // reallocate the vector.
 347     if (size_t(end()-I) >= NumToInsert) {
 348       T *OldEnd = End;
 349       append(End-NumToInsert, End);
 350
 351       // Copy the existing elements that get replaced.
 352       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
 353
 354       std::copy(From, To, I);
 355       return I;
 356     }
 357
 358     // Otherwise, we're inserting more elements than exist already, and we're
 359     // not inserting at the end.
 360
 361     // Copy over the elements that we're about to overwrite.
 362     T *OldEnd = End;
 363     End += NumToInsert;
 364     size_t NumOverwritten = OldEnd-I;
 365     std::uninitialized_copy(I, OldEnd, End-NumOverwritten);
 366
 367     // Replace the overwritten part.
 368     std::copy(From, From+NumOverwritten, I);
 369
 370     // Insert the non-overwritten middle part.
 371     std::uninitialized_copy(From+NumOverwritten, To, OldEnd);
 372     return I;
 373   }
 374
 375   /// data - Return a pointer to the vector's buffer, even if empty().
 376   pointer data() {
 377     return pointer(Begin);
 378   }
 379
 380   /// data - Return a pointer to the vector's buffer, even if empty().
 381   const_pointer data() const {
 382     return const_pointer(Begin);
 383   }
 384
 385   const SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
 386
 387   bool operator==(const SmallVectorImpl &RHS) const {
 388     if (size() != RHS.size()) return false;
 389     for (T *This = Begin, *That = RHS.Begin, *E = Begin+size();
 390          This != E; ++This, ++That)
 391       if (*This != *That)
 392         return false;
 393     return true;
 394   }
 395   bool operator!=(const SmallVectorImpl &RHS) const { return !(*this == RHS); }
 396
 397   bool operator<(const SmallVectorImpl &RHS) const {
 398     return std::lexicographical_compare(begin(), end(),
 399                                         RHS.begin(), RHS.end());
 400   }
 401
 402 private:
 403   /// isSmall - Return true if this is a smallvector which has not had dynamic
 404   /// memory allocated for it.
 405   bool isSmall() const {
 406     return static_cast<const void*>(Begin) ==
 407            static_cast<const void*>(&FirstEl);
 408   }
 409
 410   /// grow - double the size of the allocated memory, guaranteeing space for at
 411   /// least one more element or MinSize if specified.
 412   void grow(size_type MinSize = 0);
 413
 414   void construct_range(T *S, T *E, const T &Elt) {
 415     for (; S != E; ++S)
 416       new (S) T(Elt);
 417   }
 418
 419   void destroy_range(T *S, T *E) {
 420     while (S != E) {
 421       --E;
 422       E->~T();
 423     }
 424   }
 425 };
 426
 427 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 428 template <typename T>
 429 void SmallVectorImpl<T>::grow(size_t MinSize) {
 430   size_t CurCapacity = Capacity-Begin;
 431   size_t CurSize = size();
 432   size_t NewCapacity = 2*CurCapacity;
 433   if (NewCapacity < MinSize)
 434     NewCapacity = MinSize;
 435   T *NewElts = static_cast<T*>(operator new(NewCapacity*sizeof(T)));
 436
 437   // Copy the elements over.
 438   if (is_class<T>::value)
 439     std::uninitialized_copy(Begin, End, NewElts);
 440   else
 441     // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
 442     memcpy(NewElts, Begin, CurSize * sizeof(T));
 443
 444   // Destroy the original elements.
 445   destroy_range(Begin, End);
 446
 447   // If this wasn't grown from the inline copy, deallocate the old space.
 448   if (!isSmall())
 449     operator delete(Begin);
 450
 451   Begin = NewElts;
 452   End = NewElts+CurSize;
 453   Capacity = Begin+NewCapacity;
 454 }
 455
 456 template <typename T>
 457 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
 458   if (this == &RHS) return;
 459
 460   // We can only avoid copying elements if neither vector is small.
 461   if (!isSmall() && !RHS.isSmall()) {
 462     std::swap(Begin, RHS.Begin);
 463     std::swap(End, RHS.End);
 464     std::swap(Capacity, RHS.Capacity);
 465     return;
 466   }
 467   if (RHS.size() > size_type(Capacity-Begin))
 468     grow(RHS.size());
 469   if (size() > size_type(RHS.Capacity-RHS.begin()))
 470     RHS.grow(size());
 471
 472   // Swap the shared elements.
 473   size_t NumShared = size();
 474   if (NumShared > RHS.size()) NumShared = RHS.size();
 475   for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i)
 476     std::swap(Begin[i], RHS[i]);
 477
 478   // Copy over the extra elts.
 479   if (size() > RHS.size()) {
 480     size_t EltDiff = size() - RHS.size();
 481     std::uninitialized_copy(Begin+NumShared, End, RHS.End);
 482     RHS.End += EltDiff;
 483     destroy_range(Begin+NumShared, End);
 484     End = Begin+NumShared;
 485   } else if (RHS.size() > size()) {
 486     size_t EltDiff = RHS.size() - size();
 487     std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End);
 488     End += EltDiff;
 489     destroy_range(RHS.Begin+NumShared, RHS.End);
 490     RHS.End = RHS.Begin+NumShared;
 491   }
 492 }
 493
 494 template <typename T>
 495 const SmallVectorImpl<T> &
 496 SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) {
 497   // Avoid self-assignment.
 498   if (this == &RHS) return *this;
 499
 500   // If we already have sufficient space, assign the common elements, then
 501   // destroy any excess.
 502   unsigned RHSSize = unsigned(RHS.size());
 503   unsigned CurSize = unsigned(size());
 504   if (CurSize >= RHSSize) {
 505     // Assign common elements.
 506     iterator NewEnd;
 507     if (RHSSize)
 508       NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
 509     else
 510       NewEnd = Begin;
 511
 512     // Destroy excess elements.
 513     destroy_range(NewEnd, End);
 514
 515     // Trim.
 516     End = NewEnd;
 517     return *this;
 518   }
 519
 520   // If we have to grow to have enough elements, destroy the current elements.
 521   // This allows us to avoid copying them during the grow.
 522   if (unsigned(Capacity-Begin) < RHSSize) {
 523     // Destroy current elements.
 524     destroy_range(Begin, End);
 525     End = Begin;
 526     CurSize = 0;
 527     grow(RHSSize);
 528   } else if (CurSize) {
 529     // Otherwise, use assignment for the already-constructed elements.
 530     std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
 531   }
 532
 533   // Copy construct the new elements in place.
 534   std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
 535
 536   // Set end.
 537   End = Begin+RHSSize;
 538   return *this;
 539 }
 540
 541 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
 542 /// for the case when the array is small.  It contains some number of elements
 543 /// in-place, which allows it to avoid heap allocation when the actual number of
 544 /// elements is below that threshold.  This allows normal "small" cases to be
 545 /// fast without losing generality for large inputs.
 546 ///
 547 /// Note that this does not attempt to be exception safe.
 548 ///
 549 template <typename T, unsigned N>
 550 class SmallVector : public SmallVectorImpl<T> {
 551   /// InlineElts - These are 'N-1' elements that are stored inline in the body
 552   /// of the vector.  The extra '1' element is stored in SmallVectorImpl.
 553   typedef typename SmallVectorImpl<T>::U U;
 554   enum {
 555     // MinUs - The number of U's require to cover N T's.
 556     MinUs = (static_cast<unsigned int>(sizeof(T))*N +
 557              static_cast<unsigned int>(sizeof(U)) - 1) /
 558             static_cast<unsigned int>(sizeof(U)),
 559
 560     // NumInlineEltsElts - The number of elements actually in this array.  There
 561     // is already one in the parent class, and we have to round up to avoid
 562     // having a zero-element array.
 563     NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1,
 564
 565     // NumTsAvailable - The number of T's we actually have space for, which may
 566     // be more than N due to rounding.
 567     NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(sizeof(U))/
 568                      static_cast<unsigned int>(sizeof(T))
 569   };
 570   U InlineElts[NumInlineEltsElts];
 571 public:
 572   SmallVector() : SmallVectorImpl<T>(NumTsAvailable) {
 573   }
 574
 575   explicit SmallVector(unsigned Size, const T &Value = T())
 576     : SmallVectorImpl<T>(NumTsAvailable) {
 577     this->reserve(Size);
 578     while (Size--)
 579       this->push_back(Value);
 580   }
 581
 582   template<typename ItTy>
 583   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) {
 584     this->append(S, E);
 585   }
 586
 587   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) {
 588     if (!RHS.empty())
 589       SmallVectorImpl<T>::operator=(RHS);
 590   }
 591
 592   const SmallVector &operator=(const SmallVector &RHS) {
 593     SmallVectorImpl<T>::operator=(RHS);
 594     return *this;
 595   }
 596
 597 };
 598
 599 } // End llvm namespace
 600
 601 namespace std {
 602   /// Implement std::swap in terms of SmallVector swap.
 603   template<typename T>
 604   inline void
 605   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
 606     LHS.swap(RHS);
 607   }
 608
 609   /// Implement std::swap in terms of SmallVector swap.
 610   template<typename T, unsigned N>
 611   inline void
 612   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
 613     LHS.swap(RHS);
 614   }
 615 }
 616
 617 #endif