ASTVector.h revision 239462
1207619Srdivacky//===- ASTVector.h - Vector that uses ASTContext for allocation --*- C++ -*-=// 2207619Srdivacky// 3207619Srdivacky// The LLVM Compiler Infrastructure 4207619Srdivacky// 5207619Srdivacky// This file is distributed under the University of Illinois Open Source 6207619Srdivacky// License. See LICENSE.TXT for details. 7207619Srdivacky// 8207619Srdivacky//===----------------------------------------------------------------------===// 9207619Srdivacky// 10207619Srdivacky// This file provides ASTVector, a vector ADT whose contents are 11207619Srdivacky// allocated using the allocator associated with an ASTContext.. 12207619Srdivacky// 13207619Srdivacky//===----------------------------------------------------------------------===// 14207619Srdivacky 15207619Srdivacky// FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h. 16207619Srdivacky// We can refactor this core logic into something common. 17207619Srdivacky 18207619Srdivacky#ifndef LLVM_CLANG_AST_VECTOR 19207619Srdivacky#define LLVM_CLANG_AST_VECTOR 20207619Srdivacky 21207619Srdivacky#include "llvm/Support/type_traits.h" 22207619Srdivacky#include "llvm/Support/Allocator.h" 23207619Srdivacky#include "llvm/ADT/PointerIntPair.h" 24207619Srdivacky#include <algorithm> 25207619Srdivacky#include <memory> 26207619Srdivacky#include <cstring> 27207619Srdivacky 28207619Srdivacky#ifdef _MSC_VER 29207619Srdivackynamespace std { 30207619Srdivacky#if _MSC_VER <= 1310 31207619Srdivacky // Work around flawed VC++ implementation of std::uninitialized_copy. Define 32207619Srdivacky // additional overloads so that elements with pointer types are recognized as 33207619Srdivacky // scalars and not objects, causing bizarre type conversion errors. 34207619Srdivacky template<class T1, class T2> 35207619Srdivacky inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { 36207619Srdivacky _Scalar_ptr_iterator_tag _Cat; 37207619Srdivacky return _Cat; 38207619Srdivacky } 39207619Srdivacky 40207619Srdivacky template<class T1, class T2> 41207619Srdivacky inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { 42207619Srdivacky _Scalar_ptr_iterator_tag _Cat; 43207619Srdivacky return _Cat; 44207619Srdivacky } 45207619Srdivacky#else 46207619Srdivacky // FIXME: It is not clear if the problem is fixed in VS 2005. What is clear 47207619Srdivacky // is that the above hack won't work if it wasn't fixed. 48207619Srdivacky#endif 49207619Srdivacky} 50207619Srdivacky#endif 51207619Srdivacky 52207619Srdivackynamespace clang { 53207619Srdivacky 54207619Srdivackytemplate<typename T> 55207619Srdivackyclass ASTVector { 56207619Srdivacky T *Begin, *End, *Capacity; 57207619Srdivacky 58207619Srdivacky void setEnd(T *P) { this->End = P; } 59207619Srdivacky 60207619Srdivackypublic: 61207619Srdivacky // Default ctor - Initialize to empty. 62207619Srdivacky explicit ASTVector(ASTContext &C, unsigned N = 0) 63207619Srdivacky : Begin(NULL), End(NULL), Capacity(NULL) { 64207619Srdivacky reserve(C, N); 65207619Srdivacky } 66207619Srdivacky 67207619Srdivacky ~ASTVector() { 68207619Srdivacky if (llvm::is_class<T>::value) { 69207619Srdivacky // Destroy the constructed elements in the vector. 70207619Srdivacky destroy_range(Begin, End); 71207619Srdivacky } 72207619Srdivacky } 73207619Srdivacky 74207619Srdivacky typedef size_t size_type; 75207619Srdivacky typedef ptrdiff_t difference_type; 76207619Srdivacky typedef T value_type; 77207619Srdivacky typedef T* iterator; 78207619Srdivacky typedef const T* const_iterator; 79207619Srdivacky 80207619Srdivacky typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 81207619Srdivacky typedef std::reverse_iterator<iterator> reverse_iterator; 82207619Srdivacky 83207619Srdivacky typedef T& reference; 84207619Srdivacky typedef const T& const_reference; 85207619Srdivacky typedef T* pointer; 86207619Srdivacky typedef const T* const_pointer; 87207619Srdivacky 88207619Srdivacky // forward iterator creation methods. 89207619Srdivacky iterator begin() { return Begin; } 90207619Srdivacky const_iterator begin() const { return Begin; } 91207619Srdivacky iterator end() { return End; } 92207619Srdivacky const_iterator end() const { return End; } 93207619Srdivacky 94207619Srdivacky // reverse iterator creation methods. 95207619Srdivacky reverse_iterator rbegin() { return reverse_iterator(end()); } 96207619Srdivacky const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 97207619Srdivacky reverse_iterator rend() { return reverse_iterator(begin()); } 98207619Srdivacky const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 99207619Srdivacky 100207619Srdivacky bool empty() const { return Begin == End; } 101207619Srdivacky size_type size() const { return End-Begin; } 102207619Srdivacky 103207619Srdivacky reference operator[](unsigned idx) { 104207619Srdivacky assert(Begin + idx < End); 105207619Srdivacky return Begin[idx]; 106207619Srdivacky } 107207619Srdivacky const_reference operator[](unsigned idx) const { 108207619Srdivacky assert(Begin + idx < End); 109207619Srdivacky return Begin[idx]; 110207619Srdivacky } 111207619Srdivacky 112207619Srdivacky reference front() { 113207619Srdivacky return begin()[0]; 114207619Srdivacky } 115207619Srdivacky const_reference front() const { 116207619Srdivacky return begin()[0]; 117207619Srdivacky } 118207619Srdivacky 119207619Srdivacky reference back() { 120207619Srdivacky return end()[-1]; 121207619Srdivacky } 122207619Srdivacky const_reference back() const { 123207619Srdivacky return end()[-1]; 124207619Srdivacky } 125207619Srdivacky 126207619Srdivacky void pop_back() { 127207619Srdivacky --End; 128207619Srdivacky End->~T(); 129207619Srdivacky } 130207619Srdivacky 131207619Srdivacky T pop_back_val() { 132207619Srdivacky T Result = back(); 133207619Srdivacky pop_back(); 134207619Srdivacky return Result; 135207619Srdivacky } 136207619Srdivacky 137207619Srdivacky void clear() { 138207619Srdivacky if (llvm::is_class<T>::value) { 139207619Srdivacky destroy_range(Begin, End); 140207619Srdivacky } 141207619Srdivacky End = Begin; 142207619Srdivacky } 143207619Srdivacky 144207619Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 145207619Srdivacky pointer data() { 146207619Srdivacky return pointer(Begin); 147207619Srdivacky } 148207619Srdivacky 149207619Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 150207619Srdivacky const_pointer data() const { 151207619Srdivacky return const_pointer(Begin); 152207619Srdivacky } 153207619Srdivacky 154207619Srdivacky void push_back(const_reference Elt, ASTContext &C) { 155207619Srdivacky if (End < Capacity) { 156207619Srdivacky Retry: 157207619Srdivacky new (End) T(Elt); 158207619Srdivacky ++End; 159207619Srdivacky return; 160207619Srdivacky } 161207619Srdivacky grow(C); 162207619Srdivacky goto Retry; 163207619Srdivacky } 164207619Srdivacky 165207619Srdivacky void reserve(ASTContext &C, unsigned N) { 166207619Srdivacky if (unsigned(Capacity-Begin) < N) 167207619Srdivacky grow(C, N); 168207619Srdivacky } 169207619Srdivacky 170207619Srdivacky /// capacity - Return the total number of elements in the currently allocated 171207619Srdivacky /// buffer. 172207619Srdivacky size_t capacity() const { return Capacity - Begin; } 173207619Srdivacky 174207619Srdivacky /// append - Add the specified range to the end of the SmallVector. 175207619Srdivacky /// 176207619Srdivacky template<typename in_iter> 177207619Srdivacky void append(ASTContext &C, in_iter in_start, in_iter in_end) { 178207619Srdivacky size_type NumInputs = std::distance(in_start, in_end); 179207619Srdivacky 180207619Srdivacky if (NumInputs == 0) 181207619Srdivacky return; 182207619Srdivacky 183207619Srdivacky // Grow allocated space if needed. 184207619Srdivacky if (NumInputs > size_type(this->capacity_ptr()-this->end())) 185207619Srdivacky this->grow(C, this->size()+NumInputs); 186207619Srdivacky 187207619Srdivacky // Copy the new elements over. 188207619Srdivacky // TODO: NEED To compile time dispatch on whether in_iter is a random access 189207619Srdivacky // iterator to use the fast uninitialized_copy. 190207619Srdivacky std::uninitialized_copy(in_start, in_end, this->end()); 191207619Srdivacky this->setEnd(this->end() + NumInputs); 192207619Srdivacky } 193207619Srdivacky 194207619Srdivacky /// append - Add the specified range to the end of the SmallVector. 195207619Srdivacky /// 196207619Srdivacky void append(ASTContext &C, size_type NumInputs, const T &Elt) { 197207619Srdivacky // Grow allocated space if needed. 198207619Srdivacky if (NumInputs > size_type(this->capacity_ptr()-this->end())) 199207619Srdivacky this->grow(C, this->size()+NumInputs); 200207619Srdivacky 201207619Srdivacky // Copy the new elements over. 202207619Srdivacky std::uninitialized_fill_n(this->end(), NumInputs, Elt); 203207619Srdivacky this->setEnd(this->end() + NumInputs); 204207619Srdivacky } 205207619Srdivacky 206207619Srdivacky /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 207207619Srdivacky /// starting with "Dest", constructing elements into it as needed. 208207619Srdivacky template<typename It1, typename It2> 209207619Srdivacky static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 210207619Srdivacky std::uninitialized_copy(I, E, Dest); 211207619Srdivacky } 212207619Srdivacky 213207619Srdivacky iterator insert(ASTContext &C, iterator I, const T &Elt) { 214207619Srdivacky if (I == this->end()) { // Important special case for empty vector. 215207619Srdivacky push_back(Elt); 216207619Srdivacky return this->end()-1; 217207619Srdivacky } 218207619Srdivacky 219207619Srdivacky if (this->EndX < this->CapacityX) { 220207619Srdivacky Retry: 221207619Srdivacky new (this->end()) T(this->back()); 222207619Srdivacky this->setEnd(this->end()+1); 223207619Srdivacky // Push everything else over. 224207619Srdivacky std::copy_backward(I, this->end()-1, this->end()); 225207619Srdivacky *I = Elt; 226207619Srdivacky return I; 227207619Srdivacky } 228207619Srdivacky size_t EltNo = I-this->begin(); 229207619Srdivacky this->grow(C); 230207619Srdivacky I = this->begin()+EltNo; 231207619Srdivacky goto Retry; 232207619Srdivacky } 233207619Srdivacky 234207619Srdivacky iterator insert(ASTContext &C, iterator I, size_type NumToInsert, 235207619Srdivacky const T &Elt) { 236207619Srdivacky if (I == this->end()) { // Important special case for empty vector. 237207619Srdivacky append(C, NumToInsert, Elt); 238207619Srdivacky return this->end()-1; 239207619Srdivacky } 240207619Srdivacky 241207619Srdivacky // Convert iterator to elt# to avoid invalidating iterator when we reserve() 242207619Srdivacky size_t InsertElt = I - this->begin(); 243207619Srdivacky 244207619Srdivacky // Ensure there is enough space. 245207619Srdivacky reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 246207619Srdivacky 247207619Srdivacky // Uninvalidate the iterator. 248207619Srdivacky I = this->begin()+InsertElt; 249207619Srdivacky 250207619Srdivacky // If there are more elements between the insertion point and the end of the 251207619Srdivacky // range than there are being inserted, we can use a simple approach to 252207619Srdivacky // insertion. Since we already reserved space, we know that this won't 253207619Srdivacky // reallocate the vector. 254207619Srdivacky if (size_t(this->end()-I) >= NumToInsert) { 255207619Srdivacky T *OldEnd = this->end(); 256207619Srdivacky append(C, this->end()-NumToInsert, this->end()); 257207619Srdivacky 258207619Srdivacky // Copy the existing elements that get replaced. 259207619Srdivacky std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 260207619Srdivacky 261207619Srdivacky std::fill_n(I, NumToInsert, Elt); 262207619Srdivacky return I; 263207619Srdivacky } 264207619Srdivacky 265207619Srdivacky // Otherwise, we're inserting more elements than exist already, and we're 266207619Srdivacky // not inserting at the end. 267207619Srdivacky 268207619Srdivacky // Copy over the elements that we're about to overwrite. 269207619Srdivacky T *OldEnd = this->end(); 270207619Srdivacky this->setEnd(this->end() + NumToInsert); 271207619Srdivacky size_t NumOverwritten = OldEnd-I; 272207619Srdivacky this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 273207619Srdivacky 274207619Srdivacky // Replace the overwritten part. 275207619Srdivacky std::fill_n(I, NumOverwritten, Elt); 276207619Srdivacky 277207619Srdivacky // Insert the non-overwritten middle part. 278207619Srdivacky std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 279207619Srdivacky return I; 280207619Srdivacky } 281207619Srdivacky 282207619Srdivacky template<typename ItTy> 283207619Srdivacky iterator insert(ASTContext &C, iterator I, ItTy From, ItTy To) { 284207619Srdivacky if (I == this->end()) { // Important special case for empty vector. 285207619Srdivacky append(C, From, To); 286207619Srdivacky return this->end()-1; 287207619Srdivacky } 288207619Srdivacky 289207619Srdivacky size_t NumToInsert = std::distance(From, To); 290207619Srdivacky // Convert iterator to elt# to avoid invalidating iterator when we reserve() 291207619Srdivacky size_t InsertElt = I - this->begin(); 292207619Srdivacky 293207619Srdivacky // Ensure there is enough space. 294207619Srdivacky reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 295207619Srdivacky 296207619Srdivacky // Uninvalidate the iterator. 297207619Srdivacky I = this->begin()+InsertElt; 298207619Srdivacky 299207619Srdivacky // If there are more elements between the insertion point and the end of the 300207619Srdivacky // range than there are being inserted, we can use a simple approach to 301207619Srdivacky // insertion. Since we already reserved space, we know that this won't 302207619Srdivacky // reallocate the vector. 303207619Srdivacky if (size_t(this->end()-I) >= NumToInsert) { 304207619Srdivacky T *OldEnd = this->end(); 305207619Srdivacky append(C, this->end()-NumToInsert, this->end()); 306207619Srdivacky 307207619Srdivacky // Copy the existing elements that get replaced. 308207619Srdivacky std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 309207619Srdivacky 310207619Srdivacky std::copy(From, To, I); 311207619Srdivacky return I; 312207619Srdivacky } 313207619Srdivacky 314207619Srdivacky // Otherwise, we're inserting more elements than exist already, and we're 315207619Srdivacky // not inserting at the end. 316207619Srdivacky 317207619Srdivacky // Copy over the elements that we're about to overwrite. 318207619Srdivacky T *OldEnd = this->end(); 319207619Srdivacky this->setEnd(this->end() + NumToInsert); 320207619Srdivacky size_t NumOverwritten = OldEnd-I; 321207619Srdivacky this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 322207619Srdivacky 323207619Srdivacky // Replace the overwritten part. 324207619Srdivacky for (; NumOverwritten > 0; --NumOverwritten) { 325207619Srdivacky *I = *From; 326207619Srdivacky ++I; ++From; 327207619Srdivacky } 328207619Srdivacky 329207619Srdivacky // Insert the non-overwritten middle part. 330207619Srdivacky this->uninitialized_copy(From, To, OldEnd); 331207619Srdivacky return I; 332207619Srdivacky } 333207619Srdivacky 334207619Srdivacky void resize(ASTContext &C, unsigned N, const T &NV) { 335207619Srdivacky if (N < this->size()) { 336207619Srdivacky this->destroy_range(this->begin()+N, this->end()); 337207619Srdivacky this->setEnd(this->begin()+N); 338207619Srdivacky } else if (N > this->size()) { 339207619Srdivacky if (this->capacity() < N) 340207619Srdivacky this->grow(C, N); 341207619Srdivacky construct_range(this->end(), this->begin()+N, NV); 342207619Srdivacky this->setEnd(this->begin()+N); 343207619Srdivacky } 344207619Srdivacky } 345207619Srdivacky 346207619Srdivackyprivate: 347207619Srdivacky /// grow - double the size of the allocated memory, guaranteeing space for at 348207619Srdivacky /// least one more element or MinSize if specified. 349207619Srdivacky void grow(ASTContext &C, size_type MinSize = 1); 350207619Srdivacky 351207619Srdivacky void construct_range(T *S, T *E, const T &Elt) { 352207619Srdivacky for (; S != E; ++S) 353207619Srdivacky new (S) T(Elt); 354207619Srdivacky } 355207619Srdivacky 356207619Srdivacky void destroy_range(T *S, T *E) { 357207619Srdivacky while (S != E) { 358207619Srdivacky --E; 359207619Srdivacky E->~T(); 360207619Srdivacky } 361207619Srdivacky } 362207619Srdivacky 363207619Srdivackyprotected: 364207619Srdivacky iterator capacity_ptr() { return (iterator)this->Capacity; } 365207619Srdivacky}; 366207619Srdivacky 367207619Srdivacky// Define this out-of-line to dissuade the C++ compiler from inlining it. 368207619Srdivackytemplate <typename T> 369207619Srdivackyvoid ASTVector<T>::grow(ASTContext &C, size_t MinSize) { 370207619Srdivacky size_t CurCapacity = Capacity-Begin; 371207619Srdivacky size_t CurSize = size(); 372207619Srdivacky size_t NewCapacity = 2*CurCapacity; 373207619Srdivacky if (NewCapacity < MinSize) 374207619Srdivacky NewCapacity = MinSize; 375207619Srdivacky 376207619Srdivacky // Allocate the memory from the ASTContext. 377239462Sdim T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity]; 378207619Srdivacky 379207619Srdivacky // Copy the elements over. 380207619Srdivacky if (llvm::is_class<T>::value) { 381207619Srdivacky std::uninitialized_copy(Begin, End, NewElts); 382207619Srdivacky // Destroy the original elements. 383207619Srdivacky destroy_range(Begin, End); 384207619Srdivacky } 385207619Srdivacky else { 386207619Srdivacky // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 387207619Srdivacky memcpy(NewElts, Begin, CurSize * sizeof(T)); 388207619Srdivacky } 389207619Srdivacky 390239462Sdim // ASTContext never frees any memory. 391207619Srdivacky Begin = NewElts; 392207619Srdivacky End = NewElts+CurSize; 393207619Srdivacky Capacity = Begin+NewCapacity; 394207619Srdivacky} 395207619Srdivacky 396207619Srdivacky} // end: clang namespace 397207619Srdivacky#endif 398