2 * Copyright (c) 1989, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
6 * Michael Rendell of Memorial University of Newfoundland.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * $FreeBSD: src/usr.bin/tsort/tsort.c,v 1.10.2.1 2001/03/04 09:18:23 kris Exp $
33 * $DragonFly: src/usr.bin/tsort/tsort.c,v 1.4 2004/12/21 20:00:57 cpressey Exp $
35 * @(#) Copyright (c) 1989, 1993, 1994 The Regents of the University of California. All rights reserved.
36 * @(#)tsort.c 8.3 (Berkeley) 5/4/95
39 #include <sys/types.h>
52 * Topological sort. Input is a list of pairs of strings separated by
53 * white space (spaces, tabs, and/or newlines); strings are written to
54 * standard output in sorted order, one per line.
57 * tsort [-dlq] [inputfile]
58 * If no input file is specified, standard input is read.
60 * Should be compatible with AT&T tsort HOWEVER the output is not identical
61 * (i.e. for most graphs there is more than one sorted order, and this tsort
62 * usually generates a different one then the AT&T tsort). Also, cycle
63 * reporting seems to be more accurate in this version (the AT&T tsort
64 * sometimes says a node is in a cycle when it isn't).
66 * Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
68 #define HASHSIZE 53 /* doesn't need to be big */
69 #define NF_MARK 0x1 /* marker for cycle detection */
70 #define NF_ACYCLIC 0x2 /* this node is cycle free */
71 #define NF_NODEST 0x4 /* Unreachable */
74 typedef struct node_str NODE
;
77 NODE
**n_prevp
; /* pointer to previous node's n_next */
78 NODE
*n_next
; /* next node in graph */
79 NODE
**n_arcs
; /* array of arcs to other nodes */
80 int n_narcs
; /* number of arcs in n_arcs[] */
81 int n_arcsize
; /* size of n_arcs[] array */
82 int n_refcnt
; /* # of arcs pointing to this node */
83 int n_flags
; /* NF_* */
84 char n_name
[1]; /* name of this node */
93 NODE
*graph
, **cycle_buf
, **longest_cycle
;
94 int debug
, longest
, quiet
;
96 static void add_arc(char *, char *);
97 static void clear_cycle(void);
98 static int find_cycle(NODE
*, NODE
*, int, int);
99 static NODE
*get_node(char *);
100 static void *grow_buf(void *, size_t);
101 static void remove_node(NODE
*);
102 static void tsort(void);
103 static void usage(void);
106 main(int argc
, char **argv
)
111 int bsize
, ch
, nused
;
114 while ((ch
= getopt(argc
, argv
, "dlq")) != -1) {
138 if ((fp
= fopen(*argv
, "r")) == NULL
)
146 for (b
= bufs
, n
= 2; --n
>= 0; b
++)
147 b
->b_buf
= grow_buf(NULL
, b
->b_bsize
= 1024);
149 /* Parse input and build the graph. */
150 for (n
= 0, c
= getc(fp
);;) {
151 while (c
!= EOF
&& isspace(c
))
160 b
->b_buf
[nused
++] = c
;
162 b
->b_buf
= grow_buf(b
->b_buf
, bsize
*= 2);
164 } while (c
!= EOF
&& !isspace(c
));
166 b
->b_buf
[nused
] = '\0';
169 add_arc(bufs
[0].b_buf
, bufs
[1].b_buf
);
174 errx(1, "odd data count");
181 /* Double the size of oldbuf and return a pointer to the new buffer. */
183 grow_buf(void *bp
, size_t size
)
185 if ((bp
= realloc(bp
, size
)) == NULL
)
191 * Add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in
192 * the graph, then add them.
195 add_arc(char *s1
, char *s2
)
204 if (strcmp(s1
, s2
) == 0)
210 * Check if this arc is already here.
212 for (i
= 0; i
< n1
->n_narcs
; i
++)
213 if (n1
->n_arcs
[i
] == n2
)
218 if (n1
->n_narcs
== n1
->n_arcsize
) {
221 bsize
= n1
->n_arcsize
* sizeof(*n1
->n_arcs
) * 2;
222 n1
->n_arcs
= grow_buf(n1
->n_arcs
, bsize
);
223 n1
->n_arcsize
= bsize
/ sizeof(*n1
->n_arcs
);
225 n1
->n_arcs
[n1
->n_narcs
++] = n2
;
229 /* Find a node in the graph (insert if not found) and return a pointer to it. */
237 (db
= dbopen(NULL
, O_RDWR
, 0, DB_HASH
, NULL
)) == NULL
)
238 err(1, "db: %s", name
);
241 key
.size
= strlen(name
) + 1;
243 switch ((*db
->get
)(db
, &key
, &data
, 0)) {
245 bcopy(data
.data
, &n
, sizeof(n
));
251 err(1, "db: %s", name
);
254 if ((n
= malloc(sizeof(NODE
) + key
.size
)) == NULL
)
262 bcopy(name
, n
->n_name
, key
.size
);
264 /* Add to linked list. */
265 if ((n
->n_next
= graph
) != NULL
)
266 graph
->n_prevp
= &n
->n_next
;
270 /* Add to hash table. */
272 data
.size
= sizeof(n
);
273 if ((*db
->put
)(db
, &key
, &data
, 0))
274 err(1, "db: %s", name
);
280 * Clear the NODEST flag from all nodes.
287 for (n
= graph
; n
!= NULL
; n
= n
->n_next
)
288 n
->n_flags
&= ~NF_NODEST
;
291 /* Perform a topological sort of the graph. */
298 while (graph
!= NULL
) {
300 * Keep getting rid of simple cases until there are none left,
301 * and if there are any nodes still in the graph, then there
305 for (cnt
= 0, n
= graph
; n
!= NULL
; n
= next
) {
307 if (n
->n_refcnt
== 0) {
312 } while (graph
!= NULL
&& cnt
!= 0);
319 * Allocate space for two cycle logs - one to be used
320 * as scratch space, the other to save the longest
323 for (cnt
= 0, n
= graph
; n
!= NULL
; n
= n
->n_next
)
325 cycle_buf
= malloc(sizeof(NODE
*) * cnt
);
326 longest_cycle
= malloc(sizeof(NODE
*) * cnt
);
327 if (cycle_buf
== NULL
|| longest_cycle
== NULL
)
330 for (n
= graph
; n
!= NULL
; n
= n
->n_next
)
331 if (!(n
->n_flags
& NF_ACYCLIC
)) {
332 if ((cnt
= find_cycle(n
, n
, 0, 0))) {
334 warnx("cycle in data");
335 for (i
= 0; i
< cnt
; i
++)
337 longest_cycle
[i
]->n_name
);
343 /* To avoid further checks: */
344 n
->n_flags
|= NF_ACYCLIC
;
350 errx(1, "internal error -- could not find cycle");
355 * Print a node and remove it from the graph (does not actually free
364 printf("%s\n", n
->n_name
);
365 for (np
= n
->n_arcs
, i
= n
->n_narcs
; --i
>= 0; np
++)
368 *n
->n_prevp
= n
->n_next
;
369 if (n
->n_next
!= NULL
)
370 n
->n_next
->n_prevp
= n
->n_prevp
;
374 /* Look for the (longest?) cycle from node from to node to. */
376 find_cycle(NODE
*from
, NODE
*to
, int longest_len
, int depth
)
382 * Avoid infinite loops and ignore portions of the graph known
385 if (from
->n_flags
& (NF_NODEST
|NF_MARK
|NF_ACYCLIC
))
387 from
->n_flags
|= NF_MARK
;
389 for (np
= from
->n_arcs
, i
= from
->n_narcs
; --i
>= 0; np
++) {
390 cycle_buf
[depth
] = *np
;
392 if (depth
+ 1 > longest_len
) {
393 longest_len
= depth
+ 1;
394 memcpy((char *)longest_cycle
,
396 longest_len
* sizeof(NODE
*));
399 if ((*np
)->n_flags
& (NF_MARK
|NF_ACYCLIC
|NF_NODEST
))
401 len
= find_cycle(*np
, to
, longest_len
, depth
+ 1);
404 printf("%*s %s->%s %d\n", depth
, "",
405 from
->n_name
, to
->n_name
, len
);
409 (*np
)->n_flags
|= NF_NODEST
;
411 if (len
> longest_len
)
414 if (len
> 0 && !longest
)
418 from
->n_flags
&= ~NF_MARK
;
419 return (longest_len
);
425 fprintf(stderr
, "usage: tsort [-dlq] [file]\n");