home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / gprof / dfn.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-12  |  8.0 KB  |  317 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #ifndef lint
  35. static char sccsid[] = "@(#)dfn.c    5.4 (Berkeley) 6/1/90";
  36. #endif /* not lint */
  37.  
  38. #include <stdio.h>
  39. #include "gprof.h"
  40.  
  41. #define    DFN_DEPTH    100
  42. struct dfnstruct {
  43.     nltype    *nlentryp;
  44.     int        cycletop;
  45. };
  46. typedef struct dfnstruct    dfntype;
  47.  
  48. dfntype    dfn_stack[ DFN_DEPTH ];
  49. int    dfn_depth = 0;
  50.  
  51. int    dfn_counter = DFN_NAN;
  52.  
  53.     /*
  54.      *    given this parent, depth first number its children.
  55.      */
  56. dfn( parentp )
  57.     nltype    *parentp;
  58. {
  59.     arctype    *arcp;
  60.  
  61. #   ifdef DEBUG
  62.     if ( debug & DFNDEBUG ) {
  63.         printf( "[dfn] dfn(" );
  64.         printname( parentp );
  65.         printf( ")\n" );
  66.     }
  67. #   endif DEBUG
  68.     /*
  69.      *    if we're already numbered, no need to look any furthur.
  70.      */
  71.     if ( dfn_numbered( parentp ) ) {
  72.     return;
  73.     }
  74.     /*
  75.      *    if we're already busy, must be a cycle
  76.      */
  77.     if ( dfn_busy( parentp ) ) {
  78.     dfn_findcycle( parentp );
  79.     return;
  80.     }
  81.     /*
  82.      *    visit yourself before your children
  83.      */
  84.     dfn_pre_visit( parentp );
  85.     /*
  86.      *    visit children
  87.      */
  88.     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
  89.         dfn( arcp -> arc_childp );
  90.     }
  91.     /*
  92.      *    visit yourself after your children
  93.      */
  94.     dfn_post_visit( parentp );
  95. }
  96.  
  97.     /*
  98.      *    push a parent onto the stack and mark it busy
  99.      */
  100. dfn_pre_visit( parentp )
  101.     nltype    *parentp;
  102. {
  103.  
  104.     dfn_depth += 1;
  105.     if ( dfn_depth >= DFN_DEPTH ) {
  106.     fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
  107.     exit( 1 );
  108.     }
  109.     dfn_stack[ dfn_depth ].nlentryp = parentp;
  110.     dfn_stack[ dfn_depth ].cycletop = dfn_depth;
  111.     parentp -> toporder = DFN_BUSY;
  112. #   ifdef DEBUG
  113.     if ( debug & DFNDEBUG ) {
  114.         printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
  115.         printname( parentp );
  116.         printf( "\n" );
  117.     }
  118. #   endif DEBUG
  119. }
  120.  
  121.     /*
  122.      *    are we already numbered?
  123.      */
  124. bool
  125. dfn_numbered( childp )
  126.     nltype    *childp;
  127. {
  128.     
  129.     return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
  130. }
  131.  
  132.     /*
  133.      *    are we already busy?
  134.      */
  135. bool
  136. dfn_busy( childp )
  137.     nltype    *childp;
  138. {
  139.  
  140.     if ( childp -> toporder == DFN_NAN ) {
  141.     return FALSE;
  142.     }
  143.     return TRUE;
  144. }
  145.  
  146.     /*
  147.      *    MISSING: an explanation
  148.      */
  149. dfn_findcycle( childp )
  150.     nltype    *childp;
  151. {
  152.     int        cycletop;
  153.     nltype    *cycleheadp;
  154.     nltype    *tailp;
  155.     int        index;
  156.  
  157.     for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
  158.     cycleheadp = dfn_stack[ cycletop ].nlentryp;
  159.     if ( childp == cycleheadp ) {
  160.         break;
  161.     }
  162.     if ( childp -> cyclehead != childp &&
  163.         childp -> cyclehead == cycleheadp ) {
  164.         break;
  165.     }
  166.     }
  167.     if ( cycletop <= 0 ) {
  168.     fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
  169.     exit( 1 );
  170.     }
  171. #   ifdef DEBUG
  172.     if ( debug & DFNDEBUG ) {
  173.         printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
  174.             dfn_depth , cycletop  );
  175.         printname( cycleheadp );
  176.         printf( "\n" );
  177.     }
  178. #   endif DEBUG
  179.     if ( cycletop == dfn_depth ) {
  180.         /*
  181.          *    this is previous function, e.g. this calls itself
  182.          *    sort of boring
  183.          */
  184.     dfn_self_cycle( childp );
  185.     } else {
  186.         /*
  187.          *    glom intervening functions that aren't already
  188.          *    glommed into this cycle.
  189.          *    things have been glommed when their cyclehead field
  190.          *    points to the head of the cycle they are glommed into.
  191.          */
  192.     for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
  193.         /* void: chase down to tail of things already glommed */
  194. #        ifdef DEBUG
  195.         if ( debug & DFNDEBUG ) {
  196.             printf( "[dfn_findcycle] tail " );
  197.             printname( tailp );
  198.             printf( "\n" );
  199.         }
  200. #        endif DEBUG
  201.     }
  202.         /*
  203.          *    if what we think is the top of the cycle
  204.          *    has a cyclehead field, then it's not really the
  205.          *    head of the cycle, which is really what we want
  206.          */    
  207.     if ( cycleheadp -> cyclehead != cycleheadp ) {
  208.         cycleheadp = cycleheadp -> cyclehead;
  209. #        ifdef DEBUG
  210.         if ( debug & DFNDEBUG ) {
  211.             printf( "[dfn_findcycle] new cyclehead " );
  212.             printname( cycleheadp );
  213.             printf( "\n" );
  214.         }
  215. #        endif DEBUG
  216.     }
  217.     for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
  218.         childp = dfn_stack[ index ].nlentryp;
  219.         if ( childp -> cyclehead == childp ) {
  220.             /*
  221.              *    not yet glommed anywhere, glom it
  222.              *    and fix any children it has glommed
  223.              */
  224.         tailp -> cnext = childp;
  225.         childp -> cyclehead = cycleheadp;
  226. #        ifdef DEBUG
  227.             if ( debug & DFNDEBUG ) {
  228.             printf( "[dfn_findcycle] glomming " );
  229.             printname( childp );
  230.             printf( " onto " );
  231.             printname( cycleheadp );
  232.             printf( "\n" );
  233.             }
  234. #        endif DEBUG
  235.         for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
  236.             tailp -> cnext -> cyclehead = cycleheadp;
  237. #            ifdef DEBUG
  238.             if ( debug & DFNDEBUG ) {
  239.                 printf( "[dfn_findcycle] and its tail " );
  240.                 printname( tailp -> cnext );
  241.                 printf( " onto " );
  242.                 printname( cycleheadp );
  243.                 printf( "\n" );
  244.             }
  245. #            endif DEBUG
  246.         }
  247.         } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
  248.         fprintf( stderr ,
  249.             "[dfn_busy] glommed, but not to cyclehead\n" );
  250.         }
  251.     }
  252.     }
  253. }
  254.  
  255.     /*
  256.      *    deal with self-cycles
  257.      *    for lint: ARGSUSED
  258.      */
  259. dfn_self_cycle( parentp )
  260.     nltype    *parentp;
  261. {
  262.     /*
  263.      *    since we are taking out self-cycles elsewhere
  264.      *    no need for the special case, here.
  265.      */
  266. #   ifdef DEBUG
  267.     if ( debug & DFNDEBUG ) {
  268.         printf( "[dfn_self_cycle] " );
  269.         printname( parentp );
  270.         printf( "\n" );
  271.     }
  272. #   endif DEBUG
  273. }
  274.  
  275.     /*
  276.      *    visit a node after all its children
  277.      *    [MISSING: an explanation]
  278.      *    and pop it off the stack
  279.      */
  280. dfn_post_visit( parentp )
  281.     nltype    *parentp;
  282. {
  283.     nltype    *memberp;
  284.  
  285. #   ifdef DEBUG
  286.     if ( debug & DFNDEBUG ) {
  287.         printf( "[dfn_post_visit]\t%d: " , dfn_depth );
  288.         printname( parentp );
  289.         printf( "\n" );
  290.     }
  291. #   endif DEBUG
  292.     /*
  293.      *    number functions and things in their cycles
  294.      *    unless the function is itself part of a cycle
  295.      */
  296.     if ( parentp -> cyclehead == parentp ) {
  297.     dfn_counter += 1;
  298.     for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
  299.         memberp -> toporder = dfn_counter;
  300. #        ifdef DEBUG
  301.         if ( debug & DFNDEBUG ) {
  302.             printf( "[dfn_post_visit]\t\tmember " );
  303.             printname( memberp );
  304.             printf( " -> toporder = %d\n" , dfn_counter );
  305.         }
  306. #        endif DEBUG
  307.     }
  308.     } else {
  309. #    ifdef DEBUG
  310.         if ( debug & DFNDEBUG ) {
  311.         printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
  312.         }
  313. #    endif DEBUG
  314.     }
  315.     dfn_depth -= 1;
  316. }
  317.