sbase

suckless unix tools
git clone git://git.2f30.org/sbase
Log | Files | Refs | README | LICENSE

tsort.c (3727B)

      1 /* See LICENSE file for copyright and license details. */
      2 #include <stdio.h>
      3 #include <string.h>
      4 #include <stdlib.h>
      5 #include <ctype.h>
      6 
      7 #include "util.h"
      8 
      9 enum { WHITE = 0, GREY, BLACK };
     10 
     11 struct vertex;
     12 
     13 struct edge {
     14 	struct vertex *to;
     15 	struct edge *next;
     16 };
     17 
     18 struct vertex {
     19 	char *name;
     20 	struct vertex *next;
     21 	struct edge edges;
     22 	size_t in_edges;
     23 	int colour;
     24 };
     25 
     26 static struct vertex graph;
     27 
     28 static void
     29 find_vertex(const char *name, struct vertex **it, struct vertex **prev)
     30 {
     31 	for (*prev = &graph; (*it = (*prev)->next); *prev = *it) {
     32 		int cmp = strcmp(name, (*it)->name);
     33 		if (cmp > 0)
     34 			continue;
     35 		if (cmp < 0)
     36 			*it = 0;
     37 		return;
     38 	}
     39 }
     40 
     41 static void
     42 find_edge(struct vertex *from, const char *to, struct edge **it, struct edge **prev)
     43 {
     44 	for (*prev = &(from->edges); (*it = (*prev)->next); *prev = *it) {
     45 		int cmp = strcmp(to, (*it)->to->name);
     46 		if (cmp > 0)
     47 			continue;
     48 		if (cmp < 0)
     49 			*it = 0;
     50 		return;
     51 	}
     52 }
     53 
     54 static struct vertex *
     55 add_vertex(char *name)
     56 {
     57 	struct vertex *vertex;
     58 	struct vertex *prev;
     59 
     60 	find_vertex(name, &vertex, &prev);
     61 	if (vertex)
     62 		return vertex;
     63 
     64 	vertex = encalloc(2, 1, sizeof(*vertex));
     65 	vertex->name = name;
     66 	vertex->next = prev->next;
     67 	prev->next = vertex;
     68 
     69 	return vertex;
     70 }
     71 
     72 static struct edge *
     73 add_edge(struct vertex *from, struct vertex* to)
     74 {
     75 	struct edge *edge;
     76 	struct edge *prev;
     77 
     78 	find_edge(from, to->name, &edge, &prev);
     79 	if (edge)
     80 		return edge;
     81 
     82 	edge = encalloc(2, 1, sizeof(*edge));
     83 	edge->to = to;
     84 	edge->next = prev->next;
     85 	prev->next = edge;
     86 	to->in_edges += 1;
     87 
     88 	return edge;
     89 }
     90 
     91 static void
     92 load_graph(FILE *fp)
     93 {
     94 #define SKIP(VAR, START, FUNC)  for (VAR = START; FUNC(*VAR) && *VAR; VAR++)
     95 #define TOKEN_END(P)            do { if (*P) *P++ = 0; else P = 0; } while (0)
     96 
     97 	char *line = 0;
     98 	size_t size = 0;
     99 	ssize_t len;
    100 	char *p;
    101 	char *name;
    102 	struct vertex *from = 0;
    103 
    104 	while ((len = getline(&line, &size, fp)) != -1) {
    105 		if (line[len - 1] == '\n')
    106 			line[--len] = 0;
    107 		for (p = line; p;) {
    108 			SKIP(name, p, isspace);
    109 			if (!*name)
    110 				break;
    111 			SKIP(p, name, !isspace);
    112 			TOKEN_END(p);
    113 			if (!from) {
    114 				from = add_vertex(enstrdup(2, name));
    115 			} else if (strcmp(from->name, name)) {
    116 				add_edge(from, add_vertex(enstrdup(2, name)));
    117 				from = 0;
    118 			} else {
    119 				from = 0;
    120 			}
    121 		}
    122 	}
    123 
    124 	free(line);
    125 
    126 	if (from)
    127 		enprintf(2, "odd number of tokens in input\n");
    128 }
    129 
    130 static int
    131 sort_graph_visit(struct vertex *u)
    132 {
    133 	struct edge *e = &(u->edges);
    134 	struct vertex *v;
    135 	int r = 0;
    136 	u->colour = GREY;
    137 	printf("%s\n", u->name);
    138 	while ((e = e->next)) {
    139 		v = e->to;
    140 		if (v->colour == WHITE) {
    141 			v->in_edges -= 1;
    142 			if (v->in_edges == 0)
    143 				r |= sort_graph_visit(v);
    144 		} else if (v->colour == GREY) {
    145 			r = 1;
    146 			fprintf(stderr, "%s: loop detected between %s and %s\n",
    147 			        argv0, u->name, v->name);
    148 		}
    149 	}
    150 	u->colour = BLACK;
    151 	return r;
    152 }
    153 
    154 static int
    155 sort_graph(void)
    156 {
    157 	struct vertex *u, *prev;
    158 	int r = 0;
    159 	size_t in_edges;
    160 	for (in_edges = 0; graph.next; in_edges++) {
    161 		for (prev = &graph; (u = prev->next); prev = u) {
    162 			if (u->colour != WHITE)
    163 				goto unlist;
    164 			if (u->in_edges > in_edges)
    165 				continue;
    166 			r |= sort_graph_visit(u);
    167 		unlist:
    168 			prev->next = u->next;
    169 			u = prev;
    170 		}
    171 	}
    172 	return r;
    173 }
    174 
    175 static void
    176 usage(void)
    177 {
    178 	enprintf(2, "usage: %s [file]\n", argv0);
    179 }
    180 
    181 int
    182 main(int argc, char *argv[])
    183 {
    184 	FILE *fp = stdin;
    185 	const char *fn = "<stdin>";
    186 	int ret = 0;
    187 
    188 	ARGBEGIN {
    189 	default:
    190 		usage();
    191 	} ARGEND
    192 
    193 	if (argc > 1)
    194 		usage();
    195 	if (argc && strcmp(*argv, "-"))
    196 		if (!(fp = fopen(fn = *argv, "r")))
    197 			enprintf(2, "fopen %s:", *argv);
    198 
    199 	memset(&graph, 0, sizeof(graph));
    200 	load_graph(fp);
    201 	enfshut(2, fp, fn);
    202 
    203 	ret = sort_graph();
    204 
    205 	if (fshut(stdout, "<stdout>") | fshut(stderr, "<stderr>"))
    206 		ret = 2;
    207 
    208 	return ret;
    209 }