head	1.28;
access;
symbols
	release_4_2:1.28
	aix_ok:1.24
	Version_2_1:1.5;
locks; strict;
comment	@ * @;


1.28
date	94.02.07.11.31.23;	author aoki;	state Exp;
branches;
next	1.27;

1.27
date	94.02.01.05.28.15;	author marcel;	state Exp;
branches;
next	1.26;

1.26
date	94.01.27.23.35.29;	author aoki;	state Exp;
branches;
next	1.25;

1.25
date	93.11.18.00.26.53;	author aoki;	state Exp;
branches;
next	1.24;

1.24
date	93.09.22.00.53.41;	author aoki;	state Exp;
branches;
next	1.23;

1.23
date	93.07.02.03.06.52;	author aoki;	state Exp;
branches;
next	1.22;

1.22
date	93.02.23.02.08.28;	author mao;	state Exp;
branches;
next	1.21;

1.21
date	93.02.17.01.31.31;	author olson;	state Exp;
branches;
next	1.20;

1.20
date	93.02.03.22.36.08;	author mao;	state Exp;
branches;
next	1.19;

1.19
date	92.12.05.01.11.05;	author olson;	state Exp;
branches;
next	1.18;

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.28
log
@proto fixes
casting to shut up gcc
moved SPLITVEC typedef over protos so they could compile
@
text
@/* ----------------------------------------------------------------
 *   FILE
 *	rtree.c
 *
 *   DESCRIPTION
 *	interface routines for the postgres rtree indexed access method.
 *
 *   NOTES
 *
 *   IDENTIFICATION
 *	$Header: /import/faerie/faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.27 1994/02/01 05:28:15 marcel Exp aoki $
 * ----------------------------------------------------------------
 */

#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/palloc.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: /import/faerie/faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.27 1994/02/01 05:28:15 marcel Exp aoki $");

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

/* automatically generated using mkproto */
extern void rtbuild ARGS((Relation heap, Relation index, AttributeNumber natts, AttributeNumber *attnum, IndexStrategy istrat, uint16 pcount, Datum *params, FuncIndexInfo *finfo, LispValue predInfo));
extern InsertIndexResult rtinsert ARGS((Relation r, IndexTuple itup));
extern InsertIndexResult rtdoinsert ARGS((Relation r, IndexTuple itup));
extern int rttighten ARGS((Relation r, RTSTACK *stk, char *datum, int att_size));
extern InsertIndexResult dosplit ARGS((Relation r, Buffer buffer, RTSTACK *stack, IndexTuple itup));
extern int rtintinsert ARGS((Relation r, RTSTACK *stk, IndexTuple ltup, IndexTuple rtup));
extern int rtnewroot ARGS((Relation r, IndexTuple lt, IndexTuple rt));
extern int picksplit ARGS((Relation r, Page page, SPLITVEC *v, IndexTuple itup));
extern int RTInitBuffer ARGS((Buffer b, uint32 f));
extern int choose ARGS((Relation r, Page p, IndexTuple it));
extern int nospace ARGS((Page p, IndexTuple it));
extern int freestack ARGS((RTSTACK *s));
extern char *rtdelete ARGS((Relation r, ItemPointer tid));
extern int _rtdump ARGS((Relation r));

void
rtbuild(heap, index, natts, attnum, istrat, pcount, params, finfo, predInfo)
    Relation heap;
    Relation index;
    AttributeNumber natts;
    AttributeNumber *attnum;
    IndexStrategy istrat;
    uint16 pcount;
    Datum *params;
    FuncIndexInfo *finfo;
    LispValue predInfo;
{
    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;
    LispValue pred, oldPred;

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

    pred = CAR(predInfo);
    oldPred = CADR(predInfo);

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

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

    /* initialize the root page (if this is a new index) */
    if (oldPred == LispNil) {
	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 || oldPred != 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++;

	/*
	 * If oldPred != LispNil, this is an EXTEND INDEX command, so skip
	 * this tuple if it was already in the existing partial index
	 */
	if (oldPred != LispNil) {
	    SetSlotContents(slot, htup);
	    if (ExecQual(oldPred, econtext) == true) {
		ni++;
		continue;
	    }
	}

	/* 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 || oldPred != LispNil) {
	ExecDestroyTupleTable(tupleTable, true);
	pfree(econtext);
    }

    /*
     *  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);

    if (oldPred != LispNil) {
	if (ni == nh) pred = LispNil;
	UpdateIndexPredicate(irelid, oldPred, pred);
    }

    /* 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 = 0;	/* XXX this is never set, but it's read below!? */
    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));
    /* XXX "l" is never set! */
    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;
    char *tdatum;
    Page p;
    float *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 = (float *) fmgr(size_proc, oldud);
    datum = (char *) fmgr(union_proc, oldud, datum);

    newd_size = (float *) fmgr(size_proc, datum);

    if (*newd_size != *old_size) {
	TupleDescriptor td = RelationGetTupleDescriptor(r);

	if (td->data[0]->attlen < 0) {
	    /*
	     * This is an internal page, so 'oldud' had better be a
	     * union (constant-length) key, too.  (See comment below.)
	     */
	    Assert(VARSIZE(datum) == VARSIZE(oldud));
	    bcopy(datum, oldud, VARSIZE(datum));
	} else {
	    bcopy(datum, oldud, att_size);
	}
	WriteBuffer(b);

	/*
	 *  The user may be defining an index on variable-sized data (like
	 *  polygons).  If so, we need to get a constant-sized datum for
	 *  insertion on the internal page.  We do this by calling the union
	 *  proc, which is guaranteed to return a rectangle.
	 */

	tdatum = (char *) fmgr(union_proc, datum, datum);
	rttighten(r, stk->rts_parent, tdatum, att_size);
	pfree(tdatum);
    } 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);
	WriteBuffer(b);  /* don't forget to release buffer!  - 01/31/94 */
	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;
    float *size_alpha, *size_beta, *size_union, *size_inter;
    float size_waste, waste;
    float *size_l, *size_r;
    int nbytes;
    OffsetNumber seed_1 = 0, seed_2 = 0;
    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 = (float *) fmgr(size_proc, union_d);
	    inter_d = (char *) fmgr(inter_proc, datum_alpha, datum_beta);
	    size_inter = (float *) fmgr(size_proc, inter_d);
	    size_waste = *size_union - *size_inter;

	    pfree(union_d);
	    pfree(size_union);
	    pfree(size_inter);

	    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 = (float *) 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 = (float *) 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 = (float *) fmgr(size_proc, union_dl);
	size_beta = (float *) 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++;
	}

	pfree(size_alpha);
	pfree(size_beta);
    }
    *left = *right = (OffsetNumber)0;

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

    pfree(size_l);
    pfree(size_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;
    float *isize, *usize, *dsize;
    int which;
    float 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 = (float *) 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 = (float *) fmgr(size_proc, datum);
	ud = (char *) fmgr(union_proc, datum, id);
	usize = (float *) 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;
	}
	pfree(usize);
	pfree(dsize);
    }

    pfree(isize);
    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
#include "utils/geo-decls.h"

extern char *box_out ARGS((BOX *box));	/* XXX builtins.h clash */

_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((BOX *) 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.27
log
@Fixed buffer leak
@
text
@d11 1
a11 1
 *	$Header: /import/faerie/faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.26 1994/01/27 23:35:29 aoki Exp $
d23 1
d44 1
a44 1
RcsId("$Header: /import/faerie/faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.26 1994/01/27 23:35:29 aoki Exp $");
d46 9
a70 9
typedef struct SPLITVEC {
    OffsetNumber	*spl_left;
    int			spl_nleft;
    char		*spl_ldatum;
    OffsetNumber	*spl_right;
    int			spl_nright;
    char		*spl_rdatum;
} SPLITVEC;

d909 3
d950 1
a950 1
	    itkey = (char *) box_out(datum);
@


1.26
log
@two bug fixes:
varlena keys were not handled right (rttighten thought its key
should be the size of the original varlena key, but for its
purposes the size is always the size of a union (constant-length)
key.
picksplit was using some uninitialized variables.
@
text
@d11 1
a11 1
 *	$Header: /import/faerie/faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.25 1993/11/18 00:26:53 aoki Exp aoki $
d43 1
a43 1
RcsId("$Header: /import/faerie/faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.25 1993/11/18 00:26:53 aoki Exp aoki $");
d602 1
@


1.25
log
@growth of a union'd box was being computed using the pointers
to floats (box size) instead of the actual size.  for some
reason this doesn't seem to make the algorithm work much
differently :-)
/
@
text
@d11 1
a11 1
 *	$Header: /faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.24 1993/09/22 00:53:41 aoki Exp aoki $
d43 1
a43 1
RcsId("$Header: /faerie/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.24 1993/09/22 00:53:41 aoki Exp aoki $");
d386 12
a397 1
	bcopy(datum, oldud, att_size);
d655 1
a655 1
    OffsetNumber seed_1, seed_2;
@


1.24
log
@proto fix
@
text
@d11 1
a11 1
 *	$Header$
d43 1
a43 1
RcsId("$Header: /home2/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.23 1993/07/02 03:06:52 aoki Exp $");
d831 1
a831 1
	    which_grow = usize - dsize;
@


1.23
log
@i'm going to check this in but i was tempted to leave it the
way it was so that purify will keep screaming.  the OffsetNumber
variable was never being set but was being passed to various
macros and functions; i initialized it to 0 but i have no idea
what the right answer is for this one.
@
text
@d1 12
a12 3
/*
 *  rtree.c -- interface routines for the postgres rtree indexed access
 *	   method.
d14 1
d43 1
a43 1
RcsId("$Header: /home2/aoki/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.22 1993/02/23 02:08:28 mao Exp aoki $");
d45 15
a59 3
extern InsertIndexResult    rtdoinsert();
extern InsertIndexResult    dosplit();
extern int	            nospace();
@


1.22
log
@box_size routines now return float* instead of int
@
text
@d33 1
a33 1
RcsId("$Header: /usr/local/devel/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.21 1993/02/17 01:31:31 olson Exp $");
d264 1
a264 1
    OffsetNumber l;
d325 1
@


1.21
log
@support "extend index" command
@
text
@d33 1
a33 1
RcsId("$Header: /private/src/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.20 1993/02/03 22:36:08 mao Exp olson $");
d339 1
d341 1
a341 1
    int old_size, newd_size;
d357 1
a357 1
    old_size = (int) fmgr(size_proc, oldud);
d360 1
a360 1
    newd_size = (int) fmgr(size_proc, datum);
d362 1
a362 2
    /* XXX assume constant-size data items here */
    if (newd_size != old_size) {
d365 11
a375 1
	rttighten(r, stk->rts_parent, datum, att_size);
d617 3
a619 3
    int waste;
    int size_alpha, size_beta, size_union, size_waste, size_inter;
    int size_l, size_r;
d645 1
a645 1
	    size_union = (int) fmgr(size_proc, union_d);
d647 2
a648 2
	    size_inter = (int) fmgr(size_proc, inter_d);
	    size_waste = size_union - size_inter;
d651 3
d679 1
a679 1
    size_l = (int) fmgr(size_proc, datum_l);
d683 1
a683 1
    size_r = (int) fmgr(size_proc, datum_r);
d726 2
a727 2
	size_alpha = (int) fmgr(size_proc, union_dl);
	size_beta = (int) fmgr(size_proc, union_dr);
d730 1
a730 1
	if (size_alpha - size_l < size_beta - size_r) {
d734 1
a734 1
	    size_l = size_alpha;
d741 1
a741 1
	    size_r = size_alpha;
d745 3
d753 3
d786 3
a788 2
    int isize, usize, dsize;
    int which, which_grow;
d794 1
a794 1
    isize = (int) fmgr(size_proc, id);
d802 1
a802 1
	dsize = (int) fmgr(size_proc, datum);
d804 1
a804 1
	usize = (int) fmgr(size_proc, ud);
d806 1
a806 1
	if (which_grow < 0 || usize - dsize < which_grow) {
d812 2
d815 2
@


1.20
log
@fix up arg-passing botch in elog (i hate NameData)
@
text
@d33 1
a33 1
RcsId("$Header: /private/src/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.19 1992/12/05 01:11:05 olson Exp mao $");
d49 1
a49 1
rtbuild(heap, index, natts, attnum, istrat, pcount, params, finfo, pred)
d58 1
a58 1
    LispValue pred;
d74 1
d79 3
d87 1
a87 1
    if ((nb = RelationGetNumberOfBlocks(index)) != 0)
d90 6
a95 4
    /* initialize the root page */
    buffer = ReadBuffer(index, P_NEW);
    RTInitBuffer(buffer, F_LEAF);
    WriteBuffer(buffer);
d110 1
a110 1
    if (pred != LispNil) {
d128 12
d200 1
a200 1
    if (pred != LispNil) {
d223 5
@


1.19
log
@changes for maintaining partial indexes
@
text
@d33 1
a33 1
RcsId("$Header: /private/src/postgres/src/backend/access/index-rtree/RCS/rtree.c,v 1.18 1992/08/24 23:14:23 mao Exp olson $");
d84 1
a84 1
	elog(WARN, "%.16s already contains data", index->rd_rel->relname);
@


1.18
log
@fix cache invalidation at command boundaries when building indices
@
text
@d33 1
a33 1
RcsId("$Header: /private/mao/postgres/src/access/index-rtree/RCS/rtree.c,v 1.17 1992/03/25 17:28:47 hong Exp mao $");
d183 2
a184 1
	ExecDestroyTupleTable(tupleTable, false);
@


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() { ; }
@