19d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===// 29d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// 39d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// The LLVM Compiler Infrastructure 49d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// 59d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// This file is distributed under the University of Illinois Open Source 69d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// License. See LICENSE.TXT for details. 79d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner// 89d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner//===----------------------------------------------------------------------===// 99d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 109d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#ifndef LLVM_ADT_TINYPTRVECTOR_H 119d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#define LLVM_ADT_TINYPTRVECTOR_H 129d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 13ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#include "llvm/ADT/ArrayRef.h" 149d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#include "llvm/ADT/PointerUnion.h" 15147d9e05116518461653695a6022f6109f0eb936Chandler Carruth#include "llvm/ADT/SmallVector.h" 169d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 179d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnernamespace llvm { 18f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 199d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// TinyPtrVector - This class is specialized for cases where there are 209d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// normally 0 or 1 element in a vector, but is general enough to go beyond that 219d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// when required. 229d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// 239d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// NOTE: This container doesn't allow you to store a null pointer into it. 249d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner/// 259d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnertemplate <typename EltTy> 269d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnerclass TinyPtrVector { 279d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattnerpublic: 289d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner typedef llvm::SmallVector<EltTy, 4> VecTy; 2940dab1059e72d3af59f2523fa8a7d05f40dafca5Chandler Carruth typedef typename VecTy::value_type value_type; 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef llvm::PointerUnion<EltTy, VecTy *> PtrUnion; 3140dab1059e72d3af59f2523fa8a7d05f40dafca5Chandler Carruth 32ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesprivate: 33ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PtrUnion Val; 34b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 35ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinespublic: 369d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner TinyPtrVector() {} 3706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth ~TinyPtrVector() { 3806bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (VecTy *V = Val.template dyn_cast<VecTy*>()) 3906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth delete V; 4006bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 4106bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth 429d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 439d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (VecTy *V = Val.template dyn_cast<VecTy*>()) 449d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = new VecTy(*V); 459d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 4606bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth TinyPtrVector &operator=(const TinyPtrVector &RHS) { 4706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (this == &RHS) 4806bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 4906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (RHS.empty()) { 5006bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth this->clear(); 5106bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 5206bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 5306bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth 5406bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth // Try to squeeze into the single slot. If it won't fit, allocate a copied 5506bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth // vector. 5606bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (Val.template is<EltTy>()) { 5706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (RHS.size() == 1) 5806bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth Val = RHS.front(); 5906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth else 6006bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth Val = new VecTy(*RHS.Val.template get<VecTy*>()); 6106bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 6206bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 6306bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth 6406bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth // If we have a full vector allocated, try to re-use it. 6506bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (RHS.Val.template is<EltTy>()) { 6606bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth Val.template get<VecTy*>()->clear(); 6706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth Val.template get<VecTy*>()->push_back(RHS.front()); 6806bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } else { 6906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>(); 7006bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 7106bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 7206bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 7306bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth 74ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.Val = (EltTy)nullptr; 76ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer } 7706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth TinyPtrVector &operator=(TinyPtrVector &&RHS) { 7806bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (this == &RHS) 7906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 8006bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (RHS.empty()) { 8106bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth this->clear(); 8206bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 8306bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 8406bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth 8506bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth // If this vector has been allocated on the heap, re-use it if cheap. If it 8606bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth // would require more copying, just delete it and we'll steal the other 8706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth // side. 8806bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (VecTy *V = Val.template dyn_cast<VecTy*>()) { 8906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth if (RHS.Val.template is<EltTy>()) { 9006bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth V->clear(); 9106bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth V->push_back(RHS.front()); 9206bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 9306bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 949d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner delete V; 9506bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth } 9606bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth 9706bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth Val = RHS.Val; 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHS.Val = (EltTy)nullptr; 9906bd8ca8c276d9bc20b192188224e1e5215666a0Chandler Carruth return *this; 1009d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 101b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 102ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Constructor from an ArrayRef. 103ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// 104ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// This also is a constructor for individual array elements due to the single 105ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// element constructor for ArrayRef. 106ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines explicit TinyPtrVector(ArrayRef<EltTy> Elts) 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : Val(Elts.empty() 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ? PtrUnion() 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : Elts.size() == 1 110de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ? PtrUnion(Elts[0]) 111de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TinyPtrVector(size_t Count, EltTy Value) 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : Val(Count == 0 ? PtrUnion() 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : Count == 1 ? PtrUnion(Value) 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar : PtrUnion(new VecTy(Count, Value))) {} 117ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 118266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner // implicit conversion operator to ArrayRef. 119266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner operator ArrayRef<EltTy>() const { 120266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner if (Val.isNull()) 12137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return None; 122266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner if (Val.template is<EltTy>()) 123bb9dbb7d6b4f39b74b755795e31b219a5518dd77Eli Friedman return *Val.getAddrOfPtr1(); 124ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *Val.template get<VecTy*>(); 125ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 126ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 127ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // implicit conversion operator to MutableArrayRef. 128ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines operator MutableArrayRef<EltTy>() { 129ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Val.isNull()) 130ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return None; 131ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Val.template is<EltTy>()) 132ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *Val.getAddrOfPtr1(); 133266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner return *Val.template get<VecTy*>(); 134266451dd95b12323fad9418df9b217918ec7e9e0Chris Lattner } 135b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*. 137de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template<typename U, 138de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typename std::enable_if< 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value, 140de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool>::type = false> 141de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar operator ArrayRef<U>() const { 142de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return operator ArrayRef<EltTy>(); 143de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 144de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1459d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner bool empty() const { 14622e522e08640be459f237796009cf7666d6d75e7Chris Lattner // This vector can be empty if it contains no element, or if it 14722e522e08640be459f237796009cf7666d6d75e7Chris Lattner // contains a pointer to an empty vector. 1489d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (Val.isNull()) return true; 1499d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 1509d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return Vec->empty(); 1519d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return false; 1529d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 153b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 1549d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner unsigned size() const { 1559d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (empty()) 1569d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return 0; 15722e522e08640be459f237796009cf7666d6d75e7Chris Lattner if (Val.template is<EltTy>()) 1589d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return 1; 15922e522e08640be459f237796009cf7666d6d75e7Chris Lattner return Val.template get<VecTy*>()->size(); 1609d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 161b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 162bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis typedef EltTy *iterator; 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef const EltTy *const_iterator; 164de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef std::reverse_iterator<iterator> reverse_iterator; 165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 166bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 167bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis iterator begin() { 16879976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner if (Val.template is<EltTy>()) 1690db235a2b0ed6ae5c3c870012061906054b6dbc4Argyrios Kyrtzidis return Val.getAddrOfPtr1(); 170b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 17179976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return Val.template get<VecTy *>()->begin(); 17279976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner } 173bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis iterator end() { 17479976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner if (Val.template is<EltTy>()) 17540dab1059e72d3af59f2523fa8a7d05f40dafca5Chandler Carruth return begin() + (Val.isNull() ? 0 : 1); 176b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 17779976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner return Val.template get<VecTy *>()->end(); 17879976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner } 17979976a40728c8baa8cd16de90173fe2c48937e22Chris Lattner 180bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis const_iterator begin() const { 181bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 182bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 183bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 184bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis const_iterator end() const { 185bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 186bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 187bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 188de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar reverse_iterator rbegin() { return reverse_iterator(end()); } 189de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar reverse_iterator rend() { return reverse_iterator(begin()); } 190de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const_reverse_iterator rbegin() const { 191de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return const_reverse_iterator(end()); 192de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 193de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const_reverse_iterator rend() const { 194de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return const_reverse_iterator(begin()); 195de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 196de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 1979d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner EltTy operator[](unsigned i) const { 1989d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(!Val.isNull() && "can't index into an empty vector"); 1999d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) { 2009d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(i == 0 && "tinyvector index out of range"); 2019d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return V; 2029d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 203b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 204b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth assert(i < Val.template get<VecTy*>()->size() && 2059d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner "tinyvector index out of range"); 20622e522e08640be459f237796009cf7666d6d75e7Chris Lattner return (*Val.template get<VecTy*>())[i]; 2079d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 208b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 2099d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner EltTy front() const { 2109d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner assert(!empty() && "vector empty"); 2119d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) 2129d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return V; 2139d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return Val.template get<VecTy*>()->front(); 2149d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 215b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 2162edc74aa1fb541253f4286a70194960dab69506bChris Lattner EltTy back() const { 2172edc74aa1fb541253f4286a70194960dab69506bChris Lattner assert(!empty() && "vector empty"); 2182edc74aa1fb541253f4286a70194960dab69506bChris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) 2192edc74aa1fb541253f4286a70194960dab69506bChris Lattner return V; 2202edc74aa1fb541253f4286a70194960dab69506bChris Lattner return Val.template get<VecTy*>()->back(); 2212edc74aa1fb541253f4286a70194960dab69506bChris Lattner } 2222edc74aa1fb541253f4286a70194960dab69506bChris Lattner 2239d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner void push_back(EltTy NewVal) { 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(NewVal && "Can't add a null value"); 225b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 2269d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have nothing, add something. 2279d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner if (Val.isNull()) { 2289d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = NewVal; 2299d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner return; 2309d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 231b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 2329d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have a single value, convert to a vector. 23322e522e08640be459f237796009cf7666d6d75e7Chris Lattner if (EltTy V = Val.template dyn_cast<EltTy>()) { 2349d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val = new VecTy(); 2359d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val.template get<VecTy*>()->push_back(V); 2369d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 237b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 2389d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // Add the new value, we know we have a vector. 2399d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Val.template get<VecTy*>()->push_back(NewVal); 2409d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 241b4c28fc93f5149a0bd7967af44c429412e751c56Chandler Carruth 2422edc74aa1fb541253f4286a70194960dab69506bChris Lattner void pop_back() { 2432edc74aa1fb541253f4286a70194960dab69506bChris Lattner // If we have a single value, convert to empty. 2442edc74aa1fb541253f4286a70194960dab69506bChris Lattner if (Val.template is<EltTy>()) 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Val = (EltTy)nullptr; 2462edc74aa1fb541253f4286a70194960dab69506bChris Lattner else if (VecTy *Vec = Val.template get<VecTy*>()) 2472edc74aa1fb541253f4286a70194960dab69506bChris Lattner Vec->pop_back(); 2482edc74aa1fb541253f4286a70194960dab69506bChris Lattner } 2492edc74aa1fb541253f4286a70194960dab69506bChris Lattner 2509d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner void clear() { 2519d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have a single value, convert to empty. 252840635741f132a9a10f052cbf3b21e14bc74835aChris Lattner if (Val.template is<EltTy>()) { 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Val = (EltTy)nullptr; 2549d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 2559d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // If we have a vector form, just clear it. 2569d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner Vec->clear(); 2579d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 2589d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner // Otherwise, we're already empty. 2599d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner } 260bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis 261bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis iterator erase(iterator I) { 2620b1bcbf6b87f19402d8aef1ef9f6e527a07de9d4Chandler Carruth assert(I >= begin() && "Iterator to erase is out of bounds."); 2630b1bcbf6b87f19402d8aef1ef9f6e527a07de9d4Chandler Carruth assert(I < end() && "Erasing at past-the-end iterator."); 2640b1bcbf6b87f19402d8aef1ef9f6e527a07de9d4Chandler Carruth 265bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis // If we have a single value, convert to empty. 266bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis if (Val.template is<EltTy>()) { 267bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis if (I == begin()) 268dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Val = (EltTy)nullptr; 269bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 270bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis // multiple items in a vector; just do the erase, there is no 271bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis // benefit to collapsing back to a pointer 272bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis return Vec->erase(I); 273bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 27440dab1059e72d3af59f2523fa8a7d05f40dafca5Chandler Carruth return end(); 275bb07f21c76f011d8dde491104ff242af30bfb4abArgyrios Kyrtzidis } 276147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 277147d9e05116518461653695a6022f6109f0eb936Chandler Carruth iterator erase(iterator S, iterator E) { 278147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(S >= begin() && "Range to erase is out of bounds."); 279147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(S <= E && "Trying to erase invalid range."); 280147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(E <= end() && "Trying to erase past the end."); 281147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 282147d9e05116518461653695a6022f6109f0eb936Chandler Carruth if (Val.template is<EltTy>()) { 283147d9e05116518461653695a6022f6109f0eb936Chandler Carruth if (S == begin() && S != E) 284dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Val = (EltTy)nullptr; 285147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 286147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return Vec->erase(S, E); 287147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 288147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return end(); 289147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 290147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 291147d9e05116518461653695a6022f6109f0eb936Chandler Carruth iterator insert(iterator I, const EltTy &Elt) { 292147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(I >= this->begin() && "Insertion iterator is out of bounds."); 293147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(I <= this->end() && "Inserting past the end of the vector."); 294147d9e05116518461653695a6022f6109f0eb936Chandler Carruth if (I == end()) { 295147d9e05116518461653695a6022f6109f0eb936Chandler Carruth push_back(Elt); 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::prev(end()); 297147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 298147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(!Val.isNull() && "Null value with non-end insert iterator."); 299147d9e05116518461653695a6022f6109f0eb936Chandler Carruth if (EltTy V = Val.template dyn_cast<EltTy>()) { 300147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(I == begin()); 301147d9e05116518461653695a6022f6109f0eb936Chandler Carruth Val = Elt; 302147d9e05116518461653695a6022f6109f0eb936Chandler Carruth push_back(V); 303147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return begin(); 304147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 305147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 306147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return Val.template get<VecTy*>()->insert(I, Elt); 307147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 308147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 309147d9e05116518461653695a6022f6109f0eb936Chandler Carruth template<typename ItTy> 310147d9e05116518461653695a6022f6109f0eb936Chandler Carruth iterator insert(iterator I, ItTy From, ItTy To) { 311147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(I >= this->begin() && "Insertion iterator is out of bounds."); 312147d9e05116518461653695a6022f6109f0eb936Chandler Carruth assert(I <= this->end() && "Inserting past the end of the vector."); 313147d9e05116518461653695a6022f6109f0eb936Chandler Carruth if (From == To) 314147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return I; 315147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 316147d9e05116518461653695a6022f6109f0eb936Chandler Carruth // If we have a single value, convert to a vector. 317147d9e05116518461653695a6022f6109f0eb936Chandler Carruth ptrdiff_t Offset = I - begin(); 318147d9e05116518461653695a6022f6109f0eb936Chandler Carruth if (Val.isNull()) { 31936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(From) == To) { 320147d9e05116518461653695a6022f6109f0eb936Chandler Carruth Val = *From; 321147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return begin(); 322147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 323147d9e05116518461653695a6022f6109f0eb936Chandler Carruth 324147d9e05116518461653695a6022f6109f0eb936Chandler Carruth Val = new VecTy(); 325147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } else if (EltTy V = Val.template dyn_cast<EltTy>()) { 326147d9e05116518461653695a6022f6109f0eb936Chandler Carruth Val = new VecTy(); 327147d9e05116518461653695a6022f6109f0eb936Chandler Carruth Val.template get<VecTy*>()->push_back(V); 328147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 329147d9e05116518461653695a6022f6109f0eb936Chandler Carruth return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); 330147d9e05116518461653695a6022f6109f0eb936Chandler Carruth } 3319d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner}; 3329d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner} // end namespace llvm 3339d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner 3349d69d4aadd4a58aba5634d5c3d2c2a6d8d284134Chris Lattner#endif 335