Author: mlschroe Date: Thu Nov 8 14:45:37 2007 New Revision: 7757 URL: http://svn.opensuse.org/viewcvs/zypp?rev=7757&view=rev Log: - implement branching and solution callback Modified: trunk/sat-solver/src/solver.c trunk/sat-solver/src/solver.h trunk/sat-solver/testsuite/yps.c Modified: trunk/sat-solver/src/solver.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/solver.c?rev=7757&r1=7756&r2=7757&view=diff ============================================================================== --- trunk/sat-solver/src/solver.c (original) +++ trunk/sat-solver/src/solver.c Thu Nov 8 14:45:37 2007 @@ -1780,11 +1780,11 @@ solv->decisionq_why.count--; solv->propagate_index = solv->decisionq.count; } - while (solv->minimize.count && solv->minimize.elements[solv->minimize.count - 1] <= -level) + while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level) { - solv->minimize.count--; - while (solv->minimize.count && solv->minimize.elements[solv->minimize.count - 1] >= 0) - solv->minimize.count--; + solv->branches.count--; + while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0) + solv->branches.count--; } solv->recommends_index = -1; } @@ -1904,7 +1904,6 @@ solv = (Solver *)xcalloc(1, sizeof(Solver)); solv->pool = pool; solv->installed = installed; - pool->verbose = 1; queue_init(&solv->ruletojob); queue_init(&solv->decisionq); @@ -1913,7 +1912,7 @@ queue_init(&solv->suggestions); queue_init(&solv->learnt_why); queue_init(&solv->learnt_pool); - queue_init(&solv->minimize); + queue_init(&solv->branches); map_init(&solv->recommendsmap, pool->nsolvables); map_init(&solv->suggestsmap, pool->nsolvables); @@ -1942,7 +1941,7 @@ queue_free(&solv->learnt_pool); queue_free(&solv->problems); queue_free(&solv->suggestions); - queue_free(&solv->minimize); + queue_free(&solv->branches); map_free(&solv->recommendsmap); map_free(&solv->suggestsmap); @@ -2198,8 +2197,8 @@ if (j == dq.count) { for (j = 1; j < dq.count; j++) - queue_push(&solv->minimize, dq.elements[j]); - queue_push(&solv->minimize, -level); + queue_push(&solv->branches, dq.elements[j]); + queue_push(&solv->branches, -level); j = 0; } } @@ -2287,14 +2286,53 @@ continue; } } + + if (solv->solution_callback) + { + solv->solution_callback(solv, solv->solution_callback_data); + if (solv->branches.count) + { + int i = solv->branches.count - 1; + int l = -solv->branches.elements[i]; + for (; i > 0; i--) + if (solv->branches.elements[i - 1] < 0) + break; + p = solv->branches.elements[i]; +#if 1 + s = pool->solvables + p; + printf("branching with %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch)); +#endif + queue_empty(&dq); + for (j = i + 1; j < solv->branches.count; j++) + queue_push(&dq, solv->branches.elements[j]); + solv->branches.count = i; + level = l; + revert(solv, level); + if (dq.count > 1) + for (j = 0; j < dq.count; j++) + queue_push(&solv->branches, dq.elements[j]); + olevel = level; + level = setpropagatelearn(solv, level, p, disablerules); + if (level == 0) + { + printf("UNSOLVABLE\n"); + queue_free(&dq); + return; + } + continue; + } + /* all branches done, we're finally finished */ + break; + } + /* minimization step */ - if (solv->minimize.count) + if (solv->branches.count) { int l = 0, lasti = -1, lastl = -1; p = 0; - for (i = solv->minimize.count - 1; i >= 0; i--) + for (i = solv->branches.count - 1; i >= 0; i--) { - p = solv->minimize.elements[i]; + p = solv->branches.elements[i]; if (p < 0) l = -p; else if (p > 0 && solv->decisionmap[p] > l + 1) @@ -2306,8 +2344,8 @@ if (lasti >= 0) { /* kill old solvable so that we do not loop */ - p = solv->minimize.elements[lasti]; - solv->minimize.elements[lasti] = 0; + p = solv->branches.elements[lasti]; + solv->branches.elements[lasti] = 0; s = pool->solvables + p; #if 1 printf("minimizing %d -> %d with %s-%s.%s\n", solv->decisionmap[p], l, id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch)); Modified: trunk/sat-solver/src/solver.h URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/solver.h?rev=7757&r1=7756&r2=7757&view=diff ============================================================================== --- trunk/sat-solver/src/solver.h (original) +++ trunk/sat-solver/src/solver.h Thu Nov 8 14:45:37 2007 @@ -44,6 +44,8 @@ Id n1, n2; /* next rules in linked list, corresponding to w1,w2 */ } Rule; +struct solver; + typedef struct solver { Pool *pool; Repo *installed; @@ -83,7 +85,10 @@ /* learnt rule history */ Queue learnt_why; Queue learnt_pool; - Queue minimize; + + Queue branches; + int (*solution_callback)(struct solver *solv, void *data); + void *solution_callback_data; int propagate_index; Modified: trunk/sat-solver/testsuite/yps.c URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/testsuite/yps.c?rev=7757&r1=7756&r2=7757&view=diff ============================================================================== --- trunk/sat-solver/testsuite/yps.c (original) +++ trunk/sat-solver/testsuite/yps.c Thu Nov 8 14:45:37 2007 @@ -68,6 +68,13 @@ return pool->solvables + id; } +static int +solution_callback(Solver *solv, void *data) +{ + printf("*** Found another decision:\n"); + printdecisions(solv); + return 0; +} //----------------------------------------------- @@ -83,6 +90,7 @@ Queue job; Id id; int erase = 0; + int all = 0; pool = pool_create(); pool_setarch(pool, "i686"); @@ -98,13 +106,31 @@ exit(0); } - // '-e' ? - - if (argc > 1 && !strcmp(argv[1], "-e")) + while (argc > 1) { - erase = 1; - argc--; - argv++; + // '-e' ? + if (!strcmp(argv[1], "-e")) + { + erase = 1; + argc--; + argv++; + continue; + } + if (!strcmp(argv[1], "-A")) + { + all = 1; + argc--; + argv++; + continue; + } + if (!strcmp(argv[1], "-v")) + { + pool->verbose++; + argc--; + argv++; + continue; + } + break; } // Load system file (installed packages) @@ -153,7 +179,7 @@ pool_prepare(pool); - pool->promoteepoch = 1; + pool->promoteepoch = 0; // start solving @@ -167,6 +193,8 @@ // Solve ! + if (all) + solv->solution_callback = solution_callback; solve(solv, &job); // clean up -- To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org For additional commands, e-mail: zypp-commit+help@opensuse.org