RPM Package Manager, CVS Repository http://rpm5.org/cvs/ ____________________________________________________________________________
Server: rpm5.org Name: Jeff Johnson Root: /v/rpm/cvs Email: [email protected] Module: rpm Date: 21-Feb-2010 21:52:35 Branch: HEAD Handle: 2010022120523401 Added files: rpm/lib order.c Modified files: rpm CHANGES rpm/lib Makefile.am librpm.vers rpmte.h rpmts.h Log: - rpm.org: swipe Tarjan's loopy scissors for hacking Summary: Revision Changes Path 1.3273 +1 -0 rpm/CHANGES 2.195 +1 -1 rpm/lib/Makefile.am 1.76 +1 -0 rpm/lib/librpm.vers 2.1 +801 -0 rpm/lib/order.c 2.72 +18 -8 rpm/lib/rpmte.h 2.130 +8 -5 rpm/lib/rpmts.h ____________________________________________________________________________ patch -p0 <<'@@ .' Index: rpm/CHANGES ============================================================================ $ cvs diff -u -r1.3272 -r1.3273 CHANGES --- rpm/CHANGES 21 Feb 2010 17:17:36 -0000 1.3272 +++ rpm/CHANGES 21 Feb 2010 20:52:34 -0000 1.3273 @@ -1,5 +1,6 @@ 5.2b1 -> 5.3a1 + - rpm.org: swipe Tarjan's loopy scissors for hacking. - jbj: rpmts: add pluggable check/order/run method vectors. - jbj: hkp: add keys.rpm5.org as the default pubkey server. - jbj: fix: split NV iff V starts with digit string in lookupPackage(). @@ . patch -p0 <<'@@ .' Index: rpm/lib/Makefile.am ============================================================================ $ cvs diff -u -r2.194 -r2.195 Makefile.am --- rpm/lib/Makefile.am 31 Dec 2009 18:38:41 -0000 2.194 +++ rpm/lib/Makefile.am 21 Feb 2010 20:52:35 -0000 2.195 @@ -50,7 +50,7 @@ usrlib_LTLIBRARIES = librpm.la librpm_la_SOURCES = \ depends.c filetriggers.c formats.c fs.c fsm.c \ - manifest.c misc.c package.c \ + manifest.c misc.c order.c package.c \ poptALL.c poptI.c poptQV.c psm.c query.c \ rpmal.c rpmchecksig.c rpmds.c rpmfc.c \ rpmfi.c rpmgi.c rpminstall.c rpmrollback.c rpmversion.c \ @@ . patch -p0 <<'@@ .' Index: rpm/lib/librpm.vers ============================================================================ $ cvs diff -u -r1.75 -r1.76 librpm.vers --- rpm/lib/librpm.vers 21 Feb 2010 17:17:37 -0000 1.75 +++ rpm/lib/librpm.vers 21 Feb 2010 20:52:35 -0000 1.76 @@ -359,6 +359,7 @@ rpmtsOpenDB; rpmtsOpenSDB; _rpmtsOrder; + _orgrpmtsOrder; rpmtsOrder; rpmtsPRCO; rpmtsPrefColor; @@ . patch -p0 <<'@@ .' Index: rpm/lib/order.c ============================================================================ $ cvs diff -u -r0 -r2.1 order.c --- /dev/null 2010-02-21 21:45:40 +0100 +++ order.c 2010-02-21 21:52:35 +0100 @@ -0,0 +1,801 @@ +/** \ingroup rpmts + * \file lib/depends.c + */ + +#include "system.h" + +#include <rpmio.h> +#include <rpmlog.h> +#include <rpmmacro.h> /* XXX %{_dependency_whiteout} */ +#include <popt.h> + +#include <rpmtypes.h> +#include <rpmtag.h> + +#define _RPMEVR_INTERNAL +#include <rpmds.h> +#include <rpmfi.h> + +#define _RPMTE_INTERNAL +#define _RPMTS_ORDER_INTERNAL +#include <rpmte.h> +#define _RPMTS_INTERNAL +#include <rpmts.h> + +#include "debug.h" + +typedef rpmuint32_t rpm_color_t; + +/* + * Strongly Connected Components + * set of packages (indirectly) requiering each other + */ +struct scc_s { + int count; /* # of external requires this SCC has */ + /* int qcnt; # of external requires pointing to this SCC */ + int size; /* # of members */ + rpmte * members; +}; + +typedef struct scc_s * scc; + +struct badDeps_s { + char * pname; + const char * qname; +}; + +static int badDepsInitialized = 0; +static struct badDeps_s * badDeps = NULL; + +/** + */ +static void freeBadDeps(void) +{ + if (badDeps) { + struct badDeps_s * bdp; + /* bdp->qname is a pointer to pname so doesn't need freeing */ + for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) + bdp->pname = _free(bdp->pname); + badDeps = _free(badDeps); + } + badDepsInitialized = 0; +} + +/** + * Check for dependency relations to be ignored. + * + * @param ts transaction set + * @param p successor element (i.e. with Requires: ) + * @param q predecessor element (i.e. with Provides: ) + * @return 1 if dependency is to be ignored. + */ +static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q) +{ + struct badDeps_s * bdp; + + if (!badDepsInitialized) { + char * s = rpmExpand("%{?_dependency_whiteout}", NULL); + const char ** av = NULL; + int msglvl = (rpmtsDFlags(ts) & RPMDEPS_FLAG_DEPLOOPS) + ? RPMLOG_WARNING : RPMLOG_DEBUG; + int ac = 0; + int i; + + if (s != NULL && *s != '\0' + && !(i = poptParseArgvString(s, &ac, (const char ***)&av)) + && ac > 0 && av != NULL) + { + bdp = badDeps = xcalloc(ac+1, sizeof(*badDeps)); + for (i = 0; i < ac; i++, bdp++) { + char * pname, * qname; + + if (av[i] == NULL) + break; + pname = xstrdup(av[i]); + if ((qname = strchr(pname, '>')) != NULL) + *qname++ = '\0'; + bdp->pname = pname; + bdp->qname = qname; + rpmlog(msglvl, + _("ignore package name relation(s) [%d]\t%s -> %s\n"), + i, bdp->pname, (bdp->qname ? bdp->qname : "???")); + } + bdp->pname = NULL; + bdp->qname = NULL; + } + av = _free(av); + s = _free(s); + badDepsInitialized++; + } + + if (badDeps != NULL) + for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) { + if (!strcmp(rpmteN(p), bdp->pname) && !strcmp(rpmteN(q), bdp->qname)) + return 1; + } + return 0; +} + +/** + * Record next "q <- p" relation (i.e. "p" requires "q"). + * @param ts transaction set + * @param p predecessor (i.e. package that "Requires: q") + * @param requires relation + * @return 0 always + */ +static inline int addRelation(rpmts ts, + rpmal al, + rpmte p, + rpmds requires) +{ + rpmte q; + struct tsortInfo_s * tsi_p, * tsi_q; + relation rel; + nsType NSType = rpmdsNSType(requires); + const char * N = rpmdsN(requires); + rpmElementType teType = rpmteType(p); + rpmsenseFlags flags; + rpmsenseFlags dsflags; + +#ifdef REFERENCE + if (N == NULL) + return 0; + + dsflags = rpmdsFlags(requires); + + /* Avoid rpmlib feature and package config dependencies */ + if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG)) + return 0; + + q = rpmalSatisfiesDepend(al, requires); +#else + rpmtsi qi; + fnpyKey key; + alKey pkgKey; +#ifdef DYING + rpmal al = (teType == TR_ADDED ? ts->addedPackages : ts->erasedPackages); +#endif + int i = 0; + + dsflags = rpmdsFlags(requires); + + /* Avoid certain NS dependencies. */ + switch (NSType) { + case RPMNS_TYPE_RPMLIB: + case RPMNS_TYPE_CONFIG: + case RPMNS_TYPE_CPUINFO: + case RPMNS_TYPE_GETCONF: + case RPMNS_TYPE_UNAME: + case RPMNS_TYPE_SONAME: + case RPMNS_TYPE_ACCESS: + case RPMNS_TYPE_USER: + case RPMNS_TYPE_GROUP: + case RPMNS_TYPE_MOUNTED: + case RPMNS_TYPE_DISKSPACE: + case RPMNS_TYPE_DIGEST: + case RPMNS_TYPE_GNUPG: + case RPMNS_TYPE_MACRO: + case RPMNS_TYPE_ENVVAR: + case RPMNS_TYPE_RUNNING: + case RPMNS_TYPE_SANITY: + case RPMNS_TYPE_VCHECK: + case RPMNS_TYPE_SIGNATURE: + return 0; + /*...@notreached@*/ break; + default: + break; + } + + /* Avoid looking up files/directories that are "owned" by _THIS_ package. */ + if (*N == '/') { +#ifdef NOTYET + rpmfi fi = rpmteFI(p, RPMTAG_BASENAMES); + rpmbf bf = rpmfiBloomFN(fi); + if (bf != NULL && rpmbfChk(bf, N, strlen(N)) > 0) + return 0; +#endif + } + + pkgKey = RPMAL_NOMATCH; + key = rpmalSatisfiesDepend(al, requires, &pkgKey); + + /* Ordering depends only on added/erased package relations. */ + if (pkgKey == RPMAL_NOMATCH) + return 0; + +/* XXX Set q to the added/removed package that was found. */ + /* XXX pretend erasedPackages are just appended to addedPackages. */ + if (teType == TR_REMOVED) + pkgKey = (alKey)(((long)pkgKey) + ts->numAddedPackages); + + for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) { + if (pkgKey == rpmteAddedKey(q)) + break; + } + qi = rpmtsiFree(qi); +#endif + + /* Avoid deps outside this transaction and self dependencies */ + if (q == NULL || q == p) + return 0; + + /* Avoid certain dependency relations. */ + if (ignoreDep(ts, p, q)) + return 0; + + /* Erasures are reversed installs. */ + if (teType == TR_REMOVED) { + rpmte r = p; + p = q; + q = r; + flags = isErasePreReq(dsflags); + } else { + flags = isInstallPreReq(dsflags); + } + +#ifdef DYING + /* map legacy prereq to pre/preun as needed */ + if (isLegacyPreReq(dsflags)) { + flags |= (teType == TR_ADDED) ? + RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN; + } +#endif + + tsi_p = rpmteTSI(p); + tsi_q = rpmteTSI(q); + + /* if relation got already added just update the flags */ + if (tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == p) { + tsi_q->tsi_relations->rel_flags |= flags; + tsi_p->tsi_forward_relations->rel_flags |= flags; + return 0; + } + + /* Record next "q <- p" relation (i.e. "p" requires "q"). */ + if (p != q) { + /* bump p predecessor count */ + rpmteTSI(p)->tsi_count++; + } + + /* Save max. depth in dependency tree */ + if (rpmteDepth(p) <= rpmteDepth(q)) + (void) rpmteSetDepth(p, (rpmteDepth(q) + 1)); + if (rpmteDepth(p) > ts->maxDepth) + ts->maxDepth = rpmteDepth(p); + + rel = xcalloc(1, sizeof(*rel)); + rel->rel_suc = p; + rel->rel_flags = flags; + + rel->rel_next = rpmteTSI(q)->tsi_relations; + rpmteTSI(q)->tsi_relations = rel; + if (p != q) { + /* bump q successor count */ + rpmteTSI(q)->tsi_qcnt++; + } + + rel = xcalloc(1, sizeof(*rel)); + rel->rel_suc = q; + rel->rel_flags = flags; + + rel->rel_next = rpmteTSI(p)->tsi_forward_relations; + rpmteTSI(p)->tsi_forward_relations = rel; + + return 0; +} + +/** + * Add element to list sorting by tsi_qcnt. + * @param p new element + * @retval qp address of first element + * @retval rp address of last element + * @param prefcolor + */ +static void addQ(rpmte p, + rpmte * qp, + rpmte * rp, + rpm_color_t prefcolor) +{ + rpmte q, qprev; + + /* Mark the package as queued. */ + rpmteTSI(p)->tsi_reqx = 1; + + if ((*rp) == NULL) { /* 1st element */ + /* FIX: double indirection */ + (*rp) = (*qp) = p; + return; + } + + /* Find location in queue using metric tsi_qcnt. */ + for (qprev = NULL, q = (*qp); + q != NULL; + qprev = q, q = rpmteTSI(q)->tsi_suc) + { + /* XXX Insure preferred color first. */ + if (rpmteColor(p) != prefcolor && rpmteColor(p) != rpmteColor(q)) + continue; + + if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt) + break; + } + + if (qprev == NULL) { /* insert at beginning of list */ + rpmteTSI(p)->tsi_suc = q; + (*qp) = p; /* new head */ + } else if (q == NULL) { /* insert at end of list */ + rpmteTSI(qprev)->tsi_suc = p; + (*rp) = p; /* new tail */ + } else { /* insert between qprev and q */ + rpmteTSI(p)->tsi_suc = q; + rpmteTSI(qprev)->tsi_suc = p; + } +} + +/* Search for SCCs and return an array last entry has a .size of 0 */ +static scc detectSCCs(rpmts ts) +{ + int index = 0; /* DFS node number counter */ +#ifdef REFERENCE + rpmte stack[ts->orderCount]; /* An empty stack of nodes */ +#else + rpmte * stack = alloca(ts->orderCount * sizeof(stack)); +#endif + int stackcnt = 0; + rpmtsi pi; + rpmte p; + + int sccCnt = 2; + scc SCCs = xcalloc(ts->orderCount+3, sizeof(struct scc_s)); + + auto void tarjan(rpmte p); + + void tarjan(rpmte p) { + tsortInfo tsi = rpmteTSI(p); + rpmte q; + tsortInfo tsi_q; + relation rel; + + /* use negative index numbers */ + index--; + /* Set the depth index for p */ + tsi->tsi_SccIdx = index; + tsi->tsi_SccLowlink = index; + + stack[stackcnt++] = p; /* Push p on the stack */ + for (rel=tsi->tsi_relations; rel != NULL; rel=rel->rel_next) { + /* Consider successors of p */ + q = rel->rel_suc; + tsi_q = rpmteTSI(q); + if (tsi_q->tsi_SccIdx > 0) + /* Ignore already found SCCs */ + continue; + if (tsi_q->tsi_SccIdx == 0){ + /* Was successor q not yet visited? */ + tarjan(q); /* Recurse */ + /* negative index numers: use max as it is closer to 0 */ + tsi->tsi_SccLowlink = ( + tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink + ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink); + } else { + tsi->tsi_SccLowlink = ( + tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx + ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx); + } + } + + if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) { + /* v is the root of an SCC? */ + if (stack[stackcnt-1] == p) { + /* ignore trivial SCCs */ + q = stack[--stackcnt]; + tsi_q = rpmteTSI(q); + tsi_q->tsi_SccIdx = 1; + } else { + int stackIdx = stackcnt; + do { + q = stack[--stackIdx]; + tsi_q = rpmteTSI(q); + tsi_q->tsi_SccIdx = sccCnt; + } while (q != p); + + stackIdx = stackcnt; + do { + q = stack[--stackIdx]; + tsi_q = rpmteTSI(q); + /* Calculate count for the SCC */ + SCCs[sccCnt].count += tsi_q->tsi_count; + /* Subtract internal relations */ + for (rel=tsi_q->tsi_relations; rel != NULL; + rel=rel->rel_next) { + if (rel->rel_suc != q && + rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccCnt) + SCCs[sccCnt].count--; + } + } while (q != p); + SCCs[sccCnt].size = stackcnt - stackIdx; + /* copy members */ + SCCs[sccCnt].members = xcalloc(SCCs[sccCnt].size, + sizeof(rpmte)); + memcpy(SCCs[sccCnt].members, stack + stackIdx, + SCCs[sccCnt].size * sizeof(rpmte)); + stackcnt = stackIdx; + sccCnt++; + } + } + } + + pi = rpmtsiInit(ts); + while ((p=rpmtsiNext(pi, 0)) != NULL) { + /* Start a DFS at each node */ + if (rpmteTSI(p)->tsi_SccIdx == 0) + tarjan(p); + } + pi = rpmtsiFree(pi); + + SCCs = xrealloc(SCCs, (sccCnt+1)*sizeof(struct scc_s)); + /* Debug output */ + if (sccCnt > 2) { + int msglvl = (rpmtsDFlags(ts) & RPMDEPS_FLAG_DEPLOOPS) ? + RPMLOG_WARNING : RPMLOG_DEBUG; + int i; + + rpmlog(msglvl, "%d Strongly Connected Components\n", sccCnt-2); + for (i = 2; i < sccCnt; i++) { + int j; + + rpmlog(msglvl, "SCC #%d: requires %d packages\n", + i, SCCs[i].count); + /* loop over members */ + for (j = 0; j < SCCs[i].size; j++) { + rpmlog(msglvl, "\t%s\n", rpmteNEVRA(SCCs[i].members[j])); + /* show relations between members */ + rpmte member = SCCs[i].members[j]; + relation rel = rpmteTSI(member)->tsi_forward_relations; + for (; rel != NULL; rel=rel->rel_next) { + if (rpmteTSI(rel->rel_suc)->tsi_SccIdx!=i) continue; + rpmlog(msglvl, "\t\t%s %s\n", + rel->rel_flags ? "=>" : "->", + rpmteNEVRA(rel->rel_suc)); + } + } + } + } + return SCCs; +} + +static void collectTE(rpm_color_t prefcolor, rpmte q, + rpmte * newOrder, int * newOrderCount, + scc SCCs, + rpmte * queue_end, + rpmte * outer_queue, + rpmte * outer_queue_end) +{ + int treex = rpmteTree(q); + int depth = rpmteDepth(q); + char deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+'); + tsortInfo tsi = rpmteTSI(q); + relation rel; + + rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n", + *newOrderCount, rpmteNpreds(q), + rpmteTSI(q)->tsi_qcnt, + treex, depth, + (2 * depth), "", + deptypechar, + (rpmteNEVRA(q) ? rpmteNEVRA(q) : "???")); + + (void) rpmteSetDegree(q, 0); + + newOrder[*newOrderCount] = q; + (*newOrderCount)++; + + /* T6. Erase relations. */ + for (rel = rpmteTSI(q)->tsi_relations; rel != NULL; rel = rel->rel_next) { + rpmte p = rel->rel_suc; + tsortInfo p_tsi = rpmteTSI(p); + /* ignore already collected packages */ + if (p_tsi->tsi_SccIdx == 0) continue; + if (p == q) continue; + + if (p && (--p_tsi->tsi_count) == 0) { + + (void) rpmteSetTree(p, treex); + (void) rpmteSetDepth(p, depth+1); + (void) rpmteSetParent(p, q); + (void) rpmteSetDegree(q, rpmteDegree(q)+1); + + if (tsi->tsi_SccIdx > 1 && tsi->tsi_SccIdx != p_tsi->tsi_SccIdx) { + /* Relation point outside of this SCC: add to outside queue */ + assert(outer_queue != NULL && outer_queue_end != NULL); + addQ(p, outer_queue, outer_queue_end, prefcolor); + } else { + addQ(p, &tsi->tsi_suc, queue_end, prefcolor); + } + } + if (p && p_tsi->tsi_SccIdx > 1 && + p_tsi->tsi_SccIdx != rpmteTSI(q)->tsi_SccIdx) { + if (--SCCs[p_tsi->tsi_SccIdx].count == 0) { + /* New SCC is ready, add this package as representative */ + + (void) rpmteSetTree(p, treex); + (void) rpmteSetDepth(p, depth+1); + (void) rpmteSetParent(p, q); + (void) rpmteSetDegree(q, rpmteDegree(q)+1); + + if (outer_queue != NULL) { + addQ(p, outer_queue, outer_queue_end, prefcolor); + } else { + addQ(p, &rpmteTSI(q)->tsi_suc, queue_end, prefcolor); + } + } + } + } + tsi->tsi_SccIdx = 0; +} + +static void collectSCC(rpm_color_t prefcolor, rpmte p, + rpmte * newOrder, int * newOrderCount, + scc SCCs, rpmte * queue_end) +{ + int sccNr = rpmteTSI(p)->tsi_SccIdx; + struct scc_s SCC = SCCs[sccNr]; + int i; + int start, end; + relation rel; + + /* remove p from the outer queue */ + rpmte outer_queue_start = rpmteTSI(p)->tsi_suc; + rpmteTSI(p)->tsi_suc = NULL; + + /* + * Run a multi source Dijkstra's algorithm to find relations + * that can be zapped with least danger to pre reqs. + * As weight of the edges is always 1 it is not necessary to + * sort the vertices by distance as the queue gets them + * already in order + */ + + /* can use a simple queue as edge weights are always 1 */ + rpmte * queue = xmalloc((SCC.size+1) * sizeof(rpmte)); + + /* + * Find packages that are prerequired and use them as + * starting points for the Dijkstra algorithm + */ + start = end = 0; + for (i = 0; i < SCC.size; i++) { + rpmte q = SCC.members[i]; + tsortInfo tsi = rpmteTSI(q); + tsi->tsi_SccLowlink = INT_MAX; + for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) { + if (rel->rel_flags && rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccNr) { + if (rel->rel_suc != q) { + tsi->tsi_SccLowlink = 0; + queue[end++] = q; + } else { + tsi->tsi_SccLowlink = INT_MAX/2; + } + break; + } + } + } + + if (start == end) { /* no regular prereqs; add self prereqs to queue */ + for (i = 0; i < SCC.size; i++) { + rpmte q = SCC.members[i]; + tsortInfo tsi = rpmteTSI(q); + if (tsi->tsi_SccLowlink != INT_MAX) { + queue[end++] = q; + } + } + } + + /* Do Dijkstra */ + while (start != end) { + rpmte q = queue[start++]; + tsortInfo tsi = rpmteTSI(q); + for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) { + tsortInfo next_tsi = rpmteTSI(rel->rel_suc); + if (next_tsi->tsi_SccIdx != sccNr) continue; + if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) { + next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1; + queue[end++] = rel->rel_suc; + } + } + } + queue = _free(queue); + + + while (1) { + rpmte best = NULL; + rpmte inner_queue_start, inner_queue_end; + int best_score = 0; + int i; + + /* select best candidate to start with */ + for (i = 0; i < SCC.size; i++) { + rpmte q = SCC.members[i]; + tsortInfo tsi = rpmteTSI(q); + if (tsi->tsi_SccIdx == 0) /* package already collected */ + continue; + if (tsi->tsi_SccLowlink >= best_score) { + best = q; + best_score = tsi->tsi_SccLowlink; + } + } + + if (best == NULL) /* done */ + break; + + /* collect best candidate and all packages that get freed */ + inner_queue_start = inner_queue_end = NULL; + addQ(best, &inner_queue_start, &inner_queue_end, prefcolor); + + for (; inner_queue_start != NULL; + inner_queue_start = rpmteTSI(inner_queue_start)->tsi_suc) { + /* Mark the package as unqueued. */ + rpmteTSI(inner_queue_start)->tsi_reqx = 0; + collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount, + SCCs, &inner_queue_end, &outer_queue_start, queue_end); + } + } + + /* restore outer queue */ + rpmteTSI(p)->tsi_suc = outer_queue_start; +} + +int _orgrpmtsOrder(rpmts ts) +{ + rpm_color_t prefcolor = rpmtsPrefColor(ts); + rpmtsi pi; rpmte p; + rpmte q; + rpmte r; + rpmte * newOrder; + int newOrderCount = 0; + int treex; + int rc; +#ifdef REFERENCE + rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts), prefcolor); +#endif + scc SCCs; + int j; + int i; + + (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0); + + /* + * XXX FIXME: this gets needlesly called twice on normal usage patterns, + * should track the need for generating the index somewhere + */ + rpmalMakeIndex(ts->addedPackages); + + /* Create erased package index. */ + pi = rpmtsiInit(ts); + while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) { +#ifdef REFERENCE + rpmalAdd(erasedPackages, p); +#else + alKey pkgKey; + fnpyKey key; + rpmuint32_t tscolor = rpmtsColor(ts); + pkgKey = RPMAL_NOMATCH; +/*...@-abstract@*/ + key = (fnpyKey) p; +/*...@=abstract@*/ + pkgKey = rpmalAdd(&ts->erasedPackages, pkgKey, key, + rpmteDS(p, RPMTAG_PROVIDENAME), + rpmteFI(p, RPMTAG_BASENAMES), tscolor); + /* XXX pretend erasedPackages are just appended to addedPackages. */ + pkgKey = (alKey)(((long)pkgKey) + ts->numAddedPackages); + (void) rpmteSetAddedKey(p, pkgKey); +#endif + } + pi = rpmtsiFree(pi); + rpmalMakeIndex(ts->erasedPackages); + + pi = rpmtsiInit(ts); + while ((p = rpmtsiNext(pi, 0)) != NULL) + rpmteNewTSI(p); + pi = rpmtsiFree(pi); + + /* Record relations. */ + rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n"); + pi = rpmtsiInit(ts); + while ((p = rpmtsiNext(pi, 0)) != NULL) { + rpmal al = (rpmteType(p) == TR_REMOVED) ? + ts->erasedPackages : ts->addedPackages; + rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME)); + + while (rpmdsNext(requires) >= 0) { + /* Record next "q <- p" relation (i.e. "p" requires "q"). */ + (void) addRelation(ts, al, p, requires); + } + } + pi = rpmtsiFree(pi); + + /* Save predecessor count and mark tree roots. */ + treex = 0; + pi = rpmtsiInit(ts); + while ((p = rpmtsiNext(pi, 0)) != NULL) { + int npreds = rpmteTSI(p)->tsi_count; + + (void) rpmteSetNpreds(p, npreds); + (void) rpmteSetDepth(p, 1); + + if (npreds == 0) + (void) rpmteSetTree(p, treex++); + else + (void) rpmteSetTree(p, -1); + } + pi = rpmtsiFree(pi); + ts->ntrees = treex; + + newOrder = xcalloc(ts->orderCount, sizeof(*newOrder)); + SCCs = detectSCCs(ts); + + rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n"); + + for (j = 0; j < 2; j++) { + /* Do two separate runs: installs first - then erases */ + unsigned oType = (j == 0 ? TR_ADDED : TR_REMOVED); + q = r = NULL; + pi = rpmtsiInit(ts); + /* Scan for zeroes and add them to the queue */ + while ((p = rpmtsiNext(pi, oType)) != NULL) { + if (rpmteTSI(p)->tsi_count != 0) + continue; + rpmteTSI(p)->tsi_suc = NULL; + addQ(p, &q, &r, prefcolor); + } + pi = rpmtsiFree(pi); + + /* Add one member of each leaf SCC */ + for (i = 2; SCCs[i].members != NULL; i++) { + if (SCCs[i].count == 0 && rpmteType(SCCs[i].members[0]) == oType) { + p = SCCs[i].members[0]; + rpmteTSI(p)->tsi_suc = NULL; + addQ(p, &q, &r, prefcolor); + } + } + + /* Process queue */ + for (; q != NULL; q = rpmteTSI(q)->tsi_suc) { + /* Mark the package as unqueued. */ + rpmteTSI(q)->tsi_reqx = 0; + if (rpmteTSI(q)->tsi_SccIdx > 1) { + collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r); + } else { + collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r, + NULL, NULL); + } + } + } + + /* Clean up tsort data */ + pi = rpmtsiInit(ts); + while ((p = rpmtsiNext(pi, 0)) != NULL) + rpmteFreeTSI(p); + pi = rpmtsiFree(pi); + + assert(newOrderCount == ts->orderCount); + + ts->order = _free(ts->order); + ts->order = newOrder; + ts->orderAlloced = ts->orderCount; + rc = 0; + + for (i = 2; SCCs[i].members != NULL; i++) + SCCs[i].members = _free(SCCs[i].members); + SCCs = _free(SCCs); + +#ifdef DYING + rpmalFree(ts->erasedPackages); + ts->erasedPackages = NULL; +#endif + freeBadDeps(); + + (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0); + + return rc; +} @@ . patch -p0 <<'@@ .' Index: rpm/lib/rpmte.h ============================================================================ $ cvs diff -u -r2.71 -r2.72 rpmte.h --- rpm/lib/rpmte.h 12 Feb 2010 12:32:08 -0000 2.71 +++ rpm/lib/rpmte.h 21 Feb 2010 20:52:35 -0000 2.72 @@ -37,26 +37,36 @@ #include <rpmtxn.h> #include <rpmal.h> +typedef struct relation_s * relation; + +#if defined(_RPMTS_ORDER_INTERNAL) +struct relation_s { + rpmte rel_suc; // pkg requiring this package + rpmsenseFlags rel_flags; // accumulated flags of the requirements + struct relation_s * rel_next; +}; +#endif + /** \ingroup rpmte * Dependncy ordering information. */ /*...@-fielduse@*/ /* LCL: confused by union? */ struct tsortInfo_s { - union { - int count; - /*...@exposed@*/ /*...@dependent@*/ /*...@null@*/ - rpmte suc; - } tsi_u; -#define tsi_count tsi_u.count -#define tsi_suc tsi_u.suc /*...@owned@*/ /*...@null@*/ tsortInfo tsi_next; /*...@exposed@*/ /*...@dependent@*/ /*...@null@*/ rpmte tsi_chain; int tsi_tagn; - int tsi_reqx; int tsi_queued; + + int tsi_count; int tsi_qcnt; + int tsi_reqx; + relation tsi_relations; + relation tsi_forward_relations; + rpmte tsi_suc; + int tsi_SccIdx; + int tsi_SccLowlink; }; /*...@=fielduse@*/ @@ . patch -p0 <<'@@ .' Index: rpm/lib/rpmts.h ============================================================================ $ cvs diff -u -r2.129 -r2.130 rpmts.h --- rpm/lib/rpmts.h 21 Feb 2010 17:17:37 -0000 2.129 +++ rpm/lib/rpmts.h 21 Feb 2010 20:52:35 -0000 2.130 @@ -343,10 +343,10 @@ * @param ts transaction set * @return 0 = deps ok, 1 = dep problems, 2 = error */ -int _rpmtsCheck(rpmts ts) +extern int (*rpmtsCheck) (rpmts ts) /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; -extern int (*rpmtsCheck) (rpmts ts) +int _rpmtsCheck(rpmts ts) /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; @@ -366,10 +366,13 @@ * @param ts transaction set * @return no. of (added) packages that could not be ordered */ +extern int (*rpmtsOrder) (rpmts ts) + /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ + /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; int _rpmtsOrder(rpmts ts) /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; -extern int (*rpmtsOrder) (rpmts ts) +int _orgrpmtsOrder(rpmts ts) /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; @@ -390,10 +393,10 @@ * @param ignoreSet bits to filter problem types * @return 0 on success, -1 on error, >0 with newProbs set */ -int _rpmtsRun(rpmts ts, rpmps okProbs, rpmprobFilterFlags ignoreSet) +extern int (*rpmtsRun) (rpmts ts, rpmps okProbs, rpmprobFilterFlags ignoreSet) /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; -extern int (*rpmtsRun) (rpmts ts, rpmps okProbs, rpmprobFilterFlags ignoreSet) +int _rpmtsRun(rpmts ts, rpmps okProbs, rpmprobFilterFlags ignoreSet) /*...@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/ /*...@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/; @@ . ______________________________________________________________________ RPM Package Manager http://rpm5.org CVS Sources Repository [email protected]
