coreutils/tsort.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * tsort implementation for busybox
   4  *
   5  * public domain -- David Leonard, 2022
   6  */
   7 //config:config TSORT
   8 //config:       bool "tsort (2.6 kb)"
   9 //config:       default y
  10 //config:       help
  11 //config:       tsort performs a topological sort.
  12
  13 //applet:IF_TSORT(APPLET(tsort, BB_DIR_USR_BIN, BB_SUID_DROP))
  14
  15 //kbuild:lib-$(CONFIG_TSORT) += tsort.o
  16
  17 /* BB_AUDIT SUSv3 compliant */
  18 /* http://www.opengroup.org/onlinepubs/007904975/utilities/tsort.html */
  19
  20 //usage:#define tsort_trivial_usage
  21 //usage:       "[FILE]"
  22 //usage:#define tsort_full_usage "\n\n"
  23 //usage:       "Topological sort"
  24 //usage:#define tsort_example_usage
  25 //usage:       "$ echo -e \"a b\\nb c\" | tsort\n"
  26 //usage:       "a\n"
  27 //usage:       "b\n"
  28 //usage:       "c\n"
  29
  30 #include "libbb.h"
  31 #include "common_bufsiz.h"
  32
  33 struct node {
  34         unsigned in_count;
  35         unsigned out_count;
  36         struct node **out;
  37         char name[1];
  38 };
  39
  40 struct globals {
  41         struct node **nodes;
  42         unsigned nodes_len;
  43 };
  44 #define G (*(struct globals*)bb_common_bufsiz1)
  45 #define INIT_G() do { \
  46         setup_common_bufsiz(); \
  47         BUILD_BUG_ON(sizeof(G) > COMMON_BUFSIZE); \
  48         G.nodes = NULL; \
  49         G.nodes_len = 0; \
  50 } while (0)
  51
  52 static struct node *
  53 get_node(const char *name)
  54 {
  55         struct node *n;
  56         unsigned a = 0;
  57         unsigned b = G.nodes_len;
  58
  59         /* Binary search for name */
  60         while (a != b) {
  61                 unsigned m = (a + b) / 2;
  62                 int cmp = strcmp(name, G.nodes[m]->name);
  63                 if (cmp == 0)
  64                         return G.nodes[m]; /* found */
  65                 if (cmp < 0) {
  66                         b = m;
  67                 } else {
  68                         a = m + 1;
  69                 }
  70         }
  71
  72         /* Allocate new node */
  73         n = xzalloc(sizeof(*n) + strlen(name));
  74         //n->in_count = 0;
  75         //n->out_count = 0;
  76         //n->out = NULL;
  77         strcpy(n->name, name);
  78
  79         /* Insert to maintain sort */
  80         G.nodes = xrealloc(G.nodes, (G.nodes_len + 1) * sizeof(*G.nodes));
  81         memmove(&G.nodes[a + 1], &G.nodes[a],
  82                 (G.nodes_len - a) * sizeof(*G.nodes));
  83         G.nodes[a] = n;
  84         G.nodes_len++;
  85         return n;
  86 }
  87
  88 static void
  89 add_edge(struct node *a, struct node *b)
  90 {
  91         a->out = xrealloc_vector(a->out, 6, a->out_count);
  92         a->out[a->out_count++] = b;
  93         b->in_count++;
  94 }
  95
  96 int tsort_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
  97 int tsort_main(int argc UNUSED_PARAM, char **argv)
  98 {
  99         char *line;
 100         size_t linesz;
 101         ssize_t len;
 102         struct node *a;
 103         int cycles;
 104         unsigned i;
 105 #if ENABLE_FEATURE_CLEAN_UP
 106         unsigned max_len;
 107 #endif
 108
 109         INIT_G();
 110
 111         if (argv[1]) {
 112                 if (argv[2])
 113                         bb_show_usage();
 114                 if (NOT_LONE_DASH(argv[1])) {
 115                         close(STDIN_FILENO); /* == 0 */
 116                         xopen(argv[1], O_RDONLY); /* fd will be 0 */
 117                 }
 118         }
 119
 120         /* Read in words separated by <blank>s */
 121         a = NULL;
 122         line = NULL;
 123         linesz = 0;
 124         while ((len = getline(&line, &linesz, stdin)) != -1) {
 125                 char *s = line;
 126                 while (*(s = skip_whitespace(s)) != '\0') {
 127                         struct node *b;
 128                         char *word;
 129
 130                         word = s;
 131                         s = skip_non_whitespace(s);
 132                         if (*s)
 133                                 *s++ = '\0';
 134
 135                         /* Create nodes and edges for each word pair */
 136                         b = get_node(word);
 137                         if (!a) {
 138                                 a = b;
 139                         } else {
 140                                 if (a != b)
 141                                         add_edge(a, b);
 142                                 a = NULL;
 143                         }
 144                 }
 145         }
 146 // Most other tools do not check for input read error (treat them as EOF)
 147 //      die_if_ferror(in, input_filename);
 148         if (a)
 149                 bb_simple_error_msg_and_die("odd input");
 150         free(line);
 151
 152         /*
 153          * Kahn's algorithm:
 154          *   - find a node that has no incoming edges, print and remove it
 155          *   - repeat until the graph is empty
 156          *   - if any nodes are left, they form cycles.
 157          */
 158         cycles = 0;
 159 #if ENABLE_FEATURE_CLEAN_UP
 160         max_len = G.nodes_len;
 161 #endif
 162         while (G.nodes_len) {
 163                 struct node *n;
 164
 165                 /* Search for first node with no incoming edges */
 166                 for (i = 0; i < G.nodes_len; i++) {
 167                         if (!G.nodes[i]->in_count)
 168                                 break;
 169                 }
 170                 if (i == G.nodes_len) {
 171                         /* Must be a cycle; arbitraily break it at node 0 */
 172                         cycles++;
 173                         i = 0;
 174 #ifndef TINY
 175                         bb_error_msg("cycle at %s", G.nodes[i]->name);
 176 #endif
 177                 }
 178
 179                 /* Remove the node (need no longer maintain sort) */
 180                 n = G.nodes[i];
 181                 G.nodes[i] = G.nodes[--G.nodes_len];
 182 #if ENABLE_FEATURE_CLEAN_UP
 183                 /* Keep reference to removed node so it can be freed */
 184                 G.nodes[G.nodes_len] = n;
 185 #endif
 186
 187                 /* And remove its outgoing edges */
 188                 for (i = 0; i < n->out_count; i++)
 189                         n->out[i]->in_count--;
 190
 191                 puts(n->name);
 192         }
 193 #if ENABLE_FEATURE_CLEAN_UP
 194         for (i = 0; i < max_len; i++) {
 195                 free(G.nodes[i]->out);
 196                 free(G.nodes[i]);
 197         }
 198         free(G.nodes);
 199 #endif
 200
 201         fflush_stdout_and_exit(cycles ? 1 : 0);
 202 }