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