/* tsort - topological sort.
- Copyright (C) 1998-2003 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>. */
#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"
{
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 error code to return to the system. */
-static int exit_status;
-
/* The head of the sorted list. */
static struct item *head = NULL;
static struct item *loop = NULL;
/* The number of strings to sort. */
-static int n_strings = 0;
-
-static struct option const long_options[] =
-{
- { NULL, 0, NULL, 0}
-};
+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
"), program_name);
fputs (HELP_OPTION_DESCRIPTION, stdout);
fputs (VERSION_OPTION_DESCRIPTION, stdout);
- printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
+ 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;
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 int
+static bool
count_items (struct item *unused ATTRIBUTE_UNUSED)
{
n_strings++;
- return 0;
+ return false;
}
-static int
+static bool
scan_zeros (struct item *k)
{
/* Ignore strings that have already been printed. */
zeros = k;
}
- return 0;
+ return false;
}
/* 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 non-zero.
+ 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
loop has completely been constructed. If the loop was found, the
global variable LOOP will be NULL. */
-static int
+static bool
detect_loop (struct item *k)
{
if (k->count > 0)
/* Since we have found the loop, stop walking
the tree. */
- return 1;
+ return true;
}
else
{
}
}
- return 0;
+ return false;
}
/* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
- Stop when ACTION returns non-zero. */
+ Stop when ACTION returns true. */
-static int
-recurse_tree (struct item *root, int (*action) (struct item *))
+static bool
+recurse_tree (struct item *root, bool (*action) (struct item *))
{
if (root->left == NULL && root->right == NULL)
return (*action) (root);
{
if (root->left != NULL)
if (recurse_tree (root->left, action))
- return 1;
+ return true;
if ((*action) (root))
- return 1;
+ return true;
if (root->right != NULL)
if (recurse_tree (root->right, action))
- return 1;
+ return true;
}
- return 0;
+ return false;
}
/* Walk the tree specified by the head ROOT, calling ACTION for
each node. */
static void
-walk_tree (struct item *root, int (*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);
struct successor *p = head->top;
/* T5. Output front of queue. */
- printf ("%s\n", head->str);
+ puts (head->str);
head->str = NULL; /* Avoid printing the same string twice. */
n_strings--;
}
/* T8. End of process. */
- assert (n_strings >= 0);
if (n_strings > 0)
{
/* The input contains a loop. */
error (0, 0, _("%s: input contains a loop:"), file);
- exit_status = 1;
+ ok = false;
/* Print the loop and remove a relation to break it. */
do
while (loop);
}
}
+
+ if (fclose (stdin) != 0)
+ error (EXIT_FAILURE, errno, "%s",
+ is_stdin ? _("standard input") : quote (file));
+
+ return ok;
}
int
main (int argc, char **argv)
{
- int opt;
+ 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);
- exit_status = 0;
-
parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, VERSION,
- AUTHORS, usage);
-
- while ((opt = getopt_long (argc, argv, "", long_options, NULL)) != -1)
- switch (opt)
- {
- case 0: /* long option */
- break;
- default:
- usage (EXIT_FAILURE);
- }
-
- have_read_stdin = 0;
+ usage, AUTHORS, (char const *) NULL);
+ if (getopt_long (argc, argv, "", NULL, NULL) != -1)
+ usage (EXIT_FAILURE);
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);
}
- tsort (optind == argc ? "-" : argv[optind]);
-
- if (have_read_stdin && fclose (stdin) == EOF)
- error (EXIT_FAILURE, errno, _("standard input"));
+ ok = tsort (optind == argc ? "-" : argv[optind]);
- exit (exit_status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
+ exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
}
projects / platform / upstream / coreutils.git / blobdiff