GopherProxy

	tsort.c - sbase - suckless unix tools
	git clone git://git.suckless.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 …
	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; VA…
	95 #define TOKEN_END(P) do { if (P) P++ = 0; else P = 0; } whi…
	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, na…
	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 an…
	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 }