Return to dfn.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / gprof

Annotation of 43BSDTahoe/ucb/gprof/dfn.c, revision 1.1

1.1     ! root        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 are permitted
        !             6:  * provided that the above copyright notice and this paragraph are
        !             7:  * duplicated in all such forms and that any documentation,
        !             8:  * advertising materials, and other materials related to such
        !             9:  * distribution and use acknowledge that the software was developed
        !            10:  * by the University of California, Berkeley.  The name of the
        !            11:  * University may not be used to endorse or promote products derived
        !            12:  * from this software without specific prior written permission.
        !            13:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
        !            14:  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
        !            15:  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            16:  */
        !            17: 
        !            18: #ifndef lint
        !            19: static char sccsid[] = "@(#)dfn.c      5.3 (Berkeley) 6/29/88";
        !            20: #endif /* not lint */
        !            21: 
        !            22: #include <stdio.h>
        !            23: #include "gprof.h"
        !            24: 
        !            25: #define        DFN_DEPTH       100
        !            26: struct dfnstruct {
        !            27:     nltype     *nlentryp;
        !            28:     int                cycletop;
        !            29: };
        !            30: typedef struct dfnstruct       dfntype;
        !            31: 
        !            32: dfntype        dfn_stack[ DFN_DEPTH ];
        !            33: int    dfn_depth = 0;
        !            34: 
        !            35: int    dfn_counter = DFN_NAN;
        !            36: 
        !            37:     /*
        !            38:      * given this parent, depth first number its children.
        !            39:      */
        !            40: dfn( parentp )
        !            41:     nltype     *parentp;
        !            42: {
        !            43:     arctype    *arcp;
        !            44: 
        !            45: #   ifdef DEBUG
        !            46:        if ( debug & DFNDEBUG ) {
        !            47:            printf( "[dfn] dfn(" );
        !            48:            printname( parentp );
        !            49:            printf( ")\n" );
        !            50:        }
        !            51: #   endif DEBUG
        !            52:        /*
        !            53:         *      if we're already numbered, no need to look any furthur.
        !            54:         */
        !            55:     if ( dfn_numbered( parentp ) ) {
        !            56:        return;
        !            57:     }
        !            58:        /*
        !            59:         *      if we're already busy, must be a cycle
        !            60:         */
        !            61:     if ( dfn_busy( parentp ) ) {
        !            62:        dfn_findcycle( parentp );
        !            63:        return;
        !            64:     }
        !            65:        /*
        !            66:         *      visit yourself before your children
        !            67:         */
        !            68:     dfn_pre_visit( parentp );
        !            69:        /*
        !            70:         *      visit children
        !            71:         */
        !            72:     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
        !            73:            dfn( arcp -> arc_childp );
        !            74:     }
        !            75:        /*
        !            76:         *      visit yourself after your children
        !            77:         */
        !            78:     dfn_post_visit( parentp );
        !            79: }
        !            80: 
        !            81:     /*
        !            82:      * push a parent onto the stack and mark it busy
        !            83:      */
        !            84: dfn_pre_visit( parentp )
        !            85:     nltype     *parentp;
        !            86: {
        !            87: 
        !            88:     dfn_depth += 1;
        !            89:     if ( dfn_depth >= DFN_DEPTH ) {
        !            90:        fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
        !            91:        exit( 1 );
        !            92:     }
        !            93:     dfn_stack[ dfn_depth ].nlentryp = parentp;
        !            94:     dfn_stack[ dfn_depth ].cycletop = dfn_depth;
        !            95:     parentp -> toporder = DFN_BUSY;
        !            96: #   ifdef DEBUG
        !            97:        if ( debug & DFNDEBUG ) {
        !            98:            printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
        !            99:            printname( parentp );
        !           100:            printf( "\n" );
        !           101:        }
        !           102: #   endif DEBUG
        !           103: }
        !           104: 
        !           105:     /*
        !           106:      * are we already numbered?
        !           107:      */
        !           108: bool
        !           109: dfn_numbered( childp )
        !           110:     nltype     *childp;
        !           111: {
        !           112:     
        !           113:     return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
        !           114: }
        !           115: 
        !           116:     /*
        !           117:      * are we already busy?
        !           118:      */
        !           119: bool
        !           120: dfn_busy( childp )
        !           121:     nltype     *childp;
        !           122: {
        !           123: 
        !           124:     if ( childp -> toporder == DFN_NAN ) {
        !           125:        return FALSE;
        !           126:     }
        !           127:     return TRUE;
        !           128: }
        !           129: 
        !           130:     /*
        !           131:      * MISSING: an explanation
        !           132:      */
        !           133: dfn_findcycle( childp )
        !           134:     nltype     *childp;
        !           135: {
        !           136:     int                cycletop;
        !           137:     nltype     *cycleheadp;
        !           138:     nltype     *tailp;
        !           139:     int                index;
        !           140: 
        !           141:     for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
        !           142:        cycleheadp = dfn_stack[ cycletop ].nlentryp;
        !           143:        if ( childp == cycleheadp ) {
        !           144:            break;
        !           145:        }
        !           146:        if ( childp -> cyclehead != childp &&
        !           147:            childp -> cyclehead == cycleheadp ) {
        !           148:            break;
        !           149:        }
        !           150:     }
        !           151:     if ( cycletop <= 0 ) {
        !           152:        fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
        !           153:        exit( 1 );
        !           154:     }
        !           155: #   ifdef DEBUG
        !           156:        if ( debug & DFNDEBUG ) {
        !           157:            printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
        !           158:                    dfn_depth , cycletop  );
        !           159:            printname( cycleheadp );
        !           160:            printf( "\n" );
        !           161:        }
        !           162: #   endif DEBUG
        !           163:     if ( cycletop == dfn_depth ) {
        !           164:            /*
        !           165:             *  this is previous function, e.g. this calls itself
        !           166:             *  sort of boring
        !           167:             */
        !           168:        dfn_self_cycle( childp );
        !           169:     } else {
        !           170:            /*
        !           171:             *  glom intervening functions that aren't already
        !           172:             *  glommed into this cycle.
        !           173:             *  things have been glommed when their cyclehead field
        !           174:             *  points to the head of the cycle they are glommed into.
        !           175:             */
        !           176:        for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
        !           177:            /* void: chase down to tail of things already glommed */
        !           178: #          ifdef DEBUG
        !           179:                if ( debug & DFNDEBUG ) {
        !           180:                    printf( "[dfn_findcycle] tail " );
        !           181:                    printname( tailp );
        !           182:                    printf( "\n" );
        !           183:                }
        !           184: #          endif DEBUG
        !           185:        }
        !           186:            /*
        !           187:             *  if what we think is the top of the cycle
        !           188:             *  has a cyclehead field, then it's not really the
        !           189:             *  head of the cycle, which is really what we want
        !           190:             */ 
        !           191:        if ( cycleheadp -> cyclehead != cycleheadp ) {
        !           192:            cycleheadp = cycleheadp -> cyclehead;
        !           193: #          ifdef DEBUG
        !           194:                if ( debug & DFNDEBUG ) {
        !           195:                    printf( "[dfn_findcycle] new cyclehead " );
        !           196:                    printname( cycleheadp );
        !           197:                    printf( "\n" );
        !           198:                }
        !           199: #          endif DEBUG
        !           200:        }
        !           201:        for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
        !           202:            childp = dfn_stack[ index ].nlentryp;
        !           203:            if ( childp -> cyclehead == childp ) {
        !           204:                    /*
        !           205:                     *  not yet glommed anywhere, glom it
        !           206:                     *  and fix any children it has glommed
        !           207:                     */
        !           208:                tailp -> cnext = childp;
        !           209:                childp -> cyclehead = cycleheadp;
        !           210: #              ifdef DEBUG
        !           211:                    if ( debug & DFNDEBUG ) {
        !           212:                        printf( "[dfn_findcycle] glomming " );
        !           213:                        printname( childp );
        !           214:                        printf( " onto " );
        !           215:                        printname( cycleheadp );
        !           216:                        printf( "\n" );
        !           217:                    }
        !           218: #              endif DEBUG
        !           219:                for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
        !           220:                    tailp -> cnext -> cyclehead = cycleheadp;
        !           221: #                  ifdef DEBUG
        !           222:                        if ( debug & DFNDEBUG ) {
        !           223:                            printf( "[dfn_findcycle] and its tail " );
        !           224:                            printname( tailp -> cnext );
        !           225:                            printf( " onto " );
        !           226:                            printname( cycleheadp );
        !           227:                            printf( "\n" );
        !           228:                        }
        !           229: #                  endif DEBUG
        !           230:                }
        !           231:            } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
        !           232:                fprintf( stderr ,
        !           233:                        "[dfn_busy] glommed, but not to cyclehead\n" );
        !           234:            }
        !           235:        }
        !           236:     }
        !           237: }
        !           238: 
        !           239:     /*
        !           240:      * deal with self-cycles
        !           241:      * for lint: ARGSUSED
        !           242:      */
        !           243: dfn_self_cycle( parentp )
        !           244:     nltype     *parentp;
        !           245: {
        !           246:        /*
        !           247:         *      since we are taking out self-cycles elsewhere
        !           248:         *      no need for the special case, here.
        !           249:         */
        !           250: #   ifdef DEBUG
        !           251:        if ( debug & DFNDEBUG ) {
        !           252:            printf( "[dfn_self_cycle] " );
        !           253:            printname( parentp );
        !           254:            printf( "\n" );
        !           255:        }
        !           256: #   endif DEBUG
        !           257: }
        !           258: 
        !           259:     /*
        !           260:      * visit a node after all its children
        !           261:      * [MISSING: an explanation]
        !           262:      * and pop it off the stack
        !           263:      */
        !           264: dfn_post_visit( parentp )
        !           265:     nltype     *parentp;
        !           266: {
        !           267:     nltype     *memberp;
        !           268: 
        !           269: #   ifdef DEBUG
        !           270:        if ( debug & DFNDEBUG ) {
        !           271:            printf( "[dfn_post_visit]\t%d: " , dfn_depth );
        !           272:            printname( parentp );
        !           273:            printf( "\n" );
        !           274:        }
        !           275: #   endif DEBUG
        !           276:        /*
        !           277:         *      number functions and things in their cycles
        !           278:         *      unless the function is itself part of a cycle
        !           279:         */
        !           280:     if ( parentp -> cyclehead == parentp ) {
        !           281:        dfn_counter += 1;
        !           282:        for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
        !           283:            memberp -> toporder = dfn_counter;
        !           284: #          ifdef DEBUG
        !           285:                if ( debug & DFNDEBUG ) {
        !           286:                    printf( "[dfn_post_visit]\t\tmember " );
        !           287:                    printname( memberp );
        !           288:                    printf( " -> toporder = %d\n" , dfn_counter );
        !           289:                }
        !           290: #          endif DEBUG
        !           291:        }
        !           292:     } else {
        !           293: #      ifdef DEBUG
        !           294:            if ( debug & DFNDEBUG ) {
        !           295:                printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
        !           296:            }
        !           297: #      endif DEBUG
        !           298:     }
        !           299:     dfn_depth -= 1;
        !           300: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.