diff options
Diffstat (limited to 'src/tsort.c')
| -rw-r--r-- | src/tsort.c | 476 |
1 files changed, 242 insertions, 234 deletions
diff --git a/src/tsort.c b/src/tsort.c index 9393232..980abcd 100644 --- a/src/tsort.c +++ b/src/tsort.c @@ -1,10 +1,10 @@ /* tsort - topological sort. - Copyright (C) 1998-2005 Free Software Foundation, Inc. + Copyright (C) 1998-2016 Free Software Foundation, Inc. - This program is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -12,8 +12,7 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + along with this program. If not, see <http://www.gnu.org/licenses/>. */ /* Written by Mark Kettenis <kettenis@phys.uva.nl>. */ @@ -23,7 +22,6 @@ #include <config.h> -#include <stdio.h> #include <assert.h> #include <getopt.h> #include <sys/types.h> @@ -31,13 +29,15 @@ #include "system.h" #include "long-options.h" #include "error.h" -#include "quote.h" +#include "fadvise.h" #include "readtokens.h" +#include "stdio--.h" +#include "quote.h" -/* The official name of this program (e.g., no `g' prefix). */ +/* The official name of this program (e.g., no 'g' prefix). */ #define PROGRAM_NAME "tsort" -#define AUTHORS "Mark Kettenis" +#define AUTHORS proper_name ("Mark Kettenis") /* Token delimiters when reading from a file. */ #define DELIM " \t\n" @@ -60,13 +60,10 @@ struct item struct successor *top; }; -/* The name this program was run with. */ -char *program_name; - /* The head of the sorted list. */ static struct item *head = NULL; -/* The tail of the list of `zeros', strings that have no predecessors. */ +/* The tail of the list of 'zeros', strings that have no predecessors. */ static struct item *zeros = NULL; /* Used for loop detection. */ @@ -74,24 +71,27 @@ static struct item *loop = NULL; /* The number of strings to sort. */ static size_t n_strings = 0; - + void usage (int status) { if (status != EXIT_SUCCESS) - fprintf (stderr, _("Try `%s --help' for more information.\n"), - program_name); + emit_try_help (); else { printf (_("\ Usage: %s [OPTION] [FILE]\n\ Write totally ordered list consistent with the partial ordering in FILE.\n\ -With no FILE, or when FILE is -, read standard input.\n\ -\n\ "), program_name); + + emit_stdin_note (); + + fputs (_("\ +\n\ +"), stdout); fputs (HELP_OPTION_DESCRIPTION, stdout); fputs (VERSION_OPTION_DESCRIPTION, stdout); - printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT); + emit_ancillary_info (PROGRAM_NAME); } exit (status); @@ -140,125 +140,125 @@ search_item (struct item *root, const char *str) t = root; s = p = root->right; - for (;;) + while (true) { /* A2. Compare. */ a = strcmp (str, p->str); if (a == 0) - return p; + return p; /* A3 & A4. Move left & right. */ if (a < 0) - q = p->left; + q = p->left; else - q = p->right; + q = p->right; if (q == NULL) - { - /* A5. Insert. */ - q = new_item (str); - - /* A3 & A4. (continued). */ - if (a < 0) - p->left = q; - else - p->right = q; - - /* A6. Adjust balance factors. */ - assert (!STREQ (str, s->str)); - if (strcmp (str, s->str) < 0) - { - r = p = s->left; - a = -1; - } - else - { - r = p = s->right; - a = 1; - } - - while (p != q) - { - assert (!STREQ (str, p->str)); - if (strcmp (str, p->str) < 0) - { - p->balance = -1; - p = p->left; - } - else - { - p->balance = 1; - p = p->right; - } - } - - /* A7. Balancing act. */ - if (s->balance == 0 || s->balance == -a) - { - s->balance += a; - return q; - } - - if (r->balance == a) - { - /* A8. Single Rotation. */ - p = r; - if (a < 0) - { - s->left = r->right; - r->right = s; - } - else - { - s->right = r->left; - r->left = s; - } - s->balance = r->balance = 0; - } - else - { - /* A9. Double rotation. */ - if (a < 0) - { - p = r->right; - r->right = p->left; - p->left = r; - s->left = p->right; - p->right = s; - } - else - { - p = r->left; - r->left = p->right; - p->right = r; - s->right = p->left; - p->left = s; - } - - s->balance = 0; - r->balance = 0; - if (p->balance == a) - s->balance = -a; - else if (p->balance == -a) - r->balance = a; - p->balance = 0; - } - - /* A10. Finishing touch. */ - if (s == t->right) - t->right = p; - else - t->left = p; - - return q; - } + { + /* A5. Insert. */ + q = new_item (str); + + /* A3 & A4. (continued). */ + if (a < 0) + p->left = q; + else + p->right = q; + + /* A6. Adjust balance factors. */ + assert (!STREQ (str, s->str)); + if (strcmp (str, s->str) < 0) + { + r = p = s->left; + a = -1; + } + else + { + r = p = s->right; + a = 1; + } + + while (p != q) + { + assert (!STREQ (str, p->str)); + if (strcmp (str, p->str) < 0) + { + p->balance = -1; + p = p->left; + } + else + { + p->balance = 1; + p = p->right; + } + } + + /* A7. Balancing act. */ + if (s->balance == 0 || s->balance == -a) + { + s->balance += a; + return q; + } + + if (r->balance == a) + { + /* A8. Single Rotation. */ + p = r; + if (a < 0) + { + s->left = r->right; + r->right = s; + } + else + { + s->right = r->left; + r->left = s; + } + s->balance = r->balance = 0; + } + else + { + /* A9. Double rotation. */ + if (a < 0) + { + p = r->right; + r->right = p->left; + p->left = r; + s->left = p->right; + p->right = s; + } + else + { + p = r->left; + r->left = p->right; + p->right = r; + s->right = p->left; + p->left = s; + } + + s->balance = 0; + r->balance = 0; + if (p->balance == a) + s->balance = -a; + else if (p->balance == -a) + r->balance = a; + p->balance = 0; + } + + /* A10. Finishing touch. */ + if (s == t->right) + t->right = p; + else + t->left = p; + + return q; + } /* A3 & A4. (continued). */ if (q->balance) - { - t = p; - s = q; - } + { + t = p; + s = q; + } p = q; } @@ -284,7 +284,7 @@ record_relation (struct item *j, struct item *k) } static bool -count_items (struct item *unused ATTRIBUTE_UNUSED) +count_items (struct item *unused _GL_UNUSED) { n_strings++; return false; @@ -297,9 +297,9 @@ scan_zeros (struct item *k) if (k->count == 0 && k->str) { if (head == NULL) - head = k; + head = k; else - zeros->qlink = k; + zeros->qlink = k; zeros = k; } @@ -331,67 +331,66 @@ detect_loop (struct item *k) if (k->count > 0) { /* K does not have to be part of a cycle. It is however part of - a graph that contains a cycle. */ + a graph that contains a cycle. */ if (loop == NULL) - /* Start traversing the graph at K. */ - loop = k; + /* Start traversing the graph at K. */ + loop = k; else - { - struct successor **p = &k->top; - - while (*p) - { - if ((*p)->suc == loop) - { - if (k->qlink) - { - /* We have found a loop. Retrace our steps. */ - while (loop) - { - struct item *tmp = loop->qlink; - - fprintf (stderr, "%s: %s\n", program_name, - loop->str); - - /* Until we encounter K again. */ - if (loop == k) - { - /* Remove relation. */ - (*p)->suc->count--; - *p = (*p)->next; - break; - } - - /* Tidy things up since we might have to + { + struct successor **p = &k->top; + + while (*p) + { + if ((*p)->suc == loop) + { + if (k->qlink) + { + /* We have found a loop. Retrace our steps. */ + while (loop) + { + struct item *tmp = loop->qlink; + + error (0, 0, "%s", (loop->str)); + + /* Until we encounter K again. */ + if (loop == k) + { + /* Remove relation. */ + (*p)->suc->count--; + *p = (*p)->next; + break; + } + + /* Tidy things up since we might have to detect another loop. */ - loop->qlink = NULL; - loop = tmp; - } + loop->qlink = NULL; + loop = tmp; + } - while (loop) - { - struct item *tmp = loop->qlink; + while (loop) + { + struct item *tmp = loop->qlink; - loop->qlink = NULL; - loop = tmp; - } + loop->qlink = NULL; + loop = tmp; + } - /* Since we have found the loop, stop walking + /* Since we have found the loop, stop walking the tree. */ - return true; - } - else - { - k->qlink = loop; - loop = k; - break; - } - } - - p = &(*p)->next; - } - } + return true; + } + else + { + k->qlink = loop; + loop = k; + break; + } + } + + p = &(*p)->next; + } + } } return false; @@ -408,13 +407,13 @@ recurse_tree (struct item *root, bool (*action) (struct item *)) else { if (root->left != NULL) - if (recurse_tree (root->left, action)) - return true; + if (recurse_tree (root->left, action)) + return true; if ((*action) (root)) - return true; + return true; if (root->right != NULL) - if (recurse_tree (root->right, action)) - return true; + if (recurse_tree (root->right, action)) + return true; } return false; @@ -446,7 +445,9 @@ tsort (const char *file) root = new_item (NULL); if (!is_stdin && ! freopen (file, "r", stdin)) - error (EXIT_FAILURE, errno, "%s", file); + error (EXIT_FAILURE, errno, "%s", quotef (file)); + + fadvise (stdin, FADVISE_SEQUENTIAL); init_tokenbuffer (&tokenbuffer); @@ -455,24 +456,24 @@ tsort (const char *file) /* T2. Next Relation. */ size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer); if (len == (size_t) -1) - break; + break; assert (len != 0); k = search_item (root, tokenbuffer.buffer); if (j) - { - /* T3. Record the relation. */ - record_relation (j, k); - k = NULL; - } + { + /* T3. Record the relation. */ + record_relation (j, k); + k = NULL; + } j = k; } if (k != NULL) error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"), - file); + quotef (file)); /* T1. Initialize (N <- n). */ walk_tree (root, count_items); @@ -483,48 +484,55 @@ tsort (const char *file) walk_tree (root, scan_zeros); while (head) - { - struct successor *p = head->top; - - /* T5. Output front of queue. */ - printf ("%s\n", head->str); - head->str = NULL; /* Avoid printing the same string twice. */ - n_strings--; - - /* T6. Erase relations. */ - while (p) - { - p->suc->count--; - if (p->suc->count == 0) - { - zeros->qlink = p->suc; - zeros = p->suc; - } - - p = p->next; - } - - /* T7. Remove from queue. */ - head = head->qlink; - } + { + struct successor *p = head->top; + + /* T5. Output front of queue. */ + puts (head->str); +#ifdef lint + /* suppress valgrind "definitely lost" warnings. */ + void *head_str = (void *) head->str; + free (head_str); +#endif + head->str = NULL; /* Avoid printing the same string twice. */ + n_strings--; + + /* T6. Erase relations. */ + while (p) + { + p->suc->count--; + if (p->suc->count == 0) + { + zeros->qlink = p->suc; + zeros = p->suc; + } + + p = p->next; + } + + /* T7. Remove from queue. */ + head = head->qlink; + } /* T8. End of process. */ if (n_strings > 0) - { - /* The input contains a loop. */ - error (0, 0, _("%s: input contains a loop:"), file); - ok = false; - - /* Print the loop and remove a relation to break it. */ - do - walk_tree (root, detect_loop); - while (loop); - } + { + /* The input contains a loop. */ + error (0, 0, _("%s: input contains a loop:"), quotef (file)); + ok = false; + + /* Print the loop and remove a relation to break it. */ + do + walk_tree (root, detect_loop); + while (loop); + } } + IF_LINT (free (root)); + if (fclose (stdin) != 0) error (EXIT_FAILURE, errno, "%s", - is_stdin ? _("standard input") : quote (file)); + is_stdin ? _("standard input") : quotef (file)); return ok; } @@ -535,15 +543,15 @@ main (int argc, char **argv) bool ok; initialize_main (&argc, &argv); - program_name = argv[0]; + set_program_name (argv[0]); setlocale (LC_ALL, ""); bindtextdomain (PACKAGE, LOCALEDIR); textdomain (PACKAGE); atexit (close_stdout); - parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION, - usage, AUTHORS, (char const *) NULL); + parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, Version, + usage, AUTHORS, (char const *) NULL); if (getopt_long (argc, argv, "", NULL, NULL) != -1) usage (EXIT_FAILURE); @@ -555,5 +563,5 @@ main (int argc, char **argv) ok = tsort (optind == argc ? "-" : argv[optind]); - exit (ok ? EXIT_SUCCESS : EXIT_FAILURE); + return ok ? EXIT_SUCCESS : EXIT_FAILURE; } |