src/tsort.c

   1 /* tsort - topological sort.
   2    Copyright (C) 1998, 1999 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 #ifdef HAVE_CONFIG_H
  25 # include <config.h>
  26 #endif
  27
  28 #include <assert.h>
  29 #include <getopt.h>
  30 #include <stdio.h>
  31
  32 #include "long-options.h"
  33 #include "system.h"
  34 #include "error.h"
  35
  36 char *xstrdup ();
  37
  38 /* Members of the list of successors.  */
  39 struct successor
  40 {
  41   struct item *suc;
  42   struct successor *next;
  43 };
  44
  45 /* Each string is held in core as the head of a list of successors.  */
  46 struct item
  47 {
  48   const char *str;
  49   struct item *left, *right;
  50   int balance;
  51   int count;
  52   struct item *qlink;
  53   struct successor *top;
  54 };
  55
  56 /* The name this program was run with. */
  57 char *program_name;
  58
  59 /* Nonzero if any of the input files are the standard input. */
  60 static int have_read_stdin;
  61
  62 /* The head of the sorted list.  */
  63 static struct item *head;
  64
  65 /* A scratch variable.  */
  66 static struct item *r = NULL;
  67
  68 /* The number of strings to sort.  */
  69 static int n = 0;
  70
  71 static struct option const long_options[] =
  72 {
  73   { NULL, 0, NULL, 0}
  74 };
  75 \f
  76 static void
  77 usage (int status)
  78 {
  79   if (status != 0)
  80     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  81              program_name);
  82   else
  83     {
  84       printf (_("\
  85 Usage: %s [OPTION] [FILE]\n\
  86 Write totally ordered list consistent with the partial ordering in FILE.\n\
  87 With no FILE, or when FILE is -, read standard input.\n\
  88 \n\
  89       --help       display this help and exit\n\
  90       --version    output version information and exit\n"),
  91               program_name);
  92       puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
  93     }
  94
  95   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
  96 }
  97
  98 /* Create a new item/node for STR.  */
  99 static struct item *
 100 new_item (const char *str)
 101 {
 102   struct item *k = xmalloc (sizeof (struct item));
 103
 104   k->str = (str ? xstrdup (str): NULL);
 105   k->left = k->right = NULL;
 106   k->balance = 0;
 107
 108   /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^).  */
 109   k->count = 0;
 110   k->qlink = NULL;
 111   k->top = NULL;
 112
 113   return k;
 114 }
 115
 116 /* Search binary tree rooted at *ROOT for STR.  Allocate a new tree if
 117    *ROOT is NULL.  Insert a node/item for STR if not found.  Return
 118    the node/item found/created for STR.
 119
 120    This is done according to Algorithm A (Balanced tree search and
 121    insertion) in Donald E. Knuth, The Art of Computer Programming,
 122    Volume 3/Searching and Sorting, pages 455--457.  */
 123
 124 static struct item *
 125 search_item (struct item *root, const char *str)
 126 {
 127   struct item *p, *q, *r, *s, *t;
 128   int a;
 129
 130   assert (root);
 131
 132   /* Make sure the tree is not empty, since that is what the algorithm
 133      below expects.  */
 134   if (root->right == NULL)
 135     return (root->right = new_item (str));
 136
 137   /* A1. Initialize.  */
 138   t = root;
 139   s = p = root->right;
 140
 141   for (;;)
 142     {
 143       /* A2. Compare.  */
 144       a = strcmp (str, p->str);
 145       if (a == 0)
 146         return p;
 147
 148       /* A3 & A4.  Move left & right.  */
 149       if (a < 0)
 150         q = p->left;
 151       else
 152         q = p->right;
 153
 154       if (q == NULL)
 155         {
 156           /* A5. Insert.  */
 157           q = new_item (str);
 158
 159           /* A3 & A4.  (continued).  */
 160           if (a < 0)
 161             p->left = q;
 162           else
 163             p->right = q;
 164
 165           /* A6. Adjust balance factors.  */
 166           assert (strcmp (str, s->str));
 167           if (strcmp (str, s->str) < 0)
 168             {
 169               r = p = s->left;
 170               a = -1;
 171             }
 172           else
 173             {
 174               r = p = s->right;
 175               a = +1;
 176             }
 177
 178           while (p != q)
 179             {
 180               assert (strcmp (str, p->str));
 181               if (strcmp (str, p->str) < 0)
 182                 {
 183                   p->balance = -1;
 184                   p = p->left;
 185                 }
 186               else
 187                 {
 188                   p->balance = +1;
 189                   p = p->right;
 190                 }
 191             }
 192
 193           /* A7. Balancing act.  */
 194           if (s->balance == 0 || s->balance == -a)
 195             {
 196               s->balance += a;
 197               return q;
 198             }
 199
 200           if (r->balance == a)
 201             {
 202               /* A8. Single Rotation.  */
 203               p = r;
 204               if (a < 0)
 205                 {
 206                   s->left = r->right;
 207                   r->right = s;
 208                 }
 209               else
 210                 {
 211                   s->right = r->left;
 212                   r->left = s;
 213                 }
 214               s->balance = r->balance = 0;
 215             }
 216           else
 217             {
 218               /* A9. Double rotation.  */
 219               if (a < 0)
 220                 {
 221                   p = r->right;
 222                   r->right = p->left;
 223                   p->left = r;
 224                   s->left = p->right;
 225                   p->right = s;
 226                 }
 227               else
 228                 {
 229                   p = r->left;
 230                   r->left = p->right;
 231                   p->right = r;
 232                   s->right = p->left;
 233                   p->left = s;
 234                 }
 235
 236               s->balance = 0;
 237               r->balance = 0;
 238               if (p->balance == a)
 239                 s->balance = -a;
 240               else if (p->balance == -a)
 241                 r->balance = a;
 242               p->balance = 0;
 243             }
 244
 245           /* A10. Finishing touch.  */
 246           if (s == t->right)
 247             t->right = p;
 248           else
 249             t->left = p;
 250
 251           return q;
 252         }
 253
 254       /* A3 & A4.  (continued).  */
 255       if (q->balance)
 256         {
 257           t = p;
 258           s = q;
 259         }
 260
 261       p = q;
 262     }
 263
 264   /* NOTREACHED */
 265 }
 266
 267 /* Record the fact that J precedes K.  */
 268
 269 static void
 270 record_relation (struct item *j, struct item *k)
 271 {
 272   struct successor *p;
 273
 274   if (strcmp (j->str, k->str))
 275     {
 276       k->count++;
 277       p = xmalloc (sizeof (struct successor));
 278       p->suc = k;
 279       p->next = j->top;
 280       j->top = p;
 281     }
 282 }
 283
 284 static void
 285 count_items (struct item *k)
 286 {
 287   n++;
 288 }
 289
 290 static void
 291 scan_zeros (struct item *k)
 292 {
 293   if (k->count == 0)
 294     {
 295       if (r == NULL)
 296         head = k;
 297       else
 298         r->qlink = k;
 299
 300       r = k;
 301     }
 302 }
 303
 304 /* If K is part of a loop, print the loop on standard error, and exit.  */
 305
 306 static void
 307 detect_loop (struct item *k)
 308 {
 309   if (k->count > 0)
 310     {
 311       while (k && k->count > 0)
 312         {
 313           k->count = 0;
 314           fprintf (stderr, "%s: %s\n", program_name, k->str);
 315           k = k->top->suc;
 316         }
 317
 318       exit (EXIT_FAILURE);
 319     }
 320 }
 321
 322 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.  */
 323
 324 static void
 325 recurse_tree (struct item *root, void (*action) (struct item *))
 326 {
 327   if (root->left == NULL && root->right == NULL)
 328     (*action) (root);
 329   else
 330     {
 331       if (root->left != NULL)
 332         recurse_tree (root->left, action);
 333       (*action) (root);
 334       if (root->right != NULL)
 335         recurse_tree (root->right, action);
 336     }
 337 }
 338
 339 /* Walk the tree specified by the head ROOT, calling ACTION for
 340    each node.  */
 341
 342 static void
 343 walk_tree (struct item *root, void (*action) (struct item *))
 344 {
 345   if (root->right)
 346     recurse_tree (root->right, action);
 347 }
 348
 349 /* The following function was copied from getline.c, but with these changes:
 350    - Read up to and not including any "whitespace" character.
 351    - Remove unused argument, OFFSET.
 352    - Use xmalloc and xrealloc instead of malloc and realloc.
 353    - Declare this function static.  */
 354
 355 /* Always add at least this many bytes when extending the buffer.  */
 356 #define MIN_CHUNK 64
 357
 358 /* Read up to (and not including) any "whitespace" character from STREAM
 359    into *LINEPTR (and null-terminate it). *LINEPTR is a pointer returned
 360    from xmalloc (or NULL), pointing to *N characters of space.  It is
 361    xrealloc'd as necessary.  Return the number of characters read (not
 362    including the null terminator), or -1 on error or EOF.  */
 363
 364 static int
 365 getstr (char **lineptr, int *n, FILE *stream)
 366 {
 367   int nchars_avail;             /* Allocated but unused chars in *LINEPTR.  */
 368   char *read_pos;               /* Where we're reading into *LINEPTR. */
 369
 370   if (!lineptr || !n || !stream)
 371     return -1;
 372
 373   if (!*lineptr)
 374     {
 375       *n = MIN_CHUNK;
 376       *lineptr = (char *) xmalloc (*n);
 377       if (!*lineptr)
 378         return -1;
 379     }
 380
 381   nchars_avail = *n;
 382   read_pos = *lineptr;
 383
 384   for (;;)
 385     {
 386       register int c = getc (stream);
 387
 388       /* We always want at least one char left in the buffer, since we
 389          always (unless we get an error while reading the first char)
 390          NUL-terminate the line buffer.  */
 391
 392       assert (*n - nchars_avail == read_pos - *lineptr);
 393       if (nchars_avail < 1)
 394         {
 395           if (*n > MIN_CHUNK)
 396             *n *= 2;
 397           else
 398             *n += MIN_CHUNK;
 399
 400           nchars_avail = *n + *lineptr - read_pos;
 401           *lineptr = xrealloc (*lineptr, *n);
 402           if (!*lineptr)
 403             return -1;
 404           read_pos = *n - nchars_avail + *lineptr;
 405           assert (*n - nchars_avail == read_pos - *lineptr);
 406         }
 407
 408       if (feof (stream) || ferror (stream))
 409         {
 410           /* Return partial line, if any.  */
 411           if (read_pos == *lineptr)
 412             return -1;
 413           else
 414             break;
 415         }
 416
 417       if (ISSPACE (c))
 418         /* Return the string.  */
 419         break;
 420
 421       *read_pos++ = c;
 422       nchars_avail--;
 423     }
 424
 425   /* Done - NUL terminate and return the number of chars read.  */
 426   *read_pos = '\0';
 427
 428   return read_pos - *lineptr;
 429 }
 430
 431
 432 static void
 433 sort (const char *file)
 434 {
 435   struct item *root;
 436   struct item *j = NULL;
 437   struct item *k = NULL;
 438   register FILE *fp;
 439   char *str = NULL;
 440   size_t size = 0;
 441   int len;
 442
 443   /* Intialize the head of the tree will hold the strings we're sorting.  */
 444   root = new_item (NULL);
 445
 446   if (STREQ (file, "-"))
 447     {
 448       fp = stdin;
 449       have_read_stdin = 1;
 450     }
 451   else
 452     {
 453       fp = fopen (file, "r");
 454       if (fp == NULL)
 455         error (EXIT_FAILURE, errno, "%s", file);
 456     }
 457
 458   while (1)
 459     {
 460       /* T2. Next Relation.  */
 461       len = getstr (&str, &size, fp);
 462       if (len < 0)
 463         break;
 464
 465       assert (len != 0);
 466
 467       k = search_item (root, str);
 468       if (j)
 469         {
 470           /* T3. Record the relation.  */
 471           record_relation (j, k);
 472           k = NULL;
 473         }
 474
 475       j = k;
 476     }
 477
 478   /* T1. Initialize (N <- n).  */
 479   walk_tree (root, count_items);
 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       printf ("%s\n", head->str);
 490       n--;
 491
 492       /* T6. Erase relations.  */
 493       while (p)
 494         {
 495           p->suc->count--;
 496           if (p->suc->count == 0)
 497             {
 498               r->qlink = p->suc;
 499               r = p->suc;
 500             }
 501
 502           p = p->next;
 503         }
 504
 505       /* T7. Remove from queue.  */
 506       head = head->qlink;
 507     }
 508
 509   /* T8.  End of process.  */
 510   assert (n >= 0);
 511   if (n > 0)
 512     {
 513       if (have_read_stdin)
 514         fprintf (stderr, _("%s: input contains a loop:\n"), program_name);
 515       else
 516         fprintf (stderr, _("%s: %s: input contains a loop:\n"),
 517                  program_name, file);
 518
 519       /* Print out loop.  */
 520       walk_tree (root, detect_loop);
 521
 522       /* Should not happen.  */
 523       error (EXIT_FAILURE, 0, _("%s: could not find loop"));
 524     }
 525 }
 526
 527
 528 int
 529 main (int argc, char **argv)
 530 {
 531   int opt;
 532
 533   program_name = argv[0];
 534   setlocale (LC_ALL, "");
 535   bindtextdomain (PACKAGE, LOCALEDIR);
 536   textdomain (PACKAGE);
 537
 538   parse_long_options (argc, argv, "tsort", GNU_PACKAGE, VERSION, usage);
 539
 540   while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
 541     switch (opt)
 542       {
 543       case 0:                   /* long option */
 544         break;
 545       default:
 546         usage (EXIT_FAILURE);
 547       }
 548
 549   have_read_stdin = 0;
 550
 551   if (optind + 1 < argc)
 552     {
 553       error (0, 0, _("only one argument may be specified"));
 554       usage (EXIT_FAILURE);
 555     }
 556
 557   if (optind < argc)
 558     sort (argv[optind]);
 559   else
 560     sort ("-");
 561
 562   if (fclose (stdout) == EOF)
 563     error (EXIT_FAILURE, errno, _("write error"));
 564
 565   if (have_read_stdin && fclose (stdin) == EOF)
 566     error (EXIT_FAILURE, errno, _("standard input"));
 567
 568   exit (EXIT_SUCCESS);
 569 }