1 | //===- llvm/ADT/SmallVector.cpp - 'Normally small' vectors ----------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file implements the SmallVector class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | // ATen: modified from llvm::SmallVector. |
14 | // replaced llvm::safe_malloc with std::bad_alloc |
15 | // deleted LLVM_ENABLE_EXCEPTIONS |
16 | |
17 | #include <c10/util/SmallVector.h> |
18 | #include <cstdint> |
19 | #include <stdexcept> |
20 | #include <string> |
21 | using namespace c10; |
22 | |
23 | // Check that no bytes are wasted and everything is well-aligned. |
24 | namespace { |
25 | // These structures may cause binary compat warnings on AIX. Suppress the |
26 | // warning since we are only using these types for the static assertions below. |
27 | #if defined(_AIX) |
28 | #pragma GCC diagnostic push |
29 | #pragma GCC diagnostic ignored "-Waix-compat" |
30 | #endif |
31 | struct Struct16B { |
32 | alignas(16) void* X; |
33 | }; |
34 | struct Struct32B { |
35 | alignas(32) void* X; |
36 | }; |
37 | #if defined(_AIX) |
38 | #pragma GCC diagnostic pop |
39 | #endif |
40 | } // namespace |
41 | static_assert( |
42 | sizeof(SmallVector<void*, 0>) == sizeof(unsigned) * 2 + sizeof(void*), |
43 | "wasted space in SmallVector size 0" ); |
44 | static_assert( |
45 | alignof(SmallVector<Struct16B, 0>) >= alignof(Struct16B), |
46 | "wrong alignment for 16-byte aligned T" ); |
47 | static_assert( |
48 | alignof(SmallVector<Struct32B, 0>) >= alignof(Struct32B), |
49 | "wrong alignment for 32-byte aligned T" ); |
50 | static_assert( |
51 | sizeof(SmallVector<Struct16B, 0>) >= alignof(Struct16B), |
52 | "missing padding for 16-byte aligned T" ); |
53 | static_assert( |
54 | sizeof(SmallVector<Struct32B, 0>) >= alignof(Struct32B), |
55 | "missing padding for 32-byte aligned T" ); |
56 | static_assert( |
57 | sizeof(SmallVector<void*, 1>) == sizeof(unsigned) * 2 + sizeof(void*) * 2, |
58 | "wasted space in SmallVector size 1" ); |
59 | |
60 | static_assert( |
61 | sizeof(SmallVector<char, 0>) == sizeof(void*) * 2 + sizeof(void*), |
62 | "1 byte elements have word-sized type for size and capacity" ); |
63 | |
64 | /// Report that MinSize doesn't fit into this vector's size type. Throws |
65 | /// std::length_error or calls report_fatal_error. |
66 | [[noreturn]] static void report_size_overflow(size_t MinSize, size_t MaxSize); |
67 | static void report_size_overflow(size_t MinSize, size_t MaxSize) { |
68 | std::string Reason = "SmallVector unable to grow. Requested capacity (" + |
69 | std::to_string(MinSize) + |
70 | ") is larger than maximum value for size type (" + |
71 | std::to_string(MaxSize) + ")" ; |
72 | throw std::length_error(Reason); |
73 | } |
74 | |
75 | /// Report that this vector is already at maximum capacity. Throws |
76 | /// std::length_error or calls report_fatal_error. |
77 | [[noreturn]] static void report_at_maximum_capacity(size_t MaxSize); |
78 | static void report_at_maximum_capacity(size_t MaxSize) { |
79 | std::string Reason = |
80 | "SmallVector capacity unable to grow. Already at maximum size " + |
81 | std::to_string(MaxSize); |
82 | throw std::length_error(Reason); |
83 | } |
84 | |
85 | // Note: Moving this function into the header may cause performance regression. |
86 | template <class Size_T> |
87 | static size_t getNewCapacity(size_t MinSize, size_t TSize, size_t OldCapacity) { |
88 | constexpr size_t MaxSize = std::numeric_limits<Size_T>::max(); |
89 | |
90 | // Ensure we can fit the new capacity. |
91 | // This is only going to be applicable when the capacity is 32 bit. |
92 | if (MinSize > MaxSize) |
93 | report_size_overflow(MinSize, MaxSize); |
94 | |
95 | // Ensure we can meet the guarantee of space for at least one more element. |
96 | // The above check alone will not catch the case where grow is called with a |
97 | // default MinSize of 0, but the current capacity cannot be increased. |
98 | // This is only going to be applicable when the capacity is 32 bit. |
99 | if (OldCapacity == MaxSize) |
100 | report_at_maximum_capacity(MaxSize); |
101 | |
102 | // In theory 2*capacity can overflow if the capacity is 64 bit, but the |
103 | // original capacity would never be large enough for this to be a problem. |
104 | size_t NewCapacity = 2 * OldCapacity + 1; // Always grow. |
105 | return std::min(std::max(NewCapacity, MinSize), MaxSize); |
106 | } |
107 | |
108 | // Note: Moving this function into the header may cause performance regression. |
109 | template <class Size_T> |
110 | void* SmallVectorBase<Size_T>::mallocForGrow( |
111 | size_t MinSize, |
112 | size_t TSize, |
113 | size_t& NewCapacity) { |
114 | NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity()); |
115 | auto Result = std::malloc(NewCapacity * TSize); |
116 | if (Result == nullptr) { |
117 | throw std::bad_alloc(); |
118 | } |
119 | return Result; |
120 | } |
121 | |
122 | // Note: Moving this function into the header may cause performance regression. |
123 | template <class Size_T> |
124 | void SmallVectorBase<Size_T>::grow_pod( |
125 | void* FirstEl, |
126 | size_t MinSize, |
127 | size_t TSize) { |
128 | size_t NewCapacity = getNewCapacity<Size_T>(MinSize, TSize, this->capacity()); |
129 | void* NewElts = nullptr; |
130 | if (BeginX == FirstEl) { |
131 | NewElts = std::malloc(NewCapacity * TSize); |
132 | if (NewElts == nullptr) { |
133 | throw std::bad_alloc(); |
134 | } |
135 | |
136 | // Copy the elements over. No need to run dtors on PODs. |
137 | memcpy(NewElts, this->BeginX, size() * TSize); |
138 | } else { |
139 | // If this wasn't grown from the inline copy, grow the allocated space. |
140 | NewElts = std::realloc(this->BeginX, NewCapacity * TSize); |
141 | if (NewElts == nullptr) { |
142 | throw std::bad_alloc(); |
143 | } |
144 | } |
145 | |
146 | this->BeginX = NewElts; |
147 | this->Capacity = NewCapacity; |
148 | } |
149 | |
150 | template class c10::SmallVectorBase<uint32_t>; |
151 | |
152 | // Disable the uint64_t instantiation for 32-bit builds. |
153 | // Both uint32_t and uint64_t instantiations are needed for 64-bit builds. |
154 | // This instantiation will never be used in 32-bit builds, and will cause |
155 | // warnings when sizeof(Size_T) > sizeof(size_t). |
156 | #if SIZE_MAX > UINT32_MAX |
157 | template class c10::SmallVectorBase<uint64_t>; |
158 | |
159 | // Assertions to ensure this #if stays in sync with SmallVectorSizeType. |
160 | static_assert( |
161 | sizeof(SmallVectorSizeType<char>) == sizeof(uint64_t), |
162 | "Expected SmallVectorBase<uint64_t> variant to be in use." ); |
163 | #else |
164 | static_assert( |
165 | sizeof(SmallVectorSizeType<char>) == sizeof(uint32_t), |
166 | "Expected SmallVectorBase<uint32_t> variant to be in use." ); |
167 | #endif |
168 | |