Return to dfn.c CVS log

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

Annotation of 42BSD/ucb/gprof/dfn.c, revision 1.1

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

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