graph.c

   1 #include "graph.h"
   2 #include "errors.h"
   3 #include "stdlib.h"
   4 #include "string.h"
   5
   6 static struct graphpin *get_last_pin(struct graphnode *node)
   7 {
   8     struct graphpin *pin;
   9     for (pin=node->pins; pin && pin->next; pin=pin->next);
  10     return pin;
  11 }
  12
  13 err_t graphnode_add_pin(struct graphnode *node, struct graphpin **pin_out)
  14 {
  15     // TODO: allocate node + pins in one block?
  16     struct graphpin *pin = malloc(sizeof *pin), *pin_prev;
  17     if (!pin){
  18         // :-(
  19         return make_error(ENOMEM, node, "memory full: allocating graph node pin");
  20     }
  21     memset(pin, 0, sizeof *pin);
  22     pin->node = node;
  23
  24     pin->next = NULL;
  25     pin_prev = get_last_pin(node);
  26     if (pin_prev){
  27         pin_prev->next = pin;
  28     } else {
  29         node->pins = pin;
  30     }
  31
  32     *pin_out = pin;
  33     return EOK;
  34 }
  35
  36 err_t graphnode_create(struct graphnode **node_out, const struct graphnode_functab *functab, size_t extra_bytes)
  37 {
  38     struct graphnode *node;
  39     node = malloc(sizeof *node + extra_bytes);
  40     if (!node){
  41         return make_error(ENOMEM, NULL, "memory full: allocating graph node");
  42     }
  43     memset(node, 0, sizeof *node);
  44     node->functab = functab;
  45     node->extra = node->extra_data;
  46     *node_out = node;
  47     return EOK;
  48 }
  49
  50 void graphnode_free(struct graphnode *node)
  51 {
  52     struct graphpin *pin, *pin_next;
  53     struct graphedge *edge;
  54
  55     pin = node->pins;
  56     while (pin){
  57         pin_next = pin->next;
  58         if (pin->edge){
  59             // it's connected
  60             // disconnect it (free the edge)
  61             edge = pin->edge;
  62             edge->a->edge = NULL;
  63             edge->b->edge = NULL;
  64             free(edge); // XXX: may need more freeing than this in the future
  65         }
  66         free(pin);
  67         pin = pin_next;
  68     }
  69
  70     free(node);
  71 }
  72
  73 bool graphnode_is_source(struct graphnode *node)
  74 {
  75     struct graphpin *pin;
  76     for (pin=node->pins; pin; pin=pin->next){
  77         if (pin->dir != DIR_OUT){
  78             return false;
  79         }
  80     }
  81     return true;
  82 }
  83
  84 bool graphnode_all_inputs_connected(struct graphnode *node)
  85 {
  86     struct graphpin *pin;
  87     for (pin=node->pins; pin; pin=pin->next){
  88         if (pin->dir == DIR_IN && !pin->edge){
  89             return false;
  90         }
  91     }
  92     return true;
  93 }
  94
  95 err_t graph_create(struct graph *graph)
  96 {
  97     graph->node_first = graph->node_last = NULL;
  98     return EOK;
  99 }
 100
 101 void graph_destroy(struct graph *graph)
 102 {
 103     struct graphnode *node = graph->node_first, *node_next;
 104     while (node){
 105         node_next = node->next;
 106         graphnode_free(node);
 107         node = node_next;
 108     }
 109     graph->node_first = graph->node_last = NULL;
 110 }
 111
 112 err_t graph_add_node(struct graph *graph, struct graphnode *node)
 113 {
 114     node->prev = graph->node_last;
 115     node->next = NULL;
 116     *(graph->node_last ? &graph->node_last->next : &graph->node_first) = node;
 117     graph->node_last = node;
 118     return EOK;
 119 }
 120
 121 err_t graph_remove_node(struct graph *graph, struct graphnode *node)
 122 {
 123     *(node->prev ? &node->prev->next : &graph->node_first) = node->next;
 124     *(node->next ? &node->next->prev : &graph->node_last) = node->prev;
 125     return EOK;
 126 }
 127
 128 static err_t do_connect(struct graph *graph, struct graphpin *a, struct graphpin *b, const struct aformat *af)
 129 {
 130     struct graphedge *edge = malloc(sizeof *edge);
 131     err_t err;
 132     if (!edge){
 133         // ack!
 134         return make_error(ENOMEM, graph, "memory full: allocating edge");
 135     }
 136
 137     buffer_init(&edge->buf);
 138     edge->buf.format = *af;
 139
 140     if (a->node->functab->set_buffer){
 141         err = a->node->functab->set_buffer(a->node, a, &edge->buf);
 142         if (err != EOK){
 143             free(edge);
 144             return err;
 145         }
 146     }
 147
 148     if (b->node->functab->set_buffer){
 149         err = b->node->functab->set_buffer(b->node, b, &edge->buf);
 150         if (err != EOK){
 151             free(edge);
 152             return err;
 153         }
 154     }
 155
 156     edge->a = a;
 157     edge->b = b;
 158     a->edge = b->edge = edge;
 159     return EOK;
 160 }
 161
 162 err_t graph_connect(struct graph *graph, struct graphpin *a, struct graphpin *b)
 163 {
 164     struct aformat af;
 165     err_t err;
 166
 167     // check a and b direction
 168     if (!(a->dir == DIR_OUT && b->dir == DIR_IN)){
 169         // oh dear.
 170         return make_error(EPINDIR, graph,
 171           "incorrect pin directions while trying to connect");
 172     } else {
 173         // if a is a source node, it will be able to provide us with a media type
 174         // if a is not a source node, all its inputs must be connected
 175         // otherwise we won't know what output format to use.
 176         if (graphnode_all_inputs_connected(a->node)){
 177             // get media type from source
 178             err = a->node->functab->get_output_format(a->node, a, &af);
 179             if (err != EOK){
 180                 return err;
 181             }
 182             // check media type with b node
 183             if (b->node->functab->is_acceptable_input_format
 184               && !b->node->functab->is_acceptable_input_format(b->node, b, &af)){
 185                 return make_error(ENO_AGREEABLE_FORMAT, graph, "cannot agree on a common media format");
 186             }
 187             // actually do the connection
 188             return do_connect(graph, a, b, &af);
 189         } else {
 190             // there are unconnected inputs, so we can't connect
 191             // (because we don't know what output format to use
 192             // without an input format)
 193             return make_error(EUNCONNECTED, graph,
 194               "unconnected input pins: cannot determine media type");
 195         }
 196     }
 197 }
 198
 199 // count the number of unprocessed incoming edges of a node
 200 static int count_incoming(struct graphnode *node)
 201 {
 202     struct graphpin *pin;
 203     int n = 0;
 204     for (pin=node->pins; pin; pin=pin->next){
 205         if (pin->dir == DIR_IN && pin->edge && !pin->edge->processed){
 206             ++n;
 207         }
 208     }
 209     return n;
 210 }
 211
 212 err_t graph_sort(struct graph *graph)
 213 {
 214     // stack of nodes
 215     struct stack_item {
 216         struct stack_item *prev;
 217         struct graphnode *node;
 218     } *S = NULL, *new, *old;
 219
 220     struct graphnode *n, *m, *prev_L, **next_ptr_ptr;
 221     struct graphpin *pin;
 222     struct graphedge *edge;
 223
 224     // find all source nodes
 225     for (n=graph->node_first; n; n=n->next){
 226         if (graphnode_is_source(n)){
 227             // insert n into S
 228             new = malloc(sizeof *new); // TODO: use alloca or something?
 229             if (!new){
 230                 // uh oh
 231                 // TODO: clean S
 232                 return make_error(ENOMEM, NULL, "memory full: allocating stack item");
 233             }
 234             new->prev = S;
 235             new->node = n;
 236             S = new;
 237         }
 238     }
 239
 240     // while S is not empty
 241     next_ptr_ptr = &graph->sorted_nodes;
 242     prev_L = NULL;
 243     while (S){
 244         // remove a node n from S
 245         n = S->node;
 246         old = S;
 247         S = S->prev;
 248         free(old);
 249         // insert n into L (the sorted list)
 250         n->sorted_prev = prev_L;
 251         *next_ptr_ptr = n;
 252         next_ptr_ptr = &n->sorted_next;
 253         prev_L = n;
 254         // for each node m with an edge from n to m
 255         for (pin=n->pins; pin; pin=pin->next){
 256             if (pin->dir != DIR_OUT
 257               || !pin->edge             // pin isn't connected (ignore it)
 258               || pin->edge->processed   // edge already 'removed' by algorithm
 259             ){
 260                 continue;
 261             }
 262             edge = pin->edge;
 263             m = edge->b->node;
 264             // remove edge from graph (we actually want to keep it, so we just
 265             // mark it, and not do any real removal)
 266             edge->processed = true;
 267             // does it have any other incoming edges?
 268             if (count_incoming(m) == 0){
 269                 // no!
 270                 // insert m into S
 271                 new = malloc(sizeof *new);
 272                 if (!new){
 273                     // ugh
 274                     // TODO: clean S
 275                     return make_error(ENOMEM, NULL, "memory full: allocating stack item");
 276                 }
 277                 new->prev = S;
 278                 new->node = m;
 279                 S = new;
 280             }
 281         }
 282     }
 283     // set the next pointer of the last node in the sequence to NULL
 284     // this finishes off the linked list.
 285     *next_ptr_ptr = NULL;
 286
 287     // TODO: if the graph still has unprocessed edges, then the graph
 288     // has at least one cycle. Maybe we should do something about that.
 289
 290     return EOK;
 291 }
 292
 293 err_t graph_run(struct graph *graph)
 294 {
 295     struct graphnode *node;
 296     err_t err;
 297
 298     for (node=graph->sorted_nodes; node; node=node->sorted_next){
 299         if (node->functab->run){
 300             err = node->functab->run(node);
 301             if (err != EOK){
 302                 return err;
 303             }
 304         }
 305     }
 306     return EOK;
 307 }