PriorityWorklist.h

Go to the documentation of this file.

//===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
///
/// This file provides a priority worklist. See the class comments for details.
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_PRIORITYWORKLIST_H
#define LLVM_ADT_PRIORITYWORKLIST_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <type_traits>
#include <vector>

namespace llvm {

/// A FILO worklist that prioritizes on re-insertion without duplication.
///
/// This is very similar to a \c SetVector with the primary difference that
/// while re-insertion does not create a duplicate, it does adjust the
/// visitation order to respect the last insertion point. This can be useful
/// when the visit order needs to be prioritized based on insertion point
/// without actually having duplicate visits.
///
/// Note that this doesn't prevent re-insertion of elements which have been
/// visited -- if you need to break cycles, a set will still be necessary.
///
/// The type \c T must be default constructable to a null value that will be
/// ignored. It is an error to insert such a value, and popping elements will
/// never produce such a value. It is expected to be used with common nullable
/// types like pointers or optionals.
///
/// Internally this uses a vector to store the worklist and a map to identify
/// existing elements in the worklist. Both of these may be customized, but the
/// map must support the basic DenseMap API for mapping from a T to an integer
/// index into the vector.
///
/// A partial specialization is provided to automatically select a SmallVector
/// and a SmallDenseMap if custom data structures are not provided.
template <typename T, typename VectorT = std::vector<T>,
          typename MapT = DenseMap<T, ptrdiff_t>>
class PriorityWorklist {
public:
  using value_type = T;
  using key_type = T;
  using reference = T&;
  using const_reference = const T&;
  using size_type = typename MapT::size_type;

  /// Construct an empty PriorityWorklist
  PriorityWorklist() = default;

  /// Determine if the PriorityWorklist is empty or not.
  bool empty() const {
    return V.empty();
  }

  /// Returns the number of elements in the worklist.
  size_type size() const {
    return M.size();
  }

  /// Count the number of elements of a given key in the PriorityWorklist.
  /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is.
  size_type count(const key_type &key) const {
    return M.count(key);
  }

  /// Return the last element of the PriorityWorklist.
  const T &back() const {
    assert(!empty() && "Cannot call back() on empty PriorityWorklist!");
    return V.back();
  }

  /// Insert a new element into the PriorityWorklist.
  /// \returns true if the element was inserted into the PriorityWorklist.
  bool insert(const T &X) {
    assert(X != T() && "Cannot insert a null (default constructed) value!");
    auto InsertResult = M.insert({X, V.size()});
    if (InsertResult.second) {
      // Fresh value, just append it to the vector.
      V.push_back(X);
      return true;
    }

    auto &Index = InsertResult.first->second;
    assert(V[Index] == X && "Value not actually at index in map!");
    if (Index != (ptrdiff_t)(V.size() - 1)) {
      // If the element isn't at the back, null it out and append a fresh one.
      V[Index] = T();
      Index = (ptrdiff_t)V.size();
      V.push_back(X);
    }
    return false;
  }

  /// Insert a sequence of new elements into the PriorityWorklist.
  template <typename SequenceT>
  typename std::enable_if<!std::is_convertible<SequenceT, T>::value>::type
  insert(SequenceT &&Input) {
    if (std::begin(Input) == std::end(Input))
      // Nothing to do for an empty input sequence.
      return;

    // First pull the input sequence into the vector as a bulk append
    // operation.
    ptrdiff_t StartIndex = V.size();
    V.insert(V.end(), std::begin(Input), std::end(Input));
    // Now walk backwards fixing up the index map and deleting any duplicates.
    for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
      auto InsertResult = M.insert({V[i], i});
      if (InsertResult.second)
        continue;

      // If the existing index is before this insert's start, nuke that one and
      // move it up.
      ptrdiff_t &Index = InsertResult.first->second;
      if (Index < StartIndex) {
        V[Index] = T();
        Index = i;
        continue;
      }

      // Otherwise the existing one comes first so just clear out the value in
      // this slot.
      V[i] = T();
    }
  }

  /// Remove the last element of the PriorityWorklist.
  void pop_back() {
    assert(!empty() && "Cannot remove an element when empty!");
    assert(back() != T() && "Cannot have a null element at the back!");
    M.erase(back());
    do {
      V.pop_back();
    } while (!V.empty() && V.back() == T());
  }

  LLVM_NODISCARD T pop_back_val() {
    T Ret = back();
    pop_back();
    return Ret;
  }

  /// Erase an item from the worklist.
  ///
  /// Note that this is constant time due to the nature of the worklist implementation.
  bool erase(const T& X) {
    auto I = M.find(X);
    if (I == M.end())
      return false;

    assert(V[I->second] == X && "Value not actually at index in map!");
    if (I->second == (ptrdiff_t)(V.size() - 1)) {
      do {
        V.pop_back();
      } while (!V.empty() && V.back() == T());
    } else {
      V[I->second] = T();
    }
    M.erase(I);
    return true;
  }

  /// Erase items from the set vector based on a predicate function.
  ///
  /// This is intended to be equivalent to the following code, if we could
  /// write it:
  ///
  /// \code
  ///   V.erase(remove_if(V, P), V.end());
  /// \endcode
  ///
  /// However, PriorityWorklist doesn't expose non-const iterators, making any
  /// algorithm like remove_if impossible to use.
  ///
  /// \returns true if any element is removed.
  template <typename UnaryPredicate>
  bool erase_if(UnaryPredicate P) {
    typename VectorT::iterator E =
        remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
    if (E == V.end())
      return false;
    for (auto I = V.begin(); I != E; ++I)
      if (*I != T())
        M[*I] = I - V.begin();
    V.erase(E, V.end());
    return true;
  }

  /// Reverse the items in the PriorityWorklist.
  ///
  /// This does an in-place reversal. Other kinds of reverse aren't easy to
  /// support in the face of the worklist semantics.

  /// Completely clear the PriorityWorklist
  void clear() {
    M.clear();
    V.clear();
  }

private:
  /// A wrapper predicate designed for use with std::remove_if.
  ///
  /// This predicate wraps a predicate suitable for use with std::remove_if to
  /// call M.erase(x) on each element which is slated for removal. This just
  /// allows the predicate to be move only which we can't do with lambdas
  /// today.
  template <typename UnaryPredicateT>
  class TestAndEraseFromMap {
    UnaryPredicateT P;
    MapT &M;

  public:
    TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
        : P(std::move(P)), M(M) {}

    bool operator()(const T &Arg) {
      if (Arg == T())
        // Skip null values in the PriorityWorklist.
        return false;

      if (P(Arg)) {
        M.erase(Arg);
        return true;
      }
      return false;
    }
  };

  /// The map from value to index in the vector.
  MapT M;

  /// The vector of elements in insertion order.
  VectorT V;
};

/// A version of \c PriorityWorklist that selects small size optimized data
/// structures for the vector and map.
template <typename T, unsigned N>
class SmallPriorityWorklist
    : public PriorityWorklist<T, SmallVector<T, N>,
                              SmallDenseMap<T, ptrdiff_t>> {
public:
  SmallPriorityWorklist() = default;
};

} // end namespace llvm

#endif // LLVM_ADT_PRIORITYWORKLIST_H