BumpVector.h source code [clang_source_code/include/clang/Analysis/Support/BumpVector.h]

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
30	namespace clang {
31
32	class BumpVectorContext {
33	llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
34
35	public:
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
50	~BumpVectorContext() {
51	if (Alloc.getInt())
52	delete Alloc.getPointer();
53	}
54
55	llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
56	};
57
58	template<typename T>
59	class BumpVector {
60	T *Begin = nullptr;
61	T *End = nullptr;
62	T *Capacity = nullptr;
63
64	public:
65	// Default ctor - Initialize to empty.
66	explicit BumpVector(BumpVectorContext &C, unsigned N) {
67	reserve(C, N);
68	}
69
70	~BumpVector() {
71	if (std::is_class<T>::value) {
72	// Destroy the constructed elements in the vector.
73	destroy_range(Begin, End);
74	}
75	}
76
77	using size_type = size_t;
78	using difference_type = ptrdiff_t;
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.
98	reverse_iterator rbegin() { return reverse_iterator(end()); }
99	const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
100	reverse_iterator rend() { return reverse_iterator(begin()); }
101	const_reverse_iterator rend() const {
102	return const_reverse_iterator(begin());
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
117	reference front() {
118	return begin()[0];
119	}
120	const_reference front() const {
121	return begin()[0];
122	}
123
124	reference back() {
125	return end()[-1];
126	}
127	const_reference back() const {
128	return end()[-1];
129	}
130
131	void pop_back() {
132	--End;
133	End->~T();
134	}
135
136	T pop_back_val() {
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().
150	pointer data() {
151	return pointer(Begin);
152	}
153
154	/// data - Return a pointer to the vector's buffer, even if empty().
155	const_pointer data() const {
156	return const_pointer(Begin);
157	}
158
159	void push_back(const_reference Elt, BumpVectorContext &C) {
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.
172	iterator insert(iterator I, size_t Cnt, const_reference E,
173	BumpVectorContext &C) {
174	(0) . __assert_fail ("I >= Begin && I <= End && \"Iterator out of bounds.\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Support/BumpVector.h", 174, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">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
197	private:
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.
224	template <typename T>
225	void 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
257