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