arcs.c

早期freebsd实现

	    continue;
	done = FALSE;
        cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
	if ( cyclestack == 0 ) {
	    fprintf( stderr , "%s: No room for %d bytes of cycle stack\n" ,
		whoami , ( size + 1 ) * sizeof( arctype * ) );
	    return;
	}
#	ifdef DEBUG
	    if ( debug & BREAKCYCLE ) {
		printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
		    cycleno , ncycle , size );
	    }
#	endif DEBUG
	for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
	    stkp = &cyclestack[0];
	    nlp -> flags |= CYCLEHEAD;
	    ret = descend ( nlp , cyclestack , stkp );
	    nlp -> flags &= ~CYCLEHEAD;
	    if ( ret == FALSE )
		break;
	}
	free( cyclestack );
	if ( cyclecnt > 0 ) {
	    compresslist();
	    for ( clp = cyclehead ; clp ; ) {
		endlist = &clp -> list[ clp -> size ];
		for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
		    (*arcpp) -> arc_cyclecnt--;
		cyclecnt--;
		clp = clp -> next;
		free( clp );
	    }
	    cyclehead = 0;
	}
    }
#   ifdef DEBUG
	if ( debug & BREAKCYCLE ) {
	    printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
		"[doarcs]" , visited , viable , newcycle , oldcycle);
	}
#   endif DEBUG
    return( done );
}

descend( node , stkstart , stkp )
    nltype	*node;
    arctype	**stkstart;
    arctype	**stkp;
{
    arctype	*arcp;
    bool	ret;

    for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
#	ifdef DEBUG
	    visited++;
#	endif DEBUG
	if ( arcp -> arc_childp -> cycleno != node -> cycleno
	    || ( arcp -> arc_childp -> flags & VISITED )
	    || ( arcp -> arc_flags & DEADARC ) )
	    continue;
#	ifdef DEBUG
	    viable++;
#	endif DEBUG
	*stkp = arcp;
	if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
	    if ( addcycle( stkstart , stkp ) == FALSE )
		return( FALSE );
	    continue;
	}
	arcp -> arc_childp -> flags |= VISITED;
	ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
	arcp -> arc_childp -> flags &= ~VISITED;
	if ( ret == FALSE )
	    return( FALSE );
    }
}

addcycle( stkstart , stkend )
    arctype	**stkstart;
    arctype	**stkend;
{
    arctype	**arcpp;
    arctype	**stkloc;
    arctype	**stkp;
    arctype	**endlist;
    arctype	*minarc;
    arctype	*arcp;
    cltype	*clp;
    int		size;

    size = stkend - stkstart + 1;
    if ( size <= 1 )
	return( TRUE );
    for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
	if ( *arcpp > minarc )
	    continue;
	minarc = *arcpp;
	stkloc = arcpp;
    }
    for ( clp = cyclehead ; clp ; clp = clp -> next ) {
	if ( clp -> size != size )
	    continue;
	stkp = stkloc;
	endlist = &clp -> list[ size ];
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
	    if ( *stkp++ != *arcpp )
		break;
	    if ( stkp > stkend )
		stkp = stkstart;
	}
	if ( arcpp == endlist ) {
#	    ifdef DEBUG
		oldcycle++;
#	    endif DEBUG
	    return( TRUE );
	}
    }
    clp = (cltype *)
	calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
    if ( clp == 0 ) {
	fprintf( stderr , "%s: No room for %d bytes of subcycle storage\n" ,
	    whoami , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
	return( FALSE );
    }
    stkp = stkloc;
    endlist = &clp -> list[ size ];
    for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
	arcp = *arcpp = *stkp++;
	if ( stkp > stkend )
	    stkp = stkstart;
	arcp -> arc_cyclecnt++;
	if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
	    arcp -> arc_flags |= ONLIST;
	    arcp -> arc_next = archead;
	    archead = arcp;
	}
    }
    clp -> size = size;
    clp -> next = cyclehead;
    cyclehead = clp;
#   ifdef DEBUG
	newcycle++;
	if ( debug & SUBCYCLELIST ) {
	    printsubcycle( clp );
	}
#   endif DEBUG
    cyclecnt++;
    if ( cyclecnt >= CYCLEMAX )
	return( FALSE );
    return( TRUE );
}

compresslist()
{
    cltype	*clp;
    cltype	**prev;
    arctype	**arcpp;
    arctype	**endlist;
    arctype	*arcp;
    arctype	*maxarcp;
    arctype	*maxexitarcp;
    arctype	*maxwithparentarcp;
    arctype	*maxnoparentarcp;
    int		maxexitcnt;
    int		maxwithparentcnt;
    int		maxnoparentcnt;
    char	*type;

    maxexitcnt = 0;
    maxwithparentcnt = 0;
    maxnoparentcnt = 0;
    for ( endlist = &archead , arcp = archead ; arcp ; ) {
	if ( arcp -> arc_cyclecnt == 0 ) {
	    arcp -> arc_flags &= ~ONLIST;
	    *endlist = arcp -> arc_next;
	    arcp -> arc_next = 0;
	    arcp = *endlist;
	    continue;
	}
	if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
	    if ( arcp -> arc_cyclecnt > maxexitcnt ||
		( arcp -> arc_cyclecnt == maxexitcnt &&
		arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
		maxexitcnt = arcp -> arc_cyclecnt;
		maxexitarcp = arcp;
	    }
	} else if ( arcp -> arc_childp -> parentcnt > 1 ) {
	    if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
		( arcp -> arc_cyclecnt == maxwithparentcnt &&
		arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
		maxwithparentcnt = arcp -> arc_cyclecnt;
		maxwithparentarcp = arcp;
	    }
	} else {
	    if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
		( arcp -> arc_cyclecnt == maxnoparentcnt &&
		arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
		maxnoparentcnt = arcp -> arc_cyclecnt;
		maxnoparentarcp = arcp;
	    }
	}
	endlist = &arcp -> arc_next;
	arcp = arcp -> arc_next;
    }
    if ( maxexitcnt > 0 ) {
	/*
	 *	first choice is edge leading to node with out-of-cycle parent
	 */
	maxarcp = maxexitarcp;
#	ifdef DEBUG
	    type = "exit";
#	endif DEBUG
    } else if ( maxwithparentcnt > 0 ) {
	/*
	 *	second choice is edge leading to node with at least one
	 *	other in-cycle parent
	 */
	maxarcp = maxwithparentarcp;
#	ifdef DEBUG
	    type = "internal";
#	endif DEBUG
    } else {
	/*
	 *	last choice is edge leading to node with only this arc as
	 *	a parent (as it will now be orphaned)
	 */
	maxarcp = maxnoparentarcp;
#	ifdef DEBUG
	    type = "orphan";
#	endif DEBUG
    }
    maxarcp -> arc_flags |= DEADARC;
    maxarcp -> arc_childp -> parentcnt -= 1;
    maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
#   ifdef DEBUG
	if ( debug & BREAKCYCLE ) {
	    printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" ,
		"[compresslist]" , type , maxarcp -> arc_parentp -> name ,
		maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
		maxarcp -> arc_cyclecnt );
	}
#   endif DEBUG
    printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name ,
	maxarcp -> arc_childp -> name , maxarcp -> arc_count );
    prev = &cyclehead;
    for ( clp = cyclehead ; clp ; ) {
	endlist = &clp -> list[ clp -> size ];
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
	    if ( (*arcpp) -> arc_flags & DEADARC )
		break;
	if ( arcpp == endlist ) {
	    prev = &clp -> next;
	    clp = clp -> next;
	    continue;
	}
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
	    (*arcpp) -> arc_cyclecnt--;
	cyclecnt--;
	*prev = clp -> next;
	clp = clp -> next;
	free( clp );
    }
}

#ifdef DEBUG
printsubcycle( clp )
    cltype	*clp;
{
    arctype	**arcpp;
    arctype	**endlist;

    arcpp = clp -> list;
    printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
	(*arcpp) -> arc_parentp -> cycleno ) ;
    for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
	printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count ,
	    (*arcpp) -> arc_childp -> name ) ;
}
#endif DEBUG

cycletime()
{
    int			cycle;
    nltype		*cyclenlp;
    nltype		*childp;

    for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
	cyclenlp = &cyclenl[ cycle ];
	for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
	    if ( childp -> propfraction == 0.0 ) {
		    /*
		     * all members have the same propfraction except those
		     *	that were excluded with -E
		     */
		continue;
	    }
	    cyclenlp -> time += childp -> time;
	}
	cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
    }
}

    /*
     *	in one top to bottom pass over the topologically sorted namelist
     *	propagate:
     *		printflag as the union of parents' printflags
     *		propfraction as the sum of fractional parents' propfractions
     *	and while we're here, sum time for functions.
     */
doflags()
{
    int		index;
    nltype	*childp;
    nltype	*oldhead;

    oldhead = 0;
    for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
	childp = topsortnlp[ index ];
	    /*
	     *	if we haven't done this function or cycle,
	     *	inherit things from parent.
	     *	this way, we are linear in the number of arcs
	     *	since we do all members of a cycle (and the cycle itself)
	     *	as we hit the first member of the cycle.
	     */
	if ( childp -> cyclehead != oldhead ) {
	    oldhead = childp -> cyclehead;
	    inheritflags( childp );
	}
#	ifdef DEBUG
	    if ( debug & PROPDEBUG ) {
		printf( "[doflags] " );
		printname( childp );
		printf( " inherits printflag %d and propfraction %f\n" ,
			childp -> printflag , childp -> propfraction );
	    }
#	endif DEBUG
	if ( ! childp -> printflag ) {
		/*
		 *	printflag is off
		 *	it gets turned on by
		 *	being on -f list,
		 *	or there not being any -f list and not being on -e list.
		 */
	    if (   onlist( flist , childp -> name )
		|| ( !fflag && !onlist( elist , childp -> name ) ) ) {
		childp -> printflag = TRUE;
	    }
	} else {
		/*
		 *	this function has printing parents:
		 *	maybe someone wants to shut it up
		 *	by putting it on -e list.  (but favor -f over -e)
		 */
	    if (  ( !onlist( flist , childp -> name ) )
		&& onlist( elist , childp -> name ) ) {
		childp -> printflag = FALSE;
	    }
	}
	if ( childp -> propfraction == 0.0 ) {
		/*
		 *	no parents to pass time to.
		 *	collect time from children if
		 *	its on -F list,
		 *	or there isn't any -F list and its not on -E list.
		 */
	    if ( onlist( Flist , childp -> name )
		|| ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
		    childp -> propfraction = 1.0;
	    }
	} else {
		/*
		 *	it has parents to pass time to, 
		 *	but maybe someone wants to shut it up
		 *	by puttting it on -E list.  (but favor -F over -E)
		 */
	    if (  !onlist( Flist , childp -> name )
		&& onlist( Elist , childp -> name ) ) {
		childp -> propfraction = 0.0;
	    }
	}
	childp -> propself = childp -> time * childp -> propfraction;
	printtime += childp -> propself;
#	ifdef DEBUG
	    if ( debug & PROPDEBUG ) {
		printf( "[doflags] " );
		printname( childp );
		printf( " ends up with printflag %d and propfraction %f\n" ,
			childp -> printflag , childp -> propfraction );
		printf( "time %f propself %f printtime %f\n" ,
			childp -> time , childp -> propself , printtime );
	    }
#	endif DEBUG
    }
}

    /*
     *	check if any parent of this child
     *	(or outside parents of this cycle)
     *	have their print flags on and set the 
     *	print flag of the child (cycle) appropriately.
     *	similarly, deal with propagation fractions from parents.
     */
inheritflags( childp )
    nltype	*childp;
{
    nltype	*headp;
    arctype	*arcp;
    nltype	*parentp;
    nltype	*memp;

    headp = childp -> cyclehead;
    if ( childp == headp ) {
	    /*
	     *	just a regular child, check its parents
	     */
	childp -> printflag = FALSE;
	childp -> propfraction = 0.0;
	for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
	    parentp = arcp -> arc_parentp;
	    if ( childp == parentp ) {
		continue;
	    }
	    childp -> printflag |= parentp -> printflag;
		/*
		 *	if the child was never actually called
		 *	(e.g. this arc is static (and all others are, too))
		 *	no time propagates along this arc.
		 */
	    if ( arcp -> arc_flags & DEADARC ) {
		continue;
	    }
	    if ( childp -> npropcall ) {
		childp -> propfraction += parentp -> propfraction
					* ( ( (double) arcp -> arc_count )
					  / ( (double) childp -> npropcall ) );
	    }
	}
    } else {
	    /*
	     *	its a member of a cycle, look at all parents from 
	     *	outside the cycle
	     */
	headp -> printflag = FALSE;
	headp -> propfraction = 0.0;
	for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
	    for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
		if ( arcp -> arc_parentp -> cyclehead == headp ) {
		    continue;
		}
		parentp = arcp -> arc_parentp;
		headp -> printflag |= parentp -> printflag;
		    /*
		     *	if the cycle was never actually called
		     *	(e.g. this arc is static (and all others are, too))
		     *	no time propagates along this arc.
		     */
		if ( arcp -> arc_flags & DEADARC ) {
		    continue;
		}
		if ( headp -> npropcall ) {
		    headp -> propfraction += parentp -> propfraction
					* ( ( (double) arcp -> arc_count )
					  / ( (double) headp -> npropcall ) );
		}
	    }
	}
	for ( memp = headp ; memp ; memp = memp -> cnext ) {
	    memp -> printflag = headp -> printflag;
	    memp -> propfraction = headp -> propfraction;
	}
    }
}