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