Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/trunk]: src/usr.bin/tsort - document -d



details:   https://anonhg.NetBSD.org/src/rev/df9c277bd357
branches:  trunk
changeset: 974826:df9c277bd357
user:      christos <christos%NetBSD.org@localhost>
date:      Wed Aug 12 23:23:04 2020 +0000

description:
- document -d
- add -r (reverse)
- const, size_t, emalloc, EXIT_FOO

diffstat:

 usr.bin/tsort/Makefile |    5 +-
 usr.bin/tsort/tsort.1  |   10 +++-
 usr.bin/tsort/tsort.c  |  120 ++++++++++++++++++++++--------------------------
 3 files changed, 68 insertions(+), 67 deletions(-)

diffs (truncated from 382 to 300 lines):

diff -r bc825e6c9031 -r df9c277bd357 usr.bin/tsort/Makefile
--- a/usr.bin/tsort/Makefile    Wed Aug 12 19:36:14 2020 +0000
+++ b/usr.bin/tsort/Makefile    Wed Aug 12 23:23:04 2020 +0000
@@ -1,6 +1,9 @@
-#      $NetBSD: Makefile,v 1.7 2009/04/14 22:15:27 lukem Exp $
+#      $NetBSD: Makefile,v 1.8 2020/08/12 23:23:04 christos Exp $
 #      @(#)Makefile    8.1 (Berkeley) 6/9/93
 
+WARNS= 6
 PROG=  tsort
+LDADD+= -lutil
+DPADD+= ${LIBUTIL}
 
 .include <bsd.prog.mk>
diff -r bc825e6c9031 -r df9c277bd357 usr.bin/tsort/tsort.1
--- a/usr.bin/tsort/tsort.1     Wed Aug 12 19:36:14 2020 +0000
+++ b/usr.bin/tsort/tsort.1     Wed Aug 12 23:23:04 2020 +0000
@@ -1,4 +1,4 @@
-.\"    $NetBSD: tsort.1,v 1.10 2003/08/07 11:16:50 agc Exp $
+.\"    $NetBSD: tsort.1,v 1.11 2020/08/12 23:23:04 christos Exp $
 .\"
 .\" Copyright (c) 1990, 1993, 1994
 .\"    The Regents of the University of California.  All rights reserved.
@@ -32,7 +32,7 @@
 .\"
 .\"     @(#)tsort.1    8.3 (Berkeley) 4/1/94
 .\"
-.Dd April 1, 1994
+.Dd August 12, 2020
 .Dt TSORT 1
 .Os
 .Sh NAME
@@ -40,8 +40,10 @@
 .Nd topological sort of a directed graph
 .Sh SYNOPSIS
 .Nm
+.Op Fl d
 .Op Fl l
 .Op Fl q
+.Op Fl r
 .Op Ar file
 .Sh DESCRIPTION
 .Nm
@@ -65,6 +67,8 @@
 .Pp
 The options are as follows:
 .Bl -tag -width Ds
+.It Fl d
+Print debugging information.
 .It Fl l
 Search for and display the longest cycle.
 Can take a very long time.
@@ -73,6 +77,8 @@
 This is primarily
 intended for building libraries, where optimal ordering is not critical,
 and cycles occur often.
+.It Fl r
+Reverse the sort.
 .El
 .Sh SEE ALSO
 .Xr ar 1
diff -r bc825e6c9031 -r df9c277bd357 usr.bin/tsort/tsort.c
--- a/usr.bin/tsort/tsort.c     Wed Aug 12 19:36:14 2020 +0000
+++ b/usr.bin/tsort/tsort.c     Wed Aug 12 23:23:04 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: tsort.c,v 1.23 2011/09/06 18:34:37 joerg Exp $ */
+/*     $NetBSD: tsort.c,v 1.24 2020/08/12 23:23:04 christos Exp $      */
 
 /*
  * Copyright (c) 1989, 1993, 1994
@@ -43,7 +43,7 @@
 #if 0
 static char sccsid[] = "@(#)tsort.c    8.3 (Berkeley) 5/4/95";
 #endif
-__RCSID("$NetBSD: tsort.c,v 1.23 2011/09/06 18:34:37 joerg Exp $");
+__RCSID("$NetBSD: tsort.c,v 1.24 2020/08/12 23:23:04 christos Exp $");
 #endif /* not lint */
 
 #include <sys/types.h>
@@ -56,6 +56,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <util.h>
 
 /*
  *  Topological sort.  Input is a list of pairs of strings separated by
@@ -85,27 +86,26 @@
        NODE **n_prevp;                 /* pointer to previous node's n_next */
        NODE *n_next;                   /* next node in graph */
        NODE **n_arcs;                  /* array of arcs to other nodes */
-       int n_narcs;                    /* number of arcs in n_arcs[] */
-       int n_arcsize;                  /* size of n_arcs[] array */
-       int n_refcnt;                   /* # of arcs pointing to this node */
+       size_t n_narcs;                 /* number of arcs in n_arcs[] */
+       size_t n_arcsize;               /* size of n_arcs[] array */
+       size_t n_refcnt;                /* # of arcs pointing to this node */
        int n_flags;                    /* NF_* */
        char n_name[1];                 /* name of this node */
 };
 
 typedef struct _buf {
        char *b_buf;
-       int b_bsize;
+       size_t b_bsize;
 } BUF;
 
 static DB *db;
 static NODE *graph, **cycle_buf, **longest_cycle;
-static int debug, longest, quiet;
+static int debug, longest, quiet, reverse;
 
-static void     add_arc(char *, char *);
+static void     add_arc(const char *, const char *);
 static void     clear_cycle(void);
-static int      find_cycle(NODE *, NODE *, int, int);
-static NODE    *get_node(char *);
-static void    *grow_buf(void *, int);
+static size_t   find_cycle(NODE *, NODE *, size_t, size_t);
+static NODE    *get_node(const char *);
 static void     remove_node(NODE *);
 static void     tsort(void);
 __dead static void      usage(void);
@@ -114,15 +114,15 @@
 main(int argc, char *argv[])
 {
        BUF *b;
-       int c, n;
+       int c, n, ch;
        FILE *fp;
-       int bsize, ch, nused;
+       size_t bsize, nused;
        BUF bufs[2];
 
        setprogname(argv[0]);
 
        fp = NULL;
-       while ((ch = getopt(argc, argv, "dlq")) != -1)
+       while ((ch = getopt(argc, argv, "dlqr")) != -1)
                switch (ch) {
                case 'd':
                        debug = 1;
@@ -133,6 +133,9 @@
                case 'q':
                        quiet = 1;
                        break;
+               case 'r':
+                       reverse = 1;
+                       break;
                case '?':
                default:
                        usage();
@@ -146,14 +149,14 @@
                break;
        case 1:
                if ((fp = fopen(*argv, "r")) == NULL)
-                       err(1, "%s", *argv);
+                       err(EXIT_FAILURE, "%s", *argv);
                break;
        default:
                usage();
        }
 
-       for (b = bufs, n = 2; --n >= 0; b++)
-               b->b_buf = grow_buf(NULL, b->b_bsize = 1024);
+       for (b = bufs, n = 2; n-- > 0; b++)
+               b->b_buf = erealloc(NULL, b->b_bsize = 1024);
 
        /* parse input and build the graph */
        for (n = 0, c = getc(fp);;) {
@@ -166,37 +169,29 @@
                b = &bufs[n];
                bsize = b->b_bsize;
                do {
-                       b->b_buf[nused++] = c;
+                       b->b_buf[nused++] = (char)c;
                        if (nused == bsize)
-                               b->b_buf = grow_buf(b->b_buf, bsize *= 2);
+                               b->b_buf = erealloc(b->b_buf, bsize *= 2);
                        c = getc(fp);
                } while (c != EOF && !isspace(c));
 
                b->b_buf[nused] = '\0';
                b->b_bsize = bsize;
-               if (n)
-                       add_arc(bufs[0].b_buf, bufs[1].b_buf);
+               if (n) {
+                       if (reverse)
+                               add_arc(bufs[1].b_buf, bufs[0].b_buf);
+                       else
+                               add_arc(bufs[0].b_buf, bufs[1].b_buf);
+               }
                n = !n;
        }
        (void)fclose(fp);
        if (n)
-               errx(1, "odd data count");
+               errx(EXIT_FAILURE, "odd data count");
 
        /* do the sort */
        tsort();
-       return(0);
-}
-
-/* double the size of oldbuf and return a pointer to the new buffer. */
-static void *
-grow_buf(void *bp, int size)
-{
-       void *n;
-
-       if ((n = realloc(bp, (u_int)size)) == NULL)
-               err(1, "realloc");
-       bp = n;
-       return (bp);
+       return EXIT_SUCCESS;
 }
 
 /*
@@ -204,15 +199,15 @@
  * the graph, then add them.
  */
 static void
-add_arc(char *s1, char *s2)
+add_arc(const char *s1, const char *s2)
 {
        NODE *n1;
        NODE *n2;
-       int bsize, i;
+       size_t bsize, i;
 
        n1 = get_node(s1);
 
-       if (!strcmp(s1, s2))
+       if (strcmp(s1, s2) == 0)
                return;
 
        n2 = get_node(s2);
@@ -230,7 +225,7 @@
                if (!n1->n_arcsize)
                        n1->n_arcsize = 10;
                bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
-               n1->n_arcs = grow_buf(n1->n_arcs, bsize);
+               n1->n_arcs = erealloc(n1->n_arcs, bsize);
                n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
        }
        n1->n_arcs[n1->n_narcs++] = n2;
@@ -239,31 +234,30 @@
 
 /* Find a node in the graph (insert if not found) and return a pointer to it. */
 static NODE *
-get_node(char *name)
+get_node(const char *name)
 {
        DBT data, key;
        NODE *n;
 
        if (db == NULL &&
            (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL)
-               err(1, "db: %s", name);
+               err(EXIT_FAILURE, "db: %s", name);
 
-       key.data = name;
+       key.data = __UNCONST(name);
        key.size = strlen(name) + 1;
 
        switch ((*db->get)(db, &key, &data, 0)) {
        case 0:
                (void)memmove(&n, data.data, sizeof(n));
-               return (n);
+               return n;
        case 1:
                break;
        default:
        case -1:
-               err(1, "db: %s", name);
+               err(EXIT_FAILURE, "db: %s", name);
        }
 
-       if ((n = malloc(sizeof(NODE) + key.size)) == NULL)
-               err(1, "malloc");
+       n = emalloc(sizeof(NODE) + key.size);
 
        n->n_narcs = 0;
        n->n_arcsize = 0;
@@ -282,8 +276,8 @@
        data.data = &n;
        data.size = sizeof(n);
        if ((*db->put)(db, &key, &data, 0))
-               err(1, "db: %s", name);
-       return (n);
+               err(EXIT_FAILURE, "db: %s", name);
+       return n;
 }
 
 
@@ -304,7 +298,7 @@
 tsort(void)
 {
        NODE *n, *next;
-       int cnt, i;



Home | Main Index | Thread Index | Old Index