diff options
| -rw-r--r-- | usr.bin/tsort/tsort.c | 99 |
1 files changed, 83 insertions, 16 deletions
diff --git a/usr.bin/tsort/tsort.c b/usr.bin/tsort/tsort.c index 5e9cbcece06..a5006d753d7 100644 --- a/usr.bin/tsort/tsort.c +++ b/usr.bin/tsort/tsort.c @@ -1,4 +1,4 @@ -/* $OpenBSD: tsort.c,v 1.7 2001/04/18 17:57:28 espie Exp $ */ +/* $OpenBSD: tsort.c,v 1.8 2001/04/30 21:03:55 espie Exp $ */ /* ex:ts=8 sw=4: */ @@ -63,6 +63,12 @@ * heap. The resulting complexity is O(e+v log v) for the worst case. * The average should actually be near O(e). * + * If the hints file is incomplete, there is some extra complexity incurred + * by make_transparent, which does propagate order values to unmarked + * nodes. In the worst case, make_transparent is O(e u), + * where u is the number of originally unmarked nodes. + * In practice, it is much faster. + * * The simple topological sort algorithm detects cycles. This program * goes further, breaking cycles through the use of simple heuristics. * Each cycle break checks the whole set of nodes, hence if c cycles break @@ -127,8 +133,9 @@ static void usage __P((void)); static struct node *new_node __P((const char *, const char *)); static unsigned int read_pairs __P((FILE *, struct ohash *, int, - const char *, unsigned int)); + const char *, unsigned int, int)); static void split_nodes __P((struct ohash *, struct array *, struct array *)); +static void make_transparent __P((struct ohash *)); static void insert_arc __P((struct node *, struct node *)); #ifdef DEBUG @@ -271,10 +278,10 @@ dump_node(n) if (n->refs == 0) return; - printf("%s (%u): ", n->k, n->refs); + printf("%s (%u/%u): ", n->k, n->order, n->refs); for (l = n->arcs; l != NULL; l = l->next) if (n->refs != 0) - printf("%s(%u) ", l->node->k, l->node->refs); + printf("%s(%u/%u) ", l->node->k, l->node->order, l->node->refs); putchar('\n'); } @@ -290,7 +297,7 @@ dump_array(a) static void dump_hash(h) - struct hash *h; + struct ohash *h; { unsigned int i; struct node *n; @@ -324,12 +331,13 @@ insert_arc(a, b) } static unsigned int -read_pairs(f, h, reverse, name, order) +read_pairs(f, h, reverse, name, order, hint) FILE *f; struct ohash *h; int reverse; const char *name; unsigned int order; + int hint; { int toggle; struct node *a; @@ -354,7 +362,7 @@ read_pairs(f, h, reverse, name, order) continue; if (toggle) { a = node_lookup(h, str, e); - if (a->order == NO_ORDER) + if (a->order == NO_ORDER && hint) a->order = order++; } else { struct node *b; @@ -450,7 +458,7 @@ heapify(h, verbose) unsigned int i; for (i = h->entries; i != 0;) { - if (h->t[--i]->order == 0 && verbose) + if (h->t[--i]->order == NO_ORDER && verbose) warnx("node %s absent from hints file", h->t[i]->k); heap_down(h, i); } @@ -502,6 +510,60 @@ enqueue(h, n) } } +/* Nodes without order should not hinder direct dependencies. + * Iterate until no nodes are left. + */ +static void +make_transparent(hash) + struct ohash *hash; +{ + struct node *n; + unsigned int i; + struct link *l; + int adjusted; + int bad; + unsigned int min; + + /* first try to solve complete nodes */ + do { + adjusted = 0; + bad = 0; + for (n = ohash_first(hash, &i); n != NULL; + n = ohash_next(hash, &i)) { + if (n->order == NO_ORDER) { + min = NO_ORDER; + + for (l = n->arcs; l != NULL; l = l->next) { + /* unsolved node -> delay resolution */ + if (l->node->order == NO_ORDER) { + bad = 1; + break; + } else if (l->node->order < min) + min = l->node->order; + } + if (min < NO_ORDER && l == NULL) { + n->order = min; + adjusted = 1; + } + } + } + + } while (adjusted); + + /* then, if incomplete nodes are left, do them */ + if (bad) do { + adjusted = 0; + for (n = ohash_first(hash, &i); n != NULL; + n = ohash_next(hash, &i)) + if (n->order == NO_ORDER) + for (l = n->arcs; l != NULL; l = l->next) + if (l->node->order < n->order) { + n->order = l->node->order; + adjusted = 1; + } + } while (adjusted); +} + /*** *** Search through hash array for nodes. @@ -517,9 +579,9 @@ split_nodes(hash, heap, remaining) struct node *n; unsigned int i; + unsigned int total = ohash_entries(hash); heap->t = emalloc(sizeof(struct node *) * ohash_entries(hash)); - remaining->t = emalloc(sizeof(struct node *) * ohash_entries(hash)); heap->entries = 0; remaining->entries = 0; @@ -527,8 +589,9 @@ split_nodes(hash, heap, remaining) if (n->refs == 0) heap->t[heap->entries++] = n; else - remaining->t[remaining->entries++] = n; + heap->t[total-1-remaining->entries++] = n; } + remaining->t = heap->t + heap->entries; } /* Good point to break a cycle: live node with as few refs as possible. */ @@ -807,7 +870,7 @@ main(argc, argv) warn_flag, hints_flag, verbose_flag; unsigned int order; - order = 1; + order = 0; reverse_flag = quiet_flag = long_flag = warn_flag = hints_flag = verbose_flag = 0; @@ -829,11 +892,11 @@ main(argc, argv) optarg, order); fclose(f); } + hints_flag = 1; + break; /*FALLTHRU*/ case 'f': - if (hints_flag == 1) - usage(); - hints_flag = 1; + hints_flag = 2; break; case 'l': long_flag = 1; @@ -866,12 +929,14 @@ main(argc, argv) f = fopen(argv[0], "r"); if (f == NULL) err(EX_NOINPUT, "Can't open file %s", argv[1]); - order = read_pairs(f, &pairs, reverse_flag, argv[1], order); + order = read_pairs(f, &pairs, reverse_flag, argv[1], order, + hints_flag == 2); fclose(f); break; } case 0: - order = read_pairs(stdin, &pairs, reverse_flag, "stdin", order); + order = read_pairs(stdin, &pairs, reverse_flag, "stdin", + order, hints_flag == 2); break; default: usage(); @@ -886,6 +951,8 @@ main(argc, argv) broken_arcs = 0; broken_cycles = 0; + if (hints_flag) + make_transparent(&pairs); split_nodes(&pairs, &aux, &remaining); ohash_delete(&pairs); |