1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22
23 /*
24 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
25 * Use is subject to license terms.
26 */
27
28 /* Copyright (c) 1988 AT&T */
29 /* All Rights Reserved */
30
31 /*
32 * topological sort
33 * input is sequence of pairs of items (blank-free strings)
34 * nonidentical pair is a directed edge in graph
35 * identical pair merely indicates presence of node
36 * output is ordered list of items consistent with
37 * the partial ordering specified by the graph
38 */
39 #include "errmsg.h"
40 #include "stdio.h"
41 #include "string.h"
42 #include <locale.h>
43
44 /*
45 * the nodelist always has an empty element at the end to
46 * make it easy to grow in natural order
47 * states of the "live" field:
48 */
49 #define DEAD 0 /* already printed */
50 #define LIVE 1 /* not yet printed */
51 #define VISITED 2 /* used only in findloop() */
52
53 #define STR(X) #X
54 #define XSTR(X) STR(X)
55 #define FORMAT "%" XSTR(FILENAME_MAX) "s%" XSTR(FILENAME_MAX) "s"
56 /* These should make FORMAT "%1024s%1024s", if FILENAME_MAX is 1024. */
57
58 static
59 struct nodelist {
60 struct nodelist *nextnode;
61 struct predlist *inedges;
62 char *name;
63 int live;
64 } firstnode = {NULL, NULL, NULL, DEAD};
65
66 /*
67 * a predecessor list tells all the immediate
68 * predecessors of a given node
69 */
70 struct predlist {
71 struct predlist *nextpred;
72 struct nodelist *pred;
73 };
74
75 static struct nodelist *index(char *s);
76 static struct nodelist *findloop(void);
77 static struct nodelist *mark(struct nodelist *i);
78 static int present(struct nodelist *i, struct nodelist *j);
79 static int anypred(struct nodelist *i);
80
81 /*
82 * the first for loop reads in the graph,
83 * the second prints out the ordering
84 */
85 int
main(int argc,char ** argv)86 main(int argc, char **argv)
87 {
88 struct predlist *t;
89 FILE *input = stdin;
90 struct nodelist *i, *j;
91 int x;
92 char precedes[FILENAME_MAX+1], follows[FILENAME_MAX+1];
93
94 (void) setlocale(LC_ALL, "");
95 #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
96 #define TEXT_DOMAIN "SYS_TEST" /* Use this only if not previously defined */
97 #endif
98 (void) textdomain(TEXT_DOMAIN);
99
100 errprefix("UX");
101 errsource(*argv);
102 errverb("notag,notofix");
103 switch (argc) {
104 case 1:
105 break;
106 case 2:
107 if (strcmp(argv[1], "-") == 0)
108 break;
109 if (strcmp(argv[1], "--") == 0)
110 break;
111 input = zfopen(EERROR, argv[1], "r");
112 break;
113 case 3:
114 if (strcmp(argv[1], "--") != 0)
115 errusage(gettext("[ file ]"));
116 input = zfopen(EERROR, argv[2], "r");
117 break;
118 default:
119 errusage("[ file ]");
120 }
121 for (;;) {
122 x = fscanf(input, FORMAT, precedes, follows);
123 if (x == EOF)
124 break;
125 if (x != 2)
126 errmsg(EERROR, gettext("odd data"));
127 i = index(precedes);
128 j = index(follows);
129 if (i == j || present(i, j))
130 continue;
131 t = (struct predlist *)
132 zmalloc(EERROR, sizeof (struct predlist));
133 t->nextpred = j->inedges;
134 t->pred = i;
135 j->inedges = t;
136 }
137 for (;;) {
138 x = 0; /* anything LIVE on this sweep? */
139 for (i = &firstnode; i->nextnode != NULL; i = i->nextnode) {
140 if (i->live == LIVE) {
141 x = 1;
142 if (!anypred(i))
143 break;
144 }
145 }
146 if (x == 0)
147 break;
148 if (i->nextnode == NULL)
149 i = findloop();
150 (void) puts(i->name);
151 i->live = DEAD;
152 }
153 return (0); /* Ensure zero return on normal termination */
154 }
155
156 /*
157 * is i present on j's predecessor list?
158 */
159 static int
present(struct nodelist * i,struct nodelist * j)160 present(struct nodelist *i, struct nodelist *j)
161 {
162 struct predlist *t;
163 for (t = j->inedges; t != NULL; t = t->nextpred)
164 if (t->pred == i)
165 return (1);
166 return (0);
167 }
168
169 /*
170 * is there any live predecessor for i?
171 */
172 static int
anypred(struct nodelist * i)173 anypred(struct nodelist *i)
174 {
175 struct predlist *t;
176 for (t = i->inedges; t != NULL; t = t->nextpred)
177 if (t->pred->live == LIVE)
178 return (1);
179 return (0);
180 }
181
182 /*
183 * turn a string into a node pointer
184 */
185 static struct nodelist *
index(char * s)186 index(char *s)
187 {
188 struct nodelist *i;
189 char *t;
190 for (i = &firstnode; i->nextnode != NULL; i = i->nextnode)
191 if (strcmp(s, i->name) == 0)
192 return (i);
193 for (t = s; *t; t++);
194 t = zmalloc(EERROR, (unsigned)(t + 1 - s));
195 i->nextnode = (struct nodelist *)
196 zmalloc(EERROR, sizeof (struct nodelist));
197 i->name = t;
198 i->live = LIVE;
199 i->nextnode->nextnode = NULL;
200 i->nextnode->inedges = NULL;
201 i->nextnode->live = DEAD;
202 while (*t++ = *s++);
203 return (i);
204 }
205
206 /*
207 * given that there is a cycle, find some
208 * node in it
209 */
210 static struct nodelist *
findloop(void)211 findloop(void)
212 {
213 struct nodelist *i, *j;
214
215 for (i = &firstnode; i->nextnode != NULL; i = i->nextnode)
216 if (i->live == LIVE)
217 break;
218 errmsg(EINFO, "cycle in data");
219 i = mark(i);
220 if (i == NULL)
221 errmsg(EHALT, gettext("program error"));
222 for (j = &firstnode; j->nextnode != NULL; j = j->nextnode)
223 if (j->live == VISITED)
224 j->live = LIVE;
225 return (i);
226 }
227
228 /*
229 * depth-first search of LIVE predecessors
230 * to find some element of a cycle;
231 * VISITED is a temporary state recording the
232 * visits of the search
233 */
234 static struct nodelist *
mark(struct nodelist * i)235 mark(struct nodelist *i)
236 {
237 struct nodelist *j;
238 struct predlist *t;
239
240 if (i->live == DEAD)
241 return (NULL);
242 if (i->live == VISITED)
243 return (i);
244 i->live = VISITED;
245 for (t = i->inedges; t != NULL; t = t->nextpred) {
246 j = mark(t->pred);
247 if (j != NULL) {
248 (void) fprintf(stderr, "\t%s\n", i->name);
249 return (j);
250 }
251 }
252 return (NULL);
253 }
254