#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/iterator.h"
#include <vector>
namespace llvm {
/// This is implemented using Tarjan's DFS algorithm using an internal stack to
/// build up a vector of nodes in a particular SCC. Note that it is a forward
/// iterator and thus you cannot backtrack or re-visit nodes.
-template <class GraphT, class GT = GraphTraits<GraphT> >
+template <class GraphT, class GT = GraphTraits<GraphT>>
class scc_iterator
- : public std::iterator<std::forward_iterator_tag,
- std::vector<typename GT::NodeType>, ptrdiff_t> {
+ : public iterator_facade_base<
+ scc_iterator<GraphT, GT>, std::forward_iterator_tag,
+ const std::vector<typename GT::NodeType *>, ptrdiff_t> {
typedef typename GT::NodeType NodeType;
typedef typename GT::ChildIteratorType ChildItTy;
typedef std::vector<NodeType *> SccTy;
- typedef std::iterator<std::forward_iterator_tag,
- std::vector<typename GT::NodeType>, ptrdiff_t> super;
- typedef typename super::reference reference;
- typedef typename super::pointer pointer;
+ typedef typename scc_iterator::reference reference;
- // Element of VisitStack during DFS.
+ /// Element of VisitStack during DFS.
struct StackElement {
NodeType *Node; ///< The current node pointer.
ChildItTy NextChild; ///< The next child, modified inplace during DFS.
}
};
- // The visit counters used to detect when a complete SCC is on the stack.
- // visitNum is the global counter.
- // nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
+ /// The visit counters used to detect when a complete SCC is on the stack.
+ /// visitNum is the global counter.
+ ///
+ /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
unsigned visitNum;
DenseMap<NodeType *, unsigned> nodeVisitNumbers;
- // Stack holding nodes of the SCC.
+ /// Stack holding nodes of the SCC.
std::vector<NodeType *> SCCNodeStack;
- // The current SCC, retrieved using operator*().
+ /// The current SCC, retrieved using operator*().
SccTy CurrentSCC;
-
- // DFS stack, Used to maintain the ordering. The top contains the current
- // node, the next child to visit, and the minimum uplink value of all child
+ /// DFS stack, Used to maintain the ordering. The top contains the current
+ /// node, the next child to visit, and the minimum uplink value of all child
std::vector<StackElement> VisitStack;
- // A single "visit" within the non-recursive DFS traversal.
+ /// A single "visit" within the non-recursive DFS traversal.
void DFSVisitOne(NodeType *N);
- // The stack-based DFS traversal; defined below.
+ /// The stack-based DFS traversal; defined below.
void DFSVisitChildren();
- // Compute the next SCC using the DFS traversal.
+ /// Compute the next SCC using the DFS traversal.
void GetNextSCC();
scc_iterator(NodeType *entryN) : visitNum(0) {
GetNextSCC();
}
- // End is when the DFS stack is empty.
+ /// End is when the DFS stack is empty.
scc_iterator() {}
public:
bool operator==(const scc_iterator &x) const {
return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
}
- bool operator!=(const scc_iterator &x) const { return !operator==(x); }
scc_iterator &operator++() {
GetNextSCC();
return *this;
}
- scc_iterator operator++(int) {
- scc_iterator tmp = *this;
- ++*this;
- return tmp;
- }
- const SccTy &operator*() const {
- assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
- return CurrentSCC;
- }
- SccTy &operator*() {
+ reference operator*() const {
assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
return CurrentSCC;
}