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
30namespace clang {
31
32class BumpVectorContext {
33  llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
34
35public:
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
50  ~BumpVectorContext() {
51    if (Alloc.getInt())
52      delete Alloc.getPointer();
53  }
54
55  llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
56};
57
58template<typename T>
59class BumpVector {
60  T *Begin = nullptr;
61  T *End = nullptr;
62  T *Capacity = nullptr;
63
64public:
65  // Default ctor - Initialize to empty.
66  explicit BumpVector(BumpVectorContext &C, unsigned N) {
67    reserve(C, N);
68  }
69
70  ~BumpVector() {
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;
78  using difference_type = ptrdiff_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.
98  reverse_iterator rbegin() { return reverse_iterator(end()); }
99  const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
100  reverse_iterator rend() { return reverse_iterator(begin()); }
101  const_reverse_iterator rend() const {
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
117  reference front() {
118    return begin()[0];
119  }
120  const_reference front() const {
121    return begin()[0];
122  }
123
124  reference back() {
125    return end()[-1];
126  }
127  const_reference back() const {
128    return end()[-1];
129  }
130
131  void pop_back() {
132    --End;
133    End->~T();
134  }
135
136  T pop_back_val() {
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().
150  pointer data() {
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
159  void push_back(const_reference Elt, BumpVectorContext &C) {
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.
172  iterator insert(iterator I, size_t Cnt, const_reference E,
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
197private:
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.
224template <typename T>
225void 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
257