![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to 2.dfs.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / usr.bin / struct|
Return to 2.dfs.c CVS log | Up to [CSRG BSD Unix] / 43BSD / usr.bin / struct |
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.