Return to 2.dfs.c CVS log

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

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

1.1     ! root        1: #ifndef lint
        !             2: static char sccsid[] = "@(#)2.dfs.c    4.1     (Berkeley)      2/11/83";
        !             3: #endif not lint
        !             4: 
        !             5: #include <stdio.h>
        !             6: #
        !             7: /* depth-first search used to identify back edges, unreachable nodes;
        !             8:        each node v entered by back edge replaced by
        !             9:        LOOPVX ->ITERVX -> v,
        !            10:        so that back edges entering v now enter the ITERVX,
        !            11:        and other edges entering v now enter the LOOPVX.
        !            12:        Nodes are numbered according to depth-first search:
        !            13:                before numbering- ntobef[v] = i => node numbered v is i'th
        !            14:                        node in order of first visit during the search;
        !            15:                after numbering- ntoaft[v] = i => node numbered v is i'th
        !            16:                        node visited in order of last visit during the search.
        !            17:                        Also, in this case after[i] = v.
        !            18: */
        !            19: 
        !            20: #include "def.h"
        !            21: #include "2.def.h"
        !            22: 
        !            23: #define MAXINS 3       /* spacing needed between numbers generated during depth first search */
        !            24: 
        !            25: int *status;
        !            26: int befcount, aftcount;
        !            27: /* following defines used to mark back edges and nodes entered by back edges */
        !            28: #define UNPROCESSED    0
        !            29: #define STACKED        1
        !            30: #define FINISHED       2
        !            31: #define MARK(v)        {REACH(v) = 1; }        /* mark node v */
        !            32: #define UNMARK(v)      {REACH(v) = 0; }
        !            33: #define MARKED(v)      (REACH(v))
        !            34: #define MKEDGE(e)      {if (e >= -1) e = -(e+3); }     /* mark edge e */
        !            35: #define UNMKEDGE(e)    {if (e < -1) e = -(e+3); }
        !            36: #define BACKEDGE(e)    (e < -1)
        !            37: 
        !            38: 
        !            39: dfs(v)         /* depth first search */
        !            40: VERT v;
        !            41:        {
        !            42:        int i; VERT w;
        !            43:        accessnum = 0;
        !            44:        status = challoc(sizeof(*status) * nodenum);
        !            45:        for (w = 0; w < nodenum; ++w)
        !            46:                {
        !            47:                status[w] = UNPROCESSED;
        !            48:                UNMARK(w);
        !            49:                }
        !            50:        search(v);
        !            51:        chreach();
        !            52:        chfree(status, sizeof(*status) * nodenum);
        !            53:        addloop();
        !            54:        after = challoc(sizeof(*after) * accessnum);
        !            55:        for (i = 0; i < accessnum; ++i)
        !            56:                after[i] = UNDEFINED;
        !            57:        ntoaft = challoc(sizeof(*ntoaft) * nodenum);
        !            58:        ntobef = challoc(sizeof(*ntobef) * nodenum);
        !            59:        for (w = 0; w < nodenum; ++w)
        !            60:                ntobef[w] = ntoaft[w] = UNDEFINED;
        !            61:        befcount = 0;
        !            62:        aftcount = 0;
        !            63:        repsearch(v);
        !            64:        }
        !            65: 
        !            66: 
        !            67: search(v)
        !            68:        /* using depth first search, mark back edges using MKEDGE, and nodes entered by back
        !            69:        edges using MARK */
        !            70: VERT v;
        !            71:        {
        !            72:        VERT adj; int i;
        !            73:        status[v] = STACKED;
        !            74:        for(i = 0; i < ARCNUM(v); ++i)
        !            75:                {
        !            76:                adj = ARC(v,i);
        !            77:                if (!DEFINED(adj)) continue;
        !            78:                else if (status[adj] == UNPROCESSED)
        !            79:                        search(adj);
        !            80:                else if (status[adj] == STACKED)
        !            81:                        {
        !            82:                        MARK(adj);              /* mark adj as entered by back edge */
        !            83:                        MKEDGE(ARC(v,i));       /* mark edge ARC(v,i) as being back edge */
        !            84:                        }
        !            85:                }
        !            86:        status[v] = FINISHED;
        !            87:        ++accessnum;
        !            88:        }
        !            89: 
        !            90: chreach()              /* look for unreachable nodes */
        !            91:        {
        !            92:        VERT v;
        !            93:        LOGICAL unreach;
        !            94:        unreach = FALSE;
        !            95:        for (v = 0; v < nodenum; ++v)
        !            96:                if (status[v] == UNPROCESSED && NTYPE(v) != FMTVX
        !            97:                        && NTYPE(v) != STOPVX && NTYPE(v) != RETVX)
        !            98:                        {
        !            99:                        unreach = TRUE;
        !           100:                        if (debug)
        !           101:                                fprintf(stderr,"node %d unreachable\n",v);
        !           102:                        }
        !           103:        if (unreach)
        !           104:                error(": unreachable statements - ","will be ignored","");
        !           105:        }
        !           106: 
        !           107: 
        !           108: addloop()      /* add LOOPVX, ITERVX at nodes entered by back edges, and adjust edges */
        !           109:        {
        !           110:        VERT v, adj;
        !           111:        int j, oldnum;
        !           112:        for (v = 0, oldnum = nodenum; v < oldnum; ++v)  /* insloop increases nodenum */
        !           113:                if (MARKED(v))
        !           114:                        {
        !           115:                        UNMARK(v);      /* remove mark indicating v entered by back edge */
        !           116:                        if (NTYPE(v) != ITERVX)                 /* DO loops already have ITERVX */
        !           117:                                 insloop(v);  /* add LOOPVX, ITERVX since v entered by back edge*/
        !           118:                        }
        !           119:        /* arcs which used to enter v now enter LOOPVX; must make back edges enter ITERVX */
        !           120:        for (v = 0; v < nodenum; ++v)
        !           121:                for (j = 0; j < ARCNUM(v); ++j)
        !           122:                        {
        !           123:                        if (BACKEDGE(ARC(v,j)))
        !           124:                                {
        !           125:                                UNMKEDGE(ARC(v,j));             /* return edge to normal value */
        !           126:                                adj = ARC(v,j);
        !           127:                                if (NTYPE(adj) == ITERVX) continue;
        !           128:                                ASSERT(NTYPE(adj) == LOOPVX,addloop);
        !           129:                                ARC(v,j) = ARC(adj,0);  /* change arc to point to ITERVX */
        !           130:                                ASSERT(NTYPE(ARC(v,j)) == ITERVX,addloop);
        !           131:                                }
        !           132:                        }
        !           133:        }
        !           134: 
        !           135: insloop(v)             /* insert LOOPVX, ITERVX at node number v */
        !           136: VERT v;
        !           137:        {
        !           138:        VERT loo, iter;
        !           139:        loo = create(LOOPVX, 1);
        !           140:        iter = create(ITERVX,1);
        !           141:        accessnum += 2;
        !           142:        /* want LOOPVX to take on node number v, so that arcs other than back arcs
        !           143:                entering v will enter the LOOPVX automatically */
        !           144:        exchange(&graph[v], &graph[loo]);
        !           145:        exchange(&v, &loo);
        !           146:        ARC(loo,0) = iter;
        !           147:        ARC(iter,0) = v;
        !           148:        FATH(iter) = UNDEFINED; /* will be defined later along with FATH for DOVX */
        !           149:        }
        !           150: 
        !           151: exchange(p1,p2)                /* exchange values of p1,p2 */
        !           152: int *p1,*p2;
        !           153:        {
        !           154:        int temp;
        !           155:        temp = *p1;
        !           156:        *p1 = *p2;
        !           157:        *p2 = temp;
        !           158:        }
        !           159: 
        !           160: 
        !           161: repsearch(v)           /* repeat df search in order to fill in after, ntoaft, ntobef tables */
        !           162: VERT v;
        !           163:        {
        !           164:        VERT adj; int i,temp;
        !           165:        ntobef[v] = befcount;
        !           166:        ++befcount;
        !           167:        for(i = 0; i < ARCNUM(v); ++i)
        !           168:                {
        !           169:                adj = ARC(v,i);
        !           170:                if (DEFINED(adj) && ntobef[adj] == UNDEFINED)
        !           171:                        repsearch(adj);
        !           172:                }
        !           173:        ++aftcount;
        !           174:        temp = accessnum - aftcount;
        !           175:        after[temp] = v;
        !           176:        ntoaft[v] = temp;
        !           177:        }

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