usr/src/cmd/sgs/tsort/common/tsort.c

   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
  60 static
  61 struct 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  */
  72 struct predlist {
  73         struct predlist *nextpred;
  74         struct nodelist *pred;
  75 };
  76
  77 static struct nodelist *index(char *s);
  78 static struct nodelist *findloop(void);
  79 static struct nodelist *mark(struct nodelist *i);
  80 static int present(struct nodelist *i, struct nodelist *j);
  81 static int anypred(struct nodelist *i);
  82
  83 /*
  84  *      the first for loop reads in the graph,
  85  *      the second prints out the ordering
  86  */
  87 int
  88 main(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  */
 161 static int
 162 present(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  */
 174 static int
 175 anypred(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  */
 187 static struct nodelist *
 188 index(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  */
 212 static struct nodelist *
 213 findloop(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  */
 236 static struct nodelist *
 237 mark(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 }