1/*
2 * Copyright (c) 1989, 1993, 1994
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 * $Id: tsort.c,v 1.7 1997/03/11 14:48:14 peter Exp $
37 */
38
39#ifndef lint
40static char copyright[] =
41"@(#) Copyright (c) 1989, 1993, 1994\n\
42 The Regents of the University of California. All rights reserved.\n";
43#endif /* not lint */
44
45#ifndef lint
46static char sccsid[] = "@(#)tsort.c 8.3 (Berkeley) 5/4/95";
47#endif /* not lint */
48
49#include <sys/types.h>
50
51#include <ctype.h>
52#include <db.h>
53#include <err.h>
54#include <errno.h>
55#include <fcntl.h>
56#include <stdio.h>
57#include <stdlib.h>
58#include <string.h>
59#include <unistd.h>
60
61/*
62 * Topological sort. Input is a list of pairs of strings separated by
63 * white space (spaces, tabs, and/or newlines); strings are written to
64 * standard output in sorted order, one per line.
65 *
66 * usage:
67 * tsort [-dlq] [inputfile]
68 * If no input file is specified, standard input is read.
69 *
70 * Should be compatable with AT&T tsort HOWEVER the output is not identical
71 * (i.e. for most graphs there is more than one sorted order, and this tsort
72 * usually generates a different one then the AT&T tsort). Also, cycle
73 * reporting seems to be more accurate in this version (the AT&T tsort
74 * sometimes says a node is in a cycle when it isn't).
75 *
76 * Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
77 */
78#define HASHSIZE 53 /* doesn't need to be big */
79#define NF_MARK 0x1 /* marker for cycle detection */
80#define NF_ACYCLIC 0x2 /* this node is cycle free */
81#define NF_NODEST 0x4 /* Unreachable */
82
83
84typedef struct node_str NODE;
85
86struct node_str {
87 NODE **n_prevp; /* pointer to previous node's n_next */
88 NODE *n_next; /* next node in graph */
89 NODE **n_arcs; /* array of arcs to other nodes */
90 int n_narcs; /* number of arcs in n_arcs[] */
91 int n_arcsize; /* size of n_arcs[] array */
92 int n_refcnt; /* # of arcs pointing to this node */
93 int n_flags; /* NF_* */
94 char n_name[1]; /* name of this node */
95};
96
97typedef struct _buf {
98 char *b_buf;
99 int b_bsize;
100} BUF;
101
102DB *db;
103NODE *graph, **cycle_buf, **longest_cycle;
104int debug, longest, quiet;
105
106void add_arc __P((char *, char *));
107int find_cycle __P((NODE *, NODE *, int, int));
108NODE *get_node __P((char *));
109void *grow_buf __P((void *, int));
110void remove_node __P((NODE *));
111void tsort __P((void));
112void usage __P((void));
113
114int
115main(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, "dlq")) != -1)
126 switch (ch) {
127 case 'd':
128 debug = 1;
129 break;
130 case 'l':
131 longest = 1;
132 break;
133 case 'q':
134 quiet = 1;
135 break;
136 case '?':
137 default:
138 usage();
139 }
140 argc -= optind;
141 argv += optind;
142
143 switch (argc) {
144 case 0:
145 fp = stdin;
146 break;
147 case 1:
148 if ((fp = fopen(*argv, "r")) == NULL)
149 err(1, "%s", *argv);
150 break;
151 default:
152 usage();
153 }
154
155 for (b = bufs, n = 2; --n >= 0; b++)
156 b->b_buf = grow_buf(NULL, b->b_bsize = 1024);
157
158 /* parse input and build the graph */
159 for (n = 0, c = getc(fp);;) {
160 while (c != EOF && isspace(c))
161 c = getc(fp);
162 if (c == EOF)
163 break;
164
165 nused = 0;
166 b = &bufs[n];
167 bsize = b->b_bsize;
168 do {
169 b->b_buf[nused++] = c;
170 if (nused == bsize)
171 b->b_buf = grow_buf(b->b_buf, bsize *= 2);
172 c = getc(fp);
173 } while (c != EOF && !isspace(c));
174
175 b->b_buf[nused] = '\0';
176 b->b_bsize = bsize;
177 if (n)
178 add_arc(bufs[0].b_buf, bufs[1].b_buf);
179 n = !n;
180 }
181 (void)fclose(fp);
182 if (n)
183 errx(1, "odd data count");
184
185 /* do the sort */
186 tsort();
187 exit(0);
188}
189
190/* double the size of oldbuf and return a pointer to the new buffer. */
191void *
192grow_buf(bp, size)
193 void *bp;
194 int size;
195{
196 if ((bp = realloc(bp, (u_int)size)) == NULL)
197 err(1, NULL);
198 return (bp);
199}
200
201/*
202 * add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in
203 * the graph, then add them.
204 */
205void
206add_arc(s1, s2)
207 char *s1, *s2;
208{
209 register NODE *n1;
210 NODE *n2;
211 int bsize, i;
212
213 n1 = get_node(s1);
214
215 if (!strcmp(s1, s2))
216 return;
217
218 n2 = get_node(s2);
219
220 /*
221 * Check if this arc is already here.
222 */
223 for (i = 0; i < n1->n_narcs; i++)
224 if (n1->n_arcs[i] == n2)
225 return;
226 /*
227 * Add it.
228 */
229 if (n1->n_narcs == n1->n_arcsize) {
230 if (!n1->n_arcsize)
231 n1->n_arcsize = 10;
232 bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
233 n1->n_arcs = grow_buf(n1->n_arcs, bsize);
234 n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
235 }
236 n1->n_arcs[n1->n_narcs++] = n2;
237 ++n2->n_refcnt;
238}
239
240/* Find a node in the graph (insert if not found) and return a pointer to it. */
241NODE *
242get_node(name)
243 char *name;
244{
245 DBT data, key;
246 NODE *n;
247
248 if (db == NULL &&
249 (db = dbopen(NULL, O_RDWR, 0, DB_HASH, NULL)) == NULL)
250 err(1, "db: %s", name);
251
252 key.data = name;
253 key.size = strlen(name) + 1;
254
255 switch ((*db->get)(db, &key, &data, 0)) {
256 case 0:
257 bcopy(data.data, &n, sizeof(n));
258 return (n);
259 case 1:
260 break;
261 default:
262 case -1:
263 err(1, "db: %s", name);
264 }
265
266 if ((n = malloc(sizeof(NODE) + key.size)) == NULL)
267 err(1, NULL);
268
269 n->n_narcs = 0;
270 n->n_arcsize = 0;
271 n->n_arcs = NULL;
272 n->n_refcnt = 0;
273 n->n_flags = 0;
274 bcopy(name, n->n_name, key.size);
275
276 /* Add to linked list. */
277 if ((n->n_next = graph) != NULL)
278 graph->n_prevp = &n->n_next;
279 n->n_prevp = &graph;
280 graph = n;
281
282 /* Add to hash table. */
283 data.data = &n;
284 data.size = sizeof(n);
285 if ((*db->put)(db, &key, &data, 0))
286 err(1, "db: %s", name);
287 return (n);
288}
289
290
291/*
292 * Clear the NODEST flag from all nodes.
293 */
294void
295clear_cycle()
296{
297 NODE *n;
298
299 for (n = graph; n != NULL; n = n->n_next)
300 n->n_flags &= ~NF_NODEST;
301}
302
303/* do topological sort on graph */
304void
305tsort()
306{
307 register NODE *n, *next;
308 register int cnt, i;
309
310 while (graph != NULL) {
311 /*
312 * Keep getting rid of simple cases until there are none left,
313 * if there are any nodes still in the graph, then there is
314 * a cycle in it.
315 */
316 do {
317 for (cnt = 0, n = graph; n != NULL; n = next) {
318 next = n->n_next;
319 if (n->n_refcnt == 0) {
320 remove_node(n);
321 ++cnt;
322 }
323 }
324 } while (graph != NULL && cnt);
325
326 if (graph == NULL)
327 break;
328
329 if (!cycle_buf) {
330 /*
331 * Allocate space for two cycle logs - one to be used
332 * as scratch space, the other to save the longest
333 * cycle.
334 */
335 for (cnt = 0, n = graph; n != NULL; n = n->n_next)
336 ++cnt;
337 cycle_buf = malloc((u_int)sizeof(NODE *) * cnt);
338 longest_cycle = malloc((u_int)sizeof(NODE *) * cnt);
339 if (cycle_buf == NULL || longest_cycle == NULL)
340 err(1, NULL);
341 }
342 for (n = graph; n != NULL; n = n->n_next)
343 if (!(n->n_flags & NF_ACYCLIC))
344 if ((cnt = find_cycle(n, n, 0, 0))) {
345 if (!quiet) {
346 warnx("cycle in data");
347 for (i = 0; i < cnt; i++)
348 warnx("%s",
349 longest_cycle[i]->n_name);
350 }
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 if (n == NULL)
361 errx(1, "internal error -- could not find cycle");
362 }
363}
364
365/* print node and remove from graph (does not actually free node) */
366void
367remove_node(n)
368 register NODE *n;
369{
370 register NODE **np;
371 register int i;
372
373 (void)printf("%s\n", n->n_name);
374 for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
375 --(*np)->n_refcnt;
376 n->n_narcs = 0;
377 *n->n_prevp = n->n_next;
378 if (n->n_next)
379 n->n_next->n_prevp = n->n_prevp;
380}
381
382
383/* look for the longest? cycle from node from to node to. */
384int
385find_cycle(from, to, longest_len, depth)
386 NODE *from, *to;
387 int depth, longest_len;
388{
389 register NODE **np;
390 register int i, len;
391
392 /*
393 * avoid infinite loops and ignore portions of the graph known
394 * to be acyclic
395 */
396 if (from->n_flags & (NF_NODEST|NF_MARK|NF_ACYCLIC))
397 return (0);
398 from->n_flags |= NF_MARK;
399
400 for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
401 cycle_buf[depth] = *np;
402 if (*np == to) {
403 if (depth + 1 > longest_len) {
404 longest_len = depth + 1;
405 (void)memcpy((char *)longest_cycle,
406 (char *)cycle_buf,
407 longest_len * sizeof(NODE *));
408 }
409 } else {
410 if ((*np)->n_flags & (NF_MARK|NF_ACYCLIC|NF_NODEST))
411 continue;
412 len = find_cycle(*np, to, longest_len, depth + 1);
413
414 if (debug)
415 (void)printf("%*s %s->%s %d\n", depth, "",
416 from->n_name, to->n_name, len);
417
418 if (len == 0)
419 (*np)->n_flags |= NF_NODEST;
420
421 if (len > longest_len)
422 longest_len = len;
423
424 if (len > 0 && !longest)
425 break;
426 }
427 }
428 from->n_flags &= ~NF_MARK;
429 return (longest_len);
430}
431
432void
433usage()
434{
435 (void)fprintf(stderr, "usage: tsort [-dlq] [file]\n");
436 exit(1);
437}