tsort.c (24360) | tsort.c (48566) |
---|---|
1/* 2 * Copyright (c) 1989, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Michael Rendell of Memorial University of Newfoundland. 7 * 8 * Redistribution and use in source and binary forms, with or without --- 19 unchanged lines hidden (view full) --- 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 * | 1/* 2 * Copyright (c) 1989, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Michael Rendell of Memorial University of Newfoundland. 7 * 8 * Redistribution and use in source and binary forms, with or without --- 19 unchanged lines hidden (view full) --- 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 * $Id: tsort.c,v 1.7 1997/03/11 14:48:14 peter Exp $ | 36 * $Id: tsort.c,v 1.8 1997/03/29 04:33:15 imp Exp $ |
37 */ 38 39#ifndef lint 40static char copyright[] = 41"@(#) Copyright (c) 1989, 1993, 1994\n\ 42 The Regents of the University of California. All rights reserved.\n"; 43#endif /* not lint */ 44 --- 290 unchanged lines hidden (view full) --- 335 for (cnt = 0, n = graph; n != NULL; n = n->n_next) 336 ++cnt; 337 cycle_buf = malloc((u_int)sizeof(NODE *) * cnt); 338 longest_cycle = malloc((u_int)sizeof(NODE *) * cnt); 339 if (cycle_buf == NULL || longest_cycle == NULL) 340 err(1, NULL); 341 } 342 for (n = graph; n != NULL; n = n->n_next) | 37 */ 38 39#ifndef lint 40static char copyright[] = 41"@(#) Copyright (c) 1989, 1993, 1994\n\ 42 The Regents of the University of California. All rights reserved.\n"; 43#endif /* not lint */ 44 --- 290 unchanged lines hidden (view full) --- 335 for (cnt = 0, n = graph; n != NULL; n = n->n_next) 336 ++cnt; 337 cycle_buf = malloc((u_int)sizeof(NODE *) * cnt); 338 longest_cycle = malloc((u_int)sizeof(NODE *) * cnt); 339 if (cycle_buf == NULL || longest_cycle == NULL) 340 err(1, NULL); 341 } 342 for (n = graph; n != NULL; n = n->n_next) |
343 if (!(n->n_flags & NF_ACYCLIC)) | 343 if (!(n->n_flags & NF_ACYCLIC)) { |
344 if ((cnt = find_cycle(n, n, 0, 0))) { 345 if (!quiet) { 346 warnx("cycle in data"); 347 for (i = 0; i < cnt; i++) 348 warnx("%s", 349 longest_cycle[i]->n_name); 350 } 351 remove_node(n); 352 clear_cycle(); 353 break; 354 } else { 355 /* to avoid further checks */ 356 n->n_flags |= NF_ACYCLIC; 357 clear_cycle(); 358 } | 344 if ((cnt = find_cycle(n, n, 0, 0))) { 345 if (!quiet) { 346 warnx("cycle in data"); 347 for (i = 0; i < cnt; i++) 348 warnx("%s", 349 longest_cycle[i]->n_name); 350 } 351 remove_node(n); 352 clear_cycle(); 353 break; 354 } else { 355 /* to avoid further checks */ 356 n->n_flags |= NF_ACYCLIC; 357 clear_cycle(); 358 } |
359 } |
|
359 360 if (n == NULL) 361 errx(1, "internal error -- could not find cycle"); 362 } 363} 364 365/* print node and remove from graph (does not actually free node) */ 366void --- 71 unchanged lines hidden --- | 360 361 if (n == NULL) 362 errx(1, "internal error -- could not find cycle"); 363 } 364} 365 366/* print node and remove from graph (does not actually free node) */ 367void --- 71 unchanged lines hidden --- |