Logo AND Algorithmique Numérique Distribuée

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