summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2011-08-05 11:53:26 +0300
committerTimo Teräs <timo.teras@iki.fi>2011-08-05 14:34:58 +0300
commit48d368e7d53ebdfd7ec0abcdd8340ae339de6030 (patch)
tree6f610183ec408ffa6dcd63abbbba0276341dbd18 /src
parenta5146f1b6cb5bb0cf56c6aa8293e26302e5d0ee2 (diff)
downloadapk-tools-48d368e7d53ebdfd7ec0abcdd8340ae339de6030.tar.gz
apk-tools-48d368e7d53ebdfd7ec0abcdd8340ae339de6030.tar.bz2
apk-tools-48d368e7d53ebdfd7ec0abcdd8340ae339de6030.tar.xz
apk-tools-48d368e7d53ebdfd7ec0abcdd8340ae339de6030.zip
solver: move topology sorting to solver code
this allows quite some optimizations to running time and memory requirements.
Diffstat (limited to 'src')
-rw-r--r--src/Makefile2
-rw-r--r--src/apk_package.h5
-rw-r--r--src/dot.c15
-rw-r--r--src/solver.c130
-rw-r--r--src/test.c1
-rw-r--r--src/topology.c56
6 files changed, 104 insertions, 105 deletions
diff --git a/src/Makefile b/src/Makefile
index e3b7dfb..1405a10 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -25,7 +25,7 @@ apk-objs := apk.o add.o del.o fix.o update.o info.o \
libapk.so-objs := common.o state.o database.o package.o archive.o \
version.o io.o url.o gunzip.o blob.o hash.o print.o \
- solver.o topology.o
+ solver.o
ifeq ($(TEST),y)
progs-y += apk_test
diff --git a/src/apk_package.h b/src/apk_package.h
index 6c6c1bf..51d251b 100644
--- a/src/apk_package.h
+++ b/src/apk_package.h
@@ -80,7 +80,10 @@ struct apk_installed_package {
struct apk_package {
apk_hash_node hash_node;
- unsigned int topology_sort;
+ union {
+ int state_int;
+ void *state_ptr;
+ };
struct apk_name *name;
struct apk_installed_package *ipkg;
apk_blob_t *version, *arch, *license;
diff --git a/src/dot.c b/src/dot.c
index fc6d3c2..633954b 100644
--- a/src/dot.c
+++ b/src/dot.c
@@ -53,16 +53,15 @@ static int dump_pkg(struct dot_ctx *ctx, struct apk_package *pkg)
{
int i, j, r, ret = 0;
- /* Succesfully vandalize the apk_package by reusing
- * size field for our evil purposes ;) */
- if (pkg->size == S_EVALUATED)
+ if (pkg->state_int == S_EVALUATED)
return 0;
- if (((ssize_t)pkg->size) <= S_EVALUATING) {
- pkg->size--;
+
+ if (pkg->state_int <= S_EVALUATING) {
+ pkg->state_int--;
return 1;
}
- pkg->size = S_EVALUATING;
+ pkg->state_int = S_EVALUATING;
for (i = 0; i < pkg->depends->num; i++) {
struct apk_dependency *dep = &pkg->depends->item[i];
struct apk_name *name = dep->name;
@@ -96,8 +95,8 @@ static int dump_pkg(struct dot_ctx *ctx, struct apk_package *pkg)
}
}
}
- ret -= S_EVALUATING - pkg->size;
- pkg->size = S_EVALUATED;
+ ret -= S_EVALUATING - pkg->state_int;
+ pkg->state_int = S_EVALUATED;
return ret;
}
diff --git a/src/solver.c b/src/solver.c
index c632176..e257cad 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -9,8 +9,6 @@
* by the Free Software Foundation. See http://www.gnu.org/ for details.
*/
-/* FIXME: install-if not supported yet */
-
#include <stdlib.h>
#include "apk_defines.h"
#include "apk_database.h"
@@ -31,6 +29,7 @@
struct apk_package_state {
struct apk_package *backtrack;
+ unsigned int topology_depends;
unsigned short flags;
unsigned short conflicts;
unsigned short cur_unsatisfiable;
@@ -48,8 +47,9 @@ struct apk_name_state {
struct apk_solver_state {
struct apk_database *db;
- struct apk_package_state *pkg_state;
struct apk_name_state *name_state;
+ unsigned num_topology_positions;
+
struct list_head unsolved_list_head;
struct apk_package *latest_decision;
unsigned int topology_position;
@@ -66,6 +66,11 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
int flags);
+static inline struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
+{
+ return (struct apk_package_state*) pkg->state_ptr;
+}
+
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
{
if (pkg->installed_size == 0)
@@ -77,6 +82,47 @@ static inline int pkg_available(struct apk_database *db, struct apk_package *pkg
return FALSE;
}
+static void sort_pkg(struct apk_solver_state *ss, struct apk_package *pkg)
+{
+ struct apk_package_state *ps;
+ int i, j;
+
+ /* Avoid recursion to same package */
+ if (pkg->state_ptr != NULL)
+ return;
+
+ pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
+ ps = pkg_to_ps(pkg);
+
+ /* Sort all dependants before self */
+ for (i = 0; i < pkg->depends->num; i++) {
+ struct apk_dependency *dep = &pkg->depends->item[i];
+ struct apk_name *name0 = dep->name;
+
+ for (j = 0; j < name0->pkgs->num; j++) {
+ struct apk_package *pkg0 = name0->pkgs->item[j];
+ /* conflict depends on all to be not installed */
+ if (dep->result_mask != APK_DEPMASK_CONFLICT &&
+ !apk_dep_is_satisfied(dep, pkg0))
+ continue;
+ sort_pkg(ss, pkg0);
+ }
+ }
+
+ /* Assign a topology sorting order */
+ ps->topology_depends = ++ss->num_topology_positions;
+
+ /* FIXME: install_if */
+}
+
+static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
+{
+ int i;
+
+ for (i = 0; i < name->pkgs->num; i++)
+ sort_pkg(ss, name->pkgs->item[i]);
+}
+
static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
struct apk_name_state *ns)
{
@@ -87,7 +133,7 @@ static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
for (i = 0; i < name->pkgs->num; i++) {
struct apk_package *pkg = name->pkgs->item[i];
- struct apk_package_state *ps = &ss->pkg_state[pkg->topology_sort];
+ struct apk_package_state *ps = pkg_to_ps(pkg);
/* if package is needed for (re-)install */
if ((name->flags & APK_NAME_REINSTALL) || (pkg->ipkg == NULL)) {
@@ -108,10 +154,11 @@ static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependenc
func(ss, &deps->item[i]);
}
-static int inline can_consider_package(struct apk_solver_state *ss, struct apk_package *pkg)
+static int inline can_consider_package(struct apk_solver_state *ss, struct apk_package_state *ps)
{
- struct apk_package_state *ps = &ss->pkg_state[pkg->topology_sort];
- if (pkg->topology_sort > ss->topology_position)
+ if (ps == NULL)
+ return FALSE;
+ if (ps->topology_depends > ss->topology_position)
return FALSE;
if (ps->conflicts)
return FALSE;
@@ -127,8 +174,9 @@ static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_packa
* available packages for the name */
for (i = 0; i < name->pkgs->num; i++) {
struct apk_package *pkg0 = name->pkgs->item[i];
+ struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- if (pkg0 == pkg || !can_consider_package(ss, pkg0))
+ if (pkg0 == pkg || !can_consider_package(ss, ps0))
continue;
if (apk_flags & APK_PREFER_AVAILABLE) {
@@ -165,21 +213,23 @@ static int update_name_state(struct apk_solver_state *ss,
struct apk_name *name, struct apk_name_state *ns,
int requirers_adjustment)
{
- struct apk_package *pkg_best = NULL;
+ struct apk_package *best_pkg = NULL;
+ unsigned int best_topology = 0;
int i, options = 0;
ns->requirers += requirers_adjustment;
for (i = 0; i < name->pkgs->num; i++) {
struct apk_package *pkg0 = name->pkgs->item[i];
+ struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- if (!can_consider_package(ss, pkg0))
+ if (!can_consider_package(ss, ps0))
continue;
options++;
- if (pkg_best == NULL ||
- pkg0->topology_sort > pkg_best->topology_sort)
- pkg_best = pkg0;
+ if (best_pkg == NULL ||
+ ps0->topology_depends > best_topology)
+ best_pkg = pkg0, best_topology = ps0->topology_depends;
}
if (options == 0) {
@@ -202,10 +252,10 @@ static int update_name_state(struct apk_solver_state *ss,
name->name, ns->requirers, options);
} else {
dbg_printf("%s: added to unsolved: %d requirers, %d options (next topology %d)\n",
- name->name, ns->requirers, options, pkg_best->topology_sort);
+ name->name, ns->requirers, options, best_topology);
if (!list_hashed(&ns->unsolved_list))
list_add(&ns->unsolved_list, &ss->unsolved_list_head);
- ns->chosen = pkg_best;
+ ns->chosen = best_pkg;
}
return options;
@@ -248,7 +298,7 @@ static void undo_decision(struct apk_solver_state *ss,
ss->cur_unsatisfiable = ps->cur_unsatisfiable;
if (ps->flags & APK_PKGSTF_BRANCH)
- ss->topology_position = pkg->topology_sort;
+ ss->topology_position = ps->topology_depends;
if (ps->flags & APK_PKGSTF_INSTALL) {
ss->assigned_names--;
@@ -266,7 +316,7 @@ static void undo_decision(struct apk_solver_state *ss,
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
int flags)
{
- struct apk_package_state *ps = &ss->pkg_state[pkg->topology_sort];
+ struct apk_package_state *ps = pkg_to_ps(pkg);
ps->backtrack = ss->latest_decision;
ps->flags = flags;
@@ -274,7 +324,7 @@ static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
ss->latest_decision = pkg;
if (flags & APK_PKGSTF_BRANCH) {
- ss->topology_position = pkg->topology_sort;
+ ss->topology_position = ps->topology_depends;
dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
ss->topology_position);
} else
@@ -288,18 +338,14 @@ static int next_branch(struct apk_solver_state *ss)
struct apk_package *pkg;
struct apk_package_state *ps;
- while (1) {
+ while (ss->latest_decision != NULL) {
pkg = ss->latest_decision;
- ps = &ss->pkg_state[pkg->topology_sort];
+ ps = pkg_to_ps(pkg);
undo_decision(ss, pkg, ps);
if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
pkg = ps->backtrack;
ss->latest_decision = pkg;
- if (pkg == NULL) {
- dbg_printf("next_branch: no more branches\n");
- return 1;
- }
dbg_printf("next_branch: undo decision at topology_position %d\n",
ss->topology_position);
} else {
@@ -313,6 +359,9 @@ static int next_branch(struct apk_solver_state *ss)
return 0;
}
}
+
+ dbg_printf("next_branch: no more branches\n");
+ return 1;
}
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
@@ -333,9 +382,10 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
for (i = 0; i < name->pkgs->num; i++) {
struct apk_package *pkg0 = name->pkgs->item[i];
- struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
+ struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- if (pkg0->topology_sort >= ss->topology_position)
+ if (ps0 == NULL ||
+ ps0->topology_depends >= ss->topology_position)
continue;
if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -364,9 +414,9 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
for (i = 0; i < name->pkgs->num; i++) {
struct apk_package *pkg0 = name->pkgs->item[i];
- struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
+ struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- if (pkg0->topology_sort >= ss->topology_position)
+ if (ps0->topology_depends >= ss->topology_position)
continue;
if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -385,12 +435,13 @@ static int expand_branch(struct apk_solver_state *ss)
{
struct apk_name_state *ns;
struct apk_package *pkg0 = NULL;
+ unsigned int topology0 = 0;
/* FIXME: change unsolved_list to a priority queue */
list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
if (pkg0 == NULL ||
- ns->chosen->topology_sort > pkg0->topology_sort)
- pkg0 = ns->chosen;
+ pkg_to_ps(ns->chosen)->topology_depends > topology0)
+ pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_depends;
}
if (pkg0 == NULL) {
dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
@@ -401,7 +452,7 @@ static int expand_branch(struct apk_solver_state *ss)
/* someone needs to provide this name -- find next eligible
* provider candidate */
ns = &ss->name_state[pkg0->name->id];
- dbg_printf("expand_branch: %s %d\n", pkg0->name->name, pkg0->topology_sort);
+ dbg_printf("expand_branch: %s\n", pkg0->name->name);
push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
#if 0
@@ -424,7 +475,7 @@ static void record_solution(struct apk_solver_state *ss)
i = 0;
pkg = ss->latest_decision;
while (pkg != NULL) {
- ps = &ss->pkg_state[pkg->topology_sort];
+ ps = pkg_to_ps(pkg);
if ((ps->flags & APK_PKGSTF_INSTALL) &&
(ps->conflicts == 0))
ss->best_solution->item[i++] = pkg;
@@ -451,7 +502,7 @@ int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world
struct apk_package_array **solution, int allow_errors)
{
struct apk_solver_state *ss;
- int r;
+ int i, r;
ss = calloc(1, sizeof(struct apk_solver_state));
ss->db = db;
@@ -459,8 +510,10 @@ int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world
ss->best_unsatisfiable = -1;
ss->allow_errors = allow_errors;
list_init(&ss->unsolved_list_head);
- ss->pkg_state = calloc(db->available.packages.num_items+1, sizeof(struct apk_package_state));
- ss->name_state = calloc(db->available.names.num_items+1, sizeof(struct apk_name_state));
+ ss->name_state = calloc(db->available.names.num_items + 1, sizeof(struct apk_name_state));
+
+ for (i = 0; i < world->num; i++)
+ sort_name(ss, world->item[i].name);
foreach_dependency(ss, world, apply_constraint);
do {
@@ -497,7 +550,6 @@ int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world
r = -1;
free(ss->name_state);
- free(ss->pkg_state);
free(ss);
return r;
@@ -511,7 +563,8 @@ static int compare_change(const void *p1, const void *p2)
if (c1->newpkg == NULL) {
if (c2->newpkg == NULL)
/* both deleted - reverse topology order */
- return c1->oldpkg->topology_sort - c2->oldpkg->topology_sort;
+ return pkg_to_ps(c1->oldpkg)->topology_depends -
+ pkg_to_ps(c2->oldpkg)->topology_depends;
/* c1 deleted, c2 installed -> c2 first*/
return -1;
@@ -520,7 +573,8 @@ static int compare_change(const void *p1, const void *p2)
/* c1 installed, c2 deleted -> c1 first*/
return 1;
- return c2->newpkg->topology_sort - c1->newpkg->topology_sort;
+ return pkg_to_ps(c2->newpkg)->topology_depends -
+ pkg_to_ps(c1->newpkg)->topology_depends;
}
int apk_solver_generate_changeset(struct apk_database *db,
diff --git a/src/test.c b/src/test.c
index b6327d8..76a513d 100644
--- a/src/test.c
+++ b/src/test.c
@@ -179,7 +179,6 @@ static int test_main(void *pctx, struct apk_database *db, int argc, char **argv)
apk_deps_parse(db, &db->world, APK_BLOB_STR(argv[0]));
/* run solver */
- apk_solver_sort(db);
r = apk_solver_solve(db, db->world, &solution, TRUE);
if (r == 0) {
memset(&changeset, 0, sizeof(changeset));
diff --git a/src/topology.c b/src/topology.c
deleted file mode 100644
index a60d20c..0000000
--- a/src/topology.c
+++ /dev/null
@@ -1,56 +0,0 @@
-/* topology.c - Alpine Package Keeper (APK)
- * Topological sorting of database packages
- *
- * Copyright (C) 2011 Timo Teräs <timo.teras@iki.fi>
- * All rights reserved.
- *
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 as published
- * by the Free Software Foundation. See http://www.gnu.org/ for details.
- */
-
-#include "apk_database.h"
-
-static int sort_pkg(apk_hash_item item, void *ctx)
-{
- struct apk_package *pkg = (struct apk_package *) item;
- unsigned int *sort_order = (unsigned int *) ctx;
- int i, j;
-
- /* Avoid recursion to same package */
- if (pkg->topology_sort != 0) {
- /* if pkg->topology_sort==-1 we have encountered a
- * dependency loop. Just silently ignore it and pick a
- * random topology sorting. */
- return 0;
- }
- pkg->topology_sort = -1;
-
- /* Sort all dependants before self */
- for (i = 0; i < pkg->depends->num; i++) {
- struct apk_dependency *dep = &pkg->depends->item[i];
- struct apk_name *name0 = dep->name;
-
- /* FIXME: sort names in order of ascending preference */
- for (j = 0; j < name0->pkgs->num; j++) {
- struct apk_package *pkg0 = name0->pkgs->item[j];
- if (!apk_dep_is_satisfied(dep, pkg0))
- continue;
- sort_pkg(pkg0, ctx);
- }
- }
-
- /* FIXME: install_if, provides, etc.*/
-
- /* Finally assign a topology sorting order */
- pkg->topology_sort = ++(*sort_order);
-
- return 0;
-}
-
-void apk_solver_sort(struct apk_database *db)
-{
- unsigned int sort_order = 0;
-
- apk_hash_foreach(&db->available.packages, sort_pkg, &sort_order);
-}