# 2.11BSD#431 - /usr/src/usr.bin/struct/2.dfs.c

##### Functions

    addloop           X
    chreach           X
    dfs               X
    exchange          X
    insloop           X
    repsearch         X
    search            X

##### Variables

    aftcount          X
    befcount          X
    status            X

##### Macros

    BACKEDGE          X
    FINISHED          X
    MARK              X
    MARKED            X
    MAXINS            X
    MKEDGE            X
    STACKED           X
    UNMARK            X
    UNMKEDGE          X
    UNPROCESSED       X

       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 = (int *)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 = (int *)challoc(sizeof(*after) * accessnum);
      55:     for (i = 0; i < accessnum; ++i)
      56:         after[i] = UNDEFINED;
      57:     ntoaft = (int *)challoc(sizeof(*ntoaft) * nodenum);
      58:     ntobef = (int *)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:     }

#### Defined functions

addloop defined in line 108; used 3 times

- in line 53, 128-130(2)

chreach defined in line 90; used 1 times

- in line 51

dfs defined in line 39; used 1 times

- in /usr/src/usr.bin/struct/2.main.c line 16

exchange defined in line 151; used 4 times

- in line 144-145(2)
- in /usr/src/usr.bin/struct/3.loop.c line 140
- in /usr/src/usr.bin/struct/3.then.c line 77

insloop defined in line 135; used 1 times

- in line 117

repsearch defined in line 161; used 2 times

- in line 63, 171

search defined in line 67; used 2 times

- in line 50, 79

#### Defined variables

aftcount defined in line 26; used 3 times

- in line 62, 173-174(2)

befcount defined in line 26; used 3 times

- in line 61, 165-166(2)

sccsid defined in line 2; never used
status defined in line 25; used 10 times

- in line 44-52(5), 73-80(3), 86, 96

#### Defined macros

BACKEDGE defined in line 36; used 1 times

- in line 123

FINISHED defined in line 30; used 1 times

- in line 86

MARK defined in line 31; used 1 times

- in line 82

MARKED defined in line 33; used 1 times

- in line 113

MAXINS defined in line 23; never used
MKEDGE defined in line 34; used 1 times

- in line 83

STACKED defined in line 29; used 2 times

- in line 73, 80

UNMARK defined in line 32; used 2 times

- in line 48, 115

UNMKEDGE defined in line 35; used 1 times

- in line 125

UNPROCESSED defined in line 28; used 3 times

- in line 47, 78, 96

Last modified: 1993-01-18 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1000 |