rpm  5.4.15
order.c
Go to the documentation of this file.
1 
5 #include "system.h"
6 
7 #include <rpmio.h>
8 #include <rpmlog.h>
9 #include <rpmmacro.h> /* XXX %{_dependency_whiteout} */
10 #include <popt.h>
11 
12 #include <rpmtypes.h>
13 #include <rpmtag.h>
14 
15 #define _RPMEVR_INTERNAL
16 #include <rpmds.h>
17 #include <rpmfi.h>
18 
19 #define _RPMTE_INTERNAL
20 #define _RPMTS_ORDER_INTERNAL
21 #include <rpmte.h>
22 #define _RPMTS_INTERNAL
23 #include <rpmts.h>
24 
25 #include "debug.h"
26 
28 
29 /*@access alKey @*/ /* XXX for reordering and RPMAL_NOMATCH assign */
30 
33 typedef /*@abstract@*/ struct orderListIndex_s * orderListIndex;
34 /*@access orderListIndex@*/
35 
39 /*@dependent@*/
41  int orIndex;
42 };
43 
44 /*
45  * Strongly Connected Components
46  * set of packages (indirectly) requiering each other
47  */
48 struct scc_s {
49  int count; /* # of external requires this SCC has */
50 #if 0
51  int qcnt; /* # of external requires pointing to this SCC */
52 #endif
53  int size; /* # of members */
54 #ifdef REFERENCE
56 #else
58 #endif /* REFERENCE */
59 };
60 
61 typedef struct scc_s * scc;
62 
63 #ifdef REFERENCE
64 struct relation_s {
65  tsortInfo rel_suc; /* pkg requiring this package */
66  rpmsenseFlags rel_flags; /* accumulated flags of the requirements */
67  struct relation_s * rel_next;
68 };
69 
70 typedef struct relation_s * relation;
71 
72 struct tsortInfo_s {
73  rpmte te;
74  int tsi_count; /* #pkgs this pkg requires */
75  int tsi_qcnt; /* #pkgs requiring this package */
76  int tsi_reqx; /* requires Idx/mark as (queued/loop) */
77  struct relation_s * tsi_relations;
78  struct relation_s * tsi_forward_relations;
79  tsortInfo tsi_suc; /* used for queuing (addQ) */
80  int tsi_SccIdx; /* # of the SCC the node belongs to (1 for trivial SCCs) */
81  int tsi_SccLowlink; /* used for SCC detection */
82 };
83 #endif /* REFERENCE */
84 
85 struct badDeps_s {
86 /*@observer@*/ /*@owned@*/ /*@null@*/
87  const char * pname;
88 /*@observer@*/ /*@dependent@*/ /*@null@*/
89  const char * qname;
90 };
91 
92 #ifdef __cplusplus
93 GENfree(orderListIndex)
94 GENfree(rpmte *)
95 #endif /* __cplusplus */
96 
97 /*@unchecked@*/
98 static int badDepsInitialized;
99 
100 /*@unchecked@*/ /*@only@*/ /*@null@*/
101 static struct badDeps_s * badDeps;
102 
105 /*@-modobserver -observertrans @*/
106 static void freeBadDeps(void)
107  /*@globals badDeps, badDepsInitialized @*/
108  /*@modifies badDeps, badDepsInitialized @*/
109 {
110  if (badDeps) {
111  struct badDeps_s * bdp;
112  /* bdp->qname is a pointer to pname so doesn't need freeing */
113  for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++)
114  bdp->pname = _free(bdp->pname);
115  badDeps = _free(badDeps);
116  }
117  badDepsInitialized = 0;
118 }
119 /*@=modobserver =observertrans @*/
120 
129 static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q)
130  /*@globals badDeps, badDepsInitialized,
131  rpmGlobalMacroContext, h_errno, internalState @*/
132  /*@modifies badDeps, badDepsInitialized,
133  rpmGlobalMacroContext, internalState @*/
134 {
135  struct badDeps_s * bdp;
136 
137  if (!badDepsInitialized) {
138  char * s = rpmExpand("%{?_dependency_whiteout}", NULL);
139  const char ** av = NULL;
140 #ifdef REFERENCE
141  int msglvl = (rpmtsDFlags(ts) & RPMDEPS_FLAG_DEPLOOPS)
143 #else
144  int anaconda = rpmtsDFlags(ts) & RPMDEPS_FLAG_ANACONDA;
145  int msglvl = (anaconda || (rpmtsDFlags(ts) & RPMDEPS_FLAG_DEPLOOPS))
147 #endif
148  int ac = 0;
149  int i;
150 
151  if (s != NULL && *s != '\0'
152  && !(i = poptParseArgvString(s, &ac, (const char ***)&av))
153  && ac > 0 && av != NULL)
154  {
155  bdp = badDeps = (struct badDeps_s *)xcalloc(ac+1, sizeof(*badDeps));
156  for (i = 0; i < ac; i++, bdp++) {
157  char * pname, * qname;
158 
159  if (av[i] == NULL)
160  break;
161  pname = xstrdup(av[i]);
162  if ((qname = strchr(pname, '>')) != NULL)
163  *qname++ = '\0';
164  bdp->pname = pname;
165 /*@-usereleased@*/
166  bdp->qname = qname;
167 /*@=usereleased@*/
168  rpmlog(msglvl,
169  _("ignore package name relation(s) [%d]\t%s -> %s\n"),
170  i, bdp->pname, (bdp->qname ? bdp->qname : "???"));
171  }
172  bdp->pname = NULL;
173  bdp->qname = NULL;
174  }
175  av = _free(av);
176  s = _free(s);
177  badDepsInitialized++;
178  }
179 
180 /*@-compdef@*/
181  if (badDeps != NULL)
182  for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) {
183  if (!strcmp(rpmteN(p), bdp->pname) && !strcmp(rpmteN(q), bdp->qname))
184  return 1;
185  }
186  return 0;
187 /*@=compdef@*/
188 }
189 
190 #ifdef REFERENCE
191 static void rpmTSIFree(tsortInfo tsi)
192 {
193  relation rel;
194 
195  while (tsi->tsi_relations != NULL) {
196  rel = tsi->tsi_relations;
197  tsi->tsi_relations = tsi->tsi_relations->rel_next;
198  rel = _free(rel);
199  }
200  while (tsi->tsi_forward_relations != NULL) {
201  rel = tsi->tsi_forward_relations;
202  tsi->tsi_forward_relations = \
203  tsi->tsi_forward_relations->rel_next;
204  rel = _free(rel);
205  }
206 }
207 
208 static inline int addSingleRelation(rpmte p,
209  rpmte q,
210  rpmsenseFlags dsflags)
211 {
212  struct tsortInfo_s *tsi_p, *tsi_q;
213  relation rel;
214  rpmElementType teType = rpmteType(p);
216 
217  /* Avoid deps outside this transaction and self dependencies */
218  if (q == NULL || q == p)
219  return 0;
220 
221  /* Erasures are reversed installs. */
222  if (teType == TR_REMOVED) {
223  rpmte r = p;
224  p = q;
225  q = r;
226  flags = isErasePreReq(dsflags);
227  } else {
228  flags = isInstallPreReq(dsflags);
229  }
230 
231  /* map legacy prereq to pre/preun as needed */
232  if (isLegacyPreReq(dsflags)) {
233  flags |= (teType == TR_ADDED) ?
234  RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
235  }
236 
237  tsi_p = rpmteTSI(p);
238  tsi_q = rpmteTSI(q);
239 
240  /* if relation got already added just update the flags */
241  if (tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == tsi_p) {
242  tsi_q->tsi_relations->rel_flags |= flags;
243  tsi_p->tsi_forward_relations->rel_flags |= flags;
244  return 0;
245  }
246 
247  /* Record next "q <- p" relation (i.e. "p" requires "q"). */
248  if (p != q) {
249  /* bump p predecessor count */
250  tsi_p->tsi_count++;
251  }
252 
253  rel = (relation) xcalloc(1, sizeof(*rel));
254  rel->rel_suc = tsi_p;
255  rel->rel_flags = flags;
256 
257  rel->rel_next = tsi_q->tsi_relations;
258  tsi_q->tsi_relations = rel;
259  if (p != q) {
260  /* bump q successor count */
261  tsi_q->tsi_qcnt++;
262  }
263 
264  rel = (relation) xcalloc(1, sizeof(*rel));
265  rel->rel_suc = tsi_q;
266  rel->rel_flags = flags;
267 
268  rel->rel_next = tsi_p->tsi_forward_relations;
269  tsi_p->tsi_forward_relations = rel;
270 
271  return 0;
272 }
273 #endif /* REFERENCE */
274 
280 static void markLoop(/*@special@*/ tsortInfo tsi, rpmte q)
281  /*@globals internalState @*/
282  /*@uses tsi @*/
283  /*@modifies internalState @*/
284 {
285  rpmte p;
286 
287  while (tsi != NULL && (p = tsi->tsi_suc) != NULL) {
288  tsi = tsi->tsi_next;
289  if (rpmteTSI(p)->tsi_chain != NULL)
290  continue;
291  /*@-assignexpose -temptrans@*/
292  rpmteTSI(p)->tsi_chain = q;
293  /*@=assignexpose =temptrans@*/
294  if (rpmteTSI(p)->tsi_next != NULL)
295  markLoop(rpmteTSI(p)->tsi_next, p);
296  }
297 }
298 
299 /*
300  * Return display string a dependency, adding contextual flags marker.
301  * @param f dependency flags
302  * @return display string
303  */
304 static inline /*@observer@*/ const char * identifyDepend(rpmuint32_t f)
305  /*@*/
306 {
307  f = _notpre(f);
308  if (f & RPMSENSE_SCRIPT_PRE)
309  return "Requires(pre):";
310  if (f & RPMSENSE_SCRIPT_POST)
311  return "Requires(post):";
312  if (f & RPMSENSE_SCRIPT_PREUN)
313  return "Requires(preun):";
314  if (f & RPMSENSE_SCRIPT_POSTUN)
315  return "Requires(postun):";
316  if (f & RPMSENSE_SCRIPT_VERIFY)
317  return "Requires(verify):";
318  if (f & RPMSENSE_MISSINGOK)
319  return "Requires(hint):";
320  if (f & RPMSENSE_FIND_REQUIRES)
321  return "Requires(auto):";
322  return "Requires:";
323 }
324 
337 /*@-mustmod@*/ /* FIX: hack modifies, but -type disables */
338 static /*@owned@*/ /*@null@*/ const char *
340  int zap, /*@in@*/ /*@out@*/ int * nzaps, int msglvl)
341  /*@globals rpmGlobalMacroContext, h_errno, internalState @*/
342  /*@modifies q, p, *nzaps, rpmGlobalMacroContext, internalState @*/
343 {
344  rpmds requires;
345  tsortInfo tsi_prev;
346  tsortInfo tsi;
347  const char *dp = NULL;
348 
349  for (tsi_prev = rpmteTSI(q), tsi = rpmteTSI(q)->tsi_next;
350  tsi != NULL;
351  /* XXX Note: the loop traverses "not found", break on "found". */
352  /*@-nullderef@*/
353  tsi_prev = tsi, tsi = tsi->tsi_next)
354  /*@=nullderef@*/
355  {
356  rpmuint32_t Flags;
357 
358  /*@-abstractcompare@*/
359  if (tsi->tsi_suc != p)
360  continue;
361  /*@=abstractcompare@*/
362 
363  requires = rpmteDS((rpmteType(p) == TR_REMOVED ? q : p), tsi->tsi_tagn);
364  if (requires == NULL) continue; /* XXX can't happen */
365 
366  (void) rpmdsSetIx(requires, tsi->tsi_reqx);
367 
368  Flags = rpmdsFlags(requires);
369 
370  dp = rpmdsNewDNEVR( identifyDepend(Flags), requires);
371 
372  /*
373  * Attempt to unravel a dependency loop by eliminating Requires's.
374  */
375  if (zap) {
376  rpmlog(msglvl,
377  _("removing %s \"%s\" from tsort relations.\n"),
378  (rpmteNEVRA(p) ? rpmteNEVRA(p) : "???"), dp);
379  rpmteTSI(p)->tsi_count--;
380  if (tsi_prev) tsi_prev->tsi_next = tsi->tsi_next;
381  tsi->tsi_next = NULL;
382  tsi->tsi_suc = NULL;
383  tsi = _free(tsi);
384  if (nzaps)
385  (*nzaps)++;
386  if (zap)
387  zap--;
388  }
389  /* XXX Note: the loop traverses "not found", get out now! */
390  break;
391  }
392  return dp;
393 }
394 /*@=mustmod@*/
395 
396 #ifdef REFERENCE
397 
404 static inline int addRelation(rpmts ts,
405  rpmal al,
406  rpmte p,
407  rpmds requires)
408 {
409  rpmte q;
410  ARGV_const_t qcolls;
411  rpmsenseFlags dsflags;
412 
413  dsflags = rpmdsFlags(requires);
414 
415  /* Avoid dependendencies which are not relevant for ordering */
416  if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG|RPMSENSE_PRETRANS))
417  return 0;
418 
419  q = rpmalSatisfiesDepend(al, requires);
420 
421  /* Avoid deps outside this transaction and self dependencies */
422  if (q == NULL || q == p)
423  return 0;
424 
425  /* Avoid certain dependency relations. */
426  if (ignoreDep(ts, p, q))
427  return 0;
428 
429  addSingleRelation(p, q, dsflags);
430 
431  /* If q is a member of any collections, make sure p requires all packages
432  * that are also in those collections */
433  for (qcolls = rpmteCollections(q); qcolls && *qcolls; qcolls++) {
434  rpmte *te;
435  rpmte *tes = rpmalAllInCollection(al, *qcolls);
436  for (te = tes; te && *te; te++) {
437  addSingleRelation(p, *te, RPMSENSE_SCRIPT_PRE);
438  }
439  _free(tes);
440  }
441 
442  return 0;
443 }
444 #endif /* REFERENCE */
445 
454 static inline int orgrpmAddRelation(rpmts ts,
455  rpmal al,
456  rpmte p,
457  rpmds requires)
458 {
459  rpmte q;
460  struct tsortInfo_s * tsi_p, * tsi_q;
461  relation rel;
462  const char * N = rpmdsN(requires);
463  rpmElementType teType = rpmteType(p);
465  rpmsenseFlags dsflags;
466 
467 #ifdef REFERENCE
468  if (N == NULL)
469  return 0;
470 
471  dsflags = rpmdsFlags(requires);
472 
473  /* Avoid rpmlib feature and package config dependencies */
474  if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG))
475  return 0;
476 
477  q = rpmalSatisfiesDepend(al, requires);
478 #else
479  rpmtsi qi;
480  fnpyKey key;
481  alKey pkgKey;
482  int i = 0;
483 
484  dsflags = rpmdsFlags(requires);
485 
486  /* Avoid certain NS dependencies. */
487  switch (rpmdsNSType(requires)) {
488  default:
489  break;
490  case RPMNS_TYPE_RPMLIB:
491  case RPMNS_TYPE_CONFIG:
492  case RPMNS_TYPE_CPUINFO:
493  case RPMNS_TYPE_GETCONF:
494  case RPMNS_TYPE_UNAME:
495  case RPMNS_TYPE_SONAME:
496  case RPMNS_TYPE_ACCESS:
497  case RPMNS_TYPE_USER:
498  case RPMNS_TYPE_GROUP:
499  case RPMNS_TYPE_MOUNTED:
501  case RPMNS_TYPE_DIGEST:
502  case RPMNS_TYPE_GNUPG:
503  case RPMNS_TYPE_MACRO:
504  case RPMNS_TYPE_ENVVAR:
505  case RPMNS_TYPE_RUNNING:
506  case RPMNS_TYPE_SANITY:
507  case RPMNS_TYPE_VCHECK:
509  return 0;
510  /*@notreached@*/ break;
511  }
512 
513 #ifndef NOTYET
514  /* Avoid looking up files/directories that are "owned" by _THIS_ package. */
515  if (*N == '/') {
517  rpmbf bf = rpmfiFNBF(fi);
518  if (bf != NULL && rpmbfChk(bf, N, strlen(N)) > 0)
519  return 0;
520  }
521 #endif
522 
523  pkgKey = RPMAL_NOMATCH;
524  key = rpmalSatisfiesDepend(al, requires, &pkgKey);
525 
526  /* Ordering depends only on added/erased package relations. */
527  if (pkgKey == RPMAL_NOMATCH)
528  return 0;
529 
530 /* XXX Set q to the added/removed package that was found. */
531  /* XXX pretend erasedPackages are just appended to addedPackages. */
532  if (teType == TR_REMOVED)
533  pkgKey = (alKey)(((long)pkgKey) + ts->numAddedPackages);
534 
535  for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) {
536  if (pkgKey == rpmteAddedKey(q))
537  break;
538  }
539  qi = rpmtsiFree(qi);
540 #endif
541 
542  /* Avoid deps outside this transaction and self dependencies */
543  if (q == NULL || q == p)
544  return 0;
545 
546  /* Avoid certain dependency relations. */
547  if (ignoreDep(ts, p, q))
548  return 0;
549 
550  /* Erasures are reversed installs. */
551  if (teType == TR_REMOVED) {
552  rpmte r = p;
553  p = q;
554  q = r;
555  flags = isErasePreReq(dsflags);
556  } else {
557  flags = isInstallPreReq(dsflags);
558  }
559 
560 #ifndef DYING
561 #define isLegacyPreReq(_x) (((_x) & _ALL_REQUIRES_MASK) == RPMSENSE_PREREQ)
562  /* map legacy prereq to pre/preun as needed */
563  if (isLegacyPreReq(dsflags)) {
564  flags |= (teType == TR_ADDED) ?
565  RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
566  }
567 #undef isLegacyPreReq
568 #endif
569 
570  tsi_p = rpmteTSI(p);
571  tsi_q = rpmteTSI(q);
572 
573  /* if relation got already added just update the flags */
574  if (tsi_q->tsi_relations && tsi_q->tsi_relations->rel_suc == p) {
575  tsi_q->tsi_relations->rel_flags |= flags;
576  tsi_p->tsi_forward_relations->rel_flags |= flags;
577  return 0;
578  }
579 
580  /* Record next "q <- p" relation (i.e. "p" requires "q"). */
581  if (p != q) {
582  /* bump p predecessor count */
583  rpmteTSI(p)->tsi_count++;
584  }
585 
586  /* Save max. depth in dependency tree */
587  if (rpmteDepth(p) <= rpmteDepth(q))
588  (void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
589  if (rpmteDepth(p) > ts->maxDepth)
590  ts->maxDepth = rpmteDepth(p);
591 
592  rel = (relation) xcalloc(1, sizeof(*rel));
593  rel->rel_suc = p;
594  rel->rel_flags = flags;
595 
596  rel->rel_next = rpmteTSI(q)->tsi_relations;
597  rpmteTSI(q)->tsi_relations = rel;
598  if (p != q) {
599  /* bump q successor count */
600  rpmteTSI(q)->tsi_qcnt++;
601  }
602 
603  rel = (relation) xcalloc(1, sizeof(*rel));
604  rel->rel_suc = q;
605  rel->rel_flags = flags;
606 
607  rel->rel_next = rpmteTSI(p)->tsi_forward_relations;
608  rpmteTSI(p)->tsi_forward_relations = rel;
609 
610  return 0;
611 }
612 
622 /*@-mustmod@*/
623 static inline int addRelation(rpmts ts, rpmal al,
624  /*@dependent@*/ rpmte p,
625  unsigned char * selected,
626  rpmds requires)
627  /*@globals rpmGlobalMacroContext, h_errno, fileSystem, internalState @*/
628  /*@modifies ts, p, *selected, rpmGlobalMacroContext,
629  fileSystem, internalState @*/
630 {
631  rpmtsi qi; rpmte q;
632  tsortInfo tsi;
633  const char * N = rpmdsN(requires);
634  fnpyKey key;
635  int teType = rpmteType(p);
636  alKey pkgKey;
637  int i = 0;
638 
639  /* Avoid certain NS dependencies. */
640  switch (rpmdsNSType(requires)) {
641  default:
642  break;
643  case RPMNS_TYPE_RPMLIB:
644  case RPMNS_TYPE_CONFIG:
645  case RPMNS_TYPE_CPUINFO:
646  case RPMNS_TYPE_GETCONF:
647  case RPMNS_TYPE_UNAME:
648  case RPMNS_TYPE_SONAME:
649  case RPMNS_TYPE_ACCESS:
650  case RPMNS_TYPE_USER:
651  case RPMNS_TYPE_GROUP:
652  case RPMNS_TYPE_MOUNTED:
654  case RPMNS_TYPE_DIGEST:
655  case RPMNS_TYPE_GNUPG:
656  case RPMNS_TYPE_MACRO:
657  case RPMNS_TYPE_ENVVAR:
658  case RPMNS_TYPE_RUNNING:
659  case RPMNS_TYPE_SANITY:
660  case RPMNS_TYPE_VCHECK:
662  return 0;
663  /*@notreached@*/ break;
664  }
665 
666  /* Avoid looking up files/directories that are "owned" by _THIS_ package. */
667  if (*N == '/') {
669  rpmbf bf = rpmfiFNBF(fi);
670  if (bf != NULL && rpmbfChk(bf, N, strlen(N)) > 0)
671  return 0;
672  }
673 
674  pkgKey = RPMAL_NOMATCH;
675  key = rpmalSatisfiesDepend(al, requires, &pkgKey);
676 
677  /* Ordering depends only on added/erased package relations. */
678  if (pkgKey == RPMAL_NOMATCH)
679  return 0;
680 
681 /* XXX Set q to the added/removed package that was found. */
682  /* XXX pretend erasedPackages are just appended to addedPackages. */
683  if (teType == TR_REMOVED)
684  pkgKey = (alKey)(((long)pkgKey) + ts->numAddedPackages);
685 
686  for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) {
687  if (pkgKey == rpmteAddedKey(q))
688  break;
689  }
690  qi = rpmtsiFree(qi);
691  if (q == NULL || i >= ts->orderCount)
692  return 0;
693 
694  /* Avoid certain dependency relations. */
695  if (ignoreDep(ts, p, q))
696  return 0;
697 
698  /* Avoid redundant relations. */
699  if (selected[i] != 0)
700  return 0;
701  selected[i] = 1;
702 
703  /* Erasures are reversed installs. */
704  if (teType == TR_REMOVED) {
705  rpmte r = p;
706  p = q;
707  q = r;
708  }
709 
710  /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
711  rpmteTSI(p)->tsi_count++; /* bump p predecessor count */
712 
713  if (rpmteDepth(p) <= rpmteDepth(q)) /* Save max. depth in dependency tree */
714  (void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
715  if (rpmteDepth(p) > ts->maxDepth)
716  ts->maxDepth = rpmteDepth(p);
717 
718  tsi = (tsortInfo) xcalloc(1, sizeof(*tsi));
719  tsi->tsi_suc = p;
720 
721  tsi->tsi_tagn = rpmdsTagN(requires);
722  tsi->tsi_reqx = rpmdsIx(requires);
723 
724  tsi->tsi_next = rpmteTSI(q)->tsi_next;
725  rpmteTSI(q)->tsi_next = tsi;
726  rpmteTSI(q)->tsi_qcnt++; /* bump q successor count */
727 
728  return 0;
729 }
730 /*@=mustmod@*/
731 
738 static int orderListIndexCmp(const void * one, const void * two) /*@*/
739 {
740  /*@-castexpose@*/
741  long a = (long) ((const orderListIndex)one)->pkgKey;
742  long b = (long) ((const orderListIndex)two)->pkgKey;
743  /*@=castexpose@*/
744  return (a - b);
745 }
746 
747 #ifdef REFERENCE
748 
755 static void addQ(tsortInfo p, tsortInfo * qp, tsortInfo * rp,
756  rpm_color_t prefcolor)
757 {
758  tsortInfo q, qprev;
759 
760  /* Mark the package as queued. */
761  p->tsi_reqx = 1;
762 
763  if ((*rp) == NULL) { /* 1st element */
764  /* FIX: double indirection */
765  (*rp) = (*qp) = p;
766  return;
767  }
768 
769  /* Find location in queue using metric tsi_qcnt. */
770  for (qprev = NULL, q = (*qp);
771  q != NULL;
772  qprev = q, q = q->tsi_suc)
773  {
774  /* XXX Insure preferred color first. */
775  if (rpmteColor(p->te) != prefcolor && rpmteColor(p->te) != rpmteColor(q->te))
776  continue;
777 
778  if (q->tsi_qcnt <= p->tsi_qcnt)
779  break;
780  }
781 
782  if (qprev == NULL) { /* insert at beginning of list */
783  p->tsi_suc = q;
784  (*qp) = p; /* new head */
785  } else if (q == NULL) { /* insert at end of list */
786  qprev->tsi_suc = p;
787  (*rp) = p; /* new tail */
788  } else { /* insert between qprev and q */
789  p->tsi_suc = q;
790  qprev->tsi_suc = p;
791  }
792 }
793 #endif /* REFERENCE */
794 
802 static void addQ(/*@dependent@*/ rpmte p,
803  /*@in@*/ /*@out@*/ rpmte * qp,
804  /*@in@*/ /*@out@*/ rpmte * rp,
805  rpmuint32_t prefcolor)
806  /*@modifies p, *qp, *rp @*/
807 {
808  rpmte q, qprev;
809 
810 #ifdef REFERENCE
811  /* Mark the package as queued. */
812  rpmteTSI(p)->tsi_reqx = 1;
813 #endif /* REFERENCE */
814 
815  if ((*rp) == NULL) { /* 1st element */
816  (*rp) = (*qp) = p;
817  return;
818  }
819 
820  /* Find location in queue using metric tsi_qcnt. */
821  for (qprev = NULL, q = (*qp);
822  q != NULL;
823  qprev = q, q = rpmteTSI(q)->tsi_suc)
824  {
825  /* XXX Insure preferred color first. */
826  if (rpmteColor(p) != prefcolor && rpmteColor(p) != rpmteColor(q))
827  continue;
828 
829 #ifdef REFERENCE
830 #else /* REFERENCE */
831  /* XXX Insure removed after added. */
832  if (rpmteType(p) == TR_REMOVED && rpmteType(p) != rpmteType(q))
833  continue;
834 
835  /* XXX Follow all previous generations in the queue. */
836  if (rpmteTSI(p)->tsi_queued > rpmteTSI(q)->tsi_queued)
837  continue;
838 #endif /* REFERENCE */
839 
840  /* XXX Within a generation, queue behind more "important". */
841  if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
842  break;
843  }
844 
845  if (qprev == NULL) { /* insert at beginning of list */
846  rpmteTSI(p)->tsi_suc = q;
847  (*qp) = p; /* new head */
848  } else if (q == NULL) { /* insert at end of list */
849  rpmteTSI(qprev)->tsi_suc = p;
850  (*rp) = p; /* new tail */
851  } else { /* insert between qprev and q */
852  rpmteTSI(p)->tsi_suc = q;
853  rpmteTSI(qprev)->tsi_suc = p;
854  }
855 }
856 
857 /*@unchecked@*/
858 #ifdef NOTYET
859 static rpmuint32_t _autobits = _notpre(_ALL_REQUIRES_MASK);
860 #else
861 static rpmuint32_t _autobits = 0xffffffff;
862 #endif
863 #define isAuto(_x) ((_x) & _autobits)
864 
865 typedef struct sccData_s {
866  int index; /* DFS node number counter */
867 #ifdef REFERENCE
868  tsortInfo *stack; /* Stack of nodes */
869 #else
870  rpmte * stack; /* Stack of nodes */
871 #endif
872  int stackcnt; /* Stack top counter */
873  scc SCCs; /* Array of SCC's found */
874  int sccCnt; /* Number of SCC's found */
875 } * sccData;
876 
877 #ifdef REFERENCE
878 static void tarjan(sccData sd, tsortInfo tsi)
879 {
880  tsortInfo tsi_q;
881  relation rel;
882 
883  /* use negative index numbers */
884  sd->index--;
885  /* Set the depth index for p */
886  tsi->tsi_SccIdx = sd->index;
887  tsi->tsi_SccLowlink = sd->index;
888 
889  sd->stack[sd->stackcnt++] = tsi; /* Push p on the stack */
890  for (rel = tsi->tsi_relations; rel != NULL; rel = rel->rel_next) {
891  /* Consider successors of p */
892  tsi_q = rel->rel_suc;
893  if (tsi_q->tsi_SccIdx > 0)
894  /* Ignore already found SCCs */
895  continue;
896  if (tsi_q->tsi_SccIdx == 0) {
897  /* Was successor q not yet visited? */
898  tarjan(sd, tsi_q); /* Recurse */
899  /* negative index numbers: use max as it is closer to 0 */
900  tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink)
901  ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink;
902  } else {
903  tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx)
904  ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx;
905  }
906  }
907 
908  if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
909  /* v is the root of an SCC? */
910  if (sd->stack[sd->stackcnt-1] == tsi) {
911  /* ignore trivial SCCs */
912  tsi_q = sd->stack[--sd->stackcnt];
913  tsi_q->tsi_SccIdx = 1;
914  } else {
915  int stackIdx = sd->stackcnt;
916  do {
917  tsi_q = sd->stack[--stackIdx];
918  tsi_q->tsi_SccIdx = sd->sccCnt;
919  } while (tsi_q != tsi);
920 
921  stackIdx = sd->stackcnt;
922  do {
923  tsi_q = sd->stack[--stackIdx];
924  /* Calculate count for the SCC */
925  sd->SCCs[sd->sccCnt].count += tsi_q->tsi_count;
926  /* Subtract internal relations */
927  for (rel=tsi_q->tsi_relations; rel != NULL; rel=rel->rel_next) {
928  if (rel->rel_suc != tsi_q
929  && rel->rel_suc->tsi_SccIdx == sd->sccCnt)
930  sd->SCCs[sd->sccCnt].count--;
931  }
932  } while (tsi_q != tsi);
933  sd->SCCs[sd->sccCnt].size = sd->stackcnt - stackIdx;
934  /* copy members */
935  sd->SCCs[sd->sccCnt].members =
936  (tsortInfo *) xcalloc(sd->SCCs[sd->sccCnt].size, sizeof(tsortInfo));
937  memcpy(sd->SCCs[sd->sccCnt].members, sd->stack + stackIdx,
938  sd->SCCs[sd->sccCnt].size * sizeof(tsortInfo));
939  sd->stackcnt = stackIdx;
940  sd->sccCnt++;
941  }
942  }
943 }
944 #else /* REFERENCE */
945 static void tarjan(sccData sd, rpmte p)
946 {
947  tsortInfo tsi = rpmteTSI(p);
948  rpmte q;
949  tsortInfo tsi_q;
950  relation rel;
951 
952  /* use negative index numbers */
953  sd->index--;
954  /* Set the depth index for p */
955  tsi->tsi_SccIdx = sd->index;
956  tsi->tsi_SccLowlink = sd->index;
957 
958  sd->stack[sd->stackcnt++] = p; /* Push p on the stack */
959  for (rel = tsi->tsi_relations; rel != NULL; rel = rel->rel_next) {
960  /* Consider successors of p */
961  q = rel->rel_suc;
962  tsi_q = rpmteTSI(q);
963  if (tsi_q->tsi_SccIdx > 0)
964  /* Ignore already found SCCs */
965  continue;
966  if (tsi_q->tsi_SccIdx == 0) {
967  /* Was successor q not yet visited? */
968  tarjan(sd, q); /* Recurse */
969  /* negative index numbers: use max as it is closer to 0 */
970  tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink)
971  ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink;
972  } else {
973  tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx)
974  ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx;
975  }
976  }
977 
978  if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
979  /* v is the root of an SCC? */
980  if (sd->stack[sd->stackcnt-1] == p) {
981  /* ignore trivial SCCs */
982  q = sd->stack[--sd->stackcnt];
983  tsi_q = rpmteTSI(q);
984  tsi_q->tsi_SccIdx = 1;
985  } else {
986  int stackIdx = sd->stackcnt;
987  do {
988  q = sd->stack[--stackIdx];
989  tsi_q = rpmteTSI(q);
990  tsi_q->tsi_SccIdx = sd->sccCnt;
991  } while (q != p);
992 
993  stackIdx = sd->stackcnt;
994  do {
995  q = sd->stack[--stackIdx];
996  tsi_q = rpmteTSI(q);
997  /* Calculate count for the SCC */
998  sd->SCCs[sd->sccCnt].count += tsi_q->tsi_count;
999  /* Subtract internal relations */
1000  for (rel=tsi_q->tsi_relations; rel != NULL; rel=rel->rel_next) {
1001  if (rel->rel_suc != q
1002  && rpmteTSI(rel->rel_suc)->tsi_SccIdx == sd->sccCnt)
1003  sd->SCCs[sd->sccCnt].count--;
1004  }
1005  } while (q != p);
1006  sd->SCCs[sd->sccCnt].size = sd->stackcnt - stackIdx;
1007  /* copy members */
1008  sd->SCCs[sd->sccCnt].members =
1009  (rpmte *) xcalloc(sd->SCCs[sd->sccCnt].size, sizeof(rpmte));
1010  memcpy(sd->SCCs[sd->sccCnt].members, sd->stack + stackIdx,
1011  sd->SCCs[sd->sccCnt].size * sizeof(rpmte));
1012  sd->stackcnt = stackIdx;
1013  sd->sccCnt++;
1014  }
1015  }
1016 }
1017 #endif /* REFERENCE */
1018 
1019 /* Search for SCCs and return an array last entry has a .size of 0 */
1020 #ifdef REFERENCE
1021 static scc detectSCCs(tsortInfo orderInfo, int nelem, int debugloops)
1022 #else /* REFERENCE */
1023 static scc detectSCCs(rpmts ts)
1024 #endif /* REFERENCE */
1025 {
1026 int nelem = ts->orderCount;
1027  scc _SCCs = (scc) xcalloc(nelem+3, sizeof(*_SCCs));
1028 #ifdef REFERENCE
1029  tsortInfo *_stack = (tsortInfo *) xcalloc(nelem, sizeof(*_stack));
1030 #else
1031  rpmte * _stack = (rpmte *) xcalloc(nelem , sizeof(*_stack));
1032 #endif
1033  struct sccData_s sd = { 0, _stack, 0, _SCCs, 2 };
1034 
1035 #ifdef REFERENCE
1036  for (int i = 0; i < nelem; i++) {
1037  tsortInfo tsi = &orderInfo[i];
1038  /* Start a DFS at each node */
1039  if (tsi->tsi_SccIdx == 0)
1040  tarjan(&sd, tsi);
1041  }
1042 #else /* REFERENCE */
1043  { rpmtsi pi;
1044  rpmte p;
1045 
1046  pi = rpmtsiInit(ts);
1047  while ((p = rpmtsiNext(pi, 0)) != NULL) {
1048  /* Start a DFS at each node */
1049  if (rpmteTSI(p)->tsi_SccIdx == 0)
1050  tarjan(&sd, p);
1051  }
1052  pi = rpmtsiFree(pi);
1053  }
1054 #endif /* REFERENCE */
1055 
1056  sd.stack = _free(sd.stack);
1057 
1058  sd.SCCs = (scc) xrealloc(sd.SCCs, (sd.sccCnt+1)*sizeof(*sd.SCCs));
1059 
1060  /* Debug output */
1061  if (sd.sccCnt > 2) {
1062 #ifdef REFERENCE
1063 int debugloops = (rpmtsDFlags(ts) & RPMDEPS_FLAG_DEPLOOPS);
1064  int msglvl = debugloops ? RPMLOG_WARNING : RPMLOG_DEBUG;
1065 #else /* REFERENCE */
1066 int debugloops = (rpmtsDFlags(ts) & (RPMDEPS_FLAG_ANACONDA|RPMDEPS_FLAG_DEPLOOPS));
1067  rpmlogLvl msglvl = debugloops ? RPMLOG_WARNING : RPMLOG_ERR;
1068  int i, j;
1069 #endif /* REFERENCE */
1070 
1071  rpmlog(msglvl, "%d Strongly Connected Components\n", sd.sccCnt-2);
1072  for (i = 2; i < sd.sccCnt; i++) {
1073  rpmlog(msglvl, "SCC #%d: requires %d packages\n",
1074  i, sd.SCCs[i].count);
1075  /* loop over members */
1076  for (j = 0; j < sd.SCCs[i].size; j++) {
1077 #ifdef REFERENCE
1078  tsortInfo member = SCCs[i].members[j];
1079  rpmlog(msglvl, "\t%s\n", rpmteNEVRA(member->te));
1080  /* show relations between members */
1081  relation rel = member->tsi_forward_relations;
1082  for (; rel != NULL; rel=rel->rel_next) {
1083  if (rel->rel_suc->tsi_SccIdx!=i) continue;
1084  rpmlog(msglvl, "\t\t%s %s\n",
1085  rel->rel_flags ? "=>" : "->",
1086  rpmteNEVRA(rel->rel_suc->te));
1087  }
1088 #else /* REFERENCE */
1089  /* show relations between members */
1090  rpmte member = sd.SCCs[i].members[j];
1091  rpmlog(msglvl, "\t%s\n", rpmteNEVRA(sd.SCCs[i].members[j]));
1092  relation rel = rpmteTSI(member)->tsi_forward_relations;
1093  for (; rel != NULL; rel=rel->rel_next) {
1094  if (rpmteTSI(rel->rel_suc)->tsi_SccIdx!=i) continue;
1095  rpmlog(msglvl, "\t\t%s %s\n",
1096  rel->rel_flags ? "=>" : "->",
1097  rpmteNEVRA(rel->rel_suc));
1098  }
1099 #endif /* REFERENCE */
1100  }
1101  }
1102  }
1103 
1104  return sd.SCCs;
1105 }
1106 
1107 #ifdef REFERENCE
1108 static void collectTE(rpm_color_t prefcolor, tsortInfo q,
1109  rpmte * newOrder, int * newOrderCount,
1110  scc SCCs,
1111  tsortInfo * queue_end,
1112  tsortInfo * outer_queue,
1113  tsortInfo * outer_queue_end)
1114 {
1115  char deptypechar = (rpmteType(q->te) == TR_REMOVED ? '-' : '+');
1116 
1117  if (rpmIsDebug()) {
1118  int depth = 1;
1119  /* figure depth in tree for nice formatting */
1120  for (rpmte p = q->te; (p = rpmteParent(p)); depth++) {}
1121  rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d %*s%c%s\n",
1122  *newOrderCount, q->tsi_count, q->tsi_qcnt,
1123  depth, (2 * depth), "",
1124  deptypechar, rpmteNEVRA(q->te));
1125  }
1126 
1127  newOrder[*newOrderCount] = q->te;
1128  (*newOrderCount)++;
1129 
1130  /* T6. Erase relations. */
1131  for (relation rel = q->tsi_relations; rel != NULL; rel = rel->rel_next) {
1132  tsortInfo p = rel->rel_suc;
1133  /* ignore already collected packages */
1134  if (p->tsi_SccIdx == 0) continue;
1135  if (p == q) continue;
1136 
1137  if (p && (--p->tsi_count) == 0) {
1138  (void) rpmteSetParent(p->te, q->te);
1139 
1140  if (q->tsi_SccIdx > 1 && q->tsi_SccIdx != p->tsi_SccIdx) {
1141  /* Relation point outside of this SCC: add to outside queue */
1142  assert(outer_queue != NULL && outer_queue_end != NULL);
1143  addQ(p, outer_queue, outer_queue_end, prefcolor);
1144  } else {
1145  addQ(p, &q->tsi_suc, queue_end, prefcolor);
1146  }
1147  }
1148  if (p && p->tsi_SccIdx > 1 &&
1149  p->tsi_SccIdx != q->tsi_SccIdx) {
1150  if (--SCCs[p->tsi_SccIdx].count == 0) {
1151  /* New SCC is ready, add this package as representative */
1152  (void) rpmteSetParent(p->te, q->te);
1153 
1154  if (outer_queue != NULL) {
1155  addQ(p, outer_queue, outer_queue_end, prefcolor);
1156  } else {
1157  addQ(p, &q->tsi_suc, queue_end, prefcolor);
1158  }
1159  }
1160  }
1161  }
1162  q->tsi_SccIdx = 0;
1163 }
1164 #endif /* REFERENCE */
1165 
1166 static void collectTE(rpm_color_t prefcolor, rpmte q,
1167  rpmte * newOrder, int * newOrderCount,
1168  scc SCCs,
1169  rpmte * queue_end,
1170  rpmte * outer_queue,
1171  rpmte * outer_queue_end)
1172 {
1173  int treex = rpmteTree(q);
1174  int depth = rpmteDepth(q);
1175  char deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
1176  tsortInfo tsi = rpmteTSI(q);
1177  relation rel;
1178 
1179  rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
1180  *newOrderCount, rpmteNpreds(q),
1181  rpmteTSI(q)->tsi_qcnt,
1182  treex, depth,
1183  (2 * depth), "",
1184  deptypechar,
1185  (rpmteNEVRA(q) ? rpmteNEVRA(q) : "???"));
1186 
1187  (void) rpmteSetDegree(q, 0);
1188 
1189  newOrder[*newOrderCount] = q;
1190  (*newOrderCount)++;
1191 
1192  /* T6. Erase relations. */
1193  for (rel = rpmteTSI(q)->tsi_relations; rel != NULL; rel = rel->rel_next) {
1194  rpmte p = rel->rel_suc;
1195  tsortInfo p_tsi = rpmteTSI(p);
1196 
1197  /* ignore already collected packages */
1198  if (p_tsi->tsi_SccIdx == 0) continue;
1199  if (p == q) continue;
1200 
1201  if (p && (--p_tsi->tsi_count) == 0) {
1202 
1203  (void) rpmteSetTree(p, treex);
1204  (void) rpmteSetDepth(p, depth+1);
1205  (void) rpmteSetParent(p, q);
1206  (void) rpmteSetDegree(q, rpmteDegree(q)+1);
1207 
1208  if (tsi->tsi_SccIdx > 1 && tsi->tsi_SccIdx != p_tsi->tsi_SccIdx) {
1209  /* Relation point outside of this SCC: add to outside queue */
1210  assert(outer_queue != NULL && outer_queue_end != NULL);
1211  addQ(p, outer_queue, outer_queue_end, prefcolor);
1212  } else {
1213  addQ(p, &tsi->tsi_suc, queue_end, prefcolor);
1214  }
1215  }
1216  if (p && p_tsi->tsi_SccIdx > 1 &&
1217  p_tsi->tsi_SccIdx != rpmteTSI(q)->tsi_SccIdx) {
1218  if (--SCCs[p_tsi->tsi_SccIdx].count == 0) {
1219  /* New SCC is ready, add this package as representative */
1220 
1221  (void) rpmteSetTree(p, treex);
1222  (void) rpmteSetDepth(p, depth+1);
1223  (void) rpmteSetParent(p, q);
1224  (void) rpmteSetDegree(q, rpmteDegree(q)+1);
1225 
1226  if (outer_queue != NULL) {
1227  addQ(p, outer_queue, outer_queue_end, prefcolor);
1228  } else {
1229  addQ(p, &rpmteTSI(q)->tsi_suc, queue_end, prefcolor);
1230  }
1231  }
1232  }
1233  }
1234  tsi->tsi_SccIdx = 0;
1235 }
1236 
1237 #ifdef REFERENCE
1238 static void collectSCC(rpm_color_t prefcolor, tsortInfo p_tsi,
1239  rpmte * newOrder, int * newOrderCount,
1240  scc SCCs, tsortInfo * queue_end)
1241 {
1242  int sccNr = p_tsi->tsi_SccIdx;
1243  struct scc_s SCC = SCCs[sccNr];
1244  int i;
1245  int start, end;
1246  relation rel;
1247 
1248  /* remove p from the outer queue */
1249  tsortInfo outer_queue_start = p_tsi->tsi_suc;
1250  p_tsi->tsi_suc = NULL;
1251 
1252  /*
1253  * Run a multi source Dijkstra's algorithm to find relations
1254  * that can be zapped with least danger to pre reqs.
1255  * As weight of the edges is always 1 it is not necessary to
1256  * sort the vertices by distance as the queue gets them
1257  * already in order
1258  */
1259 
1260  /* can use a simple queue as edge weights are always 1 */
1261  tsortInfo * queue = (tsortInfo *) xmalloc((SCC.size+1) * sizeof(*queue));
1262 
1263  /*
1264  * Find packages that are prerequired and use them as
1265  * starting points for the Dijkstra algorithm
1266  */
1267  start = end = 0;
1268  for (i = 0; i < SCC.size; i++) {
1269  tsortInfo tsi = SCC.members[i];
1270  tsi->tsi_SccLowlink = INT_MAX;
1271  for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
1272  if (rel->rel_flags && rel->rel_suc->tsi_SccIdx == sccNr) {
1273  if (rel->rel_suc != tsi) {
1274  tsi->tsi_SccLowlink = 0;
1275  queue[end++] = tsi;
1276  } else {
1277  tsi->tsi_SccLowlink = INT_MAX/2;
1278  }
1279  break;
1280  }
1281  }
1282  }
1283 
1284  if (start == end) { /* no regular prereqs; add self prereqs to queue */
1285  for (i = 0; i < SCC.size; i++) {
1286  tsortInfo tsi = SCC.members[i];
1287  if (tsi->tsi_SccLowlink != INT_MAX) {
1288  queue[end++] = tsi;
1289  }
1290  }
1291  }
1292 
1293  /* Do Dijkstra */
1294  while (start != end) {
1295  tsortInfo tsi = queue[start++];
1296  for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
1297  tsortInfo next_tsi = rel->rel_suc;
1298  if (next_tsi->tsi_SccIdx != sccNr) continue;
1299  if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) {
1300  next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1;
1301  queue[end++] = rel->rel_suc;
1302  }
1303  }
1304  }
1305  queue = _free(queue);
1306 
1307 
1308  while (1) {
1309  tsortInfo best = NULL;
1310  tsortInfo inner_queue_start, inner_queue_end;
1311  int best_score = 0;
1312 
1313  /* select best candidate to start with */
1314  for (int i = 0; i < SCC.size; i++) {
1315  tsortInfo tsi = SCC.members[i];
1316  if (tsi->tsi_SccIdx == 0) /* package already collected */
1317  continue;
1318  if (tsi->tsi_SccLowlink >= best_score) {
1319  best = tsi;
1320  best_score = tsi->tsi_SccLowlink;
1321  }
1322  }
1323 
1324  if (best == NULL) /* done */
1325  break;
1326 
1327  /* collect best candidate and all packages that get freed */
1328  inner_queue_start = inner_queue_end = NULL;
1329  addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
1330 
1331  for (; inner_queue_start != NULL;
1332  inner_queue_start = inner_queue_start->tsi_suc) {
1333  /* Mark the package as unqueued. */
1334  inner_queue_start->tsi_reqx = 0;
1335  collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount,
1336  SCCs, &inner_queue_end, &outer_queue_start, queue_end);
1337  }
1338  }
1339 
1340  /* restore outer queue */
1341  p_tsi->tsi_suc = outer_queue_start;
1342 }
1343 #endif /* REFERENCE */
1344 
1345 static void collectSCC(rpm_color_t prefcolor, rpmte p,
1346  rpmte * newOrder, int * newOrderCount,
1347  scc SCCs, rpmte * queue_end)
1348 {
1349  int sccNr = rpmteTSI(p)->tsi_SccIdx;
1350  struct scc_s SCC = SCCs[sccNr];
1351  int i;
1352  int start, end;
1353  relation rel;
1354 
1355  /* remove p from the outer queue */
1356  rpmte outer_queue_start = rpmteTSI(p)->tsi_suc;
1357  rpmteTSI(p)->tsi_suc = NULL;
1358 
1359  /*
1360  * Run a multi source Dijkstra's algorithm to find relations
1361  * that can be zapped with least danger to pre reqs.
1362  * As weight of the edges is always 1 it is not necessary to
1363  * sort the vertices by distance as the queue gets them
1364  * already in order
1365  */
1366 
1367  /* can use a simple queue as edge weights are always 1 */
1368  rpmte * queue = (rpmte *) xmalloc((SCC.size+1) * sizeof(rpmte));
1369 
1370  /*
1371  * Find packages that are prerequired and use them as
1372  * starting points for the Dijkstra algorithm
1373  */
1374  start = end = 0;
1375  for (i = 0; i < SCC.size; i++) {
1376  rpmte q = SCC.members[i];
1377  tsortInfo tsi = rpmteTSI(q);
1378  tsi->tsi_SccLowlink = INT_MAX;
1379  for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
1380  if (rel->rel_flags && rpmteTSI(rel->rel_suc)->tsi_SccIdx == sccNr) {
1381  if (rel->rel_suc != q) {
1382  tsi->tsi_SccLowlink = 0;
1383  queue[end++] = q;
1384  } else {
1385  tsi->tsi_SccLowlink = INT_MAX/2;
1386  }
1387  break;
1388  }
1389  }
1390  }
1391 
1392  if (start == end) { /* no regular prereqs; add self prereqs to queue */
1393  for (i = 0; i < SCC.size; i++) {
1394  rpmte q = SCC.members[i];
1395  tsortInfo tsi = rpmteTSI(q);
1396  if (tsi->tsi_SccLowlink != INT_MAX) {
1397  queue[end++] = q;
1398  }
1399  }
1400  }
1401 
1402  /* Do Dijkstra */
1403  while (start != end) {
1404  rpmte q = queue[start++];
1405  tsortInfo tsi = rpmteTSI(q);
1406  for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
1407  tsortInfo next_tsi = rpmteTSI(rel->rel_suc);
1408  if (next_tsi->tsi_SccIdx != sccNr) continue;
1409  if (next_tsi->tsi_SccLowlink > tsi->tsi_SccLowlink+1) {
1410  next_tsi->tsi_SccLowlink = tsi->tsi_SccLowlink + 1;
1411  queue[end++] = rel->rel_suc;
1412  }
1413  }
1414  }
1415  queue = _free(queue);
1416 
1417 
1418  while (1) {
1419  rpmte best = NULL;
1420  rpmte inner_queue_start, inner_queue_end;
1421  int best_score = 0;
1422  int i;
1423 
1424  /* select best candidate to start with */
1425  for (i = 0; i < SCC.size; i++) {
1426  rpmte q = SCC.members[i];
1427  tsortInfo tsi = rpmteTSI(q);
1428  if (tsi->tsi_SccIdx == 0) /* package already collected */
1429  continue;
1430  if (tsi->tsi_SccLowlink >= best_score) {
1431  best = q;
1432  best_score = tsi->tsi_SccLowlink;
1433  }
1434  }
1435 
1436  if (best == NULL) /* done */
1437  break;
1438 
1439  /* collect best candidate and all packages that get freed */
1440  inner_queue_start = inner_queue_end = NULL;
1441  addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
1442 
1443  for (; inner_queue_start != NULL;
1444  inner_queue_start = rpmteTSI(inner_queue_start)->tsi_suc) {
1445  /* Mark the package as unqueued. */
1446  rpmteTSI(inner_queue_start)->tsi_reqx = 0;
1447  collectTE(prefcolor, inner_queue_start, newOrder, newOrderCount,
1448  SCCs, &inner_queue_end, &outer_queue_start, queue_end);
1449  }
1450  }
1451 
1452  /* restore outer queue */
1453  rpmteTSI(p)->tsi_suc = outer_queue_start;
1454 }
1455 
1456 #ifdef REFERENCE
1457 int rpmtsOrder(rpmts ts)
1458 {
1459  tsMembers tsmem = rpmtsMembers(ts);
1460  rpm_color_t prefcolor = rpmtsPrefColor(ts);
1461  rpmtsi pi; rpmte p;
1462  tsortInfo q, r;
1463  rpmte * newOrder;
1464  int newOrderCount = 0;
1465  int rc;
1466  rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts), prefcolor);
1467  scc SCCs;
1468  int nelem = rpmtsNElements(ts);
1469  tsortInfo sortInfo = (tsortInfo) xcalloc(nelem, sizeof(struct tsortInfo_s));
1470 
1471  (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1472 
1473  /* Create erased package index. */
1474  pi = rpmtsiInit(ts);
1475  while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
1476  rpmalAdd(erasedPackages, p);
1477  }
1478  pi = rpmtsiFree(pi);
1479 
1480  for (int i = 0; i < nelem; i++) {
1481  sortInfo[i].te = tsmem->order[i];
1482  rpmteSetTSI(tsmem->order[i], &sortInfo[i]);
1483  }
1484 
1485  /* Record relations. */
1486  rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
1487  pi = rpmtsiInit(ts);
1488  while ((p = rpmtsiNext(pi, 0)) != NULL) {
1489  rpmal al = (rpmteType(p) == TR_REMOVED) ?
1490  erasedPackages : tsmem->addedPackages;
1491  rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME));
1492 
1493  while (rpmdsNext(requires) >= 0) {
1494  /* Record next "q <- p" relation (i.e. "p" requires "q"). */
1495  (void) addRelation(ts, al, p, requires);
1496  }
1497  }
1498  pi = rpmtsiFree(pi);
1499 
1500  newOrder = (rpmte *) xcalloc(tsmem->orderCount, sizeof(*newOrder));
1501  SCCs = detectSCCs(sortInfo, nelem, (rpmtsFlags(ts) & RPMTRANS_FLAG_DEPLOOPS));
1502 
1503  rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, depth)\n");
1504 
1505  for (int i = 0; i < 2; i++) {
1506  /* Do two separate runs: installs first - then erases */
1507  int oType = !i ? TR_ADDED : TR_REMOVED;
1508  q = r = NULL;
1509  /* Scan for zeroes and add them to the queue */
1510  for (int e = 0; e < nelem; e++) {
1511  tsortInfo p = &sortInfo[e];
1512  if (rpmteType(p->te) != oType) continue;
1513  if (p->tsi_count != 0)
1514  continue;
1515  p->tsi_suc = NULL;
1516  addQ(p, &q, &r, prefcolor);
1517  }
1518 
1519  /* Add one member of each leaf SCC */
1520  for (int i = 2; SCCs[i].members != NULL; i++) {
1521  tsortInfo member = SCCs[i].members[0];
1522  if (SCCs[i].count == 0 && rpmteType(member->te) == oType) {
1523  addQ(member, &q, &r, prefcolor);
1524  }
1525  }
1526 
1527  while (q != NULL) {
1528  /* Mark the package as unqueued. */
1529  q->tsi_reqx = 0;
1530  if (q->tsi_SccIdx > 1) {
1531  collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
1532  } else {
1533  collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
1534  NULL, NULL);
1535  }
1536  q = q->tsi_suc;
1537  }
1538  }
1539 
1540  /* Clean up tsort data */
1541  for (int i = 0; i < nelem; i++) {
1542  rpmteSetTSI(tsmem->order[i], NULL);
1543  rpmTSIFree(&sortInfo[i]);
1544  }
1545  free(sortInfo);
1546 
1547  assert(newOrderCount == tsmem->orderCount);
1548 
1549  tsmem->order = _free(tsmem->order);
1550  tsmem->order = newOrder;
1551  tsmem->orderAlloced = tsmem->orderCount;
1552  rc = 0;
1553 
1554  freeBadDeps();
1555 
1556  for (int i = 2; SCCs[i].members != NULL; i++) {
1557  free(SCCs[i].members);
1558  }
1559  free(SCCs);
1560  rpmalFree(erasedPackages);
1561 
1562  (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1563 
1564  return rc;
1565 }
1566 #endif /* REFERENCE */
1567 
1569 {
1570  rpm_color_t prefcolor = rpmtsPrefColor(ts);
1571  rpmtsi pi; rpmte p;
1572  rpmte q;
1573  rpmte r;
1574  rpmte * newOrder;
1575  int newOrderCount = 0;
1576  int treex;
1577  int rc;
1578 #ifdef REFERENCE
1579  rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts), prefcolor);
1580 #endif
1581  scc SCCs;
1582  int j;
1583  int i;
1584 
1585  (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1586 
1587  /*
1588  * XXX FIXME: this gets needlesly called twice on normal usage patterns,
1589  * should track the need for generating the index somewhere
1590  */
1591  rpmalMakeIndex(ts->addedPackages);
1592 
1593  /* Create erased package index. */
1594  pi = rpmtsiInit(ts);
1595  while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
1596 #ifdef REFERENCE
1597  rpmalAdd(ts->erasedPackages, p);
1598 #else
1599  alKey pkgKey;
1600  fnpyKey key;
1601  rpmuint32_t tscolor = rpmtsColor(ts);
1602  pkgKey = RPMAL_NOMATCH;
1603 /*@-abstract@*/
1604  key = (fnpyKey) p;
1605 /*@=abstract@*/
1606  pkgKey = rpmalAdd(&ts->erasedPackages, pkgKey, key,
1608  rpmteFI(p, RPMTAG_BASENAMES), tscolor);
1609  /* XXX pretend erasedPackages are just appended to addedPackages. */
1610  pkgKey = (alKey)(((long)pkgKey) + ts->numAddedPackages);
1611  (void) rpmteSetAddedKey(p, pkgKey);
1612 #endif
1613  }
1614  pi = rpmtsiFree(pi);
1615  rpmalMakeIndex(ts->erasedPackages);
1616 
1617  pi = rpmtsiInit(ts);
1618  while ((p = rpmtsiNext(pi, 0)) != NULL)
1619  rpmteNewTSI(p);
1620  pi = rpmtsiFree(pi);
1621 
1622  /* Record relations. */
1623  rpmlog(RPMLOG_DEBUG, "========== recording tsort relations\n");
1624  pi = rpmtsiInit(ts);
1625  while ((p = rpmtsiNext(pi, 0)) != NULL) {
1626  rpmal al = (rpmteType(p) == TR_REMOVED) ?
1627  ts->erasedPackages : ts->addedPackages;
1628  rpmds requires = rpmdsInit(rpmteDS(p, RPMTAG_REQUIRENAME));
1629 
1630  while (rpmdsNext(requires) >= 0) {
1631  /* Record next "q <- p" relation (i.e. "p" requires "q"). */
1632  (void) orgrpmAddRelation(ts, al, p, requires);
1633  }
1634 
1635 #if defined(RPM_VENDOR_PLD)
1636  /* Ensure that erasures follow installs during upgrades. */
1637  if (rpmteType(p) == TR_REMOVED && p->flink.Pkgid && p->flink.Pkgid[0]) {
1638  rpmtsi qi;
1639 
1640  qi = rpmtsiInit(ts);
1641  while ((q = rpmtsiNext(qi, TR_ADDED)) != NULL) {
1642 
1643  if (strcmp(q->pkgid, p->flink.Pkgid[0]))
1644  /*@innercontinue@*/ continue;
1645 
1646  requires = rpmdsFromPRCO(q->PRCO, RPMTAG_NAME);
1647  if (requires != NULL) {
1648  /* XXX disable erased arrow reversal. */
1649  p->type = TR_ADDED;
1650  (void) orgrpmAddRelation(ts, ts->addedPackages, p, requires);
1651  p->type = TR_REMOVED;
1652  }
1653  }
1654  qi = rpmtsiFree(qi);
1655  }
1656 #endif
1657 
1658 #ifdef NOTYET
1659  /* Order by requiring parent directories as prerequisites. */
1660  requires = rpmdsInit(rpmteDS(p, RPMTAG_DIRNAMES));
1661  if (requires != NULL)
1662  while (rpmdsNext(requires) >= 0) {
1663 
1664 #ifdef DYING
1665  /* XXX Attempt to avoid loops by filtering out deep paths. */
1666  if (countSlashes(rpmdsN(requires)) > slashDepth)
1667  /*@innercontinue@*/ continue;
1668 #endif
1669 
1670  /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1671  (void) orgrpmAddRelation(ts, al, p, requires);
1672 
1673  }
1674 #endif /* NOTYET */
1675 
1676 #ifdef NOTYET
1677  /* Order by requiring no dangling symlinks. */
1678  requires = rpmdsInit(rpmteDS(p, RPMTAG_FILELINKTOS));
1679  if (requires != NULL)
1680  while (rpmdsNext(requires) >= 0) {
1681 
1682  /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1683  (void) orgrpmAddRelation(ts, al, p, requires);
1684 
1685  }
1686 #endif /* NOTYET */
1687 
1688  }
1689  pi = rpmtsiFree(pi);
1690 
1691  /* Save predecessor count and mark tree roots. */
1692  treex = 0;
1693  pi = rpmtsiInit(ts);
1694  while ((p = rpmtsiNext(pi, 0)) != NULL) {
1695  int npreds = rpmteTSI(p)->tsi_count;
1696 
1697  (void) rpmteSetNpreds(p, npreds);
1698  (void) rpmteSetDepth(p, 1);
1699 
1700  if (npreds == 0)
1701  (void) rpmteSetTree(p, treex++);
1702  else
1703  (void) rpmteSetTree(p, -1);
1704  }
1705  pi = rpmtsiFree(pi);
1706  ts->ntrees = treex;
1707 
1708  newOrder = (rpmte *) xcalloc(ts->orderCount, sizeof(*newOrder));
1709  SCCs = detectSCCs(ts);
1710 
1711  rpmlog(RPMLOG_DEBUG, "========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n");
1712 
1713  for (j = 0; j < 2; j++) {
1714  /* Do two separate runs: installs first - then erases */
1715  unsigned oType = (j == 0 ? TR_ADDED : TR_REMOVED);
1716  q = r = NULL;
1717  pi = rpmtsiInit(ts);
1718  /* Scan for zeroes and add them to the queue */
1719  while ((p = rpmtsiNext(pi, oType)) != NULL) {
1720  if (rpmteTSI(p)->tsi_count != 0)
1721  continue;
1722  rpmteTSI(p)->tsi_suc = NULL;
1723  addQ(p, &q, &r, prefcolor);
1724  }
1725  pi = rpmtsiFree(pi);
1726 
1727  /* Add one member of each leaf SCC */
1728  for (i = 2; SCCs[i].members != NULL; i++) {
1729  if (SCCs[i].count == 0 && rpmteType(SCCs[i].members[0]) == oType) {
1730  p = SCCs[i].members[0];
1731  rpmteTSI(p)->tsi_suc = NULL;
1732  addQ(p, &q, &r, prefcolor);
1733  }
1734  }
1735 
1736  /* Process queue */
1737  for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
1738  /* Mark the package as unqueued. */
1739  rpmteTSI(q)->tsi_reqx = 0;
1740  if (rpmteTSI(q)->tsi_SccIdx > 1) {
1741  collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
1742  } else {
1743  collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
1744  NULL, NULL);
1745  }
1746  }
1747  }
1748 
1749  /* Clean up tsort data */
1750  pi = rpmtsiInit(ts);
1751  while ((p = rpmtsiNext(pi, 0)) != NULL)
1752  rpmteFreeTSI(p);
1753  pi = rpmtsiFree(pi);
1754 
1755  assert(newOrderCount == ts->orderCount);
1756 
1757  ts->order = _free(ts->order);
1758  ts->order = newOrder;
1759  ts->orderAlloced = ts->orderCount;
1760  rc = 0;
1761 
1762  for (i = 2; SCCs[i].members != NULL; i++)
1763  SCCs[i].members = _free(SCCs[i].members);
1764  SCCs = _free(SCCs);
1765 
1766 #ifdef DYING
1767  rpmalFree(ts->erasedPackages);
1768  ts->erasedPackages = NULL;
1769 #endif
1770  freeBadDeps();
1771 
1772  (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1773 
1774  return rc;
1775 }
1776 
1778 {
1779  rpmds requires;
1780  rpmuint32_t Flags;
1781 
1782  rpmuint32_t prefcolor = rpmtsPrefColor(ts);
1783  rpmtsi pi; rpmte p;
1784  rpmtsi qi; rpmte q;
1785  rpmtsi ri; rpmte r;
1786  rpmte * newOrder;
1787  int newOrderCount = 0;
1788  int treex;
1789  int rc = -1; /* assume failure */
1790  int i;
1791  int j;
1792 
1793  rpmal al;
1794 
1795 #ifdef REFERENCE
1796  rpmal erasedPackages = rpmalCreate(5, rpmtsColor(ts), prefcolor);
1797  scc SCCs;
1798 #else /* REFERENCE */
1799  rpmuint32_t tscolor = rpmtsColor(ts);
1800  int anaconda = rpmtsDFlags(ts) & RPMDEPS_FLAG_ANACONDA;
1801 
1802  tsortInfo tsi;
1803  tsortInfo tsi_next;
1804  alKey * ordering;
1805  int orderingCount = 0;
1806 
1807  unsigned char * selected = (unsigned char *) alloca(sizeof(*selected) * (ts->orderCount + 1));
1808  int loopcheck;
1809  orderListIndex orderList;
1810  int numOrderList;
1811  int npeer = 128; /* XXX more than deep enough for now. */
1812  int * peer = (int *) memset(alloca(npeer*sizeof(*peer)), 0, (npeer*sizeof(*peer)));
1813  int nrescans = 100;
1814  int _printed = 0;
1815  char deptypechar;
1816  size_t tsbytes = 0;
1817  int oType = 0;
1818  int depth;
1819  int breadth;
1820  int qlen;
1821 #endif /* REFERENCE */
1822 
1823 if (_rpmts_debug)
1824 fprintf(stderr, "--> %s(%p) tsFlags 0x%x\n", __FUNCTION__, ts, rpmtsFlags(ts));
1825 
1826  (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1827 
1828  /* Create added package index. */
1829 #ifdef REFERENCE
1830  rpmalMakeIndex(ts->addedPackages);
1831 #else
1832 #endif
1833 
1834  /* Create erased package index. */
1835  pi = rpmtsiInit(ts);
1836  while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
1837 #ifdef REFERENCE
1838  rpmalAdd(ts->erasedPackages, p);
1839 #else
1840 /*@-abstract@*/
1841  fnpyKey key = (fnpyKey) p;
1842 /*@=abstract@*/
1843  alKey pkgKey = RPMAL_NOMATCH;
1844 
1845  pkgKey = rpmalAdd(&ts->erasedPackages, pkgKey, key,
1847  rpmteFI(p, RPMTAG_BASENAMES), tscolor);
1848  /* XXX pretend erasedPackages are just appended to addedPackages. */
1849  pkgKey = (alKey)(((long)pkgKey) + ts->numAddedPackages);
1850  (void) rpmteSetAddedKey(p, pkgKey);
1851 #endif
1852  }
1853  pi = rpmtsiFree(pi);
1854  rpmalMakeIndex(ts->erasedPackages);
1855 
1856  /* T1. Initialize. */
1857 #ifdef REFERENCE
1858 #else
1859  if (oType == 0)
1860  numOrderList = ts->orderCount;
1861  else {
1862  numOrderList = 0;
1863  if (oType & TR_ADDED)
1864  numOrderList += ts->numAddedPackages;
1865  if (oType & TR_REMOVED)
1866  numOrderList += ts->numRemovedPackages;
1867  }
1868  ordering = (alKey *) alloca(sizeof(*ordering) * (numOrderList + 1));
1869  loopcheck = numOrderList;
1870 #endif
1871 
1872  pi = rpmtsiInit(ts);
1873  while ((p = rpmtsiNext(pi, oType)) != NULL)
1874  rpmteNewTSI(p);
1875  pi = rpmtsiFree(pi);
1876 
1877  /* Record all relations. */
1878  rpmlog(RPMLOG_DEBUG, D_("========== recording tsort relations\n"));
1879  pi = rpmtsiInit(ts);
1880  while ((p = rpmtsiNext(pi, oType)) != NULL) {
1881  al = (rpmteType(p) == TR_ADDED ? ts->addedPackages : ts->erasedPackages);
1882 
1883  /* T2. Next "q <- p" relation. */
1884 
1885 #ifdef REFERENCE
1886 #else
1887  memset(selected, 0, sizeof(*selected) * ts->orderCount);
1888 
1889  /* Avoid narcisstic relations. */
1890  selected[rpmtsiOc(pi)] = 1;
1891 #endif
1892 
1893  requires = rpmteDS(p, RPMTAG_REQUIRENAME);
1894  requires = rpmdsInit(requires);
1895  if (requires != NULL)
1896  while (rpmdsNext(requires) >= 0) {
1897 
1898  Flags = rpmdsFlags(requires);
1899  if (!isAuto(Flags))
1900  /*@innercontinue@*/ continue;
1901 
1902  /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1903 #ifdef REFERENCE
1904  (void) orgrpmAddRelation(ts, al, p, requires);
1905 #else
1906  (void) addRelation(ts, al, p, selected, requires);
1907 #endif
1908 
1909  }
1910 
1911 #ifdef REFERENCE
1912 #else /* REFERENCE */
1913  /* Ensure that erasures follow installs during upgrades. */
1914  if (rpmteType(p) == TR_REMOVED && p->flink.Pkgid && p->flink.Pkgid[0]) {
1915 
1916  qi = rpmtsiInit(ts);
1917  while ((q = rpmtsiNext(qi, TR_ADDED)) != NULL) {
1918 
1919  if (strcmp(q->pkgid, p->flink.Pkgid[0]))
1920  /*@innercontinue@*/ continue;
1921 
1922  requires = rpmdsFromPRCO(q->PRCO, RPMTAG_NAME);
1923  if (requires != NULL) {
1924  /* XXX disable erased arrow reversal. */
1925  p->type = TR_ADDED;
1926 #ifdef REFERENCE
1927  (void) orgrpmAddRelation(ts, ts->addedPackages, p, requires);
1928 #else
1929  (void) addRelation(ts, ts->addedPackages, p, selected, requires);
1930 #endif
1931  p->type = TR_REMOVED;
1932  }
1933  }
1934  qi = rpmtsiFree(qi);
1935  }
1936 
1937  /* Order by requiring parent directories as prerequisites. */
1938  requires = rpmdsInit(rpmteDS(p, RPMTAG_DIRNAMES));
1939  if (requires != NULL)
1940  while (rpmdsNext(requires) >= 0) {
1941 
1942  /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1943 #ifdef REFERENCE
1944  (void) orgrpmAddRelation(ts, al, p, requires);
1945 #else
1946  (void) addRelation(ts, al, p, selected, requires);
1947 #endif
1948 
1949  }
1950 
1951  /* Order by requiring no dangling symlinks. */
1952  requires = rpmdsInit(rpmteDS(p, RPMTAG_FILELINKTOS));
1953  if (requires != NULL)
1954  while (rpmdsNext(requires) >= 0) {
1955 
1956  /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1957 #ifdef REFERENCE
1958  (void) orgrpmAddRelation(ts, al, p, requires);
1959 #else
1960  (void) addRelation(ts, al, p, selected, requires);
1961 #endif
1962 
1963  }
1964 #endif /* REFERENCE */
1965  }
1966  pi = rpmtsiFree(pi);
1967 
1968  /* Save predecessor count and mark tree roots. */
1969  treex = 0;
1970  pi = rpmtsiInit(ts);
1971  while ((p = rpmtsiNext(pi, oType)) != NULL) {
1972  int npreds = rpmteTSI(p)->tsi_count;
1973 
1974  (void) rpmteSetNpreds(p, npreds);
1975 #ifdef REFERENCE
1976  (void) rpmteSetDepth(p, 1);
1977 #else
1978  (void) rpmteSetDepth(p, 0);
1979 #endif
1980 
1981  if (npreds == 0) {
1982 #ifdef REFERENCE
1983  (void) rpmteSetTree(p, treex++);
1984 #else
1985  (void) rpmteSetTree(p, ++treex);
1986  (void) rpmteSetBreadth(p, treex);
1987 #endif
1988  } else
1989  (void) rpmteSetTree(p, -1);
1990 #ifdef UNNECESSARY
1991  (void) rpmteSetParent(p, NULL);
1992 #endif
1993 
1994  }
1995  pi = rpmtsiFree(pi);
1996  ts->ntrees = treex;
1997 
1998 #ifdef REFERENCE
1999  /* Remove dependency loops. */
2000  newOrder = (rpmte *) xcalloc(ts->orderCount, sizeof(*newOrder));
2001  SCCs = detectSCCs(ts);
2002 #endif
2003 
2004  /* T4. Scan for zeroes. */
2005  rpmlog(RPMLOG_DEBUG, D_("========== tsorting packages (order, #predecessors, #succesors, tree, Ldepth, Rbreadth)\n"));
2006 
2007 #ifdef REFERENCE
2008  for (j = 0; j < 2; j++) {
2009  /* Do two separate runs: installs first - then erases */
2010  unsigned oType = (j == 0 ? TR_ADDED : TR_REMOVED);
2011 
2012 #else
2013 rescan:
2014  if (pi != NULL) pi = rpmtsiFree(pi);
2015 #endif
2016  q = r = NULL;
2017  qlen = 0;
2018  pi = rpmtsiInit(ts);
2019  while ((p = rpmtsiNext(pi, oType)) != NULL) {
2020 
2021  /* Prefer packages in chainsaw or anaconda presentation order. */
2022  if (anaconda)
2023  rpmteTSI(p)->tsi_qcnt = (ts->orderCount - rpmtsiOc(pi));
2024 
2025  if (rpmteTSI(p)->tsi_count != 0)
2026  continue;
2027 
2028  /* Mark the package as queued. */
2029  rpmteTSI(p)->tsi_queued = orderingCount + 1;
2030  rpmteTSI(p)->tsi_suc = NULL;
2031  addQ(p, &q, &r, prefcolor);
2032  qlen++;
2033  }
2034  pi = rpmtsiFree(pi);
2035 
2036  /* T5. Output front of queue (T7. Remove from queue.) */
2037  for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
2038 
2039  /* Mark the package as unqueued. */
2040  rpmteTSI(q)->tsi_queued = 0;
2041 
2042  if (oType != 0)
2043  switch (rpmteType(q)) {
2044  case TR_ADDED:
2045  if (!(oType & TR_ADDED))
2046  continue;
2047  /*@switchbreak@*/ break;
2048  case TR_REMOVED:
2049  if (!(oType & TR_REMOVED))
2050  continue;
2051  /*@switchbreak@*/ break;
2052  default:
2053  continue;
2054  /*@notreached@*/ /*@switchbreak@*/ break;
2055  }
2056  deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
2057 
2058  treex = rpmteTree(q);
2059  depth = rpmteDepth(q);
2060  breadth = ((depth < npeer) ? peer[depth]++ : 0);
2061  (void) rpmteSetBreadth(q, breadth);
2062 
2063  rpmlog(RPMLOG_DEBUG, "%5d%5d%5d%5d%5d%5d %*s%c%s\n",
2064  orderingCount, rpmteNpreds(q),
2065  rpmteTSI(q)->tsi_qcnt,
2066  treex, depth, breadth,
2067  (2 * depth), "",
2068  deptypechar,
2069  (rpmteNEVRA(q) ? rpmteNEVRA(q) : "???"));
2070 
2071  (void) rpmteSetDegree(q, 0);
2072  tsbytes += rpmtePkgFileSize(q);
2073 
2074  ordering[orderingCount] = rpmteAddedKey(q);
2075  orderingCount++;
2076  qlen--;
2077  loopcheck--;
2078 
2079  /* T6. Erase relations. */
2080  tsi_next = rpmteTSI(q)->tsi_next;
2081  rpmteTSI(q)->tsi_next = NULL;
2082  while ((tsi = tsi_next) != NULL) {
2083  tsi_next = tsi->tsi_next;
2084  tsi->tsi_next = NULL;
2085  p = tsi->tsi_suc;
2086  if (p && (--rpmteTSI(p)->tsi_count) <= 0) {
2087 
2088  (void) rpmteSetTree(p, treex);
2089  (void) rpmteSetDepth(p, depth+1);
2090  (void) rpmteSetParent(p, q);
2091  (void) rpmteSetDegree(q, rpmteDegree(q)+1);
2092 
2093  /* Mark the package as queued. */
2094  rpmteTSI(p)->tsi_queued = orderingCount + 1;
2095  /* XXX TODO: add control bit. */
2096  rpmteTSI(p)->tsi_suc = NULL;
2097 /*@-nullstate@*/ /* XXX FIX: rpmteTSI(q)->tsi_suc can be NULL. */
2098  addQ(p, &rpmteTSI(q)->tsi_suc, &r, prefcolor);
2099 /*@=nullstate@*/
2100  qlen++;
2101  }
2102  tsi = _free(tsi);
2103  }
2104  if (!_printed && loopcheck == qlen && rpmteTSI(q)->tsi_suc != NULL) {
2105  _printed++;
2106  (void) rpmtsUnorderedSuccessors(ts, orderingCount);
2108  D_("========== successors only (%d bytes)\n"), (int)tsbytes);
2109 
2110  /* Relink the queue in presentation order. */
2111  tsi = rpmteTSI(q);
2112  pi = rpmtsiInit(ts);
2113  while ((p = rpmtsiNext(pi, oType)) != NULL) {
2114  /* Is this element in the queue? */
2115  if (rpmteTSI(p)->tsi_queued == 0)
2116  /*@innercontinue@*/ continue;
2117  tsi->tsi_suc = p;
2118  tsi = rpmteTSI(p);
2119  }
2120  pi = rpmtsiFree(pi);
2121  tsi->tsi_suc = NULL;
2122  }
2123  }
2124 #ifdef REFERENCE
2125  }
2126 #else /* REFERENCE */
2127  /* T8. End of process. Check for loops. */
2128  if (loopcheck != 0) {
2129  int nzaps;
2130 
2131  /* T9. Initialize predecessor chain. */
2132  nzaps = 0;
2133  qi = rpmtsiInit(ts);
2134  while ((q = rpmtsiNext(qi, oType)) != NULL) {
2135  rpmteTSI(q)->tsi_chain = NULL;
2136  rpmteTSI(q)->tsi_queued = 0;
2137  /* Mark packages already sorted. */
2138  if (rpmteTSI(q)->tsi_count == 0)
2139  rpmteTSI(q)->tsi_count = -1;
2140  }
2141  qi = rpmtsiFree(qi);
2142 
2143  /* T10. Mark all packages with their predecessors. */
2144  qi = rpmtsiInit(ts);
2145  while ((q = rpmtsiNext(qi, oType)) != NULL) {
2146  if ((tsi = rpmteTSI(q)->tsi_next) == NULL)
2147  continue;
2148  rpmteTSI(q)->tsi_next = NULL;
2149  markLoop(tsi, q);
2150  rpmteTSI(q)->tsi_next = tsi;
2151  }
2152  qi = rpmtsiFree(qi);
2153 
2154  /* T11. Print all dependency loops. */
2155  ri = rpmtsiInit(ts);
2156  while ((r = rpmtsiNext(ri, oType)) != NULL)
2157  {
2158  int printed;
2159 
2160  printed = 0;
2161 
2162  /* T12. Mark predecessor chain, looking for start of loop. */
2163  for (q = rpmteTSI(r)->tsi_chain; q != NULL;
2164  q = rpmteTSI(q)->tsi_chain)
2165  {
2166  if (rpmteTSI(q)->tsi_queued)
2167  /*@innerbreak@*/ break;
2168  rpmteTSI(q)->tsi_queued = 1;
2169  }
2170 
2171  /* T13. Print predecessor chain from start of loop. */
2172  while ((p = q) != NULL && (q = rpmteTSI(p)->tsi_chain) != NULL) {
2173 #if 0
2174  const char * nevra;
2175 #endif
2176  const char * dp;
2177  rpmlogLvl msglvl = (anaconda || (rpmtsDFlags(ts) & RPMDEPS_FLAG_DEPLOOPS))
2179 #if defined(RPM_VENDOR_MANDRIVA) || defined(RPM_VENDOR_PLD) /* loop-detection-optional-loglevel */
2180  // Report loops as debug-level message by default (7 = RPMLOG_DEBUG), overridable
2181  msglvl = rpmExpandNumeric("%{?_loop_detection_loglevel}%{?!_loop_detection_loglevel:7}");
2182 #endif
2183 
2184  /* Unchain predecessor loop. */
2185  rpmteTSI(p)->tsi_chain = NULL;
2186 
2187  if (!printed) {
2188  rpmlog(msglvl, _("LOOP:\n"));
2189  printed = 1;
2190  }
2191 
2192  /* Find (and destroy if co-requisite) "q <- p" relation. */
2193  dp = zapRelation(q, p, 1, &nzaps, msglvl);
2194 
2195 #if 0
2196  /* Print next member of loop. */
2197  nevra = rpmteNEVRA(p);
2198  rpmlog(msglvl, " %-40s %s\n", (nevra ? nevra : "???"),
2199  (dp ? dp : "not found!?!"));
2200 #endif
2201 
2202  dp = _free(dp);
2203  }
2204 
2205  /* Walk (and erase) linear part of predecessor chain as well. */
2206  for (p = r, q = rpmteTSI(r)->tsi_chain; q != NULL;
2207  p = q, q = rpmteTSI(q)->tsi_chain)
2208  {
2209  /* Unchain linear part of predecessor loop. */
2210  rpmteTSI(p)->tsi_chain = NULL;
2211  rpmteTSI(p)->tsi_queued = 0;
2212  }
2213  }
2214  ri = rpmtsiFree(ri);
2215 
2216  /* If a relation was eliminated, then continue sorting. */
2217  /* XXX TODO: add control bit. */
2218  if (nzaps && nrescans-- > 0) {
2219  rpmlog(RPMLOG_DEBUG, D_("========== continuing tsort ...\n"));
2220  goto rescan;
2221  }
2222 
2223  /* Return no. of packages that could not be ordered. */
2224  rpmlog(RPMLOG_ERR, _("rpmtsOrder failed, %d elements remain\n"),
2225  loopcheck);
2226 
2227 #ifdef NOTYET
2228  /* Do autorollback goal since we could not sort this transaction properly. */
2229  (void) rpmtsRollback(ts, RPMPROB_FILTER_NONE, 0, NULL);
2230 #endif
2231 
2232  return loopcheck;
2233  }
2234 #endif /* REFERENCE */
2235 
2236  /* Clean up tsort remnants (if any). */
2237  pi = rpmtsiInit(ts);
2238  while ((p = rpmtsiNext(pi, 0)) != NULL)
2239  rpmteFreeTSI(p);
2240  pi = rpmtsiFree(pi);
2241 
2242 #ifdef REFERENCE
2243 #else /* REFERENCE */
2244  /* The order ends up as installed packages followed by removed packages. */
2245  orderList = (orderListIndex) xcalloc(numOrderList, sizeof(*orderList));
2246  j = 0;
2247  pi = rpmtsiInit(ts);
2248  while ((p = rpmtsiNext(pi, oType)) != NULL) {
2249  /* Prepare added/erased package ordering permutation. */
2250  orderList[j].pkgKey = rpmteAddedKey(p);
2251  orderList[j].orIndex = rpmtsiOc(pi);
2252  j++;
2253  }
2254  pi = rpmtsiFree(pi);
2255 
2256  qsort(orderList, numOrderList, sizeof(*orderList), orderListIndexCmp);
2257 
2258 /*@-type@*/
2259  newOrder = (rpmte *) xcalloc(ts->orderCount, sizeof(*newOrder));
2260 /*@=type@*/
2261  for (i = 0, newOrderCount = 0; i < orderingCount; i++)
2262  {
2263  struct orderListIndex_s key;
2264  orderListIndex needle;
2265 
2266  key.pkgKey = ordering[i];
2267  needle = bsearch(&key, orderList, numOrderList,
2268  sizeof(key), orderListIndexCmp);
2269  if (needle == NULL) /* XXX can't happen */
2270  continue;
2271 
2272  j = needle->orIndex;
2273  if ((q = ts->order[j]) == NULL || needle->pkgKey == RPMAL_NOMATCH)
2274  continue;
2275 
2276  newOrder[newOrderCount++] = q;
2277  ts->order[j] = NULL;
2278  }
2279  orderList = _free(orderList);
2280 #endif /* REFERENCE */
2281 
2282 assert(newOrderCount == ts->orderCount);
2283  rc = 0;
2284 
2285 /*@+voidabstract@*/
2286  ts->order = _free(ts->order);
2287 /*@=voidabstract@*/
2288  ts->order = newOrder;
2289  ts->orderAlloced = ts->orderCount;
2290 
2291 #ifdef REFERENCE
2292  for (i = 2; SCCs[i].members != NULL; i++)
2293  SCCs[i].members = _free(SCCs[i].members);
2294  SCCs = _free(SCCs);
2295 
2296  rpmalFree(ts->erasedPackages);
2297  ts->erasedPackages = NULL;
2298 #else /* REFERENCE */
2299 #ifdef DYING /* XXX now done at the CLI level just before rpmtsRun(). */
2300  rpmtsClean(ts);
2301 #endif
2302 #endif /* REFERENCE */
2303 
2304  freeBadDeps();
2305 
2306  (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
2307 
2308  return rc;
2309 }
2310 
2312  = _rpmtsOrder;
static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q)
Check for dependency relations to be ignored.
Definition: order.c:129
const bson * b
Definition: bson.h:280
evrFlags rpmdsFlags(const rpmds ds)
Return current dependency flags.
Definition: rpmds.c:691
static const int one
Definition: mongo.c:49
rpmds rpmdsInit(rpmds ds)
Initialize dependency set iterator.
Definition: rpmds.c:943
int rpmteSetDegree(rpmte te, int ndegree)
Set number of children of transaction element.
Definition: rpmte.c:472
rpmuint32_t rpmteColor(rpmte te)
Retrieve color bits of transaction element.
Definition: rpmte.c:360
rpmtime_t rpmswExit(rpmop op, ssize_t rc)
Exit timed operation.
Definition: rpmsw.c:264
nsType rpmdsNSType(const rpmds ds)
Return dependency class type.
Definition: rpmds.c:738
int rpmteSetTree(rpmte te, int ntree)
Set tree index of transaction element.
Definition: rpmte.c:440
static const char * identifyDepend(rpmuint32_t f)
Definition: order.c:304
static int badDepsInitialized
Definition: order.c:98
const char bson_timestamp_t * ts
Definition: bson.h:1004
void rpmteFreeTSI(rpmte te)
Destroy tsort info of transaction element.
Definition: rpmte.c:489
static const char * zapRelation(rpmte q, rpmte p, int zap, int *nzaps, int msglvl)
Find (and eliminate co-requisites) "q <- p" relation in dependency loop.
Definition: order.c:339
enum rpmlogLvl_e rpmlogLvl
RPM Log levels.
int rpmteSetBreadth(rpmte te, int nbreadth)
Set dependency tree breadth of transaction element.
Definition: rpmte.c:410
Structures used for an "rpmte" transaction element.
char * xstrdup(const char *str)
Definition: rpmmalloc.c:321
Structure(s) used for file info tag sets.
struct rpmbf_s * rpmbf
Definition: rpmbf.h:17
static void tarjan(sccData sd, rpmte p)
Definition: order.c:945
alKey rpmalAdd(rpmal *alistp, alKey pkgKey, fnpyKey key, rpmds provides, rpmfi fi, rpmuint32_t tscolor)
Add package to available list.
Definition: rpmal.c:222
rpmte * members
Definition: order.c:57
const char * rpmteN(rpmte te)
Retrieve name string of transaction element.
Definition: rpmte.c:316
void * rpmfiFNBF(rpmfi fi)
Return FN Bloom filter from file info set.
Definition: rpmfi.c:181
int rpmteDegree(rpmte te)
Retrieve number of children of transaction element.
Definition: rpmte.c:467
scc SCCs
Definition: order.c:873
int index
Definition: order.c:866
int rpmteNpreds(rpmte te)
Retrieve tsort no.
Definition: rpmte.c:420
rpmTag rpmdsTagN(const rpmds ds)
Return current dependency type.
Definition: rpmds.c:702
rpmop rpmtsOp(rpmts ts, rpmtsOpX opx)
Retrieve operation timestamp from a transaction set.
Definition: pkgio.c:133
rpmtsi rpmtsiFree(rpmtsi tsi)
Destroy transaction element iterator.
struct rpmtsi_s * rpmtsi
Transaction element iterator.
Definition: rpmte.h:31
static void rpmlog(int code, const char *fmt,...)
Definition: rpmlog.h:299
rpmElementType rpmteType(rpmte te)
Retrieve type of transaction element.
Definition: rpmte.c:311
rpmRC rpmtsRollback(rpmts rbts, rpmprobFilterFlags ignoreSet, int running, rpmte rbte)
Rollback a failed transaction.
Definition: transaction.c:2025
struct rpmds_s * rpmds
Dependency tag sets from a header, so that a header can be discarded early.
Definition: rpmtypes.h:28
static rpmuint32_t _autobits
Definition: order.c:861
rpmds rpmteDS(rpmte te, rpmTag tag)
Retrieve dependency tag set from transaction element.
Definition: rpmte.c:573
struct rpmte_s * rpmte
An element of a transaction set, i.e.
Definition: rpmtypes.h:38
struct tsortInfo_s * tsortInfo
Transaction element ordering chain linkage.
Definition: rpmte.h:26
static struct badDeps_s * badDeps
Definition: order.c:101
static void addQ(rpmte p, rpmte *qp, rpmte *rp, rpmuint32_t prefcolor)
Add element to list sorting by tsi_qcnt.
Definition: order.c:802
char * alloca()
alKey rpmteSetAddedKey(rpmte te, alKey npkgKey)
Definition: rpmte.c:520
rpmte * stack
Definition: order.c:870
int _rpmts_debug
Definition: rpmts.c:93
Yet Another syslog(3) API clone.
enum rpmElementType_e rpmElementType
Transaction element type.
unsigned int rpmuint32_t
Definition: rpmiotypes.h:28
Definition: order.c:48
void * xcalloc(size_t nmemb, size_t size)
Definition: rpmmalloc.c:300
static int orgrpmAddRelation(rpmts ts, rpmal al, rpmte p, rpmds requires)
Record next "q <- p" relation (i.e.
Definition: order.c:454
rpmte rpmteParent(rpmte te)
Retrieve parent transaction element.
Definition: rpmte.c:450
int rpmteDepth(rpmte te)
Retrieve dependency tree depth of transaction element.
Definition: rpmte.c:390
int _orgrpmtsOrder(rpmts ts)
Definition: order.c:1568
int sccCnt
Definition: order.c:874
alKey rpmteAddedKey(rpmte te)
Definition: rpmte.c:515
rpmfi rpmteFI(rpmte te, rpmTag tag)
Retrieve file info tag set from transaction element.
Definition: rpmte.c:587
static int addRelation(rpmts ts, rpmal al, rpmte p, unsigned char *selected, rpmds requires)
Record next "q <- p" relation (i.e.
Definition: order.c:623
static void collectSCC(rpm_color_t prefcolor, rpmte p, rpmte *newOrder, int *newOrderCount, scc SCCs, rpmte *queue_end)
Definition: order.c:1345
struct rpmfi_s * rpmfi
File info tag sets from a header, so that a header can be discarded early.
Definition: rpmfi.h:83
#define RPMAL_NOMATCH
Definition: rpmal.h:17
enum evrFlags_e rpmsenseFlags
Definition: rpmevr.h:74
Set of available packages, items, and directories.
Definition: rpmal.c:90
int rpmtsNElements(rpmts ts)
Return number of (ordered) transaction set elements.
Definition: rpmts.c:1308
static void freeBadDeps(void)
Definition: order.c:106
rpmuint32_t rpmtsPrefColor(rpmts ts)
Retrieve preferred file color.
Definition: rpmts.c:1455
int rpmdsNext(rpmds ds)
Return next dependency set iterator index.
Definition: rpmds.c:912
Structure(s) used for dependency tag sets.
const char * rpmteNEVRA(rpmte te)
Retrieve name-version-release.arch string from transaction element.
Definition: rpmte.c:541
#define isLegacyPreReq(_x)
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)
Definition: order.c:1166
const char * qname
Definition: order.c:89
int rpmswEnter(rpmop op, ssize_t rc)
Enter timed operation.
Definition: rpmsw.c:248
char * rpmExpand(const char *arg,...)
Return (malloc'ed) concatenated macro expansion(s).
Definition: macro.c:3250
void * alKey
An added/available package retrieval key.
Definition: rpmtypes.h:19
void rpmteNewTSI(rpmte te)
Initialize tsort info of transaction element.
Definition: rpmte.c:507
const char * pname
Definition: order.c:87
char * rpmdsNewDNEVR(const char *dspfx, rpmds ds)
Return new formatted dependency string.
Definition: rpmds.c:434
int depth
Definition: bson.h:258
int count
Definition: order.c:49
const char * rpmdsN(const rpmds ds)
Return current dependency name.
Definition: rpmds.c:668
rpmuint32_t rpm_color_t
Definition: order.c:27
const char const bson int mongo_write_concern int flags
Definition: mongo.h:485
rpmte rpmtsiNext(rpmtsi tsi, rpmElementType type)
Return next transaction element of type.
Definition: rpmte.c:831
struct orderListIndex_s * orderListIndex
Definition: order.c:33
int rpmtsiOc(rpmtsi tsi)
Return transaction element index.
Definition: rpmte.c:755
int rpmteSetDepth(rpmte te, int ndepth)
Set dependency tree depth of transaction element.
Definition: rpmte.c:395
rpmuint32_t rpmtsColor(rpmts ts)
Retrieve color bits of transaction set.
Definition: rpmts.c:1440
Definition: rpmte.h:37
const char const int i
Definition: bson.h:778
rpmdepFlags rpmtsDFlags(rpmts ts)
Get dependency flags, i.e.
Definition: rpmts.c:1363
const char const bson * key
Definition: mongo.h:717
fnpyKey rpmalSatisfiesDepend(const rpmal al, const rpmds ds, alKey *keyp)
Check added package file lists for first package that has a provide.
Definition: rpmal.c:511
struct rpmts_s * rpmts
The RPM Transaction Set.
Definition: rpmtypes.h:14
static void * _free(const void *p)
Wrapper to free(3), hides const compilation noise, permit NULL, return NULL.
Definition: rpmiotypes.h:756
static void markLoop(tsortInfo tsi, rpmte q)
Recursively mark all nodes with their predecessors.
Definition: order.c:280
rpmuint32_t rpmtePkgFileSize(rpmte te)
Retrieve size in bytes of package file.
Definition: rpmte.c:375
const void * fnpyKey
Definition: rpmiotypes.h:134
Structures and prototypes used for an "rpmts" transaction set.
rpmfi fi
Definition: filetriggers.h:15
int rpmteSetNpreds(rpmte te, int npreds)
Set tsort no.
Definition: rpmte.c:425
rpmte rpmteSetParent(rpmte te, rpmte pte)
Set parent transaction element.
Definition: rpmte.c:455
tsortInfo rpmteTSI(rpmte te)
Retrieve tsort info for transaction element.
Definition: rpmte.c:482
static scc detectSCCs(rpmts ts)
Definition: order.c:1023
int rpmdsIx(const rpmds ds)
Return dependency set index.
Definition: rpmds.c:641
void rpmalMakeIndex(rpmal al)
Generate index for available list.
Definition: rpmal.c:330
int rpmtsUnorderedSuccessors(rpmts ts, int first)
Set index of 1st element of successors.
Definition: rpmts.c:892
int size
Definition: order.c:53
rpmal rpmalFree(rpmal al)
Destroy available list.
#define rpmIsDebug()
Definition: rpmcb.h:23
#define _(Text)
Definition: system.h:29
#define isAuto(_x)
Definition: order.c:863
#define xmalloc
Definition: system.h:32
struct sccData_s * sccData
rpmtsi rpmtsiInit(rpmts ts)
Create transaction element iterator.
#define D_(Text)
Definition: system.h:526
alKey pkgKey
Definition: order.c:40
rpmtransFlags rpmtsFlags(rpmts ts)
Get transaction flags, i.e.
Definition: rpmts.c:1334
int rpmteTree(rpmte te)
Retrieve tree index of transaction element.
Definition: rpmte.c:435
struct scc_s * scc
Definition: order.c:61
int rpmdsSetIx(rpmds ds, int ix)
Set dependency set index.
Definition: rpmds.c:646
int(* rpmtsOrder)(rpmts ts)
Determine package order in a transaction set according to dependencies.
Definition: order.c:2311
int rpmExpandNumeric(const char *arg)
Return macro expansion as a numeric value.
Definition: macro.c:3324
#define xrealloc
Definition: system.h:35
void rpmtsClean(rpmts ts)
Free memory needed only for dependency checks and ordering.
Definition: rpmts.c:598
int _rpmtsOrder(rpmts ts)
Definition: order.c:1777
int j
Definition: mongo.h:438
static int orderListIndexCmp(const void *one, const void *two)
Compare ordered list entries by index (qsort/bsearch).
Definition: order.c:738
int rpmbfChk(rpmbf bf, const void *_s, size_t ns)
Check for item in a Bloom filter.
Definition: rpmbf.c:90
rpmds rpmdsFromPRCO(rpmPRCO PRCO, rpmTag tagN)
Retrieve a dependency set from container.
Definition: rpmds.c:2901
int stackcnt
Definition: order.c:872