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