BumpVector.h revision 355940
1//===- BumpVector.h - Vector-like ADT that uses bump allocation -*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file provides BumpVector, a vector-like ADT whose contents are 10// allocated from a BumpPtrAllocator. 11// 12//===----------------------------------------------------------------------===// 13 14// FIXME: Most of this is copy-and-paste from SmallVector.h. We can 15// refactor this core logic into something common that is shared between 16// the two. The main thing that is different is the allocation strategy. 17 18#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 19#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 20 21#include "llvm/ADT/PointerIntPair.h" 22#include "llvm/Support/Allocator.h" 23#include <cassert> 24#include <cstddef> 25#include <cstring> 26#include <iterator> 27#include <memory> 28#include <type_traits> 29 30namespace clang { 31 32class BumpVectorContext { 33 llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 34 35public: 36 /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator 37 /// and destroys it when the BumpVectorContext object is destroyed. 38 BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} 39 40 BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) { 41 Other.Alloc.setInt(false); 42 Other.Alloc.setPointer(nullptr); 43 } 44 45 /// Construct a new BumpVectorContext that reuses an existing 46 /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 47 /// BumpVectorContext object is destroyed. 48 BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 49 50 ~BumpVectorContext() { 51 if (Alloc.getInt()) 52 delete Alloc.getPointer(); 53 } 54 55 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 56}; 57 58template<typename T> 59class BumpVector { 60 T *Begin = nullptr; 61 T *End = nullptr; 62 T *Capacity = nullptr; 63 64public: 65 // Default ctor - Initialize to empty. 66 explicit BumpVector(BumpVectorContext &C, unsigned N) { 67 reserve(C, N); 68 } 69 70 ~BumpVector() { 71 if (std::is_class<T>::value) { 72 // Destroy the constructed elements in the vector. 73 destroy_range(Begin, End); 74 } 75 } 76 77 using size_type = size_t; 78 using difference_type = ptrdiff_t; 79 using value_type = T; 80 using iterator = T *; 81 using const_iterator = const T *; 82 83 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 84 using reverse_iterator = std::reverse_iterator<iterator>; 85 86 using reference = T &; 87 using const_reference = const T &; 88 using pointer = T *; 89 using const_pointer = const T *; 90 91 // forward iterator creation methods. 92 iterator begin() { return Begin; } 93 const_iterator begin() const { return Begin; } 94 iterator end() { return End; } 95 const_iterator end() const { return End; } 96 97 // reverse iterator creation methods. 98 reverse_iterator rbegin() { return reverse_iterator(end()); } 99 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 100 reverse_iterator rend() { return reverse_iterator(begin()); } 101 const_reverse_iterator rend() const { 102 return const_reverse_iterator(begin()); 103 } 104 105 bool empty() const { return Begin == End; } 106 size_type size() const { return End-Begin; } 107 108 reference operator[](unsigned idx) { 109 assert(Begin + idx < End); 110 return Begin[idx]; 111 } 112 const_reference operator[](unsigned idx) const { 113 assert(Begin + idx < End); 114 return Begin[idx]; 115 } 116 117 reference front() { 118 return begin()[0]; 119 } 120 const_reference front() const { 121 return begin()[0]; 122 } 123 124 reference back() { 125 return end()[-1]; 126 } 127 const_reference back() const { 128 return end()[-1]; 129 } 130 131 void pop_back() { 132 --End; 133 End->~T(); 134 } 135 136 T pop_back_val() { 137 T Result = back(); 138 pop_back(); 139 return Result; 140 } 141 142 void clear() { 143 if (std::is_class<T>::value) { 144 destroy_range(Begin, End); 145 } 146 End = Begin; 147 } 148 149 /// data - Return a pointer to the vector's buffer, even if empty(). 150 pointer data() { 151 return pointer(Begin); 152 } 153 154 /// data - Return a pointer to the vector's buffer, even if empty(). 155 const_pointer data() const { 156 return const_pointer(Begin); 157 } 158 159 void push_back(const_reference Elt, BumpVectorContext &C) { 160 if (End < Capacity) { 161 Retry: 162 new (End) T(Elt); 163 ++End; 164 return; 165 } 166 grow(C); 167 goto Retry; 168 } 169 170 /// insert - Insert some number of copies of element into a position. Return 171 /// iterator to position after last inserted copy. 172 iterator insert(iterator I, size_t Cnt, const_reference E, 173 BumpVectorContext &C) { 174 assert(I >= Begin && I <= End && "Iterator out of bounds."); 175 if (End + Cnt <= Capacity) { 176 Retry: 177 move_range_right(I, End, Cnt); 178 construct_range(I, I + Cnt, E); 179 End += Cnt; 180 return I + Cnt; 181 } 182 ptrdiff_t D = I - Begin; 183 grow(C, size() + Cnt); 184 I = Begin + D; 185 goto Retry; 186 } 187 188 void reserve(BumpVectorContext &C, unsigned N) { 189 if (unsigned(Capacity-Begin) < N) 190 grow(C, N); 191 } 192 193 /// capacity - Return the total number of elements in the currently allocated 194 /// buffer. 195 size_t capacity() const { return Capacity - Begin; } 196 197private: 198 /// grow - double the size of the allocated memory, guaranteeing space for at 199 /// least one more element or MinSize if specified. 200 void grow(BumpVectorContext &C, size_type MinSize = 1); 201 202 void construct_range(T *S, T *E, const T &Elt) { 203 for (; S != E; ++S) 204 new (S) T(Elt); 205 } 206 207 void destroy_range(T *S, T *E) { 208 while (S != E) { 209 --E; 210 E->~T(); 211 } 212 } 213 214 void move_range_right(T *S, T *E, size_t D) { 215 for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { 216 --E; 217 new (I) T(*E); 218 E->~T(); 219 } 220 } 221}; 222 223// Define this out-of-line to dissuade the C++ compiler from inlining it. 224template <typename T> 225void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 226 size_t CurCapacity = Capacity-Begin; 227 size_t CurSize = size(); 228 size_t NewCapacity = 2*CurCapacity; 229 if (NewCapacity < MinSize) 230 NewCapacity = MinSize; 231 232 // Allocate the memory from the BumpPtrAllocator. 233 T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 234 235 // Copy the elements over. 236 if (Begin != End) { 237 if (std::is_class<T>::value) { 238 std::uninitialized_copy(Begin, End, NewElts); 239 // Destroy the original elements. 240 destroy_range(Begin, End); 241 } else { 242 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 243 memcpy(NewElts, Begin, CurSize * sizeof(T)); 244 } 245 } 246 247 // For now, leak 'Begin'. We can add it back to a freelist in 248 // BumpVectorContext. 249 Begin = NewElts; 250 End = NewElts+CurSize; 251 Capacity = Begin+NewCapacity; 252} 253 254} // namespace clang 255 256#endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 257