LCOV - code coverage report
Current view: top level - include/llvm/ADT - PriorityWorklist.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 63 63 100.0 %
Date: 2017-09-14 15:23:50 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        2931 : 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        2931 :   PriorityWorklist() = default;
      67             : 
      68             :   /// Determine if the PriorityWorklist is empty or not.
      69             :   bool empty() const {
      70        2350 :     return V.empty();
      71             :   }
      72             : 
      73             :   /// Returns the number of elements in the worklist.
      74             :   size_type size() const {
      75          44 :     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          40 :     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        4785 :     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        1755 :   bool insert(const T &X) {
      93             :     assert(X != T() && "Cannot insert a null (default constructed) value!");
      94        7020 :     auto InsertResult = M.insert({X, V.size()});
      95        1755 :     if (InsertResult.second) {
      96             :       // Fresh value, just append it to the vector.
      97        1733 :       V.push_back(X);
      98        1733 :       return true;
      99             :     }
     100             : 
     101          22 :     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          23 :       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         530 :   insert(SequenceT &&Input) {
     116        1062 :     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        1056 :     ptrdiff_t StartIndex = V.size();
     123        1589 :     V.insert(V.end(), std::begin(Input), std::end(Input));
     124             :     // Now walk backwards fixing up the index map and deleting any duplicates.
     125        1711 :     for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
     126        2620 :       auto InsertResult = M.insert({V[i], i});
     127         655 :       if (InsertResult.second)
     128        1300 :         continue;
     129             : 
     130             :       // If the existing index is before this insert's start, nuke that one and
     131             :       // move it up.
     132           8 :       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           4 :       V[i] = T();
     142             :     }
     143             :   }
     144             : 
     145             :   /// Remove the last element of the PriorityWorklist.
     146        2366 :   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        4732 :     M.erase(back());
     150             :     do {
     151        4750 :       V.pop_back();
     152        2674 :     } while (!V.empty() && V.back() == T());
     153        2366 :   }
     154             : 
     155             :   LLVM_NODISCARD T pop_back_val() {
     156        2366 :     T Ret = back();
     157        2366 :     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          18 :     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           3 :         V.pop_back();
     173           5 :       } while (!V.empty() && V.back() == T());
     174             :     } else {
     175           4 :       V[I->second] = T();
     176             :     }
     177           8 :     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           8 :     typename VectorT::iterator E =
     197           8 :         remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
     198          10 :     if (E == V.end())
     199             :       return false;
     200          15 :     for (auto I = V.begin(); I != E; ++I)
     201          10 :       if (*I != T())
     202          21 :         M[*I] = I - V.begin();
     203           8 :     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           4 :     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           4 :     TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
     232           4 :         : 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          36 :       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         974 : class SmallPriorityWorklist
     258             :     : public PriorityWorklist<T, SmallVector<T, N>,
     259             :                               SmallDenseMap<T, ptrdiff_t>> {
     260             : public:
     261        1948 :   SmallPriorityWorklist() = default;
     262             : };
     263             : 
     264             : } // end namespace llvm
     265             : 
     266             : #endif // LLVM_ADT_PRIORITYWORKLIST_H

Generated by: LCOV version 1.13