BumpVector.h revision 204643
1261260Shselasky//===-- BumpVector.h - Vector-like ADT that uses bump allocation --*- C++ -*-=// 2261260Shselasky// 3261260Shselasky// The LLVM Compiler Infrastructure 4261260Shselasky// 5261260Shselasky// This file is distributed under the University of Illinois Open Source 6261260Shselasky// License. See LICENSE.TXT for details. 7261260Shselasky// 8261260Shselasky//===----------------------------------------------------------------------===// 9261260Shselasky// 10261260Shselasky// This file provides BumpVector, a vector-like ADT whose contents are 11261260Shselasky// allocated from a BumpPtrAllocator. 12261260Shselasky// 13261260Shselasky//===----------------------------------------------------------------------===// 14261260Shselasky 15261260Shselasky// FIXME: Most of this is copy-and-paste from SmallVector.h. We can 16261260Shselasky// refactor this core logic into something common that is shared between 17261260Shselasky// the two. The main thing that is different is the allocation strategy. 18261260Shselasky 19261260Shselasky#ifndef LLVM_CLANG_BUMP_VECTOR 20261260Shselasky#define LLVM_CLANG_BUMP_VECTOR 21261260Shselasky 22261260Shselasky#include "llvm/Support/type_traits.h" 23261260Shselasky#include "llvm/Support/Allocator.h" 24261260Shselasky#include "llvm/ADT/PointerIntPair.h" 25261260Shselasky#include <algorithm> 26261260Shselasky#include <cstring> 27261260Shselasky 28261260Shselaskynamespace clang { 29261260Shselasky 30261260Shselaskyclass BumpVectorContext { 31261260Shselasky llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 32261260Shselaskypublic: 33261260Shselasky /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator 34261260Shselasky /// and destroys it when the BumpVectorContext object is destroyed. 35261260Shselasky BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} 36261260Shselasky 37261260Shselasky /// Construct a new BumpVectorContext that reuses an existing 38261260Shselasky /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 39261260Shselasky /// BumpVectorContext object is destroyed. 40261260Shselasky BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 41261260Shselasky 42261260Shselasky ~BumpVectorContext() { 43261260Shselasky if (Alloc.getInt()) 44261260Shselasky delete Alloc.getPointer(); 45261260Shselasky } 46261260Shselasky 47261260Shselasky llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 48261260Shselasky}; 49261260Shselasky 50261260Shselaskytemplate<typename T> 51261260Shselaskyclass BumpVector { 52261260Shselasky T *Begin, *End, *Capacity; 53261260Shselaskypublic: 54261260Shselasky // Default ctor - Initialize to empty. 55261260Shselasky explicit BumpVector(BumpVectorContext &C, unsigned N) 56261260Shselasky : Begin(NULL), End(NULL), Capacity(NULL) { 57261260Shselasky reserve(C, N); 58262368Shselasky } 59261260Shselasky 60261260Shselasky ~BumpVector() { 61261260Shselasky if (llvm::is_class<T>::value) { 62261260Shselasky // Destroy the constructed elements in the vector. 63261260Shselasky destroy_range(Begin, End); 64261260Shselasky } 65261260Shselasky } 66261260Shselasky 67261260Shselasky typedef size_t size_type; 68261260Shselasky typedef ptrdiff_t difference_type; 69261260Shselasky typedef T value_type; 70261260Shselasky typedef T* iterator; 71261260Shselasky typedef const T* const_iterator; 72261260Shselasky 73261260Shselasky typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 74261260Shselasky typedef std::reverse_iterator<iterator> reverse_iterator; 75261260Shselasky 76261260Shselasky typedef T& reference; 77261260Shselasky typedef const T& const_reference; 78261260Shselasky typedef T* pointer; 79261260Shselasky typedef const T* const_pointer; 80261260Shselasky 81261260Shselasky // forward iterator creation methods. 82261260Shselasky iterator begin() { return Begin; } 83261260Shselasky const_iterator begin() const { return Begin; } 84261260Shselasky iterator end() { return End; } 85261260Shselasky const_iterator end() const { return End; } 86261260Shselasky 87261260Shselasky // reverse iterator creation methods. 88261260Shselasky reverse_iterator rbegin() { return reverse_iterator(end()); } 89261260Shselasky const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 90261260Shselasky reverse_iterator rend() { return reverse_iterator(begin()); } 91261260Shselasky const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 92261260Shselasky 93261260Shselasky bool empty() const { return Begin == End; } 94261260Shselasky size_type size() const { return End-Begin; } 95261260Shselasky 96261260Shselasky reference operator[](unsigned idx) { 97263071Shselasky assert(Begin + idx < End); 98263071Shselasky return Begin[idx]; 99261260Shselasky } 100261260Shselasky const_reference operator[](unsigned idx) const { 101261260Shselasky assert(Begin + idx < End); 102261260Shselasky return Begin[idx]; 103261260Shselasky } 104261260Shselasky 105261260Shselasky reference front() { 106261260Shselasky return begin()[0]; 107261260Shselasky } 108261260Shselasky const_reference front() const { 109261260Shselasky return begin()[0]; 110261260Shselasky } 111261260Shselasky 112261260Shselasky reference back() { 113261260Shselasky return end()[-1]; 114261260Shselasky } 115261260Shselasky const_reference back() const { 116261260Shselasky return end()[-1]; 117261260Shselasky } 118261260Shselasky 119261260Shselasky void pop_back() { 120261260Shselasky --End; 121261260Shselasky End->~T(); 122261260Shselasky } 123261260Shselasky 124261260Shselasky T pop_back_val() { 125261260Shselasky T Result = back(); 126261260Shselasky pop_back(); 127261510Shselasky return Result; 128262368Shselasky } 129262368Shselasky 130261510Shselasky void clear() { 131261510Shselasky if (llvm::is_class<T>::value) { 132261510Shselasky destroy_range(Begin, End); 133262368Shselasky } 134261510Shselasky End = Begin; 135261510Shselasky } 136261510Shselasky 137261510Shselasky /// data - Return a pointer to the vector's buffer, even if empty(). 138261510Shselasky pointer data() { 139261510Shselasky return pointer(Begin); 140261510Shselasky } 141261510Shselasky 142261510Shselasky /// data - Return a pointer to the vector's buffer, even if empty(). 143261510Shselasky const_pointer data() const { 144261510Shselasky return const_pointer(Begin); 145261510Shselasky } 146261260Shselasky 147261260Shselasky void push_back(const_reference Elt, BumpVectorContext &C) { 148261260Shselasky if (End < Capacity) { 149261260Shselasky Retry: 150261260Shselasky new (End) T(Elt); 151261260Shselasky ++End; 152261260Shselasky return; 153261260Shselasky } 154261260Shselasky grow(C); 155261260Shselasky goto Retry; 156261260Shselasky } 157261260Shselasky 158261260Shselasky void reserve(BumpVectorContext &C, unsigned N) { 159261260Shselasky if (unsigned(Capacity-Begin) < N) 160261260Shselasky grow(C, N); 161261260Shselasky } 162261260Shselasky 163261260Shselasky /// capacity - Return the total number of elements in the currently allocated 164261260Shselasky /// buffer. 165261260Shselasky size_t capacity() const { return Capacity - Begin; } 166261260Shselasky 167261260Shselaskyprivate: 168261260Shselasky /// grow - double the size of the allocated memory, guaranteeing space for at 169261260Shselasky /// least one more element or MinSize if specified. 170261260Shselasky void grow(BumpVectorContext &C, size_type MinSize = 1); 171261260Shselasky 172261260Shselasky void construct_range(T *S, T *E, const T &Elt) { 173261260Shselasky for (; S != E; ++S) 174261260Shselasky new (S) T(Elt); 175261260Shselasky } 176261260Shselasky 177261260Shselasky void destroy_range(T *S, T *E) { 178261260Shselasky while (S != E) { 179261260Shselasky --E; 180261260Shselasky E->~T(); 181261260Shselasky } 182261260Shselasky } 183261260Shselasky}; 184261260Shselasky 185261260Shselasky// Define this out-of-line to dissuade the C++ compiler from inlining it. 186261260Shselaskytemplate <typename T> 187261260Shselaskyvoid BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 188261260Shselasky size_t CurCapacity = Capacity-Begin; 189261260Shselasky size_t CurSize = size(); 190261260Shselasky size_t NewCapacity = 2*CurCapacity; 191261260Shselasky if (NewCapacity < MinSize) 192261260Shselasky NewCapacity = MinSize; 193261260Shselasky 194261260Shselasky // Allocate the memory from the BumpPtrAllocator. 195261260Shselasky T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 196261260Shselasky 197261260Shselasky // Copy the elements over. 198261260Shselasky if (llvm::is_class<T>::value) { 199261260Shselasky std::uninitialized_copy(Begin, End, NewElts); 200261260Shselasky // Destroy the original elements. 201261260Shselasky destroy_range(Begin, End); 202261260Shselasky } 203261260Shselasky else { 204261260Shselasky // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 205261260Shselasky memcpy(NewElts, Begin, CurSize * sizeof(T)); 206261260Shselasky } 207261260Shselasky 208261260Shselasky // For now, leak 'Begin'. We can add it back to a freelist in 209261260Shselasky // BumpVectorContext. 210262368Shselasky Begin = NewElts; 211262368Shselasky End = NewElts+CurSize; 212262368Shselasky Capacity = Begin+NewCapacity; 213261260Shselasky} 214261260Shselasky 215261260Shselasky} // end: clang namespace 216261260Shselasky#endif // end: LLVM_CLANG_BUMP_VECTOR 217261260Shselasky