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 #include <stdlib.h>
   9 #include <stdio.h>
  10 #include <stdarg.h>
  11 #include <string.h>
  12 #include "lpp.h"
  13 #include "xmalloc.h"
  14 #include "assert.h"
  15 #include "hashptr.h"
  16 #include "set.h"
  17 #include "sp_matrix.h"
  18
  19 typedef struct _name_t name_t;
  20
  21 struct _name_t {
  22         const char *name;               /**< the name of the var/constraint supplied by user */
  23         int nr;                                 /**< the col/row number in the matrix */
  24         union _type {
  25                 var_t var_type;
  26                 cst_t cst_type;
  27         } type;
  28 };
  29
  30 struct _lpp_t {
  31         /* The problem data */
  32         char *name;                                             /**< A textual name for this problem */
  33         opt_t opt_type;                                 /**< Optimization direction */
  34         sp_matrix_t *m;                                 /**< The matrix holding objective and constraints */
  35         int rhs_size;                                   /**< Size of the rhs-array below */
  36         int *rhs;                                               /**< The right hand side vector */
  37
  38         /* Cst/Var to Nr mapping */
  39         set *cst2nr;                                    /**< Holds name_t's for constraints */
  40         set *var2nr;                                    /**< Holds name_t's for variables */
  41
  42         /* Nr to Cst/Var mapping */
  43         int cst_size, var_size;                 /**< Size of the csts/vars-arrays below */
  44         int cst_next, var_next;                 /**< Next free position in arrays below */
  45         name_t **csts;                                  /**< Pointers to the elements in the cst2nr set */
  46         name_t **vars;                                  /**< Pointers to the elements in the var2nr set */
  47 };
  48
  49 #define HASH_NAME_T(n) HASH_STR((n)->name, strlen((n)->name))
  50
  51 static int cmp_name_t(const void *x, const void *y, size_t size) {
  52         const name_t *n = x;
  53         const name_t *m = y;
  54         return strcmp(n->name, m->name);
  55 }
  56
  57 #define INITIAL_SIZE 64
  58
  59 lpp_t *new_lp(char *name, opt_t opt_type) {
  60         lpp_t *lpp = xcalloc(1, sizeof(*lpp));
  61         lpp->name = name;
  62         lpp->opt_type = opt_type;
  63         lpp->cst2nr = new_set(cmp_name_t, INITIAL_SIZE);
  64         lpp->var2nr = new_set(cmp_name_t, INITIAL_SIZE);
  65         lpp->cst_size = INITIAL_SIZE;
  66         lpp->csts = xcalloc(INITIAL_SIZE, sizeof(*lpp->csts));
  67         lpp->var_size = INITIAL_SIZE;
  68         lpp->vars = xcalloc(INITIAL_SIZE, sizeof(*lpp->vars));
  69         lpp->m = new_matrix(INITIAL_SIZE, INITIAL_SIZE);
  70         lpp->rhs_size = INITIAL_SIZE;
  71         lpp->rhs = xcalloc(INITIAL_SIZE, sizeof(*lpp->rhs));
  72         return lpp;
  73 }
  74
  75 void free_lp(lpp_t *lpp) {
  76         del_set(lpp->cst2nr);
  77         del_set(lpp->var2nr);
  78         del_matrix(lpp->m);
  79         free(lpp->csts);
  80         free(lpp->vars);
  81         free(lpp->rhs);
  82         free(lpp);
  83 }
  84
  85 void lpp_add_constr(lpp_t *lpp, const char *cst_name, cst_t cst_type) {
  86         name_t n, *inner;
  87         n.name = xstrdup(cst_name);
  88         n.nr = lpp->cst_next++;
  89         n.type.cst_type = cst_type;
  90         inner = set_insert(lpp->cst2nr, &n, sizeof(n), HASH_NAME_T(&n));
  91         assert(inner);
  92         if (lpp->cst_next == lpp->cst_size)
  93                 lpp->csts = xrealloc(lpp->csts, 2 * lpp->cst_size * sizeof(*lpp->csts));
  94         lpp->csts[lpp->cst_next++] = inner;
  95 }
  96
  97 void lpp_add_var(lpp_t *lpp, const char *var_name, var_t var_type) {
  98         name_t n, *inner;
  99         assert(var_type != invalid && "invalid is for internal use only");
 100         n.name = xstrdup(var_name);
 101         n.nr = lpp->var_next++;
 102         n.type.var_type = var_type;
 103         inner = set_insert(lpp->var2nr, &n, sizeof(n), HASH_NAME_T(&n));
 104         assert(inner);
 105         if (lpp->var_next == lpp->var_size)
 106                 lpp->vars = xrealloc(lpp->vars, 2 * lpp->var_size * sizeof(*lpp->vars));
 107         lpp->vars[lpp->var_next++] = inner;
 108 }
 109
 110 static INLINE int name2nr(set *where, const char *name) {
 111         name_t find, *found;
 112         find.name = name;
 113         found = set_find(where, &find, sizeof(find), HASH_NAME_T(&find));
 114         if (found)
 115                 return found->nr;
 116         else
 117                 return -1;
 118 }
 119
 120 #define cst_nr(lp, name) name2nr(lpp->cst2nr, name)
 121 #define var_nr(lp, name) name2nr(lpp->var2nr, name)
 122
 123 void lpp_set_factor(lpp_t *lpp, const char *cst_name, const char *var_name, int value) {
 124         int cst, var;
 125         cst = cst_nr(lp, cst_name);
 126         var = var_nr(lp, var_name);
 127         assert(cst != -1);
 128         assert(var != -1);
 129         matrix_set(lpp->m, cst, var, value);
 130 }
 131
 132 static INLINE void adjust_rhs_size(lpp_t *lpp) {
 133         if (lpp->cst_size > lpp->rhs_size) {
 134                 lpp->rhs_size = lpp->cst_size;
 135                 lpp->rhs = xrealloc(lpp->rhs, lpp->rhs_size);
 136         }
 137 }
 138
 139 void lpp_set_rhs(lpp_t *lpp, char *cst_name, int value) {
 140         int cst = cst_nr(lp, cst_name);
 141         assert(cst != -1);
 142         adjust_rhs_size(lpp);
 143         lpp->rhs[cst] = value;
 144 }
 145
 146 void lpp_set_all_constr(lpp_t *lpp, char *cst_name, char **var_names, int *values) {
 147         assert(0 && "NYI");
 148 }
 149
 150 /******************************************************************************
 151        MPS-STUFF
 152 ******************************************************************************/
 153
 154 static char *mps_cst_encoding[4] = {"N", "E", "L", "G"};
 155 typedef enum _mps_line_t {l_raw,
 156                                                   l_ind_name, l_ind_objs, l_ind_rows, l_ind_cols, l_ind_rhs, l_ind_end,
 157                                                   l_data_row, l_data_col1, l_data_col2, l_marker} mps_line_t;
 158
 159 static INLINE void mps_write_line(FILE *out, style_t style, mps_line_t line_type, ...) {
 160         va_list args;
 161         char *fmt = "";
 162
 163         assert(style == s_mps_fixed || style == s_mps_free);
 164         va_start(args, line_type);
 165
 166         if (style == s_mps_fixed) {
 167                 /* white spaces are important! */
 168                 switch (line_type) {
 169                         case l_raw:                     fmt = "%s\n"; break;
 170                         case l_ind_name:        fmt = "NAME          %s\n"; break;
 171                         case l_ind_objs:        fmt = "OBJSENSE\n"; break;
 172                         case l_ind_rows:        fmt = "ROWS\n"; break;
 173                         case l_ind_cols:        fmt = "COLUMNS\n"; break;
 174                         case l_ind_rhs:         fmt = "RHS\n"; break;
 175                         case l_ind_end:         fmt = "ENDATA\n"; break;
 176                         case l_data_row:        fmt = " %-2s %-8s\n"; break; /* Field 1-2 */
 177                         case l_data_col1:       fmt = "    %-8s  %-8s  %12d\n"; break; /* Field 2-4 */
 178                         case l_data_col2:       fmt = "    %-8s  %-8s  %12d   %-8s  %12d\n"; break; /* Field 2-6 */
 179                         case l_marker:          fmt = "    M%-7d  'MARKER'                 '%s'\n"; break; /* Field 2,3,5 */
 180                         default: assert(0);
 181                 }
 182         } else {
 183                 switch (line_type) {
 184                         case l_raw:                     fmt = "%s\n"; break;
 185                         case l_ind_name:        fmt = "NAME %s\n"; break;
 186                         case l_ind_objs:        fmt = "OBJSENSE\n"; break;
 187                         case l_ind_rows:        fmt = "ROWS\n"; break;
 188                         case l_ind_cols:        fmt = "COLUMNS\n"; break;
 189                         case l_ind_rhs:         fmt = "RHS\n"; break;
 190                         case l_ind_end:         fmt = "ENDATA\n"; break;
 191                         case l_data_row:        fmt = " %s\t%s\n"; break;
 192                         case l_data_col1:       fmt = " %s\t%s\t%d\n"; break;
 193                         case l_data_col2:       fmt = " %s\t%s\t%d\t%s\t%d\n"; break;
 194                         case l_marker:          fmt = " M%d\t'MARKER'\t'%s'\n"; break;
 195                         default: assert(0);
 196                 }
 197         }
 198
 199         vfprintf(out, fmt, args);
 200         va_end(args);
 201 }
 202
 203 static INLINE int mps_insert_markers(FILE *out, style_t style, var_t curr, var_t last, int marker_nr) {
 204         assert(style == s_mps_fixed || style == s_mps_free);
 205         if (last != curr) {
 206                 /* print end-marker for last */
 207                 if (last == binary)
 208                         mps_write_line(out, style, l_marker, marker_nr++, "INTEND");
 209
 210                 /* print begin-marker for curr */
 211                 if (curr == binary)
 212                         mps_write_line(out, style, l_marker, marker_nr++, "INTORG");
 213         }
 214         return marker_nr;
 215 }
 216
 217 static void lpp_dump_mps(lpp_t *lpp, FILE *out, style_t style) {
 218         int i, count, marker_nr = 0;
 219         const name_t *curr;
 220         var_t last_type;
 221         assert(style == s_mps_fixed || style == s_mps_free);
 222
 223         /* NAME */
 224         mps_write_line(out, style, l_ind_name, lpp->name);
 225
 226         /* OBJSENSE */
 227         mps_write_line(out, style, l_ind_objs);
 228         if (lpp->opt_type == maximize)
 229                 mps_write_line(out, style, l_raw, " MAX");
 230
 231         /* ROWS */
 232         mps_write_line(out, style, l_ind_rows);
 233         for(i=0; i<lpp->cst_next; ++i) {
 234                 curr = lpp->csts[i];
 235                 mps_write_line(out, style, l_data_row, mps_cst_encoding[curr->type.cst_type], curr->name);
 236         }
 237
 238         /* COLUMNS */
 239         mps_write_line(out, style, l_ind_cols);
 240         last_type = invalid;
 241         for(i=0; i<lpp->var_next; ++i) {
 242                 const matrix_elem_t *elem, *before = NULL;
 243                 curr = lpp->vars[i];
 244
 245                 /* markers */
 246                 marker_nr = mps_insert_markers(out, style, last_type, curr->type.var_type, marker_nr);
 247                 last_type = curr->type.var_type;
 248
 249                 /* participation in constraints */
 250                 count = 0;
 251                 matrix_foreach_in_col(lpp->m, curr->nr, elem) {
 252                         if (count == 0) {
 253                                 before = elem;
 254                                 count = 1;
 255                         } else {
 256                                 mps_write_line(out, style, l_data_col2, curr->name, lpp->csts[before->row]->name, before->val, lpp->csts[elem->row]->name, elem->val);
 257                                 count = 0;
 258                         }
 259                 }
 260                 if (count == 1)
 261                         mps_write_line(out, style, l_data_col1, curr->name, lpp->csts[before->row]->name, before->val);
 262         }
 263         mps_insert_markers(out, style, last_type, invalid, marker_nr); /* potential end-marker */
 264
 265         /* RHS */
 266         mps_write_line(out, style, l_ind_rhs);
 267         for(i=0; i<lpp->rhs_size/2; ++i)
 268                 mps_write_line(out, style, l_data_col2, "rhs", lpp->csts[2*i]->name, lpp->rhs[2*i], lpp->csts[2*i+1]->name, lpp->rhs[2*i+1]);
 269         if ((lpp->rhs_size & 1) == 1)
 270                 mps_write_line(out, style, l_data_col1, "rhs", lpp->csts[lpp->rhs_size-1]->name, lpp->rhs[lpp->rhs_size-1]);
 271
 272         /* ENDATA */
 273         mps_write_line(out, style, l_ind_end);
 274 }
 275
 276 /******************************************************************************
 277        LP-STUFF
 278 ******************************************************************************/
 279
 280 static void lpp_dump_lp(lpp_t *lpp, FILE *out) {
 281         assert(0 && "NYI");
 282 }
 283
 284 void lpp_dump(lpp_t *lpp, FILE *out, style_t style) {
 285         adjust_rhs_size(lpp);
 286         switch (style) {
 287                 case s_mps_fixed:
 288                 case s_mps_free:        lpp_dump_mps(lpp, out, style); break;
 289                 case s_lp:                      lpp_dump_lp(lpp, out); break;
 290                 default: assert(0);
 291         }
 292 }