X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FTinyPtrVector.h;h=d3d33b8adde1baa93f4a2fd1b60f48838aca5007;hb=75eac5f0ebff4d0ffe10ce6bc8f2867c5f15315b;hp=5014517c9e05bae4a433bb402b165f8edc85e596;hpb=bb9dbb7d6b4f39b74b755795e31b219a5518dd77;p=oota-llvm.git diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index 5014517c9e0..d3d33b8adde 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -10,8 +10,11 @@ #ifndef LLVM_ADT_TINYPTRVECTOR_H #define LLVM_ADT_TINYPTRVECTOR_H -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Compiler.h" namespace llvm { @@ -25,18 +28,78 @@ template class TinyPtrVector { public: typedef llvm::SmallVector VecTy; + typedef typename VecTy::value_type value_type; + llvm::PointerUnion Val; - + TinyPtrVector() {} + ~TinyPtrVector() { + if (VecTy *V = Val.template dyn_cast()) + delete V; + } + TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) { if (VecTy *V = Val.template dyn_cast()) Val = new VecTy(*V); } - ~TinyPtrVector() { - if (VecTy *V = Val.template dyn_cast()) + TinyPtrVector &operator=(const TinyPtrVector &RHS) { + if (this == &RHS) + return *this; + if (RHS.empty()) { + this->clear(); + return *this; + } + + // Try to squeeze into the single slot. If it won't fit, allocate a copied + // vector. + if (Val.template is()) { + if (RHS.size() == 1) + Val = RHS.front(); + else + Val = new VecTy(*RHS.Val.template get()); + return *this; + } + + // If we have a full vector allocated, try to re-use it. + if (RHS.Val.template is()) { + Val.template get()->clear(); + Val.template get()->push_back(RHS.front()); + } else { + *Val.template get() = *RHS.Val.template get(); + } + return *this; + } + +#if LLVM_USE_RVALUE_REFERENCES + TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { + RHS.Val = (EltTy)0; + } + TinyPtrVector &operator=(TinyPtrVector &&RHS) { + if (this == &RHS) + return *this; + if (RHS.empty()) { + this->clear(); + return *this; + } + + // If this vector has been allocated on the heap, re-use it if cheap. If it + // would require more copying, just delete it and we'll steal the other + // side. + if (VecTy *V = Val.template dyn_cast()) { + if (RHS.Val.template is()) { + V->clear(); + V->push_back(RHS.front()); + return *this; + } delete V; + } + + Val = RHS.Val; + RHS.Val = (EltTy)0; + return *this; } - +#endif + // implicit conversion operator to ArrayRef. operator ArrayRef() const { if (Val.isNull()) @@ -45,7 +108,7 @@ public: return *Val.getAddrOfPtr1(); return *Val.template get(); } - + bool empty() const { // This vector can be empty if it contains no element, or if it // contains a pointer to an empty vector. @@ -54,7 +117,7 @@ public: return Vec->empty(); return false; } - + unsigned size() const { if (empty()) return 0; @@ -62,27 +125,21 @@ public: return 1; return Val.template get()->size(); } - + typedef const EltTy *const_iterator; typedef EltTy *iterator; iterator begin() { - if (empty()) - return 0; - if (Val.template is()) return Val.getAddrOfPtr1(); - + return Val.template get()->begin(); } iterator end() { - if (empty()) - return 0; - if (Val.template is()) - return begin() + 1; - + return begin() + (Val.isNull() ? 0 : 1); + return Val.template get()->end(); } @@ -100,38 +157,53 @@ public: assert(i == 0 && "tinyvector index out of range"); return V; } - - assert(i < Val.template get()->size() && + + assert(i < Val.template get()->size() && "tinyvector index out of range"); return (*Val.template get())[i]; } - + EltTy front() const { assert(!empty() && "vector empty"); if (EltTy V = Val.template dyn_cast()) return V; return Val.template get()->front(); } - + + EltTy back() const { + assert(!empty() && "vector empty"); + if (EltTy V = Val.template dyn_cast()) + return V; + return Val.template get()->back(); + } + void push_back(EltTy NewVal) { assert(NewVal != 0 && "Can't add a null value"); - + // If we have nothing, add something. if (Val.isNull()) { Val = NewVal; return; } - + // If we have a single value, convert to a vector. if (EltTy V = Val.template dyn_cast()) { Val = new VecTy(); Val.template get()->push_back(V); } - + // Add the new value, we know we have a vector. Val.template get()->push_back(NewVal); } - + + void pop_back() { + // If we have a single value, convert to empty. + if (Val.template is()) + Val = (EltTy)0; + else if (VecTy *Vec = Val.template get()) + Vec->pop_back(); + } + void clear() { // If we have a single value, convert to empty. if (Val.template is()) { @@ -144,6 +216,9 @@ public: } iterator erase(iterator I) { + assert(I >= begin() && "Iterator to erase is out of bounds."); + assert(I < end() && "Erasing at past-the-end iterator."); + // If we have a single value, convert to empty. if (Val.template is()) { if (I == begin()) @@ -153,12 +228,63 @@ public: // benefit to collapsing back to a pointer return Vec->erase(I); } + return end(); + } + + iterator erase(iterator S, iterator E) { + assert(S >= begin() && "Range to erase is out of bounds."); + assert(S <= E && "Trying to erase invalid range."); + assert(E <= end() && "Trying to erase past the end."); + + if (Val.template is()) { + if (S == begin() && S != E) + Val = (EltTy)0; + } else if (VecTy *Vec = Val.template dyn_cast()) { + return Vec->erase(S, E); + } + return end(); + } - return 0; + iterator insert(iterator I, const EltTy &Elt) { + assert(I >= this->begin() && "Insertion iterator is out of bounds."); + assert(I <= this->end() && "Inserting past the end of the vector."); + if (I == end()) { + push_back(Elt); + return llvm::prior(end()); + } + assert(!Val.isNull() && "Null value with non-end insert iterator."); + if (EltTy V = Val.template dyn_cast()) { + assert(I == begin()); + Val = Elt; + push_back(V); + return begin(); + } + + return Val.template get()->insert(I, Elt); + } + + template + iterator insert(iterator I, ItTy From, ItTy To) { + assert(I >= this->begin() && "Insertion iterator is out of bounds."); + assert(I <= this->end() && "Inserting past the end of the vector."); + if (From == To) + return I; + + // If we have a single value, convert to a vector. + ptrdiff_t Offset = I - begin(); + if (Val.isNull()) { + if (llvm::next(From) == To) { + Val = *From; + return begin(); + } + + Val = new VecTy(); + } else if (EltTy V = Val.template dyn_cast()) { + Val = new VecTy(); + Val.template get()->push_back(V); + } + return Val.template get()->insert(begin() + Offset, From, To); } - -private: - void operator=(const TinyPtrVector&); // NOT IMPLEMENTED YET. }; } // end namespace llvm