1226584Sdim//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===// 2226584Sdim// 3226584Sdim// The LLVM Compiler Infrastructure 4226584Sdim// 5226584Sdim// This file is distributed under the University of Illinois Open Source 6226584Sdim// License. See LICENSE.TXT for details. 7226584Sdim// 8226584Sdim//===----------------------------------------------------------------------===// 9226584Sdim 10226584Sdim#ifndef LLVM_ADT_TINYPTRVECTOR_H 11226584Sdim#define LLVM_ADT_TINYPTRVECTOR_H 12226584Sdim 13239462Sdim#include "llvm/ADT/ArrayRef.h" 14239462Sdim#include "llvm/ADT/PointerUnion.h" 15239462Sdim#include "llvm/ADT/STLExtras.h" 16226584Sdim#include "llvm/ADT/SmallVector.h" 17239462Sdim#include "llvm/Support/Compiler.h" 18226584Sdim 19226584Sdimnamespace llvm { 20226584Sdim 21226584Sdim/// TinyPtrVector - This class is specialized for cases where there are 22226584Sdim/// normally 0 or 1 element in a vector, but is general enough to go beyond that 23226584Sdim/// when required. 24226584Sdim/// 25226584Sdim/// NOTE: This container doesn't allow you to store a null pointer into it. 26226584Sdim/// 27226584Sdimtemplate <typename EltTy> 28226584Sdimclass TinyPtrVector { 29226584Sdimpublic: 30226584Sdim typedef llvm::SmallVector<EltTy, 4> VecTy; 31239462Sdim typedef typename VecTy::value_type value_type; 32239462Sdim 33226584Sdim llvm::PointerUnion<EltTy, VecTy*> Val; 34239462Sdim 35226584Sdim TinyPtrVector() {} 36239462Sdim ~TinyPtrVector() { 37239462Sdim if (VecTy *V = Val.template dyn_cast<VecTy*>()) 38239462Sdim delete V; 39239462Sdim } 40239462Sdim 41226584Sdim TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 42226584Sdim if (VecTy *V = Val.template dyn_cast<VecTy*>()) 43226584Sdim Val = new VecTy(*V); 44226584Sdim } 45239462Sdim TinyPtrVector &operator=(const TinyPtrVector &RHS) { 46239462Sdim if (this == &RHS) 47239462Sdim return *this; 48239462Sdim if (RHS.empty()) { 49239462Sdim this->clear(); 50239462Sdim return *this; 51239462Sdim } 52239462Sdim 53239462Sdim // Try to squeeze into the single slot. If it won't fit, allocate a copied 54239462Sdim // vector. 55239462Sdim if (Val.template is<EltTy>()) { 56239462Sdim if (RHS.size() == 1) 57239462Sdim Val = RHS.front(); 58239462Sdim else 59239462Sdim Val = new VecTy(*RHS.Val.template get<VecTy*>()); 60239462Sdim return *this; 61239462Sdim } 62239462Sdim 63239462Sdim // If we have a full vector allocated, try to re-use it. 64239462Sdim if (RHS.Val.template is<EltTy>()) { 65239462Sdim Val.template get<VecTy*>()->clear(); 66239462Sdim Val.template get<VecTy*>()->push_back(RHS.front()); 67239462Sdim } else { 68239462Sdim *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>(); 69239462Sdim } 70239462Sdim return *this; 71239462Sdim } 72239462Sdim 73249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 74239462Sdim TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 75239462Sdim RHS.Val = (EltTy)0; 76239462Sdim } 77239462Sdim TinyPtrVector &operator=(TinyPtrVector &&RHS) { 78239462Sdim if (this == &RHS) 79239462Sdim return *this; 80239462Sdim if (RHS.empty()) { 81239462Sdim this->clear(); 82239462Sdim return *this; 83239462Sdim } 84239462Sdim 85239462Sdim // If this vector has been allocated on the heap, re-use it if cheap. If it 86239462Sdim // would require more copying, just delete it and we'll steal the other 87239462Sdim // side. 88239462Sdim if (VecTy *V = Val.template dyn_cast<VecTy*>()) { 89239462Sdim if (RHS.Val.template is<EltTy>()) { 90239462Sdim V->clear(); 91239462Sdim V->push_back(RHS.front()); 92239462Sdim return *this; 93239462Sdim } 94226584Sdim delete V; 95239462Sdim } 96239462Sdim 97239462Sdim Val = RHS.Val; 98239462Sdim RHS.Val = (EltTy)0; 99239462Sdim return *this; 100226584Sdim } 101239462Sdim#endif 102239462Sdim 103234353Sdim // implicit conversion operator to ArrayRef. 104234353Sdim operator ArrayRef<EltTy>() const { 105234353Sdim if (Val.isNull()) 106234353Sdim return ArrayRef<EltTy>(); 107234353Sdim if (Val.template is<EltTy>()) 108234353Sdim return *Val.getAddrOfPtr1(); 109234353Sdim return *Val.template get<VecTy*>(); 110234353Sdim } 111239462Sdim 112226584Sdim bool empty() const { 113226584Sdim // This vector can be empty if it contains no element, or if it 114226584Sdim // contains a pointer to an empty vector. 115226584Sdim if (Val.isNull()) return true; 116226584Sdim if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 117226584Sdim return Vec->empty(); 118226584Sdim return false; 119226584Sdim } 120239462Sdim 121226584Sdim unsigned size() const { 122226584Sdim if (empty()) 123226584Sdim return 0; 124226584Sdim if (Val.template is<EltTy>()) 125226584Sdim return 1; 126226584Sdim return Val.template get<VecTy*>()->size(); 127226584Sdim } 128239462Sdim 129234353Sdim typedef const EltTy *const_iterator; 130234353Sdim typedef EltTy *iterator; 131234353Sdim 132234353Sdim iterator begin() { 133226584Sdim if (Val.template is<EltTy>()) 134234353Sdim return Val.getAddrOfPtr1(); 135239462Sdim 136226584Sdim return Val.template get<VecTy *>()->begin(); 137226584Sdim 138226584Sdim } 139234353Sdim iterator end() { 140226584Sdim if (Val.template is<EltTy>()) 141239462Sdim return begin() + (Val.isNull() ? 0 : 1); 142239462Sdim 143226584Sdim return Val.template get<VecTy *>()->end(); 144226584Sdim } 145226584Sdim 146234353Sdim const_iterator begin() const { 147234353Sdim return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 148234353Sdim } 149234353Sdim 150234353Sdim const_iterator end() const { 151234353Sdim return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 152234353Sdim } 153234353Sdim 154226584Sdim EltTy operator[](unsigned i) const { 155226584Sdim assert(!Val.isNull() && "can't index into an empty vector"); 156226584Sdim if (EltTy V = Val.template dyn_cast<EltTy>()) { 157226584Sdim assert(i == 0 && "tinyvector index out of range"); 158226584Sdim return V; 159226584Sdim } 160239462Sdim 161239462Sdim assert(i < Val.template get<VecTy*>()->size() && 162226584Sdim "tinyvector index out of range"); 163226584Sdim return (*Val.template get<VecTy*>())[i]; 164226584Sdim } 165239462Sdim 166226584Sdim EltTy front() const { 167226584Sdim assert(!empty() && "vector empty"); 168226584Sdim if (EltTy V = Val.template dyn_cast<EltTy>()) 169226584Sdim return V; 170226584Sdim return Val.template get<VecTy*>()->front(); 171226584Sdim } 172239462Sdim 173239462Sdim EltTy back() const { 174239462Sdim assert(!empty() && "vector empty"); 175239462Sdim if (EltTy V = Val.template dyn_cast<EltTy>()) 176239462Sdim return V; 177239462Sdim return Val.template get<VecTy*>()->back(); 178239462Sdim } 179239462Sdim 180226584Sdim void push_back(EltTy NewVal) { 181226584Sdim assert(NewVal != 0 && "Can't add a null value"); 182239462Sdim 183226584Sdim // If we have nothing, add something. 184226584Sdim if (Val.isNull()) { 185226584Sdim Val = NewVal; 186226584Sdim return; 187226584Sdim } 188239462Sdim 189226584Sdim // If we have a single value, convert to a vector. 190226584Sdim if (EltTy V = Val.template dyn_cast<EltTy>()) { 191226584Sdim Val = new VecTy(); 192226584Sdim Val.template get<VecTy*>()->push_back(V); 193226584Sdim } 194239462Sdim 195226584Sdim // Add the new value, we know we have a vector. 196226584Sdim Val.template get<VecTy*>()->push_back(NewVal); 197226584Sdim } 198239462Sdim 199239462Sdim void pop_back() { 200239462Sdim // If we have a single value, convert to empty. 201239462Sdim if (Val.template is<EltTy>()) 202239462Sdim Val = (EltTy)0; 203239462Sdim else if (VecTy *Vec = Val.template get<VecTy*>()) 204239462Sdim Vec->pop_back(); 205239462Sdim } 206239462Sdim 207226584Sdim void clear() { 208226584Sdim // If we have a single value, convert to empty. 209226584Sdim if (Val.template is<EltTy>()) { 210226584Sdim Val = (EltTy)0; 211226584Sdim } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 212226584Sdim // If we have a vector form, just clear it. 213226584Sdim Vec->clear(); 214226584Sdim } 215226584Sdim // Otherwise, we're already empty. 216226584Sdim } 217234353Sdim 218234353Sdim iterator erase(iterator I) { 219239462Sdim assert(I >= begin() && "Iterator to erase is out of bounds."); 220239462Sdim assert(I < end() && "Erasing at past-the-end iterator."); 221239462Sdim 222234353Sdim // If we have a single value, convert to empty. 223234353Sdim if (Val.template is<EltTy>()) { 224234353Sdim if (I == begin()) 225234353Sdim Val = (EltTy)0; 226234353Sdim } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 227234353Sdim // multiple items in a vector; just do the erase, there is no 228234353Sdim // benefit to collapsing back to a pointer 229234353Sdim return Vec->erase(I); 230234353Sdim } 231239462Sdim return end(); 232239462Sdim } 233234353Sdim 234239462Sdim iterator erase(iterator S, iterator E) { 235239462Sdim assert(S >= begin() && "Range to erase is out of bounds."); 236239462Sdim assert(S <= E && "Trying to erase invalid range."); 237239462Sdim assert(E <= end() && "Trying to erase past the end."); 238239462Sdim 239239462Sdim if (Val.template is<EltTy>()) { 240239462Sdim if (S == begin() && S != E) 241239462Sdim Val = (EltTy)0; 242239462Sdim } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 243239462Sdim return Vec->erase(S, E); 244239462Sdim } 245239462Sdim return end(); 246234353Sdim } 247239462Sdim 248239462Sdim iterator insert(iterator I, const EltTy &Elt) { 249239462Sdim assert(I >= this->begin() && "Insertion iterator is out of bounds."); 250239462Sdim assert(I <= this->end() && "Inserting past the end of the vector."); 251239462Sdim if (I == end()) { 252239462Sdim push_back(Elt); 253239462Sdim return llvm::prior(end()); 254239462Sdim } 255239462Sdim assert(!Val.isNull() && "Null value with non-end insert iterator."); 256239462Sdim if (EltTy V = Val.template dyn_cast<EltTy>()) { 257239462Sdim assert(I == begin()); 258239462Sdim Val = Elt; 259239462Sdim push_back(V); 260239462Sdim return begin(); 261239462Sdim } 262239462Sdim 263239462Sdim return Val.template get<VecTy*>()->insert(I, Elt); 264239462Sdim } 265239462Sdim 266239462Sdim template<typename ItTy> 267239462Sdim iterator insert(iterator I, ItTy From, ItTy To) { 268239462Sdim assert(I >= this->begin() && "Insertion iterator is out of bounds."); 269239462Sdim assert(I <= this->end() && "Inserting past the end of the vector."); 270239462Sdim if (From == To) 271239462Sdim return I; 272239462Sdim 273239462Sdim // If we have a single value, convert to a vector. 274239462Sdim ptrdiff_t Offset = I - begin(); 275239462Sdim if (Val.isNull()) { 276239462Sdim if (llvm::next(From) == To) { 277239462Sdim Val = *From; 278239462Sdim return begin(); 279239462Sdim } 280239462Sdim 281239462Sdim Val = new VecTy(); 282239462Sdim } else if (EltTy V = Val.template dyn_cast<EltTy>()) { 283239462Sdim Val = new VecTy(); 284239462Sdim Val.template get<VecTy*>()->push_back(V); 285239462Sdim } 286239462Sdim return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); 287239462Sdim } 288226584Sdim}; 289226584Sdim} // end namespace llvm 290226584Sdim 291226584Sdim#endif 292