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