1 /* tsort - topological sort.
2 Copyright (C) 1998-2013 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 3 of the License, or
7 (at your option) any later version.
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, see <http://www.gnu.org/licenses/>. */
17 /* Written by Mark Kettenis <kettenis@phys.uva.nl>. */
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. */
27 #include <sys/types.h>
30 #include "long-options.h"
34 #include "readtokens.h"
37 /* The official name of this program (e.g., no 'g' prefix). */
38 #define PROGRAM_NAME "tsort"
40 #define AUTHORS proper_name ("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 head of the sorted list. */
64 static struct item *head = NULL;
66 /* The tail of the list of 'zeros', strings that have no predecessors. */
67 static struct item *zeros = NULL;
69 /* Used for loop detection. */
70 static struct item *loop = NULL;
72 /* The number of strings to sort. */
73 static size_t n_strings = 0;
78 if (status != EXIT_SUCCESS)
83 Usage: %s [OPTION] [FILE]\n\
84 Write totally ordered list consistent with the partial ordering in FILE.\n\
85 With no FILE, or when FILE is -, read standard input.\n\
88 fputs (HELP_OPTION_DESCRIPTION, stdout);
89 fputs (VERSION_OPTION_DESCRIPTION, stdout);
90 emit_ancillary_info ();
96 /* Create a new item/node for STR. */
98 new_item (const char *str)
100 struct item *k = xmalloc (sizeof *k);
102 k->str = (str ? xstrdup (str): NULL);
103 k->left = k->right = NULL;
106 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
114 /* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
115 *ROOT is NULL. Insert a node/item for STR if not found. Return
116 the node/item found/created for STR.
118 This is done according to Algorithm A (Balanced tree search and
119 insertion) in Donald E. Knuth, The Art of Computer Programming,
120 Volume 3/Searching and Sorting, pages 455--457. */
123 search_item (struct item *root, const char *str)
125 struct item *p, *q, *r, *s, *t;
130 /* Make sure the tree is not empty, since that is what the algorithm
132 if (root->right == NULL)
133 return (root->right = new_item (str));
135 /* A1. Initialize. */
142 a = strcmp (str, p->str);
146 /* A3 & A4. Move left & right. */
157 /* A3 & A4. (continued). */
163 /* A6. Adjust balance factors. */
164 assert (!STREQ (str, s->str));
165 if (strcmp (str, s->str) < 0)
178 assert (!STREQ (str, p->str));
179 if (strcmp (str, p->str) < 0)
191 /* A7. Balancing act. */
192 if (s->balance == 0 || s->balance == -a)
200 /* A8. Single Rotation. */
212 s->balance = r->balance = 0;
216 /* A9. Double rotation. */
238 else if (p->balance == -a)
243 /* A10. Finishing touch. */
252 /* A3 & A4. (continued). */
265 /* Record the fact that J precedes K. */
268 record_relation (struct item *j, struct item *k)
272 if (!STREQ (j->str, k->str))
275 p = xmalloc (sizeof *p);
283 count_items (struct item *unused ATTRIBUTE_UNUSED)
290 scan_zeros (struct item *k)
292 /* Ignore strings that have already been printed. */
293 if (k->count == 0 && k->str)
306 /* Try to detect the loop. If we have detected that K is part of a
307 loop, print the loop on standard error, remove a relation to break
308 the loop, and return true.
310 The loop detection strategy is as follows: Realise that what we're
311 dealing with is essentially a directed graph. If we find an item
312 that is part of a graph that contains a cycle we traverse the graph
313 in backwards direction. In general there is no unique way to do
314 this, but that is no problem. If we encounter an item that we have
315 encountered before, we know that we've found a cycle. All we have
316 to do now is retrace our steps, printing out the items until we
317 encounter that item again. (This is not necessarily the item that
318 we started from originally.) Since the order in which the items
319 are stored in the tree is not related to the specified partial
320 ordering, we may need to walk the tree several times before the
321 loop has completely been constructed. If the loop was found, the
322 global variable LOOP will be NULL. */
325 detect_loop (struct item *k)
329 /* K does not have to be part of a cycle. It is however part of
330 a graph that contains a cycle. */
333 /* Start traversing the graph at K. */
337 struct successor **p = &k->top;
341 if ((*p)->suc == loop)
345 /* We have found a loop. Retrace our steps. */
348 struct item *tmp = loop->qlink;
350 fprintf (stderr, "%s: %s\n", program_name,
353 /* Until we encounter K again. */
356 /* Remove relation. */
362 /* Tidy things up since we might have to
363 detect another loop. */
370 struct item *tmp = loop->qlink;
376 /* Since we have found the loop, stop walking
396 /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
397 Stop when ACTION returns true. */
400 recurse_tree (struct item *root, bool (*action) (struct item *))
402 if (root->left == NULL && root->right == NULL)
403 return (*action) (root);
406 if (root->left != NULL)
407 if (recurse_tree (root->left, action))
409 if ((*action) (root))
411 if (root->right != NULL)
412 if (recurse_tree (root->right, action))
419 /* Walk the tree specified by the head ROOT, calling ACTION for
423 walk_tree (struct item *root, bool (*action) (struct item *))
426 recurse_tree (root->right, action);
429 /* Do a topological sort on FILE. Return true if successful. */
432 tsort (const char *file)
436 struct item *j = NULL;
437 struct item *k = NULL;
438 token_buffer tokenbuffer;
439 bool is_stdin = STREQ (file, "-");
441 /* Intialize the head of the tree will hold the strings we're sorting. */
442 root = new_item (NULL);
444 if (!is_stdin && ! freopen (file, "r", stdin))
445 error (EXIT_FAILURE, errno, "%s", file);
447 fadvise (stdin, FADVISE_SEQUENTIAL);
449 init_tokenbuffer (&tokenbuffer);
453 /* T2. Next Relation. */
454 size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
455 if (len == (size_t) -1)
460 k = search_item (root, tokenbuffer.buffer);
463 /* T3. Record the relation. */
464 record_relation (j, k);
472 error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
475 /* T1. Initialize (N <- n). */
476 walk_tree (root, count_items);
478 while (n_strings > 0)
480 /* T4. Scan for zeros. */
481 walk_tree (root, scan_zeros);
485 struct successor *p = head->top;
487 /* T5. Output front of queue. */
490 /* suppress valgrind "definitely lost" warnings. */
491 void *head_str = (void *) head->str;
494 head->str = NULL; /* Avoid printing the same string twice. */
497 /* T6. Erase relations. */
501 if (p->suc->count == 0)
503 zeros->qlink = p->suc;
510 /* T7. Remove from queue. */
514 /* T8. End of process. */
517 /* The input contains a loop. */
518 error (0, 0, _("%s: input contains a loop:"), file);
521 /* Print the loop and remove a relation to break it. */
523 walk_tree (root, detect_loop);
528 if (fclose (stdin) != 0)
529 error (EXIT_FAILURE, errno, "%s",
530 is_stdin ? _("standard input") : quote (file));
536 main (int argc, char **argv)
540 initialize_main (&argc, &argv);
541 set_program_name (argv[0]);
542 setlocale (LC_ALL, "");
543 bindtextdomain (PACKAGE, LOCALEDIR);
544 textdomain (PACKAGE);
546 atexit (close_stdout);
548 parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, Version,
549 usage, AUTHORS, (char const *) NULL);
550 if (getopt_long (argc, argv, "", NULL, NULL) != -1)
551 usage (EXIT_FAILURE);
553 if (1 < argc - optind)
555 error (0, 0, _("extra operand %s"), quote (argv[optind + 1]));
556 usage (EXIT_FAILURE);
559 ok = tsort (optind == argc ? "-" : argv[optind]);
561 exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);