1 //===-- BumpVector.h - Vector-like ADT that uses bump allocation --*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides BumpVector, a vector-like ADT whose contents are
11 // allocated from a BumpPtrAllocator.
13 //===----------------------------------------------------------------------===//
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.
19 #ifndef LLVM_CLANG_BUMP_VECTOR
20 #define LLVM_CLANG_BUMP_VECTOR
22 #include "llvm/ADT/PointerIntPair.h"
23 #include "llvm/Support/Allocator.h"
24 #include "llvm/Support/type_traits.h"
32 class BumpVectorContext {
33 llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc;
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) {}
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) {}
44 ~BumpVectorContext() {
46 delete Alloc.getPointer();
49 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); }
54 T *Begin, *End, *Capacity;
56 // Default ctor - Initialize to empty.
57 explicit BumpVector(BumpVectorContext &C, unsigned N)
58 : Begin(NULL), End(NULL), Capacity(NULL) {
63 if (llvm::is_class<T>::value) {
64 // Destroy the constructed elements in the vector.
65 destroy_range(Begin, End);
69 typedef size_t size_type;
70 typedef ptrdiff_t difference_type;
73 typedef const T* const_iterator;
75 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
76 typedef std::reverse_iterator<iterator> reverse_iterator;
79 typedef const T& const_reference;
81 typedef const T* const_pointer;
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; }
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());}
95 bool empty() const { return Begin == End; }
96 size_type size() const { return End-Begin; }
98 reference operator[](unsigned idx) {
99 assert(Begin + idx < End);
102 const_reference operator[](unsigned idx) const {
103 assert(Begin + idx < End);
110 const_reference front() const {
117 const_reference back() const {
133 if (llvm::is_class<T>::value) {
134 destroy_range(Begin, End);
139 /// data - Return a pointer to the vector's buffer, even if empty().
141 return pointer(Begin);
144 /// data - Return a pointer to the vector's buffer, even if empty().
145 const_pointer data() const {
146 return const_pointer(Begin);
149 void push_back(const_reference Elt, BumpVectorContext &C) {
150 if (End < Capacity) {
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) {
167 move_range_right(I, End, Cnt);
168 construct_range(I, I + Cnt, E);
172 ptrdiff_t D = I - Begin;
173 grow(C, size() + Cnt);
178 void reserve(BumpVectorContext &C, unsigned N) {
179 if (unsigned(Capacity-Begin) < N)
183 /// capacity - Return the total number of elements in the currently allocated
185 size_t capacity() const { return Capacity - Begin; }
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);
192 void construct_range(T *S, T *E, const T &Elt) {
197 void destroy_range(T *S, T *E) {
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) {
213 // Define this out-of-line to dissuade the C++ compiler from inlining it.
214 template <typename T>
215 void 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;
222 // Allocate the memory from the BumpPtrAllocator.
223 T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity);
225 // Copy the elements over.
226 if (llvm::is_class<T>::value) {
227 std::uninitialized_copy(Begin, End, NewElts);
228 // Destroy the original elements.
229 destroy_range(Begin, End);
232 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
233 memcpy(NewElts, Begin, CurSize * sizeof(T));
236 // For now, leak 'Begin'. We can add it back to a freelist in
237 // BumpVectorContext.
239 End = NewElts+CurSize;
240 Capacity = Begin+NewCapacity;
243 } // end: clang namespace
244 #endif // end: LLVM_CLANG_BUMP_VECTOR