From df5937c801159ccf5fd7dc38754faa4077629bb4 Mon Sep 17 00:00:00 2001 From: Keith Bostic Date: Wed, 30 Mar 1994 21:19:09 -0800 Subject: [PATCH] change tsort to not look for the longest cycle (add a -l flag for users that actually want the longest cycle). This is backward compatible with historic tsort, it didn't find the longest cycle either. This provides a major speedup for some tsort runs. From: christos@deshaw.com (Christos Zoulas) SCCS-vsn: usr.bin/tsort/tsort.1 8.2 SCCS-vsn: usr.bin/tsort/tsort.c 8.2 --- usr/src/usr.bin/tsort/tsort.1 | 13 ++- usr/src/usr.bin/tsort/tsort.c | 155 ++++++++++++++++++---------------- 2 files changed, 91 insertions(+), 77 deletions(-) diff --git a/usr/src/usr.bin/tsort/tsort.1 b/usr/src/usr.bin/tsort/tsort.1 index e0e1dc726a..6958891362 100644 --- a/usr/src/usr.bin/tsort/tsort.1 +++ b/usr/src/usr.bin/tsort/tsort.1 @@ -1,11 +1,12 @@ -.\" Copyright (c) 1990, 1993 +.\" Copyright (c) 1990, 1993, 1994 .\" The Regents of the University of California. All rights reserved. .\" .\" This manual is derived from one contributed to Berkeley by .\" Michael Rendell of Memorial University of Newfoundland. +.\" .\" %sccs.include.redist.roff% .\" -.\" @(#)tsort.1 8.1 (Berkeley) %G% +.\" @(#)tsort.1 8.2 (Berkeley) %G% .\" .Dd .Dt TSORT 1 @@ -15,6 +16,7 @@ .Nd topological sort of a directed graph .Sh SYNOPSIS .Nm tsort +.Op Fl l .Op Ar file .Sh DESCRIPTION .Nm Tsort @@ -35,6 +37,13 @@ This is useful when a node is not connected to any other nodes. If the graph contains a cycle (and therefore cannot be properly sorted), one of the arcs in the cycle is ignored and the sort continues. Cycles are reported on standard error. +.Pp +The options are as follows: +.Bl -tag -width Ds +.It Fl l +Search for and display the longest cycle. +Can take a very long time. +.El .Sh SEE ALSO .Xr ar 1 .Sh HISTORY diff --git a/usr/src/usr.bin/tsort/tsort.c b/usr/src/usr.bin/tsort/tsort.c index eb0c324002..16d2ae2201 100644 --- a/usr/src/usr.bin/tsort/tsort.c +++ b/usr/src/usr.bin/tsort/tsort.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 1989, 1993 + * Copyright (c) 1989, 1993, 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by @@ -10,21 +10,23 @@ #ifndef lint static char copyright[] = -"@(#) Copyright (c) 1989, 1993\n\ +"@(#) Copyright (c) 1989, 1993, 1994\n\ The Regents of the University of California. All rights reserved.\n"; #endif /* not lint */ #ifndef lint -static char sccsid[] = "@(#)tsort.c 8.1 (Berkeley) %G%"; +static char sccsid[] = "@(#)tsort.c 8.2 (Berkeley) %G%"; #endif /* not lint */ #include + +#include +#include +#include #include #include -#include #include #include -#include #include /* @@ -33,7 +35,7 @@ static char sccsid[] = "@(#)tsort.c 8.1 (Berkeley) %G%"; * standard output in sorted order, one per line. * * usage: - * tsort [inputfile] + * tsort [-l] [inputfile] * If no input file is specified, standard input is read. * * Should be compatable with AT&T tsort HOWEVER the output is not identical @@ -47,6 +49,8 @@ static char sccsid[] = "@(#)tsort.c 8.1 (Berkeley) %G%"; #define HASHSIZE 53 /* doesn't need to be big */ #define NF_MARK 0x1 /* marker for cycle detection */ #define NF_ACYCLIC 0x2 /* this node is cycle free */ +#define NF_NODEST 0x4 /* Unreachable */ + typedef struct node_str NODE; @@ -67,12 +71,10 @@ typedef struct _buf { } BUF; DB *db; -NODE *graph; -NODE **cycle_buf; -NODE **longest_cycle; +NODE *graph, **cycle_buf, **longest_cycle; +int debug, longest; void add_arc __P((char *, char *)); -void err __P((const char *, ...)); int find_cycle __P((NODE *, NODE *, int, int)); NODE *get_node __P((char *)); void *grow_buf __P((void *, int)); @@ -91,8 +93,14 @@ main(argc, argv) int bsize, ch, nused; BUF bufs[2]; - while ((ch = getopt(argc, argv, "")) != EOF) - switch(ch) { + while ((ch = getopt(argc, argv, "dl")) != EOF) + switch (ch) { + case 'd': + debug = 1; + break; + case 'l': + longest = 1; + break; case '?': default: usage(); @@ -100,13 +108,13 @@ main(argc, argv) argc -= optind; argv += optind; - switch(argc) { + switch (argc) { case 0: fp = stdin; break; case 1: if ((fp = fopen(*argv, "r")) == NULL) - err("%s: %s", *argv, strerror(errno)); + err(1, "%s", *argv); break; default: usage(); @@ -140,7 +148,7 @@ main(argc, argv) } (void)fclose(fp); if (n) - err("odd data count"); + errx(1, "odd data count"); /* do the sort */ tsort(); @@ -154,7 +162,7 @@ grow_buf(bp, size) int size; { if ((bp = realloc(bp, (u_int)size)) == NULL) - err("%s", strerror(errno)); + err(1, NULL); return (bp); } @@ -207,12 +215,12 @@ get_node(name) if (db == NULL && (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL) - err("db: open: %s", name, strerror(errno)); + err(1, "db: %s", name); key.data = name; key.size = strlen(name) + 1; - switch((*db->get)(db, &key, &data, 0)) { + switch ((*db->get)(db, &key, &data, 0)) { case 0: bcopy(data.data, &n, sizeof(n)); return (n); @@ -220,11 +228,11 @@ get_node(name) break; default: case -1: - err("db: get %s: %s", name, strerror(errno)); + err(1, "db: %s", name); } if ((n = malloc(sizeof(NODE) + key.size)) == NULL) - err("%s", strerror(errno)); + err(1, NULL); n->n_narcs = 0; n->n_arcsize = 0; @@ -234,7 +242,7 @@ get_node(name) bcopy(name, n->n_name, key.size); /* Add to linked list. */ - if (n->n_next = graph) + if ((n->n_next = graph) != NULL) graph->n_prevp = &n->n_next; n->n_prevp = &graph; graph = n; @@ -243,34 +251,47 @@ get_node(name) data.data = &n; data.size = sizeof(n); if ((*db->put)(db, &key, &data, 0)) - err("db: put %s: %s", name, strerror(errno)); + err(1, "db: %s", name); return (n); } + +/* + * Clear the NODEST flag from all nodes. + */ +void +clear_cycle() +{ + NODE *n; + + for (n = graph; n != NULL; n = n->n_next) + n->n_flags &= ~NF_NODEST; +} + /* do topological sort on graph */ void tsort() { register NODE *n, *next; - register int cnt; + register int cnt, i; - while (graph) { + while (graph != NULL) { /* * Keep getting rid of simple cases until there are none left, * if there are any nodes still in the graph, then there is * a cycle in it. */ do { - for (cnt = 0, n = graph; n; n = next) { + for (cnt = 0, n = graph; n != NULL; n = next) { next = n->n_next; if (n->n_refcnt == 0) { remove_node(n); ++cnt; } } - } while (graph && cnt); + } while (graph != NULL && cnt); - if (!graph) + if (graph == NULL) break; if (!cycle_buf) { @@ -279,32 +300,31 @@ tsort() * as scratch space, the other to save the longest * cycle. */ - for (cnt = 0, n = graph; n; n = n->n_next) + for (cnt = 0, n = graph; n != NULL; n = n->n_next) ++cnt; cycle_buf = malloc((u_int)sizeof(NODE *) * cnt); longest_cycle = malloc((u_int)sizeof(NODE *) * cnt); if (cycle_buf == NULL || longest_cycle == NULL) - err("%s", strerror(errno)); + err(1, NULL); } - for (n = graph; n; n = n->n_next) - if (!(n->n_flags & NF_ACYCLIC)) { + for (n = graph; n != NULL; n = n->n_next) + if (!(n->n_flags & NF_ACYCLIC)) if (cnt = find_cycle(n, n, 0, 0)) { - register int i; - - (void)fprintf(stderr, - "tsort: cycle in data\n"); + warnx("cycle in data"); for (i = 0; i < cnt; i++) - (void)fprintf(stderr, - "tsort: %s\n", longest_cycle[i]->n_name); + warnx("%s", + longest_cycle[i]->n_name); remove_node(n); + clear_cycle(); break; - } else + } else { /* to avoid further checks */ - n->n_flags = NF_ACYCLIC; - } + n->n_flags |= NF_ACYCLIC; + clear_cycle(); + } - if (!n) - err("internal error -- could not find cycle"); + if (n == NULL) + errx(1, "internal error -- could not find cycle"); } } @@ -325,7 +345,8 @@ remove_node(n) n->n_next->n_prevp = n->n_prevp; } -/* look for the longest cycle from node from to node to. */ + +/* look for the longest? cycle from node from to node to. */ int find_cycle(from, to, longest_len, depth) NODE *from, *to; @@ -338,9 +359,9 @@ find_cycle(from, to, longest_len, depth) * avoid infinite loops and ignore portions of the graph known * to be acyclic */ - if (from->n_flags & (NF_MARK|NF_ACYCLIC)) + if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC)) return (0); - from->n_flags = NF_MARK; + from->n_flags |= NF_MARK; for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) { cycle_buf[depth] = *np; @@ -352,9 +373,22 @@ find_cycle(from, to, longest_len, depth) longest_len * sizeof(NODE *)); } } else { + if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST)) + continue; len = find_cycle(*np, to, longest_len, depth + 1); + + if (debug) + (void)printf("%*s %s->%s %d\n", depth, "", + from->n_name, to->n_name, len); + + if (len == 0) + (*np)->n_flags |= NF_NODEST; + if (len > longest_len) longest_len = len; + + if (len > 0 && !longest) + break; } } from->n_flags &= ~NF_MARK; @@ -364,35 +398,6 @@ find_cycle(from, to, longest_len, depth) void usage() { - (void)fprintf(stderr, "usage: tsort [file]\n"); - exit(1); -} - -#if __STDC__ -#include -#else -#include -#endif - -void -#if __STDC__ -err(const char *fmt, ...) -#else -err(fmt, va_alist) - char *fmt; - va_dcl -#endif -{ - va_list ap; -#if __STDC__ - va_start(ap, fmt); -#else - va_start(ap); -#endif - (void)fprintf(stderr, "tsort: "); - (void)vfprintf(stderr, fmt, ap); - va_end(ap); - (void)fprintf(stderr, "\n"); + (void)fprintf(stderr, "usage: tsort [-l] [file]\n"); exit(1); - /* NOTREACHED */ } -- 2.20.1