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
70 typedef struct node_str NODE;
71
72 struct 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
83 typedef struct _buf {
84 char *b_buf;
85 int b_bsize;
86 } BUF;
87
88 static DB *db;
89 static NODE *graph, **cycle_buf, **longest_cycle;
90 static int debug, longest, quiet;
91
92 static void add_arc(char *, char *);
93 static int find_cycle(NODE *, NODE *, int, int);
94 static NODE *get_node(char *);
95 static void *grow_buf(void *, size_t);
96 static void remove_node(NODE *);
97 static void clear_cycle(void);
98 static void tsort(void);
99 static void usage(void);
100
101 int
main(int argc,char * argv[])102 main(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. */
179 static void *
grow_buf(void * bp,size_t size)180 grow_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 */
191 static void
add_arc(char * s1,char * s2)192 add_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. */
226 static NODE *
get_node(char * name)227 get_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 */
278 static void
clear_cycle(void)279 clear_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 */
288 static void
tsort(void)289 tsort(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) */
351 static void
remove_node(NODE * n)352 remove_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. */
368 static int
find_cycle(NODE * from,NODE * to,int longest_len,int depth)369 find_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
414 static void
usage(void)415 usage(void)
416 {
417 (void)fprintf(stderr, "usage: tsort [-dlq] [file]\n");
418 exit(1);
419 }
420