The old code freed nodes inline after processing them.
This works fine unless the input has cycles, in which case future iterations
will try to decrement in_count for the freed nodes.
The new code defers freeing all nodes until the processing is done.
---
coreutils/tsort.c | 24 ++++++++++++++++--------
1 file changed, 16 insertions(+), 8 deletions(-)
diff --git a/coreutils/tsort.c b/coreutils/tsort.c
index dedb65b15..15c8ecbf2 100644
--- a/coreutils/tsort.c
+++ b/coreutils/tsort.c
@@ -101,6 +101,8 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
ssize_t len;
struct node *a;
int cycles;
+ unsigned i;
+ unsigned remaining;
INIT_G();
@@ -152,16 +154,17 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
* - if any nodes are left, they form cycles.
*/
cycles = 0;
- while (G.nodes_len) {
+ remaining = G.nodes_len;
+
+ while (remaining) {
struct node *n;
- unsigned i;
/* Search for first node with no incoming edges */
- for (i = 0; i < G.nodes_len; i++) {
+ for (i = 0; i < remaining; i++) {
if (!G.nodes[i]->in_count)
break;
}
- if (i == G.nodes_len) {
+ if (i == remaining) {
/* Must be a cycle; arbitraily break it at node 0 */
cycles++;
i = 0;
@@ -170,17 +173,22 @@ int tsort_main(int argc UNUSED_PARAM, char **argv)
#endif
}
- /* Remove the node (need no longer maintain sort) */
+ /* Swap the node to the back (need no longer maintain sort) */
n = G.nodes[i];
- G.nodes[i] = G.nodes[--G.nodes_len];
+ G.nodes[i] = G.nodes[--remaining];
+ G.nodes[remaining] = n;
/* And remove its outgoing edges */
for (i = 0; i < n->out_count; i++)
n->out[i]->in_count--;
- free(n->out);
puts(n->name);
- free(n);
+ }
+
+ /* Free all nodes */
+ for (i = 0; i < G.nodes_len; i++) {
+ free(G.nodes[i]->out);
+ free(G.nodes[i]);
}
free(G.nodes);
--
2.39.0.314.g84b9a713c41-goog
_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox
