tsort.c revision 3f54fd611f536639ec30dd53c48e5ec1897cc7d9
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa/***********************************************************************
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* *
e9458b1a7a19a63aa4c179f9ab20f4d50681c168Jens Elkner* This software is part of the ast package *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* Copyright (c) 1989-2011 AT&T Intellectual Property *
cacbb5e3100fb85d23d1614cace3a8662801f2e6Eugen Kuksa* and is licensed under the *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* Eclipse Public License, Version 1.0 *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* by AT&T Intellectual Property *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* A copy of the License is available at *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* http://www.eclipse.org/org/documents/epl-v10.html *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* Information and Software Systems Research *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* AT&T Research *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* Florham Park NJ *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* Glenn Fowler <gsf@research.att.com> *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa* *
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa***********************************************************************/
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#pragma prototyped
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksastatic const char usage[] =
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"[-?\n@(#)$Id: tsort (AT&T Research) 2000-03-23 $\n]"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen KuksaUSAGE_LICENSE
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"[+NAME?tsort - topological sort]"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"[+DESCRIPTION?\btsort\b writes to the standard output a totally ordered"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa" list of items consistent with a partial ordering of items contained"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa" in the input \afile\a. If \afile\a is omitted then the standard"
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa" input is read.]"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"[+?The input consists of pairs of items (non-empty strings) separated by"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa" blanks. Pairs of different items indicate ordering. Pairs of"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa" identical items indicate presence, but not ordering.]"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"\n"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"\n[ file ]\n"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"\n"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa"[+SEE ALSO?\bcomm\b(1), \bsort\b(1), \buniq\b(1)]"
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#include <ast.h>
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#include <error.h>
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#include <hash.h>
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#define NODE_INIT 0
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#define NODE_CYCLE 1
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa#define NODE_DONE 2
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksastruct List_s;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksatypedef struct Node_s
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa{
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa HASH_HEADER;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa struct List_s* prereqs;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa int state;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa} Node_t;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksatypedef struct List_s
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa{
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa struct List_s* next;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa Node_t* node;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa} List_t;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksastatic int
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksavisit(register Node_t* x)
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa{
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa register List_t* p;
1ea7fb6b0f66210bc0d3cb995f1b655277b33884Eugen Kuksa int cycle = 0;
037be4e5b0e867dd148db2ea89640d8edf009053Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa switch (x->state)
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa {
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa case NODE_CYCLE:
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa error(1, "cycle in data");
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa cycle = 1;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa break;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa case NODE_INIT:
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa x->state = NODE_CYCLE;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa for (p = x->prereqs; p; p = p->next)
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa if (visit(p->node))
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa {
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa cycle = 1;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa error(2, " %s", hashname((Hash_bucket_t*)x));
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa break;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa }
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa x->state = NODE_DONE;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa sfputr(sfstdout, hashname((Hash_bucket_t*)x), '\n');
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa break;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa }
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa return cycle;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa}
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksastatic void
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroedertsort(Sfio_t* ip)
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa{
1ea7fb6b0f66210bc0d3cb995f1b655277b33884Eugen Kuksa register int c;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa register char* s;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa register char* b;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa Node_t* head = 0;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa Node_t* x;
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa List_t* p;
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa Hash_table_t* tab;
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder Hash_position_t* pos;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa if (!(tab = hashalloc(NiL, HASH_set, HASH_ALLOCATE, 0)))
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa error(ERROR_exit(1), "out of space [hash table]");
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa while (s = sfgetr(ip, '\n', 1))
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa {
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa do
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa {
1ea7fb6b0f66210bc0d3cb995f1b655277b33884Eugen Kuksa while (*s == ' ' || *s == '\t')
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa s++;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa if (*s == 0)
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder break;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa for (b = s; (c = *s) && c != ' ' && c != '\t'; s++);
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa *s++ = 0;
1ea7fb6b0f66210bc0d3cb995f1b655277b33884Eugen Kuksa if (!(x = (Node_t*)hashlook(tab, b, HASH_CREATE|HASH_SIZE(sizeof(Node_t)), 0)))
c4b9911676ee4c9e8597ecb49efbf4abc69b4090Eugen Kuksa error(ERROR_exit(1), "out of space [hash entry]");
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa if (head)
1ea7fb6b0f66210bc0d3cb995f1b655277b33884Eugen Kuksa {
8247c2f9606497ccfc5b4d10b3fcb07d8c0f6074Eugen Kuksa if (head != x)
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa {
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa if (!(p = newof(0, List_t, 1, 0)))
a8ddb13beb092672c9f537ef1cf2e14f1f8a8f26Eugen Kuksa error(ERROR_exit(1), "out of space [hash list]");
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze p->node = head;
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze p->next = x->prereqs;
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze x->prereqs = p;
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze }
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa head = 0;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa }
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa else
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa head = x;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa } while (c);
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa }
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa if (sfvalue(ip))
d2d5606ab65ddf48599bd044416de07a205095f2Soeren D. Schulze error(ERROR_warn(1), "last line incomplete");
d2d5606ab65ddf48599bd044416de07a205095f2Soeren D. Schulze if (head)
d2d5606ab65ddf48599bd044416de07a205095f2Soeren D. Schulze error(ERROR_exit(1), "odd data");
d2d5606ab65ddf48599bd044416de07a205095f2Soeren D. Schulze if (pos = hashscan(tab, 0))
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa {
d2d5606ab65ddf48599bd044416de07a205095f2Soeren D. Schulze while (hashnext(pos))
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa visit((Node_t*)pos->bucket);
d2d5606ab65ddf48599bd044416de07a205095f2Soeren D. Schulze hashdone(pos);
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa }
3d3889e0cefcdce9b3f43c53aaa201943ac2e895Jonathan von Schroeder else
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze error(ERROR_exit(1), "hash error");
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze hashfree(tab);
ea570f40967ef8bc16b76c54f9b867a8036cc750Soeren D. Schulze}
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksaint
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksamain(int argc, char** argv)
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa{
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa Sfio_t* ip;
e3ed0ae47dd551ddd9d74c33fff11b19a23a1d97Eugen Kuksa
NoP(argc);
error_info.id = "tsort";
for (;;)
{
switch (optget(argv, usage))
{
case ':':
error(2, "%s", opt_info.arg);
break;
case '?':
error(ERROR_usage(2), "%s", opt_info.arg);
break;
}
break;
}
argv += opt_info.index;
if (error_info.errors)
error(ERROR_usage(2), "%s", optusage(NiL));
if (!*argv || streq(*argv, "-") || streq(*argv, "/dev/stdin"))
ip = sfstdin;
else if (!(ip = sfopen(NiL, *argv, "r")))
error(ERROR_system(1), "%s cannot open", *argv);
tsort(ip);
if (ip != sfstdin)
sfclose(ip);
return error_info.errors != 0;
}