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 34 namespace llvm { 35 36 /// This is all the non-templated stuff common to all SmallVectors. 37 class SmallVectorBase { 38 protected: 39 void *BeginX, *EndX, *CapacityX; 40 41 protected: 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 49 public: 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. 66 template <typename T, typename = void> 67 class SmallVectorTemplateCommon : public SmallVectorBase { 68 private: 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 typedef AlignedCharArrayUnion<T> U; 75 U FirstEl; 76 // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 77 78 protected: 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 98 public: 99 typedef size_t size_type; 100 typedef ptrdiff_t difference_type; 101 typedef T value_type; 102 typedef T *iterator; 103 typedef const T *const_iterator; 104 105 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 106 typedef std::reverse_iterator<iterator> reverse_iterator; 107 108 typedef T &reference; 109 typedef const T &const_reference; 110 typedef T *pointer; 111 typedef const T *const_pointer; 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 123 protected: 124 iterator capacity_ptr() { return (iterator)this->CapacityX; } 125 const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} 126 127 public: 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. 178 template <typename T, bool isPodLike> 179 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { 180 protected: 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 210 public: 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. 232 template <typename T, bool isPodLike> 233 void 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. 260 template <typename T> 261 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { 262 protected: 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 305 public: 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. 320 template <typename T> 321 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { 322 typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; 323 324 public: 325 typedef typename SuperClass::iterator iterator; 326 typedef typename SuperClass::const_iterator const_iterator; 327 typedef typename SuperClass::size_type size_type; 328 329 protected: 330 // Default ctor - Initialize to empty. 331 explicit SmallVectorImpl(unsigned N) 332 : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { 333 } 334 335 public: 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 void append(in_iter in_start, in_iter in_end) { 393 size_type NumInputs = std::distance(in_start, in_end); 394 // Grow allocated space if needed. 395 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 396 this->grow(this->size()+NumInputs); 397 398 // Copy the new elements over. 399 this->uninitialized_copy(in_start, in_end, this->end()); 400 this->setEnd(this->end() + NumInputs); 401 } 402 403 /// Add the specified range to the end of the SmallVector. 404 void append(size_type NumInputs, const T &Elt) { 405 // Grow allocated space if needed. 406 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 407 this->grow(this->size()+NumInputs); 408 409 // Copy the new elements over. 410 std::uninitialized_fill_n(this->end(), NumInputs, Elt); 411 this->setEnd(this->end() + NumInputs); 412 } 413 414 void append(std::initializer_list<T> IL) { 415 append(IL.begin(), IL.end()); 416 } 417 418 void assign(size_type NumElts, const T &Elt) { 419 clear(); 420 if (this->capacity() < NumElts) 421 this->grow(NumElts); 422 this->setEnd(this->begin()+NumElts); 423 std::uninitialized_fill(this->begin(), this->end(), Elt); 424 } 425 426 void assign(std::initializer_list<T> IL) { 427 clear(); 428 append(IL); 429 } 430 431 iterator erase(const_iterator CI) { 432 // Just cast away constness because this is a non-const member function. 433 iterator I = const_cast<iterator>(CI); 434 435 assert(I >= this->begin() && "Iterator to erase is out of bounds."); 436 assert(I < this->end() && "Erasing at past-the-end iterator."); 437 438 iterator N = I; 439 // Shift all elts down one. 440 std::move(I+1, this->end(), I); 441 // Drop the last elt. 442 this->pop_back(); 443 return(N); 444 } 445 446 iterator erase(const_iterator CS, const_iterator CE) { 447 // Just cast away constness because this is a non-const member function. 448 iterator S = const_cast<iterator>(CS); 449 iterator E = const_cast<iterator>(CE); 450 451 assert(S >= this->begin() && "Range to erase is out of bounds."); 452 assert(S <= E && "Trying to erase invalid range."); 453 assert(E <= this->end() && "Trying to erase past the end."); 454 455 iterator N = S; 456 // Shift all elts down. 457 iterator I = std::move(E, this->end(), S); 458 // Drop the last elts. 459 this->destroy_range(I, this->end()); 460 this->setEnd(I); 461 return(N); 462 } 463 464 iterator insert(iterator I, T &&Elt) { 465 if (I == this->end()) { // Important special case for empty vector. 466 this->push_back(::std::move(Elt)); 467 return this->end()-1; 468 } 469 470 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 471 assert(I <= this->end() && "Inserting past the end of the vector."); 472 473 if (this->EndX >= this->CapacityX) { 474 size_t EltNo = I-this->begin(); 475 this->grow(); 476 I = this->begin()+EltNo; 477 } 478 479 ::new ((void*) this->end()) T(::std::move(this->back())); 480 // Push everything else over. 481 std::move_backward(I, this->end()-1, this->end()); 482 this->setEnd(this->end()+1); 483 484 // If we just moved the element we're inserting, be sure to update 485 // the reference. 486 T *EltPtr = &Elt; 487 if (I <= EltPtr && EltPtr < this->EndX) 488 ++EltPtr; 489 490 *I = ::std::move(*EltPtr); 491 return I; 492 } 493 494 iterator insert(iterator I, const T &Elt) { 495 if (I == this->end()) { // Important special case for empty vector. 496 this->push_back(Elt); 497 return this->end()-1; 498 } 499 500 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 501 assert(I <= this->end() && "Inserting past the end of the vector."); 502 503 if (this->EndX >= this->CapacityX) { 504 size_t EltNo = I-this->begin(); 505 this->grow(); 506 I = this->begin()+EltNo; 507 } 508 ::new ((void*) this->end()) T(std::move(this->back())); 509 // Push everything else over. 510 std::move_backward(I, this->end()-1, this->end()); 511 this->setEnd(this->end()+1); 512 513 // If we just moved the element we're inserting, be sure to update 514 // the reference. 515 const T *EltPtr = &Elt; 516 if (I <= EltPtr && EltPtr < this->EndX) 517 ++EltPtr; 518 519 *I = *EltPtr; 520 return I; 521 } 522 523 iterator insert(iterator I, size_type NumToInsert, const T &Elt) { 524 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 525 size_t InsertElt = I - this->begin(); 526 527 if (I == this->end()) { // Important special case for empty vector. 528 append(NumToInsert, Elt); 529 return this->begin()+InsertElt; 530 } 531 532 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 533 assert(I <= this->end() && "Inserting past the end of the vector."); 534 535 // Ensure there is enough space. 536 reserve(this->size() + NumToInsert); 537 538 // Uninvalidate the iterator. 539 I = this->begin()+InsertElt; 540 541 // If there are more elements between the insertion point and the end of the 542 // range than there are being inserted, we can use a simple approach to 543 // insertion. Since we already reserved space, we know that this won't 544 // reallocate the vector. 545 if (size_t(this->end()-I) >= NumToInsert) { 546 T *OldEnd = this->end(); 547 append(std::move_iterator<iterator>(this->end() - NumToInsert), 548 std::move_iterator<iterator>(this->end())); 549 550 // Copy the existing elements that get replaced. 551 std::move_backward(I, OldEnd-NumToInsert, OldEnd); 552 553 std::fill_n(I, NumToInsert, Elt); 554 return I; 555 } 556 557 // Otherwise, we're inserting more elements than exist already, and we're 558 // not inserting at the end. 559 560 // Move over the elements that we're about to overwrite. 561 T *OldEnd = this->end(); 562 this->setEnd(this->end() + NumToInsert); 563 size_t NumOverwritten = OldEnd-I; 564 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 565 566 // Replace the overwritten part. 567 std::fill_n(I, NumOverwritten, Elt); 568 569 // Insert the non-overwritten middle part. 570 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 571 return I; 572 } 573 574 template<typename ItTy> 575 iterator insert(iterator I, ItTy From, ItTy To) { 576 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 577 size_t InsertElt = I - this->begin(); 578 579 if (I == this->end()) { // Important special case for empty vector. 580 append(From, To); 581 return this->begin()+InsertElt; 582 } 583 584 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 585 assert(I <= this->end() && "Inserting past the end of the vector."); 586 587 size_t NumToInsert = std::distance(From, To); 588 589 // Ensure there is enough space. 590 reserve(this->size() + NumToInsert); 591 592 // Uninvalidate the iterator. 593 I = this->begin()+InsertElt; 594 595 // If there are more elements between the insertion point and the end of the 596 // range than there are being inserted, we can use a simple approach to 597 // insertion. Since we already reserved space, we know that this won't 598 // reallocate the vector. 599 if (size_t(this->end()-I) >= NumToInsert) { 600 T *OldEnd = this->end(); 601 append(std::move_iterator<iterator>(this->end() - NumToInsert), 602 std::move_iterator<iterator>(this->end())); 603 604 // Copy the existing elements that get replaced. 605 std::move_backward(I, OldEnd-NumToInsert, OldEnd); 606 607 std::copy(From, To, I); 608 return I; 609 } 610 611 // Otherwise, we're inserting more elements than exist already, and we're 612 // not inserting at the end. 613 614 // Move over the elements that we're about to overwrite. 615 T *OldEnd = this->end(); 616 this->setEnd(this->end() + NumToInsert); 617 size_t NumOverwritten = OldEnd-I; 618 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 619 620 // Replace the overwritten part. 621 for (T *J = I; NumOverwritten > 0; --NumOverwritten) { 622 *J = *From; 623 ++J; ++From; 624 } 625 626 // Insert the non-overwritten middle part. 627 this->uninitialized_copy(From, To, OldEnd); 628 return I; 629 } 630 631 void insert(iterator I, std::initializer_list<T> IL) { 632 insert(I, IL.begin(), IL.end()); 633 } 634 635 template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) { 636 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) 637 this->grow(); 638 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); 639 this->setEnd(this->end() + 1); 640 } 641 642 SmallVectorImpl &operator=(const SmallVectorImpl &RHS); 643 644 SmallVectorImpl &operator=(SmallVectorImpl &&RHS); 645 646 bool operator==(const SmallVectorImpl &RHS) const { 647 if (this->size() != RHS.size()) return false; 648 return std::equal(this->begin(), this->end(), RHS.begin()); 649 } 650 bool operator!=(const SmallVectorImpl &RHS) const { 651 return !(*this == RHS); 652 } 653 654 bool operator<(const SmallVectorImpl &RHS) const { 655 return std::lexicographical_compare(this->begin(), this->end(), 656 RHS.begin(), RHS.end()); 657 } 658 659 /// Set the array size to \p N, which the current array must have enough 660 /// capacity for. 661 /// 662 /// This does not construct or destroy any elements in the vector. 663 /// 664 /// Clients can use this in conjunction with capacity() to write past the end 665 /// of the buffer when they know that more elements are available, and only 666 /// update the size later. This avoids the cost of value initializing elements 667 /// which will only be overwritten. 668 void set_size(size_type N) { 669 assert(N <= this->capacity()); 670 this->setEnd(this->begin() + N); 671 } 672 }; 673 674 template <typename T> 675 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 676 if (this == &RHS) return; 677 678 // We can only avoid copying elements if neither vector is small. 679 if (!this->isSmall() && !RHS.isSmall()) { 680 std::swap(this->BeginX, RHS.BeginX); 681 std::swap(this->EndX, RHS.EndX); 682 std::swap(this->CapacityX, RHS.CapacityX); 683 return; 684 } 685 if (RHS.size() > this->capacity()) 686 this->grow(RHS.size()); 687 if (this->size() > RHS.capacity()) 688 RHS.grow(this->size()); 689 690 // Swap the shared elements. 691 size_t NumShared = this->size(); 692 if (NumShared > RHS.size()) NumShared = RHS.size(); 693 for (size_type i = 0; i != NumShared; ++i) 694 std::swap((*this)[i], RHS[i]); 695 696 // Copy over the extra elts. 697 if (this->size() > RHS.size()) { 698 size_t EltDiff = this->size() - RHS.size(); 699 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); 700 RHS.setEnd(RHS.end()+EltDiff); 701 this->destroy_range(this->begin()+NumShared, this->end()); 702 this->setEnd(this->begin()+NumShared); 703 } else if (RHS.size() > this->size()) { 704 size_t EltDiff = RHS.size() - this->size(); 705 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); 706 this->setEnd(this->end() + EltDiff); 707 this->destroy_range(RHS.begin()+NumShared, RHS.end()); 708 RHS.setEnd(RHS.begin()+NumShared); 709 } 710 } 711 712 template <typename T> 713 SmallVectorImpl<T> &SmallVectorImpl<T>:: 714 operator=(const SmallVectorImpl<T> &RHS) { 715 // Avoid self-assignment. 716 if (this == &RHS) return *this; 717 718 // If we already have sufficient space, assign the common elements, then 719 // destroy any excess. 720 size_t RHSSize = RHS.size(); 721 size_t CurSize = this->size(); 722 if (CurSize >= RHSSize) { 723 // Assign common elements. 724 iterator NewEnd; 725 if (RHSSize) 726 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); 727 else 728 NewEnd = this->begin(); 729 730 // Destroy excess elements. 731 this->destroy_range(NewEnd, this->end()); 732 733 // Trim. 734 this->setEnd(NewEnd); 735 return *this; 736 } 737 738 // If we have to grow to have enough elements, destroy the current elements. 739 // This allows us to avoid copying them during the grow. 740 // FIXME: don't do this if they're efficiently moveable. 741 if (this->capacity() < RHSSize) { 742 // Destroy current elements. 743 this->destroy_range(this->begin(), this->end()); 744 this->setEnd(this->begin()); 745 CurSize = 0; 746 this->grow(RHSSize); 747 } else if (CurSize) { 748 // Otherwise, use assignment for the already-constructed elements. 749 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); 750 } 751 752 // Copy construct the new elements in place. 753 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), 754 this->begin()+CurSize); 755 756 // Set end. 757 this->setEnd(this->begin()+RHSSize); 758 return *this; 759 } 760 761 template <typename T> 762 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { 763 // Avoid self-assignment. 764 if (this == &RHS) return *this; 765 766 // If the RHS isn't small, clear this vector and then steal its buffer. 767 if (!RHS.isSmall()) { 768 this->destroy_range(this->begin(), this->end()); 769 if (!this->isSmall()) free(this->begin()); 770 this->BeginX = RHS.BeginX; 771 this->EndX = RHS.EndX; 772 this->CapacityX = RHS.CapacityX; 773 RHS.resetToSmall(); 774 return *this; 775 } 776 777 // If we already have sufficient space, assign the common elements, then 778 // destroy any excess. 779 size_t RHSSize = RHS.size(); 780 size_t CurSize = this->size(); 781 if (CurSize >= RHSSize) { 782 // Assign common elements. 783 iterator NewEnd = this->begin(); 784 if (RHSSize) 785 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd); 786 787 // Destroy excess elements and trim the bounds. 788 this->destroy_range(NewEnd, this->end()); 789 this->setEnd(NewEnd); 790 791 // Clear the RHS. 792 RHS.clear(); 793 794 return *this; 795 } 796 797 // If we have to grow to have enough elements, destroy the current elements. 798 // This allows us to avoid copying them during the grow. 799 // FIXME: this may not actually make any sense if we can efficiently move 800 // elements. 801 if (this->capacity() < RHSSize) { 802 // Destroy current elements. 803 this->destroy_range(this->begin(), this->end()); 804 this->setEnd(this->begin()); 805 CurSize = 0; 806 this->grow(RHSSize); 807 } else if (CurSize) { 808 // Otherwise, use assignment for the already-constructed elements. 809 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin()); 810 } 811 812 // Move-construct the new elements in place. 813 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), 814 this->begin()+CurSize); 815 816 // Set end. 817 this->setEnd(this->begin()+RHSSize); 818 819 RHS.clear(); 820 return *this; 821 } 822 823 /// Storage for the SmallVector elements which aren't contained in 824 /// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1' 825 /// element is in the base class. This is specialized for the N=1 and N=0 cases 826 /// to avoid allocating unnecessary storage. 827 template <typename T, unsigned N> 828 struct SmallVectorStorage { 829 typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1]; 830 }; 831 template <typename T> struct SmallVectorStorage<T, 1> {}; 832 template <typename T> struct SmallVectorStorage<T, 0> {}; 833 834 /// This is a 'vector' (really, a variable-sized array), optimized 835 /// for the case when the array is small. It contains some number of elements 836 /// in-place, which allows it to avoid heap allocation when the actual number of 837 /// elements is below that threshold. This allows normal "small" cases to be 838 /// fast without losing generality for large inputs. 839 /// 840 /// Note that this does not attempt to be exception safe. 841 /// 842 template <typename T, unsigned N> 843 class SmallVector : public SmallVectorImpl<T> { 844 /// Inline space for elements which aren't stored in the base class. 845 SmallVectorStorage<T, N> Storage; 846 847 public: 848 SmallVector() : SmallVectorImpl<T>(N) { 849 } 850 851 explicit SmallVector(size_t Size, const T &Value = T()) 852 : SmallVectorImpl<T>(N) { 853 this->assign(Size, Value); 854 } 855 856 template<typename ItTy> 857 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { 858 this->append(S, E); 859 } 860 861 template <typename RangeTy> 862 explicit SmallVector(const iterator_range<RangeTy> &R) 863 : SmallVectorImpl<T>(N) { 864 this->append(R.begin(), R.end()); 865 } 866 867 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) { 868 this->assign(IL); 869 } 870 871 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { 872 if (!RHS.empty()) 873 SmallVectorImpl<T>::operator=(RHS); 874 } 875 876 const SmallVector &operator=(const SmallVector &RHS) { 877 SmallVectorImpl<T>::operator=(RHS); 878 return *this; 879 } 880 881 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { 882 if (!RHS.empty()) 883 SmallVectorImpl<T>::operator=(::std::move(RHS)); 884 } 885 886 const SmallVector &operator=(SmallVector &&RHS) { 887 SmallVectorImpl<T>::operator=(::std::move(RHS)); 888 return *this; 889 } 890 891 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) { 892 if (!RHS.empty()) 893 SmallVectorImpl<T>::operator=(::std::move(RHS)); 894 } 895 896 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) { 897 SmallVectorImpl<T>::operator=(::std::move(RHS)); 898 return *this; 899 } 900 901 const SmallVector &operator=(std::initializer_list<T> IL) { 902 this->assign(IL); 903 return *this; 904 } 905 }; 906 907 template<typename T, unsigned N> 908 static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { 909 return X.capacity_in_bytes(); 910 } 911 912 } // end namespace llvm 913 914 namespace std { 915 916 /// Implement std::swap in terms of SmallVector swap. 917 template<typename T> 918 inline void 919 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 920 LHS.swap(RHS); 921 } 922 923 /// Implement std::swap in terms of SmallVector swap. 924 template<typename T, unsigned N> 925 inline void 926 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 927 LHS.swap(RHS); 928 } 929 930 } // end namespace std 931 932 #endif // LLVM_ADT_SMALLVECTOR_H 933