nsz Git - libfirm/blob - ir/be/lpp.c

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                Fri 13.05.2005
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  */
   7
   8 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #ifdef HAVE_IO_H
  13 #include <io.h>
  14 #endif
  15
  16 #include <stdlib.h>
  17 #include <stdio.h>
  18 #include <string.h>
  19
  20 #include "xmalloc.h"
  21 #include "debug.h"
  22 #include "assert.h"
  23 #include "hashptr.h"
  24 #include "mps.h"
  25 #include "lpp.h"
  26
  27 #define DEBUG_LVL SET_LEVEL_1
  28 static firm_dbg_module_t *dbg = NULL;
  29
  30 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
  31
  32 static int cmp_name_t(const void *x, const void *y, size_t size) {
  33         const name_t *n = x;
  34         const name_t *m = y;
  35         return strcmp(n->name, m->name);
  36 }
  37
  38 #define INITIAL_SIZE 64
  39
  40 lpp_t *new_lpp(const char *name, opt_t opt_type) {
  41         lpp_t *lpp;
  42
  43         dbg = firm_dbg_register("ir.be.lpp");
  44         firm_dbg_set_mask(dbg, DEBUG_LVL);
  45
  46         lpp = xcalloc(1, sizeof(*lpp));
  47         lpp->name = xstrdup(name);
  48         lpp->opt_type = opt_type;
  49         lpp->cst2nr = new_set(cmp_name_t, INITIAL_SIZE);
  50         lpp->var2nr = new_set(cmp_name_t, INITIAL_SIZE);
  51         lpp->cst_size = INITIAL_SIZE;
  52         lpp->var_size = INITIAL_SIZE;
  53         lpp->csts = xcalloc(INITIAL_SIZE, sizeof(*lpp->csts));
  54         lpp->vars = xcalloc(INITIAL_SIZE, sizeof(*lpp->vars));
  55         lpp->m = new_matrix(INITIAL_SIZE, INITIAL_SIZE);
  56         lpp_add_cst(lpp, "obj", objective, 0);
  57         lpp_add_var(lpp, "rhs", rhs, 0);
  58         return lpp;
  59 }
  60
  61 void free_lpp(lpp_t *lpp) {
  62         int i;
  63         for(i=0;i<lpp->cst_next;++i)
  64                 free(lpp->csts[i]->name);
  65         for(i=0;i<lpp->var_next;++i)
  66                 free(lpp->vars[i]->name);
  67         del_set(lpp->cst2nr);
  68         del_set(lpp->var2nr);
  69         del_matrix(lpp->m);
  70         free(lpp->name);
  71         free(lpp->csts);
  72         free(lpp->vars);
  73         if (lpp->error)
  74                 free(lpp->error);
  75         free(lpp);
  76 }
  77
  78 static INLINE int name2nr(set *where, char *name) {
  79         name_t find, *found;
  80         find.name = name;
  81         found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
  82         return (found ? found->nr : -1);
  83 }
  84
  85 #define cst_nr(lpp, name) name2nr(lpp->cst2nr, name)
  86 #define var_nr(lpp, name) name2nr(lpp->var2nr, name)
  87
  88 static INLINE char *get_next_name(lpp_t *lpp) {
  89         char *res = xmalloc(12);
  90         snprintf(res, 12, "_%d", lpp->next_name_number++);
  91         return res;
  92 }
  93
  94 int lpp_add_cst(lpp_t *lpp, char *cst_name, cst_t cst_type, double rhs) {
  95         name_t n, *inner;
  96         DBG((dbg, LEVEL_2, "%s %d %g\n", cst_name, cst_type, rhs));
  97         if (cst_name && cst_name[0] == '_')
  98                 return ERR_NAME_NOT_ALLOWED;
  99         if (cst_name)
 100                 n.name = xstrdup(cst_name);
 101         else
 102                 n.name = get_next_name(lpp);
 103         n.nr = -1;
 104         inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
 105         assert(inner);
 106
 107         if (inner->nr == -1) {
 108                 inner->nr = lpp->cst_next;
 109                 inner->type.cst_type = cst_type;
 110                 if (lpp->cst_next == lpp->cst_size) {
 111                         lpp->cst_size *= 2;
 112                         lpp->csts = xrealloc(lpp->csts, lpp->cst_size * sizeof(*lpp->csts));
 113                 }
 114                 lpp->csts[lpp->cst_next] = inner;
 115                 lpp->cst_next++;
 116                 matrix_set(lpp->m, inner->nr, 0, rhs);
 117         }
 118
 119         return inner->nr;
 120 }
 121
 122 int lpp_get_cst_idx(lpp_t *lpp, char *cst_name) {
 123         DBG((dbg, LEVEL_2, "%s --> %d\n", cst_name, cst_nr(lpp, cst_name)));
 124         return cst_nr(lpp, cst_name);
 125 }
 126
 127 void lpp_get_cst_name(lpp_t *lpp, int index, char *buf, size_t buf_size) {
 128         DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->csts[index]->name));
 129         strncpy(buf, lpp->csts[index]->name, buf_size);
 130 }
 131
 132 int lpp_add_var(lpp_t *lpp, char *var_name, var_t var_type, double obj) {
 133         name_t n, *inner;
 134         DBG((dbg, LEVEL_2, "%s %d %g\n", var_name, var_type, obj));
 135         assert(var_type != invalid && "invalid is for internal use only");
 136         if (var_name && var_name[0] == '_')
 137                 return ERR_NAME_NOT_ALLOWED;
 138         if (var_name)
 139                 n.name = xstrdup(var_name);
 140         else
 141                 n.name = get_next_name(lpp);
 142         n.nr = -1;
 143         inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
 144         assert(inner);
 145
 146         if (inner->nr == -1) {
 147                 inner->nr = lpp->var_next;
 148                 inner->value_kind = 0;
 149                 inner->value = 0;
 150                 inner->type.var_type = var_type;
 151                 if (lpp->var_next == lpp->var_size) {
 152                         lpp->var_size *= 2;
 153                         lpp->vars = xrealloc(lpp->vars, lpp->var_size * sizeof(*lpp->vars));
 154                 }
 155                 lpp->vars[lpp->var_next] = inner;
 156                 lpp->var_next++;
 157                 matrix_set(lpp->m, 0, inner->nr, obj);
 158         }
 159
 160         return inner->nr;
 161 }
 162
 163 int lpp_get_var_idx(lpp_t *lpp, char *var_name) {
 164         DBG((dbg, LEVEL_2, "%s --> %d\n", var_name, var_nr(lpp, var_name)));
 165         return var_nr(lpp, var_name);
 166 }
 167
 168 void lpp_get_var_name(lpp_t *lpp, int index, char *buf, size_t buf_size) {
 169         DBG((dbg, LEVEL_2, "%d --> %s\n", index, lpp->vars[index]->name));
 170         strncpy(buf, lpp->vars[index]->name, buf_size);
 171 }
 172
 173 int lpp_set_factor(lpp_t *lpp, char *cst_name, char *var_name, double value) {
 174         int cst, var;
 175
 176         cst = cst_nr(lpp, cst_name);
 177         var = var_nr(lpp, var_name);
 178         assert(cst != -1 && var != -1);
 179         DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", cst_name, cst, var_name, var, value));
 180         matrix_set(lpp->m, cst, var, value);
 181         return 0;
 182 }
 183
 184 int lpp_set_factor_fast(lpp_t *lpp, int cst_idx, int var_idx, double value) {
 185         assert(cst_idx >= 0 && var_idx >= 0);
 186         assert(cst_idx < lpp->cst_next && var_idx < lpp->var_next);
 187         DBG((dbg, LEVEL_2, "%s[%d] %s[%d] %g\n", lpp->csts[cst_idx]->name, cst_idx, lpp->vars[var_idx]->name, var_idx, value));
 188         matrix_set(lpp->m, cst_idx, var_idx, value);
 189         return 0;
 190 }
 191
 192 void lpp_set_start_value(lpp_t *lpp, int var_idx, double value) {
 193         assert(var_idx > 0 && var_idx < lpp->var_next);
 194         DBG((dbg, LEVEL_2, "%d %s %g\n", var_idx, lpp->vars[var_idx]->name, value));
 195         lpp->vars[var_idx]->value = value;
 196         lpp->vars[var_idx]->value_kind = value_start;
 197 }
 198
 199 sol_state_t lpp_get_solution(lpp_t *lpp, double *values, int begin, int end) {
 200         int i;
 201         if (lpp->sol_state < feasible)
 202                 return lpp->sol_state;
 203         /* here we are feasible or optimal */
 204         for (i=0; i<end-begin+1; ++i)
 205                 values[i] = lpp->vars[begin+i]->value;
 206         return lpp->sol_state;
 207 }
 208
 209 void lpp_dump(lpp_t *lpp, const char *filename) {
 210         FILE *out = fopen(filename, "wt");
 211         mps_write_mps(lpp, s_mps_fixed, out);
 212         fclose(out);
 213 }