src/surf/maxmin.c

   1 /* Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7
   8 #include "xbt/sysdep.h"
   9 #include "xbt/log.h"
  10 #include "xbt/mallocator.h"
  11 #include "maxmin_private.h"
  12 #include <stdlib.h>
  13 #include <stdio.h>              /* sprintf */
  14 #include <math.h>
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf,
  16                                 "Logging specific to SURF (maxmin)");
  17
  18 static void *lmm_variable_mallocator_new_f(void);
  19 static void lmm_variable_mallocator_free_f(void *var);
  20 static void lmm_variable_mallocator_reset_f(void *var);
  21 static void lmm_update_modified_set(lmm_system_t sys, lmm_constraint_t cnst);
  22 static void lmm_remove_all_modified_set(lmm_system_t sys);
  23 int sg_maxmin_selective_update = 1;
  24 static int Global_debug_id = 1;
  25 static int Global_const_debug_id = 1;
  26 lmm_system_t lmm_system_new(void)
  27 {
  28   lmm_system_t l = NULL;
  29   s_lmm_variable_t var;
  30   s_lmm_constraint_t cnst;
  31
  32   l = xbt_new0(s_lmm_system_t, 1);
  33
  34   l->modified = 0;
  35   l->selective_update_active = sg_maxmin_selective_update;
  36
  37   DEBUG1("Setting selective_update_active flag to %d\n",
  38          l->selective_update_active);
  39
  40   xbt_swag_init(&(l->variable_set),
  41                 xbt_swag_offset(var, variable_set_hookup));
  42   xbt_swag_init(&(l->constraint_set),
  43                 xbt_swag_offset(cnst, constraint_set_hookup));
  44
  45   xbt_swag_init(&(l->active_constraint_set),
  46                 xbt_swag_offset(cnst, active_constraint_set_hookup));
  47
  48   xbt_swag_init(&(l->modified_constraint_set),
  49                 xbt_swag_offset(cnst, modified_constraint_set_hookup));
  50   xbt_swag_init(&(l->saturated_variable_set),
  51                 xbt_swag_offset(var, saturated_variable_set_hookup));
  52   xbt_swag_init(&(l->saturated_constraint_set),
  53                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
  54
  55   l->variable_mallocator = xbt_mallocator_new(64,
  56                                               lmm_variable_mallocator_new_f,
  57                                               lmm_variable_mallocator_free_f,
  58                                               lmm_variable_mallocator_reset_f);
  59
  60   return l;
  61 }
  62
  63 void lmm_system_free(lmm_system_t sys)
  64 {
  65   lmm_variable_t var = NULL;
  66   lmm_constraint_t cnst = NULL;
  67
  68   while ((var = extract_variable(sys))) {
  69     WARN2("Variable %p (%d) still in LMM system when freing it: this may be a bug",
  70         var,var->id_int);
  71     lmm_var_free(sys, var);
  72   }
  73
  74   while ((cnst = extract_constraint(sys)))
  75     lmm_cnst_free(sys, cnst);
  76
  77   xbt_mallocator_free(sys->variable_mallocator);
  78   free(sys);
  79 }
  80
  81 XBT_INLINE void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var)
  82 {
  83   int i;
  84   lmm_element_t elem = NULL;
  85
  86   XBT_IN2("(sys=%p, var=%p)", sys, var);
  87   sys->modified = 1;
  88
  89   for (i = 0; i < var->cnsts_number; i++) {
  90     elem = &var->cnsts[i];
  91     xbt_swag_remove(elem, &(elem->constraint->element_set));
  92     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
  93     if (!xbt_swag_size(&(elem->constraint->element_set)))
  94       make_constraint_inactive(sys, elem->constraint);
  95     else
  96       lmm_update_modified_set(sys, elem->constraint);
  97   }
  98   var->cnsts_number = 0;
  99   XBT_OUT;
 100 }
 101
 102 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
 103 {
 104
 105   lmm_variable_disable(sys, var);
 106   free(var->cnsts);
 107   xbt_mallocator_release(sys->variable_mallocator, var);
 108 }
 109
 110 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst)
 111 {
 112 /*   xbt_assert0(xbt_swag_size(&(cnst->element_set)), */
 113 /*            "This list should be empty!"); */
 114   remove_active_constraint(sys, cnst);
 115   free(cnst);
 116 }
 117
 118 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
 119                                     double bound_value)
 120 {
 121   lmm_constraint_t cnst = NULL;
 122   s_lmm_element_t elem;
 123
 124   cnst = xbt_new0(s_lmm_constraint_t, 1);
 125   cnst->id = id;
 126   cnst->id_int = Global_const_debug_id++;
 127   xbt_swag_init(&(cnst->element_set),
 128                 xbt_swag_offset(elem, element_set_hookup));
 129   xbt_swag_init(&(cnst->active_element_set),
 130                 xbt_swag_offset(elem, active_element_set_hookup));
 131
 132   cnst->bound = bound_value;
 133   cnst->usage = 0;
 134   cnst->shared = 1;
 135   insert_constraint(sys, cnst);
 136
 137   return cnst;
 138 }
 139
 140 XBT_INLINE void lmm_constraint_shared(lmm_constraint_t cnst)
 141 {
 142   cnst->shared = 0;
 143 }
 144
 145 XBT_INLINE int lmm_constraint_is_shared(lmm_constraint_t cnst)
 146 {
 147   return (cnst->shared);
 148 }
 149
 150 XBT_INLINE void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst)
 151 {
 152   remove_constraint(sys, cnst);
 153   lmm_cnst_free(sys, cnst);
 154 }
 155
 156 static void *lmm_variable_mallocator_new_f(void)
 157 {
 158   return xbt_new(s_lmm_variable_t, 1);
 159 }
 160
 161 static void lmm_variable_mallocator_free_f(void *var)
 162 {
 163   xbt_free(var);
 164 }
 165
 166 static void lmm_variable_mallocator_reset_f(void *var)
 167 {
 168   /* memset to zero like calloc */
 169   memset(var, 0, sizeof(s_lmm_variable_t));
 170 }
 171
 172 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
 173                                 double weight,
 174                                 double bound, int number_of_constraints)
 175 {
 176   lmm_variable_t var = NULL;
 177   int i;
 178
 179   XBT_IN5("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)",
 180           sys, id, weight, bound, number_of_constraints);
 181
 182   var = xbt_mallocator_get(sys->variable_mallocator);
 183   var->id = id;
 184   var->id_int = Global_debug_id++;
 185   var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints);
 186   for (i = 0; i < number_of_constraints; i++) {
 187     /* Should be useless because of the
 188        calloc but it seems to help valgrind... */
 189     var->cnsts[i].element_set_hookup.next = NULL;
 190     var->cnsts[i].element_set_hookup.prev = NULL;
 191     var->cnsts[i].active_element_set_hookup.next = NULL;
 192     var->cnsts[i].active_element_set_hookup.prev = NULL;
 193     var->cnsts[i].constraint = NULL;
 194     var->cnsts[i].variable = NULL;
 195     var->cnsts[i].value = 0.0;
 196   }
 197   var->cnsts_size = number_of_constraints;
 198   var->cnsts_number = 0;        /* Should be useless because of the
 199                                    calloc but it seems to help valgrind... */
 200   var->weight = weight;
 201   var->bound = bound;
 202   var->value = 0.0;
 203
 204
 205   var->func_f = func_f_def;
 206   var->func_fp = func_fp_def;
 207   var->func_fpi = func_fpi_def;
 208
 209   if (weight)
 210     xbt_swag_insert_at_head(var, &(sys->variable_set));
 211   else
 212     xbt_swag_insert_at_tail(var, &(sys->variable_set));
 213   XBT_OUT;
 214   return var;
 215 }
 216
 217 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
 218 {
 219   remove_variable(sys, var);
 220   lmm_var_free(sys, var);
 221 }
 222
 223 XBT_INLINE double lmm_variable_getvalue(lmm_variable_t var)
 224 {
 225   return (var->value);
 226 }
 227
 228 XBT_INLINE double lmm_variable_getbound(lmm_variable_t var)
 229 {
 230   return (var->bound);
 231 }
 232
 233 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
 234                 lmm_variable_t var, double value)
 235 {
 236   lmm_element_t elem = NULL;
 237
 238   sys->modified = 1;
 239
 240   xbt_assert0(var->cnsts_number < var->cnsts_size, "Too much constraints");
 241
 242   elem = &(var->cnsts[var->cnsts_number++]);
 243
 244   elem->value = value;
 245   elem->constraint = cnst;
 246   elem->variable = var;
 247
 248   if (var->weight)
 249     xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
 250   else
 251     xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
 252
 253   make_constraint_active(sys, cnst);
 254   lmm_update_modified_set(sys, cnst);
 255 }
 256
 257 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
 258                     lmm_variable_t var, double value)
 259 {
 260   int i;
 261   sys->modified = 1;
 262
 263   for (i = 0; i < var->cnsts_number; i++)
 264     if (var->cnsts[i].constraint == cnst)
 265       break;
 266
 267   if (i < var->cnsts_number) {
 268     if (cnst->shared)
 269       var->cnsts[i].value += value;
 270     else
 271       var->cnsts[i].value = MAX(var->cnsts[i].value, value);
 272     lmm_update_modified_set(sys, cnst);
 273   } else
 274     lmm_expand(sys, cnst, var, value);
 275 }
 276
 277 void lmm_elem_set_value(lmm_system_t sys, lmm_constraint_t cnst,
 278                         lmm_variable_t var, double value)
 279 {
 280   int i;
 281
 282   for (i = 0; i < var->cnsts_number; i++)
 283     if (var->cnsts[i].constraint == cnst)
 284       break;
 285
 286   if (i < var->cnsts_number) {
 287     var->cnsts[i].value = value;
 288     sys->modified = 1;
 289     lmm_update_modified_set(sys, cnst);
 290   } else
 291     DIE_IMPOSSIBLE;
 292 }
 293
 294 XBT_INLINE lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys,
 295                                        lmm_variable_t var, int num)
 296 {
 297   if (num < var->cnsts_number)
 298     return (var->cnsts[num].constraint);
 299   else
 300     return NULL;
 301 }
 302
 303 XBT_INLINE int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var)
 304 {
 305   return (var->cnsts_number);
 306 }
 307
 308 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys,
 309                                      lmm_constraint_t cnst,
 310                                      lmm_element_t * elem)
 311 {
 312   if (!(*elem))
 313     *elem = xbt_swag_getFirst(&(cnst->element_set));
 314   else
 315     *elem = xbt_swag_getNext(*elem, cnst->element_set.offset);
 316   if (*elem)
 317     return (*elem)->variable;
 318   else
 319     return NULL;
 320 }
 321
 322 XBT_INLINE void *lmm_constraint_id(lmm_constraint_t cnst)
 323 {
 324   return cnst->id;
 325 }
 326
 327 XBT_INLINE void *lmm_variable_id(lmm_variable_t var)
 328 {
 329   return var->id;
 330 }
 331
 332 static XBT_INLINE void saturated_constraint_set_update(lmm_system_t sys,
 333                                             lmm_constraint_t cnst,
 334                                             double *min_usage)
 335 {
 336   lmm_constraint_t useless_cnst = NULL;
 337
 338   XBT_IN3("sys=%p, cnst=%p, min_usage=%f", sys, cnst, *min_usage);
 339   if (cnst->usage <= 0) {
 340     XBT_OUT;
 341     return;
 342   }
 343   if (cnst->remaining <= 0) {
 344     XBT_OUT;
 345     return;
 346   }
 347   if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) {
 348     *min_usage = cnst->remaining / cnst->usage;
 349     LOG3(xbt_log_priority_trace,
 350          "min_usage=%f (cnst->remaining=%f, cnst->usage=%f)", *min_usage,
 351          cnst->remaining, cnst->usage);
 352     while ((useless_cnst =
 353             xbt_swag_getFirst(&(sys->saturated_constraint_set))))
 354       xbt_swag_remove(useless_cnst, &(sys->saturated_constraint_set));
 355
 356     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
 357   } else if (*min_usage == cnst->remaining / cnst->usage) {
 358     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
 359   }
 360   XBT_OUT;
 361 }
 362
 363 static XBT_INLINE void saturated_variable_set_update(lmm_system_t sys)
 364 {
 365   lmm_constraint_t cnst = NULL;
 366   xbt_swag_t cnst_list = NULL;
 367   lmm_element_t elem = NULL;
 368   xbt_swag_t elem_list = NULL;
 369
 370   cnst_list = &(sys->saturated_constraint_set);
 371   while ((cnst = xbt_swag_getFirst(cnst_list))) {
 372     elem_list = &(cnst->active_element_set);
 373     xbt_swag_foreach(elem, elem_list) {
 374       if (elem->variable->weight <= 0)
 375         break;
 376       if ((elem->value > 0))
 377         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
 378     }
 379     xbt_swag_remove(cnst, cnst_list);
 380   }
 381 }
 382
 383 void lmm_print(lmm_system_t sys)
 384 {
 385   lmm_constraint_t cnst = NULL;
 386   lmm_element_t elem = NULL;
 387   lmm_variable_t var = NULL;
 388   xbt_swag_t cnst_list = NULL;
 389   xbt_swag_t var_list = NULL;
 390   xbt_swag_t elem_list = NULL;
 391   char print_buf[1024];
 392   char *trace_buf = xbt_malloc0(sizeof(char));
 393   double sum = 0.0;
 394
 395   /* Printing Objective */
 396   var_list = &(sys->variable_set);
 397   sprintf(print_buf, "MAX-MIN ( ");
 398   trace_buf =
 399     xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 400   strcat(trace_buf, print_buf);
 401   xbt_swag_foreach(var, var_list) {
 402     sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight);
 403     trace_buf =
 404       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 405     strcat(trace_buf, print_buf);
 406   }
 407   sprintf(print_buf, ")");
 408   trace_buf =
 409     xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 410   strcat(trace_buf, print_buf);
 411   fprintf(stderr, "%s", trace_buf);
 412   //DEBUG1("%20s", trace_buf); FIXME
 413   trace_buf[0] = '\000';
 414
 415   DEBUG0("Constraints");
 416   /* Printing Constraints */
 417   cnst_list = &(sys->active_constraint_set);
 418   xbt_swag_foreach(cnst, cnst_list) {
 419     sum = 0.0;
 420     elem_list = &(cnst->element_set);
 421     sprintf(print_buf, "\t");
 422     trace_buf =
 423       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 424     strcat(trace_buf, print_buf);
 425     xbt_swag_foreach(elem, elem_list) {
 426       sprintf(print_buf, "%f.'%d'(%f) + ", elem->value,
 427               elem->variable->id_int, elem->variable->value);
 428       trace_buf =
 429         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 430       strcat(trace_buf, print_buf);
 431       sum += elem->value * elem->variable->value;
 432     }
 433     sprintf(print_buf, "0 <= %f ('%d')", cnst->bound, cnst->id_int);
 434     trace_buf =
 435       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 436     strcat(trace_buf, print_buf);
 437
 438     if (!cnst->shared) {
 439       sprintf(print_buf, " [MAX-Constraint]");
 440       trace_buf =
 441         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 442       strcat(trace_buf, print_buf);
 443     }
 444     //   DEBUG1("%s", trace_buf);
 445     fprintf(stderr, "%s", trace_buf);
 446     trace_buf[0] = '\000';
 447     xbt_assert3(!double_positive(sum - cnst->bound),
 448                 "Incorrect value (%f is not smaller than %f): %g",
 449                 sum, cnst->bound, sum - cnst->bound);
 450   }
 451
 452   DEBUG0("Variables");
 453   /* Printing Result */
 454   xbt_swag_foreach(var, var_list) {
 455     if (var->bound > 0) {
 456       DEBUG4("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value,
 457              var->bound);
 458       xbt_assert2(!double_positive(var->value - var->bound),
 459                   "Incorrect value (%f is not smaller than %f",
 460                   var->value, var->bound);
 461     } else {
 462       DEBUG3("'%d'(%f) : %f", var->id_int, var->weight, var->value);
 463     }
 464   }
 465
 466   free(trace_buf);
 467 }
 468
 469 void lmm_solve(lmm_system_t sys)
 470 {
 471   lmm_variable_t var = NULL;
 472   lmm_constraint_t cnst = NULL;
 473   lmm_element_t elem = NULL;
 474   xbt_swag_t cnst_list = NULL;
 475   xbt_swag_t var_list = NULL;
 476   xbt_swag_t elem_list = NULL;
 477   double min_usage = -1;
 478   double min_bound = -1;
 479
 480   if (!(sys->modified))
 481     return;
 482
 483   /*
 484    * Compute Usage and store the variables that reach the maximum.
 485    */
 486   cnst_list = sys->selective_update_active ? &(sys->modified_constraint_set) :
 487     &(sys->active_constraint_set);
 488
 489   DEBUG1("Active constraints : %d", xbt_swag_size(cnst_list));
 490   /* Init: Only modified code portions */
 491   xbt_swag_foreach(cnst, cnst_list) {
 492     elem_list = &(cnst->element_set);
 493     //DEBUG1("Variable set : %d", xbt_swag_size(elem_list));
 494     xbt_swag_foreach(elem, elem_list) {
 495       var = elem->variable;
 496       if (var->weight <= 0.0)
 497         break;
 498       var->value = 0.0;
 499     }
 500   }
 501
 502   DEBUG1("Active constraints : %d", xbt_swag_size(cnst_list));
 503   xbt_swag_foreach(cnst, cnst_list) {
 504     /* INIT */
 505     cnst->remaining = cnst->bound;
 506     if (cnst->remaining == 0)
 507       continue;
 508     cnst->usage = 0;
 509     elem_list = &(cnst->element_set);
 510     xbt_swag_foreach(elem, elem_list) {
 511       /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */
 512       if (elem->variable->weight <= 0)
 513         break;
 514       if ((elem->value > 0)) {
 515         if (cnst->shared)
 516           cnst->usage += elem->value / elem->variable->weight;
 517         else if (cnst->usage < elem->value / elem->variable->weight)
 518           cnst->usage = elem->value / elem->variable->weight;
 519
 520         make_elem_active(elem);
 521       }
 522     }
 523     DEBUG2("Constraint Usage %d : %f", cnst->id_int, cnst->usage);
 524     /* Saturated constraints update */
 525     saturated_constraint_set_update(sys, cnst, &min_usage);
 526   }
 527   saturated_variable_set_update(sys);
 528
 529   /* Saturated variables update */
 530
 531   do {
 532     /* Fix the variables that have to be */
 533     var_list = &(sys->saturated_variable_set);
 534
 535     xbt_swag_foreach(var, var_list) {
 536       if (var->weight <= 0.0)
 537         DIE_IMPOSSIBLE;
 538       /* First check if some of these variables have reach their upper
 539          bound and update min_usage accordingly. */
 540       DEBUG5
 541         ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f",
 542          var->id_int, var->bound, var->weight, min_usage,
 543          var->bound * var->weight);
 544       if ((var->bound > 0) && (var->bound * var->weight < min_usage)) {
 545         if (min_bound < 0)
 546           min_bound = var->bound;
 547         else
 548           min_bound = MIN(min_bound, var->bound);
 549         DEBUG1("Updated min_bound=%f", min_bound);
 550       }
 551     }
 552
 553
 554     while ((var = xbt_swag_getFirst(var_list))) {
 555       int i;
 556
 557       if (min_bound < 0) {
 558         var->value = min_usage / var->weight;
 559       } else {
 560         if (min_bound == var->bound)
 561           var->value = var->bound;
 562         else {
 563           xbt_swag_remove(var, var_list);
 564           continue;
 565         }
 566       }
 567       DEBUG5("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ",
 568              min_usage, var->id_int, var->weight, var->id_int, var->value);
 569
 570
 571       /* Update usage */
 572
 573       for (i = 0; i < var->cnsts_number; i++) {
 574         elem = &var->cnsts[i];
 575         cnst = elem->constraint;
 576         if (cnst->shared) {
 577           double_update(&(cnst->remaining), elem->value * var->value);
 578           double_update(&(cnst->usage), elem->value / var->weight);
 579           make_elem_inactive(elem);
 580         } else {                /* FIXME one day: We recompute usage.... :( */
 581           cnst->usage = 0.0;
 582           make_elem_inactive(elem);
 583           elem_list = &(cnst->element_set);
 584           xbt_swag_foreach(elem, elem_list) {
 585             if (elem->variable->weight <= 0)
 586               break;
 587             if (elem->variable->value > 0)
 588               break;
 589             if ((elem->value > 0)) {
 590               cnst->usage=MAX(cnst->usage,elem->value / elem->variable->weight);
 591               DEBUG2("Constraint Usage %d : %f", cnst->id_int, cnst->usage);
 592               make_elem_active(elem);
 593             }
 594           }
 595         }
 596       }
 597       xbt_swag_remove(var, var_list);
 598     }
 599
 600     /* Find out which variables reach the maximum */
 601     cnst_list =
 602       sys->selective_update_active ? &(sys->modified_constraint_set) :
 603       &(sys->active_constraint_set);
 604     min_usage = -1;
 605     min_bound = -1;
 606     xbt_swag_foreach(cnst, cnst_list) {
 607       saturated_constraint_set_update(sys, cnst, &min_usage);
 608     }
 609     saturated_variable_set_update(sys);
 610
 611   } while (xbt_swag_size(&(sys->saturated_variable_set)));
 612
 613   sys->modified = 0;
 614   if (sys->selective_update_active)
 615     lmm_remove_all_modified_set(sys);
 616
 617   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
 618     lmm_print(sys);
 619   }
 620 }
 621
 622 /* Not a O(1) function */
 623
 624 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
 625                 lmm_variable_t var, double value)
 626 {
 627   int i;
 628
 629   for (i = 0; i < var->cnsts_number; i++)
 630     if (var->cnsts[i].constraint == cnst) {
 631       var->cnsts[i].value = value;
 632       sys->modified = 1;
 633       lmm_update_modified_set(sys, cnst);
 634       return;
 635     }
 636 }
 637
 638 /** \brief Attribute the value bound to var->bound.
 639  *
 640  *  \param sys the lmm_system_t
 641  *  \param var the lmm_variable_t
 642  *  \param bound the new bound to associate with var
 643  *
 644  *  Makes var->bound equal to bound. Whenever this function is called
 645  *  a change is  signed in the system. To
 646  *  avoid false system changing detection it is a good idea to test
 647  *  (bound != 0) before calling it.
 648  *
 649  */
 650 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
 651                                double bound)
 652 {
 653   int i;
 654
 655   sys->modified = 1;
 656   var->bound = bound;
 657
 658   for (i = 0; i < var->cnsts_number; i++)
 659     lmm_update_modified_set(sys, var->cnsts[i].constraint);
 660
 661 }
 662
 663
 664 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
 665                                 double weight)
 666 {
 667   int i;
 668   lmm_element_t elem;
 669
 670   if (weight == var->weight)
 671     return;
 672   XBT_IN3("(sys=%p, var=%p, weight=%f)", sys, var, weight);
 673   sys->modified = 1;
 674   var->weight = weight;
 675   xbt_swag_remove(var, &(sys->variable_set));
 676   if (weight)
 677     xbt_swag_insert_at_head(var, &(sys->variable_set));
 678   else
 679     xbt_swag_insert_at_tail(var, &(sys->variable_set));
 680
 681   for (i = 0; i < var->cnsts_number; i++) {
 682     elem = &var->cnsts[i];
 683     xbt_swag_remove(elem, &(elem->constraint->element_set));
 684     if (weight)
 685       xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
 686     else
 687       xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
 688
 689     lmm_update_modified_set(sys, elem->constraint);
 690   }
 691   if (!weight)
 692     var->value = 0.0;
 693
 694   XBT_OUT;
 695 }
 696
 697 XBT_INLINE double lmm_get_variable_weight(lmm_variable_t var)
 698 {
 699   return var->weight;
 700 }
 701
 702 XBT_INLINE void lmm_update_constraint_bound(lmm_system_t sys, lmm_constraint_t cnst,
 703                                  double bound)
 704 {
 705   sys->modified = 1;
 706   lmm_update_modified_set(sys, cnst);
 707   cnst->bound = bound;
 708 }
 709
 710 XBT_INLINE int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
 711 {
 712   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
 713 }
 714
 715 XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys)
 716 {
 717   return xbt_swag_getFirst(&(sys->active_constraint_set));
 718 }
 719
 720 XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys,
 721                                                 lmm_constraint_t cnst)
 722 {
 723   return xbt_swag_getNext(cnst, (sys->active_constraint_set).offset);
 724 }
 725
 726 /** \brief Update the constraint set propagating recursively to
 727  *  other constraints so the system should not be entirely computed.
 728  *
 729  *  \param sys the lmm_system_t
 730  *  \param cnst the lmm_constraint_t affected by the change
 731  *
 732  *  A recursive algorithm to optimize the system recalculation selecting only
 733  *  constraints that have changed. Each constraint change is propagated
 734  *  to the list of constraints for each variable.
 735  */
 736 static void lmm_update_modified_set(lmm_system_t sys, lmm_constraint_t cnst)
 737 {
 738   lmm_element_t elem = NULL;
 739   lmm_variable_t var = NULL;
 740   xbt_swag_t elem_list = NULL;
 741   int i;
 742
 743   /* return if selective update isn't active */
 744   if (!sys->selective_update_active)
 745     return;
 746
 747   //DEBUG1("Updating modified constraint set with constraint %d", cnst->id_int);
 748
 749   if (xbt_swag_belongs(cnst, &(sys->modified_constraint_set)))
 750     return;
 751
 752   //DEBUG1("Inserting into modified constraint set %d", cnst->id_int);
 753
 754   /* add to modified set */
 755   xbt_swag_insert(cnst, &(sys->modified_constraint_set));
 756
 757   elem_list = &(cnst->element_set);
 758   xbt_swag_foreach(elem, elem_list) {
 759     var = elem->variable;
 760     for (i = 0; i < var->cnsts_number; i++)
 761       if (cnst != var->cnsts[i].constraint) {
 762         //DEBUG2("Updating modified %d calling for %d", cnst->id_int, var->cnsts[i].constraint->id_int);
 763         lmm_update_modified_set(sys, var->cnsts[i].constraint);
 764       }
 765   }
 766 }
 767
 768 /** \brief Remove all constraints of the modified_constraint_set.
 769  *
 770  *  \param sys the lmm_system_t
 771  */
 772 static void lmm_remove_all_modified_set(lmm_system_t sys)
 773 {
 774   lmm_element_t elem = NULL;
 775   lmm_element_t elem_next = NULL;
 776   xbt_swag_t elem_list = NULL;
 777
 778   elem_list = &(sys->modified_constraint_set);
 779   xbt_swag_foreach_safe(elem, elem_next, elem_list) {
 780     xbt_swag_remove(elem, elem_list);
 781   }
 782 }