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
  46         if (tgt_index < src_index) {
  47                 int tmp = src_index;
  48                 src_index = tgt_index;
  49                 tgt_index = tmp;
  50
  51                 transpose = 1;
  52         }
  53
  54         pbqp_edge_t *edge = OALLOC(&pbqp->obstack, pbqp_edge_t);
  55         assert(edge);
  56
  57         pbqp_node_t *src_node = get_node(pbqp, src_index);
  58         assert(src_node);
  59
  60         pbqp_node_t *tgt_node = get_node(pbqp, tgt_index);
  61         assert(tgt_node);
  62
  63         if (transpose) {
  64                 edge->costs = pbqp_matrix_copy_and_transpose(pbqp, costs);
  65         } else {
  66                 edge->costs = pbqp_matrix_copy(pbqp, costs);
  67         }
  68
  69         /*
  70          * Connect edge with incident nodes. Since the edge is allocated, we know
  71          * that it don't appear in the edge lists of the nodes.
  72          */
  73         ARR_APP1(pbqp_edge_t *, src_node->edges, edge);
  74         edge->src = src_node;
  75         ARR_APP1(pbqp_edge_t *, tgt_node->edges, edge);
  76         edge->tgt = tgt_node;
  77         edge->bucket_index = UINT_MAX;
  78
  79         return edge;
  80 }
  81
  82 void delete_edge(pbqp_edge_t *edge)
  83 {
  84         pbqp_node_t  *src_node;
  85         pbqp_node_t  *tgt_node;
  86
  87         assert(edge);
  88
  89         src_node = edge->src;
  90         tgt_node = edge->tgt;
  91         assert(src_node);
  92         assert(tgt_node);
  93
  94         disconnect_edge(src_node, edge);
  95         disconnect_edge(tgt_node, edge);
  96
  97         edge->src = NULL;
  98         edge->tgt = NULL;
  99
 100         reorder_node_after_edge_deletion(src_node);
 101         reorder_node_after_edge_deletion(tgt_node);
 102 }
 103
 104 unsigned is_deleted(pbqp_edge_t *edge)
 105 {
 106         unsigned deleted;
 107
 108         assert(edge);
 109
 110         deleted = (edge->src == NULL) && (edge-> tgt == NULL);
 111
 112         return deleted;
 113 }
 114
 115 pbqp_edge_t *pbqp_edge_deep_copy(pbqp_t *pbqp, pbqp_edge_t *edge,
 116                                  pbqp_node_t *src_node, pbqp_node_t *tgt_node)
 117 {
 118         pbqp_edge_t *copy = OALLOC(&pbqp->obstack, pbqp_edge_t);
 119         assert(src_node);
 120         assert(tgt_node);
 121
 122         copy->costs = pbqp_matrix_copy(pbqp, edge->costs);
 123
 124         /* Connect edge with incident nodes. */
 125         copy->src = src_node;
 126         copy->tgt = tgt_node;
 127         copy->bucket_index = UINT_MAX;
 128
 129         return copy;
 130 }