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