SmallVector.h revision 326990f1eb7ff005adabe46a1f982eff8835813e
1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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 "llvm/Support/type_traits.h" 18#include <algorithm> 19#include <cassert> 20#include <cstddef> 21#include <cstdlib> 22#include <cstring> 23#include <memory> 24 25#ifdef _MSC_VER 26namespace std { 27#if _MSC_VER <= 1310 28 // Work around flawed VC++ implementation of std::uninitialized_copy. Define 29 // additional overloads so that elements with pointer types are recognized as 30 // scalars and not objects, causing bizarre type conversion errors. 31 template<class T1, class T2> 32 inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { 33 _Scalar_ptr_iterator_tag _Cat; 34 return _Cat; 35 } 36 37 template<class T1, class T2> 38 inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { 39 _Scalar_ptr_iterator_tag _Cat; 40 return _Cat; 41 } 42#else 43// FIXME: It is not clear if the problem is fixed in VS 2005. What is clear 44// is that the above hack won't work if it wasn't fixed. 45#endif 46} 47#endif 48 49namespace llvm { 50 51/// SmallVectorBase - This is all the non-templated stuff common to all 52/// SmallVectors. 53class SmallVectorBase { 54protected: 55 void *BeginX, *EndX, *CapacityX; 56 57 // Allocate raw space for N elements of type T. If T has a ctor or dtor, we 58 // don't want it to be automatically run, so we need to represent the space as 59 // something else. An array of char would work great, but might not be 60 // aligned sufficiently. Instead we use some number of union instances for 61 // the space, which guarantee maximal alignment. 62 union U { 63 double D; 64 long double LD; 65 long long L; 66 void *P; 67 } FirstEl; 68 // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 69 70protected: 71 SmallVectorBase(size_t Size) 72 : BeginX(&FirstEl), EndX(&FirstEl), CapacityX((char*)&FirstEl+Size) {} 73 74 /// isSmall - Return true if this is a smallvector which has not had dynamic 75 /// memory allocated for it. 76 bool isSmall() const { 77 return BeginX == static_cast<const void*>(&FirstEl); 78 } 79 80 /// size_in_bytes - This returns size()*sizeof(T). 81 size_t size_in_bytes() const { 82 return size_t((char*)EndX - (char*)BeginX); 83 } 84 85 /// capacity_in_bytes - This returns capacity()*sizeof(T). 86 size_t capacity_in_bytes() const { 87 return size_t((char*)CapacityX - (char*)BeginX); 88 } 89 90 /// grow_pod - This is an implementation of the grow() method which only works 91 /// on POD-like datatypes and is out of line to reduce code duplication. 92 void grow_pod(size_t MinSizeInBytes, size_t TSize); 93 94public: 95 bool empty() const { return BeginX == EndX; } 96}; 97 98 99template <typename T> 100class SmallVectorTemplateCommon : public SmallVectorBase { 101protected: 102 void setEnd(T *P) { this->EndX = P; } 103public: 104 SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(Size) {} 105 106 typedef size_t size_type; 107 typedef ptrdiff_t difference_type; 108 typedef T value_type; 109 typedef T *iterator; 110 typedef const T *const_iterator; 111 112 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 113 typedef std::reverse_iterator<iterator> reverse_iterator; 114 115 typedef T &reference; 116 typedef const T &const_reference; 117 typedef T *pointer; 118 typedef const T *const_pointer; 119 120 // forward iterator creation methods. 121 iterator begin() { return (iterator)this->BeginX; } 122 const_iterator begin() const { return (const_iterator)this->BeginX; } 123 iterator end() { return (iterator)this->EndX; } 124 const_iterator end() const { return (const_iterator)this->EndX; } 125protected: 126 iterator capacity_ptr() { return (iterator)this->CapacityX; } 127 const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} 128public: 129 130 // reverse iterator creation methods. 131 reverse_iterator rbegin() { return reverse_iterator(end()); } 132 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 133 reverse_iterator rend() { return reverse_iterator(begin()); } 134 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 135 136 size_type size() const { return end()-begin(); } 137 size_type max_size() const { return size_type(-1) / sizeof(T); } 138 139 /// capacity - Return the total number of elements in the currently allocated 140 /// buffer. 141 size_t capacity() const { return capacity_ptr() - begin(); } 142 143 /// data - Return a pointer to the vector's buffer, even if empty(). 144 pointer data() { return pointer(begin()); } 145 /// data - Return a pointer to the vector's buffer, even if empty(). 146 const_pointer data() const { return const_pointer(begin()); } 147 148 reference operator[](unsigned idx) { 149 assert(begin() + idx < end()); 150 return begin()[idx]; 151 } 152 const_reference operator[](unsigned idx) const { 153 assert(begin() + idx < end()); 154 return begin()[idx]; 155 } 156 157 reference front() { 158 return begin()[0]; 159 } 160 const_reference front() const { 161 return begin()[0]; 162 } 163 164 reference back() { 165 return end()[-1]; 166 } 167 const_reference back() const { 168 return end()[-1]; 169 } 170}; 171 172/// SmallVectorTemplateBase<isPodLike = false> - This is where we put method 173/// implementations that are designed to work with non-POD-like T's. 174template <typename T, bool isPodLike> 175class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { 176public: 177 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 178 179 static void destroy_range(T *S, T *E) { 180 while (S != E) { 181 --E; 182 E->~T(); 183 } 184 } 185 186 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 187 /// starting with "Dest", constructing elements into it as needed. 188 template<typename It1, typename It2> 189 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 190 std::uninitialized_copy(I, E, Dest); 191 } 192 193 /// grow - double the size of the allocated memory, guaranteeing space for at 194 /// least one more element or MinSize if specified. 195 void grow(size_t MinSize = 0); 196}; 197 198// Define this out-of-line to dissuade the C++ compiler from inlining it. 199template <typename T, bool isPodLike> 200void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { 201 size_t CurCapacity = this->capacity(); 202 size_t CurSize = this->size(); 203 size_t NewCapacity = 2*CurCapacity + 1; // Always grow, even from zero. 204 if (NewCapacity < MinSize) 205 NewCapacity = MinSize; 206 T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); 207 208 // Copy the elements over. 209 this->uninitialized_copy(this->begin(), this->end(), NewElts); 210 211 // Destroy the original elements. 212 destroy_range(this->begin(), this->end()); 213 214 // If this wasn't grown from the inline copy, deallocate the old space. 215 if (!this->isSmall()) 216 free(this->begin()); 217 218 this->setEnd(NewElts+CurSize); 219 this->BeginX = NewElts; 220 this->CapacityX = this->begin()+NewCapacity; 221} 222 223 224/// SmallVectorTemplateBase<isPodLike = true> - This is where we put method 225/// implementations that are designed to work with POD-like T's. 226template <typename T> 227class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { 228public: 229 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 230 231 // No need to do a destroy loop for POD's. 232 static void destroy_range(T *, T *) {} 233 234 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 235 /// starting with "Dest", constructing elements into it as needed. 236 template<typename It1, typename It2> 237 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 238 // Arbitrary iterator types; just use the basic implementation. 239 std::uninitialized_copy(I, E, Dest); 240 } 241 242 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 243 /// starting with "Dest", constructing elements into it as needed. 244 template<typename T1, typename T2> 245 static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) { 246 // Use memcpy for PODs iterated by pointers (which includes SmallVector 247 // iterators): std::uninitialized_copy optimizes to memmove, but we can 248 // use memcpy here. 249 memcpy(Dest, I, (E-I)*sizeof(T)); 250 } 251 252 /// grow - double the size of the allocated memory, guaranteeing space for at 253 /// least one more element or MinSize if specified. 254 void grow(size_t MinSize = 0) { 255 this->grow_pod(MinSize*sizeof(T), sizeof(T)); 256 } 257}; 258 259 260/// SmallVectorImpl - This class consists of common code factored out of the 261/// SmallVector class to reduce code duplication based on the SmallVector 'N' 262/// template parameter. 263template <typename T> 264class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { 265 typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; 266 267 SmallVectorImpl(const SmallVectorImpl&); // DISABLED. 268public: 269 typedef typename SuperClass::iterator iterator; 270 typedef typename SuperClass::size_type size_type; 271 272 // Default ctor - Initialize to empty. 273 explicit SmallVectorImpl(unsigned N) 274 : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { 275 } 276 277 ~SmallVectorImpl() { 278 // Destroy the constructed elements in the vector. 279 this->destroy_range(this->begin(), this->end()); 280 281 // If this wasn't grown from the inline copy, deallocate the old space. 282 if (!this->isSmall()) 283 free(this->begin()); 284 } 285 286 287 void clear() { 288 this->destroy_range(this->begin(), this->end()); 289 this->EndX = this->BeginX; 290 } 291 292 void resize(unsigned N) { 293 if (N < this->size()) { 294 this->destroy_range(this->begin()+N, this->end()); 295 this->setEnd(this->begin()+N); 296 } else if (N > this->size()) { 297 if (this->capacity() < N) 298 this->grow(N); 299 this->construct_range(this->end(), this->begin()+N, T()); 300 this->setEnd(this->begin()+N); 301 } 302 } 303 304 void resize(unsigned N, const T &NV) { 305 if (N < this->size()) { 306 this->destroy_range(this->begin()+N, this->end()); 307 this->setEnd(this->begin()+N); 308 } else if (N > this->size()) { 309 if (this->capacity() < N) 310 this->grow(N); 311 construct_range(this->end(), this->begin()+N, NV); 312 this->setEnd(this->begin()+N); 313 } 314 } 315 316 void reserve(unsigned N) { 317 if (this->capacity() < N) 318 this->grow(N); 319 } 320 321 void push_back(const T &Elt) { 322 if (this->EndX < this->CapacityX) { 323 Retry: 324 new (this->end()) T(Elt); 325 this->setEnd(this->end()+1); 326 return; 327 } 328 this->grow(); 329 goto Retry; 330 } 331 332 void pop_back() { 333 this->setEnd(this->end()-1); 334 this->end()->~T(); 335 } 336 337 T pop_back_val() { 338 T Result = this->back(); 339 pop_back(); 340 return Result; 341 } 342 343 344 void swap(SmallVectorImpl &RHS); 345 346 /// append - Add the specified range to the end of the SmallVector. 347 /// 348 template<typename in_iter> 349 void append(in_iter in_start, in_iter in_end) { 350 size_type NumInputs = std::distance(in_start, in_end); 351 // Grow allocated space if needed. 352 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 353 this->grow(this->size()+NumInputs); 354 355 // Copy the new elements over. 356 // TODO: NEED To compile time dispatch on whether in_iter is a random access 357 // iterator to use the fast uninitialized_copy. 358 std::uninitialized_copy(in_start, in_end, this->end()); 359 this->setEnd(this->end() + NumInputs); 360 } 361 362 /// append - Add the specified range to the end of the SmallVector. 363 /// 364 void append(size_type NumInputs, const T &Elt) { 365 // Grow allocated space if needed. 366 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 367 this->grow(this->size()+NumInputs); 368 369 // Copy the new elements over. 370 std::uninitialized_fill_n(this->end(), NumInputs, Elt); 371 this->setEnd(this->end() + NumInputs); 372 } 373 374 void assign(unsigned NumElts, const T &Elt) { 375 clear(); 376 if (this->capacity() < NumElts) 377 this->grow(NumElts); 378 this->setEnd(this->begin()+NumElts); 379 construct_range(this->begin(), this->end(), Elt); 380 } 381 382 iterator erase(iterator I) { 383 iterator N = I; 384 // Shift all elts down one. 385 std::copy(I+1, this->end(), I); 386 // Drop the last elt. 387 pop_back(); 388 return(N); 389 } 390 391 iterator erase(iterator S, iterator E) { 392 iterator N = S; 393 // Shift all elts down. 394 iterator I = std::copy(E, this->end(), S); 395 // Drop the last elts. 396 this->destroy_range(I, this->end()); 397 this->setEnd(I); 398 return(N); 399 } 400 401 iterator insert(iterator I, const T &Elt) { 402 if (I == this->end()) { // Important special case for empty vector. 403 push_back(Elt); 404 return this->end()-1; 405 } 406 407 if (this->EndX < this->CapacityX) { 408 Retry: 409 new (this->end()) T(this->back()); 410 this->setEnd(this->end()+1); 411 // Push everything else over. 412 std::copy_backward(I, this->end()-1, this->end()); 413 *I = Elt; 414 return I; 415 } 416 size_t EltNo = I-this->begin(); 417 this->grow(); 418 I = this->begin()+EltNo; 419 goto Retry; 420 } 421 422 iterator insert(iterator I, size_type NumToInsert, const T &Elt) { 423 if (I == this->end()) { // Important special case for empty vector. 424 append(NumToInsert, Elt); 425 return this->end()-1; 426 } 427 428 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 429 size_t InsertElt = I - this->begin(); 430 431 // Ensure there is enough space. 432 reserve(static_cast<unsigned>(this->size() + NumToInsert)); 433 434 // Uninvalidate the iterator. 435 I = this->begin()+InsertElt; 436 437 // If there are more elements between the insertion point and the end of the 438 // range than there are being inserted, we can use a simple approach to 439 // insertion. Since we already reserved space, we know that this won't 440 // reallocate the vector. 441 if (size_t(this->end()-I) >= NumToInsert) { 442 T *OldEnd = this->end(); 443 append(this->end()-NumToInsert, this->end()); 444 445 // Copy the existing elements that get replaced. 446 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 447 448 std::fill_n(I, NumToInsert, Elt); 449 return I; 450 } 451 452 // Otherwise, we're inserting more elements than exist already, and we're 453 // not inserting at the end. 454 455 // Copy over the elements that we're about to overwrite. 456 T *OldEnd = this->end(); 457 this->setEnd(this->end() + NumToInsert); 458 size_t NumOverwritten = OldEnd-I; 459 this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 460 461 // Replace the overwritten part. 462 std::fill_n(I, NumOverwritten, Elt); 463 464 // Insert the non-overwritten middle part. 465 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 466 return I; 467 } 468 469 template<typename ItTy> 470 iterator insert(iterator I, ItTy From, ItTy To) { 471 if (I == this->end()) { // Important special case for empty vector. 472 append(From, To); 473 return this->end()-1; 474 } 475 476 size_t NumToInsert = std::distance(From, To); 477 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 478 size_t InsertElt = I - this->begin(); 479 480 // Ensure there is enough space. 481 reserve(static_cast<unsigned>(this->size() + NumToInsert)); 482 483 // Uninvalidate the iterator. 484 I = this->begin()+InsertElt; 485 486 // If there are more elements between the insertion point and the end of the 487 // range than there are being inserted, we can use a simple approach to 488 // insertion. Since we already reserved space, we know that this won't 489 // reallocate the vector. 490 if (size_t(this->end()-I) >= NumToInsert) { 491 T *OldEnd = this->end(); 492 append(this->end()-NumToInsert, this->end()); 493 494 // Copy the existing elements that get replaced. 495 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 496 497 std::copy(From, To, I); 498 return I; 499 } 500 501 // Otherwise, we're inserting more elements than exist already, and we're 502 // not inserting at the end. 503 504 // Copy over the elements that we're about to overwrite. 505 T *OldEnd = this->end(); 506 this->setEnd(this->end() + NumToInsert); 507 size_t NumOverwritten = OldEnd-I; 508 this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 509 510 // Replace the overwritten part. 511 for (; NumOverwritten > 0; --NumOverwritten) { 512 *I = *From; 513 ++I; ++From; 514 } 515 516 // Insert the non-overwritten middle part. 517 this->uninitialized_copy(From, To, OldEnd); 518 return I; 519 } 520 521 const SmallVectorImpl 522 &operator=(const SmallVectorImpl &RHS); 523 524 bool operator==(const SmallVectorImpl &RHS) const { 525 if (this->size() != RHS.size()) return false; 526 return std::equal(this->begin(), this->end(), RHS.begin()); 527 } 528 bool operator!=(const SmallVectorImpl &RHS) const { 529 return !(*this == RHS); 530 } 531 532 bool operator<(const SmallVectorImpl &RHS) const { 533 return std::lexicographical_compare(this->begin(), this->end(), 534 RHS.begin(), RHS.end()); 535 } 536 537 /// set_size - Set the array size to \arg N, which the current array must have 538 /// enough capacity for. 539 /// 540 /// This does not construct or destroy any elements in the vector. 541 /// 542 /// Clients can use this in conjunction with capacity() to write past the end 543 /// of the buffer when they know that more elements are available, and only 544 /// update the size later. This avoids the cost of value initializing elements 545 /// which will only be overwritten. 546 void set_size(unsigned N) { 547 assert(N <= this->capacity()); 548 this->setEnd(this->begin() + N); 549 } 550 551private: 552 static void construct_range(T *S, T *E, const T &Elt) { 553 for (; S != E; ++S) 554 new (S) T(Elt); 555 } 556}; 557 558 559template <typename T> 560void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 561 if (this == &RHS) return; 562 563 // We can only avoid copying elements if neither vector is small. 564 if (!this->isSmall() && !RHS.isSmall()) { 565 std::swap(this->BeginX, RHS.BeginX); 566 std::swap(this->EndX, RHS.EndX); 567 std::swap(this->CapacityX, RHS.CapacityX); 568 return; 569 } 570 if (RHS.size() > this->capacity()) 571 this->grow(RHS.size()); 572 if (this->size() > RHS.capacity()) 573 RHS.grow(this->size()); 574 575 // Swap the shared elements. 576 size_t NumShared = this->size(); 577 if (NumShared > RHS.size()) NumShared = RHS.size(); 578 for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i) 579 std::swap((*this)[i], RHS[i]); 580 581 // Copy over the extra elts. 582 if (this->size() > RHS.size()) { 583 size_t EltDiff = this->size() - RHS.size(); 584 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); 585 RHS.setEnd(RHS.end()+EltDiff); 586 this->destroy_range(this->begin()+NumShared, this->end()); 587 this->setEnd(this->begin()+NumShared); 588 } else if (RHS.size() > this->size()) { 589 size_t EltDiff = RHS.size() - this->size(); 590 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); 591 this->setEnd(this->end() + EltDiff); 592 this->destroy_range(RHS.begin()+NumShared, RHS.end()); 593 RHS.setEnd(RHS.begin()+NumShared); 594 } 595} 596 597template <typename T> 598const SmallVectorImpl<T> &SmallVectorImpl<T>:: 599 operator=(const SmallVectorImpl<T> &RHS) { 600 // Avoid self-assignment. 601 if (this == &RHS) return *this; 602 603 // If we already have sufficient space, assign the common elements, then 604 // destroy any excess. 605 size_t RHSSize = RHS.size(); 606 size_t CurSize = this->size(); 607 if (CurSize >= RHSSize) { 608 // Assign common elements. 609 iterator NewEnd; 610 if (RHSSize) 611 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); 612 else 613 NewEnd = this->begin(); 614 615 // Destroy excess elements. 616 this->destroy_range(NewEnd, this->end()); 617 618 // Trim. 619 this->setEnd(NewEnd); 620 return *this; 621 } 622 623 // If we have to grow to have enough elements, destroy the current elements. 624 // This allows us to avoid copying them during the grow. 625 if (this->capacity() < RHSSize) { 626 // Destroy current elements. 627 this->destroy_range(this->begin(), this->end()); 628 this->setEnd(this->begin()); 629 CurSize = 0; 630 this->grow(RHSSize); 631 } else if (CurSize) { 632 // Otherwise, use assignment for the already-constructed elements. 633 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); 634 } 635 636 // Copy construct the new elements in place. 637 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), 638 this->begin()+CurSize); 639 640 // Set end. 641 this->setEnd(this->begin()+RHSSize); 642 return *this; 643} 644 645 646/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized 647/// for the case when the array is small. It contains some number of elements 648/// in-place, which allows it to avoid heap allocation when the actual number of 649/// elements is below that threshold. This allows normal "small" cases to be 650/// fast without losing generality for large inputs. 651/// 652/// Note that this does not attempt to be exception safe. 653/// 654template <typename T, unsigned N> 655class SmallVector : public SmallVectorImpl<T> { 656 /// InlineElts - These are 'N-1' elements that are stored inline in the body 657 /// of the vector. The extra '1' element is stored in SmallVectorImpl. 658 typedef typename SmallVectorImpl<T>::U U; 659 enum { 660 // MinUs - The number of U's require to cover N T's. 661 MinUs = (static_cast<unsigned int>(sizeof(T))*N + 662 static_cast<unsigned int>(sizeof(U)) - 1) / 663 static_cast<unsigned int>(sizeof(U)), 664 665 // NumInlineEltsElts - The number of elements actually in this array. There 666 // is already one in the parent class, and we have to round up to avoid 667 // having a zero-element array. 668 NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1, 669 670 // NumTsAvailable - The number of T's we actually have space for, which may 671 // be more than N due to rounding. 672 NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(sizeof(U))/ 673 static_cast<unsigned int>(sizeof(T)) 674 }; 675 U InlineElts[NumInlineEltsElts]; 676public: 677 SmallVector() : SmallVectorImpl<T>(NumTsAvailable) { 678 } 679 680 explicit SmallVector(unsigned Size, const T &Value = T()) 681 : SmallVectorImpl<T>(NumTsAvailable) { 682 this->reserve(Size); 683 while (Size--) 684 this->push_back(Value); 685 } 686 687 template<typename ItTy> 688 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) { 689 this->append(S, E); 690 } 691 692 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) { 693 if (!RHS.empty()) 694 SmallVectorImpl<T>::operator=(RHS); 695 } 696 697 const SmallVector &operator=(const SmallVector &RHS) { 698 SmallVectorImpl<T>::operator=(RHS); 699 return *this; 700 } 701 702}; 703 704/// Specialize SmallVector at N=0. This specialization guarantees 705/// that it can be instantiated at an incomplete T if none of its 706/// members are required. 707template <typename T> 708class SmallVector<T,0> : public SmallVectorImpl<T> { 709public: 710 SmallVector() : SmallVectorImpl<T>(0) {} 711 712 explicit SmallVector(unsigned Size, const T &Value = T()) 713 : SmallVectorImpl<T>(0) { 714 this->reserve(Size); 715 while (Size--) 716 this->push_back(Value); 717 } 718 719 template<typename ItTy> 720 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(0) { 721 this->append(S, E); 722 } 723 724 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(0) { 725 SmallVectorImpl<T>::operator=(RHS); 726 } 727 728 SmallVector &operator=(const SmallVectorImpl<T> &RHS) { 729 return SmallVectorImpl<T>::operator=(RHS); 730 } 731 732}; 733 734} // End llvm namespace 735 736namespace std { 737 /// Implement std::swap in terms of SmallVector swap. 738 template<typename T> 739 inline void 740 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 741 LHS.swap(RHS); 742 } 743 744 /// Implement std::swap in terms of SmallVector swap. 745 template<typename T, unsigned N> 746 inline void 747 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 748 LHS.swap(RHS); 749 } 750} 751 752#endif 753