Return to 2.head.c CVS log

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

Annotation of 40BSD/cmd/struct/2.head.c, revision 1.1.1.1

1.1       root        1: #include <stdio.h>
                      2: #
                      3: /*
                      4: set head[v] to ITERVX heading smallest loop containing v, for each v
                      5: */
                      6: #include "def.h"
                      7: #include "2.def.h"
                      8: 
                      9: /* define ANC(v,w) true if v == w or v is ancestor of w */
                     10: #define ANC(v,w)       (ntobef[v] <= ntobef[w] && ntoaft[v] <= ntoaft[w])      /* reflexive ancestor */
                     11: 
                     12: 
                     13: gethead(head)
                     14: VERT *head;
                     15:        {
                     16:        VERT v, w, adj; int i, j;
                     17:        /* search nodes in reverse of after numbering so that all paths from
                     18:                a node to an ancestor are searched before the node */
                     19:        /* at any point, the current value of head allows chains of nodes
                     20:                to be reached from any node v by taking head[v], head[head[v]], etc.
                     21:                until an UNDEFINED value is reached.  Upon searching each arc, 
                     22:                the appropriate chains must be merged to avoid losing information.
                     23:                For example, from one path out of a node v it may be known that
                     24:                 v is in a loop headed by z, while from another
                     25:                it may be known that v is in a loop headed by w.
                     26:                Thus, head[v] must be set to whichever of z,w is the closer ancestor,
                     27:                and the fact that this node is in a loop headed by the other must be
                     28:                recorded in head.       */
                     29:        for (v = 0; v < nodenum; ++v)
                     30:                head[v] = UNDEFINED;
                     31:        for (i = accessnum -1; i >= 0; --i)
                     32:                {
                     33:                v = after[i];
                     34:                for (j = 0; j < ARCNUM(v); ++j)
                     35:                        {
                     36:                        adj = ARC(v,j);
                     37:                        if (!DEFINED(adj)) continue;
                     38:                        if (ntoaft[adj] < i)            /* back edge */
                     39:                                merge(v,adj,head);
                     40:                        else if (ANC(v,adj))            /* not back edge or cross edge */
                     41:                                {
                     42:                                /* need to do only tree edges - must not do edge (v,adj)
                     43:                                        when head[adj] is not ANC of v */
                     44:                                if (DEFINED(head[adj]) && ANC(head[adj],v))
                     45:                                        merge(v,head[adj],head);
                     46:                                }
                     47:                        else                            /* cross edge */
                     48:                                {
                     49:                                w = lowanc(adj,v,head);
                     50:                                if (DEFINED(w))
                     51:                                        merge(w,v,head);
                     52:                                }
                     53:                        }
                     54:                if (NTYPE(v) == LOOPVX || NTYPE(v) == DOVX)
                     55:                        head[ARC(v,0)] = head[v];       /* head of ITERVX must be different ITERVX */
                     56:                }
                     57:        }
                     58: 
                     59: 
                     60: lowanc(y,z,head)               /* find the first node in chain of y which is anc of z, if it exists */
                     61: VERT y,z, *head;
                     62:        {
                     63:        while (y != -1 && !ANC(y,z))
                     64:                y = head[y];
                     65:        return(y);
                     66:        }
                     67: 
                     68: 
                     69: merge(w,y,head)                /* merge chains of w and y according to ANC relation */
                     70: VERT w,y, *head;
                     71:        {
                     72:        VERT t, min;
                     73:        if (w == y) return;
                     74: 
                     75:        if (ANC(w,y))           /* set t to min of w,y */
                     76:                {
                     77:                t = y;
                     78:                 y = head[y];
                     79:                }
                     80:        else
                     81:                {
                     82:                t = w;
                     83:                 w = head[w];
                     84:                }
                     85: 
                     86:        while (w != -1 && y != -1)              /* construct chain at t by adding min of remaining elts */
                     87:                {
                     88:                if (ANC(w,y))
                     89:                        {
                     90:                        min = y;
                     91:                        y = head[y];
                     92:                        }
                     93:                else
                     94:                        {
                     95:                        min = w;
                     96:                        w = head[w];
                     97:                        }
                     98:                if (t != min)
                     99:                        {
                    100:                        head[t] = min;
                    101:                        t = min;
                    102:                        }
                    103:                }
                    104:        if (w == -1)  min = y;  else  min = w;
                    105:        if (t != min)  head[t] = min;
                    106: 
                    107:        }

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