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

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.