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