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