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