Return to 2.inarc.c CVS log

Up to [CSRG BSD Unix] / 40BSD / cmd / struct

Annotation of 40BSD/cmd/struct/2.inarc.c, revision 1.1

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

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