/* tsort - topological sort.
- Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1998-2005, 2007-2008 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
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Written by Mark Kettenis <kettenis@phys.uva.nl>. */
sort) in Donald E. Knuth, The Art of Computer Programming, Volume
1/Fundamental Algorithms, page 262. */
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
+#include <config.h>
#include <stdio.h>
#include <assert.h>
#include <getopt.h>
+#include <sys/types.h>
#include "system.h"
#include "long-options.h"
#include "error.h"
+#include "quote.h"
#include "readtokens.h"
/* 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"
-char *xstrdup ();
-
/* Members of the list of successors. */
struct successor
{
{
const char *str;
struct item *left, *right;
- int balance;
- int count;
+ int balance; /* -1, 0, or +1 */
+ size_t count;
struct item *qlink;
struct successor *top;
};
-/* The name this program was run with. */
-char *program_name;
-
-/* Nonzero if any of the input files are the standard input. */
-static int have_read_stdin;
-
/* The head of the sorted list. */
static struct item *head = NULL;
/* The tail of the list of `zeros', strings that have no predecessors. */
static struct item *zeros = NULL;
-/* The number of strings to sort. */
-static int n_strings = 0;
+/* Used for loop detection. */
+static struct item *loop = NULL;
-static struct option const long_options[] =
-{
- { NULL, 0, NULL, 0}
-};
+/* The number of strings to sort. */
+static size_t n_strings = 0;
\f
void
usage (int status)
{
- if (status != 0)
+ if (status != EXIT_SUCCESS)
fprintf (stderr, _("Try `%s --help' for more information.\n"),
program_name);
else
Write totally ordered list consistent with the partial ordering in FILE.\n\
With no FILE, or when FILE is -, read standard input.\n\
\n\
- --help display this help and exit\n\
- --version output version information and exit\n"),
- program_name);
- puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
+"), program_name);
+ fputs (HELP_OPTION_DESCRIPTION, stdout);
+ fputs (VERSION_OPTION_DESCRIPTION, stdout);
+ emit_bug_reporting_address ();
}
- exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
+ exit (status);
}
/* Create a new item/node for STR. */
static struct item *
new_item (const char *str)
{
- struct item *k = xmalloc (sizeof (struct item));
+ struct item *k = xmalloc (sizeof *k);
k->str = (str ? xstrdup (str): NULL);
k->left = k->right = NULL;
else
{
r = p = s->right;
- a = +1;
+ a = 1;
}
while (p != q)
}
else
{
- p->balance = +1;
+ p->balance = 1;
p = p->right;
}
}
if (!STREQ (j->str, k->str))
{
k->count++;
- p = xmalloc (sizeof (struct successor));
+ p = xmalloc (sizeof *p);
p->suc = k;
p->next = j->top;
j->top = p;
}
}
-static void
-count_items (struct item *k)
+static bool
+count_items (struct item *unused ATTRIBUTE_UNUSED)
{
n_strings++;
+ return false;
}
-static void
+static bool
scan_zeros (struct item *k)
{
- if (k->count == 0)
+ /* Ignore strings that have already been printed. */
+ if (k->count == 0 && k->str)
{
if (head == NULL)
head = k;
zeros = k;
}
-}
-/* If K is part of a loop, print the loop on standard error, and exit. */
+ return false;
+}
-static void
+/* Try to detect the loop. If we have detected that K is part of a
+ loop, print the loop on standard error, remove a relation to break
+ the loop, and return true.
+
+ The loop detection strategy is as follows: Realise that what we're
+ dealing with is essentially a directed graph. If we find an item
+ that is part of a graph that contains a cycle we traverse the graph
+ in backwards direction. In general there is no unique way to do
+ this, but that is no problem. If we encounter an item that we have
+ encountered before, we know that we've found a cycle. All we have
+ to do now is retrace our steps, printing out the items until we
+ encounter that item again. (This is not necessarily the item that
+ we started from originally.) Since the order in which the items
+ are stored in the tree is not related to the specified partial
+ ordering, we may need to walk the tree several times before the
+ loop has completely been constructed. If the loop was found, the
+ global variable LOOP will be NULL. */
+
+static bool
detect_loop (struct item *k)
{
if (k->count > 0)
{
- while (k && k->count > 0)
+ /* K does not have to be part of a cycle. It is however part of
+ a graph that contains a cycle. */
+
+ if (loop == NULL)
+ /* Start traversing the graph at K. */
+ loop = k;
+ else
{
- k->count = 0;
- fprintf (stderr, "%s: %s\n", program_name, k->str);
- k = k->top->suc;
- }
+ 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
+ detect another loop. */
+ loop->qlink = NULL;
+ loop = tmp;
+ }
+
+ while (loop)
+ {
+ struct item *tmp = loop->qlink;
+
+ loop->qlink = NULL;
+ loop = tmp;
+ }
+
+ /* Since we have found the loop, stop walking
+ the tree. */
+ return true;
+ }
+ else
+ {
+ k->qlink = loop;
+ loop = k;
+ break;
+ }
+ }
- exit (EXIT_FAILURE);
+ p = &(*p)->next;
+ }
+ }
}
+
+ return false;
}
-/* Recurse (sub)tree rooted at ROOT, calling ACTION for each node. */
+/* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
+ Stop when ACTION returns true. */
-static void
-recurse_tree (struct item *root, void (*action) (struct item *))
+static bool
+recurse_tree (struct item *root, bool (*action) (struct item *))
{
if (root->left == NULL && root->right == NULL)
- (*action) (root);
+ return (*action) (root);
else
{
if (root->left != NULL)
- recurse_tree (root->left, action);
- (*action) (root);
+ if (recurse_tree (root->left, action))
+ return true;
+ if ((*action) (root))
+ return true;
if (root->right != NULL)
- recurse_tree (root->right, action);
+ if (recurse_tree (root->right, action))
+ return true;
}
+
+ return false;
}
/* Walk the tree specified by the head ROOT, calling ACTION for
each node. */
static void
-walk_tree (struct item *root, void (*action) (struct item *))
+walk_tree (struct item *root, bool (*action) (struct item *))
{
if (root->right)
recurse_tree (root->right, action);
}
-/* Do a topological sort on FILE. */
+/* Do a topological sort on FILE. Return true if successful. */
-static void
+static bool
tsort (const char *file)
{
+ bool ok = true;
struct item *root;
struct item *j = NULL;
struct item *k = NULL;
- register FILE *fp;
token_buffer tokenbuffer;
+ bool is_stdin = STREQ (file, "-");
/* Intialize the head of the tree will hold the strings we're sorting. */
root = new_item (NULL);
- if (STREQ (file, "-"))
- {
- fp = stdin;
- have_read_stdin = 1;
- }
- else
- {
- fp = fopen (file, "r");
- if (fp == NULL)
- error (EXIT_FAILURE, errno, "%s", file);
- }
+ if (!is_stdin && ! freopen (file, "r", stdin))
+ error (EXIT_FAILURE, errno, "%s", file);
init_tokenbuffer (&tokenbuffer);
while (1)
{
- long int len;
-
/* T2. Next Relation. */
- len = readtoken (fp, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
- if (len < 0)
+ size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
+ if (len == (size_t) -1)
break;
assert (len != 0);
j = k;
}
+ if (k != NULL)
+ error (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
+ file);
+
/* T1. Initialize (N <- n). */
walk_tree (root, count_items);
- /* T4. Scan for zeros. */
- walk_tree (root, scan_zeros);
-
- while (head)
+ while (n_strings > 0)
{
- struct successor *p = head->top;
-
- /* T5. Output front of queue. */
- printf ("%s\n", head->str);
- n_strings--;
+ /* T4. Scan for zeros. */
+ walk_tree (root, scan_zeros);
- /* T6. Erase relations. */
- while (p)
+ while (head)
{
- p->suc->count--;
- if (p->suc->count == 0)
+ struct successor *p = head->top;
+
+ /* T5. Output front of queue. */
+ puts (head->str);
+ head->str = NULL; /* Avoid printing the same string twice. */
+ n_strings--;
+
+ /* T6. Erase relations. */
+ while (p)
{
- zeros->qlink = p->suc;
- zeros = p->suc;
+ p->suc->count--;
+ if (p->suc->count == 0)
+ {
+ zeros->qlink = p->suc;
+ zeros = p->suc;
+ }
+
+ p = p->next;
}
- p = p->next;
+ /* T7. Remove from queue. */
+ head = head->qlink;
}
- /* 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);
+ }
}
- /* T8. End of process. */
- assert (n_strings >= 0);
- if (n_strings > 0)
- {
- error (0, 0, _("%s: input contains a loop:\n"),
- (have_read_stdin ? "-" : file));
-
- /* Print out loop. */
- walk_tree (root, detect_loop);
+ if (fclose (stdin) != 0)
+ error (EXIT_FAILURE, errno, "%s",
+ is_stdin ? _("standard input") : quote (file));
- /* Should not happen. */
- error (EXIT_FAILURE, 0, _("could not find loop"));
- }
+ return ok;
}
int
main (int argc, char **argv)
{
- int opt;
+ bool ok;
- program_name = argv[0];
+ initialize_main (&argc, &argv);
+ set_program_name (argv[0]);
setlocale (LC_ALL, "");
bindtextdomain (PACKAGE, LOCALEDIR);
textdomain (PACKAGE);
- parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
- "Mark Kettenis", usage);
-
- while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
- switch (opt)
- {
- case 0: /* long option */
- break;
- default:
- usage (EXIT_FAILURE);
- }
+ atexit (close_stdout);
- have_read_stdin = 0;
+ 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);
- if (optind + 1 < argc)
+ if (1 < argc - optind)
{
- error (0, 0, _("only one argument may be specified"));
+ error (0, 0, _("extra operand %s"), quote (argv[optind + 1]));
usage (EXIT_FAILURE);
}
- if (optind < argc)
- tsort (argv[optind]);
- else
- tsort ("-");
-
- if (fclose (stdout) == EOF)
- error (EXIT_FAILURE, errno, _("write error"));
-
- if (have_read_stdin && fclose (stdin) == EOF)
- error (EXIT_FAILURE, errno, _("standard input"));
+ ok = tsort (optind == argc ? "-" : argv[optind]);
- exit (EXIT_SUCCESS);
+ exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
}
projects / platform / upstream / coreutils.git / blobdiff