[PATCH] tsort: new applet
tito
farmatito at tiscali.it
Sun Feb 20 16:11:41 UTC 2022
On Mon, 21 Feb 2022 01:00:32 +1000 (AEST)
David Leonard <d+busybox at adaptive-enterprises.com> 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 <d+busybox at adaptive-enterprises.com>
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);
+}
More information about the busybox
mailing list