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 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 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 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 * 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 * 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 * 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