Return to 2.inarc.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin / struct

Annotation of 43BSDTahoe/usr.bin/struct/2.inarc.c, revision 1.1

1.1     ! root        1: #ifndef lint
        !             2: static char sccsid[] = "@(#)2.inarc.c  4.1     (Berkeley)      2/11/83";
        !             3: #endif not lint
        !             4: 
        !             5: #include <stdio.h>
        !             6: #
        !             7: /* find forward in-arcs for each node, pretending that arcs which jump into a loop 
        !             8:        jump to the head of the largest such loop instead, based on the
        !             9:        depth first search tree */
        !            10: #include "def.h"
        !            11: #include "2.def.h"
        !            12: 
        !            13: getinarc(inarc,head)           /* construct array "inarc" containing in arcs for each node */
        !            14: struct list **inarc;
        !            15: VERT *head;
        !            16:        {
        !            17:        VERT v,adj,x;
        !            18:        int i, j;
        !            19: 
        !            20:        for (v=0; v < nodenum; ++v) inarc[v] = 0;
        !            21: 
        !            22:        /* fill in inarc nodes */
        !            23: 
        !            24:        for (i = 0; i < accessnum; ++i)
        !            25:                {
        !            26:                v = after[i];
        !            27:                for (j = 0; j < ARCNUM(v); ++j)
        !            28:                        {
        !            29:                        adj = ARC(v,j);
        !            30:                        if (!DEFINED(adj))
        !            31:                                continue;
        !            32:                        if (ntoaft[adj] > ntoaft[v])            /* not a back edge */
        !            33:                                /* if edge jumps into loop, pretend jumps to head of
        !            34:                                        largest loop jumped into */
        !            35:                                {
        !            36:                                x = maxentry(v,adj,head);
        !            37:                                if (!DEFINED(x)) x = adj;
        !            38:                                else x = FATH(x);
        !            39: 
        !            40:                                inarc[x] = consls(v,inarc[x]);  /* insert v in list inarc[x] */
        !            41:                                }
        !            42:                        }
        !            43:                }
        !            44:        }
        !            45: 
        !            46: 
        !            47: 
        !            48: maxentry(x,y,head)     /* return z if z is ITERVX of largest loop containing y but not x, UNDEFINED otherwise */
        !            49: VERT x,y, *head;
        !            50:        {
        !            51:        if (head[y] == UNDEFINED)  return(UNDEFINED);
        !            52:        if (loomem(x,head[y], head)) return (UNDEFINED);
        !            53:        y = head[y];
        !            54:        while (head[y] != UNDEFINED)
        !            55:                {
        !            56:                if (loomem(x,head[y],head))  return(y);
        !            57:                y = head[y];
        !            58:                }
        !            59:        return(y);
        !            60:        }
        !            61: 
        !            62: 
        !            63: 
        !            64: loomem(x,y,head)                       /* return TRUE if x is in loop headed by y, FALSE otherwise */
        !            65: VERT x,y, *head;
        !            66:        {
        !            67:        VERT w;
        !            68:        if (!DEFINED(y)) return(TRUE);
        !            69:        ASSERT(NTYPE(y) == ITERVX, loomem);
        !            70:        for (w = (NTYPE(x) == ITERVX) ? x : head[x]; DEFINED(w); w = head[w])
        !            71:                if (w == y)  return (TRUE);
        !            72:        return(FALSE);
        !            73:        }

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