/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <stdio.h>
#include "gprof.h"

#define DFN_DEPTH       100

struct dfnstruct {
        nltype  *nlentryp;
        int     cycletop;
};

typedef struct dfnstruct        dfntype;

dfntype *dfn_stack = NULL;
int     dfn_depth = 0;
int     dfn_sz = 0;

int     dfn_counter = DFN_NAN;

/*
 *      given this parent, depth first number its children.
 */
void
dfn(nltype *parentp)
{
        arctype *arcp;

#ifdef DEBUG
        if (debug & DFNDEBUG) {
                (void) printf("[dfn] dfn(");
                printname(parentp);
                (void) printf(")\n");
        }
#endif /* DEBUG */

        if (!dfn_stack) {
                dfn_sz = DFN_DEPTH;
                dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype));
                if (!dfn_stack) {
                        (void) fprintf(stderr,
                            "fatal: can't malloc %d objects\n", dfn_sz);
                        exit(1);
                }
        }

        /*
         *      if we're already numbered, no need to look any furthur.
         */
        if (dfn_numbered(parentp))
                return;

        /*
         *      if we're already busy, must be a cycle
         */
        if (dfn_busy(parentp)) {
                dfn_findcycle(parentp);
                return;
        }

        /*
         *      visit yourself before your children
         */
        dfn_pre_visit(parentp);

        /*
         *      visit children
         */
        for (arcp = parentp->children; arcp; arcp = arcp->arc_childlist)
                dfn(arcp->arc_childp);

        /*
         *      visit yourself after your children
         */
        dfn_post_visit(parentp);
}

/*
 *      push a parent onto the stack and mark it busy
 */
void
dfn_pre_visit(nltype *parentp)
{

        if (!dfn_stack) {
                dfn_sz = DFN_DEPTH;
                dfn_stack = (dfntype *) malloc(dfn_sz * sizeof (dfntype));
                if (!dfn_stack) {
                        (void) printf("fatal: can't malloc %d objects\n",
                            dfn_sz);
                        exit(1);
                }
        }

        dfn_depth += 1;

        if (dfn_depth >= dfn_sz) {
                dfn_sz += DFN_DEPTH;
                dfn_stack = (dfntype *) realloc(dfn_stack,
                    dfn_sz * sizeof (dfntype));

                if (!dfn_stack) {
                        (void) fprintf(stderr,
                            "fatal: can't realloc %d objects\n", dfn_sz);
                        exit(1);
                }
        }

        dfn_stack[dfn_depth].nlentryp = parentp;
        dfn_stack[dfn_depth].cycletop = dfn_depth;
        parentp->toporder = DFN_BUSY;

#ifdef DEBUG
        if (debug & DFNDEBUG) {
                (void) printf("[dfn_pre_visit]\t\t%d:", dfn_depth);
                printname(parentp);
                (void) printf("\n");
        }
#endif /* DEBUG */
}

/*
 *      are we already numbered?
 */
bool
dfn_numbered(nltype *childp)
{
        return (childp->toporder != DFN_NAN && childp->toporder != DFN_BUSY);
}

/*
 *      are we already busy?
 */
bool
dfn_busy(nltype *childp)
{
        if (childp->toporder == DFN_NAN)
                return (FALSE);

        return (TRUE);
}

void
dfn_findcycle(nltype *childp)
{
        int     cycletop;
        nltype  *cycleheadp = NULL;
        nltype  *tailp;
        int     index;

        for (cycletop = dfn_depth; cycletop > 0; cycletop -= 1) {
                cycleheadp = dfn_stack[cycletop].nlentryp;
                if (childp == cycleheadp)
                        break;

                if (childp->cyclehead != childp &&
                    childp->cyclehead == cycleheadp)
                        break;
        }

        if (cycletop <= 0) {
                /*
                 * don't report non existent functions
                 */
                if (childp->value) {
                        (void) fprintf(stderr,
                            "[dfn_findcycle] couldn't find head "
                            "of cycle for %s\n", childp->name);
                        return;
                }
        }

#ifdef DEBUG
        if (debug & DFNDEBUG) {
                (void) printf("[dfn_findcycle] dfn_depth %d cycletop %d ",
                    dfn_depth, cycletop);
                printname(cycleheadp);
                (void) printf("\n");
        }
#endif /* DEBUG */

        if (cycletop == dfn_depth) {
                /*
                 *      this is previous function, e.g. this calls itself
                 *      sort of boring
                 */
                dfn_self_cycle(childp);
        } else {
                /*
                 *      glom intervening functions that aren't already
                 *      glommed into this cycle.
                 *      things have been glommed when their cyclehead field
                 *      points to the head of the cycle they are glommed into.
                 */
                for (tailp = cycleheadp; tailp->cnext; tailp = tailp->cnext) {
                        /* void: chase down to tail of things already glommed */
#ifdef DEBUG
                        if (debug & DFNDEBUG) {
                                (void) printf("[dfn_findcycle] tail ");
                                printname(tailp);
                                (void) printf("\n");
                        }
#endif /* DEBUG */
                }

                /*
                 *      if what we think is the top of the cycle
                 *      has a cyclehead field, then it's not really the
                 *      head of the cycle, which is really what we want
                 */
                if (cycleheadp->cyclehead != cycleheadp) {
                        cycleheadp = cycleheadp->cyclehead;
#ifdef DEBUG
                        if (debug & DFNDEBUG) {
                                (void) printf("[dfn_findcycle] new cyclehead ");
                                printname(cycleheadp);
                                (void) printf("\n");
                        }
#endif /* DEBUG */
                }

                for (index = cycletop + 1; index <= dfn_depth; index += 1) {

                        childp = dfn_stack[index].nlentryp;
                        if (childp->cyclehead == childp) {
                                /*
                                 *      not yet glommed anywhere, glom it
                                 *      and fix any children it has glommed
                                 */
                                tailp->cnext = childp;
                                childp->cyclehead = cycleheadp;
#ifdef DEBUG
                                if (debug & DFNDEBUG) {
                                        (void) printf(
                                            "[dfn_findcycle] glomming ");
                                        printname(childp);
                                        (void) printf(" onto ");
                                        printname(cycleheadp);
                                        (void) printf("\n");
                                }
#endif /* DEBUG */
                                for (tailp = childp; tailp->cnext;
                                    tailp = tailp->cnext) {
                                        tailp->cnext->cyclehead = cycleheadp;
#ifdef DEBUG
                                        if (debug & DFNDEBUG) {
                                                (void) printf("[dfn_findcycle]"
                                                    " and its tail ");
                                                printname(tailp->cnext);
                                                (void) printf(" onto ");
                                                printname(cycleheadp);
                                                (void) printf("\n");
                                        }
#endif /* DEBUG */
                                }
                        } else if (childp->cyclehead != cycleheadp) {
                                (void) fprintf(stderr, "[dfn_busy] glommed,"
                                    " but not to cyclehead\n");
                        }
                }
        }
}

/*
 *      deal with self-cycles
 *      for lint: ARGSUSED
 */
/* ARGSUSED */
void
dfn_self_cycle(nltype *parentp)
{
        /*
         *      since we are taking out self-cycles elsewhere
         *      no need for the special case, here.
         */
#ifdef DEBUG
        if (debug & DFNDEBUG) {
                (void) printf("[dfn_self_cycle] ");
                printname(parentp);
                (void) printf("\n");
        }
#endif /* DEBUG */
}

/*
 *      visit a node after all its children
 *      [MISSING: an explanation]
 *      and pop it off the stack
 */
void
dfn_post_visit(nltype *parentp)
{
        nltype  *memberp;

#ifdef DEBUG
        if (debug & DFNDEBUG) {
                (void) printf("[dfn_post_visit]\t%d: ", dfn_depth);
                printname(parentp);
                (void) printf("\n");
        }
#endif /* DEBUG */
        /*
         *      number functions and things in their cycles
         *      unless the function is itself part of a cycle
         */
        if (parentp->cyclehead == parentp) {
                dfn_counter += 1;

                for (memberp = parentp; memberp; memberp = memberp->cnext) {

                        memberp->toporder = dfn_counter;
#ifdef DEBUG
                        if (debug & DFNDEBUG) {
                                (void) printf("[dfn_post_visit]\t\tmember ");
                                printname(memberp);
                                (void) printf(" -> toporder = %d\n",
                                    dfn_counter);
                        }
#endif /* DEBUG */
                }
#ifdef DEBUG
        } else {
                if (debug & DFNDEBUG)
                        (void) printf(
                            "[dfn_post_visit]\t\tis part of a cycle\n");
#endif /* DEBUG */
        }
        dfn_depth -= 1;
}