1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
//===- DSGraphTraits.h - Provide generic graph interface --------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file provides GraphTraits specializations for the DataStructure graph
// nodes, allowing datastructure graphs to be processed by generic graph
// algorithms.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_DSGRAPHTRAITS_H
#define LLVM_ANALYSIS_DSGRAPHTRAITS_H
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/iterator"
#include "llvm/ADT/STLExtras.h"
namespace llvm {
template<typename NodeTy>
class DSNodeIterator : public forward_iterator<const DSNode, ptrdiff_t> {
friend class DSNode;
NodeTy * const Node;
unsigned Offset;
typedef DSNodeIterator<NodeTy> _Self;
DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {} // begin iterator
DSNodeIterator(NodeTy *N, bool) : Node(N) { // Create end iterator
if (N != 0) {
Offset = N->getNumLinks() << DS::PointerShift;
if (Offset == 0 && Node->getForwardNode() &&
Node->isDeadNode()) // Model Forward link
Offset += DS::PointerSize;
} else {
Offset = 0;
}
}
public:
DSNodeIterator(const DSNodeHandle &NH)
: Node(NH.getNode()), Offset(NH.getOffset()) {}
bool operator==(const _Self& x) const {
return Offset == x.Offset;
}
bool operator!=(const _Self& x) const { return !operator==(x); }
const _Self &operator=(const _Self &I) {
assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
Offset = I.Offset;
return *this;
}
pointer operator*() const {
if (Node->isDeadNode())
return Node->getForwardNode();
else
return Node->getLink(Offset).getNode();
}
pointer operator->() const { return operator*(); }
_Self& operator++() { // Preincrement
Offset += (1 << DS::PointerShift);
return *this;
}
_Self operator++(int) { // Postincrement
_Self tmp = *this; ++*this; return tmp;
}
unsigned getOffset() const { return Offset; }
const DSNode *getNode() const { return Node; }
};
// Provide iterators for DSNode...
inline DSNode::iterator DSNode::begin() {
return DSNode::iterator(this);
}
inline DSNode::iterator DSNode::end() {
return DSNode::iterator(this, false);
}
inline DSNode::const_iterator DSNode::begin() const {
return DSNode::const_iterator(this);
}
inline DSNode::const_iterator DSNode::end() const {
return DSNode::const_iterator(this, false);
}
template <> struct GraphTraits<DSNode*> {
typedef DSNode NodeType;
typedef DSNode::iterator ChildIteratorType;
static NodeType *getEntryNode(NodeType *N) { return N; }
static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
static ChildIteratorType child_end(NodeType *N) { return N->end(); }
};
template <> struct GraphTraits<const DSNode*> {
typedef const DSNode NodeType;
typedef DSNode::const_iterator ChildIteratorType;
static NodeType *getEntryNode(NodeType *N) { return N; }
static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
static ChildIteratorType child_end(NodeType *N) { return N->end(); }
};
static DSNode &dereference ( DSNode *N) { return *N; }
static const DSNode &dereferenceC(const DSNode *N) { return *N; }
template <> struct GraphTraits<DSGraph*> {
typedef DSNode NodeType;
typedef DSNode::iterator ChildIteratorType;
typedef std::pointer_to_unary_function<DSNode *, DSNode&> DerefFun;
// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator;
static nodes_iterator nodes_begin(DSGraph *G) {
return map_iterator(G->node_begin(), DerefFun(dereference));
}
static nodes_iterator nodes_end(DSGraph *G) {
return map_iterator(G->node_end(), DerefFun(dereference));
}
static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
static ChildIteratorType child_end(NodeType *N) { return N->end(); }
};
template <> struct GraphTraits<const DSGraph*> {
typedef const DSNode NodeType;
typedef DSNode::const_iterator ChildIteratorType;
typedef std::pointer_to_unary_function<const DSNode *,const DSNode&> DerefFun;
// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator;
static nodes_iterator nodes_begin(const DSGraph *G) {
return map_iterator(G->node_begin(), DerefFun(dereferenceC));
}
static nodes_iterator nodes_end(const DSGraph *G) {
return map_iterator(G->node_end(), DerefFun(dereferenceC));
}
static ChildIteratorType child_begin(const NodeType *N) { return N->begin(); }
static ChildIteratorType child_end(const NodeType *N) { return N->end(); }
};
} // End llvm namespace
#endif
|
