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 typedef llvm::PointerUnion<EltTy, VecTy *> PtrUnion; 31 32 private: 33 PtrUnion Val; 34 35 public: 36 TinyPtrVector() {} 37 ~TinyPtrVector() { 38 if (VecTy *V = Val.template dyn_cast<VecTy*>()) 39 delete V; 40 } 41 42 TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 43 if (VecTy *V = Val.template dyn_cast<VecTy*>()) 44 Val = new VecTy(*V); 45 } 46 TinyPtrVector &operator=(const TinyPtrVector &RHS) { 47 if (this == &RHS) 48 return *this; 49 if (RHS.empty()) { 50 this->clear(); 51 return *this; 52 } 53 54 // Try to squeeze into the single slot. If it won't fit, allocate a copied 55 // vector. 56 if (Val.template is<EltTy>()) { 57 if (RHS.size() == 1) 58 Val = RHS.front(); 59 else 60 Val = new VecTy(*RHS.Val.template get<VecTy*>()); 61 return *this; 62 } 63 64 // If we have a full vector allocated, try to re-use it. 65 if (RHS.Val.template is<EltTy>()) { 66 Val.template get<VecTy*>()->clear(); 67 Val.template get<VecTy*>()->push_back(RHS.front()); 68 } else { 69 *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>(); 70 } 71 return *this; 72 } 73 74 TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 75 RHS.Val = (EltTy)nullptr; 76 } 77 TinyPtrVector &operator=(TinyPtrVector &&RHS) { 78 if (this == &RHS) 79 return *this; 80 if (RHS.empty()) { 81 this->clear(); 82 return *this; 83 } 84 85 // If this vector has been allocated on the heap, re-use it if cheap. If it 86 // would require more copying, just delete it and we'll steal the other 87 // side. 88 if (VecTy *V = Val.template dyn_cast<VecTy*>()) { 89 if (RHS.Val.template is<EltTy>()) { 90 V->clear(); 91 V->push_back(RHS.front()); 92 return *this; 93 } 94 delete V; 95 } 96 97 Val = RHS.Val; 98 RHS.Val = (EltTy)nullptr; 99 return *this; 100 } 101 102 /// Constructor from an ArrayRef. 103 /// 104 /// This also is a constructor for individual array elements due to the single 105 /// element constructor for ArrayRef. 106 explicit TinyPtrVector(ArrayRef<EltTy> Elts) 107 : Val(Elts.empty() 108 ? PtrUnion() 109 : Elts.size() == 1 110 ? PtrUnion(Elts[0]) 111 : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} 112 113 TinyPtrVector(size_t Count, EltTy Value) 114 : Val(Count == 0 ? PtrUnion() 115 : Count == 1 ? PtrUnion(Value) 116 : PtrUnion(new VecTy(Count, Value))) {} 117 118 // implicit conversion operator to ArrayRef. 119 operator ArrayRef<EltTy>() const { 120 if (Val.isNull()) 121 return None; 122 if (Val.template is<EltTy>()) 123 return *Val.getAddrOfPtr1(); 124 return *Val.template get<VecTy*>(); 125 } 126 127 // implicit conversion operator to MutableArrayRef. 128 operator MutableArrayRef<EltTy>() { 129 if (Val.isNull()) 130 return None; 131 if (Val.template is<EltTy>()) 132 return *Val.getAddrOfPtr1(); 133 return *Val.template get<VecTy*>(); 134 } 135 136 // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*. 137 template<typename U, 138 typename std::enable_if< 139 std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value, 140 bool>::type = false> 141 operator ArrayRef<U>() const { 142 return operator ArrayRef<EltTy>(); 143 } 144 145 bool empty() const { 146 // This vector can be empty if it contains no element, or if it 147 // contains a pointer to an empty vector. 148 if (Val.isNull()) return true; 149 if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 150 return Vec->empty(); 151 return false; 152 } 153 154 unsigned size() const { 155 if (empty()) 156 return 0; 157 if (Val.template is<EltTy>()) 158 return 1; 159 return Val.template get<VecTy*>()->size(); 160 } 161 162 typedef EltTy *iterator; 163 typedef const EltTy *const_iterator; 164 typedef std::reverse_iterator<iterator> reverse_iterator; 165 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 166 167 iterator begin() { 168 if (Val.template is<EltTy>()) 169 return Val.getAddrOfPtr1(); 170 171 return Val.template get<VecTy *>()->begin(); 172 } 173 iterator end() { 174 if (Val.template is<EltTy>()) 175 return begin() + (Val.isNull() ? 0 : 1); 176 177 return Val.template get<VecTy *>()->end(); 178 } 179 180 const_iterator begin() const { 181 return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 182 } 183 184 const_iterator end() const { 185 return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 186 } 187 188 reverse_iterator rbegin() { return reverse_iterator(end()); } 189 reverse_iterator rend() { return reverse_iterator(begin()); } 190 const_reverse_iterator rbegin() const { 191 return const_reverse_iterator(end()); 192 } 193 const_reverse_iterator rend() const { 194 return const_reverse_iterator(begin()); 195 } 196 197 EltTy operator[](unsigned i) const { 198 assert(!Val.isNull() && "can't index into an empty vector"); 199 if (EltTy V = Val.template dyn_cast<EltTy>()) { 200 assert(i == 0 && "tinyvector index out of range"); 201 return V; 202 } 203 204 assert(i < Val.template get<VecTy*>()->size() && 205 "tinyvector index out of range"); 206 return (*Val.template get<VecTy*>())[i]; 207 } 208 209 EltTy front() const { 210 assert(!empty() && "vector empty"); 211 if (EltTy V = Val.template dyn_cast<EltTy>()) 212 return V; 213 return Val.template get<VecTy*>()->front(); 214 } 215 216 EltTy back() const { 217 assert(!empty() && "vector empty"); 218 if (EltTy V = Val.template dyn_cast<EltTy>()) 219 return V; 220 return Val.template get<VecTy*>()->back(); 221 } 222 223 void push_back(EltTy NewVal) { 224 assert(NewVal && "Can't add a null value"); 225 226 // If we have nothing, add something. 227 if (Val.isNull()) { 228 Val = NewVal; 229 return; 230 } 231 232 // If we have a single value, convert to a vector. 233 if (EltTy V = Val.template dyn_cast<EltTy>()) { 234 Val = new VecTy(); 235 Val.template get<VecTy*>()->push_back(V); 236 } 237 238 // Add the new value, we know we have a vector. 239 Val.template get<VecTy*>()->push_back(NewVal); 240 } 241 242 void pop_back() { 243 // If we have a single value, convert to empty. 244 if (Val.template is<EltTy>()) 245 Val = (EltTy)nullptr; 246 else if (VecTy *Vec = Val.template get<VecTy*>()) 247 Vec->pop_back(); 248 } 249 250 void clear() { 251 // If we have a single value, convert to empty. 252 if (Val.template is<EltTy>()) { 253 Val = (EltTy)nullptr; 254 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 255 // If we have a vector form, just clear it. 256 Vec->clear(); 257 } 258 // Otherwise, we're already empty. 259 } 260 261 iterator erase(iterator I) { 262 assert(I >= begin() && "Iterator to erase is out of bounds."); 263 assert(I < end() && "Erasing at past-the-end iterator."); 264 265 // If we have a single value, convert to empty. 266 if (Val.template is<EltTy>()) { 267 if (I == begin()) 268 Val = (EltTy)nullptr; 269 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 270 // multiple items in a vector; just do the erase, there is no 271 // benefit to collapsing back to a pointer 272 return Vec->erase(I); 273 } 274 return end(); 275 } 276 277 iterator erase(iterator S, iterator E) { 278 assert(S >= begin() && "Range to erase is out of bounds."); 279 assert(S <= E && "Trying to erase invalid range."); 280 assert(E <= end() && "Trying to erase past the end."); 281 282 if (Val.template is<EltTy>()) { 283 if (S == begin() && S != E) 284 Val = (EltTy)nullptr; 285 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 286 return Vec->erase(S, E); 287 } 288 return end(); 289 } 290 291 iterator insert(iterator I, const EltTy &Elt) { 292 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 293 assert(I <= this->end() && "Inserting past the end of the vector."); 294 if (I == end()) { 295 push_back(Elt); 296 return std::prev(end()); 297 } 298 assert(!Val.isNull() && "Null value with non-end insert iterator."); 299 if (EltTy V = Val.template dyn_cast<EltTy>()) { 300 assert(I == begin()); 301 Val = Elt; 302 push_back(V); 303 return begin(); 304 } 305 306 return Val.template get<VecTy*>()->insert(I, Elt); 307 } 308 309 template<typename ItTy> 310 iterator insert(iterator I, ItTy From, ItTy To) { 311 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 312 assert(I <= this->end() && "Inserting past the end of the vector."); 313 if (From == To) 314 return I; 315 316 // If we have a single value, convert to a vector. 317 ptrdiff_t Offset = I - begin(); 318 if (Val.isNull()) { 319 if (std::next(From) == To) { 320 Val = *From; 321 return begin(); 322 } 323 324 Val = new VecTy(); 325 } else if (EltTy V = Val.template dyn_cast<EltTy>()) { 326 Val = new VecTy(); 327 Val.template get<VecTy*>()->push_back(V); 328 } 329 return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); 330 } 331 }; 332 } // end namespace llvm 333 334 #endif 335
