Use std::copy instead of custom loops to take advantage of STL optimizations.
[oota-llvm.git] / include / llvm / ADT / SmallVector.h
1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by Chris Lattner and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the SmallVector class.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_ADT_SMALLVECTOR_H
15 #define LLVM_ADT_SMALLVECTOR_H
16
17 #include <algorithm>
18 #include <cassert>
19 #include <iterator>
20 #include <memory>
21
22 namespace llvm {
23
24 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
25 /// for the case when the array is small.  It contains some number of elements
26 /// in-place, which allows it to avoid heap allocation when the actual number of
27 /// elements is below that threshold.  This allows normal "small" cases to be
28 /// fast without losing generality for large inputs.
29 ///
30 /// Note that this does not attempt to be exception safe.
31 ///
32 template <typename T, unsigned N>
33 class SmallVector {
34   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
35   // don't want it to be automatically run, so we need to represent the space as
36   // something else.  An array of char would work great, but might not be
37   // aligned sufficiently.  Instead, we either use GCC extensions, or some
38   // number of union instances for the space, which guarantee maximal alignment.
39   union U {
40     double D;
41     long double LD;
42     long long L;
43     void *P;
44   };
45   
46   /// InlineElts - These are the 'N' elements that are stored inline in the body
47   /// of the vector
48   U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U)];
49   T *Begin, *End, *Capacity;
50 public:
51   // Default ctor - Initialize to empty.
52   SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) {
53   }
54   
55   SmallVector(const SmallVector &RHS) {
56     unsigned RHSSize = RHS.size();
57     Begin = (T*)InlineElts;
58
59     // Doesn't fit in the small case?  Allocate space.
60     if (RHSSize > N) {
61       End = Capacity = Begin;
62       grow(RHSSize);
63     }
64     End = Begin+RHSSize;
65     Capacity = Begin+N;
66     std::uninitialized_copy(RHS.begin(), RHS.end(), Begin);
67   }
68   ~SmallVector() {
69     // If this wasn't grown from the inline copy, deallocate the old space.
70     if ((void*)Begin != (void*)InlineElts)
71       delete[] (char*)Begin;
72   }
73   
74   typedef size_t size_type;
75   typedef T* iterator;
76   typedef const T* const_iterator;
77   typedef T& reference;
78   typedef const T& const_reference;
79
80   bool empty() const { return Begin == End; }
81   size_type size() const { return End-Begin; }
82   
83   iterator begin() { return Begin; }
84   const_iterator begin() const { return Begin; }
85
86   iterator end() { return End; }
87   const_iterator end() const { return End; }
88   
89   reference operator[](unsigned idx) {
90     assert(idx < size() && "out of range reference!");
91     return Begin[idx];
92   }
93   const_reference operator[](unsigned idx) const {
94     assert(idx < size() && "out of range reference!");
95     return Begin[idx];
96   }
97   
98   reference back() {
99     assert(!empty() && "SmallVector is empty!");
100     return end()[-1];
101   }
102   const_reference back() const {
103     assert(!empty() && "SmallVector is empty!");
104     return end()[-1];
105   }
106   
107   void push_back(const_reference Elt) {
108     if (End < Capacity) {
109   Retry:
110       new (End) T(Elt);
111       ++End;
112       return;
113     }
114     grow();
115     goto Retry;
116   }
117   
118   /// append - Add the specified range to the end of the SmallVector.
119   ///
120   template<typename in_iter>
121   void append(in_iter in_start, in_iter in_end) {
122     unsigned NumInputs = std::distance(in_start, in_end);
123     // Grow allocated space if needed.
124     if (End+NumInputs > Capacity)
125       grow(size()+NumInputs);
126
127     // Copy the new elements over.
128     std::uninitialized_copy(in_start, in_end, End);
129     End += NumInputs;
130   }
131   
132   const SmallVector &operator=(const SmallVector &RHS) {
133     // Avoid self-assignment.
134     if (this == &RHS) return *this;
135     
136     // If we already have sufficient space, assign the common elements, then
137     // destroy any excess.
138     unsigned RHSSize = RHS.size();
139     unsigned CurSize = size();
140     if (CurSize >= RHSSize) {
141       // Assign common elements.
142       std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
143       
144       // Destroy excess elements.
145       for (unsigned i = RHSSize; i != CurSize; ++i)
146         Begin[i].~T();
147       
148       // Trim.
149       End = Begin + RHSSize;
150       return *this;
151     }
152     
153     // If we have to grow to have enough elements, destroy the current elements.
154     // This allows us to avoid copying them during the grow.
155     if (Capacity-Begin < RHSSize) {
156       // Destroy current elements.
157       for (T *I = Begin, E = End; I != E; ++I)
158         I->~T();
159       End = Begin;
160       CurSize = 0;
161       grow(RHSSize);
162     } else if (CurSize) {
163       // Otherwise, use assignment for the already-constructed elements.
164       std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
165     }
166     
167     // Copy construct the new elements in place.
168     std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
169     
170     // Set end.
171     End = Begin+RHSSize;
172   }
173   
174 private:
175   /// isSmall - Return true if this is a smallvector which has not had dynamic
176   /// memory allocated for it.
177   bool isSmall() const {
178     return (void*)Begin == (void*)InlineElts;
179   }
180
181   /// grow - double the size of the allocated memory, guaranteeing space for at
182   /// least one more element or MinSize if specified.
183   void grow(unsigned MinSize = 0) {
184     unsigned CurCapacity = Capacity-Begin;
185     unsigned CurSize = size();
186     unsigned NewCapacity = 2*CurCapacity;
187     if (NewCapacity < MinSize)
188       NewCapacity = MinSize;
189     T *NewElts = reinterpret_cast<T*>(new char[NewCapacity*sizeof(T)]);
190
191     // Copy the elements over.
192     std::uninitialized_copy(Begin, End, NewElts);
193     
194     // Destroy the original elements.
195     for (T *I = Begin, *E = End; I != E; ++I)
196       I->~T();
197     
198     // If this wasn't grown from the inline copy, deallocate the old space.
199     if (!isSmall())
200       delete[] (char*)Begin;
201     
202     Begin = NewElts;
203     End = NewElts+CurSize;
204     Capacity = Begin+NewCapacity*2;
205   }
206 };
207
208 } // End llvm namespace
209
210 #endif