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