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