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