pg_dump_sort.c

PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统

/*-------------------------------------------------------------------------
 *
 * pg_dump_sort.c
 *	  Sort the items of a dump into a safe order for dumping
 *
 *
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/bin/pg_dump/pg_dump_sort.c,v 1.11.2.1 2005/11/22 18:23:27 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "pg_dump.h"
#include "pg_backup_archiver.h"


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

/*
 * Sort priority for object types when dumping a pre-7.3 database.
 * Objects are sorted by priority levels, and within an equal priority level
 * by OID.	(This is a relatively crude hack to provide semi-reasonable
 * behavior for old databases without full dependency info.)
 */
static const int oldObjectTypePriority[] =
{
	1,							/* DO_NAMESPACE */
	2,							/* DO_TYPE */
	2,							/* DO_FUNC */
	3,							/* DO_AGG */
	3,							/* DO_OPERATOR */
	4,							/* DO_OPCLASS */
	5,							/* DO_CONVERSION */
	6,							/* DO_TABLE */
	8,							/* DO_ATTRDEF */
	13,							/* DO_INDEX */
	14,							/* DO_RULE */
	15,							/* DO_TRIGGER */
	12,							/* DO_CONSTRAINT */
	16,							/* DO_FK_CONSTRAINT */
	2,							/* DO_PROCLANG */
	2,							/* DO_CAST */
	9,							/* DO_TABLE_DATA */
	7,							/* DO_TABLE_TYPE */
	10,							/* DO_BLOBS */
	11							/* DO_BLOB_COMMENTS */
};

/*
 * Sort priority for object types when dumping newer databases.
 * Objects are sorted by type, and within a type by name.
 */
static const int newObjectTypePriority[] =
{
	1,							/* DO_NAMESPACE */
	3,							/* DO_TYPE */
	4,							/* DO_FUNC */
	5,							/* DO_AGG */
	6,							/* DO_OPERATOR */
	7,							/* DO_OPCLASS */
	9,							/* DO_CONVERSION */
	10,							/* DO_TABLE */
	12,							/* DO_ATTRDEF */
	17,							/* DO_INDEX */
	18,							/* DO_RULE */
	19,							/* DO_TRIGGER */
	16,							/* DO_CONSTRAINT */
	20,							/* DO_FK_CONSTRAINT */
	2,							/* DO_PROCLANG */
	8,							/* DO_CAST */
	13,							/* DO_TABLE_DATA */
	11,							/* DO_TABLE_TYPE */
	14,							/* DO_BLOBS */
	15							/* DO_BLOB_COMMENTS */
};


static int	DOTypeNameCompare(const void *p1, const void *p2);
static int	DOTypeOidCompare(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 bool findLoop(DumpableObject *obj,
		 DumpId startPoint,
		 DumpableObject **workspace,
		 int depth,
		 int *newDepth);
static void repairDependencyLoop(DumpableObject **loop,
					 int nLoop);
static void describeDumpableObject(DumpableObject *obj,
					   char *buf, int bufsize);


/*
 * Sort the given objects into a type/name-based ordering
 *
 * Normally this is just the starting point for the dependency-based
 * ordering.
 */
void
sortDumpableObjectsByTypeName(DumpableObject **objs, int numObjs)
{
	if (numObjs > 1)
		qsort((void *) objs, numObjs, sizeof(DumpableObject *),
			  DOTypeNameCompare);
}

static int
DOTypeNameCompare(const void *p1, const void *p2)
{
	DumpableObject *obj1 = *(DumpableObject **) p1;
	DumpableObject *obj2 = *(DumpableObject **) p2;
	int			cmpval;

	/* Sort by type */
	cmpval = newObjectTypePriority[obj1->objType] -
		newObjectTypePriority[obj2->objType];

	if (cmpval != 0)
		return cmpval;

	/*
	 * Sort by namespace.  Note that all objects of the same type should
	 * either have or not have a namespace link, so we needn't be fancy about
	 * cases where one link is null and the other not.
	 */
	if (obj1->namespace && obj2->namespace)
	{
		cmpval = strcmp(obj1->namespace->dobj.name,
						obj2->namespace->dobj.name);
		if (cmpval != 0)
			return cmpval;
	}

	/* Sort by name */
	cmpval = strcmp(obj1->name, obj2->name);
	if (cmpval != 0)
		return cmpval;

	/* Probably shouldn't get here, but if we do, sort by OID */
	return oidcmp(obj1->catId.oid, obj2->catId.oid);
}


/*
 * Sort the given objects into a type/OID-based ordering
 *
 * This is used with pre-7.3 source databases as a crude substitute for the
 * lack of dependency information.
 */
void
sortDumpableObjectsByTypeOid(DumpableObject **objs, int numObjs)
{
	if (numObjs > 1)
		qsort((void *) objs, numObjs, sizeof(DumpableObject *),
			  DOTypeOidCompare);
}

static int
DOTypeOidCompare(const void *p1, const void *p2)
{
	DumpableObject *obj1 = *(DumpableObject **) p1;
	DumpableObject *obj2 = *(DumpableObject **) p2;
	int			cmpval;

	cmpval = oldObjectTypePriority[obj1->objType] -
		oldObjectTypePriority[obj2->objType];

	if (cmpval != 0)
		return cmpval;

	return oidcmp(obj1->catId.oid, obj2->catId.oid);
}


/*
 * Sort the given objects into a safe dump order using dependency
 * information (to the extent we have it available).
 */
void
sortDumpableObjects(DumpableObject **objs, int numObjs)
{
	DumpableObject **ordering;
	int			nOrdering;

	if (numObjs <= 0)
		return;

	ordering = (DumpableObject **) malloc(numObjs * sizeof(DumpableObject *));
	if (ordering == NULL)
		exit_horribly(NULL, modulename, "out of memory\n");

	while (!TopoSort(objs, numObjs, ordering, &nOrdering))
		findDependencyLoops(ordering, nOrdering, numObjs);

	memcpy(objs, ordering, numObjs * sizeof(DumpableObject *));

	free(ordering);
}

/*
 * TopoSort -- topological sort of a dump list
 *
 * Generate a re-ordering of the dump list that satisfies all the dependency
 * constraints shown in the dump list.	(Each such constraint is a fact of a
 * partial ordering.)  Minimize rearrangement of the list not needed to
 * achieve the partial ordering.
 *
 * The input is the list of numObjs objects in objs[].	This list is not
 * modified.
 *
 * Returns TRUE if able to build an ordering that satisfies all the
 * constraints, FALSE if not (there are contradictory constraints).
 *
 * On success (TRUE result), ordering[] is filled with a sorted array of
 * DumpableObject pointers, of length equal to the input list length.
 *
 * On failure (FALSE result), ordering[] is filled with an unsorted array of
 * DumpableObject pointers of length *nOrdering, listing the objects that
 * prevented the sort from being completed.  In general, these objects either
 * participate directly in a dependency cycle, or are depended on by objects
 * that are in a cycle.  (The latter objects are not actually problematic,
 * but it takes further analysis to identify which are which.)
 *
 * The caller is responsible for allocating sufficient space at *ordering.
 */
static bool
TopoSort(DumpableObject **objs,
		 int numObjs,
		 DumpableObject **ordering,		/* output argument */
		 int *nOrdering)		/* output argument */
{
	DumpId		maxDumpId = getMaxDumpId();
	int		   *pendingHeap;
	int		   *beforeConstraints;
	int		   *idMap;
	DumpableObject *obj;
	int			heapLength;
	int			i,
				j,
				k;

	/*
	 * This is basically the same algorithm shown for topological sorting in
	 * Knuth's Volume 1.  However, we would like to minimize unnecessary
	 * rearrangement of the input ordering; that is, when we have a choice of
	 * which item to output next, we always want to take the one highest in
	 * the original list.  Therefore, instead of maintaining an unordered
	 * linked list of items-ready-to-output as Knuth does, we maintain a heap
	 * of their item numbers, which we can use as a priority queue.  This
	 * turns the algorithm from O(N) to O(N log N) because each insertion or
	 * removal of a heap item takes O(log N) time.	However, that's still
	 * plenty fast enough for this application.
	 */

	*nOrdering = numObjs;		/* for success return */

	/* Eliminate the null case */
	if (numObjs <= 0)
		return true;

	/* Create workspace for the above-described heap */
	pendingHeap = (int *) malloc(numObjs * sizeof(int));
	if (pendingHeap == NULL)
		exit_horribly(NULL, modulename, "out of memory\n");

	/*
	 * Scan the constraints, and for each item in the input, generate a count
	 * of the number of constraints that say it must be before something else.
	 * The count for the item with dumpId j is stored in beforeConstraints[j].
	 * We also make a map showing the input-order index of the item with
	 * dumpId j.
	 */
	beforeConstraints = (int *) malloc((maxDumpId + 1) * sizeof(int));
	if (beforeConstraints == NULL)
		exit_horribly(NULL, modulename, "out of memory\n");
	memset(beforeConstraints, 0, (maxDumpId + 1) * sizeof(int));
	idMap = (int *) malloc((maxDumpId + 1) * sizeof(int));
	if (idMap == NULL)
		exit_horribly(NULL, modulename, "out of memory\n");
	for (i = 0; i < numObjs; i++)
	{
		obj = objs[i];
		j = obj->dumpId;
		if (j <= 0 || j > maxDumpId)
			exit_horribly(NULL, modulename, "invalid dumpId %d\n", j);
		idMap[j] = i;
		for (j = 0; j < obj->nDeps; j++)
		{
			k = obj->dependencies[j];
			if (k <= 0 || k > maxDumpId)
				exit_horribly(NULL, modulename, "invalid dependency %d\n", k);
			beforeConstraints[k]++;
		}
	}

	/*
	 * Now initialize the heap of items-ready-to-output by filling it with the
	 * indexes of items that already have beforeConstraints[id] == 0.
	 *
	 * The essential property of a heap is heap[(j-1)/2] >= heap[j] for each j
	 * in the range 1..heapLength-1 (note we are using 0-based subscripts
	 * here, while the discussion in Knuth assumes 1-based subscripts). So, if
	 * we simply enter the indexes into pendingHeap[] in decreasing order, we
	 * a-fortiori have the heap invariant satisfied at completion of this
	 * loop, and don't need to do any sift-up comparisons.
	 */
	heapLength = 0;
	for (i = numObjs; --i >= 0;)
	{
		if (beforeConstraints[objs[i]->dumpId] == 0)
			pendingHeap[heapLength++] = i;
	}

	/*--------------------
	 * Now emit objects, working backwards in the output list.	At each step,
	 * we use the priority heap to select the last item that has no remaining
	 * before-constraints.	We remove that item from the heap, output it to
	 * ordering[], and decrease the beforeConstraints count of each of the
	 * items it was constrained against.  Whenever an item's beforeConstraints
	 * count is thereby decreased to zero, we insert it into the priority heap
	 * to show that it is a candidate to output.  We are done when the heap
	 * becomes empty; if we have output every element then we succeeded,
	 * otherwise we failed.
	 * i = number of ordering[] entries left to output
	 * j = objs[] index of item we are outputting
	 * k = temp for scanning constraint list for item j
	 *--------------------
	 */
	i = numObjs;
	while (heapLength > 0)
	{
		/* Select object to output by removing largest heap member */
		j = removeHeapElement(pendingHeap, heapLength--);
		obj = objs[j];
		/* Output candidate to ordering[] */
		ordering[--i] = obj;
		/* Update beforeConstraints counts of its predecessors */
		for (k = 0; k < obj->nDeps; k++)
		{
			int			id = obj->dependencies[k];

			if ((--beforeConstraints[id]) == 0)
				addHeapElement(idMap[id], pendingHeap, heapLength++);
		}
	}

	/*
	 * If we failed, report the objects that couldn't be output; these are the
	 * ones with beforeConstraints[] still nonzero.
	 */
	if (i != 0)
	{
		k = 0;
		for (j = 1; j <= maxDumpId; j++)