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