summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2011-09-28 08:39:52 +0300
committerTimo Teräs <timo.teras@iki.fi>2011-09-28 08:39:52 +0300
commitf76535cb5e09d447fb72313b244840ead42da1dd (patch)
treea5d59d99fd77ae37a270c7583516078494ac13ba /src
parentf4ac687a8a448d7dc89d1c9dc42a5b10e3f86957 (diff)
downloadapk-tools-f76535cb5e09d447fb72313b244840ead42da1dd.tar.gz
apk-tools-f76535cb5e09d447fb72313b244840ead42da1dd.tar.bz2
apk-tools-f76535cb5e09d447fb72313b244840ead42da1dd.tar.xz
apk-tools-f76535cb5e09d447fb72313b244840ead42da1dd.zip
solver: evaluate penalty of unsatisfiable name early
this prunes the search tree considerably and fixes a speed regression introduced in an earlier commit.
Diffstat (limited to 'src')
-rw-r--r--src/solver.c20
1 files changed, 16 insertions, 4 deletions
diff --git a/src/solver.c b/src/solver.c
index 1f38136..a3530d0 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -377,6 +377,15 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
best_pkg = pkg0, best_topology = pkg0->topology_hard;
}
+ if (skipped_options == 0 && options == 0) {
+ if (!ns->locked)
+ ss->cur_unsatisfiable += ns->requirers;
+ ns->locked = 1;
+ ns->chosen = NULL;
+ } else {
+ ns->locked = 0;
+ }
+
if (ns->requirers == 0 && ns->install_ifs == 0) {
if (list_hashed(&ns->unsolved_list)) {
list_del(&ns->unsolved_list);
@@ -624,8 +633,13 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
int i;
if (ns->locked) {
- dbg_printf(PKG_VER_FMT " selected already for %s\n",
- PKG_VER_PRINTF(ns->chosen), dep->name->name);
+ if (ns->chosen != NULL) {
+ dbg_printf(PKG_VER_FMT " selected already for %s\n",
+ PKG_VER_PRINTF(ns->chosen), dep->name->name);
+ } else {
+ dbg_printf("%s selected to not be satisfied\n",
+ dep->name->name);
+ }
return;
}
@@ -677,8 +691,6 @@ static int expand_branch(struct apk_solver_state *ss)
}
ss->refresh_name_states = 0;
if (pkg0 == NULL) {
- list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list)
- ss->cur_unsatisfiable += ns->requirers;
dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
ss->cur_unsatisfiable);
return 1;