Use more bucket functions.

[libfirm] / heuristical.c

diff --git a/heuristical.c b/heuristical.c
index cbc61e0..2f3e38d 100644 (file)
--- a/heuristical.c
+++ b/heuristical.c
@@ -2,6 +2,7 @@
 #include "assert.h"
 #include "error.h"
 
+#include "bucket.h"
 #include "heuristical.h"
 #include "html_dumper.h"
 #include "kaps.h"
@@ -19,26 +20,23 @@ static int         buckets_filled = 0;
 
 static void insert_into_edge_bucket(pbqp_edge *edge)
 {
-       unsigned bucket_len = ARR_LEN(edge_bucket);
-
-       if (edge->bucket_index < bucket_len && edge_bucket[edge->bucket_index]
-                       == edge)
+       if (edge_bucket_contains(edge_bucket, edge)) {
                /* Edge is already inserted. */
                return;
+       }
 
-       edge->bucket_index = bucket_len;
-       ARR_APP1(pbqp_edge *, edge_bucket, edge);
+       edge_bucket_insert(&edge_bucket, edge);
 }
 
 static void init_buckets(void)
 {
        int i;
 
-       edge_bucket = NEW_ARR_F(pbqp_edge *, 0);
-       reduced_bucket = NEW_ARR_F(pbqp_node *, 0);
+       edge_bucket_init(&edge_bucket);
+       node_bucket_init(&reduced_bucket);
 
        for (i = 0; i < 4; ++i) {
-               node_buckets[i] = NEW_ARR_F(pbqp_node *, 0);
+               node_bucket_init(&node_buckets[i]);
        }
 }
 
@@ -47,15 +45,11 @@ static void free_buckets(void)
        int i;
 
        for (i = 0; i < 4; ++i) {
-               DEL_ARR_F(node_buckets[i]);
-               node_buckets[i] = NULL;
+               node_bucket_free(&node_buckets[i]);
        }
 
-       DEL_ARR_F(edge_bucket);
-       edge_bucket = NULL;
-
-       DEL_ARR_F(reduced_bucket);
-       reduced_bucket = NULL;
+       edge_bucket_free(&edge_bucket);
+       node_bucket_free(&reduced_bucket);
 
        buckets_filled = 0;
 }
@@ -81,9 +75,7 @@ static void fill_node_buckets(pbqp *pbqp)
                        arity = 3;
                }
 
-               node->bucket_index = ARR_LEN(node_buckets[arity]);
-
-               ARR_APP1(pbqp_node *, node_buckets[arity], node);
+               node_bucket_insert(&node_buckets[arity], node);
        }
 
        buckets_filled = 1;
@@ -229,12 +221,12 @@ static void reorder_node(pbqp_node *node)
        /* Assume node lost one incident edge. */
        old_arity        = arity + 1;
        old_bucket       = node_buckets[old_arity];
-       old_bucket_len   = ARR_LEN(old_bucket);
+       old_bucket_len   = node_bucket_get_length(old_bucket);
        old_bucket_index = node->bucket_index;
 
        if (old_bucket_len <= old_bucket_index || old_bucket[old_bucket_index]
                        != node) {
-               unsigned bucket_len = ARR_LEN(node_buckets[arity]);
+               unsigned bucket_len = node_bucket_get_length(node_buckets[arity]);
 
                /* Old arity is new arity, so we have nothing to do. */
                assert(old_bucket_index < bucket_len);
@@ -251,7 +243,7 @@ static void reorder_node(pbqp_node *node)
        ARR_SHRINKLEN(node_buckets[old_arity], old_bucket_len - 1);
 
        /* ..and add to new one. */
-       node->bucket_index = ARR_LEN(node_buckets[arity]);
+       node->bucket_index = node_bucket_get_length(node_buckets[arity]);
        ARR_APP1(pbqp_node*, node_buckets[arity], node);
 }
 
@@ -362,13 +354,13 @@ void solve_pbqp_heuristical(pbqp *pbqp)
        fill_node_buckets(pbqp);
 
        for (;;) {
-               if (ARR_LEN(edge_bucket) > 0) {
+               if (edge_bucket_get_length(edge_bucket) > 0) {
                        apply_edge(pbqp);
-               } else if (ARR_LEN(node_buckets[1]) > 0) {
+               } else if (node_bucket_get_length(node_buckets[1]) > 0) {
                        apply_RI(pbqp);
-               } else if (ARR_LEN(node_buckets[2]) > 0) {
+               } else if (node_bucket_get_length(node_buckets[2]) > 0) {
                        apply_RII(pbqp);
-               } else if (ARR_LEN(node_buckets[3]) > 0) {
+               } else if (node_bucket_get_length(node_buckets[3]) > 0) {
                        apply_RN(pbqp);
                } else {
                        break;
@@ -381,7 +373,7 @@ void solve_pbqp_heuristical(pbqp *pbqp)
        }
 
        /* Solve trivial nodes and calculate solution. */
-       node_len = ARR_LEN(node_buckets[0]);
+       node_len = node_bucket_get_length(node_buckets[0]);
        for (node_index = 0; node_index < node_len; ++node_index) {
                pbqp_node *node = node_buckets[0][node_index];
                assert(node);
@@ -402,7 +394,7 @@ void solve_pbqp_heuristical(pbqp *pbqp)
        }
 
        /* Solve reduced nodes. */
-       node_len = ARR_LEN(reduced_bucket);
+       node_len = node_bucket_get_length(reduced_bucket);
        for (node_index = node_len; node_index > 0; --node_index) {
                pbqp_node *node = reduced_bucket[node_index - 1];
                assert(node);
@@ -425,19 +417,14 @@ void solve_pbqp_heuristical(pbqp *pbqp)
 
 void apply_edge(pbqp *pbqp)
 {
-       unsigned   bucket_len = ARR_LEN(edge_bucket);
-       pbqp_edge *edge       = edge_bucket[bucket_len - 1];
-
-       ARR_SHRINKLEN(edge_bucket, (int)bucket_len - 1);
+       pbqp_edge *edge = edge_bucket_pop(&edge_bucket);
 
        simplify_edge(pbqp, edge);
 }
 
 void apply_RI(pbqp *pbqp)
 {
-       pbqp_node  **bucket     = node_buckets[1];
-       unsigned     bucket_len = ARR_LEN(bucket);
-       pbqp_node   *node       = bucket[bucket_len - 1];
+       pbqp_node   *node       = node_bucket_pop(&node_buckets[1]);
        pbqp_edge   *edge       = node->edges[0];
        pbqp_matrix *mat        = edge->costs;
        int          is_src     = edge->src == node;
@@ -474,20 +461,15 @@ void apply_RI(pbqp *pbqp)
                dump_node(pbqp, other_node);
        }
 
-       /* Remove node from bucket... */
-       ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
        reorder_node(other_node);
 
-       /* ...and add it to back propagation list. */
-       node->bucket_index = ARR_LEN(reduced_bucket);
-       ARR_APP1(pbqp_node *, reduced_bucket, node);
+       /* Add node to back propagation list. */
+       node_bucket_insert(&reduced_bucket, node);
 }
 
 void apply_RII(pbqp *pbqp)
 {
-       pbqp_node  **bucket     = node_buckets[2];
-       unsigned     bucket_len = ARR_LEN(bucket);
-       pbqp_node   *node       = bucket[bucket_len - 1];
+       pbqp_node   *node       = node_bucket_pop(&node_buckets[2]);
        pbqp_edge   *src_edge   = node->edges[0];
        pbqp_edge   *tgt_edge   = node->edges[1];
        int          src_is_src = src_edge->src == node;
@@ -592,12 +574,8 @@ void apply_RII(pbqp *pbqp)
        disconnect_edge(src_node, src_edge);
        disconnect_edge(tgt_node, tgt_edge);
 
-       /* Remove node from bucket... */
-       ARR_SHRINKLEN(bucket, (int)bucket_len - 1);
-
-       /* ...and add it to back propagation list. */
-       node->bucket_index = ARR_LEN(reduced_bucket);
-       ARR_APP1(pbqp_node *, reduced_bucket, node);
+       /* Add node to back propagation list. */
+       node_bucket_insert(&reduced_bucket, node);
 
        if (edge == NULL) {
                edge = alloc_edge(pbqp, src_node->index, tgt_node->index, mat);
@@ -623,7 +601,7 @@ void apply_RII(pbqp *pbqp)
 void apply_RN(pbqp *pbqp)
 {
        pbqp_node  **bucket       = node_buckets[3];
-       unsigned     bucket_len   = ARR_LEN(bucket);
+       unsigned     bucket_len   = node_bucket_get_length(bucket);
        unsigned     bucket_index;
        pbqp_node   *node         = NULL;
        pbqp_edge   *edge;
@@ -825,8 +803,5 @@ int node_is_reduced(pbqp_node *node)
        assert(node);
        if (ARR_LEN(node->edges) == 0) return 1;
 
-       unsigned bucket_length = ARR_LEN(reduced_bucket);
-       unsigned bucket_index  = node->bucket_index;
-
-       return bucket_index < bucket_length && reduced_bucket[bucket_index] == node;
+       return node_bucket_contains(reduced_bucket, node);
 }