1//===- llvm/ADT/SmallVector.cpp - 'Normally small' vectors ----------------===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// This file implements the SmallVector class. 11//===----------------------------------------------------------------------===// 17#ifdef LLVM_ENABLE_EXCEPTIONS 22// Check that no bytes are wasted and everything is well-aligned. 24// These structures may cause binary compat warnings on AIX. Suppress the 25// warning since we are only using these types for the static assertions below. 27#pragma GCC diagnostic push 28#pragma GCC diagnostic ignored "-Waix-compat" 37#pragma GCC diagnostic pop 41sizeof(
unsigned) * 2 +
sizeof(
void *),
42"wasted space in SmallVector size 0");
44"wrong alignment for 16-byte aligned T");
46"wrong alignment for 32-byte aligned T");
48"missing padding for 16-byte aligned T");
50"missing padding for 32-byte aligned T");
52sizeof(
unsigned) * 2 +
sizeof(
void *) * 2,
53"wasted space in SmallVector size 1");
56sizeof(
void *) * 2 +
sizeof(
void *),
57"1 byte elements have word-sized type for size and capacity");
59/// Report that MinSize doesn't fit into this vector's size type. Throws 60/// std::length_error or calls report_fatal_error. 63 std::string Reason =
"SmallVector unable to grow. Requested capacity (" +
64 std::to_string(MinSize) +
65") is larger than maximum value for size type (" +
66 std::to_string(MaxSize) +
")";
67#ifdef LLVM_ENABLE_EXCEPTIONS 68throw std::length_error(Reason);
74/// Report that this vector is already at maximum capacity. Throws 75/// std::length_error or calls report_fatal_error. 79"SmallVector capacity unable to grow. Already at maximum size " +
80 std::to_string(MaxSize);
81#ifdef LLVM_ENABLE_EXCEPTIONS 82throw std::length_error(Reason);
88// Note: Moving this function into the header may cause performance regression. 89template <
class Size_T>
91constexprsize_t MaxSize = std::numeric_limits<Size_T>::max();
93// Ensure we can fit the new capacity. 94// This is only going to be applicable when the capacity is 32 bit. 98// Ensure we can meet the guarantee of space for at least one more element. 99// The above check alone will not catch the case where grow is called with a 100// default MinSize of 0, but the current capacity cannot be increased. 101// This is only going to be applicable when the capacity is 32 bit. 102if (OldCapacity == MaxSize)
105// In theory 2*capacity can overflow if the capacity is 64 bit, but the 106// original capacity would never be large enough for this to be a problem. 107size_t NewCapacity = 2 * OldCapacity + 1;
// Always grow. 108return std::clamp(NewCapacity, MinSize, MaxSize);
111/// If vector was first created with capacity 0, getFirstEl() points to the 112/// memory right after, an area unallocated. If a subsequent allocation, 113/// that grows the vector, happens to return the same pointer as getFirstEl(), 114/// get a new allocation, otherwise isSmall() will falsely return that no 115/// allocation was done (true) and the memory will not be freed in the 116/// destructor. If a VSize is given (vector size), also copy that many 117/// elements to the new allocation - used if realloca fails to increase 118/// space, and happens to allocate precisely at BeginX. 119/// This is unlikely to be called often, but resolves a memory leak when the 120/// situation does occur. 125 memcpy(NewEltsReplace, NewElts, VSize * TSize);
127return NewEltsReplace;
130// Note: Moving this function into the header may cause performance regression. 131template <
class Size_T>
134size_t &NewCapacity) {
135 NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity());
136// Even if capacity is not 0 now, if the vector was originally created with 137// capacity 0, it's possible for the malloc to return FirstEl. 139if (NewElts == FirstEl)
144// Note: Moving this function into the header may cause performance regression. 145template <
class Size_T>
148size_t NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity());
150if (BeginX == FirstEl) {
152if (NewElts == FirstEl)
155// Copy the elements over. No need to run dtors on PODs. 156 memcpy(NewElts, this->BeginX,
size() * TSize);
158// If this wasn't grown from the inline copy, grow the allocated space. 160if (NewElts == FirstEl)
164 this->set_allocation_range(NewElts, NewCapacity);
169// Disable the uint64_t instantiation for 32-bit builds. 170// Both uint32_t and uint64_t instantiations are needed for 64-bit builds. 171// This instantiation will never be used in 32-bit builds, and will cause 172// warnings when sizeof(Size_T) > sizeof(size_t). 173#if SIZE_MAX > UINT32_MAX 176// Assertions to ensure this #if stays in sync with SmallVectorSizeType. 178"Expected SmallVectorBase<uint64_t> variant to be in use.");
181"Expected SmallVectorBase<uint32_t> variant to be in use.");
This file defines counterparts of C library allocation functions defined in the namespace 'std'.
static void report_size_overflow(size_t MinSize, size_t MaxSize)
Report that MinSize doesn't fit into this vector's size type.
static size_t getNewCapacity(size_t MinSize, size_t TSize, size_t OldCapacity)
static void report_at_maximum_capacity(size_t MaxSize)
Report that this vector is already at maximum capacity.
static void * replaceAllocation(void *NewElts, size_t TSize, size_t NewCapacity, size_t VSize=0)
If vector was first created with capacity 0, getFirstEl() points to the memory right after,...
This file defines the SmallVector class.
This is all the stuff common to all SmallVectors.
void grow_pod(void *FirstEl, size_t MinSize, size_t TSize)
This is an implementation of the grow() method which only works on POD-like data types and is out of ...
void * mallocForGrow(void *FirstEl, size_t MinSize, size_t TSize, size_t &NewCapacity)
This is a helper for grow() that's out of line to reduce code duplication.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
std::conditional_t< sizeof(T)< 4 &&sizeof(void *) >=8, uint64_t, uint32_t > SmallVectorSizeType
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_realloc(void *Ptr, size_t Sz)
