LCOV - code coverage report
Current view: top level - include/llvm/ADT - TinyPtrVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 89 96 92.7 %
Date: 2018-07-13 00:08:38 Functions: 97 100 97.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/None.h"
      15             : #include "llvm/ADT/PointerUnion.h"
      16             : #include "llvm/ADT/SmallVector.h"
      17             : #include <cassert>
      18             : #include <cstddef>
      19             : #include <iterator>
      20             : #include <type_traits>
      21             : 
      22             : namespace llvm {
      23             : 
      24             : /// TinyPtrVector - This class is specialized for cases where there are
      25             : /// normally 0 or 1 element in a vector, but is general enough to go beyond that
      26             : /// when required.
      27             : ///
      28             : /// NOTE: This container doesn't allow you to store a null pointer into it.
      29             : ///
      30             : template <typename EltTy>
      31             : class TinyPtrVector {
      32             : public:
      33             :   using VecTy = SmallVector<EltTy, 4>;
      34             :   using value_type = typename VecTy::value_type;
      35             :   using PtrUnion = PointerUnion<EltTy, VecTy *>;
      36             : 
      37             : private:
      38             :   PtrUnion Val;
      39             : 
      40             : public:
      41             :   TinyPtrVector() = default;
      42             : 
      43     1428843 :   ~TinyPtrVector() {
      44       13090 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      45       13090 :       delete V;
      46     1428843 :   }
      47             : 
      48         227 :   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
      49           6 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      50           6 :       Val = new VecTy(*V);
      51         227 :   }
      52             : 
      53         506 :   TinyPtrVector &operator=(const TinyPtrVector &RHS) {
      54         506 :     if (this == &RHS)
      55             :       return *this;
      56          16 :     if (RHS.empty()) {
      57             :       this->clear();
      58             :       return *this;
      59             :     }
      60             : 
      61             :     // Try to squeeze into the single slot. If it won't fit, allocate a copied
      62             :     // vector.
      63         498 :     if (Val.template is<EltTy>()) {
      64         474 :       if (RHS.size() == 1)
      65             :         Val = RHS.front();
      66             :       else
      67           0 :         Val = new VecTy(*RHS.Val.template get<VecTy*>());
      68             :       return *this;
      69             :     }
      70             : 
      71             :     // If we have a full vector allocated, try to re-use it.
      72          24 :     if (RHS.Val.template is<EltTy>()) {
      73             :       Val.template get<VecTy*>()->clear();
      74          16 :       Val.template get<VecTy*>()->push_back(RHS.front());
      75             :     } else {
      76             :       *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
      77             :     }
      78             :     return *this;
      79             :   }
      80             : 
      81       82389 :   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
      82             :     RHS.Val = (EltTy)nullptr;
      83             :   }
      84             : 
      85      388642 :   TinyPtrVector &operator=(TinyPtrVector &&RHS) {
      86      388642 :     if (this == &RHS)
      87             :       return *this;
      88          29 :     if (RHS.empty()) {
      89             :       this->clear();
      90             :       return *this;
      91             :     }
      92             : 
      93             :     // If this vector has been allocated on the heap, re-use it if cheap. If it
      94             :     // would require more copying, just delete it and we'll steal the other
      95             :     // side.
      96          26 :     if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
      97          26 :       if (RHS.Val.template is<EltTy>()) {
      98             :         V->clear();
      99          20 :         V->push_back(RHS.front());
     100             :         RHS.Val = (EltTy)nullptr;
     101          10 :         return *this;
     102             :       }
     103          16 :       delete V;
     104             :     }
     105             : 
     106       10651 :     Val = RHS.Val;
     107             :     RHS.Val = (EltTy)nullptr;
     108       10651 :     return *this;
     109             :   }
     110             : 
     111         130 :   TinyPtrVector(std::initializer_list<EltTy> IL)
     112             :       : Val(IL.size() == 0
     113             :                 ? PtrUnion()
     114             :                 : IL.size() == 1 ? PtrUnion(*IL.begin())
     115         260 :                                  : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
     116             : 
     117             :   /// Constructor from an ArrayRef.
     118             :   ///
     119             :   /// This also is a constructor for individual array elements due to the single
     120             :   /// element constructor for ArrayRef.
     121           7 :   explicit TinyPtrVector(ArrayRef<EltTy> Elts)
     122             :       : Val(Elts.empty()
     123             :                 ? PtrUnion()
     124             :                 : Elts.size() == 1
     125             :                       ? PtrUnion(Elts[0])
     126          18 :                       : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
     127             : 
     128             :   TinyPtrVector(size_t Count, EltTy Value)
     129             :       : Val(Count == 0 ? PtrUnion()
     130             :                        : Count == 1 ? PtrUnion(Value)
     131             :                                     : PtrUnion(new VecTy(Count, Value))) {}
     132             : 
     133             :   // implicit conversion operator to ArrayRef.
     134       13149 :   operator ArrayRef<EltTy>() const {
     135       13149 :     if (Val.isNull())
     136           0 :       return None;
     137       13149 :     if (Val.template is<EltTy>())
     138       12971 :       return *Val.getAddrOfPtr1();
     139         178 :     return *Val.template get<VecTy*>();
     140             :   }
     141             : 
     142             :   // implicit conversion operator to MutableArrayRef.
     143       56198 :   operator MutableArrayRef<EltTy>() {
     144       56198 :     if (Val.isNull())
     145       51579 :       return None;
     146        4619 :     if (Val.template is<EltTy>())
     147        4228 :       return *Val.getAddrOfPtr1();
     148         391 :     return *Val.template get<VecTy*>();
     149             :   }
     150             : 
     151             :   // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
     152             :   template<typename U,
     153             :            typename std::enable_if<
     154             :                std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
     155             :                bool>::type = false>
     156             :   operator ArrayRef<U>() const {
     157             :     return operator ArrayRef<EltTy>();
     158             :   }
     159             : 
     160             :   bool empty() const {
     161             :     // This vector can be empty if it contains no element, or if it
     162             :     // contains a pointer to an empty vector.
     163      724030 :     if (Val.isNull()) return true;
     164             :     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
     165       21825 :       return Vec->empty();
     166             :     return false;
     167             :   }
     168             : 
     169       33125 :   unsigned size() const {
     170        6000 :     if (empty())
     171             :       return 0;
     172       32151 :     if (Val.template is<EltTy>())
     173             :       return 1;
     174        5982 :     return Val.template get<VecTy*>()->size();
     175             :   }
     176             : 
     177             :   using iterator = EltTy *;
     178             :   using const_iterator = const EltTy *;
     179             :   using reverse_iterator = std::reverse_iterator<iterator>;
     180             :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     181             : 
     182             :   iterator begin() {
     183      655740 :     if (Val.template is<EltTy>())
     184             :       return Val.getAddrOfPtr1();
     185             : 
     186             :     return Val.template get<VecTy *>()->begin();
     187             :   }
     188             : 
     189             :   iterator end() {
     190      587655 :     if (Val.template is<EltTy>())
     191      569007 :       return begin() + (Val.isNull() ? 0 : 1);
     192             : 
     193             :     return Val.template get<VecTy *>()->end();
     194             :   }
     195             : 
     196             :   const_iterator begin() const {
     197             :     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
     198             :   }
     199             : 
     200             :   const_iterator end() const {
     201             :     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
     202             :   }
     203             : 
     204             :   reverse_iterator rbegin() { return reverse_iterator(end()); }
     205             :   reverse_iterator rend() { return reverse_iterator(begin()); }
     206             : 
     207             :   const_reverse_iterator rbegin() const {
     208             :     return const_reverse_iterator(end());
     209             :   }
     210             : 
     211             :   const_reverse_iterator rend() const {
     212             :     return const_reverse_iterator(begin());
     213             :   }
     214             : 
     215             :   EltTy operator[](unsigned i) const {
     216             :     assert(!Val.isNull() && "can't index into an empty vector");
     217          31 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     218             :       assert(i == 0 && "tinyvector index out of range");
     219             :       return V;
     220             :     }
     221             : 
     222             :     assert(i < Val.template get<VecTy*>()->size() &&
     223             :            "tinyvector index out of range");
     224        3016 :     return (*Val.template get<VecTy*>())[i];
     225             :   }
     226             : 
     227             :   EltTy front() const {
     228             :     assert(!empty() && "vector empty");
     229        1220 :     if (EltTy V = Val.template dyn_cast<EltTy>())
     230             :       return V;
     231        1002 :     return Val.template get<VecTy*>()->front();
     232             :   }
     233             : 
     234             :   EltTy back() const {
     235             :     assert(!empty() && "vector empty");
     236             :     if (EltTy V = Val.template dyn_cast<EltTy>())
     237             :       return V;
     238             :     return Val.template get<VecTy*>()->back();
     239             :   }
     240             : 
     241      127425 :   void push_back(EltTy NewVal) {
     242             :     assert(NewVal && "Can't add a null value");
     243             : 
     244             :     // If we have nothing, add something.
     245      127425 :     if (Val.isNull()) {
     246      104820 :       Val = NewVal;
     247             :       return;
     248             :     }
     249             : 
     250             :     // If we have a single value, convert to a vector.
     251       22605 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     252       13277 :       Val = new VecTy();
     253       13277 :       Val.template get<VecTy*>()->push_back(V);
     254             :     }
     255             : 
     256             :     // Add the new value, we know we have a vector.
     257       22605 :     Val.template get<VecTy*>()->push_back(NewVal);
     258             :   }
     259             : 
     260             :   void pop_back() {
     261             :     // If we have a single value, convert to empty.
     262          14 :     if (Val.template is<EltTy>())
     263             :       Val = (EltTy)nullptr;
     264          14 :     else if (VecTy *Vec = Val.template get<VecTy*>())
     265             :       Vec->pop_back();
     266             :   }
     267             : 
     268             :   void clear() {
     269             :     // If we have a single value, convert to empty.
     270      512539 :     if (Val.template is<EltTy>()) {
     271             :       Val = (EltTy)nullptr;
     272        1697 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     273             :       // If we have a vector form, just clear it.
     274             :       Vec->clear();
     275             :     }
     276             :     // Otherwise, we're already empty.
     277             :   }
     278             : 
     279          88 :   iterator erase(iterator I) {
     280             :     assert(I >= begin() && "Iterator to erase is out of bounds.");
     281             :     assert(I < end() && "Erasing at past-the-end iterator.");
     282             : 
     283             :     // If we have a single value, convert to empty.
     284          88 :     if (Val.template is<EltTy>()) {
     285           2 :       if (I == begin())
     286             :         Val = (EltTy)nullptr;
     287          86 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     288             :       // multiple items in a vector; just do the erase, there is no
     289             :       // benefit to collapsing back to a pointer
     290          86 :       return Vec->erase(I);
     291             :     }
     292             :     return end();
     293             :   }
     294             : 
     295         742 :   iterator erase(iterator S, iterator E) {
     296             :     assert(S >= begin() && "Range to erase is out of bounds.");
     297             :     assert(S <= E && "Trying to erase invalid range.");
     298             :     assert(E <= end() && "Trying to erase past the end.");
     299             : 
     300         742 :     if (Val.template is<EltTy>()) {
     301         625 :       if (S == begin() && S != E)
     302             :         Val = (EltTy)nullptr;
     303         117 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     304         117 :       return Vec->erase(S, E);
     305             :     }
     306             :     return end();
     307             :   }
     308             : 
     309           8 :   iterator insert(iterator I, const EltTy &Elt) {
     310             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     311             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     312           8 :     if (I == end()) {
     313           4 :       push_back(Elt);
     314           4 :       return std::prev(end());
     315             :     }
     316             :     assert(!Val.isNull() && "Null value with non-end insert iterator.");
     317           0 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     318             :       assert(I == begin());
     319           0 :       Val = Elt;
     320           0 :       push_back(V);
     321             :       return begin();
     322             :     }
     323             : 
     324           4 :     return Val.template get<VecTy*>()->insert(I, Elt);
     325             :   }
     326             : 
     327             :   template<typename ItTy>
     328       15447 :   iterator insert(iterator I, ItTy From, ItTy To) {
     329             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     330             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     331       15447 :     if (From == To)
     332             :       return I;
     333             : 
     334             :     // If we have a single value, convert to a vector.
     335         838 :     ptrdiff_t Offset = I - begin();
     336         419 :     if (Val.isNull()) {
     337         204 :       if (std::next(From) == To) {
     338         141 :         Val = *From;
     339             :         return begin();
     340             :       }
     341             : 
     342          63 :       Val = new VecTy();
     343         215 :     } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
     344           0 :       Val = new VecTy();
     345           0 :       Val.template get<VecTy*>()->push_back(V);
     346             :     }
     347         556 :     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
     348             :   }
     349             : };
     350             : 
     351             : } // end namespace llvm
     352             : 
     353             : #endif // LLVM_ADT_TINYPTRVECTOR_H

Generated by: LCOV version 1.13