19c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek//===- ASTVector.h - Vector that uses ASTContext for allocation --*- C++ -*-=// 29c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// 39c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// The LLVM Compiler Infrastructure 49c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// 59c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// This file is distributed under the University of Illinois Open Source 69c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// License. See LICENSE.TXT for details. 79c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// 89c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek//===----------------------------------------------------------------------===// 99c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// 109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// This file provides ASTVector, a vector ADT whose contents are 119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// allocated using the allocator associated with an ASTContext.. 129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// 139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek//===----------------------------------------------------------------------===// 149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h. 169c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// We can refactor this core logic into something common. 179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 189c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#ifndef LLVM_CLANG_AST_VECTOR 199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#define LLVM_CLANG_AST_VECTOR 209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include "llvm/Support/type_traits.h" 229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include "llvm/Support/Allocator.h" 239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include "llvm/ADT/PointerIntPair.h" 249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include <algorithm> 259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include <memory> 269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include <cstring> 279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#ifdef _MSC_VER 299c9bd84383f742513b3cfd656948bab16d752937Ted Kremeneknamespace std { 309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#if _MSC_VER <= 1310 319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Work around flawed VC++ implementation of std::uninitialized_copy. Define 329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // additional overloads so that elements with pointer types are recognized as 339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // scalars and not objects, causing bizarre type conversion errors. 349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<class T1, class T2> 359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { 369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek _Scalar_ptr_iterator_tag _Cat; 379c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return _Cat; 389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<class T1, class T2> 419c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { 429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek _Scalar_ptr_iterator_tag _Cat; 439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return _Cat; 449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#else 469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // FIXME: It is not clear if the problem is fixed in VS 2005. What is clear 479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // is that the above hack won't work if it wasn't fixed. 489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#endif 499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek} 509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#endif 519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 529c9bd84383f742513b3cfd656948bab16d752937Ted Kremeneknamespace clang { 539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenektemplate<typename T> 559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekclass ASTVector { 569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *Begin, *End, *Capacity; 579c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void setEnd(T *P) { this->End = P; } 599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekpublic: 619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Default ctor - Initialize to empty. 629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek explicit ASTVector(ASTContext &C, unsigned N = 0) 639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek : Begin(NULL), End(NULL), Capacity(NULL) { 649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reserve(C, N); 659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 679c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek ~ASTVector() { 689c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (llvm::is_class<T>::value) { 699c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Destroy the constructed elements in the vector. 709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek destroy_range(Begin, End); 719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef size_t size_type; 759c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef ptrdiff_t difference_type; 769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T value_type; 779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T* iterator; 789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef const T* const_iterator; 799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 809c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 829c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 839c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T& reference; 849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef const T& const_reference; 859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T* pointer; 869c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef const T* const_pointer; 879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // forward iterator creation methods. 899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator begin() { return Begin; } 909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_iterator begin() const { return Begin; } 919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator end() { return End; } 929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_iterator end() const { return End; } 939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // reverse iterator creation methods. 959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reverse_iterator rbegin() { return reverse_iterator(end()); } 969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reverse_iterator rend() { return reverse_iterator(begin()); } 989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 999c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek bool empty() const { return Begin == End; } 1019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_type size() const { return End-Begin; } 1029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reference operator[](unsigned idx) { 1049c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek assert(Begin + idx < End); 1059c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return Begin[idx]; 1069c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1079c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reference operator[](unsigned idx) const { 1089c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek assert(Begin + idx < End); 1099c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return Begin[idx]; 1109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reference front() { 1139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return begin()[0]; 1149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reference front() const { 1169c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return begin()[0]; 1179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1189c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reference back() { 1209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return end()[-1]; 1219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reference back() const { 1239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return end()[-1]; 1249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void pop_back() { 1279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek --End; 1289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek End->~T(); 1299c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T pop_back_val() { 1329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T Result = back(); 1339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek pop_back(); 1349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return Result; 1359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1379c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void clear() { 1389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (llvm::is_class<T>::value) { 1399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek destroy_range(Begin, End); 1409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1419c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek End = Begin; 1429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek pointer data() { 1469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return pointer(Begin); 1479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_pointer data() const { 1519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return const_pointer(Begin); 1529c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void push_back(const_reference Elt, ASTContext &C) { 1559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (End < Capacity) { 1569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Retry: 1579c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek new (End) T(Elt); 1589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek ++End; 1599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return; 1609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek grow(C); 1629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek goto Retry; 1639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void reserve(ASTContext &C, unsigned N) { 1669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (unsigned(Capacity-Begin) < N) 1679c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek grow(C, N); 1689c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1699c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// capacity - Return the total number of elements in the currently allocated 1719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// buffer. 1729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t capacity() const { return Capacity - Begin; } 1739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// append - Add the specified range to the end of the SmallVector. 1759c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// 1769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<typename in_iter> 1779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void append(ASTContext &C, in_iter in_start, in_iter in_end) { 1789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_type NumInputs = std::distance(in_start, in_end); 179b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek 180b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek if (NumInputs == 0) 181b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek return; 182b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek 1839c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Grow allocated space if needed. 1849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (NumInputs > size_type(this->capacity_ptr()-this->end())) 1859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C, this->size()+NumInputs); 1869c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the new elements over. 1889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // TODO: NEED To compile time dispatch on whether in_iter is a random access 1899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // iterator to use the fast uninitialized_copy. 1909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_copy(in_start, in_end, this->end()); 1919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumInputs); 1929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// append - Add the specified range to the end of the SmallVector. 1959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// 1969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void append(ASTContext &C, size_type NumInputs, const T &Elt) { 1979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Grow allocated space if needed. 1989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (NumInputs > size_type(this->capacity_ptr()-this->end())) 1999c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C, this->size()+NumInputs); 2009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the new elements over. 2029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_fill_n(this->end(), NumInputs, Elt); 2039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumInputs); 2049c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2059c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2069c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 2079c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// starting with "Dest", constructing elements into it as needed. 2089c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<typename It1, typename It2> 2099c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 2109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_copy(I, E, Dest); 2119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator insert(ASTContext &C, iterator I, const T &Elt) { 2149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (I == this->end()) { // Important special case for empty vector. 2159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek push_back(Elt); 2169c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return this->end()-1; 2179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2189c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (this->EndX < this->CapacityX) { 2209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Retry: 2219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek new (this->end()) T(this->back()); 2229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end()+1); 2239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Push everything else over. 2249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy_backward(I, this->end()-1, this->end()); 2259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek *I = Elt; 2269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 2279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t EltNo = I-this->begin(); 2299c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C); 2309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek I = this->begin()+EltNo; 2319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek goto Retry; 2329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator insert(ASTContext &C, iterator I, size_type NumToInsert, 2359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const T &Elt) { 2369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (I == this->end()) { // Important special case for empty vector. 2379c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, NumToInsert, Elt); 2389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return this->end()-1; 2399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2419c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Convert iterator to elt# to avoid invalidating iterator when we reserve() 2429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t InsertElt = I - this->begin(); 2439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Ensure there is enough space. 2459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 2469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Uninvalidate the iterator. 2489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek I = this->begin()+InsertElt; 2499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // If there are more elements between the insertion point and the end of the 2519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // range than there are being inserted, we can use a simple approach to 2529c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // insertion. Since we already reserved space, we know that this won't 2539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // reallocate the vector. 2549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (size_t(this->end()-I) >= NumToInsert) { 2559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 2569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, this->end()-NumToInsert, this->end()); 2579c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the existing elements that get replaced. 2599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 2609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::fill_n(I, NumToInsert, Elt); 2629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 2639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Otherwise, we're inserting more elements than exist already, and we're 2669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // not inserting at the end. 2679c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2689c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy over the elements that we're about to overwrite. 2699c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 2709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumToInsert); 2719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NumOverwritten = OldEnd-I; 2729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 2739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Replace the overwritten part. 2759c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::fill_n(I, NumOverwritten, Elt); 2769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Insert the non-overwritten middle part. 2789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 2799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 2809c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2829c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<typename ItTy> 2839c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator insert(ASTContext &C, iterator I, ItTy From, ItTy To) { 2849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (I == this->end()) { // Important special case for empty vector. 2859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, From, To); 2869c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return this->end()-1; 2879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NumToInsert = std::distance(From, To); 2909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Convert iterator to elt# to avoid invalidating iterator when we reserve() 2919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t InsertElt = I - this->begin(); 2929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Ensure there is enough space. 2949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 2959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Uninvalidate the iterator. 2979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek I = this->begin()+InsertElt; 2989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2999c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // If there are more elements between the insertion point and the end of the 3009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // range than there are being inserted, we can use a simple approach to 3019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // insertion. Since we already reserved space, we know that this won't 3029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // reallocate the vector. 3039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (size_t(this->end()-I) >= NumToInsert) { 3049c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 3059c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, this->end()-NumToInsert, this->end()); 3069c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3079c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the existing elements that get replaced. 3089c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 3099c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy(From, To, I); 3119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 3129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Otherwise, we're inserting more elements than exist already, and we're 3159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // not inserting at the end. 3169c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy over the elements that we're about to overwrite. 3189c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 3199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumToInsert); 3209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NumOverwritten = OldEnd-I; 3219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 3229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Replace the overwritten part. 3249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek for (; NumOverwritten > 0; --NumOverwritten) { 3259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek *I = *From; 3269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek ++I; ++From; 3279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3299c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Insert the non-overwritten middle part. 3309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->uninitialized_copy(From, To, OldEnd); 3319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 3329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void resize(ASTContext &C, unsigned N, const T &NV) { 3359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (N < this->size()) { 3369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->destroy_range(this->begin()+N, this->end()); 3379c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->begin()+N); 3389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } else if (N > this->size()) { 3399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (this->capacity() < N) 3409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C, N); 3419c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek construct_range(this->end(), this->begin()+N, NV); 3429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->begin()+N); 3439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekprivate: 3479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// grow - double the size of the allocated memory, guaranteeing space for at 3489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// least one more element or MinSize if specified. 3499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void grow(ASTContext &C, size_type MinSize = 1); 3509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void construct_range(T *S, T *E, const T &Elt) { 3529c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek for (; S != E; ++S) 3539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek new (S) T(Elt); 3549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void destroy_range(T *S, T *E) { 3579c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek while (S != E) { 3589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek --E; 3599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek E->~T(); 3609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekprotected: 3649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator capacity_ptr() { return (iterator)this->Capacity; } 3659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek}; 3669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3679c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// Define this out-of-line to dissuade the C++ compiler from inlining it. 3689c9bd84383f742513b3cfd656948bab16d752937Ted Kremenektemplate <typename T> 3699c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekvoid ASTVector<T>::grow(ASTContext &C, size_t MinSize) { 3709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t CurCapacity = Capacity-Begin; 3719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t CurSize = size(); 3729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NewCapacity = 2*CurCapacity; 3739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (NewCapacity < MinSize) 3749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek NewCapacity = MinSize; 3759c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Allocate the memory from the ASTContext. 377478851c3ed6bd784e7377dffd8e57b200c1b9ba9Benjamin Kramer T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity]; 3789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the elements over. 3809c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (llvm::is_class<T>::value) { 3819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_copy(Begin, End, NewElts); 3829c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Destroy the original elements. 3839c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek destroy_range(Begin, End); 3849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek else { 3869c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 3879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek memcpy(NewElts, Begin, CurSize * sizeof(T)); 3889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 390478851c3ed6bd784e7377dffd8e57b200c1b9ba9Benjamin Kramer // ASTContext never frees any memory. 3919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Begin = NewElts; 3929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek End = NewElts+CurSize; 3939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Capacity = Begin+NewCapacity; 3949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek} 3959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek} // end: clang namespace 3979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#endif 398