LCOV - code coverage report
Current view: top level - include/llvm/ADT - PriorityWorklist.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 47 47 100.0 %
Date: 2018-02-18 16:14:26 Functions: 28 32 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- PriorityWorklist.h - Worklist with insertion priority ----*- 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             : /// \file
      11             : ///
      12             : /// This file provides a priority worklist. See the class comments for details.
      13             : ///
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #ifndef LLVM_ADT_PRIORITYWORKLIST_H
      17             : #define LLVM_ADT_PRIORITYWORKLIST_H
      18             : 
      19             : #include "llvm/ADT/DenseMap.h"
      20             : #include "llvm/ADT/STLExtras.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/Support/Compiler.h"
      23             : #include <algorithm>
      24             : #include <cassert>
      25             : #include <cstddef>
      26             : #include <iterator>
      27             : #include <type_traits>
      28             : #include <vector>
      29             : 
      30             : namespace llvm {
      31             : 
      32             : /// A FILO worklist that prioritizes on re-insertion without duplication.
      33             : ///
      34             : /// This is very similar to a \c SetVector with the primary difference that
      35             : /// while re-insertion does not create a duplicate, it does adjust the
      36             : /// visitation order to respect the last insertion point. This can be useful
      37             : /// when the visit order needs to be prioritized based on insertion point
      38             : /// without actually having duplicate visits.
      39             : ///
      40             : /// Note that this doesn't prevent re-insertion of elements which have been
      41             : /// visited -- if you need to break cycles, a set will still be necessary.
      42             : ///
      43             : /// The type \c T must be default constructable to a null value that will be
      44             : /// ignored. It is an error to insert such a value, and popping elements will
      45             : /// never produce such a value. It is expected to be used with common nullable
      46             : /// types like pointers or optionals.
      47             : ///
      48             : /// Internally this uses a vector to store the worklist and a map to identify
      49             : /// existing elements in the worklist. Both of these may be customized, but the
      50             : /// map must support the basic DenseMap API for mapping from a T to an integer
      51             : /// index into the vector.
      52             : ///
      53             : /// A partial specialization is provided to automatically select a SmallVector
      54             : /// and a SmallDenseMap if custom data structures are not provided.
      55             : template <typename T, typename VectorT = std::vector<T>,
      56             :           typename MapT = DenseMap<T, ptrdiff_t>>
      57        2158 : class PriorityWorklist {
      58             : public:
      59             :   using value_type = T;
      60             :   using key_type = T;
      61             :   using reference = T&;
      62             :   using const_reference = const T&;
      63             :   using size_type = typename MapT::size_type;
      64             : 
      65             :   /// Construct an empty PriorityWorklist
      66             :   PriorityWorklist() = default;
      67             : 
      68             :   /// Determine if the PriorityWorklist is empty or not.
      69             :   bool empty() const {
      70             :     return V.empty();
      71             :   }
      72             : 
      73             :   /// Returns the number of elements in the worklist.
      74             :   size_type size() const {
      75             :     return M.size();
      76             :   }
      77             : 
      78             :   /// Count the number of elements of a given key in the PriorityWorklist.
      79             :   /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is.
      80             :   size_type count(const key_type &key) const {
      81             :     return M.count(key);
      82             :   }
      83             : 
      84             :   /// Return the last element of the PriorityWorklist.
      85             :   const T &back() const {
      86             :     assert(!empty() && "Cannot call back() on empty PriorityWorklist!");
      87             :     return V.back();
      88             :   }
      89             : 
      90             :   /// Insert a new element into the PriorityWorklist.
      91             :   /// \returns true if the element was inserted into the PriorityWorklist.
      92        1895 :   bool insert(const T &X) {
      93             :     assert(X != T() && "Cannot insert a null (default constructed) value!");
      94        3790 :     auto InsertResult = M.insert({X, V.size()});
      95        1895 :     if (InsertResult.second) {
      96             :       // Fresh value, just append it to the vector.
      97        1873 :       V.push_back(X);
      98        1873 :       return true;
      99             :     }
     100             : 
     101             :     auto &Index = InsertResult.first->second;
     102             :     assert(V[Index] == X && "Value not actually at index in map!");
     103          44 :     if (Index != (ptrdiff_t)(V.size() - 1)) {
     104             :       // If the element isn't at the back, null it out and append a fresh one.
     105          28 :       V[Index] = T();
     106          14 :       Index = (ptrdiff_t)V.size();
     107          14 :       V.push_back(X);
     108             :     }
     109             :     return false;
     110             :   }
     111             : 
     112             :   /// Insert a sequence of new elements into the PriorityWorklist.
     113             :   template <typename SequenceT>
     114             :   typename std::enable_if<!std::is_convertible<SequenceT, T>::value>::type
     115         596 :   insert(SequenceT &&Input) {
     116         594 :     if (std::begin(Input) == std::end(Input))
     117             :       // Nothing to do for an empty input sequence.
     118             :       return;
     119             : 
     120             :     // First pull the input sequence into the vector as a bulk append
     121             :     // operation.
     122             :     ptrdiff_t StartIndex = V.size();
     123         597 :     V.insert(V.end(), std::begin(Input), std::end(Input));
     124             :     // Now walk backwards fixing up the index map and deleting any duplicates.
     125        1337 :     for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
     126        1486 :       auto InsertResult = M.insert({V[i], i});
     127         743 :       if (InsertResult.second)
     128        1476 :         continue;
     129             : 
     130             :       // If the existing index is before this insert's start, nuke that one and
     131             :       // move it up.
     132             :       ptrdiff_t &Index = InsertResult.first->second;
     133          14 :       if (Index < StartIndex) {
     134          12 :         V[Index] = T();
     135           6 :         Index = i;
     136           6 :         continue;
     137             :       }
     138             : 
     139             :       // Otherwise the existing one comes first so just clear out the value in
     140             :       // this slot.
     141           2 :       V[i] = T();
     142             :     }
     143             :   }
     144             : 
     145             :   /// Remove the last element of the PriorityWorklist.
     146        2594 :   void pop_back() {
     147             :     assert(!empty() && "Cannot remove an element when empty!");
     148             :     assert(back() != T() && "Cannot have a null element at the back!");
     149        5188 :     M.erase(back());
     150             :     do {
     151             :       V.pop_back();
     152        2618 :     } while (!V.empty() && V.back() == T());
     153        2594 :   }
     154             : 
     155             :   LLVM_NODISCARD T pop_back_val() {
     156        2594 :     T Ret = back();
     157        2594 :     pop_back();
     158             :     return Ret;
     159             :   }
     160             : 
     161             :   /// Erase an item from the worklist.
     162             :   ///
     163             :   /// Note that this is constant time due to the nature of the worklist implementation.
     164           6 :   bool erase(const T& X) {
     165           6 :     auto I = M.find(X);
     166           6 :     if (I == M.end())
     167             :       return false;
     168             : 
     169             :     assert(V[I->second] == X && "Value not actually at index in map!");
     170           8 :     if (I->second == (ptrdiff_t)(V.size() - 1)) {
     171             :       do {
     172             :         V.pop_back();
     173           2 :       } while (!V.empty() && V.back() == T());
     174             :     } else {
     175           4 :       V[I->second] = T();
     176             :     }
     177             :     M.erase(I);
     178           4 :     return true;
     179             :   }
     180             : 
     181             :   /// Erase items from the set vector based on a predicate function.
     182             :   ///
     183             :   /// This is intended to be equivalent to the following code, if we could
     184             :   /// write it:
     185             :   ///
     186             :   /// \code
     187             :   ///   V.erase(remove_if(V, P), V.end());
     188             :   /// \endcode
     189             :   ///
     190             :   /// However, PriorityWorklist doesn't expose non-const iterators, making any
     191             :   /// algorithm like remove_if impossible to use.
     192             :   ///
     193             :   /// \returns true if any element is removed.
     194             :   template <typename UnaryPredicate>
     195           4 :   bool erase_if(UnaryPredicate P) {
     196             :     typename VectorT::iterator E =
     197           4 :         remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
     198           4 :     if (E == V.end())
     199             :       return false;
     200          17 :     for (auto I = V.begin(); I != E; ++I)
     201          10 :       if (*I != T())
     202          12 :         M[*I] = I - V.begin();
     203           1 :     V.erase(E, V.end());
     204             :     return true;
     205             :   }
     206             : 
     207             :   /// Reverse the items in the PriorityWorklist.
     208             :   ///
     209             :   /// This does an in-place reversal. Other kinds of reverse aren't easy to
     210             :   /// support in the face of the worklist semantics.
     211             : 
     212             :   /// Completely clear the PriorityWorklist
     213             :   void clear() {
     214           2 :     M.clear();
     215             :     V.clear();
     216             :   }
     217             : 
     218             : private:
     219             :   /// A wrapper predicate designed for use with std::remove_if.
     220             :   ///
     221             :   /// This predicate wraps a predicate suitable for use with std::remove_if to
     222             :   /// call M.erase(x) on each element which is slated for removal. This just
     223             :   /// allows the predicate to be move only which we can't do with lambdas
     224             :   /// today.
     225             :   template <typename UnaryPredicateT>
     226             :   class TestAndEraseFromMap {
     227             :     UnaryPredicateT P;
     228             :     MapT &M;
     229             : 
     230             :   public:
     231             :     TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
     232             :         : P(std::move(P)), M(M) {}
     233             : 
     234             :     bool operator()(const T &Arg) {
     235          32 :       if (Arg == T())
     236             :         // Skip null values in the PriorityWorklist.
     237             :         return false;
     238             : 
     239          24 :       if (P(Arg)) {
     240           6 :         M.erase(Arg);
     241             :         return true;
     242             :       }
     243             :       return false;
     244             :     }
     245             :   };
     246             : 
     247             :   /// The map from value to index in the vector.
     248             :   MapT M;
     249             : 
     250             :   /// The vector of elements in insertion order.
     251             :   VectorT V;
     252             : };
     253             : 
     254             : /// A version of \c PriorityWorklist that selects small size optimized data
     255             : /// structures for the vector and map.
     256             : template <typename T, unsigned N>
     257         820 : class SmallPriorityWorklist
     258             :     : public PriorityWorklist<T, SmallVector<T, N>,
     259             :                               SmallDenseMap<T, ptrdiff_t>> {
     260             : public:
     261             :   SmallPriorityWorklist() = default;
     262             : };
     263             : 
     264             : } // end namespace llvm
     265             : 
     266             : #endif // LLVM_ADT_PRIORITYWORKLIST_H

Generated by: LCOV version 1.13