-
-
Save njames93/f26f159f06bda9e7ed2270adb39d9b08 to your computer and use it in GitHub Desktop.
Experimenting with outline methods
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
diff --git a/llvm/include/llvm/ADT/SmallVector.h b/llvm/include/llvm/ADT/SmallVector.h | |
index c3c6a366dab..40d21b7d1d3 100644 | |
--- a/llvm/include/llvm/ADT/SmallVector.h | |
+++ b/llvm/include/llvm/ADT/SmallVector.h | |
@@ -1,995 +1,1284 @@ | |
//===- llvm/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 | |
// | |
//===----------------------------------------------------------------------===// | |
// | |
// This file defines the SmallVector class. | |
// | |
//===----------------------------------------------------------------------===// | |
#ifndef LLVM_ADT_SMALLVECTOR_H | |
#define LLVM_ADT_SMALLVECTOR_H | |
#include "llvm/ADT/iterator_range.h" | |
#include "llvm/Support/AlignOf.h" | |
#include "llvm/Support/Compiler.h" | |
#include "llvm/Support/ErrorHandling.h" | |
#include "llvm/Support/MathExtras.h" | |
#include "llvm/Support/MemAlloc.h" | |
#include "llvm/Support/type_traits.h" | |
#include <algorithm> | |
#include <cassert> | |
#include <cstddef> | |
#include <cstdlib> | |
#include <cstring> | |
#include <initializer_list> | |
#include <iterator> | |
#include <limits> | |
#include <memory> | |
#include <new> | |
#include <type_traits> | |
#include <utility> | |
namespace llvm { | |
/// 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(TotalCapacity) {} | |
/// 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. | |
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize); | |
+ size_t grow_size(size_t MinSize = 0) { | |
+ // Ensure we can fit the new capacity. | |
+ // This is only going to be applicable when the capacity is 32 bit. | |
+ if (MinSize > this->SizeTypeMax()) | |
+ report_size_overflow(MinSize); | |
+ | |
+ // Ensure we can meet the guarantee of space for at least one more element. | |
+ // The above check alone will not catch the case where grow is called with a | |
+ // default MinSize of 0, but the current capacity cannot be increased. | |
+ // This is only going to be applicable when the capacity is 32 bit. | |
+ if (capacity() == SizeTypeMax()) | |
+ report_at_maximum_capacity(); | |
+ // Always grow, even from zero. | |
+ size_t NewCapacity = size_t(NextPowerOf2(capacity() + 2)); | |
+ return std::min(std::max(NewCapacity, MinSize), SizeTypeMax()); | |
+ } | |
+ | |
/// Report that MinSize doesn't fit into this vector's size type. Throws | |
/// std::length_error or calls report_fatal_error. | |
LLVM_ATTRIBUTE_NORETURN static void report_size_overflow(size_t MinSize); | |
/// Report that this vector is already at maximum capacity. Throws | |
/// std::length_error or calls report_fatal_error. | |
LLVM_ATTRIBUTE_NORETURN static void report_at_maximum_capacity(); | |
public: | |
size_t size() const { return Size; } | |
size_t capacity() const { return Capacity; } | |
LLVM_NODISCARD bool empty() const { return !Size; } | |
/// 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. | |
/// | |
/// Clients can use this in conjunction with capacity() to write past the end | |
/// of the buffer when they know that more elements are available, and only | |
/// update the size later. This avoids the cost of value initializing elements | |
/// which will only be overwritten. | |
void set_size(size_t N) { | |
assert(N <= capacity()); | |
Size = N; | |
} | |
}; | |
template <class T> | |
using SmallVectorSizeType = | |
typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t, | |
uint32_t>::type; | |
/// Figure out the offset of the first element. | |
template <class T, typename = void> struct SmallVectorAlignmentAndSize { | |
AlignedCharArrayUnion<SmallVectorBase<SmallVectorSizeType<T>>> Base; | |
AlignedCharArrayUnion<T> FirstEl; | |
}; | |
+namespace detail { | |
+template <typename Size_T> class GrowBufferBase; | |
+} // namespace detail | |
+ | |
/// 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>>; | |
+ friend class detail::GrowBufferBase<SmallVectorSizeType<T>>; | |
/// 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. | |
protected: | |
SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {} | |
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(); | |
this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. | |
} | |
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]; | |
} | |
}; | |
+namespace detail { | |
+template <typename T> | |
+static constexpr bool | |
+ is_pod_like_v = (is_trivially_copy_constructible<T>::value) && | |
+ (is_trivially_move_constructible<T>::value) && | |
+ std::is_trivially_destructible<T>::value; | |
+ | |
+template <typename Size_T> class GrowBufferBase { | |
+public: | |
+ GrowBufferBase(Size_T Size, Size_T Capacity, Size_T TSize) | |
+ : Size(Size), Capacity(Capacity) { | |
+ BeginX = llvm::safe_malloc(Capacity * TSize); | |
+ } | |
+ | |
+ ~GrowBufferBase() { | |
+ assert(BeginX == nullptr && "Buffers haven't been swapped out"); | |
+ } | |
+ | |
+ Size_T size() const { return Size; } | |
+ Size_T capacity() const { return Capacity; } | |
+ | |
+protected: | |
+ void *BeginX; | |
+ Size_T Size, Capacity; | |
+ | |
+ void increaseSize(Size_T NumItems = 1) { Size += NumItems; } | |
+ void setSize(Size_T NewSize) { Size = NewSize; } | |
+ | |
+ template <typename T> void take_buffers(SmallVectorTemplateCommon<T> &Vec) { | |
+ if (!Vec.isSmall()) | |
+ free(Vec.begin()); | |
+ Vec.BeginX = BeginX; | |
+ Vec.Size = Size; | |
+ Vec.Capacity = Capacity; | |
+ BeginX = nullptr; | |
+ Size = 0U; | |
+ Capacity = 0U; | |
+ } | |
+}; | |
+ | |
+template <typename T, bool = is_pod_like_v<T>> | |
+class GrowBuffer : public GrowBufferBase<SmallVectorSizeType<T>> { | |
+public: | |
+ using Size_T = SmallVectorSizeType<T>; | |
+ using Base = GrowBufferBase<Size_T>; | |
+ | |
+ using Base::capacity; | |
+ using Base::increaseSize; | |
+ using Base::size; | |
+ | |
+ GrowBuffer(Size_T Size, Size_T Capacity) : Base(Size, Capacity, sizeof(T)) {} | |
+ | |
+ T *begin() { return static_cast<T *>(this->BeginX); } | |
+ T *end() { return begin() + size(); } | |
+ | |
+ void default_construct_at_end(Size_T Count) { | |
+ assert((size() + Count) <= capacity() && "Overflowed GrowBuffer storage"); | |
+ T *First = end(); | |
+ increaseSize(Count); | |
+ T *Last = end(); | |
+ for (; First != Last; ++First) { | |
+ ::new (static_cast<void *>(First)) T; | |
+ } | |
+ } | |
+ | |
+ void push(const T &Elt) { | |
+ assert(size() < capacity() && "Overflowed GrowBuffer storage"); | |
+ ::new (static_cast<void *>(end())) T(Elt); | |
+ increaseSize(); | |
+ } | |
+ | |
+ void push(T &&Elt) { | |
+ assert(size() < capacity() && "Overflowed GrowBuffer storage"); | |
+ ::new (static_cast<void *>(end())) T(std::move(Elt)); | |
+ increaseSize(); | |
+ } | |
+ | |
+ template <typename... ArgTypes> void emplace(ArgTypes &&...Args) { | |
+ assert(size() < capacity() && "Overflowed GrowBuffer storage"); | |
+ ::new (static_cast<void *>(end())) T(std::forward<ArgTypes>(Args)...); | |
+ increaseSize(); | |
+ } | |
+ | |
+ void append(Size_T Count, const T &Elt) { | |
+ assert((size() + Count) <= capacity() && "Overflowed GrowBuffer storage"); | |
+ std::uninitialized_fill_n(end(), Count, Elt); | |
+ increaseSize(Count); | |
+ } | |
+ | |
+ template <typename in_iter, | |
+ typename = std::enable_if_t<std::is_convertible< | |
+ typename std::iterator_traits<in_iter>::iterator_category, | |
+ std::input_iterator_tag>::value>> | |
+ void append(in_iter Start, in_iter End) { | |
+ assert(size() + std::distance(Start, End) <= capacity() && | |
+ "Overflowed GrowBuffer storage"); | |
+ T *NewEnd = std::uninitialized_copy(Start, End, end()); | |
+ this->setSize(NewEnd - begin()); | |
+ } | |
+ | |
+ void swap_out_buffer(SmallVectorTemplateCommon<T> &Vec); | |
+ | |
+ void swap_out_split_buffer(SmallVectorTemplateCommon<T> &Vec, | |
+ Size_T SplitIndex); | |
+}; | |
+template <typename T> | |
+class GrowBuffer<T, true> : public GrowBufferBase<SmallVectorSizeType<T>> { | |
+public: | |
+ using Size_T = SmallVectorSizeType<T>; | |
+ using Base = GrowBufferBase<Size_T>; | |
+ | |
+ using Base::capacity; | |
+ using Base::increaseSize; | |
+ using Base::size; | |
+ | |
+ GrowBuffer(Size_T Size, Size_T Capacity) : Base(Size, Capacity, sizeof(T)) {} | |
+ | |
+ T *begin() { return static_cast<T *>(this->BeginX); } | |
+ T *end() { return begin() + size(); } | |
+ | |
+ void default_construct_at_end(Size_T Count) { | |
+ assert((size() + Count) <= capacity() && "Overflowed GrowBuffer storage"); | |
+ // No need to do any construction here. | |
+ increaseSize(Count); | |
+ } | |
+ | |
+ void push(const T &Elt) { | |
+ assert(size() < capacity() && "Overflowed GrowBuffer storage"); | |
+ memcpy(end(), &Elt, sizeof(Elt)); | |
+ increaseSize(); | |
+ } | |
+ | |
+ template <typename... ArgTypes> void emplace(ArgTypes &&...Args) { | |
+ assert(size() < capacity() && "Overflowed GrowBuffer storage"); | |
+ ::new ((void *)end()) T(std::forward<ArgTypes>(Args)...); | |
+ increaseSize(); | |
+ } | |
+ | |
+ template <typename in_iter, | |
+ typename = std::enable_if_t<std::is_convertible< | |
+ typename std::iterator_traits<in_iter>::iterator_category, | |
+ std::input_iterator_tag>::value>> | |
+ void append(in_iter Start, in_iter End) { | |
+ assert(size() + std::distance(Start, End) <= capacity() && | |
+ "Overflowed GrowBuffer storage"); | |
+ T *NewEnd = std::uninitialized_copy(Start, End, end()); | |
+ this->setSize(NewEnd - begin()); | |
+ } | |
+ | |
+ void append(T *Start, T *End) { | |
+ Size_T NumItems = End - Start; | |
+ assert(size() + NumItems <= capacity() && "Overflowed GrowBuffer storage"); | |
+ memcpy(end(), Start, NumItems * sizeof(T)); | |
+ increaseSize(NumItems); | |
+ } | |
+ | |
+ void append(Size_T Count, const T &Elt) { | |
+ assert((size() + Count) <= capacity() && "Overflowed GrowBuffer storage"); | |
+ T *First = end(); | |
+ increaseSize(Count); | |
+ T *Last = end(); | |
+ for (; First != Last; ++First) { | |
+ memcpy(First, &Elt, sizeof(Elt)); | |
+ } | |
+ } | |
+ | |
+ void swap_out_buffer(SmallVectorTemplateCommon<T> &Vec); | |
+ | |
+ void swap_out_split_buffer(SmallVectorTemplateCommon<T> &Vec, | |
+ Size_T SplitIndex); | |
+}; | |
+ | |
+template <typename T, bool TriviallyCopyable> | |
+void GrowBuffer<T, TriviallyCopyable>::swap_out_buffer( | |
+ SmallVectorTemplateCommon<T> &Vec) { | |
+ std::uninitialized_copy(std::make_move_iterator(Vec.rbegin()), | |
+ std::make_move_iterator(Vec.rend()), | |
+ std::reverse_iterator<T *>(begin() + Vec.size())); | |
+ // Destory the items in the old vector. | |
+ for (T &Item : Vec) | |
+ Item.~T(); | |
+ this->take_buffers(Vec); | |
+} | |
+ | |
+template <typename T, bool TriviallyCopyable> | |
+void GrowBuffer<T, TriviallyCopyable>::swap_out_split_buffer( | |
+ SmallVectorTemplateCommon<T> &Vec, Size_T SplitIndex) { | |
+ std::uninitialized_copy(std::make_move_iterator(std::reverse_iterator<T *>( | |
+ Vec.begin() + SplitIndex)), | |
+ std::make_move_iterator(Vec.rend()), | |
+ std::reverse_iterator<T *>(begin() + SplitIndex)); | |
+ std::uninitialized_copy(std::make_move_iterator(&Vec[SplitIndex]), | |
+ std::make_move_iterator(Vec.end()), end()); | |
+ increaseSize(Vec.size() - SplitIndex); | |
+ // Destory the items in the old vector. | |
+ for (T &Item : Vec) | |
+ Item.~T(); | |
+ this->take_buffers(Vec); | |
+} | |
+ | |
+template <typename T> | |
+void GrowBuffer<T, true>::swap_out_buffer(SmallVectorTemplateCommon<T> &Vec) { | |
+ memcpy(begin(), Vec.begin(), Vec.size_in_bytes()); | |
+ this->take_buffers(Vec); | |
+} | |
+ | |
+template <typename T> | |
+void GrowBuffer<T, true>::swap_out_split_buffer( | |
+ SmallVectorTemplateCommon<T> &Vec, Size_T SplitIndex) { | |
+ memcpy(begin(), Vec.begin(), SplitIndex * sizeof(T)); | |
+ memcpy(end(), &Vec[SplitIndex], (Vec.size() - SplitIndex) * sizeof(T)); | |
+ increaseSize(Vec.size() - SplitIndex); | |
+ this->take_buffers(Vec); | |
+} | |
+ | |
+} // namespace detail | |
+ | |
/// 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 = (is_trivially_copy_constructible<T>::value) && | |
- (is_trivially_move_constructible<T>::value) && | |
- std::is_trivially_destructible<T>::value> | |
+template <typename T, bool = detail::is_pod_like_v<T>> | |
class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { | |
protected: | |
SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} | |
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_copy(std::make_move_iterator(I), | |
std::make_move_iterator(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); | |
public: | |
void push_back(const T &Elt) { | |
- if (LLVM_UNLIKELY(this->size() >= this->capacity())) | |
- this->grow(); | |
+ if (LLVM_UNLIKELY(this->size() >= this->capacity())) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), this->grow_size()); | |
+ Buffer.push(Elt); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
::new ((void*) this->end()) T(Elt); | |
this->set_size(this->size() + 1); | |
} | |
void push_back(T &&Elt) { | |
- if (LLVM_UNLIKELY(this->size() >= this->capacity())) | |
- this->grow(); | |
+ if (LLVM_UNLIKELY(this->size() >= this->capacity())) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), this->grow_size()); | |
+ Buffer.push(std::move(Elt)); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
::new ((void*) this->end()) T(::std::move(Elt)); | |
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) { | |
- // Ensure we can fit the new capacity. | |
- // This is only going to be applicable when the capacity is 32 bit. | |
- if (MinSize > this->SizeTypeMax()) | |
- this->report_size_overflow(MinSize); | |
- | |
- // Ensure we can meet the guarantee of space for at least one more element. | |
- // The above check alone will not catch the case where grow is called with a | |
- // default MinSize of 0, but the current capacity cannot be increased. | |
- // This is only going to be applicable when the capacity is 32 bit. | |
- if (this->capacity() == this->SizeTypeMax()) | |
- this->report_at_maximum_capacity(); | |
- | |
- // Always grow, even from zero. | |
- size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2)); | |
- NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax()); | |
+ size_t NewCapacity = this->grow_size(MinSize); | |
T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T))); | |
// Move the elements over. | |
this->uninitialized_move(this->begin(), this->end(), NewElts); | |
// Destroy the original elements. | |
destroy_range(this->begin(), this->end()); | |
// If this wasn't grown from the inline copy, deallocate the old space. | |
if (!this->isSmall()) | |
free(this->begin()); | |
this->BeginX = NewElts; | |
this->Capacity = 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> { | |
protected: | |
SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} | |
// 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) { | |
// Arbitrary iterator types; just use the basic implementation. | |
std::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 T1, typename T2> | |
static void uninitialized_copy( | |
T1 *I, T1 *E, T2 *Dest, | |
std::enable_if_t<std::is_same<typename std::remove_const<T1>::type, | |
T2>::value> * = nullptr) { | |
// 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) | |
memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T)); | |
} | |
/// 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)); } | |
public: | |
void push_back(const T &Elt) { | |
- if (LLVM_UNLIKELY(this->size() >= this->capacity())) | |
- this->grow(); | |
+ if (LLVM_UNLIKELY(this->size() >= this->capacity())) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), this->grow_size()); | |
+ Buffer.push(Elt); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
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: | |
// Default ctor - Initialize to empty. | |
explicit SmallVectorImpl(unsigned N) | |
: SmallVectorTemplateBase<T>(N) {} | |
public: | |
SmallVectorImpl(const SmallVectorImpl &) = delete; | |
~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()); | |
} | |
void clear() { | |
this->destroy_range(this->begin(), this->end()); | |
this->Size = 0; | |
} | |
void resize(size_type N) { | |
if (N < this->size()) { | |
this->destroy_range(this->begin()+N, this->end()); | |
this->set_size(N); | |
} else if (N > this->size()) { | |
if (this->capacity() < N) | |
this->grow(N); | |
for (auto I = this->end(), E = this->begin() + N; I != E; ++I) | |
new (&*I) T(); | |
this->set_size(N); | |
} | |
} | |
void resize(size_type N, const T &NV) { | |
if (N < this->size()) { | |
this->destroy_range(this->begin()+N, this->end()); | |
this->set_size(N); | |
} else if (N > this->size()) { | |
- if (this->capacity() < N) | |
- this->grow(N); | |
+ if (this->capacity() < N) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), this->grow_size(N)); | |
+ Buffer.append(N - this->size(), NV); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
std::uninitialized_fill(this->end(), this->begin()+N, NV); | |
this->set_size(N); | |
} | |
} | |
void reserve(size_type N) { | |
if (this->capacity() < N) | |
this->grow(N); | |
} | |
LLVM_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 in_iter, | |
typename = std::enable_if_t<std::is_convertible< | |
typename std::iterator_traits<in_iter>::iterator_category, | |
std::input_iterator_tag>::value>> | |
void append(in_iter in_start, in_iter in_end) { | |
size_type NumInputs = std::distance(in_start, in_end); | |
- if (NumInputs > this->capacity() - this->size()) | |
- this->grow(this->size()+NumInputs); | |
+ if (NumInputs > this->capacity() - this->size()) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), | |
+ this->grow_size(this->size() + NumInputs)); | |
+ Buffer.append(in_start, in_end); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
this->uninitialized_copy(in_start, in_end, this->end()); | |
this->set_size(this->size() + NumInputs); | |
} | |
/// Append \p NumInputs copies of \p Elt to the end. | |
void append(size_type NumInputs, const T &Elt) { | |
- if (NumInputs > this->capacity() - this->size()) | |
- this->grow(this->size()+NumInputs); | |
+ if (NumInputs > this->capacity() - this->size()) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), | |
+ this->grow_size(this->size() + NumInputs)); | |
+ Buffer.append(NumInputs, Elt); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
std::uninitialized_fill_n(this->end(), NumInputs, Elt); | |
this->set_size(this->size() + NumInputs); | |
} | |
void append(std::initializer_list<T> IL) { | |
append(IL.begin(), IL.end()); | |
} | |
// FIXME: Consider assigning over existing elements, rather than clearing & | |
// re-initializing them - for all assign(...) variants. | |
void assign(size_type NumElts, const T &Elt) { | |
- clear(); | |
- if (this->capacity() < NumElts) | |
- this->grow(NumElts); | |
- this->set_size(NumElts); | |
- std::uninitialized_fill(this->begin(), this->end(), Elt); | |
+ if (this->capacity() < NumElts) { | |
+ detail::GrowBuffer<T> Buffer(0, this->grow_size(NumElts)); | |
+ Buffer.append(NumElts, Elt); | |
+ this->clear(); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
+ if (NumElts == this->size()) { | |
+ std::fill(this->begin(), this->end(), Elt); | |
+ } else if (NumElts < this->size()) { | |
+ this->destroy_range(this->begin() + NumElts, this->end()); | |
+ this->set_size(NumElts); | |
+ std::fill(this->begin(), this->end(), Elt); | |
+ } else { | |
+ std::fill(this->begin(), this->end(), Elt); | |
+ std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt); | |
+ this->set_size(NumElts); | |
+ } | |
} | |
template <typename in_iter, | |
typename = std::enable_if_t<std::is_convertible< | |
typename std::iterator_traits<in_iter>::iterator_category, | |
std::input_iterator_tag>::value>> | |
void assign(in_iter in_start, in_iter in_end) { | |
- clear(); | |
- append(in_start, in_end); | |
+ size_type NumElts = std::distance(in_start, in_end); | |
+ if (this->capacity() < NumElts) { | |
+ detail::GrowBuffer<T> Buffer(0, this->grow_size(NumElts)); | |
+ Buffer.append(in_start, in_end); | |
+ this->clear(); | |
+ Buffer.swap_out_buffer(*this); | |
+ return; | |
+ } | |
+ if (NumElts == this->size()) { | |
+ std::copy(in_start, in_end, this->begin()); | |
+ } else if (NumElts < this->size()) { | |
+ this->destroy_range(this->begin() + NumElts, this->end()); | |
+ this->set_size(NumElts); | |
+ std::copy(in_start, in_end, this->begin()); | |
+ } else { | |
+ for (auto &I : *this) | |
+ I = *in_start++; | |
+ this->uninitialized_copy(in_start, in_end, this->end()); | |
+ this->set_size(NumElts); | |
+ } | |
} | |
- void assign(std::initializer_list<T> IL) { | |
- clear(); | |
- append(IL); | |
- } | |
+ void assign(std::initializer_list<T> IL) { assign(IL.begin(), IL.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(I >= this->begin() && "Iterator to erase is out of bounds."); | |
assert(I < this->end() && "Erasing at past-the-end iterator."); | |
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(S >= this->begin() && "Range to erase is out of bounds."); | |
assert(S <= E && "Trying to erase invalid range."); | |
assert(E <= this->end() && "Trying to erase past the end."); | |
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); | |
} | |
iterator insert(iterator I, T &&Elt) { | |
if (I == this->end()) { // Important special case for empty vector. | |
this->push_back(::std::move(Elt)); | |
return this->end()-1; | |
} | |
assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
assert(I <= this->end() && "Inserting past the end of the vector."); | |
if (this->size() >= this->capacity()) { | |
size_t EltNo = I-this->begin(); | |
- this->grow(); | |
- I = this->begin()+EltNo; | |
+ detail::GrowBuffer<T> Buffer(EltNo, this->grow_size()); | |
+ Buffer.push(std::move(Elt)); | |
+ Buffer.swap_out_split_buffer(*this, EltNo); | |
+ return this->begin() + EltNo; | |
} | |
::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. | |
T *EltPtr = &Elt; | |
if (I <= EltPtr && EltPtr < this->end()) | |
++EltPtr; | |
*I = ::std::move(*EltPtr); | |
return I; | |
} | |
iterator insert(iterator I, const T &Elt) { | |
if (I == this->end()) { // Important special case for empty vector. | |
this->push_back(Elt); | |
return this->end()-1; | |
} | |
assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
assert(I <= this->end() && "Inserting past the end of the vector."); | |
if (this->size() >= this->capacity()) { | |
size_t EltNo = I-this->begin(); | |
- this->grow(); | |
- I = this->begin()+EltNo; | |
+ detail::GrowBuffer<T> Buffer(EltNo, this->grow_size()); | |
+ Buffer.push(Elt); | |
+ Buffer.swap_out_split_buffer(*this, EltNo); | |
+ return this->begin() + EltNo; | |
} | |
::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. | |
const T *EltPtr = &Elt; | |
if (I <= EltPtr && EltPtr < this->end()) | |
++EltPtr; | |
*I = *EltPtr; | |
return I; | |
} | |
iterator insert(iterator I, size_type NumToInsert, const T &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(I >= this->begin() && "Insertion iterator is out of bounds."); | |
assert(I <= this->end() && "Inserting past the end of the vector."); | |
- // Ensure there is enough space. | |
- reserve(this->size() + NumToInsert); | |
- | |
- // Uninvalidate the iterator. | |
- I = this->begin()+InsertElt; | |
+ if ((this->size() + NumToInsert) > this->capacity()) { | |
+ detail::GrowBuffer<T> Buffer(InsertElt, | |
+ this->grow_size(this->size() + NumToInsert)); | |
+ Buffer.append(NumToInsert, Elt); | |
+ Buffer.swap_out_split_buffer(*this, InsertElt); | |
+ return 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::fill_n(I, NumToInsert, Elt); | |
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. | |
std::fill_n(I, NumOverwritten, Elt); | |
// Insert the non-overwritten middle part. | |
std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); | |
return I; | |
} | |
template <typename ItTy, | |
typename = std::enable_if_t<std::is_convertible< | |
typename std::iterator_traits<ItTy>::iterator_category, | |
std::input_iterator_tag>::value>> | |
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; | |
} | |
assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
assert(I <= this->end() && "Inserting past the end of the vector."); | |
size_t NumToInsert = std::distance(From, To); | |
- // Ensure there is enough space. | |
- reserve(this->size() + NumToInsert); | |
- | |
- // Uninvalidate the iterator. | |
- I = this->begin()+InsertElt; | |
+ if ((this->size() + NumToInsert) > this->capacity()) { | |
+ detail::GrowBuffer<T> Buffer(InsertElt, | |
+ this->grow_size(this->size() + NumToInsert)); | |
+ Buffer.append(From, To); | |
+ Buffer.swap_out_split_buffer(*this, InsertElt); | |
+ return 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 (LLVM_UNLIKELY(this->size() >= this->capacity())) | |
- this->grow(); | |
- ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); | |
- this->set_size(this->size() + 1); | |
+ if (LLVM_UNLIKELY(this->size() >= this->capacity())) { | |
+ detail::GrowBuffer<T> Buffer(this->size(), this->grow_size()); | |
+ Buffer.emplace(std::forward<ArgTypes>(Args)...); | |
+ Buffer.swap_out_buffer(*this); | |
+ } else { | |
+ ::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()); | |
} | |
}; | |
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; | |
} | |
if (RHS.size() > this->capacity()) | |
this->grow(RHS.size()); | |
if (this->size() > RHS.capacity()) | |
RHS.grow(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->destroy_range(this->begin(), this->end()); | |
this->set_size(0); | |
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->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(); | |
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->destroy_range(this->begin(), this->end()); | |
this->set_size(0); | |
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 { | |
AlignedCharArrayUnion<T> InlineElts[N]; | |
}; | |
/// 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(alignof(T)) SmallVectorStorage<T, 0> {}; | |
/// 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 that this does not attempt to be exception safe. | |
/// | |
template <typename T, unsigned N> | |
class LLVM_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 Size, const T &Value = T()) | |
: SmallVectorImpl<T>(N) { | |
this->assign(Size, Value); | |
} | |
template <typename ItTy, | |
typename = std::enable_if_t<std::is_convertible< | |
typename std::iterator_traits<ItTy>::iterator_category, | |
std::input_iterator_tag>::value>> | |
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->assign(IL); | |
} | |
SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { | |
if (!RHS.empty()) | |
SmallVectorImpl<T>::operator=(RHS); | |
} | |
const SmallVector &operator=(const SmallVector &RHS) { | |
SmallVectorImpl<T>::operator=(RHS); | |
return *this; | |
} | |
SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { | |
if (!RHS.empty()) | |
SmallVectorImpl<T>::operator=(::std::move(RHS)); | |
} | |
SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) { | |
if (!RHS.empty()) | |
SmallVectorImpl<T>::operator=(::std::move(RHS)); | |
} | |
const SmallVector &operator=(SmallVector &&RHS) { | |
SmallVectorImpl<T>::operator=(::std::move(RHS)); | |
return *this; | |
} | |
const SmallVector &operator=(SmallVectorImpl<T> &&RHS) { | |
SmallVectorImpl<T>::operator=(::std::move(RHS)); | |
return *this; | |
} | |
const 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(); | |
} | |
/// 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<typename std::remove_const<typename std::remove_reference< | |
decltype(*std::begin(std::declval<R &>()))>::type>::type, | |
Size> | |
to_vector(R &&Range) { | |
return {std::begin(Range), std::end(Range)}; | |
} | |
} // end namespace llvm | |
namespace std { | |
/// Implement std::swap in terms of SmallVector swap. | |
template<typename T> | |
inline void | |
swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { | |
LHS.swap(RHS); | |
} | |
/// Implement std::swap in terms of SmallVector swap. | |
template<typename T, unsigned N> | |
inline void | |
swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { | |
LHS.swap(RHS); | |
} | |
} // end namespace std | |
#endif // LLVM_ADT_SMALLVECTOR_H | |
diff --git a/llvm/unittests/ADT/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp | |
index dbe404869e2..a69a6a501ff 100644 | |
--- a/llvm/unittests/ADT/SmallVectorTest.cpp | |
+++ b/llvm/unittests/ADT/SmallVectorTest.cpp | |
@@ -1,1003 +1,1038 @@ | |
//===- llvm/unittest/ADT/SmallVectorTest.cpp ------------------------------===// | |
// | |
// 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 | |
// | |
//===----------------------------------------------------------------------===// | |
// | |
// SmallVector unit tests. | |
// | |
//===----------------------------------------------------------------------===// | |
#include "llvm/ADT/SmallVector.h" | |
#include "llvm/ADT/ArrayRef.h" | |
#include "llvm/Support/Compiler.h" | |
#include "gtest/gtest.h" | |
#include <list> | |
#include <stdarg.h> | |
using namespace llvm; | |
namespace { | |
/// A helper class that counts the total number of constructor and | |
/// destructor calls. | |
class Constructable { | |
private: | |
static int numConstructorCalls; | |
static int numMoveConstructorCalls; | |
static int numCopyConstructorCalls; | |
static int numDestructorCalls; | |
static int numAssignmentCalls; | |
static int numMoveAssignmentCalls; | |
static int numCopyAssignmentCalls; | |
+ enum class ObjectState { Destroyed = 0, Constructed, MovedFrom }; | |
- bool constructed; | |
+ ObjectState State; | |
int value; | |
public: | |
- Constructable() : constructed(true), value(0) { | |
+ Constructable() : State(ObjectState::Constructed), value(0) { | |
++numConstructorCalls; | |
} | |
- Constructable(int val) : constructed(true), value(val) { | |
+ Constructable(int val) : State(ObjectState::Constructed), value(val) { | |
++numConstructorCalls; | |
} | |
- Constructable(const Constructable & src) : constructed(true) { | |
+ Constructable(const Constructable &src) : State(src.State) { | |
+ EXPECT_EQ(State, ObjectState::Constructed); | |
value = src.value; | |
++numConstructorCalls; | |
++numCopyConstructorCalls; | |
} | |
- Constructable(Constructable && src) : constructed(true) { | |
+ Constructable(Constructable &&src) : State(src.State) { | |
+ EXPECT_EQ(State, ObjectState::Constructed); | |
value = src.value; | |
+ src.State = ObjectState::MovedFrom; | |
++numConstructorCalls; | |
++numMoveConstructorCalls; | |
} | |
~Constructable() { | |
- EXPECT_TRUE(constructed); | |
+ EXPECT_NE(State, ObjectState::Destroyed); | |
++numDestructorCalls; | |
- constructed = false; | |
+ State = ObjectState::Destroyed; | |
} | |
Constructable & operator=(const Constructable & src) { | |
- EXPECT_TRUE(constructed); | |
+ EXPECT_NE(State, ObjectState::Destroyed); | |
+ EXPECT_EQ(src.State, ObjectState::Constructed); | |
+ State = src.State; | |
value = src.value; | |
++numAssignmentCalls; | |
++numCopyAssignmentCalls; | |
return *this; | |
} | |
Constructable & operator=(Constructable && src) { | |
- EXPECT_TRUE(constructed); | |
+ EXPECT_NE(State, ObjectState::Destroyed); | |
+ EXPECT_EQ(src.State, ObjectState::Constructed); | |
+ State = src.State; | |
value = src.value; | |
+ src.State = ObjectState::MovedFrom; | |
++numAssignmentCalls; | |
++numMoveAssignmentCalls; | |
return *this; | |
} | |
int getValue() const { | |
+ EXPECT_EQ(State, ObjectState::Constructed); | |
return abs(value); | |
} | |
static void reset() { | |
numConstructorCalls = 0; | |
numMoveConstructorCalls = 0; | |
numCopyConstructorCalls = 0; | |
numDestructorCalls = 0; | |
numAssignmentCalls = 0; | |
numMoveAssignmentCalls = 0; | |
numCopyAssignmentCalls = 0; | |
} | |
static int getNumConstructorCalls() { | |
return numConstructorCalls; | |
} | |
static int getNumMoveConstructorCalls() { | |
return numMoveConstructorCalls; | |
} | |
static int getNumCopyConstructorCalls() { | |
return numCopyConstructorCalls; | |
} | |
static int getNumDestructorCalls() { | |
return numDestructorCalls; | |
} | |
static int getNumAssignmentCalls() { | |
return numAssignmentCalls; | |
} | |
static int getNumMoveAssignmentCalls() { | |
return numMoveAssignmentCalls; | |
} | |
static int getNumCopyAssignmentCalls() { | |
return numCopyAssignmentCalls; | |
} | |
friend bool operator==(const Constructable & c0, const Constructable & c1) { | |
return c0.getValue() == c1.getValue(); | |
} | |
friend bool LLVM_ATTRIBUTE_UNUSED | |
operator!=(const Constructable & c0, const Constructable & c1) { | |
return c0.getValue() != c1.getValue(); | |
} | |
}; | |
int Constructable::numConstructorCalls; | |
int Constructable::numCopyConstructorCalls; | |
int Constructable::numMoveConstructorCalls; | |
int Constructable::numDestructorCalls; | |
int Constructable::numAssignmentCalls; | |
int Constructable::numCopyAssignmentCalls; | |
int Constructable::numMoveAssignmentCalls; | |
struct NonCopyable { | |
NonCopyable() {} | |
NonCopyable(NonCopyable &&) {} | |
NonCopyable &operator=(NonCopyable &&) { return *this; } | |
private: | |
NonCopyable(const NonCopyable &) = delete; | |
NonCopyable &operator=(const NonCopyable &) = delete; | |
}; | |
LLVM_ATTRIBUTE_USED void CompileTest() { | |
SmallVector<NonCopyable, 0> V; | |
V.resize(42); | |
} | |
class SmallVectorTestBase : public testing::Test { | |
protected: | |
void SetUp() override { Constructable::reset(); } | |
template <typename VectorT> | |
void assertEmpty(VectorT & v) { | |
// Size tests | |
EXPECT_EQ(0u, v.size()); | |
EXPECT_TRUE(v.empty()); | |
// Iterator tests | |
EXPECT_TRUE(v.begin() == v.end()); | |
} | |
// Assert that v contains the specified values, in order. | |
template <typename VectorT> | |
void assertValuesInOrder(VectorT & v, size_t size, ...) { | |
EXPECT_EQ(size, v.size()); | |
va_list ap; | |
va_start(ap, size); | |
for (size_t i = 0; i < size; ++i) { | |
int value = va_arg(ap, int); | |
EXPECT_EQ(value, v[i].getValue()); | |
} | |
va_end(ap); | |
} | |
// Generate a sequence of values to initialize the vector. | |
template <typename VectorT> | |
void makeSequence(VectorT & v, int start, int end) { | |
for (int i = start; i <= end; ++i) { | |
v.push_back(Constructable(i)); | |
} | |
} | |
}; | |
// Test fixture class | |
template <typename VectorT> | |
class SmallVectorTest : public SmallVectorTestBase { | |
protected: | |
VectorT theVector; | |
VectorT otherVector; | |
}; | |
typedef ::testing::Types<SmallVector<Constructable, 0>, | |
SmallVector<Constructable, 1>, | |
SmallVector<Constructable, 2>, | |
SmallVector<Constructable, 4>, | |
SmallVector<Constructable, 5> | |
> SmallVectorTestTypes; | |
TYPED_TEST_CASE(SmallVectorTest, SmallVectorTestTypes); | |
// Constructor test. | |
TYPED_TEST(SmallVectorTest, ConstructorNonIterTest) { | |
SCOPED_TRACE("ConstructorTest"); | |
this->theVector = SmallVector<Constructable, 2>(2, 2); | |
this->assertValuesInOrder(this->theVector, 2u, 2, 2); | |
} | |
// Constructor test. | |
TYPED_TEST(SmallVectorTest, ConstructorIterTest) { | |
SCOPED_TRACE("ConstructorTest"); | |
int arr[] = {1, 2, 3}; | |
this->theVector = | |
SmallVector<Constructable, 4>(std::begin(arr), std::end(arr)); | |
this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); | |
} | |
// New vector test. | |
TYPED_TEST(SmallVectorTest, EmptyVectorTest) { | |
SCOPED_TRACE("EmptyVectorTest"); | |
this->assertEmpty(this->theVector); | |
EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend()); | |
EXPECT_EQ(0, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(0, Constructable::getNumDestructorCalls()); | |
} | |
// Simple insertions and deletions. | |
TYPED_TEST(SmallVectorTest, PushPopTest) { | |
SCOPED_TRACE("PushPopTest"); | |
// Track whether the vector will potentially have to grow. | |
bool RequiresGrowth = this->theVector.capacity() < 3; | |
// Push an element | |
this->theVector.push_back(Constructable(1)); | |
// Size tests | |
this->assertValuesInOrder(this->theVector, 1u, 1); | |
EXPECT_FALSE(this->theVector.begin() == this->theVector.end()); | |
EXPECT_FALSE(this->theVector.empty()); | |
// Push another element | |
this->theVector.push_back(Constructable(2)); | |
this->assertValuesInOrder(this->theVector, 2u, 1, 2); | |
// Insert at beginning | |
this->theVector.insert(this->theVector.begin(), this->theVector[1]); | |
this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2); | |
// Pop one element | |
this->theVector.pop_back(); | |
this->assertValuesInOrder(this->theVector, 2u, 2, 1); | |
// Pop remaining elements | |
this->theVector.pop_back(); | |
this->theVector.pop_back(); | |
this->assertEmpty(this->theVector); | |
// Check number of constructor calls. Should be 2 for each list element, | |
// one for the argument to push_back, one for the argument to insert, | |
// and one for the list element itself. | |
if (!RequiresGrowth) { | |
EXPECT_EQ(5, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(5, Constructable::getNumDestructorCalls()); | |
} else { | |
// If we had to grow the vector, these only have a lower bound, but should | |
// always be equal. | |
EXPECT_LE(5, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(Constructable::getNumConstructorCalls(), | |
Constructable::getNumDestructorCalls()); | |
} | |
} | |
// Clear test. | |
TYPED_TEST(SmallVectorTest, ClearTest) { | |
SCOPED_TRACE("ClearTest"); | |
this->theVector.reserve(2); | |
this->makeSequence(this->theVector, 1, 2); | |
this->theVector.clear(); | |
this->assertEmpty(this->theVector); | |
EXPECT_EQ(4, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(4, Constructable::getNumDestructorCalls()); | |
} | |
// Resize smaller test. | |
TYPED_TEST(SmallVectorTest, ResizeShrinkTest) { | |
SCOPED_TRACE("ResizeShrinkTest"); | |
this->theVector.reserve(3); | |
this->makeSequence(this->theVector, 1, 3); | |
this->theVector.resize(1); | |
this->assertValuesInOrder(this->theVector, 1u, 1); | |
EXPECT_EQ(6, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(5, Constructable::getNumDestructorCalls()); | |
} | |
// Resize bigger test. | |
TYPED_TEST(SmallVectorTest, ResizeGrowTest) { | |
SCOPED_TRACE("ResizeGrowTest"); | |
this->theVector.resize(2); | |
EXPECT_EQ(2, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(0, Constructable::getNumDestructorCalls()); | |
EXPECT_EQ(2u, this->theVector.size()); | |
} | |
TYPED_TEST(SmallVectorTest, ResizeWithElementsTest) { | |
this->theVector.resize(2); | |
Constructable::reset(); | |
this->theVector.resize(4); | |
size_t Ctors = Constructable::getNumConstructorCalls(); | |
EXPECT_TRUE(Ctors == 2 || Ctors == 4); | |
size_t MoveCtors = Constructable::getNumMoveConstructorCalls(); | |
EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2); | |
size_t Dtors = Constructable::getNumDestructorCalls(); | |
EXPECT_TRUE(Dtors == 0 || Dtors == 2); | |
} | |
// Resize with fill value. | |
TYPED_TEST(SmallVectorTest, ResizeFillTest) { | |
SCOPED_TRACE("ResizeFillTest"); | |
this->theVector.resize(3, Constructable(77)); | |
this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77); | |
} | |
// Overflow past fixed size. | |
TYPED_TEST(SmallVectorTest, OverflowTest) { | |
SCOPED_TRACE("OverflowTest"); | |
// Push more elements than the fixed size. | |
this->makeSequence(this->theVector, 1, 10); | |
// Test size and values. | |
EXPECT_EQ(10u, this->theVector.size()); | |
for (int i = 0; i < 10; ++i) { | |
EXPECT_EQ(i+1, this->theVector[i].getValue()); | |
} | |
// Now resize back to fixed size. | |
this->theVector.resize(1); | |
this->assertValuesInOrder(this->theVector, 1u, 1); | |
} | |
// Iteration tests. | |
TYPED_TEST(SmallVectorTest, IterationTest) { | |
this->makeSequence(this->theVector, 1, 2); | |
// Forward Iteration | |
typename TypeParam::iterator it = this->theVector.begin(); | |
EXPECT_TRUE(*it == this->theVector.front()); | |
EXPECT_TRUE(*it == this->theVector[0]); | |
EXPECT_EQ(1, it->getValue()); | |
++it; | |
EXPECT_TRUE(*it == this->theVector[1]); | |
EXPECT_TRUE(*it == this->theVector.back()); | |
EXPECT_EQ(2, it->getValue()); | |
++it; | |
EXPECT_TRUE(it == this->theVector.end()); | |
--it; | |
EXPECT_TRUE(*it == this->theVector[1]); | |
EXPECT_EQ(2, it->getValue()); | |
--it; | |
EXPECT_TRUE(*it == this->theVector[0]); | |
EXPECT_EQ(1, it->getValue()); | |
// Reverse Iteration | |
typename TypeParam::reverse_iterator rit = this->theVector.rbegin(); | |
EXPECT_TRUE(*rit == this->theVector[1]); | |
EXPECT_EQ(2, rit->getValue()); | |
++rit; | |
EXPECT_TRUE(*rit == this->theVector[0]); | |
EXPECT_EQ(1, rit->getValue()); | |
++rit; | |
EXPECT_TRUE(rit == this->theVector.rend()); | |
--rit; | |
EXPECT_TRUE(*rit == this->theVector[0]); | |
EXPECT_EQ(1, rit->getValue()); | |
--rit; | |
EXPECT_TRUE(*rit == this->theVector[1]); | |
EXPECT_EQ(2, rit->getValue()); | |
} | |
// Swap test. | |
TYPED_TEST(SmallVectorTest, SwapTest) { | |
SCOPED_TRACE("SwapTest"); | |
this->makeSequence(this->theVector, 1, 2); | |
std::swap(this->theVector, this->otherVector); | |
this->assertEmpty(this->theVector); | |
this->assertValuesInOrder(this->otherVector, 2u, 1, 2); | |
} | |
// Append test | |
TYPED_TEST(SmallVectorTest, AppendTest) { | |
SCOPED_TRACE("AppendTest"); | |
this->makeSequence(this->otherVector, 2, 3); | |
this->theVector.push_back(Constructable(1)); | |
this->theVector.append(this->otherVector.begin(), this->otherVector.end()); | |
this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); | |
} | |
// Append repeated test | |
TYPED_TEST(SmallVectorTest, AppendRepeatedTest) { | |
SCOPED_TRACE("AppendRepeatedTest"); | |
this->theVector.push_back(Constructable(1)); | |
this->theVector.append(2, Constructable(77)); | |
this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77); | |
} | |
// Append test | |
TYPED_TEST(SmallVectorTest, AppendNonIterTest) { | |
SCOPED_TRACE("AppendRepeatedTest"); | |
this->theVector.push_back(Constructable(1)); | |
this->theVector.append(2, 7); | |
this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7); | |
} | |
struct output_iterator { | |
typedef std::output_iterator_tag iterator_category; | |
typedef int value_type; | |
typedef int difference_type; | |
typedef value_type *pointer; | |
typedef value_type &reference; | |
operator int() { return 2; } | |
operator Constructable() { return 7; } | |
}; | |
TYPED_TEST(SmallVectorTest, AppendRepeatedNonForwardIterator) { | |
SCOPED_TRACE("AppendRepeatedTest"); | |
this->theVector.push_back(Constructable(1)); | |
this->theVector.append(output_iterator(), output_iterator()); | |
this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7); | |
} | |
// Assign test | |
TYPED_TEST(SmallVectorTest, AssignTest) { | |
SCOPED_TRACE("AssignTest"); | |
this->theVector.push_back(Constructable(1)); | |
+ Constructable::reset(); | |
this->theVector.assign(2, Constructable(77)); | |
this->assertValuesInOrder(this->theVector, 2u, 77, 77); | |
+ EXPECT_EQ(Constructable::getNumCopyAssignmentCalls() + | |
+ Constructable::getNumCopyConstructorCalls(), | |
+ 2); | |
} | |
// Assign test | |
TYPED_TEST(SmallVectorTest, AssignRangeTest) { | |
SCOPED_TRACE("AssignTest"); | |
this->theVector.push_back(Constructable(1)); | |
int arr[] = {1, 2, 3}; | |
this->theVector.assign(std::begin(arr), std::end(arr)); | |
this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); | |
} | |
// Assign test | |
TYPED_TEST(SmallVectorTest, AssignNonIterTest) { | |
SCOPED_TRACE("AssignTest"); | |
this->theVector.push_back(Constructable(1)); | |
+ Constructable::reset(); | |
this->theVector.assign(2, 7); | |
this->assertValuesInOrder(this->theVector, 2u, 7, 7); | |
+ EXPECT_EQ(Constructable::getNumCopyAssignmentCalls() + | |
+ Constructable::getNumCopyConstructorCalls(), | |
+ 2); | |
} | |
// Move-assign test | |
TYPED_TEST(SmallVectorTest, MoveAssignTest) { | |
SCOPED_TRACE("MoveAssignTest"); | |
// Set up our vector with a single element, but enough capacity for 4. | |
this->theVector.reserve(4); | |
this->theVector.push_back(Constructable(1)); | |
// Set up the other vector with 2 elements. | |
this->otherVector.push_back(Constructable(2)); | |
this->otherVector.push_back(Constructable(3)); | |
// Move-assign from the other vector. | |
this->theVector = std::move(this->otherVector); | |
// Make sure we have the right result. | |
this->assertValuesInOrder(this->theVector, 2u, 2, 3); | |
// Make sure the # of constructor/destructor calls line up. There | |
// are two live objects after clearing the other vector. | |
this->otherVector.clear(); | |
EXPECT_EQ(Constructable::getNumConstructorCalls()-2, | |
Constructable::getNumDestructorCalls()); | |
// There shouldn't be any live objects any more. | |
this->theVector.clear(); | |
EXPECT_EQ(Constructable::getNumConstructorCalls(), | |
Constructable::getNumDestructorCalls()); | |
} | |
// Erase a single element | |
TYPED_TEST(SmallVectorTest, EraseTest) { | |
SCOPED_TRACE("EraseTest"); | |
this->makeSequence(this->theVector, 1, 3); | |
const auto &theConstVector = this->theVector; | |
this->theVector.erase(theConstVector.begin()); | |
this->assertValuesInOrder(this->theVector, 2u, 2, 3); | |
} | |
// Erase a range of elements | |
TYPED_TEST(SmallVectorTest, EraseRangeTest) { | |
SCOPED_TRACE("EraseRangeTest"); | |
this->makeSequence(this->theVector, 1, 3); | |
const auto &theConstVector = this->theVector; | |
this->theVector.erase(theConstVector.begin(), theConstVector.begin() + 2); | |
this->assertValuesInOrder(this->theVector, 1u, 3); | |
} | |
// Insert a single element. | |
TYPED_TEST(SmallVectorTest, InsertTest) { | |
SCOPED_TRACE("InsertTest"); | |
this->makeSequence(this->theVector, 1, 3); | |
typename TypeParam::iterator I = | |
this->theVector.insert(this->theVector.begin() + 1, Constructable(77)); | |
EXPECT_EQ(this->theVector.begin() + 1, I); | |
this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3); | |
} | |
// Insert a copy of a single element. | |
TYPED_TEST(SmallVectorTest, InsertCopy) { | |
SCOPED_TRACE("InsertTest"); | |
this->makeSequence(this->theVector, 1, 3); | |
Constructable C(77); | |
typename TypeParam::iterator I = | |
this->theVector.insert(this->theVector.begin() + 1, C); | |
EXPECT_EQ(this->theVector.begin() + 1, I); | |
this->assertValuesInOrder(this->theVector, 4u, 1, 77, 2, 3); | |
} | |
// Insert repeated elements. | |
TYPED_TEST(SmallVectorTest, InsertRepeatedTest) { | |
SCOPED_TRACE("InsertRepeatedTest"); | |
this->makeSequence(this->theVector, 1, 4); | |
Constructable::reset(); | |
+ bool RequiresGrowth = this->theVector.capacity() < 6; | |
auto I = | |
this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16)); | |
- // Move construct the top element into newly allocated space, and optionally | |
- // reallocate the whole buffer, move constructing into it. | |
- // FIXME: This is inefficient, we shouldn't move things into newly allocated | |
- // space, then move them up/around, there should only be 2 or 4 move | |
- // constructions here. | |
- EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || | |
- Constructable::getNumMoveConstructorCalls() == 6); | |
- // Move assign the next two to shift them up and make a gap. | |
- EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); | |
- // Copy construct the two new elements from the parameter. | |
- EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); | |
- // All without any copy construction. | |
- EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); | |
+ | |
+ if (RequiresGrowth) { | |
+ // Moving [1] and [2,3,4] into the new storage. | |
+ EXPECT_EQ(4, Constructable::getNumMoveConstructorCalls()); | |
+ // Copy construct the new elements directly into the new storage. | |
+ EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); | |
+ // Nothing is move or copy assigned in the growth case. | |
+ EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); | |
+ EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); | |
+ } else { | |
+ // Shifting [3,4] down 2 blocks into uninitialized storage. | |
+ EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls()); | |
+ // Shifting [2] into where [4] lived. | |
+ EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); | |
+ // Copy assign the two new elements inside the buffer. | |
+ EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); | |
+ EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); | |
+ } | |
+ | |
EXPECT_EQ(this->theVector.begin() + 1, I); | |
this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4); | |
} | |
TYPED_TEST(SmallVectorTest, InsertRepeatedNonIterTest) { | |
SCOPED_TRACE("InsertRepeatedTest"); | |
this->makeSequence(this->theVector, 1, 4); | |
Constructable::reset(); | |
auto I = this->theVector.insert(this->theVector.begin() + 1, 2, 7); | |
EXPECT_EQ(this->theVector.begin() + 1, I); | |
this->assertValuesInOrder(this->theVector, 6u, 1, 7, 7, 2, 3, 4); | |
} | |
TYPED_TEST(SmallVectorTest, InsertRepeatedAtEndTest) { | |
SCOPED_TRACE("InsertRepeatedTest"); | |
this->makeSequence(this->theVector, 1, 4); | |
Constructable::reset(); | |
auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16)); | |
// Just copy construct them into newly allocated space | |
EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); | |
// Move everything across if reallocation is needed. | |
EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || | |
Constructable::getNumMoveConstructorCalls() == 4); | |
// Without ever moving or copying anything else. | |
EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); | |
EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); | |
EXPECT_EQ(this->theVector.begin() + 4, I); | |
this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 4, 16, 16); | |
} | |
TYPED_TEST(SmallVectorTest, InsertRepeatedEmptyTest) { | |
SCOPED_TRACE("InsertRepeatedTest"); | |
this->makeSequence(this->theVector, 10, 15); | |
// Empty insert. | |
EXPECT_EQ(this->theVector.end(), | |
this->theVector.insert(this->theVector.end(), | |
0, Constructable(42))); | |
EXPECT_EQ(this->theVector.begin() + 1, | |
this->theVector.insert(this->theVector.begin() + 1, | |
0, Constructable(42))); | |
} | |
// Insert range. | |
TYPED_TEST(SmallVectorTest, InsertRangeTest) { | |
SCOPED_TRACE("InsertRangeTest"); | |
Constructable Arr[3] = | |
{ Constructable(77), Constructable(77), Constructable(77) }; | |
this->makeSequence(this->theVector, 1, 3); | |
Constructable::reset(); | |
+ bool RequiresGrowth = this->theVector.capacity() < 6; | |
auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3); | |
- // Move construct the top 3 elements into newly allocated space. | |
- // Possibly move the whole sequence into new space first. | |
- // FIXME: This is inefficient, we shouldn't move things into newly allocated | |
- // space, then move them up/around, there should only be 2 or 3 move | |
- // constructions here. | |
- EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || | |
- Constructable::getNumMoveConstructorCalls() == 5); | |
- // Copy assign the lower 2 new elements into existing space. | |
- EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); | |
- // Copy construct the third element into newly allocated space. | |
- EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); | |
+ | |
+ if (RequiresGrowth) { | |
+ // Moving [1] and [2,3] into the new storage. | |
+ EXPECT_EQ(3, Constructable::getNumMoveConstructorCalls()); | |
+ // Copy construct the 3 items from Arr into the new storage. | |
+ EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); | |
+ // Nothing is move or copy assigned in the growth case. | |
+ EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); | |
+ EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); | |
+ } else { | |
+ // Shifting [2,3] down 3 blocks into uninitialized storage. | |
+ EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls()); | |
+ // Copy assign the lower 2 new elements into existing storage. | |
+ EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); | |
+ // Copy construct the third element into uninitialized storage. | |
+ EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); | |
+ // Nothing needs to be move assigned here as the only items that need | |
+ // shifting, are shifted into uninitialized storage. | |
+ EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); | |
+ } | |
EXPECT_EQ(this->theVector.begin() + 1, I); | |
this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3); | |
} | |
TYPED_TEST(SmallVectorTest, InsertRangeAtEndTest) { | |
SCOPED_TRACE("InsertRangeTest"); | |
Constructable Arr[3] = | |
{ Constructable(77), Constructable(77), Constructable(77) }; | |
this->makeSequence(this->theVector, 1, 3); | |
// Insert at end. | |
Constructable::reset(); | |
auto I = this->theVector.insert(this->theVector.end(), Arr, Arr+3); | |
// Copy construct the 3 elements into new space at the top. | |
EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); | |
// Don't copy/move anything else. | |
EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); | |
// Reallocation might occur, causing all elements to be moved into the new | |
// buffer. | |
EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || | |
Constructable::getNumMoveConstructorCalls() == 3); | |
EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); | |
EXPECT_EQ(this->theVector.begin() + 3, I); | |
this->assertValuesInOrder(this->theVector, 6u, | |
1, 2, 3, 77, 77, 77); | |
} | |
TYPED_TEST(SmallVectorTest, InsertEmptyRangeTest) { | |
SCOPED_TRACE("InsertRangeTest"); | |
this->makeSequence(this->theVector, 1, 3); | |
// Empty insert. | |
EXPECT_EQ(this->theVector.end(), | |
this->theVector.insert(this->theVector.end(), | |
this->theVector.begin(), | |
this->theVector.begin())); | |
EXPECT_EQ(this->theVector.begin() + 1, | |
this->theVector.insert(this->theVector.begin() + 1, | |
this->theVector.begin(), | |
this->theVector.begin())); | |
} | |
// Comparison tests. | |
TYPED_TEST(SmallVectorTest, ComparisonTest) { | |
SCOPED_TRACE("ComparisonTest"); | |
this->makeSequence(this->theVector, 1, 3); | |
this->makeSequence(this->otherVector, 1, 3); | |
EXPECT_TRUE(this->theVector == this->otherVector); | |
EXPECT_FALSE(this->theVector != this->otherVector); | |
this->otherVector.clear(); | |
this->makeSequence(this->otherVector, 2, 4); | |
EXPECT_FALSE(this->theVector == this->otherVector); | |
EXPECT_TRUE(this->theVector != this->otherVector); | |
} | |
// Constant vector tests. | |
TYPED_TEST(SmallVectorTest, ConstVectorTest) { | |
const TypeParam constVector; | |
EXPECT_EQ(0u, constVector.size()); | |
EXPECT_TRUE(constVector.empty()); | |
EXPECT_TRUE(constVector.begin() == constVector.end()); | |
} | |
// Direct array access. | |
TYPED_TEST(SmallVectorTest, DirectVectorTest) { | |
EXPECT_EQ(0u, this->theVector.size()); | |
this->theVector.reserve(4); | |
EXPECT_LE(4u, this->theVector.capacity()); | |
EXPECT_EQ(0, Constructable::getNumConstructorCalls()); | |
this->theVector.push_back(1); | |
this->theVector.push_back(2); | |
this->theVector.push_back(3); | |
this->theVector.push_back(4); | |
EXPECT_EQ(4u, this->theVector.size()); | |
EXPECT_EQ(8, Constructable::getNumConstructorCalls()); | |
EXPECT_EQ(1, this->theVector[0].getValue()); | |
EXPECT_EQ(2, this->theVector[1].getValue()); | |
EXPECT_EQ(3, this->theVector[2].getValue()); | |
EXPECT_EQ(4, this->theVector[3].getValue()); | |
} | |
TYPED_TEST(SmallVectorTest, IteratorTest) { | |
std::list<int> L; | |
this->theVector.insert(this->theVector.end(), L.begin(), L.end()); | |
} | |
template <typename InvalidType> class DualSmallVectorsTest; | |
template <typename VectorT1, typename VectorT2> | |
class DualSmallVectorsTest<std::pair<VectorT1, VectorT2>> : public SmallVectorTestBase { | |
protected: | |
VectorT1 theVector; | |
VectorT2 otherVector; | |
template <typename T, unsigned N> | |
static unsigned NumBuiltinElts(const SmallVector<T, N>&) { return N; } | |
}; | |
typedef ::testing::Types< | |
// Small mode -> Small mode. | |
std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 4>>, | |
// Small mode -> Big mode. | |
std::pair<SmallVector<Constructable, 4>, SmallVector<Constructable, 2>>, | |
// Big mode -> Small mode. | |
std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 4>>, | |
// Big mode -> Big mode. | |
std::pair<SmallVector<Constructable, 2>, SmallVector<Constructable, 2>> | |
> DualSmallVectorTestTypes; | |
TYPED_TEST_CASE(DualSmallVectorsTest, DualSmallVectorTestTypes); | |
TYPED_TEST(DualSmallVectorsTest, MoveAssignment) { | |
SCOPED_TRACE("MoveAssignTest-DualVectorTypes"); | |
// Set up our vector with four elements. | |
for (unsigned I = 0; I < 4; ++I) | |
this->otherVector.push_back(Constructable(I)); | |
const Constructable *OrigDataPtr = this->otherVector.data(); | |
// Move-assign from the other vector. | |
this->theVector = | |
std::move(static_cast<SmallVectorImpl<Constructable>&>(this->otherVector)); | |
// Make sure we have the right result. | |
this->assertValuesInOrder(this->theVector, 4u, 0, 1, 2, 3); | |
// Make sure the # of constructor/destructor calls line up. There | |
// are two live objects after clearing the other vector. | |
this->otherVector.clear(); | |
EXPECT_EQ(Constructable::getNumConstructorCalls()-4, | |
Constructable::getNumDestructorCalls()); | |
// If the source vector (otherVector) was in small-mode, assert that we just | |
// moved the data pointer over. | |
EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 || | |
this->theVector.data() == OrigDataPtr); | |
// There shouldn't be any live objects any more. | |
this->theVector.clear(); | |
EXPECT_EQ(Constructable::getNumConstructorCalls(), | |
Constructable::getNumDestructorCalls()); | |
// We shouldn't have copied anything in this whole process. | |
EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0); | |
} | |
struct notassignable { | |
int &x; | |
notassignable(int &x) : x(x) {} | |
}; | |
TEST(SmallVectorCustomTest, NoAssignTest) { | |
int x = 0; | |
SmallVector<notassignable, 2> vec; | |
vec.push_back(notassignable(x)); | |
x = 42; | |
EXPECT_EQ(42, vec.pop_back_val().x); | |
} | |
struct MovedFrom { | |
bool hasValue; | |
MovedFrom() : hasValue(true) { | |
} | |
MovedFrom(MovedFrom&& m) : hasValue(m.hasValue) { | |
m.hasValue = false; | |
} | |
MovedFrom &operator=(MovedFrom&& m) { | |
hasValue = m.hasValue; | |
m.hasValue = false; | |
return *this; | |
} | |
}; | |
TEST(SmallVectorTest, MidInsert) { | |
SmallVector<MovedFrom, 3> v; | |
v.push_back(MovedFrom()); | |
v.insert(v.begin(), MovedFrom()); | |
for (MovedFrom &m : v) | |
EXPECT_TRUE(m.hasValue); | |
} | |
enum EmplaceableArgState { | |
EAS_Defaulted, | |
EAS_Arg, | |
EAS_LValue, | |
EAS_RValue, | |
EAS_Failure | |
}; | |
template <int I> struct EmplaceableArg { | |
EmplaceableArgState State; | |
EmplaceableArg() : State(EAS_Defaulted) {} | |
EmplaceableArg(EmplaceableArg &&X) | |
: State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {} | |
EmplaceableArg(EmplaceableArg &X) | |
: State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {} | |
explicit EmplaceableArg(bool) : State(EAS_Arg) {} | |
private: | |
EmplaceableArg &operator=(EmplaceableArg &&) = delete; | |
EmplaceableArg &operator=(const EmplaceableArg &) = delete; | |
}; | |
enum EmplaceableState { ES_Emplaced, ES_Moved }; | |
struct Emplaceable { | |
EmplaceableArg<0> A0; | |
EmplaceableArg<1> A1; | |
EmplaceableArg<2> A2; | |
EmplaceableArg<3> A3; | |
EmplaceableState State; | |
Emplaceable() : State(ES_Emplaced) {} | |
template <class A0Ty> | |
explicit Emplaceable(A0Ty &&A0) | |
: A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {} | |
template <class A0Ty, class A1Ty> | |
Emplaceable(A0Ty &&A0, A1Ty &&A1) | |
: A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), | |
State(ES_Emplaced) {} | |
template <class A0Ty, class A1Ty, class A2Ty> | |
Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2) | |
: A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), | |
A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {} | |
template <class A0Ty, class A1Ty, class A2Ty, class A3Ty> | |
Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3) | |
: A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)), | |
A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)), | |
State(ES_Emplaced) {} | |
Emplaceable(Emplaceable &&) : State(ES_Moved) {} | |
Emplaceable &operator=(Emplaceable &&) { | |
State = ES_Moved; | |
return *this; | |
} | |
private: | |
Emplaceable(const Emplaceable &) = delete; | |
Emplaceable &operator=(const Emplaceable &) = delete; | |
}; | |
TEST(SmallVectorTest, EmplaceBack) { | |
EmplaceableArg<0> A0(true); | |
EmplaceableArg<1> A1(true); | |
EmplaceableArg<2> A2(true); | |
EmplaceableArg<3> A3(true); | |
{ | |
SmallVector<Emplaceable, 3> V; | |
Emplaceable &back = V.emplace_back(); | |
EXPECT_TRUE(&back == &V.back()); | |
EXPECT_TRUE(V.size() == 1); | |
EXPECT_TRUE(back.State == ES_Emplaced); | |
EXPECT_TRUE(back.A0.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A1.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); | |
} | |
{ | |
SmallVector<Emplaceable, 3> V; | |
Emplaceable &back = V.emplace_back(std::move(A0)); | |
EXPECT_TRUE(&back == &V.back()); | |
EXPECT_TRUE(V.size() == 1); | |
EXPECT_TRUE(back.State == ES_Emplaced); | |
EXPECT_TRUE(back.A0.State == EAS_RValue); | |
EXPECT_TRUE(back.A1.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); | |
} | |
{ | |
SmallVector<Emplaceable, 3> V; | |
Emplaceable &back = V.emplace_back(A0); | |
EXPECT_TRUE(&back == &V.back()); | |
EXPECT_TRUE(V.size() == 1); | |
EXPECT_TRUE(back.State == ES_Emplaced); | |
EXPECT_TRUE(back.A0.State == EAS_LValue); | |
EXPECT_TRUE(back.A1.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); | |
} | |
{ | |
SmallVector<Emplaceable, 3> V; | |
Emplaceable &back = V.emplace_back(A0, A1); | |
EXPECT_TRUE(&back == &V.back()); | |
EXPECT_TRUE(V.size() == 1); | |
EXPECT_TRUE(back.State == ES_Emplaced); | |
EXPECT_TRUE(back.A0.State == EAS_LValue); | |
EXPECT_TRUE(back.A1.State == EAS_LValue); | |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); | |
} | |
{ | |
SmallVector<Emplaceable, 3> V; | |
Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1)); | |
EXPECT_TRUE(&back == &V.back()); | |
EXPECT_TRUE(V.size() == 1); | |
EXPECT_TRUE(back.State == ES_Emplaced); | |
EXPECT_TRUE(back.A0.State == EAS_RValue); | |
EXPECT_TRUE(back.A1.State == EAS_RValue); | |
EXPECT_TRUE(back.A2.State == EAS_Defaulted); | |
EXPECT_TRUE(back.A3.State == EAS_Defaulted); | |
} | |
{ | |
SmallVector<Emplaceable, 3> V; | |
Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3); | |
EXPECT_TRUE(&back == &V.back()); | |
EXPECT_TRUE(V.size() == 1); | |
EXPECT_TRUE(back.State == ES_Emplaced); | |
EXPECT_TRUE(back.A0.State == EAS_RValue); | |
EXPECT_TRUE(back.A1.State == EAS_LValue); | |
EXPECT_TRUE(back.A2.State == EAS_RValue); | |
EXPECT_TRUE(back.A3.State == EAS_LValue); | |
} | |
{ | |
SmallVector<int, 1> V; | |
V.emplace_back(); | |
V.emplace_back(42); | |
EXPECT_EQ(2U, V.size()); | |
EXPECT_EQ(0, V[0]); | |
EXPECT_EQ(42, V[1]); | |
} | |
} | |
TEST(SmallVectorTest, InitializerList) { | |
SmallVector<int, 2> V1 = {}; | |
EXPECT_TRUE(V1.empty()); | |
V1 = {0, 0}; | |
EXPECT_TRUE(makeArrayRef(V1).equals({0, 0})); | |
V1 = {-1, -1}; | |
EXPECT_TRUE(makeArrayRef(V1).equals({-1, -1})); | |
SmallVector<int, 2> V2 = {1, 2, 3, 4}; | |
EXPECT_TRUE(makeArrayRef(V2).equals({1, 2, 3, 4})); | |
V2.assign({4}); | |
EXPECT_TRUE(makeArrayRef(V2).equals({4})); | |
V2.append({3, 2}); | |
EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2})); | |
V2.insert(V2.begin() + 1, 5); | |
EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2})); | |
} | |
} // end namespace |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment