LCOV - code coverage report
Current view: top level - include/llvm/ADT - TinyPtrVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 87 94 92.6 %
Date: 2018-05-20 00:06:23 Functions: 91 94 96.8 %
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     1395240 :   ~TinyPtrVector() {
      44       13270 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      45       13270 :       delete V;
      46     1395240 :   }
      47             : 
      48          97 :   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
      49           6 :     if (VecTy *V = Val.template dyn_cast<VecTy*>())
      50           6 :       Val = new VecTy(*V);
      51          97 :   }
      52             : 
      53         478 :   TinyPtrVector &operator=(const TinyPtrVector &RHS) {
      54         478 :     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         470 :     if (Val.template is<EltTy>()) {
      64         446 :       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       80978 :   TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
      82             :     RHS.Val = (EltTy)nullptr;
      83             :   }
      84             : 
      85      379651 :   TinyPtrVector &operator=(TinyPtrVector &&RHS) {
      86      379651 :     if (this == &RHS)
      87             :       return *this;
      88          26 :     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        9727 :     Val = RHS.Val;
     107             :     RHS.Val = (EltTy)nullptr;
     108        9727 :     return *this;
     109             :   }
     110             : 
     111             :   /// Constructor from an ArrayRef.
     112             :   ///
     113             :   /// This also is a constructor for individual array elements due to the single
     114             :   /// element constructor for ArrayRef.
     115           7 :   explicit TinyPtrVector(ArrayRef<EltTy> Elts)
     116             :       : Val(Elts.empty()
     117             :                 ? PtrUnion()
     118             :                 : Elts.size() == 1
     119             :                       ? PtrUnion(Elts[0])
     120          18 :                       : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
     121             : 
     122             :   TinyPtrVector(size_t Count, EltTy Value)
     123             :       : Val(Count == 0 ? PtrUnion()
     124             :                        : Count == 1 ? PtrUnion(Value)
     125             :                                     : PtrUnion(new VecTy(Count, Value))) {}
     126             : 
     127             :   // implicit conversion operator to ArrayRef.
     128       13001 :   operator ArrayRef<EltTy>() const {
     129       13001 :     if (Val.isNull())
     130           0 :       return None;
     131       13001 :     if (Val.template is<EltTy>())
     132       12824 :       return *Val.getAddrOfPtr1();
     133         177 :     return *Val.template get<VecTy*>();
     134             :   }
     135             : 
     136             :   // implicit conversion operator to MutableArrayRef.
     137     1009655 :   operator MutableArrayRef<EltTy>() {
     138     1009655 :     if (Val.isNull())
     139     1005116 :       return None;
     140        4539 :     if (Val.template is<EltTy>())
     141        4151 :       return *Val.getAddrOfPtr1();
     142         388 :     return *Val.template get<VecTy*>();
     143             :   }
     144             : 
     145             :   // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
     146             :   template<typename U,
     147             :            typename std::enable_if<
     148             :                std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
     149             :                bool>::type = false>
     150             :   operator ArrayRef<U>() const {
     151             :     return operator ArrayRef<EltTy>();
     152             :   }
     153             : 
     154             :   bool empty() const {
     155             :     // This vector can be empty if it contains no element, or if it
     156             :     // contains a pointer to an empty vector.
     157     1151736 :     if (Val.isNull()) return true;
     158             :     if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
     159       21161 :       return Vec->empty();
     160             :     return false;
     161             :   }
     162             : 
     163      144285 :   unsigned size() const {
     164        5842 :     if (empty())
     165             :       return 0;
     166      143311 :     if (Val.template is<EltTy>())
     167             :       return 1;
     168        5824 :     return Val.template get<VecTy*>()->size();
     169             :   }
     170             : 
     171             :   using iterator = EltTy *;
     172             :   using const_iterator = const EltTy *;
     173             :   using reverse_iterator = std::reverse_iterator<iterator>;
     174             :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     175             : 
     176             :   iterator begin() {
     177      999089 :     if (Val.template is<EltTy>())
     178             :       return Val.getAddrOfPtr1();
     179             : 
     180             :     return Val.template get<VecTy *>()->begin();
     181             :   }
     182             : 
     183             :   iterator end() {
     184      720562 :     if (Val.template is<EltTy>())
     185      702505 :       return begin() + (Val.isNull() ? 0 : 1);
     186             : 
     187             :     return Val.template get<VecTy *>()->end();
     188             :   }
     189             : 
     190             :   const_iterator begin() const {
     191             :     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
     192             :   }
     193             : 
     194             :   const_iterator end() const {
     195             :     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
     196             :   }
     197             : 
     198             :   reverse_iterator rbegin() { return reverse_iterator(end()); }
     199             :   reverse_iterator rend() { return reverse_iterator(begin()); }
     200             : 
     201             :   const_reverse_iterator rbegin() const {
     202             :     return const_reverse_iterator(end());
     203             :   }
     204             : 
     205             :   const_reverse_iterator rend() const {
     206             :     return const_reverse_iterator(begin());
     207             :   }
     208             : 
     209             :   EltTy operator[](unsigned i) const {
     210             :     assert(!Val.isNull() && "can't index into an empty vector");
     211          31 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     212             :       assert(i == 0 && "tinyvector index out of range");
     213             :       return V;
     214             :     }
     215             : 
     216             :     assert(i < Val.template get<VecTy*>()->size() &&
     217             :            "tinyvector index out of range");
     218        3016 :     return (*Val.template get<VecTy*>())[i];
     219             :   }
     220             : 
     221             :   EltTy front() const {
     222             :     assert(!empty() && "vector empty");
     223        1134 :     if (EltTy V = Val.template dyn_cast<EltTy>())
     224             :       return V;
     225         940 :     return Val.template get<VecTy*>()->front();
     226             :   }
     227             : 
     228             :   EltTy back() const {
     229             :     assert(!empty() && "vector empty");
     230             :     if (EltTy V = Val.template dyn_cast<EltTy>())
     231             :       return V;
     232             :     return Val.template get<VecTy*>()->back();
     233             :   }
     234             : 
     235      129501 :   void push_back(EltTy NewVal) {
     236             :     assert(NewVal && "Can't add a null value");
     237             : 
     238             :     // If we have nothing, add something.
     239      129501 :     if (Val.isNull()) {
     240      106914 :       Val = NewVal;
     241             :       return;
     242             :     }
     243             : 
     244             :     // If we have a single value, convert to a vector.
     245       22587 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     246       13482 :       Val = new VecTy();
     247       13482 :       Val.template get<VecTy*>()->push_back(V);
     248             :     }
     249             : 
     250             :     // Add the new value, we know we have a vector.
     251       22587 :     Val.template get<VecTy*>()->push_back(NewVal);
     252             :   }
     253             : 
     254             :   void pop_back() {
     255             :     // If we have a single value, convert to empty.
     256          14 :     if (Val.template is<EltTy>())
     257             :       Val = (EltTy)nullptr;
     258          14 :     else if (VecTy *Vec = Val.template get<VecTy*>())
     259             :       Vec->pop_back();
     260             :   }
     261             : 
     262             :   void clear() {
     263             :     // If we have a single value, convert to empty.
     264      511440 :     if (Val.template is<EltTy>()) {
     265             :       Val = (EltTy)nullptr;
     266        1631 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     267             :       // If we have a vector form, just clear it.
     268             :       Vec->clear();
     269             :     }
     270             :     // Otherwise, we're already empty.
     271             :   }
     272             : 
     273          88 :   iterator erase(iterator I) {
     274             :     assert(I >= begin() && "Iterator to erase is out of bounds.");
     275             :     assert(I < end() && "Erasing at past-the-end iterator.");
     276             : 
     277             :     // If we have a single value, convert to empty.
     278          88 :     if (Val.template is<EltTy>()) {
     279           2 :       if (I == begin())
     280             :         Val = (EltTy)nullptr;
     281          86 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     282             :       // multiple items in a vector; just do the erase, there is no
     283             :       // benefit to collapsing back to a pointer
     284          86 :       return Vec->erase(I);
     285             :     }
     286             :     return end();
     287             :   }
     288             : 
     289         742 :   iterator erase(iterator S, iterator E) {
     290             :     assert(S >= begin() && "Range to erase is out of bounds.");
     291             :     assert(S <= E && "Trying to erase invalid range.");
     292             :     assert(E <= end() && "Trying to erase past the end.");
     293             : 
     294         742 :     if (Val.template is<EltTy>()) {
     295         625 :       if (S == begin() && S != E)
     296             :         Val = (EltTy)nullptr;
     297         117 :     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
     298         117 :       return Vec->erase(S, E);
     299             :     }
     300             :     return end();
     301             :   }
     302             : 
     303           8 :   iterator insert(iterator I, const EltTy &Elt) {
     304             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     305             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     306           8 :     if (I == end()) {
     307           4 :       push_back(Elt);
     308           4 :       return std::prev(end());
     309             :     }
     310             :     assert(!Val.isNull() && "Null value with non-end insert iterator.");
     311           0 :     if (EltTy V = Val.template dyn_cast<EltTy>()) {
     312             :       assert(I == begin());
     313           0 :       Val = Elt;
     314           0 :       push_back(V);
     315             :       return begin();
     316             :     }
     317             : 
     318           4 :     return Val.template get<VecTy*>()->insert(I, Elt);
     319             :   }
     320             : 
     321             :   template<typename ItTy>
     322       27309 :   iterator insert(iterator I, ItTy From, ItTy To) {
     323             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     324             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     325       27309 :     if (From == To)
     326             :       return I;
     327             : 
     328             :     // If we have a single value, convert to a vector.
     329         836 :     ptrdiff_t Offset = I - begin();
     330         418 :     if (Val.isNull()) {
     331         203 :       if (std::next(From) == To) {
     332         141 :         Val = *From;
     333             :         return begin();
     334             :       }
     335             : 
     336          62 :       Val = new VecTy();
     337         215 :     } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
     338           0 :       Val = new VecTy();
     339           0 :       Val.template get<VecTy*>()->push_back(V);
     340             :     }
     341         554 :     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
     342             :   }
     343             : };
     344             : 
     345             : } // end namespace llvm
     346             : 
     347             : #endif // LLVM_ADT_TINYPTRVECTOR_H

Generated by: LCOV version 1.13