pg_dump_sort.c

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

		{
			if (beforeConstraints[j] != 0)
				ordering[k++] = objs[idMap[j]];
		}
		*nOrdering = k;
	}

	/* Done */
	free(pendingHeap);
	free(beforeConstraints);
	free(idMap);

	return (i == 0);
}

/*
 * Add an item to a heap (priority queue)
 *
 * heapLength is the current heap size; caller is responsible for increasing
 * its value after the call.  There must be sufficient storage at *heap.
 */
static void
addHeapElement(int val, int *heap, int heapLength)
{
	int			j;

	/*
	 * Sift-up the new entry, per Knuth 5.2.3 exercise 16. Note that Knuth is
	 * using 1-based array indexes, not 0-based.
	 */
	j = heapLength;
	while (j > 0)
	{
		int			i = (j - 1) >> 1;

		if (val <= heap[i])
			break;
		heap[j] = heap[i];
		j = i;
	}
	heap[j] = val;
}

/*
 * Remove the largest item present in a heap (priority queue)
 *
 * heapLength is the current heap size; caller is responsible for decreasing
 * its value after the call.
 *
 * We remove and return heap[0], which is always the largest element of
 * the heap, and then "sift up" to maintain the heap invariant.
 */
static int
removeHeapElement(int *heap, int heapLength)
{
	int			result = heap[0];
	int			val;
	int			i;

	if (--heapLength <= 0)
		return result;
	val = heap[heapLength];		/* value that must be reinserted */
	i = 0;						/* i is where the "hole" is */
	for (;;)
	{
		int			j = 2 * i + 1;

		if (j >= heapLength)
			break;
		if (j + 1 < heapLength &&
			heap[j] < heap[j + 1])
			j++;
		if (val >= heap[j])
			break;
		heap[i] = heap[j];
		i = j;
	}
	heap[i] = val;
	return result;
}

/*
 * findDependencyLoops - identify loops in TopoSort's failure output,
 *		and pass each such loop to repairDependencyLoop() for action
 *
 * In general there may be many loops in the set of objects returned by
 * TopoSort; for speed we should try to repair as many loops as we can
 * before trying TopoSort again.  We can safely repair loops that are
 * disjoint (have no members in common); if we find overlapping loops
 * then we repair only the first one found, because the action taken to
 * repair the first might have repaired the other as well.	(If not,
 * we'll fix it on the next go-round.)
 *
 * objs[] lists the objects TopoSort couldn't sort
 * nObjs is the number of such objects
 * totObjs is the total number of objects in the universe
 */
static void
findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
{
	/*
	 * We use a workspace array, the initial part of which stores objects
	 * already processed, and the rest of which is used as temporary space to
	 * try to build a loop in.	This is convenient because we do not care
	 * about loops involving already-processed objects (see notes above); we
	 * can easily reject such loops in findLoop() because of this
	 * representation.	After we identify and process a loop, we can add it to
	 * the initial part of the workspace just by moving the boundary pointer.
	 *
	 * When we determine that an object is not part of any interesting loop,
	 * we also add it to the initial part of the workspace.  This is not
	 * necessary for correctness, but saves later invocations of findLoop()
	 * from uselessly chasing references to such an object.
	 *
	 * We make the workspace large enough to hold all objects in the original
	 * universe.  This is probably overkill, but it's provably enough space...
	 */
	DumpableObject **workspace;
	int			initiallen;
	bool		fixedloop;
	int			i;

	workspace = (DumpableObject **) malloc(totObjs * sizeof(DumpableObject *));
	if (workspace == NULL)
		exit_horribly(NULL, modulename, "out of memory\n");
	initiallen = 0;
	fixedloop = false;

	for (i = 0; i < nObjs; i++)
	{
		DumpableObject *obj = objs[i];
		int			newlen;

		workspace[initiallen] = NULL;	/* see test below */

		if (findLoop(obj, obj->dumpId, workspace, initiallen, &newlen))
		{
			/* Found a loop of length newlen - initiallen */
			repairDependencyLoop(&workspace[initiallen], newlen - initiallen);
			/* Add loop members to workspace */
			initiallen = newlen;
			fixedloop = true;
		}
		else
		{
			/*
			 * Didn't find a loop, but add this object to workspace anyway,
			 * unless it's already present.  We piggyback on the test that
			 * findLoop() already did: it won't have tentatively added obj to
			 * workspace if it's already present.
			 */
			if (workspace[initiallen] == obj)
				initiallen++;
		}
	}

	/* We'd better have fixed at least one loop */
	if (!fixedloop)
		exit_horribly(NULL, modulename, "could not identify dependency loop\n");

	free(workspace);
}

/*
 * Recursively search for a circular dependency loop that doesn't include
 * any existing workspace members.
 *
 *	obj: object we are examining now
 *	startPoint: dumpId of starting object for the hoped-for circular loop
 *	workspace[]: work array for previously processed and current objects
 *	depth: number of valid entries in workspace[] at call
 *	newDepth: if successful, set to new number of workspace[] entries
 *
 * On success, *newDepth is set and workspace[] entries depth..*newDepth-1
 * are filled with pointers to the members of the loop.
 *
 * Note: it is possible that the given starting object is a member of more
 * than one cycle; if so, we will find an arbitrary one of the cycles.
 */
static bool
findLoop(DumpableObject *obj,
		 DumpId startPoint,
		 DumpableObject **workspace,
		 int depth,
		 int *newDepth)
{
	int			i;

	/*
	 * Reject if obj is already present in workspace.  This test serves three
	 * purposes: it prevents us from finding loops that overlap
	 * previously-processed loops, it prevents us from going into infinite
	 * recursion if we are given a startPoint object that links to a cycle
	 * it's not a member of, and it guarantees that we can't overflow the
	 * allocated size of workspace[].
	 */
	for (i = 0; i < depth; i++)
	{
		if (workspace[i] == obj)
			return false;
	}

	/*
	 * Okay, tentatively add obj to workspace
	 */
	workspace[depth++] = obj;

	/*
	 * See if we've found a loop back to the desired startPoint; if so, done
	 */
	for (i = 0; i < obj->nDeps; i++)
	{
		if (obj->dependencies[i] == startPoint)
		{
			*newDepth = depth;
			return true;
		}
	}

	/*
	 * Recurse down each outgoing branch
	 */
	for (i = 0; i < obj->nDeps; i++)
	{
		DumpableObject *nextobj = findObjectByDumpId(obj->dependencies[i]);

		if (!nextobj)
			continue;			/* ignore dependencies on undumped objects */
		if (findLoop(nextobj,
					 startPoint,
					 workspace,
					 depth,
					 newDepth))
			return true;
	}

	return false;
}

/*
 * A user-defined datatype will have a dependency loop with each of its
 * I/O functions (since those have the datatype as input or output).
 * We want the dump ordering to be the input function, then any other
 * I/O functions, then the datatype.  So we break the circularity in
 * favor of the functions, and add a dependency from any non-input
 * function to the input function.
 */
static void
repairTypeFuncLoop(DumpableObject *typeobj, DumpableObject *funcobj)
{
	TypeInfo   *typeInfo = (TypeInfo *) typeobj;
	FuncInfo   *inputFuncInfo;

	/* remove function's dependency on type */
	removeObjectDependency(funcobj, typeobj->dumpId);

	/* if this isn't the input function, make it depend on same */
	if (funcobj->catId.oid == typeInfo->typinput)
		return;					/* it is the input function */
	inputFuncInfo = findFuncByOid(typeInfo->typinput);
	if (inputFuncInfo == NULL)
		return;
	addObjectDependency(funcobj, inputFuncInfo->dobj.dumpId);

	/*
	 * Make sure the input function's dependency on type gets removed too; if
	 * it hasn't been done yet, we'd end up with loops involving the type and
	 * two or more functions, which repairDependencyLoop() is not smart enough
	 * to handle.
	 */
	removeObjectDependency(&inputFuncInfo->dobj, typeobj->dumpId);
}

/*
 * Because we force a view to depend on its ON SELECT rule, while there
 * will be an implicit dependency in the other direction, we need to break
 * the loop.  If there are no other objects in the loop then we can remove
 * the implicit dependency and leave the ON SELECT rule non-separate.
 */
static void
repairViewRuleLoop(DumpableObject *viewobj,
				   DumpableObject *ruleobj)
{
	/* remove rule's dependency on view */
	removeObjectDependency(ruleobj, viewobj->dumpId);
}

/*
 * However, if there are other objects in the loop, we must break the loop
 * by making the ON SELECT rule a separately-dumped object.
 *
 * Because findLoop() finds shorter cycles before longer ones, it's likely
 * that we will have previously fired repairViewRuleLoop() and removed the
 * rule's dependency on the view.  Put it back to ensure the rule won't be
 * emitted before the view...
 */
static void
repairViewRuleMultiLoop(DumpableObject *viewobj,
						DumpableObject *ruleobj)
{
	/* remove view's dependency on rule */
	removeObjectDependency(viewobj, ruleobj->dumpId);
	/* pretend view is a plain table and dump it that way */
	((TableInfo *) viewobj)->relkind = 'r';		/* RELKIND_RELATION */
	/* mark rule as needing its own dump */
	((RuleInfo *) ruleobj)->separate = true;
	/* put back rule's dependency on view */
	addObjectDependency(ruleobj, viewobj->dumpId);
}

/*
 * Because we make tables depend on their CHECK constraints, while there
 * will be an automatic dependency in the other direction, we need to break
 * the loop.  If there are no other objects in the loop then we can remove
 * the automatic dependency and leave the CHECK constraint non-separate.
 */
static void
repairTableConstraintLoop(DumpableObject *tableobj,
						  DumpableObject *constraintobj)
{
	/* remove constraint's dependency on table */
	removeObjectDependency(constraintobj, tableobj->dumpId);
}

/*
 * However, if there are other objects in the loop, we must break the loop
 * by making the CHECK constraint a separately-dumped object.
 *
 * Because findLoop() finds shorter cycles before longer ones, it's likely
 * that we will have previously fired repairTableConstraintLoop() and
 * removed the constraint's dependency on the table.  Put it back to ensure
 * the constraint won't be emitted before the table...
 */
static void
repairTableConstraintMultiLoop(DumpableObject *tableobj,
							   DumpableObject *constraintobj)
{
	/* remove table's dependency on constraint */
	removeObjectDependency(tableobj, constraintobj->dumpId);
	/* mark constraint as needing its own dump */
	((ConstraintInfo *) constraintobj)->separate = true;
	/* put back constraint's dependency on table */
	addObjectDependency(constraintobj, tableobj->dumpId);
}

/*
 * Attribute defaults behave exactly the same as CHECK constraints...
 */
static void
repairTableAttrDefLoop(DumpableObject *tableobj,
					   DumpableObject *attrdefobj)
{
	/* remove attrdef's dependency on table */
	removeObjectDependency(attrdefobj, tableobj->dumpId);
}

static void
repairTableAttrDefMultiLoop(DumpableObject *tableobj,
							DumpableObject *attrdefobj)
{
	/* remove table's dependency on attrdef */
	removeObjectDependency(tableobj, attrdefobj->dumpId);