1f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// 2f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// 3f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// The LLVM Compiler Infrastructure 4f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// 8f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner//===----------------------------------------------------------------------===// 9f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// 10f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// This file defines the SmallVector class. 11f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner// 12f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner//===----------------------------------------------------------------------===// 13f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner 14f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner#ifndef LLVM_ADT_SMALLVECTOR_H 15f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner#define LLVM_ADT_SMALLVECTOR_H 16f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner 17bc363931085587bac42a40653962a3e5acd1ffceRichard Smith#include "llvm/Support/AlignOf.h" 1838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#include "llvm/Support/Compiler.h" 19f4d7708972370bdd438830e50594b90a36bb6f76Dan Gohman#include "llvm/Support/type_traits.h" 20825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner#include <algorithm> 21a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <cassert> 22345b378309eabd74a7a43f095dca9a4894bc371eDuncan Sands#include <cstddef> 23d164d3d9e74aa099ce7ef86ac0724fe504f7c3f9Benjamin Kramer#include <cstdlib> 24ff4d609ec5eca4fc30a931a505d0c18f7569f8c4Seo Sanghyeon#include <cstring> 25476b242fe7a61e5f9ac6214b0bc5c680d24f152eNick Lewycky#include <iterator> 26f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner#include <memory> 27f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner 28f28265402130eb03762d9a6333fd8f87765a8875Chris Lattnernamespace llvm { 29f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner 30dc2e570411bb1b1345a6b9840050aca823835a81Chris Lattner/// SmallVectorBase - This is all the non-templated stuff common to all 31dc2e570411bb1b1345a6b9840050aca823835a81Chris Lattner/// SmallVectors. 32dc2e570411bb1b1345a6b9840050aca823835a81Chris Lattnerclass SmallVectorBase { 33dd94c8d6b2afb9c33c364ac8f0c8f8ed5d4c04a0Chris Lattnerprotected: 3410aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner void *BeginX, *EndX, *CapacityX; 353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3610aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattnerprotected: 37bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVectorBase(void *FirstEl, size_t Size) 38bc363931085587bac42a40653962a3e5acd1ffceRichard Smith : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} 3938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 4018dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek /// grow_pod - This is an implementation of the grow() method which only works 4118dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek /// on POD-like data types and is out of line to reduce code duplication. 42bc363931085587bac42a40653962a3e5acd1ffceRichard Smith void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); 4318dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek 4418dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekpublic: 4599ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner /// size_in_bytes - This returns size()*sizeof(T). 4699ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner size_t size_in_bytes() const { 4799ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner return size_t((char*)EndX - (char*)BeginX); 4899ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner } 49bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 5099ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner /// capacity_in_bytes - This returns capacity()*sizeof(T). 5199ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner size_t capacity_in_bytes() const { 5299ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner return size_t((char*)CapacityX - (char*)BeginX); 5399ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner } 5463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 5510aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner bool empty() const { return BeginX == EndX; } 5610aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner}; 5763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 58bc363931085587bac42a40653962a3e5acd1ffceRichard Smithtemplate <typename T, unsigned N> struct SmallVectorStorage; 59de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner 60bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// SmallVectorTemplateCommon - This is the part of SmallVectorTemplateBase 61bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// which does not depend on whether the type T is a POD. The extra dummy 62bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// template argument is used by ArrayRef to avoid unnecessarily requiring T 63bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// to be complete. 64bc363931085587bac42a40653962a3e5acd1ffceRichard Smithtemplate <typename T, typename = void> 65de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattnerclass SmallVectorTemplateCommon : public SmallVectorBase { 66bc363931085587bac42a40653962a3e5acd1ffceRichard Smithprivate: 67bc363931085587bac42a40653962a3e5acd1ffceRichard Smith template <typename, unsigned> friend struct SmallVectorStorage; 68bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 69bc363931085587bac42a40653962a3e5acd1ffceRichard Smith // Allocate raw space for N elements of type T. If T has a ctor or dtor, we 70bc363931085587bac42a40653962a3e5acd1ffceRichard Smith // don't want it to be automatically run, so we need to represent the space as 71bc363931085587bac42a40653962a3e5acd1ffceRichard Smith // something else. Use an array of char of sufficient alignment. 72bc363931085587bac42a40653962a3e5acd1ffceRichard Smith typedef llvm::AlignedCharArrayUnion<T> U; 73bc363931085587bac42a40653962a3e5acd1ffceRichard Smith U FirstEl; 74bc363931085587bac42a40653962a3e5acd1ffceRichard Smith // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 75bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 76e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnerprotected: 77bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {} 78bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 79bc363931085587bac42a40653962a3e5acd1ffceRichard Smith void grow_pod(size_t MinSizeInBytes, size_t TSize) { 80bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); 81bc363931085587bac42a40653962a3e5acd1ffceRichard Smith } 82bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 83bc363931085587bac42a40653962a3e5acd1ffceRichard Smith /// isSmall - Return true if this is a smallvector which has not had dynamic 84bc363931085587bac42a40653962a3e5acd1ffceRichard Smith /// memory allocated for it. 85bc363931085587bac42a40653962a3e5acd1ffceRichard Smith bool isSmall() const { 86bc363931085587bac42a40653962a3e5acd1ffceRichard Smith return BeginX == static_cast<const void*>(&FirstEl); 87bc363931085587bac42a40653962a3e5acd1ffceRichard Smith } 88bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 89bc363931085587bac42a40653962a3e5acd1ffceRichard Smith /// resetToSmall - Put this vector in a state of being small. 90bc363931085587bac42a40653962a3e5acd1ffceRichard Smith void resetToSmall() { 91bc363931085587bac42a40653962a3e5acd1ffceRichard Smith BeginX = EndX = CapacityX = &FirstEl; 92bc363931085587bac42a40653962a3e5acd1ffceRichard Smith } 9363ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 943feccbaaee2fe639fd089cdb78ad623f662a5796Benjamin Kramer void setEnd(T *P) { this->EndX = P; } 953feccbaaee2fe639fd089cdb78ad623f662a5796Benjamin Kramerpublic: 96f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner typedef size_t size_type; 97254a8860570b2624752b079b4a3e37b0942a888aDan Gohman typedef ptrdiff_t difference_type; 980c5a560b034b377e3966833de30167e9030b5cc8Owen Anderson typedef T value_type; 9910aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef T *iterator; 10010aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef const T *const_iterator; 10163ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 10210aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 10310aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef std::reverse_iterator<iterator> reverse_iterator; 10463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 10510aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef T &reference; 10610aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef const T &const_reference; 10710aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef T *pointer; 10810aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner typedef const T *const_pointer; 10963ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 1108568122b41340e9c3bfac47f3714db4241196fbdChris Lattner // forward iterator creation methods. 111de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner iterator begin() { return (iterator)this->BeginX; } 112de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner const_iterator begin() const { return (const_iterator)this->BeginX; } 113de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner iterator end() { return (iterator)this->EndX; } 114de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner const_iterator end() const { return (const_iterator)this->EndX; } 115e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnerprotected: 116de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner iterator capacity_ptr() { return (iterator)this->CapacityX; } 117de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} 11810aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattnerpublic: 11963ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 1208568122b41340e9c3bfac47f3714db4241196fbdChris Lattner // reverse iterator creation methods. 1218568122b41340e9c3bfac47f3714db4241196fbdChris Lattner reverse_iterator rbegin() { return reverse_iterator(end()); } 1228568122b41340e9c3bfac47f3714db4241196fbdChris Lattner const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 1238568122b41340e9c3bfac47f3714db4241196fbdChris Lattner reverse_iterator rend() { return reverse_iterator(begin()); } 1248568122b41340e9c3bfac47f3714db4241196fbdChris Lattner const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 1253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 12610aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner size_type size() const { return end()-begin(); } 12710aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner size_type max_size() const { return size_type(-1) / sizeof(T); } 12863ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 12910aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner /// capacity - Return the total number of elements in the currently allocated 13010aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner /// buffer. 13110aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner size_t capacity() const { return capacity_ptr() - begin(); } 13263ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 13310aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner /// data - Return a pointer to the vector's buffer, even if empty(). 13410aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner pointer data() { return pointer(begin()); } 13510aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner /// data - Return a pointer to the vector's buffer, even if empty(). 13610aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner const_pointer data() const { return const_pointer(begin()); } 13763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 138f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner reference operator[](unsigned idx) { 13910aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner assert(begin() + idx < end()); 14010aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner return begin()[idx]; 141f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner } 142f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner const_reference operator[](unsigned idx) const { 14310aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner assert(begin() + idx < end()); 14410aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner return begin()[idx]; 145f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner } 1463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 147d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner reference front() { 1480ac7e6f293bc502b39005496d2160b0089d3fa46Richard Trieu assert(!empty()); 149d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner return begin()[0]; 150d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 151d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner const_reference front() const { 1520ac7e6f293bc502b39005496d2160b0089d3fa46Richard Trieu assert(!empty()); 153d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner return begin()[0]; 154d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 1553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 156f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner reference back() { 1570ac7e6f293bc502b39005496d2160b0089d3fa46Richard Trieu assert(!empty()); 158f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner return end()[-1]; 159f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner } 160f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner const_reference back() const { 1610ac7e6f293bc502b39005496d2160b0089d3fa46Richard Trieu assert(!empty()); 162f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner return end()[-1]; 163f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner } 164e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner}; 16563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 1662676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner/// SmallVectorTemplateBase<isPodLike = false> - This is where we put method 1672676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner/// implementations that are designed to work with non-POD-like T's. 168e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnertemplate <typename T, bool isPodLike> 169e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnerclass SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { 1703feccbaaee2fe639fd089cdb78ad623f662a5796Benjamin Kramerprotected: 171e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 1723a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1732676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner static void destroy_range(T *S, T *E) { 1742676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner while (S != E) { 1752676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner --E; 1762676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner E->~T(); 1772676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner } 1782676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner } 17963ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 18038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// move - Use move-assignment to move the range [I, E) onto the 18138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// objects starting with "Dest". This is just <memory>'s 18238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// std::move, but not all stdlibs actually provide that. 18338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall template<typename It1, typename It2> 18438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall static It2 move(It1 I, It1 E, It2 Dest) { 1854334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 18638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall for (; I != E; ++I, ++Dest) 18738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall *Dest = ::std::move(*I); 18838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return Dest; 18938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#else 19038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return ::std::copy(I, E, Dest); 19138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 19238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 19338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 19438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// move_backward - Use move-assignment to move the range 19538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// [I, E) onto the objects ending at "Dest", moving objects 19638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// in reverse order. This is just <algorithm>'s 19738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// std::move_backward, but not all stdlibs actually provide that. 19838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall template<typename It1, typename It2> 19938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall static It2 move_backward(It1 I, It1 E, It2 Dest) { 2004334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 20138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall while (I != E) 20238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall *--Dest = ::std::move(*--E); 20338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return Dest; 20438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#else 20538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return ::std::copy_backward(I, E, Dest); 20638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 20738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 20838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 20938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// uninitialized_move - Move the range [I, E) into the uninitialized 21038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// memory starting with "Dest", constructing elements as needed. 21138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall template<typename It1, typename It2> 21238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall static void uninitialized_move(It1 I, It1 E, It2 Dest) { 2134334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 21438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall for (; I != E; ++I, ++Dest) 21538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ::new ((void*) &*Dest) T(::std::move(*I)); 21638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#else 21738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ::std::uninitialized_copy(I, E, Dest); 21838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 21938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 22038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 22138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// uninitialized_copy - Copy the range [I, E) onto the uninitialized 22238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// memory starting with "Dest", constructing elements as needed. 2232676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner template<typename It1, typename It2> 2242676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 2252676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner std::uninitialized_copy(I, E, Dest); 2262676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner } 22763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 22838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// grow - Grow the allocated memory (without initializing new 22938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// elements), doubling the size of the allocated memory. 23038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// Guarantees space for at least one more element, or MinSize more 23138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// elements if specified. 23299ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner void grow(size_t MinSize = 0); 233d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper 234d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooperpublic: 235d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper void push_back(const T &Elt) { 236d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper if (this->EndX < this->CapacityX) { 237d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper Retry: 23838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ::new ((void*) this->end()) T(Elt); 23938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->setEnd(this->end()+1); 24038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return; 24138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 24238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->grow(); 24338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall goto Retry; 24438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 24538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 2464334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 24738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall void push_back(T &&Elt) { 24838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (this->EndX < this->CapacityX) { 24938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall Retry: 25038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ::new ((void*) this->end()) T(::std::move(Elt)); 251d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->setEnd(this->end()+1); 252d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper return; 253d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper } 254d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->grow(); 255d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper goto Retry; 256d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper } 25738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 258d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper 259d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper void pop_back() { 260d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->setEnd(this->end()-1); 261d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->end()->~T(); 262d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper } 263e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner}; 2643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 26599ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner// Define this out-of-line to dissuade the C++ compiler from inlining it. 26699ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattnertemplate <typename T, bool isPodLike> 26799ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattnervoid SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { 26899ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner size_t CurCapacity = this->capacity(); 26999ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner size_t CurSize = this->size(); 2702a9a2dba4c02e7eea3aeba2be5dc1fc377d5aa5cJohn McCall size_t NewCapacity = 2*CurCapacity + 1; // Always grow, even from zero. 27199ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner if (NewCapacity < MinSize) 27299ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner NewCapacity = MinSize; 273d164d3d9e74aa099ce7ef86ac0724fe504f7c3f9Benjamin Kramer T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); 27463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 27538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Move the elements over. 27638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->uninitialized_move(this->begin(), this->end(), NewElts); 27763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 27899ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner // Destroy the original elements. 27999ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner destroy_range(this->begin(), this->end()); 28063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 28199ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner // If this wasn't grown from the inline copy, deallocate the old space. 28299ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner if (!this->isSmall()) 283d164d3d9e74aa099ce7ef86ac0724fe504f7c3f9Benjamin Kramer free(this->begin()); 28463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 2854eeeb4767ca4e020e7d9aff1be671d2fc6f74b81Daniel Dunbar this->setEnd(NewElts+CurSize); 28699ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->BeginX = NewElts; 28799ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->CapacityX = this->begin()+NewCapacity; 28899ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner} 28963ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 29063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 2912676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner/// SmallVectorTemplateBase<isPodLike = true> - This is where we put method 2922676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner/// implementations that are designed to work with POD-like T's. 293e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnertemplate <typename T> 294e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnerclass SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { 2953feccbaaee2fe639fd089cdb78ad623f662a5796Benjamin Kramerprotected: 296e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 29763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 2982676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner // No need to do a destroy loop for POD's. 299af15ffb9127dff185b74ff8b37a9d570ca547c61Eric Christopher static void destroy_range(T *, T *) {} 30063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 30138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// move - Use move-assignment to move the range [I, E) onto the 30238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// objects starting with "Dest". For PODs, this is just memcpy. 30338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall template<typename It1, typename It2> 30438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall static It2 move(It1 I, It1 E, It2 Dest) { 30538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return ::std::copy(I, E, Dest); 30638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 30738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 30838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// move_backward - Use move-assignment to move the range 30938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// [I, E) onto the objects ending at "Dest", moving objects 31038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// in reverse order. 31138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall template<typename It1, typename It2> 31238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall static It2 move_backward(It1 I, It1 E, It2 Dest) { 31338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return ::std::copy_backward(I, E, Dest); 31438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 31538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 31638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// uninitialized_move - Move the range [I, E) onto the uninitialized memory 31738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall /// starting with "Dest", constructing elements into it as needed. 31838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall template<typename It1, typename It2> 31938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall static void uninitialized_move(It1 I, It1 E, It2 Dest) { 32038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Just do a copy. 32138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall uninitialized_copy(I, E, Dest); 32238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 32338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 3242676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 3252676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner /// starting with "Dest", constructing elements into it as needed. 3262676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner template<typename It1, typename It2> 3272676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 328a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman // Arbitrary iterator types; just use the basic implementation. 329a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman std::uninitialized_copy(I, E, Dest); 3302676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner } 331a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman 332a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 333a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman /// starting with "Dest", constructing elements into it as needed. 334a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman template<typename T1, typename T2> 335a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) { 336a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman // Use memcpy for PODs iterated by pointers (which includes SmallVector 337a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman // iterators): std::uninitialized_copy optimizes to memmove, but we can 338a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman // use memcpy here. 339a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman memcpy(Dest, I, (E-I)*sizeof(T)); 340a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman } 341a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman 34299ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner /// grow - double the size of the allocated memory, guaranteeing space for at 34399ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner /// least one more element or MinSize if specified. 34499ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner void grow(size_t MinSize = 0) { 34599ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow_pod(MinSize*sizeof(T), sizeof(T)); 34699ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner } 347d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooperpublic: 348d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper void push_back(const T &Elt) { 349d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper if (this->EndX < this->CapacityX) { 350d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper Retry: 3513703baacf5c17425a07d57583148086a746c5f98Benjamin Kramer memcpy(this->end(), &Elt, sizeof(T)); 352d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->setEnd(this->end()+1); 353d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper return; 354d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper } 355d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->grow(); 356d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper goto Retry; 357d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper } 358d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper 359d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper void pop_back() { 360d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->setEnd(this->end()-1); 361d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper } 362e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner}; 36363ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 36463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 365e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner/// SmallVectorImpl - This class consists of common code factored out of the 366e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner/// SmallVector class to reduce code duplication based on the SmallVector 'N' 367e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner/// template parameter. 368e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnertemplate <typename T> 369e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnerclass SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { 3702676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; 371326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 372b61a11f7c0a6dd453f2b53e0583fe14603516420Jakub Staszak SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION; 373e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnerpublic: 3742676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner typedef typename SuperClass::iterator iterator; 3752676f183123e1472c8d9d7f6a64f1d50a74e484aChris Lattner typedef typename SuperClass::size_type size_type; 37663ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 3773feccbaaee2fe639fd089cdb78ad623f662a5796Benjamin Kramerprotected: 378e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner // Default ctor - Initialize to empty. 379e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner explicit SmallVectorImpl(unsigned N) 380e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { 381d91e5f911f5fc840725771d3b27211b9748659e3Chris Lattner } 38263ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 3833feccbaaee2fe639fd089cdb78ad623f662a5796Benjamin Kramerpublic: 384e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner ~SmallVectorImpl() { 385e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner // Destroy the constructed elements in the vector. 386acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(this->begin(), this->end()); 38763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 388e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner // If this wasn't grown from the inline copy, deallocate the old space. 389e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (!this->isSmall()) 390d164d3d9e74aa099ce7ef86ac0724fe504f7c3f9Benjamin Kramer free(this->begin()); 3917f50863e527f5464bd6fcbcd7719f8344f54cb7eChris Lattner } 39263ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 39363ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 394f5e42bfed1726607506b6502166016cb2e41fe32Chris Lattner void clear() { 395acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(this->begin(), this->end()); 396de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner this->EndX = this->BeginX; 397d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 3983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 39957b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner void resize(unsigned N) { 400e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (N < this->size()) { 401e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner this->destroy_range(this->begin()+N, this->end()); 402e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner this->setEnd(this->begin()+N); 403e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner } else if (N > this->size()) { 404e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->capacity() < N) 40599ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(N); 406c05277ea8744adc1ac75541a078d8ebbb04233a6Benjamin Kramer std::uninitialized_fill(this->end(), this->begin()+N, T()); 407e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner this->setEnd(this->begin()+N); 408f5e42bfed1726607506b6502166016cb2e41fe32Chris Lattner } 409f5e42bfed1726607506b6502166016cb2e41fe32Chris Lattner } 4103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 411181c359c9d29be884ca1fd33c0469b1b567bd33cChris Lattner void resize(unsigned N, const T &NV) { 412e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (N < this->size()) { 413acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(this->begin()+N, this->end()); 414acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin()+N); 415e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner } else if (N > this->size()) { 416e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->capacity() < N) 41799ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(N); 418c05277ea8744adc1ac75541a078d8ebbb04233a6Benjamin Kramer std::uninitialized_fill(this->end(), this->begin()+N, NV); 419acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin()+N); 420181c359c9d29be884ca1fd33c0469b1b567bd33cChris Lattner } 421181c359c9d29be884ca1fd33c0469b1b567bd33cChris Lattner } 4223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4230750bec272350cbbf23aa4d43a46785324ee212eChris Lattner void reserve(unsigned N) { 424e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->capacity() < N) 42599ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(N); 4260750bec272350cbbf23aa4d43a46785324ee212eChris Lattner } 42763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 428e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner T pop_back_val() { 4294334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 43038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall T Result = ::std::move(this->back()); 43138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#else 432e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner T Result = this->back(); 43338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 434d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->pop_back(); 435e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner return Result; 436e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner } 43763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 438e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner void swap(SmallVectorImpl &RHS); 43963ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 440825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner /// append - Add the specified range to the end of the SmallVector. 441825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner /// 442825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner template<typename in_iter> 443825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner void append(in_iter in_start, in_iter in_end) { 44434cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng size_type NumInputs = std::distance(in_start, in_end); 445825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner // Grow allocated space if needed. 446e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (NumInputs > size_type(this->capacity_ptr()-this->end())) 44799ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(this->size()+NumInputs); 44863ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 449825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner // Copy the new elements over. 450de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner // TODO: NEED To compile time dispatch on whether in_iter is a random access 451de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner // iterator to use the fast uninitialized_copy. 452e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner std::uninitialized_copy(in_start, in_end, this->end()); 453acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->end() + NumInputs); 454825405c0c1b92c69cea283f97ee829ea3f23e3a4Chris Lattner } 45563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 456254a8860570b2624752b079b4a3e37b0942a888aDan Gohman /// append - Add the specified range to the end of the SmallVector. 457254a8860570b2624752b079b4a3e37b0942a888aDan Gohman /// 458254a8860570b2624752b079b4a3e37b0942a888aDan Gohman void append(size_type NumInputs, const T &Elt) { 459254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Grow allocated space if needed. 460e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (NumInputs > size_type(this->capacity_ptr()-this->end())) 46199ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(this->size()+NumInputs); 46263ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 463254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Copy the new elements over. 464e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner std::uninitialized_fill_n(this->end(), NumInputs, Elt); 465acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->end() + NumInputs); 466254a8860570b2624752b079b4a3e37b0942a888aDan Gohman } 46763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 4681c567b5d92c4babe33d606aa2c2643655fd3a136Chris Lattner void assign(unsigned NumElts, const T &Elt) { 4691c567b5d92c4babe33d606aa2c2643655fd3a136Chris Lattner clear(); 470e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->capacity() < NumElts) 47199ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(NumElts); 472acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin()+NumElts); 473c05277ea8744adc1ac75541a078d8ebbb04233a6Benjamin Kramer std::uninitialized_fill(this->begin(), this->end(), Elt); 4741c567b5d92c4babe33d606aa2c2643655fd3a136Chris Lattner } 47563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 476a022e3fc2f2faec2982ac184c98fee28d85a448aDavid Greene iterator erase(iterator I) { 477e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I >= this->begin() && "Iterator to erase is out of bounds."); 478e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I < this->end() && "Erasing at past-the-end iterator."); 479e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer 480a022e3fc2f2faec2982ac184c98fee28d85a448aDavid Greene iterator N = I; 481d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner // Shift all elts down one. 482d9cff9a25a9d4f2d8d9c1cb4960fb52cb049ef49Benjamin Kramer this->move(I+1, this->end(), I); 483d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner // Drop the last elt. 484d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->pop_back(); 485a022e3fc2f2faec2982ac184c98fee28d85a448aDavid Greene return(N); 486d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 48763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 488a022e3fc2f2faec2982ac184c98fee28d85a448aDavid Greene iterator erase(iterator S, iterator E) { 489e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(S >= this->begin() && "Range to erase is out of bounds."); 490e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(S <= E && "Trying to erase invalid range."); 491e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(E <= this->end() && "Trying to erase past the end."); 492e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer 493a022e3fc2f2faec2982ac184c98fee28d85a448aDavid Greene iterator N = S; 494d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner // Shift all elts down. 495d9cff9a25a9d4f2d8d9c1cb4960fb52cb049ef49Benjamin Kramer iterator I = this->move(E, this->end(), S); 496d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner // Drop the last elts. 497acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(I, this->end()); 498acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(I); 499a022e3fc2f2faec2982ac184c98fee28d85a448aDavid Greene return(N); 500d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 50163ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 5024334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 50338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall iterator insert(iterator I, T &&Elt) { 50438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (I == this->end()) { // Important special case for empty vector. 50538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->push_back(::std::move(Elt)); 50638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return this->end()-1; 50738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 50838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 509e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I >= this->begin() && "Insertion iterator is out of bounds."); 510e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I <= this->end() && "Inserting past the end of the vector."); 511e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer 51238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (this->EndX < this->CapacityX) { 51338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall Retry: 51438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ::new ((void*) this->end()) T(::std::move(this->back())); 51538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->setEnd(this->end()+1); 51638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Push everything else over. 51738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->move_backward(I, this->end()-1, this->end()); 51838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 51938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // If we just moved the element we're inserting, be sure to update 52038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // the reference. 52138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall T *EltPtr = &Elt; 52238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (I <= EltPtr && EltPtr < this->EndX) 52338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ++EltPtr; 52438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 52538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall *I = ::std::move(*EltPtr); 52638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return I; 52738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 52838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall size_t EltNo = I-this->begin(); 52938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->grow(); 53038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall I = this->begin()+EltNo; 53138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall goto Retry; 53238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 53338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 53438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 535d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner iterator insert(iterator I, const T &Elt) { 536e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (I == this->end()) { // Important special case for empty vector. 537d8d110e08ab3fee8d0a2b758c893b7966fd2d3d8Pete Cooper this->push_back(Elt); 538e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner return this->end()-1; 539d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 54063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 541e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I >= this->begin() && "Insertion iterator is out of bounds."); 542e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I <= this->end() && "Inserting past the end of the vector."); 543e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer 544de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner if (this->EndX < this->CapacityX) { 545e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner Retry: 54638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall ::new ((void*) this->end()) T(this->back()); 547e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner this->setEnd(this->end()+1); 548d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner // Push everything else over. 54938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->move_backward(I, this->end()-1, this->end()); 5509cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson 5519cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson // If we just moved the element we're inserting, be sure to update 5529cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson // the reference. 5539cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson const T *EltPtr = &Elt; 5549cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson if (I <= EltPtr && EltPtr < this->EndX) 5559cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson ++EltPtr; 5569cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson 5579cbd7afb76f20ce874464c238764c54f86b3ce3bOwen Anderson *I = *EltPtr; 558d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner return I; 559d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 560e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner size_t EltNo = I-this->begin(); 561e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner this->grow(); 562e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner I = this->begin()+EltNo; 563d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner goto Retry; 564d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 56563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 566254a8860570b2624752b079b4a3e37b0942a888aDan Gohman iterator insert(iterator I, size_type NumToInsert, const T &Elt) { 567d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer // Convert iterator to elt# to avoid invalidating iterator when we reserve() 568d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer size_t InsertElt = I - this->begin(); 569d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer 570e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (I == this->end()) { // Important special case for empty vector. 571254a8860570b2624752b079b4a3e37b0942a888aDan Gohman append(NumToInsert, Elt); 572d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer return this->begin()+InsertElt; 573254a8860570b2624752b079b4a3e37b0942a888aDan Gohman } 57463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 575e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I >= this->begin() && "Insertion iterator is out of bounds."); 576e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I <= this->end() && "Inserting past the end of the vector."); 577e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer 578254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Ensure there is enough space. 579e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner reserve(static_cast<unsigned>(this->size() + NumToInsert)); 58063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 581254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Uninvalidate the iterator. 582e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner I = this->begin()+InsertElt; 58363ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 584dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // If there are more elements between the insertion point and the end of the 585dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // range than there are being inserted, we can use a simple approach to 586dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // insertion. Since we already reserved space, we know that this won't 587dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // reallocate the vector. 588e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (size_t(this->end()-I) >= NumToInsert) { 589e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner T *OldEnd = this->end(); 590e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner append(this->end()-NumToInsert, this->end()); 59163ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 592254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Copy the existing elements that get replaced. 59338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->move_backward(I, OldEnd-NumToInsert, OldEnd); 59463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 595254a8860570b2624752b079b4a3e37b0942a888aDan Gohman std::fill_n(I, NumToInsert, Elt); 596254a8860570b2624752b079b4a3e37b0942a888aDan Gohman return I; 597254a8860570b2624752b079b4a3e37b0942a888aDan Gohman } 59863ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 599254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Otherwise, we're inserting more elements than exist already, and we're 600254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // not inserting at the end. 60163ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 602d9cff9a25a9d4f2d8d9c1cb4960fb52cb049ef49Benjamin Kramer // Move over the elements that we're about to overwrite. 603e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner T *OldEnd = this->end(); 604acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->end() + NumToInsert); 605254a8860570b2624752b079b4a3e37b0942a888aDan Gohman size_t NumOverwritten = OldEnd-I; 606d9cff9a25a9d4f2d8d9c1cb4960fb52cb049ef49Benjamin Kramer this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 60763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 608254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Replace the overwritten part. 609254a8860570b2624752b079b4a3e37b0942a888aDan Gohman std::fill_n(I, NumOverwritten, Elt); 61063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 611254a8860570b2624752b079b4a3e37b0942a888aDan Gohman // Insert the non-overwritten middle part. 612254a8860570b2624752b079b4a3e37b0942a888aDan Gohman std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 613254a8860570b2624752b079b4a3e37b0942a888aDan Gohman return I; 614254a8860570b2624752b079b4a3e37b0942a888aDan Gohman } 61563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 61609b6ac92d855fc0224562bdc06349f986a31926bChris Lattner template<typename ItTy> 61709b6ac92d855fc0224562bdc06349f986a31926bChris Lattner iterator insert(iterator I, ItTy From, ItTy To) { 618d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer // Convert iterator to elt# to avoid invalidating iterator when we reserve() 619d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer size_t InsertElt = I - this->begin(); 620d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer 621e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (I == this->end()) { // Important special case for empty vector. 62209b6ac92d855fc0224562bdc06349f986a31926bChris Lattner append(From, To); 623d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer return this->begin()+InsertElt; 62409b6ac92d855fc0224562bdc06349f986a31926bChris Lattner } 62563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 626e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I >= this->begin() && "Insertion iterator is out of bounds."); 627e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer assert(I <= this->end() && "Inserting past the end of the vector."); 628e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807Benjamin Kramer 62934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng size_t NumToInsert = std::distance(From, To); 63063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 63109b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // Ensure there is enough space. 632e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner reserve(static_cast<unsigned>(this->size() + NumToInsert)); 63363ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 63409b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // Uninvalidate the iterator. 635e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner I = this->begin()+InsertElt; 63663ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 637dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // If there are more elements between the insertion point and the end of the 638dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // range than there are being inserted, we can use a simple approach to 639dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // insertion. Since we already reserved space, we know that this won't 640dae2206390be0b1886cf0c1dba3edf079d28274fChris Lattner // reallocate the vector. 641e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (size_t(this->end()-I) >= NumToInsert) { 642e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner T *OldEnd = this->end(); 643e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner append(this->end()-NumToInsert, this->end()); 64463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 64509b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // Copy the existing elements that get replaced. 64638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->move_backward(I, OldEnd-NumToInsert, OldEnd); 64763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 64809b6ac92d855fc0224562bdc06349f986a31926bChris Lattner std::copy(From, To, I); 64909b6ac92d855fc0224562bdc06349f986a31926bChris Lattner return I; 65009b6ac92d855fc0224562bdc06349f986a31926bChris Lattner } 65163ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 65209b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // Otherwise, we're inserting more elements than exist already, and we're 65309b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // not inserting at the end. 65463ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 655d9cff9a25a9d4f2d8d9c1cb4960fb52cb049ef49Benjamin Kramer // Move over the elements that we're about to overwrite. 656e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner T *OldEnd = this->end(); 657b63bb1615b44bc9e18dec68660d33c04401987b6Chris Lattner this->setEnd(this->end() + NumToInsert); 65834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng size_t NumOverwritten = OldEnd-I; 659d9cff9a25a9d4f2d8d9c1cb4960fb52cb049ef49Benjamin Kramer this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 66063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 66109b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // Replace the overwritten part. 662d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer for (T *J = I; NumOverwritten > 0; --NumOverwritten) { 663d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer *J = *From; 664d45f7b6b5dd36b4732dff82ab7c8a856a7b36ae0Benjamin Kramer ++J; ++From; 665a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman } 66663ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 66709b6ac92d855fc0224562bdc06349f986a31926bChris Lattner // Insert the non-overwritten middle part. 668a7a33fd95f15428b7030ef1b764fcf924d5199c8Dan Gohman this->uninitialized_copy(From, To, OldEnd); 66909b6ac92d855fc0224562bdc06349f986a31926bChris Lattner return I; 67009b6ac92d855fc0224562bdc06349f986a31926bChris Lattner } 67163ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 67238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall SmallVectorImpl &operator=(const SmallVectorImpl &RHS); 67338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 6744334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 67538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall SmallVectorImpl &operator=(SmallVectorImpl &&RHS); 67638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 67763ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 678e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner bool operator==(const SmallVectorImpl &RHS) const { 679e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->size() != RHS.size()) return false; 680e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner return std::equal(this->begin(), this->end(), RHS.begin()); 6818874628e30a327afe91648c84bfa1e2dd13f0dbaChris Lattner } 682e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner bool operator!=(const SmallVectorImpl &RHS) const { 683de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner return !(*this == RHS); 684de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner } 68563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 686e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner bool operator<(const SmallVectorImpl &RHS) const { 687e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner return std::lexicographical_compare(this->begin(), this->end(), 68811bf2ace556da018c65163557fb97704b1cf88e4Dan Gohman RHS.begin(), RHS.end()); 68911bf2ace556da018c65163557fb97704b1cf88e4Dan Gohman } 69063ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 6912d9eb72178af8e79dc6432cd1b7d29bde16da1b9Dmitri Gribenko /// Set the array size to \p N, which the current array must have enough 6922d9eb72178af8e79dc6432cd1b7d29bde16da1b9Dmitri Gribenko /// capacity for. 693c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// 694c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// This does not construct or destroy any elements in the vector. 695c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// 696c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// Clients can use this in conjunction with capacity() to write past the end 697c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// of the buffer when they know that more elements are available, and only 698c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// update the size later. This avoids the cost of value initializing elements 699c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar /// which will only be overwritten. 700c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar void set_size(unsigned N) { 701e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner assert(N <= this->capacity()); 702acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin() + N); 703c2da6fb3e50902daf670fe83b8b017a2bcba05dfDaniel Dunbar } 7041653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner}; 70563ef367954c0981ec221f183fc0808ba21cb678dJim Grosbach 706f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner 70757b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattnertemplate <typename T> 708e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattnervoid SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 70957b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner if (this == &RHS) return; 7103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 71157b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner // We can only avoid copying elements if neither vector is small. 712de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner if (!this->isSmall() && !RHS.isSmall()) { 713de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner std::swap(this->BeginX, RHS.BeginX); 714de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner std::swap(this->EndX, RHS.EndX); 715de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner std::swap(this->CapacityX, RHS.CapacityX); 71657b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner return; 71757b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner } 718e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (RHS.size() > this->capacity()) 71999ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(RHS.size()); 720e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->size() > RHS.capacity()) 721e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner RHS.grow(this->size()); 7223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 72357b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner // Swap the shared elements. 724e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner size_t NumShared = this->size(); 72557b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner if (NumShared > RHS.size()) NumShared = RHS.size(); 72634cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i) 72710aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner std::swap((*this)[i], RHS[i]); 7283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 72957b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner // Copy over the extra elts. 730e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->size() > RHS.size()) { 731e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner size_t EltDiff = this->size() - RHS.size(); 732acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); 73310aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner RHS.setEnd(RHS.end()+EltDiff); 734acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(this->begin()+NumShared, this->end()); 735acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin()+NumShared); 736e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner } else if (RHS.size() > this->size()) { 737e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner size_t EltDiff = RHS.size() - this->size(); 738acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); 739acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->end() + EltDiff); 740acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(RHS.begin()+NumShared, RHS.end()); 74110aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner RHS.setEnd(RHS.begin()+NumShared); 74257b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner } 74357b79795b37b367d69d58ad10f25e997b4f55ce9Chris Lattner} 7443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7451653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattnertemplate <typename T> 74638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCallSmallVectorImpl<T> &SmallVectorImpl<T>:: 747e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner operator=(const SmallVectorImpl<T> &RHS) { 7481653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Avoid self-assignment. 7491653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner if (this == &RHS) return *this; 7503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7511653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // If we already have sufficient space, assign the common elements, then 7521653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // destroy any excess. 75310aaf05c304e259dbb853a37d491fdc4ea54c9b1Chris Lattner size_t RHSSize = RHS.size(); 754e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner size_t CurSize = this->size(); 7551653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner if (CurSize >= RHSSize) { 7561653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Assign common elements. 7574f155b4c8597f40a79add430dfedb2c08ba28375Chris Lattner iterator NewEnd; 7584f155b4c8597f40a79add430dfedb2c08ba28375Chris Lattner if (RHSSize) 759e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); 7604f155b4c8597f40a79add430dfedb2c08ba28375Chris Lattner else 761e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner NewEnd = this->begin(); 7623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7631653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Destroy excess elements. 764acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(NewEnd, this->end()); 7653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7661653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Trim. 767acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(NewEnd); 7681653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner return *this; 7691653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner } 7703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7711653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // If we have to grow to have enough elements, destroy the current elements. 7721653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // This allows us to avoid copying them during the grow. 77338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // FIXME: don't do this if they're efficiently moveable. 774e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner if (this->capacity() < RHSSize) { 7751653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Destroy current elements. 776acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->destroy_range(this->begin(), this->end()); 777acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin()); 7781653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner CurSize = 0; 77999ea87a48a3a891dbf5f4cb89179610a5f3f84cfChris Lattner this->grow(RHSSize); 7801653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner } else if (CurSize) { 7811653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Otherwise, use assignment for the already-constructed elements. 782e6e55d79592fa0926175d6b17e3db89b298ada4eChris Lattner std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); 783f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner } 7843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7851653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Copy construct the new elements in place. 786acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), 787acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->begin()+CurSize); 7883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7891653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner // Set end. 790acf8723b8e531e64abd3be61b4f34e7700c6028dChris Lattner this->setEnd(this->begin()+RHSSize); 79167b7ff9ede110999f3a37f22c24bdf00a405a78aChris Lattner return *this; 7921653366010ce0c69fdb0fac7c08cc7ca5668bd84Chris Lattner} 7933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 7944334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 79538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCalltemplate <typename T> 79638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCallSmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { 79738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Avoid self-assignment. 79838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (this == &RHS) return *this; 79938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 80038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // If the RHS isn't small, clear this vector and then steal its buffer. 80138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (!RHS.isSmall()) { 80238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->destroy_range(this->begin(), this->end()); 80338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (!this->isSmall()) free(this->begin()); 80438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->BeginX = RHS.BeginX; 80538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->EndX = RHS.EndX; 80638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->CapacityX = RHS.CapacityX; 80738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall RHS.resetToSmall(); 80838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return *this; 80938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 81038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 81138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // If we already have sufficient space, assign the common elements, then 81238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // destroy any excess. 81338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall size_t RHSSize = RHS.size(); 81438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall size_t CurSize = this->size(); 81538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (CurSize >= RHSSize) { 81638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Assign common elements. 81738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall iterator NewEnd = this->begin(); 81838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (RHSSize) 81938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd); 82038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 82138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Destroy excess elements and trim the bounds. 82238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->destroy_range(NewEnd, this->end()); 82338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->setEnd(NewEnd); 82438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 82538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Clear the RHS. 82638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall RHS.clear(); 82738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 82838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return *this; 82938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 83038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 83138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // If we have to grow to have enough elements, destroy the current elements. 83238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // This allows us to avoid copying them during the grow. 83338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // FIXME: this may not actually make any sense if we can efficiently move 83438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // elements. 83538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (this->capacity() < RHSSize) { 83638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Destroy current elements. 83738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->destroy_range(this->begin(), this->end()); 83838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->setEnd(this->begin()); 83938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall CurSize = 0; 84038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->grow(RHSSize); 84138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } else if (CurSize) { 84238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Otherwise, use assignment for the already-constructed elements. 84338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->move(RHS.begin(), RHS.end(), this->begin()); 84438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 84538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 84638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Move-construct the new elements in place. 84738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), 84838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->begin()+CurSize); 84938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 85038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall // Set end. 85138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall this->setEnd(this->begin()+RHSSize); 85238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 85338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall RHS.clear(); 85438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return *this; 85538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall} 85638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 857de576fa579b4b3077a3c315d6507f13ab71d61abChris Lattner 858bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// Storage for the SmallVector elements which aren't contained in 859bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1' 860bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// element is in the base class. This is specialized for the N=1 and N=0 cases 861bc363931085587bac42a40653962a3e5acd1ffceRichard Smith/// to avoid allocating unnecessary storage. 862bc363931085587bac42a40653962a3e5acd1ffceRichard Smithtemplate <typename T, unsigned N> 863bc363931085587bac42a40653962a3e5acd1ffceRichard Smithstruct SmallVectorStorage { 864bc363931085587bac42a40653962a3e5acd1ffceRichard Smith typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1]; 865bc363931085587bac42a40653962a3e5acd1ffceRichard Smith}; 866bc363931085587bac42a40653962a3e5acd1ffceRichard Smithtemplate <typename T> struct SmallVectorStorage<T, 1> {}; 867bc363931085587bac42a40653962a3e5acd1ffceRichard Smithtemplate <typename T> struct SmallVectorStorage<T, 0> {}; 868bc363931085587bac42a40653962a3e5acd1ffceRichard Smith 86980b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized 87080b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// for the case when the array is small. It contains some number of elements 87180b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// in-place, which allows it to avoid heap allocation when the actual number of 87280b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// elements is below that threshold. This allows normal "small" cases to be 87380b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// fast without losing generality for large inputs. 87480b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// 87580b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// Note that this does not attempt to be exception safe. 87680b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner/// 87780b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattnertemplate <typename T, unsigned N> 87880b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattnerclass SmallVector : public SmallVectorImpl<T> { 879bc363931085587bac42a40653962a3e5acd1ffceRichard Smith /// Storage - Inline space for elements which aren't stored in the base class. 880bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVectorStorage<T, N> Storage; 8813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpublic: 882bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVector() : SmallVectorImpl<T>(N) { 88380b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner } 8843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 88559310c3dc0061a0fd6842c66ac3215fbbdfe4ae4Dan Gohman explicit SmallVector(unsigned Size, const T &Value = T()) 886bc363931085587bac42a40653962a3e5acd1ffceRichard Smith : SmallVectorImpl<T>(N) { 887b25e44ec1506cd42ab676ac7ddf8dc8f228bcadaBenjamin Kramer this->assign(Size, Value); 888af3e4d4bee2519962fb1f5dabece364df522f508Chris Lattner } 8893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 89080b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner template<typename ItTy> 891bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { 892c1edbfc2bac278ef050615f403c1bc74ef44cf14Cedric Venet this->append(S, E); 89380b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner } 8943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 895bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { 896e49e52d85601e8f732da16ca21e3de6cefd20158Chris Lattner if (!RHS.empty()) 897c1edbfc2bac278ef050615f403c1bc74ef44cf14Cedric Venet SmallVectorImpl<T>::operator=(RHS); 898e49e52d85601e8f732da16ca21e3de6cefd20158Chris Lattner } 899e49e52d85601e8f732da16ca21e3de6cefd20158Chris Lattner 900d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner const SmallVector &operator=(const SmallVector &RHS) { 901d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner SmallVectorImpl<T>::operator=(RHS); 902d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner return *this; 903d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 9043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9054334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 906bc363931085587bac42a40653962a3e5acd1ffceRichard Smith SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { 90738dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall if (!RHS.empty()) 90838dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall SmallVectorImpl<T>::operator=(::std::move(RHS)); 90938dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 91038dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 91138dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall const SmallVector &operator=(SmallVector &&RHS) { 91238dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall SmallVectorImpl<T>::operator=(::std::move(RHS)); 91338dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall return *this; 91438dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall } 91538dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall#endif 91638dbb606755232e229f11994fc2bbf10e8c5788bJohn McCall 91780b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner}; 91880b65823147ba498efd9a5df72afc7ff7d9dc0d9Chris Lattner 91918dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenektemplate<typename T, unsigned N> 92018dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { 92118dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.capacity_in_bytes(); 92218dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 92318dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek 924f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner} // End llvm namespace 925f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner 926d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattnernamespace std { 927d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner /// Implement std::swap in terms of SmallVector swap. 928d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner template<typename T> 929d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner inline void 930d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 931d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner LHS.swap(RHS); 932d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 9333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 934d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner /// Implement std::swap in terms of SmallVector swap. 935d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner template<typename T, unsigned N> 936d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner inline void 937d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 938d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner LHS.swap(RHS); 939d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner } 940d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner} 941d6007d607641b6dae3511b8ebc1d752ff327aed0Chris Lattner 942f28265402130eb03762d9a6333fd8f87765a8875Chris Lattner#endif 943