head	1.18;
access;
symbols
	Version_2_1:1.5;
locks; strict;
comment	@ * @;


1.18
date	92.08.24.23.14.23;	author mao;	state Exp;
branches;
next	1.17;

1.17
date	92.03.25.17.28.47;	author hong;	state Exp;
branches;
next	1.16;

1.16
date	92.03.11.02.15.25;	author mer;	state Exp;
branches;
next	1.15;

1.15
date	92.02.19.23.09.17;	author olson;	state Exp;
branches;
next	1.14;

1.14
date	92.02.12.13.28.27;	author olson;	state Exp;
branches;
next	1.13;

1.13
date	91.11.08.15.42.01;	author kemnitz;	state Exp;
branches;
next	1.12;

1.12
date	91.09.29.00.22.29;	author mer;	state Exp;
branches;
next	1.11;

1.11
date	91.05.22.14.02.45;	author kemnitz;	state Exp;
branches;
next	1.10;

1.10
date	91.05.22.13.47.08;	author mao;	state Exp;
branches;
next	1.9;

1.9
date	91.05.22.13.02.34;	author mao;	state Exp;
branches;
next	1.8;

1.8
date	91.05.22.07.43.59;	author mao;	state Exp;
branches;
next	1.7;

1.7
date	91.04.28.15.19.56;	author mao;	state Exp;
branches;
next	1.6;

1.6
date	91.03.22.00.30.42;	author mao;	state Exp;
branches;
next	1.5;

1.5
date	91.03.01.16.56.42;	author mao;	state Exp;
branches;
next	1.4;

1.4
date	91.02.28.23.58.44;	author mao;	state Exp;
branches;
next	1.3;

1.3
date	91.02.27.19.32.10;	author mao;	state Exp;
branches;
next	1.2;

1.2
date	91.02.24.09.00.13;	author mao;	state Exp;
branches;
next	1.1;

1.1
date	91.02.19.15.52.57;	author mao;	state Exp;
branches;
next	;


desc
@rtree interface routines
@


1.18
log
@fix cache invalidation at command boundaries when building indices
@
text
@/*
 *  rtree.c -- interface routines for the postgres rtree indexed access
 *	   method.
 */
#include "tmp/c.h"
#include "tmp/postgres.h"

#include "storage/bufmgr.h"
#include "storage/bufpage.h"
#include "storage/page.h"

#include "utils/log.h"
#include "utils/rel.h"
#include "utils/excid.h"

#include "access/heapam.h"
#include "access/genam.h"
#include "access/ftup.h"
#include "access/rtree.h"
#include "access/funcindex.h"

#include "nodes/execnodes.h"
#include "nodes/plannodes.h"

#include "executor/x_qual.h"
#include "executor/x_tuples.h"
#include "executor/tuptable.h"

#include "lib/index.h"

extern ExprContext RMakeExprContext();

RcsId("$Header: /private/mao/postgres/src/access/index-rtree/RCS/rtree.c,v 1.17 1992/03/25 17:28:47 hong Exp mao $");

extern InsertIndexResult    rtdoinsert();
extern InsertIndexResult    dosplit();
extern int	            nospace();

typedef struct SPLITVEC {
    OffsetNumber	*spl_left;
    int			spl_nleft;
    char		*spl_ldatum;
    OffsetNumber	*spl_right;
    int			spl_nright;
    char		*spl_rdatum;
} SPLITVEC;

void
rtbuild(heap, index, natts, attnum, istrat, pcount, params, finfo, pred)
    Relation heap;
    Relation index;
    AttributeNumber natts;
    AttributeNumber *attnum;
    IndexStrategy istrat;
    uint16 pcount;
    Datum *params;
    FuncIndexInfo *finfo;
    LispValue pred;
{
    HeapScanDesc scan;
    Buffer buffer;
    AttributeNumber i;
    HeapTuple htup;
    IndexTuple itup;
    TupleDescriptor hd, id;
    InsertIndexResult res;
    Datum *d;
    Boolean *nulls;
    int nb, nh, ni;
    ExprContext econtext;
    TupleTable tupleTable;
    TupleTableSlot slot;
    ObjectId hrelid, irelid;

    /* rtrees only know how to do stupid locking now */
    RelationSetLockForWrite(index);

    /*
     *  We expect to be called exactly once for any index relation.
     *  If that's not the case, big trouble's what we have.
     */

    if ((nb = RelationGetNumberOfBlocks(index)) != 0)
	elog(WARN, "%.16s already contains data", index->rd_rel->relname);

    /* initialize the root page */
    buffer = ReadBuffer(index, P_NEW);
    RTInitBuffer(buffer, F_LEAF);
    WriteBuffer(buffer);

    /* init the tuple descriptors and get set for a heap scan */
    hd = RelationGetTupleDescriptor(heap);
    id = RelationGetTupleDescriptor(index);
    d = LintCast(Datum *, palloc(natts * sizeof (*d)));
    nulls = LintCast(Boolean *, palloc(natts * sizeof (*nulls)));

    /*
     * If this is a predicate (partial) index, we will need to evaluate the
     * predicate using ExecQual, which requires the current tuple to be in a
     * slot of a TupleTable.  In addition, ExecQual must have an ExprContext
     * referring to that slot.  Here, we initialize dummy TupleTable and
     * ExprContext objects for this purpose. --Nels, Feb '92
     */
    if (pred != LispNil) {
	tupleTable = ExecCreateTupleTable(1);
	slot = (TupleTableSlot)
	    ExecGetTableSlot(tupleTable, ExecAllocTableSlot(tupleTable));
	econtext = RMakeExprContext();
	FillDummyExprContext(econtext, slot, hd, buffer);
    }

    scan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL);
    htup = heap_getnext(scan, 0, &buffer);

    /* count the tuples as we insert them */
    nh = ni = 0;

    for (; HeapTupleIsValid(htup); htup = heap_getnext(scan, 0, &buffer)) {

	nh++;

	/* Skip this tuple if it doesn't satisfy the partial-index predicate */
	if (pred != LispNil) {
	    SetSlotContents(slot, htup);
	    if (ExecQual(pred, econtext) == false)
		continue;
	}

	ni++;

	/*
	 *  For the current heap tuple, extract all the attributes
	 *  we use in this index, and note which are null.
	 */

	for (i = 1; i <= natts; i++) {
	    AttributeOffset attoff;
	    Boolean attnull;

	    /*
	     *  Offsets are from the start of the tuple, and are
	     *  zero-based; indices are one-based.  The next call
	     *  returns i - 1.  That's data hiding for you.
	     */

	    attoff = AttributeNumberGetAttributeOffset(i);
	    /*
	    d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
	    */
	    d[attoff] = GetIndexValue(htup, 
				      hd,
				      attoff, 
				      attnum, 
				      finfo, 
				      &attnull,
				      buffer);
	    nulls[attoff] = (attnull ? 'n' : ' ');
	}

	/* form an index tuple and point it at the heap tuple */
	itup = FormIndexTuple(natts, id, &d[0], nulls);
	itup->t_tid = htup->t_ctid;

	/*
	 *  Since we already have the index relation locked, we
	 *  call rtdoinsert directly.  Normal access method calls
	 *  dispatch through rtinsert, which locks the relation
	 *  for write.  This is the right thing to do if you're
	 *  inserting single tups, but not when you're initializing
	 *  the whole index at once.
	 */

	res = rtdoinsert(index, itup);
	pfree(itup);
	pfree(res);
    }

    /* okay, all heap tuples are indexed */
    heap_endscan(scan);
    RelationUnsetLockForWrite(index);

    if (pred != LispNil) {
	ExecDestroyTupleTable(tupleTable, false);
    }

    /*
     *  Since we just counted the tuples in the heap, we update its
     *  stats in pg_relation to guarantee that the planner takes
     *  advantage of the index we just created.  UpdateStats() does a
     *  CommandCounterIncrement(), which flushes changed entries from
     *  the system relcache.  The act of constructing an index changes
     *  these heap and index tuples in the system catalogs, so they
     *  need to be flushed.  We close them to guarantee that they
     *  will be.
     */

    hrelid = heap->rd_id;
    irelid = index->rd_id;
    heap_close(heap);
    index_close(index);

    UpdateStats(hrelid, nh, true);
    UpdateStats(irelid, ni, false);

    /* be tidy */
    pfree(nulls);
    pfree(d);
}

/*
 *  rtinsert -- wrapper for rtree tuple insertion.
 *
 *    This is the public interface routine for tuple insertion in rtrees.
 *    It doesn't do any work; just locks the relation and passes the buck.
 */

InsertIndexResult
rtinsert(r, itup)
    Relation r;
    IndexTuple itup;
{
    InsertIndexResult res;

    RelationSetLockForWrite(r);
    res = rtdoinsert(r, itup);

    /* XXX two-phase locking -- don't unlock the relation until EOT */
    return (res);
}

InsertIndexResult
rtdoinsert(r, itup)
    Relation r;
    IndexTuple itup;
{
    Page page;
    Buffer buffer;
    BlockNumber blk;
    IndexTuple which;
    OffsetNumber l;
    RTSTACK *stack;
    InsertIndexResult res;
    RTreePageOpaque opaque;
    char *datum;

    blk = P_ROOT;
    buffer = InvalidBuffer;
    stack = (RTSTACK *) NULL;

    do {
	/* let go of current buffer before getting next */
	if (buffer != InvalidBuffer)
	    ReleaseBuffer(buffer);

	/* get next buffer */
	buffer = ReadBuffer(r, blk);
	page = (Page) BufferGetPage(buffer, 0);

	opaque = (RTreePageOpaque) PageGetSpecialPointer(page);
	if (!(opaque->flags & F_LEAF)) {
	    RTSTACK *n;
	    ItemId iid;

	    n = (RTSTACK *) palloc(sizeof(RTSTACK));
	    n->rts_parent = stack;
	    n->rts_blk = blk;
	    n->rts_child = choose(r, page, itup);
	    stack = n;

	    iid = PageGetItemId(page, n->rts_child);
	    which = (IndexTuple) PageGetItem(page, iid);
	    blk = ItemPointerGetBlockNumber(&(which->t_tid));
	}
    } while (!(opaque->flags & F_LEAF));

    if (nospace(page, itup)) {
	/* need to do a split */
	res = dosplit(r, buffer, stack, itup);
	freestack(stack);
	WriteBuffer(buffer);  /* don't forget to release buffer! */
	return (res);
    }

    /* add the item and write the buffer */
    if (PageIsEmpty(page))
	PageAddItem(page, (Item) itup, IndexTupleSize(itup), 1, LP_USED);
    else
	PageAddItem(page, (Item) itup, IndexTupleSize(itup),
		    PageGetMaxOffsetIndex(page) + 2, LP_USED);

    WriteBuffer(buffer);

    datum = (((char *) itup) + sizeof(IndexTupleData));

    /* now expand the page boundary in the parent to include the new child */
    rttighten(r, stack, datum, (IndexTupleSize(itup) - sizeof(IndexTupleData)));
    freestack(stack);

    /* build and return an InsertIndexResult for this insertion */
    res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
    ItemPointerSet(&(res->pointerData), 0, blk, 0, l);
    res->lock = (RuleLock) NULL;
    res->offset = (double) 0;

    return (res);
}

rttighten(r, stk, datum, att_size)
    Relation r;
    RTSTACK *stk;
    char *datum;
    int att_size;
{
    char *oldud;
    Page p;
    int old_size, newd_size;
    RegProcedure union_proc, size_proc;
    Buffer b;

    if (stk == (RTSTACK *) NULL)
	return;

    b = ReadBuffer(r, stk->rts_blk);
    p = BufferGetPage(b, 0);

    union_proc = index_getprocid(r, 1, RT_UNION_PROC);
    size_proc = index_getprocid(r, 1, RT_SIZE_PROC);

    oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->rts_child));
    oldud += sizeof(IndexTupleData);

    old_size = (int) fmgr(size_proc, oldud);
    datum = (char *) fmgr(union_proc, oldud, datum);

    newd_size = (int) fmgr(size_proc, datum);

    /* XXX assume constant-size data items here */
    if (newd_size != old_size) {
	bcopy(datum, oldud, att_size);
	WriteBuffer(b);
	rttighten(r, stk->rts_parent, datum, att_size);
    } else {
	ReleaseBuffer(b);
    }
    pfree(datum);
}

/*
 *  dosplit -- split a page in the tree.
 *
 *    This is the quadratic-cost split algorithm Guttman describes in
 *    his paper.  The reason we chose it is that you can implement this
 *    with less information about the data types on which you're operating.
 */

InsertIndexResult
dosplit(r, buffer, stack, itup)
    Relation r;
    Buffer buffer;
    RTSTACK *stack;
    IndexTuple itup;
{
    Page p;
    Buffer leftbuf, rightbuf;
    Page left, right;
    ItemId itemid;
    IndexTuple item;
    IndexTuple ltup, rtup;
    OffsetNumber maxoff;
    OffsetIndex i;
    OffsetIndex leftoff, rightoff;
    BlockNumber lbknum, rbknum;
    BlockNumber bufblock;
    RTreePageOpaque opaque;
    int blank;
    InsertIndexResult res;
    char *isnull;
    SPLITVEC v;

    isnull = (char *) palloc(r->rd_rel->relnatts);
    for (blank = 0; blank < r->rd_rel->relnatts; blank++)
	isnull[blank] = ' ';
    p = (Page) BufferGetPage(buffer, 0);
    opaque = (RTreePageOpaque) PageGetSpecialPointer(p);

    /*
     *  The root of the tree is the first block in the relation.  If
     *  we're about to split the root, we need to do some hocus-pocus
     *  to enforce this guarantee.
     */

    if (BufferGetBlockNumber(buffer) == P_ROOT) {
	leftbuf = ReadBuffer(r, P_NEW);
	RTInitBuffer(leftbuf, opaque->flags);
	lbknum = BufferGetBlockNumber(leftbuf);
	left = (Page) BufferGetPage(leftbuf, 0);
    } else {
	leftbuf = buffer;
	IncrBufferRefCount(buffer);
	lbknum = BufferGetBlockNumber(buffer);
	left = (Page) PageGetTempPage(p, sizeof(RTreePageOpaqueData));
    }

    rightbuf = ReadBuffer(r, P_NEW);
    RTInitBuffer(rightbuf, opaque->flags);
    rbknum = BufferGetBlockNumber(rightbuf);
    right = (Page) BufferGetPage(rightbuf, 0);

    picksplit(r, p, &v, itup);

    leftoff = rightoff = 0;
    maxoff = PageGetMaxOffsetIndex(p);
    for (i = 0; i <= maxoff; i++) {
	char *dp;

	itemid = PageGetItemId(p, i);
	item = (IndexTuple) PageGetItem(p, itemid);

	if (i == *(v.spl_left)) {
	    (void) PageAddItem(left, (Item) item, IndexTupleSize(item),
			       leftoff++, LP_USED);
	    v.spl_left++;
	} else {
	    (void) PageAddItem(right, (Item) item, IndexTupleSize(item),
			       rightoff++, LP_USED);
	    v.spl_right++;
	}
    }

    /* build an InsertIndexResult for this insertion */
    res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
    res->lock = (RuleLock) NULL;
    res->offset = (double) 0;

    /* now insert the new index tuple */
    if (*(v.spl_left) != (OffsetNumber) 0) {
	(void) PageAddItem(left, (Item) itup, IndexTupleSize(itup),
			   leftoff++, LP_USED);
	ItemPointerSet(&(res->pointerData), 0, lbknum, 0, leftoff);
    } else {
	(void) PageAddItem(right, (Item) itup, IndexTupleSize(itup),
			   rightoff++, LP_USED);
	ItemPointerSet(&(res->pointerData), 0, rbknum, 0, rightoff);
    }

    if ((bufblock = BufferGetBlockNumber(buffer)) != P_ROOT) {
	PageRestoreTempPage(left, p);
    }
    WriteBuffer(leftbuf);
    WriteBuffer(rightbuf);

    /*
     *  Okay, the page is split.  We have three things left to do:
     *
     *    1)  Adjust any active scans on this index to cope with changes
     *        we introduced in its structure by splitting this page.
     *
     *    2)  "Tighten" the bounding box of the pointer to the left
     *	      page in the parent node in the tree, if any.  Since we
     *	      moved a bunch of stuff off the left page, we expect it
     *	      to get smaller.  This happens in the internal insertion
     *        routine.
     *
     *    3)  Insert a pointer to the right page in the parent.  This
     *	      may cause the parent to split.  If it does, we need to
     *	      repeat steps one and two for each split node in the tree.
     */

    /* adjust active scans */
    rtadjscans(r, RTOP_SPLIT, bufblock, 0);

    ltup = (IndexTuple) index_formtuple(r->rd_rel->relnatts,
				   (TupleDescriptor) (&r->rd_att.data[0]),
			           (Datum *) &(v.spl_ldatum), isnull);
    rtup = (IndexTuple) index_formtuple(r->rd_rel->relnatts,
				   (TupleDescriptor) &r->rd_att.data[0],
				   (Datum *) &(v.spl_rdatum), isnull);
    pfree (isnull);

    /* set pointers to new child pages in the internal index tuples */
    ItemPointerSet(&(ltup->t_tid), 0, lbknum, 0, 1);
    ItemPointerSet(&(rtup->t_tid), 0, rbknum, 0, 1);

    rtintinsert(r, stack, ltup, rtup);

    pfree(ltup);
    pfree(rtup);

    return (res);
}

rtintinsert(r, stk, ltup, rtup)
    Relation r;
    RTSTACK *stk;
    IndexTuple ltup;
    IndexTuple rtup;
{
    IndexTuple old;
    IndexTuple it;
    Buffer b;
    Page p;
    RegProcedure union_proc, size_proc;
    char *ldatum, *rdatum, *newdatum;
    InsertIndexResult res;

    if (stk == (RTSTACK *) NULL) {
	rtnewroot(r, ltup, rtup);
	return;
    }

    union_proc = index_getprocid(r, 1, RT_UNION_PROC);
    b = ReadBuffer(r, stk->rts_blk);
    p = BufferGetPage(b, 0);
    old = (IndexTuple) PageGetItem(p, PageGetItemId(p, stk->rts_child));

    /*
     *  This is a hack.  Right now, we force rtree keys to be constant size.
     *  To fix this, need delete the old key and add both left and right
     *  for the two new pages.  The insertion of left may force a split if
     *  the new left key is bigger than the old key.
     */

    if (IndexTupleSize(old) != IndexTupleSize(ltup))
	elog(WARN, "Variable-length rtree keys are not supported.");

    /* install pointer to left child */
    bcopy(ltup, old, IndexTupleSize(ltup));

    if (nospace(p, rtup)) {
	newdatum = (((char *) ltup) + sizeof(IndexTupleData));
	rttighten(r, stk->rts_parent, newdatum,
		  (IndexTupleSize(ltup) - sizeof(IndexTupleData)));
	res = dosplit(r, b, stk->rts_parent, rtup);
	pfree (res);
    } else {
	PageAddItem(p, (Item) rtup, IndexTupleSize(rtup),
		    PageGetMaxOffsetIndex(p), LP_USED);
	WriteBuffer(b);
	ldatum = (((char *) ltup) + sizeof(IndexTupleData));
	rdatum = (((char *) rtup) + sizeof(IndexTupleData));
	newdatum = (char *) fmgr(union_proc, ldatum, rdatum);

	rttighten(r, stk->rts_parent, newdatum,
		  (IndexTupleSize(rtup) - sizeof(IndexTupleData)));

	pfree(newdatum);
    }
}

rtnewroot(r, lt, rt)
    Relation r;
    IndexTuple lt;
    IndexTuple rt;
{
    Buffer b;
    Page p;

    b = ReadBuffer(r, P_ROOT);
    RTInitBuffer(b, 0);
    p = BufferGetPage(b, 0);
    PageAddItem(p, (Item) lt, IndexTupleSize(lt), 0, LP_USED);
    PageAddItem(p, (Item) rt, IndexTupleSize(rt), 1, LP_USED);
    WriteBuffer(b);
}

picksplit(r, page, v, itup)
    Relation r;
    Page page;
    SPLITVEC *v;
    IndexTuple itup;
{
    OffsetNumber maxoff;
    OffsetNumber i, j;
    IndexTuple item_1, item_2;
    char *datum_alpha, *datum_beta;
    char *datum_l, *datum_r;
    char *union_d, *union_dl, *union_dr;
    char *inter_d;
    RegProcedure union_proc;
    RegProcedure size_proc;
    RegProcedure inter_proc;
    bool firsttime;
    int waste;
    int size_alpha, size_beta, size_union, size_waste, size_inter;
    int size_l, size_r;
    int nbytes;
    OffsetNumber seed_1, seed_2;
    OffsetNumber *left, *right;

    union_proc = index_getprocid(r, 1, RT_UNION_PROC);
    size_proc = index_getprocid(r, 1, RT_SIZE_PROC);
    inter_proc = index_getprocid(r, 1, RT_INTER_PROC);
    maxoff = PageGetMaxOffsetIndex(page);

    nbytes = (maxoff + 3) * sizeof(OffsetNumber);
    v->spl_left = (OffsetNumber *) palloc(nbytes);
    v->spl_right = (OffsetNumber *) palloc(nbytes);

    firsttime = true;
    waste = 0;

    for (i = 0; i < maxoff; i++) {
	item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
	datum_alpha = ((char *) item_1) + sizeof(IndexTupleData);
	for (j = i + 1; j <= maxoff; j++) {
	    item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, j));
	    datum_beta = ((char *) item_2) + sizeof(IndexTupleData);

	    /* compute the wasted space by unioning these guys */
	    union_d = (char *) fmgr(union_proc, datum_alpha, datum_beta);
	    size_union = (int) fmgr(size_proc, union_d);
	    inter_d = (char *) fmgr(inter_proc, datum_alpha, datum_beta);
	    size_inter = (int) fmgr(size_proc, inter_d);
	    size_waste = size_union - size_inter;

	    pfree(union_d);
	    if (inter_d != (char *) NULL)
		    pfree(inter_d);

	    /*
	     *  are these a more promising split that what we've
	     *  already seen?
	     */

	    if (size_waste > waste || firsttime) {
		waste = size_waste;
		seed_1 = i;
		seed_2 = j;
		firsttime = false;
	    }
	}
    }

    left = v->spl_left;
    v->spl_nleft = 0;
    right = v->spl_right;
    v->spl_nright = 0;

    item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_1));
    datum_alpha = ((char *) item_1) + sizeof(IndexTupleData);
    datum_l = (char *) fmgr(union_proc, datum_alpha, datum_alpha);
    size_l = (int) fmgr(size_proc, datum_l);
    item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_2));
    datum_beta = ((char *) item_2) + sizeof(IndexTupleData);
    datum_r = (char *) fmgr(union_proc, datum_beta, datum_beta);
    size_r = (int) fmgr(size_proc, datum_r);

    /*
     *  Now split up the regions between the two seeds.  An important
     *  property of this split algorithm is that the split vector v
     *  has the indices of items to be split in order in its left and
     *  right vectors.  We exploit this property by doing a merge in
     *  the code that actually splits the page.
     *
     *  For efficiency, we also place the new index tuple in this loop.
     *  This is handled at the very end, when we have placed all the
     *  existing tuples and i == maxoff + 1.
     */

    maxoff++;
    for (i = 0; i <= maxoff; i++) {

	/*
	 *  If we've already decided where to place this item, just
	 *  put it on the right list.  Otherwise, we need to figure
	 *  out which page needs the least enlargement in order to
	 *  store the item.
	 */

	if (i == seed_1) {
	    *left++ = i;
	    v->spl_nleft++;
	    continue;
	} else if (i == seed_2) {
	    *right++ = i;
	    v->spl_nright++;
	    continue;
	}

	/* okay, which page needs least enlargement? */ 
	if (i == maxoff)
	    item_1 = itup;
	else
	    item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));

	datum_alpha = ((char *) item_1) + sizeof(IndexTupleData);
	union_dl = (char *) fmgr(union_proc, datum_l, datum_alpha);
	union_dr = (char *) fmgr(union_proc, datum_r, datum_alpha);
	size_alpha = (int) fmgr(size_proc, union_dl);
	size_beta = (int) fmgr(size_proc, union_dr);

	/* pick which page to add it to */
	if (size_alpha - size_l < size_beta - size_r) {
	    pfree(datum_l);
	    pfree(union_dr);
	    datum_l = union_dl;
	    size_l = size_alpha;
	    *left++ = i;
	    v->spl_nleft++;
	} else {
	    pfree(datum_r);
	    pfree(union_dl);
	    datum_r = union_dr;
	    size_r = size_alpha;
	    *right++ = i;
	    v->spl_nright++;
	}
    }
    *left = *right = (OffsetNumber)0;

    v->spl_ldatum = datum_l;
    v->spl_rdatum = datum_r;
}

RTInitBuffer(b, f)
    Buffer b;
    uint32 f;
{
    RTreePageOpaque opaque;
    Page page;
    PageSize pageSize;

    pageSize = BufferGetBlockSize(b) / PagePartitionGetPagesPerBlock(0);
    BufferInitPage(b, pageSize);

    page = BufferGetPage(b, FirstPageNumber);
    bzero(page, (int) pageSize);
    PageInit(page, pageSize, sizeof(RTreePageOpaqueData));

    opaque = (RTreePageOpaque) PageGetSpecialPointer(page);
    opaque->flags = f;
}

choose(r, p, it)
    Relation r;
    Page p;
    IndexTuple it;
{
    int maxoff;
    int i;
    char *ud, *id;
    char *datum;
    int isize, usize, dsize;
    int which, which_grow;
    RegProcedure union_proc, size_proc;

    union_proc = index_getprocid(r, 1, RT_UNION_PROC);
    size_proc = index_getprocid(r, 1, RT_SIZE_PROC);
    id = ((char *) it) + sizeof(IndexTupleData);
    isize = (int) fmgr(size_proc, id);
    maxoff = PageGetMaxOffsetIndex(p);
    which_grow = -1;
    which = -1;

    for (i = 0; i <= maxoff; i++) {
	datum = (char *) PageGetItem(p, PageGetItemId(p, i));
	datum += sizeof(IndexTupleData);
	dsize = (int) fmgr(size_proc, datum);
	ud = (char *) fmgr(union_proc, datum, id);
	usize = (int) fmgr(size_proc, ud);
	pfree(ud);
	if (which_grow < 0 || usize - dsize < which_grow) {
	    which = i;
	    which_grow = usize - dsize;
	    if (which_grow == 0)
		break;
	}
    }
    return (which);
}

int
nospace(p, it)
    Page p;
    IndexTuple it;
{
    return (PageGetFreeSpace(p) < IndexTupleSize(it));
}

freestack(s)
    RTSTACK *s;
{
    RTSTACK *p;

    while (s != (RTSTACK *) NULL) {
	p = s->rts_parent;
	pfree (s);
	s = p;
    }
}

char *
rtdelete(r, tid)
    Relation r;
    ItemPointer tid;
{
    BlockNumber blkno;
    OffsetIndex offind;
    Buffer buf;
    Page page;

    /* must write-lock on delete */
    RelationSetLockForWrite(r);

    blkno = ItemPointerGetBlockNumber(tid);
    offind = ItemPointerGetOffsetNumber(tid, 0) - 1;

    /* adjust any scans that will be affected by this deletion */
    rtadjscans(r, RTOP_DEL, blkno, offind);

    /* delete the index tuple */
    buf = ReadBuffer(r, blkno);
    page = BufferGetPage(buf, 0);

    PageIndexTupleDelete(page, offind + 1);

    WriteBuffer(buf);

    /* XXX -- two-phase locking, don't release the write lock */
    return ((char *) NULL);
}

#define RTDEBUG
#ifdef RTDEBUG

_rtdump(r)
    Relation r;
{
    Buffer buf;
    Page page;
    OffsetIndex offind, maxoff;
    BlockNumber blkno;
    BlockNumber nblocks;
    RTreePageOpaque po;
    IndexTuple itup;
    BlockNumber itblkno;
    PageNumber itpgno;
    OffsetNumber itoffno;
    char *datum;
    char *itkey;

    nblocks = RelationGetNumberOfBlocks(r);
    for (blkno = 0; blkno < nblocks; blkno++) {
	buf = ReadBuffer(r, blkno);
	page = BufferGetPage(buf, 0);
	po = (RTreePageOpaque) PageGetSpecialPointer(page);
	maxoff = PageGetMaxOffsetIndex(page);
	printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
		(po->flags & F_LEAF ? "LEAF" : "INTERNAL"));

	if (PageIsEmpty(page)) {
	    ReleaseBuffer(buf);
	    continue;
	}

	for (offind = 0; offind <= maxoff; offind++) {
	    itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offind));
	    itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
	    itpgno = ItemPointerGetPageNumber(&(itup->t_tid), 0);
	    itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid), 0);
	    datum = ((char *) itup);
	    datum += sizeof(IndexTupleData);
	    itkey = (char *) box_out(datum);
	    printf("\t[%d] size %d heap <%d,%d,%d> key:%s\n",
		   offind + 1, IndexTupleSize(itup), itblkno, itpgno,
		   itoffno, itkey);
	    pfree(itkey);
	}

	ReleaseBuffer(buf);
    }
}
#endif /* defined RTDEBUG */
@


1.17
log
@plugged more buffer leaks
@
text
@d33 1
a33 1
RcsId("$Header: RCS/rtree.c,v 1.16 92/03/11 02:15:25 mer Exp $");
d73 1
d189 6
a194 1
     *  advantage of the index we just created.
d197 7
a203 2
    UpdateStats(heap, nh);
    UpdateStats(index, ni);
@


1.16
log
@0 terminate split vectors.
@
text
@d33 1
a33 1
RcsId("$Header: /users/mer/pg/src/access/index-rtree/RCS/rtree.c,v 1.15 1992/02/19 23:09:17 olson Exp mer $");
d269 1
d388 1
@


1.15
log
@fix up includes for prototypes
@
text
@d33 1
a33 1
RcsId("$Header: src/access/index-rtree/RCS/rtree.c,v 1.14 92/02/12 13:28:27 olson Exp Locker: olson $");
d582 1
a582 1
    nbytes = (maxoff + 2) * sizeof(OffsetNumber);
d696 2
@


1.14
log
@support partial index definition
@
text
@d23 1
a23 1
#include "nodes/execnodes.a.h"
d33 1
a33 1
RcsId("$Header: src/access/index-rtree/RCS/rtree.c,v 1.13 91/11/08 15:42:01 kemnitz Exp Locker: olson $");
@


1.13
log
@fixed prototypes
@
text
@d22 2
a23 1
RcsId("$Header: RCS/rtree.c,v 1.12 91/09/29 00:22:29 mer Exp Locker: kemnitz $");
d25 10
d49 1
a49 1
rtbuild(heap, index, natts, attnum, istrat, pcount, params, finfo)
d58 1
d68 5
a72 2
    Boolean *null;
    int n;
d82 1
a82 1
    if ((n = RelationGetNumberOfBlocks(index)) != 0)
d94 1
a94 1
    null = LintCast(Boolean *, palloc(natts * sizeof (*null)));
d96 15
d115 1
a115 1
    n = 0;
d117 1
a117 1
    while (HeapTupleIsValid(htup)) {
d119 1
a119 1
	n++;
d121 9
d156 1
a156 1
	    null[attoff] = (attnull ? 'n' : ' ');
d160 1
a160 1
	itup = FormIndexTuple(natts, id, &d[0], null);
a174 3

	/* do the next tuple in the heap */
	htup = heap_getnext(scan, 0, &buffer);
d181 4
d191 2
a192 2
    UpdateStats(heap, n);
    UpdateStats(index, n);
d195 1
a195 1
    pfree(null);
a825 1
    Boolean null;
@


1.12
log
@functional indices change
@
text
@d22 1
a22 1
RcsId("$Header: /users/mer/postgres/src/access/index-rtree/RCS/rtree.c,v 1.11 1991/05/22 14:02:45 kemnitz Exp mer $");
d185 1
a185 1
    PageHeader page;
d206 1
a206 1
	page = (PageHeader) BufferGetPage(buffer, 0);
d234 1
a234 1
	PageAddItem(page, itup, IndexTupleSize(itup), 1, LP_USED);
d236 1
a236 1
	PageAddItem(page, itup, IndexTupleSize(itup),
d311 1
a311 1
    PageHeader p;
d313 1
a313 1
    PageHeader left, right;
d331 1
a331 1
    p = (PageHeader) BufferGetPage(buffer, 0);
d344 1
a344 1
	left = (PageHeader) BufferGetPage(leftbuf, 0);
d348 1
a348 1
	left = (PageHeader) PageGetTempPage(p, sizeof(RTreePageOpaqueData));
d354 1
a354 1
    right = (PageHeader) BufferGetPage(rightbuf, 0);
d367 1
a367 1
	    (void) PageAddItem(left, item, IndexTupleSize(item),
d371 1
a371 1
	    (void) PageAddItem(right, item, IndexTupleSize(item),
d384 1
a384 1
	(void) PageAddItem(left, itup, IndexTupleSize(itup),
d388 1
a388 1
	(void) PageAddItem(right, itup, IndexTupleSize(itup),
d419 6
a424 4
    ltup = (IndexTuple) formituple(r->rd_rel->relnatts, &r->rd_att.data[0],
			           &(v.spl_ldatum), isnull);
    rtup = (IndexTuple) formituple(r->rd_rel->relnatts, &r->rd_att.data[0],
				   &(v.spl_rdatum), isnull);
d483 1
a483 1
	PageAddItem(p, rtup, IndexTupleSize(rtup),
d508 2
a509 2
    PageAddItem(p, lt, IndexTupleSize(lt), 0, LP_USED);
    PageAddItem(p, rt, IndexTupleSize(rt), 1, LP_USED);
d515 1
a515 1
    PageHeader page;
d790 1
a790 1
	buf = RelationGetBuffer(r, blkno);
@


1.11
log
@changed indextuple header somewhat
@
text
@d20 1
d22 1
a22 1
RcsId("$Header: RCS/rtree.c,v 1.10 91/05/22 13:47:08 mao Exp Locker: kemnitz $");
d38 1
a38 1
rtbuild(heap, index, natts, attnum, istrat, pcount, params)
d46 1
d110 7
a116 2
	    d[attoff] = (Datum) heap_getattr(htup, buffer,
					     attnum[attoff], hd, &attnull);
@


1.10
log
@misc fixes
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.9 91/05/22 13:02:34 mao Exp Locker: mao $");
d227 1
a227 1
	PageAddItem(page, itup, itup->t_size, 1, LP_USED);
d229 1
a229 1
	PageAddItem(page, itup, itup->t_size,
d237 1
a237 1
    rttighten(r, stack, datum, (itup->t_size - sizeof(IndexTupleData)));
d360 2
a361 1
	    (void) PageAddItem(left, item, item->t_size, leftoff++, LP_USED);
d364 2
a365 1
	    (void) PageAddItem(right, item, item->t_size, rightoff++, LP_USED);
d377 2
a378 1
	(void) PageAddItem(left, itup, itup->t_size, leftoff++, LP_USED);
d381 2
a382 1
	(void) PageAddItem(right, itup, itup->t_size, rightoff++, LP_USED);
d461 1
a461 1
    if (old->t_size != ltup->t_size)
d465 1
a465 1
    bcopy(ltup, old, ltup->t_size);
d470 1
a470 1
		  (ltup->t_size - sizeof(IndexTupleData)));
d474 2
a475 1
	PageAddItem(p, rtup, rtup->t_size, PageGetMaxOffsetIndex(p), LP_USED);
d482 1
a482 1
		  (rtup->t_size - sizeof(IndexTupleData)));
d499 2
a500 2
    PageAddItem(p, lt, lt->t_size, 0, LP_USED);
    PageAddItem(p, rt, rt->t_size, 1, LP_USED);
d713 1
a713 1
    return (PageGetFreeSpace(p) < it->t_size);
d802 2
a803 1
		   offind + 1, itup->t_size, itblkno, itpgno, itoffno, itkey);
@


1.9
log
@take out debugging stuff.
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.8 91/05/22 07:43:59 mao Exp $");
a135 1
    _rtdump(index);
d226 6
a231 1
    PageAddItem(page, itup, itup->t_size, PageGetMaxOffsetIndex(page), LP_USED);
d314 1
d382 1
a382 1
    if (BufferGetBlockNumber(buffer) != P_ROOT) {
d406 1
a406 1
    rtadjscans(r, RTOP_SPLIT, BufferGetBlockNumber(buffer), 0);
d796 1
a796 1
	    printf("\t[%d] size %d heap <%d,%d,%d> key:%s",
@


1.8
log
@deletion code is in.  this version contains some debugging noise that
will go away soon, but kemnitz needs the file.
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.7 91/04/28 15:19:56 mao Exp Locker: mao $");
a35 2
static int MaoDebugRT = 0;

a56 3
    if (MaoDebugRT)
	return;

a110 1
	    box_maodebug(d[attoff]);
d114 1
a114 1
	itup = FormIndexTuple(natts, id, d, null);
d136 1
d790 4
a793 3
	    printf("\t[%d] size %d heap <%d,%d,%d> key:",
		   offind + 1, itup->t_size, itblkno, itpgno, itoffno);
	    box_maodebug(datum);
@


1.7
log
@add code to handle index tuple deletion; manage scans in private space
during updates so that we don't lose our position.
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.6 91/03/22 00:30:42 mao Exp Locker: mao $");
d36 2
d59 3
d110 1
d112 3
a114 1
			attnum[attoff], hd, &attnull);
d116 1
d562 1
d724 3
a726 1
rtdelete()
d728 24
a751 1
    return (char *) NULL;
d753 51
@


1.6
log
@update the index relation stats, as well as the heap relation stats.
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.5 91/03/01 16:56:42 mao Exp Locker: mao $");
d380 1
a380 1
     *  Okay, the page is split.  We have two things left to do:
d382 4
a385 1
     *    1)  "Tighten" the bounding box of the pointer to the left
d388 2
a389 1
     *	      to get smaller.
d391 1
a391 1
     *    2)  Insert a pointer to the right page in the parent.  This
d396 3
a712 1
/* ================================================================ */
@


1.5
log
@don't free tuples in doinsert -- let the caller do it.
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.4 91/02/28 23:58:44 mao Exp Locker: mao $");
d142 1
@


1.4
log
@plug memory leak
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.3 91/02/27 19:32:10 mao Exp $");
d120 1
a120 2
	 *  the whole index at once.  As a side effect, rtdoinsert
	 *  pfree's the tuple after insertion.
d124 2
a125 1
	pfree (res);
d164 2
a165 1
    RelationUnsetLockForWrite(r);
a229 2

    pfree(itup);
@


1.3
log
@this version works correctly for build and scan
@
text
@d21 1
a21 1
RcsId("$Header: RCS/rtree.c,v 1.2 91/02/24 09:00:13 mao Exp Locker: mao $");
d52 1
d124 2
a125 1
	rtdoinsert(index, itup);
@


1.2
log
@working (!) version of rtree am for postgres 2.1
@
text
@d14 1
d21 1
a21 1
RcsId("$Header$");
d175 1
a176 2
    OffsetNumber l;
    bool split;
d179 1
a183 1
    split = false;
d213 3
a215 1
	return (dosplit(r, buffer, stack, itup));
d222 6
d239 40
d394 1
d402 3
a414 4
    OffsetNumber off;
    OffsetNumber maxoff;
    char *oldud, *ud;
    char *isnull;
d419 1
a419 2
    int blank;
    RTSTACK *oldstk;
d446 3
d453 4
a456 1
	WriteNoReleaseBuffer(b);
d458 2
a459 3
	isnull = (char *) palloc(r->rd_rel->relnatts);
	for (blank = 0; blank < r->rd_rel->relnatts; blank++)
	    isnull[blank] = ' ';
d461 1
a461 33
	while (stk->rts_parent != (RTSTACK *) NULL) {
	    /* get the new bounding box for this page */
	    maxoff = PageGetMaxOffsetIndex(p);
	    oldud = (char *) PageGetItem(p, PageGetItemId(p, 0));
	    oldud += sizeof(IndexTupleData);
	    for (off = 1; off < maxoff; off++) {
		it = (IndexTuple) PageGetItem(p, PageGetItemId(p, off));
		ud = ((char *) it) + sizeof(IndexTupleData);
		ud = (char *) fmgr(union_proc, ud, oldud);
		if (off > 1)
		    pfree (oldud);
		oldud = ud;
	    }
	    ReleaseBuffer(b);
	    oldstk = stk;
	    stk = stk->rts_parent;
	    pfree (oldstk);
	    b = ReadBuffer(r, stk->rts_blk);
	    p = BufferGetPage(b, 0);
	    old = (IndexTuple) PageGetItem(p, PageGetItemId(p, stk->rts_child));
	    it = (IndexTuple) formituple(r->rd_rel->relnatts,
					 &(r->rd_att.data[0]),
					 &ud, isnull);
	    pfree(ud);
	    it->t_tid = old->t_tid;
	    if (old->t_size != it->t_size)
		elog(WARN, "Variable-length rtree keys are not supported.");

	    bcopy(it, old, it->t_size);
	    WriteNoReleaseBuffer(b);
	}
	ReleaseBuffer(b);
	pfree (isnull);
d521 1
a521 2
	    item_2 = (IndexTuple)
		PageGetItem(page, PageGetItemId(page, j));
d532 2
a533 1
	    pfree(inter_d);
d667 1
a667 1
    for (i = 0; i < maxoff; i++) {
d673 1
@


1.1
log
@Initial revision
@
text
@d3 1
a3 1
 *	       method.
d20 1
a20 2
extern InsertIndexResult	rtdoinsert();
extern PageHeader		dosplit();
d22 3
a24 5
typedef struct RTSTACK {
	struct RTSTACK	*rts_parent;
	OffsetNumber	rts_child;
	BlockNumber	rts_blk;
} RTSTACK;
d27 6
a32 6
	OffsetNumber	*spl_left;
	int		spl_nleft;
	char		*spl_ldatum;
	OffsetNumber	*spl_right;
	int		spl_nright;
	char		*spl_rdatum;
d37 7
a43 7
	Relation heap;
	Relation index;
	AttributeNumber natts;
	AttributeNumber *attnum;
	IndexStrategy istrat;
	uint16 pcount;
	Datum *params;
d45 9
a53 9
	HeapScanDesc scan;
	Buffer buffer;
	AttributeNumber i;
	HeapTuple htup;
	IndexTuple itup;
	TupleDescriptor hd, id;
	Datum *d;
	Boolean *null;
	int n;
d55 2
a56 2
	/* rtrees only know how to do stupid locking now */
	RelationSetLockForWrite(index);
d58 4
a61 4
	/*
	 *  We expect to be called exactly once for any index relation.
	 *  If that's not the case, big trouble's what we have.
	 */
d63 2
a64 3
	if (RelationGetNumberOfBlocks != 0)
		elog(WARN, "%.16s already contains data",
		     index->rd_rel->relname);
d66 4
a69 4
	/* initialize the root page */
	buffer = ReadBuffer(index, P_NEW);
	RTInitBuffer(buffer, F_LEAF);
	WriteBuffer(buffer);
d71 5
a75 5
	/* init the tuple descriptors and get set for a heap scan */
	hd = RelationGetTupleDescriptor(heap);
	id = RelationGetTupleDescriptor(index);
	d = LintCast(Datum *, palloc(natts * sizeof (*d)));
	null = LintCast(Boolean *, palloc(natts * sizeof (*null)));
d77 2
a78 2
	scan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL);
	htup = heap_getnext(scan, 0, &buffer);
d80 2
a81 2
	/* count the tuples as we insert them */
	n = 0;
d83 1
a83 1
	while (HeapTupleIsValid(htup)) {
d85 1
a85 1
		n++;
d87 4
a90 4
		/*
		 *  For the current heap tuple, extract all the attributes
		 *  we use in this index, and note which are null.
		 */
d92 3
a94 3
		for (i = 1; i <= natts; i++) {
			AttributeOffset attoff;
			Boolean attnull;
d96 5
a100 5
			/*
			 *  Offsets are from the start of the tuple, and are
			 *  zero-based; indices are one-based.  The next call
			 *  returns i - 1.  That's data hiding for you.
			 */
d102 5
a106 5
			attoff = AttributeNumberGetAttributeOffset(i);
			d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
						attnum[attoff], hd, &attnull);
			null[attoff] = (attnull ? 'n' : ' ');
		}
d108 3
a110 12
		/* form an index tuple and point it at the heap tuple */
		itup = FormIndexTuple(natts, id, d, null);
		itup->t_tid = htup->t_ctid;

		/*
		 *  Since we already have the index relation locked, we
		 *  call rtdoinsert directly.  Normal access method calls
		 *  dispatch through rtinsert, which locks the relation
		 *  for write.  This is the right thing to do if you're
		 *  inserting single tups, but not when you're initializing
		 *  the whole index at once.
		 */
d112 9
a120 1
		rtdoinsert(index, itup);
d122 1
a122 2
		/* done with this tuple */
		pfree(itup);
d124 3
a126 3
		/* do the next tuple in the heap */
		htup = heap_getnext(scan, 0, &buffer);
	}
d128 3
a130 3
	/* okay, all heap tuples are indexed */
	heap_endscan(scan);
	RelationUnsetLockForWrite(index);
d132 5
a136 5
	/*
	 *  Since we just counted the tuples in the heap, we update its
	 *  stats in pg_relation to guarantee that the planner takes
	 *  advantage of the index we just created.
	 */
d138 1
a138 1
	UpdateStats(heap, n);
d140 3
a142 3
	/* be tidy */
	pfree(null);
	pfree(d);
d148 2
a149 2
 *	This is the public interface routine for tuple insertion in rtrees.
 *	It doesn't do any work; just locks the relation and passes the buck.
d154 2
a155 2
	Relation r;
	IndexTuple itup;
d157 1
a157 1
	InsertIndexResult res;
d159 4
a162 4
	RelationSetLockForWrite(r);
	res = rtdoinsert(r, itup);
	RelationUnsetLockForWrite(r);
	return (res);
d167 2
a168 2
	Relation r;
	IndexTuple itup;
d170 9
a178 8
	PageHeader page;
	Buffer buffer;
	BlockNumber blk;
	IndexTuple which;
	RTSTACK *stack;
	OffsetNumber l;
	bool split;
	InsertIndexResult res;
d180 4
a183 4
	blk = P_ROOT;
	buffer = InvalidBuffer;
	stack = (RTSTACK *) NULL;
	split = false;
d185 4
a188 4
	do {
		/* let go of current buffer before getting next */
		if (buffer != InvalidBuffer)
			ReleaseBuffer(buffer);
d190 3
a192 3
		/* get next buffer */
		buffer = ReadBuffer(r, blk);
		page = (PageHeader) BufferGetPage(buffer, 0);
d194 4
a197 2
		if (!(page->opaque & F_LEAF)) {
			RTSTACK *n;
d199 5
a203 5
			n = (RTSTACK *) palloc(sizeof(RTSTACK));
			n->rts_parent = stack;
			n->rts_blk = blk;
			n->rts_child = choose(page, itup);
			stack = n;
d205 3
a207 10
			which = (IndexTuple) PageGetItem(page, n->rts_child);
			blk = ItemPointerGetBlock(&(which->t_tid));
		}
	} while (!(page->opaque & F_LEAF));

	if (nospace(page, itup)) {
		page = dosplit(r, buffer, stack, itup);
		ReleaseBuffer(buffer);
		freestack(stack);
		return (rtdoinsert(r, itup));
d209 1
d211 4
a214 4
	/* add the item and release the buffer */
	PageAddItem(page, itup, PSIZE(itup),
		    PageGetMaxOffsetIndex(page), LP_USED);
	ReleaseBuffer(buffer);
d216 3
a218 1
	pfree(itup);
d220 1
a220 5
	/* build and return an InsertIndexResult for this insertion */
	res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
	ItemPointerSet(&(res->pointerData), 0, blk, 0, l);
	res->lock = (RuleLock) NULL;
	res->offset = (double) 0;
d222 7
a228 1
	return (res);
d234 3
a236 3
 *	This is the quadratic-cost split algorithm Guttman describes in
 *	his paper.  The reason we chose it is that you can implement this
 *	with less information about the data types on which you're operating.
d239 1
a239 1
PageHeader
d241 4
a244 4
	Relation r;
	Buffer buffer;
	RTSTACK *stack;
	IndexTuple itup;
d246 15
a260 9
	PageHeader thispg;
	Buffer leftbuf, rightbuf;
	PageHeader left, right;
	ItemId itemid;
	IndexTuple item;
	OffsetNumber maxoff;
	OffsetIndex i;
	OffsetIndex leftoff, rightoff;
	SPLITVEC v;
d262 5
a266 1
	thispg = (PageHeader) BufferGetPage(buffer, 0);
d268 5
a272 5
	/*
	 *  The root of the tree is the first block in the relation.  If
	 *  we're about to split the root, we need to do some hocus-pocus
	 *  to enforce this guarantee.
	 */
d274 29
a302 4
	if (BufferGetBlock(buffer) == P_ROOT) {
		leftbuf = (Buffer) NULL;
		left = (PageHeader)
			  PageGetTempPage(thispg, sizeof(RTreePageOpaqueData));
d304 2
a305 2
		leftbuf = ReadBuffer(r, P_NEW);
		left = (PageHeader) BufferGetPage(leftbuf, 0);
d307 1
a307 2
	rightbuf = ReadBuffer(r, P_NEW);
	right = (PageHeader) BufferGetPage(rightbuf, 0);
d309 4
a312 1
	picksplit(r, thispg, &v);
d314 125
a438 14
	leftoff = rightoff = 0;
	maxoff = PageGetMaxOffsetIndex(thispg);
	for (i = 0; i < maxoff; i++) {
		itemid = PageGetItemId(thispg, i);
		item = (IndexTuple) PageGetItem(thispg, itemid);
		if (i == *(v.spl_left)) {
			(void) PageAddItem(left, item, /* XXX XXX SIZE ,*/
					   leftoff++, LP_USED);
			v.spl_left++;
		} else {
			(void) PageAddItem(right, item, /* XXX XXX SIZE ,*/
					   rightoff++, LP_USED);
			v.spl_right++;
		}
d440 3
a442 1
	/* XXX here, we need to propogate the insertion up the tree */
d445 4
a448 4
picksplit(r, page, v)
	Relation r;
	PageHeader page;
	SPLITVEC *v;
d450 2
a451 16
	OffsetNumber maxoff;
	OffsetNumber i, j;
	IndexTuple item_1, item_2;
	char *datum_alpha, *datum_beta;
	char *datum_l, *datum_r;
	char *union_d, *union_dl, *union_dr;
	char *inter_d;
	RegProcedure union_proc;
	RegProcedure size_proc;
	RegProcedure inter_proc;
	bool firsttime;
	int waste;
	int size_alpha, size_beta, size_union, size_waste, size_inter;
	int size_l, size_r;
	OffsetNumber seed_1, seed_2;
	OffsetNumber *left, *right;
d453 7
a459 4
	union_proc = index_getprocid(r, 1, RT_UNION_PROC);
	size_proc = index_getprocid(r, 1, RT_SIZE_PROC);
	inter_proc = index_getprocid(r, 1, RT_INTER_PROC);
	maxoff = PageGetMaxOffsetIndex(page);
d461 23
a483 2
	v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
	v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
d485 4
a488 2
	firsttime = true;
	waste = 0;
d490 3
a492 7
	for (i = 0; i < maxoff; i++) {
		item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
		datum_alpha = ((char *) item_1) + sizeof(IndexTuple);
		for (j = i + 1; j <= maxoff; j++) {
			item_2 = (IndexTuple)
				PageGetItem(page, PageGetItemId(page, j));
			datum_beta = ((char *) item_2) + sizeof(IndexTuple);
d494 2
a495 8
			/* compute the wasted space by unioning these guys */
			union_d = (char *) fmgr(union_proc,
						datum_alpha, datum_beta);
			size_union = (int) fmgr(size_proc, union_d);
			inter_d = (char *) fmgr(inter_proc,
						datum_alpha, datum_beta);
			size_inter = (int) fmgr(size_proc, inter_d);
			size_waste = size_union - size_inter;
d497 7
a503 2
			pfree(union_d);
			pfree(inter_d);
d505 6
a510 4
			/*
			 *  are these a more promising split that what we've
			 *  already seen?
			 */
d512 13
a524 6
			if (size_waste > waste || firsttime) {
				waste = size_waste;
				seed_1 = i;
				seed_2 = j;
			}
		}
d526 1
d528 4
a531 4
	left = v->spl_left;
	v->spl_nleft = 0;
	right = v->spl_right;
	v->spl_nright = 0;
d533 8
a540 8
	item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_1));
	datum_alpha = ((char *) item_1) + sizeof(IndexTuple);
	datum_l = (char *) fmgr(union_proc, datum_alpha, datum_alpha);
	size_l = (int) fmgr(size_proc, datum_l);
	item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_2));
	datum_beta = ((char *) item_2) + sizeof(IndexTuple);
	datum_r = (char *) fmgr(union_proc, datum_beta, datum_beta);
	size_r = (int) fmgr(size_proc, datum_r);
d542 15
d558 4
a561 5
	 *  Now split up the regions between the two seeds.  An important
	 *  property of this split algorithm is that the split vector v
	 *  has the indices of items to be split in order in its left and
	 *  right vectors.  We exploit this property by doing a merge in
	 *  the code that actually splits the page.
d564 9
a572 1
	for (i = 0; i <= maxoff; i++) {
d574 5
a578 6
		/*
		 *  If we've already decided where to place this item, just
		 *  put it on the right list.  Otherwise, we need to figure
		 *  out which page needs the least enlargement in order to
		 *  store the item.
		 */
d580 5
a584 9
		if (i == seed_1) {
			*left++ = i;
			v->spl_nleft++;
			continue;
		} else if (i == seed_2) {
			*right++ = i;
			v->spl_nright++;
			continue;
		}
d586 15
a600 24
		/* okay, which page needs least enlargement? */ 
		item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
		datum_alpha = ((char *) item_1) + sizeof(IndexTuple);
		union_dl = (char *) fmgr(union_proc, datum_l, datum_alpha);
		union_dr = (char *) fmgr(union_proc, datum_r, datum_alpha);
		size_alpha = (int) fmgr(size_proc, union_dl);
		size_beta = (int) fmgr(size_proc, union_dr);

		/* pick which page to add it to */
		if (size_alpha - size_l < size_beta - size_r) {
			pfree(datum_l);
			pfree(union_dr);
			datum_l = union_dl;
			size_l = size_alpha;
			*left++ = i;
			v->spl_nleft++;
		} else {
			pfree(datum_r);
			pfree(union_dl);
			datum_r = union_dr;
			size_r = size_alpha;
			*right++ = i;
			v->spl_nright++;
		}
d602 3
a604 2
	v->spl_ldatum = datum_l;
	v->spl_rdatum = datum_r;
d607 3
a609 3
/* ================================================================ */
char *
rtdelete()
d611 13
a623 1
	return (char *) NULL;
d626 4
a629 2
char *
rtgettuple()
d631 7
a637 2
	return (char *) NULL;
}
d639 22
a660 4
char *
rtbeginscan()
{
	return (char *) NULL;
d663 4
a666 2
void
rtendscan()
d668 1
a668 1
	;
d671 2
a672 2
void
rtmarkpos()
d674 1
a674 2
	;
}
d676 5
a680 4
void
rtrestrpos()
{
	;
d683 3
a685 2
void
rtrescan()
d687 1
a687 1
	;
a688 6

RTInitBuffer() { ; }
choose() { ; }
ItemPointerGetBlock() { ; }
nospace() { ; }
freestack() { ; }
@