tsort.c - sbase - suckless unix tools
(HTM) git clone git://git.suckless.org/sbase
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) 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 }