LCOV - code coverage report
Current view: top level - include/llvm/ADT - GraphTraits.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 8 23 34.8 %
Date: 2018-09-23 13:06:45 Functions: 3 29 10.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/GraphTraits.h - Graph traits template -----------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the little GraphTraits<X> template class that should be
      11             : // specialized by classes that want to be iteratable by generic graph iterators.
      12             : //
      13             : // This file also defines the marker class Inverse that is used to iterate over
      14             : // graphs in a graph defined, inverse ordering...
      15             : //
      16             : //===----------------------------------------------------------------------===//
      17             : 
      18             : #ifndef LLVM_ADT_GRAPHTRAITS_H
      19             : #define LLVM_ADT_GRAPHTRAITS_H
      20             : 
      21             : #include "llvm/ADT/iterator_range.h"
      22             : 
      23             : namespace llvm {
      24             : 
      25             : // GraphTraits - This class should be specialized by different graph types...
      26             : // which is why the default version is empty.
      27             : //
      28             : // This template evolved from supporting `BasicBlock` to also later supporting
      29             : // more complex types (e.g. CFG and DomTree).
      30             : //
      31             : // GraphTraits can be used to create a view over a graph interpreting it
      32             : // differently without requiring a copy of the original graph. This could
      33             : // be achieved by carrying more data in NodeRef. See LoopBodyTraits for one
      34             : // example.
      35             : template<class GraphType>
      36             : struct GraphTraits {
      37             :   // Elements to provide:
      38             : 
      39             :   // typedef NodeRef           - Type of Node token in the graph, which should
      40             :   //                             be cheap to copy.
      41             :   // typedef ChildIteratorType - Type used to iterate over children in graph,
      42             :   //                             dereference to a NodeRef.
      43             : 
      44             :   // static NodeRef getEntryNode(const GraphType &)
      45             :   //    Return the entry node of the graph
      46             : 
      47             :   // static ChildIteratorType child_begin(NodeRef)
      48             :   // static ChildIteratorType child_end  (NodeRef)
      49             :   //    Return iterators that point to the beginning and ending of the child
      50             :   //    node list for the specified node.
      51             : 
      52             :   // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
      53             :   // static nodes_iterator nodes_begin(GraphType *G)
      54             :   // static nodes_iterator nodes_end  (GraphType *G)
      55             :   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
      56             : 
      57             :   // typedef EdgeRef           - Type of Edge token in the graph, which should
      58             :   //                             be cheap to copy.
      59             :   // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
      60             :   //                             graph, dereference to a EdgeRef.
      61             : 
      62             :   // static ChildEdgeIteratorType child_edge_begin(NodeRef)
      63             :   // static ChildEdgeIteratorType child_edge_end(NodeRef)
      64             :   //     Return iterators that point to the beginning and ending of the
      65             :   //     edge list for the given callgraph node.
      66             :   //
      67             :   // static NodeRef edge_dest(EdgeRef)
      68             :   //     Return the destination node of an edge.
      69             : 
      70             :   // static unsigned       size       (GraphType *G)
      71             :   //    Return total number of nodes in the graph
      72             : 
      73             :   // If anyone tries to use this class without having an appropriate
      74             :   // specialization, make an error.  If you get this error, it's because you
      75             :   // need to include the appropriate specialization of GraphTraits<> for your
      76             :   // graph, or you need to define it for a new graph type. Either that or
      77             :   // your argument to XXX_begin(...) is unknown or needs to have the proper .h
      78             :   // file #include'd.
      79             :   using NodeRef = typename GraphType::UnknownGraphTypeError;
      80             : };
      81             : 
      82             : // Inverse - This class is used as a little marker class to tell the graph
      83             : // iterator to iterate over the graph in a graph defined "Inverse" ordering.
      84             : // Not all graphs define an inverse ordering, and if they do, it depends on
      85             : // the graph exactly what that is.  Here's an example of usage with the
      86             : // df_iterator:
      87             : //
      88             : // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
      89             : // for (; I != E; ++I) { ... }
      90             : //
      91             : // Which is equivalent to:
      92             : // df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
      93             : // for (; I != E; ++I) { ... }
      94             : //
      95             : template <class GraphType>
      96             : struct Inverse {
      97             :   const GraphType &Graph;
      98             : 
      99           0 :   inline Inverse(const GraphType &G) : Graph(G) {}
     100             : };
     101             : 
     102             : // Provide a partial specialization of GraphTraits so that the inverse of an
     103             : // inverse falls back to the original graph.
     104             : template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
     105             : 
     106             : // Provide iterator ranges for the graph traits nodes and children
     107             : template <class GraphType>
     108             : iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
     109           2 : nodes(const GraphType &G) {
     110           0 :   return make_range(GraphTraits<GraphType>::nodes_begin(G),
     111           2 :                     GraphTraits<GraphType>::nodes_end(G));
     112             : }
     113             : template <class GraphType>
     114             : iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
     115             : inverse_nodes(const GraphType &G) {
     116             :   return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
     117             :                     GraphTraits<Inverse<GraphType>>::nodes_end(G));
     118             : }
     119             : 
     120             : template <class GraphType>
     121             : iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
     122    21893422 : children(const typename GraphTraits<GraphType>::NodeRef &G) {
     123    21893422 :   return make_range(GraphTraits<GraphType>::child_begin(G),
     124    21893422 :                     GraphTraits<GraphType>::child_end(G));
     125             : }
     126    21293247 : 
     127    21293247 : template <class GraphType>
     128    21293247 : iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
     129           0 : inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
     130           0 :   return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
     131           0 :                     GraphTraits<Inverse<GraphType>>::child_end(G));
     132           0 : }
     133             : 
     134           0 : template <class GraphType>
     135           0 : iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
     136           0 : children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
     137           0 :   return make_range(GraphTraits<GraphType>::child_edge_begin(G),
     138           0 :                     GraphTraits<GraphType>::child_edge_end(G));
     139           0 : }
     140             : 
     141           0 : } // end namespace llvm
     142           0 : 
     143           0 : #endif // LLVM_ADT_GRAPHTRAITS_H

Generated by: LCOV version 1.13