Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

///

/// \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 <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>

  std::enable_if_t<!std::is_convertible<SequenceT, T>::value>

  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());

  }

  [[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