From 955153eac28cbf3d303cabd3563116c51a48ed16 Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Wed, 22 Feb 2012 09:08:14 +0200 Subject: solver: remove dependency merging; it's not worth it callgrind says it's more overhead than improvement. back jumping effectively prunes all bad trees. but can be added later if it becomes needed; due to e.g. provides support. --- src/solver.c | 81 +++--------------------------------------------------------- 1 file changed, 4 insertions(+), 77 deletions(-) (limited to 'src/solver.c') diff --git a/src/solver.c b/src/solver.c index 98fa99b..e758634 100644 --- a/src/solver.c +++ b/src/solver.c @@ -96,8 +96,6 @@ struct apk_name_state { struct apk_package *chosen; struct apk_score minimum_penalty; - unsigned short merge_index; - unsigned short prerequires; unsigned short requirers; unsigned short install_ifs; @@ -120,7 +118,6 @@ struct apk_name_state { unsigned decision_counted : 1; unsigned originally_installed : 1; unsigned has_available_pkgs : 1; - unsigned prepared : 1; unsigned in_changeset : 1; /* dynamic state flags */ @@ -633,57 +630,12 @@ static int install_if_missing(struct apk_solver_state *ss, struct apk_package *p return missing; } -static void foreach_common_dependency( - struct apk_solver_state *ss, struct apk_name *name, - void (*cb)(struct apk_solver_state *ss, struct apk_name *common_dependency)) -{ - struct apk_name *name0; - struct apk_name_state *ns0; - struct apk_package *pkg; - struct apk_package_state *ps; - struct apk_dependency *dep; - int i, j, first_found = -1, last_found = 0; - - for (i = 0; i < name->pkgs->num; i++) { - pkg = name->pkgs->item[i]; - ps = pkg_to_ps(pkg); - if (ps == NULL || ps->locked) - continue; - if (first_found == -1) - first_found = i; - for (j = 0; j < pkg->depends->num; j++) { - dep = &pkg->depends->item[j]; - if (dep->optional) - continue; - name0 = dep->name; - ns0 = name_to_ns(name0); - if (ns0->merge_index == last_found) - ns0->merge_index = i + 1; - } - last_found = i + 1; - } - if (first_found == -1) - return; - - pkg = name->pkgs->item[first_found]; - for (j = 0; j < pkg->depends->num; j++) { - dep = &pkg->depends->item[j]; - if (dep->optional) - continue; - name0 = dep->name; - ns0 = name_to_ns(name0); - if (ns0->merge_index == last_found) - cb(ss, name0); - ns0->merge_index = 0; - } -} - static void get_unassigned_score(struct apk_name *name, struct apk_score *score) { struct apk_name_state *ns = name_to_ns(name); *score = (struct apk_score){ - .conflicts = ns->requirers ? : (ns->prerequires ? 1 : 0), + .conflicts = ns->requirers, .non_preferred_actions = 1, .preference = name->pkgs->num, }; @@ -735,7 +687,7 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name) options++; } - if (ns->prerequires == 0 && ns->requirers == 0 && ns->install_ifs == 0) { + if (ns->requirers == 0 && ns->install_ifs == 0) { /* No one really needs this name (anymore). */ if (list_hashed(&ns->unsolved_list)) { list_del(&ns->unsolved_list); @@ -755,10 +707,10 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name) ns->minimum_penalty = preferred_score; addscore(&ss->minimum_penalty, &ns->minimum_penalty); - dbg_printf("%s: min.pen. " SCORE_FMT ", %d prerequirers, %d requirers, %d install_ifs, %d options (next topology %d)\n", + dbg_printf("%s: min.pen. " SCORE_FMT ", %d requirers, %d install_ifs, %d options (next topology %d)\n", name->name, SCORE_PRINTF(&ns->minimum_penalty), - ns->prerequires, ns->requirers, ns->install_ifs, + ns->requirers, ns->install_ifs, options, best_topology); if (!ns->none_excluded) { @@ -847,26 +799,6 @@ static void untrigger_install_if(struct apk_solver_state *ss, } } -static void increment_prerequires(struct apk_solver_state *ss, struct apk_name *name) -{ - struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); - struct apk_name_state *ns = name_to_ns(name); - - ns->prerequires++; - inherit_name_state(ss->db, name, name0); - update_name_state(ss, name); -} - -static void decrement_prerequires(struct apk_solver_state *ss, struct apk_name *name) -{ - struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); - struct apk_name_state *ns = name_to_ns(name); - - ns->prerequires--; - uninherit_name_state(ss->db, name, name0); - update_name_state(ss, name); -} - static solver_result_t apply_decision(struct apk_solver_state *ss, struct apk_decision *d) { @@ -951,8 +883,6 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, } if (d->type == DECISION_EXCLUDE) { - foreach_common_dependency(ss, name, increment_prerequires); - if (update_name_state(ss, name) == 0) { dbg_printf("%s: %s would prune name to empty\n", name->name, @@ -983,9 +913,6 @@ static void undo_decision(struct apk_solver_state *ss, struct apk_score score; ns->name_touched = 1; - if (d->type == DECISION_EXCLUDE) { - foreach_common_dependency(ss, name, decrement_prerequires); - } if (pkg != NULL) { struct apk_package_state *ps = pkg_to_ps(pkg); -- cgit v1.2.3-70-g09d2