src/tsort.c

   1 /* tsort - topological sort.
   2    Copyright (C) 1998-2003 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 #include <config.h>
  25
  26 #include <stdio.h>
  27 #include <assert.h>
  28 #include <getopt.h>
  29 #include <sys/types.h>
  30
  31 #include "system.h"
  32 #include "closeout.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 error code to return to the system. */
  70 static int exit_status;
  71
  72 /* The head of the sorted list.  */
  73 static struct item *head = NULL;
  74
  75 /* The tail of the list of `zeros', strings that have no predecessors.  */
  76 static struct item *zeros = NULL;
  77
  78 /* Used for loop detection.  */
  79 static struct item *loop = NULL;
  80
  81 /* The number of strings to sort.  */
  82 static int n_strings = 0;
  83
  84 static struct option const long_options[] =
  85 {
  86   { NULL, 0, NULL, 0}
  87 };
  88 \f
  89 void
  90 usage (int status)
  91 {
  92   if (status != 0)
  93     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  94              program_name);
  95   else
  96     {
  97       printf (_("\
  98 Usage: %s [OPTION] [FILE]\n\
  99 Write totally ordered list consistent with the partial ordering in FILE.\n\
 100 With no FILE, or when FILE is -, read standard input.\n\
 101 \n\
 102 "), program_name);
 103       fputs (HELP_OPTION_DESCRIPTION, stdout);
 104       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 105       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
 106     }
 107
 108   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 109 }
 110
 111 /* Create a new item/node for STR.  */
 112 static struct item *
 113 new_item (const char *str)
 114 {
 115   struct item *k = xmalloc (sizeof (struct item));
 116
 117   k->str = (str ? xstrdup (str): NULL);
 118   k->left = k->right = NULL;
 119   k->balance = 0;
 120
 121   /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^).  */
 122   k->count = 0;
 123   k->qlink = NULL;
 124   k->top = NULL;
 125
 126   return k;
 127 }
 128
 129 /* Search binary tree rooted at *ROOT for STR.  Allocate a new tree if
 130    *ROOT is NULL.  Insert a node/item for STR if not found.  Return
 131    the node/item found/created for STR.
 132
 133    This is done according to Algorithm A (Balanced tree search and
 134    insertion) in Donald E. Knuth, The Art of Computer Programming,
 135    Volume 3/Searching and Sorting, pages 455--457.  */
 136
 137 static struct item *
 138 search_item (struct item *root, const char *str)
 139 {
 140   struct item *p, *q, *r, *s, *t;
 141   int a;
 142
 143   assert (root);
 144
 145   /* Make sure the tree is not empty, since that is what the algorithm
 146      below expects.  */
 147   if (root->right == NULL)
 148     return (root->right = new_item (str));
 149
 150   /* A1. Initialize.  */
 151   t = root;
 152   s = p = root->right;
 153
 154   for (;;)
 155     {
 156       /* A2. Compare.  */
 157       a = strcmp (str, p->str);
 158       if (a == 0)
 159         return p;
 160
 161       /* A3 & A4.  Move left & right.  */
 162       if (a < 0)
 163         q = p->left;
 164       else
 165         q = p->right;
 166
 167       if (q == NULL)
 168         {
 169           /* A5. Insert.  */
 170           q = new_item (str);
 171
 172           /* A3 & A4.  (continued).  */
 173           if (a < 0)
 174             p->left = q;
 175           else
 176             p->right = q;
 177
 178           /* A6. Adjust balance factors.  */
 179           assert (!STREQ (str, s->str));
 180           if (strcmp (str, s->str) < 0)
 181             {
 182               r = p = s->left;
 183               a = -1;
 184             }
 185           else
 186             {
 187               r = p = s->right;
 188               a = 1;
 189             }
 190
 191           while (p != q)
 192             {
 193               assert (!STREQ (str, p->str));
 194               if (strcmp (str, p->str) < 0)
 195                 {
 196                   p->balance = -1;
 197                   p = p->left;
 198                 }
 199               else
 200                 {
 201                   p->balance = 1;
 202                   p = p->right;
 203                 }
 204             }
 205
 206           /* A7. Balancing act.  */
 207           if (s->balance == 0 || s->balance == -a)
 208             {
 209               s->balance += a;
 210               return q;
 211             }
 212
 213           if (r->balance == a)
 214             {
 215               /* A8. Single Rotation.  */
 216               p = r;
 217               if (a < 0)
 218                 {
 219                   s->left = r->right;
 220                   r->right = s;
 221                 }
 222               else
 223                 {
 224                   s->right = r->left;
 225                   r->left = s;
 226                 }
 227               s->balance = r->balance = 0;
 228             }
 229           else
 230             {
 231               /* A9. Double rotation.  */
 232               if (a < 0)
 233                 {
 234                   p = r->right;
 235                   r->right = p->left;
 236                   p->left = r;
 237                   s->left = p->right;
 238                   p->right = s;
 239                 }
 240               else
 241                 {
 242                   p = r->left;
 243                   r->left = p->right;
 244                   p->right = r;
 245                   s->right = p->left;
 246                   p->left = s;
 247                 }
 248
 249               s->balance = 0;
 250               r->balance = 0;
 251               if (p->balance == a)
 252                 s->balance = -a;
 253               else if (p->balance == -a)
 254                 r->balance = a;
 255               p->balance = 0;
 256             }
 257
 258           /* A10. Finishing touch.  */
 259           if (s == t->right)
 260             t->right = p;
 261           else
 262             t->left = p;
 263
 264           return q;
 265         }
 266
 267       /* A3 & A4.  (continued).  */
 268       if (q->balance)
 269         {
 270           t = p;
 271           s = q;
 272         }
 273
 274       p = q;
 275     }
 276
 277   /* NOTREACHED */
 278 }
 279
 280 /* Record the fact that J precedes K.  */
 281
 282 static void
 283 record_relation (struct item *j, struct item *k)
 284 {
 285   struct successor *p;
 286
 287   if (!STREQ (j->str, k->str))
 288     {
 289       k->count++;
 290       p = xmalloc (sizeof (struct successor));
 291       p->suc = k;
 292       p->next = j->top;
 293       j->top = p;
 294     }
 295 }
 296
 297 static int
 298 count_items (struct item *unused ATTRIBUTE_UNUSED)
 299 {
 300   n_strings++;
 301   return 0;
 302 }
 303
 304 static int
 305 scan_zeros (struct item *k)
 306 {
 307   /* Ignore strings that have already been printed.  */
 308   if (k->count == 0 && k->str)
 309     {
 310       if (head == NULL)
 311         head = k;
 312       else
 313         zeros->qlink = k;
 314
 315       zeros = k;
 316     }
 317
 318   return 0;
 319 }
 320
 321 /* Try to detect the loop.  If we have detected that K is part of a
 322    loop, print the loop on standard error, remove a relation to break
 323    the loop, and return non-zero.
 324
 325    The loop detection strategy is as follows: Realise that what we're
 326    dealing with is essentially a directed graph.  If we find an item
 327    that is part of a graph that contains a cycle we traverse the graph
 328    in backwards direction.  In general there is no unique way to do
 329    this, but that is no problem.  If we encounter an item that we have
 330    encountered before, we know that we've found a cycle.  All we have
 331    to do now is retrace our steps, printing out the items until we
 332    encounter that item again.  (This is not necessarily the item that
 333    we started from originally.)  Since the order in which the items
 334    are stored in the tree is not related to the specified partial
 335    ordering, we may need to walk the tree several times before the
 336    loop has completely been constructed.  If the loop was found, the
 337    global variable LOOP will be NULL.  */
 338
 339 static int
 340 detect_loop (struct item *k)
 341 {
 342   if (k->count > 0)
 343     {
 344       /* K does not have to be part of a cycle.  It is however part of
 345          a graph that contains a cycle.  */
 346
 347       if (loop == NULL)
 348         /* Start traversing the graph at K.  */
 349         loop = k;
 350       else
 351         {
 352           struct successor **p = &k->top;
 353
 354           while (*p)
 355             {
 356               if ((*p)->suc == loop)
 357                 {
 358                   if (k->qlink)
 359                     {
 360                       /* We have found a loop.  Retrace our steps.  */
 361                       while (loop)
 362                         {
 363                           struct item *tmp = loop->qlink;
 364
 365                           fprintf (stderr, "%s: %s\n", program_name,
 366                                    loop->str);
 367
 368                           /* Until we encounter K again.  */
 369                           if (loop == k)
 370                             {
 371                               /* Remove relation.  */
 372                               (*p)->suc->count--;
 373                               *p = (*p)->next;
 374                               break;
 375                             }
 376
 377                           /* Tidy things up since we might have to
 378                              detect another loop.  */
 379                           loop->qlink = NULL;
 380                           loop = tmp;
 381                         }
 382
 383                       while (loop)
 384                         {
 385                           struct item *tmp = loop->qlink;
 386
 387                           loop->qlink = NULL;
 388                           loop = tmp;
 389                         }
 390
 391                       /* Since we have found the loop, stop walking
 392                          the tree.  */
 393                       return 1;
 394                     }
 395                   else
 396                     {
 397                       k->qlink = loop;
 398                       loop = k;
 399                       break;
 400                     }
 401                 }
 402
 403               p = &(*p)->next;
 404             }
 405         }
 406     }
 407
 408   return 0;
 409 }
 410
 411 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
 412    Stop when ACTION returns non-zero.  */
 413
 414 static int
 415 recurse_tree (struct item *root, int (*action) (struct item *))
 416 {
 417   if (root->left == NULL && root->right == NULL)
 418     return (*action) (root);
 419   else
 420     {
 421       if (root->left != NULL)
 422         if (recurse_tree (root->left, action))
 423           return 1;
 424       if ((*action) (root))
 425         return 1;
 426       if (root->right != NULL)
 427         if (recurse_tree (root->right, action))
 428           return 1;
 429     }
 430
 431   return 0;
 432 }
 433
 434 /* Walk the tree specified by the head ROOT, calling ACTION for
 435    each node.  */
 436
 437 static void
 438 walk_tree (struct item *root, int (*action) (struct item *))
 439 {
 440   if (root->right)
 441     recurse_tree (root->right, action);
 442 }
 443
 444 /* Do a topological sort on FILE.   */
 445
 446 static void
 447 tsort (const char *file)
 448 {
 449   struct item *root;
 450   struct item *j = NULL;
 451   struct item *k = NULL;
 452   register FILE *fp;
 453   token_buffer tokenbuffer;
 454
 455   /* Intialize the head of the tree will hold the strings we're sorting.  */
 456   root = new_item (NULL);
 457
 458   if (STREQ (file, "-"))
 459     {
 460       fp = stdin;
 461       have_read_stdin = 1;
 462     }
 463   else
 464     {
 465       fp = fopen (file, "r");
 466       if (fp == NULL)
 467         error (EXIT_FAILURE, errno, "%s", file);
 468     }
 469
 470   init_tokenbuffer (&tokenbuffer);
 471
 472   while (1)
 473     {
 474       long int len;
 475
 476       /* T2. Next Relation.  */
 477       len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
 478       if (len < 0)
 479         break;
 480
 481       assert (len != 0);
 482
 483       k = search_item (root, tokenbuffer.buffer);
 484       if (j)
 485         {
 486           /* T3. Record the relation.  */
 487           record_relation (j, k);
 488           k = NULL;
 489         }
 490
 491       j = k;
 492     }
 493
 494   if (k != NULL)
 495     error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
 496            file);
 497
 498   /* T1. Initialize (N <- n).  */
 499   walk_tree (root, count_items);
 500
 501   while (n_strings > 0)
 502     {
 503       /* T4. Scan for zeros.  */
 504       walk_tree (root, scan_zeros);
 505
 506       while (head)
 507         {
 508           struct successor *p = head->top;
 509
 510           /* T5. Output front of queue.  */
 511           printf ("%s\n", head->str);
 512           head->str = NULL;     /* Avoid printing the same string twice.  */
 513           n_strings--;
 514
 515           /* T6. Erase relations.  */
 516           while (p)
 517             {
 518               p->suc->count--;
 519               if (p->suc->count == 0)
 520                 {
 521                   zeros->qlink = p->suc;
 522                   zeros = p->suc;
 523                 }
 524
 525               p = p->next;
 526             }
 527
 528           /* T7. Remove from queue.  */
 529           head = head->qlink;
 530         }
 531
 532       /* T8.  End of process.  */
 533       assert (n_strings >= 0);
 534       if (n_strings > 0)
 535         {
 536           /* The input contains a loop.  */
 537           error (0, 0, _("%s: input contains a loop:"), file);
 538           exit_status = 1;
 539
 540           /* Print the loop and remove a relation to break it.  */
 541           do
 542             walk_tree (root, detect_loop);
 543           while (loop);
 544         }
 545     }
 546 }
 547
 548 int
 549 main (int argc, char **argv)
 550 {
 551   int opt;
 552
 553   initialize_main (&argc, &argv);
 554   program_name = argv[0];
 555   setlocale (LC_ALL, "");
 556   bindtextdomain (PACKAGE, LOCALEDIR);
 557   textdomain (PACKAGE);
 558
 559   atexit (close_stdout);
 560
 561   exit_status = 0;
 562
 563   parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION,
 564                       AUTHORS, usage);
 565
 566   while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
 567     switch (opt)
 568       {
 569       case 0:                   /* long option */
 570         break;
 571       default:
 572         usage (EXIT_FAILURE);
 573       }
 574
 575   have_read_stdin = 0;
 576
 577   if (1 < argc - optind)
 578     {
 579       error (0, 0, _("only one argument may be specified"));
 580       usage (EXIT_FAILURE);
 581     }
 582
 583   tsort (optind == argc ? "-" : argv[optind]);
 584
 585   if (have_read_stdin && fclose (stdin) == EOF)
 586     error (EXIT_FAILURE, errno, _("standard input"));
 587
 588   exit (exit_status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 589 }