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         RHS.Val = (EltTy)nullptr;
 101         return *this;
 102       }
 103       delete V;
 104     }
 105
 106     Val = RHS.Val;
 107     RHS.Val = (EltTy)nullptr;
 108     return *this;
 109   }
 110
 111   TinyPtrVector(std::initializer_list<EltTy> IL)
 112       : Val(IL.size() == 0
 113                 ? PtrUnion()
 114                 : IL.size() == 1 ? PtrUnion(*IL.begin())
 115                                  : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
 116
 117   /// Constructor from an ArrayRef.
 118   ///
 119   /// This also is a constructor for individual array elements due to the single
 120   /// element constructor for ArrayRef.
 121   explicit TinyPtrVector(ArrayRef<EltTy> Elts)
 122       : Val(Elts.empty()
 123                 ? PtrUnion()
 124                 : Elts.size() == 1
 125                       ? PtrUnion(Elts[0])
 126                       : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
 127
 128   TinyPtrVector(size_t Count, EltTy Value)
 129       : Val(Count == 0 ? PtrUnion()
 130                        : Count == 1 ? PtrUnion(Value)
 131                                     : PtrUnion(new VecTy(Count, Value))) {}
 132
 133   // implicit conversion operator to ArrayRef.
 134   operator ArrayRef<EltTy>() const {
 135     if (Val.isNull())
 136       return None;
 137     if (Val.template is<EltTy>())
 138       return *Val.getAddrOfPtr1();
 139     return *Val.template get<VecTy*>();
 140   }
 141
 142   // implicit conversion operator to MutableArrayRef.
 143   operator MutableArrayRef<EltTy>() {
 144     if (Val.isNull())
 145       return None;
 146     if (Val.template is<EltTy>())
 147       return *Val.getAddrOfPtr1();
 148     return *Val.template get<VecTy*>();
 149   }
 150
 151   // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
 152   template<typename U,
 153            typename std::enable_if<
 154                std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
 155                bool>::type = false>
 156   operator ArrayRef<U>() const {
 157     return operator ArrayRef<EltTy>();
 158   }
 159
 160   bool empty() const {
 161     // This vector can be empty if it contains no element, or if it
 162     // contains a pointer to an empty vector.
 163     if (Val.isNull()) return true;
 164     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
 165       return Vec->empty();
 166     return false;
 167   }
 168
 169   unsigned size() const {
 170     if (empty())
 171       return 0;
 172     if (Val.template is<EltTy>())
 173       return 1;
 174     return Val.template get<VecTy*>()->size();
 175   }
 176
 177   using iterator = EltTy *;
 178   using const_iterator = const EltTy *;
 179   using reverse_iterator = std::reverse_iterator<iterator>;
 180   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 181
 182   iterator begin() {
 183     if (Val.template is<EltTy>())
 184       return Val.getAddrOfPtr1();
 185
 186     return Val.template get<VecTy *>()->begin();
 187   }
 188
 189   iterator end() {
 190     if (Val.template is<EltTy>())
 191       return begin() + (Val.isNull() ? 0 : 1);
 192
 193     return Val.template get<VecTy *>()->end();
 194   }
 195
 196   const_iterator begin() const {
 197     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
 198   }
 199
 200   const_iterator end() const {
 201     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
 202   }
 203
 204   reverse_iterator rbegin() { return reverse_iterator(end()); }
 205   reverse_iterator rend() { return reverse_iterator(begin()); }
 206
 207   const_reverse_iterator rbegin() const {
 208     return const_reverse_iterator(end());
 209   }
 210
 211   const_reverse_iterator rend() const {
 212     return const_reverse_iterator(begin());
 213   }
 214
 215   EltTy operator[](unsigned i) const {
 216     assert(!Val.isNull() && "can't index into an empty vector");
 217     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 218       assert(i == 0 && "tinyvector index out of range");
 219       return V;
 220     }
 221
 222     assert(i < Val.template get<VecTy*>()->size() &&
 223            "tinyvector index out of range");
 224     return (*Val.template get<VecTy*>())[i];
 225   }
 226
 227   EltTy front() const {
 228     assert(!empty() && "vector empty");
 229     if (EltTy V = Val.template dyn_cast<EltTy>())
 230       return V;
 231     return Val.template get<VecTy*>()->front();
 232   }
 233
 234   EltTy back() const {
 235     assert(!empty() && "vector empty");
 236     if (EltTy V = Val.template dyn_cast<EltTy>())
 237       return V;
 238     return Val.template get<VecTy*>()->back();
 239   }
 240
 241   void push_back(EltTy NewVal) {
 242     assert(NewVal && "Can't add a null value");
 243
 244     // If we have nothing, add something.
 245     if (Val.isNull()) {
 246       Val = NewVal;
 247       return;
 248     }
 249
 250     // If we have a single value, convert to a vector.
 251     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 252       Val = new VecTy();
 253       Val.template get<VecTy*>()->push_back(V);
 254     }
 255
 256     // Add the new value, we know we have a vector.
 257     Val.template get<VecTy*>()->push_back(NewVal);
 258   }
 259
 260   void pop_back() {
 261     // If we have a single value, convert to empty.
 262     if (Val.template is<EltTy>())
 263       Val = (EltTy)nullptr;
 264     else if (VecTy *Vec = Val.template get<VecTy*>())
 265       Vec->pop_back();
 266   }
 267
 268   void clear() {
 269     // If we have a single value, convert to empty.
 270     if (Val.template is<EltTy>()) {
 271       Val = (EltTy)nullptr;
 272     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 273       // If we have a vector form, just clear it.
 274       Vec->clear();
 275     }
 276     // Otherwise, we're already empty.
 277   }
 278
 279   iterator erase(iterator I) {
 280     assert(I >= begin() && "Iterator to erase is out of bounds.");
 281     assert(I < end() && "Erasing at past-the-end iterator.");
 282
 283     // If we have a single value, convert to empty.
 284     if (Val.template is<EltTy>()) {
 285       if (I == begin())
 286         Val = (EltTy)nullptr;
 287     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 288       // multiple items in a vector; just do the erase, there is no
 289       // benefit to collapsing back to a pointer
 290       return Vec->erase(I);
 291     }
 292     return end();
 293   }
 294
 295   iterator erase(iterator S, iterator E) {
 296     assert(S >= begin() && "Range to erase is out of bounds.");
 297     assert(S <= E && "Trying to erase invalid range.");
 298     assert(E <= end() && "Trying to erase past the end.");
 299
 300     if (Val.template is<EltTy>()) {
 301       if (S == begin() && S != E)
 302         Val = (EltTy)nullptr;
 303     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 304       return Vec->erase(S, E);
 305     }
 306     return end();
 307   }
 308
 309   iterator insert(iterator I, const EltTy &Elt) {
 310     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
 311     assert(I <= this->end() && "Inserting past the end of the vector.");
 312     if (I == end()) {
 313       push_back(Elt);
 314       return std::prev(end());
 315     }
 316     assert(!Val.isNull() && "Null value with non-end insert iterator.");
 317     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 318       assert(I == begin());
 319       Val = Elt;
 320       push_back(V);
 321       return begin();
 322     }
 323
 324     return Val.template get<VecTy*>()->insert(I, Elt);
 325   }
 326
 327   template<typename ItTy>
 328   iterator insert(iterator I, ItTy From, ItTy To) {
 329     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
 330     assert(I <= this->end() && "Inserting past the end of the vector.");
 331     if (From == To)
 332       return I;
 333
 334     // If we have a single value, convert to a vector.
 335     ptrdiff_t Offset = I - begin();
 336     if (Val.isNull()) {
 337       if (std::next(From) == To) {
 338         Val = *From;
 339         return begin();
 340       }
 341
 342       Val = new VecTy();
 343     } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
 344       Val = new VecTy();
 345       Val.template get<VecTy*>()->push_back(V);
 346     }
 347     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
 348   }
 349 };
 350
 351 } // end namespace llvm
 352
 353 #endif // LLVM_ADT_TINYPTRVECTOR_H