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