1 //===- DSGraphTraits.h - Provide generic graph interface --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides GraphTraits specializations for the DataStructure graph
11 // nodes, allowing datastructure graphs to be processed by generic graph
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ANALYSIS_DSGRAPHTRAITS_H
17 #define LLVM_ANALYSIS_DSGRAPHTRAITS_H
19 #include "llvm/Analysis/DSGraph.h"
20 #include "Support/GraphTraits.h"
21 #include "Support/iterator"
22 #include "Support/STLExtras.h"
26 template<typename NodeTy>
27 class DSNodeIterator : public forward_iterator<const DSNode, ptrdiff_t> {
32 typedef DSNodeIterator<NodeTy> _Self;
34 DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {} // begin iterator
35 DSNodeIterator(NodeTy *N, bool) : Node(N) { // Create end iterator
37 Offset = N->getNumLinks() << DS::PointerShift;
38 if (Offset == 0 && Node->getForwardNode() &&
39 Node->isDeadNode()) // Model Forward link
40 Offset += DS::PointerSize;
46 DSNodeIterator(const DSNodeHandle &NH)
47 : Node(NH.getNode()), Offset(NH.getOffset()) {}
49 bool operator==(const _Self& x) const {
50 return Offset == x.Offset;
52 bool operator!=(const _Self& x) const { return !operator==(x); }
54 const _Self &operator=(const _Self &I) {
55 assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
60 pointer operator*() const {
61 if (Node->isDeadNode())
62 return Node->getForwardNode();
64 return Node->getLink(Offset).getNode();
66 pointer operator->() const { return operator*(); }
68 _Self& operator++() { // Preincrement
69 Offset += (1 << DS::PointerShift);
72 _Self operator++(int) { // Postincrement
73 _Self tmp = *this; ++*this; return tmp;
76 unsigned getOffset() const { return Offset; }
77 const DSNode *getNode() const { return Node; }
80 // Provide iterators for DSNode...
81 inline DSNode::iterator DSNode::begin() {
82 return DSNode::iterator(this);
84 inline DSNode::iterator DSNode::end() {
85 return DSNode::iterator(this, false);
87 inline DSNode::const_iterator DSNode::begin() const {
88 return DSNode::const_iterator(this);
90 inline DSNode::const_iterator DSNode::end() const {
91 return DSNode::const_iterator(this, false);
94 template <> struct GraphTraits<DSNode*> {
95 typedef DSNode NodeType;
96 typedef DSNode::iterator ChildIteratorType;
98 static NodeType *getEntryNode(NodeType *N) { return N; }
99 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
100 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
103 template <> struct GraphTraits<const DSNode*> {
104 typedef const DSNode NodeType;
105 typedef DSNode::const_iterator ChildIteratorType;
107 static NodeType *getEntryNode(NodeType *N) { return N; }
108 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
109 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
112 static DSNode &dereference ( DSNode *N) { return *N; }
113 static const DSNode &dereferenceC(const DSNode *N) { return *N; }
115 template <> struct GraphTraits<DSGraph*> {
116 typedef DSNode NodeType;
117 typedef DSNode::iterator ChildIteratorType;
119 typedef std::pointer_to_unary_function<DSNode *, DSNode&> DerefFun;
121 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
122 typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator;
123 static nodes_iterator nodes_begin(DSGraph *G) {
124 return map_iterator(G->node_begin(), DerefFun(dereference));
126 static nodes_iterator nodes_end(DSGraph *G) {
127 return map_iterator(G->node_end(), DerefFun(dereference));
130 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
131 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
134 template <> struct GraphTraits<const DSGraph*> {
135 typedef const DSNode NodeType;
136 typedef DSNode::const_iterator ChildIteratorType;
138 typedef std::pointer_to_unary_function<const DSNode *,const DSNode&> DerefFun;
140 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
141 typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator;
142 static nodes_iterator nodes_begin(const DSGraph *G) {
143 return map_iterator(G->node_begin(), DerefFun(dereferenceC));
145 static nodes_iterator nodes_end(const DSGraph *G) {
146 return map_iterator(G->node_end(), DerefFun(dereferenceC));
149 static ChildIteratorType child_begin(const NodeType *N) { return N->begin(); }
150 static ChildIteratorType child_end(const NodeType *N) { return N->end(); }
153 } // End llvm namespace