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