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 211bf43cae5d3175838242060cbbc08f6f4fce3536Benjamin Kramer#include "clang/AST/AttrIterator.h" 229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include "llvm/ADT/PointerIntPair.h" 2330a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/Support/Allocator.h" 2430a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include "llvm/Support/type_traits.h" 259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include <algorithm> 269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#include <cstring> 2730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth#include <memory> 289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 299c9bd84383f742513b3cfd656948bab16d752937Ted Kremeneknamespace clang { 301bf43cae5d3175838242060cbbc08f6f4fce3536Benjamin Kramer class ASTContext; 319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenektemplate<typename T> 339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekclass ASTVector { 34c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smithprivate: 35c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith T *Begin, *End; 36c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith llvm::PointerIntPair<T*, 1, bool> Capacity; 379c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void setEnd(T *P) { this->End = P; } 399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 40c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smithprotected: 41c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith // Make a tag bit available to users of this class. 42c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith // FIXME: This is a horrible hack. 43c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith bool getTag() const { return Capacity.getInt(); } 44c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith void setTag(bool B) { Capacity.setInt(B); } 45c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith 469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekpublic: 479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Default ctor - Initialize to empty. 486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ASTVector() : Begin(nullptr), End(nullptr), Capacity(nullptr, false) {} 496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ASTVector(ASTVector &&O) : Begin(O.Begin), End(O.End), Capacity(O.Capacity) { 516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines O.Begin = O.End = nullptr; 526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines O.Capacity.setPointer(nullptr); 536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines O.Capacity.setInt(false); 546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 552a82ca255b0f99f6201a75ed52b91fc024f6e9cfArgyrios Kyrtzidis 5605ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper ASTVector(const ASTContext &C, unsigned N) 576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : Begin(nullptr), End(nullptr), Capacity(nullptr, false) { 589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reserve(C, N); 599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ASTVector &operator=(ASTVector &&RHS) { 626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ASTVector O(std::move(RHS)); 636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines using std::swap; 646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines swap(Begin, O.Begin); 656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines swap(End, O.End); 666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines swap(Capacity, O.Capacity); 676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return *this; 686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek ~ASTVector() { 71651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (std::is_class<T>::value) { 729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Destroy the constructed elements in the vector. 739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek destroy_range(Begin, End); 749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 759c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef size_t size_type; 789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef ptrdiff_t difference_type; 799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T value_type; 809c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T* iterator; 819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef const T* const_iterator; 829c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 839c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 869c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T& reference; 879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef const T& const_reference; 889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef T* pointer; 899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek typedef const T* const_pointer; 909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // forward iterator creation methods. 929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator begin() { return Begin; } 939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_iterator begin() const { return Begin; } 949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek iterator end() { return End; } 959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_iterator end() const { return End; } 969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // reverse iterator creation methods. 989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reverse_iterator rbegin() { return reverse_iterator(end()); } 999c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } 1009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reverse_iterator rend() { return reverse_iterator(begin()); } 1019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reverse_iterator rend() const { return const_reverse_iterator(begin());} 1029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek bool empty() const { return Begin == End; } 1049c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_type size() const { return End-Begin; } 1059c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1069c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reference operator[](unsigned idx) { 1079c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek assert(Begin + idx < End); 1089c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return Begin[idx]; 1099c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reference operator[](unsigned idx) const { 1119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek assert(Begin + idx < End); 1129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return Begin[idx]; 1139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reference front() { 1169c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return begin()[0]; 1179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1189c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reference front() const { 1199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return begin()[0]; 1209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reference back() { 1239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return end()[-1]; 1249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_reference back() const { 1269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return end()[-1]; 1279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1299c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void pop_back() { 1309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek --End; 1319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek End->~T(); 1329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T pop_back_val() { 1359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T Result = back(); 1369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek pop_back(); 1379c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return Result; 1389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void clear() { 141651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (std::is_class<T>::value) { 1429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek destroy_range(Begin, End); 1439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek End = Begin; 1459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek pointer data() { 1499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return pointer(Begin); 1509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1529c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// data - Return a pointer to the vector's buffer, even if empty(). 1539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const_pointer data() const { 1549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return const_pointer(Begin); 1559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 15705ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper void push_back(const_reference Elt, const ASTContext &C) { 158c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith if (End < this->capacity_ptr()) { 1599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Retry: 1609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek new (End) T(Elt); 1619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek ++End; 1629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return; 1639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek grow(C); 1659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek goto Retry; 1669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1679c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 16805ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper void reserve(const ASTContext &C, unsigned N) { 169c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith if (unsigned(this->capacity_ptr()-Begin) < N) 1709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek grow(C, N); 1719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// capacity - Return the total number of elements in the currently allocated 1749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// buffer. 175c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith size_t capacity() const { return this->capacity_ptr() - Begin; } 1769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// append - Add the specified range to the end of the SmallVector. 1789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// 1799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<typename in_iter> 18005ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper void append(const ASTContext &C, in_iter in_start, in_iter in_end) { 1819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_type NumInputs = std::distance(in_start, in_end); 182b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek 183b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek if (NumInputs == 0) 184b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek return; 185b13c170a280673f4cf4d7d11ec818392407254d4Ted Kremenek 1869c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Grow allocated space if needed. 1879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (NumInputs > size_type(this->capacity_ptr()-this->end())) 1889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C, this->size()+NumInputs); 1899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the new elements over. 1919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // TODO: NEED To compile time dispatch on whether in_iter is a random access 1929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // iterator to use the fast uninitialized_copy. 1939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_copy(in_start, in_end, this->end()); 1949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumInputs); 1959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 1969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 1979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// append - Add the specified range to the end of the SmallVector. 1989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// 19905ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper void append(const ASTContext &C, size_type NumInputs, const T &Elt) { 2009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Grow allocated space if needed. 2019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (NumInputs > size_type(this->capacity_ptr()-this->end())) 2029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C, this->size()+NumInputs); 2039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2049c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the new elements over. 2059c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_fill_n(this->end(), NumInputs, Elt); 2069c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumInputs); 2079c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2089c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2099c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory 2109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// starting with "Dest", constructing elements into it as needed. 2119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<typename It1, typename It2> 2129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek static void uninitialized_copy(It1 I, It1 E, It2 Dest) { 2139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_copy(I, E, Dest); 2149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 21605ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper iterator insert(const ASTContext &C, iterator I, const T &Elt) { 2179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (I == this->end()) { // Important special case for empty vector. 218f475bf83a45435a211edb4e0ef6ac3481ce7b3feDavid Blaikie push_back(Elt, C); 2199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return this->end()-1; 2209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 222c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith if (this->End < this->capacity_ptr()) { 2239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Retry: 2249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek new (this->end()) T(this->back()); 2259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end()+1); 2269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Push everything else over. 2279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy_backward(I, this->end()-1, this->end()); 2289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek *I = Elt; 2299c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 2309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t EltNo = I-this->begin(); 2329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C); 2339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek I = this->begin()+EltNo; 2349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek goto Retry; 2359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 23705ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper iterator insert(const ASTContext &C, iterator I, size_type NumToInsert, 2389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek const T &Elt) { 2399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (I == this->end()) { // Important special case for empty vector. 2409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, NumToInsert, Elt); 2419c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return this->end()-1; 2429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Convert iterator to elt# to avoid invalidating iterator when we reserve() 2459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t InsertElt = I - this->begin(); 2469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Ensure there is enough space. 2489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 2499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Uninvalidate the iterator. 2519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek I = this->begin()+InsertElt; 2529c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // If there are more elements between the insertion point and the end of the 2549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // range than there are being inserted, we can use a simple approach to 2559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // insertion. Since we already reserved space, we know that this won't 2569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // reallocate the vector. 2579c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (size_t(this->end()-I) >= NumToInsert) { 2589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 2599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, this->end()-NumToInsert, this->end()); 2609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the existing elements that get replaced. 2629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 2639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::fill_n(I, NumToInsert, Elt); 2659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 2669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2679c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2689c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Otherwise, we're inserting more elements than exist already, and we're 2699c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // not inserting at the end. 2709c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy over the elements that we're about to overwrite. 2729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 2739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumToInsert); 2749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NumOverwritten = OldEnd-I; 2759c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 2769c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Replace the overwritten part. 2789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::fill_n(I, NumOverwritten, Elt); 2799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2809c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Insert the non-overwritten middle part. 2819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); 2829c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 2839c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek template<typename ItTy> 28605ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper iterator insert(const ASTContext &C, iterator I, ItTy From, ItTy To) { 2879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (I == this->end()) { // Important special case for empty vector. 2889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, From, To); 2899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return this->end()-1; 2909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 2919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NumToInsert = std::distance(From, To); 2939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Convert iterator to elt# to avoid invalidating iterator when we reserve() 2949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t InsertElt = I - this->begin(); 2959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2969c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Ensure there is enough space. 2979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek reserve(C, static_cast<unsigned>(this->size() + NumToInsert)); 2989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 2999c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Uninvalidate the iterator. 3009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek I = this->begin()+InsertElt; 3019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // If there are more elements between the insertion point and the end of the 3039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // range than there are being inserted, we can use a simple approach to 3049c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // insertion. Since we already reserved space, we know that this won't 3059c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // reallocate the vector. 3069c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (size_t(this->end()-I) >= NumToInsert) { 3079c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 3089c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek append(C, this->end()-NumToInsert, this->end()); 3099c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3109c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the existing elements that get replaced. 3119c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy_backward(I, OldEnd-NumToInsert, OldEnd); 3129c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3139c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::copy(From, To, I); 3149c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 3159c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3169c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3179c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Otherwise, we're inserting more elements than exist already, and we're 3189c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // not inserting at the end. 3199c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3209c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy over the elements that we're about to overwrite. 3219c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek T *OldEnd = this->end(); 3229c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->end() + NumToInsert); 3239c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NumOverwritten = OldEnd-I; 3249c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten); 3259c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3269c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Replace the overwritten part. 3279c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek for (; NumOverwritten > 0; --NumOverwritten) { 3289c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek *I = *From; 3299c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek ++I; ++From; 3309c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3319c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3329c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Insert the non-overwritten middle part. 3339c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->uninitialized_copy(From, To, OldEnd); 3349c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek return I; 3359c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3369c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 33705ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper void resize(const ASTContext &C, unsigned N, const T &NV) { 3389c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (N < this->size()) { 3399c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->destroy_range(this->begin()+N, this->end()); 3409c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->begin()+N); 3419c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } else if (N > this->size()) { 3429c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (this->capacity() < N) 3439c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->grow(C, N); 3449c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek construct_range(this->end(), this->begin()+N, NV); 3459c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek this->setEnd(this->begin()+N); 3469c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3479c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3489c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3499c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekprivate: 3509c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// grow - double the size of the allocated memory, guaranteeing space for at 3519c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek /// least one more element or MinSize if specified. 35205ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Topper void grow(const ASTContext &C, size_type MinSize = 1); 3539c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3549c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void construct_range(T *S, T *E, const T &Elt) { 3559c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek for (; S != E; ++S) 3569c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek new (S) T(Elt); 3579c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3589c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3599c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek void destroy_range(T *S, T *E) { 3609c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek while (S != E) { 3619c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek --E; 3629c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek E->~T(); 3639c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3649c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3659c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3669c9bd84383f742513b3cfd656948bab16d752937Ted Kremenekprotected: 367c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith const_iterator capacity_ptr() const { 368c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith return (iterator) Capacity.getPointer(); 369c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith } 370c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith iterator capacity_ptr() { return (iterator)Capacity.getPointer(); } 3719c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek}; 3729c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3739c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek// Define this out-of-line to dissuade the C++ compiler from inlining it. 3749c9bd84383f742513b3cfd656948bab16d752937Ted Kremenektemplate <typename T> 37505ed1a0587edcf3b8ee84a67d8c8ca76753d1fc1Craig Toppervoid ASTVector<T>::grow(const ASTContext &C, size_t MinSize) { 376c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith size_t CurCapacity = this->capacity(); 3779c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t CurSize = size(); 3789c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek size_t NewCapacity = 2*CurCapacity; 3799c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek if (NewCapacity < MinSize) 3809c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek NewCapacity = MinSize; 3819c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3829c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Allocate the memory from the ASTContext. 383478851c3ed6bd784e7377dffd8e57b200c1b9ba9Benjamin Kramer T *NewElts = new (C, llvm::alignOf<T>()) T[NewCapacity]; 3849c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 3859c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Copy the elements over. 386651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (std::is_class<T>::value) { 3879c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek std::uninitialized_copy(Begin, End, NewElts); 3889c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Destroy the original elements. 3899c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek destroy_range(Begin, End); 3909c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3919c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek else { 3929c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). 3939c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek memcpy(NewElts, Begin, CurSize * sizeof(T)); 3949c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek } 3959c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 396478851c3ed6bd784e7377dffd8e57b200c1b9ba9Benjamin Kramer // ASTContext never frees any memory. 3979c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek Begin = NewElts; 3989c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek End = NewElts+CurSize; 399c2d775714f79af977672e4f1dbc16ee9e02d1deaRichard Smith Capacity.setPointer(Begin+NewCapacity); 4009c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek} 4019c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek 4029c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek} // end: clang namespace 4039c9bd84383f742513b3cfd656948bab16d752937Ted Kremenek#endif 404