![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dfn.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ucb / gprof|
Return to dfn.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ucb / gprof |
1.1 root 1: /*
2: * Copyright (c) 1983 Regents of the University of California.
3: * All rights reserved. The Berkeley software License Agreement
4: * specifies the terms and conditions for redistribution.
5: */
6:
7: #ifndef lint
8: static char sccsid[] = "@(#)dfn.c 5.1 (Berkeley) 6/4/85";
9: #endif not lint
10:
11: #include <stdio.h>
12: #include "gprof.h"
13:
14: #define DFN_DEPTH 100
15: struct dfnstruct {
16: nltype *nlentryp;
17: int cycletop;
18: };
19: typedef struct dfnstruct dfntype;
20:
21: dfntype dfn_stack[ DFN_DEPTH ];
22: int dfn_depth = 0;
23:
24: int dfn_counter = DFN_NAN;
25:
26: /*
27: * given this parent, depth first number its children.
28: */
29: dfn( parentp )
30: nltype *parentp;
31: {
32: arctype *arcp;
33:
34: # ifdef DEBUG
35: if ( debug & DFNDEBUG ) {
36: printf( "[dfn] dfn(" );
37: printname( parentp );
38: printf( ")\n" );
39: }
40: # endif DEBUG
41: /*
42: * if we're already numbered, no need to look any furthur.
43: */
44: if ( dfn_numbered( parentp ) ) {
45: return;
46: }
47: /*
48: * if we're already busy, must be a cycle
49: */
50: if ( dfn_busy( parentp ) ) {
51: dfn_findcycle( parentp );
52: return;
53: }
54: /*
55: * visit yourself before your children
56: */
57: dfn_pre_visit( parentp );
58: /*
59: * visit children
60: */
61: for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
62: dfn( arcp -> arc_childp );
63: }
64: /*
65: * visit yourself after your children
66: */
67: dfn_post_visit( parentp );
68: }
69:
70: /*
71: * push a parent onto the stack and mark it busy
72: */
73: dfn_pre_visit( parentp )
74: nltype *parentp;
75: {
76:
77: dfn_depth += 1;
78: if ( dfn_depth >= DFN_DEPTH ) {
79: fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
80: exit( 1 );
81: }
82: dfn_stack[ dfn_depth ].nlentryp = parentp;
83: dfn_stack[ dfn_depth ].cycletop = dfn_depth;
84: parentp -> toporder = DFN_BUSY;
85: # ifdef DEBUG
86: if ( debug & DFNDEBUG ) {
87: printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
88: printname( parentp );
89: printf( "\n" );
90: }
91: # endif DEBUG
92: }
93:
94: /*
95: * are we already numbered?
96: */
97: bool
98: dfn_numbered( childp )
99: nltype *childp;
100: {
101:
102: return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
103: }
104:
105: /*
106: * are we already busy?
107: */
108: bool
109: dfn_busy( childp )
110: nltype *childp;
111: {
112:
113: if ( childp -> toporder == DFN_NAN ) {
114: return FALSE;
115: }
116: return TRUE;
117: }
118:
119: /*
120: * MISSING: an explanation
121: */
122: dfn_findcycle( childp )
123: nltype *childp;
124: {
125: int cycletop;
126: nltype *cycleheadp;
127: nltype *tailp;
128: int index;
129:
130: for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
131: cycleheadp = dfn_stack[ cycletop ].nlentryp;
132: if ( childp == cycleheadp ) {
133: break;
134: }
135: if ( childp -> cyclehead != childp &&
136: childp -> cyclehead == cycleheadp ) {
137: break;
138: }
139: }
140: if ( cycletop <= 0 ) {
141: fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
142: exit( 1 );
143: }
144: # ifdef DEBUG
145: if ( debug & DFNDEBUG ) {
146: printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
147: dfn_depth , cycletop );
148: printname( cycleheadp );
149: printf( "\n" );
150: }
151: # endif DEBUG
152: if ( cycletop == dfn_depth ) {
153: /*
154: * this is previous function, e.g. this calls itself
155: * sort of boring
156: */
157: dfn_self_cycle( childp );
158: } else {
159: /*
160: * glom intervening functions that aren't already
161: * glommed into this cycle.
162: * things have been glommed when their cyclehead field
163: * points to the head of the cycle they are glommed into.
164: */
165: for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
166: /* void: chase down to tail of things already glommed */
167: # ifdef DEBUG
168: if ( debug & DFNDEBUG ) {
169: printf( "[dfn_findcycle] tail " );
170: printname( tailp );
171: printf( "\n" );
172: }
173: # endif DEBUG
174: }
175: /*
176: * if what we think is the top of the cycle
177: * has a cyclehead field, then it's not really the
178: * head of the cycle, which is really what we want
179: */
180: if ( cycleheadp -> cyclehead != cycleheadp ) {
181: cycleheadp = cycleheadp -> cyclehead;
182: # ifdef DEBUG
183: if ( debug & DFNDEBUG ) {
184: printf( "[dfn_findcycle] new cyclehead " );
185: printname( cycleheadp );
186: printf( "\n" );
187: }
188: # endif DEBUG
189: }
190: for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
191: childp = dfn_stack[ index ].nlentryp;
192: if ( childp -> cyclehead == childp ) {
193: /*
194: * not yet glommed anywhere, glom it
195: * and fix any children it has glommed
196: */
197: tailp -> cnext = childp;
198: childp -> cyclehead = cycleheadp;
199: # ifdef DEBUG
200: if ( debug & DFNDEBUG ) {
201: printf( "[dfn_findcycle] glomming " );
202: printname( childp );
203: printf( " onto " );
204: printname( cycleheadp );
205: printf( "\n" );
206: }
207: # endif DEBUG
208: for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
209: tailp -> cnext -> cyclehead = cycleheadp;
210: # ifdef DEBUG
211: if ( debug & DFNDEBUG ) {
212: printf( "[dfn_findcycle] and its tail " );
213: printname( tailp -> cnext );
214: printf( " onto " );
215: printname( cycleheadp );
216: printf( "\n" );
217: }
218: # endif DEBUG
219: }
220: } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
221: fprintf( stderr ,
222: "[dfn_busy] glommed, but not to cyclehead\n" );
223: }
224: }
225: }
226: }
227:
228: /*
229: * deal with self-cycles
230: * for lint: ARGSUSED
231: */
232: dfn_self_cycle( parentp )
233: nltype *parentp;
234: {
235: /*
236: * since we are taking out self-cycles elsewhere
237: * no need for the special case, here.
238: */
239: # ifdef DEBUG
240: if ( debug & DFNDEBUG ) {
241: printf( "[dfn_self_cycle] " );
242: printname( parentp );
243: printf( "\n" );
244: }
245: # endif DEBUG
246: }
247:
248: /*
249: * visit a node after all its children
250: * [MISSING: an explanation]
251: * and pop it off the stack
252: */
253: dfn_post_visit( parentp )
254: nltype *parentp;
255: {
256: nltype *memberp;
257:
258: # ifdef DEBUG
259: if ( debug & DFNDEBUG ) {
260: printf( "[dfn_post_visit]\t%d: " , dfn_depth );
261: printname( parentp );
262: printf( "\n" );
263: }
264: # endif DEBUG
265: /*
266: * number functions and things in their cycles
267: * unless the function is itself part of a cycle
268: */
269: if ( parentp -> cyclehead == parentp ) {
270: dfn_counter += 1;
271: for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
272: memberp -> toporder = dfn_counter;
273: # ifdef DEBUG
274: if ( debug & DFNDEBUG ) {
275: printf( "[dfn_post_visit]\t\tmember " );
276: printname( memberp );
277: printf( " -> toporder = %d\n" , dfn_counter );
278: }
279: # endif DEBUG
280: }
281: } else {
282: # ifdef DEBUG
283: if ( debug & DFNDEBUG ) {
284: printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
285: }
286: # endif DEBUG
287: }
288: dfn_depth -= 1;
289: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.