LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

DSGraphTraits.h

Go to the documentation of this file.
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