src/tsort.c

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