Logo AND Algorithmique Numérique Distribuée

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