LCOV - code coverage report
Current view: top level - include/llvm/ADT - TinyPtrVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 251 278 90.3 %
Date: 2018-10-17 09:37:48 Functions: 88 91 96.7 %
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  1658533320 :   ~TinyPtrVector() {
      44    33135113 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      45    33135113 :       delete V;
      46  1658533320 :   }
      47      381665 : 
      48   346121955 :   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
      49    10982822 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      50    11364227 :       Val = new VecTy(*V);
      51   354056654 :   }
      52        1660 : 
      53       18940 :   TinyPtrVector &operator=(const TinyPtrVector &RHS) {
      54     7952239 :     if (this == &RHS)
      55             :       return *this;
      56           4 :     if (RHS.empty()) {
      57           2 :       this->clear();
      58       15657 :       return *this;
      59           4 :     }
      60           2 : 
      61           1 :     // Try to squeeze into the single slot. If it won't fit, allocate a copied
      62           1 :     // vector.
      63        1627 :     if (Val.template is<EltTy>()) {
      64           2 :       if (RHS.size() == 1)
      65           1 :         Val = RHS.front();
      66           1 :       else
      67           2 :         Val = new VecTy(*RHS.Val.template get<VecTy*>());
      68        1625 :       return *this;
      69          32 :     }
      70          32 : 
      71             :     // If we have a full vector allocated, try to re-use it.
      72           0 :     if (RHS.Val.template is<EltTy>()) {
      73             :       Val.template get<VecTy*>()->clear();
      74           8 :       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          24 :   }
      80           0 : 
      81      176694 :   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
      82             :     RHS.Val = (EltTy)nullptr;
      83           0 :   }
      84           0 : 
      85      452918 :   TinyPtrVector &operator=(TinyPtrVector &&RHS) {
      86      452918 :     if (this == &RHS)
      87             :       return *this;
      88          37 :     if (RHS.empty()) {
      89      297322 :       this->clear();
      90      424218 :       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          16 :     if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
      97          16 :       if (RHS.Val.template is<EltTy>()) {
      98             :         V->clear();
      99           0 :         V->push_back(RHS.front());
     100             :         RHS.Val = (EltTy)nullptr;
     101           4 :         return *this;
     102             :       }
     103           0 :       delete V;
     104             :     }
     105             : 
     106       28728 :     Val = RHS.Val;
     107           0 :     RHS.Val = (EltTy)nullptr;
     108       28716 :     return *this;
     109             :   }
     110           0 : 
     111         144 :   TinyPtrVector(std::initializer_list<EltTy> IL)
     112             :       : Val(IL.size() == 0
     113             :                 ? PtrUnion()
     114             :                 : IL.size() == 1 ? PtrUnion(*IL.begin())
     115         156 :                                  : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
     116             : 
     117           8 :   /// 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             :   explicit TinyPtrVector(ArrayRef<EltTy> Elts)
     122             :       : Val(Elts.empty()
     123          16 :                 ? PtrUnion()
     124          16 :                 : Elts.size() == 1
     125             :                       ? PtrUnion(Elts[0])
     126             :                       : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
     127             : 
     128           4 :   TinyPtrVector(size_t Count, EltTy Value)
     129             :       : Val(Count == 0 ? PtrUnion()
     130             :                        : Count == 1 ? PtrUnion(Value)
     131             :                                     : PtrUnion(new VecTy(Count, Value))) {}
     132             : 
     133          12 :   // implicit conversion operator to ArrayRef.
     134           0 :   operator ArrayRef<EltTy>() const {
     135       15354 :     if (Val.isNull())
     136             :       return None;
     137       15354 :     if (Val.template is<EltTy>())
     138           0 :       return *Val.getAddrOfPtr1();
     139             :     return *Val.template get<VecTy*>();
     140             :   }
     141             : 
     142          12 :   // implicit conversion operator to MutableArrayRef.
     143             :   operator MutableArrayRef<EltTy>() {
     144      139598 :     if (Val.isNull())
     145             :       return None;
     146       68235 :     if (Val.template is<EltTy>())
     147             :       return *Val.getAddrOfPtr1();
     148             :     return *Val.template get<VecTy*>();
     149             :   }
     150             : 
     151           2 :   // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
     152          99 :   template<typename U,
     153             :            typename std::enable_if<
     154          85 :                std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
     155          34 :                bool>::type = false>
     156          34 :   operator ArrayRef<U>() const {
     157             :     return operator ArrayRef<EltTy>();
     158          16 :   }
     159             : 
     160           8 :   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   419734915 :     if (Val.isNull()) return true;
     164             :     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
     165    21685232 :       return Vec->empty();
     166          26 :     return false;
     167          26 :   }
     168             : 
     169          20 :   unsigned size() const {
     170         386 :     if (empty())
     171      136894 :       return 0;
     172        3069 :     if (Val.template is<EltTy>())
     173       21286 :       return 1;
     174         386 :     return Val.template get<VecTy*>()->size();
     175             :   }
     176          16 : 
     177             :   using iterator = EltTy *;
     178        9086 :   using const_iterator = const EltTy *;
     179             :   using reverse_iterator = std::reverse_iterator<iterator>;
     180       37918 :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     181          17 : 
     182        9070 :   iterator begin() {
     183  1815207557 :     if (Val.template is<EltTy>())
     184             :       return Val.getAddrOfPtr1();
     185           4 : 
     186             :     return Val.template get<VecTy *>()->begin();
     187             :   }
     188             : 
     189             :   iterator end() {
     190  1789449348 :     if (Val.template is<EltTy>())
     191  1780295974 :       return begin() + (Val.isNull() ? 0 : 1);
     192          13 : 
     193             :     return Val.template get<VecTy *>()->end();
     194          10 :   }
     195             : 
     196           5 :   const_iterator begin() const {
     197             :     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
     198    40260555 :   }
     199    36280102 : 
     200             :   const_iterator end() const {
     201           8 :     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
     202             :   }
     203           8 : 
     204             :   reverse_iterator rbegin() { return reverse_iterator(end()); }
     205          17 :   reverse_iterator rend() { return reverse_iterator(begin()); }
     206          17 : 
     207             :   const_reverse_iterator rbegin() const {
     208           8 :     return const_reverse_iterator(end());
     209             :   }
     210           4 : 
     211             :   const_reverse_iterator rend() const {
     212             :     return const_reverse_iterator(begin());
     213             :   }
     214             : 
     215             :   EltTy operator[](unsigned i) const {
     216          13 :     assert(!Val.isNull() && "can't index into an empty vector");
     217          19 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     218             :       assert(i == 0 && "tinyvector index out of range");
     219          10 :       return V;
     220             :     }
     221           5 : 
     222             :     assert(i < Val.template get<VecTy*>()->size() &&
     223           8 :            "tinyvector index out of range");
     224          20 :     return (*Val.template get<VecTy*>())[i];
     225           1 :   }
     226           8 : 
     227             :   EltTy front() const {
     228           8 :     assert(!empty() && "vector empty");
     229        1490 :     if (EltTy V = Val.template dyn_cast<EltTy>())
     230             :       return V;
     231        1037 :     return Val.template get<VecTy*>()->front();
     232          11 :   }
     233             : 
     234             :   EltTy back() const {
     235             :     assert(!empty() && "vector empty");
     236          20 :     if (EltTy V = Val.template dyn_cast<EltTy>())
     237             :       return V;
     238           1 :     return Val.template get<VecTy*>()->back();
     239             :   }
     240             : 
     241    55290406 :   void push_back(EltTy NewVal) {
     242             :     assert(NewVal && "Can't add a null value");
     243             : 
     244             :     // If we have nothing, add something.
     245    55290399 :     if (Val.isNull()) {
     246    31462123 :       Val = NewVal;
     247    31462118 :       return;
     248             :     }
     249      435016 : 
     250             :     // If we have a single value, convert to a vector.
     251    23828283 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     252    21580548 :       Val = new VecTy();
     253    22015567 :       Val.template get<VecTy*>()->push_back(V);
     254      428469 :     }
     255      428469 : 
     256             :     // Add the new value, we know we have a vector.
     257    23828283 :     Val.template get<VecTy*>()->push_back(NewVal);
     258           5 :   }
     259        6547 : 
     260        3304 :   void pop_back() {
     261        3304 :     // If we have a single value, convert to empty.
     262             :     if (Val.template is<EltTy>())
     263             :       Val = (EltTy)nullptr;
     264             :     else if (VecTy *Vec = Val.template get<VecTy*>())
     265        6547 :       Vec->pop_back();
     266             :   }
     267      419103 : 
     268             :   void clear() {
     269             :     // If we have a single value, convert to empty.
     270   585468236 :     if (Val.template is<EltTy>()) {
     271      419103 :       Val = (EltTy)nullptr;
     272     1484054 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     273      417442 :       // If we have a vector form, just clear it.
     274             :       Vec->clear();
     275             :     }
     276           1 :     // Otherwise, we're already empty.
     277        1661 :   }
     278      296224 : 
     279       46911 :   iterator erase(iterator I) {
     280        1439 :     assert(I >= begin() && "Iterator to erase is out of bounds.");
     281             :     assert(I < end() && "Erasing at past-the-end iterator.");
     282             : 
     283        1661 :     // If we have a single value, convert to empty.
     284       45264 :     if (Val.template is<EltTy>()) {
     285       46881 :       if (I == begin())
     286             :         Val = (EltTy)nullptr;
     287        1679 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     288             :       // multiple items in a vector; just do the erase, there is no
     289        3296 :       // benefit to collapsing back to a pointer
     290        2629 :       return Vec->erase(I);
     291         950 :     }
     292             :     return end();
     293             :   }
     294             : 
     295        2917 :   iterator erase(iterator S, iterator E) {
     296         306 :     assert(S >= begin() && "Range to erase is out of bounds.");
     297         340 :     assert(S <= E && "Trying to erase invalid range.");
     298             :     assert(E <= end() && "Trying to erase past the end.");
     299             : 
     300         499 :     if (Val.template is<EltTy>()) {
     301        2780 :       if (S == begin() && S != E)
     302           2 :         Val = (EltTy)nullptr;
     303         104 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     304          68 :       return Vec->erase(S, E);
     305             :     }
     306           2 :     return end();
     307             :   }
     308          39 : 
     309           0 :   iterator insert(iterator I, const EltTy &Elt) {
     310             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     311          39 :     assert(I <= this->end() && "Inserting past the end of the vector.");
     312          39 :     if (I == end()) {
     313             :       push_back(Elt);
     314             :       return std::prev(end());
     315          74 :     }
     316             :     assert(!Val.isNull() && "Null value with non-end insert iterator.");
     317             :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     318             :       assert(I == begin());
     319             :       Val = Elt;
     320             :       push_back(V);
     321             :       return begin();
     322         118 :     }
     323          36 : 
     324             :     return Val.template get<VecTy*>()->insert(I, Elt);
     325             :   }
     326             : 
     327             :   template<typename ItTy>
     328   260968935 :   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   260968935 :     if (From == To)
     332             :       return I;
     333             : 
     334             :     // If we have a single value, convert to a vector.
     335     3999352 :     ptrdiff_t Offset = I - begin();
     336     4011924 :     if (Val.isNull()) {
     337     3680923 :       if (std::next(From) == To) {
     338     3254597 :         Val = *From;
     339       13138 :         return begin();
     340             :       }
     341             : 
     342      426326 :       Val = new VecTy();
     343      318674 :     } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
     344      144585 :       Val = new VecTy();
     345      144094 :       Val.template get<VecTy*>()->push_back(V);
     346           0 :     }
     347     1489796 :     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
     348         286 :   }
     349           0 : };
     350          40 : 
     351         205 : } // end namespace llvm
     352           0 : 
     353           0 : #endif // LLVM_ADT_TINYPTRVECTOR_H

Generated by: LCOV version 1.13