nsz Git - libfirm/blob - pbqp_node.c

   1 #include "adt/array.h"
   2
   3 #include "assert.h"
   4
   5 #include "bucket.h"
   6 #include "pbqp_edge.h"
   7 #include "pbqp_edge_t.h"
   8 #include "pbqp_node.h"
   9 #include "pbqp_node_t.h"
  10 #include "vector.h"
  11
  12 pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs)
  13 {
  14         pbqp_node *node = obstack_alloc(&pbqp->obstack, sizeof(*node));
  15         assert(node);
  16
  17         node->edges = NEW_ARR_F(pbqp_edge *, 0);
  18         node->costs = vector_copy(pbqp, costs);
  19         node->bucket_index = UINT_MAX;
  20         node->solution = UINT_MAX;
  21         node->index = node_index;
  22
  23         return node;
  24 }
  25
  26 int is_connected(pbqp_node *node, pbqp_edge *edge)
  27 {
  28         pbqp_edge **edges;
  29         unsigned    edge_index;
  30         unsigned    edge_len;
  31
  32         assert(node);
  33         assert(edge);
  34
  35         if (edge->src != node && edge->tgt != node) return 0;
  36
  37         edges = node->edges;
  38         edge_len = ARR_LEN(edges);
  39
  40         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  41                 pbqp_edge *edge_candidate = edges[edge_index];
  42                 if (edge_candidate == edge) {
  43                         return 1;
  44                 }
  45         }
  46
  47         return 0;
  48 }
  49
  50 void disconnect_edge(pbqp_node *node, pbqp_edge *edge)
  51 {
  52         pbqp_edge **edges;
  53         unsigned    edge_index;
  54         unsigned    edge_len;
  55
  56         edges = node->edges;
  57         edge_len = ARR_LEN(edges);
  58
  59         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  60                 pbqp_edge *edge_candidate = edges[edge_index];
  61                 if (edge_candidate == edge) {
  62                         edges[edge_index] = edges[edge_len - 1];
  63                         ARR_SHRINKLEN(edges, (int)edge_len - 1);
  64                         break;
  65                 }
  66         }
  67 }
  68
  69 unsigned pbqp_node_get_degree(pbqp_node *node)
  70 {
  71         assert(node);
  72         return ARR_LEN(node->edges);
  73 }
  74
  75 pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node_bucket new_bucket, pbqp_node *node)
  76 {
  77         unsigned   edge_index;
  78         unsigned   edge_length = pbqp_node_get_degree(node);
  79         pbqp_node *copy        = obstack_alloc(&pbqp->obstack, sizeof(*node));
  80         assert(copy);
  81
  82         copy->edges        = NEW_ARR_F(pbqp_edge *, 0);
  83         for (edge_index = 0; edge_index < edge_length; ++edge_index) {
  84                 pbqp_edge *edge_copy;
  85                 pbqp_edge *edge        = node->edges[edge_index];
  86                 int        is_src      = edge->src == node;
  87
  88                 if (is_src) {
  89                         unsigned other_index = edge->tgt->bucket_index;
  90                         unsigned is_copied   = other_index < node->bucket_index;
  91
  92                         if (is_copied) {
  93                                 pbqp_node *other_copy = new_bucket[other_index];
  94                                 unsigned degree = pbqp_node_get_degree(other_copy);
  95                                 unsigned index;
  96
  97                                 for (index = 0; index < degree; ++index) {
  98                                         if (other_copy->edges[index]->src == node) {
  99                                                 edge_copy      = other_copy->edges[index];
 100                                                 edge_copy->src = copy;
 101                                                 break;
 102                                         }
 103                                 }
 104                         } else {
 105                                 edge_copy = pbqp_edge_deep_copy(pbqp, edge, copy, edge->tgt);
 106                         }
 107                 } else {
 108                         unsigned other_index = edge->src->bucket_index;
 109                         unsigned is_copied   = other_index < node->bucket_index;
 110
 111                         if (is_copied) {
 112                                 pbqp_node *other_copy = new_bucket[other_index];
 113                                 unsigned degree = pbqp_node_get_degree(other_copy);
 114                                 unsigned index;
 115
 116                                 for (index = 0; index < degree; ++index) {
 117                                         if (other_copy->edges[index]->tgt == node) {
 118                                                 edge_copy      = other_copy->edges[index];
 119                                                 edge_copy->tgt = copy;
 120                                                 break;
 121                                         }
 122                                 }
 123                         } else {
 124                                 edge_copy = pbqp_edge_deep_copy(pbqp, edge, edge->src, copy);
 125                         }
 126                 }
 127                 ARR_APP1(pbqp_edge *, copy->edges, edge_copy);
 128         }
 129         copy->costs        = vector_copy(pbqp, node->costs);
 130         copy->bucket_index = node->bucket_index;
 131         copy->solution     = node->solution;
 132         copy->index   = node->index;
 133
 134         return copy;
 135 }