Logo AND Algorithmique Numérique Distribuée

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