/* 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 <stdio.h>
+#include <sys/types.h>
-#include "long-options.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 proper_name ("Mark Kettenis")
-char *xstrdup ();
+/* Token delimiters when reading from a file. */
+#define DELIM " \t\n"
/* 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;
+static struct item *head = NULL;
-/* A scratch variable. */
-static struct item *r = 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 = 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
-static void
+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;
p->right = q;
/* A6. Adjust balance factors. */
- assert (strcmp (str, s->str));
+ assert (!STREQ (str, s->str));
if (strcmp (str, s->str) < 0)
{
r = p = s->left;
else
{
r = p = s->right;
- a = +1;
+ a = 1;
}
while (p != q)
{
- assert (strcmp (str, p->str));
+ assert (!STREQ (str, p->str));
if (strcmp (str, p->str) < 0)
{
p->balance = -1;
}
else
{
- p->balance = +1;
+ p->balance = 1;
p = p->right;
}
}
{
struct successor *p;
- if (strcmp (j->str, k->str))
+ 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++;
+ 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 (r == NULL)
+ if (head == NULL)
head = k;
else
- r->qlink = k;
+ zeros->qlink = k;
- r = 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;
- exit (EXIT_FAILURE);
+ 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;
+ }
+ }
+
+ 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);
}
-/* The following function was copied from getline.c, but with these changes:
- - Read up to and not including any "whitespace" character.
- - Remove unused argument, OFFSET.
- - Use xmalloc and xrealloc instead of malloc and realloc.
- - Declare this function static. */
-
-/* Always add at least this many bytes when extending the buffer. */
-#define MIN_CHUNK 64
-
-/* Read up to (and not including) any "whitespace" character from STREAM
- into *LINEPTR (and null-terminate it). *LINEPTR is a pointer returned
- from xmalloc (or NULL), pointing to *N characters of space. It is
- xrealloc'd as necessary. Return the number of characters read (not
- including the null terminator), or -1 on error or EOF. */
-
-static int
-getstr (char **lineptr, int *n, FILE *stream)
-{
- int nchars_avail; /* Allocated but unused chars in *LINEPTR. */
- char *read_pos; /* Where we're reading into *LINEPTR. */
-
- if (!lineptr || !n || !stream)
- return -1;
-
- if (!*lineptr)
- {
- *n = MIN_CHUNK;
- *lineptr = (char *) xmalloc (*n);
- if (!*lineptr)
- return -1;
- }
-
- nchars_avail = *n;
- read_pos = *lineptr;
-
- for (;;)
- {
- register int c = getc (stream);
-
- /* We always want at least one char left in the buffer, since we
- always (unless we get an error while reading the first char)
- NUL-terminate the line buffer. */
-
- assert (*n - nchars_avail == read_pos - *lineptr);
- if (nchars_avail < 1)
- {
- if (*n > MIN_CHUNK)
- *n *= 2;
- else
- *n += MIN_CHUNK;
-
- nchars_avail = *n + *lineptr - read_pos;
- *lineptr = xrealloc (*lineptr, *n);
- if (!*lineptr)
- return -1;
- read_pos = *n - nchars_avail + *lineptr;
- assert (*n - nchars_avail == read_pos - *lineptr);
- }
-
- if (feof (stream) || ferror (stream))
- {
- /* Return partial line, if any. */
- if (read_pos == *lineptr)
- return -1;
- else
- break;
- }
-
- if (ISSPACE (c))
- /* Return the string. */
- break;
-
- *read_pos++ = c;
- nchars_avail--;
- }
-
- /* Done - NUL terminate and return the number of chars read. */
- *read_pos = '\0';
-
- return read_pos - *lineptr;
-}
-
+/* Do a topological sort on FILE. Return true if successful. */
-static void
-sort (const char *file)
+static bool
+tsort (const char *file)
{
+ bool ok = true;
struct item *root;
struct item *j = NULL;
struct item *k = NULL;
- register FILE *fp;
- char *str = NULL;
- size_t size = 0;
- int len;
+ 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)
{
/* T2. Next Relation. */
- len = getstr (&str, &size, fp);
- if (len < 0)
+ size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer);
+ if (len == (size_t) -1)
break;
assert (len != 0);
- k = search_item (root, str);
+ k = search_item (root, tokenbuffer.buffer);
if (j)
{
/* T3. Record the relation. */
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;
+ /* T4. Scan for zeros. */
+ walk_tree (root, scan_zeros);
- /* T5. Output front of queue. */
- printf ("%s\n", head->str);
- n--;
-
- /* 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)
{
- r->qlink = p->suc;
- r = 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 >= 0);
- if (n > 0)
- {
- if (have_read_stdin)
- fprintf (stderr, _("%s: input contains a loop:\n"), program_name);
- else
- fprintf (stderr, _("%s: %s: input contains a loop:\n"),
- program_name, 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, _("%s: 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, "tsort", GNU_PACKAGE, VERSION, usage);
+ atexit (close_stdout);
- 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;
+ 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)
- sort (argv[optind]);
- else
- sort ("-");
-
- 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);
}