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

References i, and val.

Referenced by TopoSort().

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

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

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

Definition at line 173 of file pg_dump_sort.c.

References DO_INDEX, DO_TABLE_DATA, and _dumpableObject::objType.

Referenced by sortDataAndIndexObjectsBySize().

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

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

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

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

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

References i.

Referenced by sortDataAndIndexObjectsBySize().

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

Definition at line 111 of file pg_dump_sort.c.

References i.

Referenced by sortDataAndIndexObjectsBySize().

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

Definition at line 676 of file pg_dump_sort.c.

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

Referenced by findDependencyLoops().

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

Definition at line 535 of file pg_dump_sort.c.

References i, and val.

Referenced by TopoSort().

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

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

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

Definition at line 918 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

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

Definition at line 926 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 842 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 895 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

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

Definition at line 903 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 861 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

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

Definition at line 878 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 761 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 792 of file pg_dump_sort.c.

References _dumpableObject::dumpId, and removeObjectDependency().

Referenced by repairDependencyLoop().

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

Definition at line 812 of file pg_dump_sort.c.

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

Referenced by repairDependencyLoop().

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

Definition at line 144 of file pg_dump_sort.c.

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

Referenced by main().

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

Definition at line 308 of file pg_dump_sort.c.

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

Referenced by main().

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

Definition at line 206 of file pg_dump_sort.c.

References DOTypeNameCompare(), and qsort.

Referenced by main().

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

Definition at line 360 of file pg_dump_sort.c.

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

Referenced by sortDumpableObjects().

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

Referenced by sortDumpableObjects().