LLVM API Documentation
00001 //===- DSGraphTraits.h - Provide generic graph interface --------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file provides GraphTraits specializations for the DataStructure graph 00011 // nodes, allowing datastructure graphs to be processed by generic graph 00012 // algorithms. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #ifndef LLVM_ANALYSIS_DSGRAPHTRAITS_H 00017 #define LLVM_ANALYSIS_DSGRAPHTRAITS_H 00018 00019 #include "llvm/Analysis/DataStructure/DSGraph.h" 00020 #include "llvm/ADT/GraphTraits.h" 00021 #include "llvm/ADT/iterator" 00022 #include "llvm/ADT/STLExtras.h" 00023 00024 namespace llvm { 00025 00026 template<typename NodeTy> 00027 class DSNodeIterator : public forward_iterator<const DSNode, ptrdiff_t> { 00028 friend class DSNode; 00029 NodeTy * const Node; 00030 unsigned Offset; 00031 00032 typedef DSNodeIterator<NodeTy> _Self; 00033 00034 DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {} // begin iterator 00035 DSNodeIterator(NodeTy *N, bool) : Node(N) { // Create end iterator 00036 if (N != 0) { 00037 Offset = N->getNumLinks() << DS::PointerShift; 00038 if (Offset == 0 && Node->getForwardNode() && 00039 Node->isDeadNode()) // Model Forward link 00040 Offset += DS::PointerSize; 00041 } else { 00042 Offset = 0; 00043 } 00044 } 00045 public: 00046 DSNodeIterator(const DSNodeHandle &NH) 00047 : Node(NH.getNode()), Offset(NH.getOffset()) {} 00048 00049 bool operator==(const _Self& x) const { 00050 return Offset == x.Offset; 00051 } 00052 bool operator!=(const _Self& x) const { return !operator==(x); } 00053 00054 const _Self &operator=(const _Self &I) { 00055 assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); 00056 Offset = I.Offset; 00057 return *this; 00058 } 00059 00060 pointer operator*() const { 00061 if (Node->isDeadNode()) 00062 return Node->getForwardNode(); 00063 else 00064 return Node->getLink(Offset).getNode(); 00065 } 00066 pointer operator->() const { return operator*(); } 00067 00068 _Self& operator++() { // Preincrement 00069 Offset += (1 << DS::PointerShift); 00070 return *this; 00071 } 00072 _Self operator++(int) { // Postincrement 00073 _Self tmp = *this; ++*this; return tmp; 00074 } 00075 00076 unsigned getOffset() const { return Offset; } 00077 const DSNode *getNode() const { return Node; } 00078 }; 00079 00080 // Provide iterators for DSNode... 00081 inline DSNode::iterator DSNode::begin() { 00082 return DSNode::iterator(this); 00083 } 00084 inline DSNode::iterator DSNode::end() { 00085 return DSNode::iterator(this, false); 00086 } 00087 inline DSNode::const_iterator DSNode::begin() const { 00088 return DSNode::const_iterator(this); 00089 } 00090 inline DSNode::const_iterator DSNode::end() const { 00091 return DSNode::const_iterator(this, false); 00092 } 00093 00094 template <> struct GraphTraits<DSNode*> { 00095 typedef DSNode NodeType; 00096 typedef DSNode::iterator ChildIteratorType; 00097 00098 static NodeType *getEntryNode(NodeType *N) { return N; } 00099 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } 00100 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 00101 }; 00102 00103 template <> struct GraphTraits<const DSNode*> { 00104 typedef const DSNode NodeType; 00105 typedef DSNode::const_iterator ChildIteratorType; 00106 00107 static NodeType *getEntryNode(NodeType *N) { return N; } 00108 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } 00109 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 00110 }; 00111 00112 static DSNode &dereference ( DSNode *N) { return *N; } 00113 static const DSNode &dereferenceC(const DSNode *N) { return *N; } 00114 00115 template <> struct GraphTraits<DSGraph*> { 00116 typedef DSNode NodeType; 00117 typedef DSNode::iterator ChildIteratorType; 00118 00119 typedef std::pointer_to_unary_function<DSNode *, DSNode&> DerefFun; 00120 00121 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00122 typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator; 00123 static nodes_iterator nodes_begin(DSGraph *G) { 00124 return map_iterator(G->node_begin(), DerefFun(dereference)); 00125 } 00126 static nodes_iterator nodes_end(DSGraph *G) { 00127 return map_iterator(G->node_end(), DerefFun(dereference)); 00128 } 00129 00130 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } 00131 static ChildIteratorType child_end(NodeType *N) { return N->end(); } 00132 }; 00133 00134 template <> struct GraphTraits<const DSGraph*> { 00135 typedef const DSNode NodeType; 00136 typedef DSNode::const_iterator ChildIteratorType; 00137 00138 typedef std::pointer_to_unary_function<const DSNode *,const DSNode&> DerefFun; 00139 00140 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 00141 typedef mapped_iterator<DSGraph::node_iterator, DerefFun> nodes_iterator; 00142 static nodes_iterator nodes_begin(const DSGraph *G) { 00143 return map_iterator(G->node_begin(), DerefFun(dereferenceC)); 00144 } 00145 static nodes_iterator nodes_end(const DSGraph *G) { 00146 return map_iterator(G->node_end(), DerefFun(dereferenceC)); 00147 } 00148 00149 static ChildIteratorType child_begin(const NodeType *N) { return N->begin(); } 00150 static ChildIteratorType child_end(const NodeType *N) { return N->end(); } 00151 }; 00152 00153 } // End llvm namespace 00154 00155 #endif