nsz Git - libfirm/blob - ir/kaps/pbqp_edge.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   PBQP edges.
   9  * @date    02.10.2008
  10  * @author  Sebastian Buchwald
  11  */
  12 #include "config.h"
  13
  14 #include "adt/array.h"
  15 #include "assert.h"
  16
  17 #include "kaps.h"
  18 #include "matrix.h"
  19 #include "optimal.h"
  20 #include "pbqp_edge.h"
  21 #include "pbqp_edge_t.h"
  22 #include "pbqp_node.h"
  23 #include "pbqp_node_t.h"
  24 #include "pbqp_t.h"
  25
  26 pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index,
  27                         pbqp_matrix_t *costs)
  28 {
  29         int transpose = 0;
  30         pbqp_edge_t *edge = OALLOC(&pbqp->obstack, pbqp_edge_t);
  31         pbqp_node_t *src_node;
  32         pbqp_node_t *tgt_node;
  33
  34         if (tgt_index < src_index) {
  35                 int tmp = src_index;
  36                 src_index = tgt_index;
  37                 tgt_index = tmp;
  38
  39                 transpose = 1;
  40         }
  41
  42         src_node = get_node(pbqp, src_index);
  43
  44         tgt_node = get_node(pbqp, tgt_index);
  45
  46         if (transpose) {
  47                 edge->costs = pbqp_matrix_copy_and_transpose(pbqp, costs);
  48         } else {
  49                 edge->costs = pbqp_matrix_copy(pbqp, costs);
  50         }
  51
  52         /*
  53          * Connect edge with incident nodes. Since the edge is allocated, we know
  54          * that it don't appear in the edge lists of the nodes.
  55          */
  56         ARR_APP1(pbqp_edge_t *, src_node->edges, edge);
  57         edge->src = src_node;
  58         ARR_APP1(pbqp_edge_t *, tgt_node->edges, edge);
  59         edge->tgt = tgt_node;
  60         edge->bucket_index = UINT_MAX;
  61
  62         return edge;
  63 }
  64
  65 void delete_edge(pbqp_edge_t *edge)
  66 {
  67         pbqp_node_t  *src_node;
  68         pbqp_node_t  *tgt_node;
  69
  70         src_node = edge->src;
  71         tgt_node = edge->tgt;
  72
  73         disconnect_edge(src_node, edge);
  74         disconnect_edge(tgt_node, edge);
  75
  76         edge->src = NULL;
  77         edge->tgt = NULL;
  78
  79         reorder_node_after_edge_deletion(src_node);
  80         reorder_node_after_edge_deletion(tgt_node);
  81 }
  82
  83 unsigned is_deleted(pbqp_edge_t *edge)
  84 {
  85         unsigned deleted;
  86
  87         deleted = (edge->src == NULL) && (edge-> tgt == NULL);
  88
  89         return deleted;
  90 }
  91
  92 pbqp_edge_t *pbqp_edge_deep_copy(pbqp_t *pbqp, pbqp_edge_t *edge,
  93                                  pbqp_node_t *src_node, pbqp_node_t *tgt_node)
  94 {
  95         pbqp_edge_t *copy = OALLOC(&pbqp->obstack, pbqp_edge_t);
  96         assert(src_node);
  97         assert(tgt_node);
  98
  99         copy->costs = pbqp_matrix_copy(pbqp, edge->costs);
 100
 101         /* Connect edge with incident nodes. */
 102         copy->src = src_node;
 103         copy->tgt = tgt_node;
 104         copy->bucket_index = UINT_MAX;
 105
 106         return copy;
 107 }