3 /* Copyright (c) 2004 Arnaud Legrand. All rights reserved. */
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. */
9 #include "xbt/sysdep.h"
10 #include "xbt/error.h"
11 #include "maxmin_private.h"
14 lmm_system_t lmm_system_new(void)
16 lmm_system_t l = NULL;
18 s_lmm_constraint_t cnst;
20 l = xbt_new0(s_lmm_system_t, 1);
23 xbt_swag_init(&(l->variable_set),
24 xbt_swag_offset(var, variable_set_hookup));
25 xbt_swag_init(&(l->constraint_set),
26 xbt_swag_offset(cnst, constraint_set_hookup));
28 xbt_swag_init(&(l->active_constraint_set),
29 xbt_swag_offset(cnst, active_constraint_set_hookup));
31 xbt_swag_init(&(l->saturated_variable_set),
32 xbt_swag_offset(var, saturated_variable_set_hookup));
33 xbt_swag_init(&(l->saturated_constraint_set),
34 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
39 void lmm_system_free(lmm_system_t sys)
41 lmm_variable_t var = NULL;
42 lmm_constraint_t cnst = NULL;
44 while ((var = extract_variable(sys)))
45 lmm_var_free(sys, var);
47 while ((cnst = extract_constraint(sys)))
48 lmm_cnst_free(sys, cnst);
53 void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var)
56 lmm_element_t elem = NULL;
60 for (i = 0; i < var->cnsts_number; i++) {
61 elem = &var->cnsts[i];
62 xbt_swag_remove(elem, &(elem->constraint->element_set));
63 if (xbt_swag_size(&(elem->constraint->element_set)))
64 make_constraint_inactive(sys, elem->constraint);
66 var->cnsts_number = 0;
69 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
72 lmm_variable_disable(sys, var);
78 static void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst)
80 /* xbt_assert0(xbt_fifo_size(&(cnst->row)), */
81 /* "This list should be empty!"); */
82 remove_active_constraint(sys, cnst);
86 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
89 lmm_constraint_t cnst = NULL;
92 cnst = xbt_new0(s_lmm_constraint_t, 1);
94 xbt_swag_init(&(cnst->element_set),
95 xbt_swag_offset(elem, element_set_hookup));
96 xbt_swag_init(&(cnst->active_element_set),
97 xbt_swag_offset(elem, active_element_set_hookup));
99 cnst->bound = bound_value;
101 insert_constraint(sys, cnst);
106 void lmm_constraint_free(lmm_system_t sys, lmm_constraint_t cnst)
108 remove_constraint(sys, cnst);
109 lmm_cnst_free(sys, cnst);
112 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
114 double bound, int number_of_constraints)
116 lmm_variable_t var = NULL;
118 var = xbt_new0(s_lmm_variable_t, 1);
120 var->cnsts = xbt_new0(s_lmm_element_t, number_of_constraints);
121 var->cnsts_size = number_of_constraints;
122 /* var->cnsts_number = 0; *//* Useless because of the calloc */
123 var->weight = weight;
126 insert_variable(sys, var);
131 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
133 remove_variable(sys, var);
134 lmm_var_free(sys, var);
137 double lmm_variable_getvalue(lmm_variable_t var)
142 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
143 lmm_variable_t var, double value)
145 lmm_element_t elem = NULL;
149 if (var->cnsts_number >= var->cnsts_size)
152 elem = &(var->cnsts[var->cnsts_number++]);
155 elem->constraint = cnst;
156 elem->variable = var;
158 insert_elem_in_constraint(elem);
160 make_constraint_active(sys, cnst);
163 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t sys,
164 lmm_variable_t var, int num)
166 if (num < var->cnsts_number)
167 return (var->cnsts[num].constraint);
172 int lmm_get_number_of_cnst_from_var(lmm_system_t sys, lmm_variable_t var)
174 return (var->cnsts_number);
177 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t sys,
178 lmm_constraint_t cnst,
179 lmm_variable_t * var)
182 xbt_swag_getFirst(&(cnst->element_set));
184 *var = xbt_swag_getNext(*var, cnst->element_set.offset);
188 void *lmm_constraint_id(lmm_constraint_t cnst)
193 void *lmm_variable_id(lmm_variable_t var)
198 static void saturated_constraint_set_update(lmm_system_t sys,
199 lmm_constraint_t cnst,
202 lmm_constraint_t useless_cnst = NULL;
204 if (cnst->usage <= 0)
206 if (cnst->remaining <= 0)
208 if ((*min_usage < 0) || (*min_usage > cnst->remaining / cnst->usage)) {
209 *min_usage = cnst->remaining / cnst->usage;
211 while ((useless_cnst =
212 xbt_swag_getFirst(&(sys->saturated_constraint_set))))
213 xbt_swag_remove(useless_cnst, &(sys->saturated_constraint_set));
215 xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
216 } else if (*min_usage == cnst->remaining / cnst->usage) {
217 xbt_swag_insert(cnst, &(sys->saturated_constraint_set));
221 static void saturated_variable_set_update(lmm_system_t sys)
223 lmm_constraint_t cnst = NULL;
224 xbt_swag_t cnst_list = NULL;
225 lmm_element_t elem = NULL;
226 xbt_swag_t elem_list = NULL;
228 cnst_list = &(sys->saturated_constraint_set);
229 while ((cnst = xbt_swag_getFirst(cnst_list))) {
230 elem_list = &(cnst->active_element_set);
231 xbt_swag_foreach(elem, elem_list)
232 if ((elem->value > 0) && (elem->variable->weight > 0))
233 xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
234 xbt_swag_remove(cnst, cnst_list);
239 void lmm_solve(lmm_system_t sys)
241 lmm_variable_t var = NULL;
242 lmm_constraint_t cnst = NULL;
243 lmm_element_t elem = NULL;
244 xbt_swag_t cnst_list = NULL;
245 xbt_swag_t var_list = NULL;
246 xbt_swag_t elem_list = NULL;
247 double min_usage = -1;
249 if (!(sys->modified))
253 var_list = &(sys->variable_set);
254 xbt_swag_foreach(var, var_list) {
259 /* Compute Usage and store the variables that reach the maximum */
261 cnst_list = &(sys->active_constraint_set);
262 xbt_swag_foreach(cnst, cnst_list) {
264 elem_list = &(cnst->element_set);
265 cnst->remaining = cnst->bound;
267 xbt_swag_foreach(elem, elem_list) {
268 if ((elem->value > 0) && (elem->variable->weight > 0)) {
269 cnst->usage += elem->value / elem->variable->weight;
270 insert_active_elem_in_constraint(elem);
274 /* Saturated constraints update */
275 saturated_constraint_set_update(sys, cnst, &min_usage);
278 saturated_variable_set_update(sys);
280 /* Saturated variables update */
283 /* Fix the variables that have to be */
284 var_list = &(sys->saturated_variable_set);
287 xbt_swag_foreach(var, var_list) {
288 /* First check if some of these variables have reach their upper
289 bound and update min_usage accordingly. */
290 if ((var->bound > 0) && (var->bound / var->weight < min_usage)) {
291 min_usage = var->bound / var->weight;
296 while ((var = xbt_swag_getFirst(var_list))) {
299 var->value = min_usage / var->weight;
303 for (i = 0; i < var->cnsts_number; i++) {
304 elem = &var->cnsts[i];
305 cnst = elem->constraint;
306 cnst->remaining -= elem->value * var->value;
307 cnst->usage -= elem->value / var->weight;
308 remove_active_elem_in_constraint(elem);
310 xbt_swag_remove(var, var_list);
313 /* Find out which variables reach the maximum */
314 cnst_list = &(sys->active_constraint_set);
316 xbt_swag_foreach(cnst, cnst_list) {
317 saturated_constraint_set_update(sys, cnst, &min_usage);
319 saturated_variable_set_update(sys);
321 } while (xbt_swag_size(&(sys->saturated_variable_set)));
326 /* Not a O(1) function */
328 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
329 lmm_variable_t var, double value)
334 for (i = 0; i < var->cnsts_number; i++)
335 if (var->cnsts[i].constraint == cnst) {
336 var->cnsts[i].value = value;
341 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
348 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
352 var->weight = weight;
355 void lmm_update_constraint_bound(lmm_system_t sys, lmm_constraint_t cnst,
362 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
364 return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
368 /* void lmm_print(lmm_system_t sys) */
370 /* lmm_variable_t var = NULL; */
371 /* lmm_constraint_t cnst = NULL; */
372 /* lmm_element_t elem = NULL; */
373 /* xbt_swag_t cnst_list = NULL; */
374 /* xbt_swag_t var_list = NULL; */
375 /* xbt_swag_t elem_list = NULL; */
377 /* var_list = &(sys->variable_set); */
378 /* xbt_swag_foreach(var, var_list) { */
379 /* printf("%s : {\n",var->id); */
380 /* printf("\t %s : {\n",var->id); */