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