contrib/llvm/include/llvm/ADT/TinyPtrVector.h

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