1//===- ASTVector.h - Vector that uses ASTContext for 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 ASTVector, a vector ADT whose contents are 10// allocated using the allocator associated with an ASTContext.. 11// 12//===----------------------------------------------------------------------===// 13 14// FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h. 15// We can refactor this core logic into something common. 16 17#ifndef LLVM_CLANG_AST_ASTVECTOR_H 18#define LLVM_CLANG_AST_ASTVECTOR_H 19 20#include "clang/AST/ASTContextAllocate.h" 21#include "llvm/ADT/PointerIntPair.h" 22#include <algorithm> 23#include <cassert> 24#include <cstddef> 25#include <cstring> 26#include <iterator> 27#include <memory> 28#include <type_traits> 29#include <utility> 30 31namespace clang { 32 33class ASTContext; 34 35template<typename T> 36class ASTVector { 37private: 38 T *Begin = nullptr; 39 T *End = nullptr; 40 llvm::PointerIntPair<T *, 1, bool> Capacity; 41 42 void setEnd(T *P) { this->End = P; } 43 44protected: 45 // Make a tag bit available to users of this class. 46 // FIXME: This is a horrible hack. 47 bool getTag() const { return Capacity.getInt(); } 48 void setTag(bool B) { Capacity.setInt(B); } 49 50public: 51 // Default ctor - Initialize to empty. 52 ASTVector() : Capacity(nullptr, false) {} 53 54 ASTVector(ASTVector &&O) : Begin(O.Begin), End(O.End), Capacity(O.Capacity) { 55 O.Begin = O.End = nullptr; 56 O.Capacity.setPointer(nullptr); 57 O.Capacity.setInt(false); 58 } 59 60 ASTVector(const ASTContext &C, unsigned N) : Capacity(nullptr, false) { 61 reserve(C, N); 62 } 63 64 ASTVector &operator=(ASTVector &&RHS) { 65 ASTVector O(std::move(RHS)); 66 67 using std::swap; 68 69 swap(Begin, O.Begin); 70 swap(End, O.End); 71 swap(Capacity, O.Capacity); 72 return *this; 73 } 74 75 ~ASTVector() { 76 if (std::is_class<T>::value) { 77 // Destroy the constructed elements in the vector. 78 destroy_range(Begin, End); 79 } 80 } 81 82 using size_type = size_t; 83 using difference_type = ptrdiff_t; 84 using value_type = T; 85 using iterator = T *; 86 using const_iterator = const T *; 87 88 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 89 using reverse_iterator = std::reverse_iterator<iterator>; 90 91 using reference = T &; 92 using const_reference = const T &; 93 using pointer = T *; 94 using const_pointer = const T *; 95 96 // forward iterator creation methods. 97 iterator begin() { return Begin; } 98 const_iterator begin() const { return Begin; } 99 iterator end() { return End; } 100 const_iterator end() const { return End; } 101 102 // reverse iterator creation methods. 103 reverse_iterator rbegin() { return reverse_iterator(end()); } 104 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 105 reverse_iterator rend() { return reverse_iterator(begin()); } 106 const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 107 108 bool empty() const { return Begin == End; } 109 size_type size() const { return End-Begin; } 110 111 reference operator[](unsigned idx) { 112 assert(Begin + idx < End); 113 return Begin[idx]; 114 } 115 const_reference operator[](unsigned idx) const { 116 assert(Begin + idx < End); 117 return Begin[idx]; 118 } 119 120 reference front() { 121 return begin()[0]; 122 } 123 const_reference front() const { 124 return begin()[0]; 125 } 126 127 reference back() { 128 return end()[-1]; 129 } 130 const_reference back() const { 131 return end()[-1]; 132 } 133 134 void pop_back() { 135 --End; 136 End->~T(); 137 } 138 139 T pop_back_val() { 140 T Result = back(); 141 pop_back(); 142 return Result; 143 } 144 145 void clear() { 146 if (std::is_class<T>::value) { 147 destroy_range(Begin, End); 148 } 149 End = Begin; 150 } 151 152 /// data - Return a pointer to the vector's buffer, even if empty(). 153 pointer data() { 154 return pointer(Begin); 155 } 156 157 /// data - Return a pointer to the vector's buffer, even if empty(). 158 const_pointer data() const { 159 return const_pointer(Begin); 160 } 161 162 void push_back(const_reference Elt, const ASTContext &C) { 163 if (End < this->capacity_ptr()) { 164 Retry: 165 new (End) T(Elt); 166 ++End; 167 return; 168 } 169 grow(C); 170 goto Retry; 171 } 172 173 void reserve(const ASTContext &C, unsigned N) { 174 if (unsigned(this->capacity_ptr()-Begin) < N) 175 grow(C, N); 176 } 177 178 /// capacity - Return the total number of elements in the currently allocated 179 /// buffer. 180 size_t capacity() const { return this->capacity_ptr() - Begin; } 181 182 /// append - Add the specified range to the end of the SmallVector. 183 template<typename in_iter> 184 void append(const ASTContext &C, in_iter in_start, in_iter in_end) { 185 size_type NumInputs = std::distance(in_start, in_end); 186 187 if (NumInputs == 0) 188 return; 189 190 // Grow allocated space if needed. 191 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 192 this->grow(C, this->size()+NumInputs); 193 194 // Copy the new elements over. 195 // TODO: NEED To compile time dispatch on whether in_iter is a random access 196 // iterator to use the fast uninitialized_copy. 197 std::uninitialized_copy(in_start, in_end, this->end()); 198 this->setEnd(this->end() + NumInputs); 199 } 200 201 /// append - Add the specified range to the end of the SmallVector. 202 void append(const ASTContext &C, size_type NumInputs, const T &Elt) { 203 // Grow allocated space if needed. 204 if (NumInputs > size_type(this->capacity_ptr()-this->end())) 205 this->grow(C, this->size()+NumInputs); 206 207 // Copy the new elements over. 208 std::uninitialized_fill_n(this->end(), NumInputs, Elt); 209 this->setEnd(this->end() + NumInputs); 210 } 211 212 /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 213 /// starting with "Dest", constructing elements into it as needed. 214 template<typename It1, typename It2> 215 static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 216 std::uninitialized_copy(I, E, Dest); 217 } 218 219 iterator insert(const ASTContext &C, iterator I, const T &Elt) { 220 if (I == this->end()) { // Important special case for empty vector. 221 push_back(Elt, C); 222 return this->end()-1; 223 } 224 225 if (this->End < this->capacity_ptr()) { 226 Retry: 227 new (this->end()) T(this->back()); 228 this->setEnd(this->end()+1); 229 // Push everything else over. 230 std::copy_backward(I, this->end()-1, this->end()); 231 *I = Elt; 232 return I; 233 } 234 size_t EltNo = I-this->begin(); 235 this->grow(C); 236 I = this->begin()+EltNo; 237 goto Retry; 238 } 239 240 iterator insert(const ASTContext &C, iterator I, size_type NumToInsert, 241 const T &Elt) { 242 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 243 size_t InsertElt = I - this->begin(); 244 245 if (I == this->end()) { // Important special case for empty vector. 246 append(C, NumToInsert, Elt); 247 return this->begin() + InsertElt; 248 } 249 250 // Ensure there is enough space. 251 reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 252 253 // Uninvalidate the iterator. 254 I = this->begin()+InsertElt; 255 256 // If there are more elements between the insertion point and the end of the 257 // range than there are being inserted, we can use a simple approach to 258 // insertion. Since we already reserved space, we know that this won't 259 // reallocate the vector. 260 if (size_t(this->end()-I) >= NumToInsert) { 261 T *OldEnd = this->end(); 262 append(C, this->end()-NumToInsert, this->end()); 263 264 // Copy the existing elements that get replaced. 265 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 266 267 std::fill_n(I, NumToInsert, Elt); 268 return I; 269 } 270 271 // Otherwise, we're inserting more elements than exist already, and we're 272 // not inserting at the end. 273 274 // Copy over the elements that we're about to overwrite. 275 T *OldEnd = this->end(); 276 this->setEnd(this->end() + NumToInsert); 277 size_t NumOverwritten = OldEnd-I; 278 this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 279 280 // Replace the overwritten part. 281 std::fill_n(I, NumOverwritten, Elt); 282 283 // Insert the non-overwritten middle part. 284 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 285 return I; 286 } 287 288 template<typename ItTy> 289 iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) { 290 // Convert iterator to elt# to avoid invalidating iterator when we reserve() 291 size_t InsertElt = I - this->begin(); 292 293 if (I == this->end()) { // Important special case for empty vector. 294 append(C, From, To); 295 return this->begin() + InsertElt; 296 } 297 298 size_t NumToInsert = std::distance(From, To); 299 300 // Ensure there is enough space. 301 reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 302 303 // Uninvalidate the iterator. 304 I = this->begin()+InsertElt; 305 306 // If there are more elements between the insertion point and the end of the 307 // range than there are being inserted, we can use a simple approach to 308 // insertion. Since we already reserved space, we know that this won't 309 // reallocate the vector. 310 if (size_t(this->end()-I) >= NumToInsert) { 311 T *OldEnd = this->end(); 312 append(C, this->end()-NumToInsert, this->end()); 313 314 // Copy the existing elements that get replaced. 315 std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 316 317 std::copy(From, To, I); 318 return I; 319 } 320 321 // Otherwise, we're inserting more elements than exist already, and we're 322 // not inserting at the end. 323 324 // Copy over the elements that we're about to overwrite. 325 T *OldEnd = this->end(); 326 this->setEnd(this->end() + NumToInsert); 327 size_t NumOverwritten = OldEnd-I; 328 this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 329 330 // Replace the overwritten part. 331 for (; NumOverwritten > 0; --NumOverwritten) { 332 *I = *From; 333 ++I; ++From; 334 } 335 336 // Insert the non-overwritten middle part. 337 this->uninitialized_copy(From, To, OldEnd); 338 return I; 339 } 340 341 void resize(const ASTContext &C, unsigned N, const T &NV) { 342 if (N < this->size()) { 343 this->destroy_range(this->begin()+N, this->end()); 344 this->setEnd(this->begin()+N); 345 } else if (N > this->size()) { 346 if (this->capacity() < N) 347 this->grow(C, N); 348 construct_range(this->end(), this->begin()+N, NV); 349 this->setEnd(this->begin()+N); 350 } 351 } 352 353private: 354 /// grow - double the size of the allocated memory, guaranteeing space for at 355 /// least one more element or MinSize if specified. 356 void grow(const ASTContext &C, size_type MinSize = 1); 357 358 void construct_range(T *S, T *E, const T &Elt) { 359 for (; S != E; ++S) 360 new (S) T(Elt); 361 } 362 363 void destroy_range(T *S, T *E) { 364 while (S != E) { 365 --E; 366 E->~T(); 367 } 368 } 369 370protected: 371 const_iterator capacity_ptr() const { 372 return (iterator) Capacity.getPointer(); 373 } 374 375 iterator capacity_ptr() { return (iterator)Capacity.getPointer(); } 376}; 377 378// Define this out-of-line to dissuade the C++ compiler from inlining it. 379template <typename T> 380void ASTVector<T>::grow(const ASTContext &C, size_t MinSize) { 381 size_t CurCapacity = this->capacity(); 382 size_t CurSize = size(); 383 size_t NewCapacity = 2*CurCapacity; 384 if (NewCapacity < MinSize) 385 NewCapacity = MinSize; 386 387 // Allocate the memory from the ASTContext. 388 T *NewElts = new (C, alignof(T)) T[NewCapacity]; 389 390 // Copy the elements over. 391 if (Begin != End) { 392 if (std::is_class<T>::value) { 393 std::uninitialized_copy(Begin, End, NewElts); 394 // Destroy the original elements. 395 destroy_range(Begin, End); 396 } else { 397 // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 398 memcpy(NewElts, Begin, CurSize * sizeof(T)); 399 } 400 } 401 402 // ASTContext never frees any memory. 403 Begin = NewElts; 404 End = NewElts+CurSize; 405 Capacity.setPointer(Begin+NewCapacity); 406} 407 408} // namespace clang 409 410#endif // LLVM_CLANG_AST_ASTVECTOR_H 411