nsz Git - libfirm/blob - pbqp_node.c

   1 #include "adt/array.h"
   2
   3 #include "assert.h"
   4
   5 #include "pbqp_edge.h"
   6 #include "pbqp_edge_t.h"
   7 #include "pbqp_node.h"
   8 #include "pbqp_node_t.h"
   9 #include "vector.h"
  10
  11 pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs)
  12 {
  13         pbqp_node *node = obstack_alloc(&pbqp->obstack, sizeof(*node));
  14         assert(node);
  15
  16         node->edges = NEW_ARR_F(pbqp_edge *, 0);
  17         node->costs = vector_copy(pbqp, costs);
  18         node->bucket_index = UINT_MAX;
  19         node->solution = UINT_MAX;
  20         node->index = node_index;
  21
  22         return node;
  23 }
  24
  25 int is_connected(pbqp_node *node, pbqp_edge *edge)
  26 {
  27         pbqp_edge **edges;
  28         unsigned    edge_index;
  29         unsigned    edge_len;
  30
  31         assert(node);
  32         assert(edge);
  33
  34         if (edge->src != node && edge->tgt != node) return 0;
  35
  36         edges = node->edges;
  37         edge_len = ARR_LEN(edges);
  38
  39         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  40                 pbqp_edge *edge_candidate = edges[edge_index];
  41                 if (edge_candidate == edge) {
  42                         return 1;
  43                 }
  44         }
  45
  46         return 0;
  47 }
  48
  49 void disconnect_edge(pbqp_node *node, pbqp_edge *edge)
  50 {
  51         pbqp_edge **edges;
  52         unsigned    edge_index;
  53         unsigned    edge_len;
  54
  55         edges = node->edges;
  56         edge_len = ARR_LEN(edges);
  57
  58         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  59                 pbqp_edge *edge_candidate = edges[edge_index];
  60                 if (edge_candidate == edge) {
  61                         edges[edge_index] = edges[edge_len - 1];
  62                         ARR_SHRINKLEN(edges, (int)edge_len - 1);
  63                         break;
  64                 }
  65         }
  66 }
  67
  68 unsigned pbqp_node_get_degree(pbqp_node *node)
  69 {
  70         assert(node);
  71         return ARR_LEN(node->edges);
  72 }
  73
  74 pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node *node)
  75 {
  76         unsigned   edge_index;
  77         unsigned   edge_length = pbqp_node_get_degree(node);
  78         pbqp_node *copy        = obstack_alloc(&pbqp->obstack, sizeof(*node));
  79         assert(copy);
  80
  81         copy->edges        = NEW_ARR_F(pbqp_edge *, 0);
  82         for (edge_index = 0; edge_index < edge_length; ++edge_index) {
  83                 ARR_APP1(pbqp_edge *, copy->edges, pbqp_edge_deep_copy(pbqp, node->edges[edge_index]));
  84         }
  85         copy->costs        = vector_copy(pbqp, node->costs);
  86         copy->bucket_index = node->bucket_index;
  87         copy->solution     = node->solution;
  88         copy->index   = node->index;
  89
  90         return node;
  91 }