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
30namespace clang {
31
32class BumpVectorContext {
33  llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
34public:
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
49  ~BumpVectorContext() {
50    if (Alloc.getInt())
51      delete Alloc.getPointer();
52  }
53
54  llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
55};
56
57template<typename T>
58class BumpVector {
59  T *Begin, *End, *Capacity;
60public:
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
67  ~BumpVector() {
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;
75  typedef ptrdiff_t difference_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
131  T pop_back_val() {
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
192private:
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.
219template <typename T>
220void 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
251