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   void push_back(EltTy NewVal) {
 124     assert(NewVal != 0 && "Can't add a null value");
 125
 126     // If we have nothing, add something.
 127     if (Val.isNull()) {
 128       Val = NewVal;
 129       return;
 130     }
 131
 132     // If we have a single value, convert to a vector.
 133     if (EltTy V = Val.template dyn_cast<EltTy>()) {
 134       Val = new VecTy();
 135       Val.template get<VecTy*>()->push_back(V);
 136     }
 137
 138     // Add the new value, we know we have a vector.
 139     Val.template get<VecTy*>()->push_back(NewVal);
 140   }
 141
 142   void clear() {
 143     // If we have a single value, convert to empty.
 144     if (Val.template is<EltTy>()) {
 145       Val = (EltTy)0;
 146     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 147       // If we have a vector form, just clear it.
 148       Vec->clear();
 149     }
 150     // Otherwise, we're already empty.
 151   }
 152
 153   iterator erase(iterator I) {
 154     // If we have a single value, convert to empty.
 155     if (Val.template is<EltTy>()) {
 156       if (I == begin())
 157         Val = (EltTy)0;
 158     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
 159       // multiple items in a vector; just do the erase, there is no
 160       // benefit to collapsing back to a pointer
 161       return Vec->erase(I);
 162     }
 163
 164     return 0;
 165   }
 166
 167 private:
 168   void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET.
 169 #if LLVM_USE_RVALUE_REFERENCES
 170   void operator=(TinyPtrVector&&); // NOT IMPLEMENTED YET.
 171 #endif
 172 };
 173 } // end namespace llvm
 174
 175 #endif