Annotation of src/usr.bin/gprof/dfn.c, Revision 1.7
1.7 ! deraadt 1: /* $OpenBSD: dfn.c,v 1.6 2006/03/25 19:06:35 espie Exp $ */
1.1 deraadt 2: /* $NetBSD: dfn.c,v 1.5 1995/04/19 07:15:56 cgd Exp $ */
3:
4: /*
5: * Copyright (c) 1983, 1993
6: * The Regents of the University of California. All rights reserved.
7: *
8: * Redistribution and use in source and binary forms, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
1.5 millert 16: * 3. Neither the name of the University nor the names of its contributors
1.1 deraadt 17: * may be used to endorse or promote products derived from this software
18: * without specific prior written permission.
19: *
20: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30: * SUCH DAMAGE.
31: */
32:
33: #include <stdio.h>
34: #include "gprof.h"
35:
36: #define DFN_DEPTH 100
37: struct dfnstruct {
38: nltype *nlentryp;
39: int cycletop;
40: };
41: typedef struct dfnstruct dfntype;
42:
43: dfntype dfn_stack[ DFN_DEPTH ];
44: int dfn_depth;
45:
46: int dfn_counter;
47:
1.3 mickey 48: void
1.1 deraadt 49: dfn_init()
50: {
51:
52: dfn_depth = 0;
53: dfn_counter = DFN_NAN;
54: }
55:
56: /*
57: * given this parent, depth first number its children.
58: */
1.3 mickey 59: void
1.6 espie 60: dfn(nltype *parentp)
1.1 deraadt 61: {
62: arctype *arcp;
63:
64: # ifdef DEBUG
65: if ( debug & DFNDEBUG ) {
66: printf( "[dfn] dfn(" );
67: printname( parentp );
68: printf( ")\n" );
69: }
1.4 danh 70: # endif /* DEBUG */
1.1 deraadt 71: /*
72: * if we're already numbered, no need to look any furthur.
73: */
74: if ( dfn_numbered( parentp ) ) {
75: return;
76: }
77: /*
78: * if we're already busy, must be a cycle
79: */
80: if ( dfn_busy( parentp ) ) {
81: dfn_findcycle( parentp );
82: return;
83: }
84: /*
85: * visit yourself before your children
86: */
87: dfn_pre_visit( parentp );
88: /*
89: * visit children
90: */
91: for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
92: if ( arcp -> arc_flags & DEADARC )
93: continue;
94: dfn( arcp -> arc_childp );
95: }
96: /*
97: * visit yourself after your children
98: */
99: dfn_post_visit( parentp );
100: }
101:
102: /*
103: * push a parent onto the stack and mark it busy
104: */
1.3 mickey 105: void
1.6 espie 106: dfn_pre_visit(nltype *parentp)
1.1 deraadt 107: {
108:
109: dfn_depth += 1;
1.3 mickey 110: if ( dfn_depth >= DFN_DEPTH )
111: errx(1, "[dfn] out of my depth (dfn_stack overflow)" );
1.1 deraadt 112: dfn_stack[ dfn_depth ].nlentryp = parentp;
113: dfn_stack[ dfn_depth ].cycletop = dfn_depth;
114: parentp -> toporder = DFN_BUSY;
115: # ifdef DEBUG
116: if ( debug & DFNDEBUG ) {
117: printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
118: printname( parentp );
119: printf( "\n" );
120: }
1.4 danh 121: # endif /* DEBUG */
1.1 deraadt 122: }
123:
124: /*
125: * are we already numbered?
126: */
127: bool
1.6 espie 128: dfn_numbered(nltype *childp)
1.1 deraadt 129: {
130:
131: return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
132: }
133:
134: /*
135: * are we already busy?
136: */
137: bool
1.6 espie 138: dfn_busy(nltype *childp)
1.1 deraadt 139: {
140:
141: if ( childp -> toporder == DFN_NAN ) {
142: return FALSE;
143: }
144: return TRUE;
145: }
146:
147: /*
148: * MISSING: an explanation
149: */
1.3 mickey 150: void
1.6 espie 151: dfn_findcycle(nltype *childp)
1.1 deraadt 152: {
153: int cycletop;
154: nltype *cycleheadp;
155: nltype *tailp;
156: int index;
157:
158: for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
159: cycleheadp = dfn_stack[ cycletop ].nlentryp;
160: if ( childp == cycleheadp ) {
161: break;
162: }
163: if ( childp -> cyclehead != childp &&
164: childp -> cyclehead == cycleheadp ) {
165: break;
166: }
167: }
1.3 mickey 168: if ( cycletop <= 0 )
169: errx( 1, "[dfn_findcycle] couldn't find head of cycle");
1.1 deraadt 170: # ifdef DEBUG
171: if ( debug & DFNDEBUG ) {
172: printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
173: dfn_depth , cycletop );
174: printname( cycleheadp );
175: printf( "\n" );
176: }
1.4 danh 177: # endif /* DEBUG */
1.1 deraadt 178: if ( cycletop == dfn_depth ) {
179: /*
180: * this is previous function, e.g. this calls itself
181: * sort of boring
182: */
183: dfn_self_cycle( childp );
184: } else {
185: /*
186: * glom intervening functions that aren't already
187: * glommed into this cycle.
188: * things have been glommed when their cyclehead field
189: * points to the head of the cycle they are glommed into.
190: */
191: for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
192: /* void: chase down to tail of things already glommed */
193: # ifdef DEBUG
194: if ( debug & DFNDEBUG ) {
195: printf( "[dfn_findcycle] tail " );
196: printname( tailp );
197: printf( "\n" );
198: }
1.4 danh 199: # endif /* DEBUG */
1.1 deraadt 200: }
201: /*
202: * if what we think is the top of the cycle
203: * has a cyclehead field, then it's not really the
204: * head of the cycle, which is really what we want
205: */
206: if ( cycleheadp -> cyclehead != cycleheadp ) {
207: cycleheadp = cycleheadp -> cyclehead;
208: # ifdef DEBUG
209: if ( debug & DFNDEBUG ) {
210: printf( "[dfn_findcycle] new cyclehead " );
211: printname( cycleheadp );
212: printf( "\n" );
213: }
1.4 danh 214: # endif /* DEBUG */
1.1 deraadt 215: }
216: for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
217: childp = dfn_stack[ index ].nlentryp;
218: if ( childp -> cyclehead == childp ) {
219: /*
220: * not yet glommed anywhere, glom it
221: * and fix any children it has glommed
222: */
223: tailp -> cnext = childp;
224: childp -> cyclehead = cycleheadp;
225: # ifdef DEBUG
226: if ( debug & DFNDEBUG ) {
227: printf( "[dfn_findcycle] glomming " );
228: printname( childp );
229: printf( " onto " );
230: printname( cycleheadp );
231: printf( "\n" );
232: }
1.4 danh 233: # endif /* DEBUG */
1.1 deraadt 234: for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
235: tailp -> cnext -> cyclehead = cycleheadp;
236: # ifdef DEBUG
237: if ( debug & DFNDEBUG ) {
238: printf( "[dfn_findcycle] and its tail " );
239: printname( tailp -> cnext );
240: printf( " onto " );
241: printname( cycleheadp );
242: printf( "\n" );
243: }
1.4 danh 244: # endif /* DEBUG */
1.1 deraadt 245: }
1.3 mickey 246: } else if ( childp -> cyclehead != cycleheadp /* firewall */ )
247: warnx("[dfn_busy] glommed, but not to cyclehead");
1.1 deraadt 248: }
249: }
250: }
251:
252: /*
253: * deal with self-cycles
254: * for lint: ARGSUSED
255: */
1.3 mickey 256: void
1.6 espie 257: dfn_self_cycle(nltype *parentp)
1.1 deraadt 258: {
259: /*
260: * since we are taking out self-cycles elsewhere
261: * no need for the special case, here.
262: */
263: # ifdef DEBUG
264: if ( debug & DFNDEBUG ) {
265: printf( "[dfn_self_cycle] " );
266: printname( parentp );
267: printf( "\n" );
268: }
1.4 danh 269: # endif /* DEBUG */
1.1 deraadt 270: }
271:
272: /*
273: * visit a node after all its children
274: * [MISSING: an explanation]
275: * and pop it off the stack
276: */
1.3 mickey 277: void
1.6 espie 278: dfn_post_visit(nltype *parentp)
1.1 deraadt 279: {
280: nltype *memberp;
281:
282: # ifdef DEBUG
283: if ( debug & DFNDEBUG ) {
284: printf( "[dfn_post_visit]\t%d: " , dfn_depth );
285: printname( parentp );
286: printf( "\n" );
287: }
1.4 danh 288: # endif /* DEBUG */
1.1 deraadt 289: /*
290: * number functions and things in their cycles
291: * unless the function is itself part of a cycle
292: */
293: if ( parentp -> cyclehead == parentp ) {
294: dfn_counter += 1;
295: for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
296: memberp -> toporder = dfn_counter;
297: # ifdef DEBUG
298: if ( debug & DFNDEBUG ) {
299: printf( "[dfn_post_visit]\t\tmember " );
300: printname( memberp );
301: printf( " -> toporder = %d\n" , dfn_counter );
302: }
1.4 danh 303: # endif /* DEBUG */
1.1 deraadt 304: }
305: } else {
306: # ifdef DEBUG
307: if ( debug & DFNDEBUG ) {
308: printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
309: }
1.4 danh 310: # endif /* DEBUG */
1.1 deraadt 311: }
312: dfn_depth -= 1;
313: }
![[BACK]](/icons/back.gif){kind=icon}
Return to dfn.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / gprof