diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/Makefile | 2 | ||||
| -rw-r--r-- | src/apk_package.h | 5 | ||||
| -rw-r--r-- | src/dot.c | 15 | ||||
| -rw-r--r-- | src/solver.c | 130 | ||||
| -rw-r--r-- | src/test.c | 1 | ||||
| -rw-r--r-- | src/topology.c | 56 |
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; @@ -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, @@ -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); -} |