Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Bugfix... I had forgotten to reorder elements when updating a variable weight (and...
[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/error.h"
11 #include "maxmin_private.h"
12 #include <stdlib.h>
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(maxmin, surf,
14                                 "Logging specific to the SURF maxmin module");
15
16 lmm_system_t lmm_system_new(void)
17 {
18   lmm_system_t l = NULL;
19   s_lmm_variable_t var;
20   s_lmm_constraint_t cnst;
21
22   l = xbt_new0(s_lmm_system_t, 1);
23
24   l->modified = 0;
25   xbt_swag_init(&(l->variable_set),
26                 xbt_swag_offset(var, variable_set_hookup));
27   xbt_swag_init(&(l->constraint_set),
28                 xbt_swag_offset(cnst, constraint_set_hookup));
29
30   xbt_swag_init(&(l->active_constraint_set),
31                 xbt_swag_offset(cnst, active_constraint_set_hookup));
32
33   xbt_swag_init(&(l->saturated_variable_set),
34                 xbt_swag_offset(var, saturated_variable_set_hookup));
35   xbt_swag_init(&(l->saturated_constraint_set),
36                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
37
38   return l;
39 }
40
41 void lmm_system_free(lmm_system_t sys)
42 {
43   lmm_variable_t var = NULL;
44   lmm_constraint_t cnst = NULL;
45
46   while ((var = extract_variable(sys)))
47     lmm_var_free(sys, var);
48
49   while ((cnst = extract_constraint(sys)))
50     lmm_cnst_free(sys, cnst);
51
52   xbt_free(sys);
53 }
54
55 void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var)
56 {
57   int i;
58   lmm_element_t elem = NULL;
59
60   sys->modified = 1;
61
62   for (i = 0; i < var->cnsts_number; i++) {
63     elem = &var->cnsts[i];
64     xbt_swag_remove(elem, &(elem->constraint->element_set));
65     if (!xbt_swag_size(&(elem->constraint->element_set)))
66       make_constraint_inactive(sys, elem->constraint);
67   }
68   var->cnsts_number = 0;
69 }
70
71 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
72 {
73
74   lmm_variable_disable(sys, var);
75
76   xbt_free(var->cnsts);
77   xbt_free(var);
78 }
79
80 static void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst)
81 {
82 /*   xbt_assert0(xbt_swag_size(&(cnst->element_set)), */
83 /*            "This list should be empty!"); */
84   remove_active_constraint(sys, cnst);
85   xbt_free(cnst);
86 }
87
88 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
89                                     double bound_value)
90 {
91   lmm_constraint_t cnst = NULL;
92   s_lmm_element_t elem;
93
94   cnst = xbt_new0(s_lmm_constraint_t, 1);
95   cnst->id = id;
96   xbt_swag_init(&(cnst->element_set),
97                 xbt_swag_offset(elem, element_set_hookup));
98   xbt_swag_init(&(cnst->active_element_set),
99                 xbt_swag_offset(elem, active_element_set_hookup));
100
101   cnst->bound = bound_value;
102   cnst->usage = 0;
103   insert_constraint(sys, cnst);
104
105   return cnst;
106 }
107
108 void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst)
109 {
110   remove_constraint(sys, cnst);
111   lmm_cnst_free(sys, cnst);
112 }
113
114 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
115                                 double weight,
116                                 double bound, int number_of_constraints)
117 {
118   lmm_variable_t var = NULL;
119
120   var = xbt_new0(s_lmm_variable_t, 1);
121   var->id = id;
122   var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints);
123   var->cnsts_size = number_of_constraints;
124   /* var->cnsts_number = 0; *//* Useless because of the calloc  */
125   var->weight = weight;
126   var->bound = bound;
127   var->value = 0.0;
128   if(weight) xbt_swag_insert_at_head(var,&(sys->variable_set));
129   else xbt_swag_insert_at_tail(var,&(sys->variable_set));
130
131   return var;
132 }
133
134 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
135 {
136   remove_variable(sys, var);
137   lmm_var_free(sys, var);
138 }
139
140 double lmm_variable_getvalue(lmm_variable_t var)
141 {
142   return (var->value);
143 }
144
145 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
146                 lmm_variable_t var, double value)
147 {
148   lmm_element_t elem = NULL;
149
150   sys->modified = 1;
151
152   xbt_assert0(var->cnsts_number < var->cnsts_size,
153               "Too much constraints");
154
155   elem = &(var->cnsts[var->cnsts_number++]);
156
157   elem->value = value;
158   elem->constraint = cnst;
159   elem->variable = var;
160
161   if(var->weight) xbt_swag_insert_at_head(elem,&(elem->constraint->element_set));
162   else xbt_swag_insert_at_tail(elem,&(elem->constraint->element_set));
163
164   make_constraint_active(sys, cnst);
165 }
166
167 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys,
168                                        lmm_variable_t var, int num)
169 {
170   if (num < var->cnsts_number)
171     return (var->cnsts[num].constraint);
172   else
173     return NULL;
174 }
175
176 int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var)
177 {
178   return (var->cnsts_number);
179 }
180
181 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys,
182                                      lmm_constraint_t cnst,
183                                      lmm_variable_t * var)
184 {
185   if (!(*var))
186     xbt_swag_getFirst(&(cnst->element_set));
187   else
188     *var = xbt_swag_getNext(*var, cnst->element_set.offset);
189   return *var;
190 }
191
192 void *lmm_constraint_id(lmm_constraint_t cnst)
193 {
194   return cnst->id;
195 }
196
197 void *lmm_variable_id(lmm_variable_t var)
198 {
199   return var->id;
200 }
201
202 static void saturated_constraint_set_update(lmm_system_t sys,
203                                             lmm_constraint_t cnst,
204                                             double *min_usage)
205 {
206   lmm_constraint_t useless_cnst = NULL;
207
208   if (cnst->usage <= 0)
209     return;
210   if (cnst->remaining <= 0)
211     return;
212   if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) {
213     *min_usage = cnst->remaining / cnst->usage;
214
215     while ((useless_cnst =
216             xbt_swag_getFirst(&(sys->saturated_constraint_set))))
217       xbt_swag_remove(useless_cnst, &(sys->saturated_constraint_set));
218
219     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
220   } else if (*min_usage == cnst->remaining / cnst->usage) {
221     xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
222   }
223 }
224
225 static void saturated_variable_set_update(lmm_system_t sys)
226 {
227   lmm_constraint_t cnst = NULL;
228   xbt_swag_t cnst_list = NULL;
229   lmm_element_t elem = NULL;
230   xbt_swag_t elem_list = NULL;
231
232   cnst_list = &(sys->saturated_constraint_set);
233   while ((cnst = xbt_swag_getFirst(cnst_list))) {
234     elem_list = &(cnst->active_element_set);
235     xbt_swag_foreach(elem, elem_list) {
236       if(elem->variable->weight<=0) break;
237       if ((elem->value > 0))
238         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
239     }
240     xbt_swag_remove(cnst, cnst_list);
241   }
242
243 }
244
245 void lmm_solve(lmm_system_t sys)
246 {
247   lmm_variable_t var = NULL;
248   lmm_constraint_t cnst = NULL;
249   lmm_element_t elem = NULL;
250   xbt_swag_t cnst_list = NULL;
251   xbt_swag_t var_list = NULL;
252   xbt_swag_t elem_list = NULL;
253   double min_usage = -1;
254
255   if (!(sys->modified))
256     return;
257
258   /* Init */
259   var_list = &(sys->variable_set);
260   xbt_swag_foreach(var, var_list) {
261     var->value = 0.0;
262   }
263
264
265   /* Compute Usage and store the variables that reach the maximum */
266
267   cnst_list = &(sys->active_constraint_set);
268   xbt_swag_foreach(cnst, cnst_list) {
269     /* INIT */
270     elem_list = &(cnst->element_set);
271     cnst->remaining = cnst->bound;
272     cnst->usage = 0;
273     xbt_swag_foreach(elem, elem_list) {
274       if(elem->variable->weight <=0) break;
275       if ((elem->value > 0)) {
276         cnst->usage += elem->value / elem->variable->weight;
277         insert_active_elem_in_constraint(elem);
278       }
279     }
280
281     /* Saturated constraints update */
282     saturated_constraint_set_update(sys, cnst, &min_usage);
283   }
284
285   saturated_variable_set_update(sys);
286
287   /* Saturated variables update */
288
289   do {
290     /* Fix the variables that have to be */
291     var_list = &(sys->saturated_variable_set);
292
293
294     xbt_swag_foreach(var, var_list) {
295       /* First check if some of these variables have reach their upper
296          bound and update min_usage accordingly. */
297       if ((var->bound > 0) && (var->bound / var->weight < min_usage)) {
298         min_usage = var->bound / var->weight;
299       }
300     }
301
302
303     while ((var = xbt_swag_getFirst(var_list))) {
304       int i;
305
306       var->value = min_usage / var->weight;
307
308       /* Update usage */
309
310       for (i = 0; i < var->cnsts_number; i++) {
311         elem = &var->cnsts[i];
312         cnst = elem->constraint;
313         cnst->remaining -= elem->value * var->value;
314         cnst->usage -= elem->value / var->weight;
315         remove_active_elem_in_constraint(elem);
316       }
317       xbt_swag_remove(var, var_list);
318     }
319
320     /* Find out which variables reach the maximum */
321     cnst_list = &(sys->active_constraint_set);
322     min_usage = -1;
323     xbt_swag_foreach(cnst, cnst_list) {
324       saturated_constraint_set_update(sys, cnst, &min_usage);
325     }
326     saturated_variable_set_update(sys);
327
328   } while (xbt_swag_size(&(sys->saturated_variable_set)));
329
330   sys->modified = 0;
331 }
332
333 /* Not a O(1) function */
334
335 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
336                 lmm_variable_t var, double value)
337 {
338   int i;
339
340   sys->modified = 1;
341   for (i = 0; i < var->cnsts_number; i++)
342     if (var->cnsts[i].constraint == cnst) {
343       var->cnsts[i].value = value;
344       return;
345     }
346 }
347
348 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
349                                double bound)
350 {
351   sys->modified = 1;
352   var->bound = bound;
353 }
354
355 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
356                                 double weight)
357 {
358   int i ;
359   lmm_element_t elem;
360
361   sys->modified = 1;
362   var->weight = weight;
363   xbt_swag_remove(var,&(sys->variable_set));
364   if(weight) xbt_swag_insert_at_head(var,&(sys->variable_set));
365   else xbt_swag_insert_at_tail(var,&(sys->variable_set));
366
367   for (i = 0; i < var->cnsts_number; i++) {
368     elem = &var->cnsts[i];
369     xbt_swag_remove(elem, &(elem->constraint->element_set));
370     if(weight) xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
371     else xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
372   }
373 }
374
375 double lmm_get_variable_weight(lmm_variable_t var)
376                                   
377 {
378   return var->weight;
379 }
380
381 void lmm_update_constraint_bound(lmm_system_t sys, lmm_constraint_t cnst,
382                                  double bound)
383 {
384   sys->modified = 1;
385   cnst->bound = bound;
386 }
387
388 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
389 {
390   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
391 }
392
393 lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys)
394 {
395   return xbt_swag_getFirst(&(sys->active_constraint_set));
396 }
397
398 lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint_t cnst)
399 {
400   return xbt_swag_getNext(cnst,(sys->active_constraint_set).offset);
401 }
402
403
404 /* void lmm_print(lmm_system_t sys) */
405 /* { */
406 /*   lmm_variable_t var = NULL; */
407 /*   lmm_constraint_t cnst = NULL; */
408 /*   lmm_element_t elem = NULL; */
409 /*   xbt_swag_t cnst_list = NULL; */
410 /*   xbt_swag_t var_list = NULL; */
411 /*   xbt_swag_t elem_list = NULL; */
412
413 /*   var_list = &(sys->variable_set); */
414 /*   xbt_swag_foreach(var, var_list) { */
415 /*     printf("%s : {\n",var->id); */
416 /*     printf("\t %s : {\n",var->id); */
417 /*   } */
418 /* } */