diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/depends.c | 23 | ||||
| -rw-r--r-- | lib/rpmte.c | 15 | ||||
| -rw-r--r-- | lib/rpmte.h | 24 | ||||
| -rw-r--r-- | lib/rpmts.c | 4 | ||||
| -rw-r--r-- | lib/rpmts.h | 2 |
5 files changed, 59 insertions, 9 deletions
diff --git a/lib/depends.c b/lib/depends.c index 707032369..37ecef3cd 100644 --- a/lib/depends.c +++ b/lib/depends.c @@ -1126,6 +1126,8 @@ static inline int addRelation(rpmts ts, if (rpmteDepth(p) <= rpmteDepth(q)) /* Save max. depth in dependency tree */ (void) rpmteSetDepth(p, (rpmteDepth(q) + 1)); + if (rpmteDepth(p) > ts->maxDepth) + ts->maxDepth = rpmteDepth(p); tsi = xcalloc(1, sizeof(*tsi)); tsi->tsi_suc = p; @@ -1225,6 +1227,8 @@ int rpmtsOrder(rpmts ts) int newOrderCount = 0; orderListIndex orderList; int numOrderList; + int npeer = 128; /* XXX more than deep enough for now. */ + int * peer = memset(alloca(npeer*sizeof(*peer)), 0, (npeer*sizeof(*peer))); int nrescans = 10; int _printed = 0; char deptypechar; @@ -1232,6 +1236,7 @@ int rpmtsOrder(rpmts ts) int oType = 0; int treex; int depth; + int breadth; int qlen; int i, j; @@ -1340,6 +1345,7 @@ int rpmtsOrder(rpmts ts) npreds = rpmteTSI(p)->tsi_count; (void) rpmteSetNpreds(p, npreds); + (void) rpmteSetDepth(p, 1); if (npreds == 0) (void) rpmteSetTree(p, treex++); @@ -1351,9 +1357,10 @@ int rpmtsOrder(rpmts ts) } pi = rpmtsiFree(pi); + ts->ntrees = treex; /* T4. Scan for zeroes. */ - rpmMessage(RPMMESS_DEBUG, _("========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n")); + rpmMessage(RPMMESS_DEBUG, _("========== tsorting packages (order, #predecessors, #succesors, tree, depth, breadth)\n")); rescan: if (pi != NULL) pi = rpmtsiFree(pi); @@ -1396,15 +1403,19 @@ rescan: } deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+'); - rpmMessage(RPMMESS_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n", + treex = rpmteTree(q); + depth = rpmteDepth(q); + breadth = ((depth < npeer) ? peer[depth]++ : 0); + (void) rpmteSetBreadth(q, breadth); + + rpmMessage(RPMMESS_DEBUG, "%5d%5d%5d%5d%5d%5d %*s%c%s\n", orderingCount, rpmteNpreds(q), - rpmteTSI(q)->tsi_qcnt, rpmteTree(q), rpmteDepth(q), - (2 * rpmteDepth(q)), "", + rpmteTSI(q)->tsi_qcnt, + treex, depth, breadth, + (2 * depth), "", deptypechar, (rpmteNEVRA(q) ? rpmteNEVRA(q) : "???")); - treex = rpmteTree(q); - depth = rpmteDepth(q); (void) rpmteSetDegree(q, 0); tsbytes += rpmtePkgFileSize(q); diff --git a/lib/rpmte.c b/lib/rpmte.c index dab00a8cf..e4961dc53 100644 --- a/lib/rpmte.c +++ b/lib/rpmte.c @@ -339,6 +339,21 @@ int rpmteSetDepth(rpmte te, int ndepth) return odepth; } +int rpmteBreadth(rpmte te) +{ + return (te != NULL ? te->depth : 0); +} + +int rpmteSetBreadth(rpmte te, int nbreadth) +{ + int obreadth = 0; + if (te != NULL) { + obreadth = te->breadth; + te->breadth = nbreadth; + } + return obreadth; +} + int rpmteNpreds(rpmte te) { return (te != NULL ? te->npreds : 0); diff --git a/lib/rpmte.h b/lib/rpmte.h index 68410f1ce..724ab247d 100644 --- a/lib/rpmte.h +++ b/lib/rpmte.h @@ -83,9 +83,10 @@ struct rpmte_s { rpmte parent; /*!< Parent transaction element. */ int degree; /*!< No. of immediate children. */ - int depth; /*!< Max. depth in dependency tree. */ int npreds; /*!< No. of predecessors. */ int tree; /*!< Tree index. */ + int depth; /*!< Depth in dependency tree. */ + int breadth; /*!< Breadth in dependency tree. */ unsigned int db_instance; /*!< Database Instance after add */ /*@owned@*/ tsortInfo tsi; /*!< Dependency ordering chains. */ @@ -307,7 +308,7 @@ uint_32 rpmtePkgFileSize(rpmte te) /*@*/; /** - * Retrieve tsort tree depth of transaction element. + * Retrieve dependency tree depth of transaction element. * @param te transaction element * @return depth */ @@ -315,7 +316,7 @@ int rpmteDepth(rpmte te) /*@*/; /** - * Set tsort tree depth of transaction element. + * Set dependency tree depth of transaction element. * @param te transaction element * @param ndepth new depth * @return previous depth @@ -324,6 +325,23 @@ int rpmteSetDepth(rpmte te, int ndepth) /*@modifies te @*/; /** + * Retrieve dependency tree breadth of transaction element. + * @param te transaction element + * @return breadth + */ +int rpmteBreadth(rpmte te) + /*@*/; + +/** + * Set dependency tree breadth of transaction element. + * @param te transaction element + * @param nbreadth new breadth + * @return previous breadth + */ +int rpmteSetBreadth(rpmte te, int nbreadth) + /*@modifies te @*/; + +/** * Retrieve tsort no. of predecessors of transaction element. * @param te transaction element * @return no. of predecessors diff --git a/lib/rpmts.c b/lib/rpmts.c index db526831a..54e16c7c3 100644 --- a/lib/rpmts.c +++ b/lib/rpmts.c @@ -767,6 +767,8 @@ void rpmtsEmpty(rpmts ts) pi = rpmtsiFree(pi); ts->orderCount = 0; + ts->ntrees = 0; + ts->maxDepth = 0; ts->numRemovedPackages = 0; /*@-nullstate@*/ /* FIX: partial annotations */ @@ -1519,6 +1521,8 @@ rpmts rpmtsCreate(void) ts->orderAlloced = 0; ts->orderCount = 0; ts->order = NULL; + ts->ntrees = 0; + ts->maxDepth = 0; ts->probs = NULL; diff --git a/lib/rpmts.h b/lib/rpmts.h index f209c7d39..64ec13641 100644 --- a/lib/rpmts.h +++ b/lib/rpmts.h @@ -294,6 +294,8 @@ struct rpmts_s { int orderCount; /*!< No. of transaction elements. */ int orderAlloced; /*!< No. of allocated transaction elements. */ int unorderedSuccessors; /*!< Index of 1st element of successors. */ + int ntrees; /*!< No. of dependency trees. */ + int maxDepth; /*!< Maximum depth of dependency tree(s). */ int selinuxEnabled; /*!< Is SE linux enabled? */ int chrootDone; /*!< Has chroot(2) been been done? */ |