From a8b0898ba5e7c9ed414472030c726813d216d216 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Tue, 25 Jan 2000 12:03:15 +0000 Subject: tsort now works more like the traditional UNIX tsort. Before it would exit when it found a loop. Now it continues and outputs all items. (exit_status): New variable. (loop): New varibale. (count_items, scan_zeroes): Change return type to int. (detect_loop): Complete rewrite to correctly implement detection of loops. Also change return type to int. (recurse_tree): Stop if ACTION returns non-zero. This involves changing the return type of this function and ACTION to int. (walk_tree): Change return type of ACTION to int. (tsort): Continue sort after a loop has been detected (and broken). Set exit_status to 1 if a loop was detected. (main): Use exit_status to determine exit code. --- src/tsort.c | 201 +++++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 146 insertions(+), 55 deletions(-) (limited to 'src/tsort.c') diff --git a/src/tsort.c b/src/tsort.c index 3234a4065..2097eca95 100644 --- a/src/tsort.c +++ b/src/tsort.c @@ -1,5 +1,5 @@ /* tsort - topological sort. - Copyright (C) 1998, 1999 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. 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 @@ -66,12 +66,18 @@ 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; /* The tail of the list of `zeros', strings that have no predecessors. */ static struct item *zeros = NULL; +/* Used for loop detection. */ +static struct item *loop = NULL; + /* The number of strings to sort. */ static int n_strings = 0; @@ -288,16 +294,18 @@ record_relation (struct item *j, struct item *k) } } -static void +static int count_items (struct item *k) { n_strings++; + return 0; } -static void +static int 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; @@ -306,48 +314,124 @@ scan_zeros (struct item *k) zeros = k; } -} -/* If K is part of a loop, print the loop on standard error, and exit. */ + return 0; +} -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 non-zero. + + 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 does not have to be the item that + we started at in the first place.) Since the order */ + +static int detect_loop (struct item *k) { - if (k->count > 0 && k->top) + 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 1; + } + else + { + k->qlink = loop; + loop = k; + break; + } + } - exit (EXIT_FAILURE); + p = &(*p)->next; + } + } } + + return 0; } -/* 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 non-zero. */ -static void -recurse_tree (struct item *root, void (*action) (struct item *)) +static int +recurse_tree (struct item *root, int (*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 1; + if ((*action) (root)) + return 1; if (root->right != NULL) - recurse_tree (root->right, action); + if (recurse_tree (root->right, action)) + return 1; } + + return 0; } /* 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, int (*action) (struct item *)) { if (root->right) recurse_tree (root->right, action); @@ -406,46 +490,51 @@ tsort (const char *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_strings--; - - /* T6. Erase relations. */ - while (p) + while (head) { - p->suc->count--; - if (p->suc->count == 0) - { - zeros->qlink = p->suc; - zeros = p->suc; - } + struct successor *p = head->top; - p = p->next; - } + /* T5. Output front of queue. */ + printf ("%s\n", head->str); + head->str = NULL; /* Avoid printing the same string twice. */ + n_strings--; - /* T7. Remove from queue. */ - head = head->qlink; - } + /* T6. Erase relations. */ + while (p) + { + p->suc->count--; + if (p->suc->count == 0) + { + zeros->qlink = p->suc; + zeros = p->suc; + } - /* T8. End of process. */ - assert (n_strings >= 0); - if (n_strings > 0) - { - error (0, 0, _("%s: input contains a loop:"), - (have_read_stdin ? "-" : file)); + p = p->next; + } - /* Print out loop. */ - walk_tree (root, detect_loop); + /* T7. Remove from queue. */ + head = head->qlink; + } - /* Should not happen. */ - error (EXIT_FAILURE, 0, _("could not find loop")); + /* 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:"), + (have_read_stdin ? "-" : file)); + exit_status = 1; + + /* Print the loop and remove a relation to break it. */ + do + walk_tree (root, detect_loop); + while (loop); + } } } @@ -459,6 +548,8 @@ main (int argc, char **argv) bindtextdomain (PACKAGE, LOCALEDIR); textdomain (PACKAGE); + exit_status = 0; + parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION, AUTHORS, usage); @@ -490,5 +581,5 @@ main (int argc, char **argv) if (have_read_stdin && fclose (stdin) == EOF) error (EXIT_FAILURE, errno, _("standard input")); - exit (EXIT_SUCCESS); + exit (exit_status == 0 ? EXIT_SUCCESS : EXIT_FAILURE); } -- cgit v1.2.3-54-g00ecf