/*
- * 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
#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 <sys/types.h>
+
+#include <ctype.h>
+#include <db.h>
+#include <err.h>
#include <errno.h>
#include <fcntl.h>
-#include <db.h>
#include <stdio.h>
#include <stdlib.h>
-#include <ctype.h>
#include <string.h>
/*
* 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
#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;
} 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));
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();
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();
}
(void)fclose(fp);
if (n)
- err("odd data count");
+ errx(1, "odd data count");
/* do the sort */
tsort();
int size;
{
if ((bp = realloc(bp, (u_int)size)) == NULL)
- err("%s", strerror(errno));
+ err(1, NULL);
return (bp);
}
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);
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;
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;
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) {
* 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");
}
}
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;
* 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;
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;
void
usage()
{
- (void)fprintf(stderr, "usage: tsort [file]\n");
- exit(1);
-}
-
-#if __STDC__
-#include <stdarg.h>
-#else
-#include <varargs.h>
-#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 */
}