clang  6.0.0svn
BumpVector.h
Go to the documentation of this file.
1 //===- BumpVector.h - Vector-like ADT that uses bump allocation -*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file provides BumpVector, a vector-like ADT whose contents are
11 // allocated from a BumpPtrAllocator.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 // FIXME: Most of this is copy-and-paste from SmallVector.h. We can
16 // refactor this core logic into something common that is shared between
17 // the two. The main thing that is different is the allocation strategy.
18 
19 #ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
20 #define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
21 
22 #include "llvm/ADT/PointerIntPair.h"
23 #include "llvm/Support/Allocator.h"
24 #include <cassert>
25 #include <cstddef>
26 #include <cstring>
27 #include <iterator>
28 #include <memory>
29 #include <type_traits>
30 
31 namespace clang {
32 
34  llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
35 
36 public:
37  /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator
38  /// and destroys it when the BumpVectorContext object is destroyed.
39  BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {}
40 
41  BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) {
42  Other.Alloc.setInt(false);
43  Other.Alloc.setPointer(nullptr);
44  }
45 
46  /// Construct a new BumpVectorContext that reuses an existing
47  /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the
48  /// BumpVectorContext object is destroyed.
49  BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {}
50 
52  if (Alloc.getInt())
53  delete Alloc.getPointer();
54  }
55 
56  llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
57 };
58 
59 template<typename T>
60 class BumpVector {
61  T *Begin = nullptr;
62  T *End = nullptr;
63  T *Capacity = nullptr;
64 
65 public:
66  // Default ctor - Initialize to empty.
67  explicit BumpVector(BumpVectorContext &C, unsigned N) {
68  reserve(C, N);
69  }
70 
72  if (std::is_class<T>::value) {
73  // Destroy the constructed elements in the vector.
74  destroy_range(Begin, End);
75  }
76  }
77 
78  using size_type = size_t;
80  using value_type = T;
81  using iterator = T *;
82  using const_iterator = const T *;
83 
84  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
85  using reverse_iterator = std::reverse_iterator<iterator>;
86 
87  using reference = T &;
88  using const_reference = const T &;
89  using pointer = T *;
90  using const_pointer = const T *;
91 
92  // forward iterator creation methods.
93  iterator begin() { return Begin; }
94  const_iterator begin() const { return Begin; }
95  iterator end() { return End; }
96  const_iterator end() const { return End; }
97 
98  // reverse iterator creation methods.
101  reverse_iterator rend() { return reverse_iterator(begin()); }
103  return const_reverse_iterator(begin());
104  }
105 
106  bool empty() const { return Begin == End; }
107  size_type size() const { return End-Begin; }
108 
109  reference operator[](unsigned idx) {
110  assert(Begin + idx < End);
111  return Begin[idx];
112  }
113  const_reference operator[](unsigned idx) const {
114  assert(Begin + idx < End);
115  return Begin[idx];
116  }
117 
119  return begin()[0];
120  }
122  return begin()[0];
123  }
124 
126  return end()[-1];
127  }
129  return end()[-1];
130  }
131 
132  void pop_back() {
133  --End;
134  End->~T();
135  }
136 
138  T Result = back();
139  pop_back();
140  return Result;
141  }
142 
143  void clear() {
144  if (std::is_class<T>::value) {
145  destroy_range(Begin, End);
146  }
147  End = Begin;
148  }
149 
150  /// data - Return a pointer to the vector's buffer, even if empty().
152  return pointer(Begin);
153  }
154 
155  /// data - Return a pointer to the vector's buffer, even if empty().
156  const_pointer data() const {
157  return const_pointer(Begin);
158  }
159 
161  if (End < Capacity) {
162  Retry:
163  new (End) T(Elt);
164  ++End;
165  return;
166  }
167  grow(C);
168  goto Retry;
169  }
170 
171  /// insert - Insert some number of copies of element into a position. Return
172  /// iterator to position after last inserted copy.
174  BumpVectorContext &C) {
175  assert(I >= Begin && I <= End && "Iterator out of bounds.");
176  if (End + Cnt <= Capacity) {
177  Retry:
178  move_range_right(I, End, Cnt);
179  construct_range(I, I + Cnt, E);
180  End += Cnt;
181  return I + Cnt;
182  }
183  ptrdiff_t D = I - Begin;
184  grow(C, size() + Cnt);
185  I = Begin + D;
186  goto Retry;
187  }
188 
189  void reserve(BumpVectorContext &C, unsigned N) {
190  if (unsigned(Capacity-Begin) < N)
191  grow(C, N);
192  }
193 
194  /// capacity - Return the total number of elements in the currently allocated
195  /// buffer.
196  size_t capacity() const { return Capacity - Begin; }
197 
198 private:
199  /// grow - double the size of the allocated memory, guaranteeing space for at
200  /// least one more element or MinSize if specified.
201  void grow(BumpVectorContext &C, size_type MinSize = 1);
202 
203  void construct_range(T *S, T *E, const T &Elt) {
204  for (; S != E; ++S)
205  new (S) T(Elt);
206  }
207 
208  void destroy_range(T *S, T *E) {
209  while (S != E) {
210  --E;
211  E->~T();
212  }
213  }
214 
215  void move_range_right(T *S, T *E, size_t D) {
216  for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) {
217  --E;
218  new (I) T(*E);
219  E->~T();
220  }
221  }
222 };
223 
224 // Define this out-of-line to dissuade the C++ compiler from inlining it.
225 template <typename T>
226 void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) {
227  size_t CurCapacity = Capacity-Begin;
228  size_t CurSize = size();
229  size_t NewCapacity = 2*CurCapacity;
230  if (NewCapacity < MinSize)
231  NewCapacity = MinSize;
232 
233  // Allocate the memory from the BumpPtrAllocator.
234  T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
235 
236  // Copy the elements over.
237  if (Begin != End) {
238  if (std::is_class<T>::value) {
239  std::uninitialized_copy(Begin, End, NewElts);
240  // Destroy the original elements.
241  destroy_range(Begin, End);
242  } else {
243  // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
244  memcpy(NewElts, Begin, CurSize * sizeof(T));
245  }
246  }
247 
248  // For now, leak 'Begin'. We can add it back to a freelist in
249  // BumpVectorContext.
250  Begin = NewElts;
251  End = NewElts+CurSize;
252  Capacity = Begin+NewCapacity;
253 }
254 
255 } // namespace clang
256 
257 #endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H
reference operator[](unsigned idx)
Definition: BumpVector.h:109
iterator end()
Definition: BumpVector.h:95
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Definition: opencl-c.h:60
iterator begin()
Definition: BumpVector.h:93
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
reference back()
Definition: BumpVector.h:125
size_type size() const
Definition: BumpVector.h:107
llvm::BumpPtrAllocator & getAllocator()
Definition: BumpVector.h:56
reverse_iterator rbegin()
Definition: BumpVector.h:99
BumpVector(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:67
const_iterator begin() const
Definition: BumpVector.h:94
std::reverse_iterator< iterator > reverse_iterator
Definition: BumpVector.h:85
BumpVectorContext(BumpVectorContext &&Other)
Definition: BumpVector.h:41
bool empty() const
Definition: BumpVector.h:106
pointer data()
data - Return a pointer to the vector&#39;s buffer, even if empty().
Definition: BumpVector.h:151
const_reference back() const
Definition: BumpVector.h:128
const_iterator end() const
Definition: BumpVector.h:96
void reserve(BumpVectorContext &C, unsigned N)
Definition: BumpVector.h:189
reverse_iterator rend()
Definition: BumpVector.h:101
SourceLocation End
const FunctionProtoType * T
const_pointer data() const
data - Return a pointer to the vector&#39;s buffer, even if empty().
Definition: BumpVector.h:156
SourceLocation Begin
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: BumpVector.h:84
The result type of a method or function.
const_reference front() const
Definition: BumpVector.h:121
__PTRDIFF_TYPE__ ptrdiff_t
A signed integer type that is the result of subtracting two pointers.
Definition: opencl-c.h:68
const_reference operator[](unsigned idx) const
Definition: BumpVector.h:113
void push_back(const_reference Elt, BumpVectorContext &C)
Definition: BumpVector.h:160
Dataflow Directional Tag Classes.
BumpVectorContext(llvm::BumpPtrAllocator &A)
Construct a new BumpVectorContext that reuses an existing BumpPtrAllocator.
Definition: BumpVector.h:49
reference front()
Definition: BumpVector.h:118
const_reverse_iterator rbegin() const
Definition: BumpVector.h:100
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:173
CFGElement - Represents a top-level expression in a basic block.
Definition: CFG.h:54
size_t capacity() const
capacity - Return the total number of elements in the currently allocated buffer. ...
Definition: BumpVector.h:196
const_reverse_iterator rend() const
Definition: BumpVector.h:102
BumpVectorContext()
Construct a new BumpVectorContext that creates a new BumpPtrAllocator and destroys it when the BumpVe...
Definition: BumpVector.h:39