src/tsort.c

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