Return to dfn.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / pgrm / gprof

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

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