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