From 01d0e4c408ec5096784c59d5f470960fbb2f3753 Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Mon, 8 Oct 2012 12:25:43 +0300 Subject: solver: optimize backjumping to be functional when backtracking --- src/apk_package.h | 3 ++- src/solver.c | 14 +++++++------- 2 files changed, 9 insertions(+), 8 deletions(-) (limited to 'src') diff --git a/src/apk_package.h b/src/apk_package.h index bd2bbe3..fdc0b8d 100644 --- a/src/apk_package.h +++ b/src/apk_package.h @@ -60,7 +60,8 @@ struct apk_sign_ctx { struct apk_dependency { struct apk_name *name; apk_blob_t *version; - unsigned short repository_tag; + unsigned solver_state : 22; + unsigned repository_tag : 6; unsigned conflict : 1; unsigned result_mask : 3; }; diff --git a/src/solver.c b/src/solver.c index 75a044b..940282a 100644 --- a/src/solver.c +++ b/src/solver.c @@ -1029,8 +1029,10 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency } } - if (name->ss.last_touched_decision == 0 || changed) + if (name->ss.last_touched_decision == 0 || changed) { + dep->solver_state = name->ss.last_touched_decision; name->ss.last_touched_decision = ss->num_decisions; + } if (!dep->conflict) { dbg_printf("%s requirers += %d\n", name->name, strength); @@ -1099,12 +1101,10 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency * } } - /* note: for perfection, we should revert here to the - * *previous* value, but that'd require keeping track - * of it which would require dynamic memory allocations - * or additional solver state field in apk_dependency - * to store it (or hefty recalculations). */ - name->ss.last_touched_decision = 0; + if (dep->solver_state) { + name->ss.last_touched_decision = dep->solver_state; + dep->solver_state = 0; + } if (!dep->conflict) { name->ss.requirers -= strength; -- cgit v1.2.3-60-g2f50