109467b48Spatrick //===- llvm/ADT/SmallVector.cpp - 'Normally small' vectors ----------------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This file implements the SmallVector class.
1009467b48Spatrick //
1109467b48Spatrick //===----------------------------------------------------------------------===//
1209467b48Spatrick
1309467b48Spatrick #include "llvm/ADT/SmallVector.h"
14*d415bd75Srobert #include "llvm/ADT/Twine.h"
15*d415bd75Srobert #include "llvm/Support/MemAlloc.h"
16097a140dSpatrick #include <cstdint>
1773471bf0Spatrick #ifdef LLVM_ENABLE_EXCEPTIONS
1873471bf0Spatrick #include <stdexcept>
1973471bf0Spatrick #endif
2009467b48Spatrick using namespace llvm;
2109467b48Spatrick
2209467b48Spatrick // Check that no bytes are wasted and everything is well-aligned.
2309467b48Spatrick namespace {
24*d415bd75Srobert // These structures may cause binary compat warnings on AIX. Suppress the
25*d415bd75Srobert // warning since we are only using these types for the static assertions below.
26*d415bd75Srobert #if defined(_AIX)
27*d415bd75Srobert #pragma GCC diagnostic push
28*d415bd75Srobert #pragma GCC diagnostic ignored "-Waix-compat"
29*d415bd75Srobert #endif
3009467b48Spatrick struct Struct16B {
3109467b48Spatrick alignas(16) void *X;
3209467b48Spatrick };
3309467b48Spatrick struct Struct32B {
3409467b48Spatrick alignas(32) void *X;
3509467b48Spatrick };
36*d415bd75Srobert #if defined(_AIX)
37*d415bd75Srobert #pragma GCC diagnostic pop
38*d415bd75Srobert #endif
3909467b48Spatrick }
4009467b48Spatrick static_assert(sizeof(SmallVector<void *, 0>) ==
4109467b48Spatrick sizeof(unsigned) * 2 + sizeof(void *),
4209467b48Spatrick "wasted space in SmallVector size 0");
4309467b48Spatrick static_assert(alignof(SmallVector<Struct16B, 0>) >= alignof(Struct16B),
4409467b48Spatrick "wrong alignment for 16-byte aligned T");
4509467b48Spatrick static_assert(alignof(SmallVector<Struct32B, 0>) >= alignof(Struct32B),
4609467b48Spatrick "wrong alignment for 32-byte aligned T");
4709467b48Spatrick static_assert(sizeof(SmallVector<Struct16B, 0>) >= alignof(Struct16B),
4809467b48Spatrick "missing padding for 16-byte aligned T");
4909467b48Spatrick static_assert(sizeof(SmallVector<Struct32B, 0>) >= alignof(Struct32B),
5009467b48Spatrick "missing padding for 32-byte aligned T");
5109467b48Spatrick static_assert(sizeof(SmallVector<void *, 1>) ==
5209467b48Spatrick sizeof(unsigned) * 2 + sizeof(void *) * 2,
5309467b48Spatrick "wasted space in SmallVector size 1");
5409467b48Spatrick
55097a140dSpatrick static_assert(sizeof(SmallVector<char, 0>) ==
56097a140dSpatrick sizeof(void *) * 2 + sizeof(void *),
57097a140dSpatrick "1 byte elements have word-sized type for size and capacity");
58097a140dSpatrick
5973471bf0Spatrick /// Report that MinSize doesn't fit into this vector's size type. Throws
6073471bf0Spatrick /// std::length_error or calls report_fatal_error.
61*d415bd75Srobert [[noreturn]] static void report_size_overflow(size_t MinSize, size_t MaxSize);
report_size_overflow(size_t MinSize,size_t MaxSize)6273471bf0Spatrick static void report_size_overflow(size_t MinSize, size_t MaxSize) {
6373471bf0Spatrick std::string Reason = "SmallVector unable to grow. Requested capacity (" +
6473471bf0Spatrick std::to_string(MinSize) +
6573471bf0Spatrick ") is larger than maximum value for size type (" +
6673471bf0Spatrick std::to_string(MaxSize) + ")";
6773471bf0Spatrick #ifdef LLVM_ENABLE_EXCEPTIONS
6873471bf0Spatrick throw std::length_error(Reason);
6973471bf0Spatrick #else
70*d415bd75Srobert report_fatal_error(Twine(Reason));
7173471bf0Spatrick #endif
7273471bf0Spatrick }
7373471bf0Spatrick
7473471bf0Spatrick /// Report that this vector is already at maximum capacity. Throws
7573471bf0Spatrick /// std::length_error or calls report_fatal_error.
76*d415bd75Srobert [[noreturn]] static void report_at_maximum_capacity(size_t MaxSize);
report_at_maximum_capacity(size_t MaxSize)7773471bf0Spatrick static void report_at_maximum_capacity(size_t MaxSize) {
7873471bf0Spatrick std::string Reason =
7973471bf0Spatrick "SmallVector capacity unable to grow. Already at maximum size " +
8073471bf0Spatrick std::to_string(MaxSize);
8173471bf0Spatrick #ifdef LLVM_ENABLE_EXCEPTIONS
8273471bf0Spatrick throw std::length_error(Reason);
8373471bf0Spatrick #else
84*d415bd75Srobert report_fatal_error(Twine(Reason));
8573471bf0Spatrick #endif
8673471bf0Spatrick }
8773471bf0Spatrick
88097a140dSpatrick // Note: Moving this function into the header may cause performance regression.
89097a140dSpatrick template <class Size_T>
getNewCapacity(size_t MinSize,size_t TSize,size_t OldCapacity)9073471bf0Spatrick static size_t getNewCapacity(size_t MinSize, size_t TSize, size_t OldCapacity) {
9173471bf0Spatrick constexpr size_t MaxSize = std::numeric_limits<Size_T>::max();
9273471bf0Spatrick
93097a140dSpatrick // Ensure we can fit the new capacity.
94097a140dSpatrick // This is only going to be applicable when the capacity is 32 bit.
9573471bf0Spatrick if (MinSize > MaxSize)
9673471bf0Spatrick report_size_overflow(MinSize, MaxSize);
9709467b48Spatrick
98097a140dSpatrick // Ensure we can meet the guarantee of space for at least one more element.
99097a140dSpatrick // The above check alone will not catch the case where grow is called with a
10073471bf0Spatrick // default MinSize of 0, but the current capacity cannot be increased.
101097a140dSpatrick // This is only going to be applicable when the capacity is 32 bit.
10273471bf0Spatrick if (OldCapacity == MaxSize)
10373471bf0Spatrick report_at_maximum_capacity(MaxSize);
104097a140dSpatrick
105097a140dSpatrick // In theory 2*capacity can overflow if the capacity is 64 bit, but the
106097a140dSpatrick // original capacity would never be large enough for this to be a problem.
10773471bf0Spatrick size_t NewCapacity = 2 * OldCapacity + 1; // Always grow.
108*d415bd75Srobert return std::clamp(NewCapacity, MinSize, MaxSize);
109*d415bd75Srobert }
110*d415bd75Srobert
111*d415bd75Srobert template <class Size_T>
replaceAllocation(void * NewElts,size_t TSize,size_t NewCapacity,size_t VSize)112*d415bd75Srobert void *SmallVectorBase<Size_T>::replaceAllocation(void *NewElts, size_t TSize,
113*d415bd75Srobert size_t NewCapacity,
114*d415bd75Srobert size_t VSize) {
115*d415bd75Srobert void *NewEltsReplace = llvm::safe_malloc(NewCapacity * TSize);
116*d415bd75Srobert if (VSize)
117*d415bd75Srobert memcpy(NewEltsReplace, NewElts, VSize * TSize);
118*d415bd75Srobert free(NewElts);
119*d415bd75Srobert return NewEltsReplace;
12073471bf0Spatrick }
12109467b48Spatrick
12273471bf0Spatrick // Note: Moving this function into the header may cause performance regression.
12373471bf0Spatrick template <class Size_T>
mallocForGrow(void * FirstEl,size_t MinSize,size_t TSize,size_t & NewCapacity)124*d415bd75Srobert void *SmallVectorBase<Size_T>::mallocForGrow(void *FirstEl, size_t MinSize,
125*d415bd75Srobert size_t TSize,
12673471bf0Spatrick size_t &NewCapacity) {
12773471bf0Spatrick NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity());
128*d415bd75Srobert // Even if capacity is not 0 now, if the vector was originally created with
129*d415bd75Srobert // capacity 0, it's possible for the malloc to return FirstEl.
130*d415bd75Srobert void *NewElts = llvm::safe_malloc(NewCapacity * TSize);
131*d415bd75Srobert if (NewElts == FirstEl)
132*d415bd75Srobert NewElts = replaceAllocation(NewElts, TSize, NewCapacity);
133*d415bd75Srobert return NewElts;
13473471bf0Spatrick }
13573471bf0Spatrick
13673471bf0Spatrick // Note: Moving this function into the header may cause performance regression.
13773471bf0Spatrick template <class Size_T>
grow_pod(void * FirstEl,size_t MinSize,size_t TSize)13873471bf0Spatrick void SmallVectorBase<Size_T>::grow_pod(void *FirstEl, size_t MinSize,
13973471bf0Spatrick size_t TSize) {
14073471bf0Spatrick size_t NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity());
14109467b48Spatrick void *NewElts;
14209467b48Spatrick if (BeginX == FirstEl) {
143*d415bd75Srobert NewElts = llvm::safe_malloc(NewCapacity * TSize);
144*d415bd75Srobert if (NewElts == FirstEl)
145*d415bd75Srobert NewElts = replaceAllocation(NewElts, TSize, NewCapacity);
14609467b48Spatrick
14709467b48Spatrick // Copy the elements over. No need to run dtors on PODs.
14809467b48Spatrick memcpy(NewElts, this->BeginX, size() * TSize);
14909467b48Spatrick } else {
15009467b48Spatrick // If this wasn't grown from the inline copy, grow the allocated space.
151*d415bd75Srobert NewElts = llvm::safe_realloc(this->BeginX, NewCapacity * TSize);
152*d415bd75Srobert if (NewElts == FirstEl)
153*d415bd75Srobert NewElts = replaceAllocation(NewElts, TSize, NewCapacity, size());
15409467b48Spatrick }
15509467b48Spatrick
15609467b48Spatrick this->BeginX = NewElts;
15709467b48Spatrick this->Capacity = NewCapacity;
15809467b48Spatrick }
159097a140dSpatrick
160097a140dSpatrick template class llvm::SmallVectorBase<uint32_t>;
161097a140dSpatrick
162097a140dSpatrick // Disable the uint64_t instantiation for 32-bit builds.
16373471bf0Spatrick // Both uint32_t and uint64_t instantiations are needed for 64-bit builds.
164097a140dSpatrick // This instantiation will never be used in 32-bit builds, and will cause
165097a140dSpatrick // warnings when sizeof(Size_T) > sizeof(size_t).
166097a140dSpatrick #if SIZE_MAX > UINT32_MAX
167097a140dSpatrick template class llvm::SmallVectorBase<uint64_t>;
168097a140dSpatrick
169097a140dSpatrick // Assertions to ensure this #if stays in sync with SmallVectorSizeType.
170097a140dSpatrick static_assert(sizeof(SmallVectorSizeType<char>) == sizeof(uint64_t),
171097a140dSpatrick "Expected SmallVectorBase<uint64_t> variant to be in use.");
172097a140dSpatrick #else
173097a140dSpatrick static_assert(sizeof(SmallVectorSizeType<char>) == sizeof(uint32_t),
174097a140dSpatrick "Expected SmallVectorBase<uint32_t> variant to be in use.");
175097a140dSpatrick #endif
176