From f76535cb5e09d447fb72313b244840ead42da1dd Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Wed, 28 Sep 2011 08:39:52 +0300 Subject: solver: evaluate penalty of unsatisfiable name early this prunes the search tree considerably and fixes a speed regression introduced in an earlier commit. --- src/solver.c | 20 ++++++++++++++++---- 1 file 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; -- cgit v1.2.3-70-g09d2