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