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