1 /* tsort - topological sort.
2 Copyright (C) 1998-2004 Free Software Foundation, Inc.
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)
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.
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. */
18 /* Written by Mark Kettenis <kettenis@phys.uva.nl>. */
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. */
29 #include <sys/types.h>
32 #include "long-options.h"
35 #include "readtokens.h"
37 /* The official name of this program (e.g., no `g' prefix). */
38 #define PROGRAM_NAME "tsort"
40 #define AUTHORS "Mark Kettenis"
42 /* Token delimiters when reading from a file. */
45 /* Members of the list of successors. */
49 struct successor *next;
52 /* Each string is held in core as the head of a list of successors. */
56 struct item *left, *right;
57 int balance; /* -1, 0, or +1 */
60 struct successor *top;
63 /* The name this program was run with. */
66 /* True if any of the input files are the standard input. */
67 static bool have_read_stdin;
69 /* The head of the sorted list. */
70 static struct item *head = NULL;
72 /* The tail of the list of `zeros', strings that have no predecessors. */
73 static struct item *zeros = NULL;
75 /* Used for loop detection. */
76 static struct item *loop = NULL;
78 /* The number of strings to sort. */
79 static size_t n_strings = 0;
84 if (status != EXIT_SUCCESS)
85 fprintf (stderr, _("Try `%s --help' for more information.\n"),
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\
95 fputs (HELP_OPTION_DESCRIPTION, stdout);
96 fputs (VERSION_OPTION_DESCRIPTION, stdout);
97 printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
103 /* Create a new item/node for STR. */
105 new_item (const char *str)
107 struct item *k = xmalloc (sizeof *k);
109 k->str = (str ? xstrdup (str): NULL);
110 k->left = k->right = NULL;
113 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
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.
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. */
130 search_item (struct item *root, const char *str)
132 struct item *p, *q, *r, *s, *t;
137 /* Make sure the tree is not empty, since that is what the algorithm
139 if (root->right == NULL)
140 return (root->right = new_item (str));
142 /* A1. Initialize. */
149 a = strcmp (str, p->str);
153 /* A3 & A4. Move left & right. */
164 /* A3 & A4. (continued). */
170 /* A6. Adjust balance factors. */
171 assert (!STREQ (str, s->str));
172 if (strcmp (str, s->str) < 0)
185 assert (!STREQ (str, p->str));
186 if (strcmp (str, p->str) < 0)
198 /* A7. Balancing act. */
199 if (s->balance == 0 || s->balance == -a)
207 /* A8. Single Rotation. */
219 s->balance = r->balance = 0;
223 /* A9. Double rotation. */
245 else if (p->balance == -a)
250 /* A10. Finishing touch. */
259 /* A3 & A4. (continued). */
272 /* Record the fact that J precedes K. */
275 record_relation (struct item *j, struct item *k)
279 if (!STREQ (j->str, k->str))
282 p = xmalloc (sizeof *p);
290 count_items (struct item *unused ATTRIBUTE_UNUSED)
297 scan_zeros (struct item *k)
299 /* Ignore strings that have already been printed. */
300 if (k->count == 0 && k->str)
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.
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. */
332 detect_loop (struct item *k)
336 /* K does not have to be part of a cycle. It is however part of
337 a graph that contains a cycle. */
340 /* Start traversing the graph at K. */
344 struct successor **p = &k->top;
348 if ((*p)->suc == loop)
352 /* We have found a loop. Retrace our steps. */
355 struct item *tmp = loop->qlink;
357 fprintf (stderr, "%s: %s\n", program_name,
360 /* Until we encounter K again. */
363 /* Remove relation. */
369 /* Tidy things up since we might have to
370 detect another loop. */
377 struct item *tmp = loop->qlink;
383 /* Since we have found the loop, stop walking
403 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
404 Stop when ACTION returns true. */
407 recurse_tree (struct item *root, bool (*action) (struct item *))
409 if (root->left == NULL && root->right == NULL)
410 return (*action) (root);
413 if (root->left != NULL)
414 if (recurse_tree (root->left, action))
416 if ((*action) (root))
418 if (root->right != NULL)
419 if (recurse_tree (root->right, action))
426 /* Walk the tree specified by the head ROOT, calling ACTION for
430 walk_tree (struct item *root, bool (*action) (struct item *))
433 recurse_tree (root->right, action);
436 /* Do a topological sort on FILE. Return true if successful. */
439 tsort (const char *file)
443 struct item *j = NULL;
444 struct item *k = NULL;
446 token_buffer tokenbuffer;
448 /* Intialize the head of the tree will hold the strings we're sorting. */
449 root = new_item (NULL);
451 if (STREQ (file, "-"))
454 have_read_stdin = true;
458 fp = fopen (file, "r");
460 error (EXIT_FAILURE, errno, "%s", file);
463 init_tokenbuffer (&tokenbuffer);
467 /* T2. Next Relation. */
468 size_t len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
469 if (len == (size_t) -1)
474 k = search_item (root, tokenbuffer.buffer);
477 /* T3. Record the relation. */
478 record_relation (j, k);
486 error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
489 /* T1. Initialize (N <- n). */
490 walk_tree (root, count_items);
492 while (n_strings > 0)
494 /* T4. Scan for zeros. */
495 walk_tree (root, scan_zeros);
499 struct successor *p = head->top;
501 /* T5. Output front of queue. */
502 printf ("%s\n", head->str);
503 head->str = NULL; /* Avoid printing the same string twice. */
506 /* T6. Erase relations. */
510 if (p->suc->count == 0)
512 zeros->qlink = p->suc;
519 /* T7. Remove from queue. */
523 /* T8. End of process. */
526 /* The input contains a loop. */
527 error (0, 0, _("%s: input contains a loop:"), file);
530 /* Print the loop and remove a relation to break it. */
532 walk_tree (root, detect_loop);
541 main (int argc, char **argv)
545 initialize_main (&argc, &argv);
546 program_name = argv[0];
547 setlocale (LC_ALL, "");
548 bindtextdomain (PACKAGE, LOCALEDIR);
549 textdomain (PACKAGE);
551 atexit (close_stdout);
553 parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION,
554 usage, AUTHORS, (char const *) NULL);
555 if (getopt (argc, argv, "") != -1)
556 usage (EXIT_FAILURE);
558 have_read_stdin = false;
560 if (1 < argc - optind)
562 error (0, 0, _("extra operand %s"), quote (argv[optind + 1]));
563 usage (EXIT_FAILURE);
566 ok = tsort (optind == argc ? "-" : argv[optind]);
568 if (have_read_stdin && fclose (stdin) == EOF)
569 error (EXIT_FAILURE, errno, _("standard input"));
571 exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);