It is impressive how long tsort currenly takes on gnu/usr.bin/gcc2/common
on the current NetBSD tree. Here's a fix that:

1. Adds a -l option to tsort to explicitly look for the longest cycle, 
   and by default stop after finding the first cycle.
2. Speeds up the current longest search, but flagging nodes that cannot
   reach the current destination of the cycle.

christos

Here's a shar file containing tsort.1 and tsort.c:

# This is a shell archive.  Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file".  Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
#	tsort.c
#	tsort.1
#
echo x - tsort.c
sed 's/^X//' >tsort.c << 'END-of-tsort.c'
X/*
X * Copyright (c) 1989, 1993
X *	The Regents of the University of California.  All rights reserved.
X *
X * This code is derived from software contributed to Berkeley by
X * Michael Rendell of Memorial University of Newfoundland.
X *
X * Redistribution and use in source and binary forms, with or without
X * modification, are permitted provided that the following conditions
X * are met:
X * 1. Redistributions of source code must retain the above copyright
X *    notice, this list of conditions and the following disclaimer.
X * 2. Redistributions in binary form must reproduce the above copyright
X *    notice, this list of conditions and the following disclaimer in the
X *    documentation and/or other materials provided with the distribution.
X * 3. All advertising materials mentioning features or use of this software
X *    must display the following acknowledgement:
X *	This product includes software developed by the University of
X *	California, Berkeley and its contributors.
X * 4. Neither the name of the University nor the names of its contributors
X *    may be used to endorse or promote products derived from this software
X *    without specific prior written permission.
X *
X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
X * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
X * SUCH DAMAGE.
X */
X
X#ifndef lint
Xstatic char copyright[] =
X"@(#) Copyright (c) 1989, 1993\n\
X	The Regents of the University of California.  All rights reserved.\n";
X#endif /* not lint */
X
X#ifndef lint
Xstatic char sccsid[] = "@(#)tsort.c	8.1 (Berkeley) 6/9/93";
X#endif /* not lint */
X
X#include <sys/types.h>
X#include <errno.h>
X#include <fcntl.h>
X#include <db.h>
X#include <stdio.h>
X#include <stdlib.h>
X#include <ctype.h>
X#include <string.h>
X
X/*
X *  Topological sort.  Input is a list of pairs of strings separated by
X *  white space (spaces, tabs, and/or newlines); strings are written to
X *  standard output in sorted order, one per line.
X *
X *  usage:
X *     tsort [-l] [inputfile]
X *  If no input file is specified, standard input is read.
X *
X *  Should be compatable with AT&T tsort HOWEVER the output is not identical
X *  (i.e. for most graphs there is more than one sorted order, and this tsort
X *  usually generates a different one then the AT&T tsort).  Also, cycle
X *  reporting seems to be more accurate in this version (the AT&T tsort
X *  sometimes says a node is in a cycle when it isn't).
X *
X *  Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
X */
X#define	HASHSIZE	53		/* doesn't need to be big */
X#define	NF_MARK		0x1		/* marker for cycle detection */
X#define	NF_ACYCLIC	0x2		/* this node is cycle free */
X#define	NF_NODEST	0x4		/* Unreachable */
X
X
Xtypedef struct node_str NODE;
X
Xstruct node_str {
X	NODE **n_prevp;			/* pointer to previous node's n_next */
X	NODE *n_next;			/* next node in graph */
X	NODE **n_arcs;			/* array of arcs to other nodes */
X	int n_narcs;			/* number of arcs in n_arcs[] */
X	int n_arcsize;			/* size of n_arcs[] array */
X	int n_refcnt;			/* # of arcs pointing to this node */
X	int n_flags;			/* NF_* */
X	char n_name[1];			/* name of this node */
X};
X
Xtypedef struct _buf {
X	char *b_buf;
X	int b_bsize;
X} BUF;
X
XDB *db;
XNODE *graph;
XNODE **cycle_buf;
XNODE **longest_cycle;
Xint longest = 0;
Xint debug = 0;
X
Xvoid	 add_arc __P((char *, char *));
Xvoid	 err __P((const char *, ...));
Xint	 find_cycle __P((NODE *, NODE *, int, int));
XNODE	*get_node __P((char *));
Xvoid	*grow_buf __P((void *, int));
Xvoid	 remove_node __P((NODE *));
Xvoid	 tsort __P((void));
Xvoid	 usage __P((void));
X
Xint
Xmain(argc, argv)
X	int argc;
X	char *argv[];
X{
X	register BUF *b;
X	register int c, n;
X	FILE *fp;
X	int bsize, ch, nused;
X	BUF bufs[2];
X
X	while ((ch = getopt(argc, argv, "dl")) != EOF)
X		switch(ch) {
X		case 'd':
X		    debug = 1;
X		    break;
X
X		case 'l':
X		    longest = 1;
X		    break;
X
X		case '?':
X		default:
X			usage();
X		}
X	argc -= optind;
X	argv += optind;
X
X	switch(argc) {
X	case 0:
X		fp = stdin;
X		break;
X	case 1:
X		if ((fp = fopen(*argv, "r")) == NULL)
X			err("%s: %s", *argv, strerror(errno));
X		break;
X	default:
X		usage();
X	}
X
X	for (b = bufs, n = 2; --n >= 0; b++)
X		b->b_buf = grow_buf(NULL, b->b_bsize = 1024);
X
X	/* parse input and build the graph */
X	for (n = 0, c = getc(fp);;) {
X		while (c != EOF && isspace(c))
X			c = getc(fp);
X		if (c == EOF)
X			break;
X
X		nused = 0;
X		b = &bufs[n];
X		bsize = b->b_bsize;
X		do {
X			b->b_buf[nused++] = c;
X			if (nused == bsize)
X				b->b_buf = grow_buf(b->b_buf, bsize *= 2);
X			c = getc(fp);
X		} while (c != EOF && !isspace(c));
X
X		b->b_buf[nused] = '\0';
X		b->b_bsize = bsize;
X		if (n)
X			add_arc(bufs[0].b_buf, bufs[1].b_buf);
X		n = !n;
X	}
X	(void)fclose(fp);
X	if (n)
X		err("odd data count");
X
X	/* do the sort */
X	tsort();
X	exit(0);
X}
X
X/* double the size of oldbuf and return a pointer to the new buffer. */
Xvoid *
Xgrow_buf(bp, size)
X	void *bp;
X	int size;
X{
X	if ((bp = realloc(bp, (u_int)size)) == NULL)
X		err("%s", strerror(errno));
X	return (bp);
X}
X
X/*
X * add an arc from node s1 to node s2 in the graph.  If s1 or s2 are not in
X * the graph, then add them.
X */
Xvoid
Xadd_arc(s1, s2)
X	char *s1, *s2;
X{
X	register NODE *n1;
X	NODE *n2;
X	int bsize, i;
X
X	n1 = get_node(s1);
X
X	if (!strcmp(s1, s2))
X		return;
X
X	n2 = get_node(s2);
X
X	/*
X	 * Check if this arc is already here.
X	 */
X	for (i = 0; i < n1->n_narcs; i++)
X		if (n1->n_arcs[i] == n2)
X			return;
X	/*
X	 * Add it.
X	 */
X	if (n1->n_narcs == n1->n_arcsize) {
X		if (!n1->n_arcsize)
X			n1->n_arcsize = 10;
X		bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
X		n1->n_arcs = grow_buf(n1->n_arcs, bsize);
X		n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
X	}
X	n1->n_arcs[n1->n_narcs++] = n2;
X	++n2->n_refcnt;
X}
X
X/* Find a node in the graph (insert if not found) and return a pointer to it. */
XNODE *
Xget_node(name)
X	char *name;
X{
X	DBT data, key;
X	NODE *n;
X
X	if (db == NULL &&
X	    (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL)
X		err("db: open: %s", name, strerror(errno));
X
X	key.data = name;
X	key.size = strlen(name) + 1;
X
X	switch((*db->get)(db, &key, &data, 0)) {
X	case 0:
X		bcopy(data.data, &n, sizeof(n));
X		return (n);
X	case 1:
X		break;
X	default:
X	case -1:
X		err("db: get %s: %s", name, strerror(errno));
X	}
X
X	if ((n = malloc(sizeof(NODE) + key.size)) == NULL)
X		err("%s", strerror(errno));
X
X	n->n_narcs = 0;
X	n->n_arcsize = 0;
X	n->n_arcs = NULL;
X	n->n_refcnt = 0;
X	n->n_flags = 0;
X	bcopy(name, n->n_name, key.size);
X
X	/* Add to linked list. */
X	if (n->n_next = graph)
X		graph->n_prevp = &n->n_next;
X	n->n_prevp = &graph;
X	graph = n;
X
X	/* Add to hash table. */
X	data.data = &n;
X	data.size = sizeof(n);
X	if ((*db->put)(db, &key, &data, 0))
X		err("db: put %s: %s", name, strerror(errno));
X	return (n);
X}
X
X
X/*
X * Clear the NODEST flag from all nodes.
X */
Xvoid
Xclear_cycle()
X{
X	NODE *n;
X
X	for (n = graph; n; n = n->n_next)
X		n->n_flags &= ~NF_NODEST;
X}
X
X/* do topological sort on graph */
Xvoid
Xtsort()
X{
X	register NODE *n, *next;
X	register int cnt;
X
X	while (graph) {
X		/*
X		 * Keep getting rid of simple cases until there are none left,
X		 * if there are any nodes still in the graph, then there is
X		 * a cycle in it.
X		 */
X		do {
X			for (cnt = 0, n = graph; n; n = next) {
X				next = n->n_next;
X				if (n->n_refcnt == 0) {
X					remove_node(n);
X					++cnt;
X				}
X			}
X		} while (graph && cnt);
X
X		if (!graph)
X			break;
X
X		if (!cycle_buf) {
X			/*
X			 * Allocate space for two cycle logs - one to be used
X			 * as scratch space, the other to save the longest
X			 * cycle.
X			 */
X			for (cnt = 0, n = graph; n; n = n->n_next)
X				++cnt;
X			cycle_buf = malloc((u_int)sizeof(NODE *) * cnt);
X			longest_cycle = malloc((u_int)sizeof(NODE *) * cnt);
X			if (cycle_buf == NULL || longest_cycle == NULL)
X				err("%s", strerror(errno));
X		}
X		for (n = graph; n; n = n->n_next)
X			if (!(n->n_flags & NF_ACYCLIC)) {
X				if (cnt = find_cycle(n, n, 0, 0)) {
X					register int i;
X
X					(void)fprintf(stderr,
X					    "tsort: cycle in data\n");
X					for (i = 0; i < cnt; i++)
X						(void)fprintf(stderr,
X				"tsort: %s\n", longest_cycle[i]->n_name);
X					remove_node(n);
X					clear_cycle();
X					break;
X				} else {
X					/* to avoid further checks */
X					n->n_flags  |= NF_ACYCLIC;
X					clear_cycle();
X				}
X			}
X
X		if (!n)
X			err("internal error -- could not find cycle");
X	}
X}
X
X/* print node and remove from graph (does not actually free node) */
Xvoid
Xremove_node(n)
X	register NODE *n;
X{
X	register NODE **np;
X	register int i;
X
X	(void)printf("%s\n", n->n_name);
X	for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
X		--(*np)->n_refcnt;
X	n->n_narcs = 0;
X	*n->n_prevp = n->n_next;
X	if (n->n_next)
X		n->n_next->n_prevp = n->n_prevp;
X}
X
X
X/* look for the longest? cycle from node from to node to. */
Xint
Xfind_cycle(from, to, longest_len, depth)
X	NODE *from, *to;
X	int depth, longest_len;
X{
X	register NODE **np;
X	register int i, len;
X
X	/*
X	 * avoid infinite loops and ignore portions of the graph known
X	 * to be acyclic
X	 */
X	if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC))
X		return (0);
X	from->n_flags |= NF_MARK;
X
X	for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
X		cycle_buf[depth] = *np;
X		if (*np == to) {
X			if (depth + 1 > longest_len) {
X				longest_len = depth + 1;
X				(void)memcpy((char *)longest_cycle,
X				    (char *)cycle_buf,
X				    longest_len * sizeof(NODE *));
X			}
X		} else {
X			if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST))
X				continue;
X			len = find_cycle(*np, to, longest_len, depth + 1);
X
X			if (debug)
X			    printf("%*s %s->%s %d\n", depth, "",
X			    	   from->n_name, to->n_name, len);
X
X			if (len == 0)
X			    (*np)->n_flags |= NF_NODEST;
X
X			if (len > longest_len)
X				longest_len = len;
X
X			if (len > 0 && !longest)
X				break;
X		}
X	}
X	from->n_flags &= ~NF_MARK;
X	return (longest_len);
X}
X
Xvoid
Xusage()
X{
X	(void)fprintf(stderr, "usage: tsort [-l] [file]\n");
X	exit(1);
X}
X
X#if __STDC__
X#include <stdarg.h>
X#else
X#include <varargs.h>
X#endif
X
Xvoid
X#if __STDC__
Xerr(const char *fmt, ...)
X#else
Xerr(fmt, va_alist)
X	char *fmt;
X        va_dcl
X#endif
X{
X	va_list ap;
X#if __STDC__
X	va_start(ap, fmt);
X#else
X	va_start(ap);
X#endif
X	(void)fprintf(stderr, "tsort: ");
X	(void)vfprintf(stderr, fmt, ap);
X	va_end(ap);
X	(void)fprintf(stderr, "\n");
X	exit(1);
X	/* NOTREACHED */
X}
END-of-tsort.c
echo x - tsort.1
sed 's/^X//' >tsort.1 << 'END-of-tsort.1'
X.\" Copyright (c) 1990, 1993
X.\"	The Regents of the University of California.  All rights reserved.
X.\"
X.\" This manual is derived from one contributed to Berkeley by
X.\" Michael Rendell of Memorial University of Newfoundland.
X.\" %sccs.include.redist.roff%
X.\"
X.\"     %W% (Berkeley) %G%
X.\"
X.Dd %Q%
X.Dt TSORT 1
X.Os
X.Sh NAME
X.Nm tsort
X.Nd topological sort of a directed graph
X.Sh SYNOPSIS
X.Nm tsort
X.Op Fl l
X.Op Ar file
X.Sh DESCRIPTION
X.Nm Tsort
Xtakes a list of pairs of node names representing directed arcs in
Xa graph and prints the nodes in topological order on standard output.
XInput is taken from the named
X.Ar file ,
Xor from standard input if no file
Xis given.
X.Pp
XNode names in the input are separated by white space and there must be an
Xeven number of nodes.
X.Pp
XPresence of a node in a graph can be represented by an arc from the node
Xto itself.
XThis is useful when a node is not connected to any other nodes.
X.Pp
XIf the graph contains a cycle (and therefore cannot be properly sorted),
Xone of the arcs in the cycle is ignored and the sort continues.
XCycles are reported on standard error.
X.Sh OPTIONS
X.Bl -tag -width indent
XThe available options are as follows:
X.It Fl l 
XSearch for the longest cycle. Can take a long time.
X.Sh SEE ALSO
X.Xr ar 1
X.Sh HISTORY
XA
X.Nm
Xcommand appeared in
X.At v7 .
XThis
X.Nm tsort
Xcommand and manual page are derived from sources contributed to Berkeley by
XMichael Rendell of Memorial University of Newfoundland.
END-of-tsort.1
exit


------------------------------------------------------------------------------