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