llvm/ADT/TinyPtrVector.h

0001 //===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_TINYPTRVECTOR_H
0010 #define LLVM_ADT_TINYPTRVECTOR_H
0011
0012 #include "llvm/ADT/ArrayRef.h"
0013 #include "llvm/ADT/PointerUnion.h"
0014 #include "llvm/ADT/SmallVector.h"
0015 #include <cassert>
0016 #include <cstddef>
0017 #include <iterator>
0018 #include <type_traits>
0019
0020 namespace llvm {
0021
0022 /// TinyPtrVector - This class is specialized for cases where there are
0023 /// normally 0 or 1 element in a vector, but is general enough to go beyond that
0024 /// when required.
0025 ///
0026 /// NOTE: This container doesn't allow you to store a null pointer into it.
0027 ///
0028 template <typename EltTy>
0029 class TinyPtrVector {
0030 public:
0031   using VecTy = SmallVector<EltTy, 4>;
0032   using value_type = typename VecTy::value_type;
0033   // EltTy must be the first pointer type so that is<EltTy> is true for the
0034   // default-constructed PtrUnion. This allows an empty TinyPtrVector to
0035   // naturally vend a begin/end iterator of type EltTy* without an additional
0036   // check for the empty state.
0037   using PtrUnion = PointerUnion<EltTy, VecTy *>;
0038
0039 private:
0040   PtrUnion Val;
0041
0042 public:
0043   TinyPtrVector() = default;
0044
0045   ~TinyPtrVector() {
0046     if (VecTy *V = dyn_cast_if_present<VecTy *>(Val))
0047       delete V;
0048   }
0049
0050   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
0051     if (VecTy *V = dyn_cast_if_present<VecTy *>(Val))
0052       Val = new VecTy(*V);
0053   }
0054
0055   TinyPtrVector &operator=(const TinyPtrVector &RHS) {
0056     if (this == &RHS)
0057       return *this;
0058     if (RHS.empty()) {
0059       this->clear();
0060       return *this;
0061     }
0062
0063     // Try to squeeze into the single slot. If it won't fit, allocate a copied
0064     // vector.
0065     if (isa<EltTy>(Val)) {
0066       if (RHS.size() == 1)
0067         Val = RHS.front();
0068       else
0069         Val = new VecTy(*cast<VecTy *>(RHS.Val));
0070       return *this;
0071     }
0072
0073     // If we have a full vector allocated, try to re-use it.
0074     if (isa<EltTy>(RHS.Val)) {
0075       cast<VecTy *>(Val)->clear();
0076       cast<VecTy *>(Val)->push_back(RHS.front());
0077     } else {
0078       *cast<VecTy *>(Val) = *cast<VecTy *>(RHS.Val);
0079     }
0080     return *this;
0081   }
0082
0083   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
0084     RHS.Val = (EltTy)nullptr;
0085   }
0086
0087   TinyPtrVector &operator=(TinyPtrVector &&RHS) {
0088     if (this == &RHS)
0089       return *this;
0090     if (RHS.empty()) {
0091       this->clear();
0092       return *this;
0093     }
0094
0095     // If this vector has been allocated on the heap, re-use it if cheap. If it
0096     // would require more copying, just delete it and we'll steal the other
0097     // side.
0098     if (VecTy *V = dyn_cast_if_present<VecTy *>(Val)) {
0099       if (isa<EltTy>(RHS.Val)) {
0100         V->clear();
0101         V->push_back(RHS.front());
0102         RHS.Val = EltTy();
0103         return *this;
0104       }
0105       delete V;
0106     }
0107
0108     Val = RHS.Val;
0109     RHS.Val = EltTy();
0110     return *this;
0111   }
0112
0113   TinyPtrVector(std::initializer_list<EltTy> IL)
0114       : Val(IL.size() == 0
0115                 ? PtrUnion()
0116                 : IL.size() == 1 ? PtrUnion(*IL.begin())
0117                                  : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
0118
0119   /// Constructor from an ArrayRef.
0120   ///
0121   /// This also is a constructor for individual array elements due to the single
0122   /// element constructor for ArrayRef.
0123   explicit TinyPtrVector(ArrayRef<EltTy> Elts)
0124       : Val(Elts.empty()
0125                 ? PtrUnion()
0126                 : Elts.size() == 1
0127                       ? PtrUnion(Elts[0])
0128                       : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
0129
0130   TinyPtrVector(size_t Count, EltTy Value)
0131       : Val(Count == 0 ? PtrUnion()
0132                        : Count == 1 ? PtrUnion(Value)
0133                                     : PtrUnion(new VecTy(Count, Value))) {}
0134
0135   // implicit conversion operator to ArrayRef.
0136   operator ArrayRef<EltTy>() const {
0137     if (Val.isNull())
0138       return {};
0139     if (isa<EltTy>(Val))
0140       return *Val.getAddrOfPtr1();
0141     return *cast<VecTy *>(Val);
0142   }
0143
0144   // implicit conversion operator to MutableArrayRef.
0145   operator MutableArrayRef<EltTy>() {
0146     if (Val.isNull())
0147       return {};
0148     if (isa<EltTy>(Val))
0149       return *Val.getAddrOfPtr1();
0150     return *cast<VecTy *>(Val);
0151   }
0152
0153   // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
0154   template <
0155       typename U,
0156       std::enable_if_t<std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
0157                        bool> = false>
0158   operator ArrayRef<U>() const {
0159     return operator ArrayRef<EltTy>();
0160   }
0161
0162   bool empty() const {
0163     // This vector can be empty if it contains no element, or if it
0164     // contains a pointer to an empty vector.
0165     if (Val.isNull()) return true;
0166     if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val))
0167       return Vec->empty();
0168     return false;
0169   }
0170
0171   unsigned size() const {
0172     if (empty())
0173       return 0;
0174     if (isa<EltTy>(Val))
0175       return 1;
0176     return cast<VecTy *>(Val)->size();
0177   }
0178
0179   using iterator = EltTy *;
0180   using const_iterator = const EltTy *;
0181   using reverse_iterator = std::reverse_iterator<iterator>;
0182   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
0183
0184   iterator begin() {
0185     if (isa<EltTy>(Val))
0186       return Val.getAddrOfPtr1();
0187
0188     return cast<VecTy *>(Val)->begin();
0189   }
0190
0191   iterator end() {
0192     if (isa<EltTy>(Val))
0193       return begin() + (Val.isNull() ? 0 : 1);
0194
0195     return cast<VecTy *>(Val)->end();
0196   }
0197
0198   const_iterator begin() const {
0199     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
0200   }
0201
0202   const_iterator end() const {
0203     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
0204   }
0205
0206   reverse_iterator rbegin() { return reverse_iterator(end()); }
0207   reverse_iterator rend() { return reverse_iterator(begin()); }
0208
0209   const_reverse_iterator rbegin() const {
0210     return const_reverse_iterator(end());
0211   }
0212
0213   const_reverse_iterator rend() const {
0214     return const_reverse_iterator(begin());
0215   }
0216
0217   EltTy operator[](unsigned i) const {
0218     assert(!Val.isNull() && "can't index into an empty vector");
0219     if (isa<EltTy>(Val)) {
0220       assert(i == 0 && "tinyvector index out of range");
0221       return cast<EltTy>(Val);
0222     }
0223
0224     assert(i < cast<VecTy *>(Val)->size() && "tinyvector index out of range");
0225     return (*cast<VecTy *>(Val))[i];
0226   }
0227
0228   EltTy front() const {
0229     assert(!empty() && "vector empty");
0230     if (isa<EltTy>(Val))
0231       return cast<EltTy>(Val);
0232     return cast<VecTy *>(Val)->front();
0233   }
0234
0235   EltTy back() const {
0236     assert(!empty() && "vector empty");
0237     if (isa<EltTy>(Val))
0238       return cast<EltTy>(Val);
0239     return cast<VecTy *>(Val)->back();
0240   }
0241
0242   void push_back(EltTy NewVal) {
0243     // If we have nothing, add something.
0244     if (Val.isNull()) {
0245       Val = NewVal;
0246       assert(!Val.isNull() && "Can't add a null value");
0247       return;
0248     }
0249
0250     // If we have a single value, convert to a vector.
0251     if (isa<EltTy>(Val)) {
0252       EltTy V = cast<EltTy>(Val);
0253       Val = new VecTy();
0254       cast<VecTy *>(Val)->push_back(V);
0255     }
0256
0257     // Add the new value, we know we have a vector.
0258     cast<VecTy *>(Val)->push_back(NewVal);
0259   }
0260
0261   void pop_back() {
0262     // If we have a single value, convert to empty.
0263     if (isa<EltTy>(Val))
0264       Val = (EltTy)nullptr;
0265     else if (VecTy *Vec = cast<VecTy *>(Val))
0266       Vec->pop_back();
0267   }
0268
0269   void clear() {
0270     // If we have a single value, convert to empty.
0271     if (isa<EltTy>(Val)) {
0272       Val = EltTy();
0273     } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) {
0274       // If we have a vector form, just clear it.
0275       Vec->clear();
0276     }
0277     // Otherwise, we're already empty.
0278   }
0279
0280   iterator erase(iterator I) {
0281     assert(I >= begin() && "Iterator to erase is out of bounds.");
0282     assert(I < end() && "Erasing at past-the-end iterator.");
0283
0284     // If we have a single value, convert to empty.
0285     if (isa<EltTy>(Val)) {
0286       if (I == begin())
0287         Val = EltTy();
0288     } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) {
0289       // multiple items in a vector; just do the erase, there is no
0290       // benefit to collapsing back to a pointer
0291       return Vec->erase(I);
0292     }
0293     return end();
0294   }
0295
0296   iterator erase(iterator S, iterator E) {
0297     assert(S >= begin() && "Range to erase is out of bounds.");
0298     assert(S <= E && "Trying to erase invalid range.");
0299     assert(E <= end() && "Trying to erase past the end.");
0300
0301     if (isa<EltTy>(Val)) {
0302       if (S == begin() && S != E)
0303         Val = EltTy();
0304     } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) {
0305       return Vec->erase(S, E);
0306     }
0307     return end();
0308   }
0309
0310   iterator insert(iterator I, const EltTy &Elt) {
0311     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
0312     assert(I <= this->end() && "Inserting past the end of the vector.");
0313     if (I == end()) {
0314       push_back(Elt);
0315       return std::prev(end());
0316     }
0317     assert(!Val.isNull() && "Null value with non-end insert iterator.");
0318     if (isa<EltTy>(Val)) {
0319       EltTy V = cast<EltTy>(Val);
0320       assert(I == begin());
0321       Val = Elt;
0322       push_back(V);
0323       return begin();
0324     }
0325
0326     return cast<VecTy *>(Val)->insert(I, Elt);
0327   }
0328
0329   template<typename ItTy>
0330   iterator insert(iterator I, ItTy From, ItTy To) {
0331     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
0332     assert(I <= this->end() && "Inserting past the end of the vector.");
0333     if (From == To)
0334       return I;
0335
0336     // If we have a single value, convert to a vector.
0337     ptrdiff_t Offset = I - begin();
0338     if (Val.isNull()) {
0339       if (std::next(From) == To) {
0340         Val = *From;
0341         return begin();
0342       }
0343
0344       Val = new VecTy();
0345     } else if (isa<EltTy>(Val)) {
0346       EltTy V = cast<EltTy>(Val);
0347       Val = new VecTy();
0348       cast<VecTy *>(Val)->push_back(V);
0349     }
0350     return cast<VecTy *>(Val)->insert(begin() + Offset, From, To);
0351   }
0352 };
0353
0354 } // end namespace llvm
0355
0356 #endif // LLVM_ADT_TINYPTRVECTOR_H