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

References i, and val.

Referenced by TopoSort().

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

◆ describeDumpableObject()

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

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

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

◆ DOTypeNameCompare()

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

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

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

◆ findDependencyLoops()

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

Definition at line 528 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

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

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

Referenced by findDependencyLoops().

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

◆ removeHeapElement()

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

Definition at line 483 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

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

◆ repairDependencyLoop()

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

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

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

◆ repairDomainConstraintLoop()

static void repairDomainConstraintLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 873 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

875 {
876  /* remove constraint's dependency on domain */
877  removeObjectDependency(constraintobj, domainobj->dumpId);
878 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809

◆ repairDomainConstraintMultiLoop()

static void repairDomainConstraintMultiLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 881 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

883 {
884  /* remove domain's dependency on constraint */
885  removeObjectDependency(domainobj, constraintobj->dumpId);
886  /* mark constraint as needing its own dump */
887  ((ConstraintInfo *) constraintobj)->separate = true;
888  /* put back constraint's dependency on domain */
889  addObjectDependency(constraintobj, domainobj->dumpId);
890  /* now that constraint is separate, it must be post-data */
891  addObjectDependency(constraintobj, postDataBoundId);
892 }
DumpId dumpId
Definition: pg_dump.h:129
static DumpId postDataBoundId
Definition: pg_dump_sort.c:94
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:782

◆ repairIndexLoop()

static void repairIndexLoop ( DumpableObject partedindex,
DumpableObject partindex 
)
static

Definition at line 895 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

897 {
898  removeObjectDependency(partedindex, partindex->dumpId);
899 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809

◆ repairMatViewBoundaryMultiLoop()

static void repairMatViewBoundaryMultiLoop ( DumpableObject boundaryobj,
DumpableObject nextobj 
)
static

Definition at line 794 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

796 {
797  /* remove boundary's dependency on object after it in loop */
798  removeObjectDependency(boundaryobj, nextobj->dumpId);
799  /* if that object is a matview, mark it as postponed into post-data */
800  if (nextobj->objType == DO_TABLE)
801  {
802  TableInfo *nextinfo = (TableInfo *) nextobj;
803 
804  if (nextinfo->relkind == RELKIND_MATVIEW)
805  nextinfo->postponed_def = true;
806  }
807 }
char relkind
Definition: pg_dump.h:265
DumpId dumpId
Definition: pg_dump.h:129
bool postponed_def
Definition: pg_dump.h:295
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809
DumpableObjectType objType
Definition: pg_dump.h:127

◆ repairTableAttrDefLoop()

static void repairTableAttrDefLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 850 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

852 {
853  /* remove attrdef's dependency on table */
854  removeObjectDependency(attrdefobj, tableobj->dumpId);
855 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809

◆ repairTableAttrDefMultiLoop()

static void repairTableAttrDefMultiLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 858 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

860 {
861  /* remove table's dependency on attrdef */
862  removeObjectDependency(tableobj, attrdefobj->dumpId);
863  /* mark attrdef as needing its own dump */
864  ((AttrDefInfo *) attrdefobj)->separate = true;
865  /* put back attrdef's dependency on table */
866  addObjectDependency(attrdefobj, tableobj->dumpId);
867 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:782

◆ repairTableConstraintLoop()

static void repairTableConstraintLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 816 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

818 {
819  /* remove constraint's dependency on table */
820  removeObjectDependency(constraintobj, tableobj->dumpId);
821 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809

◆ repairTableConstraintMultiLoop()

static void repairTableConstraintMultiLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 833 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

835 {
836  /* remove table's dependency on constraint */
837  removeObjectDependency(tableobj, constraintobj->dumpId);
838  /* mark constraint as needing its own dump */
839  ((ConstraintInfo *) constraintobj)->separate = true;
840  /* put back constraint's dependency on table */
841  addObjectDependency(constraintobj, tableobj->dumpId);
842  /* now that constraint is separate, it must be post-data */
843  addObjectDependency(constraintobj, postDataBoundId);
844 }
DumpId dumpId
Definition: pg_dump.h:129
static DumpId postDataBoundId
Definition: pg_dump_sort.c:94
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:782

◆ repairTypeFuncLoop()

static void repairTypeFuncLoop ( DumpableObject typeobj,
DumpableObject funcobj 
)
static

Definition at line 709 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

710 {
711  TypeInfo *typeInfo = (TypeInfo *) typeobj;
712 
713  /* remove function's dependency on type */
714  removeObjectDependency(funcobj, typeobj->dumpId);
715 
716  /* add function's dependency on shell type, instead */
717  if (typeInfo->shellType)
718  {
719  addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
720 
721  /*
722  * Mark shell type (always including the definition, as we need the
723  * shell type defined to identify the function fully) as to be dumped
724  * if any such function is
725  */
726  if (funcobj->dump)
727  typeInfo->shellType->dobj.dump = funcobj->dump |
729  }
730 }
DumpableObject dobj
Definition: pg_dump.h:189
DumpComponents dump
Definition: pg_dump.h:131
struct _shellTypeInfo * shellType
Definition: pg_dump.h:181
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809
#define DUMP_COMPONENT_DEFINITION
Definition: pg_dump.h:89
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:782

◆ repairViewRuleLoop()

static void repairViewRuleLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 740 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

742 {
743  /* remove rule's dependency on view */
744  removeObjectDependency(ruleobj, viewobj->dumpId);
745  /* flags on the two objects are already set correctly for this case */
746 }
DumpId dumpId
Definition: pg_dump.h:129
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809

◆ repairViewRuleMultiLoop()

static void repairViewRuleMultiLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 760 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

762 {
763  TableInfo *viewinfo = (TableInfo *) viewobj;
764  RuleInfo *ruleinfo = (RuleInfo *) ruleobj;
765 
766  /* remove view's dependency on rule */
767  removeObjectDependency(viewobj, ruleobj->dumpId);
768  /* mark view to be printed with a dummy definition */
769  viewinfo->dummy_view = true;
770  /* mark rule as needing its own dump */
771  ruleinfo->separate = true;
772  /* put back rule's dependency on view */
773  addObjectDependency(ruleobj, viewobj->dumpId);
774  /* now that rule is separate, it must be post-data */
776 }
bool separate
Definition: pg_dump.h:399
DumpId dumpId
Definition: pg_dump.h:129
static DumpId postDataBoundId
Definition: pg_dump_sort.c:94
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:809
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:782
bool dummy_view
Definition: pg_dump.h:294

◆ sortDumpableObjects()

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

Definition at line 257 of file pg_dump_sort.c.

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

Referenced by main().

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

◆ sortDumpableObjectsByTypeName()

void sortDumpableObjectsByTypeName ( DumpableObject **  objs,
int  numObjs 
)

Definition at line 124 of file pg_dump_sort.c.

References DOTypeNameCompare(), and qsort.

Referenced by main().

125 {
126  if (numObjs > 1)
127  qsort((void *) objs, numObjs, sizeof(DumpableObject *),
129 }
static int DOTypeNameCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:132
#define qsort(a, b, c, d)
Definition: port.h:479

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

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

Variable Documentation

◆ dbObjectTypePriority

const int dbObjectTypePriority[]
static

Definition at line 42 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

◆ postDataBoundId

◆ preDataBoundId

DumpId preDataBoundId
static

Definition at line 93 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().