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