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.

Enumerations

enum  dbObjectTypePriorities {
  PRIO_NAMESPACE = 1, PRIO_PROCLANG, PRIO_COLLATION, PRIO_TRANSFORM,
  PRIO_EXTENSION, PRIO_TYPE, PRIO_FUNC, PRIO_AGG,
  PRIO_ACCESS_METHOD, PRIO_OPERATOR, PRIO_OPFAMILY, PRIO_CAST,
  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_BLOB,
  PRIO_PRE_DATA_BOUNDARY, PRIO_TABLE_DATA, PRIO_SEQUENCE_SET, PRIO_BLOB_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_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

Enumerator
PRIO_NAMESPACE 
PRIO_PROCLANG 
PRIO_COLLATION 
PRIO_TRANSFORM 
PRIO_EXTENSION 
PRIO_TYPE 
PRIO_FUNC 
PRIO_AGG 
PRIO_ACCESS_METHOD 
PRIO_OPERATOR 
PRIO_OPFAMILY 
PRIO_CAST 
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_BLOB 
PRIO_PRE_DATA_BOUNDARY 
PRIO_TABLE_DATA 
PRIO_SEQUENCE_SET 
PRIO_BLOB_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_SUBSCRIPTION 
PRIO_DEFAULT_ACL 
PRIO_EVENT_TRIGGER 
PRIO_REFRESH_MATVIEW 

Definition at line 44 of file pg_dump_sort.c.

45 {
46  PRIO_NAMESPACE = 1,
51  PRIO_TYPE, /* used for DO_TYPE and DO_SHELL_TYPE */
52  PRIO_FUNC,
53  PRIO_AGG,
56  PRIO_OPFAMILY, /* used for DO_OPFAMILY and DO_OPCLASS */
57  PRIO_CAST,
63  PRIO_FDW,
65  PRIO_TABLE,
69  PRIO_BLOB,
70  PRIO_PRE_DATA_BOUNDARY, /* boundary! */
74  PRIO_POST_DATA_BOUNDARY, /* boundary! */
76  PRIO_INDEX,
79  PRIO_RULE,
86  PRIO_DEFAULT_ACL, /* done in ACL pass */
87  PRIO_EVENT_TRIGGER, /* must be next to last! */
88  PRIO_REFRESH_MATVIEW /* must be last! */
89 };

Function Documentation

◆ addHeapElement()

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

Definition at line 503 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

504 {
505  int j;
506 
507  /*
508  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
509  * using 1-based array indexes, not 0-based.
510  */
511  j = heapLength;
512  while (j > 0)
513  {
514  int i = (j - 1) >> 1;
515 
516  if (val <= heap[i])
517  break;
518  heap[j] = heap[i];
519  j = i;
520  }
521  heap[j] = val;
522 }
int i
long val
Definition: informix.c:664

◆ describeDumpableObject()

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

Definition at line 1260 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_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().

1261 {
1262  switch (obj->objType)
1263  {
1264  case DO_NAMESPACE:
1265  snprintf(buf, bufsize,
1266  "SCHEMA %s (ID %d OID %u)",
1267  obj->name, obj->dumpId, obj->catId.oid);
1268  return;
1269  case DO_EXTENSION:
1270  snprintf(buf, bufsize,
1271  "EXTENSION %s (ID %d OID %u)",
1272  obj->name, obj->dumpId, obj->catId.oid);
1273  return;
1274  case DO_TYPE:
1275  snprintf(buf, bufsize,
1276  "TYPE %s (ID %d OID %u)",
1277  obj->name, obj->dumpId, obj->catId.oid);
1278  return;
1279  case DO_SHELL_TYPE:
1280  snprintf(buf, bufsize,
1281  "SHELL TYPE %s (ID %d OID %u)",
1282  obj->name, obj->dumpId, obj->catId.oid);
1283  return;
1284  case DO_FUNC:
1285  snprintf(buf, bufsize,
1286  "FUNCTION %s (ID %d OID %u)",
1287  obj->name, obj->dumpId, obj->catId.oid);
1288  return;
1289  case DO_AGG:
1290  snprintf(buf, bufsize,
1291  "AGGREGATE %s (ID %d OID %u)",
1292  obj->name, obj->dumpId, obj->catId.oid);
1293  return;
1294  case DO_OPERATOR:
1295  snprintf(buf, bufsize,
1296  "OPERATOR %s (ID %d OID %u)",
1297  obj->name, obj->dumpId, obj->catId.oid);
1298  return;
1299  case DO_ACCESS_METHOD:
1300  snprintf(buf, bufsize,
1301  "ACCESS METHOD %s (ID %d OID %u)",
1302  obj->name, obj->dumpId, obj->catId.oid);
1303  return;
1304  case DO_OPCLASS:
1305  snprintf(buf, bufsize,
1306  "OPERATOR CLASS %s (ID %d OID %u)",
1307  obj->name, obj->dumpId, obj->catId.oid);
1308  return;
1309  case DO_OPFAMILY:
1310  snprintf(buf, bufsize,
1311  "OPERATOR FAMILY %s (ID %d OID %u)",
1312  obj->name, obj->dumpId, obj->catId.oid);
1313  return;
1314  case DO_COLLATION:
1315  snprintf(buf, bufsize,
1316  "COLLATION %s (ID %d OID %u)",
1317  obj->name, obj->dumpId, obj->catId.oid);
1318  return;
1319  case DO_CONVERSION:
1320  snprintf(buf, bufsize,
1321  "CONVERSION %s (ID %d OID %u)",
1322  obj->name, obj->dumpId, obj->catId.oid);
1323  return;
1324  case DO_TABLE:
1325  snprintf(buf, bufsize,
1326  "TABLE %s (ID %d OID %u)",
1327  obj->name, obj->dumpId, obj->catId.oid);
1328  return;
1329  case DO_TABLE_ATTACH:
1330  snprintf(buf, bufsize,
1331  "TABLE ATTACH %s (ID %d)",
1332  obj->name, obj->dumpId);
1333  return;
1334  case DO_ATTRDEF:
1335  snprintf(buf, bufsize,
1336  "ATTRDEF %s.%s (ID %d OID %u)",
1337  ((AttrDefInfo *) obj)->adtable->dobj.name,
1338  ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
1339  obj->dumpId, obj->catId.oid);
1340  return;
1341  case DO_INDEX:
1342  snprintf(buf, bufsize,
1343  "INDEX %s (ID %d OID %u)",
1344  obj->name, obj->dumpId, obj->catId.oid);
1345  return;
1346  case DO_INDEX_ATTACH:
1347  snprintf(buf, bufsize,
1348  "INDEX ATTACH %s (ID %d)",
1349  obj->name, obj->dumpId);
1350  return;
1351  case DO_STATSEXT:
1352  snprintf(buf, bufsize,
1353  "STATISTICS %s (ID %d OID %u)",
1354  obj->name, obj->dumpId, obj->catId.oid);
1355  return;
1356  case DO_REFRESH_MATVIEW:
1357  snprintf(buf, bufsize,
1358  "REFRESH MATERIALIZED VIEW %s (ID %d OID %u)",
1359  obj->name, obj->dumpId, obj->catId.oid);
1360  return;
1361  case DO_RULE:
1362  snprintf(buf, bufsize,
1363  "RULE %s (ID %d OID %u)",
1364  obj->name, obj->dumpId, obj->catId.oid);
1365  return;
1366  case DO_TRIGGER:
1367  snprintf(buf, bufsize,
1368  "TRIGGER %s (ID %d OID %u)",
1369  obj->name, obj->dumpId, obj->catId.oid);
1370  return;
1371  case DO_EVENT_TRIGGER:
1372  snprintf(buf, bufsize,
1373  "EVENT TRIGGER %s (ID %d OID %u)",
1374  obj->name, obj->dumpId, obj->catId.oid);
1375  return;
1376  case DO_CONSTRAINT:
1377  snprintf(buf, bufsize,
1378  "CONSTRAINT %s (ID %d OID %u)",
1379  obj->name, obj->dumpId, obj->catId.oid);
1380  return;
1381  case DO_FK_CONSTRAINT:
1382  snprintf(buf, bufsize,
1383  "FK CONSTRAINT %s (ID %d OID %u)",
1384  obj->name, obj->dumpId, obj->catId.oid);
1385  return;
1386  case DO_PROCLANG:
1387  snprintf(buf, bufsize,
1388  "PROCEDURAL LANGUAGE %s (ID %d OID %u)",
1389  obj->name, obj->dumpId, obj->catId.oid);
1390  return;
1391  case DO_CAST:
1392  snprintf(buf, bufsize,
1393  "CAST %u to %u (ID %d OID %u)",
1394  ((CastInfo *) obj)->castsource,
1395  ((CastInfo *) obj)->casttarget,
1396  obj->dumpId, obj->catId.oid);
1397  return;
1398  case DO_TRANSFORM:
1399  snprintf(buf, bufsize,
1400  "TRANSFORM %u lang %u (ID %d OID %u)",
1401  ((TransformInfo *) obj)->trftype,
1402  ((TransformInfo *) obj)->trflang,
1403  obj->dumpId, obj->catId.oid);
1404  return;
1405  case DO_TABLE_DATA:
1406  snprintf(buf, bufsize,
1407  "TABLE DATA %s (ID %d OID %u)",
1408  obj->name, obj->dumpId, obj->catId.oid);
1409  return;
1410  case DO_SEQUENCE_SET:
1411  snprintf(buf, bufsize,
1412  "SEQUENCE SET %s (ID %d OID %u)",
1413  obj->name, obj->dumpId, obj->catId.oid);
1414  return;
1415  case DO_DUMMY_TYPE:
1416  snprintf(buf, bufsize,
1417  "DUMMY TYPE %s (ID %d OID %u)",
1418  obj->name, obj->dumpId, obj->catId.oid);
1419  return;
1420  case DO_TSPARSER:
1421  snprintf(buf, bufsize,
1422  "TEXT SEARCH PARSER %s (ID %d OID %u)",
1423  obj->name, obj->dumpId, obj->catId.oid);
1424  return;
1425  case DO_TSDICT:
1426  snprintf(buf, bufsize,
1427  "TEXT SEARCH DICTIONARY %s (ID %d OID %u)",
1428  obj->name, obj->dumpId, obj->catId.oid);
1429  return;
1430  case DO_TSTEMPLATE:
1431  snprintf(buf, bufsize,
1432  "TEXT SEARCH TEMPLATE %s (ID %d OID %u)",
1433  obj->name, obj->dumpId, obj->catId.oid);
1434  return;
1435  case DO_TSCONFIG:
1436  snprintf(buf, bufsize,
1437  "TEXT SEARCH CONFIGURATION %s (ID %d OID %u)",
1438  obj->name, obj->dumpId, obj->catId.oid);
1439  return;
1440  case DO_FDW:
1441  snprintf(buf, bufsize,
1442  "FOREIGN DATA WRAPPER %s (ID %d OID %u)",
1443  obj->name, obj->dumpId, obj->catId.oid);
1444  return;
1445  case DO_FOREIGN_SERVER:
1446  snprintf(buf, bufsize,
1447  "FOREIGN SERVER %s (ID %d OID %u)",
1448  obj->name, obj->dumpId, obj->catId.oid);
1449  return;
1450  case DO_DEFAULT_ACL:
1451  snprintf(buf, bufsize,
1452  "DEFAULT ACL %s (ID %d OID %u)",
1453  obj->name, obj->dumpId, obj->catId.oid);
1454  return;
1455  case DO_BLOB:
1456  snprintf(buf, bufsize,
1457  "BLOB (ID %d OID %u)",
1458  obj->dumpId, obj->catId.oid);
1459  return;
1460  case DO_BLOB_DATA:
1461  snprintf(buf, bufsize,
1462  "BLOB DATA (ID %d)",
1463  obj->dumpId);
1464  return;
1465  case DO_POLICY:
1466  snprintf(buf, bufsize,
1467  "POLICY (ID %d OID %u)",
1468  obj->dumpId, obj->catId.oid);
1469  return;
1470  case DO_PUBLICATION:
1471  snprintf(buf, bufsize,
1472  "PUBLICATION (ID %d OID %u)",
1473  obj->dumpId, obj->catId.oid);
1474  return;
1475  case DO_PUBLICATION_REL:
1476  snprintf(buf, bufsize,
1477  "PUBLICATION TABLE (ID %d OID %u)",
1478  obj->dumpId, obj->catId.oid);
1479  return;
1480  case DO_SUBSCRIPTION:
1481  snprintf(buf, bufsize,
1482  "SUBSCRIPTION (ID %d OID %u)",
1483  obj->dumpId, obj->catId.oid);
1484  return;
1485  case DO_PRE_DATA_BOUNDARY:
1486  snprintf(buf, bufsize,
1487  "PRE-DATA BOUNDARY (ID %d)",
1488  obj->dumpId);
1489  return;
1490  case DO_POST_DATA_BOUNDARY:
1491  snprintf(buf, bufsize,
1492  "POST-DATA BOUNDARY (ID %d)",
1493  obj->dumpId);
1494  return;
1495  }
1496  /* shouldn't get here */
1497  snprintf(buf, bufsize,
1498  "object type %d (ID %d OID %u)",
1499  (int) obj->objType,
1500  obj->dumpId, obj->catId.oid);
1501 }
char * name
Definition: pg_dump.h:131
DumpId dumpId
Definition: pg_dump.h:130
Definition: pg_dump.h:45
static char * buf
Definition: pg_test_fsync.c:68
Definition: pg_dump.h:71
CatalogId catId
Definition: pg_dump.h:129
DumpableObjectType objType
Definition: pg_dump.h:128
#define snprintf
Definition: port.h:216

◆ DOTypeNameCompare()

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

Definition at line 183 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().

184 {
185  DumpableObject *obj1 = *(DumpableObject *const *) p1;
186  DumpableObject *obj2 = *(DumpableObject *const *) p2;
187  int cmpval;
188 
189  /* Sort by type's priority */
190  cmpval = dbObjectTypePriority[obj1->objType] -
192 
193  if (cmpval != 0)
194  return cmpval;
195 
196  /*
197  * Sort by namespace. Typically, all objects of the same priority would
198  * either have or not have a namespace link, but there are exceptions.
199  * Sort NULL namespace after non-NULL in such cases.
200  */
201  if (obj1->namespace)
202  {
203  if (obj2->namespace)
204  {
205  cmpval = strcmp(obj1->namespace->dobj.name,
206  obj2->namespace->dobj.name);
207  if (cmpval != 0)
208  return cmpval;
209  }
210  else
211  return -1;
212  }
213  else if (obj2->namespace)
214  return 1;
215 
216  /* Sort by name */
217  cmpval = strcmp(obj1->name, obj2->name);
218  if (cmpval != 0)
219  return cmpval;
220 
221  /* To have a stable sort order, break ties for some object types */
222  if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
223  {
224  FuncInfo *fobj1 = *(FuncInfo *const *) p1;
225  FuncInfo *fobj2 = *(FuncInfo *const *) p2;
226  int i;
227 
228  /* Sort by number of arguments, then argument type names */
229  cmpval = fobj1->nargs - fobj2->nargs;
230  if (cmpval != 0)
231  return cmpval;
232  for (i = 0; i < fobj1->nargs; i++)
233  {
234  TypeInfo *argtype1 = findTypeByOid(fobj1->argtypes[i]);
235  TypeInfo *argtype2 = findTypeByOid(fobj2->argtypes[i]);
236 
237  if (argtype1 && argtype2)
238  {
239  if (argtype1->dobj.namespace && argtype2->dobj.namespace)
240  {
241  cmpval = strcmp(argtype1->dobj.namespace->dobj.name,
242  argtype2->dobj.namespace->dobj.name);
243  if (cmpval != 0)
244  return cmpval;
245  }
246  cmpval = strcmp(argtype1->dobj.name, argtype2->dobj.name);
247  if (cmpval != 0)
248  return cmpval;
249  }
250  }
251  }
252  else if (obj1->objType == DO_OPERATOR)
253  {
254  OprInfo *oobj1 = *(OprInfo *const *) p1;
255  OprInfo *oobj2 = *(OprInfo *const *) p2;
256 
257  /* oprkind is 'l', 'r', or 'b'; this sorts prefix, postfix, infix */
258  cmpval = (oobj2->oprkind - oobj1->oprkind);
259  if (cmpval != 0)
260  return cmpval;
261  }
262  else if (obj1->objType == DO_ATTRDEF)
263  {
264  AttrDefInfo *adobj1 = *(AttrDefInfo *const *) p1;
265  AttrDefInfo *adobj2 = *(AttrDefInfo *const *) p2;
266 
267  /* Sort by attribute number */
268  cmpval = (adobj1->adnum - adobj2->adnum);
269  if (cmpval != 0)
270  return cmpval;
271  }
272  else if (obj1->objType == DO_POLICY)
273  {
274  PolicyInfo *pobj1 = *(PolicyInfo *const *) p1;
275  PolicyInfo *pobj2 = *(PolicyInfo *const *) p2;
276 
277  /* Sort by table name (table namespace was considered already) */
278  cmpval = strcmp(pobj1->poltable->dobj.name,
279  pobj2->poltable->dobj.name);
280  if (cmpval != 0)
281  return cmpval;
282  }
283  else if (obj1->objType == DO_TRIGGER)
284  {
285  TriggerInfo *tobj1 = *(TriggerInfo *const *) p1;
286  TriggerInfo *tobj2 = *(TriggerInfo *const *) p2;
287 
288  /* Sort by table name (table namespace was considered already) */
289  cmpval = strcmp(tobj1->tgtable->dobj.name,
290  tobj2->tgtable->dobj.name);
291  if (cmpval != 0)
292  return cmpval;
293  }
294 
295  /* Usually shouldn't get here, but if we do, sort by OID */
296  return oidcmp(obj1->catId.oid, obj2->catId.oid);
297 }
Oid * argtypes
Definition: pg_dump.h:206
char * name
Definition: pg_dump.h:131
#define oidcmp(x, y)
Definition: pg_dump.h:20
int nargs
Definition: pg_dump.h:205
DumpableObject dobj
Definition: pg_dump.h:265
TableInfo * tgtable
Definition: pg_dump.h:420
Definition: pg_dump.h:45
TableInfo * poltable
Definition: pg_dump.h:599
DumpableObject dobj
Definition: pg_dump.h:166
static const int dbObjectTypePriority[]
Definition: pg_dump_sort.c:92
char oprkind
Definition: pg_dump.h:225
CatalogId catId
Definition: pg_dump.h:129
int i
TypeInfo * findTypeByOid(Oid oid)
Definition: common.c:904
DumpableObjectType objType
Definition: pg_dump.h:128

◆ findDependencyLoops()

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

Definition at line 579 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

580 {
581  /*
582  * We use three data structures here:
583  *
584  * processed[] is a bool array indexed by dump ID, marking the objects
585  * already processed during this invocation of findDependencyLoops().
586  *
587  * searchFailed[] is another array indexed by dump ID. searchFailed[j] is
588  * set to dump ID k if we have proven that there is no dependency path
589  * leading from object j back to start point k. This allows us to skip
590  * useless searching when there are multiple dependency paths from k to j,
591  * which is a common situation. We could use a simple bool array for
592  * this, but then we'd need to re-zero it for each start point, resulting
593  * in O(N^2) zeroing work. Using the start point's dump ID as the "true"
594  * value lets us skip clearing the array before we consider the next start
595  * point.
596  *
597  * workspace[] is an array of DumpableObject pointers, in which we try to
598  * build lists of objects constituting loops. We make workspace[] large
599  * enough to hold all the objects in TopoSort's output, which is huge
600  * overkill in most cases but could theoretically be necessary if there is
601  * a single dependency chain linking all the objects.
602  */
603  bool *processed;
604  DumpId *searchFailed;
605  DumpableObject **workspace;
606  bool fixedloop;
607  int i;
608 
609  processed = (bool *) pg_malloc0((getMaxDumpId() + 1) * sizeof(bool));
610  searchFailed = (DumpId *) pg_malloc0((getMaxDumpId() + 1) * sizeof(DumpId));
611  workspace = (DumpableObject **) pg_malloc(totObjs * sizeof(DumpableObject *));
612  fixedloop = false;
613 
614  for (i = 0; i < nObjs; i++)
615  {
616  DumpableObject *obj = objs[i];
617  int looplen;
618  int j;
619 
620  looplen = findLoop(obj,
621  obj->dumpId,
622  processed,
623  searchFailed,
624  workspace,
625  0);
626 
627  if (looplen > 0)
628  {
629  /* Found a loop, repair it */
630  repairDependencyLoop(workspace, looplen);
631  fixedloop = true;
632  /* Mark loop members as processed */
633  for (j = 0; j < looplen; j++)
634  processed[workspace[j]->dumpId] = true;
635  }
636  else
637  {
638  /*
639  * There's no loop starting at this object, but mark it processed
640  * anyway. This is not necessary for correctness, but saves later
641  * invocations of findLoop() from uselessly chasing references to
642  * such an object.
643  */
644  processed[obj->dumpId] = true;
645  }
646  }
647 
648  /* We'd better have fixed at least one loop */
649  if (!fixedloop)
650  fatal("could not identify dependency loop");
651 
652  free(workspace);
653  free(searchFailed);
654  free(processed);
655 }
int DumpId
Definition: pg_backup.h:243
static void repairDependencyLoop(DumpableObject **loop, int nLoop)
Definition: pg_dump_sort.c:960
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
DumpId dumpId
Definition: pg_dump.h:130
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:675
DumpId getMaxDumpId(void)
Definition: common.c:660
#define free(a)
Definition: header.h:65
#define fatal(...)
int i
unsigned char bool
Definition: c.h:391

◆ findLoop()

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

Definition at line 675 of file pg_dump_sort.c.

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

Referenced by findDependencyLoops().

681 {
682  int i;
683 
684  /*
685  * Reject if obj is already processed. This test prevents us from finding
686  * loops that overlap previously-processed loops.
687  */
688  if (processed[obj->dumpId])
689  return 0;
690 
691  /*
692  * If we've already proven there is no path from this object back to the
693  * startPoint, forget it.
694  */
695  if (searchFailed[obj->dumpId] == startPoint)
696  return 0;
697 
698  /*
699  * Reject if obj is already present in workspace. This test prevents us
700  * from going into infinite recursion if we are given a startPoint object
701  * that links to a cycle it's not a member of, and it guarantees that we
702  * can't overflow the allocated size of workspace[].
703  */
704  for (i = 0; i < depth; i++)
705  {
706  if (workspace[i] == obj)
707  return 0;
708  }
709 
710  /*
711  * Okay, tentatively add obj to workspace
712  */
713  workspace[depth++] = obj;
714 
715  /*
716  * See if we've found a loop back to the desired startPoint; if so, done
717  */
718  for (i = 0; i < obj->nDeps; i++)
719  {
720  if (obj->dependencies[i] == startPoint)
721  return depth;
722  }
723 
724  /*
725  * Recurse down each outgoing branch
726  */
727  for (i = 0; i < obj->nDeps; i++)
728  {
729  DumpableObject *nextobj = findObjectByDumpId(obj->dependencies[i]);
730  int newDepth;
731 
732  if (!nextobj)
733  continue; /* ignore dependencies on undumped objects */
734  newDepth = findLoop(nextobj,
735  startPoint,
736  processed,
737  searchFailed,
738  workspace,
739  depth);
740  if (newDepth > 0)
741  return newDepth;
742  }
743 
744  /*
745  * Remember there is no path from here back to startPoint
746  */
747  searchFailed[obj->dumpId] = startPoint;
748 
749  return 0;
750 }
DumpId * dependencies
Definition: pg_dump.h:137
DumpId dumpId
Definition: pg_dump.h:130
DumpableObject * findObjectByDumpId(DumpId dumpId)
Definition: common.c:671
static int findLoop(DumpableObject *obj, DumpId startPoint, bool *processed, DumpId *searchFailed, DumpableObject **workspace, int depth)
Definition: pg_dump_sort.c:675
int i

◆ removeHeapElement()

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

Definition at line 534 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

535 {
536  int result = heap[0];
537  int val;
538  int i;
539 
540  if (--heapLength <= 0)
541  return result;
542  val = heap[heapLength]; /* value that must be reinserted */
543  i = 0; /* i is where the "hole" is */
544  for (;;)
545  {
546  int j = 2 * i + 1;
547 
548  if (j >= heapLength)
549  break;
550  if (j + 1 < heapLength &&
551  heap[j] < heap[j + 1])
552  j++;
553  if (val >= heap[j])
554  break;
555  heap[i] = heap[j];
556  i = j;
557  }
558  heap[i] = val;
559  return result;
560 }
int i
long val
Definition: informix.c:664

◆ repairDependencyLoop()

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

Definition at line 960 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().

962 {
963  int i,
964  j;
965 
966  /* Datatype and one of its I/O or canonicalize functions */
967  if (nLoop == 2 &&
968  loop[0]->objType == DO_TYPE &&
969  loop[1]->objType == DO_FUNC)
970  {
971  repairTypeFuncLoop(loop[0], loop[1]);
972  return;
973  }
974  if (nLoop == 2 &&
975  loop[1]->objType == DO_TYPE &&
976  loop[0]->objType == DO_FUNC)
977  {
978  repairTypeFuncLoop(loop[1], loop[0]);
979  return;
980  }
981 
982  /* View (including matview) and its ON SELECT rule */
983  if (nLoop == 2 &&
984  loop[0]->objType == DO_TABLE &&
985  loop[1]->objType == DO_RULE &&
986  (((TableInfo *) loop[0])->relkind == RELKIND_VIEW ||
987  ((TableInfo *) loop[0])->relkind == RELKIND_MATVIEW) &&
988  ((RuleInfo *) loop[1])->ev_type == '1' &&
989  ((RuleInfo *) loop[1])->is_instead &&
990  ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
991  {
992  repairViewRuleLoop(loop[0], loop[1]);
993  return;
994  }
995  if (nLoop == 2 &&
996  loop[1]->objType == DO_TABLE &&
997  loop[0]->objType == DO_RULE &&
998  (((TableInfo *) loop[1])->relkind == RELKIND_VIEW ||
999  ((TableInfo *) loop[1])->relkind == RELKIND_MATVIEW) &&
1000  ((RuleInfo *) loop[0])->ev_type == '1' &&
1001  ((RuleInfo *) loop[0])->is_instead &&
1002  ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
1003  {
1004  repairViewRuleLoop(loop[1], loop[0]);
1005  return;
1006  }
1007 
1008  /* Indirect loop involving view (but not matview) and ON SELECT rule */
1009  if (nLoop > 2)
1010  {
1011  for (i = 0; i < nLoop; i++)
1012  {
1013  if (loop[i]->objType == DO_TABLE &&
1014  ((TableInfo *) loop[i])->relkind == RELKIND_VIEW)
1015  {
1016  for (j = 0; j < nLoop; j++)
1017  {
1018  if (loop[j]->objType == DO_RULE &&
1019  ((RuleInfo *) loop[j])->ev_type == '1' &&
1020  ((RuleInfo *) loop[j])->is_instead &&
1021  ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
1022  {
1023  repairViewRuleMultiLoop(loop[i], loop[j]);
1024  return;
1025  }
1026  }
1027  }
1028  }
1029  }
1030 
1031  /* Indirect loop involving matview and data boundary */
1032  if (nLoop > 2)
1033  {
1034  for (i = 0; i < nLoop; i++)
1035  {
1036  if (loop[i]->objType == DO_TABLE &&
1037  ((TableInfo *) loop[i])->relkind == RELKIND_MATVIEW)
1038  {
1039  for (j = 0; j < nLoop; j++)
1040  {
1041  if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
1042  {
1043  DumpableObject *nextobj;
1044 
1045  nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
1046  repairMatViewBoundaryMultiLoop(loop[j], nextobj);
1047  return;
1048  }
1049  }
1050  }
1051  }
1052  }
1053 
1054  /* Table and CHECK constraint */
1055  if (nLoop == 2 &&
1056  loop[0]->objType == DO_TABLE &&
1057  loop[1]->objType == DO_CONSTRAINT &&
1058  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1059  ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
1060  {
1061  repairTableConstraintLoop(loop[0], loop[1]);
1062  return;
1063  }
1064  if (nLoop == 2 &&
1065  loop[1]->objType == DO_TABLE &&
1066  loop[0]->objType == DO_CONSTRAINT &&
1067  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1068  ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
1069  {
1070  repairTableConstraintLoop(loop[1], loop[0]);
1071  return;
1072  }
1073 
1074  /* Indirect loop involving table and CHECK constraint */
1075  if (nLoop > 2)
1076  {
1077  for (i = 0; i < nLoop; i++)
1078  {
1079  if (loop[i]->objType == DO_TABLE)
1080  {
1081  for (j = 0; j < nLoop; j++)
1082  {
1083  if (loop[j]->objType == DO_CONSTRAINT &&
1084  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1085  ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
1086  {
1087  repairTableConstraintMultiLoop(loop[i], loop[j]);
1088  return;
1089  }
1090  }
1091  }
1092  }
1093  }
1094 
1095  /* Table and attribute default */
1096  if (nLoop == 2 &&
1097  loop[0]->objType == DO_TABLE &&
1098  loop[1]->objType == DO_ATTRDEF &&
1099  ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
1100  {
1101  repairTableAttrDefLoop(loop[0], loop[1]);
1102  return;
1103  }
1104  if (nLoop == 2 &&
1105  loop[1]->objType == DO_TABLE &&
1106  loop[0]->objType == DO_ATTRDEF &&
1107  ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
1108  {
1109  repairTableAttrDefLoop(loop[1], loop[0]);
1110  return;
1111  }
1112 
1113  /* index on partitioned table and corresponding index on partition */
1114  if (nLoop == 2 &&
1115  loop[0]->objType == DO_INDEX &&
1116  loop[1]->objType == DO_INDEX)
1117  {
1118  if (((IndxInfo *) loop[0])->parentidx == loop[1]->catId.oid)
1119  {
1120  repairIndexLoop(loop[0], loop[1]);
1121  return;
1122  }
1123  else if (((IndxInfo *) loop[1])->parentidx == loop[0]->catId.oid)
1124  {
1125  repairIndexLoop(loop[1], loop[0]);
1126  return;
1127  }
1128  }
1129 
1130  /* Indirect loop involving table and attribute default */
1131  if (nLoop > 2)
1132  {
1133  for (i = 0; i < nLoop; i++)
1134  {
1135  if (loop[i]->objType == DO_TABLE)
1136  {
1137  for (j = 0; j < nLoop; j++)
1138  {
1139  if (loop[j]->objType == DO_ATTRDEF &&
1140  ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
1141  {
1142  repairTableAttrDefMultiLoop(loop[i], loop[j]);
1143  return;
1144  }
1145  }
1146  }
1147  }
1148  }
1149 
1150  /* Domain and CHECK constraint */
1151  if (nLoop == 2 &&
1152  loop[0]->objType == DO_TYPE &&
1153  loop[1]->objType == DO_CONSTRAINT &&
1154  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1155  ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
1156  {
1157  repairDomainConstraintLoop(loop[0], loop[1]);
1158  return;
1159  }
1160  if (nLoop == 2 &&
1161  loop[1]->objType == DO_TYPE &&
1162  loop[0]->objType == DO_CONSTRAINT &&
1163  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1164  ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
1165  {
1166  repairDomainConstraintLoop(loop[1], loop[0]);
1167  return;
1168  }
1169 
1170  /* Indirect loop involving domain and CHECK constraint */
1171  if (nLoop > 2)
1172  {
1173  for (i = 0; i < nLoop; i++)
1174  {
1175  if (loop[i]->objType == DO_TYPE)
1176  {
1177  for (j = 0; j < nLoop; j++)
1178  {
1179  if (loop[j]->objType == DO_CONSTRAINT &&
1180  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1181  ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
1182  {
1183  repairDomainConstraintMultiLoop(loop[i], loop[j]);
1184  return;
1185  }
1186  }
1187  }
1188  }
1189  }
1190 
1191  /*
1192  * Loop of table with itself --- just ignore it.
1193  *
1194  * (Actually, what this arises from is a dependency of a table column on
1195  * another column, which happens with generated columns; or a dependency
1196  * of a table column on the whole table, which happens with partitioning.
1197  * But we didn't pay attention to sub-object IDs while collecting the
1198  * dependency data, so we can't see that here.)
1199  */
1200  if (nLoop == 1)
1201  {
1202  if (loop[0]->objType == DO_TABLE)
1203  {
1204  removeObjectDependency(loop[0], loop[0]->dumpId);
1205  return;
1206  }
1207  }
1208 
1209  /*
1210  * If all the objects are TABLE_DATA items, what we must have is a
1211  * circular set of foreign key constraints (or a single self-referential
1212  * table). Print an appropriate complaint and break the loop arbitrarily.
1213  */
1214  for (i = 0; i < nLoop; i++)
1215  {
1216  if (loop[i]->objType != DO_TABLE_DATA)
1217  break;
1218  }
1219  if (i >= nLoop)
1220  {
1221  pg_log_warning(ngettext("there are circular foreign-key constraints on this table:",
1222  "there are circular foreign-key constraints among these tables:",
1223  nLoop));
1224  for (i = 0; i < nLoop; i++)
1225  pg_log_generic(PG_LOG_INFO, " %s", loop[i]->name);
1226  pg_log_generic(PG_LOG_INFO, "You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.");
1227  pg_log_generic(PG_LOG_INFO, "Consider using a full dump instead of a --data-only dump to avoid this problem.");
1228  if (nLoop > 1)
1229  removeObjectDependency(loop[0], loop[1]->dumpId);
1230  else /* must be a self-dependency */
1231  removeObjectDependency(loop[0], loop[0]->dumpId);
1232  return;
1233  }
1234 
1235  /*
1236  * If we can't find a principled way to break the loop, complain and break
1237  * it in an arbitrary fashion.
1238  */
1239  pg_log_warning("could not resolve dependency loop among these items:");
1240  for (i = 0; i < nLoop; i++)
1241  {
1242  char buf[1024];
1243 
1244  describeDumpableObject(loop[i], buf, sizeof(buf));
1245  pg_log_generic(PG_LOG_INFO, " %s", buf);
1246  }
1247 
1248  if (nLoop > 1)
1249  removeObjectDependency(loop[0], loop[1]->dumpId);
1250  else /* must be a self-dependency */
1251  removeObjectDependency(loop[0], loop[0]->dumpId);
1252 }
static void repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
Definition: pg_dump_sort.c:760
static void describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
static void repairViewRuleLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:791
static char * buf
Definition: pg_test_fsync.c:68
static void repairTableConstraintMultiLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:884
static void repairViewRuleMultiLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:811
static void repairDomainConstraintLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:924
#define ngettext(s, p, n)
Definition: c.h:1182
static void repairMatViewBoundaryMultiLoop(DumpableObject *boundaryobj, DumpableObject *nextobj)
Definition: pg_dump_sort.c:845
static void repairIndexLoop(DumpableObject *partedindex, DumpableObject *partindex)
Definition: pg_dump_sort.c:946
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
void pg_log_generic(enum pg_log_level level, const char *pg_restrict fmt,...)
Definition: logging.c:197
static void repairTableConstraintLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:867
const char * name
Definition: encode.c:561
int i
static void repairTableAttrDefMultiLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:909
#define pg_log_warning(...)
Definition: pgfnames.c:24
static void repairDomainConstraintMultiLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:932
static void repairTableAttrDefLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:901

◆ repairDomainConstraintLoop()

static void repairDomainConstraintLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 924 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

926 {
927  /* remove constraint's dependency on domain */
928  removeObjectDependency(constraintobj, domainobj->dumpId);
929 }
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873

◆ repairDomainConstraintMultiLoop()

static void repairDomainConstraintMultiLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 932 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

934 {
935  /* remove domain's dependency on constraint */
936  removeObjectDependency(domainobj, constraintobj->dumpId);
937  /* mark constraint as needing its own dump */
938  ((ConstraintInfo *) constraintobj)->separate = true;
939  /* put back constraint's dependency on domain */
940  addObjectDependency(constraintobj, domainobj->dumpId);
941  /* now that constraint is separate, it must be post-data */
942  addObjectDependency(constraintobj, postDataBoundId);
943 }
DumpId dumpId
Definition: pg_dump.h:130
static DumpId postDataBoundId
Definition: pg_dump_sort.c:145
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:846

◆ repairIndexLoop()

static void repairIndexLoop ( DumpableObject partedindex,
DumpableObject partindex 
)
static

Definition at line 946 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

948 {
949  removeObjectDependency(partedindex, partindex->dumpId);
950 }
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873

◆ repairMatViewBoundaryMultiLoop()

static void repairMatViewBoundaryMultiLoop ( DumpableObject boundaryobj,
DumpableObject nextobj 
)
static

Definition at line 845 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

847 {
848  /* remove boundary's dependency on object after it in loop */
849  removeObjectDependency(boundaryobj, nextobj->dumpId);
850  /* if that object is a matview, mark it as postponed into post-data */
851  if (nextobj->objType == DO_TABLE)
852  {
853  TableInfo *nextinfo = (TableInfo *) nextobj;
854 
855  if (nextinfo->relkind == RELKIND_MATVIEW)
856  nextinfo->postponed_def = true;
857  }
858 }
char relkind
Definition: pg_dump.h:271
DumpId dumpId
Definition: pg_dump.h:130
bool postponed_def
Definition: pg_dump.h:301
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
DumpableObjectType objType
Definition: pg_dump.h:128

◆ repairTableAttrDefLoop()

static void repairTableAttrDefLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 901 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

903 {
904  /* remove attrdef's dependency on table */
905  removeObjectDependency(attrdefobj, tableobj->dumpId);
906 }
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873

◆ repairTableAttrDefMultiLoop()

static void repairTableAttrDefMultiLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 909 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

911 {
912  /* remove table's dependency on attrdef */
913  removeObjectDependency(tableobj, attrdefobj->dumpId);
914  /* mark attrdef as needing its own dump */
915  ((AttrDefInfo *) attrdefobj)->separate = true;
916  /* put back attrdef's dependency on table */
917  addObjectDependency(attrdefobj, tableobj->dumpId);
918 }
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:846

◆ repairTableConstraintLoop()

static void repairTableConstraintLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 867 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

869 {
870  /* remove constraint's dependency on table */
871  removeObjectDependency(constraintobj, tableobj->dumpId);
872 }
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873

◆ repairTableConstraintMultiLoop()

static void repairTableConstraintMultiLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 884 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

886 {
887  /* remove table's dependency on constraint */
888  removeObjectDependency(tableobj, constraintobj->dumpId);
889  /* mark constraint as needing its own dump */
890  ((ConstraintInfo *) constraintobj)->separate = true;
891  /* put back constraint's dependency on table */
892  addObjectDependency(constraintobj, tableobj->dumpId);
893  /* now that constraint is separate, it must be post-data */
894  addObjectDependency(constraintobj, postDataBoundId);
895 }
DumpId dumpId
Definition: pg_dump.h:130
static DumpId postDataBoundId
Definition: pg_dump_sort.c:145
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:846

◆ repairTypeFuncLoop()

static void repairTypeFuncLoop ( DumpableObject typeobj,
DumpableObject funcobj 
)
static

Definition at line 760 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

761 {
762  TypeInfo *typeInfo = (TypeInfo *) typeobj;
763 
764  /* remove function's dependency on type */
765  removeObjectDependency(funcobj, typeobj->dumpId);
766 
767  /* add function's dependency on shell type, instead */
768  if (typeInfo->shellType)
769  {
770  addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
771 
772  /*
773  * Mark shell type (always including the definition, as we need the
774  * shell type defined to identify the function fully) as to be dumped
775  * if any such function is
776  */
777  if (funcobj->dump)
778  typeInfo->shellType->dobj.dump = funcobj->dump |
780  }
781 }
DumpableObject dobj
Definition: pg_dump.h:195
DumpComponents dump
Definition: pg_dump.h:132
struct _shellTypeInfo * shellType
Definition: pg_dump.h:187
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
#define DUMP_COMPONENT_DEFINITION
Definition: pg_dump.h:90
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:846

◆ repairViewRuleLoop()

static void repairViewRuleLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 791 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

793 {
794  /* remove rule's dependency on view */
795  removeObjectDependency(ruleobj, viewobj->dumpId);
796  /* flags on the two objects are already set correctly for this case */
797 }
DumpId dumpId
Definition: pg_dump.h:130
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873

◆ repairViewRuleMultiLoop()

static void repairViewRuleMultiLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 811 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

813 {
814  TableInfo *viewinfo = (TableInfo *) viewobj;
815  RuleInfo *ruleinfo = (RuleInfo *) ruleobj;
816 
817  /* remove view's dependency on rule */
818  removeObjectDependency(viewobj, ruleobj->dumpId);
819  /* mark view to be printed with a dummy definition */
820  viewinfo->dummy_view = true;
821  /* mark rule as needing its own dump */
822  ruleinfo->separate = true;
823  /* put back rule's dependency on view */
824  addObjectDependency(ruleobj, viewobj->dumpId);
825  /* now that rule is separate, it must be post-data */
827 }
bool separate
Definition: pg_dump.h:413
DumpId dumpId
Definition: pg_dump.h:130
static DumpId postDataBoundId
Definition: pg_dump_sort.c:145
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:873
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:846
bool dummy_view
Definition: pg_dump.h:300

◆ sortDumpableObjects()

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

Definition at line 308 of file pg_dump_sort.c.

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

Referenced by main().

310 {
311  DumpableObject **ordering;
312  int nOrdering;
313 
314  if (numObjs <= 0) /* can't happen anymore ... */
315  return;
316 
317  /*
318  * Saving the boundary IDs in static variables is a bit grotty, but seems
319  * better than adding them to parameter lists of subsidiary functions.
320  */
321  preDataBoundId = preBoundaryId;
322  postDataBoundId = postBoundaryId;
323 
324  ordering = (DumpableObject **) pg_malloc(numObjs * sizeof(DumpableObject *));
325  while (!TopoSort(objs, numObjs, ordering, &nOrdering))
326  findDependencyLoops(ordering, nOrdering, numObjs);
327 
328  memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));
329 
330  free(ordering);
331 }
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
static DumpId preDataBoundId
Definition: pg_dump_sort.c:144
static void findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
Definition: pg_dump_sort.c:579
static bool TopoSort(DumpableObject **objs, int numObjs, DumpableObject **ordering, int *nOrdering)
Definition: pg_dump_sort.c:360
static DumpId postDataBoundId
Definition: pg_dump_sort.c:145
#define free(a)
Definition: header.h:65

◆ sortDumpableObjectsByTypeName()

void sortDumpableObjectsByTypeName ( DumpableObject **  objs,
int  numObjs 
)

Definition at line 175 of file pg_dump_sort.c.

References DOTypeNameCompare(), and qsort.

Referenced by main().

176 {
177  if (numObjs > 1)
178  qsort((void *) objs, numObjs, sizeof(DumpableObject *),
180 }
static int DOTypeNameCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:183
#define qsort(a, b, c, d)
Definition: port.h:504

◆ 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 360 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().

364 {
365  DumpId maxDumpId = getMaxDumpId();
366  int *pendingHeap;
367  int *beforeConstraints;
368  int *idMap;
369  DumpableObject *obj;
370  int heapLength;
371  int i,
372  j,
373  k;
374 
375  /*
376  * This is basically the same algorithm shown for topological sorting in
377  * Knuth's Volume 1. However, we would like to minimize unnecessary
378  * rearrangement of the input ordering; that is, when we have a choice of
379  * which item to output next, we always want to take the one highest in
380  * the original list. Therefore, instead of maintaining an unordered
381  * linked list of items-ready-to-output as Knuth does, we maintain a heap
382  * of their item numbers, which we can use as a priority queue. This
383  * turns the algorithm from O(N) to O(N log N) because each insertion or
384  * removal of a heap item takes O(log N) time. However, that's still
385  * plenty fast enough for this application.
386  */
387 
388  *nOrdering = numObjs; /* for success return */
389 
390  /* Eliminate the null case */
391  if (numObjs <= 0)
392  return true;
393 
394  /* Create workspace for the above-described heap */
395  pendingHeap = (int *) pg_malloc(numObjs * sizeof(int));
396 
397  /*
398  * Scan the constraints, and for each item in the input, generate a count
399  * of the number of constraints that say it must be before something else.
400  * The count for the item with dumpId j is stored in beforeConstraints[j].
401  * We also make a map showing the input-order index of the item with
402  * dumpId j.
403  */
404  beforeConstraints = (int *) pg_malloc0((maxDumpId + 1) * sizeof(int));
405  idMap = (int *) pg_malloc((maxDumpId + 1) * sizeof(int));
406  for (i = 0; i < numObjs; i++)
407  {
408  obj = objs[i];
409  j = obj->dumpId;
410  if (j <= 0 || j > maxDumpId)
411  fatal("invalid dumpId %d", j);
412  idMap[j] = i;
413  for (j = 0; j < obj->nDeps; j++)
414  {
415  k = obj->dependencies[j];
416  if (k <= 0 || k > maxDumpId)
417  fatal("invalid dependency %d", k);
418  beforeConstraints[k]++;
419  }
420  }
421 
422  /*
423  * Now initialize the heap of items-ready-to-output by filling it with the
424  * indexes of items that already have beforeConstraints[id] == 0.
425  *
426  * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
427  * in the range 1..heapLength-1 (note we are using 0-based subscripts
428  * here, while the discussion in Knuth assumes 1-based subscripts). So, if
429  * we simply enter the indexes into pendingHeap[] in decreasing order, we
430  * a-fortiori have the heap invariant satisfied at completion of this
431  * loop, and don't need to do any sift-up comparisons.
432  */
433  heapLength = 0;
434  for (i = numObjs; --i >= 0;)
435  {
436  if (beforeConstraints[objs[i]->dumpId] == 0)
437  pendingHeap[heapLength++] = i;
438  }
439 
440  /*--------------------
441  * Now emit objects, working backwards in the output list. At each step,
442  * we use the priority heap to select the last item that has no remaining
443  * before-constraints. We remove that item from the heap, output it to
444  * ordering[], and decrease the beforeConstraints count of each of the
445  * items it was constrained against. Whenever an item's beforeConstraints
446  * count is thereby decreased to zero, we insert it into the priority heap
447  * to show that it is a candidate to output. We are done when the heap
448  * becomes empty; if we have output every element then we succeeded,
449  * otherwise we failed.
450  * i = number of ordering[] entries left to output
451  * j = objs[] index of item we are outputting
452  * k = temp for scanning constraint list for item j
453  *--------------------
454  */
455  i = numObjs;
456  while (heapLength > 0)
457  {
458  /* Select object to output by removing largest heap member */
459  j = removeHeapElement(pendingHeap, heapLength--);
460  obj = objs[j];
461  /* Output candidate to ordering[] */
462  ordering[--i] = obj;
463  /* Update beforeConstraints counts of its predecessors */
464  for (k = 0; k < obj->nDeps; k++)
465  {
466  int id = obj->dependencies[k];
467 
468  if ((--beforeConstraints[id]) == 0)
469  addHeapElement(idMap[id], pendingHeap, heapLength++);
470  }
471  }
472 
473  /*
474  * If we failed, report the objects that couldn't be output; these are the
475  * ones with beforeConstraints[] still nonzero.
476  */
477  if (i != 0)
478  {
479  k = 0;
480  for (j = 1; j <= maxDumpId; j++)
481  {
482  if (beforeConstraints[j] != 0)
483  ordering[k++] = objs[idMap[j]];
484  }
485  *nOrdering = k;
486  }
487 
488  /* Done */
489  free(pendingHeap);
490  free(beforeConstraints);
491  free(idMap);
492 
493  return (i == 0);
494 }
int DumpId
Definition: pg_backup.h:243
DumpId * dependencies
Definition: pg_dump.h:137
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
static int removeHeapElement(int *heap, int heapLength)
Definition: pg_dump_sort.c:534
DumpId dumpId
Definition: pg_dump.h:130
void * pg_malloc0(size_t size)
Definition: fe_memutils.c:53
DumpId getMaxDumpId(void)
Definition: common.c:660
#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:503
static int * beforeConstraints
Definition: deadlock.c:107

Variable Documentation

◆ dbObjectTypePriority

const int dbObjectTypePriority[]
static

Definition at line 92 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

◆ postDataBoundId

◆ preDataBoundId

DumpId preDataBoundId
static

Definition at line 144 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().