Home | History | Annotate | Line # | Download | only in tsort
tsort.c revision 1.7 
      1 /*
      2  * Copyright (c) 1989, 1993
      3  *	The Regents of the University of California.  All rights reserved.
      4  *
      5  * This code is derived from software contributed to Berkeley by
      6  * Michael Rendell of Memorial University of Newfoundland.
      7  *
      8  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  * 1. Redistributions of source code must retain the above copyright
     12  *    notice, this list of conditions and the following disclaimer.
     13  * 2. Redistributions in binary form must reproduce the above copyright
     14  *    notice, this list of conditions and the following disclaimer in the
     15  *    documentation and/or other materials provided with the distribution.
     16  * 3. All advertising materials mentioning features or use of this software
     17  *    must display the following acknowledgement:
     18  *	This product includes software developed by the University of
     19  *	California, Berkeley and its contributors.
     20  * 4. Neither the name of the University nor the names of its contributors
     21  *    may be used to endorse or promote products derived from this software
     22  *    without specific prior written permission.
     23  *
     24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     34  * SUCH DAMAGE.
     35  */
     36 
     37 #ifndef lint
     38 static char copyright[] =
     39 "@(#) Copyright (c) 1989, 1993\n\
     40 	The Regents of the University of California.  All rights reserved.\n";
     41 #endif /* not lint */
     42 
     43 #ifndef lint
     44 /* from: static char sccsid[] = "@(#)tsort.c	8.1 (Berkeley) 6/9/93"; */
     45 static char *rcsid = "$Id: tsort.c,v 1.7 1994/02/04 07:02:11 cgd Exp $";
     46 #endif /* not lint */
     47 
     48 #include <sys/types.h>
     49 #include <errno.h>
     50 #include <fcntl.h>
     51 #include <db.h>
     52 #include <stdio.h>
     53 #include <stdlib.h>
     54 #include <ctype.h>
     55 #include <string.h>
     56 
     57 /*
     58  *  Topological sort.  Input is a list of pairs of strings separated by
     59  *  white space (spaces, tabs, and/or newlines); strings are written to
     60  *  standard output in sorted order, one per line.
     61  *
     62  *  usage:
     63  *     tsort [-l] [inputfile]
     64  *  If no input file is specified, standard input is read.
     65  *
     66  *  Should be compatable with AT&T tsort HOWEVER the output is not identical
     67  *  (i.e. for most graphs there is more than one sorted order, and this tsort
     68  *  usually generates a different one then the AT&T tsort).  Also, cycle
     69  *  reporting seems to be more accurate in this version (the AT&T tsort
     70  *  sometimes says a node is in a cycle when it isn't).
     71  *
     72  *  Michael Rendell, michael (at) stretch.cs.mun.ca - Feb 26, '90
     73  */
     74 #define	HASHSIZE	53		/* doesn't need to be big */
     75 #define	NF_MARK		0x1		/* marker for cycle detection */
     76 #define	NF_ACYCLIC	0x2		/* this node is cycle free */
     77 #define	NF_NODEST	0x4		/* Unreachable */
     78 
     79 
     80 typedef struct node_str NODE;
     81 
     82 struct node_str {
     83 	NODE **n_prevp;			/* pointer to previous node's n_next */
     84 	NODE *n_next;			/* next node in graph */
     85 	NODE **n_arcs;			/* array of arcs to other nodes */
     86 	int n_narcs;			/* number of arcs in n_arcs[] */
     87 	int n_arcsize;			/* size of n_arcs[] array */
     88 	int n_refcnt;			/* # of arcs pointing to this node */
     89 	int n_flags;			/* NF_* */
     90 	char n_name[1];			/* name of this node */
     91 };
     92 
     93 typedef struct _buf {
     94 	char *b_buf;
     95 	int b_bsize;
     96 } BUF;
     97 
     98 DB *db;
     99 NODE *graph;
    100 NODE **cycle_buf;
    101 NODE **longest_cycle;
    102 int longest = 0;
    103 int debug = 0;
    104 
    105 void	 add_arc __P((char *, char *));
    106 void	 err __P((const char *, ...));
    107 int	 find_cycle __P((NODE *, NODE *, int, int));
    108 NODE	*get_node __P((char *));
    109 void	*grow_buf __P((void *, int));
    110 void	 remove_node __P((NODE *));
    111 void	 tsort __P((void));
    112 void	 usage __P((void));
    113 
    114 int
    115 main(argc, argv)
    116 	int argc;
    117 	char *argv[];
    118 {
    119 	register BUF *b;
    120 	register int c, n;
    121 	FILE *fp;
    122 	int bsize, ch, nused;
    123 	BUF bufs[2];
    124 
    125 	while ((ch = getopt(argc, argv, "dl")) != EOF)
    126 		switch(ch) {
    127 		case 'd':
    128 		    debug = 1;
    129 		    break;
    130 
    131 		case 'l':
    132 		    longest = 1;
    133 		    break;
    134 
    135 		case '?':
    136 		default:
    137 			usage();
    138 		}
    139 	argc -= optind;
    140 	argv += optind;
    141 
    142 	switch(argc) {
    143 	case 0:
    144 		fp = stdin;
    145 		break;
    146 	case 1:
    147 		if ((fp = fopen(*argv, "r")) == NULL)
    148 			err("%s: %s", *argv, strerror(errno));
    149 		break;
    150 	default:
    151 		usage();
    152 	}
    153 
    154 	for (b = bufs, n = 2; --n >= 0; b++)
    155 		b->b_buf = grow_buf(NULL, b->b_bsize = 1024);
    156 
    157 	/* parse input and build the graph */
    158 	for (n = 0, c = getc(fp);;) {
    159 		while (c != EOF && isspace(c))
    160 			c = getc(fp);
    161 		if (c == EOF)
    162 			break;
    163 
    164 		nused = 0;
    165 		b = &bufs[n];
    166 		bsize = b->b_bsize;
    167 		do {
    168 			b->b_buf[nused++] = c;
    169 			if (nused == bsize)
    170 				b->b_buf = grow_buf(b->b_buf, bsize *= 2);
    171 			c = getc(fp);
    172 		} while (c != EOF && !isspace(c));
    173 
    174 		b->b_buf[nused] = '\0';
    175 		b->b_bsize = bsize;
    176 		if (n)
    177 			add_arc(bufs[0].b_buf, bufs[1].b_buf);
    178 		n = !n;
    179 	}
    180 	(void)fclose(fp);
    181 	if (n)
    182 		err("odd data count");
    183 
    184 	/* do the sort */
    185 	tsort();
    186 	exit(0);
    187 }
    188 
    189 /* double the size of oldbuf and return a pointer to the new buffer. */
    190 void *
    191 grow_buf(bp, size)
    192 	void *bp;
    193 	int size;
    194 {
    195 	if ((bp = realloc(bp, (u_int)size)) == NULL)
    196 		err("%s", strerror(errno));
    197 	return (bp);
    198 }
    199 
    200 /*
    201  * add an arc from node s1 to node s2 in the graph.  If s1 or s2 are not in
    202  * the graph, then add them.
    203  */
    204 void
    205 add_arc(s1, s2)
    206 	char *s1, *s2;
    207 {
    208 	register NODE *n1;
    209 	NODE *n2;
    210 	int bsize, i;
    211 
    212 	n1 = get_node(s1);
    213 
    214 	if (!strcmp(s1, s2))
    215 		return;
    216 
    217 	n2 = get_node(s2);
    218 
    219 	/*
    220 	 * Check if this arc is already here.
    221 	 */
    222 	for (i = 0; i < n1->n_narcs; i++)
    223 		if (n1->n_arcs[i] == n2)
    224 			return;
    225 	/*
    226 	 * Add it.
    227 	 */
    228 	if (n1->n_narcs == n1->n_arcsize) {
    229 		if (!n1->n_arcsize)
    230 			n1->n_arcsize = 10;
    231 		bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
    232 		n1->n_arcs = grow_buf(n1->n_arcs, bsize);
    233 		n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
    234 	}
    235 	n1->n_arcs[n1->n_narcs++] = n2;
    236 	++n2->n_refcnt;
    237 }
    238 
    239 /* Find a node in the graph (insert if not found) and return a pointer to it. */
    240 NODE *
    241 get_node(name)
    242 	char *name;
    243 {
    244 	DBT data, key;
    245 	NODE *n;
    246 
    247 	if (db == NULL &&
    248 	    (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL)
    249 		err("db: open: %s", name, strerror(errno));
    250 
    251 	key.data = name;
    252 	key.size = strlen(name) + 1;
    253 
    254 	switch((*db->get)(db, &key, &data, 0)) {
    255 	case 0:
    256 		bcopy(data.data, &n, sizeof(n));
    257 		return (n);
    258 	case 1:
    259 		break;
    260 	default:
    261 	case -1:
    262 		err("db: get %s: %s", name, strerror(errno));
    263 	}
    264 
    265 	if ((n = malloc(sizeof(NODE) + key.size)) == NULL)
    266 		err("%s", strerror(errno));
    267 
    268 	n->n_narcs = 0;
    269 	n->n_arcsize = 0;
    270 	n->n_arcs = NULL;
    271 	n->n_refcnt = 0;
    272 	n->n_flags = 0;
    273 	bcopy(name, n->n_name, key.size);
    274 
    275 	/* Add to linked list. */
    276 	if (n->n_next = graph)
    277 		graph->n_prevp = &n->n_next;
    278 	n->n_prevp = &graph;
    279 	graph = n;
    280 
    281 	/* Add to hash table. */
    282 	data.data = &n;
    283 	data.size = sizeof(n);
    284 	if ((*db->put)(db, &key, &data, 0))
    285 		err("db: put %s: %s", name, strerror(errno));
    286 	return (n);
    287 }
    288 
    289 
    290 /*
    291  * Clear the NODEST flag from all nodes.
    292  */
    293 void
    294 clear_cycle()
    295 {
    296 	NODE *n;
    297 
    298 	for (n = graph; n; n = n->n_next)
    299 		n->n_flags &= ~NF_NODEST;
    300 }
    301 
    302 /* do topological sort on graph */
    303 void
    304 tsort()
    305 {
    306 	register NODE *n, *next;
    307 	register int cnt;
    308 
    309 	while (graph) {
    310 		/*
    311 		 * Keep getting rid of simple cases until there are none left,
    312 		 * if there are any nodes still in the graph, then there is
    313 		 * a cycle in it.
    314 		 */
    315 		do {
    316 			for (cnt = 0, n = graph; n; n = next) {
    317 				next = n->n_next;
    318 				if (n->n_refcnt == 0) {
    319 					remove_node(n);
    320 					++cnt;
    321 				}
    322 			}
    323 		} while (graph && cnt);
    324 
    325 		if (!graph)
    326 			break;
    327 
    328 		if (!cycle_buf) {
    329 			/*
    330 			 * Allocate space for two cycle logs - one to be used
    331 			 * as scratch space, the other to save the longest
    332 			 * cycle.
    333 			 */
    334 			for (cnt = 0, n = graph; n; n = n->n_next)
    335 				++cnt;
    336 			cycle_buf = malloc((u_int)sizeof(NODE *) * cnt);
    337 			longest_cycle = malloc((u_int)sizeof(NODE *) * cnt);
    338 			if (cycle_buf == NULL || longest_cycle == NULL)
    339 				err("%s", strerror(errno));
    340 		}
    341 		for (n = graph; n; n = n->n_next)
    342 			if (!(n->n_flags & NF_ACYCLIC)) {
    343 				if (cnt = find_cycle(n, n, 0, 0)) {
    344 					register int i;
    345 
    346 					(void)fprintf(stderr,
    347 					    "tsort: cycle in data\n");
    348 					for (i = 0; i < cnt; i++)
    349 						(void)fprintf(stderr,
    350 				"tsort: %s\n", longest_cycle[i]->n_name);
    351 					remove_node(n);
    352 					clear_cycle();
    353 					break;
    354 				} else {
    355 					/* to avoid further checks */
    356 					n->n_flags  |= NF_ACYCLIC;
    357 					clear_cycle();
    358 				}
    359 			}
    360 
    361 		if (!n)
    362 			err("internal error -- could not find cycle");
    363 	}
    364 }
    365 
    366 /* print node and remove from graph (does not actually free node) */
    367 void
    368 remove_node(n)
    369 	register NODE *n;
    370 {
    371 	register NODE **np;
    372 	register int i;
    373 
    374 	(void)printf("%s\n", n->n_name);
    375 	for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
    376 		--(*np)->n_refcnt;
    377 	n->n_narcs = 0;
    378 	*n->n_prevp = n->n_next;
    379 	if (n->n_next)
    380 		n->n_next->n_prevp = n->n_prevp;
    381 }
    382 
    383 
    384 /* look for the longest? cycle from node from to node to. */
    385 int
    386 find_cycle(from, to, longest_len, depth)
    387 	NODE *from, *to;
    388 	int depth, longest_len;
    389 {
    390 	register NODE **np;
    391 	register int i, len;
    392 
    393 	/*
    394 	 * avoid infinite loops and ignore portions of the graph known
    395 	 * to be acyclic
    396 	 */
    397 	if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC))
    398 		return (0);
    399 	from->n_flags |= NF_MARK;
    400 
    401 	for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
    402 		cycle_buf[depth] = *np;
    403 		if (*np == to) {
    404 			if (depth + 1 > longest_len) {
    405 				longest_len = depth + 1;
    406 				(void)memcpy((char *)longest_cycle,
    407 				    (char *)cycle_buf,
    408 				    longest_len * sizeof(NODE *));
    409 			}
    410 		} else {
    411 			if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST))
    412 				continue;
    413 			len = find_cycle(*np, to, longest_len, depth + 1);
    414 
    415 			if (debug)
    416 			    printf("%*s %s->%s %d\n", depth, "",
    417 			    	   from->n_name, to->n_name, len);
    418 
    419 			if (len == 0)
    420 			    (*np)->n_flags |= NF_NODEST;
    421 
    422 			if (len > longest_len)
    423 				longest_len = len;
    424 
    425 			if (len > 0 && !longest)
    426 				break;
    427 		}
    428 	}
    429 	from->n_flags &= ~NF_MARK;
    430 	return (longest_len);
    431 }
    432 
    433 void
    434 usage()
    435 {
    436 	(void)fprintf(stderr, "usage: tsort [-l] [file]\n");
    437 	exit(1);
    438 }
    439 
    440 #if __STDC__
    441 #include <stdarg.h>
    442 #else
    443 #include <varargs.h>
    444 #endif
    445 
    446 void
    447 #if __STDC__
    448 err(const char *fmt, ...)
    449 #else
    450 err(fmt, va_alist)
    451 	char *fmt;
    452         va_dcl
    453 #endif
    454 {
    455 	va_list ap;
    456 #if __STDC__
    457 	va_start(ap, fmt);
    458 #else
    459 	va_start(ap);
    460 #endif
    461 	(void)fprintf(stderr, "tsort: ");
    462 	(void)vfprintf(stderr, fmt, ap);
    463 	va_end(ap);
    464 	(void)fprintf(stderr, "\n");
    465 	exit(1);
    466 	/* NOTREACHED */
    467 }
    468