tsort.c revision 372:5bfa4fc81658
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#pragma ident "%Z%%M% %I% %E% SMI" 32 33/* 34 * topological sort 35 * input is sequence of pairs of items (blank-free strings) 36 * nonidentical pair is a directed edge in graph 37 * identical pair merely indicates presence of node 38 * output is ordered list of items consistent with 39 * the partial ordering specified by the graph 40 */ 41#include "errmsg.h" 42#include "stdio.h" 43#include "string.h" 44#include <locale.h> 45 46/* 47 * the nodelist always has an empty element at the end to 48 * make it easy to grow in natural order 49 * states of the "live" field: 50 */ 51#define DEAD 0 /* already printed */ 52#define LIVE 1 /* not yet printed */ 53#define VISITED 2 /* used only in findloop() */ 54 55#define STR(X) #X 56#define XSTR(X) STR(X) 57#define FORMAT "%" XSTR(FILENAME_MAX) "s%" XSTR(FILENAME_MAX) "s" 58/* These should make FORMAT "%1024s%1024s", if FILENAME_MAX is 1024. */ 59 60static 61struct nodelist { 62 struct nodelist *nextnode; 63 struct predlist *inedges; 64 char *name; 65 int live; 66} firstnode = {NULL, NULL, NULL, DEAD}; 67 68/* 69 * a predecessor list tells all the immediate 70 * predecessors of a given node 71 */ 72struct predlist { 73 struct predlist *nextpred; 74 struct nodelist *pred; 75}; 76 77static struct nodelist *index(char *s); 78static struct nodelist *findloop(void); 79static struct nodelist *mark(struct nodelist *i); 80static int present(struct nodelist *i, struct nodelist *j); 81static int anypred(struct nodelist *i); 82 83/* 84 * the first for loop reads in the graph, 85 * the second prints out the ordering 86 */ 87int 88main(int argc, char **argv) 89{ 90 struct predlist *t; 91 FILE *input = stdin; 92 struct nodelist *i, *j; 93 int x; 94 char precedes[FILENAME_MAX+1], follows[FILENAME_MAX+1]; 95 96 (void) setlocale(LC_ALL, ""); 97#if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */ 98#define TEXT_DOMAIN "SYS_TEST" /* Use this only if not previously defined */ 99#endif 100 (void) textdomain(TEXT_DOMAIN); 101 102 errprefix("UX"); 103 errsource(*argv); 104 errverb("notag,notofix"); 105 switch (argc) { 106 case 1: 107 break; 108 case 2: 109 if (strcmp(argv[1], "-") == 0) 110 break; 111 if (strcmp(argv[1], "--") == 0) 112 break; 113 input = zfopen(EERROR, argv[1], "r"); 114 break; 115 case 3: 116 if (strcmp(argv[1], "--") != 0) 117 errusage(gettext("[ file ]")); 118 input = zfopen(EERROR, argv[2], "r"); 119 break; 120 default: 121 errusage("[ file ]"); 122 } 123 for (;;) { 124 x = fscanf(input, FORMAT, precedes, follows); 125 if (x == EOF) 126 break; 127 if (x != 2) 128 errmsg(EERROR, gettext("odd data")); 129 i = index(precedes); 130 j = index(follows); 131 if (i == j || present(i, j)) 132 continue; 133 t = (struct predlist *) 134 zmalloc(EERROR, sizeof (struct predlist)); 135 t->nextpred = j->inedges; 136 t->pred = i; 137 j->inedges = t; 138 } 139 for (;;) { 140 x = 0; /* anything LIVE on this sweep? */ 141 for (i = &firstnode; i->nextnode != NULL; i = i->nextnode) { 142 if (i->live == LIVE) { 143 x = 1; 144 if (!anypred(i)) 145 break; 146 } 147 } 148 if (x == 0) 149 break; 150 if (i->nextnode == NULL) 151 i = findloop(); 152 (void) puts(i->name); 153 i->live = DEAD; 154 } 155 return (0); /* Ensure zero return on normal termination */ 156} 157 158/* 159 * is i present on j's predecessor list? 160 */ 161static int 162present(struct nodelist *i, struct nodelist *j) 163{ 164 struct predlist *t; 165 for (t = j->inedges; t != NULL; t = t->nextpred) 166 if (t->pred == i) 167 return (1); 168 return (0); 169} 170 171/* 172 * is there any live predecessor for i? 173 */ 174static int 175anypred(struct nodelist *i) 176{ 177 struct predlist *t; 178 for (t = i->inedges; t != NULL; t = t->nextpred) 179 if (t->pred->live == LIVE) 180 return (1); 181 return (0); 182} 183 184/* 185 * turn a string into a node pointer 186 */ 187static struct nodelist * 188index(char *s) 189{ 190 struct nodelist *i; 191 char *t; 192 for (i = &firstnode; i->nextnode != NULL; i = i->nextnode) 193 if (strcmp(s, i->name) == 0) 194 return (i); 195 for (t = s; *t; t++); 196 t = zmalloc(EERROR, (unsigned)(t + 1 - s)); 197 i->nextnode = (struct nodelist *) 198 zmalloc(EERROR, sizeof (struct nodelist)); 199 i->name = t; 200 i->live = LIVE; 201 i->nextnode->nextnode = NULL; 202 i->nextnode->inedges = NULL; 203 i->nextnode->live = DEAD; 204 while (*t++ = *s++); 205 return (i); 206} 207 208/* 209 * given that there is a cycle, find some 210 * node in it 211 */ 212static struct nodelist * 213findloop(void) 214{ 215 struct nodelist *i, *j; 216 217 for (i = &firstnode; i->nextnode != NULL; i = i->nextnode) 218 if (i->live == LIVE) 219 break; 220 errmsg(EINFO, "cycle in data"); 221 i = mark(i); 222 if (i == NULL) 223 errmsg(EHALT, gettext("program error")); 224 for (j = &firstnode; j->nextnode != NULL; j = j->nextnode) 225 if (j->live == VISITED) 226 j->live = LIVE; 227 return (i); 228} 229 230/* 231 * depth-first search of LIVE predecessors 232 * to find some element of a cycle; 233 * VISITED is a temporary state recording the 234 * visits of the search 235 */ 236static struct nodelist * 237mark(struct nodelist *i) 238{ 239 struct nodelist *j; 240 struct predlist *t; 241 242 if (i->live == DEAD) 243 return (NULL); 244 if (i->live == VISITED) 245 return (i); 246 i->live = VISITED; 247 for (t = i->inedges; t != NULL; t = t->nextpred) { 248 j = mark(t->pred); 249 if (j != NULL) { 250 (void) fprintf(stderr, "\t%s\n", i->name); 251 return (j); 252 } 253 } 254 return (NULL); 255} 256