LCOV - code coverage report
Current view: top level - include/llvm/ADT - TinyPtrVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 109 116 94.0 %
Date: 2017-09-14 15:23:50 Functions: 82 86 95.3 %
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      606926 :   TinyPtrVector() = default;
      42             : 
      43      328893 :   ~TinyPtrVector() {
      44      336441 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      45        7548 :       delete V;
      46      328893 :   }
      47             : 
      48          26 :   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
      49          28 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      50           6 :       Val = new VecTy(*V);
      51          26 :   }
      52             : 
      53          33 :   TinyPtrVector &operator=(const TinyPtrVector &RHS) {
      54          33 :     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          50 :     if (Val.template is<EltTy>()) {
      64           1 :       if (RHS.size() == 1)
      65           2 :         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          48 :     if (RHS.Val.template is<EltTy>()) {
      73          24 :       Val.template get<VecTy*>()->clear();
      74          24 :       Val.template get<VecTy*>()->push_back(RHS.front());
      75             :     } else {
      76          48 :       *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
      77             :     }
      78             :     return *this;
      79             :   }
      80             : 
      81       40091 :   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
      82       80182 :     RHS.Val = (EltTy)nullptr;
      83             :   }
      84             : 
      85          32 :   TinyPtrVector &operator=(TinyPtrVector &&RHS) {
      86          32 :     if (this == &RHS)
      87             :       return *this;
      88          16 :     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          48 :     if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
      97          48 :       if (RHS.Val.template is<EltTy>()) {
      98          16 :         V->clear();
      99          16 :         V->push_back(RHS.front());
     100           8 :         return *this;
     101             :       }
     102          16 :       delete V;
     103             :     }
     104             : 
     105          16 :     Val = RHS.Val;
     106          32 :     RHS.Val = (EltTy)nullptr;
     107          16 :     return *this;
     108             :   }
     109             : 
     110             :   /// Constructor from an ArrayRef.
     111             :   ///
     112             :   /// This also is a constructor for individual array elements due to the single
     113             :   /// element constructor for ArrayRef.
     114           3 :   explicit TinyPtrVector(ArrayRef<EltTy> Elts)
     115             :       : Val(Elts.empty()
     116           3 :                 ? PtrUnion()
     117           3 :                 : Elts.size() == 1
     118           1 :                       ? PtrUnion(Elts[0])
     119          16 :                       : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
     120             : 
     121             :   TinyPtrVector(size_t Count, EltTy Value)
     122             :       : Val(Count == 0 ? PtrUnion()
     123             :                        : Count == 1 ? PtrUnion(Value)
     124             :                                     : PtrUnion(new VecTy(Count, Value))) {}
     125             : 
     126             :   // implicit conversion operator to ArrayRef.
     127       11277 :   operator ArrayRef<EltTy>() const {
     128       22554 :     if (Val.isNull())
     129           0 :       return None;
     130       22554 :     if (Val.template is<EltTy>())
     131       22206 :       return *Val.getAddrOfPtr1();
     132         522 :     return *Val.template get<VecTy*>();
     133             :   }
     134             : 
     135             :   // implicit conversion operator to MutableArrayRef.
     136       51744 :   operator MutableArrayRef<EltTy>() {
     137      103488 :     if (Val.isNull())
     138       47484 :       return None;
     139        8520 :     if (Val.template is<EltTy>())
     140       11616 :       return *Val.getAddrOfPtr1();
     141        1164 :     return *Val.template get<VecTy*>();
     142             :   }
     143             : 
     144             :   // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
     145             :   template<typename U,
     146             :            typename std::enable_if<
     147             :                std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
     148             :                bool>::type = false>
     149             :   operator ArrayRef<U>() const {
     150             :     return operator ArrayRef<EltTy>();
     151             :   }
     152             : 
     153             :   bool empty() const {
     154             :     // This vector can be empty if it contains no element, or if it
     155             :     // contains a pointer to an empty vector.
     156      206522 :     if (Val.isNull()) return true;
     157      101774 :     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
     158       18788 :       return Vec->empty();
     159             :     return false;
     160             :   }
     161             : 
     162       36730 :   unsigned size() const {
     163        5547 :     if (empty())
     164             :       return 0;
     165       71520 :     if (Val.template is<EltTy>())
     166             :       return 1;
     167       16587 :     return Val.template get<VecTy*>()->size();
     168             :   }
     169             : 
     170             :   using iterator = EltTy *;
     171             :   using const_iterator = const EltTy *;
     172             :   using reverse_iterator = std::reverse_iterator<iterator>;
     173             :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     174             : 
     175             :   iterator begin() {
     176      769700 :     if (Val.template is<EltTy>())
     177      715518 :       return Val.getAddrOfPtr1();
     178             : 
     179       81261 :     return Val.template get<VecTy *>()->begin();
     180             :   }
     181             : 
     182             :   iterator end() {
     183      377330 :     if (Val.template is<EltTy>())
     184      333902 :       return begin() + (Val.isNull() ? 0 : 1);
     185             : 
     186       56526 :     return Val.template get<VecTy *>()->end();
     187             :   }
     188             : 
     189             :   const_iterator begin() const {
     190       47791 :     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
     191             :   }
     192             : 
     193             :   const_iterator end() const {
     194         993 :     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
     195             :   }
     196             : 
     197             :   reverse_iterator rbegin() { return reverse_iterator(end()); }
     198             :   reverse_iterator rend() { return reverse_iterator(begin()); }
     199             : 
     200             :   const_reverse_iterator rbegin() const {
     201             :     return const_reverse_iterator(end());
     202             :   }
     203             : 
     204             :   const_reverse_iterator rend() const {
     205             :     return const_reverse_iterator(begin());
     206             :   }
     207             : 
     208             :   EltTy operator[](unsigned i) const {
     209             :     assert(!Val.isNull() && "can't index into an empty vector");
     210        2934 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     211             :       assert(i == 0 && "tinyvector index out of range");
     212             :       return V;
     213             :     }
     214             : 
     215             :     assert(i < Val.template get<VecTy*>()->size() &&
     216             :            "tinyvector index out of range");
     217        8616 :     return (*Val.template get<VecTy*>())[i];
     218             :   }
     219             : 
     220             :   EltTy front() const {
     221             :     assert(!empty() && "vector empty");
     222        2419 :     if (EltTy V = Val.template dyn_cast<EltTy>())
     223             :       return V;
     224        2025 :     return Val.template get<VecTy*>()->front();
     225             :   }
     226             : 
     227             :   EltTy back() const {
     228             :     assert(!empty() && "vector empty");
     229             :     if (EltTy V = Val.template dyn_cast<EltTy>())
     230             :       return V;
     231             :     return Val.template get<VecTy*>()->back();
     232             :   }
     233             : 
     234       63917 :   void push_back(EltTy NewVal) {
     235             :     assert(NewVal && "Can't add a null value");
     236             : 
     237             :     // If we have nothing, add something.
     238      127834 :     if (Val.isNull()) {
     239       50978 :       Val = NewVal;
     240             :       return;
     241             :     }
     242             : 
     243             :     // If we have a single value, convert to a vector.
     244       25878 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     245       22845 :       Val = new VecTy();
     246       15230 :       Val.template get<VecTy*>()->push_back(V);
     247             :     }
     248             : 
     249             :     // Add the new value, we know we have a vector.
     250       25878 :     Val.template get<VecTy*>()->push_back(NewVal);
     251             :   }
     252             : 
     253             :   void pop_back() {
     254             :     // If we have a single value, convert to empty.
     255          28 :     if (Val.template is<EltTy>())
     256           0 :       Val = (EltTy)nullptr;
     257          28 :     else if (VecTy *Vec = Val.template get<VecTy*>())
     258          14 :       Vec->pop_back();
     259             :   }
     260             : 
     261             :   void clear() {
     262             :     // If we have a single value, convert to empty.
     263       23634 :     if (Val.template is<EltTy>()) {
     264       20692 :       Val = (EltTy)nullptr;
     265        2942 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     266             :       // If we have a vector form, just clear it.
     267        1471 :       Vec->clear();
     268             :     }
     269             :     // Otherwise, we're already empty.
     270             :   }
     271             : 
     272          88 :   iterator erase(iterator I) {
     273             :     assert(I >= begin() && "Iterator to erase is out of bounds.");
     274             :     assert(I < end() && "Erasing at past-the-end iterator.");
     275             : 
     276             :     // If we have a single value, convert to empty.
     277         176 :     if (Val.template is<EltTy>()) {
     278           2 :       if (I == begin())
     279           4 :         Val = (EltTy)nullptr;
     280         172 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     281             :       // multiple items in a vector; just do the erase, there is no
     282             :       // benefit to collapsing back to a pointer
     283         172 :       return Vec->erase(I);
     284             :     }
     285             :     return end();
     286             :   }
     287             : 
     288         714 :   iterator erase(iterator S, iterator E) {
     289             :     assert(S >= begin() && "Range to erase is out of bounds.");
     290             :     assert(S <= E && "Trying to erase invalid range.");
     291             :     assert(E <= end() && "Trying to erase past the end.");
     292             : 
     293        1428 :     if (Val.template is<EltTy>()) {
     294         597 :       if (S == begin() && S != E)
     295         754 :         Val = (EltTy)nullptr;
     296         234 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     297         234 :       return Vec->erase(S, E);
     298             :     }
     299             :     return end();
     300             :   }
     301             : 
     302           8 :   iterator insert(iterator I, const EltTy &Elt) {
     303             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     304             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     305           8 :     if (I == end()) {
     306           4 :       push_back(Elt);
     307           8 :       return std::prev(end());
     308             :     }
     309             :     assert(!Val.isNull() && "Null value with non-end insert iterator.");
     310           4 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     311             :       assert(I == begin());
     312           0 :       Val = Elt;
     313           0 :       push_back(V);
     314             :       return begin();
     315             :     }
     316             : 
     317           8 :     return Val.template get<VecTy*>()->insert(I, Elt);
     318             :   }
     319             : 
     320             :   template<typename ItTy>
     321       10112 :   iterator insert(iterator I, ItTy From, ItTy To) {
     322             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     323             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     324       10112 :     if (From == To)
     325             :       return I;
     326             : 
     327             :     // If we have a single value, convert to a vector.
     328         836 :     ptrdiff_t Offset = I - begin();
     329         836 :     if (Val.isNull()) {
     330         207 :       if (std::next(From) == To) {
     331         280 :         Val = *From;
     332             :         return begin();
     333             :       }
     334             : 
     335         189 :       Val = new VecTy();
     336         430 :     } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
     337           0 :       Val = new VecTy();
     338           0 :       Val.template get<VecTy*>()->push_back(V);
     339             :     }
     340         834 :     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
     341             :   }
     342             : };
     343             : 
     344             : } // end namespace llvm
     345             : 
     346             : #endif // LLVM_ADT_TINYPTRVECTOR_H

Generated by: LCOV version 1.13