gist.c 43.3 KB
Newer Older
1 2
/*-------------------------------------------------------------------------
 *
3
 * gist.c
4
 *	  interface routines for the postgres GiST index access method.
5 6
 *
 *
7
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
8
 * Portions Copyright (c) 1994, Regents of the University of California
9 10
 *
 * IDENTIFICATION
11
 *	  $PostgreSQL: pgsql/src/backend/access/gist/gist.c,v 1.117 2005/05/17 03:34:18 neilc Exp $
12 13 14
 *
 *-------------------------------------------------------------------------
 */
15
#include "postgres.h"
16

17
#include "access/genam.h"
18
#include "access/gist_private.h"
19 20 21
#include "access/gistscan.h"
#include "access/heapam.h"
#include "catalog/index.h"
22
#include "commands/vacuum.h"
23
#include "miscadmin.h"
Neil Conway's avatar
Neil Conway committed
24
#include "utils/memutils.h"
25

26

27 28
#undef GIST_PAGEADDITEM

29
#define ATTSIZE(datum, tupdesc, i, isnull) \
30
	( \
31
		(isnull) ? 0 : \
32
			att_addlength(0, (tupdesc)->attrs[(i)-1]->attlen, (datum)) \
33 34
	)

35
/* result's status */
Marc G. Fournier's avatar
Marc G. Fournier committed
36 37 38
#define INSERTED	0x01
#define SPLITED		0x02

39 40
/* group flags ( in gistSplit ) */
#define LEFT_ADDED	0x01
41
#define RIGHT_ADDED 0x02
42 43
#define BOTH_ADDED	( LEFT_ADDED | RIGHT_ADDED )

44 45 46 47
/*
 * This defines only for shorter code, used in gistgetadjusted
 * and gistadjsubkey only
 */
48
#define FILLITEM(evp, isnullkey, okey, okeyb, rkey, rkeyb)	 do { \
Neil Conway's avatar
Neil Conway committed
49 50 51 52 53 54 55
	if (isnullkey) {											  \
		gistentryinit((evp), rkey, r, NULL,						  \
					  (OffsetNumber) 0, rkeyb, FALSE);			  \
	} else {													  \
		gistentryinit((evp), okey, r, NULL,						  \
					  (OffsetNumber) 0, okeyb, FALSE);			  \
	}															  \
56 57 58
} while(0)

#define FILLEV(isnull1, key1, key1b, isnull2, key2, key2b) do { \
59 60
	FILLITEM(*ev0p, isnull1, key1, key1b, key2, key2b);		\
	FILLITEM(*ev1p, isnull2, key2, key2b, key1, key1b);		\
61
} while(0);
62 63 64 65 66 67 68

/* Working state for gistbuild and its callback */
typedef struct
{
	GISTSTATE	giststate;
	int			numindexattrs;
	double		indtuples;
Neil Conway's avatar
Neil Conway committed
69
	MemoryContext tmpCxt;
70 71 72
} GISTBuildState;


73
/* non-export function prototypes */
74
static void gistbuildCallback(Relation index,
75
				  HeapTuple htup,
76 77
				  Datum *values,
				  bool *isnull,
78 79
				  bool tupleIsAlive,
				  void *state);
80 81 82 83 84 85 86 87 88 89 90
static void gistdoinsert(Relation r,
			 IndexTuple itup,
			 GISTSTATE *GISTstate);
static int gistlayerinsert(Relation r, BlockNumber blkno,
				IndexTuple **itup,
				int *len,
				GISTSTATE *giststate);
static OffsetNumber gistwritebuffer(Relation r,
				Page page,
				IndexTuple *itup,
				int len,
91
				OffsetNumber off);
92
static bool gistnospace(Page page, IndexTuple *itvec, int len);
93
static IndexTuple *gistreadbuffer(Buffer buffer, int *len);
94 95 96 97 98
static IndexTuple *gistjoinvector(
			   IndexTuple *itvec, int *len,
			   IndexTuple *additvec, int addlen);
static IndexTuple gistunion(Relation r, IndexTuple *itvec,
		  int len, GISTSTATE *giststate);
99

100 101 102 103
static IndexTuple gistgetadjusted(Relation r,
				IndexTuple oldtup,
				IndexTuple addtup,
				GISTSTATE *giststate);
104 105
static int gistfindgroup(GISTSTATE *giststate,
			  GISTENTRY *valvec, GIST_SPLITVEC *spl);
106
static void gistadjsubkey(Relation r,
107 108 109 110
			  IndexTuple *itup, int *len,
			  GIST_SPLITVEC *v,
			  GISTSTATE *giststate);
static IndexTuple gistFormTuple(GISTSTATE *giststate,
111
			Relation r, Datum *attdata, int *datumsize, bool *isnull);
112 113 114 115
static IndexTuple *gistSplit(Relation r,
		  Buffer buffer,
		  IndexTuple *itup,
		  int *len,
116
		  GISTSTATE *giststate);
117
static void gistnewroot(Relation r, IndexTuple *itup, int len);
118
static void GISTInitBuffer(Buffer b, uint32 f);
119 120 121
static OffsetNumber gistchoose(Relation r, Page p,
		   IndexTuple it,
		   GISTSTATE *giststate);
122
static void gistdelete(Relation r, ItemPointer tid);
123

124
#ifdef GIST_PAGEADDITEM
125 126
static IndexTuple gist_tuple_replacekey(Relation r,
					  GISTENTRY entry, IndexTuple t);
127 128 129
#endif
static void gistcentryinit(GISTSTATE *giststate, int nkey,
			   GISTENTRY *e, Datum k,
130
			   Relation r, Page pg,
131
			   OffsetNumber o, int b, bool l, bool isNull);
132
static void gistDeCompressAtt(GISTSTATE *giststate, Relation r,
Neil Conway's avatar
Neil Conway committed
133 134
							  IndexTuple tuple, Page p, OffsetNumber o,
							  GISTENTRY *attdata, bool *isnull);
135
static void gistpenalty(GISTSTATE *giststate, int attno,
136
			GISTENTRY *key1, bool isNull1,
137 138 139
			GISTENTRY *key2, bool isNull2,
			float *penalty);

Marc G. Fournier's avatar
Marc G. Fournier committed
140
#undef GISTDEBUG
141

142
#ifdef GISTDEBUG
Marc G. Fournier's avatar
Marc G. Fournier committed
143
static void gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff);
144
#endif
145 146

/*
Neil Conway's avatar
Neil Conway committed
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
 * Create and return a temporary memory context for use by GiST. We
 * _always_ invoke user-provided methods in a temporary memory
 * context, so that memory leaks in those functions cannot cause
 * problems. Also, we use some additional temporary contexts in the
 * GiST code itself, to avoid the need to do some awkward manual
 * memory management.
 */
MemoryContext                                                                                 
createTempGistContext(void)                                                                   
{                                                                                             
    return AllocSetContextCreate(CurrentMemoryContext,                                        
                                 "GiST temporary context",                                    
                                 ALLOCSET_DEFAULT_MINSIZE,                                    
                                 ALLOCSET_DEFAULT_INITSIZE,                                   
                                 ALLOCSET_DEFAULT_MAXSIZE);                                   
}                                                                                             

/*
 * Routine to build an index.  Basically calls insert over and over.
 *
 * XXX: it would be nice to implement some sort of bulk-loading
 * algorithm, but it is not clear how to do that.
169
 */
170 171
Datum
gistbuild(PG_FUNCTION_ARGS)
172
{
173 174 175
	Relation	heap = (Relation) PG_GETARG_POINTER(0);
	Relation	index = (Relation) PG_GETARG_POINTER(1);
	IndexInfo  *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
176 177 178
	double		reltuples;
	GISTBuildState buildstate;
	Buffer		buffer;
179 180 181 182 183

	/*
	 * We expect to be called exactly once for any index relation. If
	 * that's not the case, big trouble's what we have.
	 */
184
	if (RelationGetNumberOfBlocks(index) != 0)
185
		elog(ERROR, "index \"%s\" already contains data",
186
			 RelationGetRelationName(index));
187

Neil Conway's avatar
Neil Conway committed
188 189 190
	/* no locking is needed */
	initGISTstate(&buildstate.giststate, index);

191 192 193 194
	/* initialize the root page */
	buffer = ReadBuffer(index, P_NEW);
	GISTInitBuffer(buffer, F_LEAF);
	WriteBuffer(buffer);
195

196
	/* build the index */
197 198
	buildstate.numindexattrs = indexInfo->ii_NumIndexAttrs;
	buildstate.indtuples = 0;
Neil Conway's avatar
Neil Conway committed
199 200 201 202 203
	/*
	 * create a temporary memory context that is reset once for each
	 * tuple inserted into the index
	 */
	buildstate.tmpCxt = createTempGistContext();
204

205 206
	/* do the heap scan */
	reltuples = IndexBuildHeapScan(heap, index, indexInfo,
Neil Conway's avatar
Neil Conway committed
207
								   gistbuildCallback, (void *) &buildstate);
208 209

	/* okay, all heap tuples are indexed */
Neil Conway's avatar
Neil Conway committed
210
	MemoryContextDelete(buildstate.tmpCxt);
211

212 213
	/* since we just counted the # of tuples, may as well update stats */
	IndexCloseAndUpdateStats(heap, reltuples, index, buildstate.indtuples);
214

215
	freeGISTstate(&buildstate.giststate);
Neil Conway's avatar
Neil Conway committed
216

Marc G. Fournier's avatar
Marc G. Fournier committed
217
#ifdef GISTDEBUG
Neil Conway's avatar
Neil Conway committed
218
	gist_dumptree(index, 0, GIST_ROOT_BLKNO, 0);
Marc G. Fournier's avatar
Marc G. Fournier committed
219
#endif
220
	PG_RETURN_VOID();
221 222
}

223 224 225 226 227 228
/*
 * Per-tuple callback from IndexBuildHeapScan
 */
static void
gistbuildCallback(Relation index,
				  HeapTuple htup,
229 230
				  Datum *values,
				  bool *isnull,
231 232 233
				  bool tupleIsAlive,
				  void *state)
{
234
	GISTBuildState *buildstate = (GISTBuildState *) state;
235 236 237
	IndexTuple	itup;
	GISTENTRY	tmpcentry;
	int			i;
Neil Conway's avatar
Neil Conway committed
238
	MemoryContext oldCxt;
239

240
	/* GiST cannot index tuples with leading NULLs */
241
	if (isnull[0])
242
		return;
243

Neil Conway's avatar
Neil Conway committed
244 245
	oldCxt = MemoryContextSwitchTo(buildstate->tmpCxt);

246 247 248
	/* immediately compress keys to normalize */
	for (i = 0; i < buildstate->numindexattrs; i++)
	{
249 250
		if (isnull[i])
			values[i] = (Datum) 0;
251 252
		else
		{
253
			gistcentryinit(&buildstate->giststate, i, &tmpcentry, values[i],
254
						   NULL, NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
255
						   -1 /* size is currently bogus */, TRUE, FALSE);
256
			values[i] = tmpcentry.key;
257
		}
258 259 260
	}

	/* form an index tuple and point it at the heap tuple */
261
	itup = index_form_tuple(buildstate->giststate.tupdesc, values, isnull);
262 263
	itup->t_tid = htup->t_self;

264 265
	/*
	 * Since we already have the index relation locked, we call
266 267 268 269
	 * 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.
270
	 */
271
	gistdoinsert(index, itup, &buildstate->giststate);
272

273
	buildstate->indtuples += 1;
Neil Conway's avatar
Neil Conway committed
274 275
	MemoryContextSwitchTo(oldCxt);
	MemoryContextReset(buildstate->tmpCxt);
276 277
}

278
/*
279
 *	gistinsert -- wrapper for GiST tuple insertion.
280
 *
281 282
 *	  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.
283
 */
284 285
Datum
gistinsert(PG_FUNCTION_ARGS)
286
{
287
	Relation	r = (Relation) PG_GETARG_POINTER(0);
288 289
	Datum	   *values = (Datum *) PG_GETARG_POINTER(1);
	bool	   *isnull = (bool *) PG_GETARG_POINTER(2);
290
	ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);
291
#ifdef NOT_USED
292
	Relation	heapRel = (Relation) PG_GETARG_POINTER(4);
293
	bool		checkUnique = PG_GETARG_BOOL(5);
294
#endif
295 296 297 298
	IndexTuple	itup;
	GISTSTATE	giststate;
	GISTENTRY	tmpentry;
	int			i;
Neil Conway's avatar
Neil Conway committed
299 300
	MemoryContext oldCxt;
	MemoryContext insertCxt;
301 302 303

	/*
	 * Since GIST is not marked "amconcurrent" in pg_am, caller should
304
	 * have acquired exclusive lock on index relation.	We need no locking
305 306
	 * here.
	 */
307

308
	/* GiST cannot index tuples with leading NULLs */
309 310
	if (isnull[0])
		PG_RETURN_BOOL(false);
311

Neil Conway's avatar
Neil Conway committed
312 313 314
	insertCxt = createTempGistContext();
	oldCxt = MemoryContextSwitchTo(insertCxt);

315 316 317 318 319
	initGISTstate(&giststate, r);

	/* immediately compress keys to normalize */
	for (i = 0; i < r->rd_att->natts; i++)
	{
320 321
		if (isnull[i])
			values[i] = (Datum) 0;
322 323
		else
		{
324
			gistcentryinit(&giststate, i, &tmpentry, values[i],
325
						   NULL, NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
326
						   -1 /* size is currently bogus */, TRUE, FALSE);
327
			values[i] = tmpentry.key;
328
		}
329
	}
330
	itup = index_form_tuple(giststate.tupdesc, values, isnull);
331 332
	itup->t_tid = *ht_ctid;

333
	gistdoinsert(r, itup, &giststate);
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
334

Neil Conway's avatar
Neil Conway committed
335
	/* cleanup */
336
	freeGISTstate(&giststate);
Neil Conway's avatar
Neil Conway committed
337 338
	MemoryContextSwitchTo(oldCxt);
	MemoryContextDelete(insertCxt);
339

340
	PG_RETURN_BOOL(true);
341 342
}

343
#ifdef GIST_PAGEADDITEM
344
/*
345 346 347 348 349
 * 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.)
 */
350
static OffsetNumber
351
gistPageAddItem(GISTSTATE *giststate,
352 353 354 355 356 357
				Relation r,
				Page page,
				Item item,
				Size size,
				OffsetNumber offsetNumber,
				ItemIdFlags flags,
358 359
				GISTENTRY *dentry,
				IndexTuple *newtup)
360
{
361 362
	GISTENTRY	tmpcentry;
	IndexTuple	itup = (IndexTuple) item;
363
	OffsetNumber retval;
364 365
	Datum		datum;
	bool		IsNull;
366 367 368 369 370

	/*
	 * recompress the item given that we now know the exact page and
	 * offset for insertion
	 */
371
	datum = index_getattr(itup, 1, r->rd_att, &IsNull);
372
	gistdentryinit(giststate, 0, dentry, datum,
373 374
				   (Relation) 0, (Page) 0,
				   (OffsetNumber) InvalidOffsetNumber,
375
				   ATTSIZE(datum, r, 1, IsNull),
376
				   FALSE, IsNull);
377
	gistcentryinit(giststate, 0, &tmpcentry, dentry->key, r, page,
378
				   offsetNumber, dentry->bytes, FALSE);
Marc G. Fournier's avatar
Marc G. Fournier committed
379 380
	*newtup = gist_tuple_replacekey(r, tmpcentry, itup);
	retval = PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
381
						 offsetNumber, flags);
382
	if (retval == InvalidOffsetNumber)
383
		elog(ERROR, "failed to add index item to \"%s\"",
384
			 RelationGetRelationName(r));
Neil Conway's avatar
Neil Conway committed
385
	return retval;
386
}
387
#endif
388

Neil Conway's avatar
Neil Conway committed
389 390 391 392 393
/*
 * Workhouse routine for doing insertion into a GiST index. Note that
 * this routine assumes it is invoked in a short-lived memory context,
 * so it does not bother releasing palloc'd allocations.
 */
394
static void
Neil Conway's avatar
Neil Conway committed
395
gistdoinsert(Relation r, IndexTuple itup, GISTSTATE *giststate)
396
{
Marc G. Fournier's avatar
Marc G. Fournier committed
397
	IndexTuple *instup;
Neil Conway's avatar
Neil Conway committed
398
	int			ret,
399 400 401 402 403
				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
404

Neil Conway's avatar
Neil Conway committed
405
	ret = gistlayerinsert(r, GIST_ROOT_BLKNO, &instup, &len, giststate);
406
	if (ret & SPLITED)
407
		gistnewroot(r, instup, len);
Marc G. Fournier's avatar
Marc G. Fournier committed
408
}
409

Marc G. Fournier's avatar
Marc G. Fournier committed
410
static int
411 412 413 414 415 416 417 418
gistlayerinsert(Relation r, BlockNumber blkno,
				IndexTuple **itup,		/* in - out, has compressed entry */
				int *len,		/* in - out */
				GISTSTATE *giststate)
{
	Buffer		buffer;
	Page		page;
	int			ret;
Marc G. Fournier's avatar
Marc G. Fournier committed
419
	GISTPageOpaque opaque;
420

Marc G. Fournier's avatar
Marc G. Fournier committed
421 422 423
	buffer = ReadBuffer(r, blkno);
	page = (Page) BufferGetPage(buffer);
	opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
424

425 426
	if (!(opaque->flags & F_LEAF))
	{
Neil Conway's avatar
Neil Conway committed
427 428 429 430 431 432 433 434 435
        /*
         * This is an internal page, so continue to walk down the
         * tree. We find the child node that has the minimum insertion
         * penalty and recursively invoke ourselves to modify that
         * node. Once the recursive call returns, we may need to
         * adjust the parent node for two reasons: the child node
         * split, or the key in this node needs to be adjusted for the
         * newly inserted key below us.
         */
436
		ItemId		iid;
Marc G. Fournier's avatar
Marc G. Fournier committed
437 438
		BlockNumber nblkno;
		ItemPointerData oldtid;
439
		IndexTuple	oldtup;
Neil Conway's avatar
Neil Conway committed
440
		OffsetNumber child;
441 442

		child = gistchoose(r, page, *(*itup), giststate);
Marc G. Fournier's avatar
Marc G. Fournier committed
443 444 445 446
		iid = PageGetItemId(page, child);
		oldtup = (IndexTuple) PageGetItem(page, iid);
		nblkno = ItemPointerGetBlockNumber(&(oldtup->t_tid));

447 448 449
		/*
		 * After this call: 1. if child page was splited, then itup
		 * contains keys for each page 2. if  child page wasn't splited,
450
		 * then itup contains additional for adjustment of current key
Marc G. Fournier's avatar
Marc G. Fournier committed
451
		 */
452
		ret = gistlayerinsert(r, nblkno, itup, len, giststate);
453

Marc G. Fournier's avatar
Marc G. Fournier committed
454
		/* nothing inserted in child */
455 456
		if (!(ret & INSERTED))
		{
Marc G. Fournier's avatar
Marc G. Fournier committed
457
			ReleaseBuffer(buffer);
458
			return 0x00;
Marc G. Fournier's avatar
Marc G. Fournier committed
459
		}
460

Neil Conway's avatar
Neil Conway committed
461
		/* child did not split */
462 463 464
		if (!(ret & SPLITED))
		{
			IndexTuple	newtup = gistgetadjusted(r, oldtup, (*itup)[0], giststate);
465

466 467
			if (!newtup)
			{
Marc G. Fournier's avatar
Marc G. Fournier committed
468 469 470 471
				/* not need to update key */
				ReleaseBuffer(buffer);
				return 0x00;
			}
472

Marc G. Fournier's avatar
Marc G. Fournier committed
473 474
			(*itup)[0] = newtup;
		}
475

Neil Conway's avatar
Neil Conway committed
476 477 478 479 480 481
        /*
         * This node's key has been modified, either because a child
         * split occurred or because we needed to adjust our key for
         * an insert in a child node. Therefore, remove the old
         * version of this node's key.
         */
Marc G. Fournier's avatar
Marc G. Fournier committed
482
		ItemPointerSet(&oldtid, blkno, child);
483
		gistdelete(r, &oldtid);
Bruce Momjian's avatar
Bruce Momjian committed
484

485
		/*
Bruce Momjian's avatar
Bruce Momjian committed
486 487 488
		 * if child was splitted, new key for child will be inserted in
		 * the end list of child, so we must say to any scans that page is
		 * changed beginning from 'child' offset
489
		 */
Bruce Momjian's avatar
Bruce Momjian committed
490
		if (ret & SPLITED)
491
			gistadjscans(r, GISTOP_SPLIT, blkno, child);
Marc G. Fournier's avatar
Marc G. Fournier committed
492
	}
493

494
	ret = INSERTED;
Marc G. Fournier's avatar
Marc G. Fournier committed
495

496 497
	if (gistnospace(page, (*itup), *len))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
498
		/* no space for insertion */
499 500 501 502
		IndexTuple *itvec,
				   *newitup;
		int			tlen,
					oldlen;
Marc G. Fournier's avatar
Marc G. Fournier committed
503 504

		ret |= SPLITED;
505
		itvec = gistreadbuffer(buffer, &tlen);
506
		itvec = gistjoinvector(itvec, &tlen, (*itup), *len);
507
		oldlen = *len;
508
		newitup = gistSplit(r, buffer, itvec, &tlen, giststate);
509
		ReleaseBuffer(buffer);
510
		*itup = newitup;
511 512 513 514
		*len = tlen;			/* now tlen >= 2 */
	}
	else
	{
515
		/* enough space */
516 517
		OffsetNumber off,
					l;
Marc G. Fournier's avatar
Marc G. Fournier committed
518

519 520
		off = (PageIsEmpty(page)) ?
			FirstOffsetNumber
Marc G. Fournier's avatar
Marc G. Fournier committed
521
			:
522
			OffsetNumberNext(PageGetMaxOffsetNumber(page));
Neil Conway's avatar
Neil Conway committed
523
		l = gistwritebuffer(r, page, *itup, *len, off);
Marc G. Fournier's avatar
Marc G. Fournier committed
524
		WriteBuffer(buffer);
525

526
		if (*len > 1)
527
		{						/* previous insert ret & SPLITED != 0 */
528 529 530 531 532
			/*
			 * child was splited, so we must form union for insertion in
			 * parent
			 */
			IndexTuple	newtup = gistunion(r, (*itup), *len, giststate);
533
			ItemPointerSet(&(newtup->t_tid), blkno, 1);
Marc G. Fournier's avatar
Marc G. Fournier committed
534 535 536 537
			(*itup)[0] = newtup;
			*len = 1;
		}
	}
538

539 540 541 542
	return ret;
}

/*
Marc G. Fournier's avatar
Marc G. Fournier committed
543 544 545
 * Write itup vector to page, has no control of free space
 */
static OffsetNumber
546
gistwritebuffer(Relation r, Page page, IndexTuple *itup,
547
				int len, OffsetNumber off)
548
{
Marc G. Fournier's avatar
Marc G. Fournier committed
549
	OffsetNumber l = InvalidOffsetNumber;
550
	int			i;
551

552 553
	for (i = 0; i < len; i++)
	{
554
#ifdef GIST_PAGEADDITEM
Neil Conway's avatar
Neil Conway committed
555 556 557 558
		GISTENTRY	tmpdentry;
		IndexTuple	newtup;
		bool		IsNull;

559 560 561 562
		l = gistPageAddItem(giststate, r, page,
							(Item) itup[i], IndexTupleSize(itup[i]),
							off, LP_USED, &tmpdentry, &newtup);
		off = OffsetNumberNext(off);
563 564
#else
		l = PageAddItem(page, (Item) itup[i], IndexTupleSize(itup[i]),
565
						off, LP_USED);
566
		if (l == InvalidOffsetNumber)
567
			elog(ERROR, "failed to add index item to \"%s\"",
568 569
				 RelationGetRelationName(r));
#endif
Marc G. Fournier's avatar
Marc G. Fournier committed
570
	}
571
	return l;
Marc G. Fournier's avatar
Marc G. Fournier committed
572
}
573

Marc G. Fournier's avatar
Marc G. Fournier committed
574 575 576
/*
 * Check space for itup vector on page
 */
577
static bool
578 579
gistnospace(Page page, IndexTuple *itvec, int len)
{
Bruce Momjian's avatar
Bruce Momjian committed
580
	unsigned int size = 0;
581
	int			i;
582

583
	for (i = 0; i < len; i++)
584
		size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);
585 586 587

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

Marc G. Fournier's avatar
Marc G. Fournier committed
589 590 591 592
/*
 * Read buffer into itup vector
 */
static IndexTuple *
593
gistreadbuffer(Buffer buffer, int *len /* out */ )
594 595 596 597 598
{
	OffsetNumber i,
				maxoff;
	IndexTuple *itvec;
	Page		p = (Page) BufferGetPage(buffer);
599

Marc G. Fournier's avatar
Marc G. Fournier committed
600
	maxoff = PageGetMaxOffsetNumber(p);
601
	*len = maxoff;
602 603
	itvec = palloc(sizeof(IndexTuple) * maxoff);
	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
604
		itvec[i - 1] = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
605

Marc G. Fournier's avatar
Marc G. Fournier committed
606 607
	return itvec;
}
608

Marc G. Fournier's avatar
Marc G. Fournier committed
609 610 611 612
/*
 * join two vectors into one
 */
static IndexTuple *
613 614 615 616
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
617 618
	*len += addlen;
	return itvec;
619 620
}

Marc G. Fournier's avatar
Marc G. Fournier committed
621
/*
Neil Conway's avatar
Neil Conway committed
622 623
 * Return an IndexTuple containing the result of applying the "union"
 * method to the specified IndexTuple vector.
Marc G. Fournier's avatar
Marc G. Fournier committed
624 625
 */
static IndexTuple
626 627
gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
{
628
	Datum		attr[INDEX_MAX_KEYS];
629
	bool		isnull[INDEX_MAX_KEYS];
Bruce Momjian's avatar
Bruce Momjian committed
630
	GistEntryVector *evec;
Neil Conway's avatar
Neil Conway committed
631
	int			i;
632
	GISTENTRY	centry[INDEX_MAX_KEYS];
Marc G. Fournier's avatar
Marc G. Fournier committed
633

634
	evec = (GistEntryVector *) palloc(((len == 1) ? 2 : len) * sizeof(GISTENTRY) + GEVHDRSZ);
Marc G. Fournier's avatar
Marc G. Fournier committed
635

Neil Conway's avatar
Neil Conway committed
636
	for (i = 0; i < r->rd_att->natts; i++)
637
	{
Neil Conway's avatar
Neil Conway committed
638 639 640 641 642 643
		Datum		datum;
		int			j;
		int			real_len;

		real_len = 0;
		for (j = 0; j < len; j++)
644
		{
Neil Conway's avatar
Neil Conway committed
645 646
			bool		IsNull;
			datum = index_getattr(itvec[j], i + 1, giststate->tupdesc, &IsNull);
647 648
			if (IsNull)
				continue;
649

Neil Conway's avatar
Neil Conway committed
650 651
			gistdentryinit(giststate, i,
						   &(evec->vector[real_len]),
652
						   datum,
653
						   NULL, NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
654 655 656
						   ATTSIZE(datum, giststate->tupdesc, i + 1, IsNull),
						   FALSE, IsNull);
			real_len++;
657
		}
658

Neil Conway's avatar
Neil Conway committed
659 660
		/* If this tuple vector was all NULLs, the union is NULL */
		if (real_len == 0)
661
		{
Neil Conway's avatar
Neil Conway committed
662 663
			attr[i] = (Datum) 0;
			isnull[i] = TRUE;
664 665 666
		}
		else
		{
Neil Conway's avatar
Neil Conway committed
667 668 669
			int datumsize;

			if (real_len == 1)
670
			{
671 672
				evec->n = 2;
				gistentryinit(evec->vector[1],
Bruce Momjian's avatar
Bruce Momjian committed
673
							  evec->vector[0].key, r, NULL,
Neil Conway's avatar
Neil Conway committed
674
							  (OffsetNumber) 0, evec->vector[0].bytes, FALSE);
675
			}
676
			else
Neil Conway's avatar
Neil Conway committed
677 678 679 680
				evec->n = real_len;

			/* Compress the result of the union and store in attr array */
			datum = FunctionCall2(&giststate->unionFn[i],
681 682 683
								  PointerGetDatum(evec),
								  PointerGetDatum(&datumsize));

Neil Conway's avatar
Neil Conway committed
684
			gistcentryinit(giststate, i, &centry[i], datum,
685
						   NULL, NULL, (OffsetNumber) 0,
686
						   datumsize, FALSE, FALSE);
Neil Conway's avatar
Neil Conway committed
687 688
			isnull[i] = FALSE;
			attr[i] = centry[i].key;
689
		}
690
	}
691

Neil Conway's avatar
Neil Conway committed
692
	return index_form_tuple(giststate->tupdesc, attr, isnull);
693
}
694

695

Marc G. Fournier's avatar
Marc G. Fournier committed
696 697 698 699
/*
 * Forms union of oldtup and addtup, if union == oldtup then return NULL
 */
static IndexTuple
700 701
gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
{
Bruce Momjian's avatar
Bruce Momjian committed
702
	GistEntryVector *evec;
Neil Conway's avatar
Neil Conway committed
703 704
	bool		neednew = false;
	bool		isnull[INDEX_MAX_KEYS];
705 706 707 708
	Datum		attr[INDEX_MAX_KEYS];
	GISTENTRY	centry[INDEX_MAX_KEYS],
				oldatt[INDEX_MAX_KEYS],
				addatt[INDEX_MAX_KEYS],
709 710
			   *ev0p,
			   *ev1p;
711
	bool		oldisnull[INDEX_MAX_KEYS],
712
				addisnull[INDEX_MAX_KEYS];
713
	IndexTuple	newtup = NULL;
Neil Conway's avatar
Neil Conway committed
714
	int			i;
715

716 717 718 719
	evec = palloc(2 * sizeof(GISTENTRY) + GEVHDRSZ);
	evec->n = 2;
	ev0p = &(evec->vector[0]);
	ev1p = &(evec->vector[1]);
720

721
	gistDeCompressAtt(giststate, r, oldtup, NULL,
Neil Conway's avatar
Neil Conway committed
722
					  (OffsetNumber) 0, oldatt, oldisnull);
723

724
	gistDeCompressAtt(giststate, r, addtup, NULL,
Neil Conway's avatar
Neil Conway committed
725
					  (OffsetNumber) 0, addatt, addisnull);
726

Neil Conway's avatar
Neil Conway committed
727
	for (i = 0; i < r->rd_att->natts; i++)
728
	{
Neil Conway's avatar
Neil Conway committed
729
		if (oldisnull[i] && addisnull[i])
730
		{
Neil Conway's avatar
Neil Conway committed
731 732
			attr[i] = (Datum) 0;
			isnull[i] = TRUE;
733 734 735
		}
		else
		{
Neil Conway's avatar
Neil Conway committed
736 737
			Datum		datum;
			int			datumsize;
738

Neil Conway's avatar
Neil Conway committed
739 740 741 742
			FILLEV(oldisnull[i], oldatt[i].key, oldatt[i].bytes,
				   addisnull[i], addatt[i].key, addatt[i].bytes);

			datum = FunctionCall2(&giststate->unionFn[i],
743 744
								  PointerGetDatum(evec),
								  PointerGetDatum(&datumsize));
745

Neil Conway's avatar
Neil Conway committed
746
			if (oldisnull[i] || addisnull[i])
747
			{
Neil Conway's avatar
Neil Conway committed
748
				if (oldisnull[i])
749
					neednew = true;
750 751 752
			}
			else
			{
Neil Conway's avatar
Neil Conway committed
753 754 755
				bool	result;

				FunctionCall3(&giststate->equalFn[i],
756 757 758 759 760
							  ev0p->key,
							  datum,
							  PointerGetDatum(&result));

				if (!result)
761 762
					neednew = true;
			}
763

Neil Conway's avatar
Neil Conway committed
764
			gistcentryinit(giststate, i, &centry[i], datum,
765
						   NULL, NULL, (OffsetNumber) 0,
766 767
						   datumsize, FALSE, FALSE);

Neil Conway's avatar
Neil Conway committed
768 769
			attr[i] = centry[i].key;
			isnull[i] = FALSE;
770
		}
771
	}
772

773 774
	if (neednew)
	{
775
		/* need to update key */
776
		newtup = index_form_tuple(giststate->tupdesc, attr, isnull);
777
		newtup->t_tid = oldtup->t_tid;
Marc G. Fournier's avatar
Marc G. Fournier committed
778
	}
779

780 781
	return newtup;
}
782

783
static void
784 785
gistunionsubkey(Relation r, GISTSTATE *giststate, IndexTuple *itvec, GIST_SPLITVEC *spl)
{
Neil Conway's avatar
Neil Conway committed
786
	int lr;
787

Neil Conway's avatar
Neil Conway committed
788
	for (lr = 0; lr < 2; lr++)
789
	{
Neil Conway's avatar
Neil Conway committed
790 791 792 793 794 795 796 797
		OffsetNumber *entries;
		int			i;
		Datum	   *attr;
		int			len,
					*attrsize;
		bool	   *isnull;
		GistEntryVector *evec;

798 799
		if (lr)
		{
800 801 802 803
			attrsize = spl->spl_lattrsize;
			attr = spl->spl_lattr;
			len = spl->spl_nleft;
			entries = spl->spl_left;
804
			isnull = spl->spl_lisnull;
805 806 807
		}
		else
		{
808 809 810 811
			attrsize = spl->spl_rattrsize;
			attr = spl->spl_rattr;
			len = spl->spl_nright;
			entries = spl->spl_right;
812
			isnull = spl->spl_risnull;
813 814
		}

815
		evec = palloc(((len == 1) ? 2 : len) * sizeof(GISTENTRY) + GEVHDRSZ);
816

Neil Conway's avatar
Neil Conway committed
817
		for (i = 1; i < r->rd_att->natts; i++)
818
		{
Neil Conway's avatar
Neil Conway committed
819 820 821 822 823 824 825
			int			j;
			Datum		datum;
			int			datumsize;
			int			real_len;

			real_len = 0;
			for (j = 0; j < len; j++)
826
			{
Neil Conway's avatar
Neil Conway committed
827 828 829
				bool		IsNull;

				if (spl->spl_idgrp[entries[j]])
830
					continue;
Neil Conway's avatar
Neil Conway committed
831
				datum = index_getattr(itvec[entries[j] - 1], i + 1,
832
									  giststate->tupdesc, &IsNull);
833
				if (IsNull)
834
					continue;
Neil Conway's avatar
Neil Conway committed
835 836
				gistdentryinit(giststate, i,
							   &(evec->vector[real_len]),
837
							   datum,
838
							   NULL, NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
839 840 841
							   ATTSIZE(datum, giststate->tupdesc, i + 1, IsNull),
							   FALSE, IsNull);
				real_len++;
842 843

			}
Neil Conway's avatar
Neil Conway committed
844 845

			if (real_len == 0)
846 847 848
			{
				datum = (Datum) 0;
				datumsize = 0;
Neil Conway's avatar
Neil Conway committed
849
				isnull[i] = true;
850 851 852
			}
			else
			{
853
				/*
Bruce Momjian's avatar
Bruce Momjian committed
854 855
				 * evec->vector[0].bytes may be not defined, so form union
				 * with itself
856
				 */
Neil Conway's avatar
Neil Conway committed
857
				if (real_len == 1)
858
				{
859
					evec->n = 2;
Neil Conway's avatar
Neil Conway committed
860
					memcpy(&(evec->vector[1]), &(evec->vector[0]),
861 862 863
						   sizeof(GISTENTRY));
				}
				else
Neil Conway's avatar
Neil Conway committed
864 865
					evec->n = real_len;
				datum = FunctionCall2(&giststate->unionFn[i],
866 867
									  PointerGetDatum(evec),
									  PointerGetDatum(&datumsize));
Neil Conway's avatar
Neil Conway committed
868
				isnull[i] = false;
869
			}
870

Neil Conway's avatar
Neil Conway committed
871 872
			attr[i] = datum;
			attrsize[i] = datumsize;
873
		}
874
	}
875
}
876

877
/*
878
 * find group in vector with equal value
879 880
 */
static int
881 882
gistfindgroup(GISTSTATE *giststate, GISTENTRY *valvec, GIST_SPLITVEC *spl)
{
Neil Conway's avatar
Neil Conway committed
883
	int			i;
884 885 886 887 888 889 890 891
	int			curid = 1;

	/*
	 * first key is always not null (see gistinsert), so we may not check
	 * for nulls
	 */
	for (i = 0; i < spl->spl_nleft; i++)
	{
Neil Conway's avatar
Neil Conway committed
892 893 894 895
		int j;
		int len;
		bool result;

896 897
		if (spl->spl_idgrp[spl->spl_left[i]])
			continue;
898 899
		len = 0;
		/* find all equal value in right part */
900 901 902 903
		for (j = 0; j < spl->spl_nright; j++)
		{
			if (spl->spl_idgrp[spl->spl_right[j]])
				continue;
904
			FunctionCall3(&giststate->equalFn[0],
905 906
						  valvec[spl->spl_left[i]].key,
						  valvec[spl->spl_right[j]].key,
907
						  PointerGetDatum(&result));
908 909 910
			if (result)
			{
				spl->spl_idgrp[spl->spl_right[j]] = curid;
911 912 913 914
				len++;
			}
		}
		/* find all other equal value in left part */
915 916
		if (len)
		{
917
			/* add current val to list of equal values */
918
			spl->spl_idgrp[spl->spl_left[i]] = curid;
919
			/* searching .. */
920 921 922 923
			for (j = i + 1; j < spl->spl_nleft; j++)
			{
				if (spl->spl_idgrp[spl->spl_left[j]])
					continue;
924
				FunctionCall3(&giststate->equalFn[0],
925 926
							  valvec[spl->spl_left[i]].key,
							  valvec[spl->spl_left[j]].key,
927
							  PointerGetDatum(&result));
928 929 930
				if (result)
				{
					spl->spl_idgrp[spl->spl_left[j]] = curid;
931 932 933
					len++;
				}
			}
934
			spl->spl_ngrp[curid] = len + 1;
935 936 937
			curid++;
		}
	}
Marc G. Fournier's avatar
Marc G. Fournier committed
938

939
	return curid;
Marc G. Fournier's avatar
Marc G. Fournier committed
940
}
941

942
/*
Neil Conway's avatar
Neil Conway committed
943 944
 * Insert equivalent tuples to left or right page with minimum
 * penalty
945 946 947
 */
static void
gistadjsubkey(Relation r,
948 949 950
			  IndexTuple *itup, /* contains compressed entry */
			  int *len,
			  GIST_SPLITVEC *v,
951
			  GISTSTATE *giststate)
952 953 954 955 956 957 958 959 960
{
	int			curlen;
	OffsetNumber *curwpos;
	GISTENTRY	entry,
				identry[INDEX_MAX_KEYS],
			   *ev0p,
			   *ev1p;
	float		lpenalty,
				rpenalty;
Bruce Momjian's avatar
Bruce Momjian committed
961
	GistEntryVector *evec;
962 963 964 965
	int			datumsize;
	bool		isnull[INDEX_MAX_KEYS];
	int			i,
				j;
966 967 968 969

	/* clear vectors */
	curlen = v->spl_nleft;
	curwpos = v->spl_left;
970
	for (i = 0; i < v->spl_nleft; i++)
Neil Conway's avatar
Neil Conway committed
971
	{
972 973
		if (v->spl_idgrp[v->spl_left[i]] == 0)
		{
974 975
			*curwpos = v->spl_left[i];
			curwpos++;
976 977
		}
		else
978
			curlen--;
Neil Conway's avatar
Neil Conway committed
979
	}
980 981 982 983
	v->spl_nleft = curlen;

	curlen = v->spl_nright;
	curwpos = v->spl_right;
984
	for (i = 0; i < v->spl_nright; i++)
Neil Conway's avatar
Neil Conway committed
985
	{
986 987
		if (v->spl_idgrp[v->spl_right[i]] == 0)
		{
988 989
			*curwpos = v->spl_right[i];
			curwpos++;
990 991
		}
		else
992
			curlen--;
Neil Conway's avatar
Neil Conway committed
993
	}
994 995
	v->spl_nright = curlen;

996 997 998 999
	evec = palloc(2 * sizeof(GISTENTRY) + GEVHDRSZ);
	evec->n = 2;
	ev0p = &(evec->vector[0]);
	ev1p = &(evec->vector[1]);
1000 1001

	/* add equivalent tuple */
1002 1003
	for (i = 0; i < *len; i++)
	{
Neil Conway's avatar
Neil Conway committed
1004 1005
		Datum		datum;

1006
		if (v->spl_idgrp[i + 1] == 0)	/* already inserted */
1007
			continue;
1008
		gistDeCompressAtt(giststate, r, itup[i], NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
1009
						  identry, isnull);
1010

1011 1012
		v->spl_ngrp[v->spl_idgrp[i + 1]]--;
		if (v->spl_ngrp[v->spl_idgrp[i + 1]] == 0 &&
Neil Conway's avatar
Neil Conway committed
1013
			(v->spl_grpflag[v->spl_idgrp[i + 1]] & BOTH_ADDED) != BOTH_ADDED)
1014
		{
1015 1016
			/* force last in group */
			rpenalty = 1.0;
1017 1018 1019 1020 1021 1022 1023
			lpenalty = (v->spl_grpflag[v->spl_idgrp[i + 1]] & LEFT_ADDED) ? 2.0 : 0.0;
		}
		else
		{
			/* where? */
			for (j = 1; j < r->rd_att->natts; j++)
			{
1024
				gistentryinit(entry, v->spl_lattr[j], r, NULL,
1025 1026 1027 1028
						   (OffsetNumber) 0, v->spl_lattrsize[j], FALSE);
				gistpenalty(giststate, j, &entry, v->spl_lisnull[j],
							&identry[j], isnull[j], &lpenalty);

1029
				gistentryinit(entry, v->spl_rattr[j], r, NULL,
1030 1031 1032 1033 1034
						   (OffsetNumber) 0, v->spl_rattrsize[j], FALSE);
				gistpenalty(giststate, j, &entry, v->spl_risnull[j],
							&identry[j], isnull[j], &rpenalty);

				if (lpenalty != rpenalty)
1035 1036 1037
					break;
			}
		}
Neil Conway's avatar
Neil Conway committed
1038 1039 1040 1041 1042

		/*
		 * add
		 * XXX: refactor this to avoid duplicating code
		 */
1043 1044 1045 1046
		if (lpenalty < rpenalty)
		{
			v->spl_grpflag[v->spl_idgrp[i + 1]] |= LEFT_ADDED;
			v->spl_left[v->spl_nleft] = i + 1;
1047
			v->spl_nleft++;
1048 1049 1050 1051
			for (j = 1; j < r->rd_att->natts; j++)
			{
				if (isnull[j] && v->spl_lisnull[j])
				{
1052 1053
					v->spl_lattr[j] = (Datum) 0;
					v->spl_lattrsize[j] = 0;
1054 1055 1056
				}
				else
				{
Neil Conway's avatar
Neil Conway committed
1057 1058
					FILLEV(v->spl_lisnull[j], v->spl_lattr[j], v->spl_lattrsize[j],
						   isnull[j], identry[j].key, identry[j].bytes);
1059 1060

					datum = FunctionCall2(&giststate->unionFn[j],
1061 1062
										  PointerGetDatum(evec),
										  PointerGetDatum(&datumsize));
1063 1064 1065 1066 1067 1068

					v->spl_lattr[j] = datum;
					v->spl_lattrsize[j] = datumsize;
					v->spl_lisnull[j] = false;
				}
			}
1069 1070 1071 1072 1073
		}
		else
		{
			v->spl_grpflag[v->spl_idgrp[i + 1]] |= RIGHT_ADDED;
			v->spl_right[v->spl_nright] = i + 1;
1074
			v->spl_nright++;
1075 1076 1077 1078
			for (j = 1; j < r->rd_att->natts; j++)
			{
				if (isnull[j] && v->spl_risnull[j])
				{
1079 1080
					v->spl_rattr[j] = (Datum) 0;
					v->spl_rattrsize[j] = 0;
1081 1082 1083
				}
				else
				{
Neil Conway's avatar
Neil Conway committed
1084 1085
					FILLEV(v->spl_risnull[j], v->spl_rattr[j], v->spl_rattrsize[j],
						   isnull[j], identry[j].key, identry[j].bytes);
1086 1087

					datum = FunctionCall2(&giststate->unionFn[j],
1088 1089
										  PointerGetDatum(evec),
										  PointerGetDatum(&datumsize));
1090 1091 1092 1093 1094 1095

					v->spl_rattr[j] = datum;
					v->spl_rattrsize[j] = datumsize;
					v->spl_risnull[j] = false;
				}
			}
1096
		}
1097 1098 1099
	}
}

1100
/*
1101
 *	gistSplit -- split a page in the tree.
1102
 */
Marc G. Fournier's avatar
Marc G. Fournier committed
1103
static IndexTuple *
1104
gistSplit(Relation r,
1105
		  Buffer buffer,
Marc G. Fournier's avatar
Marc G. Fournier committed
1106 1107
		  IndexTuple *itup,		/* contains compressed entry */
		  int *len,
1108
		  GISTSTATE *giststate)
1109
{
1110
	Page		p;
1111 1112 1113 1114 1115 1116 1117 1118 1119
	Buffer		leftbuf,
				rightbuf;
	Page		left,
				right;
	IndexTuple *lvectup,
			   *rvectup,
			   *newtup;
	BlockNumber lbknum,
				rbknum;
1120 1121
	GISTPageOpaque opaque;
	GIST_SPLITVEC v;
Bruce Momjian's avatar
Bruce Momjian committed
1122
	GistEntryVector *entryvec;
1123
	int			i,
1124
				nlen;
1125 1126 1127 1128 1129 1130 1131 1132 1133

	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.
	 */
Neil Conway's avatar
Neil Conway committed
1134
	if (BufferGetBlockNumber(buffer) == GIST_ROOT_BLKNO)
1135 1136 1137 1138 1139
	{
		leftbuf = ReadBuffer(r, P_NEW);
		GISTInitBuffer(leftbuf, opaque->flags);
		lbknum = BufferGetBlockNumber(leftbuf);
		left = (Page) BufferGetPage(leftbuf);
1140
	}
1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154
	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 */
1155 1156
	entryvec = palloc(GEVHDRSZ + (*len + 1) * sizeof(GISTENTRY));
	entryvec->n = *len + 1;
Neil Conway's avatar
Neil Conway committed
1157

Marc G. Fournier's avatar
Marc G. Fournier committed
1158
	for (i = 1; i <= *len; i++)
1159
	{
Neil Conway's avatar
Neil Conway committed
1160 1161 1162
		Datum		datum;
		bool		IsNull;

1163
		datum = index_getattr(itup[i - 1], 1, giststate->tupdesc, &IsNull);
1164
		gistdentryinit(giststate, 0, &(entryvec->vector[i]),
1165
					   datum, r, p, i,
Neil Conway's avatar
Neil Conway committed
1166 1167
					   ATTSIZE(datum, giststate->tupdesc, 1, IsNull),
					   FALSE, IsNull);
1168 1169
	}

1170 1171 1172 1173
	/*
	 * now let the user-defined picksplit function set up the split
	 * vector; in entryvec have no null value!!
	 */
1174
	FunctionCall2(&giststate->picksplitFn[0],
1175 1176
				  PointerGetDatum(entryvec),
				  PointerGetDatum(&v));
1177

1178 1179 1180 1181 1182 1183 1184
	/* compatibility with old code */
	if (v.spl_left[v.spl_nleft - 1] == InvalidOffsetNumber)
		v.spl_left[v.spl_nleft - 1] = (OffsetNumber) *len;
	if (v.spl_right[v.spl_nright - 1] == InvalidOffsetNumber)
		v.spl_right[v.spl_nright - 1] = (OffsetNumber) *len;

	v.spl_lattr[0] = v.spl_ldatum;
1185
	v.spl_rattr[0] = v.spl_rdatum;
1186 1187
	v.spl_lisnull[0] = false;
	v.spl_risnull[0] = false;
1188

1189 1190 1191 1192 1193 1194
	/*
	 * if index is multikey, then we must to try get smaller bounding box
	 * for subkey(s)
	 */
	if (r->rd_att->natts > 1)
	{
Neil Conway's avatar
Neil Conway committed
1195 1196
		int			MaxGrpId;

1197 1198
		v.spl_idgrp = (int *) palloc0(sizeof(int) * (*len + 1));
		v.spl_grpflag = (char *) palloc0(sizeof(char) * (*len + 1));
1199
		v.spl_ngrp = (int *) palloc(sizeof(int) * (*len + 1));
1200

1201
		MaxGrpId = gistfindgroup(giststate, entryvec->vector, &v);
1202 1203

		/* form union of sub keys for each page (l,p) */
1204
		gistunionsubkey(r, giststate, itup, &v);
1205

1206 1207 1208 1209 1210 1211 1212
		/*
		 * if possible, we insert equivalent tuples with control by
		 * penalty for a subkey(s)
		 */
		if (MaxGrpId > 1)
			gistadjsubkey(r, itup, len, &v, giststate);
	}
1213

Marc G. Fournier's avatar
Marc G. Fournier committed
1214
	/* form left and right vector */
1215 1216
	lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nleft);
	rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nright);
1217

1218 1219
	for (i = 0; i < v.spl_nleft; i++)
		lvectup[i] = itup[v.spl_left[i] - 1];
1220

1221 1222
	for (i = 0; i < v.spl_nright; i++)
		rvectup[i] = itup[v.spl_right[i] - 1];
1223

1224

Neil Conway's avatar
Neil Conway committed
1225
	/* write on disk (may need another split) */
1226 1227
	if (gistnospace(right, rvectup, v.spl_nright))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
1228
		nlen = v.spl_nright;
1229
		newtup = gistSplit(r, rightbuf, rvectup, &nlen, giststate);
1230 1231 1232 1233
		ReleaseBuffer(rightbuf);
	}
	else
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
1234
		OffsetNumber l;
1235

1236
		l = gistwritebuffer(r, right, rvectup, v.spl_nright, FirstOffsetNumber);
Marc G. Fournier's avatar
Marc G. Fournier committed
1237 1238 1239
		WriteBuffer(rightbuf);

		nlen = 1;
1240
		newtup = (IndexTuple *) palloc(sizeof(IndexTuple) * 1);
1241
		newtup[0] = gistFormTuple(giststate, r, v.spl_rattr, v.spl_rattrsize, v.spl_risnull);
Marc G. Fournier's avatar
Marc G. Fournier committed
1242
		ItemPointerSet(&(newtup[0]->t_tid), rbknum, 1);
1243 1244
	}

1245 1246 1247
	if (gistnospace(left, lvectup, v.spl_nleft))
	{
		int			llen = v.spl_nleft;
Marc G. Fournier's avatar
Marc G. Fournier committed
1248 1249
		IndexTuple *lntup;

1250
		lntup = gistSplit(r, leftbuf, lvectup, &llen, giststate);
1251
		ReleaseBuffer(leftbuf);
Marc G. Fournier's avatar
Marc G. Fournier committed
1252

1253 1254 1255 1256
		newtup = gistjoinvector(newtup, &nlen, lntup, llen);
	}
	else
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
1257
		OffsetNumber l;
1258

1259
		l = gistwritebuffer(r, left, lvectup, v.spl_nleft, FirstOffsetNumber);
Neil Conway's avatar
Neil Conway committed
1260
		if (BufferGetBlockNumber(buffer) != GIST_ROOT_BLKNO)
Marc G. Fournier's avatar
Marc G. Fournier committed
1261 1262 1263 1264 1265
			PageRestoreTempPage(left, p);

		WriteBuffer(leftbuf);

		nlen += 1;
Neil Conway's avatar
Neil Conway committed
1266
		newtup = (IndexTuple *) repalloc(newtup, sizeof(IndexTuple) * nlen);
1267
		newtup[nlen - 1] = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lattrsize, v.spl_lisnull);
1268
		ItemPointerSet(&(newtup[nlen - 1]->t_tid), lbknum, 1);
1269 1270
	}

Marc G. Fournier's avatar
Marc G. Fournier committed
1271 1272
	*len = nlen;
	return newtup;
1273
}
1274 1275

static void
1276
gistnewroot(Relation r, IndexTuple *itup, int len)
1277
{
1278 1279
	Buffer		b;
	Page		p;
1280

Neil Conway's avatar
Neil Conway committed
1281
	b = ReadBuffer(r, GIST_ROOT_BLKNO);
1282 1283
	GISTInitBuffer(b, 0);
	p = BufferGetPage(b);
1284

1285
	gistwritebuffer(r, p, itup, len, FirstOffsetNumber);
1286
	WriteBuffer(b);
1287 1288 1289 1290 1291
}

static void
GISTInitBuffer(Buffer b, uint32 f)
{
1292 1293 1294
	GISTPageOpaque opaque;
	Page		page;
	Size		pageSize;
1295 1296 1297 1298 1299 1300 1301

	pageSize = BufferGetPageSize(b);
	page = BufferGetPage(b);
	PageInit(page, pageSize, sizeof(GISTPageOpaqueData));

	opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
	opaque->flags = f;
1302 1303 1304
}

/*
1305 1306
 * find entry with lowest penalty
 */
1307
static OffsetNumber
1308
gistchoose(Relation r, Page p, IndexTuple it,	/* it has compressed entry */
1309
		   GISTSTATE *giststate)
1310
{
1311 1312 1313
	OffsetNumber maxoff;
	OffsetNumber i;
	OffsetNumber which;
1314 1315
	float		sum_grow,
				which_grow[INDEX_MAX_KEYS];
1316
	GISTENTRY	entry,
1317
				identry[INDEX_MAX_KEYS];
Neil Conway's avatar
Neil Conway committed
1318
	bool		isnull[INDEX_MAX_KEYS];
1319 1320

	maxoff = PageGetMaxOffsetNumber(p);
1321
	*which_grow = -1.0;
1322
	which = -1;
1323 1324
	sum_grow = 1;
	gistDeCompressAtt(giststate, r,
1325
					  it, NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
1326
					  identry, isnull);
1327

1328
	for (i = FirstOffsetNumber; i <= maxoff && sum_grow; i = OffsetNumberNext(i))
1329
	{
Neil Conway's avatar
Neil Conway committed
1330
		int			j;
1331 1332 1333 1334 1335
		IndexTuple	itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));

		sum_grow = 0;
		for (j = 0; j < r->rd_att->natts; j++)
		{
Neil Conway's avatar
Neil Conway committed
1336 1337 1338
			Datum		datum;
			float		usize;
			bool		IsNull;
1339

Neil Conway's avatar
Neil Conway committed
1340 1341 1342 1343 1344 1345
			datum = index_getattr(itup, j + 1, giststate->tupdesc, &IsNull);
			gistdentryinit(giststate, j, &entry, datum, r, p, i,
						   ATTSIZE(datum, giststate->tupdesc, j + 1, IsNull),
						   FALSE, IsNull);
			gistpenalty(giststate, j, &entry, IsNull,
						&identry[j], isnull[j], &usize);
1346

1347 1348
			if (which_grow[j] < 0 || usize < which_grow[j])
			{
1349 1350
				which = i;
				which_grow[j] = usize;
1351 1352 1353 1354 1355
				if (j < r->rd_att->natts - 1 && i == FirstOffsetNumber)
					which_grow[j + 1] = -1;
				sum_grow += which_grow[j];
			}
			else if (which_grow[j] == usize)
1356
				sum_grow += usize;
1357 1358 1359
			else
			{
				sum_grow = 1;
1360
				break;
1361
			}
1362
		}
1363
	}
1364

1365
	return which;
1366 1367
}

1368
/*
1369 1370 1371 1372 1373 1374 1375 1376
 * Retail deletion of a single tuple.
 *
 * NB: this is no longer called externally, but is still needed by
 * gistlayerinsert().  That dependency will have to be fixed if GIST
 * is ever going to allow concurrent insertions.
 */
static void
gistdelete(Relation r, ItemPointer tid)
1377
{
1378 1379 1380 1381
	BlockNumber blkno;
	OffsetNumber offnum;
	Buffer		buf;
	Page		page;
1382

Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
1383
	/*
1384
	 * Since GIST is not marked "amconcurrent" in pg_am, caller should
1385
	 * have acquired exclusive lock on index relation.	We need no locking
1386
	 * here.
Vadim B. Mikheev's avatar
Vadim B. Mikheev committed
1387
	 */
1388 1389 1390 1391 1392

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

	/* adjust any scans that will be affected by this deletion */
1393
	/* NB: this works only for scans in *this* backend! */
1394 1395 1396 1397 1398 1399 1400 1401 1402
	gistadjscans(r, GISTOP_DEL, blkno, offnum);

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

	PageIndexTupleDelete(page, offnum);

	WriteBuffer(buf);
1403
}
1404

1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418
/*
 * Bulk deletion of all index entries pointing to a set of heap tuples.
 * The set of target tuples is specified via a callback routine that tells
 * whether any given heap tuple (identified by ItemPointer) is being deleted.
 *
 * Result: a palloc'd struct containing statistical info for VACUUM displays.
 */
Datum
gistbulkdelete(PG_FUNCTION_ARGS)
{
	Relation	rel = (Relation) PG_GETARG_POINTER(0);
	IndexBulkDeleteCallback callback = (IndexBulkDeleteCallback) PG_GETARG_POINTER(1);
	void	   *callback_state = (void *) PG_GETARG_POINTER(2);
	IndexBulkDeleteResult *result;
1419
	BlockNumber num_pages;
1420 1421 1422 1423 1424 1425 1426 1427 1428
	double		tuples_removed;
	double		num_index_tuples;
	IndexScanDesc iscan;

	tuples_removed = 0;
	num_index_tuples = 0;

	/*
	 * Since GIST is not marked "amconcurrent" in pg_am, caller should
1429
	 * have acquired exclusive lock on index relation.	We need no locking
1430 1431 1432 1433 1434 1435 1436 1437
	 * here.
	 */

	/*
	 * XXX generic implementation --- should be improved!
	 */

	/* walk through the entire index */
1438
	iscan = index_beginscan(NULL, rel, SnapshotAny, 0, NULL);
1439 1440
	/* including killed tuples */
	iscan->ignore_killed_tuples = false;
1441

1442
	while (index_getnext_indexitem(iscan, ForwardScanDirection))
1443
	{
1444 1445
		vacuum_delay_point();

1446
		if (callback(&iscan->xs_ctup.t_self, callback_state))
1447
		{
1448
			ItemPointerData indextup = iscan->currentItemData;
1449 1450 1451 1452 1453
			BlockNumber blkno;
			OffsetNumber offnum;
			Buffer		buf;
			Page		page;

1454 1455
			blkno = ItemPointerGetBlockNumber(&indextup);
			offnum = ItemPointerGetOffsetNumber(&indextup);
1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478

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

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

			PageIndexTupleDelete(page, offnum);

			WriteBuffer(buf);

			tuples_removed += 1;
		}
		else
			num_index_tuples += 1;
	}

	index_endscan(iscan);

	/* return statistics */
	num_pages = RelationGetNumberOfBlocks(rel);

1479
	result = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
1480 1481
	result->num_pages = num_pages;
	result->num_index_tuples = num_index_tuples;
1482
	result->tuples_removed = tuples_removed;
1483 1484

	PG_RETURN_POINTER(result);
1485 1486
}

1487
void
1488
initGISTstate(GISTSTATE *giststate, Relation index)
1489
{
1490
	int			i;
1491

1492
	if (index->rd_att->natts > INDEX_MAX_KEYS)
1493
		elog(ERROR, "numberOfAttributes %d > %d",
1494 1495
			 index->rd_att->natts, INDEX_MAX_KEYS);

1496
	giststate->tupdesc = index->rd_att;
1497

1498 1499
	for (i = 0; i < index->rd_att->natts; i++)
	{
1500
		fmgr_info_copy(&(giststate->consistentFn[i]),
Neil Conway's avatar
Neil Conway committed
1501
					   index_getprocinfo(index, i + 1, GIST_CONSISTENT_PROC),
1502 1503
					   CurrentMemoryContext);
		fmgr_info_copy(&(giststate->unionFn[i]),
1504
					   index_getprocinfo(index, i + 1, GIST_UNION_PROC),
1505 1506
					   CurrentMemoryContext);
		fmgr_info_copy(&(giststate->compressFn[i]),
Neil Conway's avatar
Neil Conway committed
1507
					   index_getprocinfo(index, i + 1, GIST_COMPRESS_PROC),
1508 1509
					   CurrentMemoryContext);
		fmgr_info_copy(&(giststate->decompressFn[i]),
Neil Conway's avatar
Neil Conway committed
1510
					   index_getprocinfo(index, i + 1, GIST_DECOMPRESS_PROC),
1511 1512
					   CurrentMemoryContext);
		fmgr_info_copy(&(giststate->penaltyFn[i]),
1513
					   index_getprocinfo(index, i + 1, GIST_PENALTY_PROC),
1514 1515
					   CurrentMemoryContext);
		fmgr_info_copy(&(giststate->picksplitFn[i]),
Neil Conway's avatar
Neil Conway committed
1516
					   index_getprocinfo(index, i + 1, GIST_PICKSPLIT_PROC),
1517 1518
					   CurrentMemoryContext);
		fmgr_info_copy(&(giststate->equalFn[i]),
1519
					   index_getprocinfo(index, i + 1, GIST_EQUAL_PROC),
1520
					   CurrentMemoryContext);
1521
	}
1522
}
1523

1524
void
1525 1526
freeGISTstate(GISTSTATE *giststate)
{
1527
	/* no work */
1528 1529
}

1530
#ifdef GIST_PAGEADDITEM
1531
/*
1532 1533 1534 1535 1536 1537
 * 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 or if the null status changes.
 *
 * XXX this only works for a single-column index tuple!
 */
1538
static IndexTuple
1539 1540
gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
{
1541 1542
	bool		IsNull;
	Datum		datum = index_getattr(t, 1, r->rd_att, &IsNull);
1543

1544 1545
	/*
	 * If new entry fits in index tuple, copy it in.  To avoid worrying
1546
	 * about null-value bitmask, pass it off to the general
1547
	 * index_form_tuple routine if either the previous or new value is
1548
	 * NULL.
1549 1550 1551
	 */
	if (!IsNull && DatumGetPointer(entry.key) != NULL &&
		(Size) entry.bytes <= ATTSIZE(datum, r, 1, IsNull))
1552
	{
1553 1554 1555
		memcpy(DatumGetPointer(datum),
			   DatumGetPointer(entry.key),
			   entry.bytes);
1556
		/* clear out old size */
1557
		t->t_info &= ~INDEX_SIZE_MASK;
1558 1559 1560
		/* or in new size */
		t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));

1561
		return t;
1562 1563 1564 1565
	}
	else
	{
		/* generate a new index tuple for the compressed entry */
1566 1567
		TupleDesc	tupDesc = r->rd_att;
		IndexTuple	newtup;
1568
		bool		isnull;
1569

1570 1571
		isnull = (DatumGetPointer(entry.key) == NULL);
		newtup = index_form_tuple(tupDesc, &(entry.key), &isnull);
1572
		newtup->t_tid = t->t_tid;
1573
		return newtup;
1574
	}
1575
}
1576
#endif
1577 1578

/*
1579 1580
 * initialize a GiST entry with a decompressed version of key
 */
1581
void
1582 1583
gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
			   Datum k, Relation r, Page pg, OffsetNumber o,
1584
			   int b, bool l, bool isNull)
1585
{
1586
	if (b && !isNull)
1587
	{
1588 1589 1590 1591 1592
		GISTENTRY  *dep;

		gistentryinit(*e, k, r, pg, o, b, l);
		dep = (GISTENTRY *)
			DatumGetPointer(FunctionCall1(&giststate->decompressFn[nkey],
1593
										  PointerGetDatum(e)));
1594 1595 1596 1597
		/* decompressFn may just return the given pointer */
		if (dep != e)
			gistentryinit(*e, dep->key, dep->rel, dep->page, dep->offset,
						  dep->bytes, dep->leafkey);
1598
	}
1599 1600
	else
		gistentryinit(*e, (Datum) 0, r, pg, o, 0, l);
1601 1602 1603 1604
}


/*
1605 1606
 * initialize a GiST entry with a compressed version of key
 */
1607
static void
1608 1609
gistcentryinit(GISTSTATE *giststate, int nkey,
			   GISTENTRY *e, Datum k, Relation r,
1610
			   Page pg, OffsetNumber o, int b, bool l, bool isNull)
1611
{
1612
	if (!isNull)
1613
	{
1614 1615 1616 1617 1618
		GISTENTRY  *cep;

		gistentryinit(*e, k, r, pg, o, b, l);
		cep = (GISTENTRY *)
			DatumGetPointer(FunctionCall1(&giststate->compressFn[nkey],
1619
										  PointerGetDatum(e)));
1620 1621
		/* compressFn may just return the given pointer */
		if (cep != e)
1622 1623
			gistentryinit(*e, cep->key, cep->rel, cep->page, cep->offset,
						  cep->bytes, cep->leafkey);
1624
	}
1625 1626
	else
		gistentryinit(*e, (Datum) 0, r, pg, o, 0, l);
1627
}
1628

1629
static IndexTuple
1630 1631
gistFormTuple(GISTSTATE *giststate, Relation r,
			  Datum attdata[], int datumsize[], bool isnull[])
1632
{
1633 1634
	GISTENTRY	centry[INDEX_MAX_KEYS];
	Datum		compatt[INDEX_MAX_KEYS];
Neil Conway's avatar
Neil Conway committed
1635
	int			i;
1636

Neil Conway's avatar
Neil Conway committed
1637
	for (i = 0; i < r->rd_att->natts; i++)
1638
	{
Neil Conway's avatar
Neil Conway committed
1639 1640
		if (isnull[i])
			compatt[i] = (Datum) 0;
1641 1642
		else
		{
Neil Conway's avatar
Neil Conway committed
1643
			gistcentryinit(giststate, i, &centry[i], attdata[i],
1644
						   NULL, NULL, (OffsetNumber) 0,
Neil Conway's avatar
Neil Conway committed
1645 1646
						   datumsize[i], FALSE, FALSE);
			compatt[i] = centry[i].key;
1647
		}
1648 1649
	}

Neil Conway's avatar
Neil Conway committed
1650
	return index_form_tuple(giststate->tupdesc, compatt, isnull);
1651
}
1652

1653
static void
1654
gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
Neil Conway's avatar
Neil Conway committed
1655
				  OffsetNumber o, GISTENTRY *attdata, bool *isnull)
1656 1657
{
	int			i;
1658

1659 1660
	for (i = 0; i < r->rd_att->natts; i++)
	{
Neil Conway's avatar
Neil Conway committed
1661
		Datum datum = index_getattr(tuple, i + 1, giststate->tupdesc, &isnull[i]);
1662
		gistdentryinit(giststate, i, &attdata[i],
1663
					   datum, r, p, o,
Neil Conway's avatar
Neil Conway committed
1664 1665
					   ATTSIZE(datum, giststate->tupdesc, i + 1, isnull[i]),
					   FALSE, isnull[i]);
1666
	}
1667
}
1668

1669
static void
1670 1671 1672 1673 1674 1675 1676
gistpenalty(GISTSTATE *giststate, int attno,
			GISTENTRY *key1, bool isNull1,
			GISTENTRY *key2, bool isNull2, float *penalty)
{
	if (giststate->penaltyFn[attno].fn_strict && (isNull1 || isNull2))
		*penalty = 0.0;
	else
1677
		FunctionCall3(&giststate->penaltyFn[attno],
1678 1679 1680
					  PointerGetDatum(key1),
					  PointerGetDatum(key2),
					  PointerGetDatum(penalty));
1681
}
1682

1683
#ifdef GISTDEBUG
Marc G. Fournier's avatar
Marc G. Fournier committed
1684 1685
static void
gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff)
1686
{
Marc G. Fournier's avatar
Marc G. Fournier committed
1687
	Buffer		buffer;
1688
	Page		page;
Marc G. Fournier's avatar
Marc G. Fournier committed
1689 1690
	GISTPageOpaque opaque;
	IndexTuple	which;
1691 1692 1693 1694 1695
	ItemId		iid;
	OffsetNumber i,
				maxoff;
	BlockNumber cblk;
	char	   *pred;
1696

1697
	pred = (char *) palloc(sizeof(char) * level + 1);
Marc G. Fournier's avatar
Marc G. Fournier committed
1698
	MemSet(pred, '\t', level);
1699
	pred[level] = '\0';
1700

Marc G. Fournier's avatar
Marc G. Fournier committed
1701 1702 1703
	buffer = ReadBuffer(r, blk);
	page = (Page) BufferGetPage(buffer);
	opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1704 1705 1706

	maxoff = PageGetMaxOffsetNumber(page);

1707
	elog(DEBUG4, "%sPage: %d %s blk: %d maxoff: %d free: %d", pred,
1708 1709
		 coff, (opaque->flags & F_LEAF) ? "LEAF" : "INTE", (int) blk,
		 (int) maxoff, PageGetFreeSpace(page));
1710 1711 1712

	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
	{
Marc G. Fournier's avatar
Marc G. Fournier committed
1713 1714 1715
		iid = PageGetItemId(page, i);
		which = (IndexTuple) PageGetItem(page, iid);
		cblk = ItemPointerGetBlockNumber(&(which->t_tid));
1716
#ifdef PRINTTUPLE
1717
		elog(DEBUG4, "%s  Tuple. blk: %d size: %d", pred, (int) cblk,
1718
			 IndexTupleSize(which));
1719 1720 1721 1722
#endif

		if (!(opaque->flags & F_LEAF))
			gist_dumptree(r, level + 1, cblk, i);
1723
	}
Marc G. Fournier's avatar
Marc G. Fournier committed
1724 1725
	ReleaseBuffer(buffer);
	pfree(pred);
1726
}
1727
#endif   /* defined GISTDEBUG */
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1728 1729 1730 1731

void
gist_redo(XLogRecPtr lsn, XLogRecord *record)
{
1732
	elog(PANIC, "gist_redo: unimplemented");
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1733
}
1734

Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1735 1736 1737
void
gist_undo(XLogRecPtr lsn, XLogRecord *record)
{
1738
	elog(PANIC, "gist_undo: unimplemented");
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1739
}
1740

Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1741
void
1742
gist_desc(char *buf, uint8 xl_info, char *rec)
Vadim B. Mikheev's avatar
WAL  
Vadim B. Mikheev committed
1743 1744
{
}