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 /// \file 10 /// This file defines the SmallVector class. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SMALLVECTOR_H 15 #define LLVM_ADT_SMALLVECTOR_H 16 17 #include "llvm/Support/Compiler.h" 18 #include "llvm/Support/type_traits.h" 19 #include <algorithm> 20 #include <cassert> 21 #include <cstddef> 22 #include <cstdlib> 23 #include <cstring> 24 #include <functional> 25 #include <initializer_list> 26 #include <iterator> 27 #include <limits> 28 #include <memory> 29 #include <new> 30 #include <type_traits> 31 #include <utility> 32 33 namespace llvm { 34 35 template <typename T> class ArrayRef; 36 37 template <typename IteratorT> class iterator_range; 38 39 template <class Iterator> 40 using EnableIfConvertibleToInputIterator = std::enable_if_t<std::is_convertible< 41 typename std::iterator_traits<Iterator>::iterator_category, 42 std::input_iterator_tag>::value>; 43 44 /// This is all the stuff common to all SmallVectors. 45 /// 46 /// The template parameter specifies the type which should be used to hold the 47 /// Size and Capacity of the SmallVector, so it can be adjusted. 48 /// Using 32 bit size is desirable to shrink the size of the SmallVector. 49 /// Using 64 bit size is desirable for cases like SmallVector<char>, where a 50 /// 32 bit size would limit the vector to ~4GB. SmallVectors are used for 51 /// buffering bitcode output - which can exceed 4GB. 52 template <class Size_T> class SmallVectorBase { 53 protected: 54 void *BeginX; 55 Size_T Size = 0, Capacity; 56 57 /// The maximum value of the Size_T used. 58 static constexpr size_t SizeTypeMax() { 59 return std::numeric_limits<Size_T>::max(); 60 } 61 62 SmallVectorBase() = delete; 63 SmallVectorBase(void *FirstEl, size_t TotalCapacity) 64 : BeginX(FirstEl), Capacity(TotalCapacity) {} 65 66 /// This is a helper for \a grow() that's out of line to reduce code 67 /// duplication. This function will report a fatal error if it can't grow at 68 /// least to \p MinSize. 69 void *mallocForGrow(void *FirstEl, size_t MinSize, size_t TSize, 70 size_t &NewCapacity); 71 72 /// This is an implementation of the grow() method which only works 73 /// on POD-like data types and is out of line to reduce code duplication. 74 /// This function will report a fatal error if it cannot increase capacity. 75 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize); 76 77 /// If vector was first created with capacity 0, getFirstEl() points to the 78 /// memory right after, an area unallocated. If a subsequent allocation, 79 /// that grows the vector, happens to return the same pointer as getFirstEl(), 80 /// get a new allocation, otherwise isSmall() will falsely return that no 81 /// allocation was done (true) and the memory will not be freed in the 82 /// destructor. If a VSize is given (vector size), also copy that many 83 /// elements to the new allocation - used if realloca fails to increase 84 /// space, and happens to allocate precisely at BeginX. 85 /// This is unlikely to be called often, but resolves a memory leak when the 86 /// situation does occur. 87 void *replaceAllocation(void *NewElts, size_t TSize, size_t NewCapacity, 88 size_t VSize = 0); 89 90 public: 91 size_t size() const { return Size; } 92 size_t capacity() const { return Capacity; } 93 94 [[nodiscard]] bool empty() const { return !Size; } 95 96 protected: 97 /// Set the array size to \p N, which the current array must have enough 98 /// capacity for. 99 /// 100 /// This does not construct or destroy any elements in the vector. 101 void set_size(size_t N) { 102 assert(N <= capacity()); 103 Size = N; 104 } 105 }; 106 107 template <class T> 108 using SmallVectorSizeType = 109 std::conditional_t<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t, 110 uint32_t>; 111 112 /// Figure out the offset of the first element. 113 template <class T, typename = void> struct SmallVectorAlignmentAndSize { 114 alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof( 115 SmallVectorBase<SmallVectorSizeType<T>>)]; 116 alignas(T) char FirstEl[sizeof(T)]; 117 }; 118 119 /// This is the part of SmallVectorTemplateBase which does not depend on whether 120 /// the type T is a POD. The extra dummy template argument is used by ArrayRef 121 /// to avoid unnecessarily requiring T to be complete. 122 template <typename T, typename = void> 123 class SmallVectorTemplateCommon 124 : public SmallVectorBase<SmallVectorSizeType<T>> { 125 using Base = SmallVectorBase<SmallVectorSizeType<T>>; 126 127 protected: 128 /// Find the address of the first element. For this pointer math to be valid 129 /// with small-size of 0 for T with lots of alignment, it's important that 130 /// SmallVectorStorage is properly-aligned even for small-size of 0. 131 void *getFirstEl() const { 132 return const_cast<void *>(reinterpret_cast<const void *>( 133 reinterpret_cast<const char *>(this) + 134 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl))); 135 } 136 // Space after 'FirstEl' is clobbered, do not add any instance vars after it. 137 138 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {} 139 140 void grow_pod(size_t MinSize, size_t TSize) { 141 Base::grow_pod(getFirstEl(), MinSize, TSize); 142 } 143 144 /// Return true if this is a smallvector which has not had dynamic 145 /// memory allocated for it. 146 bool isSmall() const { return this->BeginX == getFirstEl(); } 147 148 /// Put this vector in a state of being small. 149 void resetToSmall() { 150 this->BeginX = getFirstEl(); 151 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. 152 } 153 154 /// Return true if V is an internal reference to the given range. 155 bool isReferenceToRange(const void *V, const void *First, const void *Last) const { 156 // Use std::less to avoid UB. 157 std::less<> LessThan; 158 return !LessThan(V, First) && LessThan(V, Last); 159 } 160 161 /// Return true if V is an internal reference to this vector. 162 bool isReferenceToStorage(const void *V) const { 163 return isReferenceToRange(V, this->begin(), this->end()); 164 } 165 166 /// Return true if First and Last form a valid (possibly empty) range in this 167 /// vector's storage. 168 bool isRangeInStorage(const void *First, const void *Last) const { 169 // Use std::less to avoid UB. 170 std::less<> LessThan; 171 return !LessThan(First, this->begin()) && !LessThan(Last, First) && 172 !LessThan(this->end(), Last); 173 } 174 175 /// Return true unless Elt will be invalidated by resizing the vector to 176 /// NewSize. 177 bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) { 178 // Past the end. 179 if (LLVM_LIKELY(!isReferenceToStorage(Elt))) 180 return true; 181 182 // Return false if Elt will be destroyed by shrinking. 183 if (NewSize <= this->size()) 184 return Elt < this->begin() + NewSize; 185 186 // Return false if we need to grow. 187 return NewSize <= this->capacity(); 188 } 189 190 /// Check whether Elt will be invalidated by resizing the vector to NewSize. 191 void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) { 192 assert(isSafeToReferenceAfterResize(Elt, NewSize) && 193 "Attempting to reference an element of the vector in an operation " 194 "that invalidates it"); 195 } 196 197 /// Check whether Elt will be invalidated by increasing the size of the 198 /// vector by N. 199 void assertSafeToAdd(const void *Elt, size_t N = 1) { 200 this->assertSafeToReferenceAfterResize(Elt, this->size() + N); 201 } 202 203 /// Check whether any part of the range will be invalidated by clearing. 204 void assertSafeToReferenceAfterClear(const T *From, const T *To) { 205 if (From == To) 206 return; 207 this->assertSafeToReferenceAfterResize(From, 0); 208 this->assertSafeToReferenceAfterResize(To - 1, 0); 209 } 210 template < 211 class ItTy, 212 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value, 213 bool> = false> 214 void assertSafeToReferenceAfterClear(ItTy, ItTy) {} 215 216 /// Check whether any part of the range will be invalidated by growing. 217 void assertSafeToAddRange(const T *From, const T *To) { 218 if (From == To) 219 return; 220 this->assertSafeToAdd(From, To - From); 221 this->assertSafeToAdd(To - 1, To - From); 222 } 223 template < 224 class ItTy, 225 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value, 226 bool> = false> 227 void assertSafeToAddRange(ItTy, ItTy) {} 228 229 /// Reserve enough space to add one element, and return the updated element 230 /// pointer in case it was a reference to the storage. 231 template <class U> 232 static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt, 233 size_t N) { 234 size_t NewSize = This->size() + N; 235 if (LLVM_LIKELY(NewSize <= This->capacity())) 236 return &Elt; 237 238 bool ReferencesStorage = false; 239 int64_t Index = -1; 240 if (!U::TakesParamByValue) { 241 if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) { 242 ReferencesStorage = true; 243 Index = &Elt - This->begin(); 244 } 245 } 246 This->grow(NewSize); 247 return ReferencesStorage ? This->begin() + Index : &Elt; 248 } 249 250 public: 251 using size_type = size_t; 252 using difference_type = ptrdiff_t; 253 using value_type = T; 254 using iterator = T *; 255 using const_iterator = const T *; 256 257 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 258 using reverse_iterator = std::reverse_iterator<iterator>; 259 260 using reference = T &; 261 using const_reference = const T &; 262 using pointer = T *; 263 using const_pointer = const T *; 264 265 using Base::capacity; 266 using Base::empty; 267 using Base::size; 268 269 // forward iterator creation methods. 270 iterator begin() { return (iterator)this->BeginX; } 271 const_iterator begin() const { return (const_iterator)this->BeginX; } 272 iterator end() { return begin() + size(); } 273 const_iterator end() const { return begin() + size(); } 274 275 // reverse iterator creation methods. 276 reverse_iterator rbegin() { return reverse_iterator(end()); } 277 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 278 reverse_iterator rend() { return reverse_iterator(begin()); } 279 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 280 281 size_type size_in_bytes() const { return size() * sizeof(T); } 282 size_type max_size() const { 283 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T)); 284 } 285 286 size_t capacity_in_bytes() const { return capacity() * sizeof(T); } 287 288 /// Return a pointer to the vector's buffer, even if empty(). 289 pointer data() { return pointer(begin()); } 290 /// Return a pointer to the vector's buffer, even if empty(). 291 const_pointer data() const { return const_pointer(begin()); } 292 293 reference operator[](size_type idx) { 294 assert(idx < size()); 295 return begin()[idx]; 296 } 297 const_reference operator[](size_type idx) const { 298 assert(idx < size()); 299 return begin()[idx]; 300 } 301 302 reference front() { 303 assert(!empty()); 304 return begin()[0]; 305 } 306 const_reference front() const { 307 assert(!empty()); 308 return begin()[0]; 309 } 310 311 reference back() { 312 assert(!empty()); 313 return end()[-1]; 314 } 315 const_reference back() const { 316 assert(!empty()); 317 return end()[-1]; 318 } 319 }; 320 321 /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put 322 /// method implementations that are designed to work with non-trivial T's. 323 /// 324 /// We approximate is_trivially_copyable with trivial move/copy construction and 325 /// trivial destruction. While the standard doesn't specify that you're allowed 326 /// copy these types with memcpy, there is no way for the type to observe this. 327 /// This catches the important case of std::pair<POD, POD>, which is not 328 /// trivially assignable. 329 template <typename T, bool = (std::is_trivially_copy_constructible<T>::value) && 330 (std::is_trivially_move_constructible<T>::value) && 331 std::is_trivially_destructible<T>::value> 332 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { 333 friend class SmallVectorTemplateCommon<T>; 334 335 protected: 336 static constexpr bool TakesParamByValue = false; 337 using ValueParamT = const T &; 338 339 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 340 341 static void destroy_range(T *S, T *E) { 342 while (S != E) { 343 --E; 344 E->~T(); 345 } 346 } 347 348 /// Move the range [I, E) into the uninitialized memory starting with "Dest", 349 /// constructing elements as needed. 350 template<typename It1, typename It2> 351 static void uninitialized_move(It1 I, It1 E, It2 Dest) { 352 std::uninitialized_move(I, E, Dest); 353 } 354 355 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", 356 /// constructing elements as needed. 357 template<typename It1, typename It2> 358 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 359 std::uninitialized_copy(I, E, Dest); 360 } 361 362 /// Grow the allocated memory (without initializing new elements), doubling 363 /// the size of the allocated memory. Guarantees space for at least one more 364 /// element, or MinSize more elements if specified. 365 void grow(size_t MinSize = 0); 366 367 /// Create a new allocation big enough for \p MinSize and pass back its size 368 /// in \p NewCapacity. This is the first section of \a grow(). 369 T *mallocForGrow(size_t MinSize, size_t &NewCapacity); 370 371 /// Move existing elements over to the new allocation \p NewElts, the middle 372 /// section of \a grow(). 373 void moveElementsForGrow(T *NewElts); 374 375 /// Transfer ownership of the allocation, finishing up \a grow(). 376 void takeAllocationForGrow(T *NewElts, size_t NewCapacity); 377 378 /// Reserve enough space to add one element, and return the updated element 379 /// pointer in case it was a reference to the storage. 380 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) { 381 return this->reserveForParamAndGetAddressImpl(this, Elt, N); 382 } 383 384 /// Reserve enough space to add one element, and return the updated element 385 /// pointer in case it was a reference to the storage. 386 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) { 387 return const_cast<T *>( 388 this->reserveForParamAndGetAddressImpl(this, Elt, N)); 389 } 390 391 static T &&forward_value_param(T &&V) { return std::move(V); } 392 static const T &forward_value_param(const T &V) { return V; } 393 394 void growAndAssign(size_t NumElts, const T &Elt) { 395 // Grow manually in case Elt is an internal reference. 396 size_t NewCapacity; 397 T *NewElts = mallocForGrow(NumElts, NewCapacity); 398 std::uninitialized_fill_n(NewElts, NumElts, Elt); 399 this->destroy_range(this->begin(), this->end()); 400 takeAllocationForGrow(NewElts, NewCapacity); 401 this->set_size(NumElts); 402 } 403 404 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) { 405 // Grow manually in case one of Args is an internal reference. 406 size_t NewCapacity; 407 T *NewElts = mallocForGrow(0, NewCapacity); 408 ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...); 409 moveElementsForGrow(NewElts); 410 takeAllocationForGrow(NewElts, NewCapacity); 411 this->set_size(this->size() + 1); 412 return this->back(); 413 } 414 415 public: 416 void push_back(const T &Elt) { 417 const T *EltPtr = reserveForParamAndGetAddress(Elt); 418 ::new ((void *)this->end()) T(*EltPtr); 419 this->set_size(this->size() + 1); 420 } 421 422 void push_back(T &&Elt) { 423 T *EltPtr = reserveForParamAndGetAddress(Elt); 424 ::new ((void *)this->end()) T(::std::move(*EltPtr)); 425 this->set_size(this->size() + 1); 426 } 427 428 void pop_back() { 429 this->set_size(this->size() - 1); 430 this->end()->~T(); 431 } 432 }; 433 434 // Define this out-of-line to dissuade the C++ compiler from inlining it. 435 template <typename T, bool TriviallyCopyable> 436 void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) { 437 size_t NewCapacity; 438 T *NewElts = mallocForGrow(MinSize, NewCapacity); 439 moveElementsForGrow(NewElts); 440 takeAllocationForGrow(NewElts, NewCapacity); 441 } 442 443 template <typename T, bool TriviallyCopyable> 444 T *SmallVectorTemplateBase<T, TriviallyCopyable>::mallocForGrow( 445 size_t MinSize, size_t &NewCapacity) { 446 return static_cast<T *>( 447 SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow( 448 this->getFirstEl(), MinSize, sizeof(T), NewCapacity)); 449 } 450 451 // Define this out-of-line to dissuade the C++ compiler from inlining it. 452 template <typename T, bool TriviallyCopyable> 453 void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow( 454 T *NewElts) { 455 // Move the elements over. 456 this->uninitialized_move(this->begin(), this->end(), NewElts); 457 458 // Destroy the original elements. 459 destroy_range(this->begin(), this->end()); 460 } 461 462 // Define this out-of-line to dissuade the C++ compiler from inlining it. 463 template <typename T, bool TriviallyCopyable> 464 void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow( 465 T *NewElts, size_t NewCapacity) { 466 // If this wasn't grown from the inline copy, deallocate the old space. 467 if (!this->isSmall()) 468 free(this->begin()); 469 470 this->BeginX = NewElts; 471 this->Capacity = NewCapacity; 472 } 473 474 /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put 475 /// method implementations that are designed to work with trivially copyable 476 /// T's. This allows using memcpy in place of copy/move construction and 477 /// skipping destruction. 478 template <typename T> 479 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { 480 friend class SmallVectorTemplateCommon<T>; 481 482 protected: 483 /// True if it's cheap enough to take parameters by value. Doing so avoids 484 /// overhead related to mitigations for reference invalidation. 485 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *); 486 487 /// Either const T& or T, depending on whether it's cheap enough to take 488 /// parameters by value. 489 using ValueParamT = std::conditional_t<TakesParamByValue, T, const T &>; 490 491 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} 492 493 // No need to do a destroy loop for POD's. 494 static void destroy_range(T *, T *) {} 495 496 /// Move the range [I, E) onto the uninitialized memory 497 /// starting with "Dest", constructing elements into it as needed. 498 template<typename It1, typename It2> 499 static void uninitialized_move(It1 I, It1 E, It2 Dest) { 500 // Just do a copy. 501 uninitialized_copy(I, E, Dest); 502 } 503 504 /// Copy the range [I, E) onto the uninitialized memory 505 /// starting with "Dest", constructing elements into it as needed. 506 template<typename It1, typename It2> 507 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 508 // Arbitrary iterator types; just use the basic implementation. 509 std::uninitialized_copy(I, E, Dest); 510 } 511 512 /// Copy the range [I, E) onto the uninitialized memory 513 /// starting with "Dest", constructing elements into it as needed. 514 template <typename T1, typename T2> 515 static void uninitialized_copy( 516 T1 *I, T1 *E, T2 *Dest, 517 std::enable_if_t<std::is_same<std::remove_const_t<T1>, T2>::value> * = 518 nullptr) { 519 // Use memcpy for PODs iterated by pointers (which includes SmallVector 520 // iterators): std::uninitialized_copy optimizes to memmove, but we can 521 // use memcpy here. Note that I and E are iterators and thus might be 522 // invalid for memcpy if they are equal. 523 if (I != E) 524 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T)); 525 } 526 527 /// Double the size of the allocated memory, guaranteeing space for at 528 /// least one more element or MinSize if specified. 529 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); } 530 531 /// Reserve enough space to add one element, and return the updated element 532 /// pointer in case it was a reference to the storage. 533 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) { 534 return this->reserveForParamAndGetAddressImpl(this, Elt, N); 535 } 536 537 /// Reserve enough space to add one element, and return the updated element 538 /// pointer in case it was a reference to the storage. 539 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) { 540 return const_cast<T *>( 541 this->reserveForParamAndGetAddressImpl(this, Elt, N)); 542 } 543 544 /// Copy \p V or return a reference, depending on \a ValueParamT. 545 static ValueParamT forward_value_param(ValueParamT V) { return V; } 546 547 void growAndAssign(size_t NumElts, T Elt) { 548 // Elt has been copied in case it's an internal reference, side-stepping 549 // reference invalidation problems without losing the realloc optimization. 550 this->set_size(0); 551 this->grow(NumElts); 552 std::uninitialized_fill_n(this->begin(), NumElts, Elt); 553 this->set_size(NumElts); 554 } 555 556 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) { 557 // Use push_back with a copy in case Args has an internal reference, 558 // side-stepping reference invalidation problems without losing the realloc 559 // optimization. 560 push_back(T(std::forward<ArgTypes>(Args)...)); 561 return this->back(); 562 } 563 564 public: 565 void push_back(ValueParamT Elt) { 566 const T *EltPtr = reserveForParamAndGetAddress(Elt); 567 memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T)); 568 this->set_size(this->size() + 1); 569 } 570 571 void pop_back() { this->set_size(this->size() - 1); } 572 }; 573 574 /// This class consists of common code factored out of the SmallVector class to 575 /// reduce code duplication based on the SmallVector 'N' template parameter. 576 template <typename T> 577 class SmallVectorImpl : public SmallVectorTemplateBase<T> { 578 using SuperClass = SmallVectorTemplateBase<T>; 579 580 public: 581 using iterator = typename SuperClass::iterator; 582 using const_iterator = typename SuperClass::const_iterator; 583 using reference = typename SuperClass::reference; 584 using size_type = typename SuperClass::size_type; 585 586 protected: 587 using SmallVectorTemplateBase<T>::TakesParamByValue; 588 using ValueParamT = typename SuperClass::ValueParamT; 589 590 // Default ctor - Initialize to empty. 591 explicit SmallVectorImpl(unsigned N) 592 : SmallVectorTemplateBase<T>(N) {} 593 594 void assignRemote(SmallVectorImpl &&RHS) { 595 this->destroy_range(this->begin(), this->end()); 596 if (!this->isSmall()) 597 free(this->begin()); 598 this->BeginX = RHS.BeginX; 599 this->Size = RHS.Size; 600 this->Capacity = RHS.Capacity; 601 RHS.resetToSmall(); 602 } 603 604 public: 605 SmallVectorImpl(const SmallVectorImpl &) = delete; 606 607 ~SmallVectorImpl() { 608 // Subclass has already destructed this vector's elements. 609 // If this wasn't grown from the inline copy, deallocate the old space. 610 if (!this->isSmall()) 611 free(this->begin()); 612 } 613 614 void clear() { 615 this->destroy_range(this->begin(), this->end()); 616 this->Size = 0; 617 } 618 619 private: 620 // Make set_size() private to avoid misuse in subclasses. 621 using SuperClass::set_size; 622 623 template <bool ForOverwrite> void resizeImpl(size_type N) { 624 if (N == this->size()) 625 return; 626 627 if (N < this->size()) { 628 this->truncate(N); 629 return; 630 } 631 632 this->reserve(N); 633 for (auto I = this->end(), E = this->begin() + N; I != E; ++I) 634 if (ForOverwrite) 635 new (&*I) T; 636 else 637 new (&*I) T(); 638 this->set_size(N); 639 } 640 641 public: 642 void resize(size_type N) { resizeImpl<false>(N); } 643 644 /// Like resize, but \ref T is POD, the new values won't be initialized. 645 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); } 646 647 /// Like resize, but requires that \p N is less than \a size(). 648 void truncate(size_type N) { 649 assert(this->size() >= N && "Cannot increase size with truncate"); 650 this->destroy_range(this->begin() + N, this->end()); 651 this->set_size(N); 652 } 653 654 void resize(size_type N, ValueParamT NV) { 655 if (N == this->size()) 656 return; 657 658 if (N < this->size()) { 659 this->truncate(N); 660 return; 661 } 662 663 // N > this->size(). Defer to append. 664 this->append(N - this->size(), NV); 665 } 666 667 void reserve(size_type N) { 668 if (this->capacity() < N) 669 this->grow(N); 670 } 671 672 void pop_back_n(size_type NumItems) { 673 assert(this->size() >= NumItems); 674 truncate(this->size() - NumItems); 675 } 676 677 [[nodiscard]] T pop_back_val() { 678 T Result = ::std::move(this->back()); 679 this->pop_back(); 680 return Result; 681 } 682 683 void swap(SmallVectorImpl &RHS); 684 685 /// Add the specified range to the end of the SmallVector. 686 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> 687 void append(ItTy in_start, ItTy in_end) { 688 this->assertSafeToAddRange(in_start, in_end); 689 size_type NumInputs = std::distance(in_start, in_end); 690 this->reserve(this->size() + NumInputs); 691 this->uninitialized_copy(in_start, in_end, this->end()); 692 this->set_size(this->size() + NumInputs); 693 } 694 695 /// Append \p NumInputs copies of \p Elt to the end. 696 void append(size_type NumInputs, ValueParamT Elt) { 697 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs); 698 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr); 699 this->set_size(this->size() + NumInputs); 700 } 701 702 void append(std::initializer_list<T> IL) { 703 append(IL.begin(), IL.end()); 704 } 705 706 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); } 707 708 void assign(size_type NumElts, ValueParamT Elt) { 709 // Note that Elt could be an internal reference. 710 if (NumElts > this->capacity()) { 711 this->growAndAssign(NumElts, Elt); 712 return; 713 } 714 715 // Assign over existing elements. 716 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt); 717 if (NumElts > this->size()) 718 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt); 719 else if (NumElts < this->size()) 720 this->destroy_range(this->begin() + NumElts, this->end()); 721 this->set_size(NumElts); 722 } 723 724 // FIXME: Consider assigning over existing elements, rather than clearing & 725 // re-initializing them - for all assign(...) variants. 726 727 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> 728 void assign(ItTy in_start, ItTy in_end) { 729 this->assertSafeToReferenceAfterClear(in_start, in_end); 730 clear(); 731 append(in_start, in_end); 732 } 733 734 void assign(std::initializer_list<T> IL) { 735 clear(); 736 append(IL); 737 } 738 739 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); } 740 741 iterator erase(const_iterator CI) { 742 // Just cast away constness because this is a non-const member function. 743 iterator I = const_cast<iterator>(CI); 744 745 assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds."); 746 747 iterator N = I; 748 // Shift all elts down one. 749 std::move(I+1, this->end(), I); 750 // Drop the last elt. 751 this->pop_back(); 752 return(N); 753 } 754 755 iterator erase(const_iterator CS, const_iterator CE) { 756 // Just cast away constness because this is a non-const member function. 757 iterator S = const_cast<iterator>(CS); 758 iterator E = const_cast<iterator>(CE); 759 760 assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds."); 761 762 iterator N = S; 763 // Shift all elts down. 764 iterator I = std::move(E, this->end(), S); 765 // Drop the last elts. 766 this->destroy_range(I, this->end()); 767 this->set_size(I - this->begin()); 768 return(N); 769 } 770 771 private: 772 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) { 773 // Callers ensure that ArgType is derived from T. 774 static_assert( 775 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, 776 T>::value, 777 "ArgType must be derived from T!"); 778 779 if (I == this->end()) { // Important special case for empty vector. 780 this->push_back(::std::forward<ArgType>(Elt)); 781 return this->end()-1; 782 } 783 784 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."); 785 786 // Grow if necessary. 787 size_t Index = I - this->begin(); 788 std::remove_reference_t<ArgType> *EltPtr = 789 this->reserveForParamAndGetAddress(Elt); 790 I = this->begin() + Index; 791 792 ::new ((void*) this->end()) T(::std::move(this->back())); 793 // Push everything else over. 794 std::move_backward(I, this->end()-1, this->end()); 795 this->set_size(this->size() + 1); 796 797 // If we just moved the element we're inserting, be sure to update 798 // the reference (never happens if TakesParamByValue). 799 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value, 800 "ArgType must be 'T' when taking by value!"); 801 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end())) 802 ++EltPtr; 803 804 *I = ::std::forward<ArgType>(*EltPtr); 805 return I; 806 } 807 808 public: 809 iterator insert(iterator I, T &&Elt) { 810 return insert_one_impl(I, this->forward_value_param(std::move(Elt))); 811 } 812 813 iterator insert(iterator I, const T &Elt) { 814 return insert_one_impl(I, this->forward_value_param(Elt)); 815 } 816 817 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) { 818 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 819 size_t InsertElt = I - this->begin(); 820 821 if (I == this->end()) { // Important special case for empty vector. 822 append(NumToInsert, Elt); 823 return this->begin()+InsertElt; 824 } 825 826 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."); 827 828 // Ensure there is enough space, and get the (maybe updated) address of 829 // Elt. 830 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert); 831 832 // Uninvalidate the iterator. 833 I = this->begin()+InsertElt; 834 835 // If there are more elements between the insertion point and the end of the 836 // range than there are being inserted, we can use a simple approach to 837 // insertion. Since we already reserved space, we know that this won't 838 // reallocate the vector. 839 if (size_t(this->end()-I) >= NumToInsert) { 840 T *OldEnd = this->end(); 841 append(std::move_iterator<iterator>(this->end() - NumToInsert), 842 std::move_iterator<iterator>(this->end())); 843 844 // Copy the existing elements that get replaced. 845 std::move_backward(I, OldEnd-NumToInsert, OldEnd); 846 847 // If we just moved the element we're inserting, be sure to update 848 // the reference (never happens if TakesParamByValue). 849 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end()) 850 EltPtr += NumToInsert; 851 852 std::fill_n(I, NumToInsert, *EltPtr); 853 return I; 854 } 855 856 // Otherwise, we're inserting more elements than exist already, and we're 857 // not inserting at the end. 858 859 // Move over the elements that we're about to overwrite. 860 T *OldEnd = this->end(); 861 this->set_size(this->size() + NumToInsert); 862 size_t NumOverwritten = OldEnd-I; 863 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 864 865 // If we just moved the element we're inserting, be sure to update 866 // the reference (never happens if TakesParamByValue). 867 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end()) 868 EltPtr += NumToInsert; 869 870 // Replace the overwritten part. 871 std::fill_n(I, NumOverwritten, *EltPtr); 872 873 // Insert the non-overwritten middle part. 874 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr); 875 return I; 876 } 877 878 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> 879 iterator insert(iterator I, ItTy From, ItTy To) { 880 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 881 size_t InsertElt = I - this->begin(); 882 883 if (I == this->end()) { // Important special case for empty vector. 884 append(From, To); 885 return this->begin()+InsertElt; 886 } 887 888 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds."); 889 890 // Check that the reserve that follows doesn't invalidate the iterators. 891 this->assertSafeToAddRange(From, To); 892 893 size_t NumToInsert = std::distance(From, To); 894 895 // Ensure there is enough space. 896 reserve(this->size() + NumToInsert); 897 898 // Uninvalidate the iterator. 899 I = this->begin()+InsertElt; 900 901 // If there are more elements between the insertion point and the end of the 902 // range than there are being inserted, we can use a simple approach to 903 // insertion. Since we already reserved space, we know that this won't 904 // reallocate the vector. 905 if (size_t(this->end()-I) >= NumToInsert) { 906 T *OldEnd = this->end(); 907 append(std::move_iterator<iterator>(this->end() - NumToInsert), 908 std::move_iterator<iterator>(this->end())); 909 910 // Copy the existing elements that get replaced. 911 std::move_backward(I, OldEnd-NumToInsert, OldEnd); 912 913 std::copy(From, To, I); 914 return I; 915 } 916 917 // Otherwise, we're inserting more elements than exist already, and we're 918 // not inserting at the end. 919 920 // Move over the elements that we're about to overwrite. 921 T *OldEnd = this->end(); 922 this->set_size(this->size() + NumToInsert); 923 size_t NumOverwritten = OldEnd-I; 924 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); 925 926 // Replace the overwritten part. 927 for (T *J = I; NumOverwritten > 0; --NumOverwritten) { 928 *J = *From; 929 ++J; ++From; 930 } 931 932 // Insert the non-overwritten middle part. 933 this->uninitialized_copy(From, To, OldEnd); 934 return I; 935 } 936 937 void insert(iterator I, std::initializer_list<T> IL) { 938 insert(I, IL.begin(), IL.end()); 939 } 940 941 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) { 942 if (LLVM_UNLIKELY(this->size() >= this->capacity())) 943 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...); 944 945 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); 946 this->set_size(this->size() + 1); 947 return this->back(); 948 } 949 950 SmallVectorImpl &operator=(const SmallVectorImpl &RHS); 951 952 SmallVectorImpl &operator=(SmallVectorImpl &&RHS); 953 954 bool operator==(const SmallVectorImpl &RHS) const { 955 if (this->size() != RHS.size()) return false; 956 return std::equal(this->begin(), this->end(), RHS.begin()); 957 } 958 bool operator!=(const SmallVectorImpl &RHS) const { 959 return !(*this == RHS); 960 } 961 962 bool operator<(const SmallVectorImpl &RHS) const { 963 return std::lexicographical_compare(this->begin(), this->end(), 964 RHS.begin(), RHS.end()); 965 } 966 bool operator>(const SmallVectorImpl &RHS) const { return RHS < *this; } 967 bool operator<=(const SmallVectorImpl &RHS) const { return !(*this > RHS); } 968 bool operator>=(const SmallVectorImpl &RHS) const { return !(*this < RHS); } 969 }; 970 971 template <typename T> 972 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { 973 if (this == &RHS) return; 974 975 // We can only avoid copying elements if neither vector is small. 976 if (!this->isSmall() && !RHS.isSmall()) { 977 std::swap(this->BeginX, RHS.BeginX); 978 std::swap(this->Size, RHS.Size); 979 std::swap(this->Capacity, RHS.Capacity); 980 return; 981 } 982 this->reserve(RHS.size()); 983 RHS.reserve(this->size()); 984 985 // Swap the shared elements. 986 size_t NumShared = this->size(); 987 if (NumShared > RHS.size()) NumShared = RHS.size(); 988 for (size_type i = 0; i != NumShared; ++i) 989 std::swap((*this)[i], RHS[i]); 990 991 // Copy over the extra elts. 992 if (this->size() > RHS.size()) { 993 size_t EltDiff = this->size() - RHS.size(); 994 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); 995 RHS.set_size(RHS.size() + EltDiff); 996 this->destroy_range(this->begin()+NumShared, this->end()); 997 this->set_size(NumShared); 998 } else if (RHS.size() > this->size()) { 999 size_t EltDiff = RHS.size() - this->size(); 1000 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); 1001 this->set_size(this->size() + EltDiff); 1002 this->destroy_range(RHS.begin()+NumShared, RHS.end()); 1003 RHS.set_size(NumShared); 1004 } 1005 } 1006 1007 template <typename T> 1008 SmallVectorImpl<T> &SmallVectorImpl<T>:: 1009 operator=(const SmallVectorImpl<T> &RHS) { 1010 // Avoid self-assignment. 1011 if (this == &RHS) return *this; 1012 1013 // If we already have sufficient space, assign the common elements, then 1014 // destroy any excess. 1015 size_t RHSSize = RHS.size(); 1016 size_t CurSize = this->size(); 1017 if (CurSize >= RHSSize) { 1018 // Assign common elements. 1019 iterator NewEnd; 1020 if (RHSSize) 1021 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); 1022 else 1023 NewEnd = this->begin(); 1024 1025 // Destroy excess elements. 1026 this->destroy_range(NewEnd, this->end()); 1027 1028 // Trim. 1029 this->set_size(RHSSize); 1030 return *this; 1031 } 1032 1033 // If we have to grow to have enough elements, destroy the current elements. 1034 // This allows us to avoid copying them during the grow. 1035 // FIXME: don't do this if they're efficiently moveable. 1036 if (this->capacity() < RHSSize) { 1037 // Destroy current elements. 1038 this->clear(); 1039 CurSize = 0; 1040 this->grow(RHSSize); 1041 } else if (CurSize) { 1042 // Otherwise, use assignment for the already-constructed elements. 1043 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); 1044 } 1045 1046 // Copy construct the new elements in place. 1047 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), 1048 this->begin()+CurSize); 1049 1050 // Set end. 1051 this->set_size(RHSSize); 1052 return *this; 1053 } 1054 1055 template <typename T> 1056 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { 1057 // Avoid self-assignment. 1058 if (this == &RHS) return *this; 1059 1060 // If the RHS isn't small, clear this vector and then steal its buffer. 1061 if (!RHS.isSmall()) { 1062 this->assignRemote(std::move(RHS)); 1063 return *this; 1064 } 1065 1066 // If we already have sufficient space, assign the common elements, then 1067 // destroy any excess. 1068 size_t RHSSize = RHS.size(); 1069 size_t CurSize = this->size(); 1070 if (CurSize >= RHSSize) { 1071 // Assign common elements. 1072 iterator NewEnd = this->begin(); 1073 if (RHSSize) 1074 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd); 1075 1076 // Destroy excess elements and trim the bounds. 1077 this->destroy_range(NewEnd, this->end()); 1078 this->set_size(RHSSize); 1079 1080 // Clear the RHS. 1081 RHS.clear(); 1082 1083 return *this; 1084 } 1085 1086 // If we have to grow to have enough elements, destroy the current elements. 1087 // This allows us to avoid copying them during the grow. 1088 // FIXME: this may not actually make any sense if we can efficiently move 1089 // elements. 1090 if (this->capacity() < RHSSize) { 1091 // Destroy current elements. 1092 this->clear(); 1093 CurSize = 0; 1094 this->grow(RHSSize); 1095 } else if (CurSize) { 1096 // Otherwise, use assignment for the already-constructed elements. 1097 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin()); 1098 } 1099 1100 // Move-construct the new elements in place. 1101 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), 1102 this->begin()+CurSize); 1103 1104 // Set end. 1105 this->set_size(RHSSize); 1106 1107 RHS.clear(); 1108 return *this; 1109 } 1110 1111 /// Storage for the SmallVector elements. This is specialized for the N=0 case 1112 /// to avoid allocating unnecessary storage. 1113 template <typename T, unsigned N> 1114 struct SmallVectorStorage { 1115 alignas(T) char InlineElts[N * sizeof(T)]; 1116 }; 1117 1118 /// We need the storage to be properly aligned even for small-size of 0 so that 1119 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is 1120 /// well-defined. 1121 template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {}; 1122 1123 /// Forward declaration of SmallVector so that 1124 /// calculateSmallVectorDefaultInlinedElements can reference 1125 /// `sizeof(SmallVector<T, 0>)`. 1126 template <typename T, unsigned N> class LLVM_GSL_OWNER SmallVector; 1127 1128 /// Helper class for calculating the default number of inline elements for 1129 /// `SmallVector<T>`. 1130 /// 1131 /// This should be migrated to a constexpr function when our minimum 1132 /// compiler support is enough for multi-statement constexpr functions. 1133 template <typename T> struct CalculateSmallVectorDefaultInlinedElements { 1134 // Parameter controlling the default number of inlined elements 1135 // for `SmallVector<T>`. 1136 // 1137 // The default number of inlined elements ensures that 1138 // 1. There is at least one inlined element. 1139 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless 1140 // it contradicts 1. 1141 static constexpr size_t kPreferredSmallVectorSizeof = 64; 1142 1143 // static_assert that sizeof(T) is not "too big". 1144 // 1145 // Because our policy guarantees at least one inlined element, it is possible 1146 // for an arbitrarily large inlined element to allocate an arbitrarily large 1147 // amount of inline storage. We generally consider it an antipattern for a 1148 // SmallVector to allocate an excessive amount of inline storage, so we want 1149 // to call attention to these cases and make sure that users are making an 1150 // intentional decision if they request a lot of inline storage. 1151 // 1152 // We want this assertion to trigger in pathological cases, but otherwise 1153 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat 1154 // larger than kPreferredSmallVectorSizeof (otherwise, 1155 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that 1156 // pattern seems useful in practice). 1157 // 1158 // One wrinkle is that this assertion is in theory non-portable, since 1159 // sizeof(T) is in general platform-dependent. However, we don't expect this 1160 // to be much of an issue, because most LLVM development happens on 64-bit 1161 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for 1162 // 32-bit hosts, dodging the issue. The reverse situation, where development 1163 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a 1164 // 64-bit host, is expected to be very rare. 1165 static_assert( 1166 sizeof(T) <= 256, 1167 "You are trying to use a default number of inlined elements for " 1168 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an " 1169 "explicit number of inlined elements with `SmallVector<T, N>` to make " 1170 "sure you really want that much inline storage."); 1171 1172 // Discount the size of the header itself when calculating the maximum inline 1173 // bytes. 1174 static constexpr size_t PreferredInlineBytes = 1175 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>); 1176 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T); 1177 static constexpr size_t value = 1178 NumElementsThatFit == 0 ? 1 : NumElementsThatFit; 1179 }; 1180 1181 /// This is a 'vector' (really, a variable-sized array), optimized 1182 /// for the case when the array is small. It contains some number of elements 1183 /// in-place, which allows it to avoid heap allocation when the actual number of 1184 /// elements is below that threshold. This allows normal "small" cases to be 1185 /// fast without losing generality for large inputs. 1186 /// 1187 /// \note 1188 /// In the absence of a well-motivated choice for the number of inlined 1189 /// elements \p N, it is recommended to use \c SmallVector<T> (that is, 1190 /// omitting the \p N). This will choose a default number of inlined elements 1191 /// reasonable for allocation on the stack (for example, trying to keep \c 1192 /// sizeof(SmallVector<T>) around 64 bytes). 1193 /// 1194 /// \warning This does not attempt to be exception safe. 1195 /// 1196 /// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h 1197 template <typename T, 1198 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value> 1199 class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>, 1200 SmallVectorStorage<T, N> { 1201 public: 1202 SmallVector() : SmallVectorImpl<T>(N) {} 1203 1204 ~SmallVector() { 1205 // Destroy the constructed elements in the vector. 1206 this->destroy_range(this->begin(), this->end()); 1207 } 1208 1209 explicit SmallVector(size_t Size) 1210 : SmallVectorImpl<T>(N) { 1211 this->resize(Size); 1212 } 1213 1214 SmallVector(size_t Size, const T &Value) 1215 : SmallVectorImpl<T>(N) { 1216 this->assign(Size, Value); 1217 } 1218 1219 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> 1220 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { 1221 this->append(S, E); 1222 } 1223 1224 template <typename RangeTy> 1225 explicit SmallVector(const iterator_range<RangeTy> &R) 1226 : SmallVectorImpl<T>(N) { 1227 this->append(R.begin(), R.end()); 1228 } 1229 1230 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) { 1231 this->append(IL); 1232 } 1233 1234 template <typename U, 1235 typename = std::enable_if_t<std::is_convertible<U, T>::value>> 1236 explicit SmallVector(ArrayRef<U> A) : SmallVectorImpl<T>(N) { 1237 this->append(A.begin(), A.end()); 1238 } 1239 1240 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { 1241 if (!RHS.empty()) 1242 SmallVectorImpl<T>::operator=(RHS); 1243 } 1244 1245 SmallVector &operator=(const SmallVector &RHS) { 1246 SmallVectorImpl<T>::operator=(RHS); 1247 return *this; 1248 } 1249 1250 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { 1251 if (!RHS.empty()) 1252 SmallVectorImpl<T>::operator=(::std::move(RHS)); 1253 } 1254 1255 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) { 1256 if (!RHS.empty()) 1257 SmallVectorImpl<T>::operator=(::std::move(RHS)); 1258 } 1259 1260 SmallVector &operator=(SmallVector &&RHS) { 1261 if (N) { 1262 SmallVectorImpl<T>::operator=(::std::move(RHS)); 1263 return *this; 1264 } 1265 // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the 1266 // case. 1267 if (this == &RHS) 1268 return *this; 1269 if (RHS.empty()) { 1270 this->destroy_range(this->begin(), this->end()); 1271 this->Size = 0; 1272 } else { 1273 this->assignRemote(std::move(RHS)); 1274 } 1275 return *this; 1276 } 1277 1278 SmallVector &operator=(SmallVectorImpl<T> &&RHS) { 1279 SmallVectorImpl<T>::operator=(::std::move(RHS)); 1280 return *this; 1281 } 1282 1283 SmallVector &operator=(std::initializer_list<T> IL) { 1284 this->assign(IL); 1285 return *this; 1286 } 1287 }; 1288 1289 template <typename T, unsigned N> 1290 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { 1291 return X.capacity_in_bytes(); 1292 } 1293 1294 template <typename RangeType> 1295 using ValueTypeFromRangeType = 1296 std::remove_const_t<std::remove_reference_t<decltype(*std::begin( 1297 std::declval<RangeType &>()))>>; 1298 1299 /// Given a range of type R, iterate the entire range and return a 1300 /// SmallVector with elements of the vector. This is useful, for example, 1301 /// when you want to iterate a range and then sort the results. 1302 template <unsigned Size, typename R> 1303 SmallVector<ValueTypeFromRangeType<R>, Size> to_vector(R &&Range) { 1304 return {std::begin(Range), std::end(Range)}; 1305 } 1306 template <typename R> 1307 SmallVector<ValueTypeFromRangeType<R>> to_vector(R &&Range) { 1308 return {std::begin(Range), std::end(Range)}; 1309 } 1310 1311 template <typename Out, unsigned Size, typename R> 1312 SmallVector<Out, Size> to_vector_of(R &&Range) { 1313 return {std::begin(Range), std::end(Range)}; 1314 } 1315 1316 template <typename Out, typename R> SmallVector<Out> to_vector_of(R &&Range) { 1317 return {std::begin(Range), std::end(Range)}; 1318 } 1319 1320 // Explicit instantiations 1321 extern template class llvm::SmallVectorBase<uint32_t>; 1322 #if SIZE_MAX > UINT32_MAX 1323 extern template class llvm::SmallVectorBase<uint64_t>; 1324 #endif 1325 1326 } // end namespace llvm 1327 1328 namespace std { 1329 1330 /// Implement std::swap in terms of SmallVector swap. 1331 template<typename T> 1332 inline void 1333 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { 1334 LHS.swap(RHS); 1335 } 1336 1337 /// Implement std::swap in terms of SmallVector swap. 1338 template<typename T, unsigned N> 1339 inline void 1340 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { 1341 LHS.swap(RHS); 1342 } 1343 1344 } // end namespace std 1345 1346 #endif // LLVM_ADT_SMALLVECTOR_H 1347