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