From: Arnaud Giersch Date: Thu, 30 Nov 2017 17:07:39 +0000 (+0100) Subject: Use boost::intrusive::list instead of swags of s_lmm_constraint_t. X-Git-Tag: v3.18~197^2~5 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/ddbd28f29ffd7e177e74346e029bcf0dbfea7dbc?ds=sidebyside Use boost::intrusive::list instead of swags of s_lmm_constraint_t. --- diff --git a/src/kernel/lmm/fair_bottleneck.cpp b/src/kernel/lmm/fair_bottleneck.cpp index 66ce8dcb34..88c0625603 100644 --- a/src/kernel/lmm/fair_bottleneck.cpp +++ b/src/kernel/lmm/fair_bottleneck.cpp @@ -21,13 +21,9 @@ void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys) { void* _var; void* _var_next; - void* _cnst; - void* _cnst_next; void* _elem; lmm_variable_t var = nullptr; - lmm_constraint_t cnst = nullptr; lmm_element_t elem = nullptr; - xbt_swag_t cnst_list = nullptr; xbt_swag_t var_list = nullptr; xbt_swag_t elem_list = nullptr; @@ -53,19 +49,13 @@ void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys) } var_list = &(sys->saturated_variable_set); - cnst_list = &(sys->active_constraint_set); - XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list)); - xbt_swag_foreach(_cnst, cnst_list) - { - cnst = static_cast(_cnst); - xbt_swag_insert(cnst, &(sys->saturated_constraint_set)); + XBT_DEBUG("Active constraints : %zu", sys->active_constraint_set.size()); + for (s_lmm_constraint_t& cnst : sys->active_constraint_set) { + sys->saturated_constraint_set.push_back(cnst); } - cnst_list = &(sys->saturated_constraint_set); - xbt_swag_foreach(_cnst, cnst_list) - { - cnst = static_cast(_cnst); - cnst->remaining = cnst->bound; - cnst->usage = 0.0; + for (s_lmm_constraint_t& cnst : sys->saturated_constraint_set) { + cnst.remaining = cnst.bound; + cnst.usage = 0.0; } XBT_DEBUG("Fair bottleneck Initialized"); @@ -73,19 +63,19 @@ void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys) /* * Compute Usage and store the variables that reach the maximum. */ + auto& cnst_list = sys->saturated_constraint_set; do { if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { XBT_DEBUG("Fair bottleneck done"); sys->print(); } - XBT_DEBUG("******* Constraints to process: %d *******", xbt_swag_size(cnst_list)); - xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) - { - cnst = static_cast(_cnst); + XBT_DEBUG("******* Constraints to process: %zu *******", cnst_list.size()); + for (auto iter = std::begin(cnst_list); iter != std::end(cnst_list);) { + s_lmm_constraint_t& cnst = *iter; int nb = 0; - XBT_DEBUG("Processing cnst %p ", cnst); - elem_list = &(cnst->enabled_element_set); - cnst->usage = 0.0; + XBT_DEBUG("Processing cnst %p ", &cnst); + elem_list = &cnst.enabled_element_set; + cnst.usage = 0.0; xbt_swag_foreach(_elem, elem_list) { elem = static_cast(_elem); @@ -94,16 +84,17 @@ void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys) nb++; } XBT_DEBUG("\tThere are %d variables", nb); - if (nb > 0 && not cnst->sharing_policy) + if (nb > 0 && not cnst.sharing_policy) nb = 1; - if (not nb) { - cnst->remaining = 0.0; - cnst->usage = cnst->remaining; - xbt_swag_remove(cnst, cnst_list); - continue; + if (nb == 0) { + cnst.remaining = 0.0; + cnst.usage = 0.0; + iter = cnst_list.erase(iter); + } else { + cnst.usage = cnst.remaining / nb; + XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", &cnst, cnst.usage, nb); + iter++; } - cnst->usage = cnst->remaining / nb; - XBT_DEBUG("\tConstraint Usage %p : %f with %d variables", cnst, cnst->usage, nb); } xbt_swag_foreach_safe(_var, _var_next, var_list) @@ -124,36 +115,35 @@ void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys) } } - xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) - { - cnst = static_cast(_cnst); - XBT_DEBUG("Updating cnst %p ", cnst); - elem_list = &(cnst->enabled_element_set); + for (auto iter = std::begin(cnst_list); iter != std::end(cnst_list);) { + s_lmm_constraint_t& cnst = *iter; + XBT_DEBUG("Updating cnst %p ", &cnst); + elem_list = &cnst.enabled_element_set; xbt_swag_foreach(_elem, elem_list) { elem = static_cast(_elem); xbt_assert(elem->variable->sharing_weight > 0); - if (cnst->sharing_policy) { - XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g", cnst, cnst->remaining, elem->variable, + if (cnst.sharing_policy) { + XBT_DEBUG("\tUpdate constraint %p (%g) with variable %p by %g", &cnst, cnst.remaining, elem->variable, elem->variable->mu); - double_update(&(cnst->remaining), elem->consumption_weight * elem->variable->mu, sg_maxmin_precision); + double_update(&cnst.remaining, elem->consumption_weight * elem->variable->mu, sg_maxmin_precision); } else { - XBT_DEBUG("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g", cnst, - cnst->usage, elem->variable, elem->variable->mu); - cnst->usage = std::min(cnst->usage, elem->consumption_weight * elem->variable->mu); + XBT_DEBUG("\tNon-Shared variable. Update constraint usage of %p (%g) with variable %p by %g", &cnst, + cnst.usage, elem->variable, elem->variable->mu); + cnst.usage = std::min(cnst.usage, elem->consumption_weight * elem->variable->mu); } } - if (not cnst->sharing_policy) { - XBT_DEBUG("\tUpdate constraint %p (%g) by %g", cnst, cnst->remaining, cnst->usage); + if (not cnst.sharing_policy) { + XBT_DEBUG("\tUpdate constraint %p (%g) by %g", &cnst, cnst.remaining, cnst.usage); - double_update(&(cnst->remaining), cnst->usage, sg_maxmin_precision); + double_update(&cnst.remaining, cnst.usage, sg_maxmin_precision); } - XBT_DEBUG("\tRemaining for %p : %g", cnst, cnst->remaining); - if (cnst->remaining <= 0.0) { - XBT_DEBUG("\tGet rid of constraint %p", cnst); + XBT_DEBUG("\tRemaining for %p : %g", &cnst, cnst.remaining); + if (cnst.remaining <= 0.0) { + XBT_DEBUG("\tGet rid of constraint %p", &cnst); - xbt_swag_remove(cnst, cnst_list); + iter = cnst_list.erase(iter); xbt_swag_foreach(_elem, elem_list) { elem = static_cast(_elem); @@ -164,11 +154,13 @@ void simgrid::kernel::lmm::bottleneck_solve(lmm_system_t sys) xbt_swag_remove(elem->variable, var_list); } } + } else { + iter++; } } } while (xbt_swag_size(var_list)); - xbt_swag_reset(cnst_list); + cnst_list.clear(); sys->modified = true; if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { XBT_DEBUG("Fair bottleneck done"); diff --git a/src/kernel/lmm/lagrange.cpp b/src/kernel/lmm/lagrange.cpp index 7088e4e5c6..b68b4447a9 100644 --- a/src/kernel/lmm/lagrange.cpp +++ b/src/kernel/lmm/lagrange.cpp @@ -44,21 +44,18 @@ static double dichotomy(double init, double diff(double, const s_lmm_constraint_ // computes the value of the differential of constraint cnst applied to lambda static double partial_diff_lambda(double lambda, const s_lmm_constraint_t& cnst); -static int __check_feasible(xbt_swag_t cnst_list, xbt_swag_t var_list, int warn) +template +static int __check_feasible(const CnstList& cnst_list, xbt_swag_t var_list, int warn) { - void* _cnst; void* _elem; void* _var; - xbt_swag_t elem_list = nullptr; + const_xbt_swag_t elem_list = nullptr; lmm_element_t elem = nullptr; - lmm_constraint_t cnst = nullptr; lmm_variable_t var = nullptr; - xbt_swag_foreach(_cnst, cnst_list) - { - cnst = static_cast(_cnst); + for (s_lmm_constraint_t const& cnst : cnst_list) { double tmp = 0; - elem_list = &(cnst->enabled_element_set); + elem_list = &cnst.enabled_element_set; xbt_swag_foreach(_elem, elem_list) { elem = static_cast(_elem); @@ -67,13 +64,12 @@ static int __check_feasible(xbt_swag_t cnst_list, xbt_swag_t var_list, int warn) tmp += var->value; } - if (double_positive(tmp - cnst->bound, sg_maxmin_precision)) { + if (double_positive(tmp - cnst.bound, sg_maxmin_precision)) { if (warn) - XBT_WARN("The link (%p) is over-used. Expected less than %f and got %f", cnst, cnst->bound, tmp); + XBT_WARN("The link (%p) is over-used. Expected less than %f and got %f", &cnst, cnst.bound, tmp); return 0; } - XBT_DEBUG("Checking feasability for constraint (%p): sat = %f, lambda = %f ", cnst, tmp - cnst->bound, - cnst->lambda); + XBT_DEBUG("Checking feasability for constraint (%p): sat = %f, lambda = %f ", &cnst, tmp - cnst.bound, cnst.lambda); } xbt_swag_foreach(_var, var_list) @@ -122,11 +118,10 @@ static double new_mu(const s_lmm_variable_t& var) return mu_i; } -static double dual_objective(xbt_swag_t var_list, xbt_swag_t cnst_list) +template +static double dual_objective(xbt_swag_t var_list, const CnstList& cnst_list) { - void* _cnst; void* _var; - lmm_constraint_t cnst = nullptr; lmm_variable_t var = nullptr; double obj = 0.0; @@ -153,11 +148,8 @@ static double dual_objective(xbt_swag_t var_list, xbt_swag_t cnst_list) obj += var->mu * var->bound; } - xbt_swag_foreach(_cnst, cnst_list) - { - cnst = static_cast(_cnst); - obj += cnst->lambda * cnst->bound; - } + for (s_lmm_constraint_t const& cnst : cnst_list) + obj += cnst.lambda * cnst.bound; return obj; } @@ -184,14 +176,11 @@ void lagrange_solve(lmm_system_t sys) return; /* Initialize lambda. */ - xbt_swag_t cnst_list = &(sys->active_constraint_set); - void* _cnst; - xbt_swag_foreach(_cnst, cnst_list) - { - lmm_constraint_t cnst = (lmm_constraint_t)_cnst; - cnst->lambda = 1.0; - cnst->new_lambda = 2.0; - XBT_DEBUG("#### cnst(%p)->lambda : %e", cnst, cnst->lambda); + auto& cnst_list = sys->active_constraint_set; + for (s_lmm_constraint_t& cnst : cnst_list) { + cnst.lambda = 1.0; + cnst.new_lambda = 2.0; + XBT_DEBUG("#### cnst(%p)->lambda : %e", &cnst, cnst.lambda); } /* @@ -253,13 +242,11 @@ void lagrange_solve(lmm_system_t sys) } /* Improve the value of lambda_i */ - xbt_swag_foreach(_cnst, cnst_list) - { - lmm_constraint_t cnst = static_cast(_cnst); - XBT_DEBUG("Working on cnst (%p)", cnst); - cnst->new_lambda = dichotomy(cnst->lambda, partial_diff_lambda, *cnst, dichotomy_min_error); - XBT_DEBUG("Updating lambda : cnst->lambda (%p) : %1.20f -> %1.20f", cnst, cnst->lambda, cnst->new_lambda); - cnst->lambda = cnst->new_lambda; + for (s_lmm_constraint_t& cnst : cnst_list) { + XBT_DEBUG("Working on cnst (%p)", &cnst); + cnst.new_lambda = dichotomy(cnst.lambda, partial_diff_lambda, cnst, dichotomy_min_error); + XBT_DEBUG("Updating lambda : cnst->lambda (%p) : %1.20f -> %1.20f", &cnst, cnst.lambda, cnst.new_lambda); + cnst.lambda = cnst.new_lambda; double new_obj = dual_objective(var_list, cnst_list); XBT_DEBUG("Improvement for Objective (%g -> %g) : %g", obj, new_obj, obj - new_obj); diff --git a/src/kernel/lmm/maxmin.cpp b/src/kernel/lmm/maxmin.cpp index a563fca3b5..a50629930a 100644 --- a/src/kernel/lmm/maxmin.cpp +++ b/src/kernel/lmm/maxmin.cpp @@ -68,31 +68,28 @@ void s_lmm_system_t::check_concurrency() const if (not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) return; - void* cnstIt; - xbt_swag_foreach(cnstIt, &constraint_set) - { - lmm_constraint_t cnst = (lmm_constraint_t)cnstIt; + for (s_lmm_constraint_t const& cnst : constraint_set) { int concurrency = 0; void* elemIt; - xbt_swag_foreach(elemIt, &(cnst->enabled_element_set)) + 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(); } - xbt_swag_foreach(elemIt, &(cnst->disabled_element_set)) + xbt_swag_foreach(elemIt, &cnst.disabled_element_set) { lmm_element_t elem = (lmm_element_t)elemIt; // 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 || + 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!"); } - xbt_assert(cnst->get_concurrency_limit() < 0 || cnst->get_concurrency_limit() >= concurrency, + xbt_assert(cnst.get_concurrency_limit() < 0 || cnst.get_concurrency_limit() >= concurrency, "concurrency check failed!"); - xbt_assert(cnst->concurrency_current == concurrency, "concurrency_current is out-of-date!"); + xbt_assert(cnst.concurrency_current == concurrency, "concurrency_current is out-of-date!"); } // Check that for each variable, all corresponding elements are in the same state (i.e. same element sets) @@ -163,13 +160,7 @@ s_lmm_system_t::s_lmm_system_t(bool selective_update) : selective_update_active( XBT_DEBUG("Setting selective_update_active flag to %d", selective_update_active); xbt_swag_init(&variable_set, xbt_swag_offset(var, variable_set_hookup)); - xbt_swag_init(&constraint_set, xbt_swag_offset(cnst, constraint_set_hookup)); - - xbt_swag_init(&active_constraint_set, xbt_swag_offset(cnst, active_constraint_set_hookup)); - - xbt_swag_init(&modified_constraint_set, xbt_swag_offset(cnst, modified_constraint_set_hookup)); xbt_swag_init(&saturated_variable_set, xbt_swag_offset(var, saturated_variable_set_hookup)); - xbt_swag_init(&saturated_constraint_set, xbt_swag_offset(cnst, saturated_constraint_set_hookup)); keep_track = nullptr; variable_mallocator = xbt_mallocator_new(65536, s_lmm_system_t::variable_mallocator_new_f, @@ -475,28 +466,24 @@ void s_lmm_system_t::print() const XBT_DEBUG("Constraints"); /* Printing Constraints */ - void* _cnst; - const_xbt_swag_t cnst_list = &active_constraint_set; - xbt_swag_foreach(_cnst, cnst_list) - { - lmm_constraint_t cnst = (lmm_constraint_t)_cnst; + for (s_lmm_constraint_t const& cnst : active_constraint_set) { double sum = 0.0; // Show the enabled variables buf += "\t"; - buf += ((cnst->sharing_policy) ? "(" : "max("); - format_lmm_element_swag(&cnst->enabled_element_set, cnst->sharing_policy, sum, buf); + buf += cnst.sharing_policy ? "(" : "max("; + format_lmm_element_swag(&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_swag(&cnst.disabled_element_set, cnst.sharing_policy, sum, buf); - buf = buf + "0) <= " + std::to_string(cnst->bound) + " ('" + std::to_string(cnst->id_int) + "')"; + buf += "0) <= " + std::to_string(cnst.bound) + " ('" + std::to_string(cnst.id_int) + "')"; - if (not cnst->sharing_policy) { + if (not cnst.sharing_policy) { buf += " [MAX-Constraint]"; } XBT_DEBUG("%s", buf.c_str()); buf.clear(); - xbt_assert(not double_positive(sum - cnst->bound, cnst->bound * sg_maxmin_precision), - "Incorrect value (%f is not smaller than %f): %g", sum, cnst->bound, sum - cnst->bound); + xbt_assert(not double_positive(sum - cnst.bound, cnst.bound * sg_maxmin_precision), + "Incorrect value (%f is not smaller than %f): %g", sum, cnst.bound, sum - cnst.bound); } XBT_DEBUG("Variables"); @@ -516,28 +503,29 @@ void s_lmm_system_t::print() const void s_lmm_system_t::solve() { - void* _cnst; - void* _cnst_next; + if (modified) { + XBT_IN("(sys=%p)", this); + /* Compute Usage and store the variables that reach the maximum. If selective_update_active is true, only + * constraints that changed are considered. Otherwise all constraints with active actions are considered. + */ + if (selective_update_active) + solve(modified_constraint_set); + else + solve(active_constraint_set); + XBT_OUT(); + } +} + +template void s_lmm_system_t::solve(CnstList& cnst_list) +{ void* _elem; double min_usage = -1; double min_bound = -1; - if (not modified) - return; - - XBT_IN("(sys=%p)", this); - - /* Compute Usage and store the variables that reach the maximum. If selective_update_active is true, only constraints - * that changed are considered. Otherwise all constraints with active actions are considered. - */ - xbt_swag_t cnst_list = selective_update_active ? &modified_constraint_set : &active_constraint_set; - - XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list)); + XBT_DEBUG("Active constraints : %zu", cnst_list.size()); /* Init: Only modified code portions: reset the value of active variables */ - xbt_swag_foreach(_cnst, cnst_list) - { - lmm_constraint_t cnst = (lmm_constraint_t)_cnst; - xbt_swag_t elem_list = &(cnst->enabled_element_set); + 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; @@ -546,29 +534,27 @@ void s_lmm_system_t::solve() } } - s_lmm_constraint_light_t* cnst_light_tab = new s_lmm_constraint_light_t[xbt_swag_size(cnst_list)](); + s_lmm_constraint_light_t* cnst_light_tab = new s_lmm_constraint_light_t[cnst_list.size()](); int cnst_light_num = 0; dyn_light_t saturated_constraints; - xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) - { - lmm_constraint_t cnst = (lmm_constraint_t)_cnst; + for (s_lmm_constraint_t& cnst : cnst_list) { /* INIT: Collect constraints that actually need to be saturated (i.e remaining and usage are strictly positive) * into cnst_light_tab. */ - cnst->remaining = cnst->bound; - if (not double_positive(cnst->remaining, cnst->bound * sg_maxmin_precision)) + cnst.remaining = cnst.bound; + if (not double_positive(cnst.remaining, cnst.bound * sg_maxmin_precision)) continue; - cnst->usage = 0; - xbt_swag_t elem_list = &(cnst->enabled_element_set); + 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) { - 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; + 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; elem->make_active(); simgrid::surf::Action* action = static_cast(elem->variable->id); @@ -576,17 +562,17 @@ void s_lmm_system_t::solve() keep_track->push_back(*action); } } - XBT_DEBUG("Constraint '%d' usage: %f remaining: %f concurrency: %i<=%i<=%i", cnst->id_int, cnst->usage, - cnst->remaining, cnst->concurrency_current, cnst->concurrency_maximum, cnst->get_concurrency_limit()); + XBT_DEBUG("Constraint '%d' usage: %f remaining: %f concurrency: %i<=%i<=%i", cnst.id_int, cnst.usage, + cnst.remaining, cnst.concurrency_current, cnst.concurrency_maximum, cnst.get_concurrency_limit()); /* Saturated constraints update */ - if (cnst->usage > 0) { - cnst_light_tab[cnst_light_num].cnst = cnst; - cnst->cnst_light = &(cnst_light_tab[cnst_light_num]); - cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage; + if (cnst.usage > 0) { + cnst_light_tab[cnst_light_num].cnst = &cnst; + cnst.cnst_light = &cnst_light_tab[cnst_light_num]; + 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(cnst.active_element_set.count > 0, "There is no sense adding a constraint that has no active element!"); cnst_light_num++; } @@ -730,7 +716,6 @@ void s_lmm_system_t::solve() check_concurrency(); delete[] cnst_light_tab; - XBT_OUT(); } void lmm_solve(lmm_system_t sys) @@ -957,8 +942,8 @@ void s_lmm_system_t::update_modified_set_rec(lmm_constraint_t cnst) for (s_lmm_element_t const& elem : var->cnsts) { if (var->visited == visited_counter) break; - if (elem.constraint != cnst && not xbt_swag_belongs(elem.constraint, &modified_constraint_set)) { - xbt_swag_insert(elem.constraint, &modified_constraint_set); + 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); } } @@ -970,8 +955,8 @@ void s_lmm_system_t::update_modified_set_rec(lmm_constraint_t cnst) void s_lmm_system_t::update_modified_set(lmm_constraint_t cnst) { /* nothing to do if selective update isn't active */ - if (selective_update_active && not xbt_swag_belongs(cnst, &modified_constraint_set)) { - xbt_swag_insert(cnst, &modified_constraint_set); + if (selective_update_active && not cnst->modified_constraint_set_hook.is_linked()) { + modified_constraint_set.push_back(*cnst); update_modified_set_rec(cnst); } } @@ -988,7 +973,7 @@ void s_lmm_system_t::remove_all_modified_set() void* _var; xbt_swag_foreach(_var, &variable_set)((lmm_variable_t)_var)->visited = 0; } - xbt_swag_reset(&modified_constraint_set); + modified_constraint_set.clear(); } /** diff --git a/src/kernel/lmm/maxmin.hpp b/src/kernel/lmm/maxmin.hpp index 9273bcb4c0..7dc3da7dc3 100644 --- a/src/kernel/lmm/maxmin.hpp +++ b/src/kernel/lmm/maxmin.hpp @@ -13,6 +13,7 @@ #include "xbt/mallocator.h" #include "xbt/misc.h" #include "xbt/swag.h" +#include #include #include #include @@ -292,10 +293,10 @@ public: void* get_id() const { return id; } /* hookup to system */ - s_xbt_swag_hookup_t constraint_set_hookup = {nullptr, nullptr}; - s_xbt_swag_hookup_t active_constraint_set_hookup = {nullptr, nullptr}; - s_xbt_swag_hookup_t modified_constraint_set_hookup = {nullptr, nullptr}; - s_xbt_swag_hookup_t saturated_constraint_set_hookup = {nullptr, nullptr}; + boost::intrusive::list_member_hook<> constraint_set_hook; + boost::intrusive::list_member_hook<> active_constraint_set_hook; + boost::intrusive::list_member_hook<> modified_constraint_set_hook; + boost::intrusive::list_member_hook<> saturated_constraint_set_hook; s_xbt_swag_t enabled_element_set; /* a list of lmm_element_t */ s_xbt_swag_t disabled_element_set; /* a list of lmm_element_t */ s_xbt_swag_t active_element_set; /* a list of lmm_element_t */ @@ -509,7 +510,7 @@ public: * @param cnst A constraint * @return [description] */ - int constraint_used(lmm_constraint_t cnst) { return xbt_swag_belongs(cnst, &active_constraint_set); } + int constraint_used(lmm_constraint_t cnst) { return cnst->active_constraint_set_hook.is_linked(); } /** @brief Print the lmm system */ void print() const; @@ -524,18 +525,31 @@ private: void var_free(lmm_variable_t var); void cnst_free(lmm_constraint_t cnst); lmm_variable_t extract_variable() { return static_cast(xbt_swag_extract(&variable_set)); } - lmm_constraint_t extract_constraint() { return static_cast(xbt_swag_extract(&constraint_set)); } - void insert_constraint(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &constraint_set); } + lmm_constraint_t extract_constraint() + { + if (constraint_set.empty()) + return nullptr; + lmm_constraint_t res = &constraint_set.front(); + constraint_set.pop_front(); + return res; + } + void insert_constraint(lmm_constraint_t cnst) { constraint_set.push_back(*cnst); } void remove_variable(lmm_variable_t var) { xbt_swag_remove(var, &variable_set); xbt_swag_remove(var, &saturated_variable_set); } - void make_constraint_active(lmm_constraint_t cnst) { xbt_swag_insert(cnst, &active_constraint_set); } + void make_constraint_active(lmm_constraint_t cnst) + { + if (not cnst->active_constraint_set_hook.is_linked()) + active_constraint_set.push_back(*cnst); + } void make_constraint_inactive(lmm_constraint_t cnst) { - xbt_swag_remove(cnst, &active_constraint_set); - xbt_swag_remove(cnst, &modified_constraint_set); + if (cnst->active_constraint_set_hook.is_linked()) + active_constraint_set.erase(active_constraint_set.iterator_to(*cnst)); + if (cnst->modified_constraint_set_hook.is_linked()) + modified_constraint_set.erase(modified_constraint_set.iterator_to(*cnst)); } void enable_var(lmm_variable_t var); @@ -557,12 +571,19 @@ private: void remove_all_modified_set(); void check_concurrency() const; + template void solve(CnstList& cnst_list); public: bool modified; s_xbt_swag_t variable_set; /* a list of lmm_variable_t */ - s_xbt_swag_t active_constraint_set; /* a list of lmm_constraint_t */ + boost::intrusive::list, + &s_lmm_constraint_t::active_constraint_set_hook>> + active_constraint_set; s_xbt_swag_t saturated_variable_set; /* a list of lmm_variable_t */ - s_xbt_swag_t saturated_constraint_set; /* a list of lmm_constraint_t */ + boost::intrusive::list, + &s_lmm_constraint_t::saturated_constraint_set_hook>> + saturated_constraint_set; simgrid::surf::ActionLmmListPtr keep_track; @@ -572,8 +593,14 @@ private: bool selective_update_active; /* flag to update partially the system only selecting changed portions */ unsigned visited_counter; /* used by lmm_update_modified_set and lmm_remove_modified_set to cleverly (un-)flag the * constraints (more details in these functions) */ - s_xbt_swag_t constraint_set; /* a list of lmm_constraint_t */ - s_xbt_swag_t modified_constraint_set; /* a list of modified lmm_constraint_t */ + boost::intrusive::list, + &s_lmm_constraint_t::constraint_set_hook>> + constraint_set; + boost::intrusive::list, + &s_lmm_constraint_t::modified_constraint_set_hook>> + modified_constraint_set; xbt_mallocator_t variable_mallocator; };