PostgreSQL Source Code  git master
pg_dump_sort.c File Reference
#include "postgres_fe.h"
#include "pg_backup_archiver.h"
#include "pg_backup_utils.h"
#include "pg_dump.h"
#include "catalog/pg_class_d.h"
Include dependency graph for pg_dump_sort.c:

Go to the source code of this file.

Functions

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)
 
static int DOSizeCompare (const void *p1, const void *p2)
 
static int findFirstEqualType (DumpableObjectType type, DumpableObject **objs, int numObjs)
 
static int findFirstDifferentType (DumpableObjectType type, DumpableObject **objs, int numObjs, int start)
 
void sortDataAndIndexObjectsBySize (DumpableObject **objs, int numObjs)
 
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 *matviewobj, 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 char * modulename = gettext_noop("sorter")
 
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 510 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

511 {
512  int j;
513 
514  /*
515  * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
516  * using 1-based array indexes, not 0-based.
517  */
518  j = heapLength;
519  while (j > 0)
520  {
521  int i = (j - 1) >> 1;
522 
523  if (val <= heap[i])
524  break;
525  heap[j] = heap[i];
526  j = i;
527  }
528  heap[j] = val;
529 }
int i
long val
Definition: informix.c:689

◆ describeDumpableObject()

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

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

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

◆ DOSizeCompare()

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

Definition at line 179 of file pg_dump_sort.c.

References DO_INDEX, DO_TABLE_DATA, and _dumpableObject::objType.

Referenced by sortDataAndIndexObjectsBySize().

180 {
181  DumpableObject *obj1 = *(DumpableObject **) p1;
182  DumpableObject *obj2 = *(DumpableObject **) p2;
183  int obj1_size = 0;
184  int obj2_size = 0;
185 
186  if (obj1->objType == DO_TABLE_DATA)
187  obj1_size = ((TableDataInfo *) obj1)->tdtable->relpages;
188  if (obj1->objType == DO_INDEX)
189  obj1_size = ((IndxInfo *) obj1)->relpages;
190 
191  if (obj2->objType == DO_TABLE_DATA)
192  obj2_size = ((TableDataInfo *) obj2)->tdtable->relpages;
193  if (obj2->objType == DO_INDEX)
194  obj2_size = ((IndxInfo *) obj2)->relpages;
195 
196  /* we want to see the biggest item go first */
197  if (obj1_size > obj2_size)
198  return -1;
199  if (obj2_size > obj1_size)
200  return 1;
201 
202  return 0;
203 }
DumpableObjectType objType
Definition: pg_dump.h:131

◆ DOTypeNameCompare()

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

Definition at line 220 of file pg_dump_sort.c.

References _attrDefInfo::adnum, _funcInfo::argtypes, _dumpableObject::catId, dbObjectTypePriority, DO_AGG, DO_ATTRDEF, DO_FUNC, DO_OPERATOR, _typeInfo::dobj, findTypeByOid(), i, _dumpableObject::name, _funcInfo::nargs, _dumpableObject::objType, CatalogId::oid, oidcmp, and _oprInfo::oprkind.

Referenced by sortDumpableObjectsByTypeName().

221 {
222  DumpableObject *obj1 = *(DumpableObject *const *) p1;
223  DumpableObject *obj2 = *(DumpableObject *const *) p2;
224  int cmpval;
225 
226  /* Sort by type */
227  cmpval = dbObjectTypePriority[obj1->objType] -
229 
230  if (cmpval != 0)
231  return cmpval;
232 
233  /*
234  * Sort by namespace. Note that all objects of the same type should
235  * either have or not have a namespace link, so we needn't be fancy about
236  * cases where one link is null and the other not.
237  */
238  if (obj1->namespace && obj2->namespace)
239  {
240  cmpval = strcmp(obj1->namespace->dobj.name,
241  obj2->namespace->dobj.name);
242  if (cmpval != 0)
243  return cmpval;
244  }
245 
246  /* Sort by name */
247  cmpval = strcmp(obj1->name, obj2->name);
248  if (cmpval != 0)
249  return cmpval;
250 
251  /* To have a stable sort order, break ties for some object types */
252  if (obj1->objType == DO_FUNC || obj1->objType == DO_AGG)
253  {
254  FuncInfo *fobj1 = *(FuncInfo *const *) p1;
255  FuncInfo *fobj2 = *(FuncInfo *const *) p2;
256  int i;
257 
258  cmpval = fobj1->nargs - fobj2->nargs;
259  if (cmpval != 0)
260  return cmpval;
261  for (i = 0; i < fobj1->nargs; i++)
262  {
263  TypeInfo *argtype1 = findTypeByOid(fobj1->argtypes[i]);
264  TypeInfo *argtype2 = findTypeByOid(fobj2->argtypes[i]);
265 
266  if (argtype1 && argtype2)
267  {
268  if (argtype1->dobj.namespace && argtype2->dobj.namespace)
269  {
270  cmpval = strcmp(argtype1->dobj.namespace->dobj.name,
271  argtype2->dobj.namespace->dobj.name);
272  if (cmpval != 0)
273  return cmpval;
274  }
275  cmpval = strcmp(argtype1->dobj.name, argtype2->dobj.name);
276  if (cmpval != 0)
277  return cmpval;
278  }
279  }
280  }
281  else if (obj1->objType == DO_OPERATOR)
282  {
283  OprInfo *oobj1 = *(OprInfo *const *) p1;
284  OprInfo *oobj2 = *(OprInfo *const *) p2;
285 
286  /* oprkind is 'l', 'r', or 'b'; this sorts prefix, postfix, infix */
287  cmpval = (oobj2->oprkind - oobj1->oprkind);
288  if (cmpval != 0)
289  return cmpval;
290  }
291  else if (obj1->objType == DO_ATTRDEF)
292  {
293  AttrDefInfo *adobj1 = *(AttrDefInfo *const *) p1;
294  AttrDefInfo *adobj2 = *(AttrDefInfo *const *) p2;
295 
296  cmpval = (adobj1->adnum - adobj2->adnum);
297  if (cmpval != 0)
298  return cmpval;
299  }
300 
301  /* Usually shouldn't get here, but if we do, sort by OID */
302  return oidcmp(obj1->catId.oid, obj2->catId.oid);
303 }
Oid * argtypes
Definition: pg_dump.h:203
char * name
Definition: pg_dump.h:134
#define oidcmp(x, y)
Definition: pg_dump.h:20
int nargs
Definition: pg_dump.h:202
Definition: pg_dump.h:49
DumpableObject dobj
Definition: pg_dump.h:166
static const int dbObjectTypePriority[]
Definition: pg_dump_sort.c:43
char oprkind
Definition: pg_dump.h:222
CatalogId catId
Definition: pg_dump.h:132
int i
TypeInfo * findTypeByOid(Oid oid)
Definition: common.c:863
DumpableObjectType objType
Definition: pg_dump.h:131

◆ findDependencyLoops()

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

Definition at line 586 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

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

◆ findFirstDifferentType()

static int findFirstDifferentType ( DumpableObjectType  type,
DumpableObject **  objs,
int  numObjs,
int  start 
)
static

Definition at line 128 of file pg_dump_sort.c.

References i.

Referenced by sortDataAndIndexObjectsBySize().

129 {
130  int i;
131 
132  for (i = start; i < numObjs; i++)
133  if (objs[i]->objType != type)
134  return i;
135  return numObjs - 1;
136 }
int i

◆ findFirstEqualType()

static int findFirstEqualType ( DumpableObjectType  type,
DumpableObject **  objs,
int  numObjs 
)
static

Definition at line 117 of file pg_dump_sort.c.

References i.

Referenced by sortDataAndIndexObjectsBySize().

118 {
119  int i;
120 
121  for (i = 0; i < numObjs; i++)
122  if (objs[i]->objType == type)
123  return i;
124  return -1;
125 }
int i

◆ findLoop()

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

Definition at line 682 of file pg_dump_sort.c.

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

Referenced by findDependencyLoops().

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

◆ removeHeapElement()

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

Definition at line 541 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

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

◆ 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, modulename, name, ngettext, relkind, removeObjectDependency(), repairDomainConstraintLoop(), repairDomainConstraintMultiLoop(), repairIndexLoop(), repairMatViewBoundaryMultiLoop(), repairTableAttrDefLoop(), repairTableAttrDefMultiLoop(), repairTableConstraintLoop(), repairTableConstraintMultiLoop(), repairTypeFuncLoop(), repairViewRuleLoop(), repairViewRuleMultiLoop(), and write_msg().

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[i], loop[j],
1047  nextobj);
1048  return;
1049  }
1050  }
1051  }
1052  }
1053  }
1054 
1055  /* Table and CHECK constraint */
1056  if (nLoop == 2 &&
1057  loop[0]->objType == DO_TABLE &&
1058  loop[1]->objType == DO_CONSTRAINT &&
1059  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1060  ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
1061  {
1062  repairTableConstraintLoop(loop[0], loop[1]);
1063  return;
1064  }
1065  if (nLoop == 2 &&
1066  loop[1]->objType == DO_TABLE &&
1067  loop[0]->objType == DO_CONSTRAINT &&
1068  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1069  ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
1070  {
1071  repairTableConstraintLoop(loop[1], loop[0]);
1072  return;
1073  }
1074 
1075  /* Indirect loop involving table and CHECK constraint */
1076  if (nLoop > 2)
1077  {
1078  for (i = 0; i < nLoop; i++)
1079  {
1080  if (loop[i]->objType == DO_TABLE)
1081  {
1082  for (j = 0; j < nLoop; j++)
1083  {
1084  if (loop[j]->objType == DO_CONSTRAINT &&
1085  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1086  ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
1087  {
1088  repairTableConstraintMultiLoop(loop[i], loop[j]);
1089  return;
1090  }
1091  }
1092  }
1093  }
1094  }
1095 
1096  /* Table and attribute default */
1097  if (nLoop == 2 &&
1098  loop[0]->objType == DO_TABLE &&
1099  loop[1]->objType == DO_ATTRDEF &&
1100  ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
1101  {
1102  repairTableAttrDefLoop(loop[0], loop[1]);
1103  return;
1104  }
1105  if (nLoop == 2 &&
1106  loop[1]->objType == DO_TABLE &&
1107  loop[0]->objType == DO_ATTRDEF &&
1108  ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
1109  {
1110  repairTableAttrDefLoop(loop[1], loop[0]);
1111  return;
1112  }
1113 
1114  /* index on partitioned table and corresponding index on partition */
1115  if (nLoop == 2 &&
1116  loop[0]->objType == DO_INDEX &&
1117  loop[1]->objType == DO_INDEX)
1118  {
1119  if (((IndxInfo *) loop[0])->parentidx == loop[1]->catId.oid)
1120  {
1121  repairIndexLoop(loop[0], loop[1]);
1122  return;
1123  }
1124  else if (((IndxInfo *) loop[1])->parentidx == loop[0]->catId.oid)
1125  {
1126  repairIndexLoop(loop[1], loop[0]);
1127  return;
1128  }
1129  }
1130 
1131  /* Indirect loop involving table and attribute default */
1132  if (nLoop > 2)
1133  {
1134  for (i = 0; i < nLoop; i++)
1135  {
1136  if (loop[i]->objType == DO_TABLE)
1137  {
1138  for (j = 0; j < nLoop; j++)
1139  {
1140  if (loop[j]->objType == DO_ATTRDEF &&
1141  ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
1142  {
1143  repairTableAttrDefMultiLoop(loop[i], loop[j]);
1144  return;
1145  }
1146  }
1147  }
1148  }
1149  }
1150 
1151  /* Domain and CHECK constraint */
1152  if (nLoop == 2 &&
1153  loop[0]->objType == DO_TYPE &&
1154  loop[1]->objType == DO_CONSTRAINT &&
1155  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1156  ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
1157  {
1158  repairDomainConstraintLoop(loop[0], loop[1]);
1159  return;
1160  }
1161  if (nLoop == 2 &&
1162  loop[1]->objType == DO_TYPE &&
1163  loop[0]->objType == DO_CONSTRAINT &&
1164  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1165  ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
1166  {
1167  repairDomainConstraintLoop(loop[1], loop[0]);
1168  return;
1169  }
1170 
1171  /* Indirect loop involving domain and CHECK constraint */
1172  if (nLoop > 2)
1173  {
1174  for (i = 0; i < nLoop; i++)
1175  {
1176  if (loop[i]->objType == DO_TYPE)
1177  {
1178  for (j = 0; j < nLoop; j++)
1179  {
1180  if (loop[j]->objType == DO_CONSTRAINT &&
1181  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1182  ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
1183  {
1184  repairDomainConstraintMultiLoop(loop[i], loop[j]);
1185  return;
1186  }
1187  }
1188  }
1189  }
1190  }
1191 
1192  /*
1193  * If all the objects are TABLE_DATA items, what we must have is a
1194  * circular set of foreign key constraints (or a single self-referential
1195  * table). Print an appropriate complaint and break the loop arbitrarily.
1196  */
1197  for (i = 0; i < nLoop; i++)
1198  {
1199  if (loop[i]->objType != DO_TABLE_DATA)
1200  break;
1201  }
1202  if (i >= nLoop)
1203  {
1204  write_msg(NULL, ngettext("NOTICE: there are circular foreign-key constraints on this table:\n",
1205  "NOTICE: there are circular foreign-key constraints among these tables:\n",
1206  nLoop));
1207  for (i = 0; i < nLoop; i++)
1208  write_msg(NULL, " %s\n", loop[i]->name);
1209  write_msg(NULL, "You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.\n");
1210  write_msg(NULL, "Consider using a full dump instead of a --data-only dump to avoid this problem.\n");
1211  if (nLoop > 1)
1212  removeObjectDependency(loop[0], loop[1]->dumpId);
1213  else /* must be a self-dependency */
1214  removeObjectDependency(loop[0], loop[0]->dumpId);
1215  return;
1216  }
1217 
1218  /*
1219  * If we can't find a principled way to break the loop, complain and break
1220  * it in an arbitrary fashion.
1221  */
1222  write_msg(modulename, "WARNING: could not resolve dependency loop among these items:\n");
1223  for (i = 0; i < nLoop; i++)
1224  {
1225  char buf[1024];
1226 
1227  describeDumpableObject(loop[i], buf, sizeof(buf));
1228  write_msg(modulename, " %s\n", buf);
1229  }
1230 
1231  if (nLoop > 1)
1232  removeObjectDependency(loop[0], loop[1]->dumpId);
1233  else /* must be a self-dependency */
1234  removeObjectDependency(loop[0], loop[0]->dumpId);
1235 }
static void repairMatViewBoundaryMultiLoop(DumpableObject *matviewobj, DumpableObject *boundaryobj, DumpableObject *nextobj)
Definition: pg_dump_sort.c:848
static void repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
Definition: pg_dump_sort.c:767
static void describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
char relkind
Definition: pg_class.h:51
static void repairViewRuleLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:798
static char * buf
Definition: pg_test_fsync.c:67
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:818
static void repairDomainConstraintLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:924
#define ngettext(s, p, n)
Definition: c.h:1022
static void repairIndexLoop(DumpableObject *partedindex, DumpableObject *partindex)
Definition: pg_dump_sort.c:946
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832
static const char * modulename
Definition: pg_dump_sort.c:25
static void repairTableConstraintLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:867
void write_msg(const char *modulename, const char *fmt,...)
const char * name
Definition: encode.c:521
int i
static void repairTableAttrDefMultiLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:909
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:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832

◆ 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:133
static DumpId postDataBoundId
Definition: pg_dump_sort.c:92
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:805

◆ 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:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832

◆ repairMatViewBoundaryMultiLoop()

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

Definition at line 848 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

851 {
852  TableInfo *matviewinfo = (TableInfo *) matviewobj;
853 
854  /* remove boundary's dependency on object after it in loop */
855  removeObjectDependency(boundaryobj, nextobj->dumpId);
856  /* mark matview as postponed into post-data section */
857  matviewinfo->postponed_def = true;
858 }
DumpId dumpId
Definition: pg_dump.h:133
bool postponed_def
Definition: pg_dump.h:297
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832

◆ 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:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832

◆ 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:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:805

◆ 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:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832

◆ 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:133
static DumpId postDataBoundId
Definition: pg_dump_sort.c:92
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:805

◆ repairTypeFuncLoop()

static void repairTypeFuncLoop ( DumpableObject typeobj,
DumpableObject funcobj 
)
static

Definition at line 767 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

768 {
769  TypeInfo *typeInfo = (TypeInfo *) typeobj;
770 
771  /* remove function's dependency on type */
772  removeObjectDependency(funcobj, typeobj->dumpId);
773 
774  /* add function's dependency on shell type, instead */
775  if (typeInfo->shellType)
776  {
777  addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
778 
779  /*
780  * Mark shell type (always including the definition, as we need the
781  * shell type defined to identify the function fully) as to be dumped
782  * if any such function is
783  */
784  if (funcobj->dump)
785  typeInfo->shellType->dobj.dump = funcobj->dump |
787  }
788 }
DumpableObject dobj
Definition: pg_dump.h:192
DumpComponents dump
Definition: pg_dump.h:135
struct _shellTypeInfo * shellType
Definition: pg_dump.h:184
DumpId dumpId
Definition: pg_dump.h:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832
#define DUMP_COMPONENT_DEFINITION
Definition: pg_dump.h:93
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:805

◆ repairViewRuleLoop()

static void repairViewRuleLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 798 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

800 {
801  /* remove rule's dependency on view */
802  removeObjectDependency(ruleobj, viewobj->dumpId);
803  /* flags on the two objects are already set correctly for this case */
804 }
DumpId dumpId
Definition: pg_dump.h:133
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832

◆ repairViewRuleMultiLoop()

static void repairViewRuleMultiLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 818 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

820 {
821  TableInfo *viewinfo = (TableInfo *) viewobj;
822  RuleInfo *ruleinfo = (RuleInfo *) ruleobj;
823 
824  /* remove view's dependency on rule */
825  removeObjectDependency(viewobj, ruleobj->dumpId);
826  /* mark view to be printed with a dummy definition */
827  viewinfo->dummy_view = true;
828  /* mark rule as needing its own dump */
829  ruleinfo->separate = true;
830  /* put back rule's dependency on view */
831  addObjectDependency(ruleobj, viewobj->dumpId);
832  /* now that rule is separate, it must be post-data */
834 }
bool separate
Definition: pg_dump.h:395
DumpId dumpId
Definition: pg_dump.h:133
static DumpId postDataBoundId
Definition: pg_dump_sort.c:92
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:832
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:805
bool dummy_view
Definition: pg_dump.h:296

◆ sortDataAndIndexObjectsBySize()

void sortDataAndIndexObjectsBySize ( DumpableObject **  objs,
int  numObjs 
)

Definition at line 150 of file pg_dump_sort.c.

References DO_INDEX, DO_TABLE_DATA, DOSizeCompare(), findFirstDifferentType(), findFirstEqualType(), and qsort.

Referenced by main().

151 {
152  int startIdx,
153  endIdx;
154  void *startPtr;
155 
156  if (numObjs <= 1)
157  return;
158 
159  startIdx = findFirstEqualType(DO_TABLE_DATA, objs, numObjs);
160  if (startIdx >= 0)
161  {
162  endIdx = findFirstDifferentType(DO_TABLE_DATA, objs, numObjs, startIdx);
163  startPtr = objs + startIdx;
164  qsort(startPtr, endIdx - startIdx, sizeof(DumpableObject *),
165  DOSizeCompare);
166  }
167 
168  startIdx = findFirstEqualType(DO_INDEX, objs, numObjs);
169  if (startIdx >= 0)
170  {
171  endIdx = findFirstDifferentType(DO_INDEX, objs, numObjs, startIdx);
172  startPtr = objs + startIdx;
173  qsort(startPtr, endIdx - startIdx, sizeof(DumpableObject *),
174  DOSizeCompare);
175  }
176 }
static int findFirstEqualType(DumpableObjectType type, DumpableObject **objs, int numObjs)
Definition: pg_dump_sort.c:117
static int DOSizeCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:179
static int findFirstDifferentType(DumpableObjectType type, DumpableObject **objs, int numObjs, int start)
Definition: pg_dump_sort.c:128
#define qsort(a, b, c, d)
Definition: port.h:421

◆ sortDumpableObjects()

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

Definition at line 314 of file pg_dump_sort.c.

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

Referenced by main().

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

◆ sortDumpableObjectsByTypeName()

void sortDumpableObjectsByTypeName ( DumpableObject **  objs,
int  numObjs 
)

Definition at line 212 of file pg_dump_sort.c.

References DOTypeNameCompare(), and qsort.

Referenced by main().

213 {
214  if (numObjs > 1)
215  qsort((void *) objs, numObjs, sizeof(DumpableObject *),
217 }
static int DOTypeNameCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:220
#define qsort(a, b, c, d)
Definition: port.h:421

◆ TopoSort()

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

Definition at line 366 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

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

Variable Documentation

◆ dbObjectTypePriority

const int dbObjectTypePriority[]
static

Definition at line 43 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

◆ modulename

const char* modulename = gettext_noop("sorter")
static

Definition at line 25 of file pg_dump_sort.c.

Referenced by findDependencyLoops(), repairDependencyLoop(), and TopoSort().

◆ postDataBoundId

◆ preDataBoundId

DumpId preDataBoundId
static

Definition at line 91 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().