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 30 namespace clang { 31 32 class BumpVectorContext { 33 llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; 34 35 public: 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 // The move assignment operator is defined as deleted pending further 46 // motivation. 47 BumpVectorContext &operator=(BumpVectorContext &&) = delete; 48 49 // The copy constrcutor and copy assignment operator is defined as deleted 50 // pending further motivation. 51 BumpVectorContext(const BumpVectorContext &) = delete; 52 BumpVectorContext &operator=(const BumpVectorContext &) = delete; 53 54 /// Construct a new BumpVectorContext that reuses an existing 55 /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the 56 /// BumpVectorContext object is destroyed. 57 BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} 58 59 ~BumpVectorContext() { 60 if (Alloc.getInt()) 61 delete Alloc.getPointer(); 62 } 63 64 llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } 65 }; 66 67 template<typename T> 68 class BumpVector { 69 T *Begin = nullptr; 70 T *End = nullptr; 71 T *Capacity = nullptr; 72 73 public: 74 // Default ctor - Initialize to empty. 75 explicit BumpVector(BumpVectorContext &C, unsigned N) { 76 reserve(C, N); 77 } 78 79 ~BumpVector() { 80 if (std::is_class<T>::value) { 81 // Destroy the constructed elements in the vector. 82 destroy_range(Begin, End); 83 } 84 } 85 86 using size_type = size_t; 87 using difference_type = ptrdiff_t; 88 using value_type = T; 89 using iterator = T *; 90 using const_iterator = const T *; 91 92 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 93 using reverse_iterator = std::reverse_iterator<iterator>; 94 95 using reference = T &; 96 using const_reference = const T &; 97 using pointer = T *; 98 using const_pointer = const T *; 99 100 // forward iterator creation methods. 101 iterator begin() { return Begin; } 102 const_iterator begin() const { return Begin; } 103 iterator end() { return End; } 104 const_iterator end() const { return End; } 105 106 // reverse iterator creation methods. 107 reverse_iterator rbegin() { return reverse_iterator(end()); } 108 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 109 reverse_iterator rend() { return reverse_iterator(begin()); } 110 const_reverse_iterator rend() const { 111 return const_reverse_iterator(begin()); 112 } 113 114 bool empty() const { return Begin == End; } 115 size_type size() const { return End-Begin; } 116 117 reference operator[](unsigned idx) { 118 assert(Begin + idx < End); 119 return Begin[idx]; 120 } 121 const_reference operator[](unsigned idx) const { 122 assert(Begin + idx < End); 123 return Begin[idx]; 124 } 125 126 reference front() { 127 return begin()[0]; 128 } 129 const_reference front() const { 130 return begin()[0]; 131 } 132 133 reference back() { 134 return end()[-1]; 135 } 136 const_reference back() const { 137 return end()[-1]; 138 } 139 140 void pop_back() { 141 --End; 142 End->~T(); 143 } 144 145 T pop_back_val() { 146 T Result = back(); 147 pop_back(); 148 return Result; 149 } 150 151 void clear() { 152 if (std::is_class<T>::value) { 153 destroy_range(Begin, End); 154 } 155 End = Begin; 156 } 157 158 /// data - Return a pointer to the vector's buffer, even if empty(). 159 pointer data() { 160 return pointer(Begin); 161 } 162 163 /// data - Return a pointer to the vector's buffer, even if empty(). 164 const_pointer data() const { 165 return const_pointer(Begin); 166 } 167 168 void push_back(const_reference Elt, BumpVectorContext &C) { 169 if (End < Capacity) { 170 Retry: 171 new (End) T(Elt); 172 ++End; 173 return; 174 } 175 grow(C); 176 goto Retry; 177 } 178 179 /// insert - Insert some number of copies of element into a position. Return 180 /// iterator to position after last inserted copy. 181 iterator insert(iterator I, size_t Cnt, const_reference E, 182 BumpVectorContext &C) { 183 assert(I >= Begin && I <= End && "Iterator out of bounds."); 184 if (End + Cnt <= Capacity) { 185 Retry: 186 move_range_right(I, End, Cnt); 187 construct_range(I, I + Cnt, E); 188 End += Cnt; 189 return I + Cnt; 190 } 191 ptrdiff_t D = I - Begin; 192 grow(C, size() + Cnt); 193 I = Begin + D; 194 goto Retry; 195 } 196 197 void reserve(BumpVectorContext &C, unsigned N) { 198 if (unsigned(Capacity-Begin) < N) 199 grow(C, N); 200 } 201 202 /// capacity - Return the total number of elements in the currently allocated 203 /// buffer. 204 size_t capacity() const { return Capacity - Begin; } 205 206 private: 207 /// grow - double the size of the allocated memory, guaranteeing space for at 208 /// least one more element or MinSize if specified. 209 void grow(BumpVectorContext &C, size_type MinSize = 1); 210 211 void construct_range(T *S, T *E, const T &Elt) { 212 for (; S != E; ++S) 213 new (S) T(Elt); 214 } 215 216 void destroy_range(T *S, T *E) { 217 while (S != E) { 218 --E; 219 E->~T(); 220 } 221 } 222 223 void move_range_right(T *S, T *E, size_t D) { 224 for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { 225 --E; 226 new (I) T(*E); 227 E->~T(); 228 } 229 } 230 }; 231 232 // Define this out-of-line to dissuade the C++ compiler from inlining it. 233 template <typename T> 234 void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { 235 size_t CurCapacity = Capacity-Begin; 236 size_t CurSize = size(); 237 size_t NewCapacity = 2*CurCapacity; 238 if (NewCapacity < MinSize) 239 NewCapacity = MinSize; 240 241 // Allocate the memory from the BumpPtrAllocator. 242 T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); 243 244 // Copy the elements over. 245 if (Begin != End) { 246 if (std::is_class<T>::value) { 247 std::uninitialized_copy(Begin, End, NewElts); 248 // Destroy the original elements. 249 destroy_range(Begin, End); 250 } else { 251 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 252 memcpy(NewElts, Begin, CurSize * sizeof(T)); 253 } 254 } 255 256 // For now, leak 'Begin'. We can add it back to a freelist in 257 // BumpVectorContext. 258 Begin = NewElts; 259 End = NewElts+CurSize; 260 Capacity = Begin+NewCapacity; 261 } 262 263 } // namespace clang 264 265 #endif // LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H 266