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/AlignOf.h" 18#include "llvm/Support/Compiler.h" 19#include "llvm/Support/MathExtras.h" 20#include "llvm/Support/type_traits.h" 21#include <algorithm> 22#include <cassert> 23#include <cstddef> 24#include <cstdlib> 25#include <cstring> 26#include <iterator> 27#include <memory> 28 29namespace llvm { 30 31/// SmallVectorBase - This is all the non-templated stuff common to all 32/// SmallVectors. 33class SmallVectorBase { 34protected: 35 void *BeginX, *EndX, *CapacityX; 36 37protected: 38 SmallVectorBase(void *FirstEl, size_t Size) 39 : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} 40 41 /// grow_pod - This is an implementation of the grow() method which only works 42 /// on POD-like data types and is out of line to reduce code duplication. 43 void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); 44 45public: 46 /// size_in_bytes - This returns size()*sizeof(T). 47 size_t size_in_bytes() const { 48 return size_t((char*)EndX - (char*)BeginX); 49 } 50 51 /// capacity_in_bytes - This returns capacity()*sizeof(T). 52 size_t capacity_in_bytes() const { 53 return size_t((char*)CapacityX - (char*)BeginX); 54 } 55 56 bool empty() const { return BeginX == EndX; } 57}; 58 59template <typename T, unsigned N> struct SmallVectorStorage; 60 61/// SmallVectorTemplateCommon - This is the part of SmallVectorTemplateBase 62/// which does not depend on whether the type T is a POD. The extra dummy 63/// template argument is used by ArrayRef to avoid unnecessarily requiring T 64/// to be complete. 65template <typename T, typename = void> 66class SmallVectorTemplateCommon : public SmallVectorBase { 67private: 68 template <typename, unsigned> friend struct SmallVectorStorage; 69 70 // Allocate raw space for N elements of type T. If T has a ctor or dtor, we 71 // don't want it to be automatically run, so we need to represent the space as 72 // something else. Use an array of char of sufficient alignment. 73 typedef llvm::AlignedCharArrayUnion<T> U; 74 U FirstEl; 75 // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 76 77protected: 78 SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {} 79 80 void grow_pod(size_t MinSizeInBytes, size_t TSize) { 81 SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); 82 } 83 84 /// isSmall - Return true if this is a smallvector which has not had dynamic 85 /// memory allocated for it. 86 bool isSmall() const { 87 return BeginX == static_cast<const void*>(&FirstEl); 88 } 89 90 /// resetToSmall - Put this vector in a state of being small. 91 void resetToSmall() { 92 BeginX = EndX = CapacityX = &FirstEl; 93 } 94 95 void setEnd(T *P) { this->EndX = P; } 96public: 97 typedef size_t size_type; 98 typedef ptrdiff_t difference_type; 99 typedef T value_type; 100 typedef T *iterator; 101 typedef const T *const_iterator; 102 103 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 104 typedef std::reverse_iterator<iterator> reverse_iterator; 105 106 typedef T &reference; 107 typedef const T &const_reference; 108 typedef T *pointer; 109 typedef const T *const_pointer; 110 111 // forward iterator creation methods. 112 iterator begin() { return (iterator)this->BeginX; } 113 const_iterator begin() const { return (const_iterator)this->BeginX; } 114 iterator end() { return (iterator)this->EndX; } 115 const_iterator end() const { return (const_iterator)this->EndX; } 116protected: 117 iterator capacity_ptr() { return (iterator)this->CapacityX; } 118 const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} 119public: 120 121 // reverse iterator creation methods. 122 reverse_iterator rbegin() { return reverse_iterator(end()); } 123 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 124 reverse_iterator rend() { return reverse_iterator(begin()); } 125 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 126 127 size_type size() const { return end()-begin(); } 128 size_type max_size() const { return size_type(-1) / sizeof(T); } 129 130 /// capacity - Return the total number of elements in the currently allocated 131 /// buffer. 132 size_t capacity() const { return capacity_ptr() - begin(); } 133 134 /// data - Return a pointer to the vector's buffer, even if empty(). 135 pointer data() { return pointer(begin()); } 136 /// data - Return a pointer to the vector's buffer, even if empty(). 137 const_pointer data() const { return const_pointer(begin()); } 138 139 reference operator[](unsigned idx) { 140 assert(begin() + idx < end()); 141 return begin()[idx]; 142 } 143 const_reference operator[](unsigned idx) const { 144 assert(begin() + idx < end()); 145 return begin()[idx]; 146 } 147 148 reference front() { 149 assert(!empty()); 150 return begin()[0]; 151 } 152 const_reference front() const { 153 assert(!empty()); 154 return begin()[0]; 155 } 156 157 reference back() { 158 assert(!empty()); 159 return end()[-1]; 160 } 161 const_reference back() const { 162 assert(!empty()); 163 return end()[-1]; 164 } 165}; 166 167/// SmallVectorTemplateBase<isPodLike = false> - This is where we put method 168/// implementations that are designed to work with non-POD-like T's. 169template <typename T, bool isPodLike> 170class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { 171protected: 172 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 173 174 static void destroy_range(T *S, T *E) { 175 while (S != E) { 176 --E; 177 E->~T(); 178 } 179 } 180 181 /// move - Use move-assignment to move the range [I, E) onto the 182 /// objects starting with "Dest". This is just <memory>'s 183 /// std::move, but not all stdlibs actually provide that. 184 template<typename It1, typename It2> 185 static It2 move(It1 I, It1 E, It2 Dest) { 186#if LLVM_HAS_RVALUE_REFERENCES 187 for (; I != E; ++I, ++Dest) 188 *Dest = ::std::move(*I); 189 return Dest; 190#else 191 return ::std::copy(I, E, Dest); 192#endif 193 } 194 195 /// move_backward - Use move-assignment to move the range 196 /// [I, E) onto the objects ending at "Dest", moving objects 197 /// in reverse order. This is just <algorithm>'s 198 /// std::move_backward, but not all stdlibs actually provide that. 199 template<typename It1, typename It2> 200 static It2 move_backward(It1 I, It1 E, It2 Dest) { 201#if LLVM_HAS_RVALUE_REFERENCES 202 while (I != E) 203 *--Dest = ::std::move(*--E); 204 return Dest; 205#else 206 return ::std::copy_backward(I, E, Dest); 207#endif 208 } 209 210 /// uninitialized_move - Move the range [I, E) into the uninitialized 211 /// memory starting with "Dest", constructing elements as needed. 212 template<typename It1, typename It2> 213 static void uninitialized_move(It1 I, It1 E, It2 Dest) { 214#if LLVM_HAS_RVALUE_REFERENCES 215 for (; I != E; ++I, ++Dest) 216 ::new ((void*) &*Dest) T(::std::move(*I)); 217#else 218 ::std::uninitialized_copy(I, E, Dest); 219#endif 220 } 221 222 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized 223 /// memory starting with "Dest", constructing elements as needed. 224 template<typename It1, typename It2> 225 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 226 std::uninitialized_copy(I, E, Dest); 227 } 228 229 /// grow - Grow the allocated memory (without initializing new 230 /// elements), doubling the size of the allocated memory. 231 /// Guarantees space for at least one more element, or MinSize more 232 /// elements if specified. 233 void grow(size_t MinSize = 0); 234 235public: 236 void push_back(const T &Elt) { 237 if (this->EndX < this->CapacityX) { 238 Retry: 239 ::new ((void*) this->end()) T(Elt); 240 this->setEnd(this->end()+1); 241 return; 242 } 243 this->grow(); 244 goto Retry; 245 } 246 247#if LLVM_HAS_RVALUE_REFERENCES 248 void push_back(T &&Elt) { 249 if (this->EndX < this->CapacityX) { 250 Retry: 251 ::new ((void*) this->end()) T(::std::move(Elt)); 252 this->setEnd(this->end()+1); 253 return; 254 } 255 this->grow(); 256 goto Retry; 257 } 258#endif 259 260 void pop_back() { 261 this->setEnd(this->end()-1); 262 this->end()->~T(); 263 } 264}; 265 266// Define this out-of-line to dissuade the C++ compiler from inlining it. 267template <typename T, bool isPodLike> 268void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { 269 size_t CurCapacity = this->capacity(); 270 size_t CurSize = this->size(); 271 // Always grow, even from zero. 272 size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2)); 273 if (NewCapacity < MinSize) 274 NewCapacity = MinSize; 275 T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); 276 277 // Move the elements over. 278 this->uninitialized_move(this->begin(), this->end(), NewElts); 279 280 // Destroy the original elements. 281 destroy_range(this->begin(), this->end()); 282 283 // If this wasn't grown from the inline copy, deallocate the old space. 284 if (!this->isSmall()) 285 free(this->begin()); 286 287 this->setEnd(NewElts+CurSize); 288 this->BeginX = NewElts; 289 this->CapacityX = this->begin()+NewCapacity; 290} 291 292 293/// SmallVectorTemplateBase<isPodLike = true> - This is where we put method 294/// implementations that are designed to work with POD-like T's. 295template <typename T> 296class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { 297protected: 298 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 299 300 // No need to do a destroy loop for POD's. 301 static void destroy_range(T *, T *) {} 302 303 /// move - Use move-assignment to move the range [I, E) onto the 304 /// objects starting with "Dest". For PODs, this is just memcpy. 305 template<typename It1, typename It2> 306 static It2 move(It1 I, It1 E, It2 Dest) { 307 return ::std::copy(I, E, Dest); 308 } 309 310 /// move_backward - Use move-assignment to move the range 311 /// [I, E) onto the objects ending at "Dest", moving objects 312 /// in reverse order. 313 template<typename It1, typename It2> 314 static It2 move_backward(It1 I, It1 E, It2 Dest) { 315 return ::std::copy_backward(I, E, Dest); 316 } 317 318 /// uninitialized_move - Move the range [I, E) onto the uninitialized memory 319 /// starting with "Dest", constructing elements into it as needed. 320 template<typename It1, typename It2> 321 static void uninitialized_move(It1 I, It1 E, It2 Dest) { 322 // Just do a copy. 323 uninitialized_copy(I, E, Dest); 324 } 325 326 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 327 /// starting with "Dest", constructing elements into it as needed. 328 template<typename It1, typename It2> 329 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 330 // Arbitrary iterator types; just use the basic implementation. 331 std::uninitialized_copy(I, E, Dest); 332 } 333 334 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 335 /// starting with "Dest", constructing elements into it as needed. 336 template<typename T1, typename T2> 337 static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) { 338 // Use memcpy for PODs iterated by pointers (which includes SmallVector 339 // iterators): std::uninitialized_copy optimizes to memmove, but we can 340 // use memcpy here. 341 memcpy(Dest, I, (E-I)*sizeof(T)); 342 } 343 344 /// grow - double the size of the allocated memory, guaranteeing space for at 345 /// least one more element or MinSize if specified. 346 void grow(size_t MinSize = 0) { 347 this->grow_pod(MinSize*sizeof(T), sizeof(T)); 348 } 349public: 350 void push_back(const T &Elt) { 351 if (this->EndX < this->CapacityX) { 352 Retry: 353 memcpy(this->end(), &Elt, sizeof(T)); 354 this->setEnd(this->end()+1); 355 return; 356 } 357 this->grow(); 358 goto Retry; 359 } 360 361 void pop_back() { 362 this->setEnd(this->end()-1); 363 } 364}; 365 366 367/// SmallVectorImpl - This class consists of common code factored out of the 368/// SmallVector class to reduce code duplication based on the SmallVector 'N' 369/// template parameter. 370template <typename T> 371class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { 372 typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; 373 374 SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION; 375public: 376 typedef typename SuperClass::iterator iterator; 377 typedef typename SuperClass::size_type size_type; 378 379protected: 380 // Default ctor - Initialize to empty. 381 explicit SmallVectorImpl(unsigned N) 382 : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { 383 } 384 385public: 386 ~SmallVectorImpl() { 387 // Destroy the constructed elements in the vector. 388 this->destroy_range(this->begin(), this->end()); 389 390 // If this wasn't grown from the inline copy, deallocate the old space. 391 if (!this->isSmall()) 392 free(this->begin()); 393 } 394 395 396 void clear() { 397 this->destroy_range(this->begin(), this->end()); 398 this->EndX = this->BeginX; 399 } 400 401 void resize(unsigned N) { 402 if (N < this->size()) { 403 this->destroy_range(this->begin()+N, this->end()); 404 this->setEnd(this->begin()+N); 405 } else if (N > this->size()) { 406 if (this->capacity() < N) 407 this->grow(N); 408 std::uninitialized_fill(this->end(), this->begin()+N, T()); 409 this->setEnd(this->begin()+N); 410 } 411 } 412 413 void resize(unsigned N, const T &NV) { 414 if (N < this->size()) { 415 this->destroy_range(this->begin()+N, this->end()); 416 this->setEnd(this->begin()+N); 417 } else if (N > this->size()) { 418 if (this->capacity() < N) 419 this->grow(N); 420 std::uninitialized_fill(this->end(), this->begin()+N, NV); 421 this->setEnd(this->begin()+N); 422 } 423 } 424 425 void reserve(unsigned N) { 426 if (this->capacity() < N) 427 this->grow(N); 428 } 429 430 T pop_back_val() { 431#if LLVM_HAS_RVALUE_REFERENCES 432 T Result = ::std::move(this->back()); 433#else 434 T Result = this->back(); 435#endif 436 this->pop_back(); 437 return Result; 438 } 439 440 void swap(SmallVectorImpl &RHS); 441 442 /// append - Add the specified range to the end of the SmallVector. 443 /// 444 template<typename in_iter> 445 void append(in_iter in_start, in_iter in_end) { 446 size_type NumInputs = std::distance(in_start, in_end); 447 // Grow allocated space if needed. 448 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 449 this->grow(this->size()+NumInputs); 450 451 // Copy the new elements over. 452 // TODO: NEED To compile time dispatch on whether in_iter is a random access 453 // iterator to use the fast uninitialized_copy. 454 std::uninitialized_copy(in_start, in_end, this->end()); 455 this->setEnd(this->end() + NumInputs); 456 } 457 458 /// append - Add the specified range to the end of the SmallVector. 459 /// 460 void append(size_type NumInputs, const T &Elt) { 461 // Grow allocated space if needed. 462 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 463 this->grow(this->size()+NumInputs); 464 465 // Copy the new elements over. 466 std::uninitialized_fill_n(this->end(), NumInputs, Elt); 467 this->setEnd(this->end() + NumInputs); 468 } 469 470 void assign(unsigned NumElts, const T &Elt) { 471 clear(); 472 if (this->capacity() < NumElts) 473 this->grow(NumElts); 474 this->setEnd(this->begin()+NumElts); 475 std::uninitialized_fill(this->begin(), this->end(), Elt); 476 } 477 478 iterator erase(iterator I) { 479 assert(I >= this->begin() && "Iterator to erase is out of bounds."); 480 assert(I < this->end() && "Erasing at past-the-end iterator."); 481 482 iterator N = I; 483 // Shift all elts down one. 484 this->move(I+1, this->end(), I); 485 // Drop the last elt. 486 this->pop_back(); 487 return(N); 488 } 489 490 iterator erase(iterator S, iterator E) { 491 assert(S >= this->begin() && "Range to erase is out of bounds."); 492 assert(S <= E && "Trying to erase invalid range."); 493 assert(E <= this->end() && "Trying to erase past the end."); 494 495 iterator N = S; 496 // Shift all elts down. 497 iterator I = this->move(E, this->end(), S); 498 // Drop the last elts. 499 this->destroy_range(I, this->end()); 500 this->setEnd(I); 501 return(N); 502 } 503 504#if LLVM_HAS_RVALUE_REFERENCES 505 iterator insert(iterator I, T &&Elt) { 506 if (I == this->end()) { // Important special case for empty vector. 507 this->push_back(::std::move(Elt)); 508 return this->end()-1; 509 } 510 511 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 512 assert(I <= this->end() && "Inserting past the end of the vector."); 513 514 if (this->EndX < this->CapacityX) { 515 Retry: 516 ::new ((void*) this->end()) T(::std::move(this->back())); 517 this->setEnd(this->end()+1); 518 // Push everything else over. 519 this->move_backward(I, this->end()-1, this->end()); 520 521 // If we just moved the element we're inserting, be sure to update 522 // the reference. 523 T *EltPtr = &Elt; 524 if (I <= EltPtr && EltPtr < this->EndX) 525 ++EltPtr; 526 527 *I = ::std::move(*EltPtr); 528 return I; 529 } 530 size_t EltNo = I-this->begin(); 531 this->grow(); 532 I = this->begin()+EltNo; 533 goto Retry; 534 } 535#endif 536 537 iterator insert(iterator I, const T &Elt) { 538 if (I == this->end()) { // Important special case for empty vector. 539 this->push_back(Elt); 540 return this->end()-1; 541 } 542 543 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 544 assert(I <= this->end() && "Inserting past the end of the vector."); 545 546 if (this->EndX < this->CapacityX) { 547 Retry: 548 ::new ((void*) this->end()) T(this->back()); 549 this->setEnd(this->end()+1); 550 // Push everything else over. 551 this->move_backward(I, this->end()-1, this->end()); 552 553 // If we just moved the element we're inserting, be sure to update 554 // the reference. 555 const T *EltPtr = &Elt; 556 if (I <= EltPtr && EltPtr < this->EndX) 557 ++EltPtr; 558 559 *I = *EltPtr; 560 return I; 561 } 562 size_t EltNo = I-this->begin(); 563 this->grow(); 564 I = this->begin()+EltNo; 565 goto Retry; 566 } 567 568 iterator insert(iterator I, size_type NumToInsert, const T &Elt) { 569 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 570 size_t InsertElt = I - this->begin(); 571 572 if (I == this->end()) { // Important special case for empty vector. 573 append(NumToInsert, Elt); 574 return this->begin()+InsertElt; 575 } 576 577 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 578 assert(I <= this->end() && "Inserting past the end of the vector."); 579 580 // Ensure there is enough space. 581 reserve(static_cast<unsigned>(this->size() + NumToInsert)); 582 583 // Uninvalidate the iterator. 584 I = this->begin()+InsertElt; 585 586 // If there are more elements between the insertion point and the end of the 587 // range than there are being inserted, we can use a simple approach to 588 // insertion. Since we already reserved space, we know that this won't 589 // reallocate the vector. 590 if (size_t(this->end()-I) >= NumToInsert) { 591 T *OldEnd = this->end(); 592 append(this->end()-NumToInsert, this->end()); 593 594 // Copy the existing elements that get replaced. 595 this->move_backward(I, OldEnd-NumToInsert, OldEnd); 596 597 std::fill_n(I, NumToInsert, Elt); 598 return I; 599 } 600 601 // Otherwise, we're inserting more elements than exist already, and we're 602 // not inserting at the end. 603 604 // Move over the elements that we're about to overwrite. 605 T *OldEnd = this->end(); 606 this->setEnd(this->end() + NumToInsert); 607 size_t NumOverwritten = OldEnd-I; 608 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 609 610 // Replace the overwritten part. 611 std::fill_n(I, NumOverwritten, Elt); 612 613 // Insert the non-overwritten middle part. 614 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 615 return I; 616 } 617 618 template<typename ItTy> 619 iterator insert(iterator I, ItTy From, ItTy To) { 620 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 621 size_t InsertElt = I - this->begin(); 622 623 if (I == this->end()) { // Important special case for empty vector. 624 append(From, To); 625 return this->begin()+InsertElt; 626 } 627 628 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 629 assert(I <= this->end() && "Inserting past the end of the vector."); 630 631 size_t NumToInsert = std::distance(From, To); 632 633 // Ensure there is enough space. 634 reserve(static_cast<unsigned>(this->size() + NumToInsert)); 635 636 // Uninvalidate the iterator. 637 I = this->begin()+InsertElt; 638 639 // If there are more elements between the insertion point and the end of the 640 // range than there are being inserted, we can use a simple approach to 641 // insertion. Since we already reserved space, we know that this won't 642 // reallocate the vector. 643 if (size_t(this->end()-I) >= NumToInsert) { 644 T *OldEnd = this->end(); 645 append(this->end()-NumToInsert, this->end()); 646 647 // Copy the existing elements that get replaced. 648 this->move_backward(I, OldEnd-NumToInsert, OldEnd); 649 650 std::copy(From, To, I); 651 return I; 652 } 653 654 // Otherwise, we're inserting more elements than exist already, and we're 655 // not inserting at the end. 656 657 // Move over the elements that we're about to overwrite. 658 T *OldEnd = this->end(); 659 this->setEnd(this->end() + NumToInsert); 660 size_t NumOverwritten = OldEnd-I; 661 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 662 663 // Replace the overwritten part. 664 for (T *J = I; NumOverwritten > 0; --NumOverwritten) { 665 *J = *From; 666 ++J; ++From; 667 } 668 669 // Insert the non-overwritten middle part. 670 this->uninitialized_copy(From, To, OldEnd); 671 return I; 672 } 673 674 SmallVectorImpl &operator=(const SmallVectorImpl &RHS); 675 676#if LLVM_HAS_RVALUE_REFERENCES 677 SmallVectorImpl &operator=(SmallVectorImpl &&RHS); 678#endif 679 680 bool operator==(const SmallVectorImpl &RHS) const { 681 if (this->size() != RHS.size()) return false; 682 return std::equal(this->begin(), this->end(), RHS.begin()); 683 } 684 bool operator!=(const SmallVectorImpl &RHS) const { 685 return !(*this == RHS); 686 } 687 688 bool operator<(const SmallVectorImpl &RHS) const { 689 return std::lexicographical_compare(this->begin(), this->end(), 690 RHS.begin(), RHS.end()); 691 } 692 693 /// Set the array size to \p N, which the current array must have enough 694 /// capacity for. 695 /// 696 /// This does not construct or destroy any elements in the vector. 697 /// 698 /// Clients can use this in conjunction with capacity() to write past the end 699 /// of the buffer when they know that more elements are available, and only 700 /// update the size later. This avoids the cost of value initializing elements 701 /// which will only be overwritten. 702 void set_size(unsigned N) { 703 assert(N <= this->capacity()); 704 this->setEnd(this->begin() + N); 705 } 706}; 707 708 709template <typename T> 710void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 711 if (this == &RHS) return; 712 713 // We can only avoid copying elements if neither vector is small. 714 if (!this->isSmall() && !RHS.isSmall()) { 715 std::swap(this->BeginX, RHS.BeginX); 716 std::swap(this->EndX, RHS.EndX); 717 std::swap(this->CapacityX, RHS.CapacityX); 718 return; 719 } 720 if (RHS.size() > this->capacity()) 721 this->grow(RHS.size()); 722 if (this->size() > RHS.capacity()) 723 RHS.grow(this->size()); 724 725 // Swap the shared elements. 726 size_t NumShared = this->size(); 727 if (NumShared > RHS.size()) NumShared = RHS.size(); 728 for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i) 729 std::swap((*this)[i], RHS[i]); 730 731 // Copy over the extra elts. 732 if (this->size() > RHS.size()) { 733 size_t EltDiff = this->size() - RHS.size(); 734 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); 735 RHS.setEnd(RHS.end()+EltDiff); 736 this->destroy_range(this->begin()+NumShared, this->end()); 737 this->setEnd(this->begin()+NumShared); 738 } else if (RHS.size() > this->size()) { 739 size_t EltDiff = RHS.size() - this->size(); 740 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); 741 this->setEnd(this->end() + EltDiff); 742 this->destroy_range(RHS.begin()+NumShared, RHS.end()); 743 RHS.setEnd(RHS.begin()+NumShared); 744 } 745} 746 747template <typename T> 748SmallVectorImpl<T> &SmallVectorImpl<T>:: 749 operator=(const SmallVectorImpl<T> &RHS) { 750 // Avoid self-assignment. 751 if (this == &RHS) return *this; 752 753 // If we already have sufficient space, assign the common elements, then 754 // destroy any excess. 755 size_t RHSSize = RHS.size(); 756 size_t CurSize = this->size(); 757 if (CurSize >= RHSSize) { 758 // Assign common elements. 759 iterator NewEnd; 760 if (RHSSize) 761 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); 762 else 763 NewEnd = this->begin(); 764 765 // Destroy excess elements. 766 this->destroy_range(NewEnd, this->end()); 767 768 // Trim. 769 this->setEnd(NewEnd); 770 return *this; 771 } 772 773 // If we have to grow to have enough elements, destroy the current elements. 774 // This allows us to avoid copying them during the grow. 775 // FIXME: don't do this if they're efficiently moveable. 776 if (this->capacity() < RHSSize) { 777 // Destroy current elements. 778 this->destroy_range(this->begin(), this->end()); 779 this->setEnd(this->begin()); 780 CurSize = 0; 781 this->grow(RHSSize); 782 } else if (CurSize) { 783 // Otherwise, use assignment for the already-constructed elements. 784 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); 785 } 786 787 // Copy construct the new elements in place. 788 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), 789 this->begin()+CurSize); 790 791 // Set end. 792 this->setEnd(this->begin()+RHSSize); 793 return *this; 794} 795 796#if LLVM_HAS_RVALUE_REFERENCES 797template <typename T> 798SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { 799 // Avoid self-assignment. 800 if (this == &RHS) return *this; 801 802 // If the RHS isn't small, clear this vector and then steal its buffer. 803 if (!RHS.isSmall()) { 804 this->destroy_range(this->begin(), this->end()); 805 if (!this->isSmall()) free(this->begin()); 806 this->BeginX = RHS.BeginX; 807 this->EndX = RHS.EndX; 808 this->CapacityX = RHS.CapacityX; 809 RHS.resetToSmall(); 810 return *this; 811 } 812 813 // If we already have sufficient space, assign the common elements, then 814 // destroy any excess. 815 size_t RHSSize = RHS.size(); 816 size_t CurSize = this->size(); 817 if (CurSize >= RHSSize) { 818 // Assign common elements. 819 iterator NewEnd = this->begin(); 820 if (RHSSize) 821 NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd); 822 823 // Destroy excess elements and trim the bounds. 824 this->destroy_range(NewEnd, this->end()); 825 this->setEnd(NewEnd); 826 827 // Clear the RHS. 828 RHS.clear(); 829 830 return *this; 831 } 832 833 // If we have to grow to have enough elements, destroy the current elements. 834 // This allows us to avoid copying them during the grow. 835 // FIXME: this may not actually make any sense if we can efficiently move 836 // elements. 837 if (this->capacity() < RHSSize) { 838 // Destroy current elements. 839 this->destroy_range(this->begin(), this->end()); 840 this->setEnd(this->begin()); 841 CurSize = 0; 842 this->grow(RHSSize); 843 } else if (CurSize) { 844 // Otherwise, use assignment for the already-constructed elements. 845 this->move(RHS.begin(), RHS.end(), this->begin()); 846 } 847 848 // Move-construct the new elements in place. 849 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), 850 this->begin()+CurSize); 851 852 // Set end. 853 this->setEnd(this->begin()+RHSSize); 854 855 RHS.clear(); 856 return *this; 857} 858#endif 859 860/// Storage for the SmallVector elements which aren't contained in 861/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1' 862/// element is in the base class. This is specialized for the N=1 and N=0 cases 863/// to avoid allocating unnecessary storage. 864template <typename T, unsigned N> 865struct SmallVectorStorage { 866 typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1]; 867}; 868template <typename T> struct SmallVectorStorage<T, 1> {}; 869template <typename T> struct SmallVectorStorage<T, 0> {}; 870 871/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized 872/// for the case when the array is small. It contains some number of elements 873/// in-place, which allows it to avoid heap allocation when the actual number of 874/// elements is below that threshold. This allows normal "small" cases to be 875/// fast without losing generality for large inputs. 876/// 877/// Note that this does not attempt to be exception safe. 878/// 879template <typename T, unsigned N> 880class SmallVector : public SmallVectorImpl<T> { 881 /// Storage - Inline space for elements which aren't stored in the base class. 882 SmallVectorStorage<T, N> Storage; 883public: 884 SmallVector() : SmallVectorImpl<T>(N) { 885 } 886 887 explicit SmallVector(unsigned Size, const T &Value = T()) 888 : SmallVectorImpl<T>(N) { 889 this->assign(Size, Value); 890 } 891 892 template<typename ItTy> 893 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { 894 this->append(S, E); 895 } 896 897 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { 898 if (!RHS.empty()) 899 SmallVectorImpl<T>::operator=(RHS); 900 } 901 902 const SmallVector &operator=(const SmallVector &RHS) { 903 SmallVectorImpl<T>::operator=(RHS); 904 return *this; 905 } 906 907#if LLVM_HAS_RVALUE_REFERENCES 908 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { 909 if (!RHS.empty()) 910 SmallVectorImpl<T>::operator=(::std::move(RHS)); 911 } 912 913 const SmallVector &operator=(SmallVector &&RHS) { 914 SmallVectorImpl<T>::operator=(::std::move(RHS)); 915 return *this; 916 } 917#endif 918 919}; 920 921template<typename T, unsigned N> 922static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { 923 return X.capacity_in_bytes(); 924} 925 926} // End llvm namespace 927 928namespace std { 929 /// Implement std::swap in terms of SmallVector swap. 930 template<typename T> 931 inline void 932 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 933 LHS.swap(RHS); 934 } 935 936 /// Implement std::swap in terms of SmallVector swap. 937 template<typename T, unsigned N> 938 inline void 939 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 940 LHS.swap(RHS); 941 } 942} 943 944#endif 945