2 * Copyright (c) 1983 Regents of the University of California.
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.
21 static char sccsid
[] = "@(#)dfn.c 5.4 (Berkeley) 6/1/90";
32 typedef struct dfnstruct dfntype
;
34 dfntype dfn_stack
[ DFN_DEPTH
];
37 int dfn_counter
= DFN_NAN
;
40 * given this parent, depth first number its children.
48 if ( debug
& DFNDEBUG
) {
49 printf( "[dfn] dfn(" );
55 * if we're already numbered, no need to look any furthur.
57 if ( dfn_numbered( parentp
) ) {
61 * if we're already busy, must be a cycle
63 if ( dfn_busy( parentp
) ) {
64 dfn_findcycle( parentp
);
68 * visit yourself before your children
70 dfn_pre_visit( parentp
);
74 for ( arcp
= parentp
-> children
; arcp
; arcp
= arcp
-> arc_childlist
) {
75 dfn( arcp
-> arc_childp
);
78 * visit yourself after your children
80 dfn_post_visit( parentp
);
84 * push a parent onto the stack and mark it busy
86 dfn_pre_visit( parentp
)
91 if ( dfn_depth
>= DFN_DEPTH
) {
92 fprintf( stderr
, "[dfn] out of my depth (dfn_stack overflow)\n" );
95 dfn_stack
[ dfn_depth
].nlentryp
= parentp
;
96 dfn_stack
[ dfn_depth
].cycletop
= dfn_depth
;
97 parentp
-> toporder
= DFN_BUSY
;
99 if ( debug
& DFNDEBUG
) {
100 printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth
);
101 printname( parentp
);
108 * are we already numbered?
111 dfn_numbered( childp
)
115 return ( childp
-> toporder
!= DFN_NAN
&& childp
-> toporder
!= DFN_BUSY
);
119 * are we already busy?
126 if ( childp
-> toporder
== DFN_NAN
) {
133 * MISSING: an explanation
135 dfn_findcycle( childp
)
143 for ( cycletop
= dfn_depth
; cycletop
> 0 ; cycletop
-= 1 ) {
144 cycleheadp
= dfn_stack
[ cycletop
].nlentryp
;
145 if ( childp
== cycleheadp
) {
148 if ( childp
-> cyclehead
!= childp
&&
149 childp
-> cyclehead
== cycleheadp
) {
153 if ( cycletop
<= 0 ) {
154 fprintf( stderr
, "[dfn_findcycle] couldn't find head of cycle\n" );
158 if ( debug
& DFNDEBUG
) {
159 printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
160 dfn_depth
, cycletop
);
161 printname( cycleheadp
);
165 if ( cycletop
== dfn_depth
) {
167 * this is previous function, e.g. this calls itself
170 dfn_self_cycle( childp
);
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.
178 for ( tailp
= cycleheadp
; tailp
-> cnext
; tailp
= tailp
-> cnext
) {
179 /* void: chase down to tail of things already glommed */
181 if ( debug
& DFNDEBUG
) {
182 printf( "[dfn_findcycle] tail " );
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
193 if ( cycleheadp
-> cyclehead
!= cycleheadp
) {
194 cycleheadp
= cycleheadp
-> cyclehead
;
196 if ( debug
& DFNDEBUG
) {
197 printf( "[dfn_findcycle] new cyclehead " );
198 printname( cycleheadp
);
203 for ( index
= cycletop
+ 1 ; index
<= dfn_depth
; index
+= 1 ) {
204 childp
= dfn_stack
[ index
].nlentryp
;
205 if ( childp
-> cyclehead
== childp
) {
207 * not yet glommed anywhere, glom it
208 * and fix any children it has glommed
210 tailp
-> cnext
= childp
;
211 childp
-> cyclehead
= cycleheadp
;
213 if ( debug
& DFNDEBUG
) {
214 printf( "[dfn_findcycle] glomming " );
217 printname( cycleheadp
);
221 for ( tailp
= childp
; tailp
->cnext
; tailp
= tailp
->cnext
) {
222 tailp
-> cnext
-> cyclehead
= cycleheadp
;
224 if ( debug
& DFNDEBUG
) {
225 printf( "[dfn_findcycle] and its tail " );
226 printname( tailp
-> cnext
);
228 printname( cycleheadp
);
233 } else if ( childp
-> cyclehead
!= cycleheadp
/* firewall */ ) {
235 "[dfn_busy] glommed, but not to cyclehead\n" );
242 * deal with self-cycles
245 dfn_self_cycle( parentp
)
249 * since we are taking out self-cycles elsewhere
250 * no need for the special case, here.
253 if ( debug
& DFNDEBUG
) {
254 printf( "[dfn_self_cycle] " );
255 printname( parentp
);
262 * visit a node after all its children
263 * [MISSING: an explanation]
264 * and pop it off the stack
266 dfn_post_visit( parentp
)
272 if ( debug
& DFNDEBUG
) {
273 printf( "[dfn_post_visit]\t%d: " , dfn_depth
);
274 printname( parentp
);
279 * number functions and things in their cycles
280 * unless the function is itself part of a cycle
282 if ( parentp
-> cyclehead
== parentp
) {
284 for ( memberp
= parentp
; memberp
; memberp
= memberp
-> cnext
) {
285 memberp
-> toporder
= dfn_counter
;
287 if ( debug
& DFNDEBUG
) {
288 printf( "[dfn_post_visit]\t\tmember " );
289 printname( memberp
);
290 printf( " -> toporder = %d\n" , dfn_counter
);
296 if ( debug
& DFNDEBUG
) {
297 printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
This page took 0.035395 seconds and 4 git commands to generate.