2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
10 * @author Sebastian Buchwald
14 #include "adt/array.h"
19 #include "pbqp_edge.h"
20 #include "pbqp_edge_t.h"
21 #include "pbqp_node.h"
22 #include "pbqp_node_t.h"
25 pbqp_node_t *alloc_node(pbqp_t *pbqp, unsigned node_index, vector_t *costs)
27 pbqp_node_t *node = OALLOC(&pbqp->obstack, pbqp_node_t);
29 node->edges = NEW_ARR_F(pbqp_edge_t *, 0);
30 node->costs = vector_copy(pbqp, costs);
31 node->bucket_index = UINT_MAX;
32 node->solution = UINT_MAX;
33 node->index = node_index;
38 int is_connected(pbqp_node_t *node, pbqp_edge_t *edge)
45 if (edge->src != node && edge->tgt != node) return 0;
48 edge_len = ARR_LEN(edges);
50 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
51 pbqp_edge_t *edge_candidate = edges[edge_index];
52 if (edge_candidate == edge) {
60 void disconnect_edge(pbqp_node_t *node, pbqp_edge_t *edge)
67 edge_len = ARR_LEN(edges);
69 for (edge_index = 0; edge_index < edge_len; ++edge_index) {
70 pbqp_edge_t *edge_candidate = edges[edge_index];
71 if (edge_candidate == edge) {
72 edges[edge_index] = edges[edge_len - 1];
73 ARR_SHRINKLEN(edges, (int)edge_len - 1);
79 unsigned pbqp_node_get_degree(pbqp_node_t *node)
81 return ARR_LEN(node->edges);
84 pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket,
88 unsigned edge_length = pbqp_node_get_degree(node);
89 pbqp_node_t *copy = OALLOC(&pbqp->obstack, pbqp_node_t);
91 copy->edges = NEW_ARR_F(pbqp_edge_t *, 0);
92 for (edge_index = 0; edge_index < edge_length; ++edge_index) {
93 pbqp_edge_t *edge_copy = NULL;
94 pbqp_edge_t *edge = node->edges[edge_index];
95 int is_src = edge->src == node;
98 unsigned other_index = edge->tgt->bucket_index;
99 unsigned is_copied = other_index < node->bucket_index;
102 pbqp_node_t *other_copy = new_bucket[other_index];
103 unsigned degree = pbqp_node_get_degree(other_copy);
106 for (index = 0; index < degree; ++index) {
107 if (other_copy->edges[index]->src == node) {
108 edge_copy = other_copy->edges[index];
109 edge_copy->src = copy;
114 edge_copy = pbqp_edge_deep_copy(pbqp, edge, copy, edge->tgt);
117 unsigned other_index = edge->src->bucket_index;
118 unsigned is_copied = other_index < node->bucket_index;
121 pbqp_node_t *other_copy = new_bucket[other_index];
122 unsigned degree = pbqp_node_get_degree(other_copy);
125 for (index = 0; index < degree; ++index) {
126 if (other_copy->edges[index]->tgt == node) {
127 edge_copy = other_copy->edges[index];
128 edge_copy->tgt = copy;
133 edge_copy = pbqp_edge_deep_copy(pbqp, edge, edge->src, copy);
136 ARR_APP1(pbqp_edge_t *, copy->edges, edge_copy);
138 copy->costs = vector_copy(pbqp, node->costs);
139 copy->bucket_index = node->bucket_index;
140 copy->solution = node->solution;
141 copy->index = node->index;