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