lselect.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * lselect.c
 *	  leftist tree selection algorithm (linked priority queue--Knuth, Vol.3,
 *	  pp.150-52)
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/utils/sort/lselect.c,v 1.16.2.1 1999/08/02 05:25:17 scrappy Exp $
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"


#include "access/heapam.h"
#include "utils/lselect.h"

/*
 *		lmerge			- merges two leftist trees into one
 *
 *		Note:
 *				Enforcing the rule that pt->lt_dist >= qt->lt_dist may
 *				simplifify much of the code.  Removing recursion will not
 *				speed up code significantly.
 */
struct leftist *
lmerge(struct leftist * pt, struct leftist * qt, LeftistContext context)
{
	struct leftist *root,
			   *majorLeftist,
			   *minorLeftist;
	int			dist;

	if (tuplecmp(pt->lt_tuple, qt->lt_tuple, context))
	{
		root = pt;
		majorLeftist = qt;
	}
	else
	{
		root = qt;
		majorLeftist = pt;
	}
	if (root->lt_left == NULL)
		root->lt_left = majorLeftist;
	else
	{
		if ((minorLeftist = root->lt_right) != NULL)
			majorLeftist = lmerge(majorLeftist, minorLeftist, context);
		if ((dist = root->lt_left->lt_dist) < majorLeftist->lt_dist)
		{
			root->lt_dist = 1 + dist;
			root->lt_right = root->lt_left;
			root->lt_left = majorLeftist;
		}
		else
		{
			root->lt_dist = 1 + majorLeftist->lt_dist;
			root->lt_right = majorLeftist;
		}
	}
	return root;
}

static struct leftist *
linsert(struct leftist * root, struct leftist * new1, LeftistContext context)
{
	struct leftist *left,
			   *right;

	if (!tuplecmp(root->lt_tuple, new1->lt_tuple, context))
	{
		new1->lt_left = root;
		return new1;
	}
	left = root->lt_left;
	right = root->lt_right;
	if (right == NULL)
	{
		if (left == NULL)
			root->lt_left = new1;
		else
		{
			root->lt_right = new1;
			root->lt_dist = 2;
		}
		return root;
	}
	right = linsert(right, new1, context);
	if (right->lt_dist < left->lt_dist)
	{
		root->lt_dist = 1 + left->lt_dist;
		root->lt_left = right;
		root->lt_right = left;
	}
	else
	{
		root->lt_dist = 1 + right->lt_dist;
		root->lt_right = right;
	}
	return root;
}

/*
 *		gettuple		- returns tuple at top of tree (Tuples)
 *
 *		Returns:
 *				tuple at top of tree, NULL if failed ALLOC()
 *				*devnum is set to the devnum of tuple returned
 *				*treep is set to the new tree
 *
 *		Note:
 *				*treep must not be NULL
 *				NULL is currently never returned BUG
 */
HeapTuple
gettuple(struct leftist ** treep,
		 short *devnum,			/* device from which tuple came */
		 LeftistContext context)
{
	struct leftist *tp;
	HeapTuple	tup;

	tp = *treep;
	tup = tp->lt_tuple;
	*devnum = tp->lt_devnum;
	if (tp->lt_dist == 1)		/* lt_left == NULL */
		*treep = tp->lt_left;
	else
		*treep = lmerge(tp->lt_left, tp->lt_right, context);

	pfree(tp);
	return tup;
}

/*
 *		puttuple		- inserts new tuple into tree
 *
 *		Returns:
 *				NULL iff failed ALLOC()
 *
 *		Note:
 *				Currently never returns NULL BUG
 */
void
puttuple(struct leftist ** treep,
		 HeapTuple newtuple,
		 short devnum,
		 LeftistContext context)
{
	struct leftist *new1;
	struct leftist *tp;

	new1 = (struct leftist *) palloc((unsigned) sizeof(struct leftist));
	new1->lt_dist = 1;
	new1->lt_devnum = devnum;
	new1->lt_tuple = newtuple;
	new1->lt_left = NULL;
	new1->lt_right = NULL;
	if ((tp = *treep) == NULL)
		*treep = new1;
	else
		*treep = linsert(tp, new1, context);
	return;
}


/*
 *		tuplecmp		- Compares two tuples with respect CmpList
 *
 *		Returns:
 *				1 if left < right ;0 otherwise
 *		Assumtions:
 */
int
tuplecmp(HeapTuple ltup, HeapTuple rtup, LeftistContext context)
{
	int			nkey;
	int			result = 0;

	if (ltup == (HeapTuple) NULL)
		return 0;
	if (rtup == (HeapTuple) NULL)
		return 1;
	for (nkey = 0; nkey < context->nKeys; nkey++)
	{
		ScanKey		thisKey = & context->scanKeys[nkey];
		Datum		lattr,
					rattr;
		bool		lisnull,
					risnull;

		lattr = heap_getattr(ltup, thisKey->sk_attno,
							 context->tupDesc, &lisnull);
		rattr = heap_getattr(rtup, thisKey->sk_attno,
							 context->tupDesc, &risnull);
		if (lisnull)
		{
			if (risnull)
				continue;		/* treat two nulls as equal */
			return 0;			/* else, a null sorts after all else */
		}
		if (risnull)
			return 1;
		if (thisKey->sk_flags & SK_COMMUTE)
		{
			if (!(result =
				  (long) (*fmgr_faddr(&thisKey->sk_func)) (rattr, lattr)))
				result =
					-(long) (*fmgr_faddr(&thisKey->sk_func)) (lattr, rattr);
		}
		else
		{
			if (!(result =
				  (long) (*fmgr_faddr(&thisKey->sk_func)) (lattr, rattr)))
				result =
					-(long) (*fmgr_faddr(&thisKey->sk_func)) (rattr, lattr);
		}
		if (result)
			break;
	}
	return result == 1;
}

#ifdef	EBUG
void
checktree(struct leftist * tree, LeftistContext context)
{
	int			lnodes;
	int			rnodes;

	if (tree == NULL)
	{
		puts("Null tree.");
		return;
	}
	lnodes = checktreer(tree->lt_left, 1, context);
	rnodes = checktreer(tree->lt_right, 1, context);
	if (lnodes < 0)
	{
		lnodes = -lnodes;
		puts("0:\tBad left side.");
	}
	if (rnodes < 0)
	{
		rnodes = -rnodes;
		puts("0:\tBad right side.");
	}
	if (lnodes == 0)
	{
		if (rnodes != 0)
			puts("0:\tLeft and right reversed.");
		if (tree->lt_dist != 1)
			puts("0:\tDistance incorrect.");
	}
	else if (rnodes == 0)
	{
		if (tree->lt_dist != 1)
			puts("0:\tDistance incorrect.");
	}
	else if (tree->lt_left->lt_dist < tree->lt_right->lt_dist)
	{
		puts("0:\tLeft and right reversed.");
		if (tree->lt_dist != 1 + tree->lt_left->lt_dist)
			puts("0:\tDistance incorrect.");
	}
	else if (tree->lt_dist != 1 + tree->lt_right->lt_dist)
		puts("0:\tDistance incorrect.");
	if (lnodes > 0)
		if (tuplecmp(tree->lt_left->lt_tuple, tree->lt_tuple, context))
			printf("%d:\tLeft child < parent.\n");
	if (rnodes > 0)
		if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple, context))
			printf("%d:\tRight child < parent.\n");
	printf("Tree has %d nodes\n", 1 + lnodes + rnodes);
}

int
checktreer(struct leftist * tree, int level, LeftistContext context)
{
	int			lnodes,
				rnodes;
	int			error = 0;

	if (tree == NULL)
		return 0;
	lnodes = checktreer(tree->lt_left, level + 1, context);
	rnodes = checktreer(tree->lt_right, level + 1, context);
	if (lnodes < 0)
	{
		error = 1;
		lnodes = -lnodes;
		printf("%d:\tBad left side.\n", level);
	}
	if (rnodes < 0)
	{
		error = 1;
		rnodes = -rnodes;
		printf("%d:\tBad right side.\n", level);
	}
	if (lnodes == 0)
	{
		if (rnodes != 0)
		{
			error = 1;
			printf("%d:\tLeft and right reversed.\n", level);
		}
		if (tree->lt_dist != 1)
		{
			error = 1;
			printf("%d:\tDistance incorrect.\n", level);
		}
	}
	else if (rnodes == 0)
	{
		if (tree->lt_dist != 1)
		{
			error = 1;
			printf("%d:\tDistance incorrect.\n", level);
		}
	}
	else if (tree->lt_left->lt_dist < tree->lt_right->lt_dist)
	{
		error = 1;
		printf("%d:\tLeft and right reversed.\n", level);
		if (tree->lt_dist != 1 + tree->lt_left->lt_dist)
			printf("%d:\tDistance incorrect.\n", level);
	}
	else if (tree->lt_dist != 1 + tree->lt_right->lt_dist)
	{
		error = 1;
		printf("%d:\tDistance incorrect.\n", level);
	}
	if (lnodes > 0)
		if (tuplecmp(tree->lt_left->lt_tuple, tree->lt_tuple, context))
		{
			error = 1;
			printf("%d:\tLeft child < parent.\n");
		}
	if (rnodes > 0)
		if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple, context))
		{
			error = 1;
			printf("%d:\tRight child < parent.\n");
		}
	if (error)
		return -1 + -lnodes + -rnodes;
	return 1 + lnodes + rnodes;
}

#endif