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