BumpVector.h revision 327952
1327952Sdim//===- BumpVector.h - Vector-like ADT that uses bump allocation -*- C++ -*-===// 2198092Srdivacky// 3198092Srdivacky// The LLVM Compiler Infrastructure 4198092Srdivacky// 5198092Srdivacky// This file is distributed under the University of Illinois Open Source 6198092Srdivacky// License. See LICENSE.TXT for details. 7198092Srdivacky// 8198092Srdivacky//===----------------------------------------------------------------------===// 9198092Srdivacky// 10198092Srdivacky// This file provides BumpVector, a vector-like ADT whose contents are 11198092Srdivacky// allocated from a BumpPtrAllocator. 12198092Srdivacky// 13198092Srdivacky//===----------------------------------------------------------------------===// 14198092Srdivacky 15198092Srdivacky// FIXME: Most of this is copy-and-paste from SmallVector.h. We can 16198092Srdivacky// refactor this core logic into something common that is shared between 17198092Srdivacky// the two. The main thing that is different is the allocation strategy. 18198092Srdivacky 19280031Sdim#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 20280031Sdim#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 21198092Srdivacky 22249423Sdim#include "llvm/ADT/PointerIntPair.h" 23249423Sdim#include "llvm/Support/Allocator.h" 24327952Sdim#include <cassert> 25327952Sdim#include <cstddef> 26204643Srdivacky#include <cstring> 27218893Sdim#include <iterator> 28210299Sed#include <memory> 29327952Sdim#include <type_traits> 30198092Srdivacky 31198092Srdivackynamespace clang { 32198092Srdivacky 33198092Srdivackyclass BumpVectorContext { 34198398Srdivacky llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 35327952Sdim 36198092Srdivackypublic: 37198092Srdivacky /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator 38198092Srdivacky /// and destroys it when the BumpVectorContext object is destroyed. 39198398Srdivacky BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} 40296417Sdim 41296417Sdim BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) { 42296417Sdim Other.Alloc.setInt(false); 43296417Sdim Other.Alloc.setPointer(nullptr); 44296417Sdim } 45296417Sdim 46198092Srdivacky /// Construct a new BumpVectorContext that reuses an existing 47198092Srdivacky /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 48198092Srdivacky /// BumpVectorContext object is destroyed. 49198398Srdivacky BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 50198092Srdivacky 51198092Srdivacky ~BumpVectorContext() { 52198092Srdivacky if (Alloc.getInt()) 53198092Srdivacky delete Alloc.getPointer(); 54198092Srdivacky } 55198092Srdivacky 56198092Srdivacky llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 57198092Srdivacky}; 58198092Srdivacky 59198092Srdivackytemplate<typename T> 60198092Srdivackyclass BumpVector { 61327952Sdim T *Begin = nullptr; 62327952Sdim T *End = nullptr; 63327952Sdim T *Capacity = nullptr; 64327952Sdim 65198092Srdivackypublic: 66198092Srdivacky // Default ctor - Initialize to empty. 67327952Sdim explicit BumpVector(BumpVectorContext &C, unsigned N) { 68198092Srdivacky reserve(C, N); 69198092Srdivacky } 70198092Srdivacky 71198092Srdivacky ~BumpVector() { 72276479Sdim if (std::is_class<T>::value) { 73198092Srdivacky // Destroy the constructed elements in the vector. 74198092Srdivacky destroy_range(Begin, End); 75198092Srdivacky } 76198092Srdivacky } 77198092Srdivacky 78327952Sdim using size_type = size_t; 79327952Sdim using difference_type = ptrdiff_t; 80327952Sdim using value_type = T; 81327952Sdim using iterator = T *; 82327952Sdim using const_iterator = const T *; 83198092Srdivacky 84327952Sdim using const_reverse_iterator = std::reverse_iterator<const_iterator>; 85327952Sdim using reverse_iterator = std::reverse_iterator<iterator>; 86198092Srdivacky 87327952Sdim using reference = T &; 88327952Sdim using const_reference = const T &; 89327952Sdim using pointer = T *; 90327952Sdim using const_pointer = const T *; 91198092Srdivacky 92198092Srdivacky // forward iterator creation methods. 93198092Srdivacky iterator begin() { return Begin; } 94198092Srdivacky const_iterator begin() const { return Begin; } 95198092Srdivacky iterator end() { return End; } 96198092Srdivacky const_iterator end() const { return End; } 97198092Srdivacky 98198092Srdivacky // reverse iterator creation methods. 99327952Sdim reverse_iterator rbegin() { return reverse_iterator(end()); } 100198092Srdivacky const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 101327952Sdim reverse_iterator rend() { return reverse_iterator(begin()); } 102327952Sdim const_reverse_iterator rend() const { 103327952Sdim return const_reverse_iterator(begin()); 104327952Sdim } 105198092Srdivacky 106198092Srdivacky bool empty() const { return Begin == End; } 107198092Srdivacky size_type size() const { return End-Begin; } 108198092Srdivacky 109198092Srdivacky reference operator[](unsigned idx) { 110198092Srdivacky assert(Begin + idx < End); 111198092Srdivacky return Begin[idx]; 112198092Srdivacky } 113198092Srdivacky const_reference operator[](unsigned idx) const { 114198092Srdivacky assert(Begin + idx < End); 115198092Srdivacky return Begin[idx]; 116198092Srdivacky } 117198092Srdivacky 118198092Srdivacky reference front() { 119198092Srdivacky return begin()[0]; 120198092Srdivacky } 121198092Srdivacky const_reference front() const { 122198092Srdivacky return begin()[0]; 123198092Srdivacky } 124198092Srdivacky 125198092Srdivacky reference back() { 126198092Srdivacky return end()[-1]; 127198092Srdivacky } 128198092Srdivacky const_reference back() const { 129198092Srdivacky return end()[-1]; 130198092Srdivacky } 131198092Srdivacky 132198092Srdivacky void pop_back() { 133198092Srdivacky --End; 134198092Srdivacky End->~T(); 135198092Srdivacky } 136198092Srdivacky 137198092Srdivacky T pop_back_val() { 138198092Srdivacky T Result = back(); 139198092Srdivacky pop_back(); 140198092Srdivacky return Result; 141198092Srdivacky } 142198092Srdivacky 143198092Srdivacky void clear() { 144276479Sdim if (std::is_class<T>::value) { 145198092Srdivacky destroy_range(Begin, End); 146198092Srdivacky } 147198092Srdivacky End = Begin; 148198092Srdivacky } 149198092Srdivacky 150198092Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 151198092Srdivacky pointer data() { 152198092Srdivacky return pointer(Begin); 153198092Srdivacky } 154198092Srdivacky 155198092Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 156198092Srdivacky const_pointer data() const { 157198092Srdivacky return const_pointer(Begin); 158198092Srdivacky } 159198092Srdivacky 160198092Srdivacky void push_back(const_reference Elt, BumpVectorContext &C) { 161198092Srdivacky if (End < Capacity) { 162198092Srdivacky Retry: 163198092Srdivacky new (End) T(Elt); 164198092Srdivacky ++End; 165198092Srdivacky return; 166198092Srdivacky } 167198092Srdivacky grow(C); 168198092Srdivacky goto Retry; 169198092Srdivacky } 170218893Sdim 171218893Sdim /// insert - Insert some number of copies of element into a position. Return 172218893Sdim /// iterator to position after last inserted copy. 173218893Sdim iterator insert(iterator I, size_t Cnt, const_reference E, 174218893Sdim BumpVectorContext &C) { 175327952Sdim assert(I >= Begin && I <= End && "Iterator out of bounds."); 176218893Sdim if (End + Cnt <= Capacity) { 177218893Sdim Retry: 178218893Sdim move_range_right(I, End, Cnt); 179218893Sdim construct_range(I, I + Cnt, E); 180218893Sdim End += Cnt; 181218893Sdim return I + Cnt; 182218893Sdim } 183218893Sdim ptrdiff_t D = I - Begin; 184218893Sdim grow(C, size() + Cnt); 185218893Sdim I = Begin + D; 186218893Sdim goto Retry; 187218893Sdim } 188218893Sdim 189198092Srdivacky void reserve(BumpVectorContext &C, unsigned N) { 190198092Srdivacky if (unsigned(Capacity-Begin) < N) 191198092Srdivacky grow(C, N); 192198092Srdivacky } 193198092Srdivacky 194198092Srdivacky /// capacity - Return the total number of elements in the currently allocated 195198092Srdivacky /// buffer. 196198092Srdivacky size_t capacity() const { return Capacity - Begin; } 197198092Srdivacky 198198092Srdivackyprivate: 199198092Srdivacky /// grow - double the size of the allocated memory, guaranteeing space for at 200198092Srdivacky /// least one more element or MinSize if specified. 201200583Srdivacky void grow(BumpVectorContext &C, size_type MinSize = 1); 202198092Srdivacky 203198092Srdivacky void construct_range(T *S, T *E, const T &Elt) { 204198092Srdivacky for (; S != E; ++S) 205198092Srdivacky new (S) T(Elt); 206198092Srdivacky } 207198092Srdivacky 208198092Srdivacky void destroy_range(T *S, T *E) { 209198092Srdivacky while (S != E) { 210198092Srdivacky --E; 211198092Srdivacky E->~T(); 212198092Srdivacky } 213198092Srdivacky } 214218893Sdim 215218893Sdim void move_range_right(T *S, T *E, size_t D) { 216218893Sdim for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { 217218893Sdim --E; 218218893Sdim new (I) T(*E); 219218893Sdim E->~T(); 220218893Sdim } 221218893Sdim } 222198092Srdivacky}; 223198092Srdivacky 224198092Srdivacky// Define this out-of-line to dissuade the C++ compiler from inlining it. 225198092Srdivackytemplate <typename T> 226198092Srdivackyvoid BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 227198092Srdivacky size_t CurCapacity = Capacity-Begin; 228198092Srdivacky size_t CurSize = size(); 229198092Srdivacky size_t NewCapacity = 2*CurCapacity; 230198092Srdivacky if (NewCapacity < MinSize) 231198092Srdivacky NewCapacity = MinSize; 232198092Srdivacky 233198092Srdivacky // Allocate the memory from the BumpPtrAllocator. 234198092Srdivacky T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 235198092Srdivacky 236198092Srdivacky // Copy the elements over. 237288943Sdim if (Begin != End) { 238288943Sdim if (std::is_class<T>::value) { 239288943Sdim std::uninitialized_copy(Begin, End, NewElts); 240288943Sdim // Destroy the original elements. 241288943Sdim destroy_range(Begin, End); 242288943Sdim } else { 243288943Sdim // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 244288943Sdim memcpy(NewElts, Begin, CurSize * sizeof(T)); 245288943Sdim } 246198092Srdivacky } 247198092Srdivacky 248198092Srdivacky // For now, leak 'Begin'. We can add it back to a freelist in 249198092Srdivacky // BumpVectorContext. 250198092Srdivacky Begin = NewElts; 251198092Srdivacky End = NewElts+CurSize; 252198092Srdivacky Capacity = Begin+NewCapacity; 253198092Srdivacky} 254198092Srdivacky 255327952Sdim} // namespace clang 256327952Sdim 257327952Sdim#endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 258