1 //===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_ADT_TINYPTRVECTOR_H 11 #define LLVM_ADT_TINYPTRVECTOR_H 12 13 #include "llvm/ADT/ArrayRef.h" 14 #include "llvm/ADT/PointerUnion.h" 15 #include "llvm/ADT/SmallVector.h" 16 17 namespace llvm { 18 19 /// TinyPtrVector - This class is specialized for cases where there are 20 /// normally 0 or 1 element in a vector, but is general enough to go beyond that 21 /// when required. 22 /// 23 /// NOTE: This container doesn't allow you to store a null pointer into it. 24 /// 25 template <typename EltTy> 26 class TinyPtrVector { 27 public: 28 typedef llvm::SmallVector<EltTy, 4> VecTy; 29 typedef typename VecTy::value_type value_type; 30 31 llvm::PointerUnion<EltTy, VecTy*> Val; 32 TinyPtrVector()33 TinyPtrVector() {} ~TinyPtrVector()34 ~TinyPtrVector() { 35 if (VecTy *V = Val.template dyn_cast<VecTy*>()) 36 delete V; 37 } 38 TinyPtrVector(const TinyPtrVector & RHS)39 TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 40 if (VecTy *V = Val.template dyn_cast<VecTy*>()) 41 Val = new VecTy(*V); 42 } 43 TinyPtrVector &operator=(const TinyPtrVector &RHS) { 44 if (this == &RHS) 45 return *this; 46 if (RHS.empty()) { 47 this->clear(); 48 return *this; 49 } 50 51 // Try to squeeze into the single slot. If it won't fit, allocate a copied 52 // vector. 53 if (Val.template is<EltTy>()) { 54 if (RHS.size() == 1) 55 Val = RHS.front(); 56 else 57 Val = new VecTy(*RHS.Val.template get<VecTy*>()); 58 return *this; 59 } 60 61 // If we have a full vector allocated, try to re-use it. 62 if (RHS.Val.template is<EltTy>()) { 63 Val.template get<VecTy*>()->clear(); 64 Val.template get<VecTy*>()->push_back(RHS.front()); 65 } else { 66 *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>(); 67 } 68 return *this; 69 } 70 TinyPtrVector(TinyPtrVector && RHS)71 TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 72 RHS.Val = (EltTy)nullptr; 73 } 74 TinyPtrVector &operator=(TinyPtrVector &&RHS) { 75 if (this == &RHS) 76 return *this; 77 if (RHS.empty()) { 78 this->clear(); 79 return *this; 80 } 81 82 // If this vector has been allocated on the heap, re-use it if cheap. If it 83 // would require more copying, just delete it and we'll steal the other 84 // side. 85 if (VecTy *V = Val.template dyn_cast<VecTy*>()) { 86 if (RHS.Val.template is<EltTy>()) { 87 V->clear(); 88 V->push_back(RHS.front()); 89 return *this; 90 } 91 delete V; 92 } 93 94 Val = RHS.Val; 95 RHS.Val = (EltTy)nullptr; 96 return *this; 97 } 98 99 /// Constructor from a single element. TinyPtrVector(EltTy Elt)100 explicit TinyPtrVector(EltTy Elt) : Val(Elt) {} 101 102 /// Constructor from an ArrayRef. TinyPtrVector(ArrayRef<EltTy> Elts)103 explicit TinyPtrVector(ArrayRef<EltTy> Elts) 104 : Val(new VecTy(Elts.begin(), Elts.end())) {} 105 106 // implicit conversion operator to ArrayRef. 107 operator ArrayRef<EltTy>() const { 108 if (Val.isNull()) 109 return None; 110 if (Val.template is<EltTy>()) 111 return *Val.getAddrOfPtr1(); 112 return *Val.template get<VecTy*>(); 113 } 114 empty()115 bool empty() const { 116 // This vector can be empty if it contains no element, or if it 117 // contains a pointer to an empty vector. 118 if (Val.isNull()) return true; 119 if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 120 return Vec->empty(); 121 return false; 122 } 123 size()124 unsigned size() const { 125 if (empty()) 126 return 0; 127 if (Val.template is<EltTy>()) 128 return 1; 129 return Val.template get<VecTy*>()->size(); 130 } 131 132 typedef const EltTy *const_iterator; 133 typedef EltTy *iterator; 134 begin()135 iterator begin() { 136 if (Val.template is<EltTy>()) 137 return Val.getAddrOfPtr1(); 138 139 return Val.template get<VecTy *>()->begin(); 140 141 } end()142 iterator end() { 143 if (Val.template is<EltTy>()) 144 return begin() + (Val.isNull() ? 0 : 1); 145 146 return Val.template get<VecTy *>()->end(); 147 } 148 begin()149 const_iterator begin() const { 150 return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 151 } 152 end()153 const_iterator end() const { 154 return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 155 } 156 157 EltTy operator[](unsigned i) const { 158 assert(!Val.isNull() && "can't index into an empty vector"); 159 if (EltTy V = Val.template dyn_cast<EltTy>()) { 160 assert(i == 0 && "tinyvector index out of range"); 161 return V; 162 } 163 164 assert(i < Val.template get<VecTy*>()->size() && 165 "tinyvector index out of range"); 166 return (*Val.template get<VecTy*>())[i]; 167 } 168 front()169 EltTy front() const { 170 assert(!empty() && "vector empty"); 171 if (EltTy V = Val.template dyn_cast<EltTy>()) 172 return V; 173 return Val.template get<VecTy*>()->front(); 174 } 175 back()176 EltTy back() const { 177 assert(!empty() && "vector empty"); 178 if (EltTy V = Val.template dyn_cast<EltTy>()) 179 return V; 180 return Val.template get<VecTy*>()->back(); 181 } 182 push_back(EltTy NewVal)183 void push_back(EltTy NewVal) { 184 assert(NewVal && "Can't add a null value"); 185 186 // If we have nothing, add something. 187 if (Val.isNull()) { 188 Val = NewVal; 189 return; 190 } 191 192 // If we have a single value, convert to a vector. 193 if (EltTy V = Val.template dyn_cast<EltTy>()) { 194 Val = new VecTy(); 195 Val.template get<VecTy*>()->push_back(V); 196 } 197 198 // Add the new value, we know we have a vector. 199 Val.template get<VecTy*>()->push_back(NewVal); 200 } 201 pop_back()202 void pop_back() { 203 // If we have a single value, convert to empty. 204 if (Val.template is<EltTy>()) 205 Val = (EltTy)nullptr; 206 else if (VecTy *Vec = Val.template get<VecTy*>()) 207 Vec->pop_back(); 208 } 209 clear()210 void clear() { 211 // If we have a single value, convert to empty. 212 if (Val.template is<EltTy>()) { 213 Val = (EltTy)nullptr; 214 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 215 // If we have a vector form, just clear it. 216 Vec->clear(); 217 } 218 // Otherwise, we're already empty. 219 } 220 erase(iterator I)221 iterator erase(iterator I) { 222 assert(I >= begin() && "Iterator to erase is out of bounds."); 223 assert(I < end() && "Erasing at past-the-end iterator."); 224 225 // If we have a single value, convert to empty. 226 if (Val.template is<EltTy>()) { 227 if (I == begin()) 228 Val = (EltTy)nullptr; 229 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 230 // multiple items in a vector; just do the erase, there is no 231 // benefit to collapsing back to a pointer 232 return Vec->erase(I); 233 } 234 return end(); 235 } 236 erase(iterator S,iterator E)237 iterator erase(iterator S, iterator E) { 238 assert(S >= begin() && "Range to erase is out of bounds."); 239 assert(S <= E && "Trying to erase invalid range."); 240 assert(E <= end() && "Trying to erase past the end."); 241 242 if (Val.template is<EltTy>()) { 243 if (S == begin() && S != E) 244 Val = (EltTy)nullptr; 245 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 246 return Vec->erase(S, E); 247 } 248 return end(); 249 } 250 insert(iterator I,const EltTy & Elt)251 iterator insert(iterator I, const EltTy &Elt) { 252 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 253 assert(I <= this->end() && "Inserting past the end of the vector."); 254 if (I == end()) { 255 push_back(Elt); 256 return std::prev(end()); 257 } 258 assert(!Val.isNull() && "Null value with non-end insert iterator."); 259 if (EltTy V = Val.template dyn_cast<EltTy>()) { 260 assert(I == begin()); 261 Val = Elt; 262 push_back(V); 263 return begin(); 264 } 265 266 return Val.template get<VecTy*>()->insert(I, Elt); 267 } 268 269 template<typename ItTy> insert(iterator I,ItTy From,ItTy To)270 iterator insert(iterator I, ItTy From, ItTy To) { 271 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 272 assert(I <= this->end() && "Inserting past the end of the vector."); 273 if (From == To) 274 return I; 275 276 // If we have a single value, convert to a vector. 277 ptrdiff_t Offset = I - begin(); 278 if (Val.isNull()) { 279 if (std::next(From) == To) { 280 Val = *From; 281 return begin(); 282 } 283 284 Val = new VecTy(); 285 } else if (EltTy V = Val.template dyn_cast<EltTy>()) { 286 Val = new VecTy(); 287 Val.template get<VecTy*>()->push_back(V); 288 } 289 return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); 290 } 291 }; 292 } // end namespace llvm 293 294 #endif 295