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