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
32class BumpVectorContext {
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 // The move assignment operator is defined as deleted pending further
46 // motivation.
47 BumpVectorContext &operator=(BumpVectorContext &&) = delete;
48
49 // The copy constrcutor and copy assignment operator is defined as deleted
50 // pending further motivation.
51 BumpVectorContext(const BumpVectorContext &) = delete;
52 BumpVectorContext &operator=(const BumpVectorContext &) = delete;
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
59 ~BumpVectorContext() {
60 if (Alloc.getInt())
61 delete Alloc.getPointer();
62 }
63
64 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
65};
66
67template<typename T>
68class BumpVector {
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
79 ~BumpVector() {
80 if (std::is_class<T>::value) {
81 // Destroy the constructed elements in the vector.
82 destroy_range(S: Begin, E: End);
83 }
84 }
85
86 using size_type = size_t;
87 using difference_type = ptrdiff_t;
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.
107 reverse_iterator rbegin() { return reverse_iterator(end()); }
108 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
109 reverse_iterator rend() { return reverse_iterator(begin()); }
110 const_reverse_iterator rend() const {
111 return const_reverse_iterator(begin());
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
126 reference front() {
127 return begin()[0];
128 }
129 const_reference front() const {
130 return begin()[0];
131 }
132
133 reference back() {
134 return end()[-1];
135 }
136 const_reference back() const {
137 return end()[-1];
138 }
139
140 void pop_back() {
141 --End;
142 End->~T();
143 }
144
145 T pop_back_val() {
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(S: Begin, E: End);
154 }
155 End = Begin;
156 }
157
158 /// data - Return a pointer to the vector's buffer, even if empty().
159 pointer data() {
160 return pointer(Begin);
161 }
162
163 /// data - Return a pointer to the vector's buffer, even if empty().
164 const_pointer data() const {
165 return const_pointer(Begin);
166 }
167
168 void push_back(const_reference Elt, BumpVectorContext &C) {
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.
181 iterator insert(iterator I, size_t Cnt, const_reference E,
182 BumpVectorContext &C) {
183 assert(I >= Begin && I <= End && "Iterator out of bounds.");
184 if (End + Cnt <= Capacity) {
185 Retry:
186 move_range_right(S: I, E: End, D: Cnt);
187 construct_range(S: I, E: I + Cnt, Elt: E);
188 End += Cnt;
189 return I + Cnt;
190 }
191 ptrdiff_t D = I - Begin;
192 grow(C, MinSize: 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, MinSize: 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(S: Begin, E: 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
266