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/SmallVector.h"
  15 #include "llvm/ADT/PointerUnion.h"
  16 #include "llvm/Support/Compiler.h"
  17
  18 namespace llvm {
  19
  20 /// TinyPtrVector - This class is specialized for cases where there are
  21 /// normally 0 or 1 element in a vector, but is general enough to go beyond that
  22 /// when required.
  23 ///
  24 /// NOTE: This container doesn't allow you to store a null pointer into it.
  25 ///
  26 template <typename EltTy>
  27 class TinyPtrVector {
  28 public:
  29   typedef llvm::SmallVector<EltTy, 4> VecTy;
  30   typedef typename VecTy::value_type value_type;
  31
  32   llvm::PointerUnion<EltTy, VecTy*> Val;
  33
  34   TinyPtrVector() {}
  35   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
  36     if (VecTy *V = Val.template dyn_cast<VecTy*>())
  37       Val = new VecTy(*V);
  38   }
  39 #if LLVM_USE_RVALUE_REFERENCES
  40   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
  41     RHS.Val = (EltTy)0;
  42   }
  43 #endif
  44   ~TinyPtrVector() {
  45     if (VecTy *V = Val.template dyn_cast<VecTy*>())
  46       delete V;
  47   }
  48
  49   // implicit conversion operator to ArrayRef.
  50   operator ArrayRef<EltTy>() const {
  51     if (Val.isNull())
  52       return ArrayRef<EltTy>();
  53     if (Val.template is<EltTy>())
  54       return *Val.getAddrOfPtr1();
  55     return *Val.template get<VecTy*>();
  56   }
  57
  58   bool empty() const {
  59     // This vector can be empty if it contains no element, or if it
  60     // contains a pointer to an empty vector.
  61     if (Val.isNull()) return true;
  62     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
  63       return Vec->empty();
  64     return false;
  65   }
  66
  67   unsigned size() const {
  68     if (empty())
  69       return 0;
  70     if (Val.template is<EltTy>())
  71       return 1;
  72     return Val.template get<VecTy*>()->size();
  73   }
  74
  75   typedef const EltTy *const_iterator;
  76   typedef EltTy *iterator;
  77
  78   iterator begin() {
  79     if (Val.template is<EltTy>())
  80       return Val.getAddrOfPtr1();
  81
  82     return Val.template get<VecTy *>()->begin();
  83
  84   }
  85   iterator end() {
  86     if (Val.template is<EltTy>())
  87       return begin() + (Val.isNull() ? 0 : 1);
  88
  89     return Val.template get<VecTy *>()->end();
  90   }
  91
  92   const_iterator begin() const {
  93     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
  94   }
  95
  96   const_iterator end() const {
  97     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
  98   }
  99
 100   EltTy operator[](unsigned i) const {
 101     assert(!Val.isNull() && "can't index into an empty vector");
 102     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 103       assert(i == 0 && "tinyvector index out of range");
 104       return V;
 105     }
 106
 107     assert(i < Val.template get<VecTy*>()->size() &&
 108            "tinyvector index out of range");
 109     return (*Val.template get<VecTy*>())[i];
 110   }
 111
 112   EltTy front() const {
 113     assert(!empty() && "vector empty");
 114     if (EltTy V = Val.template dyn_cast<EltTy>())
 115       return V;
 116     return Val.template get<VecTy*>()->front();
 117   }
 118
 119   EltTy back() const {
 120     assert(!empty() && "vector empty");
 121     if (EltTy V = Val.template dyn_cast<EltTy>())
 122       return V;
 123     return Val.template get<VecTy*>()->back();
 124   }
 125
 126
 127   void push_back(EltTy NewVal) {
 128     assert(NewVal != 0 && "Can't add a null value");
 129
 130     // If we have nothing, add something.
 131     if (Val.isNull()) {
 132       Val = NewVal;
 133       return;
 134     }
 135
 136     // If we have a single value, convert to a vector.
 137     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 138       Val = new VecTy();
 139       Val.template get<VecTy*>()->push_back(V);
 140     }
 141
 142     // Add the new value, we know we have a vector.
 143     Val.template get<VecTy*>()->push_back(NewVal);
 144   }
 145
 146   void pop_back() {
 147     // If we have a single value, convert to empty.
 148     if (Val.template is<EltTy>())
 149       Val = (EltTy)0;
 150     else if (VecTy *Vec = Val.template get<VecTy*>())
 151       Vec->pop_back();
 152   }
 153
 154
 155   void clear() {
 156     // If we have a single value, convert to empty.
 157     if (Val.template is<EltTy>()) {
 158       Val = (EltTy)0;
 159     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 160       // If we have a vector form, just clear it.
 161       Vec->clear();
 162     }
 163     // Otherwise, we're already empty.
 164   }
 165
 166   iterator erase(iterator I) {
 167     // If we have a single value, convert to empty.
 168     if (Val.template is<EltTy>()) {
 169       if (I == begin())
 170         Val = (EltTy)0;
 171     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 172       // multiple items in a vector; just do the erase, there is no
 173       // benefit to collapsing back to a pointer
 174       return Vec->erase(I);
 175     }
 176     return end();
 177   }
 178
 179 private:
 180   void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET.
 181 #if LLVM_USE_RVALUE_REFERENCES
 182   void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET.
 183 #endif
 184 };
 185 } // end namespace llvm
 186
 187 #endif