Return to dfn.c CVS log

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

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

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