PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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.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)
 

Variables

static const char * modulename = gettext_noop("sorter")
 
static const int dbObjectTypePriority []
 
static DumpId preDataBoundId
 
static DumpId postDataBoundId
 

Function Documentation

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

Definition at line 505 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

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

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

1215 {
1216  switch (obj->objType)
1217  {
1218  case DO_NAMESPACE:
1219  snprintf(buf, bufsize,
1220  "SCHEMA %s (ID %d OID %u)",
1221  obj->name, obj->dumpId, obj->catId.oid);
1222  return;
1223  case DO_EXTENSION:
1224  snprintf(buf, bufsize,
1225  "EXTENSION %s (ID %d OID %u)",
1226  obj->name, obj->dumpId, obj->catId.oid);
1227  return;
1228  case DO_TYPE:
1229  snprintf(buf, bufsize,
1230  "TYPE %s (ID %d OID %u)",
1231  obj->name, obj->dumpId, obj->catId.oid);
1232  return;
1233  case DO_SHELL_TYPE:
1234  snprintf(buf, bufsize,
1235  "SHELL TYPE %s (ID %d OID %u)",
1236  obj->name, obj->dumpId, obj->catId.oid);
1237  return;
1238  case DO_FUNC:
1239  snprintf(buf, bufsize,
1240  "FUNCTION %s (ID %d OID %u)",
1241  obj->name, obj->dumpId, obj->catId.oid);
1242  return;
1243  case DO_AGG:
1244  snprintf(buf, bufsize,
1245  "AGGREGATE %s (ID %d OID %u)",
1246  obj->name, obj->dumpId, obj->catId.oid);
1247  return;
1248  case DO_OPERATOR:
1249  snprintf(buf, bufsize,
1250  "OPERATOR %s (ID %d OID %u)",
1251  obj->name, obj->dumpId, obj->catId.oid);
1252  return;
1253  case DO_ACCESS_METHOD:
1254  snprintf(buf, bufsize,
1255  "ACCESS METHOD %s (ID %d OID %u)",
1256  obj->name, obj->dumpId, obj->catId.oid);
1257  return;
1258  case DO_OPCLASS:
1259  snprintf(buf, bufsize,
1260  "OPERATOR CLASS %s (ID %d OID %u)",
1261  obj->name, obj->dumpId, obj->catId.oid);
1262  return;
1263  case DO_OPFAMILY:
1264  snprintf(buf, bufsize,
1265  "OPERATOR FAMILY %s (ID %d OID %u)",
1266  obj->name, obj->dumpId, obj->catId.oid);
1267  return;
1268  case DO_COLLATION:
1269  snprintf(buf, bufsize,
1270  "COLLATION %s (ID %d OID %u)",
1271  obj->name, obj->dumpId, obj->catId.oid);
1272  return;
1273  case DO_CONVERSION:
1274  snprintf(buf, bufsize,
1275  "CONVERSION %s (ID %d OID %u)",
1276  obj->name, obj->dumpId, obj->catId.oid);
1277  return;
1278  case DO_TABLE:
1279  snprintf(buf, bufsize,
1280  "TABLE %s (ID %d OID %u)",
1281  obj->name, obj->dumpId, obj->catId.oid);
1282  return;
1283  case DO_ATTRDEF:
1284  snprintf(buf, bufsize,
1285  "ATTRDEF %s.%s (ID %d OID %u)",
1286  ((AttrDefInfo *) obj)->adtable->dobj.name,
1287  ((AttrDefInfo *) obj)->adtable->attnames[((AttrDefInfo *) obj)->adnum - 1],
1288  obj->dumpId, obj->catId.oid);
1289  return;
1290  case DO_INDEX:
1291  snprintf(buf, bufsize,
1292  "INDEX %s (ID %d OID %u)",
1293  obj->name, obj->dumpId, obj->catId.oid);
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:133
int snprintf(char *str, size_t count, const char *fmt,...) pg_attribute_printf(3
DumpId dumpId
Definition: pg_dump.h:132
Definition: pg_dump.h:49
static char * buf
Definition: pg_test_fsync.c:66
Definition: pg_dump.h:73
CatalogId catId
Definition: pg_dump.h:131
DumpableObjectType objType
Definition: pg_dump.h:130
static int DOSizeCompare ( const void *  p1,
const void *  p2 
)
static

Definition at line 174 of file pg_dump_sort.c.

References DO_INDEX, DO_TABLE_DATA, and _dumpableObject::objType.

Referenced by sortDataAndIndexObjectsBySize().

175 {
176  DumpableObject *obj1 = *(DumpableObject **) p1;
177  DumpableObject *obj2 = *(DumpableObject **) p2;
178  int obj1_size = 0;
179  int obj2_size = 0;
180 
181  if (obj1->objType == DO_TABLE_DATA)
182  obj1_size = ((TableDataInfo *) obj1)->tdtable->relpages;
183  if (obj1->objType == DO_INDEX)
184  obj1_size = ((IndxInfo *) obj1)->relpages;
185 
186  if (obj2->objType == DO_TABLE_DATA)
187  obj2_size = ((TableDataInfo *) obj2)->tdtable->relpages;
188  if (obj2->objType == DO_INDEX)
189  obj2_size = ((IndxInfo *) obj2)->relpages;
190 
191  /* we want to see the biggest item go first */
192  if (obj1_size > obj2_size)
193  return -1;
194  if (obj2_size > obj1_size)
195  return 1;
196 
197  return 0;
198 }
DumpableObjectType objType
Definition: pg_dump.h:130
static int DOTypeNameCompare ( const void *  p1,
const void *  p2 
)
static

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

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

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

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

Definition at line 123 of file pg_dump_sort.c.

References i.

Referenced by sortDataAndIndexObjectsBySize().

124 {
125  int i;
126 
127  for (i = start; i < numObjs; i++)
128  if (objs[i]->objType != type)
129  return i;
130  return numObjs - 1;
131 }
int i
static int findFirstEqualType ( DumpableObjectType  type,
DumpableObject **  objs,
int  numObjs 
)
static

Definition at line 112 of file pg_dump_sort.c.

References i.

Referenced by sortDataAndIndexObjectsBySize().

113 {
114  int i;
115 
116  for (i = 0; i < numObjs; i++)
117  if (objs[i]->objType == type)
118  return i;
119  return -1;
120 }
int i
static int findLoop ( DumpableObject obj,
DumpId  startPoint,
bool processed,
DumpId searchFailed,
DumpableObject **  workspace,
int  depth 
)
static

Definition at line 677 of file pg_dump_sort.c.

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

Referenced by findDependencyLoops().

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

Definition at line 536 of file pg_dump_sort.c.

References i, result, and val.

Referenced by TopoSort().

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

Definition at line 948 of file pg_dump_sort.c.

References buf, describeDumpableObject(), DO_ATTRDEF, DO_CONSTRAINT, DO_FUNC, DO_PRE_DATA_BOUNDARY, DO_RULE, DO_TABLE, DO_TABLE_DATA, DO_TYPE, i, modulename, name, ngettext, NULL, RELKIND_MATVIEW, RELKIND_VIEW, removeObjectDependency(), repairDomainConstraintLoop(), repairDomainConstraintMultiLoop(), repairMatViewBoundaryMultiLoop(), repairTableAttrDefLoop(), repairTableAttrDefMultiLoop(), repairTableConstraintLoop(), repairTableConstraintMultiLoop(), repairTypeFuncLoop(), repairViewRuleLoop(), repairViewRuleMultiLoop(), and write_msg().

Referenced by findDependencyLoops().

950 {
951  int i,
952  j;
953 
954  /* Datatype and one of its I/O or canonicalize functions */
955  if (nLoop == 2 &&
956  loop[0]->objType == DO_TYPE &&
957  loop[1]->objType == DO_FUNC)
958  {
959  repairTypeFuncLoop(loop[0], loop[1]);
960  return;
961  }
962  if (nLoop == 2 &&
963  loop[1]->objType == DO_TYPE &&
964  loop[0]->objType == DO_FUNC)
965  {
966  repairTypeFuncLoop(loop[1], loop[0]);
967  return;
968  }
969 
970  /* View (including matview) and its ON SELECT rule */
971  if (nLoop == 2 &&
972  loop[0]->objType == DO_TABLE &&
973  loop[1]->objType == DO_RULE &&
974  (((TableInfo *) loop[0])->relkind == RELKIND_VIEW ||
975  ((TableInfo *) loop[0])->relkind == RELKIND_MATVIEW) &&
976  ((RuleInfo *) loop[1])->ev_type == '1' &&
977  ((RuleInfo *) loop[1])->is_instead &&
978  ((RuleInfo *) loop[1])->ruletable == (TableInfo *) loop[0])
979  {
980  repairViewRuleLoop(loop[0], loop[1]);
981  return;
982  }
983  if (nLoop == 2 &&
984  loop[1]->objType == DO_TABLE &&
985  loop[0]->objType == DO_RULE &&
986  (((TableInfo *) loop[1])->relkind == RELKIND_VIEW ||
987  ((TableInfo *) loop[1])->relkind == RELKIND_MATVIEW) &&
988  ((RuleInfo *) loop[0])->ev_type == '1' &&
989  ((RuleInfo *) loop[0])->is_instead &&
990  ((RuleInfo *) loop[0])->ruletable == (TableInfo *) loop[1])
991  {
992  repairViewRuleLoop(loop[1], loop[0]);
993  return;
994  }
995 
996  /* Indirect loop involving view (but not matview) and ON SELECT rule */
997  if (nLoop > 2)
998  {
999  for (i = 0; i < nLoop; i++)
1000  {
1001  if (loop[i]->objType == DO_TABLE &&
1002  ((TableInfo *) loop[i])->relkind == RELKIND_VIEW)
1003  {
1004  for (j = 0; j < nLoop; j++)
1005  {
1006  if (loop[j]->objType == DO_RULE &&
1007  ((RuleInfo *) loop[j])->ev_type == '1' &&
1008  ((RuleInfo *) loop[j])->is_instead &&
1009  ((RuleInfo *) loop[j])->ruletable == (TableInfo *) loop[i])
1010  {
1011  repairViewRuleMultiLoop(loop[i], loop[j]);
1012  return;
1013  }
1014  }
1015  }
1016  }
1017  }
1018 
1019  /* Indirect loop involving matview and data boundary */
1020  if (nLoop > 2)
1021  {
1022  for (i = 0; i < nLoop; i++)
1023  {
1024  if (loop[i]->objType == DO_TABLE &&
1025  ((TableInfo *) loop[i])->relkind == RELKIND_MATVIEW)
1026  {
1027  for (j = 0; j < nLoop; j++)
1028  {
1029  if (loop[j]->objType == DO_PRE_DATA_BOUNDARY)
1030  {
1031  DumpableObject *nextobj;
1032 
1033  nextobj = (j < nLoop - 1) ? loop[j + 1] : loop[0];
1034  repairMatViewBoundaryMultiLoop(loop[i], loop[j],
1035  nextobj);
1036  return;
1037  }
1038  }
1039  }
1040  }
1041  }
1042 
1043  /* Table and CHECK constraint */
1044  if (nLoop == 2 &&
1045  loop[0]->objType == DO_TABLE &&
1046  loop[1]->objType == DO_CONSTRAINT &&
1047  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1048  ((ConstraintInfo *) loop[1])->contable == (TableInfo *) loop[0])
1049  {
1050  repairTableConstraintLoop(loop[0], loop[1]);
1051  return;
1052  }
1053  if (nLoop == 2 &&
1054  loop[1]->objType == DO_TABLE &&
1055  loop[0]->objType == DO_CONSTRAINT &&
1056  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1057  ((ConstraintInfo *) loop[0])->contable == (TableInfo *) loop[1])
1058  {
1059  repairTableConstraintLoop(loop[1], loop[0]);
1060  return;
1061  }
1062 
1063  /* Indirect loop involving table and CHECK constraint */
1064  if (nLoop > 2)
1065  {
1066  for (i = 0; i < nLoop; i++)
1067  {
1068  if (loop[i]->objType == DO_TABLE)
1069  {
1070  for (j = 0; j < nLoop; j++)
1071  {
1072  if (loop[j]->objType == DO_CONSTRAINT &&
1073  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1074  ((ConstraintInfo *) loop[j])->contable == (TableInfo *) loop[i])
1075  {
1076  repairTableConstraintMultiLoop(loop[i], loop[j]);
1077  return;
1078  }
1079  }
1080  }
1081  }
1082  }
1083 
1084  /* Table and attribute default */
1085  if (nLoop == 2 &&
1086  loop[0]->objType == DO_TABLE &&
1087  loop[1]->objType == DO_ATTRDEF &&
1088  ((AttrDefInfo *) loop[1])->adtable == (TableInfo *) loop[0])
1089  {
1090  repairTableAttrDefLoop(loop[0], loop[1]);
1091  return;
1092  }
1093  if (nLoop == 2 &&
1094  loop[1]->objType == DO_TABLE &&
1095  loop[0]->objType == DO_ATTRDEF &&
1096  ((AttrDefInfo *) loop[0])->adtable == (TableInfo *) loop[1])
1097  {
1098  repairTableAttrDefLoop(loop[1], loop[0]);
1099  return;
1100  }
1101 
1102  /* Indirect loop involving table and attribute default */
1103  if (nLoop > 2)
1104  {
1105  for (i = 0; i < nLoop; i++)
1106  {
1107  if (loop[i]->objType == DO_TABLE)
1108  {
1109  for (j = 0; j < nLoop; j++)
1110  {
1111  if (loop[j]->objType == DO_ATTRDEF &&
1112  ((AttrDefInfo *) loop[j])->adtable == (TableInfo *) loop[i])
1113  {
1114  repairTableAttrDefMultiLoop(loop[i], loop[j]);
1115  return;
1116  }
1117  }
1118  }
1119  }
1120  }
1121 
1122  /* Domain and CHECK constraint */
1123  if (nLoop == 2 &&
1124  loop[0]->objType == DO_TYPE &&
1125  loop[1]->objType == DO_CONSTRAINT &&
1126  ((ConstraintInfo *) loop[1])->contype == 'c' &&
1127  ((ConstraintInfo *) loop[1])->condomain == (TypeInfo *) loop[0])
1128  {
1129  repairDomainConstraintLoop(loop[0], loop[1]);
1130  return;
1131  }
1132  if (nLoop == 2 &&
1133  loop[1]->objType == DO_TYPE &&
1134  loop[0]->objType == DO_CONSTRAINT &&
1135  ((ConstraintInfo *) loop[0])->contype == 'c' &&
1136  ((ConstraintInfo *) loop[0])->condomain == (TypeInfo *) loop[1])
1137  {
1138  repairDomainConstraintLoop(loop[1], loop[0]);
1139  return;
1140  }
1141 
1142  /* Indirect loop involving domain and CHECK constraint */
1143  if (nLoop > 2)
1144  {
1145  for (i = 0; i < nLoop; i++)
1146  {
1147  if (loop[i]->objType == DO_TYPE)
1148  {
1149  for (j = 0; j < nLoop; j++)
1150  {
1151  if (loop[j]->objType == DO_CONSTRAINT &&
1152  ((ConstraintInfo *) loop[j])->contype == 'c' &&
1153  ((ConstraintInfo *) loop[j])->condomain == (TypeInfo *) loop[i])
1154  {
1155  repairDomainConstraintMultiLoop(loop[i], loop[j]);
1156  return;
1157  }
1158  }
1159  }
1160  }
1161  }
1162 
1163  /*
1164  * If all the objects are TABLE_DATA items, what we must have is a
1165  * circular set of foreign key constraints (or a single self-referential
1166  * table). Print an appropriate complaint and break the loop arbitrarily.
1167  */
1168  for (i = 0; i < nLoop; i++)
1169  {
1170  if (loop[i]->objType != DO_TABLE_DATA)
1171  break;
1172  }
1173  if (i >= nLoop)
1174  {
1175  write_msg(NULL, ngettext("NOTICE: there are circular foreign-key constraints on this table:\n",
1176  "NOTICE: there are circular foreign-key constraints among these tables:\n",
1177  nLoop));
1178  for (i = 0; i < nLoop; i++)
1179  write_msg(NULL, " %s\n", loop[i]->name);
1180  write_msg(NULL, "You might not be able to restore the dump without using --disable-triggers or temporarily dropping the constraints.\n");
1181  write_msg(NULL, "Consider using a full dump instead of a --data-only dump to avoid this problem.\n");
1182  if (nLoop > 1)
1183  removeObjectDependency(loop[0], loop[1]->dumpId);
1184  else /* must be a self-dependency */
1185  removeObjectDependency(loop[0], loop[0]->dumpId);
1186  return;
1187  }
1188 
1189  /*
1190  * If we can't find a principled way to break the loop, complain and break
1191  * it in an arbitrary fashion.
1192  */
1193  write_msg(modulename, "WARNING: could not resolve dependency loop among these items:\n");
1194  for (i = 0; i < nLoop; i++)
1195  {
1196  char buf[1024];
1197 
1198  describeDumpableObject(loop[i], buf, sizeof(buf));
1199  write_msg(modulename, " %s\n", buf);
1200  }
1201 
1202  if (nLoop > 1)
1203  removeObjectDependency(loop[0], loop[1]->dumpId);
1204  else /* must be a self-dependency */
1205  removeObjectDependency(loop[0], loop[0]->dumpId);
1206 }
static void repairMatViewBoundaryMultiLoop(DumpableObject *matviewobj, DumpableObject *boundaryobj, DumpableObject *nextobj)
Definition: pg_dump_sort.c:843
static void repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
Definition: pg_dump_sort.c:762
static void describeDumpableObject(DumpableObject *obj, char *buf, int bufsize)
#define RELKIND_MATVIEW
Definition: pg_class.h:165
static void repairViewRuleLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:793
static char * buf
Definition: pg_test_fsync.c:66
static void repairTableConstraintMultiLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:879
static void repairViewRuleMultiLoop(DumpableObject *viewobj, DumpableObject *ruleobj)
Definition: pg_dump_sort.c:813
static void repairDomainConstraintLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:919
#define ngettext(s, p, n)
Definition: c.h:127
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
static const char * modulename
Definition: pg_dump_sort.c:25
static void repairTableConstraintLoop(DumpableObject *tableobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:862
void write_msg(const char *modulename, const char *fmt,...)
#define NULL
Definition: c.h:229
const char * name
Definition: encode.c:521
#define RELKIND_VIEW
Definition: pg_class.h:164
int i
static void repairTableAttrDefMultiLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:904
static void repairDomainConstraintMultiLoop(DumpableObject *domainobj, DumpableObject *constraintobj)
Definition: pg_dump_sort.c:927
static void repairTableAttrDefLoop(DumpableObject *tableobj, DumpableObject *attrdefobj)
Definition: pg_dump_sort.c:896
static void repairDomainConstraintLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 919 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

921 {
922  /* remove constraint's dependency on domain */
923  removeObjectDependency(constraintobj, domainobj->dumpId);
924 }
DumpId dumpId
Definition: pg_dump.h:132
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
static void repairDomainConstraintMultiLoop ( DumpableObject domainobj,
DumpableObject constraintobj 
)
static

Definition at line 927 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

929 {
930  /* remove domain's dependency on constraint */
931  removeObjectDependency(domainobj, constraintobj->dumpId);
932  /* mark constraint as needing its own dump */
933  ((ConstraintInfo *) constraintobj)->separate = true;
934  /* put back constraint's dependency on domain */
935  addObjectDependency(constraintobj, domainobj->dumpId);
936  /* now that constraint is separate, it must be post-data */
937  addObjectDependency(constraintobj, postDataBoundId);
938 }
DumpId dumpId
Definition: pg_dump.h:132
static DumpId postDataBoundId
Definition: pg_dump_sort.c:87
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:712
static void repairMatViewBoundaryMultiLoop ( DumpableObject matviewobj,
DumpableObject boundaryobj,
DumpableObject nextobj 
)
static

Definition at line 843 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

846 {
847  TableInfo *matviewinfo = (TableInfo *) matviewobj;
848 
849  /* remove boundary's dependency on object after it in loop */
850  removeObjectDependency(boundaryobj, nextobj->dumpId);
851  /* mark matview as postponed into post-data section */
852  matviewinfo->postponed_def = true;
853 }
DumpId dumpId
Definition: pg_dump.h:132
bool postponed_def
Definition: pg_dump.h:296
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
static void repairTableAttrDefLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 896 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

898 {
899  /* remove attrdef's dependency on table */
900  removeObjectDependency(attrdefobj, tableobj->dumpId);
901 }
DumpId dumpId
Definition: pg_dump.h:132
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
static void repairTableAttrDefMultiLoop ( DumpableObject tableobj,
DumpableObject attrdefobj 
)
static

Definition at line 904 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

906 {
907  /* remove table's dependency on attrdef */
908  removeObjectDependency(tableobj, attrdefobj->dumpId);
909  /* mark attrdef as needing its own dump */
910  ((AttrDefInfo *) attrdefobj)->separate = true;
911  /* put back attrdef's dependency on table */
912  addObjectDependency(attrdefobj, tableobj->dumpId);
913 }
DumpId dumpId
Definition: pg_dump.h:132
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:712
static void repairTableConstraintLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 862 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

864 {
865  /* remove constraint's dependency on table */
866  removeObjectDependency(constraintobj, tableobj->dumpId);
867 }
DumpId dumpId
Definition: pg_dump.h:132
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
static void repairTableConstraintMultiLoop ( DumpableObject tableobj,
DumpableObject constraintobj 
)
static

Definition at line 879 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

881 {
882  /* remove table's dependency on constraint */
883  removeObjectDependency(tableobj, constraintobj->dumpId);
884  /* mark constraint as needing its own dump */
885  ((ConstraintInfo *) constraintobj)->separate = true;
886  /* put back constraint's dependency on table */
887  addObjectDependency(constraintobj, tableobj->dumpId);
888  /* now that constraint is separate, it must be post-data */
889  addObjectDependency(constraintobj, postDataBoundId);
890 }
DumpId dumpId
Definition: pg_dump.h:132
static DumpId postDataBoundId
Definition: pg_dump_sort.c:87
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:712
static void repairTypeFuncLoop ( DumpableObject typeobj,
DumpableObject funcobj 
)
static

Definition at line 762 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

763 {
764  TypeInfo *typeInfo = (TypeInfo *) typeobj;
765 
766  /* remove function's dependency on type */
767  removeObjectDependency(funcobj, typeobj->dumpId);
768 
769  /* add function's dependency on shell type, instead */
770  if (typeInfo->shellType)
771  {
772  addObjectDependency(funcobj, typeInfo->shellType->dobj.dumpId);
773 
774  /*
775  * Mark shell type (always including the definition, as we need the
776  * shell type defined to identify the function fully) as to be dumped
777  * if any such function is
778  */
779  if (funcobj->dump)
780  typeInfo->shellType->dobj.dump = funcobj->dump |
782  }
783 }
DumpableObject dobj
Definition: pg_dump.h:191
DumpComponents dump
Definition: pg_dump.h:134
struct _shellTypeInfo * shellType
Definition: pg_dump.h:183
DumpId dumpId
Definition: pg_dump.h:132
void removeObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:739
#define DUMP_COMPONENT_DEFINITION
Definition: pg_dump.h:92
void addObjectDependency(DumpableObject *dobj, DumpId refId)
Definition: common.c:712
static void repairViewRuleLoop ( DumpableObject viewobj,
DumpableObject ruleobj 
)
static

Definition at line 793 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

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

Definition at line 813 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 145 of file pg_dump_sort.c.

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

Referenced by main().

146 {
147  int startIdx,
148  endIdx;
149  void *startPtr;
150 
151  if (numObjs <= 1)
152  return;
153 
154  startIdx = findFirstEqualType(DO_TABLE_DATA, objs, numObjs);
155  if (startIdx >= 0)
156  {
157  endIdx = findFirstDifferentType(DO_TABLE_DATA, objs, numObjs, startIdx);
158  startPtr = objs + startIdx;
159  qsort(startPtr, endIdx - startIdx, sizeof(DumpableObject *),
160  DOSizeCompare);
161  }
162 
163  startIdx = findFirstEqualType(DO_INDEX, objs, numObjs);
164  if (startIdx >= 0)
165  {
166  endIdx = findFirstDifferentType(DO_INDEX, objs, numObjs, startIdx);
167  startPtr = objs + startIdx;
168  qsort(startPtr, endIdx - startIdx, sizeof(DumpableObject *),
169  DOSizeCompare);
170  }
171 }
static int findFirstEqualType(DumpableObjectType type, DumpableObject **objs, int numObjs)
Definition: pg_dump_sort.c:112
static int DOSizeCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:174
static int findFirstDifferentType(DumpableObjectType type, DumpableObject **objs, int numObjs, int start)
Definition: pg_dump_sort.c:123
#define qsort(a, b, c, d)
Definition: port.h:443
void sortDumpableObjects ( DumpableObject **  objs,
int  numObjs,
DumpId  preBoundaryId,
DumpId  postBoundaryId 
)

Definition at line 309 of file pg_dump_sort.c.

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

Referenced by main().

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

Definition at line 207 of file pg_dump_sort.c.

References DOTypeNameCompare(), and qsort.

Referenced by main().

208 {
209  if (numObjs > 1)
210  qsort((void *) objs, numObjs, sizeof(DumpableObject *),
212 }
static int DOTypeNameCompare(const void *p1, const void *p2)
Definition: pg_dump_sort.c:215
#define qsort(a, b, c, d)
Definition: port.h:443
static bool TopoSort ( DumpableObject **  objs,
int  numObjs,
DumpableObject **  ordering,
int *  nOrdering 
)
static

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

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

Variable Documentation

const int dbObjectTypePriority[]
static

Definition at line 39 of file pg_dump_sort.c.

Referenced by DOTypeNameCompare().

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

Definition at line 25 of file pg_dump_sort.c.

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

DumpId preDataBoundId
static

Definition at line 86 of file pg_dump_sort.c.

Referenced by sortDumpableObjects().