2.9BSD - /usr/src/cmd/struct/2.dfs.c

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

Defined functions

Defined variables

Defined macros