Added strict_flag to new_r/rd_Conv(). Fixed strict Convs for irio.

[libfirm] / ir / adt / hungarian.c

diff --git a/ir/adt/hungarian.c b/ir/adt/hungarian.c
index 953cf7d..32f1d68 100644 (file)
--- a/ir/adt/hungarian.c
+++ b/ir/adt/hungarian.c
@@ -24,7 +24,12 @@
  ********************************************************************
  ********************************************************************/
 
-/* $Id$ */
+/**
+ * @file
+ * @brief   Solving the Minimum Assignment Problem using the Hungarian Method.
+ * @version $Id$
+ */
+#include "config.h"
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -53,7 +58,7 @@ struct _hungarian_problem_t {
        DEBUG_ONLY(firm_dbg_module_t *dbg);
 };
 
-static INLINE void *get_init_mem(struct obstack *obst, long sz) {
+static inline void *get_init_mem(struct obstack *obst, long sz) {
        void *p = obstack_alloc(obst, sz);
        memset(p, 0, sz);
        return p;
@@ -82,10 +87,7 @@ void hungarian_print_costmatrix(hungarian_problem_t *p) {
  */
 hungarian_problem_t *hungarian_new(int rows, int cols, int width, int match_type) {
        int i;
-       int max_cost = 0;
-       hungarian_problem_t *p = xmalloc(sizeof(*p));
-
-       memset(p, 0, sizeof(p));
+       hungarian_problem_t *p = XMALLOCZ(hungarian_problem_t);
 
        FIRM_DBG_REGISTER(p->dbg, "firm.hungarian");
 
@@ -149,6 +151,7 @@ void hungarian_prepare_cost_matrix(hungarian_problem_t *p, int mode) {
 void hungarian_add(hungarian_problem_t *p, int left, int right, int cost) {
        assert(p->num_rows > left  && "Invalid row selected.");
        assert(p->num_cols > right && "Invalid column selected.");
+       assert(cost >= 0);
 
        p->cost[left][right] = cost;
        p->max_cost          = MAX(p->max_cost, cost);
@@ -185,7 +188,7 @@ void hungarian_free(hungarian_problem_t* p) {
 /**
  * Do the assignment.
  */
-int hungarian_solve(hungarian_problem_t* p, int *assignment) {
+int hungarian_solve(hungarian_problem_t* p, int *assignment, int *final_cost, int cost_threshold) {
        int i, j, m, n, k, l, s, t, q, unmatched, cost;
        int *col_mate;
        int *row_mate;
@@ -200,15 +203,15 @@ int hungarian_solve(hungarian_problem_t* p, int *assignment) {
        m    = p->num_rows;
        n    = p->num_cols;
 
-       col_mate     = xcalloc(p->num_rows, sizeof(col_mate[0]));
-       unchosen_row = xcalloc(p->num_rows, sizeof(unchosen_row[0]));
-       row_dec      = xcalloc(p->num_rows, sizeof(row_dec[0]));
-       slack_row    = xcalloc(p->num_rows, sizeof(slack_row[0]));
+       col_mate     = XMALLOCNZ(int, p->num_rows);
+       unchosen_row = XMALLOCNZ(int, p->num_rows);
+       row_dec      = XMALLOCNZ(int, p->num_rows);
+       slack_row    = XMALLOCNZ(int, p->num_rows);
 
-       row_mate     = xcalloc(p->num_cols, sizeof(row_mate[0]));
-       parent_row   = xcalloc(p->num_cols, sizeof(parent_row[0]));
-       col_inc      = xcalloc(p->num_cols, sizeof(col_inc[0]));
-       slack        = xcalloc(p->num_cols, sizeof(slack[0]));
+       row_mate     = XMALLOCNZ(int, p->num_cols);
+       parent_row   = XMALLOCNZ(int, p->num_cols);
+       col_inc      = XMALLOCNZ(int, p->num_cols);
+       slack        = XMALLOCNZ(int, p->num_cols);
 
        memset(assignment, -1, m * sizeof(assignment[0]));
 
@@ -409,7 +412,10 @@ done:
 
        /* collect the assigned values */
        for (i = 0; i < m; ++i) {
-               assignment[i] = col_mate[i];
+               if (cost_threshold > 0 && p->cost[i][col_mate[i]] >= cost_threshold)
+                       assignment[i] = -1; /* remove matching having cost > threshold */
+               else
+                       assignment[i] = col_mate[i];
        }
 
        /* In case of normal matching: remove impossible ones */
@@ -443,5 +449,7 @@ done:
        xfree(unchosen_row);
        xfree(col_mate);
 
-       return cost;
+       *final_cost = cost;
+
+       return 0;
 }