clang  14.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 
30 namespace clang {
31 
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 
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 
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;
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.
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 
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().
155  const_pointer data() const {
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.
173  BumpVectorContext &C) {
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 
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
llvm
Definition: Dominators.h:30
clang::BumpVector< CFGElement >::difference_type
ptrdiff_t difference_type
Definition: BumpVector.h:78
clang::BumpVector::clear
void clear()
Definition: BumpVector.h:142
clang::BumpVectorContext::BumpVectorContext
BumpVectorContext(llvm::BumpPtrAllocator &A)
Construct a new BumpVectorContext that reuses an existing BumpPtrAllocator.
Definition: BumpVector.h:48
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
clang::BumpVector::rbegin
const_reverse_iterator rbegin() const
Definition: BumpVector.h:99
memcpy
__DEVICE__ void * memcpy(void *__a, const void *__b, size_t __c)
Definition: __clang_cuda_device_functions.h:1549
clang::BumpVector::reserve
void reserve(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:188
End
SourceLocation End
Definition: USRLocFinder.cpp:167
clang::BumpVector::operator[]
reference operator[](unsigned idx)
Definition: BumpVector.h:108
clang::BumpVector< CFGElement >::reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
Definition: BumpVector.h:84
clang::BumpVector::data
const_pointer data() const
data - Return a pointer to the vector's buffer, even if empty().
Definition: BumpVector.h:155
clang::BumpVector::const_pointer
const T * const_pointer
Definition: BumpVector.h:89
clang::BumpVector::end
iterator end()
Definition: BumpVector.h:94
clang::BumpVector::pop_back_val
T pop_back_val()
Definition: BumpVector.h:136
clang::BumpVector::rend
const_reverse_iterator rend() const
Definition: BumpVector.h:101
size_t
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Definition: opencl-c-base.h:102
clang::BumpVector::capacity
size_t capacity() const
capacity - Return the total number of elements in the currently allocated buffer.
Definition: BumpVector.h:195
clang::BumpVector::pointer
T * pointer
Definition: BumpVector.h:88
clang::BumpVector::rbegin
reverse_iterator rbegin()
Definition: BumpVector.h:98
clang::BumpVector::pop_back
void pop_back()
Definition: BumpVector.h:131
clang::BumpVector::back
reference back()
Definition: BumpVector.h:124
clang::BumpVector::rend
reverse_iterator rend()
Definition: BumpVector.h:100
clang::BumpVector::empty
bool empty() const
Definition: BumpVector.h:105
clang::BumpVector::back
const_reference back() const
Definition: BumpVector.h:127
clang::BumpVector::~BumpVector
~BumpVector()
Definition: BumpVector.h:70
clang::BumpVector::begin
iterator begin()
Definition: BumpVector.h:92
clang::BumpVector::front
reference front()
Definition: BumpVector.h:117
clang::BumpVectorContext::BumpVectorContext
BumpVectorContext(BumpVectorContext &&Other)
Definition: BumpVector.h:40
clang::BumpVector::insert
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
clang::BumpVector< CFGElement >::const_reverse_iterator
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: BumpVector.h:83
clang::BumpVector::data
pointer data()
data - Return a pointer to the vector's buffer, even if empty().
Definition: BumpVector.h:150
clang::BumpVectorContext::BumpVectorContext
BumpVectorContext()
Construct a new BumpVectorContext that creates a new BumpPtrAllocator and destroys it when the BumpVe...
Definition: BumpVector.h:38
Begin
SourceLocation Begin
Definition: USRLocFinder.cpp:165
clang::BumpVectorContext::getAllocator
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:55
clang::CFGElement
Represents a top-level expression in a basic block.
Definition: CFG.h:55
clang::BumpVector::end
const_iterator end() const
Definition: BumpVector.h:95
clang::BumpVectorContext::~BumpVectorContext
~BumpVectorContext()
Definition: BumpVector.h:50
clang
Definition: CalledOnceCheck.h:17
ptrdiff_t
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c-base.h:110
clang::BumpVector::BumpVector
BumpVector(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:66
clang::BumpVector::operator[]
const_reference operator[](unsigned idx) const
Definition: BumpVector.h:112
clang::BumpVector::size
size_type size() const
Definition: BumpVector.h:106
clang::BumpVectorContext
Definition: BumpVector.h:32
clang::BumpVector< CFGElement >::size_type
size_t size_type
Definition: BumpVector.h:77
clang::BumpVector::push_back
void push_back(const_reference Elt, BumpVectorContext &C)
Definition: BumpVector.h:159
clang::BumpVector
Definition: BumpVector.h:59
clang::BumpVector::begin
const_iterator begin() const
Definition: BumpVector.h:93
clang::BumpVector::front
const_reference front() const
Definition: BumpVector.h:120