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