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