Return to 2.dfs.c CVS log

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

Annotation of 3BSD/cmd/struct/2.dfs.c, revision 1.1

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

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