2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Buckets for nodes and edges.
24 * @author Sebastian Buchwald
29 #include "adt/array.h"
32 #include "pbqp_edge_t.h"
33 #include "pbqp_node.h"
34 #include "pbqp_node_t.h"
36 int edge_bucket_contains(pbqp_edge_bucket_t bucket, pbqp_edge_t *edge)
38 return edge->bucket_index < edge_bucket_get_length(bucket)
39 && bucket[edge->bucket_index] == edge;
42 void edge_bucket_free(pbqp_edge_bucket_t *bucket)
48 unsigned edge_bucket_get_length(pbqp_edge_bucket_t bucket)
50 return ARR_LEN(bucket);
53 void edge_bucket_init(pbqp_edge_bucket_t *bucket)
55 *bucket = NEW_ARR_F(pbqp_edge_t *, 0);
58 void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge)
60 edge->bucket_index = edge_bucket_get_length(*bucket);
61 ARR_APP1(pbqp_edge_t *, *bucket, edge);
64 pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket)
66 unsigned bucket_len = edge_bucket_get_length(*bucket);
69 assert(bucket_len > 0);
71 edge = (*bucket)[bucket_len - 1];
73 ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
74 edge->bucket_index = UINT_MAX;
79 void node_bucket_shrink(pbqp_node_bucket_t *bucket, unsigned len)
81 ARR_SHRINKLEN(*bucket, (int)len);
84 int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node)
86 return node->bucket_index < node_bucket_get_length(bucket)
87 && bucket[node->bucket_index] == node;
90 void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src)
93 unsigned src_length = node_bucket_get_length(src);
95 for (src_index = 0; src_index < src_length; ++src_index) {
96 node_bucket_insert(dst, src[src_index]);
100 void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket)
103 unsigned length = node_bucket_get_length(bucket);
105 for (index = 0; index < length; ++index) {
106 pbqp->nodes[bucket[index]->index] = bucket[index];
110 void node_bucket_free(pbqp_node_bucket_t *bucket)
116 unsigned node_bucket_get_length(pbqp_node_bucket_t bucket)
118 return ARR_LEN(bucket);
121 void node_bucket_init(pbqp_node_bucket_t *bucket)
123 *bucket = NEW_ARR_F(pbqp_node_t*, 0);
126 void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
128 node->bucket_index = node_bucket_get_length(*bucket);
129 ARR_APP1(pbqp_node_t *, *bucket, node);
132 pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket)
134 unsigned bucket_len = node_bucket_get_length(*bucket);
137 assert(bucket_len > 0);
139 node = (*bucket)[bucket_len - 1];
141 ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
142 node->bucket_index = UINT_MAX;
147 void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
149 unsigned bucket_len = node_bucket_get_length(*bucket);
153 assert(node_bucket_contains(*bucket, node));
155 node_index = node->bucket_index;
156 other = (*bucket)[bucket_len - 1];
157 other->bucket_index = node_index;
158 (*bucket)[node_index] = other;
160 ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
161 node->bucket_index = UINT_MAX;
164 void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst,
165 pbqp_node_bucket_t src)
167 unsigned bucket_index;
168 unsigned bucket_length;
170 bucket_length = node_bucket_get_length(src);
172 for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
173 node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));