include/llvm/ADT/TinyPtrVector.h

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