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/SmallVector.h"
21#include <algorithm>
22#include <cassert>
23#include <utility>
24#include <vector>
25
26namespace llvm {
27
28/// A FILO worklist that prioritizes on re-insertion without duplication.
29///
30/// This is very similar to a \c SetVector with the primary difference that
31/// while re-insertion does not create a duplicate, it does adjust the
32/// visitation order to respect the last insertion point. This can be useful
33/// when the visit order needs to be prioritized based on insertion point
34/// without actually having duplicate visits.
35///
36/// Note that this doesn't prevent re-insertion of elements which have been
37/// visited -- if you need to break cycles, a set will still be necessary.
38///
39/// The type \c T must be default constructable to a null value that will be
40/// ignored. It is an error to insert such a value, and popping elements will
41/// never produce such a value. It is expected to be used with common nullable
42/// types like pointers or optionals.
43///
44/// Internally this uses a vector to store the worklist and a map to identify
45/// existing elements in the worklist. Both of these may be customized, but the
46/// map must support the basic DenseMap API for mapping from a T to an integer
47/// index into the vector.
48///
49/// A partial specialization is provided to automatically select a SmallVector
50/// and a SmallDenseMap if custom data structures are not provided.
51template <typename T, typename VectorT = std::vector<T>,
52          typename MapT = DenseMap<T, ptrdiff_t>>
53class PriorityWorklist {
54public:
55  typedef T value_type;
56  typedef T key_type;
57  typedef T& reference;
58  typedef const T& const_reference;
59  typedef typename MapT::size_type size_type;
60
61  /// Construct an empty PriorityWorklist
62  PriorityWorklist() {}
63
64  /// Determine if the PriorityWorklist is empty or not.
65  bool empty() const {
66    return V.empty();
67  }
68
69  /// Returns the number of elements in the worklist.
70  size_type size() const {
71    return M.size();
72  }
73
74  /// Count the number of elements of a given key in the PriorityWorklist.
75  /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is.
76  size_type count(const key_type &key) const {
77    return M.count(key);
78  }
79
80  /// Return the last element of the PriorityWorklist.
81  const T &back() const {
82    assert(!empty() && "Cannot call back() on empty PriorityWorklist!");
83    return V.back();
84  }
85
86  /// Insert a new element into the PriorityWorklist.
87  /// \returns true if the element was inserted into the PriorityWorklist.
88  bool insert(const T &X) {
89    assert(X != T() && "Cannot insert a null (default constructed) value!");
90    auto InsertResult = M.insert({X, V.size()});
91    if (InsertResult.second) {
92      // Fresh value, just append it to the vector.
93      V.push_back(X);
94      return true;
95    }
96
97    auto &Index = InsertResult.first->second;
98    assert(V[Index] == X && "Value not actually at index in map!");
99    if (Index != (ptrdiff_t)(V.size() - 1)) {
100      // If the element isn't at the back, null it out and append a fresh one.
101      V[Index] = T();
102      Index = (ptrdiff_t)V.size();
103      V.push_back(X);
104    }
105    return false;
106  }
107
108  /// Remove the last element of the PriorityWorklist.
109  void pop_back() {
110    assert(!empty() && "Cannot remove an element when empty!");
111    assert(back() != T() && "Cannot have a null element at the back!");
112    M.erase(back());
113    do {
114      V.pop_back();
115    } while (!V.empty() && V.back() == T());
116  }
117
118  T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
119    T Ret = back();
120    pop_back();
121    return Ret;
122  }
123
124  /// Erase an item from the worklist.
125  ///
126  /// Note that this is constant time due to the nature of the worklist implementation.
127  bool erase(const T& X) {
128    auto I = M.find(X);
129    if (I == M.end())
130      return false;
131
132    assert(V[I->second] == X && "Value not actually at index in map!");
133    if (I->second == (ptrdiff_t)(V.size() - 1)) {
134      do {
135        V.pop_back();
136      } while (!V.empty() && V.back() == T());
137    } else {
138      V[I->second] = T();
139    }
140    M.erase(I);
141    return true;
142  }
143
144  /// Erase items from the set vector based on a predicate function.
145  ///
146  /// This is intended to be equivalent to the following code, if we could
147  /// write it:
148  ///
149  /// \code
150  ///   V.erase(std::remove_if(V.begin(), V.end(), P), V.end());
151  /// \endcode
152  ///
153  /// However, PriorityWorklist doesn't expose non-const iterators, making any
154  /// algorithm like remove_if impossible to use.
155  ///
156  /// \returns true if any element is removed.
157  template <typename UnaryPredicate>
158  bool erase_if(UnaryPredicate P) {
159    typename VectorT::iterator E = std::remove_if(
160        V.begin(), V.end(), TestAndEraseFromMap<UnaryPredicate>(P, M));
161    if (E == V.end())
162      return false;
163    for (auto I = V.begin(); I != E; ++I)
164      if (*I != T())
165        M[*I] = I - V.begin();
166    V.erase(E, V.end());
167    return true;
168  }
169
170  /// Completely clear the PriorityWorklist
171  void clear() {
172    M.clear();
173    V.clear();
174  }
175
176private:
177  /// A wrapper predicate designed for use with std::remove_if.
178  ///
179  /// This predicate wraps a predicate suitable for use with std::remove_if to
180  /// call M.erase(x) on each element which is slated for removal. This just
181  /// allows the predicate to be move only which we can't do with lambdas
182  /// today.
183  template <typename UnaryPredicateT>
184  class TestAndEraseFromMap {
185    UnaryPredicateT P;
186    MapT &M;
187
188  public:
189    TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
190        : P(std::move(P)), M(M) {}
191
192    bool operator()(const T &Arg) {
193      if (Arg == T())
194        // Skip null values in the PriorityWorklist.
195        return false;
196
197      if (P(Arg)) {
198        M.erase(Arg);
199        return true;
200      }
201      return false;
202    }
203  };
204
205  /// The map from value to index in the vector.
206  MapT M;
207
208  /// The vector of elements in insertion order.
209  VectorT V;
210};
211
212/// A version of \c PriorityWorklist that selects small size optimized data
213/// structures for the vector and map.
214template <typename T, unsigned N>
215class SmallPriorityWorklist
216    : public PriorityWorklist<T, SmallVector<T, N>,
217                              SmallDenseMap<T, ptrdiff_t>> {
218public:
219  SmallPriorityWorklist() {}
220};
221
222}
223
224#endif
225