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 <d+busybox@adaptive-enterprises.com>
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

1 files changed, 188 insertions, 0 deletions

diff --git a/coreutils/tsort.c b/coreutils/tsort.c
new file mode 100644
index 000000000..dedb65b15
--- /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 <blank>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);
+}