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() {
  36     if (VecTy *V = Val.template dyn_cast<VecTy*>())
  37       delete V;
  38   }
  39
  40   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
  41     if (VecTy *V = Val.template dyn_cast<VecTy*>())
  42       Val = new VecTy(*V);
  43   }
  44   TinyPtrVector &operator=(const TinyPtrVector &RHS) {
  45     if (this == &RHS)
  46       return *this;
  47     if (RHS.empty()) {
  48       this->clear();
  49       return *this;
  50     }
  51
  52     // Try to squeeze into the single slot. If it won't fit, allocate a copied
  53     // vector.
  54     if (Val.template is<EltTy>()) {
  55       if (RHS.size() == 1)
  56         Val = RHS.front();
  57       else
  58         Val = new VecTy(*RHS.Val.template get<VecTy*>());
  59       return *this;
  60     }
  61
  62     // If we have a full vector allocated, try to re-use it.
  63     if (RHS.Val.template is<EltTy>()) {
  64       Val.template get<VecTy*>()->clear();
  65       Val.template get<VecTy*>()->push_back(RHS.front());
  66     } else {
  67       *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
  68     }
  69     return *this;
  70   }
  71
  72 #if LLVM_USE_RVALUE_REFERENCES
  73   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
  74     RHS.Val = (EltTy)0;
  75   }
  76   TinyPtrVector &operator=(TinyPtrVector &&RHS) {
  77     if (this == &RHS)
  78       return *this;
  79     if (RHS.empty()) {
  80       this->clear();
  81       return *this;
  82     }
  83
  84     // If this vector has been allocated on the heap, re-use it if cheap. If it
  85     // would require more copying, just delete it and we'll steal the other
  86     // side.
  87     if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
  88       if (RHS.Val.template is<EltTy>()) {
  89         V->clear();
  90         V->push_back(RHS.front());
  91         return *this;
  92       }
  93       delete V;
  94     }
  95
  96     Val = RHS.Val;
  97     RHS.Val = (EltTy)0;
  98     return *this;
  99   }
 100 #endif
 101
 102   // implicit conversion operator to ArrayRef.
 103   operator ArrayRef<EltTy>() const {
 104     if (Val.isNull())
 105       return ArrayRef<EltTy>();
 106     if (Val.template is<EltTy>())
 107       return *Val.getAddrOfPtr1();
 108     return *Val.template get<VecTy*>();
 109   }
 110
 111   bool empty() const {
 112     // This vector can be empty if it contains no element, or if it
 113     // contains a pointer to an empty vector.
 114     if (Val.isNull()) return true;
 115     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
 116       return Vec->empty();
 117     return false;
 118   }
 119
 120   unsigned size() const {
 121     if (empty())
 122       return 0;
 123     if (Val.template is<EltTy>())
 124       return 1;
 125     return Val.template get<VecTy*>()->size();
 126   }
 127
 128   typedef const EltTy *const_iterator;
 129   typedef EltTy *iterator;
 130
 131   iterator begin() {
 132     if (Val.template is<EltTy>())
 133       return Val.getAddrOfPtr1();
 134
 135     return Val.template get<VecTy *>()->begin();
 136
 137   }
 138   iterator end() {
 139     if (Val.template is<EltTy>())
 140       return begin() + (Val.isNull() ? 0 : 1);
 141
 142     return Val.template get<VecTy *>()->end();
 143   }
 144
 145   const_iterator begin() const {
 146     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
 147   }
 148
 149   const_iterator end() const {
 150     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
 151   }
 152
 153   EltTy operator[](unsigned i) const {
 154     assert(!Val.isNull() && "can't index into an empty vector");
 155     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 156       assert(i == 0 && "tinyvector index out of range");
 157       return V;
 158     }
 159
 160     assert(i < Val.template get<VecTy*>()->size() &&
 161            "tinyvector index out of range");
 162     return (*Val.template get<VecTy*>())[i];
 163   }
 164
 165   EltTy front() const {
 166     assert(!empty() && "vector empty");
 167     if (EltTy V = Val.template dyn_cast<EltTy>())
 168       return V;
 169     return Val.template get<VecTy*>()->front();
 170   }
 171
 172   EltTy back() const {
 173     assert(!empty() && "vector empty");
 174     if (EltTy V = Val.template dyn_cast<EltTy>())
 175       return V;
 176     return Val.template get<VecTy*>()->back();
 177   }
 178
 179   void push_back(EltTy NewVal) {
 180     assert(NewVal != 0 && "Can't add a null value");
 181
 182     // If we have nothing, add something.
 183     if (Val.isNull()) {
 184       Val = NewVal;
 185       return;
 186     }
 187
 188     // If we have a single value, convert to a vector.
 189     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 190       Val = new VecTy();
 191       Val.template get<VecTy*>()->push_back(V);
 192     }
 193
 194     // Add the new value, we know we have a vector.
 195     Val.template get<VecTy*>()->push_back(NewVal);
 196   }
 197
 198   void pop_back() {
 199     // If we have a single value, convert to empty.
 200     if (Val.template is<EltTy>())
 201       Val = (EltTy)0;
 202     else if (VecTy *Vec = Val.template get<VecTy*>())
 203       Vec->pop_back();
 204   }
 205
 206   void clear() {
 207     // If we have a single value, convert to empty.
 208     if (Val.template is<EltTy>()) {
 209       Val = (EltTy)0;
 210     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 211       // If we have a vector form, just clear it.
 212       Vec->clear();
 213     }
 214     // Otherwise, we're already empty.
 215   }
 216
 217   iterator erase(iterator I) {
 218     // If we have a single value, convert to empty.
 219     if (Val.template is<EltTy>()) {
 220       if (I == begin())
 221         Val = (EltTy)0;
 222     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 223       // multiple items in a vector; just do the erase, there is no
 224       // benefit to collapsing back to a pointer
 225       return Vec->erase(I);
 226     }
 227     return end();
 228   }
 229 };
 230 } // end namespace llvm
 231
 232 #endif