contrib/llvm/include/llvm/ADT/PriorityWorklist.h

   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 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   bool insert(const T &X) {
  93     assert(X != T() && "Cannot insert a null (default constructed) value!");
  94     auto InsertResult = M.insert({X, V.size()});
  95     if (InsertResult.second) {
  96       // Fresh value, just append it to the vector.
  97       V.push_back(X);
  98       return true;
  99     }
 100
 101     auto &Index = InsertResult.first->second;
 102     assert(V[Index] == X && "Value not actually at index in map!");
 103     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       V[Index] = T();
 106       Index = (ptrdiff_t)V.size();
 107       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   insert(SequenceT &&Input) {
 116     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     V.insert(V.end(), std::begin(Input), std::end(Input));
 124     // Now walk backwards fixing up the index map and deleting any duplicates.
 125     for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
 126       auto InsertResult = M.insert({V[i], i});
 127       if (InsertResult.second)
 128         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       if (Index < StartIndex) {
 134         V[Index] = T();
 135         Index = i;
 136         continue;
 137       }
 138
 139       // Otherwise the existing one comes first so just clear out the value in
 140       // this slot.
 141       V[i] = T();
 142     }
 143   }
 144
 145   /// Remove the last element of the PriorityWorklist.
 146   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     M.erase(back());
 150     do {
 151       V.pop_back();
 152     } while (!V.empty() && V.back() == T());
 153   }
 154
 155   LLVM_NODISCARD T pop_back_val() {
 156     T Ret = back();
 157     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   bool erase(const T& X) {
 165     auto I = M.find(X);
 166     if (I == M.end())
 167       return false;
 168
 169     assert(V[I->second] == X && "Value not actually at index in map!");
 170     if (I->second == (ptrdiff_t)(V.size() - 1)) {
 171       do {
 172         V.pop_back();
 173       } while (!V.empty() && V.back() == T());
 174     } else {
 175       V[I->second] = T();
 176     }
 177     M.erase(I);
 178     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   bool erase_if(UnaryPredicate P) {
 196     typename VectorT::iterator E =
 197         remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
 198     if (E == V.end())
 199       return false;
 200     for (auto I = V.begin(); I != E; ++I)
 201       if (*I != T())
 202         M[*I] = I - V.begin();
 203     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     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       if (Arg == T())
 236         // Skip null values in the PriorityWorklist.
 237         return false;
 238
 239       if (P(Arg)) {
 240         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 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