Return to 2.inarc.c CVS log

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

Annotation of 41BSD/cmd/struct/2.inarc.c, revision 1.1.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.