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