BumpVector.h revision 288943
1196155Ssam//===-- BumpVector.h - Vector-like ADT that uses bump allocation --*- C++ -*-=// 2196155Ssam// 3196155Ssam// The LLVM Compiler Infrastructure 4196155Ssam// 5196155Ssam// This file is distributed under the University of Illinois Open Source 6196155Ssam// License. See LICENSE.TXT for details. 7196155Ssam// 8196155Ssam//===----------------------------------------------------------------------===// 9196155Ssam// 10196155Ssam// This file provides BumpVector, a vector-like ADT whose contents are 11196155Ssam// allocated from a BumpPtrAllocator. 12196155Ssam// 13196155Ssam//===----------------------------------------------------------------------===// 14196155Ssam 15196155Ssam// FIXME: Most of this is copy-and-paste from SmallVector.h. We can 16196155Ssam// refactor this core logic into something common that is shared between 17196155Ssam// the two. The main thing that is different is the allocation strategy. 18196155Ssam 19196155Ssam#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 20196155Ssam#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 21196155Ssam 22196155Ssam#include "llvm/ADT/PointerIntPair.h" 23196155Ssam#include "llvm/Support/Allocator.h" 24196155Ssam#include "llvm/Support/type_traits.h" 25196155Ssam#include <algorithm> 26196155Ssam#include <cstring> 27196155Ssam#include <iterator> 28205846Strasz#include <memory> 29196155Ssam 30196155Ssamnamespace clang { 31196155Ssam 32196155Ssamclass BumpVectorContext { 33196155Ssam llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 34196155Ssampublic: 35196155Ssam /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator 36196155Ssam /// and destroys it when the BumpVectorContext object is destroyed. 37196155Ssam BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} 38196155Ssam 39196155Ssam /// Construct a new BumpVectorContext that reuses an existing 40196155Ssam /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 41196155Ssam /// BumpVectorContext object is destroyed. 42196155Ssam BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 43196155Ssam 44196155Ssam ~BumpVectorContext() { 45196155Ssam if (Alloc.getInt()) 46196155Ssam delete Alloc.getPointer(); 47196155Ssam } 48196155Ssam 49196155Ssam llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 50196155Ssam}; 51196155Ssam 52196155Ssamtemplate<typename T> 53196155Ssamclass BumpVector { 54196155Ssam T *Begin, *End, *Capacity; 55196155Ssampublic: 56196155Ssam // Default ctor - Initialize to empty. 57196155Ssam explicit BumpVector(BumpVectorContext &C, unsigned N) 58196155Ssam : Begin(nullptr), End(nullptr), Capacity(nullptr) { 59196155Ssam reserve(C, N); 60196155Ssam } 61196155Ssam 62196155Ssam ~BumpVector() { 63196155Ssam if (std::is_class<T>::value) { 64196155Ssam // Destroy the constructed elements in the vector. 65196155Ssam destroy_range(Begin, End); 66196155Ssam } 67196155Ssam } 68196155Ssam 69196155Ssam typedef size_t size_type; 70196155Ssam typedef ptrdiff_t difference_type; 71196155Ssam typedef T value_type; 72196155Ssam typedef T* iterator; 73196155Ssam typedef const T* const_iterator; 74196155Ssam 75196155Ssam typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 76196155Ssam typedef std::reverse_iterator<iterator> reverse_iterator; 77196155Ssam 78196155Ssam typedef T& reference; 79196155Ssam typedef const T& const_reference; 80196155Ssam typedef T* pointer; 81196155Ssam typedef const T* const_pointer; 82196155Ssam 83196155Ssam // forward iterator creation methods. 84196155Ssam iterator begin() { return Begin; } 85196155Ssam const_iterator begin() const { return Begin; } 86196155Ssam iterator end() { return End; } 87196155Ssam const_iterator end() const { return End; } 88196155Ssam 89196155Ssam // reverse iterator creation methods. 90196155Ssam reverse_iterator rbegin() { return reverse_iterator(end()); } 91196155Ssam const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 92196155Ssam reverse_iterator rend() { return reverse_iterator(begin()); } 93196155Ssam const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 94196155Ssam 95196155Ssam bool empty() const { return Begin == End; } 96196155Ssam size_type size() const { return End-Begin; } 97196155Ssam 98196155Ssam reference operator[](unsigned idx) { 99196155Ssam assert(Begin + idx < End); 100196155Ssam return Begin[idx]; 101196155Ssam } 102196155Ssam const_reference operator[](unsigned idx) const { 103196155Ssam assert(Begin + idx < End); 104196155Ssam return Begin[idx]; 105196155Ssam } 106196155Ssam 107196155Ssam reference front() { 108196155Ssam return begin()[0]; 109196155Ssam } 110196155Ssam const_reference front() const { 111196155Ssam return begin()[0]; 112196155Ssam } 113196155Ssam 114196155Ssam reference back() { 115196155Ssam return end()[-1]; 116196155Ssam } 117196155Ssam const_reference back() const { 118196155Ssam return end()[-1]; 119196155Ssam } 120196155Ssam 121196155Ssam void pop_back() { 122196155Ssam --End; 123196155Ssam End->~T(); 124196155Ssam } 125196155Ssam 126196155Ssam T pop_back_val() { 127196155Ssam T Result = back(); 128196155Ssam pop_back(); 129196155Ssam return Result; 130196155Ssam } 131196155Ssam 132196155Ssam void clear() { 133196155Ssam if (std::is_class<T>::value) { 134196155Ssam destroy_range(Begin, End); 135196155Ssam } 136196155Ssam End = Begin; 137196155Ssam } 138196155Ssam 139196155Ssam /// data - Return a pointer to the vector's buffer, even if empty(). 140196155Ssam pointer data() { 141196155Ssam return pointer(Begin); 142196155Ssam } 143196155Ssam 144196155Ssam /// data - Return a pointer to the vector's buffer, even if empty(). 145196155Ssam const_pointer data() const { 146196155Ssam return const_pointer(Begin); 147196155Ssam } 148196155Ssam 149196155Ssam void push_back(const_reference Elt, BumpVectorContext &C) { 150196155Ssam if (End < Capacity) { 151196155Ssam Retry: 152196155Ssam new (End) T(Elt); 153196155Ssam ++End; 154196155Ssam return; 155196155Ssam } 156196155Ssam grow(C); 157196155Ssam goto Retry; 158196155Ssam } 159196155Ssam 160196155Ssam /// insert - Insert some number of copies of element into a position. Return 161196155Ssam /// iterator to position after last inserted copy. 162196155Ssam iterator insert(iterator I, size_t Cnt, const_reference E, 163196155Ssam BumpVectorContext &C) { 164196155Ssam assert (I >= Begin && I <= End && "Iterator out of bounds."); 165196155Ssam if (End + Cnt <= Capacity) { 166196155Ssam Retry: 167196155Ssam move_range_right(I, End, Cnt); 168196155Ssam construct_range(I, I + Cnt, E); 169196155Ssam End += Cnt; 170196155Ssam return I + Cnt; 171196155Ssam } 172196155Ssam ptrdiff_t D = I - Begin; 173196155Ssam grow(C, size() + Cnt); 174196155Ssam I = Begin + D; 175196155Ssam goto Retry; 176196155Ssam } 177196155Ssam 178196155Ssam void reserve(BumpVectorContext &C, unsigned N) { 179196155Ssam if (unsigned(Capacity-Begin) < N) 180204213Sbschmidt grow(C, N); 181204213Sbschmidt } 182196155Ssam 183196155Ssam /// capacity - Return the total number of elements in the currently allocated 184196155Ssam /// buffer. 185196155Ssam size_t capacity() const { return Capacity - Begin; } 186196155Ssam 187196155Ssamprivate: 188196155Ssam /// grow - double the size of the allocated memory, guaranteeing space for at 189196155Ssam /// least one more element or MinSize if specified. 190196155Ssam void grow(BumpVectorContext &C, size_type MinSize = 1); 191196155Ssam 192196155Ssam void construct_range(T *S, T *E, const T &Elt) { 193196155Ssam for (; S != E; ++S) 194196155Ssam new (S) T(Elt); 195196155Ssam } 196196155Ssam 197196155Ssam void destroy_range(T *S, T *E) { 198196155Ssam while (S != E) { 199196155Ssam --E; 200196155Ssam E->~T(); 201196155Ssam } 202196155Ssam } 203196155Ssam 204196155Ssam void move_range_right(T *S, T *E, size_t D) { 205196155Ssam for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { 206196155Ssam --E; 207196155Ssam new (I) T(*E); 208196155Ssam E->~T(); 209196155Ssam } 210196155Ssam } 211196155Ssam}; 212196155Ssam 213196155Ssam// Define this out-of-line to dissuade the C++ compiler from inlining it. 214196155Ssamtemplate <typename T> 215196155Ssamvoid BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 216196155Ssam size_t CurCapacity = Capacity-Begin; 217196155Ssam size_t CurSize = size(); 218196155Ssam size_t NewCapacity = 2*CurCapacity; 219196155Ssam if (NewCapacity < MinSize) 220196155Ssam NewCapacity = MinSize; 221196155Ssam 222196155Ssam // Allocate the memory from the BumpPtrAllocator. 223196155Ssam T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 224196155Ssam 225196155Ssam // Copy the elements over. 226196155Ssam if (Begin != End) { 227196155Ssam if (std::is_class<T>::value) { 228196155Ssam std::uninitialized_copy(Begin, End, NewElts); 229196155Ssam // Destroy the original elements. 230196155Ssam destroy_range(Begin, End); 231196155Ssam } else { 232196155Ssam // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 233196155Ssam memcpy(NewElts, Begin, CurSize * sizeof(T)); 234196155Ssam } 235196155Ssam } 236196155Ssam 237196155Ssam // For now, leak 'Begin'. We can add it back to a freelist in 238196155Ssam // BumpVectorContext. 239196155Ssam Begin = NewElts; 240196155Ssam End = NewElts+CurSize; 241196155Ssam Capacity = Begin+NewCapacity; 242196155Ssam} 243196155Ssam 244196155Ssam} // end: clang namespace 245196155Ssam#endif 246196155Ssam