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