LLVM API Documentation
00001 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the SmallVector class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ADT_SMALLVECTOR_H 00015 #define LLVM_ADT_SMALLVECTOR_H 00016 00017 #include "llvm/ADT/iterator.h" 00018 #include "llvm/Support/type_traits.h" 00019 #include <algorithm> 00020 #include <cassert> 00021 #include <cstring> 00022 #include <memory> 00023 00024 #ifdef _MSC_VER 00025 namespace std { 00026 #if _MSC_VER <= 1310 00027 // Work around flawed VC++ implementation of std::uninitialized_copy. Define 00028 // additional overloads so that elements with pointer types are recognized as 00029 // scalars and not objects, causing bizarre type conversion errors. 00030 template<class T1, class T2> 00031 inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { 00032 _Scalar_ptr_iterator_tag _Cat; 00033 return _Cat; 00034 } 00035 00036 template<class T1, class T2> 00037 inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { 00038 _Scalar_ptr_iterator_tag _Cat; 00039 return _Cat; 00040 } 00041 #else 00042 // FIXME: It is not clear if the problem is fixed in VS 2005. What is clear 00043 // is that the above hack won't work if it wasn't fixed. 00044 #endif 00045 } 00046 #endif 00047 00048 namespace llvm { 00049 00050 /// SmallVectorImpl - This class consists of common code factored out of the 00051 /// SmallVector class to reduce code duplication based on the SmallVector 'N' 00052 /// template parameter. 00053 template <typename T> 00054 class SmallVectorImpl { 00055 protected: 00056 T *Begin, *End, *Capacity; 00057 00058 // Allocate raw space for N elements of type T. If T has a ctor or dtor, we 00059 // don't want it to be automatically run, so we need to represent the space as 00060 // something else. An array of char would work great, but might not be 00061 // aligned sufficiently. Instead, we either use GCC extensions, or some 00062 // number of union instances for the space, which guarantee maximal alignment. 00063 protected: 00064 #ifdef __GNUC__ 00065 typedef char U; 00066 U FirstEl __attribute__((aligned)); 00067 #else 00068 union U { 00069 double D; 00070 long double LD; 00071 long long L; 00072 void *P; 00073 } FirstEl; 00074 #endif 00075 // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 00076 public: 00077 // Default ctor - Initialize to empty. 00078 explicit SmallVectorImpl(unsigned N) 00079 : Begin(reinterpret_cast<T*>(&FirstEl)), 00080 End(reinterpret_cast<T*>(&FirstEl)), 00081 Capacity(reinterpret_cast<T*>(&FirstEl)+N) { 00082 } 00083 00084 ~SmallVectorImpl() { 00085 // Destroy the constructed elements in the vector. 00086 destroy_range(Begin, End); 00087 00088 // If this wasn't grown from the inline copy, deallocate the old space. 00089 if (!isSmall()) 00090 operator delete(Begin); 00091 } 00092 00093 typedef size_t size_type; 00094 typedef ptrdiff_t difference_type; 00095 typedef T value_type; 00096 typedef T* iterator; 00097 typedef const T* const_iterator; 00098 00099 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00100 typedef std::reverse_iterator<iterator> reverse_iterator; 00101 00102 typedef T& reference; 00103 typedef const T& const_reference; 00104 typedef T* pointer; 00105 typedef const T* const_pointer; 00106 00107 bool empty() const { return Begin == End; } 00108 size_type size() const { return End-Begin; } 00109 size_type max_size() const { return size_type(-1) / sizeof(T); } 00110 00111 // forward iterator creation methods. 00112 iterator begin() { return Begin; } 00113 const_iterator begin() const { return Begin; } 00114 iterator end() { return End; } 00115 const_iterator end() const { return End; } 00116 00117 // reverse iterator creation methods. 00118 reverse_iterator rbegin() { return reverse_iterator(end()); } 00119 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 00120 reverse_iterator rend() { return reverse_iterator(begin()); } 00121 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 00122 00123 00124 reference operator[](unsigned idx) { 00125 assert(Begin + idx < End); 00126 return Begin[idx]; 00127 } 00128 const_reference operator[](unsigned idx) const { 00129 assert(Begin + idx < End); 00130 return Begin[idx]; 00131 } 00132 00133 reference front() { 00134 return begin()[0]; 00135 } 00136 const_reference front() const { 00137 return begin()[0]; 00138 } 00139 00140 reference back() { 00141 return end()[-1]; 00142 } 00143 const_reference back() const { 00144 return end()[-1]; 00145 } 00146 00147 void push_back(const_reference Elt) { 00148 if (End < Capacity) { 00149 Retry: 00150 new (End) T(Elt); 00151 ++End; 00152 return; 00153 } 00154 grow(); 00155 goto Retry; 00156 } 00157 00158 void pop_back() { 00159 --End; 00160 End->~T(); 00161 } 00162 00163 T pop_back_val() { 00164 T Result = back(); 00165 pop_back(); 00166 return Result; 00167 } 00168 00169 void clear() { 00170 destroy_range(Begin, End); 00171 End = Begin; 00172 } 00173 00174 void resize(unsigned N) { 00175 if (N < size()) { 00176 destroy_range(Begin+N, End); 00177 End = Begin+N; 00178 } else if (N > size()) { 00179 if (unsigned(Capacity-Begin) < N) 00180 grow(N); 00181 construct_range(End, Begin+N, T()); 00182 End = Begin+N; 00183 } 00184 } 00185 00186 void resize(unsigned N, const T &NV) { 00187 if (N < size()) { 00188 destroy_range(Begin+N, End); 00189 End = Begin+N; 00190 } else if (N > size()) { 00191 if (unsigned(Capacity-Begin) < N) 00192 grow(N); 00193 construct_range(End, Begin+N, NV); 00194 End = Begin+N; 00195 } 00196 } 00197 00198 void reserve(unsigned N) { 00199 if (unsigned(Capacity-Begin) < N) 00200 grow(N); 00201 } 00202 00203 void swap(SmallVectorImpl &RHS); 00204 00205 /// append - Add the specified range to the end of the SmallVector. 00206 /// 00207 template<typename in_iter> 00208 void append(in_iter in_start, in_iter in_end) { 00209 size_type NumInputs = std::distance(in_start, in_end); 00210 // Grow allocated space if needed. 00211 if (NumInputs > size_type(Capacity-End)) 00212 grow(size()+NumInputs); 00213 00214 // Copy the new elements over. 00215 std::uninitialized_copy(in_start, in_end, End); 00216 End += NumInputs; 00217 } 00218 00219 /// append - Add the specified range to the end of the SmallVector. 00220 /// 00221 void append(size_type NumInputs, const T &Elt) { 00222 // Grow allocated space if needed. 00223 if (NumInputs > size_type(Capacity-End)) 00224 grow(size()+NumInputs); 00225 00226 // Copy the new elements over. 00227 std::uninitialized_fill_n(End, NumInputs, Elt); 00228 End += NumInputs; 00229 } 00230 00231 void assign(unsigned NumElts, const T &Elt) { 00232 clear(); 00233 if (unsigned(Capacity-Begin) < NumElts) 00234 grow(NumElts); 00235 End = Begin+NumElts; 00236 construct_range(Begin, End, Elt); 00237 } 00238 00239 iterator erase(iterator I) { 00240 iterator N = I; 00241 // Shift all elts down one. 00242 std::copy(I+1, End, I); 00243 // Drop the last elt. 00244 pop_back(); 00245 return(N); 00246 } 00247 00248 iterator erase(iterator S, iterator E) { 00249 iterator N = S; 00250 // Shift all elts down. 00251 iterator I = std::copy(E, End, S); 00252 // Drop the last elts. 00253 destroy_range(I, End); 00254 End = I; 00255 return(N); 00256 } 00257 00258 iterator insert(iterator I, const T &Elt) { 00259 if (I == End) { // Important special case for empty vector. 00260 push_back(Elt); 00261 return end()-1; 00262 } 00263 00264 if (End < Capacity) { 00265 Retry: 00266 new (End) T(back()); 00267 ++End; 00268 // Push everything else over. 00269 std::copy_backward(I, End-1, End); 00270 *I = Elt; 00271 return I; 00272 } 00273 size_t EltNo = I-Begin; 00274 grow(); 00275 I = Begin+EltNo; 00276 goto Retry; 00277 } 00278 00279 iterator insert(iterator I, size_type NumToInsert, const T &Elt) { 00280 if (I == End) { // Important special case for empty vector. 00281 append(NumToInsert, Elt); 00282 return end()-1; 00283 } 00284 00285 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 00286 size_t InsertElt = I-begin(); 00287 00288 // Ensure there is enough space. 00289 reserve(static_cast<unsigned>(size() + NumToInsert)); 00290 00291 // Uninvalidate the iterator. 00292 I = begin()+InsertElt; 00293 00294 // If there are more elements between the insertion point and the end of the 00295 // range than there are being inserted, we can use a simple approach to 00296 // insertion. Since we already reserved space, we know that this won't 00297 // reallocate the vector. 00298 if (size_t(end()-I) >= NumToInsert) { 00299 T *OldEnd = End; 00300 append(End-NumToInsert, End); 00301 00302 // Copy the existing elements that get replaced. 00303 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 00304 00305 std::fill_n(I, NumToInsert, Elt); 00306 return I; 00307 } 00308 00309 // Otherwise, we're inserting more elements than exist already, and we're 00310 // not inserting at the end. 00311 00312 // Copy over the elements that we're about to overwrite. 00313 T *OldEnd = End; 00314 End += NumToInsert; 00315 size_t NumOverwritten = OldEnd-I; 00316 std::uninitialized_copy(I, OldEnd, End-NumOverwritten); 00317 00318 // Replace the overwritten part. 00319 std::fill_n(I, NumOverwritten, Elt); 00320 00321 // Insert the non-overwritten middle part. 00322 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 00323 return I; 00324 } 00325 00326 template<typename ItTy> 00327 iterator insert(iterator I, ItTy From, ItTy To) { 00328 if (I == End) { // Important special case for empty vector. 00329 append(From, To); 00330 return end()-1; 00331 } 00332 00333 size_t NumToInsert = std::distance(From, To); 00334 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 00335 size_t InsertElt = I-begin(); 00336 00337 // Ensure there is enough space. 00338 reserve(static_cast<unsigned>(size() + NumToInsert)); 00339 00340 // Uninvalidate the iterator. 00341 I = begin()+InsertElt; 00342 00343 // If there are more elements between the insertion point and the end of the 00344 // range than there are being inserted, we can use a simple approach to 00345 // insertion. Since we already reserved space, we know that this won't 00346 // reallocate the vector. 00347 if (size_t(end()-I) >= NumToInsert) { 00348 T *OldEnd = End; 00349 append(End-NumToInsert, End); 00350 00351 // Copy the existing elements that get replaced. 00352 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 00353 00354 std::copy(From, To, I); 00355 return I; 00356 } 00357 00358 // Otherwise, we're inserting more elements than exist already, and we're 00359 // not inserting at the end. 00360 00361 // Copy over the elements that we're about to overwrite. 00362 T *OldEnd = End; 00363 End += NumToInsert; 00364 size_t NumOverwritten = OldEnd-I; 00365 std::uninitialized_copy(I, OldEnd, End-NumOverwritten); 00366 00367 // Replace the overwritten part. 00368 std::copy(From, From+NumOverwritten, I); 00369 00370 // Insert the non-overwritten middle part. 00371 std::uninitialized_copy(From+NumOverwritten, To, OldEnd); 00372 return I; 00373 } 00374 00375 /// data - Return a pointer to the vector's buffer, even if empty(). 00376 pointer data() { 00377 return pointer(Begin); 00378 } 00379 00380 /// data - Return a pointer to the vector's buffer, even if empty(). 00381 const_pointer data() const { 00382 return const_pointer(Begin); 00383 } 00384 00385 const SmallVectorImpl &operator=(const SmallVectorImpl &RHS); 00386 00387 bool operator==(const SmallVectorImpl &RHS) const { 00388 if (size() != RHS.size()) return false; 00389 for (T *This = Begin, *That = RHS.Begin, *E = Begin+size(); 00390 This != E; ++This, ++That) 00391 if (*This != *That) 00392 return false; 00393 return true; 00394 } 00395 bool operator!=(const SmallVectorImpl &RHS) const { return !(*this == RHS); } 00396 00397 bool operator<(const SmallVectorImpl &RHS) const { 00398 return std::lexicographical_compare(begin(), end(), 00399 RHS.begin(), RHS.end()); 00400 } 00401 00402 /// capacity - Return the total number of elements in the currently allocated 00403 /// buffer. 00404 size_t capacity() const { return Capacity - Begin; } 00405 00406 /// set_size - Set the array size to \arg N, which the current array must have 00407 /// enough capacity for. 00408 /// 00409 /// This does not construct or destroy any elements in the vector. 00410 /// 00411 /// Clients can use this in conjunction with capacity() to write past the end 00412 /// of the buffer when they know that more elements are available, and only 00413 /// update the size later. This avoids the cost of value initializing elements 00414 /// which will only be overwritten. 00415 void set_size(unsigned N) { 00416 assert(N <= capacity()); 00417 End = Begin + N; 00418 } 00419 00420 private: 00421 /// isSmall - Return true if this is a smallvector which has not had dynamic 00422 /// memory allocated for it. 00423 bool isSmall() const { 00424 return static_cast<const void*>(Begin) == 00425 static_cast<const void*>(&FirstEl); 00426 } 00427 00428 /// grow - double the size of the allocated memory, guaranteeing space for at 00429 /// least one more element or MinSize if specified. 00430 void grow(size_type MinSize = 0); 00431 00432 void construct_range(T *S, T *E, const T &Elt) { 00433 for (; S != E; ++S) 00434 new (S) T(Elt); 00435 } 00436 00437 void destroy_range(T *S, T *E) { 00438 while (S != E) { 00439 --E; 00440 E->~T(); 00441 } 00442 } 00443 }; 00444 00445 // Define this out-of-line to dissuade the C++ compiler from inlining it. 00446 template <typename T> 00447 void SmallVectorImpl<T>::grow(size_t MinSize) { 00448 size_t CurCapacity = Capacity-Begin; 00449 size_t CurSize = size(); 00450 size_t NewCapacity = 2*CurCapacity; 00451 if (NewCapacity < MinSize) 00452 NewCapacity = MinSize; 00453 T *NewElts = static_cast<T*>(operator new(NewCapacity*sizeof(T))); 00454 00455 // Copy the elements over. 00456 if (is_class<T>::value) 00457 std::uninitialized_copy(Begin, End, NewElts); 00458 else 00459 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 00460 memcpy(NewElts, Begin, CurSize * sizeof(T)); 00461 00462 // Destroy the original elements. 00463 destroy_range(Begin, End); 00464 00465 // If this wasn't grown from the inline copy, deallocate the old space. 00466 if (!isSmall()) 00467 operator delete(Begin); 00468 00469 Begin = NewElts; 00470 End = NewElts+CurSize; 00471 Capacity = Begin+NewCapacity; 00472 } 00473 00474 template <typename T> 00475 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 00476 if (this == &RHS) return; 00477 00478 // We can only avoid copying elements if neither vector is small. 00479 if (!isSmall() && !RHS.isSmall()) { 00480 std::swap(Begin, RHS.Begin); 00481 std::swap(End, RHS.End); 00482 std::swap(Capacity, RHS.Capacity); 00483 return; 00484 } 00485 if (RHS.size() > size_type(Capacity-Begin)) 00486 grow(RHS.size()); 00487 if (size() > size_type(RHS.Capacity-RHS.begin())) 00488 RHS.grow(size()); 00489 00490 // Swap the shared elements. 00491 size_t NumShared = size(); 00492 if (NumShared > RHS.size()) NumShared = RHS.size(); 00493 for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i) 00494 std::swap(Begin[i], RHS[i]); 00495 00496 // Copy over the extra elts. 00497 if (size() > RHS.size()) { 00498 size_t EltDiff = size() - RHS.size(); 00499 std::uninitialized_copy(Begin+NumShared, End, RHS.End); 00500 RHS.End += EltDiff; 00501 destroy_range(Begin+NumShared, End); 00502 End = Begin+NumShared; 00503 } else if (RHS.size() > size()) { 00504 size_t EltDiff = RHS.size() - size(); 00505 std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End); 00506 End += EltDiff; 00507 destroy_range(RHS.Begin+NumShared, RHS.End); 00508 RHS.End = RHS.Begin+NumShared; 00509 } 00510 } 00511 00512 template <typename T> 00513 const SmallVectorImpl<T> & 00514 SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) { 00515 // Avoid self-assignment. 00516 if (this == &RHS) return *this; 00517 00518 // If we already have sufficient space, assign the common elements, then 00519 // destroy any excess. 00520 unsigned RHSSize = unsigned(RHS.size()); 00521 unsigned CurSize = unsigned(size()); 00522 if (CurSize >= RHSSize) { 00523 // Assign common elements. 00524 iterator NewEnd; 00525 if (RHSSize) 00526 NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); 00527 else 00528 NewEnd = Begin; 00529 00530 // Destroy excess elements. 00531 destroy_range(NewEnd, End); 00532 00533 // Trim. 00534 End = NewEnd; 00535 return *this; 00536 } 00537 00538 // If we have to grow to have enough elements, destroy the current elements. 00539 // This allows us to avoid copying them during the grow. 00540 if (unsigned(Capacity-Begin) < RHSSize) { 00541 // Destroy current elements. 00542 destroy_range(Begin, End); 00543 End = Begin; 00544 CurSize = 0; 00545 grow(RHSSize); 00546 } else if (CurSize) { 00547 // Otherwise, use assignment for the already-constructed elements. 00548 std::copy(RHS.Begin, RHS.Begin+CurSize, Begin); 00549 } 00550 00551 // Copy construct the new elements in place. 00552 std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize); 00553 00554 // Set end. 00555 End = Begin+RHSSize; 00556 return *this; 00557 } 00558 00559 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized 00560 /// for the case when the array is small. It contains some number of elements 00561 /// in-place, which allows it to avoid heap allocation when the actual number of 00562 /// elements is below that threshold. This allows normal "small" cases to be 00563 /// fast without losing generality for large inputs. 00564 /// 00565 /// Note that this does not attempt to be exception safe. 00566 /// 00567 template <typename T, unsigned N> 00568 class SmallVector : public SmallVectorImpl<T> { 00569 /// InlineElts - These are 'N-1' elements that are stored inline in the body 00570 /// of the vector. The extra '1' element is stored in SmallVectorImpl. 00571 typedef typename SmallVectorImpl<T>::U U; 00572 enum { 00573 // MinUs - The number of U's require to cover N T's. 00574 MinUs = (static_cast<unsigned int>(sizeof(T))*N + 00575 static_cast<unsigned int>(sizeof(U)) - 1) / 00576 static_cast<unsigned int>(sizeof(U)), 00577 00578 // NumInlineEltsElts - The number of elements actually in this array. There 00579 // is already one in the parent class, and we have to round up to avoid 00580 // having a zero-element array. 00581 NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1, 00582 00583 // NumTsAvailable - The number of T's we actually have space for, which may 00584 // be more than N due to rounding. 00585 NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(sizeof(U))/ 00586 static_cast<unsigned int>(sizeof(T)) 00587 }; 00588 U InlineElts[NumInlineEltsElts]; 00589 public: 00590 SmallVector() : SmallVectorImpl<T>(NumTsAvailable) { 00591 } 00592 00593 explicit SmallVector(unsigned Size, const T &Value = T()) 00594 : SmallVectorImpl<T>(NumTsAvailable) { 00595 this->reserve(Size); 00596 while (Size--) 00597 this->push_back(Value); 00598 } 00599 00600 template<typename ItTy> 00601 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) { 00602 this->append(S, E); 00603 } 00604 00605 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) { 00606 if (!RHS.empty()) 00607 SmallVectorImpl<T>::operator=(RHS); 00608 } 00609 00610 const SmallVector &operator=(const SmallVector &RHS) { 00611 SmallVectorImpl<T>::operator=(RHS); 00612 return *this; 00613 } 00614 00615 }; 00616 00617 } // End llvm namespace 00618 00619 namespace std { 00620 /// Implement std::swap in terms of SmallVector swap. 00621 template<typename T> 00622 inline void 00623 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 00624 LHS.swap(RHS); 00625 } 00626 00627 /// Implement std::swap in terms of SmallVector swap. 00628 template<typename T, unsigned N> 00629 inline void 00630 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 00631 LHS.swap(RHS); 00632 } 00633 } 00634 00635 #endif