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