CVS commit: src/usr.bin/tsort
Module Name:src Committed By: dbj Date: Sat Feb 6 16:02:16 UTC 2021 Modified Files: src/usr.bin/tsort: tsort.c Log Message: tsort: fix typo in comment To generate a diff of this commit: cvs rdiff -u -r1.25 -r1.26 src/usr.bin/tsort/tsort.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files. Modified files: Index: src/usr.bin/tsort/tsort.c diff -u src/usr.bin/tsort/tsort.c:1.25 src/usr.bin/tsort/tsort.c:1.26 --- src/usr.bin/tsort/tsort.c:1.25 Mon Aug 17 16:26:03 2020 +++ src/usr.bin/tsort/tsort.c Sat Feb 6 16:02:16 2021 @@ -1,4 +1,4 @@ -/* $NetBSD: tsort.c,v 1.25 2020/08/17 16:26:03 christos Exp $ */ +/* $NetBSD: tsort.c,v 1.26 2021/02/06 16:02:16 dbj Exp $ */ /* * Copyright (c) 1989, 1993, 1994 @@ -43,7 +43,7 @@ __COPYRIGHT("@(#) Copyright (c) 1989, 19 #if 0 static char sccsid[] = "@(#)tsort.c 8.3 (Berkeley) 5/4/95"; #endif -__RCSID("$NetBSD: tsort.c,v 1.25 2020/08/17 16:26:03 christos Exp $"); +__RCSID("$NetBSD: tsort.c,v 1.26 2021/02/06 16:02:16 dbj Exp $"); #endif /* not lint */ #include @@ -71,7 +71,7 @@ __RCSID("$NetBSD: tsort.c,v 1.25 2020/08 * * Should be compatible with AT tsort HOWEVER the output is not identical * (i.e. for most graphs there is more than one sorted order, and this tsort - * usually generates a different one then the AT tsort). Also, cycle + * usually generates a different one than the AT tsort). Also, cycle * reporting seems to be more accurate in this version (the AT tsort * sometimes says a node is in a cycle when it isn't). *
CVS commit: src/usr.bin/tsort
Module Name:src Committed By: christos Date: Mon Aug 17 16:26:03 UTC 2020 Modified Files: src/usr.bin/tsort: Makefile tsort.c Log Message: be host friendly To generate a diff of this commit: cvs rdiff -u -r1.8 -r1.9 src/usr.bin/tsort/Makefile cvs rdiff -u -r1.24 -r1.25 src/usr.bin/tsort/tsort.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files. Modified files: Index: src/usr.bin/tsort/Makefile diff -u src/usr.bin/tsort/Makefile:1.8 src/usr.bin/tsort/Makefile:1.9 --- src/usr.bin/tsort/Makefile:1.8 Wed Aug 12 19:23:04 2020 +++ src/usr.bin/tsort/Makefile Mon Aug 17 12:26:03 2020 @@ -1,9 +1,12 @@ -# $NetBSD: Makefile,v 1.8 2020/08/12 23:23:04 christos Exp $ +# $NetBSD: Makefile,v 1.9 2020/08/17 16:26:03 christos Exp $ # @(#)Makefile 8.1 (Berkeley) 6/9/93 +.include WARNS= 6 PROG= tsort +.if !defined(HOSTPROGNAME) LDADD+= -lutil DPADD+= ${LIBUTIL} +.endif .include Index: src/usr.bin/tsort/tsort.c diff -u src/usr.bin/tsort/tsort.c:1.24 src/usr.bin/tsort/tsort.c:1.25 --- src/usr.bin/tsort/tsort.c:1.24 Wed Aug 12 19:23:04 2020 +++ src/usr.bin/tsort/tsort.c Mon Aug 17 12:26:03 2020 @@ -1,4 +1,4 @@ -/* $NetBSD: tsort.c,v 1.24 2020/08/12 23:23:04 christos Exp $ */ +/* $NetBSD: tsort.c,v 1.25 2020/08/17 16:26:03 christos Exp $ */ /* * Copyright (c) 1989, 1993, 1994 @@ -43,7 +43,7 @@ __COPYRIGHT("@(#) Copyright (c) 1989, 19 #if 0 static char sccsid[] = "@(#)tsort.c 8.3 (Berkeley) 5/4/95"; #endif -__RCSID("$NetBSD: tsort.c,v 1.24 2020/08/12 23:23:04 christos Exp $"); +__RCSID("$NetBSD: tsort.c,v 1.25 2020/08/17 16:26:03 christos Exp $"); #endif /* not lint */ #include @@ -56,7 +56,9 @@ __RCSID("$NetBSD: tsort.c,v 1.24 2020/08 #include #include #include +#if !HAVE_NBTOOL_CONFIG_H #include +#endif /* * Topological sort. Input is a list of pairs of strings separated by
CVS commit: src/usr.bin/tsort
Module Name:src Committed By: christos Date: Wed Aug 12 23:23:04 UTC 2020 Modified Files: src/usr.bin/tsort: Makefile tsort.1 tsort.c Log Message: - document -d - add -r (reverse) - const, size_t, emalloc, EXIT_FOO To generate a diff of this commit: cvs rdiff -u -r1.7 -r1.8 src/usr.bin/tsort/Makefile cvs rdiff -u -r1.10 -r1.11 src/usr.bin/tsort/tsort.1 cvs rdiff -u -r1.23 -r1.24 src/usr.bin/tsort/tsort.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files. Modified files: Index: src/usr.bin/tsort/Makefile diff -u src/usr.bin/tsort/Makefile:1.7 src/usr.bin/tsort/Makefile:1.8 --- src/usr.bin/tsort/Makefile:1.7 Tue Apr 14 18:15:27 2009 +++ src/usr.bin/tsort/Makefile Wed Aug 12 19:23:04 2020 @@ -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 Index: src/usr.bin/tsort/tsort.1 diff -u src/usr.bin/tsort/tsort.1:1.10 src/usr.bin/tsort/tsort.1:1.11 --- src/usr.bin/tsort/tsort.1:1.10 Thu Aug 7 07:16:50 2003 +++ src/usr.bin/tsort/tsort.1 Wed Aug 12 19:23:04 2020 @@ -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 @@ Cycles are reported on standard error. .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 @@ Do not display informational messages ab 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 Index: src/usr.bin/tsort/tsort.c diff -u src/usr.bin/tsort/tsort.c:1.23 src/usr.bin/tsort/tsort.c:1.24 --- src/usr.bin/tsort/tsort.c:1.23 Tue Sep 6 14:34:37 2011 +++ src/usr.bin/tsort/tsort.c Wed Aug 12 19:23:04 2020 @@ -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 @@ __COPYRIGHT("@(#) Copyright (c) 1989, 19 #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 @@ -56,6 +56,7 @@ __RCSID("$NetBSD: tsort.c,v 1.23 2011/09 #include #include #include +#include /* * Topological sort. Input is a list of pairs of strings separated by @@ -85,27 +86,26 @@ struct node_str { 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 @@ int 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 @@ main(int argc, char *argv[]) case 'q': quiet = 1; break; + case 'r': + reverse = 1; + break; case '?': default: usage(); @@ -146,14 +149,14 @@ main(int argc, char *argv[])
CVS commit: src/usr.bin/tsort
Module Name:src Committed By: joerg Date: Tue Sep 6 18:34:38 UTC 2011 Modified Files: src/usr.bin/tsort: tsort.c Log Message: ANSIfy, static + __dead To generate a diff of this commit: cvs rdiff -u -r1.22 -r1.23 src/usr.bin/tsort/tsort.c Please note that diffs are not public domain; they are subject to the copyright notices on the relevant files. Modified files: Index: src/usr.bin/tsort/tsort.c diff -u src/usr.bin/tsort/tsort.c:1.22 src/usr.bin/tsort/tsort.c:1.23 --- src/usr.bin/tsort/tsort.c:1.22 Mon Jul 21 14:19:27 2008 +++ src/usr.bin/tsort/tsort.c Tue Sep 6 18:34:37 2011 @@ -1,4 +1,4 @@ -/* $NetBSD: tsort.c,v 1.22 2008/07/21 14:19:27 lukem Exp $ */ +/* $NetBSD: tsort.c,v 1.23 2011/09/06 18:34:37 joerg 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.22 2008/07/21 14:19:27 lukem Exp $); +__RCSID($NetBSD: tsort.c,v 1.23 2011/09/06 18:34:37 joerg Exp $); #endif /* not lint */ #include sys/types.h @@ -97,24 +97,21 @@ int b_bsize; } BUF; -DB *db; -NODE *graph, **cycle_buf, **longest_cycle; -int debug, longest, quiet; - -void add_arc __P((char *, char *)); -void clear_cycle __P((void)); -int find_cycle __P((NODE *, NODE *, int, int)); -NODE *get_node __P((char *)); -void *grow_buf __P((void *, int)); -int main __P((int, char **)); -void remove_node __P((NODE *)); -void tsort __P((void)); -void usage __P((void)); +static DB *db; +static NODE *graph, **cycle_buf, **longest_cycle; +static int debug, longest, quiet; + +static void add_arc(char *, 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 void remove_node(NODE *); +static void tsort(void); +__dead static void usage(void); int -main(argc, argv) - int argc; - char *argv[]; +main(int argc, char *argv[]) { BUF *b; int c, n; @@ -191,10 +188,8 @@ } /* double the size of oldbuf and return a pointer to the new buffer. */ -void * -grow_buf(bp, size) - void *bp; - int size; +static void * +grow_buf(void *bp, int size) { void *n; @@ -208,9 +203,8 @@ * add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in * the graph, then add them. */ -void -add_arc(s1, s2) - char *s1, *s2; +static void +add_arc(char *s1, char *s2) { NODE *n1; NODE *n2; @@ -244,9 +238,8 @@ } /* Find a node in the graph (insert if not found) and return a pointer to it. */ -NODE * -get_node(name) - char *name; +static NODE * +get_node(char *name) { DBT data, key; NODE *n; @@ -297,8 +290,8 @@ /* * Clear the NODEST flag from all nodes. */ -void -clear_cycle() +static void +clear_cycle(void) { NODE *n; @@ -307,8 +300,8 @@ } /* do topological sort on graph */ -void -tsort() +static void +tsort(void) { NODE *n, *next; int cnt, i; @@ -370,9 +363,8 @@ } /* print node and remove from graph (does not actually free node) */ -void -remove_node(n) - NODE *n; +static void +remove_node(NODE *n) { NODE **np; int i; @@ -388,10 +380,8 @@ /* look for the longest? cycle from node from to node to. */ -int -find_cycle(from, to, longest_len, depth) - NODE *from, *to; - int depth, longest_len; +static int +find_cycle(NODE *from, NODE *to, int longest_len, int depth) { NODE **np; int i, len; @@ -435,8 +425,8 @@ return (longest_len); } -void -usage() +static void +usage(void) { (void)fprintf(stderr, usage: tsort [-lq] [file]\n); exit(1);