]>
git.cameronkatri.com Git - apple_cmds.git/blob - misc_cmds/tsort/tsort.c
1 /* $NetBSD: tsort.c,v 1.13 1998/08/25 20:59:42 ross Exp $ */
4 * Copyright (c) 1989, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
8 * Michael Rendell of Memorial University of Newfoundland.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 #include <sys/cdefs.h>
41 __COPYRIGHT("@(#) Copyright (c) 1989, 1993, 1994\n\
42 The Regents of the University of California. All rights reserved.\n");
47 static char sccsid
[] = "@(#)tsort.c 8.3 (Berkeley) 5/4/95";
49 __RCSID("$NetBSD: tsort.c,v 1.13 1998/08/25 20:59:42 ross Exp $");
52 #include <sys/types.h>
65 * Topological sort. Input is a list of pairs of strings separated by
66 * white space (spaces, tabs, and/or newlines); strings are written to
67 * standard output in sorted order, one per line.
70 * tsort [-l] [inputfile]
71 * If no input file is specified, standard input is read.
73 * Should be compatable with AT&T tsort HOWEVER the output is not identical
74 * (i.e. for most graphs there is more than one sorted order, and this tsort
75 * usually generates a different one then the AT&T tsort). Also, cycle
76 * reporting seems to be more accurate in this version (the AT&T tsort
77 * sometimes says a node is in a cycle when it isn't).
79 * Michael Rendell, michael@stretch.cs.mun.ca - Feb 26, '90
81 #define HASHSIZE 53 /* doesn't need to be big */
82 #define NF_MARK 0x1 /* marker for cycle detection */
83 #define NF_ACYCLIC 0x2 /* this node is cycle free */
84 #define NF_NODEST 0x4 /* Unreachable */
86 typedef struct node_str NODE
;
89 NODE
**n_prevp
; /* pointer to previous node's n_next */
90 NODE
*n_next
; /* next node in graph */
91 NODE
**n_arcs
; /* array of arcs to other nodes */
92 int n_narcs
; /* number of arcs in n_arcs[] */
93 int n_arcsize
; /* size of n_arcs[] array */
94 int n_refcnt
; /* # of arcs pointing to this node */
95 int n_flags
; /* NF_* */
96 char n_name
[1]; /* name of this node */
105 NODE
*graph
, **cycle_buf
, **longest_cycle
;
106 int debug
, longest
, quiet
;
108 void add_arc
__P((char *, char *));
109 void clear_cycle
__P((void));
110 int find_cycle
__P((NODE
*, NODE
*, int, int));
111 NODE
*get_node
__P((char *));
112 void *grow_buf
__P((void *, int));
113 int main
__P((int, char **));
114 void remove_node
__P((NODE
*));
115 void tsort
__P((void));
116 void usage
__P((void));
126 int bsize
, ch
, nused
;
130 while ((ch
= getopt(argc
, argv
, "dlq")) != -1)
153 if ((fp
= fopen(*argv
, "r")) == NULL
)
160 for (b
= bufs
, n
= 2; --n
>= 0; b
++)
161 b
->b_buf
= grow_buf(NULL
, b
->b_bsize
= 1024);
163 /* parse input and build the graph */
164 for (n
= 0, c
= getc(fp
);;) {
165 while (c
!= EOF
&& isspace(c
))
174 b
->b_buf
[nused
++] = c
;
176 b
->b_buf
= grow_buf(b
->b_buf
, bsize
*= 2);
178 } while (c
!= EOF
&& !isspace(c
));
180 b
->b_buf
[nused
] = '\0';
183 add_arc(bufs
[0].b_buf
, bufs
[1].b_buf
);
188 errx(1, "odd data count");
195 /* double the size of oldbuf and return a pointer to the new buffer. */
201 if ((bp
= realloc(bp
, (u_int
)size
)) == NULL
)
207 * add an arc from node s1 to node s2 in the graph. If s1 or s2 are not in
208 * the graph, then add them.
226 * Check if this arc is already here.
228 for (i
= 0; i
< n1
->n_narcs
; i
++)
229 if (n1
->n_arcs
[i
] == n2
)
234 if (n1
->n_narcs
== n1
->n_arcsize
) {
237 bsize
= n1
->n_arcsize
* sizeof(*n1
->n_arcs
) * 2;
238 n1
->n_arcs
= grow_buf(n1
->n_arcs
, bsize
);
239 n1
->n_arcsize
= bsize
/ sizeof(*n1
->n_arcs
);
241 n1
->n_arcs
[n1
->n_narcs
++] = n2
;
245 /* Find a node in the graph (insert if not found) and return a pointer to it. */
254 (db
= dbopen(NULL
, O_RDWR
, 0, DB_HASH
, NULL
)) == NULL
)
255 err(1, "db: %s", name
);
258 key
.size
= strlen(name
) + 1;
260 switch ((*db
->get
)(db
, &key
, &data
, 0)) {
262 memmove(&n
, data
.data
, sizeof(n
));
268 err(1, "db: %s", name
);
271 if ((n
= malloc(sizeof(NODE
) + key
.size
)) == NULL
)
279 memmove(n
->n_name
, name
, key
.size
);
281 /* Add to linked list. */
282 if ((n
->n_next
= graph
) != NULL
)
283 graph
->n_prevp
= &n
->n_next
;
287 /* Add to hash table. */
289 data
.size
= sizeof(n
);
290 if ((*db
->put
)(db
, &key
, &data
, 0))
291 err(1, "db: %s", name
);
297 * Clear the NODEST flag from all nodes.
304 for (n
= graph
; n
!= NULL
; n
= n
->n_next
)
305 n
->n_flags
&= ~NF_NODEST
;
308 /* do topological sort on graph */
315 while (graph
!= NULL
) {
317 * Keep getting rid of simple cases until there are none left,
318 * if there are any nodes still in the graph, then there is
322 for (cnt
= 0, n
= graph
; n
!= NULL
; n
= next
) {
324 if (n
->n_refcnt
== 0) {
329 } while (graph
!= NULL
&& cnt
);
336 * Allocate space for two cycle logs - one to be used
337 * as scratch space, the other to save the longest
340 for (cnt
= 0, n
= graph
; n
!= NULL
; n
= n
->n_next
)
342 cycle_buf
= malloc((u_int
)sizeof(NODE
*) * cnt
);
343 longest_cycle
= malloc((u_int
)sizeof(NODE
*) * cnt
);
344 if (cycle_buf
== NULL
|| longest_cycle
== NULL
)
347 for (n
= graph
; n
!= NULL
; n
= n
->n_next
) {
348 if (!(n
->n_flags
& NF_ACYCLIC
)) {
349 if ((cnt
= find_cycle(n
, n
, 0, 0)) != 0) {
351 warnx("cycle in data");
352 for (i
= 0; i
< cnt
; i
++)
354 longest_cycle
[i
]->n_name
);
360 /* to avoid further checks */
361 n
->n_flags
|= NF_ACYCLIC
;
367 errx(1, "internal error -- could not find cycle");
371 /* print node and remove from graph (does not actually free node) */
379 (void)printf("%s\n", n
->n_name
);
380 for (np
= n
->n_arcs
, i
= n
->n_narcs
; --i
>= 0; np
++)
383 *n
->n_prevp
= n
->n_next
;
385 n
->n_next
->n_prevp
= n
->n_prevp
;
389 /* look for the longest? cycle from node from to node to. */
391 find_cycle(from
, to
, longest_len
, depth
)
393 int depth
, longest_len
;
399 * avoid infinite loops and ignore portions of the graph known
402 if (from
->n_flags
& (NF_NODEST
|NF_MARK
|NF_ACYCLIC
))
404 from
->n_flags
|= NF_MARK
;
406 for (np
= from
->n_arcs
, i
= from
->n_narcs
; --i
>= 0; np
++) {
407 cycle_buf
[depth
] = *np
;
409 if (depth
+ 1 > longest_len
) {
410 longest_len
= depth
+ 1;
411 (void)memcpy((char *)longest_cycle
,
413 longest_len
* sizeof(NODE
*));
416 if ((*np
)->n_flags
& (NF_MARK
|NF_ACYCLIC
|NF_NODEST
))
418 len
= find_cycle(*np
, to
, longest_len
, depth
+ 1);
421 (void)printf("%*s %s->%s %d\n", depth
, "",
422 from
->n_name
, to
->n_name
, len
);
425 (*np
)->n_flags
|= NF_NODEST
;
427 if (len
> longest_len
)
430 if (len
> 0 && !longest
)
434 from
->n_flags
&= ~NF_MARK
;
435 return (longest_len
);
441 (void)fprintf(stderr
, "usage: tsort [-lq] [file]\n");