From 4642cf5b388bf60f6bea67ce3a5031d24bccd48a Mon Sep 17 00:00:00 2001 From: David Leonard Date: Sun, 20 Feb 2022 14:29:45 +1000 Subject: tsort: new applet function old new delta tsort_main - 578 +578 .rodata 104884 104906 +22 applet_names 2759 2765 +6 applet_main 1596 1600 +4 packed_usage 34290 34288 -2 ------------------------------------------------------------------------------ (add/remove: 2/0 grow/shrink: 3/1 up/down: 610/-2) Total: 608 bytes Signed-off-by: David Leonard Signed-off-by: Denys Vlasenko --- coreutils/tsort.c | 188 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 188 insertions(+) create mode 100644 coreutils/tsort.c (limited to 'coreutils/tsort.c') diff --git a/coreutils/tsort.c b/coreutils/tsort.c new file mode 100644 index 0000000..dedb65b --- /dev/null +++ b/coreutils/tsort.c @@ -0,0 +1,188 @@ +/* vi: set sw=4 ts=4: */ +/* + * tsort implementation for busybox + * + * public domain -- David Leonard, 2022 + */ +//config:config TSORT +//config: bool "tsort (0.7 kb)" +//config: default y +//config: help +//config: tsort performs a topological sort. + +//applet:IF_TSORT(APPLET(tsort, BB_DIR_USR_BIN, BB_SUID_DROP)) + +//kbuild:lib-$(CONFIG_TSORT) += tsort.o + +/* BB_AUDIT SUSv3 compliant */ +/* http://www.opengroup.org/onlinepubs/007904975/utilities/tsort.html */ + +//usage:#define tsort_trivial_usage +//usage: "[FILE]" +//usage:#define tsort_full_usage "\n\n" +//usage: "Topological sort" +//usage:#define tsort_example_usage +//usage: "$ echo -e \"a b\\nb c\" | tsort\n" +//usage: "a\n" +//usage: "b\n" +//usage: "c\n" + +#include "libbb.h" +#include "common_bufsiz.h" + +struct node { + unsigned in_count; + unsigned out_count; + struct node **out; + char name[1]; +}; + +struct globals { + struct node **nodes; + unsigned nodes_len; +}; +#define G (*(struct globals*)bb_common_bufsiz1) +#define INIT_G() do { \ + setup_common_bufsiz(); \ + BUILD_BUG_ON(sizeof(G) > COMMON_BUFSIZE); \ + G.nodes = NULL; \ + G.nodes_len = 0; \ +} while (0) + +static struct node * +get_node(const char *name) +{ + struct node *n; + unsigned a = 0; + unsigned b = G.nodes_len; + + /* Binary search for name */ + while (a != b) { + unsigned m = (a + b) / 2; + int cmp = strcmp(name, G.nodes[m]->name); + if (cmp == 0) + return G.nodes[m]; /* found */ + if (cmp < 0) { + b = m; + } else { + a = m + 1; + } + } + + /* Allocate new node */ + n = xzalloc(sizeof(*n) + strlen(name)); + //n->in_count = 0; + //n->out_count = 0; + //n->out = NULL; + strcpy(n->name, name); + + /* Insert to maintain sort */ + G.nodes = xrealloc(G.nodes, (G.nodes_len + 1) * sizeof(*G.nodes)); + memmove(&G.nodes[a + 1], &G.nodes[a], + (G.nodes_len - a) * sizeof(*G.nodes)); + G.nodes[a] = n; + G.nodes_len++; + return n; +} + +static void +add_edge(struct node *a, struct node *b) +{ + a->out = xrealloc_vector(a->out, 6, a->out_count); + a->out[a->out_count++] = b; + b->in_count++; +} + +int tsort_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; +int tsort_main(int argc UNUSED_PARAM, char **argv) +{ + char *line; + size_t linesz; + ssize_t len; + struct node *a; + int cycles; + + INIT_G(); + + if (argv[1]) { + if (argv[2]) + bb_show_usage(); + if (NOT_LONE_DASH(argv[1])) { + close(STDIN_FILENO); /* == 0 */ + xopen(argv[1], O_RDONLY); /* fd will be 0 */ + } + } + + /* Read in words separated by s */ + a = NULL; + line = NULL; + linesz = 0; + while ((len = getline(&line, &linesz, stdin)) != -1) { + char *s = line; + while (*(s = skip_whitespace(s)) != '\0') { + struct node *b; + char *word; + + word = s; + s = skip_non_whitespace(s); + if (*s) + *s++ = '\0'; + + /* Create nodes and edges for each word pair */ + b = get_node(word); + if (!a) { + a = b; + } else { + if (a != b) + add_edge(a, b); + a = NULL; + } + } + } +// Most other tools do not check for input read error (treat them as EOF) +// die_if_ferror(in, input_filename); + if (a) + bb_simple_error_msg_and_die("odd input"); + free(line); + + /* + * Kahn's algorithm: + * - find a node that has no incoming edges, print and remove it + * - repeat until the graph is empty + * - if any nodes are left, they form cycles. + */ + cycles = 0; + while (G.nodes_len) { + struct node *n; + unsigned i; + + /* Search for first node with no incoming edges */ + for (i = 0; i < G.nodes_len; i++) { + if (!G.nodes[i]->in_count) + break; + } + if (i == G.nodes_len) { + /* Must be a cycle; arbitraily break it at node 0 */ + cycles++; + i = 0; +#ifndef TINY + bb_error_msg("cycle at %s", G.nodes[i]->name); +#endif + } + + /* Remove the node (need no longer maintain sort) */ + n = G.nodes[i]; + G.nodes[i] = G.nodes[--G.nodes_len]; + + /* 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(G.nodes); + + fflush_stdout_and_exit(cycles ? 1 : 0); +} -- cgit v1.1