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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   PBQP nodes.
  23  * @date    02.10.2008
  24  * @author  Sebastian Buchwald
  25  */
  26 #include "config.h"
  27
  28 #include "adt/array.h"
  29
  30 #include "assert.h"
  31
  32 #include "bucket.h"
  33 #include "pbqp_edge.h"
  34 #include "pbqp_edge_t.h"
  35 #include "pbqp_node.h"
  36 #include "pbqp_node_t.h"
  37 #include "vector.h"
  38
  39 pbqp_node_t *alloc_node(pbqp_t *pbqp, unsigned node_index, vector_t *costs)
  40 {
  41         pbqp_node_t *node = OALLOC(&pbqp->obstack, pbqp_node_t);
  42
  43         node->edges = NEW_ARR_F(pbqp_edge_t *, 0);
  44         node->costs = vector_copy(pbqp, costs);
  45         node->bucket_index = UINT_MAX;
  46         node->solution = UINT_MAX;
  47         node->index = node_index;
  48
  49         return node;
  50 }
  51
  52 int is_connected(pbqp_node_t *node, pbqp_edge_t *edge)
  53 {
  54         pbqp_edge_t **edges;
  55         size_t        edge_index;
  56         size_t        edge_len;
  57
  58         assert(node);
  59         if (edge->src != node && edge->tgt != node) return 0;
  60
  61         edges = node->edges;
  62         edge_len = ARR_LEN(edges);
  63
  64         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  65                 pbqp_edge_t *edge_candidate = edges[edge_index];
  66                 if (edge_candidate == edge) {
  67                         return 1;
  68                 }
  69         }
  70
  71         return 0;
  72 }
  73
  74 void disconnect_edge(pbqp_node_t *node, pbqp_edge_t *edge)
  75 {
  76         pbqp_edge_t **edges;
  77         size_t        edge_index;
  78         size_t        edge_len;
  79
  80         edges = node->edges;
  81         edge_len = ARR_LEN(edges);
  82
  83         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  84                 pbqp_edge_t *edge_candidate = edges[edge_index];
  85                 if (edge_candidate == edge) {
  86                         edges[edge_index] = edges[edge_len - 1];
  87                         ARR_SHRINKLEN(edges, (int)edge_len - 1);
  88                         break;
  89                 }
  90         }
  91 }
  92
  93 unsigned pbqp_node_get_degree(pbqp_node_t *node)
  94 {
  95         return ARR_LEN(node->edges);
  96 }
  97
  98 pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket,
  99                                  pbqp_node_t *node)
 100 {
 101         unsigned     edge_index;
 102         unsigned     edge_length = pbqp_node_get_degree(node);
 103         pbqp_node_t *copy        = OALLOC(&pbqp->obstack, pbqp_node_t);
 104
 105         copy->edges        = NEW_ARR_F(pbqp_edge_t *, 0);
 106         for (edge_index = 0; edge_index < edge_length; ++edge_index) {
 107                 pbqp_edge_t *edge_copy = NULL;
 108                 pbqp_edge_t *edge      = node->edges[edge_index];
 109                 int          is_src    = edge->src == node;
 110
 111                 if (is_src) {
 112                         unsigned other_index = edge->tgt->bucket_index;
 113                         unsigned is_copied   = other_index < node->bucket_index;
 114
 115                         if (is_copied) {
 116                                 pbqp_node_t *other_copy = new_bucket[other_index];
 117                                 unsigned     degree     = pbqp_node_get_degree(other_copy);
 118                                 unsigned     index;
 119
 120                                 for (index = 0; index < degree; ++index) {
 121                                         if (other_copy->edges[index]->src == node) {
 122                                                 edge_copy      = other_copy->edges[index];
 123                                                 edge_copy->src = copy;
 124                                                 break;
 125                                         }
 126                                 }
 127                         } else {
 128                                 edge_copy = pbqp_edge_deep_copy(pbqp, edge, copy, edge->tgt);
 129                         }
 130                 } else {
 131                         unsigned other_index = edge->src->bucket_index;
 132                         unsigned is_copied   = other_index < node->bucket_index;
 133
 134                         if (is_copied) {
 135                                 pbqp_node_t *other_copy = new_bucket[other_index];
 136                                 unsigned     degree     = pbqp_node_get_degree(other_copy);
 137                                 unsigned     index;
 138
 139                                 for (index = 0; index < degree; ++index) {
 140                                         if (other_copy->edges[index]->tgt == node) {
 141                                                 edge_copy      = other_copy->edges[index];
 142                                                 edge_copy->tgt = copy;
 143                                                 break;
 144                                         }
 145                                 }
 146                         } else {
 147                                 edge_copy = pbqp_edge_deep_copy(pbqp, edge, edge->src, copy);
 148                         }
 149                 }
 150                 ARR_APP1(pbqp_edge_t *, copy->edges, edge_copy);
 151         }
 152         copy->costs        = vector_copy(pbqp, node->costs);
 153         copy->bucket_index = node->bucket_index;
 154         copy->solution     = node->solution;
 155         copy->index   = node->index;
 156
 157         return copy;
 158 }