X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/b637025b00d12fb4661df551d70b508bf17b8b90..0aae6c51e099a78ed3fc858bd8dceca62ca1e83c:/src/kernel/lmm/maxmin.cpp diff --git a/src/kernel/lmm/maxmin.cpp b/src/kernel/lmm/maxmin.cpp index 49affdfe07..7f5cdd186b 100644 --- a/src/kernel/lmm/maxmin.cpp +++ b/src/kernel/lmm/maxmin.cpp @@ -70,20 +70,15 @@ void s_lmm_system_t::check_concurrency() const for (s_lmm_constraint_t const& cnst : constraint_set) { int concurrency = 0; - void* elemIt; - xbt_swag_foreach(elemIt, &cnst.enabled_element_set) - { - lmm_element_t elem = (lmm_element_t)elemIt; - xbt_assert(elem->variable->sharing_weight > 0); - concurrency += elem->get_concurrency(); + for (s_lmm_element_t const& elem : cnst.enabled_element_set) { + xbt_assert(elem.variable->sharing_weight > 0); + concurrency += elem.get_concurrency(); } - xbt_swag_foreach(elemIt, &cnst.disabled_element_set) - { - lmm_element_t elem = (lmm_element_t)elemIt; + for (s_lmm_element_t const& elem : cnst.disabled_element_set) { // We should have staged variables only if concurrency is reached in some constraint - xbt_assert(cnst.get_concurrency_limit() < 0 || elem->variable->staged_weight == 0 || - elem->variable->get_min_concurrency_slack() < elem->variable->concurrency_share, + xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_weight == 0 || + elem.variable->get_min_concurrency_slack() < elem.variable->concurrency_share, "should not have staged variable!"); } @@ -97,17 +92,17 @@ void s_lmm_system_t::check_concurrency() const if (var.cnsts.empty()) continue; - const s_lmm_element_t* elem = &var.cnsts[0]; - int belong_to_enabled = xbt_swag_belongs(elem, &(elem->constraint->enabled_element_set)); - int belong_to_disabled = xbt_swag_belongs(elem, &(elem->constraint->disabled_element_set)); - int belong_to_active = xbt_swag_belongs(elem, &(elem->constraint->active_element_set)); + const s_lmm_element_t& elem = var.cnsts[0]; + int belong_to_enabled = elem.enabled_element_set_hook.is_linked(); + int belong_to_disabled = elem.disabled_element_set_hook.is_linked(); + int belong_to_active = elem.active_element_set_hook.is_linked(); - for (s_lmm_element_t const& elem : var.cnsts) { - xbt_assert(belong_to_enabled == xbt_swag_belongs(&elem, &(elem.constraint->enabled_element_set)), + for (s_lmm_element_t const& elem2 : var.cnsts) { + xbt_assert(belong_to_enabled == elem2.enabled_element_set_hook.is_linked(), "Variable inconsistency (1): enabled_element_set"); - xbt_assert(belong_to_disabled == xbt_swag_belongs(&elem, &(elem.constraint->disabled_element_set)), + xbt_assert(belong_to_disabled == elem2.disabled_element_set_hook.is_linked(), "Variable inconsistency (2): disabled_element_set"); - xbt_assert(belong_to_active == xbt_swag_belongs(&elem, &(elem.constraint->active_element_set)), + xbt_assert(belong_to_active == elem2.active_element_set_hook.is_linked(), "Variable inconsistency (3): active_element_set"); } } @@ -126,11 +121,19 @@ void s_lmm_system_t::var_free(lmm_variable_t var) for (s_lmm_element_t& elem : var->cnsts) { if (var->sharing_weight > 0) elem.decrease_concurrency(); - xbt_swag_remove(&elem, &(elem.constraint->enabled_element_set)); - xbt_swag_remove(&elem, &(elem.constraint->disabled_element_set)); - xbt_swag_remove(&elem, &(elem.constraint->active_element_set)); - int nelements = xbt_swag_size(&(elem.constraint->enabled_element_set)) + - xbt_swag_size(&(elem.constraint->disabled_element_set)); + if (elem.enabled_element_set_hook.is_linked()) { + auto& set = elem.constraint->enabled_element_set; + set.erase(set.iterator_to(elem)); + } + if (elem.disabled_element_set_hook.is_linked()) { + auto& set = elem.constraint->disabled_element_set; + set.erase(set.iterator_to(elem)); + } + if (elem.active_element_set_hook.is_linked()) { + auto& set = elem.constraint->active_element_set; + set.erase(set.iterator_to(elem)); + } + int nelements = elem.constraint->enabled_element_set.size() + elem.constraint->disabled_element_set.size(); if (nelements == 0) make_constraint_inactive(elem.constraint); else @@ -147,9 +150,6 @@ void s_lmm_system_t::var_free(lmm_variable_t var) s_lmm_system_t::s_lmm_system_t(bool selective_update) : selective_update_active(selective_update) { - s_lmm_variable_t var; - s_lmm_constraint_t cnst; - modified = false; visited_counter = 1; @@ -186,12 +186,7 @@ void s_lmm_system_t::cnst_free(lmm_constraint_t cnst) s_lmm_constraint_t::s_lmm_constraint_t(void* id_value, double bound_value) : bound(bound_value), id(id_value) { - s_lmm_element_t elem; - id_int = Global_debug_id++; - xbt_swag_init(&enabled_element_set, xbt_swag_offset(elem, enabled_element_set_hookup)); - xbt_swag_init(&disabled_element_set, xbt_swag_offset(elem, disabled_element_set_hookup)); - xbt_swag_init(&active_element_set, xbt_swag_offset(elem, active_element_set_hookup)); remaining = 0.0; usage = 0.0; @@ -253,7 +248,7 @@ void s_lmm_system_t::expand(lmm_constraint_t cnst, lmm_variable_t var, double co int current_share = 0; if (var->concurrency_share > 1) { for (s_lmm_element_t& elem : var->cnsts) { - if (elem.constraint == cnst && xbt_swag_belongs(&elem, &(elem.constraint->enabled_element_set))) + if (elem.constraint == cnst && elem.enabled_element_set_hook.is_linked()) current_share += elem.get_concurrency(); } } @@ -279,10 +274,10 @@ void s_lmm_system_t::expand(lmm_constraint_t cnst, lmm_variable_t var, double co elem.variable = var; if (var->sharing_weight) { - xbt_swag_insert_at_head(&elem, &(elem.constraint->enabled_element_set)); + elem.constraint->enabled_element_set.push_front(elem); elem.increase_concurrency(); } else - xbt_swag_insert_at_tail(&elem, &(elem.constraint->disabled_element_set)); + elem.constraint->disabled_element_set.push_back(elem); if (not selective_update_active) { make_constraint_active(cnst); @@ -340,18 +335,26 @@ lmm_variable_t s_lmm_constraint_t::get_variable(const_lmm_element_t* elem) const if (*elem == nullptr) { // That is the first call, pick the first element among enabled_element_set (or disabled_element_set if // enabled_element_set is empty) - *elem = (lmm_element_t)xbt_swag_getFirst(&enabled_element_set); - if (*elem == nullptr) - *elem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); + if (not enabled_element_set.empty()) + *elem = &enabled_element_set.front(); + else if (not disabled_element_set.empty()) + *elem = &disabled_element_set.front(); + else + *elem = nullptr; } else { // elem is not null, so we carry on - if (xbt_swag_belongs(*elem, &enabled_element_set)) { + if ((*elem)->enabled_element_set_hook.is_linked()) { // Look at enabled_element_set, and jump to disabled_element_set when finished - *elem = (lmm_element_t)xbt_swag_getNext(*elem, enabled_element_set.offset); - if (*elem == nullptr) - *elem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); + auto iter = std::next(enabled_element_set.iterator_to(**elem)); + if (iter != std::end(enabled_element_set)) + *elem = &*iter; + else if (not disabled_element_set.empty()) + *elem = &disabled_element_set.front(); + else + *elem = nullptr; } else { - *elem = (lmm_element_t)xbt_swag_getNext(*elem, disabled_element_set.offset); + auto iter = std::next(disabled_element_set.iterator_to(**elem)); + *elem = iter != std::end(disabled_element_set) ? &*iter : nullptr; } } if (*elem) @@ -360,16 +363,19 @@ lmm_variable_t s_lmm_constraint_t::get_variable(const_lmm_element_t* elem) const return nullptr; } -// if we modify the swag between calls, normal version may loop forever -// this safe version ensures that we browse the swag elements only once +// if we modify the list between calls, normal version may loop forever +// this safe version ensures that we browse the list elements only once lmm_variable_t s_lmm_constraint_t::get_variable_safe(const_lmm_element_t* elem, const_lmm_element_t* nextelem, int* numelem) const { if (*elem == nullptr) { - *elem = (lmm_element_t)xbt_swag_getFirst(&enabled_element_set); - *numelem = xbt_swag_size(&enabled_element_set) + xbt_swag_size(&disabled_element_set) - 1; - if (*elem == nullptr) - *elem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); + *numelem = enabled_element_set.size() + disabled_element_set.size() - 1; + if (not enabled_element_set.empty()) + *elem = &enabled_element_set.front(); + else if (not disabled_element_set.empty()) + *elem = &disabled_element_set.front(); + else + *elem = nullptr; } else { *elem = *nextelem; if (*numelem > 0) { @@ -379,13 +385,18 @@ lmm_variable_t s_lmm_constraint_t::get_variable_safe(const_lmm_element_t* elem, } if (*elem) { // elem is not null, so we carry on - if (xbt_swag_belongs(*elem, &enabled_element_set)) { + if ((*elem)->enabled_element_set_hook.is_linked()) { // Look at enabled_element_set, and jump to disabled_element_set when finished - *nextelem = (lmm_element_t)xbt_swag_getNext(*elem, enabled_element_set.offset); - if (*nextelem == nullptr) - *nextelem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); + auto iter = std::next(enabled_element_set.iterator_to(**elem)); + if (iter != std::end(enabled_element_set)) + *elem = &*iter; + else if (not disabled_element_set.empty()) + *elem = &disabled_element_set.front(); + else + *elem = nullptr; } else { - *nextelem = (lmm_element_t)xbt_swag_getNext(*elem, disabled_element_set.offset); + auto iter = std::next(disabled_element_set.iterator_to(**elem)); + *elem = iter != std::end(disabled_element_set) ? &*iter : nullptr; } return (*elem)->variable; } else @@ -412,32 +423,26 @@ static inline void saturated_variable_set_update(s_lmm_constraint_light_t* cnst_ /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate * (cnst_light_tab)*/ for (int const& saturated_cnst : saturated_constraints) { - lmm_constraint_light_t cnst = &cnst_light_tab[saturated_cnst]; - void* _elem; - xbt_swag_t elem_list = &(cnst->cnst->active_element_set); - xbt_swag_foreach(_elem, elem_list) - { - lmm_element_t elem = (lmm_element_t)_elem; + s_lmm_constraint_light_t& cnst = cnst_light_tab[saturated_cnst]; + for (s_lmm_element_t const& elem : cnst.cnst->active_element_set) { // Visiting active_element_set, so, by construction, should never get a zero weight, correct? - xbt_assert(elem->variable->sharing_weight > 0); - if (elem->consumption_weight > 0 && not elem->variable->saturated_variable_set_hook.is_linked()) - sys->saturated_variable_set.push_back(*elem->variable); + xbt_assert(elem.variable->sharing_weight > 0); + if (elem.consumption_weight > 0 && not elem.variable->saturated_variable_set_hook.is_linked()) + sys->saturated_variable_set.push_back(*elem.variable); } } } -static void format_lmm_element_swag(const_xbt_swag_t elem_list, int sharing_policy, double& sum, std::string& buf) +template +static void format_lmm_element_list(const ElemList& elem_list, int sharing_policy, double& sum, std::string& buf) { - void* _elem; - xbt_swag_foreach(_elem, elem_list) - { - lmm_element_t elem = (lmm_element_t)_elem; - buf += std::to_string(elem->consumption_weight) + ".'" + std::to_string(elem->variable->id_int) + "'(" + - std::to_string(elem->variable->value) + ")" + (sharing_policy ? " + " : " , "); + for (s_lmm_element_t const& elem : elem_list) { + buf += std::to_string(elem.consumption_weight) + ".'" + std::to_string(elem.variable->id_int) + "'(" + + std::to_string(elem.variable->value) + ")" + (sharing_policy ? " + " : " , "); if (sharing_policy) - sum += elem->consumption_weight * elem->variable->value; + sum += elem.consumption_weight * elem.variable->value; else - sum = std::max(sum, elem->consumption_weight * elem->variable->value); + sum = std::max(sum, elem.consumption_weight * elem.variable->value); } } @@ -459,9 +464,9 @@ void s_lmm_system_t::print() const // Show the enabled variables buf += "\t"; buf += cnst.sharing_policy ? "(" : "max("; - format_lmm_element_swag(&cnst.enabled_element_set, cnst.sharing_policy, sum, buf); + format_lmm_element_list(cnst.enabled_element_set, cnst.sharing_policy, sum, buf); // TODO: Adding disabled elements only for test compatibility, but do we really want them to be printed? - format_lmm_element_swag(&cnst.disabled_element_set, cnst.sharing_policy, sum, buf); + format_lmm_element_list(cnst.disabled_element_set, cnst.sharing_policy, sum, buf); buf += "0) <= " + std::to_string(cnst.bound) + " ('" + std::to_string(cnst.id_int) + "')"; @@ -504,19 +509,15 @@ void s_lmm_system_t::solve() template void s_lmm_system_t::solve(CnstList& cnst_list) { - void* _elem; double min_usage = -1; double min_bound = -1; XBT_DEBUG("Active constraints : %zu", cnst_list.size()); /* Init: Only modified code portions: reset the value of active variables */ for (s_lmm_constraint_t const& cnst : cnst_list) { - const_xbt_swag_t elem_list = &cnst.enabled_element_set; - xbt_swag_foreach(_elem, elem_list) - { - lmm_variable_t var = ((lmm_element_t)_elem)->variable; - xbt_assert(var->sharing_weight > 0.0); - var->value = 0.0; + for (s_lmm_element_t const& elem : cnst.enabled_element_set) { + xbt_assert(elem.variable->sharing_weight > 0.0); + elem.variable->value = 0.0; } } @@ -531,19 +532,16 @@ template void s_lmm_system_t::solve(CnstList& cnst_list) if (not double_positive(cnst.remaining, cnst.bound * sg_maxmin_precision)) continue; cnst.usage = 0; - xbt_swag_t elem_list = &cnst.enabled_element_set; - xbt_swag_foreach(_elem, elem_list) - { - lmm_element_t elem = (lmm_element_t)_elem; - xbt_assert(elem->variable->sharing_weight > 0); - if (elem->consumption_weight > 0) { + for (s_lmm_element_t& elem : cnst.enabled_element_set) { + xbt_assert(elem.variable->sharing_weight > 0); + if (elem.consumption_weight > 0) { if (cnst.sharing_policy) - cnst.usage += elem->consumption_weight / elem->variable->sharing_weight; - else if (cnst.usage < elem->consumption_weight / elem->variable->sharing_weight) - cnst.usage = elem->consumption_weight / elem->variable->sharing_weight; + cnst.usage += elem.consumption_weight / elem.variable->sharing_weight; + else if (cnst.usage < elem.consumption_weight / elem.variable->sharing_weight) + cnst.usage = elem.consumption_weight / elem.variable->sharing_weight; - elem->make_active(); - simgrid::surf::Action* action = static_cast(elem->variable->id); + elem.make_active(); + simgrid::surf::Action* action = static_cast(elem.variable->id); if (keep_track && not action->is_linked()) keep_track->push_back(*action); } @@ -558,7 +556,7 @@ template void s_lmm_system_t::solve(CnstList& cnst_list) cnst_light_tab[cnst_light_num].remaining_over_usage = cnst.remaining / cnst.usage; saturated_constraints_update(cnst_light_tab[cnst_light_num].remaining_over_usage, cnst_light_num, saturated_constraints, &min_usage); - xbt_assert(cnst.active_element_set.count > 0, + xbt_assert(not cnst.active_element_set.empty(), "There is no sense adding a constraint that has no active element!"); cnst_light_num++; } @@ -634,15 +632,12 @@ template void s_lmm_system_t::solve(CnstList& cnst_list) // Remember: non-shared constraints only require that max(elem.value * var.value) < cnst->bound cnst->usage = 0.0; elem.make_inactive(); - xbt_swag_t elem_list = &(cnst->enabled_element_set); - xbt_swag_foreach(_elem, elem_list) - { - lmm_element_t elem2 = static_cast(_elem); - xbt_assert(elem2->variable->sharing_weight > 0); - if (elem2->variable->value > 0) + for (s_lmm_element_t& elem2 : cnst->enabled_element_set) { + xbt_assert(elem2.variable->sharing_weight > 0); + if (elem2.variable->value > 0) continue; - if (elem2->consumption_weight > 0) - cnst->usage = std::max(cnst->usage, elem2->consumption_weight / elem2->variable->sharing_weight); + if (elem2.consumption_weight > 0) + cnst->usage = std::max(cnst->usage, elem2.consumption_weight / elem2.variable->sharing_weight); } // If the constraint is saturated, remove it from the set of active constraints (light_tab) if (not double_positive(cnst->usage, sg_maxmin_precision) || @@ -660,7 +655,7 @@ template void s_lmm_system_t::solve(CnstList& cnst_list) } } else { cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage; - xbt_assert(cnst->active_element_set.count > 0, + xbt_assert(not cnst->active_element_set.empty(), "Should not keep a maximum constraint that has no active" " element! You want to check the maxmin precision and possible rounding effects."); } @@ -675,7 +670,7 @@ template void s_lmm_system_t::solve(CnstList& cnst_list) saturated_constraints.clear(); int pos; for (pos = 0; pos < cnst_light_num; pos++) { - xbt_assert(cnst_light_tab[pos].cnst->active_element_set.count > 0, + xbt_assert(not cnst_light_tab[pos].cnst->active_element_set.empty(), "Cannot saturate more a constraint that has" " no active element! You may want to change the maxmin precision (--cfg=maxmin/precision:)" " because of possible rounding effects.\n\tFor the record, the usage of this constraint is %g while " @@ -778,8 +773,9 @@ void s_lmm_system_t::enable_var(lmm_variable_t var) variable_set.erase(variable_set.iterator_to(*var)); variable_set.push_front(*var); for (s_lmm_element_t& elem : var->cnsts) { - xbt_swag_remove(&elem, &(elem.constraint->disabled_element_set)); - xbt_swag_insert_at_head(&elem, &(elem.constraint->enabled_element_set)); + auto& set = elem.constraint->disabled_element_set; + set.erase(set.iterator_to(elem)); + elem.constraint->enabled_element_set.push_front(elem); elem.increase_concurrency(); } if (not var->cnsts.empty()) @@ -800,11 +796,13 @@ void s_lmm_system_t::disable_var(lmm_variable_t var) if (not var->cnsts.empty()) update_modified_set(var->cnsts[0].constraint); for (s_lmm_element_t& elem : var->cnsts) { - xbt_swag_remove(&elem, &(elem.constraint->enabled_element_set)); - xbt_swag_insert_at_tail(&elem, &(elem.constraint->disabled_element_set)); - - xbt_swag_remove(&elem, &(elem.constraint->active_element_set)); - + auto& set = elem.constraint->enabled_element_set; + set.erase(set.iterator_to(elem)); + elem.constraint->disabled_element_set.push_back(elem); + if (elem.active_element_set_hook.is_linked()) { + auto& set = elem.constraint->active_element_set; + set.erase(set.iterator_to(elem)); + } elem.decrease_concurrency(); } @@ -826,16 +824,22 @@ void s_lmm_system_t::on_disabled_var(lmm_constraint_t cnstr) if (cnstr->get_concurrency_limit() < 0) return; - int numelem = xbt_swag_size(&(cnstr->disabled_element_set)); + int numelem = cnstr->disabled_element_set.size(); if (not numelem) return; - lmm_element_t elem = (lmm_element_t)xbt_swag_getFirst(&(cnstr->disabled_element_set)); + lmm_element_t elem = &cnstr->disabled_element_set.front(); - // Cannot use xbt_swag_foreach, because lmm_enable_var will modify disabled_element_set.. within the loop + // Cannot use foreach loop, because lmm_enable_var will modify disabled_element_set.. within the loop while (numelem-- && elem) { - lmm_element_t nextelem = (lmm_element_t)xbt_swag_getNext(elem, cnstr->disabled_element_set.offset); + lmm_element_t nextelem; + if (elem->disabled_element_set_hook.is_linked()) { + auto iter = std::next(cnstr->disabled_element_set.iterator_to(*elem)); + nextelem = iter != std::end(cnstr->disabled_element_set) ? &*iter : nullptr; + } else { + nextelem = nullptr; + } if (elem->variable->staged_weight > 0 && elem->variable->can_enable()) { // Found a staged variable @@ -915,17 +919,14 @@ void s_lmm_system_t::update_constraint_bound(lmm_constraint_t cnst, double bound */ void s_lmm_system_t::update_modified_set_rec(lmm_constraint_t cnst) { - void* _elem; - - xbt_swag_foreach(_elem, &cnst->enabled_element_set) - { - lmm_variable_t var = ((lmm_element_t)_elem)->variable; - for (s_lmm_element_t const& elem : var->cnsts) { + for (s_lmm_element_t const& elem : cnst->enabled_element_set) { + lmm_variable_t var = elem.variable; + for (s_lmm_element_t const& elem2 : var->cnsts) { if (var->visited == visited_counter) break; - if (elem.constraint != cnst && not elem.constraint->modified_constraint_set_hook.is_linked()) { - modified_constraint_set.push_back(*elem.constraint); - update_modified_set_rec(elem.constraint); + if (elem2.constraint != cnst && not elem2.constraint->modified_constraint_set_hook.is_linked()) { + modified_constraint_set.push_back(*elem2.constraint); + update_modified_set_rec(elem2.constraint); } } // var will be ignored in later visits as long as sys->visited_counter does not move @@ -971,35 +972,22 @@ void s_lmm_system_t::remove_all_modified_set() double s_lmm_constraint_t::get_usage() const { double result = 0.0; - const_xbt_swag_t elem_list = &enabled_element_set; - void* _elem; - - xbt_swag_foreach(_elem, elem_list) - { - lmm_element_t elem = (lmm_element_t)_elem; - if (elem->consumption_weight > 0) { - if (sharing_policy) - result += elem->consumption_weight * elem->variable->value; - else if (result < elem->consumption_weight * elem->variable->value) - result = std::max(result, elem->consumption_weight * elem->variable->value); - } + if (sharing_policy) { + for (s_lmm_element_t const& elem : enabled_element_set) + if (elem.consumption_weight > 0) + result += elem.consumption_weight * elem.variable->value; + } else { + for (s_lmm_element_t const& elem : enabled_element_set) + if (elem.consumption_weight > 0) + result = std::max(result, elem.consumption_weight * elem.variable->value); } return result; } int s_lmm_constraint_t::get_variable_amount() const { - int result = 0; - const_xbt_swag_t elem_list = &enabled_element_set; - void* _elem; - - xbt_swag_foreach(_elem, elem_list) - { - lmm_element_t elem = (lmm_element_t)_elem; - if (elem->consumption_weight > 0) - result++; - } - return result; + return std::count_if(std::begin(enabled_element_set), std::end(enabled_element_set), + [](const s_lmm_element_t& elem) { return elem.consumption_weight > 0; }); } } }