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

diff --git a/usr/src/usr.bin/tsort/tsort.1 b/usr/src/usr.bin/tsort/tsort.1
index e0e1dc7..6958891 100644 (file)
--- 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.
 .\"    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%
 .\"
 .\" %sccs.include.redist.roff%
 .\"

-.\"     @(#)tsort.1    8.1 (Berkeley) %G%
+.\"     @(#)tsort.1    8.2 (Berkeley) %G%

 .\"
 .Dd 
 .Dt TSORT 1
 .\"
 .Dd 
 .Dt TSORT 1


@@ -15,6 +16,7 @@
 .Nd topological sort of a directed graph
 .Sh SYNOPSIS
 .Nm tsort
 .Nd topological sort of a directed graph
 .Sh SYNOPSIS
 .Nm tsort

+.Op Fl l

 .Op Ar file
 .Sh DESCRIPTION
 .Nm Tsort
 .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.
 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
 .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 eb0c324..16d2ae2 100644 (file)
--- 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
  *     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[] =
 
 #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
        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>
 #endif /* not lint */
 
 #include <sys/types.h>

+
+#include <ctype.h>
+#include <db.h>
+#include <err.h>

 #include <errno.h>
 #include <fcntl.h>
 #include <errno.h>
 #include <fcntl.h>

-#include <db.h>

 #include <stdio.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <stdlib.h>

-#include <ctype.h>

 #include <string.h>
 
 /*
 #include <string.h>
 
 /*


@@ -33,7 +35,7 @@ static char sccsid[] = "@(#)tsort.c   8.1 (Berkeley) %G%";
  *  standard output in sorted order, one per line.
  *
  *  usage:
  *  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
  *  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        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;
 
 
 typedef struct node_str NODE;
 


@@ -67,12 +71,10 @@ typedef struct _buf {
 } BUF;
 
 DB *db;
 } 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    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     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];
 
        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();
                case '?':
                default:
                        usage();


@@ -100,13 +108,13 @@ main(argc, argv)
        argc -= optind;
        argv += optind;
 
        argc -= optind;
        argv += optind;
 

-       switch(argc) {
+       switch (argc) {

        case 0:
                fp = stdin;
                break;
        case 1:
                if ((fp = fopen(*argv, "r")) == NULL)
        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();
                break;
        default:
                usage();


@@ -140,7 +148,7 @@ main(argc, argv)
        }
        (void)fclose(fp);
        if (n)
        }
        (void)fclose(fp);
        if (n)

-               err("odd data count");
+               errx(1, "odd data count");

 
        /* do the sort */
        tsort();
 
        /* do the sort */
        tsort();


@@ -154,7 +162,7 @@ grow_buf(bp, size)
        int size;
 {
        if ((bp = realloc(bp, (u_int)size)) == NULL)
        int size;
 {
        if ((bp = realloc(bp, (u_int)size)) == NULL)

-               err("%s", strerror(errno));
+               err(1, NULL);

        return (bp);
 }
 
        return (bp);
 }
 


@@ -207,12 +215,12 @@ get_node(name)
 
        if (db == NULL &&
            (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL)
 
        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;
 
 
        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);
        case 0:
                bcopy(data.data, &n, sizeof(n));
                return (n);


@@ -220,11 +228,11 @@ get_node(name)
                break;
        default:
        case -1:
                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)
        }
 
        if ((n = malloc(sizeof(NODE) + key.size)) == NULL)

-               err("%s", strerror(errno));
+               err(1, NULL);

 
        n->n_narcs = 0;
        n->n_arcsize = 0;
 
        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. */
        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;
                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))
        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);
 }
 
        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;
 /* 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 {
                /*
                 * 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;
                                }
                        }
                                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) {
                        break;
 
                if (!cycle_buf) {


@@ -279,32 +300,31 @@ tsort()
                         * as scratch space, the other to save the longest
                         * cycle.
                         */
                         * 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)
                                ++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)) {
                                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++)
                                        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);
                                        remove_node(n);

+                                       clear_cycle();

                                        break;
                                        break;

-                               } else
+                               } else {

                                        /* to avoid further checks */
                                        /* 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;
 }
 
                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;
 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
         */
         * 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);
                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;
 
        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 {
                                    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);
                        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 > longest_len)
                                longest_len = len;

+
+                       if (len > 0 && !longest)
+                               break;

                }
        }
        from->n_flags &= ~NF_MARK;
                }
        }
        from->n_flags &= ~NF_MARK;


@@ -364,35 +398,6 @@ find_cycle(from, to, longest_len, depth)
 void
 usage()
 {
 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);
        exit(1);

-       /* NOTREACHED */

 }
 }