ASTVector.h revision 2fa67efeaf66a9332c30a026dc1c21bef6c33a6c
15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)//===- ASTVector.h - Vector that uses ASTContext for allocation --*- C++ -*-=// 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// The LLVM Compiler Infrastructure 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// License. See LICENSE.TXT for details. 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)//===----------------------------------------------------------------------===// 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This file provides ASTVector, a vector ADT whose contents are 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// allocated using the allocator associated with an ASTContext.. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)//===----------------------------------------------------------------------===// 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// FIXME: Most of this is copy-and-paste from BumpVector.h and SmallVector.h. 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// We can refactor this core logic into something common. 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef LLVM_CLANG_AST_VECTOR 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define LLVM_CLANG_AST_VECTOR 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "clang/AST/ASTContext.h" 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "llvm/Support/type_traits.h" 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "llvm/Support/Allocator.h" 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "llvm/ADT/PointerIntPair.h" 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <algorithm> 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <memory> 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include <cstring> 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifdef _MSC_VER 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace std { 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#if _MSC_VER <= 1310 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Work around flawed VC++ implementation of std::uninitialized_copy. Define 33f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu // additional overloads so that elements with pointer types are recognized as 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // scalars and not objects, causing bizarre type conversion errors. 358abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) template<class T1, class T2> 36926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { 37926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) _Scalar_ptr_iterator_tag _Cat; 38aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch return _Cat; 3909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) } 40aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch 41aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch template<class T1, class T2> 4253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { 4343e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) _Scalar_ptr_iterator_tag _Cat; 4453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return _Cat; 450019e4eead4d990e4304c54a9028aca9122fb256Ben Murdoch } 4653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)#else 471e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // FIXME: It is not clear if the problem is fixed in VS 2005. What is clear 48f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) // is that the above hack won't work if it wasn't fixed. 4909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif 50d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)} 51d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)#endif 52d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) 53e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdochnamespace clang { 54e69819bd8e388ea4ad1636a19aa6b2eed4952191Ben Murdoch 5553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)template<typename T> 5653e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles)class ASTVector { 5753e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) T *Begin, *End, *Capacity; 585267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 59d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) void setEnd(T *P) { this->End = P; } 60f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) 61d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)public: 621e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Default ctor - Initialize to empty. 631e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) ASTVector() : Begin(NULL), End(NULL), Capacity(NULL) { } 64a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles) 655267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) ASTVector(ASTContext &C, unsigned N) 665267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) : Begin(NULL), End(NULL), Capacity(NULL) { 675267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) reserve(C, N); 68bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) } 695267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) 70bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) ~ASTVector() { 71f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu if (llvm::is_class<T>::value) { 72f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu // Destroy the constructed elements in the vector. 73f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu destroy_range(Begin, End); 74f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu } 75f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu } 76f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 77f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef size_t size_type; 78f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef ptrdiff_t difference_type; 79f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef T value_type; 80f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef T* iterator; 81f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef const T* const_iterator; 82f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 83f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 84f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef std::reverse_iterator<iterator> reverse_iterator; 85f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 86f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef T& reference; 87f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef const T& const_reference; 88f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef T* pointer; 89f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu typedef const T* const_pointer; 90f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 91591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch // forward iterator creation methods. 92d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) iterator begin() { return Begin; } 93f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu const_iterator begin() const { return Begin; } 94f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu iterator end() { return End; } 951e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) const_iterator end() const { return End; } 96f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // reverse iterator creation methods. 9851b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) reverse_iterator rbegin() { return reverse_iterator(end()); } 99926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 100926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) reverse_iterator rend() { return reverse_iterator(begin()); } 101926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 103591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch bool empty() const { return Begin == End; } 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_type size() const { return End-Begin; } 10551b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) 10651b2906e11752df6c18351cf520e30522d3b53a1Torne (Richard Coles) reference operator[](unsigned idx) { 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) assert(Begin + idx < End); 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Begin[idx]; 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 110f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) const_reference operator[](unsigned idx) const { 111f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) assert(Begin + idx < End); 112926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return Begin[idx]; 113926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 114926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 115926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) reference front() { 116926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return begin()[0]; 117926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 118f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu const_reference front() const { 11953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) return begin()[0]; 12043e7502580f146aa5b3db8267ba6dbb5c733a489Torne (Richard Coles) } 12153e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) 12253e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) reference back() { 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return end()[-1]; 1241e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const_reference back() const { 126926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return end()[-1]; 127926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 128926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 129926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void pop_back() { 130926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) --End; 131926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) End->~T(); 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 133926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T pop_back_val() { 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T Result = back(); 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) pop_back(); 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Result; 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void clear() { 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (llvm::is_class<T>::value) { 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) destroy_range(Begin, End); 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) End = Begin; 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 146aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch 147aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch /// data - Return a pointer to the vector's buffer, even if empty(). 148aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch pointer data() { 149aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch return pointer(Begin); 150aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch } 151aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch 152aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch /// data - Return a pointer to the vector's buffer, even if empty(). 153aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch const_pointer data() const { 154aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch return const_pointer(Begin); 155aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch } 156aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch 157aafa69cb17c9d6606c07663ade5f81388a2c5986Ben Murdoch void push_back(const_reference Elt, ASTContext &C) { 1581e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (End < Capacity) { 15953e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) Retry: 1601e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) new (End) T(Elt); 1611e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) ++End; 1621e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) return; 1631e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 16453e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) grow(C); 16553e740f4a82e17f3ae59772501622dc354e42336Torne (Richard Coles) goto Retry; 1661e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 1671e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 1681e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) void reserve(ASTContext &C, unsigned N) { 1691e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (unsigned(Capacity-Begin) < N) 1701e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) grow(C, N); 1711e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 172c0e19a689c8ac22cdc96b291a8d33a5d3b0b34a4Torne (Richard Coles) 173f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) /// capacity - Return the total number of elements in the currently allocated 174f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) /// buffer. 175f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) size_t capacity() const { return Capacity - Begin; } 176f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) 177f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) /// append - Add the specified range to the end of the SmallVector. 178f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) /// 179f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) template<typename in_iter> 180f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) void append(ASTContext &C, in_iter in_start, in_iter in_end) { 181f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) size_type NumInputs = std::distance(in_start, in_end); 182f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) 183f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles) if (NumInputs == 0) 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Grow allocated space if needed. 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (NumInputs > size_type(this->capacity_ptr()-this->end())) 1888abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) this->grow(C, this->size()+NumInputs); 1898abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 1908abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) // Copy the new elements over. 1918abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) // TODO: NEED To compile time dispatch on whether in_iter is a random access 1928abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) // iterator to use the fast uninitialized_copy. 1938abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) std::uninitialized_copy(in_start, in_end, this->end()); 1948abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) this->setEnd(this->end() + NumInputs); 1958abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) } 1968abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 1978abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) /// append - Add the specified range to the end of the SmallVector. 1988abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) /// 1998abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) void append(ASTContext &C, size_type NumInputs, const T &Elt) { 2008abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) // Grow allocated space if needed. 2018abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) if (NumInputs > size_type(this->capacity_ptr()-this->end())) 2028abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) this->grow(C, this->size()+NumInputs); 2038abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Copy the new elements over. 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::uninitialized_fill_n(this->end(), NumInputs, Elt); 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->setEnd(this->end() + NumInputs); 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) /// starting with "Dest", constructing elements into it as needed. 2111e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) template<typename It1, typename It2> 2121e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::uninitialized_copy(I, E, Dest); 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2151e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator insert(ASTContext &C, iterator I, const T &Elt) { 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (I == this->end()) { // Important special case for empty vector. 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) push_back(Elt); 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this->end()-1; 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this->EndX < this->CapacityX) { 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Retry: 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new (this->end()) T(this->back()); 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->setEnd(this->end()+1); 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Push everything else over. 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::copy_backward(I, this->end()-1, this->end()); 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *I = Elt; 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return I; 2301e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 2311e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t EltNo = I-this->begin(); 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->grow(C); 2338abfc5808a4e34d6e03867af8bc440dee641886fTorne (Richard Coles) I = this->begin()+EltNo; 2346f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch goto Retry; 2356f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch } 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator insert(ASTContext &C, iterator I, size_type NumToInsert, 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const T &Elt) { 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (I == this->end()) { // Important special case for empty vector. 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) append(C, NumToInsert, Elt); 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this->end()-1; 2421e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 2431e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Convert iterator to elt# to avoid invalidating iterator when we reserve() 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t InsertElt = I - this->begin(); 2461e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2471e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Ensure there is enough space. 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Uninvalidate the iterator. 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) I = this->begin()+InsertElt; 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If there are more elements between the insertion point and the end of the 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // range than there are being inserted, we can use a simple approach to 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // insertion. Since we already reserved space, we know that this won't 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // reallocate the vector. 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size_t(this->end()-I) >= NumToInsert) { 25802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch T *OldEnd = this->end(); 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) append(C, this->end()-NumToInsert, this->end()); 2601e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2611e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Copy the existing elements that get replaced. 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2641e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) std::fill_n(I, NumToInsert, Elt); 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return I; 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2671e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Otherwise, we're inserting more elements than exist already, and we're 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // not inserting at the end. 2701e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Copy over the elements that we're about to overwrite. 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) T *OldEnd = this->end(); 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->setEnd(this->end() + NumToInsert); 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t NumOverwritten = OldEnd-I; 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Replace the overwritten part. 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::fill_n(I, NumOverwritten, Elt); 2791e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2801e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Insert the non-overwritten middle part. 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return I; 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2841e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename ItTy> 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) iterator insert(ASTContext &C, iterator I, ItTy From, ItTy To) { 2871e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (I == this->end()) { // Important special case for empty vector. 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) append(C, From, To); 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this->end()-1; 2901e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) size_t NumToInsert = std::distance(From, To); 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Convert iterator to elt# to avoid invalidating iterator when we reserve() 294bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) size_t InsertElt = I - this->begin(); 295bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 296bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Ensure there is enough space. 297bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 298bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 299bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Uninvalidate the iterator. 300bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) I = this->begin()+InsertElt; 301bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 302bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // If there are more elements between the insertion point and the end of the 303bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // range than there are being inserted, we can use a simple approach to 304bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // insertion. Since we already reserved space, we know that this won't 305bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // reallocate the vector. 306bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) if (size_t(this->end()-I) >= NumToInsert) { 307bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) T *OldEnd = this->end(); 308bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) append(C, this->end()-NumToInsert, this->end()); 309bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 310bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Copy the existing elements that get replaced. 311bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 312bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 313bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) std::copy(From, To, I); 314bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) return I; 315bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) } 316bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 317bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Otherwise, we're inserting more elements than exist already, and we're 318bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // not inserting at the end. 319bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 320bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Copy over the elements that we're about to overwrite. 321bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) T *OldEnd = this->end(); 322bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) this->setEnd(this->end() + NumToInsert); 323bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) size_t NumOverwritten = OldEnd-I; 324bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 325bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 326bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Replace the overwritten part. 327bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) for (; NumOverwritten > 0; --NumOverwritten) { 328bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) *I = *From; 329bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) ++I; ++From; 330bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) } 331bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 332bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) // Insert the non-overwritten middle part. 333d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles) this->uninitialized_copy(From, To, OldEnd); 3341e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) return I; 3351e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 336a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch 3371e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) void resize(ASTContext &C, unsigned N, const T &NV) { 338a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch if (N < this->size()) { 3391e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) this->destroy_range(this->begin()+N, this->end()); 3401e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) this->setEnd(this->begin()+N); 3411e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } else if (N > this->size()) { 342a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch if (this->capacity() < N) 3431e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) this->grow(C, N); 3441e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) construct_range(this->end(), this->begin()+N, NV); 3451e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) this->setEnd(this->begin()+N); 3461e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 3471e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 3481e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3491e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)private: 3501e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) /// grow - double the size of the allocated memory, guaranteeing space for at 3511e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) /// least one more element or MinSize if specified. 3521e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) void grow(ASTContext &C, size_type MinSize = 1); 3531e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3541e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) void construct_range(T *S, T *E, const T &Elt) { 3551e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) for (; S != E; ++S) 3561e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) new (S) T(Elt); 3571e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 3581e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3591e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) void destroy_range(T *S, T *E) { 3601e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) while (S != E) { 3611e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) --E; 3621e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) E->~T(); 363a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch } 3641e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 3651e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3661e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)protected: 3671e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) iterator capacity_ptr() { return (iterator)this->Capacity; } 3681e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)}; 3691e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3701e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)// Define this out-of-line to dissuade the C++ compiler from inlining it. 3711e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)template <typename T> 3721e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)void ASTVector<T>::grow(ASTContext &C, size_t MinSize) { 3731e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t CurCapacity = Capacity-Begin; 3741e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t CurSize = size(); 3751e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) size_t NewCapacity = 2*CurCapacity; 3761e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (NewCapacity < MinSize) 3771e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) NewCapacity = MinSize; 3781e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3791e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Allocate the memory from the ASTContext. 3801e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity]; 3811e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3821e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Copy the elements over. 3831e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) if (llvm::is_class<T>::value) { 3841e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) std::uninitialized_copy(Begin, End, NewElts); 3851e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Destroy the original elements. 386d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) destroy_range(Begin, End); 3871e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 388d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles) else { 3891e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 3901e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) memcpy(NewElts, Begin, CurSize * sizeof(T)); 3911e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) } 3921e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3931e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) // ASTContext never frees any memory. 39409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles) Begin = NewElts; 3951e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) End = NewElts+CurSize; 3961e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) Capacity = Begin+NewCapacity; 3971e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)} 3981e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles) 3991e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)} // end: clang namespace 400a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch#endif 4011e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)