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 
30 namespace clang {
31 
32 class BumpVectorContext {
33   llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
34 
35 public:
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 
58 template<typename T>
59 class BumpVector {
60   T *Begin = nullptr;
61   T *End = nullptr;
62   T *Capacity = nullptr;
63 
64 public:
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 
197 private:
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.
224 template <typename T>
225 void 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