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