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