gist.c 32.9 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * gist.c
4
 *	  interface routines for the postgres GiST index access method.
5 6 7 8
 *
 *
 *
 * IDENTIFICATION
9
 *	  $Header: /cvsroot/pgsql/src/backend/access/gist/gist.c,v 1.76 2001/05/15 14:14:49 momjian Exp $
10 11 12 13
 *
 *-------------------------------------------------------------------------
 */

14
#include "postgres.h"
15

16 17 18 19 20
#include "access/genam.h"
#include "access/gist.h"
#include "access/gistscan.h"
#include "access/heapam.h"
#include "catalog/index.h"
Bruce Momjian's avatar
Bruce Momjian committed
21
#include "catalog/pg_index.h"
22
#include "executor/executor.h"
23
#include "miscadmin.h"
24
#include "utils/syscache.h"
25

Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
26
#include "access/xlogutils.h"
27

28
/* result's status */
Marc G. Fournier's avatar
Marc G. Fournier committed
29 30 31
#define INSERTED	0x01
#define SPLITED		0x02

32
/* non-export function prototypes */
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
static void gistdoinsert(Relation r,
			 IndexTuple itup,
			 InsertIndexResult *res,
			 GISTSTATE *GISTstate);
static int gistlayerinsert(Relation r, BlockNumber blkno,
				IndexTuple **itup,
				int *len,
				InsertIndexResult *res,
				GISTSTATE *giststate);
static OffsetNumber gistwritebuffer(Relation r,
				Page page,
				IndexTuple *itup,
				int len,
				OffsetNumber off,
				GISTSTATE *giststate);
static int gistnospace(Page page,
			IndexTuple *itvec, int len);
static IndexTuple *gistreadbuffer(Relation r,
			   Buffer buffer, int *len);
static IndexTuple *gistjoinvector(
			   IndexTuple *itvec, int *len,
			   IndexTuple *additvec, int addlen);
static IndexTuple gistunion(Relation r, IndexTuple *itvec,
		  int len, GISTSTATE *giststate);
static IndexTuple gistgetadjusted(Relation r,
				IndexTuple oldtup,
				IndexTuple addtup,
				GISTSTATE *giststate);
static IndexTuple *gistSplit(Relation r,
		  Buffer buffer,
		  IndexTuple *itup,
		  int *len,
		  GISTSTATE *giststate,
		  InsertIndexResult *res);
static void gistnewroot(GISTSTATE *giststate, Relation r,
Marc G. Fournier's avatar
Marc G. Fournier committed
68
			IndexTuple *itup, int len);
69
static void GISTInitBuffer(Buffer b, uint32 f);
70 71 72 73 74 75 76 77 78
static OffsetNumber gistchoose(Relation r, Page p,
		   IndexTuple it,
		   GISTSTATE *giststate);
static IndexTuple gist_tuple_replacekey(Relation r,
					  GISTENTRY entry, IndexTuple t);
static void gistcentryinit(GISTSTATE *giststate,
			   GISTENTRY *e, char *pr,
			   Relation r, Page pg,
			   OffsetNumber o, int b, bool l);
Marc G. Fournier's avatar
Marc G. Fournier committed
79 80

#undef GISTDEBUG
81
#ifdef GISTDEBUG
Marc G. Fournier's avatar
Marc G. Fournier committed
82
static void gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff);
83

84
#endif
85 86

/*
87 88
 * routine to build an index.  Basically calls insert over and over
 */
89 90
Datum
gistbuild(PG_FUNCTION_ARGS)
91
{
92 93 94 95 96
	Relation	heap = (Relation) PG_GETARG_POINTER(0);
	Relation	index = (Relation) PG_GETARG_POINTER(1);
	IndexInfo  *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
	Node	   *oldPred = (Node *) PG_GETARG_POINTER(3);

97
#ifdef NOT_USED
98 99
	IndexStrategy istrat = (IndexStrategy) PG_GETARG_POINTER(4);

100
#endif
101
	HeapScanDesc hscan;
102 103
	HeapTuple	htup;
	IndexTuple	itup;
104 105 106 107
	TupleDesc	htupdesc,
				itupdesc;
	Datum		attdata[INDEX_MAX_KEYS];
	char		nulls[INDEX_MAX_KEYS];
108
	double		nhtups,
109 110
				nitups;
	Node	   *pred = indexInfo->ii_Predicate;
111

112
#ifndef OMIT_PARTIAL_INDEX
113
	TupleTable	tupleTable;
114
	TupleTableSlot *slot;
115

116
#endif
117
	ExprContext *econtext;
118 119
	GISTSTATE	giststate;
	GISTENTRY	tmpcentry;
120
	Buffer		buffer = InvalidBuffer;
121
	bool	   *compvec;
122
	int			i;
123

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
124
	/* no locking is needed */
125 126 127 128 129 130 131

	initGISTstate(&giststate, index);

	/*
	 * We expect to be called exactly once for any index relation. If
	 * that's not the case, big trouble's what we have.
	 */
132
	if (oldPred == NULL && RelationGetNumberOfBlocks(index) != 0)
133
		elog(ERROR, "%s already contains data", RelationGetRelationName(index));
134 135 136 137 138 139 140 141 142

	/* initialize the root page (if this is a new index) */
	if (oldPred == NULL)
	{
		buffer = ReadBuffer(index, P_NEW);
		GISTInitBuffer(buffer, F_LEAF);
		WriteBuffer(buffer);
	}

143 144 145
	/* get tuple descriptors for heap and index relations */
	htupdesc = RelationGetDescr(heap);
	itupdesc = RelationGetDescr(index);
146 147 148 149 150 151

	/*
	 * 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
152 153 154 155
	 * TupleTable and ExprContext objects for this purpose. --Nels, Feb 92
	 *
	 * We construct the ExprContext anyway since we need a per-tuple
	 * temporary memory context for function evaluation -- tgl July 00
156
	 */
157
#ifndef OMIT_PARTIAL_INDEX
158 159 160 161
	if (pred != NULL || oldPred != NULL)
	{
		tupleTable = ExecCreateTupleTable(1);
		slot = ExecAllocTableSlot(tupleTable);
162
		ExecSetSlotDescriptor(slot, htupdesc, false);
163 164
	}
	else
165 166 167 168
	{
		tupleTable = NULL;
		slot = NULL;
	}
169 170 171
	econtext = MakeExprContext(slot, TransactionCommandContext);
#else
	econtext = MakeExprContext(NULL, TransactionCommandContext);
172
#endif	 /* OMIT_PARTIAL_INDEX */
173

174
	/* build the index */
175
	nhtups = nitups = 0.0;
176 177 178 179 180

	compvec = (bool *) palloc(sizeof(bool) * indexInfo->ii_NumIndexAttrs);

	/* start a heap scan */
	hscan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
181

182
	while (HeapTupleIsValid(htup = heap_getnext(hscan, 0)))
183
	{
184 185
		MemoryContextReset(econtext->ecxt_per_tuple_memory);

186
		nhtups += 1.0;
187

188
#ifndef OMIT_PARTIAL_INDEX
189

190 191 192 193 194 195 196
		/*
		 * If oldPred != NULL, this is an EXTEND INDEX command, so skip
		 * this tuple if it was already in the existing partial index
		 */
		if (oldPred != NULL)
		{
			slot->val = htup;
197
			if (ExecQual((List *) oldPred, econtext, false))
198
			{
199
				nitups += 1.0;
200 201 202 203 204 205 206 207 208 209 210
				continue;
			}
		}

		/*
		 * Skip this tuple if it doesn't satisfy the partial-index
		 * predicate
		 */
		if (pred != NULL)
		{
			slot->val = htup;
211
			if (!ExecQual((List *) pred, econtext, false))
212 213
				continue;
		}
214
#endif	 /* OMIT_PARTIAL_INDEX */
215

216
		nitups += 1.0;
217 218 219 220 221

		/*
		 * For the current heap tuple, extract all the attributes we use
		 * in this index, and note which are null.
		 */
222 223 224 225 226 227
		FormIndexDatum(indexInfo,
					   htup,
					   htupdesc,
					   econtext->ecxt_per_tuple_memory,
					   attdata,
					   nulls);
228 229

		/* immediately compress keys to normalize */
230
		for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
231
		{
232
			gistcentryinit(&giststate, &tmpcentry, (char *) attdata[i],
233 234
						   (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
						   -1 /* size is currently bogus */ , TRUE);
235 236
			if (attdata[i] != (Datum) tmpcentry.pred &&
				!(giststate.keytypbyval))
237 238 239
				compvec[i] = TRUE;
			else
				compvec[i] = FALSE;
240
			attdata[i] = (Datum) tmpcentry.pred;
241 242 243
		}

		/* form an index tuple and point it at the heap tuple */
244
		itup = index_formtuple(itupdesc, attdata, nulls);
245
		itup->t_tid = htup->t_self;
246 247 248 249 250 251 252 253 254

		/*
		 * Since we already have the index relation locked, we call
		 * gistdoinsert directly.  Normal access method calls dispatch
		 * through gistinsert, 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.
		 */

Marc G. Fournier's avatar
Marc G. Fournier committed
255
		gistdoinsert(index, itup, NULL, &giststate);
256 257 258 259 260

		for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
			if (compvec[i])
				pfree(DatumGetPointer(attdata[i]));

261
		pfree(itup);
262
	}
263 264

	/* okay, all heap tuples are indexed */
265 266 267
	heap_endscan(hscan);

	pfree(compvec);
268

269
#ifndef OMIT_PARTIAL_INDEX
270
	if (pred != NULL || oldPred != NULL)
271
		ExecDropTupleTable(tupleTable, true);
272
#endif	 /* OMIT_PARTIAL_INDEX */
273
	FreeExprContext(econtext);
274

275
	/*
276 277
	 * Since we just counted the tuples in the heap, we update its stats
	 * in pg_class to guarantee that the planner takes advantage of the
278 279 280 281 282 283 284
	 * index we just created.  But, only update statistics during normal
	 * index definitions, not for indices on system catalogs created
	 * during bootstrap processing.  We must close the relations before
	 * updating statistics to guarantee that the relcache entries are
	 * flushed when we increment the command counter in UpdateStats(). But
	 * we do not release any locks on the relations; those will be held
	 * until end of transaction.
285
	 */
286
	if (IsNormalProcessingMode())
287
	{
288 289
		Oid			hrelid = RelationGetRelid(heap);
		Oid			irelid = RelationGetRelid(index);
290 291 292

		heap_close(heap, NoLock);
		index_close(index);
293 294 295
		UpdateStats(hrelid, nhtups);
		UpdateStats(irelid, nitups);
		if (oldPred != NULL)
296
		{
297
			if (nitups == nhtups)
298 299 300
				pred = NULL;
			UpdateIndexPredicate(irelid, oldPred, pred);
		}
301 302
	}

Marc G. Fournier's avatar
Marc G. Fournier committed
303
#ifdef GISTDEBUG
304
	gist_dumptree(index, 0, GISTP_ROOT, 0);
Marc G. Fournier's avatar
Marc G. Fournier committed
305 306
#endif

307
	PG_RETURN_VOID();
308 309 310
}

/*
311
 *	gistinsert -- wrapper for GiST tuple insertion.
312
 *
313 314
 *	  This is the public interface routine for tuple insertion in GiSTs.
 *	  It doesn't do any work; just locks the relation and passes the buck.
315
 */
316 317
Datum
gistinsert(PG_FUNCTION_ARGS)
318
{
319 320 321 322 323
	Relation	r = (Relation) PG_GETARG_POINTER(0);
	Datum	   *datum = (Datum *) PG_GETARG_POINTER(1);
	char	   *nulls = (char *) PG_GETARG_POINTER(2);
	ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);

324
#ifdef NOT_USED
325 326
	Relation	heapRel = (Relation) PG_GETARG_POINTER(4);

327
#endif
328
	InsertIndexResult res;
329 330 331 332 333
	IndexTuple	itup;
	GISTSTATE	giststate;
	GISTENTRY	tmpentry;
	int			i;
	bool	   *compvec;
334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349

	initGISTstate(&giststate, r);

	/* immediately compress keys to normalize */
	compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
	for (i = 0; i < r->rd_att->natts; i++)
	{
		gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
					   (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
					   -1 /* size is currently bogus */ , TRUE);
		if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
			compvec[i] = TRUE;
		else
			compvec[i] = FALSE;
		datum[i] = (Datum) tmpentry.pred;
	}
350
	itup = index_formtuple(RelationGetDescr(r), datum, nulls);
351 352
	itup->t_tid = *ht_ctid;

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
353 354 355
	/*
	 * Notes in ExecUtils:ExecOpenIndices()
	 *
Bruce Momjian's avatar
Bruce Momjian committed
356
	 * RelationSetLockForWrite(r);
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
357 358
	 */

Marc G. Fournier's avatar
Marc G. Fournier committed
359 360
	res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
	gistdoinsert(r, itup, &res, &giststate);
361 362 363 364 365 366
	for (i = 0; i < r->rd_att->natts; i++)
		if (compvec[i] == TRUE)
			pfree((char *) datum[i]);
	pfree(itup);
	pfree(compvec);

367
	PG_RETURN_POINTER(res);
368 369 370 371 372 373 374 375
}

/*
** Take a compressed entry, and install it on a page.  Since we now know
** where the entry will live, we decompress it and recompress it using
** that knowledge (some compression routines may want to fish around
** on the page, for example, or do something special for leaf nodes.)
*/
376
static OffsetNumber
377
gistPageAddItem(GISTSTATE *giststate,
378 379 380 381 382 383
				Relation r,
				Page page,
				Item item,
				Size size,
				OffsetNumber offsetNumber,
				ItemIdFlags flags,
384 385
				GISTENTRY *dentry,
				IndexTuple *newtup)
386
{
387 388
	GISTENTRY	tmpcentry;
	IndexTuple	itup = (IndexTuple) item;
389
	OffsetNumber retval;
390 391 392 393 394 395 396 397 398 399 400

	/*
	 * recompress the item given that we now know the exact page and
	 * offset for insertion
	 */
	gistdentryinit(giststate, dentry,
				   (((char *) itup) + sizeof(IndexTupleData)),
			  (Relation) 0, (Page) 0, (OffsetNumber) InvalidOffsetNumber,
				   IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
	gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
				   offsetNumber, dentry->bytes, FALSE);
Marc G. Fournier's avatar
Marc G. Fournier committed
401 402
	*newtup = gist_tuple_replacekey(r, tmpcentry, itup);
	retval = PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
403
						 offsetNumber, flags);
404 405 406
	if (retval == InvalidOffsetNumber)
		elog(ERROR, "gist: failed to add index item to %s",
			 RelationGetRelationName(r));
407
	/* be tidy */
Marc G. Fournier's avatar
Marc G. Fournier committed
408
	if (tmpcentry.pred && tmpcentry.pred != dentry->pred
409 410
		&& tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
		pfree(tmpcentry.pred);
Marc G. Fournier's avatar
Marc G. Fournier committed
411
	return (retval);
412 413
}

414 415 416 417 418 419
static void
gistdoinsert(Relation r,
			 IndexTuple itup,
			 InsertIndexResult *res,
			 GISTSTATE *giststate)
{
Marc G. Fournier's avatar
Marc G. Fournier committed
420
	IndexTuple *instup;
421 422 423 424 425 426 427
	int			i,
				ret,
				len = 1;

	instup = (IndexTuple *) palloc(sizeof(IndexTuple));
	instup[0] = (IndexTuple) palloc(IndexTupleSize(itup));
	memcpy(instup[0], itup, IndexTupleSize(itup));
Marc G. Fournier's avatar
Marc G. Fournier committed
428 429

	ret = gistlayerinsert(r, GISTP_ROOT, &instup, &len, res, giststate);
430 431
	if (ret & SPLITED)
		gistnewroot(giststate, r, instup, len);
432

433 434 435
	for (i = 0; i < len; i++)
		pfree(instup[i]);
	pfree(instup);
Marc G. Fournier's avatar
Marc G. Fournier committed
436
}
437

Marc G. Fournier's avatar
Marc G. Fournier committed
438
static int
439 440 441 442 443 444 445 446 447 448
gistlayerinsert(Relation r, BlockNumber blkno,
				IndexTuple **itup,		/* in - out, has compressed entry */
				int *len,		/* in - out */
				InsertIndexResult *res, /* out */
				GISTSTATE *giststate)
{
	Buffer		buffer;
	Page		page;
	OffsetNumber child;
	int			ret;
Marc G. Fournier's avatar
Marc G. Fournier committed
449
	GISTPageOpaque opaque;
450

Marc G. Fournier's avatar
Marc G. Fournier committed
451 452 453
	buffer = ReadBuffer(r, blkno);
	page = (Page) BufferGetPage(buffer);
	opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
454

455 456
	if (!(opaque->flags & F_LEAF))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
457 458
		/* internal page, so we must walk on tree */
		/* len IS equial 1 */
459
		ItemId		iid;
Marc G. Fournier's avatar
Marc G. Fournier committed
460 461
		BlockNumber nblkno;
		ItemPointerData oldtid;
462 463 464
		IndexTuple	oldtup;

		child = gistchoose(r, page, *(*itup), giststate);
Marc G. Fournier's avatar
Marc G. Fournier committed
465 466 467 468
		iid = PageGetItemId(page, child);
		oldtup = (IndexTuple) PageGetItem(page, iid);
		nblkno = ItemPointerGetBlockNumber(&(oldtup->t_tid));

469 470 471 472
		/*
		 * After this call: 1. if child page was splited, then itup
		 * contains keys for each page 2. if  child page wasn't splited,
		 * then itup contains additional for adjustement of current key
Marc G. Fournier's avatar
Marc G. Fournier committed
473
		 */
474
		ret = gistlayerinsert(r, nblkno, itup, len, res, giststate);
475

Marc G. Fournier's avatar
Marc G. Fournier committed
476
		/* nothing inserted in child */
477 478
		if (!(ret & INSERTED))
		{
Marc G. Fournier's avatar
Marc G. Fournier committed
479
			ReleaseBuffer(buffer);
480
			return 0x00;
Marc G. Fournier's avatar
Marc G. Fournier committed
481
		}
482

483 484 485 486 487 488 489
		/* child does not splited */
		if (!(ret & SPLITED))
		{
			IndexTuple	newtup = gistgetadjusted(r, oldtup, (*itup)[0], giststate);

			if (!newtup)
			{
Marc G. Fournier's avatar
Marc G. Fournier committed
490 491 492 493
				/* not need to update key */
				ReleaseBuffer(buffer);
				return 0x00;
			}
494

495
			pfree((*itup)[0]);	/* !!! */
Marc G. Fournier's avatar
Marc G. Fournier committed
496 497
			(*itup)[0] = newtup;
		}
498

499
		/* key is modified, so old version must be deleted */
Marc G. Fournier's avatar
Marc G. Fournier committed
500 501
		ItemPointerSet(&oldtid, blkno, child);
		DirectFunctionCall2(gistdelete,
502 503
							PointerGetDatum(r),
							PointerGetDatum(&oldtid));
Marc G. Fournier's avatar
Marc G. Fournier committed
504
	}
505

506
	ret = INSERTED;
Marc G. Fournier's avatar
Marc G. Fournier committed
507

508 509
	if (gistnospace(page, (*itup), *len))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
510 511
		/* no space for insertion */
		IndexTuple *itvec;
512
		int			tlen;
Marc G. Fournier's avatar
Marc G. Fournier committed
513 514

		ret |= SPLITED;
515 516 517 518 519 520 521 522 523 524 525 526
		itvec = gistreadbuffer(r, buffer, &tlen);
		itvec = gistjoinvector(itvec, &tlen, (*itup), *len);
		pfree((*itup));
		(*itup) = gistSplit(r, buffer, itvec, &tlen, giststate,
							(opaque->flags & F_LEAF) ? res : NULL);		/* res only for
																		 * inserting in leaf */
		ReleaseBuffer(buffer);
		pfree(itvec);
		*len = tlen;			/* now tlen >= 2 */
	}
	else
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
527
		/* enogth space */
528 529
		OffsetNumber off,
					l;
Marc G. Fournier's avatar
Marc G. Fournier committed
530

531 532
		off = (PageIsEmpty(page)) ?
			FirstOffsetNumber
Marc G. Fournier's avatar
Marc G. Fournier committed
533
			:
534 535
			OffsetNumberNext(PageGetMaxOffsetNumber(page));
		l = gistwritebuffer(r, page, (*itup), *len, off, giststate);
Marc G. Fournier's avatar
Marc G. Fournier committed
536
		WriteBuffer(buffer);
537

538 539 540 541
		/*
		 * set res if insert into leaf page, in this case, len = 1 always
		 */
		if (res && (opaque->flags & F_LEAF))
Marc G. Fournier's avatar
Marc G. Fournier committed
542 543
			ItemPointerSet(&((*res)->pointerData), blkno, l);

544 545 546 547 548 549 550 551 552 553 554 555
		if (*len > 1)
		{						/* previos insert ret & SPLITED != 0 */
			int			i;

			/*
			 * child was splited, so we must form union for insertion in
			 * parent
			 */
			IndexTuple	newtup = gistunion(r, (*itup), *len, giststate);

			for (i = 0; i < *len; i++)
				pfree((*itup)[i]);
Marc G. Fournier's avatar
Marc G. Fournier committed
556 557 558 559
			(*itup)[0] = newtup;
			*len = 1;
		}
	}
560

561 562 563 564
	return ret;
}

/*
Marc G. Fournier's avatar
Marc G. Fournier committed
565 566 567
 * Write itup vector to page, has no control of free space
 */
static OffsetNumber
568 569 570
gistwritebuffer(Relation r, Page page, IndexTuple *itup,
				int len, OffsetNumber off, GISTSTATE *giststate)
{
Marc G. Fournier's avatar
Marc G. Fournier committed
571
	OffsetNumber l = InvalidOffsetNumber;
572 573 574 575 576 577 578 579 580 581
	int			i;
	GISTENTRY	tmpdentry;
	IndexTuple	newtup;

	for (i = 0; i < len; i++)
	{
		l = gistPageAddItem(giststate, r, page,
							(Item) itup[i], IndexTupleSize(itup[i]),
							off, LP_USED, &tmpdentry, &newtup);
		off = OffsetNumberNext(off);
Marc G. Fournier's avatar
Marc G. Fournier committed
582 583 584 585 586
		if (tmpdentry.pred != (((char *) itup[i]) + sizeof(IndexTupleData)) && tmpdentry.pred)
			pfree(tmpdentry.pred);
		if (itup[i] != newtup)
			pfree(newtup);
	}
587
	return l;
Marc G. Fournier's avatar
Marc G. Fournier committed
588
}
589

Marc G. Fournier's avatar
Marc G. Fournier committed
590 591 592
/*
 * Check space for itup vector on page
 */
593 594 595 596 597
static int
gistnospace(Page page, IndexTuple *itvec, int len)
{
	int			size = 0;
	int			i;
598

599 600 601 602 603
	for (i = 0; i < len; i++)
		size += IndexTupleSize(itvec[i]) + 4;	/* ??? */

	return (PageGetFreeSpace(page) < size);
}
604

Marc G. Fournier's avatar
Marc G. Fournier committed
605 606 607 608
/*
 * Read buffer into itup vector
 */
static IndexTuple *
609 610 611 612 613 614
gistreadbuffer(Relation r, Buffer buffer, int *len /* out */ )
{
	OffsetNumber i,
				maxoff;
	IndexTuple *itvec;
	Page		p = (Page) BufferGetPage(buffer);
615

616
	*len = 0;
Marc G. Fournier's avatar
Marc G. Fournier committed
617
	maxoff = PageGetMaxOffsetNumber(p);
618 619 620
	itvec = palloc(sizeof(IndexTuple) * maxoff);
	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
		itvec[(*len)++] = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
621

Marc G. Fournier's avatar
Marc G. Fournier committed
622 623
	return itvec;
}
624

Marc G. Fournier's avatar
Marc G. Fournier committed
625 626 627 628
/*
 * join two vectors into one
 */
static IndexTuple *
629 630 631 632
gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
{
	itvec = (IndexTuple *) repalloc((void *) itvec, sizeof(IndexTuple) * ((*len) + addlen));
	memmove(&itvec[*len], additvec, sizeof(IndexTuple) * addlen);
Marc G. Fournier's avatar
Marc G. Fournier committed
633 634
	*len += addlen;
	return itvec;
635 636
}

Marc G. Fournier's avatar
Marc G. Fournier committed
637 638 639 640
/*
 * return union of itup vector
 */
static IndexTuple
641 642 643 644 645 646 647 648 649
gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
{
	bytea	   *evec;
	char	   *datum;
	int			datumsize,
				i;
	GISTENTRY	centry;
	char		isnull;
	IndexTuple	newtup;
Marc G. Fournier's avatar
Marc G. Fournier committed
650 651 652 653

	evec = (bytea *) palloc(len * sizeof(GISTENTRY) + VARHDRSZ);
	VARATT_SIZEP(evec) = len * sizeof(GISTENTRY) + VARHDRSZ;

654
	for (i = 0; i < len; i++)
Marc G. Fournier's avatar
Marc G. Fournier committed
655
		gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[i],
656 657 658
					   (char *) itvec[i] + sizeof(IndexTupleData),
					   (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
					   IndexTupleSize((IndexTuple) itvec[i]) - sizeof(IndexTupleData), FALSE);
659

Marc G. Fournier's avatar
Marc G. Fournier committed
660 661
	datum = (char *)
		DatumGetPointer(FunctionCall2(&giststate->unionFn,
662 663 664 665 666 667 668 669
									  PointerGetDatum(evec),
									  PointerGetDatum(&datumsize)));

	for (i = 0; i < len; i++)
		if (((GISTENTRY *) VARDATA(evec))[i].pred &&
			((GISTENTRY *) VARDATA(evec))[i].pred !=
			((char *) (itvec[i]) + sizeof(IndexTupleData)))
			pfree(((GISTENTRY *) VARDATA(evec))[i].pred);
670

671
	pfree(evec);
672

673 674 675
	gistcentryinit(giststate, &centry, datum,
				   (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
				   datumsize, FALSE);
Marc G. Fournier's avatar
Marc G. Fournier committed
676 677

	isnull = (centry.pred) ? ' ' : 'n';
678
	newtup = (IndexTuple) index_formtuple(r->rd_att, (Datum *) &centry.pred, &isnull);
Marc G. Fournier's avatar
Marc G. Fournier committed
679
	if (centry.pred != datum)
680
		pfree(datum);
681

Marc G. Fournier's avatar
Marc G. Fournier committed
682
	return newtup;
683
}
684

Marc G. Fournier's avatar
Marc G. Fournier committed
685 686 687 688
/*
 * Forms union of oldtup and addtup, if union == oldtup then return NULL
 */
static IndexTuple
689 690 691 692 693 694 695 696 697 698 699 700
gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
{
	bytea	   *evec;
	char	   *datum;
	int			datumsize;
	bool		result;
	char		isnull;
	GISTENTRY	centry,
			   *ev0p,
			   *ev1p;
	IndexTuple	newtup = NULL;

701
	evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
Jan Wieck's avatar
TOAST  
Jan Wieck committed
702
	VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
703 704

	gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
705 706 707
			   (char *) oldtup + sizeof(IndexTupleData), (Relation) NULL,
				   (Page) NULL, (OffsetNumber) 0,
	IndexTupleSize((IndexTuple) oldtup) - sizeof(IndexTupleData), FALSE);
708 709
	ev0p = &((GISTENTRY *) VARDATA(evec))[0];

Marc G. Fournier's avatar
Marc G. Fournier committed
710
	gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[1],
711 712 713
			   (char *) addtup + sizeof(IndexTupleData), (Relation) NULL,
				   (Page) NULL, (OffsetNumber) 0,
	IndexTupleSize((IndexTuple) addtup) - sizeof(IndexTupleData), FALSE);
714 715
	ev1p = &((GISTENTRY *) VARDATA(evec))[1];

716 717
	datum = (char *)
		DatumGetPointer(FunctionCall2(&giststate->unionFn,
718 719
									  PointerGetDatum(evec),
									  PointerGetDatum(&datumsize)));
Marc G. Fournier's avatar
Marc G. Fournier committed
720

721 722 723 724
	if (!(ev0p->pred && ev1p->pred))
		result = (ev0p->pred == NULL && ev1p->pred == NULL);
	else
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
725
		FunctionCall3(&giststate->equalFn,
726 727 728
					  PointerGetDatum(ev0p->pred),
					  PointerGetDatum(datum),
					  PointerGetDatum(&result));
Marc G. Fournier's avatar
Marc G. Fournier committed
729
	}
730

731 732
	if (result)
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
733
		/* not need to update key */
734 735 736 737
		pfree(datum);
	}
	else
	{
738
		gistcentryinit(giststate, &centry, datum, ev0p->rel, ev0p->page,
739
					   ev0p->offset, datumsize, FALSE);
740

Marc G. Fournier's avatar
Marc G. Fournier committed
741
		isnull = (centry.pred) ? ' ' : 'n';
742 743
		newtup = (IndexTuple) index_formtuple(r->rd_att, (Datum *) &centry.pred, &isnull);
		newtup->t_tid = oldtup->t_tid;
744
		if (centry.pred != datum)
745
			pfree(datum);
746 747
	}

748 749 750 751 752 753 754
	if (ev0p->pred &&
		ev0p->pred != (char *) oldtup + sizeof(IndexTupleData))
		pfree(ev0p->pred);
	if (ev1p->pred &&
		ev1p->pred != (char *) addtup + sizeof(IndexTupleData))
		pfree(ev1p->pred);
	pfree(evec);
Marc G. Fournier's avatar
Marc G. Fournier committed
755

756
	return newtup;
Marc G. Fournier's avatar
Marc G. Fournier committed
757
}
758

759
/*
760
 *	gistSplit -- split a page in the tree.
761
 */
Marc G. Fournier's avatar
Marc G. Fournier committed
762
static IndexTuple *
763
gistSplit(Relation r,
764
		  Buffer buffer,
Marc G. Fournier's avatar
Marc G. Fournier committed
765 766 767 768
		  IndexTuple *itup,		/* contains compressed entry */
		  int *len,
		  GISTSTATE *giststate,
		  InsertIndexResult *res)
769
{
770
	Page		p;
771 772 773 774 775 776 777 778 779 780 781 782 783
	Buffer		leftbuf,
				rightbuf;
	Page		left,
				right;
	OffsetNumber *spl_left,
			   *spl_right;
	IndexTuple *lvectup,
			   *rvectup,
			   *newtup;
	int			leftoff,
				rightoff;
	BlockNumber lbknum,
				rbknum;
784
	GISTPageOpaque opaque;
785
	char		isnull;
786 787 788
	GIST_SPLITVEC v;
	bytea	   *entryvec;
	bool	   *decompvec;
Marc G. Fournier's avatar
Marc G. Fournier committed
789
	GISTENTRY	tmpentry;
790 791
	int			i,
				nlen;
792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808

	p = (Page) BufferGetPage(buffer);
	opaque = (GISTPageOpaque) 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) == GISTP_ROOT)
	{
		leftbuf = ReadBuffer(r, P_NEW);
		GISTInitBuffer(leftbuf, opaque->flags);
		lbknum = BufferGetBlockNumber(leftbuf);
		left = (Page) BufferGetPage(leftbuf);
809
	}
810 811 812 813 814 815 816 817 818 819 820 821 822 823
	else
	{
		leftbuf = buffer;
		IncrBufferRefCount(buffer);
		lbknum = BufferGetBlockNumber(buffer);
		left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
	}

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

	/* generate the item array */
824 825 826
	entryvec = (bytea *) palloc(VARHDRSZ + (*len + 1) * sizeof(GISTENTRY));
	decompvec = (bool *) palloc(VARHDRSZ + (*len + 1) * sizeof(bool));
	VARATT_SIZEP(entryvec) = (*len + 1) * sizeof(GISTENTRY) + VARHDRSZ;
Marc G. Fournier's avatar
Marc G. Fournier committed
827
	for (i = 1; i <= *len; i++)
828 829
	{
		gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
830
					   (((char *) itup[i - 1]) + sizeof(IndexTupleData)),
831
					   r, p, i,
832
			IndexTupleSize(itup[i - 1]) - sizeof(IndexTupleData), FALSE);
833
		if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
834
			== (((char *) itup[i - 1]) + sizeof(IndexTupleData)))
835 836 837 838 839 840
			decompvec[i] = FALSE;
		else
			decompvec[i] = TRUE;
	}

	/* now let the user-defined picksplit function set up the split vector */
841
	FunctionCall2(&giststate->picksplitFn,
842 843
				  PointerGetDatum(entryvec),
				  PointerGetDatum(&v));
844 845

	/* clean up the entry vector: its preds need to be deleted, too */
Marc G. Fournier's avatar
Marc G. Fournier committed
846 847
	for (i = 1; i <= *len; i++)
		if (decompvec[i] && ((GISTENTRY *) VARDATA(entryvec))[i].pred)
848 849 850 851
			pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
	pfree(entryvec);
	pfree(decompvec);

852 853 854
	spl_left = v.spl_left;
	spl_right = v.spl_right;

Marc G. Fournier's avatar
Marc G. Fournier committed
855
	/* form left and right vector */
856 857
	lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nleft);
	rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nright);
Marc G. Fournier's avatar
Marc G. Fournier committed
858
	leftoff = rightoff = 0;
859 860 861 862 863
	for (i = 1; i <= *len; i++)
	{
		if (i == *(spl_left) || (i == *len && *(spl_left) != FirstOffsetNumber))
		{
			lvectup[leftoff++] = itup[i - 1];
Marc G. Fournier's avatar
Marc G. Fournier committed
864
			spl_left++;
865 866 867 868
		}
		else
		{
			rvectup[rightoff++] = itup[i - 1];
Marc G. Fournier's avatar
Marc G. Fournier committed
869
			spl_right++;
870 871 872
		}
	}

Marc G. Fournier's avatar
Marc G. Fournier committed
873
	/* write on disk (may be need another split) */
874 875
	if (gistnospace(right, rvectup, v.spl_nright))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
876
		nlen = v.spl_nright;
877 878 879 880 881 882
		newtup = gistSplit(r, rightbuf, rvectup, &nlen, giststate,
			  (res && rvectup[nlen - 1] == itup[*len - 1]) ? res : NULL);
		ReleaseBuffer(rightbuf);
	}
	else
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
883
		OffsetNumber l;
884 885

		l = gistwritebuffer(r, right, rvectup, v.spl_nright, FirstOffsetNumber, giststate);
Marc G. Fournier's avatar
Marc G. Fournier committed
886 887
		WriteBuffer(rightbuf);

888
		if (res)
Marc G. Fournier's avatar
Marc G. Fournier committed
889 890 891 892 893 894 895 896 897
			ItemPointerSet(&((*res)->pointerData), rbknum, l);
		gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
					   (Page) NULL, (OffsetNumber) 0,
					   -1, FALSE);
		if (v.spl_rdatum != tmpentry.pred)
			pfree(v.spl_rdatum);
		v.spl_rdatum = tmpentry.pred;

		nlen = 1;
898 899
		newtup = (IndexTuple *) palloc(sizeof(IndexTuple) * 1);
		isnull = (v.spl_rdatum) ? ' ' : 'n';
Marc G. Fournier's avatar
Marc G. Fournier committed
900 901
		newtup[0] = (IndexTuple) index_formtuple(r->rd_att, (Datum *) &(v.spl_rdatum), &isnull);
		ItemPointerSet(&(newtup[0]->t_tid), rbknum, 1);
902 903
	}

904 905 906
	if (gistnospace(left, lvectup, v.spl_nleft))
	{
		int			llen = v.spl_nleft;
Marc G. Fournier's avatar
Marc G. Fournier committed
907 908
		IndexTuple *lntup;

909 910 911
		lntup = gistSplit(r, leftbuf, lvectup, &llen, giststate,
			  (res && lvectup[llen - 1] == itup[*len - 1]) ? res : NULL);
		ReleaseBuffer(leftbuf);
Marc G. Fournier's avatar
Marc G. Fournier committed
912

913 914 915 916 917
		newtup = gistjoinvector(newtup, &nlen, lntup, llen);
		pfree(lntup);
	}
	else
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
918
		OffsetNumber l;
919 920 921

		l = gistwritebuffer(r, left, lvectup, v.spl_nleft, FirstOffsetNumber, giststate);
		if (BufferGetBlockNumber(buffer) != GISTP_ROOT)
Marc G. Fournier's avatar
Marc G. Fournier committed
922 923 924 925
			PageRestoreTempPage(left, p);

		WriteBuffer(leftbuf);

926
		if (res)
Marc G. Fournier's avatar
Marc G. Fournier committed
927 928 929 930 931 932 933 934 935
			ItemPointerSet(&((*res)->pointerData), lbknum, l);
		gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
					   (Page) NULL, (OffsetNumber) 0,
					   -1, FALSE);
		if (v.spl_ldatum != tmpentry.pred)
			pfree(v.spl_ldatum);
		v.spl_ldatum = tmpentry.pred;

		nlen += 1;
936 937 938 939
		newtup = (IndexTuple *) repalloc((void *) newtup, sizeof(IndexTuple) * nlen);
		isnull = (v.spl_ldatum) ? ' ' : 'n';
		newtup[nlen - 1] = (IndexTuple) index_formtuple(r->rd_att, (Datum *) &(v.spl_ldatum), &isnull);
		ItemPointerSet(&(newtup[nlen - 1]->t_tid), lbknum, 1);
940 941
	}

942

Marc G. Fournier's avatar
Marc G. Fournier committed
943 944
	/* adjust active scans */
	gistadjscans(r, GISTOP_SPLIT, BufferGetBlockNumber(buffer), FirstOffsetNumber);
945

Marc G. Fournier's avatar
Marc G. Fournier committed
946
	/* !!! pfree */
947 948 949 950
	pfree(rvectup);
	pfree(lvectup);
	pfree(v.spl_left);
	pfree(v.spl_right);
951

Marc G. Fournier's avatar
Marc G. Fournier committed
952 953
	*len = nlen;
	return newtup;
954
}
955 956

static void
Marc G. Fournier's avatar
Marc G. Fournier committed
957
gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple *itup, int len)
958
{
959 960
	Buffer		b;
	Page		p;
961 962 963 964

	b = ReadBuffer(r, GISTP_ROOT);
	GISTInitBuffer(b, 0);
	p = BufferGetPage(b);
965 966

	gistwritebuffer(r, p, itup, len, FirstOffsetNumber, giststate);
967
	WriteBuffer(b);
968 969 970 971 972
}

static void
GISTInitBuffer(Buffer b, uint32 f)
{
973 974 975
	GISTPageOpaque opaque;
	Page		page;
	Size		pageSize;
976 977 978 979

	pageSize = BufferGetPageSize(b);

	page = BufferGetPage(b);
Bruce Momjian's avatar
Bruce Momjian committed
980
	MemSet(page, 0, (int) pageSize);
981 982 983 984
	PageInit(page, pageSize, sizeof(GISTPageOpaqueData));

	opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
	opaque->flags = f;
985 986 987 988 989 990
}


/*
** find entry with lowest penalty
*/
991
static OffsetNumber
992
gistchoose(Relation r, Page p, IndexTuple it,	/* it has compressed entry */
993
		   GISTSTATE *giststate)
994
{
995 996 997 998 999 1000 1001 1002 1003 1004 1005
	OffsetNumber maxoff;
	OffsetNumber i;
	char	   *id;
	char	   *datum;
	float		usize;
	OffsetNumber which;
	float		which_grow;
	GISTENTRY	entry,
				identry;
	int			size,
				idsize;
1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021

	idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
	id = ((char *) it) + sizeof(IndexTupleData);
	maxoff = PageGetMaxOffsetNumber(p);
	which_grow = -1.0;
	which = -1;

	gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
				   (OffsetNumber) 0, idsize, FALSE);

	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
	{
		datum = (char *) PageGetItem(p, PageGetItemId(p, i));
		size = IndexTupleSize(datum) - sizeof(IndexTupleData);
		datum += sizeof(IndexTupleData);
		gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1022 1023 1024 1025
		FunctionCall3(&giststate->penaltyFn,
					  PointerGetDatum(&entry),
					  PointerGetDatum(&identry),
					  PointerGetDatum(&usize));
1026 1027 1028 1029 1030 1031 1032
		if (which_grow < 0 || usize < which_grow)
		{
			which = i;
			which_grow = usize;
			if (which_grow == 0)
				break;
		}
Marc G. Fournier's avatar
Marc G. Fournier committed
1033
		if (entry.pred && entry.pred != datum)
1034
			pfree(entry.pred);
1035
	}
Marc G. Fournier's avatar
Marc G. Fournier committed
1036
	if (identry.pred && identry.pred != id)
1037 1038
		pfree(identry.pred);

1039
	return which;
1040 1041 1042
}

void
1043
gistfreestack(GISTSTACK *s)
1044
{
1045
	GISTSTACK  *p;
1046 1047 1048 1049 1050 1051 1052

	while (s != (GISTSTACK *) NULL)
	{
		p = s->gs_parent;
		pfree(s);
		s = p;
	}
1053 1054 1055
}


1056 1057
/*
** remove an entry from a page
1058
*/
1059 1060
Datum
gistdelete(PG_FUNCTION_ARGS)
1061
{
1062 1063
	Relation	r = (Relation) PG_GETARG_POINTER(0);
	ItemPointer tid = (ItemPointer) PG_GETARG_POINTER(1);
1064 1065 1066 1067
	BlockNumber blkno;
	OffsetNumber offnum;
	Buffer		buf;
	Page		page;
1068

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
1069
	/*
Bruce Momjian's avatar
Bruce Momjian committed
1070 1071
	 * Notes in ExecUtils:ExecOpenIndices() Also note that only vacuum
	 * deletes index tuples now...
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
1072
	 *
Bruce Momjian's avatar
Bruce Momjian committed
1073
	 * RelationSetLockForWrite(r);
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
1074
	 */
1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089

	blkno = ItemPointerGetBlockNumber(tid);
	offnum = ItemPointerGetOffsetNumber(tid);

	/* adjust any scans that will be affected by this deletion */
	gistadjscans(r, GISTOP_DEL, blkno, offnum);

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

	PageIndexTupleDelete(page, offnum);

	WriteBuffer(buf);

1090
	PG_RETURN_VOID();
1091 1092
}

1093
void
1094
initGISTstate(GISTSTATE *giststate, Relation index)
1095
{
1096 1097 1098 1099 1100 1101 1102 1103
	RegProcedure consistent_proc,
				union_proc,
				compress_proc,
				decompress_proc;
	RegProcedure penalty_proc,
				picksplit_proc,
				equal_proc;
	HeapTuple	htup;
1104
	Form_pg_index itupform;
1105
	Oid			indexrelid;
1106 1107 1108 1109 1110 1111 1112 1113

	consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
	union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
	compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
	decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
	penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
	picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
	equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1114 1115 1116 1117 1118 1119 1120
	fmgr_info(consistent_proc, &giststate->consistentFn);
	fmgr_info(union_proc, &giststate->unionFn);
	fmgr_info(compress_proc, &giststate->compressFn);
	fmgr_info(decompress_proc, &giststate->decompressFn);
	fmgr_info(penalty_proc, &giststate->penaltyFn);
	fmgr_info(picksplit_proc, &giststate->picksplitFn);
	fmgr_info(equal_proc, &giststate->equalFn);
1121 1122

	/* see if key type is different from type of attribute being indexed */
1123 1124 1125
	htup = SearchSysCache(INDEXRELID,
						  ObjectIdGetDatum(RelationGetRelid(index)),
						  0, 0, 0);
1126
	if (!HeapTupleIsValid(htup))
1127
		elog(ERROR, "initGISTstate: index %u not found",
1128
			 RelationGetRelid(index));
1129
	itupform = (Form_pg_index) GETSTRUCT(htup);
1130
	giststate->haskeytype = itupform->indhaskeytype;
1131 1132 1133
	indexrelid = itupform->indexrelid;
	ReleaseSysCache(htup);

1134 1135 1136
	if (giststate->haskeytype)
	{
		/* key type is different -- is it byval? */
1137 1138 1139 1140
		htup = SearchSysCache(ATTNUM,
							  ObjectIdGetDatum(indexrelid),
							  UInt16GetDatum(FirstOffsetNumber),
							  0, 0);
1141
		if (!HeapTupleIsValid(htup))
1142
			elog(ERROR, "initGISTstate: no attribute tuple %u %d",
1143
				 indexrelid, FirstOffsetNumber);
1144
		giststate->keytypbyval = (((Form_pg_attribute) htup)->attbyval);
1145
		ReleaseSysCache(htup);
1146
	}
1147 1148
	else
		giststate->keytypbyval = FALSE;
1149 1150 1151 1152 1153 1154 1155 1156
}


/*
** Given an IndexTuple to be inserted on a page, this routine replaces
** the key with another key, which may involve generating a new IndexTuple
** if the sizes don't match
*/
1157
static IndexTuple
1158 1159
gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
{
1160
	char	   *datum = (((char *) t) + sizeof(IndexTupleData));
1161 1162

	/* if new entry fits in index tuple, copy it in */
1163
	if ((Size) entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData) || (Size) entry.bytes == 0)
1164 1165 1166
	{
		memcpy(datum, entry.pred, entry.bytes);
		/* clear out old size */
1167
		t->t_info &= ~INDEX_SIZE_MASK;
1168 1169 1170
		/* or in new size */
		t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));

1171
		return t;
1172 1173 1174 1175
	}
	else
	{
		/* generate a new index tuple for the compressed entry */
1176 1177
		TupleDesc	tupDesc = r->rd_att;
		IndexTuple	newtup;
1178
		char		isnull;
1179

1180
		isnull = (entry.pred) ? ' ' : 'n';
1181
		newtup = (IndexTuple) index_formtuple(tupDesc,
1182
											  (Datum *) &(entry.pred),
Marc G. Fournier's avatar
Marc G. Fournier committed
1183
											  &isnull);
1184
		newtup->t_tid = t->t_tid;
1185
		return newtup;
1186
	}
1187
}
1188

1189 1190 1191 1192 1193

/*
** initialize a GiST entry with a decompressed version of pred
*/
void
1194
gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1195 1196
			   Page pg, OffsetNumber o, int b, bool l)
{
1197
	GISTENTRY  *dep;
1198 1199 1200 1201

	gistentryinit(*e, pr, r, pg, o, b, l);
	if (giststate->haskeytype)
	{
1202 1203 1204
		if ( b ) {
			dep = (GISTENTRY *)
				DatumGetPointer(FunctionCall1(&giststate->decompressFn,
1205
										  PointerGetDatum(e)));
1206
			gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1207
					  dep->leafkey);
1208 1209 1210 1211 1212
			if (dep != e)
				pfree(dep);
		} else {
			gistentryinit(*e, (char*)NULL, r, pg, o, 0, l);
		}
1213
	}
1214 1215 1216 1217 1218 1219
}


/*
** initialize a GiST entry with a compressed version of pred
*/
1220
static void
1221
gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1222 1223
			   Page pg, OffsetNumber o, int b, bool l)
{
1224
	GISTENTRY  *cep;
1225 1226 1227 1228

	gistentryinit(*e, pr, r, pg, o, b, l);
	if (giststate->haskeytype)
	{
1229 1230 1231
		cep = (GISTENTRY *)
			DatumGetPointer(FunctionCall1(&giststate->compressFn,
										  PointerGetDatum(e)));
1232 1233 1234 1235 1236
		gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
					  cep->leafkey);
		if (cep != e)
			pfree(cep);
	}
1237
}
1238

1239
#ifdef GISTDEBUG
Marc G. Fournier's avatar
Marc G. Fournier committed
1240 1241
static void
gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff)
1242
{
Marc G. Fournier's avatar
Marc G. Fournier committed
1243
	Buffer		buffer;
1244
	Page		page;
Marc G. Fournier's avatar
Marc G. Fournier committed
1245 1246
	GISTPageOpaque opaque;
	IndexTuple	which;
1247 1248 1249 1250 1251
	ItemId		iid;
	OffsetNumber i,
				maxoff;
	BlockNumber cblk;
	char	   *pred;
1252

1253
	pred = (char *) palloc(sizeof(char) * level + 1);
Marc G. Fournier's avatar
Marc G. Fournier committed
1254
	MemSet(pred, '\t', level);
1255
	pred[level] = '\0';
1256

Marc G. Fournier's avatar
Marc G. Fournier committed
1257 1258 1259
	buffer = ReadBuffer(r, blk);
	page = (Page) BufferGetPage(buffer);
	opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1260 1261 1262 1263 1264 1265 1266

	maxoff = PageGetMaxOffsetNumber(page);

	elog(NOTICE, "%sPage: %d %s blk: %d maxoff: %d free: %d", pred, coff, (opaque->flags & F_LEAF) ? "LEAF" : "INTE", (int) blk, (int) maxoff, PageGetFreeSpace(page));

	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
1267 1268 1269
		iid = PageGetItemId(page, i);
		which = (IndexTuple) PageGetItem(page, iid);
		cblk = ItemPointerGetBlockNumber(&(which->t_tid));
1270 1271 1272 1273 1274 1275
#ifdef PRINTTUPLE
		elog(NOTICE, "%s  Tuple. blk: %d size: %d", pred, (int) cblk, IndexTupleSize(which));
#endif

		if (!(opaque->flags & F_LEAF))
			gist_dumptree(r, level + 1, cblk, i);
1276
	}
Marc G. Fournier's avatar
Marc G. Fournier committed
1277 1278
	ReleaseBuffer(buffer);
	pfree(pred);
1279
}
1280

1281
#endif	 /* defined GISTDEBUG */
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1282 1283 1284 1285 1286 1287

void
gist_redo(XLogRecPtr lsn, XLogRecord *record)
{
	elog(STOP, "gist_redo: unimplemented");
}
1288

Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1289 1290 1291 1292 1293
void
gist_undo(XLogRecPtr lsn, XLogRecord *record)
{
	elog(STOP, "gist_undo: unimplemented");
}
1294

Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1295
void
1296
gist_desc(char *buf, uint8 xl_info, char *rec)
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1297 1298
{
}