nsz Git - libfirm/blob - ir/kaps/pbqp_edge.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 edges.
  23  * @date    02.10.2008
  24  * @author  Sebastian Buchwald
  25  */
  26 #include "config.h"
  27
  28 #include "adt/array.h"
  29 #include "assert.h"
  30
  31 #include "kaps.h"
  32 #include "matrix.h"
  33 #include "optimal.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 "pbqp_t.h"
  39
  40 pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index,
  41                         pbqp_matrix_t *costs)
  42 {
  43         int transpose = 0;
  44         pbqp_edge_t *edge = OALLOC(&pbqp->obstack, pbqp_edge_t);
  45         pbqp_node_t *src_node;
  46         pbqp_node_t *tgt_node;
  47
  48         if (tgt_index < src_index) {
  49                 int tmp = src_index;
  50                 src_index = tgt_index;
  51                 tgt_index = tmp;
  52
  53                 transpose = 1;
  54         }
  55
  56         src_node = get_node(pbqp, src_index);
  57
  58         tgt_node = get_node(pbqp, tgt_index);
  59
  60         if (transpose) {
  61                 edge->costs = pbqp_matrix_copy_and_transpose(pbqp, costs);
  62         } else {
  63                 edge->costs = pbqp_matrix_copy(pbqp, costs);
  64         }
  65
  66         /*
  67          * Connect edge with incident nodes. Since the edge is allocated, we know
  68          * that it don't appear in the edge lists of the nodes.
  69          */
  70         ARR_APP1(pbqp_edge_t *, src_node->edges, edge);
  71         edge->src = src_node;
  72         ARR_APP1(pbqp_edge_t *, tgt_node->edges, edge);
  73         edge->tgt = tgt_node;
  74         edge->bucket_index = UINT_MAX;
  75
  76         return edge;
  77 }
  78
  79 void delete_edge(pbqp_edge_t *edge)
  80 {
  81         pbqp_node_t  *src_node;
  82         pbqp_node_t  *tgt_node;
  83
  84         src_node = edge->src;
  85         tgt_node = edge->tgt;
  86
  87         disconnect_edge(src_node, edge);
  88         disconnect_edge(tgt_node, edge);
  89
  90         edge->src = NULL;
  91         edge->tgt = NULL;
  92
  93         reorder_node_after_edge_deletion(src_node);
  94         reorder_node_after_edge_deletion(tgt_node);
  95 }
  96
  97 unsigned is_deleted(pbqp_edge_t *edge)
  98 {
  99         unsigned deleted;
 100
 101         deleted = (edge->src == NULL) && (edge-> tgt == NULL);
 102
 103         return deleted;
 104 }
 105
 106 pbqp_edge_t *pbqp_edge_deep_copy(pbqp_t *pbqp, pbqp_edge_t *edge,
 107                                  pbqp_node_t *src_node, pbqp_node_t *tgt_node)
 108 {
 109         pbqp_edge_t *copy = OALLOC(&pbqp->obstack, pbqp_edge_t);
 110         assert(src_node);
 111         assert(tgt_node);
 112
 113         copy->costs = pbqp_matrix_copy(pbqp, edge->costs);
 114
 115         /* Connect edge with incident nodes. */
 116         copy->src = src_node;
 117         copy->tgt = tgt_node;
 118         copy->bucket_index = UINT_MAX;
 119
 120         return copy;
 121 }