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
30namespace 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.
55template <typename T, typename VectorT = std::vector<T>,
56          typename MapT = DenseMap<T, ptrdiff_t>>
57class PriorityWorklist {
58public:
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
218private:
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.
256template <typename T, unsigned N>
257class SmallPriorityWorklist
258    : public PriorityWorklist<T, SmallVector<T, N>,
259                              SmallDenseMap<T, ptrdiff_t>> {
260public:
261  SmallPriorityWorklist() = default;
262};
263
264} // end namespace llvm
265
266#endif // LLVM_ADT_PRIORITYWORKLIST_H
267