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