src/tsort.c

   1 /* tsort - topological sort.
   2    Copyright (C) 1998, 1999 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* Written by Mark Kettenis <kettenis@phys.uva.nl>.  */
  19
  20 /* The topological sort is done according to Algorithm T (Topological
  21    sort) in Donald E. Knuth, The Art of Computer Programming, Volume
  22    1/Fundamental Algorithms, page 262.  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 # include <config.h>
  26 #endif
  27
  28 #include <stdio.h>
  29 #include <assert.h>
  30 #include <getopt.h>
  31
  32 #include "system.h"
  33 #include "long-options.h"
  34 #include "error.h"
  35 #include "readtokens.h"
  36
  37 /* The official name of this program (e.g., no `g' prefix).  */
  38 #define PROGRAM_NAME "tsort"
  39
  40 #define AUTHORS "Mark Kettenis"
  41
  42 /* Token delimiters when reading from a file.  */
  43 #define DELIM " \t\n"
  44
  45 /* Members of the list of successors.  */
  46 struct successor
  47 {
  48   struct item *suc;
  49   struct successor *next;
  50 };
  51
  52 /* Each string is held in core as the head of a list of successors.  */
  53 struct item
  54 {
  55   const char *str;
  56   struct item *left, *right;
  57   int balance;
  58   int count;
  59   struct item *qlink;
  60   struct successor *top;
  61 };
  62
  63 /* The name this program was run with. */
  64 char *program_name;
  65
  66 /* Nonzero if any of the input files are the standard input. */
  67 static int have_read_stdin;
  68
  69 /* The head of the sorted list.  */
  70 static struct item *head = NULL;
  71
  72 /* The tail of the list of `zeros', strings that have no predecessors.  */
  73 static struct item *zeros = NULL;
  74
  75 /* The number of strings to sort.  */
  76 static int n_strings = 0;
  77
  78 static struct option const long_options[] =
  79 {
  80   { NULL, 0, NULL, 0}
  81 };
  82 \f
  83 void
  84 usage (int status)
  85 {
  86   if (status != 0)
  87     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  88              program_name);
  89   else
  90     {
  91       printf (_("\
  92 Usage: %s [OPTION] [FILE]\n\
  93 Write totally ordered list consistent with the partial ordering in FILE.\n\
  94 With no FILE, or when FILE is -, read standard input.\n\
  95 \n\
  96       --help       display this help and exit\n\
  97       --version    output version information and exit\n"),
  98               program_name);
  99       puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
 100     }
 101
 102   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 103 }
 104
 105 /* Create a new item/node for STR.  */
 106 static struct item *
 107 new_item (const char *str)
 108 {
 109   struct item *k = xmalloc (sizeof (struct item));
 110
 111   k->str = (str ? xstrdup (str): NULL);
 112   k->left = k->right = NULL;
 113   k->balance = 0;
 114
 115   /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^).  */
 116   k->count = 0;
 117   k->qlink = NULL;
 118   k->top = NULL;
 119
 120   return k;
 121 }
 122
 123 /* Search binary tree rooted at *ROOT for STR.  Allocate a new tree if
 124    *ROOT is NULL.  Insert a node/item for STR if not found.  Return
 125    the node/item found/created for STR.
 126
 127    This is done according to Algorithm A (Balanced tree search and
 128    insertion) in Donald E. Knuth, The Art of Computer Programming,
 129    Volume 3/Searching and Sorting, pages 455--457.  */
 130
 131 static struct item *
 132 search_item (struct item *root, const char *str)
 133 {
 134   struct item *p, *q, *r, *s, *t;
 135   int a;
 136
 137   assert (root);
 138
 139   /* Make sure the tree is not empty, since that is what the algorithm
 140      below expects.  */
 141   if (root->right == NULL)
 142     return (root->right = new_item (str));
 143
 144   /* A1. Initialize.  */
 145   t = root;
 146   s = p = root->right;
 147
 148   for (;;)
 149     {
 150       /* A2. Compare.  */
 151       a = strcmp (str, p->str);
 152       if (a == 0)
 153         return p;
 154
 155       /* A3 & A4.  Move left & right.  */
 156       if (a < 0)
 157         q = p->left;
 158       else
 159         q = p->right;
 160
 161       if (q == NULL)
 162         {
 163           /* A5. Insert.  */
 164           q = new_item (str);
 165
 166           /* A3 & A4.  (continued).  */
 167           if (a < 0)
 168             p->left = q;
 169           else
 170             p->right = q;
 171
 172           /* A6. Adjust balance factors.  */
 173           assert (!STREQ (str, s->str));
 174           if (strcmp (str, s->str) < 0)
 175             {
 176               r = p = s->left;
 177               a = -1;
 178             }
 179           else
 180             {
 181               r = p = s->right;
 182               a = 1;
 183             }
 184
 185           while (p != q)
 186             {
 187               assert (!STREQ (str, p->str));
 188               if (strcmp (str, p->str) < 0)
 189                 {
 190                   p->balance = -1;
 191                   p = p->left;
 192                 }
 193               else
 194                 {
 195                   p->balance = 1;
 196                   p = p->right;
 197                 }
 198             }
 199
 200           /* A7. Balancing act.  */
 201           if (s->balance == 0 || s->balance == -a)
 202             {
 203               s->balance += a;
 204               return q;
 205             }
 206
 207           if (r->balance == a)
 208             {
 209               /* A8. Single Rotation.  */
 210               p = r;
 211               if (a < 0)
 212                 {
 213                   s->left = r->right;
 214                   r->right = s;
 215                 }
 216               else
 217                 {
 218                   s->right = r->left;
 219                   r->left = s;
 220                 }
 221               s->balance = r->balance = 0;
 222             }
 223           else
 224             {
 225               /* A9. Double rotation.  */
 226               if (a < 0)
 227                 {
 228                   p = r->right;
 229                   r->right = p->left;
 230                   p->left = r;
 231                   s->left = p->right;
 232                   p->right = s;
 233                 }
 234               else
 235                 {
 236                   p = r->left;
 237                   r->left = p->right;
 238                   p->right = r;
 239                   s->right = p->left;
 240                   p->left = s;
 241                 }
 242
 243               s->balance = 0;
 244               r->balance = 0;
 245               if (p->balance == a)
 246                 s->balance = -a;
 247               else if (p->balance == -a)
 248                 r->balance = a;
 249               p->balance = 0;
 250             }
 251
 252           /* A10. Finishing touch.  */
 253           if (s == t->right)
 254             t->right = p;
 255           else
 256             t->left = p;
 257
 258           return q;
 259         }
 260
 261       /* A3 & A4.  (continued).  */
 262       if (q->balance)
 263         {
 264           t = p;
 265           s = q;
 266         }
 267
 268       p = q;
 269     }
 270
 271   /* NOTREACHED */
 272 }
 273
 274 /* Record the fact that J precedes K.  */
 275
 276 static void
 277 record_relation (struct item *j, struct item *k)
 278 {
 279   struct successor *p;
 280
 281   if (!STREQ (j->str, k->str))
 282     {
 283       k->count++;
 284       p = xmalloc (sizeof (struct successor));
 285       p->suc = k;
 286       p->next = j->top;
 287       j->top = p;
 288     }
 289 }
 290
 291 static void
 292 count_items (struct item *k)
 293 {
 294   n_strings++;
 295 }
 296
 297 static void
 298 scan_zeros (struct item *k)
 299 {
 300   if (k->count == 0)
 301     {
 302       if (head == NULL)
 303         head = k;
 304       else
 305         zeros->qlink = k;
 306
 307       zeros = k;
 308     }
 309 }
 310
 311 /* If K is part of a loop, print the loop on standard error, and exit.  */
 312
 313 static void
 314 detect_loop (struct item *k)
 315 {
 316   if (k->count > 0 && k->top)
 317     {
 318       while (k && k->count > 0)
 319         {
 320           k->count = 0;
 321           fprintf (stderr, "%s: %s\n", program_name, k->str);
 322           k = k->top->suc;
 323         }
 324
 325       exit (EXIT_FAILURE);
 326     }
 327 }
 328
 329 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.  */
 330
 331 static void
 332 recurse_tree (struct item *root, void (*action) (struct item *))
 333 {
 334   if (root->left == NULL && root->right == NULL)
 335     (*action) (root);
 336   else
 337     {
 338       if (root->left != NULL)
 339         recurse_tree (root->left, action);
 340       (*action) (root);
 341       if (root->right != NULL)
 342         recurse_tree (root->right, action);
 343     }
 344 }
 345
 346 /* Walk the tree specified by the head ROOT, calling ACTION for
 347    each node.  */
 348
 349 static void
 350 walk_tree (struct item *root, void (*action) (struct item *))
 351 {
 352   if (root->right)
 353     recurse_tree (root->right, action);
 354 }
 355
 356 /* Do a topological sort on FILE.   */
 357
 358 static void
 359 tsort (const char *file)
 360 {
 361   struct item *root;
 362   struct item *j = NULL;
 363   struct item *k = NULL;
 364   register FILE *fp;
 365   token_buffer tokenbuffer;
 366
 367   /* Intialize the head of the tree will hold the strings we're sorting.  */
 368   root = new_item (NULL);
 369
 370   if (STREQ (file, "-"))
 371     {
 372       fp = stdin;
 373       have_read_stdin = 1;
 374     }
 375   else
 376     {
 377       fp = fopen (file, "r");
 378       if (fp == NULL)
 379         error (EXIT_FAILURE, errno, "%s", file);
 380     }
 381
 382   init_tokenbuffer (&tokenbuffer);
 383
 384   while (1)
 385     {
 386       long int len;
 387
 388       /* T2. Next Relation.  */
 389       len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
 390       if (len < 0)
 391         break;
 392
 393       assert (len != 0);
 394
 395       k = search_item (root, tokenbuffer.buffer);
 396       if (j)
 397         {
 398           /* T3. Record the relation.  */
 399           record_relation (j, k);
 400           k = NULL;
 401         }
 402
 403       j = k;
 404     }
 405
 406   /* T1. Initialize (N <- n).  */
 407   walk_tree (root, count_items);
 408
 409   /* T4. Scan for zeros.  */
 410   walk_tree (root, scan_zeros);
 411
 412   while (head)
 413     {
 414       struct successor *p = head->top;
 415
 416       /* T5. Output front of queue.  */
 417       printf ("%s\n", head->str);
 418       n_strings--;
 419
 420       /* T6. Erase relations.  */
 421       while (p)
 422         {
 423           p->suc->count--;
 424           if (p->suc->count == 0)
 425             {
 426               zeros->qlink = p->suc;
 427               zeros = p->suc;
 428             }
 429
 430           p = p->next;
 431         }
 432
 433       /* T7. Remove from queue.  */
 434       head = head->qlink;
 435     }
 436
 437   /* T8.  End of process.  */
 438   assert (n_strings >= 0);
 439   if (n_strings > 0)
 440     {
 441       error (0, 0, _("%s: input contains a loop:"),
 442              (have_read_stdin ? "-" : file));
 443
 444       /* Print out loop.  */
 445       walk_tree (root, detect_loop);
 446
 447       /* Should not happen.  */
 448       error (EXIT_FAILURE, 0, _("could not find loop"));
 449     }
 450 }
 451
 452 int
 453 main (int argc, char **argv)
 454 {
 455   int opt;
 456
 457   program_name = argv[0];
 458   setlocale (LC_ALL, "");
 459   bindtextdomain (PACKAGE, LOCALEDIR);
 460   textdomain (PACKAGE);
 461
 462   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 463                       AUTHORS, usage);
 464
 465   while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
 466     switch (opt)
 467       {
 468       case 0:                   /* long option */
 469         break;
 470       default:
 471         usage (EXIT_FAILURE);
 472       }
 473
 474   have_read_stdin = 0;
 475
 476   if (optind + 1 < argc)
 477     {
 478       error (0, 0, _("only one argument may be specified"));
 479       usage (EXIT_FAILURE);
 480     }
 481
 482   if (optind < argc)
 483     tsort (argv[optind]);
 484   else
 485     tsort ("-");
 486
 487   if (fclose (stdout) == EOF)
 488     error (EXIT_FAILURE, errno, _("write error"));
 489
 490   if (have_read_stdin && fclose (stdin) == EOF)
 491     error (EXIT_FAILURE, errno, _("standard input"));
 492
 493   exit (EXIT_SUCCESS);
 494 }