clang 17.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
40 BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) {
41 Other.Alloc.setInt(false);
42 Other.Alloc.setPointer(nullptr);
43 }
44
45 /// Construct a new BumpVectorContext that reuses an existing
46 /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the
47 /// BumpVectorContext object is destroyed.
48 BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {}
49
51 if (Alloc.getInt())
52 delete Alloc.getPointer();
53 }
54
55 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
56};
57
58template<typename T>
60 T *Begin = nullptr;
61 T *End = nullptr;
62 T *Capacity = nullptr;
63
64public:
65 // Default ctor - Initialize to empty.
66 explicit BumpVector(BumpVectorContext &C, unsigned N) {
67 reserve(C, N);
68 }
69
71 if (std::is_class<T>::value) {
72 // Destroy the constructed elements in the vector.
73 destroy_range(Begin, End);
74 }
75 }
76
79 using value_type = T;
80 using iterator = T *;
81 using const_iterator = const T *;
82
83 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
84 using reverse_iterator = std::reverse_iterator<iterator>;
85
86 using reference = T &;
87 using const_reference = const T &;
88 using pointer = T *;
89 using const_pointer = const T *;
90
91 // forward iterator creation methods.
92 iterator begin() { return Begin; }
93 const_iterator begin() const { return Begin; }
94 iterator end() { return End; }
95 const_iterator end() const { return End; }
96
97 // reverse iterator creation methods.
103 }
104
105 bool empty() const { return Begin == End; }
106 size_type size() const { return End-Begin; }
107
108 reference operator[](unsigned idx) {
109 assert(Begin + idx < End);
110 return Begin[idx];
111 }
112 const_reference operator[](unsigned idx) const {
113 assert(Begin + idx < End);
114 return Begin[idx];
115 }
116
118 return begin()[0];
119 }
121 return begin()[0];
122 }
123
125 return end()[-1];
126 }
128 return end()[-1];
129 }
130
131 void pop_back() {
132 --End;
133 End->~T();
134 }
135
137 T Result = back();
138 pop_back();
139 return Result;
140 }
141
142 void clear() {
143 if (std::is_class<T>::value) {
144 destroy_range(Begin, End);
145 }
146 End = Begin;
147 }
148
149 /// data - Return a pointer to the vector's buffer, even if empty().
151 return pointer(Begin);
152 }
153
154 /// data - Return a pointer to the vector's buffer, even if empty().
156 return const_pointer(Begin);
157 }
158
160 if (End < Capacity) {
161 Retry:
162 new (End) T(Elt);
163 ++End;
164 return;
165 }
166 grow(C);
167 goto Retry;
168 }
169
170 /// insert - Insert some number of copies of element into a position. Return
171 /// iterator to position after last inserted copy.
174 assert(I >= Begin && I <= End && "Iterator out of bounds.");
175 if (End + Cnt <= Capacity) {
176 Retry:
177 move_range_right(I, End, Cnt);
178 construct_range(I, I + Cnt, E);
179 End += Cnt;
180 return I + Cnt;
181 }
182 ptrdiff_t D = I - Begin;
183 grow(C, size() + Cnt);
184 I = Begin + D;
185 goto Retry;
186 }
187
188 void reserve(BumpVectorContext &C, unsigned N) {
189 if (unsigned(Capacity-Begin) < N)
190 grow(C, N);
191 }
192
193 /// capacity - Return the total number of elements in the currently allocated
194 /// buffer.
195 size_t capacity() const { return Capacity - Begin; }
196
197private:
198 /// grow - double the size of the allocated memory, guaranteeing space for at
199 /// least one more element or MinSize if specified.
200 void grow(BumpVectorContext &C, size_type MinSize = 1);
201
202 void construct_range(T *S, T *E, const T &Elt) {
203 for (; S != E; ++S)
204 new (S) T(Elt);
205 }
206
207 void destroy_range(T *S, T *E) {
208 while (S != E) {
209 --E;
210 E->~T();
211 }
212 }
213
214 void move_range_right(T *S, T *E, size_t D) {
215 for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) {
216 --E;
217 new (I) T(*E);
218 E->~T();
219 }
220 }
221};
222
223// Define this out-of-line to dissuade the C++ compiler from inlining it.
224template <typename T>
225void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) {
226 size_t CurCapacity = Capacity-Begin;
227 size_t CurSize = size();
228 size_t NewCapacity = 2*CurCapacity;
229 if (NewCapacity < MinSize)
230 NewCapacity = MinSize;
231
232 // Allocate the memory from the BumpPtrAllocator.
233 T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
234
235 // Copy the elements over.
236 if (Begin != End) {
237 if (std::is_class<T>::value) {
238 std::uninitialized_copy(Begin, End, NewElts);
239 // Destroy the original elements.
240 destroy_range(Begin, End);
241 } else {
242 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
243 memcpy(NewElts, Begin, CurSize * sizeof(T));
244 }
245 }
246
247 // For now, leak 'Begin'. We can add it back to a freelist in
248 // BumpVectorContext.
249 Begin = NewElts;
250 End = NewElts+CurSize;
251 Capacity = Begin+NewCapacity;
252}
253
254} // namespace clang
255
256#endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
SourceLocation Begin
__DEVICE__ void * memcpy(void *__a, const void *__b, size_t __c)
BumpVectorContext(llvm::BumpPtrAllocator &A)
Construct a new BumpVectorContext that reuses an existing BumpPtrAllocator.
Definition: BumpVector.h:48
BumpVectorContext(BumpVectorContext &&Other)
Definition: BumpVector.h:40
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:55
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:83
reference operator[](unsigned idx)
Definition: BumpVector.h:108
ptrdiff_t difference_type
Definition: BumpVector.h:78
reference back()
Definition: BumpVector.h:124
const_reference operator[](unsigned idx) const
Definition: BumpVector.h:112
const_reference front() const
Definition: BumpVector.h:120
const_iterator begin() const
Definition: BumpVector.h:93
const_iterator end() const
Definition: BumpVector.h:95
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:172
pointer data()
data - Return a pointer to the vector's buffer, even if empty().
Definition: BumpVector.h:150
reference front()
Definition: BumpVector.h:117
BumpVector(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:66
size_type size() const
Definition: BumpVector.h:106
iterator end()
Definition: BumpVector.h:94
void reserve(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:188
const T & const_reference
Definition: BumpVector.h:87
bool empty() const
Definition: BumpVector.h:105
const_reverse_iterator rbegin() const
Definition: BumpVector.h:99
reverse_iterator rbegin()
Definition: BumpVector.h:98
std::reverse_iterator< iterator > reverse_iterator
Definition: BumpVector.h:84
const_pointer data() const
data - Return a pointer to the vector's buffer, even if empty().
Definition: BumpVector.h:155
const_reference back() const
Definition: BumpVector.h:127
const_reverse_iterator rend() const
Definition: BumpVector.h:101
reverse_iterator rend()
Definition: BumpVector.h:100
const T * const_pointer
Definition: BumpVector.h:89
void push_back(const_reference Elt, BumpVectorContext &C)
Definition: BumpVector.h:159
const T * const_iterator
Definition: BumpVector.h:81
size_t capacity() const
capacity - Return the total number of elements in the currently allocated buffer.
Definition: BumpVector.h:195
iterator begin()
Definition: BumpVector.h:92
@ C
Languages that the frontend can parse and compile.
@ Result
The result type of a method or function.
YAML serialization mapping.
Definition: Dominators.h:30
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.