include/llvm/Analysis/DataStructure/DSGraphTraits.h

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