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