1 //===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_ADT_TINYPTRVECTOR_H 10 #define LLVM_ADT_TINYPTRVECTOR_H 11 12 #include "llvm/ADT/ArrayRef.h" 13 #include "llvm/ADT/PointerUnion.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include <cassert> 16 #include <cstddef> 17 #include <iterator> 18 #include <type_traits> 19 20 namespace llvm { 21 22 /// TinyPtrVector - This class is specialized for cases where there are 23 /// normally 0 or 1 element in a vector, but is general enough to go beyond that 24 /// when required. 25 /// 26 /// NOTE: This container doesn't allow you to store a null pointer into it. 27 /// 28 template <typename EltTy> 29 class TinyPtrVector { 30 public: 31 using VecTy = SmallVector<EltTy, 4>; 32 using value_type = typename VecTy::value_type; 33 // EltTy must be the first pointer type so that is<EltTy> is true for the 34 // default-constructed PtrUnion. This allows an empty TinyPtrVector to 35 // naturally vend a begin/end iterator of type EltTy* without an additional 36 // check for the empty state. 37 using PtrUnion = PointerUnion<EltTy, VecTy *>; 38 39 private: 40 PtrUnion Val; 41 42 public: 43 TinyPtrVector() = default; 44 ~TinyPtrVector()45 ~TinyPtrVector() { 46 if (VecTy *V = dyn_cast_if_present<VecTy *>(Val)) 47 delete V; 48 } 49 TinyPtrVector(const TinyPtrVector & RHS)50 TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { 51 if (VecTy *V = dyn_cast_if_present<VecTy *>(Val)) 52 Val = new VecTy(*V); 53 } 54 55 TinyPtrVector &operator=(const TinyPtrVector &RHS) { 56 if (this == &RHS) 57 return *this; 58 if (RHS.empty()) { 59 this->clear(); 60 return *this; 61 } 62 63 // Try to squeeze into the single slot. If it won't fit, allocate a copied 64 // vector. 65 if (isa<EltTy>(Val)) { 66 if (RHS.size() == 1) 67 Val = RHS.front(); 68 else 69 Val = new VecTy(*cast<VecTy *>(RHS.Val)); 70 return *this; 71 } 72 73 // If we have a full vector allocated, try to re-use it. 74 if (isa<EltTy>(RHS.Val)) { 75 cast<VecTy *>(Val)->clear(); 76 cast<VecTy *>(Val)->push_back(RHS.front()); 77 } else { 78 *cast<VecTy *>(Val) = *cast<VecTy *>(RHS.Val); 79 } 80 return *this; 81 } 82 TinyPtrVector(TinyPtrVector && RHS)83 TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { 84 RHS.Val = (EltTy)nullptr; 85 } 86 87 TinyPtrVector &operator=(TinyPtrVector &&RHS) { 88 if (this == &RHS) 89 return *this; 90 if (RHS.empty()) { 91 this->clear(); 92 return *this; 93 } 94 95 // If this vector has been allocated on the heap, re-use it if cheap. If it 96 // would require more copying, just delete it and we'll steal the other 97 // side. 98 if (VecTy *V = dyn_cast_if_present<VecTy *>(Val)) { 99 if (isa<EltTy>(RHS.Val)) { 100 V->clear(); 101 V->push_back(RHS.front()); 102 RHS.Val = EltTy(); 103 return *this; 104 } 105 delete V; 106 } 107 108 Val = RHS.Val; 109 RHS.Val = EltTy(); 110 return *this; 111 } 112 TinyPtrVector(std::initializer_list<EltTy> IL)113 TinyPtrVector(std::initializer_list<EltTy> IL) 114 : Val(IL.size() == 0 115 ? PtrUnion() 116 : IL.size() == 1 ? PtrUnion(*IL.begin()) 117 : PtrUnion(new VecTy(IL.begin(), IL.end()))) {} 118 119 /// Constructor from an ArrayRef. 120 /// 121 /// This also is a constructor for individual array elements due to the single 122 /// element constructor for ArrayRef. TinyPtrVector(ArrayRef<EltTy> Elts)123 explicit TinyPtrVector(ArrayRef<EltTy> Elts) 124 : Val(Elts.empty() 125 ? PtrUnion() 126 : Elts.size() == 1 127 ? PtrUnion(Elts[0]) 128 : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {} 129 TinyPtrVector(size_t Count,EltTy Value)130 TinyPtrVector(size_t Count, EltTy Value) 131 : Val(Count == 0 ? PtrUnion() 132 : Count == 1 ? PtrUnion(Value) 133 : PtrUnion(new VecTy(Count, Value))) {} 134 135 // implicit conversion operator to ArrayRef. 136 operator ArrayRef<EltTy>() const { 137 if (Val.isNull()) 138 return std::nullopt; 139 if (isa<EltTy>(Val)) 140 return *Val.getAddrOfPtr1(); 141 return *cast<VecTy *>(Val); 142 } 143 144 // implicit conversion operator to MutableArrayRef. 145 operator MutableArrayRef<EltTy>() { 146 if (Val.isNull()) 147 return std::nullopt; 148 if (isa<EltTy>(Val)) 149 return *Val.getAddrOfPtr1(); 150 return *cast<VecTy *>(Val); 151 } 152 153 // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*. 154 template < 155 typename U, 156 std::enable_if_t<std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value, 157 bool> = false> 158 operator ArrayRef<U>() const { 159 return operator ArrayRef<EltTy>(); 160 } 161 empty()162 bool empty() const { 163 // This vector can be empty if it contains no element, or if it 164 // contains a pointer to an empty vector. 165 if (Val.isNull()) return true; 166 if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) 167 return Vec->empty(); 168 return false; 169 } 170 size()171 unsigned size() const { 172 if (empty()) 173 return 0; 174 if (isa<EltTy>(Val)) 175 return 1; 176 return cast<VecTy *>(Val)->size(); 177 } 178 179 using iterator = EltTy *; 180 using const_iterator = const EltTy *; 181 using reverse_iterator = std::reverse_iterator<iterator>; 182 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 183 begin()184 iterator begin() { 185 if (isa<EltTy>(Val)) 186 return Val.getAddrOfPtr1(); 187 188 return cast<VecTy *>(Val)->begin(); 189 } 190 end()191 iterator end() { 192 if (isa<EltTy>(Val)) 193 return begin() + (Val.isNull() ? 0 : 1); 194 195 return cast<VecTy *>(Val)->end(); 196 } 197 begin()198 const_iterator begin() const { 199 return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); 200 } 201 end()202 const_iterator end() const { 203 return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); 204 } 205 rbegin()206 reverse_iterator rbegin() { return reverse_iterator(end()); } rend()207 reverse_iterator rend() { return reverse_iterator(begin()); } 208 rbegin()209 const_reverse_iterator rbegin() const { 210 return const_reverse_iterator(end()); 211 } 212 rend()213 const_reverse_iterator rend() const { 214 return const_reverse_iterator(begin()); 215 } 216 217 EltTy operator[](unsigned i) const { 218 assert(!Val.isNull() && "can't index into an empty vector"); 219 if (isa<EltTy>(Val)) { 220 assert(i == 0 && "tinyvector index out of range"); 221 return cast<EltTy>(Val); 222 } 223 224 assert(i < cast<VecTy *>(Val)->size() && "tinyvector index out of range"); 225 return (*cast<VecTy *>(Val))[i]; 226 } 227 front()228 EltTy front() const { 229 assert(!empty() && "vector empty"); 230 if (isa<EltTy>(Val)) 231 return cast<EltTy>(Val); 232 return cast<VecTy *>(Val)->front(); 233 } 234 back()235 EltTy back() const { 236 assert(!empty() && "vector empty"); 237 if (isa<EltTy>(Val)) 238 return cast<EltTy>(Val); 239 return cast<VecTy *>(Val)->back(); 240 } 241 push_back(EltTy NewVal)242 void push_back(EltTy NewVal) { 243 // If we have nothing, add something. 244 if (Val.isNull()) { 245 Val = NewVal; 246 assert(!Val.isNull() && "Can't add a null value"); 247 return; 248 } 249 250 // If we have a single value, convert to a vector. 251 if (isa<EltTy>(Val)) { 252 EltTy V = cast<EltTy>(Val); 253 Val = new VecTy(); 254 cast<VecTy *>(Val)->push_back(V); 255 } 256 257 // Add the new value, we know we have a vector. 258 cast<VecTy *>(Val)->push_back(NewVal); 259 } 260 pop_back()261 void pop_back() { 262 // If we have a single value, convert to empty. 263 if (isa<EltTy>(Val)) 264 Val = (EltTy)nullptr; 265 else if (VecTy *Vec = cast<VecTy *>(Val)) 266 Vec->pop_back(); 267 } 268 clear()269 void clear() { 270 // If we have a single value, convert to empty. 271 if (isa<EltTy>(Val)) { 272 Val = EltTy(); 273 } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) { 274 // If we have a vector form, just clear it. 275 Vec->clear(); 276 } 277 // Otherwise, we're already empty. 278 } 279 erase(iterator I)280 iterator erase(iterator I) { 281 assert(I >= begin() && "Iterator to erase is out of bounds."); 282 assert(I < end() && "Erasing at past-the-end iterator."); 283 284 // If we have a single value, convert to empty. 285 if (isa<EltTy>(Val)) { 286 if (I == begin()) 287 Val = EltTy(); 288 } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) { 289 // multiple items in a vector; just do the erase, there is no 290 // benefit to collapsing back to a pointer 291 return Vec->erase(I); 292 } 293 return end(); 294 } 295 erase(iterator S,iterator E)296 iterator erase(iterator S, iterator E) { 297 assert(S >= begin() && "Range to erase is out of bounds."); 298 assert(S <= E && "Trying to erase invalid range."); 299 assert(E <= end() && "Trying to erase past the end."); 300 301 if (isa<EltTy>(Val)) { 302 if (S == begin() && S != E) 303 Val = EltTy(); 304 } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) { 305 return Vec->erase(S, E); 306 } 307 return end(); 308 } 309 insert(iterator I,const EltTy & Elt)310 iterator insert(iterator I, const EltTy &Elt) { 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 (I == end()) { 314 push_back(Elt); 315 return std::prev(end()); 316 } 317 assert(!Val.isNull() && "Null value with non-end insert iterator."); 318 if (isa<EltTy>(Val)) { 319 EltTy V = cast<EltTy>(Val); 320 assert(I == begin()); 321 Val = Elt; 322 push_back(V); 323 return begin(); 324 } 325 326 return cast<VecTy *>(Val)->insert(I, Elt); 327 } 328 329 template<typename ItTy> insert(iterator I,ItTy From,ItTy To)330 iterator insert(iterator I, ItTy From, ItTy To) { 331 assert(I >= this->begin() && "Insertion iterator is out of bounds."); 332 assert(I <= this->end() && "Inserting past the end of the vector."); 333 if (From == To) 334 return I; 335 336 // If we have a single value, convert to a vector. 337 ptrdiff_t Offset = I - begin(); 338 if (Val.isNull()) { 339 if (std::next(From) == To) { 340 Val = *From; 341 return begin(); 342 } 343 344 Val = new VecTy(); 345 } else if (isa<EltTy>(Val)) { 346 EltTy V = cast<EltTy>(Val); 347 Val = new VecTy(); 348 cast<VecTy *>(Val)->push_back(V); 349 } 350 return cast<VecTy *>(Val)->insert(begin() + Offset, From, To); 351 } 352 }; 353 354 } // end namespace llvm 355 356 #endif // LLVM_ADT_TINYPTRVECTOR_H 357