2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Buckets for nodes and edges.
10 * @author Sebastian Buchwald
14 #include "adt/array.h"
17 #include "pbqp_edge_t.h"
18 #include "pbqp_node.h"
19 #include "pbqp_node_t.h"
21 int edge_bucket_contains(pbqp_edge_bucket_t bucket, pbqp_edge_t *edge)
23 return edge->bucket_index < edge_bucket_get_length(bucket)
24 && bucket[edge->bucket_index] == edge;
27 void edge_bucket_free(pbqp_edge_bucket_t *bucket)
33 unsigned edge_bucket_get_length(pbqp_edge_bucket_t bucket)
35 return ARR_LEN(bucket);
38 void edge_bucket_init(pbqp_edge_bucket_t *bucket)
40 *bucket = NEW_ARR_F(pbqp_edge_t *, 0);
43 void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge)
45 edge->bucket_index = edge_bucket_get_length(*bucket);
46 ARR_APP1(pbqp_edge_t *, *bucket, edge);
49 pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket)
51 unsigned bucket_len = edge_bucket_get_length(*bucket);
54 assert(bucket_len > 0);
56 edge = (*bucket)[bucket_len - 1];
58 ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
59 edge->bucket_index = UINT_MAX;
64 void node_bucket_shrink(pbqp_node_bucket_t *bucket, unsigned len)
66 ARR_SHRINKLEN(*bucket, (int)len);
69 int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node)
71 return node->bucket_index < node_bucket_get_length(bucket)
72 && bucket[node->bucket_index] == node;
75 void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src)
78 unsigned src_length = node_bucket_get_length(src);
80 for (src_index = 0; src_index < src_length; ++src_index) {
81 node_bucket_insert(dst, src[src_index]);
85 void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket)
88 unsigned length = node_bucket_get_length(bucket);
90 for (index = 0; index < length; ++index) {
91 pbqp->nodes[bucket[index]->index] = bucket[index];
95 void node_bucket_free(pbqp_node_bucket_t *bucket)
101 unsigned node_bucket_get_length(pbqp_node_bucket_t bucket)
103 return ARR_LEN(bucket);
106 void node_bucket_init(pbqp_node_bucket_t *bucket)
108 *bucket = NEW_ARR_F(pbqp_node_t*, 0);
111 void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
113 node->bucket_index = node_bucket_get_length(*bucket);
114 ARR_APP1(pbqp_node_t *, *bucket, node);
117 pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket)
119 unsigned bucket_len = node_bucket_get_length(*bucket);
122 assert(bucket_len > 0);
124 node = (*bucket)[bucket_len - 1];
126 ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
127 node->bucket_index = UINT_MAX;
132 void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node)
134 unsigned bucket_len = node_bucket_get_length(*bucket);
138 assert(node_bucket_contains(*bucket, node));
140 node_index = node->bucket_index;
141 other = (*bucket)[bucket_len - 1];
142 other->bucket_index = node_index;
143 (*bucket)[node_index] = other;
145 ARR_SHRINKLEN(*bucket, (int)bucket_len - 1);
146 node->bucket_index = UINT_MAX;
149 void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst,
150 pbqp_node_bucket_t src)
152 unsigned bucket_index;
153 unsigned bucket_length;
155 bucket_length = node_bucket_get_length(src);
157 for (bucket_index = 0; bucket_index < bucket_length; ++bucket_index) {
158 node_bucket_insert(dst, pbqp_node_deep_copy(pbqp, *dst, src[bucket_index]));