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