1193323Sed//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the SmallVector class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_SMALLVECTOR_H 15193323Sed#define LLVM_ADT_SMALLVECTOR_H 16193323Sed 17243830Sdim#include "llvm/Support/AlignOf.h" 18239462Sdim#include "llvm/Support/Compiler.h" 19249423Sdim#include "llvm/Support/MathExtras.h" 20193323Sed#include "llvm/Support/type_traits.h" 21193323Sed#include <algorithm> 22193323Sed#include <cassert> 23210299Sed#include <cstddef> 24210299Sed#include <cstdlib> 25193323Sed#include <cstring> 26218893Sdim#include <iterator> 27193323Sed#include <memory> 28193323Sed 29193323Sednamespace llvm { 30193323Sed 31200581Srdivacky/// SmallVectorBase - This is all the non-templated stuff common to all 32200581Srdivacky/// SmallVectors. 33200581Srdivackyclass SmallVectorBase { 34193323Sedprotected: 35200581Srdivacky void *BeginX, *EndX, *CapacityX; 36193323Sed 37200581Srdivackyprotected: 38243830Sdim SmallVectorBase(void *FirstEl, size_t Size) 39243830Sdim : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} 40210299Sed 41226633Sdim /// grow_pod - This is an implementation of the grow() method which only works 42226633Sdim /// on POD-like data types and is out of line to reduce code duplication. 43243830Sdim void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); 44226633Sdim 45226633Sdimpublic: 46201360Srdivacky /// size_in_bytes - This returns size()*sizeof(T). 47201360Srdivacky size_t size_in_bytes() const { 48201360Srdivacky return size_t((char*)EndX - (char*)BeginX); 49201360Srdivacky } 50243830Sdim 51201360Srdivacky /// capacity_in_bytes - This returns capacity()*sizeof(T). 52201360Srdivacky size_t capacity_in_bytes() const { 53201360Srdivacky return size_t((char*)CapacityX - (char*)BeginX); 54201360Srdivacky } 55210299Sed 56200581Srdivacky bool empty() const { return BeginX == EndX; } 57200581Srdivacky}; 58201360Srdivacky 59243830Sdimtemplate <typename T, unsigned N> struct SmallVectorStorage; 60210299Sed 61243830Sdim/// SmallVectorTemplateCommon - This is the part of SmallVectorTemplateBase 62243830Sdim/// which does not depend on whether the type T is a POD. The extra dummy 63243830Sdim/// template argument is used by ArrayRef to avoid unnecessarily requiring T 64243830Sdim/// to be complete. 65243830Sdimtemplate <typename T, typename = void> 66201360Srdivackyclass SmallVectorTemplateCommon : public SmallVectorBase { 67243830Sdimprivate: 68243830Sdim template <typename, unsigned> friend struct SmallVectorStorage; 69243830Sdim 70243830Sdim // Allocate raw space for N elements of type T. If T has a ctor or dtor, we 71243830Sdim // don't want it to be automatically run, so we need to represent the space as 72243830Sdim // something else. Use an array of char of sufficient alignment. 73243830Sdim typedef llvm::AlignedCharArrayUnion<T> U; 74243830Sdim U FirstEl; 75243830Sdim // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 76243830Sdim 77201360Srdivackyprotected: 78243830Sdim SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {} 79234353Sdim 80243830Sdim void grow_pod(size_t MinSizeInBytes, size_t TSize) { 81243830Sdim SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); 82243830Sdim } 83243830Sdim 84243830Sdim /// isSmall - Return true if this is a smallvector which has not had dynamic 85243830Sdim /// memory allocated for it. 86243830Sdim bool isSmall() const { 87243830Sdim return BeginX == static_cast<const void*>(&FirstEl); 88243830Sdim } 89243830Sdim 90243830Sdim /// resetToSmall - Put this vector in a state of being small. 91243830Sdim void resetToSmall() { 92243830Sdim BeginX = EndX = CapacityX = &FirstEl; 93243830Sdim } 94243830Sdim 95201360Srdivacky void setEnd(T *P) { this->EndX = P; } 96200581Srdivackypublic: 97193323Sed typedef size_t size_type; 98193323Sed typedef ptrdiff_t difference_type; 99193323Sed typedef T value_type; 100200581Srdivacky typedef T *iterator; 101200581Srdivacky typedef const T *const_iterator; 102210299Sed 103200581Srdivacky typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 104200581Srdivacky typedef std::reverse_iterator<iterator> reverse_iterator; 105210299Sed 106200581Srdivacky typedef T &reference; 107200581Srdivacky typedef const T &const_reference; 108200581Srdivacky typedef T *pointer; 109200581Srdivacky typedef const T *const_pointer; 110210299Sed 111193323Sed // forward iterator creation methods. 112201360Srdivacky iterator begin() { return (iterator)this->BeginX; } 113201360Srdivacky const_iterator begin() const { return (const_iterator)this->BeginX; } 114201360Srdivacky iterator end() { return (iterator)this->EndX; } 115201360Srdivacky const_iterator end() const { return (const_iterator)this->EndX; } 116201360Srdivackyprotected: 117201360Srdivacky iterator capacity_ptr() { return (iterator)this->CapacityX; } 118201360Srdivacky const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} 119200581Srdivackypublic: 120210299Sed 121193323Sed // reverse iterator creation methods. 122193323Sed reverse_iterator rbegin() { return reverse_iterator(end()); } 123193323Sed const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 124193323Sed reverse_iterator rend() { return reverse_iterator(begin()); } 125193323Sed const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 126193323Sed 127200581Srdivacky size_type size() const { return end()-begin(); } 128200581Srdivacky size_type max_size() const { return size_type(-1) / sizeof(T); } 129210299Sed 130200581Srdivacky /// capacity - Return the total number of elements in the currently allocated 131200581Srdivacky /// buffer. 132200581Srdivacky size_t capacity() const { return capacity_ptr() - begin(); } 133210299Sed 134200581Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 135200581Srdivacky pointer data() { return pointer(begin()); } 136200581Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 137200581Srdivacky const_pointer data() const { return const_pointer(begin()); } 138210299Sed 139193323Sed reference operator[](unsigned idx) { 140200581Srdivacky assert(begin() + idx < end()); 141200581Srdivacky return begin()[idx]; 142193323Sed } 143193323Sed const_reference operator[](unsigned idx) const { 144200581Srdivacky assert(begin() + idx < end()); 145200581Srdivacky return begin()[idx]; 146193323Sed } 147193323Sed 148193323Sed reference front() { 149249423Sdim assert(!empty()); 150193323Sed return begin()[0]; 151193323Sed } 152193323Sed const_reference front() const { 153249423Sdim assert(!empty()); 154193323Sed return begin()[0]; 155193323Sed } 156193323Sed 157193323Sed reference back() { 158249423Sdim assert(!empty()); 159193323Sed return end()[-1]; 160193323Sed } 161193323Sed const_reference back() const { 162249423Sdim assert(!empty()); 163193323Sed return end()[-1]; 164193323Sed } 165201360Srdivacky}; 166210299Sed 167201360Srdivacky/// SmallVectorTemplateBase<isPodLike = false> - This is where we put method 168201360Srdivacky/// implementations that are designed to work with non-POD-like T's. 169201360Srdivackytemplate <typename T, bool isPodLike> 170201360Srdivackyclass SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { 171234353Sdimprotected: 172201360Srdivacky SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 173193323Sed 174201360Srdivacky static void destroy_range(T *S, T *E) { 175201360Srdivacky while (S != E) { 176201360Srdivacky --E; 177201360Srdivacky E->~T(); 178193323Sed } 179193323Sed } 180210299Sed 181239462Sdim /// move - Use move-assignment to move the range [I, E) onto the 182239462Sdim /// objects starting with "Dest". This is just <memory>'s 183239462Sdim /// std::move, but not all stdlibs actually provide that. 184201360Srdivacky template<typename It1, typename It2> 185239462Sdim static It2 move(It1 I, It1 E, It2 Dest) { 186249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 187239462Sdim for (; I != E; ++I, ++Dest) 188239462Sdim *Dest = ::std::move(*I); 189239462Sdim return Dest; 190239462Sdim#else 191239462Sdim return ::std::copy(I, E, Dest); 192239462Sdim#endif 193239462Sdim } 194239462Sdim 195239462Sdim /// move_backward - Use move-assignment to move the range 196239462Sdim /// [I, E) onto the objects ending at "Dest", moving objects 197239462Sdim /// in reverse order. This is just <algorithm>'s 198239462Sdim /// std::move_backward, but not all stdlibs actually provide that. 199239462Sdim template<typename It1, typename It2> 200239462Sdim static It2 move_backward(It1 I, It1 E, It2 Dest) { 201249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 202239462Sdim while (I != E) 203239462Sdim *--Dest = ::std::move(*--E); 204239462Sdim return Dest; 205239462Sdim#else 206239462Sdim return ::std::copy_backward(I, E, Dest); 207239462Sdim#endif 208239462Sdim } 209239462Sdim 210239462Sdim /// uninitialized_move - Move the range [I, E) into the uninitialized 211239462Sdim /// memory starting with "Dest", constructing elements as needed. 212239462Sdim template<typename It1, typename It2> 213239462Sdim static void uninitialized_move(It1 I, It1 E, It2 Dest) { 214249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 215239462Sdim for (; I != E; ++I, ++Dest) 216239462Sdim ::new ((void*) &*Dest) T(::std::move(*I)); 217239462Sdim#else 218239462Sdim ::std::uninitialized_copy(I, E, Dest); 219239462Sdim#endif 220239462Sdim } 221239462Sdim 222239462Sdim /// uninitialized_copy - Copy the range [I, E) onto the uninitialized 223239462Sdim /// memory starting with "Dest", constructing elements as needed. 224239462Sdim template<typename It1, typename It2> 225201360Srdivacky static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 226201360Srdivacky std::uninitialized_copy(I, E, Dest); 227193323Sed } 228210299Sed 229239462Sdim /// grow - Grow the allocated memory (without initializing new 230239462Sdim /// elements), doubling the size of the allocated memory. 231239462Sdim /// Guarantees space for at least one more element, or MinSize more 232239462Sdim /// elements if specified. 233201360Srdivacky void grow(size_t MinSize = 0); 234234353Sdim 235234353Sdimpublic: 236234353Sdim void push_back(const T &Elt) { 237234353Sdim if (this->EndX < this->CapacityX) { 238234353Sdim Retry: 239239462Sdim ::new ((void*) this->end()) T(Elt); 240234353Sdim this->setEnd(this->end()+1); 241234353Sdim return; 242234353Sdim } 243234353Sdim this->grow(); 244234353Sdim goto Retry; 245234353Sdim } 246239462Sdim 247249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 248239462Sdim void push_back(T &&Elt) { 249239462Sdim if (this->EndX < this->CapacityX) { 250239462Sdim Retry: 251239462Sdim ::new ((void*) this->end()) T(::std::move(Elt)); 252239462Sdim this->setEnd(this->end()+1); 253239462Sdim return; 254239462Sdim } 255239462Sdim this->grow(); 256239462Sdim goto Retry; 257239462Sdim } 258239462Sdim#endif 259234353Sdim 260234353Sdim void pop_back() { 261234353Sdim this->setEnd(this->end()-1); 262234353Sdim this->end()->~T(); 263234353Sdim } 264201360Srdivacky}; 265193323Sed 266201360Srdivacky// Define this out-of-line to dissuade the C++ compiler from inlining it. 267201360Srdivackytemplate <typename T, bool isPodLike> 268201360Srdivackyvoid SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { 269201360Srdivacky size_t CurCapacity = this->capacity(); 270201360Srdivacky size_t CurSize = this->size(); 271249423Sdim // Always grow, even from zero. 272249423Sdim size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2)); 273201360Srdivacky if (NewCapacity < MinSize) 274201360Srdivacky NewCapacity = MinSize; 275210299Sed T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); 276210299Sed 277239462Sdim // Move the elements over. 278239462Sdim this->uninitialized_move(this->begin(), this->end(), NewElts); 279210299Sed 280201360Srdivacky // Destroy the original elements. 281201360Srdivacky destroy_range(this->begin(), this->end()); 282210299Sed 283201360Srdivacky // If this wasn't grown from the inline copy, deallocate the old space. 284201360Srdivacky if (!this->isSmall()) 285210299Sed free(this->begin()); 286210299Sed 287201360Srdivacky this->setEnd(NewElts+CurSize); 288201360Srdivacky this->BeginX = NewElts; 289201360Srdivacky this->CapacityX = this->begin()+NewCapacity; 290201360Srdivacky} 291210299Sed 292210299Sed 293201360Srdivacky/// SmallVectorTemplateBase<isPodLike = true> - This is where we put method 294201360Srdivacky/// implementations that are designed to work with POD-like T's. 295201360Srdivackytemplate <typename T> 296201360Srdivackyclass SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { 297234353Sdimprotected: 298201360Srdivacky SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 299210299Sed 300201360Srdivacky // No need to do a destroy loop for POD's. 301201360Srdivacky static void destroy_range(T *, T *) {} 302210299Sed 303239462Sdim /// move - Use move-assignment to move the range [I, E) onto the 304239462Sdim /// objects starting with "Dest". For PODs, this is just memcpy. 305239462Sdim template<typename It1, typename It2> 306239462Sdim static It2 move(It1 I, It1 E, It2 Dest) { 307239462Sdim return ::std::copy(I, E, Dest); 308239462Sdim } 309239462Sdim 310239462Sdim /// move_backward - Use move-assignment to move the range 311239462Sdim /// [I, E) onto the objects ending at "Dest", moving objects 312239462Sdim /// in reverse order. 313239462Sdim template<typename It1, typename It2> 314239462Sdim static It2 move_backward(It1 I, It1 E, It2 Dest) { 315239462Sdim return ::std::copy_backward(I, E, Dest); 316239462Sdim } 317239462Sdim 318239462Sdim /// uninitialized_move - Move the range [I, E) onto the uninitialized memory 319239462Sdim /// starting with "Dest", constructing elements into it as needed. 320239462Sdim template<typename It1, typename It2> 321239462Sdim static void uninitialized_move(It1 I, It1 E, It2 Dest) { 322239462Sdim // Just do a copy. 323239462Sdim uninitialized_copy(I, E, Dest); 324239462Sdim } 325239462Sdim 326201360Srdivacky /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 327201360Srdivacky /// starting with "Dest", constructing elements into it as needed. 328201360Srdivacky template<typename It1, typename It2> 329201360Srdivacky static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 330206083Srdivacky // Arbitrary iterator types; just use the basic implementation. 331206083Srdivacky std::uninitialized_copy(I, E, Dest); 332193323Sed } 333206083Srdivacky 334206083Srdivacky /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 335206083Srdivacky /// starting with "Dest", constructing elements into it as needed. 336206083Srdivacky template<typename T1, typename T2> 337206083Srdivacky static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) { 338206083Srdivacky // Use memcpy for PODs iterated by pointers (which includes SmallVector 339206083Srdivacky // iterators): std::uninitialized_copy optimizes to memmove, but we can 340206083Srdivacky // use memcpy here. 341206083Srdivacky memcpy(Dest, I, (E-I)*sizeof(T)); 342206083Srdivacky } 343206083Srdivacky 344201360Srdivacky /// grow - double the size of the allocated memory, guaranteeing space for at 345201360Srdivacky /// least one more element or MinSize if specified. 346201360Srdivacky void grow(size_t MinSize = 0) { 347201360Srdivacky this->grow_pod(MinSize*sizeof(T), sizeof(T)); 348201360Srdivacky } 349234353Sdimpublic: 350234353Sdim void push_back(const T &Elt) { 351234353Sdim if (this->EndX < this->CapacityX) { 352234353Sdim Retry: 353239462Sdim memcpy(this->end(), &Elt, sizeof(T)); 354234353Sdim this->setEnd(this->end()+1); 355234353Sdim return; 356234353Sdim } 357234353Sdim this->grow(); 358234353Sdim goto Retry; 359234353Sdim } 360234353Sdim 361234353Sdim void pop_back() { 362234353Sdim this->setEnd(this->end()-1); 363234353Sdim } 364201360Srdivacky}; 365210299Sed 366210299Sed 367201360Srdivacky/// SmallVectorImpl - This class consists of common code factored out of the 368201360Srdivacky/// SmallVector class to reduce code duplication based on the SmallVector 'N' 369201360Srdivacky/// template parameter. 370201360Srdivackytemplate <typename T> 371201360Srdivackyclass SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { 372201360Srdivacky typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; 373218893Sdim 374249423Sdim SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION; 375201360Srdivackypublic: 376201360Srdivacky typedef typename SuperClass::iterator iterator; 377201360Srdivacky typedef typename SuperClass::size_type size_type; 378210299Sed 379234353Sdimprotected: 380201360Srdivacky // Default ctor - Initialize to empty. 381201360Srdivacky explicit SmallVectorImpl(unsigned N) 382201360Srdivacky : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { 383201360Srdivacky } 384210299Sed 385234353Sdimpublic: 386201360Srdivacky ~SmallVectorImpl() { 387201360Srdivacky // Destroy the constructed elements in the vector. 388201360Srdivacky this->destroy_range(this->begin(), this->end()); 389210299Sed 390201360Srdivacky // If this wasn't grown from the inline copy, deallocate the old space. 391201360Srdivacky if (!this->isSmall()) 392210299Sed free(this->begin()); 393201360Srdivacky } 394210299Sed 395210299Sed 396193323Sed void clear() { 397201360Srdivacky this->destroy_range(this->begin(), this->end()); 398201360Srdivacky this->EndX = this->BeginX; 399193323Sed } 400193323Sed 401193323Sed void resize(unsigned N) { 402201360Srdivacky if (N < this->size()) { 403201360Srdivacky this->destroy_range(this->begin()+N, this->end()); 404201360Srdivacky this->setEnd(this->begin()+N); 405201360Srdivacky } else if (N > this->size()) { 406201360Srdivacky if (this->capacity() < N) 407201360Srdivacky this->grow(N); 408234353Sdim std::uninitialized_fill(this->end(), this->begin()+N, T()); 409201360Srdivacky this->setEnd(this->begin()+N); 410193323Sed } 411193323Sed } 412193323Sed 413193323Sed void resize(unsigned N, const T &NV) { 414201360Srdivacky if (N < this->size()) { 415201360Srdivacky this->destroy_range(this->begin()+N, this->end()); 416201360Srdivacky this->setEnd(this->begin()+N); 417201360Srdivacky } else if (N > this->size()) { 418201360Srdivacky if (this->capacity() < N) 419201360Srdivacky this->grow(N); 420234353Sdim std::uninitialized_fill(this->end(), this->begin()+N, NV); 421201360Srdivacky this->setEnd(this->begin()+N); 422193323Sed } 423193323Sed } 424193323Sed 425193323Sed void reserve(unsigned N) { 426201360Srdivacky if (this->capacity() < N) 427201360Srdivacky this->grow(N); 428193323Sed } 429210299Sed 430201360Srdivacky T pop_back_val() { 431249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 432239462Sdim T Result = ::std::move(this->back()); 433239462Sdim#else 434201360Srdivacky T Result = this->back(); 435239462Sdim#endif 436234353Sdim this->pop_back(); 437201360Srdivacky return Result; 438201360Srdivacky } 439210299Sed 440193323Sed void swap(SmallVectorImpl &RHS); 441210299Sed 442193323Sed /// append - Add the specified range to the end of the SmallVector. 443193323Sed /// 444193323Sed template<typename in_iter> 445193323Sed void append(in_iter in_start, in_iter in_end) { 446193323Sed size_type NumInputs = std::distance(in_start, in_end); 447193323Sed // Grow allocated space if needed. 448201360Srdivacky if (NumInputs > size_type(this->capacity_ptr()-this->end())) 449201360Srdivacky this->grow(this->size()+NumInputs); 450210299Sed 451193323Sed // Copy the new elements over. 452201360Srdivacky // TODO: NEED To compile time dispatch on whether in_iter is a random access 453201360Srdivacky // iterator to use the fast uninitialized_copy. 454201360Srdivacky std::uninitialized_copy(in_start, in_end, this->end()); 455201360Srdivacky this->setEnd(this->end() + NumInputs); 456193323Sed } 457210299Sed 458193323Sed /// append - Add the specified range to the end of the SmallVector. 459193323Sed /// 460193323Sed void append(size_type NumInputs, const T &Elt) { 461193323Sed // Grow allocated space if needed. 462201360Srdivacky if (NumInputs > size_type(this->capacity_ptr()-this->end())) 463201360Srdivacky this->grow(this->size()+NumInputs); 464210299Sed 465193323Sed // Copy the new elements over. 466201360Srdivacky std::uninitialized_fill_n(this->end(), NumInputs, Elt); 467201360Srdivacky this->setEnd(this->end() + NumInputs); 468193323Sed } 469210299Sed 470193323Sed void assign(unsigned NumElts, const T &Elt) { 471193323Sed clear(); 472201360Srdivacky if (this->capacity() < NumElts) 473201360Srdivacky this->grow(NumElts); 474201360Srdivacky this->setEnd(this->begin()+NumElts); 475234353Sdim std::uninitialized_fill(this->begin(), this->end(), Elt); 476193323Sed } 477210299Sed 478193323Sed iterator erase(iterator I) { 479239462Sdim assert(I >= this->begin() && "Iterator to erase is out of bounds."); 480239462Sdim assert(I < this->end() && "Erasing at past-the-end iterator."); 481239462Sdim 482193323Sed iterator N = I; 483193323Sed // Shift all elts down one. 484239462Sdim this->move(I+1, this->end(), I); 485193323Sed // Drop the last elt. 486234353Sdim this->pop_back(); 487193323Sed return(N); 488193323Sed } 489210299Sed 490193323Sed iterator erase(iterator S, iterator E) { 491239462Sdim assert(S >= this->begin() && "Range to erase is out of bounds."); 492239462Sdim assert(S <= E && "Trying to erase invalid range."); 493239462Sdim assert(E <= this->end() && "Trying to erase past the end."); 494239462Sdim 495193323Sed iterator N = S; 496193323Sed // Shift all elts down. 497239462Sdim iterator I = this->move(E, this->end(), S); 498193323Sed // Drop the last elts. 499201360Srdivacky this->destroy_range(I, this->end()); 500201360Srdivacky this->setEnd(I); 501193323Sed return(N); 502193323Sed } 503210299Sed 504249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 505239462Sdim iterator insert(iterator I, T &&Elt) { 506239462Sdim if (I == this->end()) { // Important special case for empty vector. 507239462Sdim this->push_back(::std::move(Elt)); 508239462Sdim return this->end()-1; 509239462Sdim } 510239462Sdim 511239462Sdim assert(I >= this->begin() && "Insertion iterator is out of bounds."); 512239462Sdim assert(I <= this->end() && "Inserting past the end of the vector."); 513239462Sdim 514239462Sdim if (this->EndX < this->CapacityX) { 515239462Sdim Retry: 516239462Sdim ::new ((void*) this->end()) T(::std::move(this->back())); 517239462Sdim this->setEnd(this->end()+1); 518239462Sdim // Push everything else over. 519239462Sdim this->move_backward(I, this->end()-1, this->end()); 520239462Sdim 521239462Sdim // If we just moved the element we're inserting, be sure to update 522239462Sdim // the reference. 523239462Sdim T *EltPtr = &Elt; 524239462Sdim if (I <= EltPtr && EltPtr < this->EndX) 525239462Sdim ++EltPtr; 526239462Sdim 527239462Sdim *I = ::std::move(*EltPtr); 528239462Sdim return I; 529239462Sdim } 530239462Sdim size_t EltNo = I-this->begin(); 531239462Sdim this->grow(); 532239462Sdim I = this->begin()+EltNo; 533239462Sdim goto Retry; 534239462Sdim } 535239462Sdim#endif 536239462Sdim 537193323Sed iterator insert(iterator I, const T &Elt) { 538201360Srdivacky if (I == this->end()) { // Important special case for empty vector. 539234353Sdim this->push_back(Elt); 540201360Srdivacky return this->end()-1; 541193323Sed } 542210299Sed 543239462Sdim assert(I >= this->begin() && "Insertion iterator is out of bounds."); 544239462Sdim assert(I <= this->end() && "Inserting past the end of the vector."); 545239462Sdim 546201360Srdivacky if (this->EndX < this->CapacityX) { 547201360Srdivacky Retry: 548239462Sdim ::new ((void*) this->end()) T(this->back()); 549201360Srdivacky this->setEnd(this->end()+1); 550193323Sed // Push everything else over. 551239462Sdim this->move_backward(I, this->end()-1, this->end()); 552224145Sdim 553224145Sdim // If we just moved the element we're inserting, be sure to update 554224145Sdim // the reference. 555224145Sdim const T *EltPtr = &Elt; 556224145Sdim if (I <= EltPtr && EltPtr < this->EndX) 557224145Sdim ++EltPtr; 558224145Sdim 559224145Sdim *I = *EltPtr; 560193323Sed return I; 561193323Sed } 562201360Srdivacky size_t EltNo = I-this->begin(); 563201360Srdivacky this->grow(); 564201360Srdivacky I = this->begin()+EltNo; 565193323Sed goto Retry; 566193323Sed } 567210299Sed 568193323Sed iterator insert(iterator I, size_type NumToInsert, const T &Elt) { 569239462Sdim // Convert iterator to elt# to avoid invalidating iterator when we reserve() 570239462Sdim size_t InsertElt = I - this->begin(); 571239462Sdim 572201360Srdivacky if (I == this->end()) { // Important special case for empty vector. 573193323Sed append(NumToInsert, Elt); 574239462Sdim return this->begin()+InsertElt; 575193323Sed } 576210299Sed 577239462Sdim assert(I >= this->begin() && "Insertion iterator is out of bounds."); 578239462Sdim assert(I <= this->end() && "Inserting past the end of the vector."); 579210299Sed 580193323Sed // Ensure there is enough space. 581201360Srdivacky reserve(static_cast<unsigned>(this->size() + NumToInsert)); 582210299Sed 583193323Sed // Uninvalidate the iterator. 584201360Srdivacky I = this->begin()+InsertElt; 585210299Sed 586193323Sed // If there are more elements between the insertion point and the end of the 587193323Sed // range than there are being inserted, we can use a simple approach to 588193323Sed // insertion. Since we already reserved space, we know that this won't 589193323Sed // reallocate the vector. 590201360Srdivacky if (size_t(this->end()-I) >= NumToInsert) { 591201360Srdivacky T *OldEnd = this->end(); 592201360Srdivacky append(this->end()-NumToInsert, this->end()); 593210299Sed 594193323Sed // Copy the existing elements that get replaced. 595239462Sdim this->move_backward(I, OldEnd-NumToInsert, OldEnd); 596210299Sed 597193323Sed std::fill_n(I, NumToInsert, Elt); 598193323Sed return I; 599193323Sed } 600210299Sed 601193323Sed // Otherwise, we're inserting more elements than exist already, and we're 602193323Sed // not inserting at the end. 603210299Sed 604239462Sdim // Move over the elements that we're about to overwrite. 605201360Srdivacky T *OldEnd = this->end(); 606201360Srdivacky this->setEnd(this->end() + NumToInsert); 607193323Sed size_t NumOverwritten = OldEnd-I; 608239462Sdim this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 609210299Sed 610193323Sed // Replace the overwritten part. 611193323Sed std::fill_n(I, NumOverwritten, Elt); 612210299Sed 613193323Sed // Insert the non-overwritten middle part. 614193323Sed std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 615193323Sed return I; 616193323Sed } 617210299Sed 618193323Sed template<typename ItTy> 619193323Sed iterator insert(iterator I, ItTy From, ItTy To) { 620239462Sdim // Convert iterator to elt# to avoid invalidating iterator when we reserve() 621239462Sdim size_t InsertElt = I - this->begin(); 622239462Sdim 623201360Srdivacky if (I == this->end()) { // Important special case for empty vector. 624193323Sed append(From, To); 625239462Sdim return this->begin()+InsertElt; 626193323Sed } 627210299Sed 628239462Sdim assert(I >= this->begin() && "Insertion iterator is out of bounds."); 629239462Sdim assert(I <= this->end() && "Inserting past the end of the vector."); 630239462Sdim 631193323Sed size_t NumToInsert = std::distance(From, To); 632210299Sed 633193323Sed // Ensure there is enough space. 634201360Srdivacky reserve(static_cast<unsigned>(this->size() + NumToInsert)); 635210299Sed 636193323Sed // Uninvalidate the iterator. 637201360Srdivacky I = this->begin()+InsertElt; 638210299Sed 639193323Sed // If there are more elements between the insertion point and the end of the 640193323Sed // range than there are being inserted, we can use a simple approach to 641193323Sed // insertion. Since we already reserved space, we know that this won't 642193323Sed // reallocate the vector. 643201360Srdivacky if (size_t(this->end()-I) >= NumToInsert) { 644201360Srdivacky T *OldEnd = this->end(); 645201360Srdivacky append(this->end()-NumToInsert, this->end()); 646210299Sed 647193323Sed // Copy the existing elements that get replaced. 648239462Sdim this->move_backward(I, OldEnd-NumToInsert, OldEnd); 649210299Sed 650193323Sed std::copy(From, To, I); 651193323Sed return I; 652193323Sed } 653210299Sed 654193323Sed // Otherwise, we're inserting more elements than exist already, and we're 655193323Sed // not inserting at the end. 656210299Sed 657239462Sdim // Move over the elements that we're about to overwrite. 658201360Srdivacky T *OldEnd = this->end(); 659201360Srdivacky this->setEnd(this->end() + NumToInsert); 660193323Sed size_t NumOverwritten = OldEnd-I; 661239462Sdim this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 662210299Sed 663193323Sed // Replace the overwritten part. 664239462Sdim for (T *J = I; NumOverwritten > 0; --NumOverwritten) { 665239462Sdim *J = *From; 666239462Sdim ++J; ++From; 667206083Srdivacky } 668210299Sed 669193323Sed // Insert the non-overwritten middle part. 670206083Srdivacky this->uninitialized_copy(From, To, OldEnd); 671193323Sed return I; 672193323Sed } 673210299Sed 674239462Sdim SmallVectorImpl &operator=(const SmallVectorImpl &RHS); 675210299Sed 676249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 677239462Sdim SmallVectorImpl &operator=(SmallVectorImpl &&RHS); 678239462Sdim#endif 679239462Sdim 680193323Sed bool operator==(const SmallVectorImpl &RHS) const { 681201360Srdivacky if (this->size() != RHS.size()) return false; 682201360Srdivacky return std::equal(this->begin(), this->end(), RHS.begin()); 683193323Sed } 684201360Srdivacky bool operator!=(const SmallVectorImpl &RHS) const { 685201360Srdivacky return !(*this == RHS); 686201360Srdivacky } 687210299Sed 688193323Sed bool operator<(const SmallVectorImpl &RHS) const { 689201360Srdivacky return std::lexicographical_compare(this->begin(), this->end(), 690193323Sed RHS.begin(), RHS.end()); 691193323Sed } 692210299Sed 693243830Sdim /// Set the array size to \p N, which the current array must have enough 694243830Sdim /// capacity for. 695198090Srdivacky /// 696198090Srdivacky /// This does not construct or destroy any elements in the vector. 697198090Srdivacky /// 698198090Srdivacky /// Clients can use this in conjunction with capacity() to write past the end 699198090Srdivacky /// of the buffer when they know that more elements are available, and only 700198090Srdivacky /// update the size later. This avoids the cost of value initializing elements 701198090Srdivacky /// which will only be overwritten. 702198090Srdivacky void set_size(unsigned N) { 703201360Srdivacky assert(N <= this->capacity()); 704201360Srdivacky this->setEnd(this->begin() + N); 705198090Srdivacky } 706193323Sed}; 707193323Sed 708210299Sed 709193323Sedtemplate <typename T> 710193323Sedvoid SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 711193323Sed if (this == &RHS) return; 712193323Sed 713193323Sed // We can only avoid copying elements if neither vector is small. 714201360Srdivacky if (!this->isSmall() && !RHS.isSmall()) { 715201360Srdivacky std::swap(this->BeginX, RHS.BeginX); 716201360Srdivacky std::swap(this->EndX, RHS.EndX); 717201360Srdivacky std::swap(this->CapacityX, RHS.CapacityX); 718193323Sed return; 719193323Sed } 720201360Srdivacky if (RHS.size() > this->capacity()) 721201360Srdivacky this->grow(RHS.size()); 722201360Srdivacky if (this->size() > RHS.capacity()) 723201360Srdivacky RHS.grow(this->size()); 724193323Sed 725193323Sed // Swap the shared elements. 726201360Srdivacky size_t NumShared = this->size(); 727193323Sed if (NumShared > RHS.size()) NumShared = RHS.size(); 728193323Sed for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i) 729200581Srdivacky std::swap((*this)[i], RHS[i]); 730193323Sed 731193323Sed // Copy over the extra elts. 732201360Srdivacky if (this->size() > RHS.size()) { 733201360Srdivacky size_t EltDiff = this->size() - RHS.size(); 734201360Srdivacky this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); 735200581Srdivacky RHS.setEnd(RHS.end()+EltDiff); 736201360Srdivacky this->destroy_range(this->begin()+NumShared, this->end()); 737201360Srdivacky this->setEnd(this->begin()+NumShared); 738201360Srdivacky } else if (RHS.size() > this->size()) { 739201360Srdivacky size_t EltDiff = RHS.size() - this->size(); 740201360Srdivacky this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); 741201360Srdivacky this->setEnd(this->end() + EltDiff); 742201360Srdivacky this->destroy_range(RHS.begin()+NumShared, RHS.end()); 743200581Srdivacky RHS.setEnd(RHS.begin()+NumShared); 744193323Sed } 745193323Sed} 746193323Sed 747193323Sedtemplate <typename T> 748239462SdimSmallVectorImpl<T> &SmallVectorImpl<T>:: 749201360Srdivacky operator=(const SmallVectorImpl<T> &RHS) { 750193323Sed // Avoid self-assignment. 751193323Sed if (this == &RHS) return *this; 752193323Sed 753193323Sed // If we already have sufficient space, assign the common elements, then 754193323Sed // destroy any excess. 755200581Srdivacky size_t RHSSize = RHS.size(); 756201360Srdivacky size_t CurSize = this->size(); 757193323Sed if (CurSize >= RHSSize) { 758193323Sed // Assign common elements. 759193323Sed iterator NewEnd; 760193323Sed if (RHSSize) 761201360Srdivacky NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); 762193323Sed else 763201360Srdivacky NewEnd = this->begin(); 764193323Sed 765193323Sed // Destroy excess elements. 766201360Srdivacky this->destroy_range(NewEnd, this->end()); 767193323Sed 768193323Sed // Trim. 769201360Srdivacky this->setEnd(NewEnd); 770193323Sed return *this; 771193323Sed } 772193323Sed 773193323Sed // If we have to grow to have enough elements, destroy the current elements. 774193323Sed // This allows us to avoid copying them during the grow. 775239462Sdim // FIXME: don't do this if they're efficiently moveable. 776201360Srdivacky if (this->capacity() < RHSSize) { 777193323Sed // Destroy current elements. 778201360Srdivacky this->destroy_range(this->begin(), this->end()); 779201360Srdivacky this->setEnd(this->begin()); 780193323Sed CurSize = 0; 781201360Srdivacky this->grow(RHSSize); 782193323Sed } else if (CurSize) { 783193323Sed // Otherwise, use assignment for the already-constructed elements. 784201360Srdivacky std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); 785193323Sed } 786193323Sed 787193323Sed // Copy construct the new elements in place. 788201360Srdivacky this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), 789201360Srdivacky this->begin()+CurSize); 790193323Sed 791193323Sed // Set end. 792201360Srdivacky this->setEnd(this->begin()+RHSSize); 793193323Sed return *this; 794193323Sed} 795193323Sed 796249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 797239462Sdimtemplate <typename T> 798239462SdimSmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { 799239462Sdim // Avoid self-assignment. 800239462Sdim if (this == &RHS) return *this; 801201360Srdivacky 802239462Sdim // If the RHS isn't small, clear this vector and then steal its buffer. 803239462Sdim if (!RHS.isSmall()) { 804239462Sdim this->destroy_range(this->begin(), this->end()); 805239462Sdim if (!this->isSmall()) free(this->begin()); 806239462Sdim this->BeginX = RHS.BeginX; 807239462Sdim this->EndX = RHS.EndX; 808239462Sdim this->CapacityX = RHS.CapacityX; 809239462Sdim RHS.resetToSmall(); 810239462Sdim return *this; 811239462Sdim } 812239462Sdim 813239462Sdim // If we already have sufficient space, assign the common elements, then 814239462Sdim // destroy any excess. 815239462Sdim size_t RHSSize = RHS.size(); 816239462Sdim size_t CurSize = this->size(); 817239462Sdim if (CurSize >= RHSSize) { 818239462Sdim // Assign common elements. 819239462Sdim iterator NewEnd = this->begin(); 820239462Sdim if (RHSSize) 821239462Sdim NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd); 822239462Sdim 823239462Sdim // Destroy excess elements and trim the bounds. 824239462Sdim this->destroy_range(NewEnd, this->end()); 825239462Sdim this->setEnd(NewEnd); 826239462Sdim 827239462Sdim // Clear the RHS. 828239462Sdim RHS.clear(); 829239462Sdim 830239462Sdim return *this; 831239462Sdim } 832239462Sdim 833239462Sdim // If we have to grow to have enough elements, destroy the current elements. 834239462Sdim // This allows us to avoid copying them during the grow. 835239462Sdim // FIXME: this may not actually make any sense if we can efficiently move 836239462Sdim // elements. 837239462Sdim if (this->capacity() < RHSSize) { 838239462Sdim // Destroy current elements. 839239462Sdim this->destroy_range(this->begin(), this->end()); 840239462Sdim this->setEnd(this->begin()); 841239462Sdim CurSize = 0; 842239462Sdim this->grow(RHSSize); 843239462Sdim } else if (CurSize) { 844239462Sdim // Otherwise, use assignment for the already-constructed elements. 845239462Sdim this->move(RHS.begin(), RHS.end(), this->begin()); 846239462Sdim } 847239462Sdim 848239462Sdim // Move-construct the new elements in place. 849239462Sdim this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), 850239462Sdim this->begin()+CurSize); 851239462Sdim 852239462Sdim // Set end. 853239462Sdim this->setEnd(this->begin()+RHSSize); 854239462Sdim 855239462Sdim RHS.clear(); 856239462Sdim return *this; 857239462Sdim} 858239462Sdim#endif 859239462Sdim 860243830Sdim/// Storage for the SmallVector elements which aren't contained in 861243830Sdim/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1' 862243830Sdim/// element is in the base class. This is specialized for the N=1 and N=0 cases 863243830Sdim/// to avoid allocating unnecessary storage. 864243830Sdimtemplate <typename T, unsigned N> 865243830Sdimstruct SmallVectorStorage { 866243830Sdim typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1]; 867243830Sdim}; 868243830Sdimtemplate <typename T> struct SmallVectorStorage<T, 1> {}; 869243830Sdimtemplate <typename T> struct SmallVectorStorage<T, 0> {}; 870243830Sdim 871193323Sed/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized 872193323Sed/// for the case when the array is small. It contains some number of elements 873193323Sed/// in-place, which allows it to avoid heap allocation when the actual number of 874193323Sed/// elements is below that threshold. This allows normal "small" cases to be 875193323Sed/// fast without losing generality for large inputs. 876193323Sed/// 877193323Sed/// Note that this does not attempt to be exception safe. 878193323Sed/// 879193323Sedtemplate <typename T, unsigned N> 880193323Sedclass SmallVector : public SmallVectorImpl<T> { 881243830Sdim /// Storage - Inline space for elements which aren't stored in the base class. 882243830Sdim SmallVectorStorage<T, N> Storage; 883193323Sedpublic: 884243830Sdim SmallVector() : SmallVectorImpl<T>(N) { 885193323Sed } 886193323Sed 887193323Sed explicit SmallVector(unsigned Size, const T &Value = T()) 888243830Sdim : SmallVectorImpl<T>(N) { 889234353Sdim this->assign(Size, Value); 890193323Sed } 891193323Sed 892193323Sed template<typename ItTy> 893243830Sdim SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { 894193323Sed this->append(S, E); 895193323Sed } 896193323Sed 897243830Sdim SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { 898193323Sed if (!RHS.empty()) 899193323Sed SmallVectorImpl<T>::operator=(RHS); 900193323Sed } 901193323Sed 902193323Sed const SmallVector &operator=(const SmallVector &RHS) { 903193323Sed SmallVectorImpl<T>::operator=(RHS); 904193323Sed return *this; 905193323Sed } 906193323Sed 907249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 908243830Sdim SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { 909239462Sdim if (!RHS.empty()) 910239462Sdim SmallVectorImpl<T>::operator=(::std::move(RHS)); 911239462Sdim } 912239462Sdim 913239462Sdim const SmallVector &operator=(SmallVector &&RHS) { 914239462Sdim SmallVectorImpl<T>::operator=(::std::move(RHS)); 915239462Sdim return *this; 916239462Sdim } 917239462Sdim#endif 918239462Sdim 919193323Sed}; 920193323Sed 921226633Sdimtemplate<typename T, unsigned N> 922226633Sdimstatic inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { 923226633Sdim return X.capacity_in_bytes(); 924226633Sdim} 925226633Sdim 926193323Sed} // End llvm namespace 927193323Sed 928193323Sednamespace std { 929193323Sed /// Implement std::swap in terms of SmallVector swap. 930193323Sed template<typename T> 931193323Sed inline void 932193323Sed swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 933193323Sed LHS.swap(RHS); 934193323Sed } 935193323Sed 936193323Sed /// Implement std::swap in terms of SmallVector swap. 937193323Sed template<typename T, unsigned N> 938193323Sed inline void 939193323Sed swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 940193323Sed LHS.swap(RHS); 941193323Sed } 942193323Sed} 943193323Sed 944193323Sed#endif 945