nsz Git - libfirm/blob - ir/kaps/pbqp_node.c

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