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