17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate * with the License.
87c478bd9Sstevel@tonic-gate *
97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate * and limitations under the License.
137c478bd9Sstevel@tonic-gate *
147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate *
207c478bd9Sstevel@tonic-gate * CDDL HEADER END
217c478bd9Sstevel@tonic-gate */
227c478bd9Sstevel@tonic-gate
237c478bd9Sstevel@tonic-gate /*
24*d6555420Smike_s * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
25*d6555420Smike_s * Use is subject to license terms.
267c478bd9Sstevel@tonic-gate */
277c478bd9Sstevel@tonic-gate
28*d6555420Smike_s /* Copyright (c) 1988 AT&T */
29*d6555420Smike_s /* All Rights Reserved */
30*d6555420Smike_s
317c478bd9Sstevel@tonic-gate /*
327c478bd9Sstevel@tonic-gate * topological sort
337c478bd9Sstevel@tonic-gate * input is sequence of pairs of items (blank-free strings)
347c478bd9Sstevel@tonic-gate * nonidentical pair is a directed edge in graph
357c478bd9Sstevel@tonic-gate * identical pair merely indicates presence of node
367c478bd9Sstevel@tonic-gate * output is ordered list of items consistent with
377c478bd9Sstevel@tonic-gate * the partial ordering specified by the graph
387c478bd9Sstevel@tonic-gate */
397c478bd9Sstevel@tonic-gate #include "errmsg.h"
407c478bd9Sstevel@tonic-gate #include "stdio.h"
417c478bd9Sstevel@tonic-gate #include "string.h"
427c478bd9Sstevel@tonic-gate #include <locale.h>
437c478bd9Sstevel@tonic-gate
447c478bd9Sstevel@tonic-gate /*
457c478bd9Sstevel@tonic-gate * the nodelist always has an empty element at the end to
467c478bd9Sstevel@tonic-gate * make it easy to grow in natural order
477c478bd9Sstevel@tonic-gate * states of the "live" field:
487c478bd9Sstevel@tonic-gate */
497c478bd9Sstevel@tonic-gate #define DEAD 0 /* already printed */
507c478bd9Sstevel@tonic-gate #define LIVE 1 /* not yet printed */
517c478bd9Sstevel@tonic-gate #define VISITED 2 /* used only in findloop() */
527c478bd9Sstevel@tonic-gate
537c478bd9Sstevel@tonic-gate #define STR(X) #X
547c478bd9Sstevel@tonic-gate #define XSTR(X) STR(X)
557c478bd9Sstevel@tonic-gate #define FORMAT "%" XSTR(FILENAME_MAX) "s%" XSTR(FILENAME_MAX) "s"
567c478bd9Sstevel@tonic-gate /* These should make FORMAT "%1024s%1024s", if FILENAME_MAX is 1024. */
577c478bd9Sstevel@tonic-gate
587c478bd9Sstevel@tonic-gate static
597c478bd9Sstevel@tonic-gate struct nodelist {
607c478bd9Sstevel@tonic-gate struct nodelist *nextnode;
617c478bd9Sstevel@tonic-gate struct predlist *inedges;
627c478bd9Sstevel@tonic-gate char *name;
637c478bd9Sstevel@tonic-gate int live;
647c478bd9Sstevel@tonic-gate } firstnode = {NULL, NULL, NULL, DEAD};
657c478bd9Sstevel@tonic-gate
667c478bd9Sstevel@tonic-gate /*
677c478bd9Sstevel@tonic-gate * a predecessor list tells all the immediate
687c478bd9Sstevel@tonic-gate * predecessors of a given node
697c478bd9Sstevel@tonic-gate */
707c478bd9Sstevel@tonic-gate struct predlist {
717c478bd9Sstevel@tonic-gate struct predlist *nextpred;
727c478bd9Sstevel@tonic-gate struct nodelist *pred;
737c478bd9Sstevel@tonic-gate };
747c478bd9Sstevel@tonic-gate
75*d6555420Smike_s static struct nodelist *index(char *s);
76*d6555420Smike_s static struct nodelist *findloop(void);
77*d6555420Smike_s static struct nodelist *mark(struct nodelist *i);
78*d6555420Smike_s static int present(struct nodelist *i, struct nodelist *j);
79*d6555420Smike_s static int anypred(struct nodelist *i);
807c478bd9Sstevel@tonic-gate
817c478bd9Sstevel@tonic-gate /*
827c478bd9Sstevel@tonic-gate * the first for loop reads in the graph,
837c478bd9Sstevel@tonic-gate * the second prints out the ordering
847c478bd9Sstevel@tonic-gate */
85*d6555420Smike_s int
main(int argc,char ** argv)86*d6555420Smike_s main(int argc, char **argv)
877c478bd9Sstevel@tonic-gate {
88*d6555420Smike_s struct predlist *t;
897c478bd9Sstevel@tonic-gate FILE *input = stdin;
90*d6555420Smike_s struct nodelist *i, *j;
917c478bd9Sstevel@tonic-gate int x;
927c478bd9Sstevel@tonic-gate char precedes[FILENAME_MAX+1], follows[FILENAME_MAX+1];
937c478bd9Sstevel@tonic-gate
947c478bd9Sstevel@tonic-gate (void) setlocale(LC_ALL, "");
957c478bd9Sstevel@tonic-gate #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
967c478bd9Sstevel@tonic-gate #define TEXT_DOMAIN "SYS_TEST" /* Use this only if not previously defined */
977c478bd9Sstevel@tonic-gate #endif
987c478bd9Sstevel@tonic-gate (void) textdomain(TEXT_DOMAIN);
997c478bd9Sstevel@tonic-gate
1007c478bd9Sstevel@tonic-gate errprefix("UX");
1017c478bd9Sstevel@tonic-gate errsource(*argv);
1027c478bd9Sstevel@tonic-gate errverb("notag,notofix");
1037c478bd9Sstevel@tonic-gate switch (argc) {
1047c478bd9Sstevel@tonic-gate case 1:
1057c478bd9Sstevel@tonic-gate break;
1067c478bd9Sstevel@tonic-gate case 2:
1077c478bd9Sstevel@tonic-gate if (strcmp(argv[1], "-") == 0)
1087c478bd9Sstevel@tonic-gate break;
1097c478bd9Sstevel@tonic-gate if (strcmp(argv[1], "--") == 0)
1107c478bd9Sstevel@tonic-gate break;
1117c478bd9Sstevel@tonic-gate input = zfopen(EERROR, argv[1], "r");
1127c478bd9Sstevel@tonic-gate break;
1137c478bd9Sstevel@tonic-gate case 3:
1147c478bd9Sstevel@tonic-gate if (strcmp(argv[1], "--") != 0)
1157c478bd9Sstevel@tonic-gate errusage(gettext("[ file ]"));
1167c478bd9Sstevel@tonic-gate input = zfopen(EERROR, argv[2], "r");
1177c478bd9Sstevel@tonic-gate break;
1187c478bd9Sstevel@tonic-gate default:
1197c478bd9Sstevel@tonic-gate errusage("[ file ]");
1207c478bd9Sstevel@tonic-gate }
1217c478bd9Sstevel@tonic-gate for (;;) {
1227c478bd9Sstevel@tonic-gate x = fscanf(input, FORMAT, precedes, follows);
1237c478bd9Sstevel@tonic-gate if (x == EOF)
1247c478bd9Sstevel@tonic-gate break;
1257c478bd9Sstevel@tonic-gate if (x != 2)
1267c478bd9Sstevel@tonic-gate errmsg(EERROR, gettext("odd data"));
1277c478bd9Sstevel@tonic-gate i = index(precedes);
1287c478bd9Sstevel@tonic-gate j = index(follows);
1297c478bd9Sstevel@tonic-gate if (i == j || present(i, j))
1307c478bd9Sstevel@tonic-gate continue;
1317c478bd9Sstevel@tonic-gate t = (struct predlist *)
1327c478bd9Sstevel@tonic-gate zmalloc(EERROR, sizeof (struct predlist));
1337c478bd9Sstevel@tonic-gate t->nextpred = j->inedges;
1347c478bd9Sstevel@tonic-gate t->pred = i;
1357c478bd9Sstevel@tonic-gate j->inedges = t;
1367c478bd9Sstevel@tonic-gate }
1377c478bd9Sstevel@tonic-gate for (;;) {
1387c478bd9Sstevel@tonic-gate x = 0; /* anything LIVE on this sweep? */
1397c478bd9Sstevel@tonic-gate for (i = &firstnode; i->nextnode != NULL; i = i->nextnode) {
1407c478bd9Sstevel@tonic-gate if (i->live == LIVE) {
1417c478bd9Sstevel@tonic-gate x = 1;
1427c478bd9Sstevel@tonic-gate if (!anypred(i))
1437c478bd9Sstevel@tonic-gate break;
1447c478bd9Sstevel@tonic-gate }
1457c478bd9Sstevel@tonic-gate }
1467c478bd9Sstevel@tonic-gate if (x == 0)
1477c478bd9Sstevel@tonic-gate break;
1487c478bd9Sstevel@tonic-gate if (i->nextnode == NULL)
1497c478bd9Sstevel@tonic-gate i = findloop();
150*d6555420Smike_s (void) puts(i->name);
1517c478bd9Sstevel@tonic-gate i->live = DEAD;
1527c478bd9Sstevel@tonic-gate }
1537c478bd9Sstevel@tonic-gate return (0); /* Ensure zero return on normal termination */
1547c478bd9Sstevel@tonic-gate }
1557c478bd9Sstevel@tonic-gate
1567c478bd9Sstevel@tonic-gate /*
1577c478bd9Sstevel@tonic-gate * is i present on j's predecessor list?
1587c478bd9Sstevel@tonic-gate */
159*d6555420Smike_s static int
present(struct nodelist * i,struct nodelist * j)160*d6555420Smike_s present(struct nodelist *i, struct nodelist *j)
1617c478bd9Sstevel@tonic-gate {
162*d6555420Smike_s struct predlist *t;
1637c478bd9Sstevel@tonic-gate for (t = j->inedges; t != NULL; t = t->nextpred)
1647c478bd9Sstevel@tonic-gate if (t->pred == i)
1657c478bd9Sstevel@tonic-gate return (1);
1667c478bd9Sstevel@tonic-gate return (0);
1677c478bd9Sstevel@tonic-gate }
1687c478bd9Sstevel@tonic-gate
1697c478bd9Sstevel@tonic-gate /*
1707c478bd9Sstevel@tonic-gate * is there any live predecessor for i?
1717c478bd9Sstevel@tonic-gate */
172*d6555420Smike_s static int
anypred(struct nodelist * i)173*d6555420Smike_s anypred(struct nodelist *i)
1747c478bd9Sstevel@tonic-gate {
175*d6555420Smike_s struct predlist *t;
1767c478bd9Sstevel@tonic-gate for (t = i->inedges; t != NULL; t = t->nextpred)
1777c478bd9Sstevel@tonic-gate if (t->pred->live == LIVE)
1787c478bd9Sstevel@tonic-gate return (1);
1797c478bd9Sstevel@tonic-gate return (0);
1807c478bd9Sstevel@tonic-gate }
1817c478bd9Sstevel@tonic-gate
1827c478bd9Sstevel@tonic-gate /*
1837c478bd9Sstevel@tonic-gate * turn a string into a node pointer
1847c478bd9Sstevel@tonic-gate */
185*d6555420Smike_s static struct nodelist *
index(char * s)186*d6555420Smike_s index(char *s)
1877c478bd9Sstevel@tonic-gate {
188*d6555420Smike_s struct nodelist *i;
189*d6555420Smike_s char *t;
1907c478bd9Sstevel@tonic-gate for (i = &firstnode; i->nextnode != NULL; i = i->nextnode)
1917c478bd9Sstevel@tonic-gate if (strcmp(s, i->name) == 0)
1927c478bd9Sstevel@tonic-gate return (i);
1937c478bd9Sstevel@tonic-gate for (t = s; *t; t++);
1947c478bd9Sstevel@tonic-gate t = zmalloc(EERROR, (unsigned)(t + 1 - s));
1957c478bd9Sstevel@tonic-gate i->nextnode = (struct nodelist *)
1967c478bd9Sstevel@tonic-gate zmalloc(EERROR, sizeof (struct nodelist));
1977c478bd9Sstevel@tonic-gate i->name = t;
1987c478bd9Sstevel@tonic-gate i->live = LIVE;
1997c478bd9Sstevel@tonic-gate i->nextnode->nextnode = NULL;
2007c478bd9Sstevel@tonic-gate i->nextnode->inedges = NULL;
2017c478bd9Sstevel@tonic-gate i->nextnode->live = DEAD;
2027c478bd9Sstevel@tonic-gate while (*t++ = *s++);
2037c478bd9Sstevel@tonic-gate return (i);
2047c478bd9Sstevel@tonic-gate }
2057c478bd9Sstevel@tonic-gate
2067c478bd9Sstevel@tonic-gate /*
2077c478bd9Sstevel@tonic-gate * given that there is a cycle, find some
2087c478bd9Sstevel@tonic-gate * node in it
2097c478bd9Sstevel@tonic-gate */
210*d6555420Smike_s static struct nodelist *
findloop(void)211*d6555420Smike_s findloop(void)
2127c478bd9Sstevel@tonic-gate {
213*d6555420Smike_s struct nodelist *i, *j;
2147c478bd9Sstevel@tonic-gate
2157c478bd9Sstevel@tonic-gate for (i = &firstnode; i->nextnode != NULL; i = i->nextnode)
2167c478bd9Sstevel@tonic-gate if (i->live == LIVE)
2177c478bd9Sstevel@tonic-gate break;
2187c478bd9Sstevel@tonic-gate errmsg(EINFO, "cycle in data");
2197c478bd9Sstevel@tonic-gate i = mark(i);
2207c478bd9Sstevel@tonic-gate if (i == NULL)
2217c478bd9Sstevel@tonic-gate errmsg(EHALT, gettext("program error"));
2227c478bd9Sstevel@tonic-gate for (j = &firstnode; j->nextnode != NULL; j = j->nextnode)
2237c478bd9Sstevel@tonic-gate if (j->live == VISITED)
2247c478bd9Sstevel@tonic-gate j->live = LIVE;
2257c478bd9Sstevel@tonic-gate return (i);
2267c478bd9Sstevel@tonic-gate }
2277c478bd9Sstevel@tonic-gate
2287c478bd9Sstevel@tonic-gate /*
2297c478bd9Sstevel@tonic-gate * depth-first search of LIVE predecessors
2307c478bd9Sstevel@tonic-gate * to find some element of a cycle;
2317c478bd9Sstevel@tonic-gate * VISITED is a temporary state recording the
2327c478bd9Sstevel@tonic-gate * visits of the search
2337c478bd9Sstevel@tonic-gate */
234*d6555420Smike_s static struct nodelist *
mark(struct nodelist * i)235*d6555420Smike_s mark(struct nodelist *i)
2367c478bd9Sstevel@tonic-gate {
237*d6555420Smike_s struct nodelist *j;
238*d6555420Smike_s struct predlist *t;
2397c478bd9Sstevel@tonic-gate
2407c478bd9Sstevel@tonic-gate if (i->live == DEAD)
2417c478bd9Sstevel@tonic-gate return (NULL);
2427c478bd9Sstevel@tonic-gate if (i->live == VISITED)
2437c478bd9Sstevel@tonic-gate return (i);
2447c478bd9Sstevel@tonic-gate i->live = VISITED;
2457c478bd9Sstevel@tonic-gate for (t = i->inedges; t != NULL; t = t->nextpred) {
2467c478bd9Sstevel@tonic-gate j = mark(t->pred);
2477c478bd9Sstevel@tonic-gate if (j != NULL) {
248*d6555420Smike_s (void) fprintf(stderr, "\t%s\n", i->name);
2497c478bd9Sstevel@tonic-gate return (j);
2507c478bd9Sstevel@tonic-gate }
2517c478bd9Sstevel@tonic-gate }
2527c478bd9Sstevel@tonic-gate return (NULL);
2537c478bd9Sstevel@tonic-gate }
254