From 5b64d9c1f04f0c48c721022ff276c37a57e32992 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Thu, 4 Nov 2010 12:15:19 +0000 Subject: [PATCH] rename types to XXX_t for C++ compatibility (because pbqp *pbqp; is not legal in C++) [r28124] --- brute_force.c | 82 +++++------ brute_force.h | 2 +- bucket.c | 61 ++++---- bucket.h | 34 ++--- bucket_t.h | 4 +- heuristical.c | 10 +- heuristical.h | 2 +- heuristical_co.c | 14 +- heuristical_co.h | 2 +- heuristical_co_ld.c | 76 +++++----- heuristical_co_ld.h | 2 +- html_dumper.c | 32 ++--- html_dumper.h | 10 +- kaps.c | 37 +++-- kaps.h | 19 +-- matrix.c | 58 ++++---- matrix.h | 38 ++--- matrix_t.h | 4 +- optimal.c | 338 ++++++++++++++++++++++---------------------- optimal.h | 40 +++--- pbqp_edge.c | 28 ++-- pbqp_edge.h | 11 +- pbqp_edge_t.h | 10 +- pbqp_node.c | 59 ++++---- pbqp_node.h | 12 +- pbqp_node_t.h | 12 +- pbqp_t.h | 10 +- vector.c | 24 ++-- vector.h | 20 +-- vector_t.h | 12 +- 30 files changed, 533 insertions(+), 530 deletions(-) diff --git a/brute_force.c b/brute_force.c index a1631260b..94111ce08 100644 --- a/brute_force.c +++ b/brute_force.c @@ -48,9 +48,9 @@ static int dump = 0; #endif /* Forward declarations. */ -static void apply_Brute_Force(pbqp *pbqp); +static void apply_Brute_Force(pbqp_t *pbqp); -static void apply_brute_force_reductions(pbqp *pbqp) +static void apply_brute_force_reductions(pbqp_t *pbqp) { for (;;) { if (edge_bucket_get_length(edge_bucket) > 0) { @@ -67,14 +67,14 @@ static void apply_brute_force_reductions(pbqp *pbqp) } } -static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node) +static unsigned get_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node) { - vector *node_vec; - unsigned node_index; - unsigned node_len; - unsigned min_index = 0; - num min = INF_COSTS; - unsigned bucket_index; + vector_t *node_vec; + unsigned node_index; + unsigned node_len; + unsigned min_index = 0; + num min = INF_COSTS; + unsigned bucket_index; assert(pbqp); assert(node); @@ -83,12 +83,12 @@ static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node) bucket_index = node->bucket_index; for (node_index = 0; node_index < node_len; ++node_index) { - pbqp_node_bucket bucket_deg3; - num value; - unsigned bucket_0_length; - unsigned bucket_red_length; + pbqp_node_bucket_t bucket_deg3; + num value; + unsigned bucket_0_length; + unsigned bucket_red_length; - char *tmp = obstack_finish(&pbqp->obstack); + char *tmp = (char*)obstack_finish(&pbqp->obstack); node_bucket_init(&bucket_deg3); @@ -142,9 +142,9 @@ static unsigned get_minimal_alternative(pbqp *pbqp, pbqp_node *node) return min_index; } -static void apply_Brute_Force(pbqp *pbqp) +static void apply_Brute_Force(pbqp_t *pbqp) { - pbqp_node *node = NULL; + pbqp_node_t *node = NULL; unsigned min_index = 0; assert(pbqp); @@ -193,13 +193,13 @@ static void apply_Brute_Force(pbqp *pbqp) -static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *edge; - pbqp_node *other; - pbqp_matrix *mat; - vector *vec; - int is_src; + pbqp_edge_t *edge; + pbqp_node_t *other; + pbqp_matrix_t *mat; + vector_t *vec; + int is_src; assert(pbqp); assert(node); @@ -234,20 +234,20 @@ static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) #endif } -static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *src_edge = node->edges[0]; - pbqp_edge *tgt_edge = node->edges[1]; - int src_is_src = src_edge->src == node; - int tgt_is_src = tgt_edge->src == node; - pbqp_matrix *src_mat; - pbqp_matrix *tgt_mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *vec; - vector *node_vec; - unsigned col_index; - unsigned row_index; + pbqp_edge_t *src_edge = node->edges[0]; + pbqp_edge_t *tgt_edge = node->edges[1]; + int src_is_src = src_edge->src == node; + int tgt_is_src = tgt_edge->src == node; + pbqp_matrix_t *src_mat; + pbqp_matrix_t *tgt_mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *vec; + vector_t *node_vec; + unsigned col_index; + unsigned row_index; assert(pbqp); @@ -265,8 +265,8 @@ static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) /* Swap nodes if necessary. */ if (tgt_node->index < src_node->index) { - pbqp_node *tmp_node; - pbqp_edge *tmp_edge; + pbqp_node_t *tmp_node; + pbqp_edge_t *tmp_edge; tmp_node = src_node; src_node = tgt_node; @@ -317,10 +317,10 @@ static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) obstack_free(&pbqp->obstack, vec); } -static void back_propagate_brute_force(pbqp *pbqp) +static void back_propagate_brute_force(pbqp_t *pbqp) { unsigned node_index; - unsigned node_len = node_bucket_get_length(reduced_bucket); + unsigned node_len = node_bucket_get_length(reduced_bucket); assert(pbqp); @@ -331,7 +331,7 @@ static void back_propagate_brute_force(pbqp *pbqp) #endif for (node_index = node_len; node_index > 0; --node_index) { - pbqp_node *node = reduced_bucket[node_index - 1]; + pbqp_node_t *node = reduced_bucket[node_index - 1]; switch (pbqp_node_get_degree(node)) { case 1: @@ -347,7 +347,7 @@ static void back_propagate_brute_force(pbqp *pbqp) } } -void solve_pbqp_brute_force(pbqp *pbqp) +void solve_pbqp_brute_force(pbqp_t *pbqp) { /* Reduce nodes degree ... */ initial_simplify_edges(pbqp); diff --git a/brute_force.h b/brute_force.h index c0e7eff75..696dccc7a 100644 --- a/brute_force.h +++ b/brute_force.h @@ -29,6 +29,6 @@ #include "pbqp_t.h" -void solve_pbqp_brute_force(pbqp *pbqp); +void solve_pbqp_brute_force(pbqp_t *pbqp); #endif /* KAPS_BRUTE_FORCE_H */ diff --git a/bucket.c b/bucket.c index fdbe753d4..77e859906 100644 --- a/bucket.c +++ b/bucket.c @@ -33,7 +33,7 @@ #include "pbqp_node.h" #include "pbqp_node_t.h" -int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge) +int edge_bucket_contains(pbqp_edge_bucket_t bucket, pbqp_edge_t *edge) { assert(edge); @@ -41,32 +41,32 @@ int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge) && bucket[edge->bucket_index] == edge; } -void edge_bucket_free(pbqp_edge_bucket *bucket) +void edge_bucket_free(pbqp_edge_bucket_t *bucket) { DEL_ARR_F(*bucket); *bucket = NULL; } -unsigned edge_bucket_get_length(pbqp_edge_bucket bucket) +unsigned edge_bucket_get_length(pbqp_edge_bucket_t bucket) { return ARR_LEN(bucket); } -void edge_bucket_init(pbqp_edge_bucket *bucket) +void edge_bucket_init(pbqp_edge_bucket_t *bucket) { - *bucket = NEW_ARR_F(pbqp_edge *, 0); + *bucket = NEW_ARR_F(pbqp_edge_t *, 0); } -void edge_bucket_insert(pbqp_edge_bucket *bucket, pbqp_edge *edge) +void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge) { edge->bucket_index = edge_bucket_get_length(*bucket); - ARR_APP1(pbqp_edge *, *bucket, edge); + ARR_APP1(pbqp_edge_t *, *bucket, edge); } -pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket) +pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket) { - unsigned bucket_len = edge_bucket_get_length(*bucket); - pbqp_edge *edge; + unsigned bucket_len = edge_bucket_get_length(*bucket); + pbqp_edge_t *edge; assert(bucket_len > 0); @@ -78,12 +78,12 @@ pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket) return edge; } -void node_bucket_shrink(pbqp_node_bucket *bucket, unsigned len) +void node_bucket_shrink(pbqp_node_bucket_t *bucket, unsigned len) { ARR_SHRINKLEN(*bucket, (int)len); } -int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node) +int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node) { assert(node); @@ -91,7 +91,7 @@ int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node) && bucket[node->bucket_index] == node; } -void node_bucket_copy(pbqp_node_bucket *dst, pbqp_node_bucket src) +void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src) { unsigned src_index; unsigned src_length = node_bucket_get_length(src); @@ -101,7 +101,7 @@ void node_bucket_copy(pbqp_node_bucket *dst, pbqp_node_bucket src) } } -void node_bucket_update(pbqp *pbqp, pbqp_node_bucket bucket) +void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket) { unsigned index; unsigned length = node_bucket_get_length(bucket); @@ -111,32 +111,32 @@ void node_bucket_update(pbqp *pbqp, pbqp_node_bucket bucket) } } -void node_bucket_free(pbqp_node_bucket *bucket) +void node_bucket_free(pbqp_node_bucket_t *bucket) { DEL_ARR_F(*bucket); *bucket = NULL; } -unsigned node_bucket_get_length(pbqp_node_bucket bucket) +unsigned node_bucket_get_length(pbqp_node_bucket_t bucket) { return ARR_LEN(bucket); } -void node_bucket_init(pbqp_node_bucket *bucket) +void node_bucket_init(pbqp_node_bucket_t *bucket) { - *bucket = NEW_ARR_F(pbqp_node *, 0); + *bucket = NEW_ARR_F(pbqp_node_t*, 0); } -void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node) +void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node) { node->bucket_index = node_bucket_get_length(*bucket); - ARR_APP1(pbqp_node *, *bucket, node); + ARR_APP1(pbqp_node_t *, *bucket, node); } -pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket) +pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket) { - unsigned bucket_len = node_bucket_get_length(*bucket); - pbqp_node *node; + unsigned bucket_len = node_bucket_get_length(*bucket); + pbqp_node_t *node; assert(bucket_len > 0); @@ -149,11 +149,11 @@ pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket) return node; } -void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node) +void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node) { - unsigned bucket_len = node_bucket_get_length(*bucket); - unsigned node_index; - pbqp_node *other; + unsigned bucket_len = node_bucket_get_length(*bucket); + unsigned node_index; + pbqp_node_t *other; assert(node); assert(node_bucket_contains(*bucket, node)); @@ -168,10 +168,11 @@ void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node) node->bucket_index = UINT_MAX; } -void node_bucket_deep_copy(pbqp *pbqp, pbqp_node_bucket *dst, pbqp_node_bucket src) +void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst, + pbqp_node_bucket_t src) { - unsigned bucket_index; - unsigned bucket_length; + unsigned bucket_index; + unsigned bucket_length; bucket_length = node_bucket_get_length(src); diff --git a/bucket.h b/bucket.h index 50a2820c3..fd0d92e7e 100644 --- a/bucket.h +++ b/bucket.h @@ -29,23 +29,23 @@ #include "bucket_t.h" -int edge_bucket_contains(pbqp_edge_bucket bucket, pbqp_edge *edge); -void edge_bucket_free(pbqp_edge_bucket *bucket); -unsigned edge_bucket_get_length(pbqp_edge_bucket bucket); -void edge_bucket_init(pbqp_edge_bucket *bucket); -void edge_bucket_insert(pbqp_edge_bucket *bucket, pbqp_edge *edge); -pbqp_edge *edge_bucket_pop(pbqp_edge_bucket *bucket); +int edge_bucket_contains(pbqp_edge_bucket_t bucket, pbqp_edge_t *edge); +void edge_bucket_free(pbqp_edge_bucket_t *bucket); +unsigned edge_bucket_get_length(pbqp_edge_bucket_t bucket); +void edge_bucket_init(pbqp_edge_bucket_t *bucket); +void edge_bucket_insert(pbqp_edge_bucket_t *bucket, pbqp_edge_t *edge); +pbqp_edge_t *edge_bucket_pop(pbqp_edge_bucket_t *bucket); -int node_bucket_contains(pbqp_node_bucket bucket, pbqp_node *node); -void node_bucket_copy(pbqp_node_bucket *dst, pbqp_node_bucket src); -void node_bucket_deep_copy(pbqp *pbqp, pbqp_node_bucket *dst, pbqp_node_bucket src); -void node_bucket_free(pbqp_node_bucket *bucket); -unsigned node_bucket_get_length(pbqp_node_bucket bucket); -void node_bucket_init(pbqp_node_bucket *bucket); -void node_bucket_insert(pbqp_node_bucket *bucket, pbqp_node *node); -pbqp_node *node_bucket_pop(pbqp_node_bucket *bucket); -void node_bucket_remove(pbqp_node_bucket *bucket, pbqp_node *node); -void node_bucket_shrink(pbqp_node_bucket *bucket, unsigned len); -void node_bucket_update(pbqp *pbqp, pbqp_node_bucket bucket); +int node_bucket_contains(pbqp_node_bucket_t bucket, pbqp_node_t *node); +void node_bucket_copy(pbqp_node_bucket_t *dst, pbqp_node_bucket_t src); +void node_bucket_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t *dst, pbqp_node_bucket_t src); +void node_bucket_free(pbqp_node_bucket_t *bucket); +unsigned node_bucket_get_length(pbqp_node_bucket_t bucket); +void node_bucket_init(pbqp_node_bucket_t *bucket); +void node_bucket_insert(pbqp_node_bucket_t *bucket, pbqp_node_t *node); +pbqp_node_t *node_bucket_pop(pbqp_node_bucket_t *bucket); +void node_bucket_remove(pbqp_node_bucket_t *bucket, pbqp_node_t *node); +void node_bucket_shrink(pbqp_node_bucket_t *bucket, unsigned len); +void node_bucket_update(pbqp_t *pbqp, pbqp_node_bucket_t bucket); #endif /* KAPS_BUCKET_H */ diff --git a/bucket_t.h b/bucket_t.h index f38d6da0d..df9cce5d2 100644 --- a/bucket_t.h +++ b/bucket_t.h @@ -29,7 +29,7 @@ #include "pbqp_t.h" -typedef pbqp_node** pbqp_node_bucket; -typedef pbqp_edge** pbqp_edge_bucket; +typedef pbqp_node_t** pbqp_node_bucket_t; +typedef pbqp_edge_t** pbqp_edge_bucket_t; #endif /* KAPS_BUCKET_T_H */ diff --git a/heuristical.c b/heuristical.c index ee810e375..c078f5d1e 100644 --- a/heuristical.c +++ b/heuristical.c @@ -46,10 +46,10 @@ #include "timing.h" -static void apply_RN(pbqp *pbqp) +static void apply_RN(pbqp_t *pbqp) { - pbqp_node *node = NULL; - unsigned min_index = 0; + pbqp_node_t *node = NULL; + unsigned min_index = 0; assert(pbqp); @@ -87,7 +87,7 @@ static void apply_RN(pbqp *pbqp) select_alternative(node, min_index); } -static void apply_heuristic_reductions(pbqp *pbqp) +static void apply_heuristic_reductions(pbqp_t *pbqp) { for (;;) { if (edge_bucket_get_length(edge_bucket) > 0) { @@ -104,7 +104,7 @@ static void apply_heuristic_reductions(pbqp *pbqp) } } -void solve_pbqp_heuristical(pbqp *pbqp) +void solve_pbqp_heuristical(pbqp_t *pbqp) { /* Reduce nodes degree ... */ initial_simplify_edges(pbqp); diff --git a/heuristical.h b/heuristical.h index 2e0164907..688b2bf53 100644 --- a/heuristical.h +++ b/heuristical.h @@ -29,6 +29,6 @@ #include "pbqp_t.h" -void solve_pbqp_heuristical(pbqp *pbqp); +void solve_pbqp_heuristical(pbqp_t *pbqp); #endif /* KAPS_HEURISTICAL_CO_H */ diff --git a/heuristical_co.c b/heuristical_co.c index b33e9d746..aa3072906 100644 --- a/heuristical_co.c +++ b/heuristical_co.c @@ -47,16 +47,16 @@ #include "plist.h" #include "timing.h" -static void merge_into_RN_node(pbqp *pbqp, plist_t *rpeo) +static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo) { - pbqp_node *node = NULL; + pbqp_node_t *node = NULL; assert(pbqp); /* We want to reduce the first node in reverse perfect elimination order. */ do { /* get first element from reverse perfect elimination order */ - node = plist_first(rpeo)->data; + node = (pbqp_node_t*)plist_first(rpeo)->data; /* remove element from reverse perfect elimination order */ plist_erase(rpeo, plist_first(rpeo)); /* insert node at the end of rpeo so the rpeo already exits after pbqp solving */ @@ -70,9 +70,9 @@ static void merge_into_RN_node(pbqp *pbqp, plist_t *rpeo) apply_RM(pbqp, node); } -static void apply_RN_co(pbqp *pbqp) +static void apply_RN_co(pbqp_t *pbqp) { - pbqp_node *node; + pbqp_node_t *node; unsigned min_index; assert(pbqp); @@ -113,7 +113,7 @@ static void apply_RN_co(pbqp *pbqp) select_alternative(node, min_index); } -static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo) +static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo) { #if KAPS_TIMING /* create timers */ @@ -187,7 +187,7 @@ static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo) } } -void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo) +void solve_pbqp_heuristical_co(pbqp_t *pbqp, plist_t *rpeo) { /* Reduce nodes degree ... */ initial_simplify_edges(pbqp); diff --git a/heuristical_co.h b/heuristical_co.h index 9e7dea930..2872edc4c 100644 --- a/heuristical_co.h +++ b/heuristical_co.h @@ -31,6 +31,6 @@ #include "plist.h" -void solve_pbqp_heuristical_co(pbqp *pbqp, plist_t *rpeo); +void solve_pbqp_heuristical_co(pbqp_t *pbqp, plist_t *rpeo); #endif /* KAPS_HEURISTICAL_H */ diff --git a/heuristical_co_ld.c b/heuristical_co_ld.c index 969afd81f..ba694f9c1 100644 --- a/heuristical_co_ld.c +++ b/heuristical_co_ld.c @@ -28,13 +28,13 @@ #include "plist.h" #include "timing.h" -static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *edge; - pbqp_node *other; - pbqp_matrix *mat; - vector *vec; - int is_src; + pbqp_edge_t *edge; + pbqp_node_t *other; + pbqp_matrix_t *mat; + vector_t *vec; + int is_src; assert(pbqp); assert(node); @@ -65,20 +65,20 @@ static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) #endif } -static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *src_edge = node->edges[0]; - pbqp_edge *tgt_edge = node->edges[1]; - int src_is_src = src_edge->src == node; - int tgt_is_src = tgt_edge->src == node; - pbqp_matrix *src_mat; - pbqp_matrix *tgt_mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *vec; - vector *node_vec; - unsigned col_index; - unsigned row_index; + pbqp_edge_t *src_edge = node->edges[0]; + pbqp_edge_t *tgt_edge = node->edges[1]; + int src_is_src = src_edge->src == node; + int tgt_is_src = tgt_edge->src == node; + pbqp_matrix_t *src_mat; + pbqp_matrix_t *tgt_mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *vec; + vector_t *node_vec; + unsigned col_index; + unsigned row_index; assert(pbqp); @@ -96,8 +96,8 @@ static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) /* Swap nodes if necessary. */ if (tgt_node->index < src_node->index) { - pbqp_node *tmp_node; - pbqp_edge *tmp_edge; + pbqp_node_t *tmp_node; + pbqp_edge_t *tmp_edge; tmp_node = src_node; src_node = tgt_node; @@ -144,12 +144,12 @@ static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) obstack_free(&pbqp->obstack, vec); } -static void back_propagate_RN(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RN(pbqp_t *pbqp, pbqp_node_t *node) { - vector *vec = NULL; - pbqp_node *neighbor = NULL; - pbqp_edge *edge = NULL; - unsigned edge_index = 0; + vector_t *vec = NULL; + pbqp_node_t *neighbor = NULL; + pbqp_edge_t *edge = NULL; + unsigned edge_index = 0; assert(pbqp); @@ -180,7 +180,7 @@ static void back_propagate_RN(pbqp *pbqp, pbqp_node *node) obstack_free(&pbqp->obstack, vec); } -static void back_propagate_ld(pbqp *pbqp) +static void back_propagate_ld(pbqp_t *pbqp) { unsigned node_index; unsigned node_len = node_bucket_get_length(reduced_bucket); @@ -194,7 +194,7 @@ static void back_propagate_ld(pbqp *pbqp) #endif for (node_index = node_len; node_index > 0; --node_index) { - pbqp_node *node = reduced_bucket[node_index - 1]; + pbqp_node_t *node = reduced_bucket[node_index - 1]; switch (pbqp_node_get_degree(node)) { case 1: @@ -210,15 +210,15 @@ static void back_propagate_ld(pbqp *pbqp) } } -static void merge_into_RN_node(pbqp *pbqp, plist_t *rpeo) +static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo) { - pbqp_node *node = NULL; + pbqp_node_t *node = NULL; assert(pbqp); do { /* get last element from reverse perfect elimination order */ - node = plist_last(rpeo)->data; + node = (pbqp_node_t*)plist_last(rpeo)->data; /* remove element from reverse perfect elimination order */ plist_erase(rpeo, plist_last(rpeo)); /* insert node at the beginning of rpeo so the rpeo already exits after pbqp solving */ @@ -232,10 +232,10 @@ static void merge_into_RN_node(pbqp *pbqp, plist_t *rpeo) apply_RM(pbqp, node); } -static void apply_RN_co_without_selection(pbqp *pbqp) +static void apply_RN_co_without_selection(pbqp_t *pbqp) { - pbqp_node *node; - unsigned edge_index; + pbqp_node_t *node; + unsigned edge_index; assert(pbqp); @@ -257,8 +257,8 @@ static void apply_RN_co_without_selection(pbqp *pbqp) /* Disconnect neighbor nodes */ for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) { - pbqp_edge *edge; - pbqp_node *neighbor; + pbqp_edge_t *edge; + pbqp_node_t *neighbor; /* get neighbor node */ edge = node->edges[edge_index]; @@ -283,7 +283,7 @@ static void apply_RN_co_without_selection(pbqp *pbqp) node_bucket_insert(&reduced_bucket, node); } -static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo) +static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo) { #if KAPS_TIMING /* create timers */ @@ -357,7 +357,7 @@ static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo) } } -void solve_pbqp_heuristical_co_ld(pbqp *pbqp, plist_t *rpeo) +void solve_pbqp_heuristical_co_ld(pbqp_t *pbqp, plist_t *rpeo) { /* Reduce nodes degree ... */ initial_simplify_edges(pbqp); diff --git a/heuristical_co_ld.h b/heuristical_co_ld.h index c593e3867..097fe3b68 100644 --- a/heuristical_co_ld.h +++ b/heuristical_co_ld.h @@ -11,6 +11,6 @@ #include "pbqp_t.h" #include "plist.h" -void solve_pbqp_heuristical_co_ld(pbqp *pbqp, plist_t *rpeo); +void solve_pbqp_heuristical_co_ld(pbqp_t *pbqp, plist_t *rpeo); #endif /* HEURISTICAL_CO_LD_H_ */ diff --git a/html_dumper.c b/html_dumper.c index d9d032149..93d0fd170 100644 --- a/html_dumper.c +++ b/html_dumper.c @@ -50,7 +50,7 @@ static const char *cost2a(num const cost) } /* print vector */ -static void dump_vector(FILE *f, vector *vec) +static void dump_vector(FILE *f, vector_t *vec) { unsigned index; assert(vec); @@ -69,7 +69,7 @@ static void dump_vector(FILE *f, vector *vec) fprintf(f, " )\n"); } -static void dump_matrix(FILE *f, pbqp_matrix *mat) +static void dump_matrix(FILE *f, pbqp_matrix_t *mat) { unsigned row, col; assert(mat); @@ -89,7 +89,7 @@ static void dump_matrix(FILE *f, pbqp_matrix *mat) fprintf(f, "\t\\end{pmatrix}\n"); } -void dump_edge(FILE *file, pbqp_edge *edge) +void dump_edge(FILE *file, pbqp_edge_t *edge) { fputs("\n", file); fprintf(file, "\t\\overline\n{C}_{%d,%d}=\n", @@ -98,7 +98,7 @@ void dump_edge(FILE *file, pbqp_edge *edge) fputs("
", file); } -static void dump_edge_costs(pbqp *pbqp) +static void dump_edge_costs(pbqp_t *pbqp) { unsigned src_index; @@ -107,7 +107,7 @@ static void dump_edge_costs(pbqp *pbqp) fputs("

", pbqp->dump_file); for (src_index = 0; src_index < pbqp->num_nodes; ++src_index) { - pbqp_node *src_node = get_node(pbqp, src_index); + pbqp_node_t *src_node = get_node(pbqp, src_index); if (!src_node) continue; @@ -115,8 +115,8 @@ static void dump_edge_costs(pbqp *pbqp) unsigned edge_index; unsigned len = ARR_LEN(src_node->edges); for (edge_index = 0; edge_index < len; ++edge_index) { - pbqp_edge *edge = src_node->edges[edge_index]; - unsigned tgt_index = edge->tgt->index; + pbqp_edge_t *edge = src_node->edges[edge_index]; + unsigned tgt_index = edge->tgt->index; if (src_index < tgt_index) { dump_edge(pbqp->dump_file, edge); } @@ -125,7 +125,7 @@ static void dump_edge_costs(pbqp *pbqp) fputs("

", pbqp->dump_file); } -void dump_node(FILE *file, pbqp_node *node) +void dump_node(FILE *file, pbqp_node_t *node) { assert(file); @@ -136,7 +136,7 @@ void dump_node(FILE *file, pbqp_node *node) } } -static void dump_node_costs(pbqp *pbqp) +static void dump_node_costs(pbqp_t *pbqp) { unsigned index; @@ -158,7 +158,7 @@ void dump_section(FILE *f, int level, const char *txt) fprintf(f, "%s\n", level, txt, level); } -void pbqp_dump_graph(pbqp *pbqp) +void pbqp_dump_graph(pbqp_t *pbqp) { unsigned src_index; @@ -167,14 +167,14 @@ void pbqp_dump_graph(pbqp *pbqp) fputs("

\n\n\tgraph input {\n", pbqp->dump_file); for (src_index = 0; src_index < pbqp->num_nodes; ++src_index) { - pbqp_node *node = get_node(pbqp, src_index); + pbqp_node_t *node = get_node(pbqp, src_index); if (node && !node_is_reduced(node)) { fprintf(pbqp->dump_file, "\t n%d;\n", src_index); } } for (src_index = 0; src_index < pbqp->num_nodes; ++src_index) { - pbqp_node *node = get_node(pbqp, src_index); + pbqp_node_t *node = get_node(pbqp, src_index); if (!node) continue; @@ -185,8 +185,8 @@ void pbqp_dump_graph(pbqp *pbqp) unsigned len = ARR_LEN(node->edges); unsigned edge_index; for (edge_index = 0; edge_index < len; ++edge_index) { - pbqp_node *tgt_node = node->edges[edge_index]->tgt; - unsigned tgt_index = tgt_node->index; + pbqp_node_t *tgt_node = node->edges[edge_index]->tgt; + unsigned tgt_index = tgt_node->index; if (node_is_reduced(tgt_node)) continue; @@ -200,7 +200,7 @@ void pbqp_dump_graph(pbqp *pbqp) fputs("\t}\n\n

\n", pbqp->dump_file); } -void pbqp_dump_input(pbqp *pbqp) +void pbqp_dump_input(pbqp_t *pbqp) { assert(pbqp); assert(pbqp->dump_file); @@ -214,7 +214,7 @@ void pbqp_dump_input(pbqp *pbqp) dump_edge_costs(pbqp); } -void dump_simplifyedge(pbqp *pbqp, pbqp_edge *edge) +void dump_simplifyedge(pbqp_t *pbqp, pbqp_edge_t *edge) { assert(pbqp); assert(pbqp->dump_file); diff --git a/html_dumper.h b/html_dumper.h index d8792f925..7f0ac06aa 100644 --- a/html_dumper.h +++ b/html_dumper.h @@ -29,15 +29,15 @@ #include "pbqp_t.h" -void pbqp_dump_input(pbqp *pbqp); +void pbqp_dump_input(pbqp_t *pbqp); -void pbqp_dump_graph(pbqp *pbqp); +void pbqp_dump_graph(pbqp_t *pbqp); -void dump_simplifyedge(pbqp *pbqp, pbqp_edge *edge); +void dump_simplifyedge(pbqp_t *pbqp, pbqp_edge_t *edge); void dump_section(FILE *f, int level, const char *txt); -void dump_node(FILE *file, pbqp_node *node); -void dump_edge(FILE *file, pbqp_edge *edge); +void dump_node(FILE *file, pbqp_node_t *node); +void dump_edge(FILE *file, pbqp_edge_t *edge); #endif /* KAPS_HTML_DUMPER_H */ diff --git a/kaps.c b/kaps.c index 88dbebde3..8bbbd931d 100644 --- a/kaps.c +++ b/kaps.c @@ -27,6 +27,7 @@ #include "config.h" #include "adt/array.h" +#include "adt/xmalloc.h" #include "kaps.h" #include "matrix.h" @@ -36,12 +37,12 @@ #include "pbqp_node_t.h" #include "vector.h" -pbqp_node *get_node(pbqp *pbqp, unsigned index) +pbqp_node_t *get_node(pbqp_t *pbqp, unsigned index) { return pbqp->nodes[index]; } -pbqp_edge *get_edge(pbqp *pbqp, unsigned src_index, unsigned tgt_index) +pbqp_edge_t *get_edge(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index) { int i; int len; @@ -52,15 +53,15 @@ pbqp_edge *get_edge(pbqp *pbqp, unsigned src_index, unsigned tgt_index) tgt_index = tmp; } - pbqp_node *src_node = get_node(pbqp, src_index); - pbqp_node *tgt_node = get_node(pbqp, tgt_index); + pbqp_node_t *src_node = get_node(pbqp, src_index); + pbqp_node_t *tgt_node = get_node(pbqp, tgt_index); assert(src_node); assert(tgt_node); len = ARR_LEN(src_node->edges); for (i = 0; i < len; ++i) { - pbqp_edge *cur_edge = src_node->edges[i]; + pbqp_edge_t *cur_edge = src_node->edges[i]; if (cur_edge->tgt == tgt_node) { return cur_edge; } @@ -69,9 +70,9 @@ pbqp_edge *get_edge(pbqp *pbqp, unsigned src_index, unsigned tgt_index) return NULL; } -pbqp *alloc_pbqp(unsigned number_nodes) +pbqp_t *alloc_pbqp(unsigned number_nodes) { - pbqp* pbqp = xmalloc(sizeof(*pbqp)); + pbqp_t *pbqp = XMALLOC(pbqp_t); obstack_init(&pbqp->obstack); @@ -80,9 +81,7 @@ pbqp *alloc_pbqp(unsigned number_nodes) #if KAPS_DUMP pbqp->dump_file = NULL; #endif - pbqp->nodes = obstack_alloc(&pbqp->obstack, number_nodes - * sizeof(*pbqp->nodes)); - memset(pbqp->nodes, 0, number_nodes * sizeof(*pbqp->nodes)); + pbqp->nodes = OALLOCNZ(&pbqp->obstack, pbqp_node_t*, number_nodes); #if KAPS_STATISTIC pbqp->num_bf = 0; pbqp->num_edges = 0; @@ -96,15 +95,15 @@ pbqp *alloc_pbqp(unsigned number_nodes) return pbqp; } -void free_pbqp(pbqp *pbqp) +void free_pbqp(pbqp_t *pbqp) { obstack_free(&pbqp->obstack, NULL); xfree(pbqp); } -void add_node_costs(pbqp *pbqp, unsigned node_index, vector *costs) +void add_node_costs(pbqp_t *pbqp, unsigned node_index, vector_t *costs) { - pbqp_node *node = get_node(pbqp, node_index); + pbqp_node_t *node = get_node(pbqp, node_index); if (node == NULL) { node = alloc_node(pbqp, node_index, costs); @@ -114,10 +113,10 @@ void add_node_costs(pbqp *pbqp, unsigned node_index, vector *costs) } } -void add_edge_costs(pbqp *pbqp, unsigned src_index, unsigned tgt_index, - pbqp_matrix *costs) +void add_edge_costs(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index, + pbqp_matrix_t *costs) { - pbqp_edge *edge = get_edge(pbqp, src_index, tgt_index); + pbqp_edge_t *edge = get_edge(pbqp, src_index, tgt_index); if (tgt_index < src_index) { pbqp_matrix_transpose(pbqp, costs); @@ -132,15 +131,15 @@ void add_edge_costs(pbqp *pbqp, unsigned src_index, unsigned tgt_index, } } -num get_node_solution(pbqp *pbqp, unsigned node_index) +num get_node_solution(pbqp_t *pbqp, unsigned node_index) { - pbqp_node *node = get_node(pbqp, node_index); + pbqp_node_t *node = get_node(pbqp, node_index); assert(node); return node->solution; } -num get_solution(pbqp *pbqp) +num get_solution(pbqp_t *pbqp) { return pbqp->solution; } diff --git a/kaps.h b/kaps.h index 0f6086f9c..c9097aa6c 100644 --- a/kaps.h +++ b/kaps.h @@ -32,29 +32,30 @@ /** * Create an empty PBQP instance with the given number of nodes. */ -pbqp* alloc_pbqp(unsigned number_nodes); +pbqp_t* alloc_pbqp(unsigned number_nodes); /** * Free the given PBQP. */ -void free_pbqp(pbqp *pbqp); +void free_pbqp(pbqp_t *pbqp); /** * Add costs vector to given node. */ -void add_node_costs(pbqp *pbqp, unsigned node_index, vector *costs); +void add_node_costs(pbqp_t *pbqp, unsigned node_index, vector_t *costs); /** * Add costs matrix between given nodes. */ -void add_edge_costs(pbqp *pbqp, unsigned src_index, unsigned tgt_index, pbqp_matrix *costs); +void add_edge_costs(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index, + pbqp_matrix_t *costs); -pbqp_edge *get_edge(pbqp *pbqp, unsigned src_index, unsigned tgt_index); -pbqp_node *get_node(pbqp *pbqp, unsigned index); +pbqp_edge_t *get_edge(pbqp_t *pbqp, unsigned src_index, unsigned tgt_index); +pbqp_node_t *get_node(pbqp_t *pbqp, unsigned index); -num get_node_solution(pbqp *pbqp, unsigned node_index); -num get_solution(pbqp *pbqp); +num get_node_solution(pbqp_t *pbqp, unsigned node_index); +num get_solution(pbqp_t *pbqp); -void set_dumpfile(pbqp *pbqp, FILE *f); +void set_dumpfile(pbqp_t *pbqp, FILE *f); #endif /* KAPS_KAPS_H */ diff --git a/matrix.c b/matrix.c index cd3bfba81..8608057e6 100644 --- a/matrix.c +++ b/matrix.c @@ -33,14 +33,14 @@ #include "vector.h" #include "matrix.h" -pbqp_matrix *pbqp_matrix_alloc(pbqp *pbqp, unsigned rows, unsigned cols) +pbqp_matrix_t *pbqp_matrix_alloc(pbqp_t *pbqp, unsigned rows, unsigned cols) { assert(cols> 0); assert(rows> 0); unsigned length = rows * cols; - pbqp_matrix *mat = obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length); + pbqp_matrix_t *mat = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*mat) + sizeof(*mat->entries) * length); assert(mat); mat->cols = cols; @@ -50,23 +50,23 @@ pbqp_matrix *pbqp_matrix_alloc(pbqp *pbqp, unsigned rows, unsigned cols) return mat; } -pbqp_matrix *pbqp_matrix_copy(pbqp *pbqp, pbqp_matrix *m) +pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m) { - unsigned len = m->rows * m->cols; - pbqp_matrix *copy = obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len); + unsigned len = m->rows * m->cols; + pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_copy(&pbqp->obstack, m, sizeof(*copy) + sizeof(*copy->entries) * len); assert(copy); return copy; } -pbqp_matrix *pbqp_matrix_copy_and_transpose(pbqp *pbqp, pbqp_matrix *m) +pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m) { - unsigned i; - unsigned j; - unsigned cols = m->cols; - unsigned rows = m->rows; - unsigned len = rows * cols; - pbqp_matrix *copy = obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len); + unsigned i; + unsigned j; + unsigned cols = m->cols; + unsigned rows = m->rows; + unsigned len = rows * cols; + pbqp_matrix_t *copy = (pbqp_matrix_t*)obstack_alloc(&pbqp->obstack, sizeof(*copy) + sizeof(*copy->entries) * len); assert(copy); for (i = 0; i < rows; ++i) { @@ -81,21 +81,21 @@ pbqp_matrix *pbqp_matrix_copy_and_transpose(pbqp *pbqp, pbqp_matrix *m) return copy; } -void pbqp_matrix_transpose(pbqp *pbqp, pbqp_matrix *mat) +void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat) { unsigned len; assert(mat); len = mat->rows * mat->cols; - pbqp_matrix *tmp = pbqp_matrix_copy_and_transpose(pbqp, mat); + pbqp_matrix_t *tmp = pbqp_matrix_copy_and_transpose(pbqp, mat); memcpy(mat, tmp, sizeof(*mat) + sizeof(*mat->entries) * len); obstack_free(&pbqp->obstack, tmp); } -void pbqp_matrix_add(pbqp_matrix *sum, pbqp_matrix *summand) +void pbqp_matrix_add(pbqp_matrix_t *sum, pbqp_matrix_t *summand) { int i; int len; @@ -112,7 +112,7 @@ void pbqp_matrix_add(pbqp_matrix *sum, pbqp_matrix *summand) } } -void pbqp_matrix_set_col_value(pbqp_matrix *mat, unsigned col, num value) +void pbqp_matrix_set_col_value(pbqp_matrix_t *mat, unsigned col, num value) { unsigned row_index; unsigned row_len; @@ -127,7 +127,7 @@ void pbqp_matrix_set_col_value(pbqp_matrix *mat, unsigned col, num value) } } -void pbqp_matrix_set_row_value(pbqp_matrix *mat, unsigned row, num value) +void pbqp_matrix_set_row_value(pbqp_matrix_t *mat, unsigned row, num value) { unsigned col_index; unsigned col_len; @@ -142,7 +142,7 @@ void pbqp_matrix_set_row_value(pbqp_matrix *mat, unsigned row, num value) } } -void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value) +void pbqp_matrix_set(pbqp_matrix_t *mat, unsigned row, unsigned col, num value) { assert(mat); assert(col < mat->cols); @@ -151,7 +151,7 @@ void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value) mat->entries[row * mat->cols + col] = value; } -num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *flags) +num pbqp_matrix_get_col_min(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags) { unsigned row_index; num min = INF_COSTS; @@ -177,7 +177,7 @@ num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *fla return min; } -unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, vector *flags) +unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags) { unsigned row_index; unsigned min_index = 0; @@ -205,8 +205,8 @@ unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, return min_index; } -void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index, - vector *flags, num value) +void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index, + vector_t *flags, num value) { unsigned col_len; unsigned row_index; @@ -232,7 +232,7 @@ void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index, } } -num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *flags) +num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags) { unsigned col_index; num min = INF_COSTS; @@ -257,7 +257,7 @@ num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *fla return min; } -unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, vector *flags) +unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags) { unsigned col_index; unsigned min_index = 0; @@ -284,8 +284,8 @@ unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, return min_index; } -void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index, - vector *flags, num value) +void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index, + vector_t *flags, num value) { unsigned col_index; unsigned col_len; @@ -309,7 +309,7 @@ void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index, } } -int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec) +int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec) { unsigned col_index; unsigned col_len; @@ -339,7 +339,7 @@ int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec) return 1; } -void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec) +void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec) { unsigned col_index; unsigned col_len; @@ -362,7 +362,7 @@ void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec) } } -void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec) +void pbqp_matrix_add_to_all_rows(pbqp_matrix_t *mat, vector_t *vec) { unsigned col_index; unsigned col_len; diff --git a/matrix.h b/matrix.h index 162f761d4..c87f7770a 100644 --- a/matrix.h +++ b/matrix.h @@ -29,37 +29,37 @@ #include "matrix_t.h" -pbqp_matrix *pbqp_matrix_alloc(pbqp *pbqp, unsigned rows, unsigned cols); +pbqp_matrix_t *pbqp_matrix_alloc(pbqp_t *pbqp, unsigned rows, unsigned cols); /* Copy the given matrix. */ -pbqp_matrix *pbqp_matrix_copy(pbqp *pbqp, pbqp_matrix *m); +pbqp_matrix_t *pbqp_matrix_copy(pbqp_t *pbqp, pbqp_matrix_t *m); -pbqp_matrix *pbqp_matrix_copy_and_transpose(pbqp *pbqp, pbqp_matrix *m); +pbqp_matrix_t *pbqp_matrix_copy_and_transpose(pbqp_t *pbqp, pbqp_matrix_t *m); -void pbqp_matrix_transpose(pbqp *pbqp, pbqp_matrix *mat); +void pbqp_matrix_transpose(pbqp_t *pbqp, pbqp_matrix_t *mat); /* sum += summand */ -void pbqp_matrix_add(pbqp_matrix *sum, pbqp_matrix *summand); +void pbqp_matrix_add(pbqp_matrix_t *sum, pbqp_matrix_t *summand); -void pbqp_matrix_set(pbqp_matrix *mat, unsigned row, unsigned col, num value); +void pbqp_matrix_set(pbqp_matrix_t *mat, unsigned row, unsigned col, num value); -num pbqp_matrix_get_col_min(pbqp_matrix *matrix, unsigned col_index, vector *flags); -num pbqp_matrix_get_row_min(pbqp_matrix *matrix, unsigned row_index, vector *flags); +num pbqp_matrix_get_col_min(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags); +num pbqp_matrix_get_row_min(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags); -unsigned pbqp_matrix_get_col_min_index(pbqp_matrix *matrix, unsigned col_index, vector *flags); -unsigned pbqp_matrix_get_row_min_index(pbqp_matrix *matrix, unsigned row_index, vector *flags); +unsigned pbqp_matrix_get_col_min_index(pbqp_matrix_t *matrix, unsigned col_index, vector_t *flags); +unsigned pbqp_matrix_get_row_min_index(pbqp_matrix_t *matrix, unsigned row_index, vector_t *flags); -void pbqp_matrix_set_col_value(pbqp_matrix *mat, unsigned col, num value); -void pbqp_matrix_set_row_value(pbqp_matrix *mat, unsigned row, num value); +void pbqp_matrix_set_col_value(pbqp_matrix_t *mat, unsigned col, num value); +void pbqp_matrix_set_row_value(pbqp_matrix_t *mat, unsigned row, num value); -void pbqp_matrix_sub_col_value(pbqp_matrix *matrix, unsigned col_index, - vector *flags, num value); -void pbqp_matrix_sub_row_value(pbqp_matrix *matrix, unsigned row_index, - vector *flags, num value); +void pbqp_matrix_sub_col_value(pbqp_matrix_t *matrix, unsigned col_index, + vector_t *flags, num value); +void pbqp_matrix_sub_row_value(pbqp_matrix_t *matrix, unsigned row_index, + vector_t *flags, num value); -int pbqp_matrix_is_zero(pbqp_matrix *mat, vector *src_vec, vector *tgt_vec); +int pbqp_matrix_is_zero(pbqp_matrix_t *mat, vector_t *src_vec, vector_t *tgt_vec); -void pbqp_matrix_add_to_all_cols(pbqp_matrix *mat, vector *vec); -void pbqp_matrix_add_to_all_rows(pbqp_matrix *mat, vector *vec); +void pbqp_matrix_add_to_all_cols(pbqp_matrix_t *mat, vector_t *vec); +void pbqp_matrix_add_to_all_rows(pbqp_matrix_t *mat, vector_t *vec); #endif /* KAPS_MATRIX_H */ diff --git a/matrix_t.h b/matrix_t.h index fdf1ab444..f1458c1c4 100644 --- a/matrix_t.h +++ b/matrix_t.h @@ -29,9 +29,9 @@ #include "pbqp_t.h" -typedef struct pbqp_matrix pbqp_matrix; +typedef struct pbqp_matrix_t pbqp_matrix_t; -struct pbqp_matrix { +struct pbqp_matrix_t { unsigned rows; unsigned cols; num entries[]; diff --git a/optimal.c b/optimal.c index 9d6d2b619..fe82844ff 100644 --- a/optimal.c +++ b/optimal.c @@ -46,14 +46,14 @@ #include "plist.h" #include "timing.h" -pbqp_edge **edge_bucket; -pbqp_edge **rm_bucket; -pbqp_node **node_buckets[4]; -pbqp_node **reduced_bucket = NULL; -pbqp_node *merged_node = NULL; +pbqp_edge_t **edge_bucket; +pbqp_edge_t **rm_bucket; +pbqp_node_t **node_buckets[4]; +pbqp_node_t **reduced_bucket = NULL; +pbqp_node_t *merged_node = NULL; static int buckets_filled = 0; -static void insert_into_edge_bucket(pbqp_edge *edge) +static void insert_into_edge_bucket(pbqp_edge_t *edge) { if (edge_bucket_contains(edge_bucket, edge)) { /* Edge is already inserted. */ @@ -63,7 +63,7 @@ static void insert_into_edge_bucket(pbqp_edge *edge) edge_bucket_insert(&edge_bucket, edge); } -static void insert_into_rm_bucket(pbqp_edge *edge) +static void insert_into_rm_bucket(pbqp_edge_t *edge) { if (edge_bucket_contains(rm_bucket, edge)) { /* Edge is already inserted. */ @@ -101,7 +101,7 @@ void free_buckets(void) buckets_filled = 0; } -void fill_node_buckets(pbqp *pbqp) +void fill_node_buckets(pbqp_t *pbqp) { unsigned node_index; unsigned node_len; @@ -115,8 +115,8 @@ void fill_node_buckets(pbqp *pbqp) #endif for (node_index = 0; node_index < node_len; ++node_index) { - unsigned degree; - pbqp_node *node = get_node(pbqp, node_index); + unsigned degree; + pbqp_node_t *node = get_node(pbqp, node_index); if (!node) continue; @@ -138,13 +138,13 @@ void fill_node_buckets(pbqp *pbqp) #endif } -static void normalize_towards_source(pbqp_edge *edge) +static void normalize_towards_source(pbqp_edge_t *edge) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *src_vec; - vector *tgt_vec; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *src_vec; + vector_t *tgt_vec; unsigned src_len; unsigned tgt_len; unsigned src_index; @@ -195,7 +195,7 @@ static void normalize_towards_source(pbqp_edge *edge) unsigned edge_len = pbqp_node_get_degree(src_node); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge_candidate = src_node->edges[edge_index]; + pbqp_edge_t *edge_candidate = src_node->edges[edge_index]; if (edge_candidate != edge) { insert_into_edge_bucket(edge_candidate); @@ -204,13 +204,13 @@ static void normalize_towards_source(pbqp_edge *edge) } } -static void normalize_towards_target(pbqp_edge *edge) +static void normalize_towards_target(pbqp_edge_t *edge) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *src_vec; - vector *tgt_vec; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *src_vec; + vector_t *tgt_vec; unsigned src_len; unsigned tgt_len; unsigned tgt_index; @@ -261,7 +261,7 @@ static void normalize_towards_target(pbqp_edge *edge) unsigned edge_len = pbqp_node_get_degree(tgt_node); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge_candidate = tgt_node->edges[edge_index]; + pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index]; if (edge_candidate != edge) { insert_into_edge_bucket(edge_candidate); @@ -276,13 +276,13 @@ static void normalize_towards_target(pbqp_edge *edge) * Checks whether the source node of edge can be merged into the target node of * edge, and performs the merge, if possible. */ -static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge) +static void merge_source_into_target(pbqp_t *pbqp, pbqp_edge_t *edge) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *src_vec; - vector *tgt_vec; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *src_vec; + vector_t *tgt_vec; unsigned *mapping; unsigned src_len; unsigned tgt_len; @@ -358,15 +358,15 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge) /* Reconnect the source's edges with the target node. */ for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *old_edge = src_node->edges[edge_index]; - pbqp_edge *new_edge; - pbqp_matrix *old_matrix; - pbqp_matrix *new_matrix; - pbqp_node *other_node; - vector *other_vec; - unsigned other_len; - unsigned other_index; - unsigned tgt_index; + pbqp_edge_t *old_edge = src_node->edges[edge_index]; + pbqp_edge_t *new_edge; + pbqp_matrix_t *old_matrix; + pbqp_matrix_t *new_matrix; + pbqp_node_t *other_node; + vector_t *other_vec; + unsigned other_len; + unsigned other_index; + unsigned tgt_index; assert(old_edge); @@ -450,13 +450,13 @@ static void merge_source_into_target(pbqp *pbqp, pbqp_edge *edge) * Checks whether the target node of edge can be merged into the source node of * edge, and performs the merge, if possible. */ -static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge) +static void merge_target_into_source(pbqp_t *pbqp, pbqp_edge_t *edge) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *src_vec; - vector *tgt_vec; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *src_vec; + vector_t *tgt_vec; unsigned *mapping; unsigned src_len; unsigned tgt_len; @@ -532,15 +532,15 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge) /* Reconnect the target's edges with the source node. */ for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *old_edge = tgt_node->edges[edge_index]; - pbqp_edge *new_edge; - pbqp_matrix *old_matrix; - pbqp_matrix *new_matrix; - pbqp_node *other_node; - vector *other_vec; - unsigned other_len; - unsigned other_index; - unsigned src_index; + pbqp_edge_t *old_edge = tgt_node->edges[edge_index]; + pbqp_edge_t *new_edge; + pbqp_matrix_t *old_matrix; + pbqp_matrix_t *new_matrix; + pbqp_node_t *other_node; + vector_t *other_vec; + unsigned other_len; + unsigned other_index; + unsigned src_index; assert(old_edge); @@ -621,11 +621,11 @@ static void merge_target_into_source(pbqp *pbqp, pbqp_edge *edge) /** * Merge neighbors into the given node. */ -void apply_RM(pbqp *pbqp, pbqp_node *node) +void apply_RM(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge **edges; - unsigned edge_index; - unsigned edge_len; + pbqp_edge_t **edges; + unsigned edge_index; + unsigned edge_len; assert(node); assert(pbqp); @@ -635,14 +635,14 @@ void apply_RM(pbqp *pbqp, pbqp_node *node) /* Check all incident edges. */ for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge = edges[edge_index]; + pbqp_edge_t *edge = edges[edge_index]; insert_into_rm_bucket(edge); } /* ALAP: Merge neighbors into given node. */ while(edge_bucket_get_length(rm_bucket) > 0) { - pbqp_edge *edge = edge_bucket_pop(&rm_bucket); + pbqp_edge_t *edge = edge_bucket_pop(&rm_bucket); assert(edge); /* If the edge is not deleted: Try a merge. */ @@ -655,7 +655,7 @@ void apply_RM(pbqp *pbqp, pbqp_node *node) merged_node = node; } -void reorder_node_after_edge_deletion(pbqp_node *node) +void reorder_node_after_edge_deletion(pbqp_node_t *node) { unsigned degree = pbqp_node_get_degree(node); /* Assume node lost one incident edge. */ @@ -673,7 +673,7 @@ void reorder_node_after_edge_deletion(pbqp_node *node) node_bucket_insert(&node_buckets[degree], node); } -void reorder_node_after_edge_insertion(pbqp_node *node) +void reorder_node_after_edge_insertion(pbqp_node_t *node) { unsigned degree = pbqp_node_get_degree(node); /* Assume node lost one incident edge. */ @@ -691,15 +691,15 @@ void reorder_node_after_edge_insertion(pbqp_node *node) node_bucket_insert(&node_buckets[degree], node); } -void simplify_edge(pbqp *pbqp, pbqp_edge *edge) +void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *src_vec; - vector *tgt_vec; - int src_len; - int tgt_len; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *src_vec; + vector_t *tgt_vec; + int src_len; + int tgt_len; assert(pbqp); assert(edge); @@ -768,7 +768,7 @@ void simplify_edge(pbqp *pbqp, pbqp_edge *edge) } } -void initial_simplify_edges(pbqp *pbqp) +void initial_simplify_edges(pbqp_t *pbqp) { unsigned node_index; unsigned node_len; @@ -793,10 +793,10 @@ void initial_simplify_edges(pbqp *pbqp) /* First simplify all edges. */ for (node_index = 0; node_index < node_len; ++node_index) { - unsigned edge_index; - pbqp_node *node = get_node(pbqp, node_index); - pbqp_edge **edges; - unsigned edge_len; + unsigned edge_index; + pbqp_node_t *node = get_node(pbqp, node_index); + pbqp_edge_t **edges; + unsigned edge_len; if (!node) continue; @@ -804,7 +804,7 @@ void initial_simplify_edges(pbqp *pbqp) edge_len = pbqp_node_get_degree(node); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge = edges[edge_index]; + pbqp_edge_t *edge = edges[edge_index]; /* Simplify only once per edge. */ if (node != edge->src) continue; @@ -819,7 +819,7 @@ void initial_simplify_edges(pbqp *pbqp) #endif } -num determine_solution(pbqp *pbqp) +num determine_solution(pbqp_t *pbqp) { unsigned node_index; unsigned node_len; @@ -855,7 +855,7 @@ num determine_solution(pbqp *pbqp) #endif for (node_index = 0; node_index < node_len; ++node_index) { - pbqp_node *node = node_buckets[0][node_index]; + pbqp_node_t *node = node_buckets[0][node_index]; assert(node); node->solution = vector_get_min_index(node->costs); @@ -889,13 +889,13 @@ num determine_solution(pbqp *pbqp) return solution; } -static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *edge; - pbqp_node *other; - pbqp_matrix *mat; - vector *vec; - int is_src; + pbqp_edge_t *edge; + pbqp_node_t *other; + pbqp_matrix_t *mat; + vector_t *vec; + int is_src; assert(pbqp); assert(node); @@ -926,20 +926,20 @@ static void back_propagate_RI(pbqp *pbqp, pbqp_node *node) #endif } -static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) +static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *src_edge = node->edges[0]; - pbqp_edge *tgt_edge = node->edges[1]; - int src_is_src = src_edge->src == node; - int tgt_is_src = tgt_edge->src == node; - pbqp_matrix *src_mat; - pbqp_matrix *tgt_mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *vec; - vector *node_vec; - unsigned col_index; - unsigned row_index; + pbqp_edge_t *src_edge = node->edges[0]; + pbqp_edge_t *tgt_edge = node->edges[1]; + int src_is_src = src_edge->src == node; + int tgt_is_src = tgt_edge->src == node; + pbqp_matrix_t *src_mat; + pbqp_matrix_t *tgt_mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *vec; + vector_t *node_vec; + unsigned col_index; + unsigned row_index; assert(pbqp); @@ -957,8 +957,8 @@ static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) /* Swap nodes if necessary. */ if (tgt_node->index < src_node->index) { - pbqp_node *tmp_node; - pbqp_edge *tmp_edge; + pbqp_node_t *tmp_node; + pbqp_edge_t *tmp_edge; tmp_node = src_node; src_node = tgt_node; @@ -1005,7 +1005,7 @@ static void back_propagate_RII(pbqp *pbqp, pbqp_node *node) obstack_free(&pbqp->obstack, vec); } -void back_propagate(pbqp *pbqp) +void back_propagate(pbqp_t *pbqp) { unsigned node_index; unsigned node_len = node_bucket_get_length(reduced_bucket); @@ -1019,7 +1019,7 @@ void back_propagate(pbqp *pbqp) #endif for (node_index = node_len; node_index > 0; --node_index) { - pbqp_node *node = reduced_bucket[node_index - 1]; + pbqp_node_t *node = reduced_bucket[node_index - 1]; switch (pbqp_node_get_degree(node)) { case 1: @@ -1035,20 +1035,20 @@ void back_propagate(pbqp *pbqp) } } -void apply_edge(pbqp *pbqp) +void apply_edge(pbqp_t *pbqp) { - pbqp_edge *edge = edge_bucket_pop(&edge_bucket); + pbqp_edge_t *edge = edge_bucket_pop(&edge_bucket); simplify_edge(pbqp, edge); } -void apply_RI(pbqp *pbqp) +void apply_RI(pbqp_t *pbqp) { - 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; - pbqp_node *other_node; + pbqp_node_t *node = node_bucket_pop(&node_buckets[1]); + pbqp_edge_t *edge = node->edges[0]; + pbqp_matrix_t *mat = edge->costs; + int is_src = edge->src == node; + pbqp_node_t *other_node; (void ) pbqp; assert(pbqp_node_get_degree(node) == 1); @@ -1098,27 +1098,27 @@ void apply_RI(pbqp *pbqp) node_bucket_insert(&reduced_bucket, node); } -void apply_RII(pbqp *pbqp) +void apply_RII(pbqp_t *pbqp) { - 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; - int tgt_is_src = tgt_edge->src == node; - pbqp_matrix *src_mat; - pbqp_matrix *tgt_mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - pbqp_matrix *mat; - vector *vec; - vector *node_vec; - vector *src_vec; - vector *tgt_vec; - unsigned col_index; - unsigned col_len; - unsigned row_index; - unsigned row_len; - unsigned node_len; + pbqp_node_t *node = node_bucket_pop(&node_buckets[2]); + pbqp_edge_t *src_edge = node->edges[0]; + pbqp_edge_t *tgt_edge = node->edges[1]; + int src_is_src = src_edge->src == node; + int tgt_is_src = tgt_edge->src == node; + pbqp_matrix_t *src_mat; + pbqp_matrix_t *tgt_mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + pbqp_matrix_t *mat; + vector_t *vec; + vector_t *node_vec; + vector_t *src_vec; + vector_t *tgt_vec; + unsigned col_index; + unsigned col_len; + unsigned row_index; + unsigned row_len; + unsigned node_len; assert(pbqp); assert(pbqp_node_get_degree(node) == 2); @@ -1137,8 +1137,8 @@ void apply_RII(pbqp *pbqp) /* Swap nodes if necessary. */ if (tgt_node->index < src_node->index) { - pbqp_node *tmp_node; - pbqp_edge *tmp_edge; + pbqp_node_t *tmp_node; + pbqp_edge_t *tmp_edge; tmp_node = src_node; src_node = tgt_node; @@ -1202,7 +1202,7 @@ void apply_RII(pbqp *pbqp) } } - pbqp_edge *edge = get_edge(pbqp, src_node->index, tgt_node->index); + pbqp_edge_t *edge = get_edge(pbqp, src_node->index, tgt_node->index); /* Disconnect node. */ disconnect_edge(src_node, src_edge); @@ -1239,13 +1239,13 @@ void apply_RII(pbqp *pbqp) simplify_edge(pbqp, edge); } -static void select_column(pbqp_edge *edge, unsigned col_index) +static void select_column(pbqp_edge_t *edge, unsigned col_index) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *src_vec; - vector *tgt_vec; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *src_vec; + vector_t *tgt_vec; unsigned src_len; unsigned tgt_len; unsigned src_index; @@ -1288,7 +1288,7 @@ static void select_column(pbqp_edge *edge, unsigned col_index) unsigned edge_len = pbqp_node_get_degree(src_node); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge_candidate = src_node->edges[edge_index]; + pbqp_edge_t *edge_candidate = src_node->edges[edge_index]; if (edge_candidate != edge) { insert_into_edge_bucket(edge_candidate); @@ -1299,12 +1299,12 @@ static void select_column(pbqp_edge *edge, unsigned col_index) delete_edge(edge); } -static void select_row(pbqp_edge *edge, unsigned row_index) +static void select_row(pbqp_edge_t *edge, unsigned row_index) { - pbqp_matrix *mat; - pbqp_node *src_node; - pbqp_node *tgt_node; - vector *tgt_vec; + pbqp_matrix_t *mat; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; + vector_t *tgt_vec; unsigned tgt_len; unsigned tgt_index; unsigned new_infinity = 0; @@ -1341,7 +1341,7 @@ static void select_row(pbqp_edge *edge, unsigned row_index) unsigned edge_len = pbqp_node_get_degree(tgt_node); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge_candidate = tgt_node->edges[edge_index]; + pbqp_edge_t *edge_candidate = tgt_node->edges[edge_index]; if (edge_candidate != edge) { insert_into_edge_bucket(edge_candidate); @@ -1352,12 +1352,12 @@ static void select_row(pbqp_edge *edge, unsigned row_index) delete_edge(edge); } -void select_alternative(pbqp_node *node, unsigned selected_index) +void select_alternative(pbqp_node_t *node, unsigned selected_index) { unsigned edge_index; unsigned node_index; unsigned node_len; - vector *node_vec; + vector_t *node_vec; unsigned max_degree = pbqp_node_get_degree(node); assert(node); @@ -1375,7 +1375,7 @@ void select_alternative(pbqp_node *node, unsigned selected_index) /* Select corresponding row/column for incident edges. */ for (edge_index = 0; edge_index < max_degree; ++edge_index) { - pbqp_edge *edge = node->edges[edge_index]; + pbqp_edge_t *edge = node->edges[edge_index]; if (edge->src == node) select_row(edge, selected_index); @@ -1384,17 +1384,17 @@ void select_alternative(pbqp_node *node, unsigned selected_index) } } -pbqp_node *get_node_with_max_degree(void) +pbqp_node_t *get_node_with_max_degree(void) { - pbqp_node **bucket = node_buckets[3]; - unsigned bucket_len = node_bucket_get_length(bucket); - unsigned bucket_index; - unsigned max_degree = 0; - pbqp_node *result = NULL; + pbqp_node_t **bucket = node_buckets[3]; + unsigned bucket_len = node_bucket_get_length(bucket); + unsigned bucket_index; + unsigned max_degree = 0; + pbqp_node_t *result = NULL; for (bucket_index = 0; bucket_index < bucket_len; ++bucket_index) { - pbqp_node *candidate = bucket[bucket_index]; - unsigned degree = pbqp_node_get_degree(candidate); + pbqp_node_t *candidate = bucket[bucket_index]; + unsigned degree = pbqp_node_get_degree(candidate); if (degree > max_degree) { result = candidate; @@ -1405,19 +1405,19 @@ pbqp_node *get_node_with_max_degree(void) return result; } -unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node) +unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node) { - pbqp_edge *edge; - vector *node_vec; - vector *vec; - pbqp_matrix *mat; - unsigned edge_index; - unsigned max_degree; - unsigned node_index; - unsigned node_len; - unsigned min_index = 0; - num min = INF_COSTS; - int is_src; + pbqp_edge_t *edge; + vector_t *node_vec; + vector_t *vec; + pbqp_matrix_t *mat; + unsigned edge_index; + unsigned max_degree; + unsigned node_index; + unsigned node_len; + unsigned min_index = 0; + num min = INF_COSTS; + int is_src; assert(pbqp); assert(node); @@ -1455,7 +1455,7 @@ unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node) return min_index; } -int node_is_reduced(pbqp_node *node) +int node_is_reduced(pbqp_node_t *node) { if (!reduced_bucket) return 0; diff --git a/optimal.h b/optimal.h index 8b4a0d3c6..ec7b026e5 100644 --- a/optimal.h +++ b/optimal.h @@ -29,29 +29,29 @@ #include "pbqp_t.h" -extern pbqp_edge **edge_bucket; -extern pbqp_node **node_buckets[4]; -extern pbqp_node **reduced_bucket; -extern pbqp_node *merged_node; +extern pbqp_edge_t **edge_bucket; +extern pbqp_node_t **node_buckets[4]; +extern pbqp_node_t **reduced_bucket; +extern pbqp_node_t *merged_node; -void apply_edge(pbqp *pbqp); +void apply_edge(pbqp_t *pbqp); -void apply_RI(pbqp *pbqp); -void apply_RII(pbqp *pbqp); -void apply_RM(pbqp *pbqp, pbqp_node *node); +void apply_RI(pbqp_t *pbqp); +void apply_RII(pbqp_t *pbqp); +void apply_RM(pbqp_t *pbqp, pbqp_node_t *node); -void back_propagate(pbqp *pbqp); -num determine_solution(pbqp *pbqp); -void fill_node_buckets(pbqp *pbqp); +void back_propagate(pbqp_t *pbqp); +num determine_solution(pbqp_t *pbqp); +void fill_node_buckets(pbqp_t *pbqp); void free_buckets(void); -unsigned get_local_minimal_alternative(pbqp *pbqp, pbqp_node *node); -pbqp_node *get_node_with_max_degree(void); -void initial_simplify_edges(pbqp *pbqp); -void select_alternative(pbqp_node *node, unsigned selected_index); -void simplify_edge(pbqp *pbqp, pbqp_edge *edge); -void reorder_node_after_edge_deletion(pbqp_node *node); -void reorder_node_after_edge_insertion(pbqp_node *node); - -int node_is_reduced(pbqp_node *node); +unsigned get_local_minimal_alternative(pbqp_t *pbqp, pbqp_node_t *node); +pbqp_node_t *get_node_with_max_degree(void); +void initial_simplify_edges(pbqp_t *pbqp); +void select_alternative(pbqp_node_t *node, unsigned selected_index); +void simplify_edge(pbqp_t *pbqp, pbqp_edge_t *edge); +void reorder_node_after_edge_deletion(pbqp_node_t *node); +void reorder_node_after_edge_insertion(pbqp_node_t *node); + +int node_is_reduced(pbqp_node_t *node); #endif /* KAPS_OPTIMAL_H */ diff --git a/pbqp_edge.c b/pbqp_edge.c index 351f157a5..8a1d0c44f 100644 --- a/pbqp_edge.c +++ b/pbqp_edge.c @@ -38,7 +38,8 @@ #include "pbqp_node_t.h" #include "pbqp_t.h" -pbqp_edge *alloc_edge(pbqp *pbqp, int src_index, int tgt_index, pbqp_matrix *costs) +pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index, + pbqp_matrix_t *costs) { int transpose = 0; @@ -50,13 +51,13 @@ pbqp_edge *alloc_edge(pbqp *pbqp, int src_index, int tgt_index, pbqp_matrix *cos transpose = 1; } - pbqp_edge *edge = obstack_alloc(&pbqp->obstack, sizeof(*edge)); + pbqp_edge_t *edge = OALLOC(&pbqp->obstack, pbqp_edge_t); assert(edge); - pbqp_node *src_node = get_node(pbqp, src_index); + pbqp_node_t *src_node = get_node(pbqp, src_index); assert(src_node); - pbqp_node *tgt_node = get_node(pbqp, tgt_index); + pbqp_node_t *tgt_node = get_node(pbqp, tgt_index); assert(tgt_node); if (transpose) { @@ -69,19 +70,19 @@ pbqp_edge *alloc_edge(pbqp *pbqp, int src_index, int tgt_index, pbqp_matrix *cos * Connect edge with incident nodes. Since the edge is allocated, we know * that it don't appear in the edge lists of the nodes. */ - ARR_APP1(pbqp_edge *, src_node->edges, edge); + ARR_APP1(pbqp_edge_t *, src_node->edges, edge); edge->src = src_node; - ARR_APP1(pbqp_edge *, tgt_node->edges, edge); + ARR_APP1(pbqp_edge_t *, tgt_node->edges, edge); edge->tgt = tgt_node; edge->bucket_index = UINT_MAX; return edge; } -void delete_edge(pbqp_edge *edge) +void delete_edge(pbqp_edge_t *edge) { - pbqp_node *src_node; - pbqp_node *tgt_node; + pbqp_node_t *src_node; + pbqp_node_t *tgt_node; assert(edge); @@ -100,7 +101,7 @@ void delete_edge(pbqp_edge *edge) reorder_node_after_edge_deletion(tgt_node); } -unsigned is_deleted(pbqp_edge *edge) +unsigned is_deleted(pbqp_edge_t *edge) { unsigned deleted; @@ -111,11 +112,10 @@ unsigned is_deleted(pbqp_edge *edge) return deleted; } -pbqp_edge *pbqp_edge_deep_copy(pbqp *pbqp, pbqp_edge *edge, - pbqp_node *src_node, pbqp_node *tgt_node) +pbqp_edge_t *pbqp_edge_deep_copy(pbqp_t *pbqp, pbqp_edge_t *edge, + pbqp_node_t *src_node, pbqp_node_t *tgt_node) { - pbqp_edge *copy = obstack_alloc(&pbqp->obstack, sizeof(*copy)); - assert(copy); + pbqp_edge_t *copy = OALLOC(&pbqp->obstack, pbqp_edge_t); assert(src_node); assert(tgt_node); diff --git a/pbqp_edge.h b/pbqp_edge.h index d7a78660e..1e649a2ad 100644 --- a/pbqp_edge.h +++ b/pbqp_edge.h @@ -29,12 +29,13 @@ #include "pbqp_t.h" -pbqp_edge *alloc_edge(pbqp *pbqp, int src_index, int tgt_index, pbqp_matrix *costs); +pbqp_edge_t *alloc_edge(pbqp_t *pbqp, int src_index, int tgt_index, + pbqp_matrix_t *costs); -pbqp_edge *pbqp_edge_deep_copy(pbqp *pbqp, pbqp_edge *edge, - pbqp_node *src_node, pbqp_node *tgt_node); +pbqp_edge_t *pbqp_edge_deep_copy(pbqp_t *pbqp, pbqp_edge_t *edge, + pbqp_node_t *src_node, pbqp_node_t *tgt_node); -void delete_edge(pbqp_edge *edge); -unsigned is_deleted(pbqp_edge *edge); +void delete_edge(pbqp_edge_t *edge); +unsigned is_deleted(pbqp_edge_t *edge); #endif /* KAPS_PBQP_EDGE_H */ diff --git a/pbqp_edge_t.h b/pbqp_edge_t.h index ce6f14ef9..02f02480a 100644 --- a/pbqp_edge_t.h +++ b/pbqp_edge_t.h @@ -29,11 +29,11 @@ #include "pbqp_t.h" -struct pbqp_edge { - pbqp_node *src; /* Source index. */ - pbqp_node *tgt; /* Target index. */ - pbqp_matrix *costs; /* Cost matrix. */ - unsigned bucket_index; /* Index of edge bucket. */ +struct pbqp_edge_t { + pbqp_node_t *src; /* Source index. */ + pbqp_node_t *tgt; /* Target index. */ + pbqp_matrix_t *costs; /* Cost matrix. */ + unsigned bucket_index; /* Index of edge bucket. */ }; #endif /* KAPS_PBQP_EDGE_T_H */ diff --git a/pbqp_node.c b/pbqp_node.c index cd9536b21..bb8a352e8 100644 --- a/pbqp_node.c +++ b/pbqp_node.c @@ -37,12 +37,12 @@ #include "pbqp_node_t.h" #include "vector.h" -pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs) +pbqp_node_t *alloc_node(pbqp_t *pbqp, unsigned node_index, vector_t *costs) { - pbqp_node *node = obstack_alloc(&pbqp->obstack, sizeof(*node)); + pbqp_node_t *node = OALLOC(&pbqp->obstack, pbqp_node_t); assert(node); - node->edges = NEW_ARR_F(pbqp_edge *, 0); + node->edges = NEW_ARR_F(pbqp_edge_t *, 0); node->costs = vector_copy(pbqp, costs); node->bucket_index = UINT_MAX; node->solution = UINT_MAX; @@ -51,11 +51,11 @@ pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs) return node; } -int is_connected(pbqp_node *node, pbqp_edge *edge) +int is_connected(pbqp_node_t *node, pbqp_edge_t *edge) { - pbqp_edge **edges; - unsigned edge_index; - unsigned edge_len; + pbqp_edge_t **edges; + unsigned edge_index; + unsigned edge_len; assert(node); assert(edge); @@ -66,7 +66,7 @@ int is_connected(pbqp_node *node, pbqp_edge *edge) edge_len = ARR_LEN(edges); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge_candidate = edges[edge_index]; + pbqp_edge_t *edge_candidate = edges[edge_index]; if (edge_candidate == edge) { return 1; } @@ -75,17 +75,17 @@ int is_connected(pbqp_node *node, pbqp_edge *edge) return 0; } -void disconnect_edge(pbqp_node *node, pbqp_edge *edge) +void disconnect_edge(pbqp_node_t *node, pbqp_edge_t *edge) { - pbqp_edge **edges; - unsigned edge_index; - unsigned edge_len; + pbqp_edge_t **edges; + unsigned edge_index; + unsigned edge_len; edges = node->edges; edge_len = ARR_LEN(edges); for (edge_index = 0; edge_index < edge_len; ++edge_index) { - pbqp_edge *edge_candidate = edges[edge_index]; + pbqp_edge_t *edge_candidate = edges[edge_index]; if (edge_candidate == edge) { edges[edge_index] = edges[edge_len - 1]; ARR_SHRINKLEN(edges, (int)edge_len - 1); @@ -94,34 +94,35 @@ void disconnect_edge(pbqp_node *node, pbqp_edge *edge) } } -unsigned pbqp_node_get_degree(pbqp_node *node) +unsigned pbqp_node_get_degree(pbqp_node_t *node) { assert(node); return ARR_LEN(node->edges); } -pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node_bucket new_bucket, pbqp_node *node) +pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket, + pbqp_node_t *node) { - unsigned edge_index; - unsigned edge_length = pbqp_node_get_degree(node); - pbqp_node *copy = obstack_alloc(&pbqp->obstack, sizeof(*node)); + unsigned edge_index; + unsigned edge_length = pbqp_node_get_degree(node); + pbqp_node_t *copy = OALLOC(&pbqp->obstack, pbqp_node_t); assert(copy); - copy->edges = NEW_ARR_F(pbqp_edge *, 0); + copy->edges = NEW_ARR_F(pbqp_edge_t *, 0); for (edge_index = 0; edge_index < edge_length; ++edge_index) { - pbqp_edge *edge_copy = NULL; - pbqp_edge *edge = node->edges[edge_index]; - int is_src = edge->src == node; + pbqp_edge_t *edge_copy = NULL; + pbqp_edge_t *edge = node->edges[edge_index]; + int is_src = edge->src == node; if (is_src) { unsigned other_index = edge->tgt->bucket_index; unsigned is_copied = other_index < node->bucket_index; if (is_copied) { - pbqp_node *other_copy = new_bucket[other_index]; - unsigned degree = pbqp_node_get_degree(other_copy); - unsigned index; + pbqp_node_t *other_copy = new_bucket[other_index]; + unsigned degree = pbqp_node_get_degree(other_copy); + unsigned index; for (index = 0; index < degree; ++index) { if (other_copy->edges[index]->src == node) { @@ -138,9 +139,9 @@ pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node_bucket new_bucket, pbqp_nod unsigned is_copied = other_index < node->bucket_index; if (is_copied) { - pbqp_node *other_copy = new_bucket[other_index]; - unsigned degree = pbqp_node_get_degree(other_copy); - unsigned index; + pbqp_node_t *other_copy = new_bucket[other_index]; + unsigned degree = pbqp_node_get_degree(other_copy); + unsigned index; for (index = 0; index < degree; ++index) { if (other_copy->edges[index]->tgt == node) { @@ -153,7 +154,7 @@ pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node_bucket new_bucket, pbqp_nod edge_copy = pbqp_edge_deep_copy(pbqp, edge, edge->src, copy); } } - ARR_APP1(pbqp_edge *, copy->edges, edge_copy); + ARR_APP1(pbqp_edge_t *, copy->edges, edge_copy); } copy->costs = vector_copy(pbqp, node->costs); copy->bucket_index = node->bucket_index; diff --git a/pbqp_node.h b/pbqp_node.h index c8f66c712..a54390726 100644 --- a/pbqp_node.h +++ b/pbqp_node.h @@ -30,15 +30,15 @@ #include "bucket_t.h" #include "pbqp_t.h" -pbqp_node *alloc_node(pbqp *pbqp, unsigned node_index, vector *costs); +pbqp_node_t *alloc_node(pbqp_t *pbqp, unsigned node_index, vector_t *costs); -void disconnect_edge(pbqp_node *node, pbqp_edge *edge); +void disconnect_edge(pbqp_node_t *node, pbqp_edge_t *edge); -int is_connected(pbqp_node *node, pbqp_edge *edge); +int is_connected(pbqp_node_t *node, pbqp_edge_t *edge); -unsigned pbqp_node_get_degree(pbqp_node *node); +unsigned pbqp_node_get_degree(pbqp_node_t *node); -pbqp_node *pbqp_node_deep_copy(pbqp *pbqp, pbqp_node_bucket new_bucket, - pbqp_node *node); +pbqp_node_t *pbqp_node_deep_copy(pbqp_t *pbqp, pbqp_node_bucket_t new_bucket, + pbqp_node_t *node); #endif /* KAPS_PBQP_NODE_H */ diff --git a/pbqp_node_t.h b/pbqp_node_t.h index 721b43b0b..4cd06fab0 100644 --- a/pbqp_node_t.h +++ b/pbqp_node_t.h @@ -29,12 +29,12 @@ #include "pbqp_t.h" -struct pbqp_node { - pbqp_edge **edges; - vector *costs; - unsigned bucket_index; - unsigned solution; - unsigned index; +struct pbqp_node_t { + pbqp_edge_t **edges; + vector_t *costs; + unsigned bucket_index; + unsigned solution; + unsigned index; }; #endif /* KAPS_PBQP_NODE_T_H */ diff --git a/pbqp_t.h b/pbqp_t.h index 438bddd5f..11cb51c7f 100644 --- a/pbqp_t.h +++ b/pbqp_t.h @@ -50,15 +50,15 @@ #include "matrix_t.h" #include "vector_t.h" -typedef struct pbqp_edge pbqp_edge; -typedef struct pbqp_node pbqp_node; -typedef struct pbqp pbqp; +typedef struct pbqp_edge_t pbqp_edge_t; +typedef struct pbqp_node_t pbqp_node_t; +typedef struct pbqp_t pbqp_t; -struct pbqp { +struct pbqp_t { struct obstack obstack; /* Obstack. */ num solution; /* Computed solution. */ size_t num_nodes; /* Number of PBQP nodes. */ - pbqp_node **nodes; /* Nodes of PBQP. */ + pbqp_node_t **nodes; /* Nodes of PBQP. */ FILE *dump_file; /* File to dump in. */ #if KAPS_STATISTIC unsigned num_bf; /* Number of brute force reductions. */ diff --git a/vector.c b/vector.c index d1695d3d0..04d58e695 100644 --- a/vector.c +++ b/vector.c @@ -54,10 +54,10 @@ num pbqp_add(num x, num y) return res; } -vector *vector_alloc(pbqp *pbqp, unsigned length) +vector_t *vector_alloc(pbqp_t *pbqp, unsigned length) { assert(length > 0); - vector *vec = obstack_alloc(&pbqp->obstack, sizeof(*vec) + sizeof(*vec->entries) * length); + vector_t *vec = (vector_t*)obstack_alloc(&pbqp->obstack, sizeof(*vec) + sizeof(*vec->entries) * length); assert(vec); vec->len = length; @@ -66,16 +66,16 @@ vector *vector_alloc(pbqp *pbqp, unsigned length) return vec; } -vector *vector_copy(pbqp *pbqp, vector *v) +vector_t *vector_copy(pbqp_t *pbqp, vector_t *v) { unsigned len = v->len; - vector *copy = obstack_copy(&pbqp->obstack, v, sizeof(*copy) + sizeof(*copy->entries) * len); + vector_t *copy = (vector_t*)obstack_copy(&pbqp->obstack, v, sizeof(*copy) + sizeof(*copy->entries) * len); assert(copy); return copy; } -void vector_add(vector *sum, vector *summand) +void vector_add(vector_t *sum, vector_t *summand) { int i; int len; @@ -92,21 +92,21 @@ void vector_add(vector *sum, vector *summand) } } -void vector_set(vector *vec, unsigned index, num value) +void vector_set(vector_t *vec, unsigned index, num value) { assert(index < vec->len); vec->entries[index].data = value; } #if KAPS_ENABLE_VECTOR_NAMES -void vector_set_description(vector *vec, unsigned index, const char *name) +void vector_set_description(vector_t *vec, unsigned index, const char *name) { assert(index < vec->len); vec->entries[index].name = name; } #endif -void vector_add_value(vector *vec, num value) +void vector_add_value(vector_t *vec, num value) { unsigned index; unsigned len; @@ -120,7 +120,7 @@ void vector_add_value(vector *vec, num value) } } -void vector_add_matrix_col(vector *vec, pbqp_matrix *mat, unsigned col_index) +void vector_add_matrix_col(vector_t *vec, pbqp_matrix_t *mat, unsigned col_index) { unsigned index; unsigned len; @@ -137,7 +137,7 @@ void vector_add_matrix_col(vector *vec, pbqp_matrix *mat, unsigned col_index) } } -void vector_add_matrix_row(vector *vec, pbqp_matrix *mat, unsigned row_index) +void vector_add_matrix_row(vector_t *vec, pbqp_matrix_t *mat, unsigned row_index) { unsigned index; unsigned len; @@ -155,7 +155,7 @@ void vector_add_matrix_row(vector *vec, pbqp_matrix *mat, unsigned row_index) } } -num vector_get_min(vector *vec) +num vector_get_min(vector_t *vec) { unsigned index; unsigned len; @@ -177,7 +177,7 @@ num vector_get_min(vector *vec) return min; } -unsigned vector_get_min_index(vector *vec) +unsigned vector_get_min_index(vector_t *vec) { unsigned index; unsigned len; diff --git a/vector.h b/vector.h index b9cce52ee..d54aaeaa8 100644 --- a/vector.h +++ b/vector.h @@ -31,26 +31,26 @@ num pbqp_add(num x, num y); -vector *vector_alloc(pbqp *pbqp, unsigned length); +vector_t *vector_alloc(pbqp_t *pbqp, unsigned length); /* Copy the given vector. */ -vector *vector_copy(pbqp *pbqp, vector *v); +vector_t *vector_copy(pbqp_t *pbqp, vector_t *v); /* sum += summand */ -void vector_add(vector *sum, vector *summand); +void vector_add(vector_t *sum, vector_t *summand); -void vector_set(vector *vec, unsigned index, num value); +void vector_set(vector_t *vec, unsigned index, num value); #if KAPS_ENABLE_VECTOR_NAMES -void vector_set_description(vector *vec, unsigned index, const char *name); +void vector_set_description(vector_t *vec, unsigned index, const char *name); #endif -void vector_add_value(vector *vec, num value); +void vector_add_value(vector_t *vec, num value); -void vector_add_matrix_col(vector *vec, pbqp_matrix *mat, unsigned col_index); -void vector_add_matrix_row(vector *vec, pbqp_matrix *mat, unsigned row_index); +void vector_add_matrix_col(vector_t *vec, pbqp_matrix_t *mat, unsigned col_index); +void vector_add_matrix_row(vector_t *vec, pbqp_matrix_t *mat, unsigned row_index); -num vector_get_min(vector *vec); -unsigned vector_get_min_index(vector *vec); +num vector_get_min(vector_t *vec); +unsigned vector_get_min_index(vector_t *vec); #endif /* KAPS_VECTOR_H */ diff --git a/vector_t.h b/vector_t.h index 41dc34db2..03692d1ba 100644 --- a/vector_t.h +++ b/vector_t.h @@ -30,20 +30,20 @@ #include "pbqp_t.h" -typedef struct vec_elem vec_elem; +typedef struct vec_elem_t vec_elem_t; -struct vec_elem { +struct vec_elem_t { num data; #if KAPS_ENABLE_VECTOR_NAMES const char *name; #endif }; -typedef struct vector vector; +typedef struct vector_t vector_t; -struct vector { - unsigned len; - vec_elem entries[]; +struct vector_t { + unsigned len; + vec_elem_t entries[]; }; #endif /* KAPS_VECTOR_T_H */ -- 2.20.1