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