On Mon, 21 Feb 2022 01:00:32 +1000 (AEST) David Leonard <[email protected]> wrote:
> > > Hi, > I was recently after tsort to do some init ordering on a small system. > Hope this patch is acceptable. > Thanks, > David > > > function old new delta > packed_usage 34414 34433 +19 > applet_main 3192 3200 +8 > applet_names 2747 2753 +6 > tsort_main 737 +737 > --- > coreutils/tsort.c | 196 +++++++++++++++++++++++++++++++++++++ > docs/posix_conformance.txt | 2 +- > testsuite/tsort.tests | 110 +++++++++++++++++++++ > 3 files changed, 307 insertions(+), 1 deletion(-) > create mode 100644 coreutils/tsort.c > create mode 100755 testsuite/tsort.tests Hi, some minor fixes inline. Ciao, Tito >From d398d3dbfd8d1356137d574fd168a61cf58898c2 Mon Sep 17 00:00:00 2001 From: David Leonard <[email protected]> Date: Sun, 20 Feb 2022 14:29:45 +1000 Subject: [PATCH] tsort: new applet function old new delta packed_usage 34414 34433 +19 applet_main 3192 3200 +8 applet_names 2747 2753 +6 tsort_main 737 +737 --- coreutils/tsort.c | 196 +++++++++++++++++++++++++++++++++++++ docs/posix_conformance.txt | 2 +- testsuite/tsort.tests | 110 +++++++++++++++++++++ 3 files changed, 307 insertions(+), 1 deletion(-) create mode 100644 coreutils/tsort.c create mode 100755 testsuite/tsort.tests diff --git a/coreutils/tsort.c b/coreutils/tsort.c new file mode 100644 index 000000000..242273156 --- /dev/null +++ b/coreutils/tsort.c @@ -0,0 +1,196 @@ +/* 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 n +//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\n" +//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 int in_count; + unsigned int out_count; + struct node **out; + char name[]; +}; + +struct globals { + struct node **nodes; + unsigned int 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 int a = 0; + unsigned int b = G.nodes_len; + + /* binry search for name */ Typo binry -> binary + while (a != b) { + unsigned int m = (a + b) / 2; + int cmp = strcmp(name, G.nodes[m]->name); + if (cmp == 0) { + return G.nodes[m]; + } else if (cmp < 0) { + b = m; + } else { + a = m + 1; + } + } + + /* allocate new node */ + n = xmalloc(sizeof *n + strlen(name) + 1); + 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(a->out, (a->out_count + 1) * sizeof *a->out); + 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) +{ + const char *input_filename = "stdin"; + FILE *in = stdin; + char *line; + size_t linesz; + ssize_t len; + struct node *a; + int cycles; + + INIT_G(); + + if (argv[1]) { + if (argv[2]) { + bb_show_usage(); + } + input_filename = argv[1]; + if (input_filename[0] != '-' || input_filename[1]) { + close(STDIN_FILENO); /* == 0 */ + xopen(input_filename, O_RDONLY); /* fd will be 0 */ + } + } + + /* Read in words separated by <blank>s */ + a = NULL; + line = NULL; + linesz = 0; + while ((len = getline(&line, &linesz, in)) != -1) { + char *s = line; + while (*(s = skip_whitespace(s))) { + 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; + } + } + } + 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 int 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); + fprintf(stderr, "tsort: cycle at %s\n", 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); +} _______________________________________________ busybox mailing list [email protected] http://lists.busybox.net/mailman/listinfo/busybox
