nbtinsert.c

关系型数据库 Postgresql 6.5.2

	Page		page;
	ItemId		hikey;
	BTPageOpaque opaque;
	BTItem		chkitem;
	OffsetNumber offnum,
				maxoff;
	bool		found;

	page = BufferGetPage(buf);

	/* no right neighbor? */
	opaque = (BTPageOpaque) PageGetSpecialPointer(page);
	if (P_RIGHTMOST(opaque))
		return true;

	/*
	 * this is a non-rightmost page, so it must have a high key item.
	 *
	 * If the scan key is < the high key (the min key on the next page), then
	 * it for sure belongs here.
	 */
	hikey = PageGetItemId(page, P_HIKEY);
	if (_bt_skeycmp(rel, keysz, scankey, page, hikey, BTLessStrategyNumber))
		return true;

	/*
	 * If the scan key is > the high key, then it for sure doesn't belong
	 * here.
	 */

	if (_bt_skeycmp(rel, keysz, scankey, page, hikey, BTGreaterStrategyNumber))
		return false;

	/*
	 * If we have no adjacency information, and the item is equal to the
	 * high key on the page (by here it is), then the item does not belong
	 * on this page.
	 *
	 * Now it's not true in all cases.		- vadim 06/10/97
	 */

	if (afteritem == (BTItem) NULL)
	{
		if (opaque->btpo_flags & BTP_LEAF)
			return false;
		if (opaque->btpo_flags & BTP_CHAIN)
			return true;
		if (_bt_skeycmp(rel, keysz, scankey, page,
						PageGetItemId(page, P_FIRSTKEY),
						BTEqualStrategyNumber))
			return true;
		return false;
	}

	/* damn, have to work for it.  i hate that. */
	maxoff = PageGetMaxOffsetNumber(page);

	/*
	 * Search the entire page for the afteroid.  We need to do this,
	 * rather than doing a binary search and starting from there, because
	 * if the key we're searching for is the leftmost key in the tree at
	 * this level, then a binary search will do the wrong thing.  Splits
	 * are pretty infrequent, so the cost isn't as bad as it could be.
	 */

	found = false;
	for (offnum = P_FIRSTKEY;
		 offnum <= maxoff;
		 offnum = OffsetNumberNext(offnum))
	{
		chkitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));

		if (BTItemSame(chkitem, afteritem))
		{
			found = true;
			break;
		}
	}

	return found;
}

/*
 *		_bt_itemcmp() -- compare item1 to item2 using a requested
 *						 strategy (<, <=, =, >=, >)
 *
 */
bool
_bt_itemcmp(Relation rel,
			Size keysz,
			BTItem item1,
			BTItem item2,
			StrategyNumber strat)
{
	TupleDesc	tupDes;
	IndexTuple	indexTuple1,
				indexTuple2;
	Datum		attrDatum1,
				attrDatum2;
	int			i;
	bool		isFirstNull,
				isSecondNull;
	bool		compare;
	bool		useEqual = false;

	if (strat == BTLessEqualStrategyNumber)
	{
		useEqual = true;
		strat = BTLessStrategyNumber;
	}
	else if (strat == BTGreaterEqualStrategyNumber)
	{
		useEqual = true;
		strat = BTGreaterStrategyNumber;
	}

	tupDes = RelationGetDescr(rel);
	indexTuple1 = &(item1->bti_itup);
	indexTuple2 = &(item2->bti_itup);

	for (i = 1; i <= keysz; i++)
	{
		attrDatum1 = index_getattr(indexTuple1, i, tupDes, &isFirstNull);
		attrDatum2 = index_getattr(indexTuple2, i, tupDes, &isSecondNull);

		/* see comments about NULLs handling in btbuild */
		if (isFirstNull)		/* attr in item1 is NULL */
		{
			if (isSecondNull)	/* attr in item2 is NULL too */
				compare = (strat == BTEqualStrategyNumber) ? true : false;
			else
				compare = (strat == BTGreaterStrategyNumber) ? true : false;
		}
		else if (isSecondNull)	/* attr in item1 is NOT_NULL and */
		{						/* and attr in item2 is NULL */
			compare = (strat == BTLessStrategyNumber) ? true : false;
		}
		else
			compare = _bt_invokestrat(rel, i, strat, attrDatum1, attrDatum2);

		if (compare)			/* true for one of ">, <, =" */
		{
			if (strat != BTEqualStrategyNumber)
				return true;
		}
		else
/* false for one of ">, <, =" */
		{
			if (strat == BTEqualStrategyNumber)
				return false;

			/*
			 * if original strat was "<=, >=" OR "<, >" but some
			 * attribute(s) left - need to test for Equality
			 */
			if (useEqual || i < keysz)
			{
				if (isFirstNull || isSecondNull)
					compare = (isFirstNull && isSecondNull) ? true : false;
				else
					compare = _bt_invokestrat(rel, i, BTEqualStrategyNumber,
											  attrDatum1, attrDatum2);
				if (compare)	/* item1' and item2' attributes are equal */
					continue;	/* - try to compare next attributes */
			}
			return false;
		}
	}
	return true;
}

/*
 *		_bt_updateitem() -- updates the key of the item identified by the
 *							oid with the key of newItem (done in place if
 *							possible)
 *
 */
static void
_bt_updateitem(Relation rel,
			   Size keysz,
			   Buffer buf,
			   BTItem oldItem,
			   BTItem newItem)
{
	Page		page;
	OffsetNumber maxoff;
	OffsetNumber i;
	ItemPointerData itemPtrData;
	BTItem		item;
	IndexTuple	oldIndexTuple,
				newIndexTuple;
	int			first;

	page = BufferGetPage(buf);
	maxoff = PageGetMaxOffsetNumber(page);

	/* locate item on the page */
	first = P_RIGHTMOST((BTPageOpaque) PageGetSpecialPointer(page))
		? P_HIKEY : P_FIRSTKEY;
	i = first;
	do
	{
		item = (BTItem) PageGetItem(page, PageGetItemId(page, i));
		i = OffsetNumberNext(i);
	} while (i <= maxoff && !BTItemSame(item, oldItem));

	/* this should never happen (in theory) */
	if (!BTItemSame(item, oldItem))
		elog(FATAL, "_bt_getstackbuf was lying!!");

	/*
	 * It's  defined by caller (_bt_insertonpg)
	 */

	/*
	 * if(IndexTupleDSize(newItem->bti_itup) >
	 * IndexTupleDSize(item->bti_itup)) { elog(NOTICE, "trying to
	 * overwrite a smaller value with a bigger one in _bt_updateitem");
	 * elog(ERROR, "this is not good."); }
	 */

	oldIndexTuple = &(item->bti_itup);
	newIndexTuple = &(newItem->bti_itup);

	/* keep the original item pointer */
	ItemPointerCopy(&(oldIndexTuple->t_tid), &itemPtrData);
	CopyIndexTuple(newIndexTuple, &oldIndexTuple);
	ItemPointerCopy(&itemPtrData, &(oldIndexTuple->t_tid));

}

/*
 * _bt_isequal - used in _bt_doinsert in check for duplicates.
 *
 * Rule is simple: NOT_NULL not equal NULL, NULL not_equal NULL too.
 */
static bool
_bt_isequal(TupleDesc itupdesc, Page page, OffsetNumber offnum,
			int keysz, ScanKey scankey)
{
	Datum		datum;
	BTItem		btitem;
	IndexTuple	itup;
	ScanKey		entry;
	AttrNumber	attno;
	long		result;
	int			i;
	bool		null;

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

	for (i = 1; i <= keysz; i++)
	{
		entry = &scankey[i - 1];
		attno = entry->sk_attno;
		Assert(attno == i);
		datum = index_getattr(itup, attno, itupdesc, &null);

		/* NULLs are not equal */
		if (entry->sk_flags & SK_ISNULL || null)
			return false;

		result = (long) FMGR_PTR2(&entry->sk_func, entry->sk_argument, datum);
		if (result != 0)
			return false;
	}

	/* by here, the keys are equal */
	return true;
}

#ifdef NOT_USED
/*
 * _bt_shift - insert btitem on the passed page after shifting page
 *			   to the right in the tree.
 *
 * NOTE: tested for shifting leftmost page only, having btitem < hikey.
 */
static InsertIndexResult
_bt_shift(Relation rel, Buffer buf, BTStack stack, int keysz,
		  ScanKey scankey, BTItem btitem, BTItem hikey)
{
	InsertIndexResult res;
	int			itemsz;
	Page		page;
	BlockNumber bknum;
	BTPageOpaque pageop;
	Buffer		rbuf;
	Page		rpage;
	BTPageOpaque rpageop;
	Buffer		pbuf;
	Page		ppage;
	BTPageOpaque ppageop;
	Buffer		nbuf;
	Page		npage;
	BTPageOpaque npageop;
	BlockNumber nbknum;
	BTItem		nitem;
	OffsetNumber afteroff;

	btitem = _bt_formitem(&(btitem->bti_itup));
	hikey = _bt_formitem(&(hikey->bti_itup));

	page = BufferGetPage(buf);

	/* grab new page */
	nbuf = _bt_getbuf(rel, P_NEW, BT_WRITE);
	nbknum = BufferGetBlockNumber(nbuf);
	npage = BufferGetPage(nbuf);
	_bt_pageinit(npage, BufferGetPageSize(nbuf));
	npageop = (BTPageOpaque) PageGetSpecialPointer(npage);

	/* copy content of the passed page */
	memmove((char *) npage, (char *) page, BufferGetPageSize(buf));

	/* re-init old (passed) page */
	_bt_pageinit(page, BufferGetPageSize(buf));
	pageop = (BTPageOpaque) PageGetSpecialPointer(page);

	/* init old page opaque */
	pageop->btpo_flags = npageop->btpo_flags;	/* restore flags */
	pageop->btpo_flags &= ~BTP_CHAIN;
	if (_bt_itemcmp(rel, keysz, hikey, btitem, BTEqualStrategyNumber))
		pageop->btpo_flags |= BTP_CHAIN;
	pageop->btpo_prev = npageop->btpo_prev;		/* restore prev */
	pageop->btpo_next = nbknum; /* next points to the new page */
	pageop->btpo_parent = npageop->btpo_parent;

	/* init shifted page opaque */
	npageop->btpo_prev = bknum = BufferGetBlockNumber(buf);

	/* shifted page is ok, populate old page */

	/* add passed hikey */
	itemsz = IndexTupleDSize(hikey->bti_itup)
		+ (sizeof(BTItemData) - sizeof(IndexTupleData));
	itemsz = MAXALIGN(itemsz);
	if (PageAddItem(page, (Item) hikey, itemsz, P_HIKEY, LP_USED) == InvalidOffsetNumber)
		elog(FATAL, "btree: failed to add hikey in _bt_shift");
	pfree(hikey);

	/* add btitem */
	itemsz = IndexTupleDSize(btitem->bti_itup)
		+ (sizeof(BTItemData) - sizeof(IndexTupleData));
	itemsz = MAXALIGN(itemsz);
	if (PageAddItem(page, (Item) btitem, itemsz, P_FIRSTKEY, LP_USED) == InvalidOffsetNumber)
		elog(FATAL, "btree: failed to add firstkey in _bt_shift");
	pfree(btitem);
	nitem = (BTItem) PageGetItem(page, PageGetItemId(page, P_FIRSTKEY));
	btitem = _bt_formitem(&(nitem->bti_itup));
	ItemPointerSet(&(btitem->bti_itup.t_tid), bknum, P_HIKEY);

	/* ok, write them out */
	_bt_wrtnorelbuf(rel, nbuf);
	_bt_wrtnorelbuf(rel, buf);

	/* fix btpo_prev on right sibling of old page */
	if (!P_RIGHTMOST(npageop))
	{
		rbuf = _bt_getbuf(rel, npageop->btpo_next, BT_WRITE);
		rpage = BufferGetPage(rbuf);
		rpageop = (BTPageOpaque) PageGetSpecialPointer(rpage);
		rpageop->btpo_prev = nbknum;
		_bt_wrtbuf(rel, rbuf);
	}

	/* get parent pointing to the old page */
	ItemPointerSet(&(stack->bts_btitem->bti_itup.t_tid),
				   bknum, P_HIKEY);
	pbuf = _bt_getstackbuf(rel, stack, BT_WRITE);
	ppage = BufferGetPage(pbuf);
	ppageop = (BTPageOpaque) PageGetSpecialPointer(ppage);

	_bt_relbuf(rel, nbuf, BT_WRITE);
	_bt_relbuf(rel, buf, BT_WRITE);

	/* re-set parent' pointer - we shifted our page to the right ! */
	nitem = (BTItem) PageGetItem(ppage,
								 PageGetItemId(ppage, stack->bts_offset));
	ItemPointerSet(&(nitem->bti_itup.t_tid), nbknum, P_HIKEY);
	ItemPointerSet(&(stack->bts_btitem->bti_itup.t_tid), nbknum, P_HIKEY);
	_bt_wrtnorelbuf(rel, pbuf);

	/*
	 * Now we want insert into the parent pointer to our old page. It has
	 * to be inserted before the pointer to new page. You may get problems
	 * here (in the _bt_goesonpg and/or _bt_pgaddtup), but may be not - I
	 * don't know. It works if old page is leftmost (nitem is NULL) and
	 * btitem < hikey and it's all what we need currently. - vadim
	 * 05/30/97
	 */
	nitem = NULL;
	afteroff = P_FIRSTKEY;
	if (!P_RIGHTMOST(ppageop))
		afteroff = OffsetNumberNext(afteroff);
	if (stack->bts_offset >= afteroff)
	{
		afteroff = OffsetNumberPrev(stack->bts_offset);
		nitem = (BTItem) PageGetItem(ppage, PageGetItemId(ppage, afteroff));
		nitem = _bt_formitem(&(nitem->bti_itup));
	}
	res = _bt_insertonpg(rel, pbuf, stack->bts_parent,
						 keysz, scankey, btitem, nitem);
	pfree(btitem);

	ItemPointerSet(&(res->pointerData), nbknum, P_HIKEY);

	return res;
}

#endif