rpm  5.4.15
Data Structures | Macros | Typedefs | Functions | Variables
order.c File Reference
#include "system.h"
#include <rpmio.h>
#include <rpmlog.h>
#include <rpmmacro.h>
#include <popt.h>
#include <rpmtypes.h>
#include <rpmtag.h>
#include <rpmds.h>
#include <rpmfi.h>
#include <rpmte.h>
#include <rpmts.h>
#include "debug.h"
Include dependency graph for order.c:

Go to the source code of this file.

Data Structures

struct  orderListIndex_s
 
struct  scc_s
 
struct  badDeps_s
 
struct  sccData_s
 

Macros

#define _RPMEVR_INTERNAL
 
#define _RPMTE_INTERNAL
 
#define _RPMTS_ORDER_INTERNAL
 
#define _RPMTS_INTERNAL
 
#define isLegacyPreReq(_x)   (((_x) & _ALL_REQUIRES_MASK) == RPMSENSE_PREREQ)
 
#define isAuto(_x)   ((_x) & _autobits)
 

Typedefs

typedef rpmuint32_t rpm_color_t
 
typedef struct orderListIndex_sorderListIndex
 
typedef struct scc_sscc
 
typedef struct sccData_ssccData
 

Functions

static void freeBadDeps (void)
 
static int ignoreDep (const rpmts ts, const rpmte p, const rpmte q)
 Check for dependency relations to be ignored. More...
 
static void markLoop (tsortInfo tsi, rpmte q)
 Recursively mark all nodes with their predecessors. More...
 
static const char * identifyDepend (rpmuint32_t f)
 
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. More...
 
static int orgrpmAddRelation (rpmts ts, rpmal al, rpmte p, rpmds requires)
 Record next "q <- p" relation (i.e. More...
 
static int addRelation (rpmts ts, rpmal al, rpmte p, unsigned char *selected, rpmds requires)
 Record next "q <- p" relation (i.e. More...
 
static int orderListIndexCmp (const void *one, const void *two)
 Compare ordered list entries by index (qsort/bsearch). More...
 
static void addQ (rpmte p, rpmte *qp, rpmte *rp, rpmuint32_t prefcolor)
 Add element to list sorting by tsi_qcnt. More...
 
static void tarjan (sccData sd, rpmte p)
 
static scc detectSCCs (rpmts ts)
 
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)
 
static void collectSCC (rpm_color_t prefcolor, rpmte p, rpmte *newOrder, int *newOrderCount, scc SCCs, rpmte *queue_end)
 
int _orgrpmtsOrder (rpmts ts)
 
int _rpmtsOrder (rpmts ts)
 

Variables

static int badDepsInitialized
 
static struct badDeps_sbadDeps
 
static rpmuint32_t _autobits = 0xffffffff
 
int(* rpmtsOrder )(rpmts ts) = _rpmtsOrder
 Determine package order in a transaction set according to dependencies. More...
 

Macro Definition Documentation

#define _RPMEVR_INTERNAL

Definition at line 15 of file order.c.

#define _RPMTE_INTERNAL

Definition at line 19 of file order.c.

#define _RPMTS_INTERNAL

Definition at line 22 of file order.c.

#define _RPMTS_ORDER_INTERNAL

Definition at line 20 of file order.c.

#define isAuto (   _x)    ((_x) & _autobits)

Definition at line 863 of file order.c.

Referenced by _rpmtsOrder().

#define isLegacyPreReq (   _x)    (((_x) & _ALL_REQUIRES_MASK) == RPMSENSE_PREREQ)

Referenced by orgrpmAddRelation().

Typedef Documentation

Definition at line 33 of file order.c.

Definition at line 27 of file order.c.

typedef struct scc_s* scc

Definition at line 61 of file order.c.

typedef struct sccData_s * sccData

Function Documentation

int _orgrpmtsOrder ( rpmts  ts)
int _rpmtsOrder ( rpmts  ts)
static void addQ ( rpmte  p,
rpmte qp,
rpmte rp,
rpmuint32_t  prefcolor 
)
static

Add element to list sorting by tsi_qcnt.

Parameters
pnew element
Return values
*qpfirst element
*rplast element
Parameters
prefcolorpreferred color

Definition at line 802 of file order.c.

References rpmteColor(), rpmteTSI(), rpmteType(), and TR_REMOVED.

Referenced by _orgrpmtsOrder(), _rpmtsOrder(), collectSCC(), and collectTE().

static int addRelation ( rpmts  ts,
rpmal  al,
rpmte  p,
unsigned char *  selected,
rpmds  requires 
)
inlinestatic
static void collectSCC ( rpm_color_t  prefcolor,
rpmte  p,
rpmte newOrder,
int *  newOrderCount,
scc  SCCs,
rpmte queue_end 
)
static

Definition at line 1345 of file order.c.

References _free(), addQ(), collectTE(), i, scc_s::members, rpmteTSI(), scc_s::size, and xmalloc.

Referenced by _orgrpmtsOrder().

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 
)
static
static scc detectSCCs ( rpmts  ts)
static
static void freeBadDeps ( void  )
static

Definition at line 106 of file order.c.

References _free(), badDeps_s::pname, and badDeps_s::qname.

Referenced by _orgrpmtsOrder(), and _rpmtsOrder().

static const char* identifyDepend ( rpmuint32_t  f)
inlinestatic

Definition at line 304 of file order.c.

Referenced by zapRelation().

static int ignoreDep ( const rpmts  ts,
const rpmte  p,
const rpmte  q 
)
static

Check for dependency relations to be ignored.

Parameters
tstransaction set
psuccessor element (i.e. with Requires: )
qpredecessor element (i.e. with Provides: )
Returns
1 if dependency is to be ignored.

Definition at line 129 of file order.c.

References _, _free(), i, badDeps_s::pname, badDeps_s::qname, RPMDEPS_FLAG_ANACONDA, RPMDEPS_FLAG_DEPLOOPS, rpmExpand(), rpmlog(), RPMLOG_DEBUG, RPMLOG_WARNING, rpmteN(), rpmtsDFlags(), xcalloc(), and xstrdup().

Referenced by addRelation(), and orgrpmAddRelation().

static void markLoop ( tsortInfo  tsi,
rpmte  q 
)
static

Recursively mark all nodes with their predecessors.

Parameters
tsisuccessor chain
qpredecessor

Definition at line 280 of file order.c.

References rpmteTSI().

Referenced by _rpmtsOrder().

static int orderListIndexCmp ( const void *  one,
const void *  two 
)
static

Compare ordered list entries by index (qsort/bsearch).

Parameters
one1st ordered list entry
two2nd ordered list entry
Returns
result of comparison

Definition at line 738 of file order.c.

References b, and one.

Referenced by _rpmtsOrder().

static int orgrpmAddRelation ( rpmts  ts,
rpmal  al,
rpmte  p,
rpmds  requires 
)
inlinestatic
static void tarjan ( sccData  sd,
rpmte  p 
)
static
static const char* zapRelation ( rpmte  q,
rpmte  p,
int  zap,
int *  nzaps,
int  msglvl 
)
static

Find (and eliminate co-requisites) "q <- p" relation in dependency loop.

Search all successors of q for instance of p. Format the specific relation, (e.g. p contains "Requires: q"). Unlink and free co-requisite (i.e. pure Requires: dependencies) successor node(s).

Parameters
qsuccessor (i.e. package required by p)
ppredecessor (i.e. package that "Requires: q")
zapmax. no. of co-requisites to remove (-1 is all)?
Return values
nzapsaddress of no. of relations removed
Parameters
msglvlmessage level at which to spew
Returns
(possibly NULL) formatted "q <- p" releation (malloc'ed)

Definition at line 339 of file order.c.

References _, _free(), identifyDepend(), rpmdsFlags(), rpmdsNewDNEVR(), rpmdsSetIx(), rpmlog(), rpmteDS(), rpmteNEVRA(), rpmteTSI(), rpmteType(), and TR_REMOVED.

Referenced by _rpmtsOrder().

Variable Documentation

rpmuint32_t _autobits = 0xffffffff
static

Definition at line 861 of file order.c.

struct badDeps_s* badDeps
static

Definition at line 101 of file order.c.

int badDepsInitialized
static

Definition at line 98 of file order.c.

int(* rpmtsOrder)(rpmts ts) = _rpmtsOrder

Determine package order in a transaction set according to dependencies.

Order packages, returning error if circular dependencies cannot be eliminated by removing Requires's from the loop(s). Only dependencies from added or removed packages are used to determine ordering using a topological sort (Knuth vol. 1, p. 262). Use rpmtsCheck() to verify that all dependencies can be resolved.

The final order ends up as installed packages followed by removed packages, with packages removed for upgrades immediately following the new package to be installed.

Parameters
tstransaction set
Returns
no. of (added) packages that could not be ordered

Definition at line 2311 of file order.c.

Referenced by rpmcliInstallOrder(), and rpmts_Order().