Good afternoon, I've studied the source code for tsort a bit and think I've found a flaw. Basically, the way tsort works is as follows: 1) Construct a graph from the input data 2) Remove all nodes which no other nodes depend on. 3) If still any nodes left there is a cycle in the graph. Remove a node that's part of a cycle. Goto 2. Now, the flaw is in the find_cycle part of the program. The current algorithm tries to find the longest cycle that a node is part of. This is an NP-complete problem and with approx 50 nodes and more than 1000 edges in the graph (as is the case for libgcc1.a) this *do* take some time..... And moreover, the result of this traversal is only used for printing out on stderr which nodes are part of this cycle, not for determining what node to remove from the cycle. I therefore modified the cycle finding algorithm to just detect a cycle, print it and then remove the node. This made my building of the libgcc1.a tractable. I would like the other persons (sorry, I don't remember your names) that had problems building various libraries to try this patch and see if there are any more (old or new) bugs in it. Diffs below. -jarle ================================================================ *** /usr/src/usr.bin/tsort/tsort.c Wed Nov 17 15:25:40 1993 --- tsort.c Wed Nov 24 17:30:32 1993 *************** *** 278,282 **** tsort() { ! register NODE *n, *next; register int cnt; --- 278,282 ---- tsort() { ! register NODE *n, *m, *next; register int cnt; *************** *** 317,320 **** --- 317,322 ---- for (n = graph; n; n = n->n_next) if (!(n->n_flags & NF_ACYCLIC)) { + for (m=graph; m; m=m->n_next) + m->n_flags &= ~NF_MARK; if (cnt = find_cycle(n, n, 0, 0)) { register int i; *************** *** 357,361 **** } ! /* look for the longest cycle from node from to node to. */ find_cycle(from, to, longest_len, depth) NODE *from, *to; --- 359,363 ---- } ! /* look for a path from node from to node to. */ find_cycle(from, to, longest_len, depth) NODE *from, *to; *************** *** 384,392 **** } else { len = find_cycle(*np, to, longest_len, depth + 1); ! if (len > longest_len) longest_len = len; } } - from->n_flags &= ~NF_MARK; return(longest_len); } --- 386,395 ---- } else { len = find_cycle(*np, to, longest_len, depth + 1); ! if (len > longest_len) { longest_len = len; + break; + } } } return(longest_len); } ================================================================ "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth ------------------------------------------------------------------------------