4.3BSD - /usr/src/usr.bin/struct/2.dfs.c

   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:     }

Defined functions

Defined variables

Defined macros