nsz Git - libfirm/blob - 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  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "adt/array.h"
  30
  31 #include "assert.h"
  32
  33 #include "bucket.h"
  34 #include "pbqp_edge.h"
  35 #include "pbqp_edge_t.h"
  36 #include "pbqp_node.h"
  37 #include "pbqp_node_t.h"
  38 #include "vector.h"
  39
  40 pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs)
  41 {
  42         pbqp_node *node = obstack_alloc(&pbqp->obstack, sizeof(*node));
  43         assert(node);
  44
  45         node->edges = NEW_ARR_F(pbqp_edge *, 0);
  46         node->costs = vector_copy(pbqp, costs);
  47         node->bucket_index = UINT_MAX;
  48         node->solution = UINT_MAX;
  49         node->index = node_index;
  50
  51         return node;
  52 }
  53
  54 int is_connected(pbqp_node *node, pbqp_edge *edge)
  55 {
  56         pbqp_edge **edges;
  57         unsigned    edge_index;
  58         unsigned    edge_len;
  59
  60         assert(node);
  61         assert(edge);
  62
  63         if (edge->src != node && edge->tgt != node) return 0;
  64
  65         edges = node->edges;
  66         edge_len = ARR_LEN(edges);
  67
  68         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  69                 pbqp_edge *edge_candidate = edges[edge_index];
  70                 if (edge_candidate == edge) {
  71                         return 1;
  72                 }
  73         }
  74
  75         return 0;
  76 }
  77
  78 void disconnect_edge(pbqp_node *node, pbqp_edge *edge)
  79 {
  80         pbqp_edge **edges;
  81         unsigned    edge_index;
  82         unsigned    edge_len;
  83
  84         edges = node->edges;
  85         edge_len = ARR_LEN(edges);
  86
  87         for (edge_index = 0; edge_index < edge_len; ++edge_index) {
  88                 pbqp_edge *edge_candidate = edges[edge_index];
  89                 if (edge_candidate == edge) {
  90                         edges[edge_index] = edges[edge_len - 1];
  91                         ARR_SHRINKLEN(edges, (int)edge_len - 1);
  92                         break;
  93                 }
  94         }
  95 }
  96
  97 unsigned pbqp_node_get_degree(pbqp_node *node)
  98 {
  99         assert(node);
 100         return ARR_LEN(node->edges);
 101 }
 102
 103 pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node_bucket new_bucket, pbqp_node *node)
 104 {
 105         unsigned   edge_index;
 106         unsigned   edge_length = pbqp_node_get_degree(node);
 107         pbqp_node *copy        = obstack_alloc(&pbqp->obstack, sizeof(*node));
 108
 109         assert(copy);
 110
 111         copy->edges        = NEW_ARR_F(pbqp_edge *, 0);
 112         for (edge_index = 0; edge_index < edge_length; ++edge_index) {
 113                 pbqp_edge *edge_copy = NULL;
 114                 pbqp_edge *edge      = node->edges[edge_index];
 115                 int        is_src    = edge->src == node;
 116
 117                 if (is_src) {
 118                         unsigned other_index = edge->tgt->bucket_index;
 119                         unsigned is_copied   = other_index < node->bucket_index;
 120
 121                         if (is_copied) {
 122                                 pbqp_node *other_copy = new_bucket[other_index];
 123                                 unsigned degree = pbqp_node_get_degree(other_copy);
 124                                 unsigned index;
 125
 126                                 for (index = 0; index < degree; ++index) {
 127                                         if (other_copy->edges[index]->src == node) {
 128                                                 edge_copy      = other_copy->edges[index];
 129                                                 edge_copy->src = copy;
 130                                                 break;
 131                                         }
 132                                 }
 133                         } else {
 134                                 edge_copy = pbqp_edge_deep_copy(pbqp, edge, copy, edge->tgt);
 135                         }
 136                 } else {
 137                         unsigned other_index = edge->src->bucket_index;
 138                         unsigned is_copied   = other_index < node->bucket_index;
 139
 140                         if (is_copied) {
 141                                 pbqp_node *other_copy = new_bucket[other_index];
 142                                 unsigned degree = pbqp_node_get_degree(other_copy);
 143                                 unsigned index;
 144
 145                                 for (index = 0; index < degree; ++index) {
 146                                         if (other_copy->edges[index]->tgt == node) {
 147                                                 edge_copy      = other_copy->edges[index];
 148                                                 edge_copy->tgt = copy;
 149                                                 break;
 150                                         }
 151                                 }
 152                         } else {
 153                                 edge_copy = pbqp_edge_deep_copy(pbqp, edge, edge->src, copy);
 154                         }
 155                 }
 156                 ARR_APP1(pbqp_edge *, copy->edges, edge_copy);
 157         }
 158         copy->costs        = vector_copy(pbqp, node->costs);
 159         copy->bucket_index = node->bucket_index;
 160         copy->solution     = node->solution;
 161         copy->index   = node->index;
 162
 163         return copy;
 164 }