Logo AND Algorithmique Numérique Distribuée

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