nbtsearch.c

关系型数据库 Postgresql 6.5.2

				} while (result >= 0);
			}
			break;
	}

	/* okay, current item pointer for the scan is right */
	offnum = ItemPointerGetOffsetNumber(current);
	page = BufferGetPage(buf);
	btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
	itup = &btitem->bti_itup;

	if (_bt_checkkeys(scan, itup, &keysok))
	{
		res = FormRetrieveIndexResult(current, &(itup->t_tid));

		/* remember which buffer we have pinned */
		so->btso_curbuf = buf;
	}
	else if (keysok >= so->numberOfFirstKeys)
	{
		so->btso_curbuf = buf;
		return _bt_next(scan, dir);
	}
	else if (keysok == -1 && ScanDirectionIsBackward(dir))
	{
		so->btso_curbuf = buf;
		return _bt_next(scan, dir);
	}
	else
	{
		ItemPointerSetInvalid(current);
		so->btso_curbuf = InvalidBuffer;
		_bt_relbuf(rel, buf, BT_READ);
		res = (RetrieveIndexResult) NULL;
	}

	return res;
}

/*
 *	_bt_step() -- Step one item in the requested direction in a scan on
 *				  the tree.
 *
 *		If no adjacent record exists in the requested direction, return
 *		false.	Else, return true and set the currentItemData for the
 *		scan to the right thing.
 */
bool
_bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
{
	Page		page;
	BTPageOpaque opaque;
	OffsetNumber offnum,
				maxoff;
	OffsetNumber start;
	BlockNumber blkno;
	BlockNumber obknum;
	BTScanOpaque so;
	ItemPointer current;
	Relation	rel;

	rel = scan->relation;
	current = &(scan->currentItemData);

	/*
	 * Don't use ItemPointerGetOffsetNumber or you risk to get assertion
	 * due to ability of ip_posid to be equal 0.
	 */
	offnum = current->ip_posid;
	page = BufferGetPage(*bufP);
	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
	so = (BTScanOpaque) scan->opaque;
	maxoff = PageGetMaxOffsetNumber(page);

	/* get the next tuple */
	if (ScanDirectionIsForward(dir))
	{
		if (!PageIsEmpty(page) && offnum < maxoff)
			offnum = OffsetNumberNext(offnum);
		else
		{

			/* if we're at end of scan, release the buffer and return */
			blkno = opaque->btpo_next;
			if (P_RIGHTMOST(opaque))
			{
				_bt_relbuf(rel, *bufP, BT_READ);
				ItemPointerSetInvalid(current);
				*bufP = so->btso_curbuf = InvalidBuffer;
				return false;
			}
			else
			{

				/* walk right to the next page with data */
				_bt_relbuf(rel, *bufP, BT_READ);
				for (;;)
				{
					*bufP = _bt_getbuf(rel, blkno, BT_READ);
					page = BufferGetPage(*bufP);
					opaque = (BTPageOpaque) PageGetSpecialPointer(page);
					maxoff = PageGetMaxOffsetNumber(page);
					start = P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY;

					if (!PageIsEmpty(page) && start <= maxoff)
						break;
					else
					{
						blkno = opaque->btpo_next;
						_bt_relbuf(rel, *bufP, BT_READ);
						if (blkno == P_NONE)
						{
							*bufP = so->btso_curbuf = InvalidBuffer;
							ItemPointerSetInvalid(current);
							return false;
						}
					}
				}
				offnum = start;
			}
		}
	}
	else if (ScanDirectionIsBackward(dir))
	{

		/* remember that high key is item zero on non-rightmost pages */
		start = P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY;

		if (offnum > start)
			offnum = OffsetNumberPrev(offnum);
		else
		{

			/* if we're at end of scan, release the buffer and return */
			blkno = opaque->btpo_prev;
			if (P_LEFTMOST(opaque))
			{
				_bt_relbuf(rel, *bufP, BT_READ);
				*bufP = so->btso_curbuf = InvalidBuffer;
				ItemPointerSetInvalid(current);
				return false;
			}
			else
			{

				obknum = BufferGetBlockNumber(*bufP);

				/* walk right to the next page with data */
				_bt_relbuf(rel, *bufP, BT_READ);
				for (;;)
				{
					*bufP = _bt_getbuf(rel, blkno, BT_READ);
					page = BufferGetPage(*bufP);
					opaque = (BTPageOpaque) PageGetSpecialPointer(page);
					maxoff = PageGetMaxOffsetNumber(page);

					/*
					 * If the adjacent page just split, then we may have
					 * the wrong block.  Handle this case.	Because pages
					 * only split right, we don't have to worry about this
					 * failing to terminate.
					 */

					while (opaque->btpo_next != obknum)
					{
						blkno = opaque->btpo_next;
						_bt_relbuf(rel, *bufP, BT_READ);
						*bufP = _bt_getbuf(rel, blkno, BT_READ);
						page = BufferGetPage(*bufP);
						opaque = (BTPageOpaque) PageGetSpecialPointer(page);
						maxoff = PageGetMaxOffsetNumber(page);
					}

					/* don't consider the high key */
					start = P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY;

					/* anything to look at here? */
					if (!PageIsEmpty(page) && maxoff >= start)
						break;
					else
					{
						blkno = opaque->btpo_prev;
						obknum = BufferGetBlockNumber(*bufP);
						_bt_relbuf(rel, *bufP, BT_READ);
						if (blkno == P_NONE)
						{
							*bufP = so->btso_curbuf = InvalidBuffer;
							ItemPointerSetInvalid(current);
							return false;
						}
					}
				}
				offnum = maxoff;/* XXX PageIsEmpty? */
			}
		}
	}
	blkno = BufferGetBlockNumber(*bufP);
	so->btso_curbuf = *bufP;
	ItemPointerSet(current, blkno, offnum);

	return true;
}

/*
 *	_bt_twostep() -- Move to an adjacent record in a scan on the tree,
 *					 if an adjacent record exists.
 *
 *		This is like _bt_step, except that if no adjacent record exists
 *		it restores us to where we were before trying the step.  This is
 *		only hairy when you cross page boundaries, since the page you cross
 *		from could have records inserted or deleted, or could even split.
 *		This is unlikely, but we try to handle it correctly here anyway.
 *
 *		This routine contains the only case in which our changes to Lehman
 *		and Yao's algorithm.
 *
 *		Like step, this routine leaves the scan's currentItemData in the
 *		proper state and acquires a lock and pin on *bufP.	If the twostep
 *		succeeded, we return true; otherwise, we return false.
 */
static bool
_bt_twostep(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
{
	Page		page;
	BTPageOpaque opaque;
	OffsetNumber offnum,
				maxoff;
	OffsetNumber start;
	ItemPointer current;
	ItemId		itemid;
	int			itemsz;
	BTItem		btitem;
	BTItem		svitem;
	BlockNumber blkno;

	blkno = BufferGetBlockNumber(*bufP);
	page = BufferGetPage(*bufP);
	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
	maxoff = PageGetMaxOffsetNumber(page);
	current = &(scan->currentItemData);
	offnum = ItemPointerGetOffsetNumber(current);

	start = P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY;

	/* if we're safe, just do it */
	if (ScanDirectionIsForward(dir) && offnum < maxoff)
	{							/* XXX PageIsEmpty? */
		ItemPointerSet(current, blkno, OffsetNumberNext(offnum));
		return true;
	}
	else if (ScanDirectionIsBackward(dir) && offnum > start)
	{
		ItemPointerSet(current, blkno, OffsetNumberPrev(offnum));
		return true;
	}

	/* if we've hit end of scan we don't have to do any work */
	if (ScanDirectionIsForward(dir) && P_RIGHTMOST(opaque))
		return false;
	else if (ScanDirectionIsBackward(dir) && P_LEFTMOST(opaque))
		return false;

	/*
	 * Okay, it's off the page; let _bt_step() do the hard work, and we'll
	 * try to remember where we were.  This is not guaranteed to work;
	 * this is the only place in the code where concurrency can screw us
	 * up, and it's because we want to be able to move in two directions
	 * in the scan.
	 */

	itemid = PageGetItemId(page, offnum);
	itemsz = ItemIdGetLength(itemid);
	btitem = (BTItem) PageGetItem(page, itemid);
	svitem = (BTItem) palloc(itemsz);
	memmove((char *) svitem, (char *) btitem, itemsz);

	if (_bt_step(scan, bufP, dir))
	{
		pfree(svitem);
		return true;
	}

	/* try to find our place again */
	*bufP = _bt_getbuf(scan->relation, blkno, BT_READ);
	page = BufferGetPage(*bufP);
	maxoff = PageGetMaxOffsetNumber(page);

	while (offnum <= maxoff)
	{
		itemid = PageGetItemId(page, offnum);
		btitem = (BTItem) PageGetItem(page, itemid);
		if (BTItemSame(btitem, svitem))
		{
			pfree(svitem);
			ItemPointerSet(current, blkno, offnum);
			return false;
		}
	}

	/*
	 * XXX crash and burn -- can't find our place.  We can be a little
	 * smarter -- walk to the next page to the right, for example, since
	 * that's the only direction that splits happen in.  Deletions screw
	 * us up less often since they're only done by the vacuum daemon.
	 */

	elog(ERROR, "btree synchronization error:  concurrent update botched scan");

	return false;
}

/*
 *	_bt_endpoint() -- Find the first or last key in the index.
 */
static RetrieveIndexResult
_bt_endpoint(IndexScanDesc scan, ScanDirection dir)
{
	Relation	rel;
	Buffer		buf;
	Page		page;
	BTPageOpaque opaque;
	ItemPointer current;
	OffsetNumber offnum,
				maxoff;
	OffsetNumber start = 0;
	BlockNumber blkno;
	BTItem		btitem;
	IndexTuple	itup;
	BTScanOpaque so;
	RetrieveIndexResult res;
	Size		keysok;

	rel = scan->relation;
	current = &(scan->currentItemData);
	so = (BTScanOpaque) scan->opaque;

	buf = _bt_getroot(rel, BT_READ);
	blkno = BufferGetBlockNumber(buf);
	page = BufferGetPage(buf);
	opaque = (BTPageOpaque) PageGetSpecialPointer(page);

	for (;;)
	{
		if (opaque->btpo_flags & BTP_LEAF)
			break;

		if (ScanDirectionIsForward(dir))
			offnum = P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY;
		else
			offnum = PageGetMaxOffsetNumber(page);

		btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
		itup = &(btitem->bti_itup);

		blkno = ItemPointerGetBlockNumber(&(itup->t_tid));

		_bt_relbuf(rel, buf, BT_READ);
		buf = _bt_getbuf(rel, blkno, BT_READ);
		page = BufferGetPage(buf);
		opaque = (BTPageOpaque) PageGetSpecialPointer(page);

		/*
		 * Race condition: If the child page we just stepped onto is in
		 * the process of being split, we need to make sure we're all the
		 * way at the right edge of the tree.  See the paper by Lehman and
		 * Yao.
		 */

		if (ScanDirectionIsBackward(dir) && !P_RIGHTMOST(opaque))
		{
			do
			{
				blkno = opaque->btpo_next;
				_bt_relbuf(rel, buf, BT_READ);
				buf = _bt_getbuf(rel, blkno, BT_READ);
				page = BufferGetPage(buf);
				opaque = (BTPageOpaque) PageGetSpecialPointer(page);
			} while (!P_RIGHTMOST(opaque));
		}
	}

	/* okay, we've got the {left,right}-most page in the tree */
	maxoff = PageGetMaxOffsetNumber(page);

	if (ScanDirectionIsForward(dir))
	{
		if (!P_LEFTMOST(opaque))/* non-leftmost page ? */
			elog(ERROR, "_bt_endpoint: leftmost page (%u) has not leftmost flag", blkno);
		start = P_RIGHTMOST(opaque) ? P_HIKEY : P_FIRSTKEY;

		/*
		 * I don't understand this stuff! It doesn't work for
		 * non-rightmost pages with only one element (P_HIKEY) which we
		 * have after deletion itups by vacuum (it's case of start >
		 * maxoff). Scanning in BackwardScanDirection is not
		 * understandable at all. Well - new stuff. - vadim 12/06/96
		 */
#ifdef NOT_USED
		if (PageIsEmpty(page) || start > maxoff)
		{
			ItemPointerSet(current, blkno, maxoff);
			if (!_bt_step(scan, &buf, BackwardScanDirection))
				return (RetrieveIndexResult) NULL;

			start = ItemPointerGetOffsetNumber(current);
			page = BufferGetPage(buf);
		}
#endif
		if (PageIsEmpty(page))
		{
			if (start != P_HIKEY)		/* non-rightmost page */
				elog(ERROR, "_bt_endpoint: non-rightmost page (%u) is empty", blkno);

			/*
			 * It's left- & right- most page - root page, - and it's
			 * empty...
			 */
			_bt_relbuf(rel, buf, BT_READ);
			ItemPointerSetInvalid(current);
			so->btso_curbuf = InvalidBuffer;
			return (RetrieveIndexResult) NULL;
		}
		if (start > maxoff)		/* start == 2 && maxoff == 1 */
		{
			ItemPointerSet(current, blkno, maxoff);
			if (!_bt_step(scan, &buf, ForwardScanDirection))
				return (RetrieveIndexResult) NULL;

			start = ItemPointerGetOffsetNumber(current);
			page = BufferGetPage(buf);
		}
		/* new stuff ends here */
		else
			ItemPointerSet(current, blkno, start);
	}
	else if (ScanDirectionIsBackward(dir))
	{

		/*
		 * I don't understand this stuff too! If RIGHT-most leaf page is
		 * empty why do scanning in ForwardScanDirection ??? Well - new
		 * stuff. - vadim 12/06/96
		 */
#ifdef NOT_USED
		if (PageIsEmpty(page))
		{
			ItemPointerSet(current, blkno, FirstOffsetNumber);
			if (!_bt_step(scan, &buf, ForwardScanDirection))
				return (RetrieveIndexResult) NULL;

			start = ItemPointerGetOffsetNumber(current);
			page = BufferGetPage(buf);
		}
#endif
		if (PageIsEmpty(page))
		{
			/* If it's leftmost page too - it's empty root page... */
			if (P_LEFTMOST(opaque))
			{
				_bt_relbuf(rel, buf, BT_READ);
				ItemPointerSetInvalid(current);
				so->btso_curbuf = InvalidBuffer;
				return (RetrieveIndexResult) NULL;
			}
			/* Go back ! */
			ItemPointerSet(current, blkno, FirstOffsetNumber);
			if (!_bt_step(scan, &buf, BackwardScanDirection))
				return (RetrieveIndexResult) NULL;

			start = ItemPointerGetOffsetNumber(current);
			page = BufferGetPage(buf);
		}
		/* new stuff ends here */
		else
		{
			start = PageGetMaxOffsetNumber(page);
			ItemPointerSet(current, blkno, start);
		}
	}
	else
		elog(ERROR, "Illegal scan direction %d", dir);

	btitem = (BTItem) PageGetItem(page, PageGetItemId(page, start));
	itup = &(btitem->bti_itup);

	/* see if we picked a winner */
	if (_bt_checkkeys(scan, itup, &keysok))
	{
		res = FormRetrieveIndexResult(current, &(itup->t_tid));

		/* remember which buffer we have pinned */
		so->btso_curbuf = buf;
	}
	else if (keysok >= so->numberOfFirstKeys)
	{
		so->btso_curbuf = buf;
		return _bt_next(scan, dir);
	}
	else if (keysok == -1 && ScanDirectionIsBackward(dir))
	{
		so->btso_curbuf = buf;
		return _bt_next(scan, dir);
	}
	else
	{
		ItemPointerSetInvalid(current);
		so->btso_curbuf = InvalidBuffer;
		_bt_relbuf(rel, buf, BT_READ);
		res = (RetrieveIndexResult) NULL;
	}

	return res;
}