1327952Sdim//===- BumpVector.h - Vector-like ADT that uses bump allocation -*- C++ -*-===// 2198092Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6198092Srdivacky// 7198092Srdivacky//===----------------------------------------------------------------------===// 8198092Srdivacky// 9198092Srdivacky// This file provides BumpVector, a vector-like ADT whose contents are 10198092Srdivacky// allocated from a BumpPtrAllocator. 11198092Srdivacky// 12198092Srdivacky//===----------------------------------------------------------------------===// 13198092Srdivacky 14198092Srdivacky// FIXME: Most of this is copy-and-paste from SmallVector.h. We can 15198092Srdivacky// refactor this core logic into something common that is shared between 16198092Srdivacky// the two. The main thing that is different is the allocation strategy. 17198092Srdivacky 18280031Sdim#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 19280031Sdim#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 20198092Srdivacky 21249423Sdim#include "llvm/ADT/PointerIntPair.h" 22249423Sdim#include "llvm/Support/Allocator.h" 23327952Sdim#include <cassert> 24327952Sdim#include <cstddef> 25204643Srdivacky#include <cstring> 26218893Sdim#include <iterator> 27210299Sed#include <memory> 28327952Sdim#include <type_traits> 29198092Srdivacky 30198092Srdivackynamespace clang { 31341825Sdim 32198092Srdivackyclass BumpVectorContext { 33198398Srdivacky llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 34327952Sdim 35198092Srdivackypublic: 36198092Srdivacky /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator 37198092Srdivacky /// and destroys it when the BumpVectorContext object is destroyed. 38198398Srdivacky BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} 39296417Sdim 40296417Sdim BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) { 41296417Sdim Other.Alloc.setInt(false); 42296417Sdim Other.Alloc.setPointer(nullptr); 43296417Sdim } 44296417Sdim 45198092Srdivacky /// Construct a new BumpVectorContext that reuses an existing 46198092Srdivacky /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 47198092Srdivacky /// BumpVectorContext object is destroyed. 48198398Srdivacky BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 49341825Sdim 50198092Srdivacky ~BumpVectorContext() { 51198092Srdivacky if (Alloc.getInt()) 52198092Srdivacky delete Alloc.getPointer(); 53198092Srdivacky } 54341825Sdim 55198092Srdivacky llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 56198092Srdivacky}; 57341825Sdim 58198092Srdivackytemplate<typename T> 59198092Srdivackyclass BumpVector { 60327952Sdim T *Begin = nullptr; 61327952Sdim T *End = nullptr; 62327952Sdim T *Capacity = nullptr; 63327952Sdim 64198092Srdivackypublic: 65198092Srdivacky // Default ctor - Initialize to empty. 66327952Sdim explicit BumpVector(BumpVectorContext &C, unsigned N) { 67198092Srdivacky reserve(C, N); 68198092Srdivacky } 69341825Sdim 70198092Srdivacky ~BumpVector() { 71276479Sdim if (std::is_class<T>::value) { 72198092Srdivacky // Destroy the constructed elements in the vector. 73198092Srdivacky destroy_range(Begin, End); 74198092Srdivacky } 75198092Srdivacky } 76341825Sdim 77327952Sdim using size_type = size_t; 78327952Sdim using difference_type = ptrdiff_t; 79327952Sdim using value_type = T; 80327952Sdim using iterator = T *; 81327952Sdim using const_iterator = const T *; 82341825Sdim 83327952Sdim using const_reverse_iterator = std::reverse_iterator<const_iterator>; 84327952Sdim using reverse_iterator = std::reverse_iterator<iterator>; 85341825Sdim 86327952Sdim using reference = T &; 87327952Sdim using const_reference = const T &; 88327952Sdim using pointer = T *; 89327952Sdim using const_pointer = const T *; 90341825Sdim 91198092Srdivacky // forward iterator creation methods. 92198092Srdivacky iterator begin() { return Begin; } 93198092Srdivacky const_iterator begin() const { return Begin; } 94198092Srdivacky iterator end() { return End; } 95198092Srdivacky const_iterator end() const { return End; } 96341825Sdim 97198092Srdivacky // reverse iterator creation methods. 98327952Sdim reverse_iterator rbegin() { return reverse_iterator(end()); } 99198092Srdivacky const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 100327952Sdim reverse_iterator rend() { return reverse_iterator(begin()); } 101327952Sdim const_reverse_iterator rend() const { 102327952Sdim return const_reverse_iterator(begin()); 103327952Sdim } 104341825Sdim 105198092Srdivacky bool empty() const { return Begin == End; } 106198092Srdivacky size_type size() const { return End-Begin; } 107198092Srdivacky 108198092Srdivacky reference operator[](unsigned idx) { 109198092Srdivacky assert(Begin + idx < End); 110198092Srdivacky return Begin[idx]; 111198092Srdivacky } 112198092Srdivacky const_reference operator[](unsigned idx) const { 113198092Srdivacky assert(Begin + idx < End); 114198092Srdivacky return Begin[idx]; 115198092Srdivacky } 116341825Sdim 117198092Srdivacky reference front() { 118198092Srdivacky return begin()[0]; 119198092Srdivacky } 120198092Srdivacky const_reference front() const { 121198092Srdivacky return begin()[0]; 122198092Srdivacky } 123341825Sdim 124198092Srdivacky reference back() { 125198092Srdivacky return end()[-1]; 126198092Srdivacky } 127198092Srdivacky const_reference back() const { 128198092Srdivacky return end()[-1]; 129198092Srdivacky } 130341825Sdim 131198092Srdivacky void pop_back() { 132198092Srdivacky --End; 133198092Srdivacky End->~T(); 134198092Srdivacky } 135341825Sdim 136198092Srdivacky T pop_back_val() { 137198092Srdivacky T Result = back(); 138198092Srdivacky pop_back(); 139198092Srdivacky return Result; 140198092Srdivacky } 141341825Sdim 142198092Srdivacky void clear() { 143276479Sdim if (std::is_class<T>::value) { 144198092Srdivacky destroy_range(Begin, End); 145198092Srdivacky } 146198092Srdivacky End = Begin; 147198092Srdivacky } 148341825Sdim 149198092Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 150198092Srdivacky pointer data() { 151198092Srdivacky return pointer(Begin); 152198092Srdivacky } 153341825Sdim 154198092Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 155198092Srdivacky const_pointer data() const { 156198092Srdivacky return const_pointer(Begin); 157198092Srdivacky } 158341825Sdim 159198092Srdivacky void push_back(const_reference Elt, BumpVectorContext &C) { 160198092Srdivacky if (End < Capacity) { 161198092Srdivacky Retry: 162198092Srdivacky new (End) T(Elt); 163198092Srdivacky ++End; 164198092Srdivacky return; 165198092Srdivacky } 166198092Srdivacky grow(C); 167341825Sdim goto Retry; 168198092Srdivacky } 169218893Sdim 170218893Sdim /// insert - Insert some number of copies of element into a position. Return 171218893Sdim /// iterator to position after last inserted copy. 172218893Sdim iterator insert(iterator I, size_t Cnt, const_reference E, 173218893Sdim BumpVectorContext &C) { 174327952Sdim assert(I >= Begin && I <= End && "Iterator out of bounds."); 175218893Sdim if (End + Cnt <= Capacity) { 176218893Sdim Retry: 177218893Sdim move_range_right(I, End, Cnt); 178218893Sdim construct_range(I, I + Cnt, E); 179218893Sdim End += Cnt; 180218893Sdim return I + Cnt; 181218893Sdim } 182218893Sdim ptrdiff_t D = I - Begin; 183218893Sdim grow(C, size() + Cnt); 184218893Sdim I = Begin + D; 185218893Sdim goto Retry; 186218893Sdim } 187218893Sdim 188198092Srdivacky void reserve(BumpVectorContext &C, unsigned N) { 189198092Srdivacky if (unsigned(Capacity-Begin) < N) 190198092Srdivacky grow(C, N); 191198092Srdivacky } 192198092Srdivacky 193198092Srdivacky /// capacity - Return the total number of elements in the currently allocated 194198092Srdivacky /// buffer. 195341825Sdim size_t capacity() const { return Capacity - Begin; } 196341825Sdim 197198092Srdivackyprivate: 198198092Srdivacky /// grow - double the size of the allocated memory, guaranteeing space for at 199198092Srdivacky /// least one more element or MinSize if specified. 200200583Srdivacky void grow(BumpVectorContext &C, size_type MinSize = 1); 201341825Sdim 202198092Srdivacky void construct_range(T *S, T *E, const T &Elt) { 203198092Srdivacky for (; S != E; ++S) 204198092Srdivacky new (S) T(Elt); 205198092Srdivacky } 206341825Sdim 207198092Srdivacky void destroy_range(T *S, T *E) { 208198092Srdivacky while (S != E) { 209198092Srdivacky --E; 210198092Srdivacky E->~T(); 211198092Srdivacky } 212198092Srdivacky } 213218893Sdim 214218893Sdim void move_range_right(T *S, T *E, size_t D) { 215218893Sdim for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { 216218893Sdim --E; 217218893Sdim new (I) T(*E); 218218893Sdim E->~T(); 219218893Sdim } 220218893Sdim } 221198092Srdivacky}; 222341825Sdim 223198092Srdivacky// Define this out-of-line to dissuade the C++ compiler from inlining it. 224198092Srdivackytemplate <typename T> 225198092Srdivackyvoid BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 226198092Srdivacky size_t CurCapacity = Capacity-Begin; 227198092Srdivacky size_t CurSize = size(); 228198092Srdivacky size_t NewCapacity = 2*CurCapacity; 229198092Srdivacky if (NewCapacity < MinSize) 230198092Srdivacky NewCapacity = MinSize; 231198092Srdivacky 232198092Srdivacky // Allocate the memory from the BumpPtrAllocator. 233198092Srdivacky T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 234341825Sdim 235198092Srdivacky // Copy the elements over. 236288943Sdim if (Begin != End) { 237288943Sdim if (std::is_class<T>::value) { 238288943Sdim std::uninitialized_copy(Begin, End, NewElts); 239288943Sdim // Destroy the original elements. 240288943Sdim destroy_range(Begin, End); 241288943Sdim } else { 242288943Sdim // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 243288943Sdim memcpy(NewElts, Begin, CurSize * sizeof(T)); 244288943Sdim } 245198092Srdivacky } 246198092Srdivacky 247198092Srdivacky // For now, leak 'Begin'. We can add it back to a freelist in 248198092Srdivacky // BumpVectorContext. 249198092Srdivacky Begin = NewElts; 250198092Srdivacky End = NewElts+CurSize; 251198092Srdivacky Capacity = Begin+NewCapacity; 252198092Srdivacky} 253198092Srdivacky 254327952Sdim} // namespace clang 255327952Sdim 256327952Sdim#endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 257