Logo AND Algorithmique Numérique Distribuée

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