graph.c

   1 #include "graph.h"
   2 #include "errors.h"
   3 #include "stdlib.h"
   4 #include "string.h"
   5 #include "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 (graphnode_all_inputs_connected(a->node)){
 261             // get media type from source
 262             if (a->node->functab->get_output_format){
 263                 err = a->node->functab->get_output_format(a->node, a, &af);
 264                 if (err != EOK){
 265                     return err;
 266                 }
 267             } else {
 268                 // assume output format is same as input format
 269                 err = guess_output_format(a, &af);
 270                 if (err != EOK){
 271                     return err;
 272                 }
 273             }
 274             // check media type with b node
 275             if (b->node->functab->is_acceptable_input_format
 276               && !b->node->functab->is_acceptable_input_format(b->node, b, &af)){
 277                 // it doesn't like that input format
 278                 // we'll have to add a converter node
 279                 if (b->node->functab->get_ideal_input_format){
 280                     err = b->node->functab->get_ideal_input_format(b->node, b, &af2);
 281                     if (err != EOK){
 282                         return err;
 283                     }
 284                     cvt_input = NULL;
 285                     return create_converter_node(graph, &af, &af2,
 286                       a, b, &cvt_node);
 287                 } else {
 288                     return make_error(ENO_AGREEABLE_FORMAT, graph, "cannot agree on a common media format (\"%s\" won't specify an ideal format)",
 289                       b->node->name);
 290                 }
 291             }
 292             // actually do the connection
 293             return do_connect(graph, a, b, &af);
 294         } else {
 295             // there are unconnected inputs, so we can't connect
 296             // (because we don't know what output format to use
 297             // without an input format)
 298             return make_error(EUNCONNECTED, graph,
 299               "unconnected input pins: cannot determine media type (\"%s\")",
 300               a->node->name);
 301         }
 302     }
 303 }
 304
 305 // count the number of unprocessed incoming edges of a node
 306 static int count_incoming(struct graphnode *node)
 307 {
 308     struct graphpin *pin;
 309     int n = 0;
 310     for (pin=node->pins; pin; pin=pin->next){
 311         if (pin->dir == DIR_IN && pin->edge && !pin->edge->processed){
 312             ++n;
 313         }
 314     }
 315     return n;
 316 }
 317
 318 err_t graph_sort(struct graph *graph)
 319 {
 320     // stack of nodes
 321     struct stack_item {
 322         struct stack_item *prev;
 323         struct graphnode *node;
 324     } *S = NULL, *new, *old;
 325
 326     struct graphnode *n, *m, *prev_L, **next_ptr_ptr;
 327     struct graphpin *pin;
 328     struct graphedge *edge;
 329
 330     // find all source nodes
 331     for (n=graph->node_first; n; n=n->next){
 332         if (graphnode_is_source(n)){
 333             // insert n into S
 334             new = malloc(sizeof *new); // TODO: use alloca or something?
 335             if (!new){
 336                 // uh oh
 337                 // TODO: clean S
 338                 return make_error(ENOMEM, NULL, "memory full: allocating stack item");
 339             }
 340             new->prev = S;
 341             new->node = n;
 342             S = new;
 343         }
 344     }
 345
 346     // while S is not empty
 347     next_ptr_ptr = &graph->sorted_nodes;
 348     prev_L = NULL;
 349     while (S){
 350         // remove a node n from S
 351         n = S->node;
 352         old = S;
 353         S = S->prev;
 354         free(old);
 355         // insert n into L (the sorted list)
 356         n->sorted_prev = prev_L;
 357         *next_ptr_ptr = n;
 358         next_ptr_ptr = &n->sorted_next;
 359         prev_L = n;
 360         // for each node m with an edge from n to m
 361         for (pin=n->pins; pin; pin=pin->next){
 362             if (pin->dir != DIR_OUT
 363               || !pin->edge             // pin isn't connected (ignore it)
 364               || pin->edge->processed   // edge already 'removed' by algorithm
 365             ){
 366                 continue;
 367             }
 368             edge = pin->edge;
 369             m = edge->b->node;
 370             // remove edge from graph (we actually want to keep it, so we just
 371             // mark it, and not do any real removal)
 372             edge->processed = true;
 373             // does it have any other incoming edges?
 374             if (count_incoming(m) == 0){
 375                 // no!
 376                 // insert m into S
 377                 new = malloc(sizeof *new);
 378                 if (!new){
 379                     // ugh
 380                     // TODO: clean S
 381                     return make_error(ENOMEM, NULL, "memory full: allocating stack item");
 382                 }
 383                 new->prev = S;
 384                 new->node = m;
 385                 S = new;
 386             }
 387         }
 388     }
 389     // set the next pointer of the last node in the sequence to NULL
 390     // this finishes off the linked list.
 391     *next_ptr_ptr = NULL;
 392
 393     // TODO: if the graph still has unprocessed edges, then the graph
 394     // has at least one cycle. Maybe we should do something about that.
 395
 396     return EOK;
 397 }
 398
 399 err_t graph_run(struct graph *graph)
 400 {
 401     struct graphnode *node;
 402     err_t err;
 403
 404     for (node=graph->sorted_nodes; node; node=node->sorted_next){
 405         if (node->functab->run){
 406             err = node->functab->run(node);
 407             if (err != EOK){
 408                 return err;
 409             }
 410         }
 411     }
 412     return EOK;
 413 }