LCOV - code coverage report
Current view: top level - include/llvm/ADT - GraphTraits.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 9 9 100.0 %
Date: 2017-09-14 15:23:50 Functions: 4 10 40.0 %
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             : template<class GraphType>
      29             : struct GraphTraits {
      30             :   // Elements to provide:
      31             : 
      32             :   // typedef NodeRef           - Type of Node token in the graph, which should
      33             :   //                             be cheap to copy.
      34             :   // typedef ChildIteratorType - Type used to iterate over children in graph,
      35             :   //                             dereference to a NodeRef.
      36             : 
      37             :   // static NodeRef getEntryNode(const GraphType &)
      38             :   //    Return the entry node of the graph
      39             : 
      40             :   // static ChildIteratorType child_begin(NodeRef)
      41             :   // static ChildIteratorType child_end  (NodeRef)
      42             :   //    Return iterators that point to the beginning and ending of the child
      43             :   //    node list for the specified node.
      44             : 
      45             :   // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
      46             :   // static nodes_iterator nodes_begin(GraphType *G)
      47             :   // static nodes_iterator nodes_end  (GraphType *G)
      48             :   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
      49             : 
      50             :   // static unsigned       size       (GraphType *G)
      51             :   //    Return total number of nodes in the graph
      52             : 
      53             :   // If anyone tries to use this class without having an appropriate
      54             :   // specialization, make an error.  If you get this error, it's because you
      55             :   // need to include the appropriate specialization of GraphTraits<> for your
      56             :   // graph, or you need to define it for a new graph type. Either that or
      57             :   // your argument to XXX_begin(...) is unknown or needs to have the proper .h
      58             :   // file #include'd.
      59             :   using NodeRef = typename GraphType::UnknownGraphTypeError;
      60             : };
      61             : 
      62             : // Inverse - This class is used as a little marker class to tell the graph
      63             : // iterator to iterate over the graph in a graph defined "Inverse" ordering.
      64             : // Not all graphs define an inverse ordering, and if they do, it depends on
      65             : // the graph exactly what that is.  Here's an example of usage with the
      66             : // df_iterator:
      67             : //
      68             : // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
      69             : // for (; I != E; ++I) { ... }
      70             : //
      71             : // Which is equivalent to:
      72             : // df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
      73             : // for (; I != E; ++I) { ... }
      74             : //
      75             : template <class GraphType>
      76             : struct Inverse {
      77             :   const GraphType &Graph;
      78             : 
      79        1430 :   inline Inverse(const GraphType &G) : Graph(G) {}
      80             : };
      81             : 
      82             : // Provide a partial specialization of GraphTraits so that the inverse of an
      83             : // inverse falls back to the original graph.
      84             : template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
      85             : 
      86             : // Provide iterator ranges for the graph traits nodes and children
      87             : template <class GraphType>
      88             : iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
      89         309 : nodes(const GraphType &G) {
      90     1545708 :   return make_range(GraphTraits<GraphType>::nodes_begin(G),
      91      516159 :                     GraphTraits<GraphType>::nodes_end(G));
      92             : }
      93             : template <class GraphType>
      94             : iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
      95             : inverse_nodes(const GraphType &G) {
      96             :   return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
      97             :                     GraphTraits<Inverse<GraphType>>::nodes_end(G));
      98             : }
      99             : 
     100             : template <class GraphType>
     101             : iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
     102     9911423 : children(const typename GraphTraits<GraphType>::NodeRef &G) {
     103    56222194 :   return make_range(GraphTraits<GraphType>::child_begin(G),
     104    29904401 :                     GraphTraits<GraphType>::child_end(G));
     105             : }
     106             : 
     107             : template <class GraphType>
     108             : iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
     109             : inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
     110     7114518 :   return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
     111     2371506 :                     GraphTraits<Inverse<GraphType>>::child_end(G));
     112             : }
     113             : 
     114             : } // end namespace llvm
     115             : 
     116             : #endif // LLVM_ADT_GRAPHTRAITS_H

Generated by: LCOV version 1.13