scons --> make
[aftubes.git] / graph.c
blob4bfdd7bd6aee7c21a49965037e59b3485197a779
1 #include "graph.h"
2 #include "errors.h"
3 #include "stdlib.h"
4 #include "string.h"
5 #include "modules/modules.h"
6 #include "assert.h"
8 static struct graphpin *get_last_pin(struct graphnode *node)
10 struct graphpin *pin;
11 for (pin=node->pins; pin && pin->next; pin=pin->next);
12 return pin;
15 struct graphpin *graphnode_get_pin(struct graphnode *node, enum direction dir)
17 struct graphpin *pin;
18 for (pin=node->pins; pin; pin=pin->next){
19 if (pin->dir == dir){
20 break;
23 return pin;
26 err_t graphnode_add_pin(struct graphnode *node, struct graphpin **pin_out)
28 // TODO: allocate node + pins in one block?
29 struct graphpin *pin = malloc(sizeof *pin), *pin_prev;
30 if (!pin){
31 // :-(
32 return make_error(ENOMEM, node, "memory full: allocating graph node pin");
34 memset(pin, 0, sizeof *pin);
35 pin->node = node;
36 pin->edge = NULL;
38 pin->next = NULL;
39 pin_prev = get_last_pin(node);
40 if (pin_prev){
41 pin_prev->next = pin;
42 } else {
43 node->pins = pin;
46 *pin_out = pin;
47 return EOK;
50 err_t graphnode_create(struct graphnode **node_out, const struct graphnode_functab *functab, size_t extra_bytes)
52 struct graphnode *node;
53 node = malloc(sizeof *node + extra_bytes);
54 if (!node){
55 return make_error(ENOMEM, NULL, "memory full: allocating graph node");
57 memset(node, 0, sizeof *node);
58 node->functab = functab;
59 node->extra = node->extra_data;
60 *node_out = node;
61 return EOK;
64 void graphnode_free(struct graphnode *node)
66 struct graphpin *pin, *pin_next;
67 struct graphedge *edge;
69 pin = node->pins;
70 while (pin){
71 pin_next = pin->next;
72 if (pin->edge){
73 // it's connected
74 // disconnect it (free the edge)
75 edge = pin->edge;
76 edge->a->edge = NULL;
77 edge->b->edge = NULL;
78 free(edge); // XXX: may need more freeing than this in the future
80 free(pin);
81 pin = pin_next;
84 free(node);
87 bool graphnode_is_source(struct graphnode *node)
89 struct graphpin *pin;
90 for (pin=node->pins; pin; pin=pin->next){
91 if (pin->dir != DIR_OUT){
92 return false;
95 return true;
98 bool graphnode_all_inputs_connected(struct graphnode *node)
100 struct graphpin *pin;
101 for (pin=node->pins; pin; pin=pin->next){
102 if (pin->dir == DIR_IN && !pin->edge){
103 return false;
106 return true;
109 err_t graph_create(struct graph *graph)
111 graph->node_first = graph->node_last = NULL;
112 return EOK;
115 void graph_destroy(struct graph *graph)
117 struct graphnode *node = graph->node_first, *node_next;
118 while (node){
119 node_next = node->next;
120 graphnode_free(node);
121 node = node_next;
123 graph->node_first = graph->node_last = NULL;
126 err_t graph_add_node(struct graph *graph, struct graphnode *node)
128 node->prev = graph->node_last;
129 node->next = NULL;
130 *(graph->node_last ? &graph->node_last->next : &graph->node_first) = node;
131 graph->node_last = node;
132 return EOK;
135 err_t graph_remove_node(struct graph *graph, struct graphnode *node)
137 *(node->prev ? &node->prev->next : &graph->node_first) = node->next;
138 *(node->next ? &node->next->prev : &graph->node_last) = node->prev;
139 return EOK;
142 // guess the format of output pin 'pin' - i.e. same as input format
143 static err_t guess_output_format(struct graphpin *pin, struct aformat *af)
145 struct graphnode *node;
146 struct graphpin *pin2;
147 bool found_input = false;
149 node = pin->node;
150 for (pin2=node->pins; pin2; pin2=pin2->next){
151 if (pin2->dir == DIR_IN){
152 if (found_input){
153 return make_error(ECANNOT_GUESS_FORMAT, node,
154 "cannot guess the output format of node \"%s\", because it has more than one input",
155 node->name);
157 found_input = true;
158 if (!pin2->edge){
159 // the input pin is not connected, so it won't have
160 // a format, yet
161 return make_error(ECANNOT_GUESS_FORMAT, node,
162 "cannot guess the output format of node \"%s\", because its input is not connected",
163 node->name);
165 *af = pin2->edge->buf.format;
168 return EOK;
171 // create a converter node to convert between formats
172 static err_t create_converter_node(struct graph *graph, struct aformat *src_af, struct aformat *dest_af,
173 struct graphpin *a, struct graphpin *b, struct graphnode **node_out)
175 struct graphnode *node;
176 struct graphpin *out_pin, *in_pin;
177 err_t err;
178 // create the new node
179 err = audio_converter_create(&node, src_af, dest_af);
180 if (err != EOK){
181 return err;
184 err = graph_add_node(graph, node);
185 if (err != EOK){
186 return err;
189 // connect it
190 out_pin = graphnode_get_pin(node, DIR_OUT);
191 in_pin = graphnode_get_pin(node, DIR_IN);
192 assert(out_pin);
193 assert(in_pin);
195 err = graph_connect(graph, a, in_pin);
196 if (err != EOK){
197 return err;
200 err = graph_connect(graph, out_pin, b);
201 if (err != EOK){
202 return err;
204 // done
205 *node_out = node;
206 return EOK;
209 static err_t do_connect(struct graph *graph, struct graphpin *a, struct graphpin *b, const struct aformat *af)
211 struct graphedge *edge = malloc(sizeof *edge);
212 err_t err;
213 if (!edge){
214 // ack!
215 return make_error(ENOMEM, graph, "memory full: allocating edge");
218 buffer_init(&edge->buf);
219 edge->buf.format = *af;
221 if (a->node->functab->set_buffer){
222 err = a->node->functab->set_buffer(a->node, a, &edge->buf);
223 if (err != EOK){
224 free(edge);
225 return err;
229 if (b->node->functab->set_buffer){
230 err = b->node->functab->set_buffer(b->node, b, &edge->buf);
231 if (err != EOK){
232 free(edge);
233 return err;
237 edge->a = a;
238 edge->b = b;
239 edge->processed = false;
240 a->edge = b->edge = edge;
241 return EOK;
244 err_t graph_connect(struct graph *graph, struct graphpin *a, struct graphpin *b)
246 struct aformat af, af2;
247 struct graphnode *cvt_node;
248 struct graphpin *cvt_input;
249 err_t err;
251 // check a and b direction
252 if (!(a->dir == DIR_OUT && b->dir == DIR_IN)){
253 // oh dear.
254 return make_error(EPINDIR, graph,
255 "incorrect pin directions while trying to connect");
256 } else {
257 // if a is a source node, it will be able to provide us with a media type
258 // if a is not a source node, all its inputs must be connected
259 // otherwise we won't know what output format to use.
260 if (a->node->functab->get_output_format){
261 err = a->node->functab->get_output_format(a->node, a, &af);
262 if (err != EOK){
263 return err;
265 } else {
266 // assume output format is same as input format
267 err = guess_output_format(a, &af);
268 if (err != EOK){
269 return err;
272 // check media type with b node
273 if (b->node->functab->is_acceptable_input_format
274 && !b->node->functab->is_acceptable_input_format(b->node, b, &af)){
275 // it doesn't like that input format
276 // we'll have to add a converter node
277 if (b->node->functab->get_ideal_input_format){
278 err = b->node->functab->get_ideal_input_format(b->node, b, &af2);
279 if (err != EOK){
280 return err;
282 cvt_input = NULL;
283 return create_converter_node(graph, &af, &af2,
284 a, b, &cvt_node);
285 } else {
286 return make_error(ENO_AGREEABLE_FORMAT, graph, "cannot agree on a common media format (\"%s\" won't specify an ideal format)",
287 b->node->name);
290 // actually do the connection
291 return do_connect(graph, a, b, &af);
295 // count the number of unprocessed incoming edges of a node
296 static int count_incoming(struct graphnode *node)
298 struct graphpin *pin;
299 int n = 0;
300 for (pin=node->pins; pin; pin=pin->next){
301 if (pin->dir == DIR_IN && pin->edge && !pin->edge->processed){
302 ++n;
305 return n;
308 err_t graph_sort(struct graph *graph)
310 // stack of nodes
311 struct stack_item {
312 struct stack_item *prev;
313 struct graphnode *node;
314 } *S = NULL, *new, *old;
316 struct graphnode *n, *m, *prev_L, **next_ptr_ptr;
317 struct graphpin *pin;
318 struct graphedge *edge;
320 // find all source nodes
321 for (n=graph->node_first; n; n=n->next){
322 if (graphnode_is_source(n)){
323 // insert n into S
324 new = malloc(sizeof *new); // TODO: use alloca or something?
325 if (!new){
326 // uh oh
327 // TODO: clean S
328 return make_error(ENOMEM, NULL, "memory full: allocating stack item");
330 new->prev = S;
331 new->node = n;
332 S = new;
336 // while S is not empty
337 next_ptr_ptr = &graph->sorted_nodes;
338 prev_L = NULL;
339 while (S){
340 // remove a node n from S
341 n = S->node;
342 old = S;
343 S = S->prev;
344 free(old);
345 // insert n into L (the sorted list)
346 n->sorted_prev = prev_L;
347 *next_ptr_ptr = n;
348 next_ptr_ptr = &n->sorted_next;
349 prev_L = n;
350 // for each node m with an edge from n to m
351 for (pin=n->pins; pin; pin=pin->next){
352 if (pin->dir != DIR_OUT
353 || !pin->edge // pin isn't connected (ignore it)
354 || pin->edge->processed // edge already 'removed' by algorithm
356 continue;
358 edge = pin->edge;
359 m = edge->b->node;
360 // remove edge from graph (we actually want to keep it, so we just
361 // mark it, and not do any real removal)
362 edge->processed = true;
363 // does it have any other incoming edges?
364 if (count_incoming(m) == 0){
365 // no!
366 // insert m into S
367 new = malloc(sizeof *new);
368 if (!new){
369 // ugh
370 // TODO: clean S
371 return make_error(ENOMEM, NULL, "memory full: allocating stack item");
373 new->prev = S;
374 new->node = m;
375 S = new;
379 // set the next pointer of the last node in the sequence to NULL
380 // this finishes off the linked list.
381 *next_ptr_ptr = NULL;
383 // TODO: if the graph still has unprocessed edges, then the graph
384 // has at least one cycle. Maybe we should do something about that.
386 return EOK;
389 err_t graph_run(struct graph *graph)
391 struct graphnode *node;
392 err_t err;
394 for (node=graph->sorted_nodes; node; node=node->sorted_next){
395 if (node->functab->run){
396 err = node->functab->run(node);
397 if (err != EOK){
398 return err;
402 return EOK;