pg_dump_sort.c File Reference

#include "postgres_fe.h"
#include "catalog/pg_class_d.h"
#include "pg_backup_archiver.h"
#include "pg_backup_utils.h"
#include "pg_dump.h"

Include dependency graph for pg_dump_sort.c:

Go to the source code of this file.

Enumerations
enum	dbObjectTypePriorities {   PRIO_NAMESPACE = 1 , PRIO_PROCLANG , PRIO_COLLATION , PRIO_TRANSFORM ,   PRIO_EXTENSION , PRIO_TYPE , PRIO_CAST , PRIO_FUNC ,   PRIO_AGG , PRIO_ACCESS_METHOD , PRIO_OPERATOR , PRIO_OPFAMILY ,   PRIO_CONVERSION , PRIO_TSPARSER , PRIO_TSTEMPLATE , PRIO_TSDICT ,   PRIO_TSCONFIG , PRIO_FDW , PRIO_FOREIGN_SERVER , PRIO_TABLE ,   PRIO_TABLE_ATTACH , PRIO_DUMMY_TYPE , PRIO_ATTRDEF , PRIO_LARGE_OBJECT ,   PRIO_PRE_DATA_BOUNDARY , PRIO_TABLE_DATA , PRIO_SEQUENCE_SET , PRIO_LARGE_OBJECT_DATA ,   PRIO_POST_DATA_BOUNDARY , PRIO_CONSTRAINT , PRIO_INDEX , PRIO_INDEX_ATTACH ,   PRIO_STATSEXT , PRIO_RULE , PRIO_TRIGGER , PRIO_FK_CONSTRAINT ,   PRIO_POLICY , PRIO_PUBLICATION , PRIO_PUBLICATION_REL , PRIO_PUBLICATION_TABLE_IN_SCHEMA ,   PRIO_SUBSCRIPTION , PRIO_DEFAULT_ACL , PRIO_EVENT_TRIGGER , PRIO_REFRESH_MATVIEW }

Functions
	StaticAssertDecl (lengthof(dbObjectTypePriority)==(DO_SUBSCRIPTION+1), "array length mismatch")
static int	DOTypeNameCompare (const void *p1, const void *p2)
static bool	TopoSort (DumpableObject **objs, int numObjs, DumpableObject **ordering, int *nOrdering)
static void	addHeapElement (int val, int *heap, int heapLength)
static int	removeHeapElement (int *heap, int heapLength)
static void	findDependencyLoops (DumpableObject **objs, int nObjs, int totObjs)
static int	findLoop (DumpableObject *obj, DumpId startPoint, bool *processed, DumpId *searchFailed, DumpableObject **workspace, int depth)
static void	repairDependencyLoop (DumpableObject **loop, int nLoop)
static void	describeDumpableObject (DumpableObject *obj, char *buf, int bufsize)
void	sortDumpableObjectsByTypeName (DumpableObject **objs, int numObjs)
void	sortDumpableObjects (DumpableObject **objs, int numObjs, DumpId preBoundaryId, DumpId postBoundaryId)
static void	repairTypeFuncLoop (DumpableObject *typeobj, DumpableObject *funcobj)
static void	repairViewRuleLoop (DumpableObject *viewobj, DumpableObject *ruleobj)
static void	repairViewRuleMultiLoop (DumpableObject *viewobj, DumpableObject *ruleobj)
static void	repairMatViewBoundaryMultiLoop (DumpableObject *boundaryobj, DumpableObject *nextobj)
static void	repairTableConstraintLoop (DumpableObject *tableobj, DumpableObject *constraintobj)
static void	repairTableConstraintMultiLoop (DumpableObject *tableobj, DumpableObject *constraintobj)
static void	repairTableAttrDefLoop (DumpableObject *tableobj, DumpableObject *attrdefobj)
static void	repairTableAttrDefMultiLoop (DumpableObject *tableobj, DumpableObject *attrdefobj)
static void	repairDomainConstraintLoop (DumpableObject *domainobj, DumpableObject *constraintobj)
static void	repairDomainConstraintMultiLoop (DumpableObject *domainobj, DumpableObject *constraintobj)
static void	repairIndexLoop (DumpableObject *partedindex, DumpableObject *partindex)

Variables
static const int	dbObjectTypePriority []
static DumpId	preDataBoundId
static DumpId	postDataBoundId

Enumeration Type Documentation

dbObjectTypePriorities

enum dbObjectTypePriorities

Enumerator
PRIO_NAMESPACE
PRIO_PROCLANG
PRIO_COLLATION
PRIO_TRANSFORM
PRIO_EXTENSION
PRIO_TYPE
PRIO_CAST
PRIO_FUNC
PRIO_AGG
PRIO_ACCESS_METHOD
PRIO_OPERATOR
PRIO_OPFAMILY
PRIO_CONVERSION
PRIO_TSPARSER
PRIO_TSTEMPLATE
PRIO_TSDICT
PRIO_TSCONFIG
PRIO_FDW
PRIO_FOREIGN_SERVER
PRIO_TABLE
PRIO_TABLE_ATTACH
PRIO_DUMMY_TYPE
PRIO_ATTRDEF
PRIO_LARGE_OBJECT
PRIO_PRE_DATA_BOUNDARY
PRIO_TABLE_DATA
PRIO_SEQUENCE_SET
PRIO_LARGE_OBJECT_DATA
PRIO_POST_DATA_BOUNDARY
PRIO_CONSTRAINT
PRIO_INDEX
PRIO_INDEX_ATTACH
PRIO_STATSEXT
PRIO_RULE
PRIO_TRIGGER
PRIO_FK_CONSTRAINT
PRIO_POLICY
PRIO_PUBLICATION
PRIO_PUBLICATION_REL
PRIO_PUBLICATION_TABLE_IN_SCHEMA
PRIO_SUBSCRIPTION
PRIO_DEFAULT_ACL
PRIO_EVENT_TRIGGER
PRIO_REFRESH_MATVIEW

Definition at line 53 of file pg_dump_sort.c.

{
    PRIO_NAMESPACE = 1,
    PRIO_PROCLANG,
    PRIO_COLLATION,
    PRIO_TRANSFORM,
    PRIO_EXTENSION,
    PRIO_TYPE,                  /* used for DO_TYPE and DO_SHELL_TYPE */
    PRIO_CAST,
    PRIO_FUNC,
    PRIO_AGG,
    PRIO_ACCESS_METHOD,
    PRIO_OPERATOR,
    PRIO_OPFAMILY,              /* used for DO_OPFAMILY and DO_OPCLASS */
    PRIO_CONVERSION,
    PRIO_TSPARSER,
    PRIO_TSTEMPLATE,
    PRIO_TSDICT,
    PRIO_TSCONFIG,
    PRIO_FDW,
    PRIO_FOREIGN_SERVER,
    PRIO_TABLE,
    PRIO_TABLE_ATTACH,
    PRIO_DUMMY_TYPE,
    PRIO_ATTRDEF,
    PRIO_LARGE_OBJECT,
    PRIO_PRE_DATA_BOUNDARY,     /* boundary! */
    PRIO_TABLE_DATA,
    PRIO_SEQUENCE_SET,
    PRIO_LARGE_OBJECT_DATA,
    PRIO_POST_DATA_BOUNDARY,    /* boundary! */
    PRIO_CONSTRAINT,
    PRIO_INDEX,
    PRIO_INDEX_ATTACH,
    PRIO_STATSEXT,
    PRIO_RULE,
    PRIO_TRIGGER,
    PRIO_FK_CONSTRAINT,
    PRIO_POLICY,
    PRIO_PUBLICATION,
    PRIO_PUBLICATION_REL,
    PRIO_PUBLICATION_TABLE_IN_SCHEMA,
    PRIO_SUBSCRIPTION,
    PRIO_DEFAULT_ACL,           /* done in ACL pass */
    PRIO_EVENT_TRIGGER,         /* must be next to last! */
    PRIO_REFRESH_MATVIEW        /* must be last! */
};

Function Documentation

addHeapElement()

static void addHeapElement ( int  val, int *  heap, int  heapLength  )

static

Definition at line 514 of file pg_dump_sort.c.

{
    int         j;
 
    /*
     * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
     * using 1-based array indexes, not 0-based.
     */
    j = heapLength;
    while (j > 0)
    {
        int         i = (j - 1) >> 1;
 
        if (val <= heap[i])
            break;
        heap[j] = heap[i];
        j = i;
    }
    heap[j] = val;
}

References i, j, and val.

Referenced by TopoSort().

describeDumpableObject()

static void describeDumpableObject ( DumpableObject *  obj, char *  buf, int  bufsize  )

static

Definition at line 1271 of file pg_dump_sort.c.

{
    switch (obj->objType)
    {
        case DO_NAMESPACE:
            snprintf(buf, bufsize,
                     "SCHEMA %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_EXTENSION:
            snprintf(buf, bufsize,
                     "EXTENSION %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TYPE:
            snprintf(buf, bufsize,
                     "TYPE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_SHELL_TYPE:
            snprintf(buf, bufsize,
                     "SHELL TYPE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_FUNC:
            snprintf(buf, bufsize,
                     "FUNCTION %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_AGG:
            snprintf(buf, bufsize,
                     "AGGREGATE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_OPERATOR:
            snprintf(buf, bufsize,
                     "OPERATOR %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_ACCESS_METHOD:
            snprintf(buf, bufsize,
                     "ACCESS METHOD %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_OPCLASS:
            snprintf(buf, bufsize,
                     "OPERATOR CLASS %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_OPFAMILY:
            snprintf(buf, bufsize,
                     "OPERATOR FAMILY %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_COLLATION:
            snprintf(buf, bufsize,
                     "COLLATION %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_CONVERSION:
            snprintf(buf, bufsize,
                     "CONVERSION %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TABLE:
            snprintf(buf, bufsize,
                     "TABLE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TABLE_ATTACH:
            snprintf(buf, bufsize,
                     "TABLE ATTACH %s  (ID %d)",
                     obj->name, obj->dumpId);
            return;
        case DO_ATTRDEF:
            snprintf(buf, bufsize,
                     "ATTRDEF %s.%s  (ID %d OID %u)",
                     ((AttrDefInfo *) obj)->adtable->dobj.name,
                     ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_INDEX:
            snprintf(buf, bufsize,
                     "INDEX %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_INDEX_ATTACH:
            snprintf(buf, bufsize,
                     "INDEX ATTACH %s  (ID %d)",
                     obj->name, obj->dumpId);
            return;
        case DO_STATSEXT:
            snprintf(buf, bufsize,
                     "STATISTICS %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_REFRESH_MATVIEW:
            snprintf(buf, bufsize,
                     "REFRESH MATERIALIZED VIEW %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_RULE:
            snprintf(buf, bufsize,
                     "RULE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TRIGGER:
            snprintf(buf, bufsize,
                     "TRIGGER %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_EVENT_TRIGGER:
            snprintf(buf, bufsize,
                     "EVENT TRIGGER %s (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_CONSTRAINT:
            snprintf(buf, bufsize,
                     "CONSTRAINT %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_FK_CONSTRAINT:
            snprintf(buf, bufsize,
                     "FK CONSTRAINT %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_PROCLANG:
            snprintf(buf, bufsize,
                     "PROCEDURAL LANGUAGE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_CAST:
            snprintf(buf, bufsize,
                     "CAST %u to %u  (ID %d OID %u)",
                     ((CastInfo *) obj)->castsource,
                     ((CastInfo *) obj)->casttarget,
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_TRANSFORM:
            snprintf(buf, bufsize,
                     "TRANSFORM %u lang %u  (ID %d OID %u)",
                     ((TransformInfo *) obj)->trftype,
                     ((TransformInfo *) obj)->trflang,
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_TABLE_DATA:
            snprintf(buf, bufsize,
                     "TABLE DATA %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_SEQUENCE_SET:
            snprintf(buf, bufsize,
                     "SEQUENCE SET %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_DUMMY_TYPE:
            snprintf(buf, bufsize,
                     "DUMMY TYPE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TSPARSER:
            snprintf(buf, bufsize,
                     "TEXT SEARCH PARSER %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TSDICT:
            snprintf(buf, bufsize,
                     "TEXT SEARCH DICTIONARY %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TSTEMPLATE:
            snprintf(buf, bufsize,
                     "TEXT SEARCH TEMPLATE %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_TSCONFIG:
            snprintf(buf, bufsize,
                     "TEXT SEARCH CONFIGURATION %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_FDW:
            snprintf(buf, bufsize,
                     "FOREIGN DATA WRAPPER %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_FOREIGN_SERVER:
            snprintf(buf, bufsize,
                     "FOREIGN SERVER %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_DEFAULT_ACL:
            snprintf(buf, bufsize,
                     "DEFAULT ACL %s  (ID %d OID %u)",
                     obj->name, obj->dumpId, obj->catId.oid);
            return;
        case DO_LARGE_OBJECT:
            snprintf(buf, bufsize,
                     "LARGE OBJECT  (ID %d OID %u)",
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_LARGE_OBJECT_DATA:
            snprintf(buf, bufsize,
                     "LARGE OBJECT DATA  (ID %d)",
                     obj->dumpId);
            return;
        case DO_POLICY:
            snprintf(buf, bufsize,
                     "POLICY (ID %d OID %u)",
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_PUBLICATION:
            snprintf(buf, bufsize,
                     "PUBLICATION (ID %d OID %u)",
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_PUBLICATION_REL:
            snprintf(buf, bufsize,
                     "PUBLICATION TABLE (ID %d OID %u)",
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_PUBLICATION_TABLE_IN_SCHEMA:
            snprintf(buf, bufsize,
                     "PUBLICATION TABLES IN SCHEMA (ID %d OID %u)",
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_SUBSCRIPTION:
            snprintf(buf, bufsize,
                     "SUBSCRIPTION (ID %d OID %u)",
                     obj->dumpId, obj->catId.oid);
            return;
        case DO_PRE_DATA_BOUNDARY:
            snprintf(buf, bufsize,
                     "PRE-DATA BOUNDARY  (ID %d)",
                     obj->dumpId);
            return;
        case DO_POST_DATA_BOUNDARY:
            snprintf(buf, bufsize,
                     "POST-DATA BOUNDARY  (ID %d)",
                     obj->dumpId);
            return;
    }
    /* shouldn't get here */
    snprintf(buf, bufsize,
             "object type %d  (ID %d OID %u)",
             (int) obj->objType,
             obj->dumpId, obj->catId.oid);
}

References buf, bufsize, _dumpableObject::catId, DO_ACCESS_METHOD, DO_AGG, DO_ATTRDEF, DO_CAST, DO_COLLATION, DO_CONSTRAINT, DO_CONVERSION, DO_DEFAULT_ACL, DO_DUMMY_TYPE, DO_EVENT_TRIGGER, DO_EXTENSION, DO_FDW, DO_FK_CONSTRAINT, DO_FOREIGN_SERVER, DO_FUNC, DO_INDEX, DO_INDEX_ATTACH, DO_LARGE_OBJECT, DO_LARGE_OBJECT_DATA, DO_NAMESPACE, DO_OPCLASS, DO_OPERATOR, DO_OPFAMILY, DO_POLICY, DO_POST_DATA_BOUNDARY, DO_PRE_DATA_BOUNDARY, DO_PROCLANG, DO_PUBLICATION, DO_PUBLICATION_REL, DO_PUBLICATION_TABLE_IN_SCHEMA, DO_REFRESH_MATVIEW, DO_RULE, DO_SEQUENCE_SET, DO_SHELL_TYPE, DO_STATSEXT, DO_SUBSCRIPTION, DO_TABLE, DO_TABLE_ATTACH, DO_TABLE_DATA, DO_TRANSFORM, DO_TRIGGER, DO_TSCONFIG, DO_TSDICT, DO_TSPARSER, DO_TSTEMPLATE, DO_TYPE, _dumpableObject::dumpId, _dumpableObject::name, _dumpableObject::objType, CatalogId::oid, and snprintf.

Referenced by repairDependencyLoop().

DOTypeNameCompare()

static int DOTypeNameCompare ( const void *  p1, const void *  p2  )

static

Definition at line 194 of file pg_dump_sort.c.

{
    DumpableObject *obj1 = *(DumpableObject *const *) p1;
    DumpableObject *obj2 = *(DumpableObject *const *) p2;
    int         cmpval;
 
    /* Sort by type's priority */
    cmpval = dbObjectTypePriority[obj1->objType] -
        dbObjectTypePriority[obj2->objType];
 
    if (cmpval != 0)
        return cmpval;
 
    /*
     * Sort by namespace.  Typically, all objects of the same priority would
     * either have or not have a namespace link, but there are exceptions.
     * Sort NULL namespace after non-NULL in such cases.
     */
    if (obj1->namespace)
    {
        if (obj2->namespace)
        {
            cmpval = strcmp(obj1->namespace->dobj.name,
                            obj2->namespace->dobj.name);
            if (cmpval != 0)
                return cmpval;
        }
        else
            return -1;
    }
    else if (obj2->namespace)
        return 1;
 
    /* Sort by name */
    cmpval = strcmp(obj1->name, obj2->name);
    if (cmpval != 0)
        return cmpval;
 
    /* To have a stable sort order, break ties for some object types */
    if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
    {
        FuncInfo   *fobj1 = *(FuncInfo *const *) p1;
        FuncInfo   *fobj2 = *(FuncInfo *const *) p2;
        int         i;
 
        /* Sort by number of arguments, then argument type names */
        cmpval = fobj1->nargs - fobj2->nargs;
        if (cmpval != 0)
            return cmpval;
        for (i = 0; i < fobj1->nargs; i++)
        {
            TypeInfo   *argtype1 = findTypeByOid(fobj1->argtypes[i]);
            TypeInfo   *argtype2 = findTypeByOid(fobj2->argtypes[i]);
 
            if (argtype1 && argtype2)
            {
                if (argtype1->dobj.namespace && argtype2->dobj.namespace)
                {
                    cmpval = strcmp(argtype1->dobj.namespace->dobj.name,
                                    argtype2->dobj.namespace->dobj.name);
                    if (cmpval != 0)
                        return cmpval;
                }
                cmpval = strcmp(argtype1->dobj.name, argtype2->dobj.name);
                if (cmpval != 0)
                    return cmpval;
            }
        }
    }
    else if (obj1->objType == DO_OPERATOR)
    {
        OprInfo    *oobj1 = *(OprInfo *const *) p1;
        OprInfo    *oobj2 = *(OprInfo *const *) p2;
 
        /* oprkind is 'l', 'r', or 'b'; this sorts prefix, postfix, infix */
        cmpval = (oobj2->oprkind - oobj1->oprkind);
        if (cmpval != 0)
            return cmpval;
    }
    else if (obj1->objType == DO_ATTRDEF)
    {
        AttrDefInfo *adobj1 = *(AttrDefInfo *const *) p1;
        AttrDefInfo *adobj2 = *(AttrDefInfo *const *) p2;
 
        /* Sort by attribute number */
        cmpval = (adobj1->adnum - adobj2->adnum);
        if (cmpval != 0)
            return cmpval;
    }
    else if (obj1->objType == DO_POLICY)
    {
        PolicyInfo *pobj1 = *(PolicyInfo *const *) p1;
        PolicyInfo *pobj2 = *(PolicyInfo *const *) p2;
 
        /* Sort by table name (table namespace was considered already) */
        cmpval = strcmp(pobj1->poltable->dobj.name,
                        pobj2->poltable->dobj.name);
        if (cmpval != 0)
            return cmpval;
    }
    else if (obj1->objType == DO_TRIGGER)
    {
        TriggerInfo *tobj1 = *(TriggerInfo *const *) p1;
        TriggerInfo *tobj2 = *(TriggerInfo *const *) p2;
 
        /* Sort by table name (table namespace was considered already) */
        cmpval = strcmp(tobj1->tgtable->dobj.name,
                        tobj2->tgtable->dobj.name);
        if (cmpval != 0)
            return cmpval;
    }
 
    /* Usually shouldn't get here, but if we do, sort by OID */
    return oidcmp(obj1->catId.oid, obj2->catId.oid);
}

References _attrDefInfo::adnum, _funcInfo::argtypes, _dumpableObject::catId, dbObjectTypePriority, DO_AGG, DO_ATTRDEF, DO_FUNC, DO_OPERATOR, DO_POLICY, DO_TRIGGER, _typeInfo::dobj, _tableInfo::dobj, findTypeByOid(), i, _dumpableObject::name, _funcInfo::nargs, _dumpableObject::objType, CatalogId::oid, oidcmp, _oprInfo::oprkind, p2, _policyInfo::poltable, and _triggerInfo::tgtable.

Referenced by sortDumpableObjectsByTypeName().

findDependencyLoops()

static void findDependencyLoops ( DumpableObject **  objs, int  nObjs, int  totObjs  )

static

Definition at line 590 of file pg_dump_sort.c.

{
    /*
     * We use three data structures here:
     *
     * processed[] is a bool array indexed by dump ID, marking the objects
     * already processed during this invocation of findDependencyLoops().
     *
     * searchFailed[] is another array indexed by dump ID.  searchFailed[j] is
     * set to dump ID k if we have proven that there is no dependency path
     * leading from object j back to start point k.  This allows us to skip
     * useless searching when there are multiple dependency paths from k to j,
     * which is a common situation.  We could use a simple bool array for
     * this, but then we'd need to re-zero it for each start point, resulting
     * in O(N^2) zeroing work.  Using the start point's dump ID as the "true"
     * value lets us skip clearing the array before we consider the next start
     * point.
     *
     * workspace[] is an array of DumpableObject pointers, in which we try to
     * build lists of objects constituting loops.  We make workspace[] large
     * enough to hold all the objects in TopoSort's output, which is huge
     * overkill in most cases but could theoretically be necessary if there is
     * a single dependency chain linking all the objects.
     */
    bool       *processed;
    DumpId     *searchFailed;
    DumpableObject **workspace;
    bool        fixedloop;
    int         i;
 
    processed = (bool *) pg_malloc0((getMaxDumpId() + 1) * sizeof(bool));
    searchFailed = (DumpId *) pg_malloc0((getMaxDumpId() + 1) * sizeof(DumpId));
    workspace = (DumpableObject **) pg_malloc(totObjs * sizeof(DumpableObject *));
    fixedloop = false;
 
    for (i = 0; i < nObjs; i++)
    {
        DumpableObject *obj = objs[i];
        int         looplen;
        int         j;
 
        looplen = findLoop(obj,
                           obj->dumpId,
                           processed,
                           searchFailed,
                           workspace,
                           0);
 
        if (looplen > 0)
        {
            /* Found a loop, repair it */
            repairDependencyLoop(workspace, looplen);
            fixedloop = true;
            /* Mark loop members as processed */
            for (j = 0; j < looplen; j++)
                processed[workspace[j]->dumpId] = true;
        }
        else
        {
            /*
             * There's no loop starting at this object, but mark it processed
             * anyway.  This is not necessary for correctness, but saves later
             * invocations of findLoop() from uselessly chasing references to
             * such an object.
             */
            processed[obj->dumpId] = true;
        }
    }
 
    /* We'd better have fixed at least one loop */
    if (!fixedloop)
        pg_fatal("could not identify dependency loop");
 
    free(workspace);
    free(searchFailed);
    free(processed);
}

References _dumpableObject::dumpId, findLoop(), free, getMaxDumpId(), i, j, pg_fatal, pg_malloc(), pg_malloc0(), and repairDependencyLoop().

Referenced by sortDumpableObjects().

findLoop()

static int findLoop ( DumpableObject *  obj, DumpId  startPoint, bool *  processed, DumpId *  searchFailed, DumpableObject **  workspace, int  depth  )

static

Definition at line 686 of file pg_dump_sort.c.

{
    int         i;
 
    /*
     * Reject if obj is already processed.  This test prevents us from finding
     * loops that overlap previously-processed loops.
     */
    if (processed[obj->dumpId])
        return 0;
 
    /*
     * If we've already proven there is no path from this object back to the
     * startPoint, forget it.
     */
    if (searchFailed[obj->dumpId] == startPoint)
        return 0;
 
    /*
     * Reject if obj is already present in workspace.  This test prevents us
     * from going into infinite recursion if we are given a startPoint object
     * that links to a cycle it's not a member of, and it guarantees that we
     * can't overflow the allocated size of workspace[].
     */
    for (i = 0; i < depth; i++)
    {
        if (workspace[i] == obj)
            return 0;
    }
 
    /*
     * Okay, tentatively add obj to workspace
     */
    workspace[depth++] = obj;
 
    /*
     * See if we've found a loop back to the desired startPoint; if so, done
     */
    for (i = 0; i < obj->nDeps; i++)
    {
        if (obj->dependencies[i] == startPoint)
            return depth;
    }
 
    /*
     * Recurse down each outgoing branch
     */
    for (i = 0; i < obj->nDeps; i++)
    {
        DumpableObject *nextobj = findObjectByDumpId(obj->dependencies[i]);
        int         newDepth;
 
        if (!nextobj)
            continue;           /* ignore dependencies on undumped objects */
        newDepth = findLoop(nextobj,
                            startPoint,
                            processed,
                            searchFailed,
                            workspace,
                            depth);
        if (newDepth > 0)
            return newDepth;
    }
 
    /*
     * Remember there is no path from here back to startPoint
     */
    searchFailed[obj->dumpId] = startPoint;
 
    return 0;
}

References _dumpableObject::dependencies, _dumpableObject::dumpId, findObjectByDumpId(), i, and _dumpableObject::nDeps.

Referenced by findDependencyLoops().

removeHeapElement()

static int removeHeapElement ( int *  heap, int  heapLength  )

static

Definition at line 545 of file pg_dump_sort.c.

{
    int         result = heap[0];
    int         val;
    int         i;
 
    if (--heapLength <= 0)
        return result;
    val = heap[heapLength];     /* value that must be reinserted */
    i = 0;                      /* i is where the "hole" is */
    for (;;)
    {
        int         j = 2 * i + 1;
 
        if (j >= heapLength)
            break;
        if (j + 1 < heapLength &&
            heap[j] < heap[j + 1])
            j++;
        if (val >= heap[j])
            break;
        heap[i] = heap[j];
        i = j;
    }
    heap[i] = val;
    return result;
}

References i, j, and val.

Referenced by TopoSort().

repairDependencyLoop()

static void repairDependencyLoop ( DumpableObject **  loop, int  nLoop  )

static

Definition at line 971 of file pg_dump_sort.c.

{
    int         i,
                j;
 
    /* Datatype and one of its I/O or canonicalize functions */
    if (nLoop == 2 &&
        loop[0]->objType == DO_TYPE &&
        loop[1]->objType == DO_FUNC)
    {
        repairTypeFuncLoop(loop[0], loop[1]);
        return;
    }
    if (nLoop == 2 &&
        loop[1]->objType == DO_TYPE &&
        loop[0]->objType == DO_FUNC)
    {
        repairTypeFuncLoop(loop[1], loop[0]);
        return;
    }
 
    /* View (including matview) and its ON SELECT rule */
    if (nLoop == 2 &&
        loop[0]->objType == DO_TABLE &&
        loop[1]->objType == DO_RULE &&
        (((TableInfo *) loop[0])->relkind == RELKIND_VIEW ||
         ((TableInfo *) loop[0])->relkind == RELKIND_MATVIEW) &&
        ((RuleInfo *) loop[1])->ev_type == '1' &&
        ((RuleInfo *) loop[1])->is_instead &&
        ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
    {
        repairViewRuleLoop(loop[0], loop[1]);
        return;
    }
    if (nLoop == 2 &&
        loop[1]->objType == DO_TABLE &&
        loop[0]->objType == DO_RULE &&
        (((TableInfo *) loop[1])->relkind == RELKIND_VIEW ||
         ((TableInfo *) loop[1])->relkind == RELKIND_MATVIEW) &&
        ((RuleInfo *) loop[0])->ev_type == '1' &&
        ((RuleInfo *) loop[0])->is_instead &&
        ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
    {
        repairViewRuleLoop(loop[1], loop[0]);
        return;
    }
 
    /* Indirect loop involving view (but not matview) and ON SELECT rule */
    if (nLoop > 2)
    {
        for (i = 0; i < nLoop; i++)
        {
            if (loop[i]->objType == DO_TABLE &&
                ((TableInfo *) loop[i])->relkind == RELKIND_VIEW)
            {
                for (j = 0; j < nLoop; j++)
                {
                    if (loop[j]->objType == DO_RULE &&
                        ((RuleInfo *) loop[j])->ev_type == '1' &&
                        ((RuleInfo *) loop[j])->is_instead &&
                        ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
                    {
                        repairViewRuleMultiLoop(loop[i], loop[j]);
                        return;
                    }
                }
            }
        }
    }
 
    /* Indirect loop involving matview and data boundary */
    if (nLoop > 2)
    {
        for (i = 0; i < nLoop; i++)
        {
            if (loop[i]->objType == DO_TABLE &&
                ((TableInfo *) loop[i])->relkind == RELKIND_MATVIEW)
            {
                for (j = 0; j < nLoop; j++)
                {
                    if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
                    {
                        DumpableObject *nextobj;
 
                        nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
                        repairMatViewBoundaryMultiLoop(loop[j], nextobj);
                        return;
                    }
                }
            }
        }
    }
 
    /* Table and CHECK constraint */
    if (nLoop == 2 &&
        loop[0]->objType == DO_TABLE &&
        loop[1]->objType == DO_CONSTRAINT &&
        ((ConstraintInfo *) loop[1])->contype == 'c' &&
        ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
    {
        repairTableConstraintLoop(loop[0], loop[1]);
        return;
    }
    if (nLoop == 2 &&
        loop[1]->objType == DO_TABLE &&
        loop[0]->objType == DO_CONSTRAINT &&
        ((ConstraintInfo *) loop[0])->contype == 'c' &&
        ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
    {
        repairTableConstraintLoop(loop[1], loop[0]);
        return;
    }
 
    /* Indirect loop involving table and CHECK constraint */
    if (nLoop > 2)
    {
        for (i = 0; i < nLoop; i++)
        {
            if (loop[i]->objType == DO_TABLE)
            {
                for (j = 0; j < nLoop; j++)
                {
                    if (loop[j]->objType == DO_CONSTRAINT &&
                        ((ConstraintInfo *) loop[j])->contype == 'c' &&
                        ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
                    {
                        repairTableConstraintMultiLoop(loop[i], loop[j]);
                        return;
                    }
                }
            }
        }
    }
 
    /* Table and attribute default */
    if (nLoop == 2 &&
        loop[0]->objType == DO_TABLE &&
        loop[1]->objType == DO_ATTRDEF &&
        ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
    {
        repairTableAttrDefLoop(loop[0], loop[1]);
        return;
    }
    if (nLoop == 2 &&
        loop[1]->objType == DO_TABLE &&
        loop[0]->objType == DO_ATTRDEF &&
        ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
    {
        repairTableAttrDefLoop(loop[1], loop[0]);
        return;
    }
 
    /* index on partitioned table and corresponding index on partition */
    if (nLoop == 2 &&
        loop[0]->objType == DO_INDEX &&
        loop[1]->objType == DO_INDEX)
    {
        if (((IndxInfo *) loop[0])->parentidx == loop[1]->catId.oid)
        {
            repairIndexLoop(loop[0], loop[1]);
            return;
        }
        else if (((IndxInfo *) loop[1])->parentidx == loop[0]->catId.oid)
        {
            repairIndexLoop(loop[1], loop[0]);
            return;
        }
    }
 
    /* Indirect loop involving table and attribute default */
    if (nLoop > 2)
    {
        for (i = 0; i < nLoop; i++)
        {
            if (loop[i]->objType == DO_TABLE)
            {
                for (j = 0; j < nLoop; j++)
                {
                    if (loop[j]->objType == DO_ATTRDEF &&
                        ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
                    {
                        repairTableAttrDefMultiLoop(loop[i], loop[j]);
                        return;
                    }
                }
            }
        }
    }
 
    /* Domain and CHECK constraint */
    if (nLoop == 2 &&
        loop[0]->objType == DO_TYPE &&
        loop[1]->objType == DO_CONSTRAINT &&
        ((ConstraintInfo *) loop[1])->contype == 'c' &&
        ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
    {
        repairDomainConstraintLoop(loop[0], loop[1]);
        return;
    }
    if (nLoop == 2 &&
        loop[1]->objType == DO_TYPE &&
        loop[0]->objType == DO_CONSTRAINT &&
        ((ConstraintInfo *) loop[0])->contype == 'c' &&
        ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
    {
        repairDomainConstraintLoop(loop[1], loop[0]);
        return;
    }
 
    /* Indirect loop involving domain and CHECK constraint */
    if (nLoop > 2)
    {
        for (i = 0; i < nLoop; i++)
        {
            if (loop[i]->objType == DO_TYPE)
            {
                for (j = 0; j < nLoop; j++)
                {
                    if (loop[j]->objType == DO_CONSTRAINT &&
                        ((ConstraintInfo *) loop[j])->contype == 'c' &&
                        ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
                    {
                        repairDomainConstraintMultiLoop(loop[i], loop[j]);
                        return;
                    }
                }
            }
        }
    }
 
    /*
     * Loop of table with itself --- just ignore it.
     *
     * (Actually, what this arises from is a dependency of a table column on
     * another column, which happened with generated columns before v15; or a
     * dependency of a table column on the whole table, which happens with
     * partitioning.  But we didn't pay attention to sub-object IDs while
     * collecting the dependency data, so we can't see that here.)
     */
    if (nLoop == 1)
    {
        if (loop[0]->objType == DO_TABLE)
        {
            removeObjectDependency(loop[0], loop[0]->dumpId);
            return;
        }
    }
 
    /*
     * If all the objects are TABLE_DATA items, what we must have is a
     * circular set of foreign key constraints (or a single self-referential
     * table).  Print an appropriate complaint and break the loop arbitrarily.
     */
    for (i = 0; i < nLoop; i++)
    {
        if (loop[i]->objType != DO_TABLE_DATA)
            break;
    }
    if (i >= nLoop)
    {
        pg_log_warning(ngettext("there are circular foreign-key constraints on this table:",
                                "there are circular foreign-key constraints among these tables:",
                                nLoop));
        for (i = 0; i < nLoop; i++)
            pg_log_info("  %s", loop[i]->name);
        pg_log_info("You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.");
        pg_log_info("Consider using a full dump instead of a --data-only dump to avoid this problem.");
        if (nLoop > 1)
            removeObjectDependency(loop[0], loop[1]->dumpId);
        else                    /* must be a self-dependency */
            removeObjectDependency(loop[0], loop[0]->dumpId);
        return;
    }
 
    /*
     * If we can't find a principled way to break the loop, complain and break
     * it in an arbitrary fashion.
     */
    pg_log_warning("could not resolve dependency loop among these items:");
    for (i = 0; i < nLoop; i++)
    {
        char        buf[1024];
 
        describeDumpableObject(loop[i], buf, sizeof(buf));
        pg_log_info("  %s", buf);
    }
 
    if (nLoop > 1)
        removeObjectDependency(loop[0], loop[1]->dumpId);
    else                        /* must be a self-dependency */
        removeObjectDependency(loop[0], loop[0]->dumpId);
}

References buf, describeDumpableObject(), DO_ATTRDEF, DO_CONSTRAINT, DO_FUNC, DO_INDEX, DO_PRE_DATA_BOUNDARY, DO_RULE, DO_TABLE, DO_TABLE_DATA, DO_TYPE, i, j, name, ngettext, pg_log_info, pg_log_warning, removeObjectDependency(), repairDomainConstraintLoop(), repairDomainConstraintMultiLoop(), repairIndexLoop(), repairMatViewBoundaryMultiLoop(), repairTableAttrDefLoop(), repairTableAttrDefMultiLoop(), repairTableConstraintLoop(), repairTableConstraintMultiLoop(), repairTypeFuncLoop(), repairViewRuleLoop(), and repairViewRuleMultiLoop().

Referenced by findDependencyLoops().

repairDomainConstraintLoop()

static void repairDomainConstraintLoop ( DumpableObject *  domainobj, DumpableObject *  constraintobj  )

static

Definition at line 935 of file pg_dump_sort.c.

{
    /* remove constraint's dependency on domain */
    removeObjectDependency(constraintobj, domainobj->dumpId);
}

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairDomainConstraintMultiLoop()

static void repairDomainConstraintMultiLoop ( DumpableObject *  domainobj, DumpableObject *  constraintobj  )

static

Definition at line 943 of file pg_dump_sort.c.

{
    /* remove domain's dependency on constraint */
    removeObjectDependency(domainobj, constraintobj->dumpId);
    /* mark constraint as needing its own dump */
    ((ConstraintInfo *) constraintobj)->separate = true;
    /* put back constraint's dependency on domain */
    addObjectDependency(constraintobj, domainobj->dumpId);
    /* now that constraint is separate, it must be post-data */
    addObjectDependency(constraintobj, postDataBoundId);
}

References addObjectDependency(), _dumpableObject::dumpId, postDataBoundId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairIndexLoop()

static void repairIndexLoop ( DumpableObject *  partedindex, DumpableObject *  partindex  )

static

Definition at line 957 of file pg_dump_sort.c.

{
    removeObjectDependency(partedindex, partindex->dumpId);
}

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairMatViewBoundaryMultiLoop()

static void repairMatViewBoundaryMultiLoop ( DumpableObject *  boundaryobj, DumpableObject *  nextobj  )

static

Definition at line 856 of file pg_dump_sort.c.

{
    /* remove boundary's dependency on object after it in loop */
    removeObjectDependency(boundaryobj, nextobj->dumpId);
    /* if that object is a matview, mark it as postponed into post-data */
    if (nextobj->objType == DO_TABLE)
    {
        TableInfo  *nextinfo = (TableInfo *) nextobj;
 
        if (nextinfo->relkind == RELKIND_MATVIEW)
            nextinfo->postponed_def = true;
    }
}

References DO_TABLE, _dumpableObject::dumpId, _dumpableObject::objType, _tableInfo::postponed_def, _tableInfo::relkind, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairTableAttrDefLoop()

static void repairTableAttrDefLoop ( DumpableObject *  tableobj, DumpableObject *  attrdefobj  )

static

Definition at line 912 of file pg_dump_sort.c.

{
    /* remove attrdef's dependency on table */
    removeObjectDependency(attrdefobj, tableobj->dumpId);
}

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairTableAttrDefMultiLoop()

static void repairTableAttrDefMultiLoop ( DumpableObject *  tableobj, DumpableObject *  attrdefobj  )

static

Definition at line 920 of file pg_dump_sort.c.

{
    /* remove table's dependency on attrdef */
    removeObjectDependency(tableobj, attrdefobj->dumpId);
    /* mark attrdef as needing its own dump */
    ((AttrDefInfo *) attrdefobj)->separate = true;
    /* put back attrdef's dependency on table */
    addObjectDependency(attrdefobj, tableobj->dumpId);
}

References addObjectDependency(), _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairTableConstraintLoop()

static void repairTableConstraintLoop ( DumpableObject *  tableobj, DumpableObject *  constraintobj  )

static

Definition at line 878 of file pg_dump_sort.c.

{
    /* remove constraint's dependency on table */
    removeObjectDependency(constraintobj, tableobj->dumpId);
}

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairTableConstraintMultiLoop()

static void repairTableConstraintMultiLoop ( DumpableObject *  tableobj, DumpableObject *  constraintobj  )

static

Definition at line 895 of file pg_dump_sort.c.

{
    /* remove table's dependency on constraint */
    removeObjectDependency(tableobj, constraintobj->dumpId);
    /* mark constraint as needing its own dump */
    ((ConstraintInfo *) constraintobj)->separate = true;
    /* put back constraint's dependency on table */
    addObjectDependency(constraintobj, tableobj->dumpId);
    /* now that constraint is separate, it must be post-data */
    addObjectDependency(constraintobj, postDataBoundId);
}

References addObjectDependency(), _dumpableObject::dumpId, postDataBoundId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairTypeFuncLoop()

static void repairTypeFuncLoop ( DumpableObject *  typeobj, DumpableObject *  funcobj  )

static

Definition at line 771 of file pg_dump_sort.c.

{
    TypeInfo   *typeInfo = (TypeInfo *) typeobj;
 
    /* remove function's dependency on type */
    removeObjectDependency(funcobj, typeobj->dumpId);
 
    /* add function's dependency on shell type, instead */
    if (typeInfo->shellType)
    {
        addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
 
        /*
         * Mark shell type (always including the definition, as we need the
         * shell type defined to identify the function fully) as to be dumped
         * if any such function is
         */
        if (funcobj->dump)
            typeInfo->shellType->dobj.dump = funcobj->dump |
                DUMP_COMPONENT_DEFINITION;
    }
}

References addObjectDependency(), _shellTypeInfo::dobj, _dumpableObject::dump, DUMP_COMPONENT_DEFINITION, _dumpableObject::dumpId, removeObjectDependency(), and _typeInfo::shellType.

Referenced by repairDependencyLoop().

repairViewRuleLoop()

static void repairViewRuleLoop ( DumpableObject *  viewobj, DumpableObject *  ruleobj  )

static

Definition at line 802 of file pg_dump_sort.c.

{
    /* remove rule's dependency on view */
    removeObjectDependency(ruleobj, viewobj->dumpId);
    /* flags on the two objects are already set correctly for this case */
}

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

repairViewRuleMultiLoop()

static void repairViewRuleMultiLoop ( DumpableObject *  viewobj, DumpableObject *  ruleobj  )

static

Definition at line 822 of file pg_dump_sort.c.

{
    TableInfo  *viewinfo = (TableInfo *) viewobj;
    RuleInfo   *ruleinfo = (RuleInfo *) ruleobj;
 
    /* remove view's dependency on rule */
    removeObjectDependency(viewobj, ruleobj->dumpId);
    /* mark view to be printed with a dummy definition */
    viewinfo->dummy_view = true;
    /* mark rule as needing its own dump */
    ruleinfo->separate = true;
    /* put back rule's dependency on view */
    addObjectDependency(ruleobj, viewobj->dumpId);
    /* now that rule is separate, it must be post-data */
    addObjectDependency(ruleobj, postDataBoundId);
}

References addObjectDependency(), _tableInfo::dummy_view, _dumpableObject::dumpId, postDataBoundId, removeObjectDependency(), and _ruleInfo::separate.

Referenced by repairDependencyLoop().

sortDumpableObjects()

void sortDumpableObjects	(	DumpableObject **	objs,
		int	numObjs,
		DumpId	preBoundaryId,
		DumpId	postBoundaryId
	)

Definition at line 319 of file pg_dump_sort.c.

{
    DumpableObject **ordering;
    int         nOrdering;
 
    if (numObjs <= 0)           /* can't happen anymore ... */
        return;
 
    /*
     * Saving the boundary IDs in static variables is a bit grotty, but seems
     * better than adding them to parameter lists of subsidiary functions.
     */
    preDataBoundId = preBoundaryId;
    postDataBoundId = postBoundaryId;
 
    ordering = (DumpableObject **) pg_malloc(numObjs * sizeof(DumpableObject *));
    while (!TopoSort(objs, numObjs, ordering, &nOrdering))
        findDependencyLoops(ordering, nOrdering, numObjs);
 
    memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));
 
    free(ordering);
}

References findDependencyLoops(), free, pg_malloc(), postDataBoundId, preDataBoundId, and TopoSort().

Referenced by main().

sortDumpableObjectsByTypeName()

void sortDumpableObjectsByTypeName	(	DumpableObject **	objs,
		int	numObjs
	)

Definition at line 186 of file pg_dump_sort.c.

{
    if (numObjs > 1)
        qsort(objs, numObjs, sizeof(DumpableObject *),
              DOTypeNameCompare);
}

References DOTypeNameCompare(), and qsort.

Referenced by main().

StaticAssertDecl()

StaticAssertDecl	(	lengthof(dbObjectTypePriority)	= =(DO_SUBSCRIPTION+1),
		"array length mismatch"
	)

TopoSort()

static bool TopoSort ( DumpableObject **  objs, int  numObjs, DumpableObject **  ordering, int *  nOrdering  )

static

Definition at line 371 of file pg_dump_sort.c.

{
    DumpId      maxDumpId = getMaxDumpId();
    int        *pendingHeap;
    int        *beforeConstraints;
    int        *idMap;
    DumpableObject *obj;
    int         heapLength;
    int         i,
                j,
                k;
 
    /*
     * This is basically the same algorithm shown for topological sorting in
     * Knuth's Volume 1.  However, we would like to minimize unnecessary
     * rearrangement of the input ordering; that is, when we have a choice of
     * which item to output next, we always want to take the one highest in
     * the original list.  Therefore, instead of maintaining an unordered
     * linked list of items-ready-to-output as Knuth does, we maintain a heap
     * of their item numbers, which we can use as a priority queue.  This
     * turns the algorithm from O(N) to O(N log N) because each insertion or
     * removal of a heap item takes O(log N) time.  However, that's still
     * plenty fast enough for this application.
     */
 
    *nOrdering = numObjs;       /* for success return */
 
    /* Eliminate the null case */
    if (numObjs <= 0)
        return true;
 
    /* Create workspace for the above-described heap */
    pendingHeap = (int *) pg_malloc(numObjs * sizeof(int));
 
    /*
     * Scan the constraints, and for each item in the input, generate a count
     * of the number of constraints that say it must be before something else.
     * The count for the item with dumpId j is stored in beforeConstraints[j].
     * We also make a map showing the input-order index of the item with
     * dumpId j.
     */
    beforeConstraints = (int *) pg_malloc0((maxDumpId + 1) * sizeof(int));
    idMap = (int *) pg_malloc((maxDumpId + 1) * sizeof(int));
    for (i = 0; i < numObjs; i++)
    {
        obj = objs[i];
        j = obj->dumpId;
        if (j <= 0 || j > maxDumpId)
            pg_fatal("invalid dumpId %d", j);
        idMap[j] = i;
        for (j = 0; j < obj->nDeps; j++)
        {
            k = obj->dependencies[j];
            if (k <= 0 || k > maxDumpId)
                pg_fatal("invalid dependency %d", k);
            beforeConstraints[k]++;
        }
    }
 
    /*
     * Now initialize the heap of items-ready-to-output by filling it with the
     * indexes of items that already have beforeConstraints[id] == 0.
     *
     * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
     * in the range 1..heapLength-1 (note we are using 0-based subscripts
     * here, while the discussion in Knuth assumes 1-based subscripts). So, if
     * we simply enter the indexes into pendingHeap[] in decreasing order, we
     * a-fortiori have the heap invariant satisfied at completion of this
     * loop, and don't need to do any sift-up comparisons.
     */
    heapLength = 0;
    for (i = numObjs; --i >= 0;)
    {
        if (beforeConstraints[objs[i]->dumpId] == 0)
            pendingHeap[heapLength++] = i;
    }
 
    /*--------------------
     * Now emit objects, working backwards in the output list.  At each step,
     * we use the priority heap to select the last item that has no remaining
     * before-constraints.  We remove that item from the heap, output it to
     * ordering[], and decrease the beforeConstraints count of each of the
     * items it was constrained against.  Whenever an item's beforeConstraints
     * count is thereby decreased to zero, we insert it into the priority heap
     * to show that it is a candidate to output.  We are done when the heap
     * becomes empty; if we have output every element then we succeeded,
     * otherwise we failed.
     * i = number of ordering[] entries left to output
     * j = objs[] index of item we are outputting
     * k = temp for scanning constraint list for item j
     *--------------------
     */
    i = numObjs;
    while (heapLength > 0)
    {
        /* Select object to output by removing largest heap member */
        j = removeHeapElement(pendingHeap, heapLength--);
        obj = objs[j];
        /* Output candidate to ordering[] */
        ordering[--i] = obj;
        /* Update beforeConstraints counts of its predecessors */
        for (k = 0; k < obj->nDeps; k++)
        {
            int         id = obj->dependencies[k];
 
            if ((--beforeConstraints[id]) == 0)
                addHeapElement(idMap[id], pendingHeap, heapLength++);
        }
    }
 
    /*
     * If we failed, report the objects that couldn't be output; these are the
     * ones with beforeConstraints[] still nonzero.
     */
    if (i != 0)
    {
        k = 0;
        for (j = 1; j <= maxDumpId; j++)
        {
            if (beforeConstraints[j] != 0)
                ordering[k++] = objs[idMap[j]];
        }
        *nOrdering = k;
    }
 
    /* Done */
    free(pendingHeap);
    free(beforeConstraints);
    free(idMap);
 
    return (i == 0);
}

References addHeapElement(), beforeConstraints, _dumpableObject::dependencies, _dumpableObject::dumpId, free, getMaxDumpId(), i, j, _dumpableObject::nDeps, pg_fatal, pg_malloc(), pg_malloc0(), and removeHeapElement().

Referenced by sortDumpableObjects().

Variable Documentation

dbObjectTypePriority

const int dbObjectTypePriority[]

static

Definition at line 102 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

postDataBoundId

DumpId postDataBoundId

static

Definition at line 156 of file pg_dump_sort.c.

Referenced by repairDomainConstraintMultiLoop(), repairTableConstraintMultiLoop(), repairViewRuleMultiLoop(), and sortDumpableObjects().

preDataBoundId

DumpId preDataBoundId

static

Definition at line 155 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().