PostgreSQL Source Code  git master
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.

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
 

Function Documentation

◆ addHeapElement()

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

Definition at line 445 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

446 {
447  int j;
448 
449  /*
450  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
451  * using 1-based array indexes, not 0-based.
452  */
453  j = heapLength;
454  while (j > 0)
455  {
456  int i = (j - 1) >> 1;
457 
458  if (val <= heap[i])
459  break;
460  heap[j] = heap[i];
461  j = i;
462  }
463  heap[j] = val;
464 }
int i
long val
Definition: informix.c:664

◆ describeDumpableObject()

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

Definition at line 1202 of file pg_dump_sort.c.

References _dumpableObject::catId, DO_ACCESS_METHOD, DO_AGG, DO_ATTRDEF, DO_BLOB, DO_BLOB_DATA, 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_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_REFRESH_MATVIEW, DO_RULE, DO_SEQUENCE_SET, DO_SHELL_TYPE, DO_STATSEXT, DO_SUBSCRIPTION, DO_TABLE, 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().

1203 {
1204  switch (obj->objType)
1205  {
1206  case DO_NAMESPACE:
1207  snprintf(buf, bufsize,
1208  "SCHEMA %s (ID %d OID %u)",
1209  obj->name, obj->dumpId, obj->catId.oid);
1210  return;
1211  case DO_EXTENSION:
1212  snprintf(buf, bufsize,
1213  "EXTENSION %s (ID %d OID %u)",
1214  obj->name, obj->dumpId, obj->catId.oid);
1215  return;
1216  case DO_TYPE:
1217  snprintf(buf, bufsize,
1218  "TYPE %s (ID %d OID %u)",
1219  obj->name, obj->dumpId, obj->catId.oid);
1220  return;
1221  case DO_SHELL_TYPE:
1222  snprintf(buf, bufsize,
1223  "SHELL TYPE %s (ID %d OID %u)",
1224  obj->name, obj->dumpId, obj->catId.oid);
1225  return;
1226  case DO_FUNC:
1227  snprintf(buf, bufsize,
1228  "FUNCTION %s (ID %d OID %u)",
1229  obj->name, obj->dumpId, obj->catId.oid);
1230  return;
1231  case DO_AGG:
1232  snprintf(buf, bufsize,
1233  "AGGREGATE %s (ID %d OID %u)",
1234  obj->name, obj->dumpId, obj->catId.oid);
1235  return;
1236  case DO_OPERATOR:
1237  snprintf(buf, bufsize,
1238  "OPERATOR %s (ID %d OID %u)",
1239  obj->name, obj->dumpId, obj->catId.oid);
1240  return;
1241  case DO_ACCESS_METHOD:
1242  snprintf(buf, bufsize,
1243  "ACCESS METHOD %s (ID %d OID %u)",
1244  obj->name, obj->dumpId, obj->catId.oid);
1245  return;
1246  case DO_OPCLASS:
1247  snprintf(buf, bufsize,
1248  "OPERATOR CLASS %s (ID %d OID %u)",
1249  obj->name, obj->dumpId, obj->catId.oid);
1250  return;
1251  case DO_OPFAMILY:
1252  snprintf(buf, bufsize,
1253  "OPERATOR FAMILY %s (ID %d OID %u)",
1254  obj->name, obj->dumpId, obj->catId.oid);
1255  return;
1256  case DO_COLLATION:
1257  snprintf(buf, bufsize,
1258  "COLLATION %s (ID %d OID %u)",
1259  obj->name, obj->dumpId, obj->catId.oid);
1260  return;
1261  case DO_CONVERSION:
1262  snprintf(buf, bufsize,
1263  "CONVERSION %s (ID %d OID %u)",
1264  obj->name, obj->dumpId, obj->catId.oid);
1265  return;
1266  case DO_TABLE:
1267  snprintf(buf, bufsize,
1268  "TABLE %s (ID %d OID %u)",
1269  obj->name, obj->dumpId, obj->catId.oid);
1270  return;
1271  case DO_ATTRDEF:
1272  snprintf(buf, bufsize,
1273  "ATTRDEF %s.%s (ID %d OID %u)",
1274  ((AttrDefInfo *) obj)->adtable->dobj.name,
1275  ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
1276  obj->dumpId, obj->catId.oid);
1277  return;
1278  case DO_INDEX:
1279  snprintf(buf, bufsize,
1280  "INDEX %s (ID %d OID %u)",
1281  obj->name, obj->dumpId, obj->catId.oid);
1282  return;
1283  case DO_INDEX_ATTACH:
1284  snprintf(buf, bufsize,
1285  "INDEX ATTACH %s (ID %d)",
1286  obj->name, obj->dumpId);
1287  return;
1288  case DO_STATSEXT:
1289  snprintf(buf, bufsize,
1290  "STATISTICS %s (ID %d OID %u)",
1291  obj->name, obj->dumpId, obj->catId.oid);
1292  return;
1293  case DO_REFRESH_MATVIEW:
1294  snprintf(buf, bufsize,
1295  "REFRESH MATERIALIZED VIEW %s (ID %d OID %u)",
1296  obj->name, obj->dumpId, obj->catId.oid);
1297  return;
1298  case DO_RULE:
1299  snprintf(buf, bufsize,
1300  "RULE %s (ID %d OID %u)",
1301  obj->name, obj->dumpId, obj->catId.oid);
1302  return;
1303  case DO_TRIGGER:
1304  snprintf(buf, bufsize,
1305  "TRIGGER %s (ID %d OID %u)",
1306  obj->name, obj->dumpId, obj->catId.oid);
1307  return;
1308  case DO_EVENT_TRIGGER:
1309  snprintf(buf, bufsize,
1310  "EVENT TRIGGER %s (ID %d OID %u)",
1311  obj->name, obj->dumpId, obj->catId.oid);
1312  return;
1313  case DO_CONSTRAINT:
1314  snprintf(buf, bufsize,
1315  "CONSTRAINT %s (ID %d OID %u)",
1316  obj->name, obj->dumpId, obj->catId.oid);
1317  return;
1318  case DO_FK_CONSTRAINT:
1319  snprintf(buf, bufsize,
1320  "FK CONSTRAINT %s (ID %d OID %u)",
1321  obj->name, obj->dumpId, obj->catId.oid);
1322  return;
1323  case DO_PROCLANG:
1324  snprintf(buf, bufsize,
1325  "PROCEDURAL LANGUAGE %s (ID %d OID %u)",
1326  obj->name, obj->dumpId, obj->catId.oid);
1327  return;
1328  case DO_CAST:
1329  snprintf(buf, bufsize,
1330  "CAST %u to %u (ID %d OID %u)",
1331  ((CastInfo *) obj)->castsource,
1332  ((CastInfo *) obj)->casttarget,
1333  obj->dumpId, obj->catId.oid);
1334  return;
1335  case DO_TRANSFORM:
1336  snprintf(buf, bufsize,
1337  "TRANSFORM %u lang %u (ID %d OID %u)",
1338  ((TransformInfo *) obj)->trftype,
1339  ((TransformInfo *) obj)->trflang,
1340  obj->dumpId, obj->catId.oid);
1341  return;
1342  case DO_TABLE_DATA:
1343  snprintf(buf, bufsize,
1344  "TABLE DATA %s (ID %d OID %u)",
1345  obj->name, obj->dumpId, obj->catId.oid);
1346  return;
1347  case DO_SEQUENCE_SET:
1348  snprintf(buf, bufsize,
1349  "SEQUENCE SET %s (ID %d OID %u)",
1350  obj->name, obj->dumpId, obj->catId.oid);
1351  return;
1352  case DO_DUMMY_TYPE:
1353  snprintf(buf, bufsize,
1354  "DUMMY TYPE %s (ID %d OID %u)",
1355  obj->name, obj->dumpId, obj->catId.oid);
1356  return;
1357  case DO_TSPARSER:
1358  snprintf(buf, bufsize,
1359  "TEXT SEARCH PARSER %s (ID %d OID %u)",
1360  obj->name, obj->dumpId, obj->catId.oid);
1361  return;
1362  case DO_TSDICT:
1363  snprintf(buf, bufsize,
1364  "TEXT SEARCH DICTIONARY %s (ID %d OID %u)",
1365  obj->name, obj->dumpId, obj->catId.oid);
1366  return;
1367  case DO_TSTEMPLATE:
1368  snprintf(buf, bufsize,
1369  "TEXT SEARCH TEMPLATE %s (ID %d OID %u)",
1370  obj->name, obj->dumpId, obj->catId.oid);
1371  return;
1372  case DO_TSCONFIG:
1373  snprintf(buf, bufsize,
1374  "TEXT SEARCH CONFIGURATION %s (ID %d OID %u)",
1375  obj->name, obj->dumpId, obj->catId.oid);
1376  return;
1377  case DO_FDW:
1378  snprintf(buf, bufsize,
1379  "FOREIGN DATA WRAPPER %s (ID %d OID %u)",
1380  obj->name, obj->dumpId, obj->catId.oid);
1381  return;
1382  case DO_FOREIGN_SERVER:
1383  snprintf(buf, bufsize,
1384  "FOREIGN SERVER %s (ID %d OID %u)",
1385  obj->name, obj->dumpId, obj->catId.oid);
1386  return;
1387  case DO_DEFAULT_ACL:
1388  snprintf(buf, bufsize,
1389  "DEFAULT ACL %s (ID %d OID %u)",
1390  obj->name, obj->dumpId, obj->catId.oid);
1391  return;
1392  case DO_BLOB:
1393  snprintf(buf, bufsize,
1394  "BLOB (ID %d OID %u)",
1395  obj->dumpId, obj->catId.oid);
1396  return;
1397  case DO_BLOB_DATA:
1398  snprintf(buf, bufsize,
1399  "BLOB DATA (ID %d)",
1400  obj->dumpId);
1401  return;
1402  case DO_POLICY:
1403  snprintf(buf, bufsize,
1404  "POLICY (ID %d OID %u)",
1405  obj->dumpId, obj->catId.oid);
1406  return;
1407  case DO_PUBLICATION:
1408  snprintf(buf, bufsize,
1409  "PUBLICATION (ID %d OID %u)",
1410  obj->dumpId, obj->catId.oid);
1411  return;
1412  case DO_PUBLICATION_REL:
1413  snprintf(buf, bufsize,
1414  "PUBLICATION TABLE (ID %d OID %u)",
1415  obj->dumpId, obj->catId.oid);
1416  return;
1417  case DO_SUBSCRIPTION:
1418  snprintf(buf, bufsize,
1419  "SUBSCRIPTION (ID %d OID %u)",
1420  obj->dumpId, obj->catId.oid);
1421  return;
1422  case DO_PRE_DATA_BOUNDARY:
1423  snprintf(buf, bufsize,
1424  "PRE-DATA BOUNDARY (ID %d)",
1425  obj->dumpId);
1426  return;
1427  case DO_POST_DATA_BOUNDARY:
1428  snprintf(buf, bufsize,
1429  "POST-DATA BOUNDARY (ID %d)",
1430  obj->dumpId);
1431  return;
1432  }
1433  /* shouldn't get here */
1434  snprintf(buf, bufsize,
1435  "object type %d (ID %d OID %u)",
1436  (int) obj->objType,
1437  obj->dumpId, obj->catId.oid);
1438 }
char * name
Definition: pg_dump.h:130
DumpId dumpId
Definition: pg_dump.h:129
Definition: pg_dump.h:45
static char * buf
Definition: pg_test_fsync.c:67
Definition: pg_dump.h:70
CatalogId catId
Definition: pg_dump.h:128
DumpableObjectType objType
Definition: pg_dump.h:127
#define snprintf
Definition: port.h:192

◆ DOTypeNameCompare()

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

Definition at line 125 of file pg_dump_sort.c.

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, _policyInfo::poltable, and _triggerInfo::tgtable.

Referenced by sortDumpableObjectsByTypeName().

126 {
127  DumpableObject *obj1 = *(DumpableObject *const *) p1;
128  DumpableObject *obj2 = *(DumpableObject *const *) p2;
129  int cmpval;
130 
131  /* Sort by type's priority */
132  cmpval = dbObjectTypePriority[obj1->objType] -
134 
135  if (cmpval != 0)
136  return cmpval;
137 
138  /*
139  * Sort by namespace. Typically, all objects of the same priority would
140  * either have or not have a namespace link, but there are exceptions.
141  * Sort NULL namespace after non-NULL in such cases.
142  */
143  if (obj1->namespace)
144  {
145  if (obj2->namespace)
146  {
147  cmpval = strcmp(obj1->namespace->dobj.name,
148  obj2->namespace->dobj.name);
149  if (cmpval != 0)
150  return cmpval;
151  }
152  else
153  return -1;
154  }
155  else if (obj2->namespace)
156  return 1;
157 
158  /* Sort by name */
159  cmpval = strcmp(obj1->name, obj2->name);
160  if (cmpval != 0)
161  return cmpval;
162 
163  /* To have a stable sort order, break ties for some object types */
164  if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
165  {
166  FuncInfo *fobj1 = *(FuncInfo *const *) p1;
167  FuncInfo *fobj2 = *(FuncInfo *const *) p2;
168  int i;
169 
170  /* Sort by number of arguments, then argument type names */
171  cmpval = fobj1->nargs - fobj2->nargs;
172  if (cmpval != 0)
173  return cmpval;
174  for (i = 0; i < fobj1->nargs; i++)
175  {
176  TypeInfo *argtype1 = findTypeByOid(fobj1->argtypes[i]);
177  TypeInfo *argtype2 = findTypeByOid(fobj2->argtypes[i]);
178 
179  if (argtype1 && argtype2)
180  {
181  if (argtype1->dobj.namespace && argtype2->dobj.namespace)
182  {
183  cmpval = strcmp(argtype1->dobj.namespace->dobj.name,
184  argtype2->dobj.namespace->dobj.name);
185  if (cmpval != 0)
186  return cmpval;
187  }
188  cmpval = strcmp(argtype1->dobj.name, argtype2->dobj.name);
189  if (cmpval != 0)
190  return cmpval;
191  }
192  }
193  }
194  else if (obj1->objType == DO_OPERATOR)
195  {
196  OprInfo *oobj1 = *(OprInfo *const *) p1;
197  OprInfo *oobj2 = *(OprInfo *const *) p2;
198 
199  /* oprkind is 'l', 'r', or 'b'; this sorts prefix, postfix, infix */
200  cmpval = (oobj2->oprkind - oobj1->oprkind);
201  if (cmpval != 0)
202  return cmpval;
203  }
204  else if (obj1->objType == DO_ATTRDEF)
205  {
206  AttrDefInfo *adobj1 = *(AttrDefInfo *const *) p1;
207  AttrDefInfo *adobj2 = *(AttrDefInfo *const *) p2;
208 
209  /* Sort by attribute number */
210  cmpval = (adobj1->adnum - adobj2->adnum);
211  if (cmpval != 0)
212  return cmpval;
213  }
214  else if (obj1->objType == DO_POLICY)
215  {
216  PolicyInfo *pobj1 = *(PolicyInfo *const *) p1;
217  PolicyInfo *pobj2 = *(PolicyInfo *const *) p2;
218 
219  /* Sort by table name (table namespace was considered already) */
220  cmpval = strcmp(pobj1->poltable->dobj.name,
221  pobj2->poltable->dobj.name);
222  if (cmpval != 0)
223  return cmpval;
224  }
225  else if (obj1->objType == DO_TRIGGER)
226  {
227  TriggerInfo *tobj1 = *(TriggerInfo *const *) p1;
228  TriggerInfo *tobj2 = *(TriggerInfo *const *) p2;
229 
230  /* Sort by table name (table namespace was considered already) */
231  cmpval = strcmp(tobj1->tgtable->dobj.name,
232  tobj2->tgtable->dobj.name);
233  if (cmpval != 0)
234  return cmpval;
235  }
236 
237  /* Usually shouldn't get here, but if we do, sort by OID */
238  return oidcmp(obj1->catId.oid, obj2->catId.oid);
239 }
Oid * argtypes
Definition: pg_dump.h:199
char * name
Definition: pg_dump.h:130
#define oidcmp(x, y)
Definition: pg_dump.h:20
int nargs
Definition: pg_dump.h:198
DumpableObject dobj
Definition: pg_dump.h:258
TableInfo * tgtable
Definition: pg_dump.h:404
Definition: pg_dump.h:45
TableInfo * poltable
Definition: pg_dump.h:582
DumpableObject dobj
Definition: pg_dump.h:162
static const int dbObjectTypePriority[]
Definition: pg_dump_sort.c:35
char oprkind
Definition: pg_dump.h:218
CatalogId catId
Definition: pg_dump.h:128
int i
TypeInfo * findTypeByOid(Oid oid)
Definition: common.c:839
DumpableObjectType objType
Definition: pg_dump.h:127

◆ findDependencyLoops()

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

Definition at line 521 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

522 {
523  /*
524  * We use three data structures here:
525  *
526  * processed[] is a bool array indexed by dump ID, marking the objects
527  * already processed during this invocation of findDependencyLoops().
528  *
529  * searchFailed[] is another array indexed by dump ID. searchFailed[j] is
530  * set to dump ID k if we have proven that there is no dependency path
531  * leading from object j back to start point k. This allows us to skip
532  * useless searching when there are multiple dependency paths from k to j,
533  * which is a common situation. We could use a simple bool array for
534  * this, but then we'd need to re-zero it for each start point, resulting
535  * in O(N^2) zeroing work. Using the start point's dump ID as the "true"
536  * value lets us skip clearing the array before we consider the next start
537  * point.
538  *
539  * workspace[] is an array of DumpableObject pointers, in which we try to
540  * build lists of objects constituting loops. We make workspace[] large
541  * enough to hold all the objects in TopoSort's output, which is huge
542  * overkill in most cases but could theoretically be necessary if there is
543  * a single dependency chain linking all the objects.
544  */
545  bool *processed;
546  DumpId *searchFailed;
547  DumpableObject **workspace;
548  bool fixedloop;
549  int i;
550 
551  processed = (bool *) pg_malloc0((getMaxDumpId() + 1) * sizeof(bool));
552  searchFailed = (DumpId *) pg_malloc0((getMaxDumpId() + 1) * sizeof(DumpId));
553  workspace = (DumpableObject **) pg_malloc(totObjs * sizeof(DumpableObject *));
554  fixedloop = false;
555 
556  for (i = 0; i < nObjs; i++)
557  {
558  DumpableObject *obj = objs[i];
559  int looplen;
560  int j;
561 
562  looplen = findLoop(obj,
563  obj->dumpId,
564  processed,
565  searchFailed,
566  workspace,
567  0);
568 
569  if (looplen > 0)
570  {
571  /* Found a loop, repair it */
572  repairDependencyLoop(workspace, looplen);
573  fixedloop = true;
574  /* Mark loop members as processed */
575  for (j = 0; j < looplen; j++)
576  processed[workspace[j]->dumpId] = true;
577  }
578  else
579  {
580  /*
581  * There's no loop starting at this object, but mark it processed
582  * anyway. This is not necessary for correctness, but saves later
583  * invocations of findLoop() from uselessly chasing references to
584  * such an object.
585  */
586  processed[obj->dumpId] = true;
587  }
588  }
589 
590  /* We'd better have fixed at least one loop */
591  if (!fixedloop)
592  fatal("could not identify dependency loop");
593 
594  free(workspace);
595  free(searchFailed);
596  free(processed);
597 }
int DumpId
Definition: pg_backup.h:234
static void repairDependencyLoop(DumpableObject **loop, int nLoop)
Definition: pg_dump_sort.c:902
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
DumpId dumpId
Definition: pg_dump.h:129
void * pg_malloc0(size_t size)
Definition: fe_memutils.c:53
static int findLoop(DumpableObject *obj, DumpId startPoint, bool *processed, DumpId *searchFailed, DumpableObject **workspace, int depth)
Definition: pg_dump_sort.c:617
DumpId getMaxDumpId(void)
Definition: common.c:598
#define free(a)
Definition: header.h:65
#define fatal(...)
int i
unsigned char bool
Definition: c.h:317

◆ findLoop()

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

Definition at line 617 of file pg_dump_sort.c.

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

Referenced by findDependencyLoops().

623 {
624  int i;
625 
626  /*
627  * Reject if obj is already processed. This test prevents us from finding
628  * loops that overlap previously-processed loops.
629  */
630  if (processed[obj->dumpId])
631  return 0;
632 
633  /*
634  * If we've already proven there is no path from this object back to the
635  * startPoint, forget it.
636  */
637  if (searchFailed[obj->dumpId] == startPoint)
638  return 0;
639 
640  /*
641  * Reject if obj is already present in workspace. This test prevents us
642  * from going into infinite recursion if we are given a startPoint object
643  * that links to a cycle it's not a member of, and it guarantees that we
644  * can't overflow the allocated size of workspace[].
645  */
646  for (i = 0; i < depth; i++)
647  {
648  if (workspace[i] == obj)
649  return 0;
650  }
651 
652  /*
653  * Okay, tentatively add obj to workspace
654  */
655  workspace[depth++] = obj;
656 
657  /*
658  * See if we've found a loop back to the desired startPoint; if so, done
659  */
660  for (i = 0; i < obj->nDeps; i++)
661  {
662  if (obj->dependencies[i] == startPoint)
663  return depth;
664  }
665 
666  /*
667  * Recurse down each outgoing branch
668  */
669  for (i = 0; i < obj->nDeps; i++)
670  {
671  DumpableObject *nextobj = findObjectByDumpId(obj->dependencies[i]);
672  int newDepth;
673 
674  if (!nextobj)
675  continue; /* ignore dependencies on undumped objects */
676  newDepth = findLoop(nextobj,
677  startPoint,
678  processed,
679  searchFailed,
680  workspace,
681  depth);
682  if (newDepth > 0)
683  return newDepth;
684  }
685 
686  /*
687  * Remember there is no path from here back to startPoint
688  */
689  searchFailed[obj->dumpId] = startPoint;
690 
691  return 0;
692 }
DumpId * dependencies
Definition: pg_dump.h:135
DumpId dumpId
Definition: pg_dump.h:129
DumpableObject * findObjectByDumpId(DumpId dumpId)
Definition: common.c:609
static int findLoop(DumpableObject *obj, DumpId startPoint, bool *processed, DumpId *searchFailed, DumpableObject **workspace, int depth)
Definition: pg_dump_sort.c:617
int i

◆ removeHeapElement()

static int removeHeapElement ( int *  heap,
int  heapLength 
)
static

Definition at line 476 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

477 {
478  int result = heap[0];
479  int val;
480  int i;
481 
482  if (--heapLength <= 0)
483  return result;
484  val = heap[heapLength]; /* value that must be reinserted */
485  i = 0; /* i is where the "hole" is */
486  for (;;)
487  {
488  int j = 2 * i + 1;
489 
490  if (j >= heapLength)
491  break;
492  if (j + 1 < heapLength &&
493  heap[j] < heap[j + 1])
494  j++;
495  if (val >= heap[j])
496  break;
497  heap[i] = heap[j];
498  i = j;
499  }
500  heap[i] = val;
501  return result;
502 }
int i
long val
Definition: informix.c:664

◆ repairDependencyLoop()

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

Definition at line 902 of file pg_dump_sort.c.

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, name, ngettext, pg_log_generic(), PG_LOG_INFO, pg_log_warning, removeObjectDependency(), repairDomainConstraintLoop(), repairDomainConstraintMultiLoop(), repairIndexLoop(), repairMatViewBoundaryMultiLoop(), repairTableAttrDefLoop(), repairTableAttrDefMultiLoop(), repairTableConstraintLoop(), repairTableConstraintMultiLoop(), repairTypeFuncLoop(), repairViewRuleLoop(), and repairViewRuleMultiLoop().

Referenced by findDependencyLoops().

904 {
905  int i,
906  j;
907 
908  /* Datatype and one of its I/O or canonicalize functions */
909  if (nLoop == 2 &&
910  loop[0]->objType == DO_TYPE &&
911  loop[1]->objType == DO_FUNC)
912  {
913  repairTypeFuncLoop(loop[0], loop[1]);
914  return;
915  }
916  if (nLoop == 2 &&
917  loop[1]->objType == DO_TYPE &&
918  loop[0]->objType == DO_FUNC)
919  {
920  repairTypeFuncLoop(loop[1], loop[0]);
921  return;
922  }
923 
924  /* View (including matview) and its ON SELECT rule */
925  if (nLoop == 2 &&
926  loop[0]->objType == DO_TABLE &&
927  loop[1]->objType == DO_RULE &&
928  (((TableInfo *) loop[0])->relkind == RELKIND_VIEW ||
929  ((TableInfo *) loop[0])->relkind == RELKIND_MATVIEW) &&
930  ((RuleInfo *) loop[1])->ev_type == '1' &&
931  ((RuleInfo *) loop[1])->is_instead &&
932  ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
933  {
934  repairViewRuleLoop(loop[0], loop[1]);
935  return;
936  }
937  if (nLoop == 2 &&
938  loop[1]->objType == DO_TABLE &&
939  loop[0]->objType == DO_RULE &&
940  (((TableInfo *) loop[1])->relkind == RELKIND_VIEW ||
941  ((TableInfo *) loop[1])->relkind == RELKIND_MATVIEW) &&
942  ((RuleInfo *) loop[0])->ev_type == '1' &&
943  ((RuleInfo *) loop[0])->is_instead &&
944  ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
945  {
946  repairViewRuleLoop(loop[1], loop[0]);
947  return;
948  }
949 
950  /* Indirect loop involving view (but not matview) and ON SELECT rule */
951  if (nLoop > 2)
952  {
953  for (i = 0; i < nLoop; i++)
954  {
955  if (loop[i]->objType == DO_TABLE &&
956  ((TableInfo *) loop[i])->relkind == RELKIND_VIEW)
957  {
958  for (j = 0; j < nLoop; j++)
959  {
960  if (loop[j]->objType == DO_RULE &&
961  ((RuleInfo *) loop[j])->ev_type == '1' &&
962  ((RuleInfo *) loop[j])->is_instead &&
963  ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
964  {
965  repairViewRuleMultiLoop(loop[i], loop[j]);
966  return;
967  }
968  }
969  }
970  }
971  }
972 
973  /* Indirect loop involving matview and data boundary */
974  if (nLoop > 2)
975  {
976  for (i = 0; i < nLoop; i++)
977  {
978  if (loop[i]->objType == DO_TABLE &&
979  ((TableInfo *) loop[i])->relkind == RELKIND_MATVIEW)
980  {
981  for (j = 0; j < nLoop; j++)
982  {
983  if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
984  {
985  DumpableObject *nextobj;
986 
987  nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
988  repairMatViewBoundaryMultiLoop(loop[j], nextobj);
989  return;
990  }
991  }
992  }
993  }
994  }
995 
996  /* Table and CHECK constraint */
997  if (nLoop == 2 &&
998  loop[0]->objType == DO_TABLE &&
999  loop[1]->objType == DO_CONSTRAINT &&
1000  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1001  ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
1002  {
1003  repairTableConstraintLoop(loop[0], loop[1]);
1004  return;
1005  }
1006  if (nLoop == 2 &&
1007  loop[1]->objType == DO_TABLE &&
1008  loop[0]->objType == DO_CONSTRAINT &&
1009  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1010  ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
1011  {
1012  repairTableConstraintLoop(loop[1], loop[0]);
1013  return;
1014  }
1015 
1016  /* Indirect loop involving table and CHECK constraint */
1017  if (nLoop > 2)
1018  {
1019  for (i = 0; i < nLoop; i++)
1020  {
1021  if (loop[i]->objType == DO_TABLE)
1022  {
1023  for (j = 0; j < nLoop; j++)
1024  {
1025  if (loop[j]->objType == DO_CONSTRAINT &&
1026  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1027  ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
1028  {
1029  repairTableConstraintMultiLoop(loop[i], loop[j]);
1030  return;
1031  }
1032  }
1033  }
1034  }
1035  }
1036 
1037  /* Table and attribute default */
1038  if (nLoop == 2 &&
1039  loop[0]->objType == DO_TABLE &&
1040  loop[1]->objType == DO_ATTRDEF &&
1041  ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
1042  {
1043  repairTableAttrDefLoop(loop[0], loop[1]);
1044  return;
1045  }
1046  if (nLoop == 2 &&
1047  loop[1]->objType == DO_TABLE &&
1048  loop[0]->objType == DO_ATTRDEF &&
1049  ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
1050  {
1051  repairTableAttrDefLoop(loop[1], loop[0]);
1052  return;
1053  }
1054 
1055  /* index on partitioned table and corresponding index on partition */
1056  if (nLoop == 2 &&
1057  loop[0]->objType == DO_INDEX &&
1058  loop[1]->objType == DO_INDEX)
1059  {
1060  if (((IndxInfo *) loop[0])->parentidx == loop[1]->catId.oid)
1061  {
1062  repairIndexLoop(loop[0], loop[1]);
1063  return;
1064  }
1065  else if (((IndxInfo *) loop[1])->parentidx == loop[0]->catId.oid)
1066  {
1067  repairIndexLoop(loop[1], loop[0]);
1068  return;
1069  }
1070  }
1071 
1072  /* Indirect loop involving table and attribute default */
1073  if (nLoop > 2)
1074  {
1075  for (i = 0; i < nLoop; i++)
1076  {
1077  if (loop[i]->objType == DO_TABLE)
1078  {
1079  for (j = 0; j < nLoop; j++)
1080  {
1081  if (loop[j]->objType == DO_ATTRDEF &&
1082  ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
1083  {
1084  repairTableAttrDefMultiLoop(loop[i], loop[j]);
1085  return;
1086  }
1087  }
1088  }
1089  }
1090  }
1091 
1092  /* Domain and CHECK constraint */
1093  if (nLoop == 2 &&
1094  loop[0]->objType == DO_TYPE &&
1095  loop[1]->objType == DO_CONSTRAINT &&
1096  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1097  ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
1098  {
1099  repairDomainConstraintLoop(loop[0], loop[1]);
1100  return;
1101  }
1102  if (nLoop == 2 &&
1103  loop[1]->objType == DO_TYPE &&
1104  loop[0]->objType == DO_CONSTRAINT &&
1105  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1106  ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
1107  {
1108  repairDomainConstraintLoop(loop[1], loop[0]);
1109  return;
1110  }
1111 
1112  /* Indirect loop involving domain and CHECK constraint */
1113  if (nLoop > 2)
1114  {
1115  for (i = 0; i < nLoop; i++)
1116  {
1117  if (loop[i]->objType == DO_TYPE)
1118  {
1119  for (j = 0; j < nLoop; j++)
1120  {
1121  if (loop[j]->objType == DO_CONSTRAINT &&
1122  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1123  ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
1124  {
1125  repairDomainConstraintMultiLoop(loop[i], loop[j]);
1126  return;
1127  }
1128  }
1129  }
1130  }
1131  }
1132 
1133  /*
1134  * Loop of table with itself --- just ignore it.
1135  *
1136  * (Actually, what this arises from is a dependency of a table column on
1137  * another column, which happens with generated columns; or a dependency
1138  * of a table column on the whole table, which happens with partitioning.
1139  * But we didn't pay attention to sub-object IDs while collecting the
1140  * dependency data, so we can't see that here.)
1141  */
1142  if (nLoop == 1)
1143  {
1144  if (loop[0]->objType == DO_TABLE)
1145  {
1146  removeObjectDependency(loop[0], loop[0]->dumpId);
1147  return;
1148  }
1149  }
1150 
1151  /*
1152  * If all the objects are TABLE_DATA items, what we must have is a
1153  * circular set of foreign key constraints (or a single self-referential
1154  * table). Print an appropriate complaint and break the loop arbitrarily.
1155  */
1156  for (i = 0; i < nLoop; i++)
1157  {
1158  if (loop[i]->objType != DO_TABLE_DATA)
1159  break;
1160  }
1161  if (i >= nLoop)
1162  {
1163  pg_log_warning(ngettext("there are circular foreign-key constraints on this table:",
1164  "there are circular foreign-key constraints among these tables:",
1165  nLoop));
1166  for (i = 0; i < nLoop; i++)
1167  pg_log_generic(PG_LOG_INFO, " %s", loop[i]->name);
1168  pg_log_generic(PG_LOG_INFO, "You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.");
1169  pg_log_generic(PG_LOG_INFO, "Consider using a full dump instead of a --data-only dump to avoid this problem.");
1170  if (nLoop > 1)
1171  removeObjectDependency(loop[0], loop[1]->dumpId);
1172  else /* must be a self-dependency */
1173  removeObjectDependency(loop[0], loop[0]->dumpId);
1174  return;
1175  }
1176 
1177  /*
1178  * If we can't find a principled way to break the loop, complain and break
1179  * it in an arbitrary fashion.
1180  */
1181  pg_log_warning("could not resolve dependency loop among these items:");
1182  for (i = 0; i < nLoop; i++)
1183  {
1184  char buf[1024];
1185 
1186  describeDumpableObject(loop[i], buf, sizeof(buf));
1187  pg_log_generic(PG_LOG_INFO, " %s", buf);
1188  }
1189 
1190  if (nLoop > 1)
1191  removeObjectDependency(loop[0], loop[1]->dumpId);
1192  else /* must be a self-dependency */
1193  removeObjectDependency(loop[0], loop[0]->dumpId);
1194 }
static void repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
Definition: pg_dump_sort.c:702
static void describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
static void repairViewRuleLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:733
static char * buf
Definition: pg_test_fsync.c:67
static void repairTableConstraintMultiLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:826
static void repairViewRuleMultiLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:753
static void repairDomainConstraintLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:866
#define ngettext(s, p, n)
Definition: c.h:1142
static void repairMatViewBoundaryMultiLoop(DumpableObject *boundaryobj, DumpableObject *nextobj)
Definition: pg_dump_sort.c:787
static void repairIndexLoop(DumpableObject *partedindex, DumpableObject *partindex)
Definition: pg_dump_sort.c:888
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
void pg_log_generic(enum pg_log_level level, const char *pg_restrict fmt,...)
Definition: logging.c:126
static void repairTableConstraintLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:809
const char * name
Definition: encode.c:521
int i
static void repairTableAttrDefMultiLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:851
#define pg_log_warning(...)
Definition: pgfnames.c:24
static void repairDomainConstraintMultiLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:874
static void repairTableAttrDefLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:843

◆ repairDomainConstraintLoop()

static void repairDomainConstraintLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 866 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

868 {
869  /* remove constraint's dependency on domain */
870  removeObjectDependency(constraintobj, domainobj->dumpId);
871 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808

◆ repairDomainConstraintMultiLoop()

static void repairDomainConstraintMultiLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 874 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

876 {
877  /* remove domain's dependency on constraint */
878  removeObjectDependency(domainobj, constraintobj->dumpId);
879  /* mark constraint as needing its own dump */
880  ((ConstraintInfo *) constraintobj)->separate = true;
881  /* put back constraint's dependency on domain */
882  addObjectDependency(constraintobj, domainobj->dumpId);
883  /* now that constraint is separate, it must be post-data */
884  addObjectDependency(constraintobj, postDataBoundId);
885 }
DumpId dumpId
Definition: pg_dump.h:129
static DumpId postDataBoundId
Definition: pg_dump_sort.c:87
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:781

◆ repairIndexLoop()

static void repairIndexLoop ( DumpableObject partedindex,
DumpableObject partindex 
)
static

Definition at line 888 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

890 {
891  removeObjectDependency(partedindex, partindex->dumpId);
892 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808

◆ repairMatViewBoundaryMultiLoop()

static void repairMatViewBoundaryMultiLoop ( DumpableObject boundaryobj,
DumpableObject nextobj 
)
static

Definition at line 787 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

789 {
790  /* remove boundary's dependency on object after it in loop */
791  removeObjectDependency(boundaryobj, nextobj->dumpId);
792  /* if that object is a matview, mark it as postponed into post-data */
793  if (nextobj->objType == DO_TABLE)
794  {
795  TableInfo *nextinfo = (TableInfo *) nextobj;
796 
797  if (nextinfo->relkind == RELKIND_MATVIEW)
798  nextinfo->postponed_def = true;
799  }
800 }
char relkind
Definition: pg_dump.h:264
DumpId dumpId
Definition: pg_dump.h:129
bool postponed_def
Definition: pg_dump.h:293
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
DumpableObjectType objType
Definition: pg_dump.h:127

◆ repairTableAttrDefLoop()

static void repairTableAttrDefLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 843 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

845 {
846  /* remove attrdef's dependency on table */
847  removeObjectDependency(attrdefobj, tableobj->dumpId);
848 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808

◆ repairTableAttrDefMultiLoop()

static void repairTableAttrDefMultiLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 851 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

853 {
854  /* remove table's dependency on attrdef */
855  removeObjectDependency(tableobj, attrdefobj->dumpId);
856  /* mark attrdef as needing its own dump */
857  ((AttrDefInfo *) attrdefobj)->separate = true;
858  /* put back attrdef's dependency on table */
859  addObjectDependency(attrdefobj, tableobj->dumpId);
860 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:781

◆ repairTableConstraintLoop()

static void repairTableConstraintLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 809 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

811 {
812  /* remove constraint's dependency on table */
813  removeObjectDependency(constraintobj, tableobj->dumpId);
814 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808

◆ repairTableConstraintMultiLoop()

static void repairTableConstraintMultiLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 826 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

828 {
829  /* remove table's dependency on constraint */
830  removeObjectDependency(tableobj, constraintobj->dumpId);
831  /* mark constraint as needing its own dump */
832  ((ConstraintInfo *) constraintobj)->separate = true;
833  /* put back constraint's dependency on table */
834  addObjectDependency(constraintobj, tableobj->dumpId);
835  /* now that constraint is separate, it must be post-data */
836  addObjectDependency(constraintobj, postDataBoundId);
837 }
DumpId dumpId
Definition: pg_dump.h:129
static DumpId postDataBoundId
Definition: pg_dump_sort.c:87
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:781

◆ repairTypeFuncLoop()

static void repairTypeFuncLoop ( DumpableObject typeobj,
DumpableObject funcobj 
)
static

Definition at line 702 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

703 {
704  TypeInfo *typeInfo = (TypeInfo *) typeobj;
705 
706  /* remove function's dependency on type */
707  removeObjectDependency(funcobj, typeobj->dumpId);
708 
709  /* add function's dependency on shell type, instead */
710  if (typeInfo->shellType)
711  {
712  addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
713 
714  /*
715  * Mark shell type (always including the definition, as we need the
716  * shell type defined to identify the function fully) as to be dumped
717  * if any such function is
718  */
719  if (funcobj->dump)
720  typeInfo->shellType->dobj.dump = funcobj->dump |
722  }
723 }
DumpableObject dobj
Definition: pg_dump.h:188
DumpComponents dump
Definition: pg_dump.h:131
struct _shellTypeInfo * shellType
Definition: pg_dump.h:180
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
#define DUMP_COMPONENT_DEFINITION
Definition: pg_dump.h:89
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:781

◆ repairViewRuleLoop()

static void repairViewRuleLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 733 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

735 {
736  /* remove rule's dependency on view */
737  removeObjectDependency(ruleobj, viewobj->dumpId);
738  /* flags on the two objects are already set correctly for this case */
739 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808

◆ repairViewRuleMultiLoop()

static void repairViewRuleMultiLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 753 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

755 {
756  TableInfo *viewinfo = (TableInfo *) viewobj;
757  RuleInfo *ruleinfo = (RuleInfo *) ruleobj;
758 
759  /* remove view's dependency on rule */
760  removeObjectDependency(viewobj, ruleobj->dumpId);
761  /* mark view to be printed with a dummy definition */
762  viewinfo->dummy_view = true;
763  /* mark rule as needing its own dump */
764  ruleinfo->separate = true;
765  /* put back rule's dependency on view */
766  addObjectDependency(ruleobj, viewobj->dumpId);
767  /* now that rule is separate, it must be post-data */
769 }
bool separate
Definition: pg_dump.h:397
DumpId dumpId
Definition: pg_dump.h:129
static DumpId postDataBoundId
Definition: pg_dump_sort.c:87
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:808
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:781
bool dummy_view
Definition: pg_dump.h:292

◆ sortDumpableObjects()

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

Definition at line 250 of file pg_dump_sort.c.

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

Referenced by main().

252 {
253  DumpableObject **ordering;
254  int nOrdering;
255 
256  if (numObjs <= 0) /* can't happen anymore ... */
257  return;
258 
259  /*
260  * Saving the boundary IDs in static variables is a bit grotty, but seems
261  * better than adding them to parameter lists of subsidiary functions.
262  */
263  preDataBoundId = preBoundaryId;
264  postDataBoundId = postBoundaryId;
265 
266  ordering = (DumpableObject **) pg_malloc(numObjs * sizeof(DumpableObject *));
267  while (!TopoSort(objs, numObjs, ordering, &nOrdering))
268  findDependencyLoops(ordering, nOrdering, numObjs);
269 
270  memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));
271 
272  free(ordering);
273 }
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
static DumpId preDataBoundId
Definition: pg_dump_sort.c:86
static void findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
Definition: pg_dump_sort.c:521
static bool TopoSort(DumpableObject **objs, int numObjs, DumpableObject **ordering, int *nOrdering)
Definition: pg_dump_sort.c:302
static DumpId postDataBoundId
Definition: pg_dump_sort.c:87
#define free(a)
Definition: header.h:65

◆ sortDumpableObjectsByTypeName()

void sortDumpableObjectsByTypeName ( DumpableObject **  objs,
int  numObjs 
)

Definition at line 117 of file pg_dump_sort.c.

References DOTypeNameCompare(), and qsort.

Referenced by main().

118 {
119  if (numObjs > 1)
120  qsort((void *) objs, numObjs, sizeof(DumpableObject *),
122 }
static int DOTypeNameCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:125
#define qsort(a, b, c, d)
Definition: port.h:474

◆ 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 302 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

306 {
307  DumpId maxDumpId = getMaxDumpId();
308  int *pendingHeap;
309  int *beforeConstraints;
310  int *idMap;
311  DumpableObject *obj;
312  int heapLength;
313  int i,
314  j,
315  k;
316 
317  /*
318  * This is basically the same algorithm shown for topological sorting in
319  * Knuth's Volume 1. However, we would like to minimize unnecessary
320  * rearrangement of the input ordering; that is, when we have a choice of
321  * which item to output next, we always want to take the one highest in
322  * the original list. Therefore, instead of maintaining an unordered
323  * linked list of items-ready-to-output as Knuth does, we maintain a heap
324  * of their item numbers, which we can use as a priority queue. This
325  * turns the algorithm from O(N) to O(N log N) because each insertion or
326  * removal of a heap item takes O(log N) time. However, that's still
327  * plenty fast enough for this application.
328  */
329 
330  *nOrdering = numObjs; /* for success return */
331 
332  /* Eliminate the null case */
333  if (numObjs <= 0)
334  return true;
335 
336  /* Create workspace for the above-described heap */
337  pendingHeap = (int *) pg_malloc(numObjs * sizeof(int));
338 
339  /*
340  * Scan the constraints, and for each item in the input, generate a count
341  * of the number of constraints that say it must be before something else.
342  * The count for the item with dumpId j is stored in beforeConstraints[j].
343  * We also make a map showing the input-order index of the item with
344  * dumpId j.
345  */
346  beforeConstraints = (int *) pg_malloc0((maxDumpId + 1) * sizeof(int));
347  idMap = (int *) pg_malloc((maxDumpId + 1) * sizeof(int));
348  for (i = 0; i < numObjs; i++)
349  {
350  obj = objs[i];
351  j = obj->dumpId;
352  if (j <= 0 || j > maxDumpId)
353  fatal("invalid dumpId %d", j);
354  idMap[j] = i;
355  for (j = 0; j < obj->nDeps; j++)
356  {
357  k = obj->dependencies[j];
358  if (k <= 0 || k > maxDumpId)
359  fatal("invalid dependency %d", k);
360  beforeConstraints[k]++;
361  }
362  }
363 
364  /*
365  * Now initialize the heap of items-ready-to-output by filling it with the
366  * indexes of items that already have beforeConstraints[id] == 0.
367  *
368  * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
369  * in the range 1..heapLength-1 (note we are using 0-based subscripts
370  * here, while the discussion in Knuth assumes 1-based subscripts). So, if
371  * we simply enter the indexes into pendingHeap[] in decreasing order, we
372  * a-fortiori have the heap invariant satisfied at completion of this
373  * loop, and don't need to do any sift-up comparisons.
374  */
375  heapLength = 0;
376  for (i = numObjs; --i >= 0;)
377  {
378  if (beforeConstraints[objs[i]->dumpId] == 0)
379  pendingHeap[heapLength++] = i;
380  }
381 
382  /*--------------------
383  * Now emit objects, working backwards in the output list. At each step,
384  * we use the priority heap to select the last item that has no remaining
385  * before-constraints. We remove that item from the heap, output it to
386  * ordering[], and decrease the beforeConstraints count of each of the
387  * items it was constrained against. Whenever an item's beforeConstraints
388  * count is thereby decreased to zero, we insert it into the priority heap
389  * to show that it is a candidate to output. We are done when the heap
390  * becomes empty; if we have output every element then we succeeded,
391  * otherwise we failed.
392  * i = number of ordering[] entries left to output
393  * j = objs[] index of item we are outputting
394  * k = temp for scanning constraint list for item j
395  *--------------------
396  */
397  i = numObjs;
398  while (heapLength > 0)
399  {
400  /* Select object to output by removing largest heap member */
401  j = removeHeapElement(pendingHeap, heapLength--);
402  obj = objs[j];
403  /* Output candidate to ordering[] */
404  ordering[--i] = obj;
405  /* Update beforeConstraints counts of its predecessors */
406  for (k = 0; k < obj->nDeps; k++)
407  {
408  int id = obj->dependencies[k];
409 
410  if ((--beforeConstraints[id]) == 0)
411  addHeapElement(idMap[id], pendingHeap, heapLength++);
412  }
413  }
414 
415  /*
416  * If we failed, report the objects that couldn't be output; these are the
417  * ones with beforeConstraints[] still nonzero.
418  */
419  if (i != 0)
420  {
421  k = 0;
422  for (j = 1; j <= maxDumpId; j++)
423  {
424  if (beforeConstraints[j] != 0)
425  ordering[k++] = objs[idMap[j]];
426  }
427  *nOrdering = k;
428  }
429 
430  /* Done */
431  free(pendingHeap);
432  free(beforeConstraints);
433  free(idMap);
434 
435  return (i == 0);
436 }
int DumpId
Definition: pg_backup.h:234
DumpId * dependencies
Definition: pg_dump.h:135
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
static int removeHeapElement(int *heap, int heapLength)
Definition: pg_dump_sort.c:476
DumpId dumpId
Definition: pg_dump.h:129
void * pg_malloc0(size_t size)
Definition: fe_memutils.c:53
DumpId getMaxDumpId(void)
Definition: common.c:598
#define free(a)
Definition: header.h:65
#define fatal(...)
int i
static void addHeapElement(int val, int *heap, int heapLength)
Definition: pg_dump_sort.c:445
static int * beforeConstraints
Definition: deadlock.c:107

Variable Documentation

◆ dbObjectTypePriority

const int dbObjectTypePriority[]
static

Definition at line 35 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

◆ postDataBoundId

◆ preDataBoundId

DumpId preDataBoundId
static

Definition at line 86 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().