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