src/tsort.c

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