graph.c

   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"
   7
   8 static struct graphpin *get_last_pin(struct graphnode *node)
   9 {
  10     struct graphpin *pin;
  11     for (pin=node->pins; pin && pin->next; pin=pin->next);
  12     return pin;
  13 }
  14
  15 struct graphpin *graphnode_get_pin(struct graphnode *node, enum direction dir)
  16 {
  17     struct graphpin *pin;
  18     for (pin=node->pins; pin; pin=pin->next){
  19         if (pin->dir == dir){
  20             break;
  21         }
  22     }
  23     return pin;
  24 }
  25
  26 err_t graphnode_add_pin(struct graphnode *node, struct graphpin **pin_out)
  27 {
  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");
  33     }
  34     memset(pin, 0, sizeof *pin);
  35     pin->node = node;
  36     pin->edge = NULL;
  37
  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;
  44     }
  45
  46     *pin_out = pin;
  47     return EOK;
  48 }
  49
  50 err_t graphnode_create(struct graphnode **node_out, const struct graphnode_functab *functab, size_t extra_bytes)
  51 {
  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");
  56     }
  57     memset(node, 0, sizeof *node);
  58     node->functab = functab;
  59     node->extra = node->extra_data;
  60     *node_out = node;
  61     return EOK;
  62 }
  63
  64 void graphnode_free(struct graphnode *node)
  65 {
  66     struct graphpin *pin, *pin_next;
  67     struct graphedge *edge;
  68
  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
  79         }
  80         free(pin);
  81         pin = pin_next;
  82     }
  83
  84     free(node);
  85 }
  86
  87 bool graphnode_is_source(struct graphnode *node)
  88 {
  89     struct graphpin *pin;
  90     for (pin=node->pins; pin; pin=pin->next){
  91         if (pin->dir != DIR_OUT){
  92             return false;
  93         }
  94     }
  95     return true;
  96 }
  97
  98 bool graphnode_all_inputs_connected(struct graphnode *node)
  99 {
 100     struct graphpin *pin;
 101     for (pin=node->pins; pin; pin=pin->next){
 102         if (pin->dir == DIR_IN && !pin->edge){
 103             return false;
 104         }
 105     }
 106     return true;
 107 }
 108
 109 err_t graph_create(struct graph *graph)
 110 {
 111     graph->node_first = graph->node_last = NULL;
 112     return EOK;
 113 }
 114
 115 void graph_destroy(struct graph *graph)
 116 {
 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;
 122     }
 123     graph->node_first = graph->node_last = NULL;
 124 }
 125
 126 err_t graph_add_node(struct graph *graph, struct graphnode *node)
 127 {
 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;
 133 }
 134
 135 err_t graph_remove_node(struct graph *graph, struct graphnode *node)
 136 {
 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;
 140 }
 141
 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)
 144 {
 145     struct graphnode *node;
 146     struct graphpin *pin2;
 147     bool found_input = false;
 148
 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);
 156             }
 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);
 164             }
 165             *af = pin2->edge->buf.format;
 166         }
 167     }
 168     return EOK;
 169 }
 170
 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)
 174 {
 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;
 182     }
 183
 184     err = graph_add_node(graph, node);
 185     if (err != EOK){
 186         return err;
 187     }
 188
 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);
 194
 195     err = graph_connect(graph, a, in_pin);
 196     if (err != EOK){
 197         return err;
 198     }
 199
 200     err = graph_connect(graph, out_pin, b);
 201     if (err != EOK){
 202         return err;
 203     }
 204     // done
 205     *node_out = node;
 206     return EOK;
 207 }
 208
 209 static err_t do_connect(struct graph *graph, struct graphpin *a, struct graphpin *b, const struct aformat *af)
 210 {
 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");
 216     }
 217
 218     buffer_init(&edge->buf);
 219     edge->buf.format = *af;
 220
 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;
 226         }
 227     }
 228
 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;
 234         }
 235     }
 236
 237     edge->a = a;
 238     edge->b = b;
 239     edge->processed = false;
 240     a->edge = b->edge = edge;
 241     return EOK;
 242 }
 243
 244 err_t graph_connect(struct graph *graph, struct graphpin *a, struct graphpin *b)
 245 {
 246     struct aformat af, af2;
 247     struct graphnode *cvt_node;
 248     struct graphpin *cvt_input;
 249     err_t err;
 250
 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;
 264             }
 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;
 270             }
 271         }
 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;
 281                 }
 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);
 288             }
 289         }
 290         // actually do the connection
 291         return do_connect(graph, a, b, &af);
 292     }
 293 }
 294
 295 // count the number of unprocessed incoming edges of a node
 296 static int count_incoming(struct graphnode *node)
 297 {
 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;
 303         }
 304     }
 305     return n;
 306 }
 307
 308 err_t graph_sort(struct graph *graph)
 309 {
 310     // stack of nodes
 311     struct stack_item {
 312         struct stack_item *prev;
 313         struct graphnode *node;
 314     } *S = NULL, *new, *old;
 315
 316     struct graphnode *n, *m, *prev_L, **next_ptr_ptr;
 317     struct graphpin *pin;
 318     struct graphedge *edge;
 319
 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");
 329             }
 330             new->prev = S;
 331             new->node = n;
 332             S = new;
 333         }
 334     }
 335
 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
 355             ){
 356                 continue;
 357             }
 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");
 372                 }
 373                 new->prev = S;
 374                 new->node = m;
 375                 S = new;
 376             }
 377         }
 378     }
 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;
 382
 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.
 385
 386     return EOK;
 387 }
 388
 389 err_t graph_run(struct graph *graph)
 390 {
 391     struct graphnode *node;
 392     err_t err;
 393
 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;
 399             }
 400         }
 401     }
 402     return EOK;
 403 }