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