1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1989-2011 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <glenn.s.fowler@gmail.com> *
18 * *
19 ***********************************************************************/
20 #pragma prototyped
21
22 static const char usage[] =
23 "[-?\n@(#)$Id: tsort (AT&T Research) 2000-03-23 $\n]"
24 USAGE_LICENSE
25 "[+NAME?tsort - topological sort]"
26 "[+DESCRIPTION?\btsort\b writes to the standard output a totally ordered"
27 " list of items consistent with a partial ordering of items contained"
28 " in the input \afile\a. If \afile\a is omitted then the standard"
29 " input is read.]"
30 "[+?The input consists of pairs of items (non-empty strings) separated by"
31 " blanks. Pairs of different items indicate ordering. Pairs of"
32 " identical items indicate presence, but not ordering.]"
33
34 "\n"
35 "\n[ file ]\n"
36 "\n"
37
38 "[+SEE ALSO?\bcomm\b(1), \bsort\b(1), \buniq\b(1)]"
39 ;
40
41 #include <ast.h>
42 #include <error.h>
43 #include <hash.h>
44
45 #define NODE_INIT 0
46 #define NODE_CYCLE 1
47 #define NODE_DONE 2
48
49 struct List_s;
50
51 typedef struct Node_s
52 {
53 HASH_HEADER;
54 struct List_s* prereqs;
55 int state;
56 } Node_t;
57
58 typedef struct List_s
59 {
60 struct List_s* next;
61 Node_t* node;
62 } List_t;
63
64 static int
visit(register Node_t * x)65 visit(register Node_t* x)
66 {
67 register List_t* p;
68 int cycle = 0;
69
70 switch (x->state)
71 {
72 case NODE_CYCLE:
73 error(1, "cycle in data");
74 cycle = 1;
75 break;
76 case NODE_INIT:
77 x->state = NODE_CYCLE;
78 for (p = x->prereqs; p; p = p->next)
79 if (visit(p->node))
80 {
81 cycle = 1;
82 error(2, " %s", hashname((Hash_bucket_t*)x));
83 break;
84 }
85 x->state = NODE_DONE;
86 sfputr(sfstdout, hashname((Hash_bucket_t*)x), '\n');
87 break;
88 }
89 return cycle;
90 }
91
92 static void
tsort(Sfio_t * ip)93 tsort(Sfio_t* ip)
94 {
95 register int c;
96 register char* s;
97 register char* b;
98 Node_t* head = 0;
99 Node_t* x;
100 List_t* p;
101 Hash_table_t* tab;
102 Hash_position_t* pos;
103
104 if (!(tab = hashalloc(NiL, HASH_set, HASH_ALLOCATE, 0)))
105 error(ERROR_exit(1), "out of space [hash table]");
106 while (s = sfgetr(ip, '\n', 1))
107 {
108 do
109 {
110 while (*s == ' ' || *s == '\t')
111 s++;
112 if (*s == 0)
113 break;
114 for (b = s; (c = *s) && c != ' ' && c != '\t'; s++);
115 *s++ = 0;
116 if (!(x = (Node_t*)hashlook(tab, b, HASH_CREATE|HASH_SIZE(sizeof(Node_t)), 0)))
117 error(ERROR_exit(1), "out of space [hash entry]");
118 if (head)
119 {
120 if (head != x)
121 {
122 if (!(p = newof(0, List_t, 1, 0)))
123 error(ERROR_exit(1), "out of space [hash list]");
124 p->node = head;
125 p->next = x->prereqs;
126 x->prereqs = p;
127 }
128 head = 0;
129 }
130 else
131 head = x;
132 } while (c);
133 }
134 if (sfvalue(ip))
135 error(ERROR_warn(1), "last line incomplete");
136 if (head)
137 error(ERROR_exit(1), "odd data");
138 if (pos = hashscan(tab, 0))
139 {
140 while (hashnext(pos))
141 visit((Node_t*)pos->bucket);
142 hashdone(pos);
143 }
144 else
145 error(ERROR_exit(1), "hash error");
146 hashfree(tab);
147 }
148
149 int
main(int argc,char ** argv)150 main(int argc, char** argv)
151 {
152 Sfio_t* ip;
153
154 NoP(argc);
155 error_info.id = "tsort";
156 for (;;)
157 {
158 switch (optget(argv, usage))
159 {
160 case ':':
161 error(2, "%s", opt_info.arg);
162 break;
163 case '?':
164 error(ERROR_usage(2), "%s", opt_info.arg);
165 break;
166 }
167 break;
168 }
169 argv += opt_info.index;
170 if (error_info.errors)
171 error(ERROR_usage(2), "%s", optusage(NiL));
172 if (!*argv || streq(*argv, "-") || streq(*argv, "/dev/stdin"))
173 ip = sfstdin;
174 else if (!(ip = sfopen(NiL, *argv, "r")))
175 error(ERROR_system(1), "%s cannot open", *argv);
176 tsort(ip);
177 if (ip != sfstdin)
178 sfclose(ip);
179 return error_info.errors != 0;
180 }
181