summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2012-10-08 12:25:43 +0300
committerTimo Teräs <timo.teras@iki.fi>2012-10-08 12:25:43 +0300
commit01d0e4c408ec5096784c59d5f470960fbb2f3753 (patch)
treec30722337ed8506cb3831a0eb8e0c89ede427975 /src
parent831bce5cf90dea266f53a0d82c7371e4652c524c (diff)
downloadapk-tools-01d0e4c408ec5096784c59d5f470960fbb2f3753.tar.gz
apk-tools-01d0e4c408ec5096784c59d5f470960fbb2f3753.tar.bz2
apk-tools-01d0e4c408ec5096784c59d5f470960fbb2f3753.tar.xz
apk-tools-01d0e4c408ec5096784c59d5f470960fbb2f3753.zip
solver: optimize backjumping
to be functional when backtracking
Diffstat (limited to 'src')
-rw-r--r--src/apk_package.h3
-rw-r--r--src/solver.c14
2 files changed, 9 insertions, 8 deletions
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;