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