clang  9.0.0svn
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.
100  reverse_iterator rend() { return reverse_iterator(begin()); }
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
reference operator[](unsigned idx)
Definition: BumpVector.h:108
iterator end()
Definition: BumpVector.h:94
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Definition: opencl-c.h:67
iterator begin()
Definition: BumpVector.h:92
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:29
reference back()
Definition: BumpVector.h:124
size_type size() const
Definition: BumpVector.h:106
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:55
reverse_iterator rbegin()
Definition: BumpVector.h:98
BumpVector(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:66
const_iterator begin() const
Definition: BumpVector.h:93
std::reverse_iterator< iterator > reverse_iterator
Definition: BumpVector.h:84
BumpVectorContext(BumpVectorContext &&Other)
Definition: BumpVector.h:40
bool empty() const
Definition: BumpVector.h:105
pointer data()
data - Return a pointer to the vector&#39;s buffer, even if empty().
Definition: BumpVector.h:150
const_reference back() const
Definition: BumpVector.h:127
const_iterator end() const
Definition: BumpVector.h:95
void reserve(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:188
reverse_iterator rend()
Definition: BumpVector.h:100
SourceLocation End
const_pointer data() const
data - Return a pointer to the vector&#39;s buffer, even if empty().
Definition: BumpVector.h:155
SourceLocation Begin
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: BumpVector.h:83
The result type of a method or function.
const_reference front() const
Definition: BumpVector.h:120
__DEVICE__ void * memcpy(void *__a, const void *__b, size_t __c)
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c.h:75
const_reference operator[](unsigned idx) const
Definition: BumpVector.h:112
void push_back(const_reference Elt, BumpVectorContext &C)
Definition: BumpVector.h:159
Dataflow Directional Tag Classes.
BumpVectorContext(llvm::BumpPtrAllocator &A)
Construct a new BumpVectorContext that reuses an existing BumpPtrAllocator.
Definition: BumpVector.h:48
reference front()
Definition: BumpVector.h:117
const_reverse_iterator rbegin() const
Definition: BumpVector.h:99
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
Represents a top-level expression in a basic block.
Definition: CFG.h:55
size_t capacity() const
capacity - Return the total number of elements in the currently allocated buffer. ...
Definition: BumpVector.h:195
const_reverse_iterator rend() const
Definition: BumpVector.h:101
BumpVectorContext()
Construct a new BumpVectorContext that creates a new BumpPtrAllocator and destroys it when the BumpVe...
Definition: BumpVector.h:38