clang 20.0.0git
BumpVector.h
Go to the documentation of this file.
1//===- BumpVector.h - Vector-like ADT that uses bump allocation -*- C++ -*-===//
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 provides BumpVector, a vector-like ADT whose contents are
10// allocated from a BumpPtrAllocator.
11//
12//===----------------------------------------------------------------------===//
13
14// FIXME: Most of this is copy-and-paste from SmallVector.h. We can
15// refactor this core logic into something common that is shared between
16// the two. The main thing that is different is the allocation strategy.
17
18#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
19#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
20
21#include "llvm/ADT/PointerIntPair.h"
22#include "llvm/Support/Allocator.h"
23#include <cassert>
24#include <cstddef>
25#include <cstring>
26#include <iterator>
27#include <memory>
28#include <type_traits>
29
30namespace clang {
31
33 llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
34
35public:
36 /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator
37 /// and destroys it when the BumpVectorContext object is destroyed.
38 BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {}
39
41 Other.Alloc.setInt(false);
42 Other.Alloc.setPointer(nullptr);
43 }
44
45 // The move assignment operator is defined as deleted pending further
46 // motivation.
48
49 // The copy constrcutor and copy assignment operator is defined as deleted
50 // pending further motivation.
53
54 /// Construct a new BumpVectorContext that reuses an existing
55 /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the
56 /// BumpVectorContext object is destroyed.
57 BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {}
58
60 if (Alloc.getInt())
61 delete Alloc.getPointer();
62 }
63
64 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
65};
66
67template<typename T>
69 T *Begin = nullptr;
70 T *End = nullptr;
71 T *Capacity = nullptr;
72
73public:
74 // Default ctor - Initialize to empty.
75 explicit BumpVector(BumpVectorContext &C, unsigned N) {
76 reserve(C, N);
77 }
78
80 if (std::is_class<T>::value) {
81 // Destroy the constructed elements in the vector.
82 destroy_range(Begin, End);
83 }
84 }
85
88 using value_type = T;
89 using iterator = T *;
90 using const_iterator = const T *;
91
92 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
93 using reverse_iterator = std::reverse_iterator<iterator>;
94
95 using reference = T &;
96 using const_reference = const T &;
97 using pointer = T *;
98 using const_pointer = const T *;
99
100 // forward iterator creation methods.
101 iterator begin() { return Begin; }
102 const_iterator begin() const { return Begin; }
103 iterator end() { return End; }
104 const_iterator end() const { return End; }
105
106 // reverse iterator creation methods.
112 }
113
114 bool empty() const { return Begin == End; }
115 size_type size() const { return End-Begin; }
116
117 reference operator[](unsigned idx) {
118 assert(Begin + idx < End);
119 return Begin[idx];
120 }
121 const_reference operator[](unsigned idx) const {
122 assert(Begin + idx < End);
123 return Begin[idx];
124 }
125
127 return begin()[0];
128 }
130 return begin()[0];
131 }
132
134 return end()[-1];
135 }
137 return end()[-1];
138 }
139
140 void pop_back() {
141 --End;
142 End->~T();
143 }
144
146 T Result = back();
147 pop_back();
148 return Result;
149 }
150
151 void clear() {
152 if (std::is_class<T>::value) {
153 destroy_range(Begin, End);
154 }
155 End = Begin;
156 }
157
158 /// data - Return a pointer to the vector's buffer, even if empty().
160 return pointer(Begin);
161 }
162
163 /// data - Return a pointer to the vector's buffer, even if empty().
165 return const_pointer(Begin);
166 }
167
169 if (End < Capacity) {
170 Retry:
171 new (End) T(Elt);
172 ++End;
173 return;
174 }
175 grow(C);
176 goto Retry;
177 }
178
179 /// insert - Insert some number of copies of element into a position. Return
180 /// iterator to position after last inserted copy.
183 assert(I >= Begin && I <= End && "Iterator out of bounds.");
184 if (End + Cnt <= Capacity) {
185 Retry:
186 move_range_right(I, End, Cnt);
187 construct_range(I, I + Cnt, E);
188 End += Cnt;
189 return I + Cnt;
190 }
191 ptrdiff_t D = I - Begin;
192 grow(C, size() + Cnt);
193 I = Begin + D;
194 goto Retry;
195 }
196
197 void reserve(BumpVectorContext &C, unsigned N) {
198 if (unsigned(Capacity-Begin) < N)
199 grow(C, N);
200 }
201
202 /// capacity - Return the total number of elements in the currently allocated
203 /// buffer.
204 size_t capacity() const { return Capacity - Begin; }
205
206private:
207 /// grow - double the size of the allocated memory, guaranteeing space for at
208 /// least one more element or MinSize if specified.
209 void grow(BumpVectorContext &C, size_type MinSize = 1);
210
211 void construct_range(T *S, T *E, const T &Elt) {
212 for (; S != E; ++S)
213 new (S) T(Elt);
214 }
215
216 void destroy_range(T *S, T *E) {
217 while (S != E) {
218 --E;
219 E->~T();
220 }
221 }
222
223 void move_range_right(T *S, T *E, size_t D) {
224 for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) {
225 --E;
226 new (I) T(*E);
227 E->~T();
228 }
229 }
230};
231
232// Define this out-of-line to dissuade the C++ compiler from inlining it.
233template <typename T>
234void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) {
235 size_t CurCapacity = Capacity-Begin;
236 size_t CurSize = size();
237 size_t NewCapacity = 2*CurCapacity;
238 if (NewCapacity < MinSize)
239 NewCapacity = MinSize;
240
241 // Allocate the memory from the BumpPtrAllocator.
242 T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
243
244 // Copy the elements over.
245 if (Begin != End) {
246 if (std::is_class<T>::value) {
247 std::uninitialized_copy(Begin, End, NewElts);
248 // Destroy the original elements.
249 destroy_range(Begin, End);
250 } else {
251 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
252 memcpy(NewElts, Begin, CurSize * sizeof(T));
253 }
254 }
255
256 // For now, leak 'Begin'. We can add it back to a freelist in
257 // BumpVectorContext.
258 Begin = NewElts;
259 End = NewElts+CurSize;
260 Capacity = Begin+NewCapacity;
261}
262
263} // namespace clang
264
265#endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
const Decl * D
Expr * E
SourceLocation Begin
__DEVICE__ void * memcpy(void *__a, const void *__b, size_t __c)
__PTRDIFF_TYPE__ ptrdiff_t
__SIZE_TYPE__ size_t
BumpVectorContext(const BumpVectorContext &)=delete
BumpVectorContext(llvm::BumpPtrAllocator &A)
Construct a new BumpVectorContext that reuses an existing BumpPtrAllocator.
Definition: BumpVector.h:57
BumpVectorContext & operator=(const BumpVectorContext &)=delete
BumpVectorContext(BumpVectorContext &&Other)
Definition: BumpVector.h:40
BumpVectorContext & operator=(BumpVectorContext &&)=delete
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:64
BumpVectorContext()
Construct a new BumpVectorContext that creates a new BumpPtrAllocator and destroys it when the BumpVe...
Definition: BumpVector.h:38
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: BumpVector.h:92
reference operator[](unsigned idx)
Definition: BumpVector.h:117
ptrdiff_t difference_type
Definition: BumpVector.h:87
reference back()
Definition: BumpVector.h:133
const_reference operator[](unsigned idx) const
Definition: BumpVector.h:121
const_reference front() const
Definition: BumpVector.h:129
const_iterator begin() const
Definition: BumpVector.h:102
const_iterator end() const
Definition: BumpVector.h:104
iterator insert(iterator I, size_t Cnt, const_reference E, BumpVectorContext &C)
insert - Insert some number of copies of element into a position.
Definition: BumpVector.h:181
pointer data()
data - Return a pointer to the vector's buffer, even if empty().
Definition: BumpVector.h:159
reference front()
Definition: BumpVector.h:126
BumpVector(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:75
size_type size() const
Definition: BumpVector.h:115
iterator end()
Definition: BumpVector.h:103
void reserve(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:197
const T & const_reference
Definition: BumpVector.h:96
bool empty() const
Definition: BumpVector.h:114
const_reverse_iterator rbegin() const
Definition: BumpVector.h:108
reverse_iterator rbegin()
Definition: BumpVector.h:107
std::reverse_iterator< iterator > reverse_iterator
Definition: BumpVector.h:93
const_pointer data() const
data - Return a pointer to the vector's buffer, even if empty().
Definition: BumpVector.h:164
const_reference back() const
Definition: BumpVector.h:136
const_reverse_iterator rend() const
Definition: BumpVector.h:110
reverse_iterator rend()
Definition: BumpVector.h:109
const T * const_pointer
Definition: BumpVector.h:98
void push_back(const_reference Elt, BumpVectorContext &C)
Definition: BumpVector.h:168
const T * const_iterator
Definition: BumpVector.h:90
size_t capacity() const
capacity - Return the total number of elements in the currently allocated buffer.
Definition: BumpVector.h:204
iterator begin()
Definition: BumpVector.h:101
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
const FunctionProtoType * T
@ Other
Other implicit parameter.
Diagnostic wrappers for TextAPI types for error reporting.
Definition: Dominators.h:30