src/tsort.c

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