diff options
Diffstat (limited to 'libsupport/include/CoreLib/ADT/SmallVector.h')
| -rw-r--r-- | libsupport/include/CoreLib/ADT/SmallVector.h | 1926 |
1 files changed, 0 insertions, 1926 deletions
diff --git a/libsupport/include/CoreLib/ADT/SmallVector.h b/libsupport/include/CoreLib/ADT/SmallVector.h deleted file mode 100644 index 8b9826a..0000000 --- a/libsupport/include/CoreLib/ADT/SmallVector.h +++ /dev/null @@ -1,1926 +0,0 @@ -/* - R *CC-Project - - Copyright (C) 2026 Richard Qin - - This file is part of RCC-Project. - - RCC-Project is free software; you can redistribute it and/or modify it under - the terms of the GNU General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at your option) any - later version. - - RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY - WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A - PARTICULAR PURPOSE. See the GNU General Public License for more details. - - You should have received a copy of the GNU General Public License along with - RCC-Project; see the file COPYING. If not see - <http://www.gnu.org/licenses/>. - */ - -//===- rcc/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// This file defines the SmallVector class. -/// -//===----------------------------------------------------------------------===// - -#ifndef RCC_ADT_SMALLVECTOR_H -#define RCC_ADT_SMALLVECTOR_H - -#include "CoreLib/Compiler/Compiler.h" -#include <algorithm> -#include <cassert> -#include <cstddef> -#include <cstdint> -#include <cstdlib> -#include <cstring> -#include <functional> -#include <initializer_list> -#include <iterator> -#include <limits> -#include <memory> -#include <new> -#include <ranges> -#include <type_traits> -#include <utility> - -namespace rcc -{ - -template <typename T> class ArrayRef; - -template <typename IteratorT> class iterator_range; - -template <class Iterator, class Tag> -using HasIteratorTag = std::is_convertible< - typename std::iterator_traits<Iterator>::iterator_category, Tag>; - -template <class Iterator> -using EnableIfConvertibleToInputIterator = - std::enable_if_t<HasIteratorTag<Iterator, std::input_iterator_tag>::value>; - -/// This is all the stuff common to all SmallVectors. -/// -/// The template parameter specifies the type which should be used to hold the -/// Size and Capacity of the SmallVector, so it can be adjusted. -/// Using 32 bit size is desirable to shrink the size of the SmallVector. -/// Using 64 bit size is desirable for cases like SmallVector<char>, where a -/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for -/// buffering bitcode output - which can exceed 4GB. -template <class Size_T> class SmallVectorBase -{ -protected: - void *BeginX; - Size_T Size = 0, Capacity; - - /// The maximum value of the Size_T used. - static constexpr size_t - SizeTypeMax () - { - return std::numeric_limits<Size_T>::max (); - } - - SmallVectorBase () = delete; - SmallVectorBase (void *FirstEl, size_t TotalCapacity) - : BeginX (FirstEl), Capacity (static_cast<Size_T> (TotalCapacity)) - { - } - - /// This is a helper for \a grow() that's out of line to reduce code - /// duplication. This function will report a fatal error if it can't grow at - /// least to \p MinSize. - RCC_ABI void * - mallocForGrow (void *FirstEl, size_t MinSize, size_t TSize, - size_t &NewCapacity); - - /// This is an implementation of the grow() method which only works - /// on POD-like data types and is out of line to reduce code duplication. - /// This function will report a fatal error if it cannot increase capacity. - RCC_ABI void - grow_pod (void *FirstEl, size_t MinSize, size_t TSize); - -public: - size_t - size () const - { - return Size; - } - size_t - capacity () const - { - return Capacity; - } - - [[nodiscard]] bool - empty () const - { - return !Size; - } - -protected: - /// Set the array size to \p N, which the current array must have enough - /// capacity for. - /// - /// This does not construct or destroy any elements in the vector. - void - set_size (size_t N) - { - assert (N <= capacity ()); // implies no overflow in assignment - Size = static_cast<Size_T> (N); - } - - /// Set the array data pointer to \p Begin and capacity to \p N. - /// - /// This does not construct or destroy any elements in the vector. - // This does not clean up any existing allocation. - void - set_allocation_range (void *Begin, size_t N) - { - assert (N <= SizeTypeMax ()); - BeginX = Begin; - Capacity = static_cast<Size_T> (N); - } -}; - -template <class T> -using SmallVectorSizeType = - std::conditional_t<sizeof (T) < 4 && sizeof (void *) >= 8, uint64_t, - uint32_t>; - -/// Figure out the offset of the first element. -template <class T, typename = void> struct SmallVectorAlignmentAndSize -{ - alignas (SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof ( - SmallVectorBase<SmallVectorSizeType<T>>)]; - alignas (T) char FirstEl[sizeof (T)]; -}; - -/// This is the part of SmallVectorTemplateBase which does not depend on whether -/// the type T is a POD. The extra dummy template argument is used by ArrayRef -/// to avoid unnecessarily requiring T to be complete. -template <typename T, typename = void> -class SmallVectorTemplateCommon : public SmallVectorBase<SmallVectorSizeType<T>> -{ - using Base = SmallVectorBase<SmallVectorSizeType<T>>; - -protected: - /// Find the address of the first element. For this pointer math to be valid - /// with small-size of 0 for T with lots of alignment, it's important that - /// SmallVectorStorage is properly-aligned even for small-size of 0. - void * - getFirstEl () const - { - return const_cast<void *> (reinterpret_cast<const void *> ( - reinterpret_cast<const char *> (this) + - offsetof (SmallVectorAlignmentAndSize<T>, FirstEl))); - } - // Space after 'FirstEl' is clobbered, do not add any instance vars after it. - - SmallVectorTemplateCommon (size_t SizeArg) : Base (getFirstEl (), SizeArg) - { - } - - void - grow_pod (size_t MinSize, size_t TSize) - { - Base::grow_pod (getFirstEl (), MinSize, TSize); - } - - /// Return true if this is a smallvector which has not had dynamic - /// memory allocated for it. - bool - isSmall () const - { - return this->BeginX == getFirstEl (); - } - - /// Put this vector in a state of being small. - void - resetToSmall () - { - this->BeginX = getFirstEl (); - // The inline capacity is unknown here. SmallVector restores it when moving - // from the same concrete type; moves through SmallVectorImpl leave it at 0. - this->Size = this->Capacity = 0; - } - - /// Return true if V is an internal reference to the given range. - bool - isReferenceToRange (const void *V, const void *First, const void *Last) const - { - // Use std::less to avoid UB. - std::less<> LessThan; - return !LessThan (V, First) && LessThan (V, Last); - } - - /// Return true if V is an internal reference to this vector. - bool - isReferenceToStorage (const void *V) const - { - return isReferenceToRange (V, this->begin (), this->end ()); - } - - /// Return true if First and Last form a valid (possibly empty) range in this - /// vector's storage. - bool - isRangeInStorage (const void *First, const void *Last) const - { - // Use std::less to avoid UB. - std::less<> LessThan; - return !LessThan (First, this->begin ()) && !LessThan (Last, First) && - !LessThan (this->end (), Last); - } - - /// Return true unless Elt will be invalidated by resizing the vector to - /// NewSize. - bool - isSafeToReferenceAfterResize (const void *Elt, size_t NewSize) - { - // Past the end. - if (RCC_LIKELY (!isReferenceToStorage (Elt))) - { - return true; - } - - // Return false if Elt will be destroyed by shrinking. - if (NewSize <= this->size ()) - { - return Elt < this->begin () + NewSize; - } - - // Return false if we need to grow. - return NewSize <= this->capacity (); - } - - /// Check whether Elt will be invalidated by resizing the vector to NewSize. - void - assertSafeToReferenceAfterResize (const void *Elt, size_t NewSize) - { - assert (isSafeToReferenceAfterResize (Elt, NewSize) && - "Attempting to reference an element of the vector in an operation " - "that invalidates it"); - } - - /// Check whether Elt will be invalidated by increasing the size of the - /// vector by N. - void - assertSafeToAdd (const void *Elt, size_t N = 1) - { - this->assertSafeToReferenceAfterResize (Elt, this->size () + N); - } - - /// Check whether any part of the range will be invalidated by clearing. - template <class ItTy> - void - assertSafeToReferenceAfterClear (ItTy From, ItTy To) - { - if constexpr (std::is_pointer_v<ItTy> && - std::is_same_v< - std::remove_const_t<std::remove_pointer_t<ItTy>>, - std::remove_const_t<T>>) - { - if (From == To) - { - return; - } - this->assertSafeToReferenceAfterResize (From, 0); - this->assertSafeToReferenceAfterResize (To - 1, 0); - } - (void)From; - (void)To; - } - - /// Check whether any part of the range will be invalidated by growing. - template <class ItTy> - void - assertSafeToAddRange (ItTy From, ItTy To) - { - if constexpr (std::is_pointer_v<ItTy> && - std::is_same_v<std::remove_cv_t<std::remove_pointer_t<ItTy>>, - T>) - { - if (From == To) - { - return; - } - this->assertSafeToAdd (From, To - From); - this->assertSafeToAdd (To - 1, To - From); - } - (void)From; - (void)To; - } - - /// Reserve enough space to add one element, and return the updated element - /// pointer in case it was a reference to the storage. - template <class U> - static const T * - reserveForParamAndGetAddressImpl (U *This, const T &Elt, size_t N) - { - size_t NewSize = This->size () + N; - if (RCC_LIKELY (NewSize <= This->capacity ())) - { - return &Elt; - } - - bool ReferencesStorage = false; - int64_t Index = -1; - if (!U::TakesParamByValue) - { - if (RCC_UNLIKELY (This->isReferenceToStorage (&Elt))) - { - ReferencesStorage = true; - Index = &Elt - This->begin (); - } - } - This->grow (NewSize); - return ReferencesStorage ? This->begin () + Index : &Elt; - } - -public: - using size_type = size_t; - using difference_type = ptrdiff_t; - using value_type = T; - using iterator = T *; - using const_iterator = const T *; - - using const_reverse_iterator = std::reverse_iterator<const_iterator>; - using reverse_iterator = std::reverse_iterator<iterator>; - - using reference = T &; - using const_reference = const T &; - using pointer = T *; - using const_pointer = const T *; - - using Base::capacity; - using Base::empty; - using Base::size; - - // forward iterator creation methods. - iterator - begin () - { - return (iterator)this->BeginX; - } - const_iterator - begin () const - { - return (const_iterator)this->BeginX; - } - iterator - end () - { - return begin () + size (); - } - const_iterator - end () const - { - return begin () + size (); - } - - // reverse iterator creation methods. - reverse_iterator - rbegin () - { - return reverse_iterator (end ()); - } - const_reverse_iterator - rbegin () const - { - return const_reverse_iterator (end ()); - } - reverse_iterator - rend () - { - return reverse_iterator (begin ()); - } - const_reverse_iterator - rend () const - { - return const_reverse_iterator (begin ()); - } - - size_type - size_in_bytes () const - { - return size () * sizeof (T); - } - size_type - max_size () const - { - return std::min (this->SizeTypeMax (), size_type (-1) / sizeof (T)); - } - - size_t - capacity_in_bytes () const - { - return capacity () * sizeof (T); - } - - /// Return a pointer to the vector's buffer, even if empty(). - pointer - data () - { - return pointer (begin ()); - } - /// Return a pointer to the vector's buffer, even if empty(). - const_pointer - data () const - { - return const_pointer (begin ()); - } - - reference - operator[] (size_type idx) - { - assert (idx < size ()); - return begin ()[idx]; - } - const_reference - operator[] (size_type idx) const - { - assert (idx < size ()); - return begin ()[idx]; - } - - reference - front () - { - assert (!empty ()); - return begin ()[0]; - } - const_reference - front () const - { - assert (!empty ()); - return begin ()[0]; - } - - reference - back () - { - assert (!empty ()); - return end ()[-1]; - } - const_reference - back () const - { - assert (!empty ()); - return end ()[-1]; - } -}; - -/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put -/// method implementations that are designed to work with non-trivial T's. -/// -/// We approximate is_trivially_copyable with trivial move/copy construction and -/// trivial destruction. While the standard doesn't specify that you're allowed -/// copy these types with memcpy, there is no way for the type to observe this. -/// This catches the important case of std::pair<POD, POD>, which is not -/// trivially assignable. -template <typename T, bool = (std::is_trivially_copy_constructible<T>::value) && - (std::is_trivially_move_constructible<T>::value) && - std::is_trivially_destructible<T>::value> -class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> -{ - friend class SmallVectorTemplateCommon<T>; - -protected: - static constexpr bool TakesParamByValue = false; - using ValueParamT = const T &; - - SmallVectorTemplateBase (size_t SizeArg) - : SmallVectorTemplateCommon<T> (SizeArg) - { - } - - static void - destroy_range (T *S, T *E) - { - while (S != E) - { - --E; - E->~T (); - } - } - - /// Move the range [I, E) into the uninitialized memory starting with "Dest", - /// constructing elements as needed. - template <typename It1, typename It2> - static void - uninitialized_move (It1 I, It1 E, It2 Dest) - { - std::uninitialized_move (I, E, Dest); - } - - /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", - /// constructing elements as needed. - template <typename It1, typename It2> - static void - uninitialized_copy (It1 I, It1 E, It2 Dest) - { - std::uninitialized_copy (I, E, Dest); - } - - /// Grow the allocated memory (without initializing new elements), doubling - /// the size of the allocated memory. Guarantees space for at least one more - /// element, or MinSize more elements if specified. - void - grow (size_t MinSize = 0); - - /// Create a new allocation big enough for \p MinSize and pass back its size - /// in \p NewCapacity. This is the first section of \a grow(). - T * - mallocForGrow (size_t MinSize, size_t &NewCapacity); - - /// Move existing elements over to the new allocation \p NewElts, the middle - /// section of \a grow(). - void - moveElementsForGrow (T *NewElts); - - /// Transfer ownership of the allocation, finishing up \a grow(). - void - takeAllocationForGrow (T *NewElts, size_t NewCapacity); - - /// Reserve enough space to add one element, and return the updated element - /// pointer in case it was a reference to the storage. - const T * - reserveForParamAndGetAddress (const T &Elt, size_t N = 1) - { - return this->reserveForParamAndGetAddressImpl (this, Elt, N); - } - - /// Reserve enough space to add one element, and return the updated element - /// pointer in case it was a reference to the storage. - T * - reserveForParamAndGetAddress (T &Elt, size_t N = 1) - { - return const_cast<T *> ( - this->reserveForParamAndGetAddressImpl (this, Elt, N)); - } - - static T && - forward_value_param (T &&V) - { - return std::move (V); - } - static const T & - forward_value_param (const T &V) - { - return V; - } - - void - growAndAssign (size_t NumElts, const T &Elt) - { - // Grow manually in case Elt is an internal reference. - size_t NewCapacity; - T *NewElts = mallocForGrow (NumElts, NewCapacity); - std::uninitialized_fill_n (NewElts, NumElts, Elt); - this->destroy_range (this->begin (), this->end ()); - takeAllocationForGrow (NewElts, NewCapacity); - this->set_size (NumElts); - } - - template <typename... ArgTypes> - T & - growAndEmplaceBack (ArgTypes &&...Args) - { - // Grow manually in case one of Args is an internal reference. - size_t NewCapacity; - T *NewElts = mallocForGrow (0, NewCapacity); - ::new ((void *)(NewElts + this->size ())) - T (std::forward<ArgTypes> (Args)...); - moveElementsForGrow (NewElts); - takeAllocationForGrow (NewElts, NewCapacity); - this->set_size (this->size () + 1); - return this->back (); - } - -public: - void - push_back (const T &Elt) - { - const T *EltPtr = reserveForParamAndGetAddress (Elt); - ::new ((void *)this->end ()) T (*EltPtr); - this->set_size (this->size () + 1); - } - - void - push_back (T &&Elt) - { - T *EltPtr = reserveForParamAndGetAddress (Elt); - ::new ((void *)this->end ()) T (::std::move (*EltPtr)); - this->set_size (this->size () + 1); - } - - void - pop_back () - { - this->set_size (this->size () - 1); - this->end ()->~T (); - } -}; - -// Define this out-of-line to dissuade the C++ compiler from inlining it. -template <typename T, bool TriviallyCopyable> -void -SmallVectorTemplateBase<T, TriviallyCopyable>::grow (size_t MinSize) -{ - size_t NewCapacity; - T *NewElts = mallocForGrow (MinSize, NewCapacity); - moveElementsForGrow (NewElts); - takeAllocationForGrow (NewElts, NewCapacity); -} - -template <typename T, bool TriviallyCopyable> -T * -SmallVectorTemplateBase<T, TriviallyCopyable>::mallocForGrow ( - size_t MinSize, size_t &NewCapacity) -{ - return static_cast<T *> ( - SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow ( - this->getFirstEl (), MinSize, sizeof (T), NewCapacity)); -} - -// Define this out-of-line to dissuade the C++ compiler from inlining it. -template <typename T, bool TriviallyCopyable> -void -SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow (T *NewElts) -{ - // Move the elements over. - this->uninitialized_move (this->begin (), this->end (), NewElts); - - // Destroy the original elements. - destroy_range (this->begin (), this->end ()); -} - -// Define this out-of-line to dissuade the C++ compiler from inlining it. -template <typename T, bool TriviallyCopyable> -void -SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow ( - T *NewElts, size_t NewCapacity) -{ - // If this wasn't grown from the inline copy, deallocate the old space. - if (!this->isSmall ()) - { - free (this->begin ()); - } - - this->set_allocation_range (NewElts, NewCapacity); -} - -/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put -/// method implementations that are designed to work with trivially copyable -/// T's. This allows using memcpy in place of copy/move construction and -/// skipping destruction. -template <typename T> -class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> -{ - friend class SmallVectorTemplateCommon<T>; - -protected: - /// True if it's cheap enough to take parameters by value. Doing so avoids - /// overhead related to mitigations for reference invalidation. - static constexpr bool TakesParamByValue = sizeof (T) <= 2 * sizeof (void *); - - /// Either const T& or T, depending on whether it's cheap enough to take - /// parameters by value. - using ValueParamT = std::conditional_t<TakesParamByValue, T, const T &>; - - SmallVectorTemplateBase (size_t SizeArg) - : SmallVectorTemplateCommon<T> (SizeArg) - { - } - - // No need to do a destroy loop for POD's. - static void - destroy_range (T *, T *) - { - } - - /// Move the range [I, E) onto the uninitialized memory - /// starting with "Dest", constructing elements into it as needed. - template <typename It1, typename It2> - static void - uninitialized_move (It1 I, It1 E, It2 Dest) - { - // Just do a copy. - uninitialized_copy (I, E, Dest); - } - - /// Copy the range [I, E) onto the uninitialized memory - /// starting with "Dest", constructing elements into it as needed. - template <typename It1, typename It2> - static void - uninitialized_copy (It1 I, It1 E, It2 Dest) - { - if constexpr (std::is_pointer_v<It1> && std::is_pointer_v<It2> && - std::is_same_v< - std::remove_const_t<std::remove_pointer_t<It1>>, - std::remove_pointer_t<It2>>) - { - // Use memcpy for PODs iterated by pointers (which includes SmallVector - // iterators): std::uninitialized_copy optimizes to memmove, but we can - // use memcpy here. Note that I and E are iterators and thus might be - // invalid for memcpy if they are equal. - if (I != E) - { - std::memcpy (reinterpret_cast<void *> (Dest), I, (E - I) * sizeof (T)); - } - } - else - { - // Arbitrary iterator types; just use the basic implementation. - std::uninitialized_copy (I, E, Dest); - } - } - - /// Double the size of the allocated memory, guaranteeing space for at - /// least one more element or MinSize if specified. - void - grow (size_t MinSize = 0) - { - this->grow_pod (MinSize, sizeof (T)); - } - - /// Reserve enough space to add one element, and return the updated element - /// pointer in case it was a reference to the storage. - const T * - reserveForParamAndGetAddress (const T &Elt, size_t N = 1) - { - return this->reserveForParamAndGetAddressImpl (this, Elt, N); - } - - /// Reserve enough space to add one element, and return the updated element - /// pointer in case it was a reference to the storage. - T * - reserveForParamAndGetAddress (T &Elt, size_t N = 1) - { - return const_cast<T *> ( - this->reserveForParamAndGetAddressImpl (this, Elt, N)); - } - - /// Copy \p V or return a reference, depending on \a ValueParamT. - static ValueParamT - forward_value_param (ValueParamT V) - { - return V; - } - - void - growAndAssign (size_t NumElts, T Elt) - { - // Elt has been copied in case it's an internal reference, side-stepping - // reference invalidation problems without losing the realloc optimization. - this->set_size (0); - this->grow (NumElts); - std::uninitialized_fill_n (this->begin (), NumElts, Elt); - this->set_size (NumElts); - } - - template <typename... ArgTypes> - T & - growAndEmplaceBack (ArgTypes &&...Args) - { - // Use push_back with a copy in case Args has an internal reference, - // side-stepping reference invalidation problems without losing the realloc - // optimization. - push_back (T (std::forward<ArgTypes> (Args)...)); - return this->back (); - } - - // Out-of-line slow path so the inline push_back needs no callee-saved - // registers or stack frame on its hot path. - RCC_ATTRIBUTE_NOINLINE void - growAndPushBack (ValueParamT Elt) - { - // Copy in case Elt is an internal reference invalidated by grow. - T Tmp = Elt; - this->grow (this->size () + 1); - std::memcpy (reinterpret_cast<void *> (this->end ()), &Tmp, sizeof (T)); - this->set_size (this->size () + 1); - } - -public: - void - push_back (ValueParamT Elt) - { - if (RCC_UNLIKELY (this->size () >= this->capacity ())) - { - return growAndPushBack (Elt); - } - std::memcpy (reinterpret_cast<void *> (this->end ()), &Elt, sizeof (T)); - this->set_size (this->size () + 1); - } - - void - pop_back () - { - this->set_size (this->size () - 1); - } -}; - -/// This class consists of common code factored out of the SmallVector class to -/// reduce code duplication based on the SmallVector 'N' template parameter. -template <typename T> class SmallVectorImpl : public SmallVectorTemplateBase<T> -{ - using SuperClass = SmallVectorTemplateBase<T>; - -public: - using iterator = typename SuperClass::iterator; - using const_iterator = typename SuperClass::const_iterator; - using reference = typename SuperClass::reference; - using size_type = typename SuperClass::size_type; - -protected: - using SmallVectorTemplateBase<T>::TakesParamByValue; - using ValueParamT = typename SuperClass::ValueParamT; - - // Default ctor - Initialize to empty. - explicit SmallVectorImpl (unsigned N) : SmallVectorTemplateBase<T> (N) - { - } - - void - assignRemote (SmallVectorImpl &&RHS) - { - this->destroy_range (this->begin (), this->end ()); - if (!this->isSmall ()) - { - free (this->begin ()); - } - this->BeginX = RHS.BeginX; - this->Size = RHS.Size; - this->Capacity = RHS.Capacity; - RHS.resetToSmall (); - } - - void - moveConstructFrom (SmallVectorImpl &&RHS) - { - assert (this->empty () && "move construction requires an empty vector"); - if (!RHS.isSmall ()) - { - assignRemote (std::move (RHS)); - return; - } - - // Construct inline elements directly instead of requiring T to be move - // assignable through the general move-assignment implementation. - size_type RHSSize = RHS.size (); - reserve (RHSSize); - this->uninitialized_move (RHS.begin (), RHS.end (), this->begin ()); - this->set_size (RHSSize); - RHS.clear (); - } - - ~SmallVectorImpl () - { - // Subclass has already destructed this vector's elements. - // If this wasn't grown from the inline copy, deallocate the old space. - if (!this->isSmall ()) - { - free (this->begin ()); - } - } - -public: - SmallVectorImpl (const SmallVectorImpl &) = delete; - - void - clear () - { - this->destroy_range (this->begin (), this->end ()); - this->Size = 0; - } - -private: - // Make set_size() private to avoid misuse in subclasses. - using SuperClass::set_size; - - template <bool ForOverwrite> - void - resizeImpl (size_type N) - { - if (N == this->size ()) - { - return; - } - - if (N < this->size ()) - { - this->truncate (N); - return; - } - - this->reserve (N); - for (auto I = this->end (), E = this->begin () + N; I != E; ++I) - { - if (ForOverwrite) - { - new (&*I) T; - } - else - { - new (&*I) T (); - } - } - this->set_size (N); - } - -public: - void - resize (size_type N) - { - resizeImpl<false> (N); - } - - /// Like resize, but \ref T is POD, the new values won't be initialized. - void - resize_for_overwrite (size_type N) - { - resizeImpl<true> (N); - } - - /// Like resize, but requires that \p N is less than \a size(). - void - truncate (size_type N) - { - assert (this->size () >= N && "Cannot increase size with truncate"); - this->destroy_range (this->begin () + N, this->end ()); - this->set_size (N); - } - - void - resize (size_type N, ValueParamT NV) - { - if (N == this->size ()) - { - return; - } - - if (N < this->size ()) - { - this->truncate (N); - return; - } - - // N > this->size(). Defer to append. - this->append (N - this->size (), NV); - } - - void - reserve (size_type N) - { - if (this->capacity () < N) - { - this->grow (N); - } - } - - void - pop_back_n (size_type NumItems) - { - assert (this->size () >= NumItems); - truncate (this->size () - NumItems); - } - - [[nodiscard]] T - pop_back_val () - { - T Result = ::std::move (this->back ()); - this->pop_back (); - return Result; - } - - void - swap (SmallVectorImpl &RHS); - - /// Add the specified range to the end of the SmallVector. - template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> - void - append (ItTy in_start, ItTy in_end) - { - if constexpr (HasIteratorTag<ItTy, std::forward_iterator_tag>::value) - { - this->assertSafeToAddRange (in_start, in_end); - size_type NumInputs = std::distance (in_start, in_end); - this->reserve (this->size () + NumInputs); - this->uninitialized_copy (in_start, in_end, this->end ()); - this->set_size (this->size () + NumInputs); - } - else - { - // Input iterator, we can't know ahead how many elements we'll add. - for (; in_start != in_end; ++in_start) - { - this->emplace_back (*in_start); - } - } - } - - /// Append \p NumInputs copies of \p Elt to the end. - void - append (size_type NumInputs, ValueParamT Elt) - { - const T *EltPtr = this->reserveForParamAndGetAddress (Elt, NumInputs); - std::uninitialized_fill_n (this->end (), NumInputs, *EltPtr); - this->set_size (this->size () + NumInputs); - } - - void - append (std::initializer_list<T> IL) - { - append (IL.begin (), IL.end ()); - } - - void - append (const SmallVectorImpl &RHS) - { - append (RHS.begin (), RHS.end ()); - } - - void - assign (size_type NumElts, ValueParamT Elt) - { - // Note that Elt could be an internal reference. - if (NumElts > this->capacity ()) - { - this->growAndAssign (NumElts, Elt); - return; - } - - // Assign over existing elements. - std::fill_n (this->begin (), std::min (NumElts, this->size ()), Elt); - if (NumElts > this->size ()) - { - std::uninitialized_fill_n (this->end (), NumElts - this->size (), Elt); - } - else if (NumElts < this->size ()) - { - this->destroy_range (this->begin () + NumElts, this->end ()); - } - this->set_size (NumElts); - } - - // FIXME: Consider assigning over existing elements, rather than clearing & - // re-initializing them - for all assign(...) variants. - - template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> - void - assign (ItTy in_start, ItTy in_end) - { - this->assertSafeToReferenceAfterClear (in_start, in_end); - clear (); - append (in_start, in_end); - } - - void - assign (std::initializer_list<T> IL) - { - clear (); - append (IL); - } - - void - assign (const SmallVectorImpl &RHS) - { - assign (RHS.begin (), RHS.end ()); - } - - template <typename U, - typename = std::enable_if_t<std::is_convertible_v<U, T>>> - void - assign (ArrayRef<U> AR) - { - assign (AR.begin (), AR.end ()); - } - - iterator - erase (const_iterator CI) - { - // Just cast away constness because this is a non-const member function. - iterator I = const_cast<iterator> (CI); - - assert (this->isReferenceToStorage (CI) && - "Iterator to erase is out of bounds."); - - iterator N = I; - // Shift all elts down one. - std::move (I + 1, this->end (), I); - // Drop the last elt. - this->pop_back (); - return (N); - } - - iterator - erase (const_iterator CS, const_iterator CE) - { - // Just cast away constness because this is a non-const member function. - iterator S = const_cast<iterator> (CS); - iterator E = const_cast<iterator> (CE); - - assert (this->isRangeInStorage (S, E) && - "Range to erase is out of bounds."); - - iterator N = S; - // Shift all elts down. - iterator I = std::move (E, this->end (), S); - // Drop the last elts. - this->destroy_range (I, this->end ()); - this->set_size (I - this->begin ()); - return (N); - } - -private: - template <class ArgType> - iterator - insert_one_impl (iterator I, ArgType &&Elt) - { - // Callers ensure that ArgType is derived from T. - static_assert ( - std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, - T>::value, - "ArgType must be derived from T!"); - - if (I == this->end ()) - { // Important special case for empty vector. - this->push_back (::std::forward<ArgType> (Elt)); - return this->end () - 1; - } - - assert (this->isReferenceToStorage (I) && - "Insertion iterator is out of bounds."); - - // Grow if necessary. - size_t Index = I - this->begin (); - std::remove_reference_t<ArgType> *EltPtr = - this->reserveForParamAndGetAddress (Elt); - I = this->begin () + Index; - - ::new ((void *)this->end ()) T (::std::move (this->back ())); - // Push everything else over. - std::move_backward (I, this->end () - 1, this->end ()); - this->set_size (this->size () + 1); - - // If we just moved the element we're inserting, be sure to update - // the reference (never happens if TakesParamByValue). - static_assert (!TakesParamByValue || std::is_same<ArgType, T>::value, - "ArgType must be 'T' when taking by value!"); - if (!TakesParamByValue && - this->isReferenceToRange (EltPtr, I, this->end ())) - { - ++EltPtr; - } - - *I = ::std::forward<ArgType> (*EltPtr); - return I; - } - -public: - iterator - insert (iterator I, T &&Elt) - { - return insert_one_impl (I, this->forward_value_param (std::move (Elt))); - } - - iterator - insert (iterator I, const T &Elt) - { - return insert_one_impl (I, this->forward_value_param (Elt)); - } - - iterator - insert (iterator I, size_type NumToInsert, ValueParamT Elt) - { - // Convert iterator to elt# to avoid invalidating iterator when we reserve() - size_t InsertElt = I - this->begin (); - - if (I == this->end ()) - { // Important special case for empty vector. - append (NumToInsert, Elt); - return this->begin () + InsertElt; - } - - assert (this->isReferenceToStorage (I) && - "Insertion iterator is out of bounds."); - - // Ensure there is enough space, and get the (maybe updated) address of - // Elt. - const T *EltPtr = this->reserveForParamAndGetAddress (Elt, NumToInsert); - - // Uninvalidate the iterator. - I = this->begin () + InsertElt; - - // If there are more elements between the insertion point and the end of the - // range than there are being inserted, we can use a simple approach to - // insertion. Since we already reserved space, we know that this won't - // reallocate the vector. - if (size_t (this->end () - I) >= NumToInsert) - { - T *OldEnd = this->end (); - append (std::move_iterator<iterator> (this->end () - NumToInsert), - std::move_iterator<iterator> (this->end ())); - - // Copy the existing elements that get replaced. - std::move_backward (I, OldEnd - NumToInsert, OldEnd); - - // If we just moved the element we're inserting, be sure to update - // the reference (never happens if TakesParamByValue). - if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end ()) - { - EltPtr += NumToInsert; - } - - std::fill_n (I, NumToInsert, *EltPtr); - return I; - } - - // Otherwise, we're inserting more elements than exist already, and we're - // not inserting at the end. - - // Move over the elements that we're about to overwrite. - T *OldEnd = this->end (); - this->set_size (this->size () + NumToInsert); - size_t NumOverwritten = OldEnd - I; - this->uninitialized_move (I, OldEnd, this->end () - NumOverwritten); - - // If we just moved the element we're inserting, be sure to update - // the reference (never happens if TakesParamByValue). - if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end ()) - { - EltPtr += NumToInsert; - } - - // Replace the overwritten part. - std::fill_n (I, NumOverwritten, *EltPtr); - - // Insert the non-overwritten middle part. - std::uninitialized_fill_n (OldEnd, NumToInsert - NumOverwritten, *EltPtr); - return I; - } - - template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> - iterator - insert (iterator I, ItTy From, ItTy To) - { - // Convert iterator to elt# to avoid invalidating iterator when we reserve() - size_t InsertElt = I - this->begin (); - - if (I == this->end ()) - { // Important special case for empty vector. - append (From, To); - return this->begin () + InsertElt; - } - - if constexpr (!HasIteratorTag<ItTy, std::forward_iterator_tag>::value) - { - // For input iterators, we don't know the number of elements to insert. - size_t OldSize = this->size (); - append (From, To); - I = this->begin () + InsertElt; // Uninvalidate the iterator. - std::rotate (I, this->begin () + OldSize, this->end ()); - return I; - } - - assert (this->isReferenceToStorage (I) && - "Insertion iterator is out of bounds."); - - // Check that the reserve that follows doesn't invalidate the iterators. - this->assertSafeToAddRange (From, To); - - size_t NumToInsert = std::distance (From, To); - - // Ensure there is enough space. - reserve (this->size () + NumToInsert); - - // Uninvalidate the iterator. - I = this->begin () + InsertElt; - - // If there are more elements between the insertion point and the end of the - // range than there are being inserted, we can use a simple approach to - // insertion. Since we already reserved space, we know that this won't - // reallocate the vector. - if (size_t (this->end () - I) >= NumToInsert) - { - T *OldEnd = this->end (); - append (std::move_iterator<iterator> (this->end () - NumToInsert), - std::move_iterator<iterator> (this->end ())); - - // Copy the existing elements that get replaced. - std::move_backward (I, OldEnd - NumToInsert, OldEnd); - - std::copy (From, To, I); - return I; - } - - // Otherwise, we're inserting more elements than exist already, and we're - // not inserting at the end. - - // Move over the elements that we're about to overwrite. - T *OldEnd = this->end (); - this->set_size (this->size () + NumToInsert); - size_t NumOverwritten = OldEnd - I; - this->uninitialized_move (I, OldEnd, this->end () - NumOverwritten); - - // Replace the overwritten part. - for (T *J = I; NumOverwritten > 0; --NumOverwritten) - { - *J = *From; - ++J; - ++From; - } - - // Insert the non-overwritten middle part. - this->uninitialized_copy (From, To, OldEnd); - return I; - } - - void - insert (iterator I, std::initializer_list<T> IL) - { - insert (I, IL.begin (), IL.end ()); - } - - template <typename... ArgTypes> - reference - emplace_back (ArgTypes &&...Args) - { - if (RCC_UNLIKELY (this->size () >= this->capacity ())) - { - return this->growAndEmplaceBack (std::forward<ArgTypes> (Args)...); - } - - ::new ((void *)this->end ()) T (std::forward<ArgTypes> (Args)...); - this->set_size (this->size () + 1); - return this->back (); - } - - SmallVectorImpl & - operator= (const SmallVectorImpl &RHS); - - SmallVectorImpl & - operator= (SmallVectorImpl &&RHS); - - bool - operator== (const SmallVectorImpl &RHS) const - { - if (this->size () != RHS.size ()) - { - return false; - } - return std::equal (this->begin (), this->end (), RHS.begin ()); - } - bool - operator!= (const SmallVectorImpl &RHS) const - { - return !(*this == RHS); - } - - bool - operator< (const SmallVectorImpl &RHS) const - { - return std::lexicographical_compare (this->begin (), this->end (), - RHS.begin (), RHS.end ()); - } - bool - operator> (const SmallVectorImpl &RHS) const - { - return RHS < *this; - } - bool - operator<= (const SmallVectorImpl &RHS) const - { - return !(*this > RHS); - } - bool - operator>= (const SmallVectorImpl &RHS) const - { - return !(*this < RHS); - } -}; - -template <typename T> -void -SmallVectorImpl<T>::swap (SmallVectorImpl<T> &RHS) -{ - if (this == &RHS) - { - return; - } - - // We can only avoid copying elements if neither vector is small. - if (!this->isSmall () && !RHS.isSmall ()) - { - std::swap (this->BeginX, RHS.BeginX); - std::swap (this->Size, RHS.Size); - std::swap (this->Capacity, RHS.Capacity); - return; - } - this->reserve (RHS.size ()); - RHS.reserve (this->size ()); - - // Swap the shared elements. - size_t NumShared = this->size (); - if (NumShared > RHS.size ()) - { - NumShared = RHS.size (); - } - for (size_type i = 0; i != NumShared; ++i) - { - std::swap ((*this)[i], RHS[i]); - } - - // Copy over the extra elts. - if (this->size () > RHS.size ()) - { - size_t EltDiff = this->size () - RHS.size (); - this->uninitialized_copy (this->begin () + NumShared, this->end (), - RHS.end ()); - RHS.set_size (RHS.size () + EltDiff); - this->destroy_range (this->begin () + NumShared, this->end ()); - this->set_size (NumShared); - } - else if (RHS.size () > this->size ()) - { - size_t EltDiff = RHS.size () - this->size (); - this->uninitialized_copy (RHS.begin () + NumShared, RHS.end (), - this->end ()); - this->set_size (this->size () + EltDiff); - this->destroy_range (RHS.begin () + NumShared, RHS.end ()); - RHS.set_size (NumShared); - } -} - -template <typename T> -SmallVectorImpl<T> & -SmallVectorImpl<T>::operator= (const SmallVectorImpl<T> &RHS) -{ - // Avoid self-assignment. - if (this == &RHS) - { - return *this; - } - - // If we already have sufficient space, assign the common elements, then - // destroy any excess. - size_t RHSSize = RHS.size (); - size_t CurSize = this->size (); - if (CurSize >= RHSSize) - { - // Assign common elements. - iterator NewEnd; - if (RHSSize) - { - NewEnd = std::copy (RHS.begin (), RHS.begin () + RHSSize, this->begin ()); - } - else - { - NewEnd = this->begin (); - } - - // Destroy excess elements. - this->destroy_range (NewEnd, this->end ()); - - // Trim. - this->set_size (RHSSize); - return *this; - } - - // If we have to grow to have enough elements, destroy the current elements. - // This allows us to avoid copying them during the grow. - // FIXME: don't do this if they're efficiently moveable. - if (this->capacity () < RHSSize) - { - // Destroy current elements. - this->clear (); - CurSize = 0; - this->grow (RHSSize); - } - else if (CurSize) - { - // Otherwise, use assignment for the already-constructed elements. - std::copy (RHS.begin (), RHS.begin () + CurSize, this->begin ()); - } - - // Copy construct the new elements in place. - this->uninitialized_copy (RHS.begin () + CurSize, RHS.end (), - this->begin () + CurSize); - - // Set end. - this->set_size (RHSSize); - return *this; -} - -template <typename T> -SmallVectorImpl<T> & -SmallVectorImpl<T>::operator= (SmallVectorImpl<T> &&RHS) -{ - // Avoid self-assignment. - if (this == &RHS) - { - return *this; - } - - // If the RHS isn't small, clear this vector and then steal its buffer. - if (!RHS.isSmall ()) - { - this->assignRemote (std::move (RHS)); - return *this; - } - - // If we already have sufficient space, assign the common elements, then - // destroy any excess. - size_t RHSSize = RHS.size (); - size_t CurSize = this->size (); - if (CurSize >= RHSSize) - { - // Assign common elements. - iterator NewEnd = this->begin (); - if (RHSSize) - { - NewEnd = std::move (RHS.begin (), RHS.end (), NewEnd); - } - - // Destroy excess elements and trim the bounds. - this->destroy_range (NewEnd, this->end ()); - this->set_size (RHSSize); - - // Clear the RHS. - RHS.clear (); - - return *this; - } - - // If we have to grow to have enough elements, destroy the current elements. - // This allows us to avoid copying them during the grow. - // FIXME: this may not actually make any sense if we can efficiently move - // elements. - if (this->capacity () < RHSSize) - { - // Destroy current elements. - this->clear (); - CurSize = 0; - this->grow (RHSSize); - } - else if (CurSize) - { - // Otherwise, use assignment for the already-constructed elements. - std::move (RHS.begin (), RHS.begin () + CurSize, this->begin ()); - } - - // Move-construct the new elements in place. - this->uninitialized_move (RHS.begin () + CurSize, RHS.end (), - this->begin () + CurSize); - - // Set end. - this->set_size (RHSSize); - - RHS.clear (); - return *this; -} - -/// Storage for the SmallVector elements. This is specialized for the N=0 case -/// to avoid allocating unnecessary storage. -template <typename T, unsigned N> struct SmallVectorStorage -{ - alignas (T) char InlineElts[N * sizeof (T)]; -}; - -/// We need the storage to be properly aligned even for small-size of 0 so that -/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is -/// well-defined. -template <typename T> struct alignas (T) SmallVectorStorage<T, 0> -{ -}; - -/// Forward declaration of SmallVector so that -/// calculateSmallVectorDefaultInlinedElements can reference -/// `sizeof(SmallVector<T, 0>)`. -template <typename T, unsigned N> class RCC_GSL_OWNER SmallVector; - -/// Helper class for calculating the default number of inline elements for -/// `SmallVector<T>`. -/// -/// This should be migrated to a constexpr function when our minimum -/// compiler support is enough for multi-statement constexpr functions. -template <typename T> struct CalculateSmallVectorDefaultInlinedElements -{ - // Parameter controlling the default number of inlined elements - // for `SmallVector<T>`. - // - // The default number of inlined elements ensures that - // 1. There is at least one inlined element. - // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless - // it contradicts 1. - static constexpr size_t kPreferredSmallVectorSizeof = 64; - - // static_assert that sizeof(T) is not "too big". - // - // Because our policy guarantees at least one inlined element, it is possible - // for an arbitrarily large inlined element to allocate an arbitrarily large - // amount of inline storage. We generally consider it an antipattern for a - // SmallVector to allocate an excessive amount of inline storage, so we want - // to call attention to these cases and make sure that users are making an - // intentional decision if they request a lot of inline storage. - // - // We want this assertion to trigger in pathological cases, but otherwise - // not be too easy to hit. To accomplish that, the cutoff is actually somewhat - // larger than kPreferredSmallVectorSizeof (otherwise, - // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that - // pattern seems useful in practice). - // - // One wrinkle is that this assertion is in theory non-portable, since - // sizeof(T) is in general platform-dependent. However, we don't expect this - // to be much of an issue, because most LLVM development happens on 64-bit - // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for - // 32-bit hosts, dodging the issue. The reverse situation, where development - // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a - // 64-bit host, is expected to be very rare. - static_assert ( - sizeof (T) <= 256, - "You are trying to use a default number of inlined elements for " - "`SmallVector<T>` but `sizeof(T)` is really big! Please use an " - "explicit number of inlined elements with `SmallVector<T, N>` to make " - "sure you really want that much inline storage."); - - // Discount the size of the header itself when calculating the maximum inline - // bytes. - static constexpr size_t PreferredInlineBytes = - kPreferredSmallVectorSizeof - sizeof (SmallVector<T, 0>); - static constexpr size_t NumElementsThatFit = - PreferredInlineBytes / sizeof (T); - static constexpr size_t value = - NumElementsThatFit == 0 ? 1 : NumElementsThatFit; -}; - -/// This is a 'vector' (really, a variable-sized array), optimized -/// for the case when the array is small. It contains some number of elements -/// in-place, which allows it to avoid heap allocation when the actual number of -/// elements is below that threshold. This allows normal "small" cases to be -/// fast without losing generality for large inputs. -/// -/// \note -/// In the absence of a well-motivated choice for the number of inlined -/// elements \p N, it is recommended to use \c SmallVector<T> (that is, -/// omitting the \p N). This will choose a default number of inlined elements -/// reasonable for allocation on the stack (for example, trying to keep \c -/// sizeof(SmallVector<T>) around 64 bytes). -/// -/// \warning This does not attempt to be exception safe. -/// -/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h -template <typename T, - unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value> -class RCC_GSL_OWNER SmallVector : public SmallVectorImpl<T>, - SmallVectorStorage<T, N> -{ -public: - SmallVector () : SmallVectorImpl<T> (N) - { - } - - ~SmallVector () - { - // Destroy the constructed elements in the vector. - this->destroy_range (this->begin (), this->end ()); - } - - explicit SmallVector (size_t SizeArg) : SmallVectorImpl<T> (N) - { - this->resize (SizeArg); - } - - SmallVector (size_t SizeArg, const T &Value) : SmallVectorImpl<T> (N) - { - this->assign (SizeArg, Value); - } - - template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> - SmallVector (ItTy S, ItTy E) : SmallVectorImpl<T> (N) - { - this->append (S, E); - } - - template <typename RangeTy> - explicit SmallVector (const iterator_range<RangeTy> &R) - : SmallVectorImpl<T> (N) - { - this->append (R.begin (), R.end ()); - } - - SmallVector (std::initializer_list<T> IL) : SmallVectorImpl<T> (N) - { - this->append (IL); - } - - template <typename U, - typename = std::enable_if_t<std::is_convertible_v<U, T>>> - explicit SmallVector (ArrayRef<U> A) : SmallVectorImpl<T> (N) - { - this->append (A.begin (), A.end ()); - } - - SmallVector (const SmallVector &RHS) : SmallVectorImpl<T> (N) - { - if (!RHS.empty ()) - { - SmallVectorImpl<T>::operator= (RHS); - } - } - - SmallVector & - operator= (const SmallVector &RHS) - { - SmallVectorImpl<T>::operator= (RHS); - return *this; - } - - // Reuse the move-assignment instantiation for trivially move-assignable - // elements. Calling moveConstructFrom unconditionally would emit an - // additional per-T wrapper at -O0, increasing object size. - // std::is_move_assignable_v<T> is too broad: it can be a false positive for - // types with an unconstrained assignment operator whose body is ill-formed. - SmallVector (SmallVector &&RHS) : SmallVectorImpl<T> (N) - { - if (!RHS.empty ()) - { - bool StoleAllocation = N > 0 && !RHS.isSmall (); - if constexpr (std::is_trivially_move_assignable_v<T>) - { - SmallVectorImpl<T>::operator= (::std::move (RHS)); - } - else - { - this->moveConstructFrom (::std::move (RHS)); - } - if constexpr (N > 0) - { - if (StoleAllocation) - { - RHS.set_allocation_range (RHS.begin (), N); - } - } - } - } - - SmallVector (SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T> (N) - { - if (!RHS.empty ()) - { - if constexpr (std::is_trivially_move_assignable_v<T>) - { - SmallVectorImpl<T>::operator= (::std::move (RHS)); - } - else - { - this->moveConstructFrom (::std::move (RHS)); - } - } - } - - SmallVector & - operator= (SmallVector &&RHS) - { - if (N) - { - bool StoleAllocation = this != &RHS && !RHS.isSmall (); - SmallVectorImpl<T>::operator= (::std::move (RHS)); - // Restore the inline capacity after stealing RHS's allocation. - if (StoleAllocation) - { - RHS.set_allocation_range (RHS.begin (), N); - } - return *this; - } - // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the - // case. - if (this == &RHS) - { - return *this; - } - if (RHS.empty ()) - { - this->destroy_range (this->begin (), this->end ()); - this->Size = 0; - } - else - { - this->assignRemote (std::move (RHS)); - } - return *this; - } - - SmallVector & - operator= (SmallVectorImpl<T> &&RHS) - { - SmallVectorImpl<T>::operator= (::std::move (RHS)); - return *this; - } - - SmallVector & - operator= (std::initializer_list<T> IL) - { - this->assign (IL); - return *this; - } -}; - -template <typename T, unsigned N> -inline size_t -capacity_in_bytes (const SmallVector<T, N> &X) -{ - return X.capacity_in_bytes (); -} - -template <typename RangeType> -using ValueTypeFromRangeType = std::ranges::range_value_t<RangeType>; - -/// Given a range of type R, iterate the entire range and return a -/// SmallVector with elements of the vector. This is useful, for example, -/// when you want to iterate a range and then sort the results. -template <unsigned Size, typename R> -SmallVector<ValueTypeFromRangeType<R>, Size> -to_vector (R &&Range) -{ - return SmallVector<ValueTypeFromRangeType<R>, Size> ( - std::ranges::begin (Range), std::ranges::end (Range)); -} -template <typename R> -SmallVector<ValueTypeFromRangeType<R>> -to_vector (R &&Range) -{ - return SmallVector<ValueTypeFromRangeType<R>> (std::ranges::begin (Range), - std::ranges::end (Range)); -} - -template <typename Out, unsigned Size, typename R> -SmallVector<Out, Size> -to_vector_of (R &&Range) -{ - return SmallVector<Out, Size> (std::ranges::begin (Range), - std::ranges::end (Range)); -} - -template <typename Out, typename R> -SmallVector<Out> -to_vector_of (R &&Range) -{ - return SmallVector<Out> (std::ranges::begin (Range), - std::ranges::end (Range)); -} - -// Explicit instantiations -extern template class rcc::SmallVectorBase<uint32_t>; -#if SIZE_MAX > UINT32_MAX -extern template class rcc::SmallVectorBase<uint64_t>; -#endif - -} // end namespace rcc - -namespace std -{ - -template <typename T, unsigned N> struct hash<rcc::SmallVector<T, N>> -{ - size_t - operator() (const rcc::SmallVector<T, N> &Value) const - { - size_t Seed = 0; - for (const T &Element : Value) - { - size_t ElementHash = std::hash<T>{}(Element); - Seed ^= ElementHash + static_cast<size_t> (0x9e3779b9U) + (Seed << 6) + - (Seed >> 2); - } - return Seed; - } -}; - -/// Implement std::swap in terms of SmallVector swap. -template <typename T> -inline void -swap (rcc::SmallVectorImpl<T> &LHS, rcc::SmallVectorImpl<T> &RHS) -{ - LHS.swap (RHS); -} - -/// Implement std::swap in terms of SmallVector swap. -template <typename T, unsigned N> -inline void -swap (rcc::SmallVector<T, N> &LHS, rcc::SmallVector<T, N> &RHS) -{ - LHS.swap (RHS); -} - -} // end namespace std - -#endif // RCC_ADT_SMALLVECTOR_H |