LCOV - code coverage report
Current view: top level - include/llvm/ADT - SetVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 71 71 100.0 %
Date: 2017-09-14 15:23:50 Functions: 335 346 96.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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             : // This file implements a set that has insertion order iteration
      11             : // characteristics. This is useful for keeping a set of things that need to be
      12             : // visited later but in a deterministic order (insertion order). The interface
      13             : // is purposefully minimal.
      14             : //
      15             : // This file defines SetVector and SmallSetVector, which performs no allocations
      16             : // if the SetVector has less than a certain number of elements.
      17             : //
      18             : //===----------------------------------------------------------------------===//
      19             : 
      20             : #ifndef LLVM_ADT_SETVECTOR_H
      21             : #define LLVM_ADT_SETVECTOR_H
      22             : 
      23             : #include "llvm/ADT/ArrayRef.h"
      24             : #include "llvm/ADT/DenseSet.h"
      25             : #include "llvm/ADT/STLExtras.h"
      26             : #include "llvm/Support/Compiler.h"
      27             : #include <algorithm>
      28             : #include <cassert>
      29             : #include <iterator>
      30             : #include <vector>
      31             : 
      32             : namespace llvm {
      33             : 
      34             : /// \brief A vector that has set insertion semantics.
      35             : ///
      36             : /// This adapter class provides a way to keep a set of things that also has the
      37             : /// property of a deterministic iteration order. The order of iteration is the
      38             : /// order of insertion.
      39             : template <typename T, typename Vector = std::vector<T>,
      40             :           typename Set = DenseSet<T>>
      41    82120635 : class SetVector {
      42             : public:
      43             :   using value_type = T;
      44             :   using key_type = T;
      45             :   using reference = T&;
      46             :   using const_reference = const T&;
      47             :   using set_type = Set;
      48             :   using vector_type = Vector;
      49             :   using iterator = typename vector_type::const_iterator;
      50             :   using const_iterator = typename vector_type::const_iterator;
      51             :   using reverse_iterator = typename vector_type::const_reverse_iterator;
      52             :   using const_reverse_iterator = typename vector_type::const_reverse_iterator;
      53             :   using size_type = typename vector_type::size_type;
      54             : 
      55             :   /// \brief Construct an empty SetVector
      56    69071097 :   SetVector() = default;
      57             : 
      58             :   /// \brief Initialize a SetVector with a range of elements
      59             :   template<typename It>
      60       40917 :   SetVector(It Start, It End) {
      61       13639 :     insert(Start, End);
      62       13639 :   }
      63             : 
      64       50458 :   ArrayRef<T> getArrayRef() const { return vector_; }
      65             : 
      66             :   /// Clear the SetVector and return the underlying vector.
      67             :   Vector takeVector() {
      68        6332 :     set_.clear();
      69        6332 :     return std::move(vector_);
      70             :   }
      71             : 
      72             :   /// \brief Determine if the SetVector is empty or not.
      73             :   bool empty() const {
      74    18158427 :     return vector_.empty();
      75             :   }
      76             : 
      77             :   /// \brief Determine the number of elements in the SetVector.
      78             :   size_type size() const {
      79     3069902 :     return vector_.size();
      80             :   }
      81             : 
      82             :   /// \brief Get an iterator to the beginning of the SetVector.
      83             :   iterator begin() {
      84    33714527 :     return vector_.begin();
      85             :   }
      86             : 
      87             :   /// \brief Get a const_iterator to the beginning of the SetVector.
      88             :   const_iterator begin() const {
      89     3892236 :     return vector_.begin();
      90             :   }
      91             : 
      92             :   /// \brief Get an iterator to the end of the SetVector.
      93             :   iterator end() {
      94    33554197 :     return vector_.end();
      95             :   }
      96             : 
      97             :   /// \brief Get a const_iterator to the end of the SetVector.
      98             :   const_iterator end() const {
      99     3848059 :     return vector_.end();
     100             :   }
     101             : 
     102             :   /// \brief Get an reverse_iterator to the end of the SetVector.
     103             :   reverse_iterator rbegin() {
     104       49176 :     return vector_.rbegin();
     105             :   }
     106             : 
     107             :   /// \brief Get a const_reverse_iterator to the end of the SetVector.
     108             :   const_reverse_iterator rbegin() const {
     109             :     return vector_.rbegin();
     110             :   }
     111             : 
     112             :   /// \brief Get a reverse_iterator to the beginning of the SetVector.
     113             :   reverse_iterator rend() {
     114       49176 :     return vector_.rend();
     115             :   }
     116             : 
     117             :   /// \brief Get a const_reverse_iterator to the beginning of the SetVector.
     118             :   const_reverse_iterator rend() const {
     119             :     return vector_.rend();
     120             :   }
     121             : 
     122             :   /// \brief Return the first element of the SetVector.
     123             :   const T &front() const {
     124             :     assert(!empty() && "Cannot call front() on empty SetVector!");
     125             :     return vector_.front();
     126             :   }
     127             : 
     128             :   /// \brief Return the last element of the SetVector.
     129             :   const T &back() const {
     130             :     assert(!empty() && "Cannot call back() on empty SetVector!");
     131    18083514 :     return vector_.back();
     132             :   }
     133             : 
     134             :   /// \brief Index into the SetVector.
     135             :   const_reference operator[](size_type n) const {
     136             :     assert(n < vector_.size() && "SetVector access out of range!");
     137     2315909 :     return vector_[n];
     138             :   }
     139             : 
     140             :   /// \brief Insert a new element into the SetVector.
     141             :   /// \returns true if the element was inserted into the SetVector.
     142    17790096 :   bool insert(const value_type &X) {
     143    34389109 :     bool result = set_.insert(X).second;
     144    17790096 :     if (result)
     145    16519948 :       vector_.push_back(X);
     146    17790096 :     return result;
     147             :   }
     148             : 
     149             :   /// \brief Insert a range of elements into the SetVector.
     150             :   template<typename It>
     151      275628 :   void insert(It Start, It End) {
     152      804501 :     for (; Start != End; ++Start)
     153      851780 :       if (set_.insert(*Start).second)
     154      448199 :         vector_.push_back(*Start);
     155      275628 :   }
     156             : 
     157             :   /// \brief Remove an item from the set vector.
     158     2610689 :   bool remove(const value_type& X) {
     159     5221378 :     if (set_.erase(X)) {
     160     3561456 :       typename vector_type::iterator I = find(vector_, X);
     161             :       assert(I != vector_.end() && "Corrupted SetVector instances!");
     162     1882298 :       vector_.erase(I);
     163     1729943 :       return true;
     164             :     }
     165             :     return false;
     166             :   }
     167             : 
     168             :   /// Erase a single element from the set vector.
     169             :   /// \returns an iterator pointing to the next element that followed the
     170             :   /// element erased. This is the end of the SetVector if the last element is
     171             :   /// erased.
     172          43 :   iterator erase(iterator I) {
     173          43 :     const key_type &V = *I;
     174             :     assert(set_.count(V) && "Corrupted SetVector instances!");
     175          86 :     set_.erase(V);
     176             : 
     177             :     // FIXME: No need to use the non-const iterator when built with
     178             :     // std:vector.erase(const_iterator) as defined in C++11. This is for
     179             :     // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
     180          86 :     auto NI = vector_.begin();
     181         129 :     std::advance(NI, std::distance<iterator>(NI, I));
     182             : 
     183          88 :     return vector_.erase(NI);
     184             :   }
     185             : 
     186             :   /// \brief Remove items from the set vector based on a predicate function.
     187             :   ///
     188             :   /// This is intended to be equivalent to the following code, if we could
     189             :   /// write it:
     190             :   ///
     191             :   /// \code
     192             :   ///   V.erase(remove_if(V, P), V.end());
     193             :   /// \endcode
     194             :   ///
     195             :   /// However, SetVector doesn't expose non-const iterators, making any
     196             :   /// algorithm like remove_if impossible to use.
     197             :   ///
     198             :   /// \returns true if any element is removed.
     199             :   template <typename UnaryPredicate>
     200       55534 :   bool remove_if(UnaryPredicate P) {
     201       55588 :     typename vector_type::iterator I =
     202      113985 :         llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
     203      112315 :     if (I == vector_.end())
     204             :       return false;
     205       28870 :     vector_.erase(I, vector_.end());
     206       14256 :     return true;
     207             :   }
     208             : 
     209             :   /// \brief Count the number of elements of a given key in the SetVector.
     210             :   /// \returns 0 if the element is not in the SetVector, 1 if it is.
     211             :   size_type count(const key_type &key) const {
     212     5650005 :     return set_.count(key);
     213             :   }
     214             : 
     215             :   /// \brief Completely clear the SetVector
     216             :   void clear() {
     217     5627314 :     set_.clear();
     218     5627314 :     vector_.clear();
     219             :   }
     220             : 
     221             :   /// \brief Remove the last element of the SetVector.
     222             :   void pop_back() {
     223             :     assert(!empty() && "Cannot remove an element from an empty SetVector!");
     224    27058926 :     set_.erase(back());
     225    17880911 :     vector_.pop_back();
     226             :   }
     227             : 
     228          61 :   LLVM_NODISCARD T pop_back_val() {
     229     8364953 :     T Ret = back();
     230     8364953 :     pop_back();
     231          61 :     return Ret;
     232             :   }
     233             : 
     234             :   bool operator==(const SetVector &that) const {
     235             :     return vector_ == that.vector_;
     236             :   }
     237             : 
     238             :   bool operator!=(const SetVector &that) const {
     239             :     return vector_ != that.vector_;
     240             :   }
     241             : 
     242             :   /// \brief Compute This := This u S, return whether 'This' changed.
     243             :   /// TODO: We should be able to use set_union from SetOperations.h, but
     244             :   ///       SetVector interface is inconsistent with DenseSet.
     245             :   template <class STy>
     246             :   bool set_union(const STy &S) {
     247        1308 :     bool Changed = false;
     248             : 
     249        4720 :     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
     250             :          ++SI)
     251         796 :       if (insert(*SI))
     252             :         Changed = true;
     253             : 
     254             :     return Changed;
     255             :   }
     256             : 
     257             :   /// \brief Compute This := This - B
     258             :   /// TODO: We should be able to use set_subtract from SetOperations.h, but
     259             :   ///       SetVector interface is inconsistent with DenseSet.
     260             :   template <class STy>
     261             :   void set_subtract(const STy &S) {
     262        3273 :     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
     263             :          ++SI)
     264         627 :       remove(*SI);
     265             :   }
     266             : 
     267             : private:
     268             :   /// \brief A wrapper predicate designed for use with std::remove_if.
     269             :   ///
     270             :   /// This predicate wraps a predicate suitable for use with std::remove_if to
     271             :   /// call set_.erase(x) on each element which is slated for removal.
     272             :   template <typename UnaryPredicate>
     273       22412 :   class TestAndEraseFromSet {
     274             :     UnaryPredicate P;
     275             :     set_type &set_;
     276             : 
     277             :   public:
     278       55534 :     TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
     279       56396 :         : P(std::move(P)), set_(set_) {}
     280             : 
     281             :     template <typename ArgumentT>
     282      507908 :     bool operator()(const ArgumentT &Arg) {
     283      588020 :       if (P(Arg)) {
     284      661570 :         set_.erase(Arg);
     285      330771 :         return true;
     286             :       }
     287             :       return false;
     288             :     }
     289             :   };
     290             : 
     291             :   set_type set_;         ///< The set.
     292             :   vector_type vector_;   ///< The vector.
     293             : };
     294             : 
     295             : /// \brief A SetVector that performs no allocations if smaller than
     296             : /// a certain size.
     297             : template <typename T, unsigned N>
     298    24333777 : class SmallSetVector
     299             :     : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
     300             : public:
     301    41256774 :   SmallSetVector() = default;
     302             : 
     303             :   /// \brief Initialize a SmallSetVector with a range of elements
     304             :   template<typename It>
     305      141002 :   SmallSetVector(It Start, It End) {
     306       70501 :     this->insert(Start, End);
     307       70501 :   }
     308             : };
     309             : 
     310             : } // end namespace llvm
     311             : 
     312             : #endif // LLVM_ADT_SETVECTOR_H

Generated by: LCOV version 1.13