Merge branch 'busybox' into merge

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);
+}