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 21249423Sdim#include "clang/AST/AttrIterator.h" 22249423Sdim#include "llvm/ADT/PointerIntPair.h" 23249423Sdim#include "llvm/Support/Allocator.h" 24207619Srdivacky#include "llvm/Support/type_traits.h" 25207619Srdivacky#include <algorithm> 26249423Sdim#include <cstring> 27207619Srdivacky#include <memory> 28207619Srdivacky 29207619Srdivacky#ifdef _MSC_VER 30207619Srdivackynamespace std { 31207619Srdivacky#if _MSC_VER <= 1310 32207619Srdivacky // Work around flawed VC++ implementation of std::uninitialized_copy. Define 33207619Srdivacky // additional overloads so that elements with pointer types are recognized as 34207619Srdivacky // scalars and not objects, causing bizarre type conversion errors. 35207619Srdivacky template<class T1, class T2> 36207619Srdivacky inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { 37207619Srdivacky _Scalar_ptr_iterator_tag _Cat; 38207619Srdivacky return _Cat; 39207619Srdivacky } 40207619Srdivacky 41207619Srdivacky template<class T1, class T2> 42207619Srdivacky inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { 43207619Srdivacky _Scalar_ptr_iterator_tag _Cat; 44207619Srdivacky return _Cat; 45207619Srdivacky } 46207619Srdivacky#else 47207619Srdivacky // FIXME: It is not clear if the problem is fixed in VS 2005. What is clear 48207619Srdivacky // is that the above hack won't work if it wasn't fixed. 49207619Srdivacky#endif 50207619Srdivacky} 51207619Srdivacky#endif 52207619Srdivacky 53207619Srdivackynamespace clang { 54249423Sdim class ASTContext; 55207619Srdivacky 56207619Srdivackytemplate<typename T> 57207619Srdivackyclass ASTVector { 58263508Sdimprivate: 59263508Sdim T *Begin, *End; 60263508Sdim llvm::PointerIntPair<T*, 1, bool> Capacity; 61207619Srdivacky 62207619Srdivacky void setEnd(T *P) { this->End = P; } 63207619Srdivacky 64263508Sdimprotected: 65263508Sdim // Make a tag bit available to users of this class. 66263508Sdim // FIXME: This is a horrible hack. 67263508Sdim bool getTag() const { return Capacity.getInt(); } 68263508Sdim void setTag(bool B) { Capacity.setInt(B); } 69263508Sdim 70207619Srdivackypublic: 71207619Srdivacky // Default ctor - Initialize to empty. 72263508Sdim ASTVector() : Begin(0), End(0), Capacity(0, false) {} 73249423Sdim 74263508Sdim ASTVector(const ASTContext &C, unsigned N) 75263508Sdim : Begin(0), End(0), Capacity(0, false) { 76207619Srdivacky reserve(C, N); 77207619Srdivacky } 78207619Srdivacky 79207619Srdivacky ~ASTVector() { 80207619Srdivacky if (llvm::is_class<T>::value) { 81207619Srdivacky // Destroy the constructed elements in the vector. 82207619Srdivacky destroy_range(Begin, End); 83207619Srdivacky } 84207619Srdivacky } 85207619Srdivacky 86207619Srdivacky typedef size_t size_type; 87207619Srdivacky typedef ptrdiff_t difference_type; 88207619Srdivacky typedef T value_type; 89207619Srdivacky typedef T* iterator; 90207619Srdivacky typedef const T* const_iterator; 91207619Srdivacky 92207619Srdivacky typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 93207619Srdivacky typedef std::reverse_iterator<iterator> reverse_iterator; 94207619Srdivacky 95207619Srdivacky typedef T& reference; 96207619Srdivacky typedef const T& const_reference; 97207619Srdivacky typedef T* pointer; 98207619Srdivacky typedef const T* const_pointer; 99207619Srdivacky 100207619Srdivacky // forward iterator creation methods. 101207619Srdivacky iterator begin() { return Begin; } 102207619Srdivacky const_iterator begin() const { return Begin; } 103207619Srdivacky iterator end() { return End; } 104207619Srdivacky const_iterator end() const { return End; } 105207619Srdivacky 106207619Srdivacky // reverse iterator creation methods. 107207619Srdivacky reverse_iterator rbegin() { return reverse_iterator(end()); } 108207619Srdivacky const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 109207619Srdivacky reverse_iterator rend() { return reverse_iterator(begin()); } 110207619Srdivacky const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 111207619Srdivacky 112207619Srdivacky bool empty() const { return Begin == End; } 113207619Srdivacky size_type size() const { return End-Begin; } 114207619Srdivacky 115207619Srdivacky reference operator[](unsigned idx) { 116207619Srdivacky assert(Begin + idx < End); 117207619Srdivacky return Begin[idx]; 118207619Srdivacky } 119207619Srdivacky const_reference operator[](unsigned idx) const { 120207619Srdivacky assert(Begin + idx < End); 121207619Srdivacky return Begin[idx]; 122207619Srdivacky } 123207619Srdivacky 124207619Srdivacky reference front() { 125207619Srdivacky return begin()[0]; 126207619Srdivacky } 127207619Srdivacky const_reference front() const { 128207619Srdivacky return begin()[0]; 129207619Srdivacky } 130207619Srdivacky 131207619Srdivacky reference back() { 132207619Srdivacky return end()[-1]; 133207619Srdivacky } 134207619Srdivacky const_reference back() const { 135207619Srdivacky return end()[-1]; 136207619Srdivacky } 137207619Srdivacky 138207619Srdivacky void pop_back() { 139207619Srdivacky --End; 140207619Srdivacky End->~T(); 141207619Srdivacky } 142207619Srdivacky 143207619Srdivacky T pop_back_val() { 144207619Srdivacky T Result = back(); 145207619Srdivacky pop_back(); 146207619Srdivacky return Result; 147207619Srdivacky } 148207619Srdivacky 149207619Srdivacky void clear() { 150207619Srdivacky if (llvm::is_class<T>::value) { 151207619Srdivacky destroy_range(Begin, End); 152207619Srdivacky } 153207619Srdivacky End = Begin; 154207619Srdivacky } 155207619Srdivacky 156207619Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 157207619Srdivacky pointer data() { 158207619Srdivacky return pointer(Begin); 159207619Srdivacky } 160207619Srdivacky 161207619Srdivacky /// data - Return a pointer to the vector's buffer, even if empty(). 162207619Srdivacky const_pointer data() const { 163207619Srdivacky return const_pointer(Begin); 164207619Srdivacky } 165207619Srdivacky 166263508Sdim void push_back(const_reference Elt, const ASTContext &C) { 167263508Sdim if (End < this->capacity_ptr()) { 168207619Srdivacky Retry: 169207619Srdivacky new (End) T(Elt); 170207619Srdivacky ++End; 171207619Srdivacky return; 172207619Srdivacky } 173207619Srdivacky grow(C); 174207619Srdivacky goto Retry; 175207619Srdivacky } 176207619Srdivacky 177263508Sdim void reserve(const ASTContext &C, unsigned N) { 178263508Sdim if (unsigned(this->capacity_ptr()-Begin) < N) 179207619Srdivacky grow(C, N); 180207619Srdivacky } 181207619Srdivacky 182207619Srdivacky /// capacity - Return the total number of elements in the currently allocated 183207619Srdivacky /// buffer. 184263508Sdim size_t capacity() const { return this->capacity_ptr() - Begin; } 185207619Srdivacky 186207619Srdivacky /// append - Add the specified range to the end of the SmallVector. 187207619Srdivacky /// 188207619Srdivacky template<typename in_iter> 189263508Sdim void append(const ASTContext &C, in_iter in_start, in_iter in_end) { 190207619Srdivacky size_type NumInputs = std::distance(in_start, in_end); 191207619Srdivacky 192207619Srdivacky if (NumInputs == 0) 193207619Srdivacky return; 194207619Srdivacky 195207619Srdivacky // Grow allocated space if needed. 196207619Srdivacky if (NumInputs > size_type(this->capacity_ptr()-this->end())) 197207619Srdivacky this->grow(C, this->size()+NumInputs); 198207619Srdivacky 199207619Srdivacky // Copy the new elements over. 200207619Srdivacky // TODO: NEED To compile time dispatch on whether in_iter is a random access 201207619Srdivacky // iterator to use the fast uninitialized_copy. 202207619Srdivacky std::uninitialized_copy(in_start, in_end, this->end()); 203207619Srdivacky this->setEnd(this->end() + NumInputs); 204207619Srdivacky } 205207619Srdivacky 206207619Srdivacky /// append - Add the specified range to the end of the SmallVector. 207207619Srdivacky /// 208263508Sdim void append(const ASTContext &C, size_type NumInputs, const T &Elt) { 209207619Srdivacky // Grow allocated space if needed. 210207619Srdivacky if (NumInputs > size_type(this->capacity_ptr()-this->end())) 211207619Srdivacky this->grow(C, this->size()+NumInputs); 212207619Srdivacky 213207619Srdivacky // Copy the new elements over. 214207619Srdivacky std::uninitialized_fill_n(this->end(), NumInputs, Elt); 215207619Srdivacky this->setEnd(this->end() + NumInputs); 216207619Srdivacky } 217207619Srdivacky 218207619Srdivacky /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 219207619Srdivacky /// starting with "Dest", constructing elements into it as needed. 220207619Srdivacky template<typename It1, typename It2> 221207619Srdivacky static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 222207619Srdivacky std::uninitialized_copy(I, E, Dest); 223207619Srdivacky } 224207619Srdivacky 225263508Sdim iterator insert(const ASTContext &C, iterator I, const T &Elt) { 226207619Srdivacky if (I == this->end()) { // Important special case for empty vector. 227263508Sdim push_back(Elt, C); 228207619Srdivacky return this->end()-1; 229207619Srdivacky } 230207619Srdivacky 231263508Sdim if (this->End < this->capacity_ptr()) { 232207619Srdivacky Retry: 233207619Srdivacky new (this->end()) T(this->back()); 234207619Srdivacky this->setEnd(this->end()+1); 235207619Srdivacky // Push everything else over. 236207619Srdivacky std::copy_backward(I, this->end()-1, this->end()); 237207619Srdivacky *I = Elt; 238207619Srdivacky return I; 239207619Srdivacky } 240207619Srdivacky size_t EltNo = I-this->begin(); 241207619Srdivacky this->grow(C); 242207619Srdivacky I = this->begin()+EltNo; 243207619Srdivacky goto Retry; 244207619Srdivacky } 245207619Srdivacky 246263508Sdim iterator insert(const ASTContext &C, iterator I, size_type NumToInsert, 247207619Srdivacky const T &Elt) { 248207619Srdivacky if (I == this->end()) { // Important special case for empty vector. 249207619Srdivacky append(C, NumToInsert, Elt); 250207619Srdivacky return this->end()-1; 251207619Srdivacky } 252207619Srdivacky 253207619Srdivacky // Convert iterator to elt# to avoid invalidating iterator when we reserve() 254207619Srdivacky size_t InsertElt = I - this->begin(); 255207619Srdivacky 256207619Srdivacky // Ensure there is enough space. 257207619Srdivacky reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 258207619Srdivacky 259207619Srdivacky // Uninvalidate the iterator. 260207619Srdivacky I = this->begin()+InsertElt; 261207619Srdivacky 262207619Srdivacky // If there are more elements between the insertion point and the end of the 263207619Srdivacky // range than there are being inserted, we can use a simple approach to 264207619Srdivacky // insertion. Since we already reserved space, we know that this won't 265207619Srdivacky // reallocate the vector. 266207619Srdivacky if (size_t(this->end()-I) >= NumToInsert) { 267207619Srdivacky T *OldEnd = this->end(); 268207619Srdivacky append(C, this->end()-NumToInsert, this->end()); 269207619Srdivacky 270207619Srdivacky // Copy the existing elements that get replaced. 271207619Srdivacky std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 272207619Srdivacky 273207619Srdivacky std::fill_n(I, NumToInsert, Elt); 274207619Srdivacky return I; 275207619Srdivacky } 276207619Srdivacky 277207619Srdivacky // Otherwise, we're inserting more elements than exist already, and we're 278207619Srdivacky // not inserting at the end. 279207619Srdivacky 280207619Srdivacky // Copy over the elements that we're about to overwrite. 281207619Srdivacky T *OldEnd = this->end(); 282207619Srdivacky this->setEnd(this->end() + NumToInsert); 283207619Srdivacky size_t NumOverwritten = OldEnd-I; 284207619Srdivacky this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 285207619Srdivacky 286207619Srdivacky // Replace the overwritten part. 287207619Srdivacky std::fill_n(I, NumOverwritten, Elt); 288207619Srdivacky 289207619Srdivacky // Insert the non-overwritten middle part. 290207619Srdivacky std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 291207619Srdivacky return I; 292207619Srdivacky } 293207619Srdivacky 294207619Srdivacky template<typename ItTy> 295263508Sdim iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) { 296207619Srdivacky if (I == this->end()) { // Important special case for empty vector. 297207619Srdivacky append(C, From, To); 298207619Srdivacky return this->end()-1; 299207619Srdivacky } 300207619Srdivacky 301207619Srdivacky size_t NumToInsert = std::distance(From, To); 302207619Srdivacky // Convert iterator to elt# to avoid invalidating iterator when we reserve() 303207619Srdivacky size_t InsertElt = I - this->begin(); 304207619Srdivacky 305207619Srdivacky // Ensure there is enough space. 306207619Srdivacky reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 307207619Srdivacky 308207619Srdivacky // Uninvalidate the iterator. 309207619Srdivacky I = this->begin()+InsertElt; 310207619Srdivacky 311207619Srdivacky // If there are more elements between the insertion point and the end of the 312207619Srdivacky // range than there are being inserted, we can use a simple approach to 313207619Srdivacky // insertion. Since we already reserved space, we know that this won't 314207619Srdivacky // reallocate the vector. 315207619Srdivacky if (size_t(this->end()-I) >= NumToInsert) { 316207619Srdivacky T *OldEnd = this->end(); 317207619Srdivacky append(C, this->end()-NumToInsert, this->end()); 318207619Srdivacky 319207619Srdivacky // Copy the existing elements that get replaced. 320207619Srdivacky std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 321207619Srdivacky 322207619Srdivacky std::copy(From, To, I); 323207619Srdivacky return I; 324207619Srdivacky } 325207619Srdivacky 326207619Srdivacky // Otherwise, we're inserting more elements than exist already, and we're 327207619Srdivacky // not inserting at the end. 328207619Srdivacky 329207619Srdivacky // Copy over the elements that we're about to overwrite. 330207619Srdivacky T *OldEnd = this->end(); 331207619Srdivacky this->setEnd(this->end() + NumToInsert); 332207619Srdivacky size_t NumOverwritten = OldEnd-I; 333207619Srdivacky this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 334207619Srdivacky 335207619Srdivacky // Replace the overwritten part. 336207619Srdivacky for (; NumOverwritten > 0; --NumOverwritten) { 337207619Srdivacky *I = *From; 338207619Srdivacky ++I; ++From; 339207619Srdivacky } 340207619Srdivacky 341207619Srdivacky // Insert the non-overwritten middle part. 342207619Srdivacky this->uninitialized_copy(From, To, OldEnd); 343207619Srdivacky return I; 344207619Srdivacky } 345207619Srdivacky 346263508Sdim void resize(const ASTContext &C, unsigned N, const T &NV) { 347207619Srdivacky if (N < this->size()) { 348207619Srdivacky this->destroy_range(this->begin()+N, this->end()); 349207619Srdivacky this->setEnd(this->begin()+N); 350207619Srdivacky } else if (N > this->size()) { 351207619Srdivacky if (this->capacity() < N) 352207619Srdivacky this->grow(C, N); 353207619Srdivacky construct_range(this->end(), this->begin()+N, NV); 354207619Srdivacky this->setEnd(this->begin()+N); 355207619Srdivacky } 356207619Srdivacky } 357207619Srdivacky 358207619Srdivackyprivate: 359207619Srdivacky /// grow - double the size of the allocated memory, guaranteeing space for at 360207619Srdivacky /// least one more element or MinSize if specified. 361263508Sdim void grow(const ASTContext &C, size_type MinSize = 1); 362207619Srdivacky 363207619Srdivacky void construct_range(T *S, T *E, const T &Elt) { 364207619Srdivacky for (; S != E; ++S) 365207619Srdivacky new (S) T(Elt); 366207619Srdivacky } 367207619Srdivacky 368207619Srdivacky void destroy_range(T *S, T *E) { 369207619Srdivacky while (S != E) { 370207619Srdivacky --E; 371207619Srdivacky E->~T(); 372207619Srdivacky } 373207619Srdivacky } 374207619Srdivacky 375207619Srdivackyprotected: 376263508Sdim const_iterator capacity_ptr() const { 377263508Sdim return (iterator) Capacity.getPointer(); 378263508Sdim } 379263508Sdim iterator capacity_ptr() { return (iterator)Capacity.getPointer(); } 380207619Srdivacky}; 381207619Srdivacky 382207619Srdivacky// Define this out-of-line to dissuade the C++ compiler from inlining it. 383207619Srdivackytemplate <typename T> 384263508Sdimvoid ASTVector<T>::grow(const ASTContext &C, size_t MinSize) { 385263508Sdim size_t CurCapacity = this->capacity(); 386207619Srdivacky size_t CurSize = size(); 387207619Srdivacky size_t NewCapacity = 2*CurCapacity; 388207619Srdivacky if (NewCapacity < MinSize) 389207619Srdivacky NewCapacity = MinSize; 390207619Srdivacky 391207619Srdivacky // Allocate the memory from the ASTContext. 392239462Sdim T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity]; 393207619Srdivacky 394207619Srdivacky // Copy the elements over. 395207619Srdivacky if (llvm::is_class<T>::value) { 396207619Srdivacky std::uninitialized_copy(Begin, End, NewElts); 397207619Srdivacky // Destroy the original elements. 398207619Srdivacky destroy_range(Begin, End); 399207619Srdivacky } 400207619Srdivacky else { 401207619Srdivacky // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 402207619Srdivacky memcpy(NewElts, Begin, CurSize * sizeof(T)); 403207619Srdivacky } 404207619Srdivacky 405239462Sdim // ASTContext never frees any memory. 406207619Srdivacky Begin = NewElts; 407207619Srdivacky End = NewElts+CurSize; 408263508Sdim Capacity.setPointer(Begin+NewCapacity); 409207619Srdivacky} 410207619Srdivacky 411207619Srdivacky} // end: clang namespace 412207619Srdivacky#endif 413