include/llvm/Analysis/DataStructure/DSGraphTraits.h

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