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 33 TinyPtrVector() {} 34 ~TinyPtrVector() { 35 if (VecTy *V = Val.template dyn_cast<VecTy*>()) 36 delete V; 37 } 38 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 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 // implicit conversion operator to ArrayRef. 100 operator ArrayRef<EltTy>() const { 101 if (Val.isNull()) 102 return ArrayRef<EltTy>(); 103 if (Val.template is<EltTy>()) 104 return *Val.getAddrOfPtr1(); 105 return *Val.template get<VecTy*>(); 106 } 107 108 bool empty() const { 109 // This vector can be empty if it contains no element, or if it 110 // contains a pointer to an empty vector. 111 if (Val.isNull()) return true; 112 if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) 113 return Vec->empty(); 114 return false; 115 } 116 117 unsigned size() const { 118 if (empty()) 119 return 0; 120 if (Val.template is<EltTy>()) 121 return 1; 122 return Val.template get<VecTy*>()->size(); 123 } 124 125 typedef const EltTy *const_iterator; 126 typedef EltTy *iterator; 127 128 iterator begin() { 129 if (Val.template is<EltTy>()) 130 return Val.getAddrOfPtr1(); 131 132 return Val.template get<VecTy *>()->begin(); 133 134 } 135 iterator end() { 136 if (Val.template is<EltTy>()) 137 return begin() + (Val.isNull() ? 0 : 1); 138 139 return Val.template get<VecTy *>()->end(); 140 } 141 142 const_iterator begin() const { 143 return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 144 } 145 146 const_iterator end() const { 147 return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 148 } 149 150 EltTy operator[](unsigned i) const { 151 assert(!Val.isNull() && "can't index into an empty vector"); 152 if (EltTy V = Val.template dyn_cast<EltTy>()) { 153 assert(i == 0 && "tinyvector index out of range"); 154 return V; 155 } 156 157 assert(i < Val.template get<VecTy*>()->size() && 158 "tinyvector index out of range"); 159 return (*Val.template get<VecTy*>())[i]; 160 } 161 162 EltTy front() const { 163 assert(!empty() && "vector empty"); 164 if (EltTy V = Val.template dyn_cast<EltTy>()) 165 return V; 166 return Val.template get<VecTy*>()->front(); 167 } 168 169 EltTy back() const { 170 assert(!empty() && "vector empty"); 171 if (EltTy V = Val.template dyn_cast<EltTy>()) 172 return V; 173 return Val.template get<VecTy*>()->back(); 174 } 175 176 void push_back(EltTy NewVal) { 177 assert(NewVal && "Can't add a null value"); 178 179 // If we have nothing, add something. 180 if (Val.isNull()) { 181 Val = NewVal; 182 return; 183 } 184 185 // If we have a single value, convert to a vector. 186 if (EltTy V = Val.template dyn_cast<EltTy>()) { 187 Val = new VecTy(); 188 Val.template get<VecTy*>()->push_back(V); 189 } 190 191 // Add the new value, we know we have a vector. 192 Val.template get<VecTy*>()->push_back(NewVal); 193 } 194 195 void pop_back() { 196 // If we have a single value, convert to empty. 197 if (Val.template is<EltTy>()) 198 Val = (EltTy)nullptr; 199 else if (VecTy *Vec = Val.template get<VecTy*>()) 200 Vec->pop_back(); 201 } 202 203 void clear() { 204 // If we have a single value, convert to empty. 205 if (Val.template is<EltTy>()) { 206 Val = (EltTy)nullptr; 207 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 208 // If we have a vector form, just clear it. 209 Vec->clear(); 210 } 211 // Otherwise, we're already empty. 212 } 213 214 iterator erase(iterator I) { 215 assert(I >= begin() && "Iterator to erase is out of bounds."); 216 assert(I < end() && "Erasing at past-the-end iterator."); 217 218 // If we have a single value, convert to empty. 219 if (Val.template is<EltTy>()) { 220 if (I == begin()) 221 Val = (EltTy)nullptr; 222 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 223 // multiple items in a vector; just do the erase, there is no 224 // benefit to collapsing back to a pointer 225 return Vec->erase(I); 226 } 227 return end(); 228 } 229 230 iterator erase(iterator S, iterator E) { 231 assert(S >= begin() && "Range to erase is out of bounds."); 232 assert(S <= E && "Trying to erase invalid range."); 233 assert(E <= end() && "Trying to erase past the end."); 234 235 if (Val.template is<EltTy>()) { 236 if (S == begin() && S != E) 237 Val = (EltTy)nullptr; 238 } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { 239 return Vec->erase(S, E); 240 } 241 return end(); 242 } 243 244 iterator insert(iterator I, const EltTy &Elt) { 245 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 246 assert(I <= this->end() && "Inserting past the end of the vector."); 247 if (I == end()) { 248 push_back(Elt); 249 return std::prev(end()); 250 } 251 assert(!Val.isNull() && "Null value with non-end insert iterator."); 252 if (EltTy V = Val.template dyn_cast<EltTy>()) { 253 assert(I == begin()); 254 Val = Elt; 255 push_back(V); 256 return begin(); 257 } 258 259 return Val.template get<VecTy*>()->insert(I, Elt); 260 } 261 262 template<typename ItTy> 263 iterator insert(iterator I, ItTy From, ItTy To) { 264 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 265 assert(I <= this->end() && "Inserting past the end of the vector."); 266 if (From == To) 267 return I; 268 269 // If we have a single value, convert to a vector. 270 ptrdiff_t Offset = I - begin(); 271 if (Val.isNull()) { 272 if (std::next(From) == To) { 273 Val = *From; 274 return begin(); 275 } 276 277 Val = new VecTy(); 278 } else if (EltTy V = Val.template dyn_cast<EltTy>()) { 279 Val = new VecTy(); 280 Val.template get<VecTy*>()->push_back(V); 281 } 282 return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); 283 } 284 }; 285 } // end namespace llvm 286 287 #endif 288
