ASTVector.h source code [clang_source_code/include/clang/AST/ASTVector.h]

1	//===- ASTVector.h - Vector that uses ASTContext for 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 ASTVector, a vector ADT whose contents are
10	// allocated using the allocator associated with an ASTContext..
11	//
12	//===----------------------------------------------------------------------===//
13
14	// FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h.
15	// We can refactor this core logic into something common.
16
17	#ifndef LLVM_CLANG_AST_ASTVECTOR_H
18	#define LLVM_CLANG_AST_ASTVECTOR_H
19
20	#include "clang/AST/ASTContextAllocate.h"
21	#include "llvm/ADT/PointerIntPair.h"
22	#include <algorithm>
23	#include <cassert>
24	#include <cstddef>
25	#include <cstring>
26	#include <iterator>
27	#include <memory>
28	#include <type_traits>
29	#include <utility>
30
31	namespace clang {
32
33	class ASTContext;
34
35	template<typename T>
36	class ASTVector {
37	private:
38	T *Begin = nullptr;
39	T *End = nullptr;
40	llvm::PointerIntPair<T *, 1, bool> Capacity;
41
42	void setEnd(T *P) { this->End = P; }
43
44	protected:
45	// Make a tag bit available to users of this class.
46	// FIXME: This is a horrible hack.
47	bool getTag() const { return Capacity.getInt(); }
48	void setTag(bool B) { Capacity.setInt(B); }
49
50	public:
51	// Default ctor - Initialize to empty.
52	ASTVector() : Capacity(nullptr, false) {}
53
54	ASTVector(ASTVector &&O) : Begin(O.Begin), End(O.End), Capacity(O.Capacity) {
55	O.Begin = O.End = nullptr;
56	O.Capacity.setPointer(nullptr);
57	O.Capacity.setInt(false);
58	}
59
60	ASTVector(const ASTContext &C, unsigned N) : Capacity(nullptr, false) {
61	reserve(C, N);
62	}
63
64	ASTVector &operator=(ASTVector &&RHS) {
65	ASTVector O(std::move(RHS));
66
67	using std::swap;
68
69	swap(Begin, O.Begin);
70	swap(End, O.End);
71	swap(Capacity, O.Capacity);
72	return *this;
73	}
74
75	~ASTVector() {
76	if (std::is_class<T>::value) {
77	// Destroy the constructed elements in the vector.
78	destroy_range(Begin, End);
79	}
80	}
81
82	using size_type = size_t;
83	using difference_type = ptrdiff_t;
84	using value_type = T;
85	using iterator = T *;
86	using const_iterator = const T *;
87
88	using const_reverse_iterator = std::reverse_iterator<const_iterator>;
89	using reverse_iterator = std::reverse_iterator<iterator>;
90
91	using reference = T &;
92	using const_reference = const T &;
93	using pointer = T *;
94	using const_pointer = const T *;
95
96	// forward iterator creation methods.
97	iterator begin() { return Begin; }
98	const_iterator begin() const { return Begin; }
99	iterator end() { return End; }
100	const_iterator end() const { return End; }
101
102	// reverse iterator creation methods.
103	reverse_iterator rbegin() { return reverse_iterator(end()); }
104	const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
105	reverse_iterator rend() { return reverse_iterator(begin()); }
106	const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
107
108	bool empty() const { return Begin == End; }
109	size_type size() const { return End-Begin; }
110
111	reference operator[](unsigned idx) {
112	assert(Begin + idx < End);
113	return Begin[idx];
114	}
115	const_reference operator[](unsigned idx) const {
116	assert(Begin + idx < End);
117	return Begin[idx];
118	}
119
120	reference front() {
121	return begin()[0];
122	}
123	const_reference front() const {
124	return begin()[0];
125	}
126
127	reference back() {
128	return end()[-1];
129	}
130	const_reference back() const {
131	return end()[-1];
132	}
133
134	void pop_back() {
135	--End;
136	End->~T();
137	}
138
139	T pop_back_val() {
140	T Result = back();
141	pop_back();
142	return Result;
143	}
144
145	void clear() {
146	if (std::is_class<T>::value) {
147	destroy_range(Begin, End);
148	}
149	End = Begin;
150	}
151
152	/// data - Return a pointer to the vector's buffer, even if empty().
153	pointer data() {
154	return pointer(Begin);
155	}
156
157	/// data - Return a pointer to the vector's buffer, even if empty().
158	const_pointer data() const {
159	return const_pointer(Begin);
160	}
161
162	void push_back(const_reference Elt, const ASTContext &C) {
163	if (End < this->capacity_ptr()) {
164	Retry:
165	new (End) T(Elt);
166	++End;
167	return;
168	}
169	grow(C);
170	goto Retry;
171	}
172
173	void reserve(const ASTContext &C, unsigned N) {
174	if (unsigned(this->capacity_ptr()-Begin) < N)
175	grow(C, N);
176	}
177
178	/// capacity - Return the total number of elements in the currently allocated
179	/// buffer.
180	size_t capacity() const { return this->capacity_ptr() - Begin; }
181
182	/// append - Add the specified range to the end of the SmallVector.
183	template<typename in_iter>
184	void append(const ASTContext &C, in_iter in_start, in_iter in_end) {
185	size_type NumInputs = std::distance(in_start, in_end);
186
187	if (NumInputs == 0)
188	return;
189
190	// Grow allocated space if needed.
191	if (NumInputs > size_type(this->capacity_ptr()-this->end()))
192	this->grow(C, this->size()+NumInputs);
193
194	// Copy the new elements over.
195	// TODO: NEED To compile time dispatch on whether in_iter is a random access
196	// iterator to use the fast uninitialized_copy.
197	std::uninitialized_copy(in_start, in_end, this->end());
198	this->setEnd(this->end() + NumInputs);
199	}
200
201	/// append - Add the specified range to the end of the SmallVector.
202	void append(const ASTContext &C, size_type NumInputs, const T &Elt) {
203	// Grow allocated space if needed.
204	if (NumInputs > size_type(this->capacity_ptr()-this->end()))
205	this->grow(C, this->size()+NumInputs);
206
207	// Copy the new elements over.
208	std::uninitialized_fill_n(this->end(), NumInputs, Elt);
209	this->setEnd(this->end() + NumInputs);
210	}
211
212	/// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
213	/// starting with "Dest", constructing elements into it as needed.
214	template<typename It1, typename It2>
215	static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
216	std::uninitialized_copy(I, E, Dest);
217	}
218
219	iterator insert(const ASTContext &C, iterator I, const T &Elt) {
220	if (I == this->end()) { // Important special case for empty vector.
221	push_back(Elt, C);
222	return this->end()-1;
223	}
224
225	if (this->End < this->capacity_ptr()) {
226	Retry:
227	new (this->end()) T(this->back());
228	this->setEnd(this->end()+1);
229	// Push everything else over.
230	std::copy_backward(I, this->end()-1, this->end());
231	*I = Elt;
232	return I;
233	}
234	size_t EltNo = I-this->begin();
235	this->grow(C);
236	I = this->begin()+EltNo;
237	goto Retry;
238	}
239
240	iterator insert(const ASTContext &C, iterator I, size_type NumToInsert,
241	const T &Elt) {
242	// Convert iterator to elt# to avoid invalidating iterator when we reserve()
243	size_t InsertElt = I - this->begin();
244
245	if (I == this->end()) { // Important special case for empty vector.
246	append(C, NumToInsert, Elt);
247	return this->begin() + InsertElt;
248	}
249
250	// Ensure there is enough space.
251	reserve(C, static_cast<unsigned>(this->size() + NumToInsert));
252
253	// Uninvalidate the iterator.
254	I = this->begin()+InsertElt;
255
256	// If there are more elements between the insertion point and the end of the
257	// range than there are being inserted, we can use a simple approach to
258	// insertion. Since we already reserved space, we know that this won't
259	// reallocate the vector.
260	if (size_t(this->end()-I) >= NumToInsert) {
261	T *OldEnd = this->end();
262	append(C, this->end()-NumToInsert, this->end());
263
264	// Copy the existing elements that get replaced.
265	std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
266
267	std::fill_n(I, NumToInsert, Elt);
268	return I;
269	}
270
271	// Otherwise, we're inserting more elements than exist already, and we're
272	// not inserting at the end.
273
274	// Copy over the elements that we're about to overwrite.
275	T *OldEnd = this->end();
276	this->setEnd(this->end() + NumToInsert);
277	size_t NumOverwritten = OldEnd-I;
278	this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
279
280	// Replace the overwritten part.
281	std::fill_n(I, NumOverwritten, Elt);
282
283	// Insert the non-overwritten middle part.
284	std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
285	return I;
286	}
287
288	template<typename ItTy>
289	iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) {
290	// Convert iterator to elt# to avoid invalidating iterator when we reserve()
291	size_t InsertElt = I - this->begin();
292
293	if (I == this->end()) { // Important special case for empty vector.
294	append(C, From, To);
295	return this->begin() + InsertElt;
296	}
297
298	size_t NumToInsert = std::distance(From, To);
299
300	// Ensure there is enough space.
301	reserve(C, static_cast<unsigned>(this->size() + NumToInsert));
302
303	// Uninvalidate the iterator.
304	I = this->begin()+InsertElt;
305
306	// If there are more elements between the insertion point and the end of the
307	// range than there are being inserted, we can use a simple approach to
308	// insertion. Since we already reserved space, we know that this won't
309	// reallocate the vector.
310	if (size_t(this->end()-I) >= NumToInsert) {
311	T *OldEnd = this->end();
312	append(C, this->end()-NumToInsert, this->end());
313
314	// Copy the existing elements that get replaced.
315	std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
316
317	std::copy(From, To, I);
318	return I;
319	}
320
321	// Otherwise, we're inserting more elements than exist already, and we're
322	// not inserting at the end.
323
324	// Copy over the elements that we're about to overwrite.
325	T *OldEnd = this->end();
326	this->setEnd(this->end() + NumToInsert);
327	size_t NumOverwritten = OldEnd-I;
328	this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
329
330	// Replace the overwritten part.
331	for (; NumOverwritten > 0; --NumOverwritten) {
332	I = From;
333	++I; ++From;
334	}
335
336	// Insert the non-overwritten middle part.
337	this->uninitialized_copy(From, To, OldEnd);
338	return I;
339	}
340
341	void resize(const ASTContext &C, unsigned N, const T &NV) {
342	if (N < this->size()) {
343	this->destroy_range(this->begin()+N, this->end());
344	this->setEnd(this->begin()+N);
345	} else if (N > this->size()) {
346	if (this->capacity() < N)
347	this->grow(C, N);
348	construct_range(this->end(), this->begin()+N, NV);
349	this->setEnd(this->begin()+N);
350	}
351	}
352
353	private:
354	/// grow - double the size of the allocated memory, guaranteeing space for at
355	/// least one more element or MinSize if specified.
356	void grow(const ASTContext &C, size_type MinSize = 1);
357
358	void construct_range(T S, T E, const T &Elt) {
359	for (; S != E; ++S)
360	new (S) T(Elt);
361	}
362
363	void destroy_range(T S, T E) {
364	while (S != E) {
365	--E;
366	E->~T();
367	}
368	}
369
370	protected:
371	const_iterator capacity_ptr() const {
372	return (iterator) Capacity.getPointer();
373	}
374
375	iterator capacity_ptr() { return (iterator)Capacity.getPointer(); }
376	};
377
378	// Define this out-of-line to dissuade the C++ compiler from inlining it.
379	template <typename T>
380	void ASTVector<T>::grow(const ASTContext &C, size_t MinSize) {
381	size_t CurCapacity = this->capacity();
382	size_t CurSize = size();
383	size_t NewCapacity = 2*CurCapacity;
384	if (NewCapacity < MinSize)
385	NewCapacity = MinSize;
386
387	// Allocate the memory from the ASTContext.
388	T *NewElts = new (C, alignof(T)) T[NewCapacity];
389
390	// Copy the elements over.
391	if (Begin != End) {
392	if (std::is_class<T>::value) {
393	std::uninitialized_copy(Begin, End, NewElts);
394	// Destroy the original elements.
395	destroy_range(Begin, End);
396	} else {
397	// Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
398	memcpy(NewElts, Begin, CurSize * sizeof(T));
399	}
400	}
401
402	// ASTContext never frees any memory.
403	Begin = NewElts;
404	End = NewElts+CurSize;
405	Capacity.setPointer(Begin+NewCapacity);
406	}
407
408	} // namespace clang
409
410	#endif // LLVM_CLANG_AST_ASTVECTOR_H
411