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