15 #define _RPMEVR_INTERNAL
19 #define _RPMTE_INTERNAL
20 #define _RPMTS_ORDER_INTERNAL
22 #define _RPMTS_INTERNAL
67 struct relation_s * rel_next;
70 typedef struct relation_s * relation;
77 struct relation_s * tsi_relations;
78 struct relation_s * tsi_forward_relations;
93 GENfree(orderListIndex)
113 for (bdp = badDeps; bdp->
pname != NULL && bdp->
qname != NULL; bdp++)
115 badDeps =
_free(badDeps);
117 badDepsInitialized = 0;
137 if (!badDepsInitialized) {
138 char * s =
rpmExpand(
"%{?_dependency_whiteout}", NULL);
139 const char ** av = NULL;
151 if (s != NULL && *s !=
'\0'
152 && !(i = poptParseArgvString(s, &ac, (
const char ***)&av))
153 && ac > 0 && av != NULL)
156 for (i = 0; i < ac; i++, bdp++) {
162 if ((qname = strchr(pname,
'>')) != NULL)
169 _(
"ignore package name relation(s) [%d]\t%s -> %s\n"),
177 badDepsInitialized++;
182 for (bdp = badDeps; bdp->
pname != NULL && bdp->
qname != NULL; bdp++) {
195 while (tsi->tsi_relations != NULL) {
196 rel = tsi->tsi_relations;
197 tsi->tsi_relations = tsi->tsi_relations->rel_next;
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;
208 static inline int addSingleRelation(
rpmte p,
212 struct tsortInfo_s *tsi_p, *tsi_q;
218 if (q == NULL || q == p)
226 flags = isErasePreReq(dsflags);
228 flags = isInstallPreReq(dsflags);
234 RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
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;
253 rel = (relation)
xcalloc(1,
sizeof(*rel));
254 rel->rel_suc = tsi_p;
255 rel->rel_flags =
flags;
257 rel->rel_next = tsi_q->tsi_relations;
258 tsi_q->tsi_relations = rel;
264 rel = (relation)
xcalloc(1,
sizeof(*rel));
265 rel->rel_suc = tsi_q;
266 rel->rel_flags =
flags;
268 rel->rel_next = tsi_p->tsi_forward_relations;
269 tsi_p->tsi_forward_relations = rel;
287 while (tsi != NULL && (p = tsi->tsi_suc) != NULL) {
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):";
340 int zap,
int * nzaps,
int msglvl)
347 const char *dp = NULL;
353 tsi_prev = tsi, tsi = tsi->tsi_next)
359 if (tsi->tsi_suc != p)
364 if (requires == NULL)
continue;
377 _(
"removing %s \"%s\" from tsort relations.\n"),
380 if (tsi_prev) tsi_prev->tsi_next = tsi->tsi_next;
381 tsi->tsi_next = NULL;
416 if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG|RPMSENSE_PRETRANS))
422 if (q == NULL || q == p)
429 addSingleRelation(p, q, dsflags);
433 for (qcolls = rpmteCollections(q); qcolls && *qcolls; qcolls++) {
435 rpmte *tes = rpmalAllInCollection(al, *qcolls);
436 for (te = tes; te && *te; te++) {
437 addSingleRelation(p, *te, RPMSENSE_SCRIPT_PRE);
460 struct tsortInfo_s * tsi_p, * tsi_q;
462 const char * N =
rpmdsN(requires);
474 if (dsflags & (RPMSENSE_RPMLIB|RPMSENSE_CONFIG))
518 if (bf != NULL &&
rpmbfChk(bf, N, strlen(N)) > 0)
533 pkgKey = (
alKey)(((
long)pkgKey) + ts->numAddedPackages);
543 if (q == NULL || q == p)
555 flags = isErasePreReq(dsflags);
557 flags = isInstallPreReq(dsflags);
561 #define isLegacyPreReq(_x) (((_x) & _ALL_REQUIRES_MASK) == RPMSENSE_PREREQ)
565 RPMSENSE_SCRIPT_PRE : RPMSENSE_SCRIPT_PREUN;
567 #undef isLegacyPreReq
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;
592 rel = (relation)
xcalloc(1,
sizeof(*rel));
594 rel->rel_flags =
flags;
596 rel->rel_next =
rpmteTSI(q)->tsi_relations;
603 rel = (relation)
xcalloc(1,
sizeof(*rel));
605 rel->rel_flags =
flags;
607 rel->rel_next =
rpmteTSI(p)->tsi_forward_relations;
608 rpmteTSI(p)->tsi_forward_relations = rel;
625 unsigned char * selected,
633 const char * N =
rpmdsN(requires);
670 if (bf != NULL &&
rpmbfChk(bf, N, strlen(N)) > 0)
684 pkgKey = (
alKey)(((
long)pkgKey) + ts->numAddedPackages);
691 if (q == NULL || i >= ts->orderCount)
699 if (selected[i] != 0)
722 tsi->tsi_reqx =
rpmdsIx(requires);
724 tsi->tsi_next =
rpmteTSI(q)->tsi_next;
741 long a = (long) ((
const orderListIndex)
one)->pkgKey;
742 long b = (long) ((
const orderListIndex)two)->pkgKey;
770 for (qprev = NULL, q = (*qp);
772 qprev = q, q = q->tsi_suc)
778 if (q->tsi_qcnt <= p->tsi_qcnt)
785 }
else if (q == NULL) {
821 for (qprev = NULL, q = (*qp);
823 qprev = q, q =
rpmteTSI(q)->tsi_suc)
848 }
else if (q == NULL) {
863 #define isAuto(_x) ((_x) & _autobits)
886 tsi->tsi_SccIdx = sd->
index;
887 tsi->tsi_SccLowlink = sd->
index;
890 for (rel = tsi->tsi_relations; rel != NULL; rel = rel->rel_next) {
892 tsi_q = rel->rel_suc;
893 if (tsi_q->tsi_SccIdx > 0)
896 if (tsi_q->tsi_SccIdx == 0) {
900 tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink)
901 ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink;
903 tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx)
904 ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx;
908 if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
913 tsi_q->tsi_SccIdx = 1;
917 tsi_q = sd->
stack[--stackIdx];
918 tsi_q->tsi_SccIdx = sd->
sccCnt;
919 }
while (tsi_q != tsi);
923 tsi_q = sd->
stack[--stackIdx];
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)
932 }
while (tsi_q != tsi);
955 tsi->tsi_SccIdx = sd->
index;
956 tsi->tsi_SccLowlink = sd->
index;
959 for (rel = tsi->tsi_relations; rel != NULL; rel = rel->rel_next) {
963 if (tsi_q->tsi_SccIdx > 0)
966 if (tsi_q->tsi_SccIdx == 0) {
970 tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccLowlink)
971 ? tsi->tsi_SccLowlink : tsi_q->tsi_SccLowlink;
973 tsi->tsi_SccLowlink = (tsi->tsi_SccLowlink > tsi_q->tsi_SccIdx)
974 ? tsi->tsi_SccLowlink : tsi_q->tsi_SccIdx;
978 if (tsi->tsi_SccLowlink == tsi->tsi_SccIdx) {
984 tsi_q->tsi_SccIdx = 1;
988 q = sd->
stack[--stackIdx];
990 tsi_q->tsi_SccIdx = sd->
sccCnt;
995 q = sd->
stack[--stackIdx];
1000 for (rel=tsi_q->tsi_relations; rel != NULL; rel=rel->rel_next) {
1001 if (rel->rel_suc != q
1026 int nelem = ts->orderCount;
1027 scc _SCCs = (
scc)
xcalloc(nelem+3,
sizeof(*_SCCs));
1033 struct sccData_s sd = { 0, _stack, 0, _SCCs, 2 };
1036 for (
int i = 0;
i < nelem;
i++) {
1039 if (tsi->tsi_SccIdx == 0)
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",
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 ?
"=>" :
"->",
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 ?
"=>" :
"->",
1109 rpmte * newOrder,
int * newOrderCount,
1122 *newOrderCount, q->tsi_count, q->tsi_qcnt,
1123 depth, (2 * depth),
"",
1127 newOrder[*newOrderCount] = q->te;
1131 for (relation rel = q->tsi_relations; rel != NULL; rel = rel->rel_next) {
1134 if (p->tsi_SccIdx == 0)
continue;
1135 if (p == q)
continue;
1137 if (p && (--p->tsi_count) == 0) {
1140 if (q->tsi_SccIdx > 1 && q->tsi_SccIdx != p->tsi_SccIdx) {
1142 assert(outer_queue != NULL && outer_queue_end != NULL);
1143 addQ(p, outer_queue, outer_queue_end, prefcolor);
1145 addQ(p, &q->tsi_suc, queue_end, prefcolor);
1148 if (p && p->tsi_SccIdx > 1 &&
1149 p->tsi_SccIdx != q->tsi_SccIdx) {
1150 if (--SCCs[p->tsi_SccIdx].
count == 0) {
1154 if (outer_queue != NULL) {
1155 addQ(p, outer_queue, outer_queue_end, prefcolor);
1157 addQ(p, &q->tsi_suc, queue_end, prefcolor);
1167 rpmte * newOrder,
int * newOrderCount,
1170 rpmte * outer_queue,
1171 rpmte * outer_queue_end)
1189 newOrder[*newOrderCount] = q;
1193 for (rel =
rpmteTSI(q)->tsi_relations; rel != NULL; rel = rel->rel_next) {
1194 rpmte p = rel->rel_suc;
1198 if (p_tsi->tsi_SccIdx == 0)
continue;
1199 if (p == q)
continue;
1201 if (p && (--p_tsi->tsi_count) == 0) {
1208 if (tsi->tsi_SccIdx > 1 && tsi->tsi_SccIdx != p_tsi->tsi_SccIdx) {
1210 assert(outer_queue != NULL && outer_queue_end != NULL);
1211 addQ(p, outer_queue, outer_queue_end, prefcolor);
1213 addQ(p, &tsi->tsi_suc, queue_end, prefcolor);
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) {
1226 if (outer_queue != NULL) {
1227 addQ(p, outer_queue, outer_queue_end, prefcolor);
1234 tsi->tsi_SccIdx = 0;
1239 rpmte * newOrder,
int * newOrderCount,
1242 int sccNr = p_tsi->tsi_SccIdx;
1243 struct scc_s SCC = SCCs[sccNr];
1249 tsortInfo outer_queue_start = p_tsi->tsi_suc;
1250 p_tsi->tsi_suc = NULL;
1268 for (i = 0; i < SCC.
size; 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;
1277 tsi->tsi_SccLowlink = INT_MAX/2;
1285 for (i = 0; i < SCC.
size; i++) {
1287 if (tsi->tsi_SccLowlink != INT_MAX) {
1294 while (start != end) {
1296 for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
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;
1305 queue =
_free(queue);
1310 tsortInfo inner_queue_start, inner_queue_end;
1314 for (
int i = 0; i < SCC.
size; i++) {
1316 if (tsi->tsi_SccIdx == 0)
1318 if (tsi->tsi_SccLowlink >= best_score) {
1320 best_score = tsi->tsi_SccLowlink;
1328 inner_queue_start = inner_queue_end = NULL;
1329 addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
1331 for (; inner_queue_start != NULL;
1332 inner_queue_start = inner_queue_start->tsi_suc) {
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);
1341 p_tsi->tsi_suc = outer_queue_start;
1346 rpmte * newOrder,
int * newOrderCount,
1347 scc SCCs,
rpmte * queue_end)
1349 int sccNr =
rpmteTSI(p)->tsi_SccIdx;
1350 struct scc_s SCC = SCCs[sccNr];
1375 for (i = 0; i < SCC.
size; i++) {
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;
1385 tsi->tsi_SccLowlink = INT_MAX/2;
1393 for (i = 0; i < SCC.
size; i++) {
1396 if (tsi->tsi_SccLowlink != INT_MAX) {
1403 while (start != end) {
1404 rpmte q = queue[start++];
1406 for (rel=tsi->tsi_forward_relations; rel != NULL; rel=rel->rel_next) {
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;
1415 queue =
_free(queue);
1420 rpmte inner_queue_start, inner_queue_end;
1425 for (i = 0; i < SCC.
size; i++) {
1428 if (tsi->tsi_SccIdx == 0)
1430 if (tsi->tsi_SccLowlink >= best_score) {
1432 best_score = tsi->tsi_SccLowlink;
1440 inner_queue_start = inner_queue_end = NULL;
1441 addQ(best, &inner_queue_start, &inner_queue_end, prefcolor);
1443 for (; inner_queue_start != NULL;
1444 inner_queue_start =
rpmteTSI(inner_queue_start)->tsi_suc) {
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);
1453 rpmteTSI(p)->tsi_suc = outer_queue_start;
1459 tsMembers tsmem = rpmtsMembers(ts);
1464 int newOrderCount = 0;
1480 for (
int i = 0; i < nelem; i++) {
1481 sortInfo[
i].te = tsmem->order[
i];
1482 rpmteSetTSI(tsmem->order[i], &sortInfo[i]);
1490 erasedPackages : tsmem->addedPackages;
1500 newOrder = (
rpmte *)
xcalloc(tsmem->orderCount,
sizeof(*newOrder));
1503 rpmlog(
RPMLOG_DEBUG,
"========== tsorting packages (order, #predecessors, #succesors, depth)\n");
1505 for (
int i = 0; i < 2; i++) {
1510 for (
int e = 0; e < nelem; e++) {
1512 if (
rpmteType(p->te) != oType)
continue;
1513 if (p->tsi_count != 0)
1516 addQ(p, &q, &r, prefcolor);
1520 for (
int i = 2; SCCs[
i].
members != NULL; i++) {
1523 addQ(member, &q, &r, prefcolor);
1530 if (q->tsi_SccIdx > 1) {
1531 collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
1533 collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
1541 for (
int i = 0; i < nelem; i++) {
1542 rpmteSetTSI(tsmem->order[i], NULL);
1543 rpmTSIFree(&sortInfo[i]);
1547 assert(newOrderCount == tsmem->orderCount);
1549 tsmem->order =
_free(tsmem->order);
1550 tsmem->order = newOrder;
1551 tsmem->orderAlloced = tsmem->orderCount;
1556 for (
int i = 2; SCCs[
i].
members != NULL; i++) {
1575 int newOrderCount = 0;
1606 pkgKey =
rpmalAdd(&ts->erasedPackages, pkgKey, key,
1610 pkgKey = (
alKey)(((
long)pkgKey) + ts->numAddedPackages);
1627 ts->erasedPackages : ts->addedPackages;
1635 #if defined(RPM_VENDOR_PLD)
1643 if (strcmp(q->pkgid, p->flink.Pkgid[0]))
1647 if (requires != NULL) {
1661 if (requires != NULL)
1666 if (countSlashes(
rpmdsN(requires)) > slashDepth)
1679 if (requires != NULL)
1695 int npreds =
rpmteTSI(p)->tsi_count;
1708 newOrder = (
rpmte *)
xcalloc(ts->orderCount,
sizeof(*newOrder));
1711 rpmlog(
RPMLOG_DEBUG,
"========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n");
1713 for (j = 0; j < 2; j++) {
1719 while ((p =
rpmtsiNext(pi, oType)) != NULL) {
1723 addQ(p, &q, &r, prefcolor);
1728 for (i = 2; SCCs[
i].
members != NULL; i++) {
1732 addQ(p, &q, &r, prefcolor);
1737 for (; q != NULL; q =
rpmteTSI(q)->tsi_suc) {
1741 collectSCC(prefcolor, q, newOrder, &newOrderCount, SCCs, &r);
1743 collectTE(prefcolor, q, newOrder, &newOrderCount, SCCs, &r,
1755 assert(newOrderCount == ts->orderCount);
1757 ts->order =
_free(ts->order);
1758 ts->order = newOrder;
1759 ts->orderAlloced = ts->orderCount;
1762 for (i = 2; SCCs[
i].
members != NULL; i++)
1768 ts->erasedPackages = NULL;
1787 int newOrderCount = 0;
1805 int orderingCount = 0;
1807 unsigned char * selected = (
unsigned char *)
alloca(
sizeof(*selected) * (ts->orderCount + 1));
1809 orderListIndex orderList;
1812 int * peer = (
int *) memset(
alloca(npeer*
sizeof(*peer)), 0, (npeer*
sizeof(*peer)));
1824 fprintf(stderr,
"--> %s(%p) tsFlags 0x%x\n", __FUNCTION__, ts,
rpmtsFlags(ts));
1845 pkgKey =
rpmalAdd(&ts->erasedPackages, pkgKey, key,
1849 pkgKey = (
alKey)(((
long)pkgKey) + ts->numAddedPackages);
1860 numOrderList = ts->orderCount;
1864 numOrderList += ts->numAddedPackages;
1866 numOrderList += ts->numRemovedPackages;
1868 ordering = (
alKey *)
alloca(
sizeof(*ordering) * (numOrderList + 1));
1869 loopcheck = numOrderList;
1880 while ((p =
rpmtsiNext(pi, oType)) != NULL) {
1887 memset(selected, 0,
sizeof(*selected) * ts->orderCount);
1895 if (requires != NULL)
1906 (void)
addRelation(ts, al, p, selected, requires);
1919 if (strcmp(q->pkgid, p->flink.Pkgid[0]))
1923 if (requires != NULL) {
1929 (void)
addRelation(ts, ts->addedPackages, p, selected, requires);
1939 if (requires != NULL)
1946 (void)
addRelation(ts, al, p, selected, requires);
1953 if (requires != NULL)
1960 (void)
addRelation(ts, al, p, selected, requires);
1971 while ((p =
rpmtsiNext(pi, oType)) != NULL) {
1972 int npreds =
rpmteTSI(p)->tsi_count;
2000 newOrder = (
rpmte *)
xcalloc(ts->orderCount,
sizeof(*newOrder));
2005 rpmlog(
RPMLOG_DEBUG,
D_(
"========== tsorting packages (order, #predecessors, #succesors, tree, Ldepth, Rbreadth)\n"));
2008 for (j = 0; j < 2; j++) {
2019 while ((p =
rpmtsiNext(pi, oType)) != NULL) {
2029 rpmteTSI(p)->tsi_queued = orderingCount + 1;
2031 addQ(p, &q, &r, prefcolor);
2037 for (; q != NULL; q =
rpmteTSI(q)->tsi_suc) {
2060 breadth = ((depth < npeer) ? peer[depth]++ : 0);
2066 treex, depth, breadth,
2082 while ((tsi = tsi_next) != NULL) {
2083 tsi_next = tsi->tsi_next;
2084 tsi->tsi_next = NULL;
2086 if (p && (--
rpmteTSI(p)->tsi_count) <= 0) {
2094 rpmteTSI(p)->tsi_queued = orderingCount + 1;
2104 if (!_printed && loopcheck == qlen &&
rpmteTSI(q)->tsi_suc != NULL) {
2108 D_(
"========== successors only (%d bytes)\n"), (
int)tsbytes);
2113 while ((p =
rpmtsiNext(pi, oType)) != NULL) {
2121 tsi->tsi_suc = NULL;
2128 if (loopcheck != 0) {
2134 while ((q =
rpmtsiNext(qi, oType)) != NULL) {
2145 while ((q =
rpmtsiNext(qi, oType)) != NULL) {
2146 if ((tsi =
rpmteTSI(q)->tsi_next) == NULL)
2163 for (q =
rpmteTSI(r)->tsi_chain; q != NULL;
2172 while ((p = q) != NULL && (q =
rpmteTSI(p)->tsi_chain) != NULL) {
2179 #if defined(RPM_VENDOR_MANDRIVA) || defined(RPM_VENDOR_PLD)
2181 msglvl =
rpmExpandNumeric(
"%{?_loop_detection_loglevel}%{?!_loop_detection_loglevel:7}");
2198 rpmlog(msglvl,
" %-40s %s\n", (nevra ? nevra :
"???"),
2199 (dp ? dp :
"not found!?!"));
2206 for (p = r, q =
rpmteTSI(r)->tsi_chain; q != NULL;
2218 if (nzaps && nrescans-- > 0) {
2248 while ((p =
rpmtsiNext(pi, oType)) != NULL) {
2259 newOrder = (
rpmte *)
xcalloc(ts->orderCount,
sizeof(*newOrder));
2261 for (i = 0, newOrderCount = 0; i < orderingCount; i++)
2264 orderListIndex needle;
2267 needle = bsearch(&key, orderList, numOrderList,
2272 j = needle->orIndex;
2273 if ((q = ts->order[j]) == NULL || needle->pkgKey ==
RPMAL_NOMATCH)
2276 newOrder[newOrderCount++] = q;
2277 ts->order[
j] = NULL;
2279 orderList =
_free(orderList);
2282 assert(newOrderCount == ts->orderCount);
2286 ts->order =
_free(ts->order);
2288 ts->order = newOrder;
2289 ts->orderAlloced = ts->orderCount;
2292 for (i = 2; SCCs[
i].
members != NULL; i++)
2293 SCCs[i].members =
_free(SCCs[i].members);
2297 ts->erasedPackages = NULL;
static int ignoreDep(const rpmts ts, const rpmte p, const rpmte q)
Check for dependency relations to be ignored.
evrFlags rpmdsFlags(const rpmds ds)
Return current dependency flags.
rpmds rpmdsInit(rpmds ds)
Initialize dependency set iterator.
int rpmteSetDegree(rpmte te, int ndegree)
Set number of children of transaction element.
rpmuint32_t rpmteColor(rpmte te)
Retrieve color bits of transaction element.
rpmtime_t rpmswExit(rpmop op, ssize_t rc)
Exit timed operation.
nsType rpmdsNSType(const rpmds ds)
Return dependency class type.
int rpmteSetTree(rpmte te, int ntree)
Set tree index of transaction element.
static const char * identifyDepend(rpmuint32_t f)
static int badDepsInitialized
const char bson_timestamp_t * ts
void rpmteFreeTSI(rpmte te)
Destroy tsort info of transaction element.
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.
enum rpmlogLvl_e rpmlogLvl
RPM Log levels.
int rpmteSetBreadth(rpmte te, int nbreadth)
Set dependency tree breadth of transaction element.
Structures used for an "rpmte" transaction element.
char * xstrdup(const char *str)
Structure(s) used for file info tag sets.
static void tarjan(sccData sd, rpmte p)
alKey rpmalAdd(rpmal *alistp, alKey pkgKey, fnpyKey key, rpmds provides, rpmfi fi, rpmuint32_t tscolor)
Add package to available list.
const char * rpmteN(rpmte te)
Retrieve name string of transaction element.
void * rpmfiFNBF(rpmfi fi)
Return FN Bloom filter from file info set.
int rpmteDegree(rpmte te)
Retrieve number of children of transaction element.
int rpmteNpreds(rpmte te)
Retrieve tsort no.
rpmTag rpmdsTagN(const rpmds ds)
Return current dependency type.
rpmop rpmtsOp(rpmts ts, rpmtsOpX opx)
Retrieve operation timestamp from a transaction set.
rpmtsi rpmtsiFree(rpmtsi tsi)
Destroy transaction element iterator.
struct rpmtsi_s * rpmtsi
Transaction element iterator.
static void rpmlog(int code, const char *fmt,...)
rpmElementType rpmteType(rpmte te)
Retrieve type of transaction element.
rpmRC rpmtsRollback(rpmts rbts, rpmprobFilterFlags ignoreSet, int running, rpmte rbte)
Rollback a failed transaction.
struct rpmds_s * rpmds
Dependency tag sets from a header, so that a header can be discarded early.
static rpmuint32_t _autobits
rpmds rpmteDS(rpmte te, rpmTag tag)
Retrieve dependency tag set from transaction element.
struct rpmte_s * rpmte
An element of a transaction set, i.e.
struct tsortInfo_s * tsortInfo
Transaction element ordering chain linkage.
static struct badDeps_s * badDeps
static void addQ(rpmte p, rpmte *qp, rpmte *rp, rpmuint32_t prefcolor)
Add element to list sorting by tsi_qcnt.
alKey rpmteSetAddedKey(rpmte te, alKey npkgKey)
Yet Another syslog(3) API clone.
enum rpmElementType_e rpmElementType
Transaction element type.
void * xcalloc(size_t nmemb, size_t size)
static int orgrpmAddRelation(rpmts ts, rpmal al, rpmte p, rpmds requires)
Record next "q <- p" relation (i.e.
rpmte rpmteParent(rpmte te)
Retrieve parent transaction element.
int rpmteDepth(rpmte te)
Retrieve dependency tree depth of transaction element.
int _orgrpmtsOrder(rpmts ts)
alKey rpmteAddedKey(rpmte te)
rpmfi rpmteFI(rpmte te, rpmTag tag)
Retrieve file info tag set from transaction element.
static int addRelation(rpmts ts, rpmal al, rpmte p, unsigned char *selected, rpmds requires)
Record next "q <- p" relation (i.e.
static void collectSCC(rpm_color_t prefcolor, rpmte p, rpmte *newOrder, int *newOrderCount, scc SCCs, rpmte *queue_end)
struct rpmfi_s * rpmfi
File info tag sets from a header, so that a header can be discarded early.
enum evrFlags_e rpmsenseFlags
Set of available packages, items, and directories.
int rpmtsNElements(rpmts ts)
Return number of (ordered) transaction set elements.
static void freeBadDeps(void)
rpmuint32_t rpmtsPrefColor(rpmts ts)
Retrieve preferred file color.
int rpmdsNext(rpmds ds)
Return next dependency set iterator index.
Structure(s) used for dependency tag sets.
const char * rpmteNEVRA(rpmte te)
Retrieve name-version-release.arch string from transaction element.
#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)
int rpmswEnter(rpmop op, ssize_t rc)
Enter timed operation.
char * rpmExpand(const char *arg,...)
Return (malloc'ed) concatenated macro expansion(s).
void * alKey
An added/available package retrieval key.
void rpmteNewTSI(rpmte te)
Initialize tsort info of transaction element.
char * rpmdsNewDNEVR(const char *dspfx, rpmds ds)
Return new formatted dependency string.
const char * rpmdsN(const rpmds ds)
Return current dependency name.
const char const bson int mongo_write_concern int flags
rpmte rpmtsiNext(rpmtsi tsi, rpmElementType type)
Return next transaction element of type.
struct orderListIndex_s * orderListIndex
int rpmtsiOc(rpmtsi tsi)
Return transaction element index.
int rpmteSetDepth(rpmte te, int ndepth)
Set dependency tree depth of transaction element.
rpmuint32_t rpmtsColor(rpmts ts)
Retrieve color bits of transaction set.
rpmdepFlags rpmtsDFlags(rpmts ts)
Get dependency flags, i.e.
const char const bson * key
fnpyKey rpmalSatisfiesDepend(const rpmal al, const rpmds ds, alKey *keyp)
Check added package file lists for first package that has a provide.
struct rpmts_s * rpmts
The RPM Transaction Set.
static void * _free(const void *p)
Wrapper to free(3), hides const compilation noise, permit NULL, return NULL.
static void markLoop(tsortInfo tsi, rpmte q)
Recursively mark all nodes with their predecessors.
rpmuint32_t rpmtePkgFileSize(rpmte te)
Retrieve size in bytes of package file.
Structures and prototypes used for an "rpmts" transaction set.
int rpmteSetNpreds(rpmte te, int npreds)
Set tsort no.
rpmte rpmteSetParent(rpmte te, rpmte pte)
Set parent transaction element.
tsortInfo rpmteTSI(rpmte te)
Retrieve tsort info for transaction element.
static scc detectSCCs(rpmts ts)
int rpmdsIx(const rpmds ds)
Return dependency set index.
void rpmalMakeIndex(rpmal al)
Generate index for available list.
int rpmtsUnorderedSuccessors(rpmts ts, int first)
Set index of 1st element of successors.
rpmal rpmalFree(rpmal al)
Destroy available list.
struct sccData_s * sccData
rpmtsi rpmtsiInit(rpmts ts)
Create transaction element iterator.
rpmtransFlags rpmtsFlags(rpmts ts)
Get transaction flags, i.e.
int rpmteTree(rpmte te)
Retrieve tree index of transaction element.
int rpmdsSetIx(rpmds ds, int ix)
Set dependency set index.
int(* rpmtsOrder)(rpmts ts)
Determine package order in a transaction set according to dependencies.
int rpmExpandNumeric(const char *arg)
Return macro expansion as a numeric value.
void rpmtsClean(rpmts ts)
Free memory needed only for dependency checks and ordering.
int _rpmtsOrder(rpmts ts)
static int orderListIndexCmp(const void *one, const void *two)
Compare ordered list entries by index (qsort/bsearch).
int rpmbfChk(rpmbf bf, const void *_s, size_t ns)
Check for item in a Bloom filter.
rpmds rpmdsFromPRCO(rpmPRCO PRCO, rpmTag tagN)
Retrieve a dependency set from container.