Here is a patch to make tsort treat cycles by constructing an equivalence
relation in the usual way, and do the tsort on the quotient of set of nodes
over it.
This makes tsort useable again for those who do "lorder *.o | tsort".
--
Debian GNU/Linux 2.1 is out! ( http://www.debian.org/ )
Email: Herbert Xu ~{PmV>HI~} <[EMAIL PROTECTED]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Index: tsort.c
===================================================================
RCS file: /home/gondor/herbert/src/CVS/debian/textutils/src/tsort.c,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 tsort.c
--- tsort.c 1999/05/04 14:30:29 1.1.1.1
+++ tsort.c 2000/06/20 03:51:18
@@ -57,7 +57,9 @@
const char *str;
struct item *left, *right;
int balance;
- int count;
+ struct item *eqnext, *eqtail;
+ enum { unvisited, visiting, visited } status;
+ int depth;
struct item *qlink;
struct successor *top;
};
@@ -71,12 +73,9 @@
/* 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;
+/* True if there are loops. */
+static int loop_found = 0;
-/* The number of strings to sort. */
-static int n_strings = 0;
-
static struct option const long_options[] =
{
{ NULL, 0, NULL, 0}
@@ -114,10 +113,11 @@
k->left = k->right = NULL;
k->balance = 0;
- /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
- k->count = 0;
k->qlink = NULL;
k->top = NULL;
+ k->eqnext = NULL;
+ k->eqtail = k;
+ k->status = unvisited;
return k;
}
@@ -282,7 +282,6 @@
if (!STREQ (j->str, k->str))
{
- k->count++;
p = xmalloc (sizeof (struct successor));
p->suc = k;
p->next = j->top;
@@ -290,42 +289,60 @@
}
}
-static void
-count_items (struct item *k)
+int dfs(struct item *k)
{
- n_strings++;
-}
+ struct successor *p;
+ int cycle_start = k->depth, new_cycle_start;
-static void
-scan_zeros (struct item *k)
-{
- if (k->count == 0)
+ k->status = visiting;
+ for (p = k->top; p; p = p->next)
{
- if (head == NULL)
- head = k;
- else
- zeros->qlink = k;
+ switch (p->suc->status)
+ {
+ case unvisited:
+ p->suc->depth = k->depth + 1;
+ new_cycle_start = dfs(p->suc);
+ if (new_cycle_start <= k->depth)
+ {
+ k->eqtail->eqnext = p->suc;
+ k->eqtail = p->suc->eqtail;
+ if (new_cycle_start < cycle_start)
+ cycle_start = new_cycle_start;
+ }
+ break;
+ case visiting:
+ if (p->suc->depth < cycle_start)
+ cycle_start = p->suc->depth;
+ break;
+ case visited:
+ break;
+ }
+ }
+ k->status = visited;
+ k->qlink = head;
+ head = k;
- zeros = k;
+ if (k->eqnext && cycle_start == k->depth)
+ {
+ struct item *j = k;
+ error (0, 0, _("input contains a loop:\n"));
+ do {
+ fprintf (stderr, "%s: %s\n", program_name, j->str);
+ } while ((j = j->eqnext));
+ loop_found = 1;
}
-}
-/* If K is part of a loop, print the loop on standard error, and exit. */
+ return cycle_start;
+}
static void
-detect_loop (struct item *k)
+tsort_node (struct item *k)
{
- if (k->count > 0)
- {
- while (k && k->count > 0)
- {
- k->count = 0;
- fprintf (stderr, "%s: %s\n", program_name, k->str);
- k = k->top->suc;
- }
+ if (k->status == visited)
+ return;
- exit (EXIT_FAILURE);
- }
+ k->depth = 0;
+ dfs(k);
}
/* Recurse (sub)tree rooted at ROOT, calling ACTION for each node. */
@@ -404,51 +421,15 @@
j = k;
}
-
- /* T1. Initialize (N <- n). */
- walk_tree (root, count_items);
- /* T4. Scan for zeros. */
- walk_tree (root, scan_zeros);
-
+ walk_tree (root, tsort_node);
while (head)
{
- struct successor *p = head->top;
-
- /* T5. Output front of queue. */
printf ("%s\n", head->str);
- 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. */
- 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);
-
- /* Should not happen. */
- error (EXIT_FAILURE, 0, _("could not find loop"));
}
+ if (loop_found)
+ exit (EXIT_FAILURE);
}
int
